ABC-G
AtCoder
AtCoder600点
ABC-G
黄色diff
二分探索
木
グラフ問題
木DP
DP
ゲーム
ゲームDP
meldable heap
マージテク
変化・遷移が限られる
木上のゲーム
白黒の問題にする二分探索
駒を動かすゲーム
グラフ上のゲーム
めっちゃ面白い問題だった! 問題へのリンク 問題概要 頂点 0 を根とする頂点数 の根付き木が与えられます。頂点 0 以外の頂点 には数値 が書かれています。今、頂点 0 にコマが置いてあります。 高橋くんと青木くんが次の動作を交互に繰り返します。 青木く…
AtCoder
AtCoder600点
ABC-G
橙色diff
部分グラフ列挙問題
数え上げ問題
グラフ問題
指数探索系問題
bitDP
高速ゼータ変換
グラフのconnectivity
グラフ・盤面・数列の個数の数え上げ
一般化した問題を解く
包除原理
除原理
グラフの頂点集合の部分集合を走査する
各kに対して
場合分け
SubsetConvolution
高速畳み込み計算
累積和
O(3^N)
補集合を考える
面白かった!! より一般化した問題 (グラフの頂点集合の任意の部分集合に対して、それらを連結にする辺の選び方の数え上げ) を考えた方が考えやすいね。 問題へのリンク 問題概要 頂点数 、辺数 の単純無向グラフ が与えられます。 の辺集合の部分集合 ( 通…
AtCoder
AtCoder600点
ABC-G
黄色diff
整数問題
原始根
Fermatの小定理
Euler関数
最大公約数
互いに素
約数
入力が定数個
素数
位数の法則
O(N^2)個のものを考える問題
約数の個数は少ない
ある量を固定して考える
条件の言い換え
変数変換して扱いやすい同型な問題を見出す
原始根が絡む問題は時々出るイメージですね。 問題へのリンク 問題概要 素数 が与えられます。 次の条件を満たす整数 の組の個数を 998244353 で割ったあまりを求めてください。 ある正の整数 が存在して、 が成立する 制約 は素数 考えたこと 整数問題とい…