titiaのノート: 灘中入試コンテストday2

2021年9月2日木曜日

　Cまで三完でした。

No.1353 Limited Sequence

　解説AC。

　まず三つ目の条件を正しく理解することが重要。

・各ｉ( 1 <=ｉ<= N ) について、i が（A_i＋１）個以上連続してはいけない

　という意味です。（コンテスト中はこれを解釈できずに飛ばしてしまった記憶が……）

　これさえ分かれば、

・同じ数字を付け加えるときは一気に付け加えれば良さそう

　と思えるので、それを利用してDPできます。

　問題を正しく理解できれば、そこまで難しくなかったか……。

　fairly_lettuceさんの解説が分かりやすかった。

　考察が難しい問題ではないけど、包除原理のとき何を除けばいいかというあたりで混乱してしまった。順番が確定しているので、包除原理といっても$(-1)^N$をかけたりする必要がない、というのがポイントか。

　というわけで、理解したので実装してみようか、と思って書いたらかなり苦戦した。こういうのをさくっと実装できるようになるにあどうしたら良いのかなぁ。

　解説AC。

　後ろから見るという発想はあったが、Pが分かっても、操作前のYが一意に決まらないためダメだと思ってしまった。分からないbitは分からないままにして計算すれば良かったのか。