SRM607 Med

問題:CombinationLockDiv1
概要:0~9からなる長さn(<=2500)の数列pがある。これを0~9からなる数列qに変えるのに必要な操作の数は? 操作:ある区間を選び、その区間に全て+1(9なら0になる) もしくは全て-1(0なら9に).

解答
+++++
.--..
は
+..++
に,

+++..
.----
は
+..--
にできるので、overlapしなくてよいことがわかる.(styleがずれるのでなにもないところに.を入れた)
よって、dp[i][j][k]で、i個目で,k==0なら+を,1なら-を、ちょうどj個開いている(つまりそこより右にj個以下ならいくらでも伸ばせるという状態)を持てば、dpができる、jのmaxとしては9*nとかなりでかいので、1/10くらいのあり得る状態だけを見れば良い(例えば3から1にしたい時、+は8,18,28,..個開いている,-は2,12,...の状態しか考えなくて良い)
閉じる回数はできるだけ少なく、開く回数も必要最小限だけでよいので、遷移はO(1)で全体でO(n^2)

別解(O(N)!):
rngさんによる?
区間に+1を足す->imosで左に+1を,右に-1を足す,とかを考えると,
まず全体でどれだけ足すかa[i]を持つ(1->4なら3,4->1なら7など).次に隣との差(a[i+1]-a[i]+10)%10を取る(両端に0をおいておく)
このa[i]の好きなところに+1,-1がセットでたせて、全て10の倍数にしたい。
ある数より小さいところは-1を,大きいところは+1をするとよさそう(aをソートしておく)
まあ"ある数"を全部試してもいいのだが、もっと楽に出来て、(あまり自明でないけど)
len=aの長さ,sum=Σa[i]として、小さい順にlen-sum/10個足せば良い
なぜなら、大きいk個を+1により10にするとすると、そこに関してのsuma=a[len-1]+..a[len-k]とすると、k*10-sumaの+1が必要.これが大体残りのsum-sumaと一致すれば良くて、ちゃんと割り算を考えるとそうなるkはsum/10であることがわかる。
よってコードはこんな感じ
http://gyazo.com/748b9196b0e4c230200edb1f164abda9
やばすぎ