AGC002 - blogskol

A - Range Product

はい
実装によってはオーバーフローに注意（一敗）

B - Box and Ball

赤いボールを持てるやつから来たら赤いボールを持てる
ボール0個になったら赤いボールがなくなる

C - Knot Puzzle

最後に解くのは必ず2本なので、2本でL以上になる隣接ペアが一つは必要
逆にそんなペアがあるなら左右からそのペアを残すように外していけばいい

D - Stamp Rally

平方分割で殴った
UnionFindを二つ用意する（A,Bとする）
まずAに辺を番号の小さい順に追加していく
この時、辺を300個追加するごとに各クエリがすでに条件を満たしているかを確認
つまり、連結成分の個数をsizeで、連結成分の一致をsameで表すとして、
- $size(x_i)+size(y_i) \geq z_i　and　!same(x_i,y_i)$
- $size(x_i) \geq z_i$
のいずれかが成立しているかを確認
各クエリが、（300の幅の下）どのタイミングで初めて条件を満たすのかをメモしておく
次にBに辺を番号の小さい順に追加していく
この時、先ほどのメモから自分が初めて条件を満たすタイミングはクエリごとに候補が300個しかないので、そのタイミングで確認させる
計算量はAを用いる方が $O(M+QM/300)$ 、Bを用いる方が $O(M+Q\times 300)$
UnionFindとかはO(1)で考えてるけど、だいたい $O(Q \sqrt(M))$ だね

E - Candy Piles

全体-1の操作をZ,最大の列を消す操作をMとおく
飴を昇順ソートする
勝利条件は飴が一つのみの状態で相手に渡すことだけ
0-indexedで $i$ 番目の山の飴1つのみになるのは、Zを $a_i-1$ 回、Mを $N-i-1$ 回行った時（ただし $a_i =a_{i-1}$ の時は無理）
この時、 $a_i-1+N-i-1$ が奇数なら先手が勝ち偶数なら後手が勝つ
また、Zを $[a_{i-1},a_i)$ 回、Mを $N-i-1$ 回行われた盤面は山が $i$ 番目の山一つのみになるため残りの操作は決まっている
これらの情報を二次元平面の格子点に書いていく
横軸をZ軸、縦軸をM軸として取り、点 $(a_i-1,N-i-1)$ にその盤面での勝者を書く
その後、残りの格子点にも勝者を書いていく
これは、例えば点(x,y)が先手の手番（つまりx+yが偶数）なら(x+1,y)と(x,y+1)のいずれかが先手の勝てる盤面なら先手、そうでないなら後手を書けば良い
片方の操作しか出来ない盤面などに注意しながら実際にやってみると、傾き1の平行線が出来上がることが分かるので、(0,0)の点を求めるには(a,a)の点を求めればいいことが分かりどうにかなる