Document

Sort the Panels の解説
問題作成者: 野田
解答作成者: 寺島、八森
英訳: 寺島
解説: 八森
概要

黒か白、いずれかの色を持つN枚のタイルが与えられる。

タイルを決められた色の順番に並び変えたい。

タイルを並べ替えるには、機械を使い任意の二ヶ所に
マークをつけて、その二枚のタイルの場所を交換する。

機械を移動させるのにはコストがかかる。

任意の順番に並び変えるのに最低限必要なコストは？
解法

パネルの並び方と機械の場所を状態として、
その移り変わりをグラフで表現する。

このグラフ上をダイクストラ。
グラフを作りましょう

パネルの並び方と機械の場所を状態とする。

任意の２枚のパネルを入れ替えるのに必要なコス
トを重みとして、入替前と入替後の状態を表す
ノードをエッジでつなぐ。
機
機
コスト６
状態1
状態2
計算量

状態数(ノード数):
色の並び方＊機械の場所
-> 16C8＊16
-> 205920

辺の数:
ノード数＊黒パネル数＊白パネル数＊２
-> 205920＊8＊8＊2
-> 26357760

順位優先探索すると:
O(N log E)
-> 205920 log (26357760)
-> 約508万
すいません

問題分より、
He decided to enter this building for his interest,
but its entrance seemed to be locked by a strange
security system.
とありますが、最初のパネルの並びが既に一致し
ているような入力が入ってました。原因不明の
WAをもらった方、申し訳ありませんでした。
Submission状況
Submit数: 83
 Accepted数: 20
 最速Accepted: 42分 (Makegumi)

おしまい
何か質問ありますか？

Download Report