くれなゐの雑記

例を上げて 自分で手を動かして学習できる入門記事を多めに書いています

門松もどき

珍しく競技プログラミングの解説記事です

yukicoderの問題 非常に厳しい問題だった 問題はこちら
No.127 門松もどき - yukicoder

要約すると、左右左右と単調に大きくなりながら真ん中によっていく最長増加部分列問題みたいなやつ
とりあえず最長増加部分列の問題
は蟻本にあったので、そちらを見ると, dpを使っている。なるほどdpを使えば確かに解けそう


というわけで以下のようにdpを組む

  •  dpL[l][r]: lから始まって(lが最小)rまでの範囲で、最大となる門松もどき
  •  dpR[l][r]: rから始まって(rが最小)lまでの範囲で、最大となる門松もどき

1. l=rで幅が0の時, 門松もどきは1なのでこれで初期化

2.1.  dpLは右に広げていくイメージで, 左が最小なのでlの値よりもrが小さければ, 広げる前と同じ.
逆のケースでは, 右から始まっているケースに, +1(lの分)を加えた値と比較して更新

2.2.  dpRは左に広げていくイメージで, 右が最小なのでrの値よりもlが小さければ, 広げる前と同じ.
逆のケースでは, 左から始まるケースに, +1(rの分)を加えた値と比較して更新


式にするとこんな感じ


 {

  dpL[l][r] = \begin{cases}
      1 & (l=r)\\
      dpL[l][r-1] & (A_l \geq A_r) \\
      max(dpL[l][r-1], dpR[l+1][r]+1) & (otherwise)
  \end{cases} \\ \\

  dpR[l][r] = \begin{cases}
      1 & (l=r)\\
      dpR[l+1][r] & (A_l \leq A_r) \\
      max(dpR[l+1][r], dpL[l][r-1]+1) & (otherwise)
  \end{cases}

}


実装方法も少し困ったREP(l,N)REP(r,l)みたいな感じで更新しようとしてもまだ求めていない値を参照する形になってしまう
このdpは, 徐々に幅を広げていくイメージがあったので幅を徐々に広げていくようなdpにした

 r = l+wとすると,
w = 0の時, l=rですべて1
w = 1の時はw=0の時の値を使用
w = 2の時はw=1の時の値を使用
のようにwとlを用いて更新するといい感じにdpできた
もしかするとlrではなくlwでdpをすると綺麗だったかもしれない

今回, dpL, dpRはそれぞれlやrから始まるdpにしているので, dpL[0][N]などを出力しても, 0から始まる門松もどきの最大値となり, たとえば正解が1から始まる門松もどきだったらWAになるので, すべてのdpL, dpRに関しての最大値を出力しなければならない.

以下にソースコード

gista5ab6cd749425ed74ea2