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

ABC167Dの場合


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

本問題の場合


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

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


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

このテーブル作りは以下のように作ります。 2の冪乗のダブリングではにいるときの回目の遷移先をで表すとで求めることができました。 今回は、にいるときの回の遷移先をで表すとというように求めることができます。 つまり、というようにします。

このテーブルを用いて検索を行う場合は移動回数を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