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を満たす文字列はいくつあるか 遷移をする際に…