A. El fucho
問題文の通りにシミュレーション．
B. Abraham’s Great Escape
「escape しない」マスの個数を $k$ とすると，
- $k=0$ は可能：すべて同じ方向にする
- $k=1$ は不可能．その $1$ マスの行先がダッシュ可能だと矛盾なので．
- $k\geq 2$ は可能．
となります．$2$ マス以上の場合の構築は，最初の $2$ マスでサイクルを作ったあと，そのサイクルに辺を向かうようなマスを $k-2$ 個作るようにします．
C. The Ancient Wizards’ Capes
状態を $x_i\in \{0,1\}$ で表して，その累積和を $S_i$ とすると，$a_i=(i-S_i)+(S_N-S_{i+1})$ という雰囲気の条件になります．
$S_N$ が決まれば，$S_i-S_{i+1}$ が全部決まって $x_i$ の候補が高々ひとつに決まります．
$a_{N-1}$ の条件から $S_{N-1}$ が決まっており，$S_N$ は高々 $2$ 通りです．これを試してチェックします．
D. Batteries
各時点でいくつかのクリークに分かれるようにします．
最も小さいクリークを $2$ つとって，それらの間の全点対を試すことを繰り返します．
$a=2,3,4$ あたりでのみ雑にチェックしましたが．評価は未証明（いざとなったら制約内の (N,a) をすべてチェックすることは簡単にできる）．
E. Mimo & Yuyu
$N=1$ が例外処理が必要です．この場合は各列の Grundy 数が $[0,1,0,0,0,\ldots]$ のようになります．
$N\geq 2$ とすると，行番号はほぼ関係なくなります．
先頭の列は茶番なので無視します．勝利条件はすべての列にあるトークンが奇数個であることです．
- すべて偶数個なら，後手必勝：後手はオウム返し戦略ですべて偶数個の状態を保てる．
- 奇数個の列があるなら，先手必勝：奇数個ある列のうち最も右側の列からスタートして適切に動かすことで，すべての列が偶数個の状態を作れる．
となって証明できます．
F. Juan’s Colorful Tree
$1.5$ 乗系の解法がいろいろありますが，ある程度定数倍の良いものを選ばなければいけないと思います．
次のように $2$ ステップに分けると実装も考察も簡潔になると思います．
- 色ごとに連結成分分解する．(色, 連結成分) というペアを「新しい色」と思って，頂点ごとに，新しい色からなる集合を求める．
- $N$ 個の集合が与えられていて，要素数の総和が $S$ である．$2$ つの集合の交わりを求めるクエリ $Q$ 個に答える．という問題を解く．
木の問題と集合の交わりの問題で，完全に分離できてしまうんですね．
前者は，$v$ から親辺を見て同色だったらマージという風に考えると，見る辺の個数は見る頂点の個数で抑えられます．後者は，要素数の大きい集合から要素数の小さい集合に向かってクエリするようにすればよいです．
