« 「平方コピペ数問題」の高度じゃないコード | トップページ | 「ロング・ロング・ストリング問題」の高度じゃないコード »

2016年3月10日 (木)

『電脳体「キュラゲタム」を討伐せよ』の高度じゃないコード

「高度じゃないコード」シリーズその8はモンハンコラボ問題『電脳体「キュラゲタム」を討伐せよ』です。激ムズ問題のため協力プレイ可ということでしたが、何とか独力で解くことができました。挑戦期間が終了していて問題を見ることができませんが、挑戦の履歴から問題を転載させていただきます。(もし問題があるようでしたらご連絡ください)

クエスト:激ムズ!頭脳を【上限解放】~電脳体キュラゲタムを討伐せよ

★この問題は「激ムズ」のため、モンハンと同じく「協力プレイ」を可とします。挑戦受付中の相談はOKです。ぜひ協力して正解をめざしてください!

【二つ名持ちモンスター、電脳体「キュラゲタム」を討伐せよ!】
キュラゲタムは、キュラゲの中でも非常に珍しく周囲が見渡せるような高い場所でしか見られません。
このキュラゲタムを、最速で討伐して無事帰還してください!

【問題詳細】
マップ上を移動し、キュラゲタムの生息エリア(マップ上で最も高度の大きい場所)に向かいます。
マップ上のキュラゲタム生息エリアをすべて通りキャンプ(スタート地点)に戻るまでの最短時間を求めてください。

◎マップ
H×Wの格子状になっている文字列が与えられます。各地点には、0~9のレベルでその地点の高度情報が与えられ、移動方法・移動にかかる時間は次のように決まっています。

◎移動ルール
●隣り合う上下左右のマスのみ移動できます。
●高低差が無い場合: 1マス移動するのに3分かかります。
●高低差が「1」の上りの場合: 1マス移動するのに11分かかります。
●高低差が「1」の下りの場合: 1マス移動するのに2分かかります。
●高低差が「2」以上の場合: 上り・下り問わず移動することはできません。

例えば、2×3のマップ

    
   
   

で、左上から右上まで移動する場合、単純に右に進むと11+2で13分かかります。

  

しかし以下のように高低差を避けて回り込めば、3+3+3+3で12分になります。

  

◎注意点
●キャンプ(スタート地点)はマップ上の左上とします。
●キャンプ(スタート地点)からキュラゲタムの生息エリアまでのルートは必ず存在する入力データとなっています。
●マップ上の同じエリアを何回通ってもかまいません。
●キュラゲタムの生息地点数は最大15です。

【入力】
標準入力の1行目は、マップの縦サイズH・横サイズWが半角スペース区切り、2行目以降のH行分にマップデータとなる文字列が与えられます。

【出力】
標準出力に、最短時間を表す整数値を出力してください。

【入出力サンプル】
Input
4 5
32445
33434
21153
12343

Output
96

【入出力サンプルの説明】

↑↓
↓↑

マップ上での最高高度は「5」です。したがって、キュラゲタムは「5」の位置に生息すると判断します。
左上がキャンプ(スタート地点)ですので、上図のように移動すると96分で帰ってくることができます。

※問題内のモンスター、武器、アイテムなどは『モンスターハンタークロス』のゲーム内には登場しません。

この問題は2つの問題が合体したものと考えられます。1つは、与えられた条件における最短移動時間を求める問題、もう1つは、全ての目的地を最短コスト(この問題の場合は時間)で回る「巡回セールスマン問題」と呼ばれる問題です。

問題には書かれていないので、挑戦してみないとマップの最大サイズがわかりません。とりあえず、200×200 でコーディングしてみて最初の挑戦をしてみました。結果は、4問目でタイムアウトして、しかも、最後の2問は 250×250 であることが判明しました。

そこで、どこに時間がかかっているかを調べてみると、前半の最大16拠点(スタート地点とモンスターがいる最大15拠点の合計)間の移動にかかる時間の計算でした。後半は、短い時間で行けるベスト3を順次調べていくという最初に作った不完全な方法で時間的には問題ないです。そこで、後半の処理はそのままで、前半のアルゴリズムの見直しからすることにしました。それでもし、タイムアウトは回避できて不正解になるようなら、その時点で後半を考え直すようにしようと・・・。

そして、グッドなアルゴリズムを思いつきました。大きな流れとしては、1分で行ける場所を探し、2分で行ける場所を探し、3分で行ける場所・・・というように順番に探して行きます。(実際には1分で行ける場所はないので、2分からスタートさせていますが・・・)

さて、n分で行ける場所ですが、次の3つの条件のどれかを満たす場所となります。

1.n-2分で行ける場所に隣接していて高さが1下りとなる場所
2.n-3分で行ける場所に隣接していて高さが同じ場所
3.n-11分で行ける場所に隣接していて高さが1上りとなる場所

ただし、最大250×250のマップを全て調べていては時間がかかるので、過去11分間(n-11分~n-1分)に行けた場所と、今(n分で)行ける場所を書き込む、合計12分間の行ける場所リストを作成すれば高速チェックが可能です。

最初は、0分で行ける場所リストにスタート地点が1つあるだけですが、隣接地点で高さが1低い場所があれば2分で行けるリストに入り、高さが同じ場所があれば3分で行けるリストに入り、高さが1高い場所があれば11分で行けるリストに入ります。問題に出ている2×3のマップだと、スタート地点の下の地点が3分のリストに入り、その右が6分のリストに入り、さらにその右が9分のリストに入り、最後にその上が12分のリストに入ることになります。スタート地点の右の地点は11分のリストに入りますが、その右の地点はそこ経由だと13分となり、すでに回り込むことで12分で到着しているのでこのルートは評価されません。

そして、チェックの終了条件は、次のどちらかです。

1.12分間連続して行ける場所リストがなくなった
 (それ以降には行ける場所は増えない)
2.調べている拠点以外の最大15拠点への最短移動時間が全て埋まった
 (目的を果たした)

処理時間もほとんど変わらないので、私は終了判定が簡単にできる1を採用しました。

しかも、この方法は、目的地を定めずに行ける場所を広げていくだけなので、他の拠点全てへの最短移動時間を一度に求めることができます。
この処理を、スタート/ゴール地点とモンスターがいる地点の最大16箇所それぞれにつき1回づつ実行すれば、全拠点間の最短移動時間を求めることができるわけです。

こうしてコーディングして2回目の挑戦をしてみました。1問目~6問目までは「00.0秒 ○ 正解」でした。これは、勝ったなと思いましたが、7問目は「00.1秒 × 不正解」、さらに、8問目で「実行エラーです。 ソースコードに不備があります。」という初めて見るメッセージが出て、そこで挑戦終了となりました。で、ソースを調べてみて、毎分の行ける場所リスト用に確保していた配列が小さすぎたことが判明し、それを修正して3度目の挑戦をしました。7問目~8問目「00.1秒 ○ 正解」、9問目「00.2秒 ○ 正解」となり、「クエスト達成!」画面を拝むことができました。

クリアしてしまったので、後半の処理は、不完全ではありますがこのままでよしとします。また、16拠点からの到達時間の配列をそのまま残すなど無駄にメモリを使うコードだし、余り人に見せられる代物ではありませんが、提出したものをそのまま後悔・・・もとい公開してしまいます。

|

« 「平方コピペ数問題」の高度じゃないコード | トップページ | 「ロング・ロング・ストリング問題」の高度じゃないコード »

コメント

コメントを書く



(ウェブ上には掲載しません)




トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/99795/63324845

この記事へのトラックバック一覧です: 『電脳体「キュラゲタム」を討伐せよ』の高度じゃないコード:

« 「平方コピペ数問題」の高度じゃないコード | トップページ | 「ロング・ロング・ストリング問題」の高度じゃないコード »