atcoder.jp ゲーム系の問題でDPをするときはメモ化再帰の方が書きやすい気がする。 解法 $ S_i $か0かの選択をする際に、その選択をした結果7の倍数を作れるor作れないことが分かれば、常に最適な行動を取れる。 ということで、前の桁から$ S_i $か0かの選択…

atcoder.jp 公式解説とは違う方法らしい。 解法 この問題は、頂点 $ U_i $の子要素で根からの距離が $ D_i $である頂点はいくつか、というクエリに回答せよ、と言い換えられる。 複数のクエリに回答する問題 複数のクエリに回答する問題は、次のような解法パ…

atcoder.jp 解法 T - 0.5分後というのは、T-1分後と言い換えることができる。 T-1秒をこえて、料理を食べることができない場合、ただのナップザックDPで解くことができる。 具体的にDPの定義は次のようになる。 dp[i][j] ← i番目の料理まで食べるかどうか決…

atcoder.jp 解法 次のように定義する。 操作1、N が K で割り切れるとき、N を N/K に置き換える 操作2、そうでないとき、N を N−K に置き換える 場合分けして考える。 操作2だけでNを1にできるような数 これは、N-1の1以外の約数すべてが該当する。 理由 m…

atcoder.jp 解法 島をノード、橋を辺とするグラフを考える。 グラフの辺を削除するというのを、高速なアルゴリズムで実装するというのは難しい。 そのため、辺の削除をUnionFind-Treeなどを使って辺をつなげていくことで同じことを表現できないかを考えるこ…

atcoder.jp 解法 3つの条件を上から順に条件1、条件2、条件3と呼ぶことにする。 3つ目の条件が存在しない場合、次のDPで解くことができる。 dp[i][j][k] ← 長さiでi-1文字目がj、i文字目がkであるような条件1,2を満たす文字列はいくつあるか 遷移をする際に…