パナソニックグループプログラミングコンテスト2023（AtCoder Beginner Contest 301）

　Eまで五完でした。

コンテストへのリンク

コンテスト後のツイート

パナソニックグループプログラDPミングコンテスト2023（AtCoder Beginner Contest 301） Eまで
C Counter使ってがんばる
D "1"をとりあえずNから引く。後は貪欲。
E マス間の距離を求めた後bitDP
F DPしようとしたけど、1<<26状態必要な気がしてしまいダメ。

— titia (@titia_til) May 13, 2023

F - Anti-DDoS

　DPとして、「何個の大文字が既に現れたか？」を持てば良いという情報を得て解いたが4caseでWA。他の方の提出と見比べて、大文字が出たときの遷移がおかしかったと気付いてAC。

　解法は、1<<26状態を持つのが無理なのだから、個数だけ持てば良いと考えるのは自然。コンテスト中も全く考えなかったわけではないはずなのですが……。

　自分が出したWAについて。

・……　A?B　……（"A"の前に大文字は現れない。なお、"?"は登場するので、"?"としての大文字はある。）

　のようなとき、最初のAが出たときは、

・今までに現れた大文字の個数がx個だったら、"DD"型に遷移するのはx/26通り

　Bが出たときは、

・今までに現れた大文字の個数がx個だったら、"DD"型に遷移するのは(x-1)/25通り（x個のうち、一つは確実にAなので、それを除いて考えなくてはいけない）

　なのですね。

　これに気付いていませんでした。

　結構本質的な間違いなのに4caseしか落ちないため、コンテスト中にこのWAを出したら修正が難しかったかもしれない。