このAGCは引越の疲れで参加できてなかった... 問題 atcoder.jp 解法 手で実験してみるとDPぽいな〜と思ったのでDPを考えます. に対する塗り方の個数 とします. 色が切り替わるときに注目します. いま，j+1番目の石を見ているとしましょう. さらにj+1番目の石…

問題 beta.atcoder.jp 解放 DPを使いましょう。 dp[i][j] を上からicm目まで横棒を引いたとき左からj本目の縦棒に行くあみだくじの数とします。 こうするとdp[H][K]が答えになります。 最初は1本目の縦棒にいるのでdp[0][1] = 1です。 正しいあみだくじの条…

問題 D - FT Robot 解法 中でが出て来るたびにロボットが動く方向が軸方向→軸方向→軸方向となる。ここで軸方向と軸方向の動きは独立に考えても良い。 軸方向について動いているときを考える。このときロボットが移動できる点は(1回前に軸方向について動いた…

問題 D - Mixing Experiment 解法 どれを買ってどれを買わないかという組み合わせは2^40通りなので全探索は無理。このタイプの問題は01ナップサックに似ている。DPを考える。2つの物質の比を考えないといけないが比を見るには物質AとBをどれだけ購入したか分…