Cellular Automaton以外を解きました。Cellular Automatonはあまりに意味不明なので解説を見ました。
Do use segment tree
問題, 解法ともにめっちゃ有名ですね。ライブラリチェック用問題。 HL分解かL/C Treeを貼ります。おすすめは後者
Common Palindromes
方針が悪く非常に大量のライブラリを使った。大変。 回文列挙はmanacher + rolling hashで可能。 後は文字列についてそれがいくつ出てくるかを判別できれば良い、これはSuffix Array + LCP + RMQ
Palindrome Generator
解法はすぐに思いついたんだけど、微妙に方針が良くなかったようでMLEで苦しんだ。きらい。 (スタート位置, ゴール位置)のペアを頂点とするグラフを考えれば良い。 強連結成分->DAGでDPしようと思ったら死んだ。クソみたいな改善で通した。
姉妹港
なんか適当にごにょごにょしたら解けた。 解法説明困難。
Brilliant Starts
簡単だった。
次数が少ない頂点から順にDPすればよい。
ねこ鍋改造計画
見るからに戻すDPっぽいのだがそのままでは不可。
dpの値を、YES/NOからそれを達成する組み合わせ数 mod 適当な数 にすればよい。この考え方は数列色ぬりで学んだ。圧倒的成長。
一般化ポーカー
面白かった。
説明困難だけど、値が2以上離れてる手札は詰めて良い。[1,2,3, 59, 60]と[1,2,3,5,6]みたいな。 こういうのを統合すると状態数がめっちゃ少なくなる。
よくわかる二重魔法
問題文読解が本質。以上。
Crystal Jails
クソ
Point Distance
FFTって面白いですね。
Air Pollution
面白い。
めちゃいじいじしてたら解けたけど、どうやら累積和で考えれば一瞬だったらしい
CarrotBreeding
大体のパターンはすぐできる。
細かいのはモンテカルロした。
Lapin Noir
面白い。
嘘解法で通してしまった…
Exhibition
dp[n][a][b][c]とdp[n-1][a][b][c]が列挙できれば後は簡単。
3次元凸包になるのだが不可能なので、dp[n][a] := 2次元凸包 みたいにした。これでも十分状態数は少ないっぽい。まあ最悪ケースとか設定上作れそうにないし。
