Dまで。
コンテスト後のツイート
E 0/1が続いた後、「0が(k-1)/2個、1が(k-1)/2個のパターン」がずっと続く。ただし、切り替わるのが最後k-1個以内なら、その後は別の数字が(k-1)/2個を超えない範囲で何でもOK。
— titia (@titia_til) October 30, 2025
だと思ったが、数え上げが難しくて、答えが合わないし、今のままだと多分計算量もダメ。
E. Left is Always Right
非常に苦労してAC。
コンテスト中の考察は正しかった。あとはそれを数え上げるだけだった。
ただ、自分は、index i-1まで0が続き、index iで初めて1が登場するという、このindex iで場合分けしてた仕上げようとしていた。
すると、終盤が繰り返しのパターンではないとき、それぞれについて、計算量が[i,n)の長さ程度かかってしまう。その中にある0,1,？の個数を見て、?が何個以下0になる……という二項係数の和になってしまうため。
そうではなく、計算量を良くするためには、繰り返しパターンでないときは一気に数え上げられる、という発想の転換が必要だった。
index n-kまで0が続いたのなら、残りは、0や1がk/2個以下ならどんな並びでも良い。なので、場合分けをしないことで一気に数え上げることができる。
こうすると計算量を減らせる。
このことに長いこと気付けなかった。公式解説を見ても、二項係数の和で表せる、としか書いていないのが辛い……。二乗ではあるけれど二項係数の和では表せたので、公式でどうにかなるのでは？ などと考えてしまった。