AOJ 1197 - サイコロ職人
サイコロ職人の朝は早い。
提出コード
さて、立方体を転がしてある面が下になった回数をカウントしたときに、指定された6つの数字のグループと一致するように転がせ、という問題です。
転がす方向は東西南北の4通りであり、答えを探していくのでなんとなく深さ優先、もしくは幅優先探索かなぁと思いました。しかしここで、目標の盤面にするために必要な手数を考えると、となるのでこの時点で幅優先はなくなります（必要な手数は不変であるため）。ということでとりあえず深さ優先探索でどうにかすることを考えます。
さて、この深さを再帰で実装することをとりあえず考えてみます。先程も述べたように、探索する方向は4通りあります。そして、手数の最悪パターンはというと、というパターンであり、この時全探索をすると、430000通りものパターンを網羅する必要があります。
また、例えば最終的にサイコロが完成したかどうかを調べるためには、の並べ方分だけ逐一見てあげる必要がありそうです。これは6!通りであるので、720回ループする必要があります。ということで、探索の途中で枝刈りをする必要がありそうです。つまり、1手目から順番に手数を決めていくとき、これ以上手数を決めても今のサイコロの転がし方だと確実にサイコロは完成しないところを探します。これにより、途中で探索を打ち切ることで無駄な探索を省くことができるのです。
まず、一番わかりやすい枝刈り方法を考えます。目標の盤面の並べ方を1つ固定したときに、どこか1つでも、目標の数より現在の数が上回っている盤面が存在するとき、この手順ではサイコロを完成させることができません。というのも、今回の方法ではサイコロの盤面の数を減らす方法がないからです。そして、目標の盤面の並べ方は720通りあるので、この中で1つでも完成する可能性があるならば、探索を実行すればよいです。なので、720回for文なりなんなりでループをまわしてあげれば枝刈りができそうです。
というところまでは、なんとか自力で思いつくことができました。これ以上はどれだけ考えても長引くだけになりそうなので、ICPCの問題ということもあり、チームメイトに問題を投げてみることにしました。...いくら考えても出てこなかった考察が、一瞬ででてきました。
ということで、今回はやまさん(@yamasangamasan )に助けを求めました。サイコロ職人(の考察パート)が解けた
— やまさん (@yamasangamasan) 2018年6月28日
では、その考察内容について述べていきます。
まず、ある面(Aとします)の数を1つ増やすためにどんな操作が必要なのか、を考えます。これは2パターンに場合分けをすることができます。底面かその向かいの面の場合と、側面の場合です。
① 側面の場合
こちらは割とシンプルです。一回、目的の方向に動かすだけで、目的の面が底面になります。よって、ほかの盤面を経由することなく1回だけで目標の盤面の数を増やすことができました。
➁ 底面かその向かいの面の場合
今一番下にある盤面に1追加するには、どこかの側面を経由する必要があります（底面の向かいも同様です）。ということで、最低2手必要になることがわかります。つまり、目標の盤面の数を増やすには、どこかしらの側面の数も増やすことになります。ということは、
(上下の盤面においてあと増やしたい数の合計) (側面においてあと増やしたい数の合計)
という不等式が成り立ちそうです。
➁で考察したように、底面かその向かいの盤面については1つ不等式を組み立てることができました。側面についてはどうでしょうか。
①より、側面は1手で数を増やせることができることはもう知っています。では、数を増やした後側面はどこへ行くでしょうか。...底面になります。ということは、ある側面の数を+2したいとき、
ⅰ)その方向へ動かす(+1)
ⅱ)目標の盤面は底面になるので、2手使ってもう一度底面に戻す(+1)
という2ステップを踏む必要がありそうです。
とここで、二番目のステップはもう不等式が判明してます。➁番と全く同じ状況になるからです。ということで、側面にいた場合、1手動かすと➁と同じ不等式が利用できます。まとめると次のようになります。
(上下の盤面においてあと増やしたい数の合計-1) (側面においてあと増やしたい数の合計)
ここまでくれば、この不等式を、あらたに探索して決めた手順に対して毎回調べていくと、うまく枝刈りすることができます。
側面は4つありますが、その後のことも考えて、サイコロ全体についてそれぞれ向かいの面とのペアを組み、3つのペアに分割すると楽です。増やしたい数は、目標の数から現在の数を引いたものになります。目標の数の並べかただけ、ループをまわし、1つでも完成する可能性があれば探索を続行します。底面と向かいのペアの数をp、側面2ぺアの増やしたい和をそれぞれq,rとすると、
が成り立ちます。これと最初の目標数を現在の数が超えた、という2つの条件が今回の枝刈り条件になります。
最後に、今回は辞書順で一番前のものを出力するので、東西南北の英語表記で一番手前のものから順番に探索していきます。つまり、
E < N < S < W
となります。さらに、この順で探索すれば、最初に見つかった手順が答えになります。ということで、再帰で戻って探索する必要はなくなります。
以上をまとめてコードにうまく落とし込むと、完成となります。
今回の問題は初めから難しいという噂を聞いていたので、解説を見ずにせめてチーム内でACしたいなと思っていたので満足です。
時間はかなりかかってしまっているので、実力をもっと伸ばしてよりはやく考察ができるようになるといいですね（まずは自力でとけるようにならないとですが）
