読者です 読者をやめる 読者になる 読者になる

AOJ-ICPC 1000点 非幾何まとめ(ネタバレ含む)

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次元凸包 みたいにした。これでも十分状態数は少ないっぽい。まあ最悪ケースとか設定上作れそうにないし。