Three Teleporters

ダブリングの考え方を使います。

ABC167Dの場合

本問は、テレポータが1台(例えば各Aだけ)しかなければ ABC167D Teleporterと出力を除いてほぼ同じ問題となり、 hamayanhamayanさんの解説や、 私の図示のように典型的なダブリングで解くことができます。

本問題の場合

ダブリングは、遷移の元となるテーブルが1枚のため、$1->2->4->8->..2^n$というように1つ前の値を参照して、2の冪乗回移動した値を計算しました。 この問題に当てはめようとすると、遷移のテーブルが3枚(A, B, Cの3つ)あるためうまくいきません。次のように２つのステップに分けて考えます。

STEP1: Aだけを用いた移動を考える

使用するテレポータは移動回数ごとに"A->B->C->A.."となるので$1,4,7..(3k+1)$のように3の倍数+1の回目に移動する際は毎回テレポータAを用いるので、同じテーブルを用いることができます。 ダブリングのように、3の冪乗で$1->3->9->27->..3^n$回の移動をテーブルにできそうです。

このテーブル作りは以下のように作ります。 2の冪乗のダブリングでは$i$にいるときの$2^j$回目の遷移先を$f(i, j)$で表すと$f(i, j) = f(f(i, j-1), j-1)$で求めることができました。 今回は、$i$にいるときの$3^j$回の遷移先を$f(i, j)$で表すと$f(i, j) = f(f(f(i, j-1), j-1), j-1)$というように求めることができます。 つまり、$1-> 3(1+1+1) -> 9(3+3+3) -> 27(9+9+9) -> 3^n(3^{n-1}+3^{n-1}+3^{n-1})$というようにします。

このテーブルを用いて検索を行う場合は移動回数$K$を3進数で考えます。例えば、15回は3進数で"120"であるので、各桁に対応する行をその回数分遷移させます。(つまり、9+3+3になるようにします。) ただし、最下位の桁についてはSTEP2で述べるようにこの移動をしてはいけません。

STEP2: B, Cを使うケースを考える。

STEP2の最後で述べた通り、Kを3で割った余りが0でない場合は、考慮が必要です。 STEP1のテーブルは、その場所からAのテレポータを使い、また次にAのテレポータを使う町に移動するテーブルです。 次にBを使う町に移動したり、次にCを使う町に移動することを考慮していません。そのため、STEP1を終えた後、

• 余りが0の時は何もしません
• 余りが1の時は、1回だけAのテレポータを使います
• 余りが1の時は、Aのテレポータを1回使い、Bのテレポータを1回使います とすればよいです。

解答例

MojaCoder Submit recuraki