AOJ 3053 - Phone Number (RUPC2019 Day2 C)

問題 提出コード

解法

配置方法は9!通りなので、全てに対して探索を行いたいです。
ので、ある配置のときにかかる操作回数の最小値の求め方を探ります。
すると、次のようなことをすればよいことになります。

1. あらかじめ、文字列について、どの数字からどの数字への遷移がいくつ存在するかを調べておく

2. 任意のマスから別のマスへの遷移方法を、マンハッタン距離かなにかを利用して求めておく

3. 最初に求めた遷移の個数と今の配置、そして先ほど求めた距離を元にして、現在の配置の操作回数を求める

2つめの操作についてですが、
012
345
678
とマスに番号を付けると、
は上から行目、左から列目に存在しています。
ので、との距離は、となります。
そして、9!通りの配置を調べるとき、のマス目で調べるのではなく、1次元配列に1~9の番号を入れておき、next_permutationで順列を順番に生成しながら、配列の添え字と上のマス目と照らし合わせて調べていくのが個人的に分かりやすいかなと思います。

感想

ぱっと見どうやるのかな～とは思ったのですが、あらかじめ距離等を計算しておくことで、時間内に答えが求められることに気づきました。ただ、これでも計算量は結構ギリギリだろう…と思って提出してみると、意外とはやかったです(c++で0.03s)。