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

競技プログラミングをするんだよ

ICPC国内予選突破を目標に一日一問題以上解いていきます。

AOJ2157 Dial Lock

AOJ

計算量の解析がよくできないシリーズ

問題文

Dial Lock | Aizu Online Judge

k桁10進のダイヤル錠がある.
最初の状態と最終状態が与えられたとき,ダイヤルを回す必要のある最小の操作回数を求めよという問題です.
ただし,1回の操作では,連続した桁を同じ分だけまとめて回すことができる.
つまり一回の操作で
12345で真ん中3つを選び2つずつ回すとすると
14565となる.

解法

端から攻めていくと,選ぶ区間の組み合わせは1回の操作でO(k)通りだが,どれだけ回せばいいかは一意に決まる.
これを終了状態になるまで試していくことで,操作すべき区間は1ずつ減っていくのでk!ぐらいの操作回数になる(はず)

提出したコードでは両端から攻めているが,冷静に考えると片側から攻めても大丈夫ですしそのほうが実装が楽だと思います.