Dまで四完。だが、そのDもafter_contestで落ちた。
D - Happy Birthday! 2
たとえば数列Aの値がランダムなら、配列の長さが長くても、mod 200がすぐに埋まりそうなことは分かる。なので、DP[x]に、和のmod 200がxになるような部分列を入れていき、二通りの表し方が登場したら、それを出力すれば良い。
……のだが、まずい実装をしていたため、BやCの長さが1のときにおかしくなってしまった。
E - Patisserie ABC 2
snukeさんの解説動画を見てAC。
時間をかけて頑張ればできる、とは思ったけど、良い方法があるのかな？ と動画を見て正解だった。
「和がSになる個数」を求めるのが重要だけど、こういう$l\leq x\leq r$みたいなものを求めるときは包除原理を使うのが定石らしい。
ほえ～、知らなかった。
それさえ分かれば後は簡単……なはずだけど、コンテスト中は、その後も二分探索とかしなくちゃいけない気がしていた（こともあって飛ばした）。その後は簡単、というのはちゃんと分かっておくべきだった。
F - Minflip Summation
snukeさんの解説動画を見てAC。
これはコンテスト中考えたことで大体あっていた。
S[0]とS[-1]が一致するか異なるか……といったあたりの場合分けがおかしかったと思う。
時間内に解けるべき問題だった。
あと、解説ACにもかかわらず、文字数が一文字のときに引っ掛かってWAを出してしまったのも反省。Dと似たミスですね。注意しましょう。
0 件のコメント:
コメントを投稿