制約条件:ある値=K
AtCoder
旧ARC-C
XOR
木
前処理
累積和
パリティ
青色diff
制約条件:ある値=K
数え上げ問題
解空間:O(N^2)個のペア
解空間:O(N^2)通りの選択肢
木上の累積和・いもす法
XOR について a ^ a = 0 な性質を上手く使う問題として。 問題へのリンク 問題概要 頂点の重み付きツリーが与えられる。 整数 が与えられ、ツリー上のパスであってパス上の重みの XOR 和が となるものが何個あるかを数えよ。 制約 考えたこと 根を 1 つ決め…
数え上げ問題
二項係数
条件の言い換え
AtCoder
AGC-B
AtCoder700点
色に関する問題
青色diff
Greedy:各要素について独立に考えてよい
f(i,j)をiとjとに分離する
主客転倒
多項式・FPS(形式的冪級数)
制約条件:ある値=K
線形性に着目する
テク:線形和への分解
最初迷走したけど、順位表見ると上位陣が 5 分とかで解いていて、「いくらなんでもこの方針で 5 分はない、きっとなにか簡潔な視点があるはず」と思えて思い付けたのがよかった。 問題へのリンク 問題概要 N 個のマスを赤、緑、青、無の 4 色に塗り分ける。 …