A. Square of Rectangles
平行に 2 回切るパターンと垂直に切るパターンを適切に判定．A にしては実装しにくい気がしました．
B. Square Pool
難読．$3$ つ以上の玉が同時に点で衝突することもありうるよな？その場合にどうなるかが読解できますか？わかりませんでした．→ そういう場合はないと書いてあった
いろいろ信じると，衝突は軌道の multiset を変化させない（アリ本のアリ問題）のでボールごとに判定すればよいことになります．
C. Divine Tree
自明評価として， $1\leq d(v)\leq v$ が成り立つことから $N\leq M\leq N(N+1)/2$ が必要です．この間がすべて作れるし，構築はパスグラフだけで十分です．
例えば $N=10$ で $M = 10+9+8+7+6+3+1+1+1+1$ ならば，パス上に $10,9,8,7,6,3,1,2,4,5$ などと並べます．
D. Matrix game
$(a-1)k+1$ 行以上必要です．そうでないとどの列にもどの種類も $a-1$ 個以下にできてしまうからです．
行数 $n=(a-1)k+1$ の場合を考えます．各列に対して 「ある種類がある $a$ 個の行で一致」というパターンが少なくともひとつできます．「パターン」は全部で $x=\binom{n}{a}\times k$ 通りあります．列数が $(b-1)x+1$ に達すると同じパターンが $b$ 個とれて条件が成り立ちます．列数がそれ未満だと反例があることも同様にわかります．
E. Lanes of Cars
操作回数 $t$ としたとき，最小コストは $t$ の下凸関数になります．
下凸を示すには操作自体のコストは無視してよく，計算量を無視すれば最小コストは貪欲シミュレーションで求まります．この貪欲シミュレーション 1 ステップごとの利得が単調減少であることは明らかで，これがそのまま下凸性です．
よって $t$ を固定したときのコストを求められればよいです．まず大きい方から削除し，そのあと小さい方から追加していくと $2$ ステップに分けてシミュレーションすると（事前のソートのもと）線形時間でシミュレーションできます．
F. Superb Graphs
独立集合にすることがある点を色 $0$，クリークにすることがある点を色 $1$ とします．大きさ $1$ にしかならないものも適当な色を割り当てておきます．
必要条件として，ある $G_i$ の $2$ 点 $a,b$ について
- $a,b$ の近傍集合が $a,b$ を除いて一致し，$a,b$ が辺で結ばれているならば，どちらかは色 $0$ である．
- $a,b$ の近傍集合が $a,b$ を除いて一致し，$a,b$ が辺で結ばれていないならば，どちらかは色 $1$ である．
があります．これが成り立たないとすると，これらをマージしても “fun graph” の条件を満たして “superb” の条件に違反するからです．逆にこれらが成り立つならば，$H_i$ をクソデカにとることで，$G_i$ が “superb” であるようにできます．
あとは 2-sat を実行するだけです．
G. Eulerian Line Graph
細部を詰めるのが面倒なのでやや雰囲気証明です
eulerian trail を持つことを good と書くことにします．
常に連結にはなるので奇点の個数だけが問題です．
- 一度でも奇点がなくなれば以降ずっとそうなので good です．
- すべてが奇点になったら次に奇点がなくなって以降ずっと good です．
よって奇点と偶点が両方ある時が問題です．
- 奇点と偶点が存在して奇点同士が隣接しているならば，十分大きな $k$ についてに $L^k(G)$ は good にならない．
これを確認します．まず奇・奇・偶がこの順に隣接するパスがあります．$1$ 回操作すると，奇点と偶点を両方含む長さ $3$ のサイクルが登場します．以降の操作ではこのサイクルを由来として常に奇点が $2$ つあるような長さ $3$ のサイクルが登場し続けます．
このサイクルのまわりにもう $1$ 点以上あることを考えると，さらに他に奇点を含む長さ $3$ のサイクルが発生して消えることがないことが分かります．
最後は，奇点と偶点の両方があり，奇点同士が隣接していない場合です．
- 奇点と偶点の両方があり，奇点同士が隣接しておらず，奇点の次数 $3$ の点がある場合：この場合，1 ターン後に奇点の隣接が発生します．1 ターン後にすべて奇点なら 2 ターン後以降ではずっと good．そうでなければ十分大きな $k$ では good ではないです．
最後に次の場合を扱います：奇点と偶点の両方があり，奇点がすべて次数 $1$ の点である場合
この場合，各奇点（葉）からはじめて $3$ 以上の点が出てくるところまでのパスを考えます（入力がパスでないことよりそういう点が必ずある）．
各ステップで葉から次数 $3$ 以上の点までの距離が $1$ ずつ減っていき，これが隣接した次のステップで奇点が増えて隣接する奇点発生ということになります．
よって，「奇点がすべて葉」「奇点が 2 個」のときに，葉から次数 $3$ 以上の点までの距離に応じたステップ数だけ good になり続けて，それ以降は good にはならない．ということになります．
「十分大きな $k$ では」の類の議論以外はだいたい解法になっていると思います．あとはストレステストで落ちなくなるまで適当な実装を繰り返しました．
