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

SRM 710 DIV1 Easy: ReverseMancala

解法

入力例(0)、(1)からわかるように、Bの操作の逆はAの操作で、Aの操作の逆はBの操作で表せる。
なのでstartとtargetの両方にAの操作を適用してある状態(かりにSとおく)にできればよい。
つまり
start->(Aの繰り返し)->S
かつ
target->(Aの繰り返し)->S
となるような状態Sがあれば、
start->(Aの繰り返し)->S->(Aの逆/Bの繰り返し)->target
のように解を作れる。
startとtargetは和が等しい配列で、その和をtとする。
S={t, 0, 0, ..., 0}
のような状態ならば操作Aの繰り返しで必ず構成できる。
S[0]<tとすると、i!=0でかつS[i]>0であるような添字iがある。
iに操作Aを適用したとき、(i+1) mod n へ少なくとも1個の要素が移される。
このように
i,i+1,...,n-1
番目に対して順に操作Aをほどこすと、最終的にS[0]の値が必ず1増える。
よってS[0]がtになるまで繰り返せばよい。

思いつき方?

入力例をよく読む。同じ操作を見つける。同じ操作で挟み撃ち。必ず作れる特異な状態を考える。