SRM378 Div2 1000

問題

ハノイの塔を考える。棒が3つあり、それぞれA,B,Cである。
始めは1〜Nのサイズの円盤が大きい順にAにすべて刺さっている。
通常のハノイの塔と同様に、別な棒のところへ移すときは、そこに刺さっている円盤のサイズよりも小さければ写すことができる。
目標となる最終状態targetが与えられる。最小手順でその目標状態へ円盤を動かした場合moves番目にあたる状態を出力せよ。

考え方

普通に計算すると間に合わない。
いくつか書き出してみるとある法則性があることがわかる。

i番目の文字はmovesが2^i回よりも多いか少ないかで変更できるか決まる。
多い場合は、文字を変更できるので、0〜(i-1)番目までの文字は変更する前と後の文字じゃない文字で埋まった状態から(moves-2^i)回の状態と同じになる。
少ない場合は、文字を変更できないので、目標状態は0〜(i-1)番目までの文字が変更する前と後の文字じゃない文字で埋まっているものになる。
このように、スタート状態とtargetの状態を書き換えながら繰り返し、0番目までの文字を変更しきったらそれがmoves番目の文字となる。

たとえば、{"CCC",4}ならば、i=2の文字を変えたいとき、
0:AAA
1:CAA
2:CBA
3:BBA<-ここで、やっとi=2の文字を変更できる状態
4:BBC<-i=2の文字を変更
5:ABC
6:ACC
7:CCC
で、i=2の文字を変えるためには2^2=4よりもmovesが大きければ変更でき、かつ、"BBC"をスタートとして(moves-4)番目の状態と等しい。
もし、movesが4より小さいならば、targetは"BBA"と考えられる。