考え方 回答例 考え方探索範囲を絞ったあと，全探索できる．アライグマ「D問題はa≦bの条件をつけて考えるのだ！ a≦ceil(√M)の範囲だけ調べればいいのだ。aを決めたら、abがギリギリM以上になるようなbを求めて、a,bがN以下なら答えの候補なのだ！」— 競技プ…

考え方 回答例 (Functional Graphであることを利用) 回答例 (UnionFind) 考え方$x$から$A_{x}$に辺を張った有向グラフを考える． グラフの閉路に含まれる頂点であることが，高橋君の勝つ必要十分条件． この頂点の個数をカウントすれば良い．アライグマ「E問…

解法1： 考え方 回答例 解法1：考え方各数字（0〜9）の出現回数偶奇性が$l -1$と$r$で一致する場合に「嬉しい列」となる． よって，bitで$i$文字目までの0〜9の出現回数の偶奇性だけを抑えておく．回答例$l - 1 = 0$の場合をd[0] = 1として考える． from col…

考え方1 考え方2 考え方1閉路ができたかどうかをUnionFind木で見る（閉路検出 - 競プロはじめました）． N, M = map(int, input().split()) # --- UnionFind --- p = [-1] * (N + 1) def root(x): if p[x] < 0: return x p[x] = root(p[x]) return p[x] def …

考え方 回答例 考え方全通りの経路を再帰でみていけば良い．回答例 H, W = map(int, input().split()) A = [list(map(int, input().split())) for _ in range(H)] def f(x, y, seen): global ans if x == H - 1 and y == W - 1: ans += 1 return if x + 1 < …

考え方 回答例 考え方アライグマ「E問題は、要するに「直接辺で繋がってないけど移動できる頂点の組の個数」を求める問題で、「移動できる頂点の組－辺の個数」なのだ！ 全部の頂点からDFSすれば求められるのだ！」— 競技プログラミングをするフレンズ (@kyo…

考え方 回答例 考え方UnionFind木（UnionFind木 - 競プロはじめました）で辺で結ばれる頂点をマージする．辺の数は，UnionFind木の親に対応付けて管理する．回答例 N, M = map(int, input().split()) E = [] for _ in range(M): u, v = map(int, input().spl…

考え方 回答例 考え方$1\leq n \leq N$を満たす$n$の約数はそれぞれ$O(\sqrt{n})$で求められる（Pythonで蟻本2-6 - 数学的な問題を解くコツ - 競プロはじめました）．よって，$1\leq n \leq N$なるすべての$n$に対して約数を調べる計算量は$O(N\sqrt{N})$で…

考え方 回答例（UnionFind） 考え方辺を順番に見ていき，閉路でないならつなぐ．つなげない辺の数をカウントすれば良い． 閉路検出 - 競プロはじめました アライグマ「ABC288だったのだ！ C問題は、「辺0本から始めて、閉路にならないように何本追加できるか…

考え方 回答例（UnionFind） 考え方置換になっている組が存在するとダメなことがわかる．変更前と変更後の名前に辺を貼ったグラフで考えれば，閉路があるということ． 閉路検出 - 競プロはじめました アライグマ「D問題は、入力例2みたいに、変えたい名前が…