estie プログラミングコンテスト2023 （AtCoder Regular Contest 169）

 　AB二完で青に落ちる。

コンテストへのリンク

コンテスト後のツイート

estie プログラミングコンテスト2023 （AtCoder Regular Contest 169）　AB二完でダメ。
A 二項係数で寄与を表せる。
B 尺取りで和Sでどこまでいけるか求めた後DP。尺取りをバグらせた。
C DPは無理そうだから、包除原理かと思ったが、解説見たら違ったみたい。

— titia (@titia_til) December 9, 2023

 C - Not So Consecutive

　解説AC。

　コンテスト中は、DPでやるなら「各数字iについてj回連続しているvalidな個数」を各indexについてもたなければいけないから無理そう→包除原理を使うのでは？　と考えていた。

　実際包除原理でも解けたらしいが、自分の実力では難しそう。

　ただ、DPで解けたかというと、解説を見て、DP[i][j]をindex iでjで、index i-1でjでないvalidな個数、DP2[i][j]をindex iでjなvalidな個数としたとき、

・DP2[i][j]がDP[l][j]+DP[l+1][j]+...+DP[i][j]という形で表せる

　というのを見て全く意味が分からず十分以上考えてしまったくらいだから、思いつけた可能性は低そう。

　ある数を連打しているときは、その個数は変わらないのですね。言われてみれば確かにそう。

　そして、その後の実装も苦戦した。

　DP2[i][j]を累積和で表したいが、その途中に-1でもjでない数が現れていると、そこまでの和にしなくてはいけない。なので、最後に-1でない数字が表れたindexを二つ保持しておく必要がある（と思うけど、解説に言及されてないし、ここに気を配らずにやる方法があるのか？）。このことになかなか気付けなかった。

D - Add to Make a Permutation

　解説AC。

　解説を追うこと自体は難しくないが、条件を整理・きちんと立式することが求められている気がした。理解して実装したつもりが答えがなかなか合わず、自分でもう一度式を整理し書き直してAC。

　しかし、実装に中国剰余定理が必要になったりしたが、本来の解答では使っていなさそうなので、まだ何か勘違いしているのかも。