11

Google Code Jam で次の問題を聞きました。大会はもう終わったから話してもいいよhttps://code.google.com/codejam/contest/2270488/dashboard#s=p3

古い地図をたどっていくと、恐怖の海賊ラリーの秘密の宝庫にたどり着きました!

宝の山は N 個のロックされたチェストで構成されており、各チェストは特定の種類のキーでのみ開くことができます。さらに、宝箱を開ける鍵は一度使うと二度と使えません。すべてのチェストの中には、もちろんたくさんの宝物があり、他のチェストを開くために使用できる 1 つまたは複数のキーが見つかる場合もあります。チェストには同じ種類のキーが複数含まれている場合があり、任意の数のキーを保持できます。

すでに少なくとも 1 つのキーを持っており、マップにはさまざまなチェストの中に他にどのようなキーがあるかが示されています。このすべての情報で、すべてのチェストのロックを解除する方法を理解できますか?

すべてのチェストを開く方法が複数ある場合は、「辞書的に最小」の方法を選択します。

コンテストには 2 つのデータセットがありました。最大で 20 個のチェストのトローブを含む小さなデータセットと、200 個のチェストのトローブを含む大きなデータセットです。

私のバックトラッキング分岐限定アルゴリズムは、小さなデータセットを解決するのに十分な速さしかありませんでした。より高速なアルゴリズムは何ですか?

4

3 に答える 3

8

私はアルゴリズム競技に慣れていません。私はこの質問に少し戸惑いました: ブランチ & バウンドの一般的なアルゴリズムでブランチをカットするには、一般的な入力を把握する必要があります。

基本的に、小さなセットで提供された入力のいくつかを調べました。このセットで何が起こるかというと、何らかのタイプ t のキーを取得できないパスに行き着くということです。このタイプ t の残りのキーはすべて、同じタイプ t のロックを持つチェストにあります。したがって、それらにアクセスすることはできなくなります。

したがって、次のカット基準を作成できます: 開くタイプ t のチェストがある場合、タイプ t の残りのすべてのキーがそれらのチェストにあり、このタイプのキーがもうない場合は、このブランチで解決策を見つけてください。

カット基準を一般化できます。頂点がキー タイプであり、タイプ t2 のキーを持つ閉じたチェストが t1 にまだある場合、t1 と t2 の間にエッジがあるグラフを考えてみましょう。タイプ t1 の鍵を持っている場合、このタイプのチェストの 1 つを開けて、外側の端からアクセスできるチェストの 1 つへの鍵を少なくとも取得できます。パスをたどると、このパスで各ロック タイプのチェストを少なくとも 1 つ開けることができます。しかし、頂点へのパスがない場合、この頂点で表されるチェストを開く方法がないことがわかります。

カットアルゴリズムがあります。キーを所有している一連の頂点から、到達可能なすべての頂点を計算します。閉じたチェストがまだ存在する到達不能な頂点がある場合は、ブランチを切断します。(これは、バックトラックすることを意味します)

大集合を解くにはこれで十分でした。しかし、私はあなたが書いた最初の条件を追加しなければなりませんでした:

if any(required > keys_across_universe):
    return False

そうでなければ、うまくいきません。これは、キーの数がチェストの数に非常に近い場合、私のソリューションが弱いことを意味します。

このカット具合は安物ではありません。実際には、O(N²) のコストがかかる場合があります。しかし、それは非常に多くの分岐をカットしたので、それだけの価値があることは明らかです...データセットが優れている場合. （公平 ？）

于 2013-04-14T01:08:40.760 に答える
-1

私もこの問題を解決できませんでした。私のアルゴリズムは最初は遅すぎたので、いくつかの拡張機能を追加しましたが、他の何かで失敗したと思います:

  1. バレンティンが言ったように、トリッキーなケースをすばやく破棄するために、利用可能なキーを数えました

  2. 最初のヒットでキーが入っていないチェストを無視しようとし、次のチェストにスキップしました

  3. 高い胸から始まる解決策をスキップする

  4. 利用可能なキーがチェストを開くのに十分でない場合は、「キー ループ」を確認します (チェストには、内部にそれ自体のキーが含まれていました)。

パフォーマンスは良好でした (25 個の小さなケースで 2 秒未満)。ケースを手動でチェックしたところ、適切に動作しましたが、とにかく間違った回答が得られました :P

于 2013-04-14T01:14:00.017 に答える