Cまで三完。橙パフォで2100復帰。ただ、Cまでがたまたま速く見えただけで、一時間以上残せたのにD以降の難しい問題に手が届いていないのは悲しい。
コンテスト後のツイート
D 最後二要素のあるなしをもってDPかと思ったが答えが合わず終了。23/51個ACだからちょっとは惜しかった？
— titia (@titia_til) October 16, 2021
……と思ったけど、解説を見たら全然違いそうだ。
D - Neq Neq
解説AC。
前半の考察部分と、後半、それをDPにする部分、どちらもすごく難しいというわけではないのだけど、結構考えにくい。
コンテスト中、一時間以上時間を使ったけど、考察も正確ではなかった。
まず、
・「1 1 1」のように同じ数字が連続する場合は全部残すしかない。
ことには気付く。そして、
・「1 2 1 2 1 2 1 2」のように二つの数字が繰り返される場合、その間二個の数字を両方消すことはできない
かと思ったが、それは間違い。「1 2 1 2 1 2 3」なら、右から順番に消していけば「1 3」まで消すことができる。
とは気付いたのだけど、二番目の内容を正確に記述することができなかった。
公式解説の通りで、
・種類数が2で長さが4以上のとき、両端を残して間を消すことはできない
と記述できる。
言われればなるほど、という感じだけど、正しく分かっていたかは疑問……。
さて、それをDPに直すところも難しい。私は、公式解説のdp[i]の定義が分からず困ってしまった。
ここでは、
・DP0[i]=i番目のボールを残したときの（i番目までの）場合の数
・DP1[i]=i番目のボールを除いたときの（i番目までの）場合の数
とする。
一番初めのボールは残すしかないので、DP0[0]=1、DP1[0]=0。
また、特に制約がなく、残すことも除くこともできる場合は、DP0[i]=DP1[i]=DP0[i-1]+DP1[i-1]となる。また、同じ数字が連続する部分では、DP1[i]=0となる。
あとは、「種類数が2で長さが4以上」の条件について考える。
たとえば、
・A=[1, 2, 1, 2, 1, 2, 1]
のとき、
DP0=[1, 1, 2, 3, 5, 8, 13]
DP1=[0, 1, 2, 4, 7, 12, 20]
となる。
これは、DP0[i]=DP0[i-1]+DP1[i-1]から、ダメな場合を除く、と考えると求められる。
たとえば、DP0[3]=3は、DP0[2]+DP1[2]=4からDP0[0]を除いている。このとき除いているのは、「1, _, _, 2」と、間にある二つを取り除いた場合だ。
同様に、DP0[4]=5は、DP0[4]+DP1[4]=7から、DP0[0]とDP0[1]を除いている。それぞれ「1, _, _, _, 2」と、「?, 2, _, _ ,1」に対応している。
DP0[5]=8は、DP0[5]+DP1[5]=12から、DP0[0]とDP0[1]とDP0[2]を除いている。
こんな感じでDP0とDP1を求められる。
あとは、DP0に関する累積和を考えると、O(N)になる。
0 件のコメント:
コメントを投稿