問題リンク この解法、結構時間かかるので流石に本番では選べないか……？ $N \leq 3000$ なので $Ο(N^2 log N)$ は通しにくい($Ο(N^3)$ でも枝刈すると通るらしいけど……)。 なるべく情報 $2$ 個で通らないだろうか？ 考えたこと $\frac{1}{2^i}$ を選ぶ部分和…

問題リンク 自分と同じ解法で通してる解説がなくて「？」になったのでやり方を書き残します。 とりあえず「組み合わせにおける個数」「組み合わせに含まれる品物の数」がわかればいいです。なので部分和 dp に個数の軸を加えて $dp[i][j][k]$ = $i - 1$ 番目…

https://atcoder.jp/contests/abc142/tasks/abc142_e 最近、水色問題を頑張っています。 面白い問題があったので貼り付けますが、割と典型な気がするので特に需要は無いです。 問題概要 鍵がたくさんあり、それぞれに値段と開けられる宝箱が決まっているので…

atcoder.jp 車校でABC/ARCに出ていない間に灰色が10個くらい増えていたので、灰色全完奪還ついでに一番気に入った問題の解説です。とはいえARC灰ですが。 問題概要 制約を満たすカードへの数字の書き込み方を数え上げてmodを取るだけです。 とはいえその制約…

ABC209 感想、解説

白羽です。 このアカウント、なんか昔ちょっとだけ書いて忘れ去られてたみたいです。 AtCoderの備忘録とか書きたいので記事全消しして再始動ということにします。よろしくお願いします。