読者です 読者をやめる 読者になる 読者になる

SRM 712 DIV1 Easy: LR

操作後のA[i]をA'[i]のように表記する。
(1)LRの操作
Lの操作により
A'[i] = A[i-1]+A[i]
A'[i+1] = A[i]+A[i+1]
更にRの操作により
A''[i]
= A'[i] + A'[i+1]
= (A[i-1]+A[i]) + (A[i]+A[i+1])
= A[i-1]+2A[i]+A[i+1]
(2)RLの操作
Rの操作により
A'[i] = A[i]+A[i+1]
A'[i-1] = A[i-1]+A[i]
更にLの操作により
A''[i]
= A'[i-1]+A'[i]
= (A[i-1]+A[i])+(A[i]+A[i+1])
= A[i-1]+2A[i]+A[i+1]

以上から、LRの操作とRLの操作は等しいことがわかる。
なので、L,Rのそれぞれの操作回数だけが問題であり、操作の順番はどうでもいい。
L,Rの操作回数を総当りしてシミュレーションしても間に合う。
n=|A|、操作回数の最大値をmとして
O(n*m^2)で間に合う。

広告を非表示にする