2012JOI本選2 たのしいカードゲーム 解説

問題リンク

解説

まず、B が残すカードは、山の中の連続する部分列だということがわかる。このようなものは 個ある。

これらすべてについて、A からカードを取ることで作れるか判定すればよいが、これは となってしまい、間に合わない。

B の残すカードの列を始点ごとにまとめて考えて、終点を後ろに移動させていくと、終点をできるだけ後ろに持っていけばいいことがわかる。終点をどこまで動かせるかは、A と同時に見ていって、A で残すカードを前の方から貪欲に決めていけばいいだけなので、これで計算量が になる。

少し実装が煩雑になることもあるかもしれないが、これくらいは本選ではぱぱっと書いて、3問目以降に時間を使えるようにしておきたい。