ABC279-Gを復習した。こういう復習をちょっとずつ増やしていきたい。

愚直な2乗DPの計算量を落とすため、以前はdp[i+1][j+1]+=dp[i][j]的なやつを見つけて変数変換でdp[i+1][j]+=dp[i][j]の形にしてDPテーブルの値を使いまわせるようにする…みたいな手口をよく使っていたのだが、常々これはあまりにも式計算の手間が非効率だと思っていた。今回はキューを使うやり方を思いついたのでそれを試すことにした。

dp[i][j]:=(端からi個を決めて、最後に決めたj個が同じ色のパターン数)と定義する。

• $dp[i][j]=dp[i-1][j-1]\ (2\leq j \leq K-2)$
• $dp[i][1]=\sum_{j=1}^{K-2}dp[i-1][j]+dp[i-1][K-1]\times (C-1)$
• $dp[i][K-1]=dp[i-1][K-1]+dp[i-1][K-2]$

このような遷移になっている。見れば分かる通り、「端の値」は「端の値」と「間の部分の総和」が分かれば算出出来て、間の部分はベルトコンベアのように1個ずつずれていくだけの形になっている。適切にキューを使ったら非常に早く実装が済んだ。全ての場合に使えるとは思わないが、今後はこれを活用していきたい。

むしろ最初の愚直な2乗DPを書くのに時間がかかった。新しい色に変えられる条件を「最後のK個が連続しているとき」と勘違いしてしまった。実際はK-1個連続していれば十分である。この辺の考察も手早く正確にしたい。ただ、こういう考察の精度を上げる方法はよくわからない。

---

大学で所属する研究室のことを考えていたらひどい夜更かしになってしまった。