FC2ブログ

CodinGame HARD 前編

つづき



The Labyrinth

まず?マスのないマップを作成するために、前の問題のロボットみたいに行き当たりばったりに歩く。一度行ったマス目に来たら、バックトラックしながら行ったことのないマス目を探して歩く。燃料が少ない場合は効率のよい歩き方を考えなくてはいけないが、今回はとても使い切れないほど大量にあるので適当でもなんとかなる。
最初コントロールルームは無視しておいて、?マスもしくはまだ歩いてないマスがなくなった後で向かう。ここに入るとカウントダウンが始まるので、入り口までの最短距離を探索しないといけない。
各マス目に評価値を設定して、そのマス目までのより短いルートを見つけたら評価値を更新、それ以外は探索を打ち切ることで枝刈りするというダイクストラ? なんか違うような気もするけど多分ダイクストラだと思う感じのアルゴリズムを使ったら解けた。

提出用データでしか発生しないバグが生まれて困ったが、単に上下反転してるだけだったのでCUSTOMで再現してデバグしたら解決。
マップデータを配列に読み込む際、端っこは壁になってるから画面外に飛び出すかどうか気にしなくていいと思っていた処理部分で、よく見ると2つ目のケースだけ端っこが開いてるのが原因。上が開いてると出てくる配列の要素番号-1は、rubyの仕様上反対側の端っこと繋がるように使われるだけなのに対し、下が開いてると上限突破して落ちるというバグだった。



APU: Improvement Phase

とりあえず主な処理は以下

・確定判定:隣接ノードの持っているリンクの数から作成可能リンク数を計算し、それがナンバーと一致していれば全確定。ナンバーより1多ければ少なくとも1本は確定。
・仮置きフェイズ:隣接ノード数2の未確定ノードについて、作成可能リンク数1なら(01 10)、2なら(02 11 20)のように分岐させながら仮のリンクを作成して、その変化によって更にリンクが確定できるか確かめる。矛盾が発生したらバックトラック、矛盾はないが完成していなければ次のノードで更に仮置きして全体を走査する。
・ナンバー全消費時処理:自分と相手と自分の隣接ノードと相手の隣接ノードの隣接ノード数を減らす。自分から見て相手ノード、相手から見た自分ノード、自分の隣接ノードから見た自分、相手の隣接ノードから見た相手を削除。自分と相手にリンク情報を追加。
・交差判定:通ったグリッドの交点座標を全て保存しておいて、同じ所を通るリンクを作ろうとしたら失敗扱いとする。
・全接続判定:全リンク数が全ノードナンバー合計の半分になったら使用。1つのノードからリンクを辿って、通ったノードをリストに入れていく。リストサイズとノード全部の数が一致すれば解答成功。

ここまでで一応理論上は全部解ける状態ではあるがスコア70%弱。遅すぎる。

とりあえず全方向について考えてるのが悪い。
よく考えたら仮置きフェイズでは周り全部ノードの状況を気にする必要が無いし、左上から順番に辿っていけばリンク対象のノードは右と下だけに限定できる。というかmediumではそうなってたんだから素直にそれに従えばよかった。
これでCGとexpert除く85%までは到達。更に何らかの枝刈りが求められる。

・島発生判定:リンクを作成し尽くしたノード群が孤立したリンクを形成しているかどうかを、全接続判定でリンク作成するたび判定する。この処理自体が重いので使うと問題によっては逆に解けなくなる。
・下方向先取り判定:右方向にリンク作った時は直後で判定するので問題ないが、下方向のノードが消えた時、その先のノードで矛盾が発生するとしてもだいぶ後にならないとわからないので、先に判定してしまう。

この2つ合わせるとCGが解けるようになったのでそれなりの効果はあるようだが、Expertが強大すぎてもっと画期的なアイデアでないと意味がない。

交差判定を見直す。上記のだと次に交差してしまう線を引く時になるまで失敗しているかわからないので効率が悪そう。
まずノードがないグリッドの交点全てについて隣接ノードを保持したインスタンスを生成し、リンクを作成した時に通った交点の隣接ノードから見た隣接ノードを削除する。
更にその変化したノードについて確定判定を……と考えたがこれは1周回って処理中のノードに帰ってきてしまった時に割り込みが発生してバグの温床になったので取りやめ。
そこまでしなくてもこの処理は非常に強力で、提出用Expertの全体に確定判定を5回繰り返すだけで仮置きフェイズに入るまでもなく解けてしまう。どんどん壁が作られて自由を失っていくイメージ。

というわけでどうにか完成。これはすごい時間かかった……。STDERR.putsだとちょっと長くなると表示できなくなるから大量データのデバグは大変すぎる。仮置きリンクはデバグ用映像に出せないから宝の持ち腐れ状態だし。間違ったのを置いた瞬間エラー起こすんじゃなく、取り消しコマンドで消せれたりすればもうちょっと楽だったろう。



Skynet strikes back

今回は1つのノードから複数のゲートに繋がる箇所がある。余裕がある時はそこを切ればいいんだけど、単にエージェントから近い複数ゲート持ちノードを選んでも、最後のケースではうまいこと遠くに誘導されて失敗するように設定されてる。

まずエージェントから一番近いゲートを探し、すぐそこに迫っているなら即切断する。組合せ爆発しないよう3個ぐらい先を見れば十分。
余裕があるときは、さっき見つけた一番近いゲートへのリンクを仮切断した上で、更一番近いゲートに向かってエージェントを仮進行させる。
仮切断仮進行を繰り返し、初めてエージェントが複数ゲート持ちノードに仮到達した時、そこのリンクを真切断する。この繰り返しも4回ぐらいで十分。

前回の多重配列をクラスにして書き直したらめっちゃすっきりしたのもあり、かなり楽に書けた。



Skynet: The Bridge

EASYのが簡単すぎたのと入力形式も変わってるのとで初めてやるのと変わんない。

今回もさっきまでの問題と同じように、まずこのゲームのシミュレータを作り、暫定コマンドを適当に選んでシミュレートし、死んだらバックトラックして別のコマンドに変える、を繰り返せば良さそう。

ただし全員生き残るパターンを探す→無理なら多少犠牲が出るパターンを探す、ってやると全探索が含まれていて組合せ爆発起こしそうなので、ある程度の所で探索を打ち切る効率化は必要か。あと状況に合わせてコマンドの優先度を変えていったりとか……
……と考えていたが特に工夫なく組んだら3つ目の実績まであっさり取れたわ。



The Paranoid Android - One step further

これもこれまでのパターンからしてシミュレートで探索するところだが、問題が単純なのでそこまでしなくてもミディアムのに条件継ぎ足すほうが早いんじゃないかと思った。(同じ解き方するのに飽きてきた)

1-5.エレベーターがない階では作る
6.一番近いエレベーターを選ぶ
7.一番近いエレベーターが遠すぎる時は自分で作る(ステージの広さで「遠すぎる」の基準は変化)
8.ゴールまでの階数分エレベーター作成可能数が余ってる時は真下まで行って作る。重なってるエレベーターがある時は多少遠くてもそっちを選ぶ。
9.自分の真上にエレベーターがあるときは作る(作成可能数が余ってる場合)
10.ゴールの左右を走査、エレベーターがあったら下に降りるを繰り返し、通った地点におけるエレベーターの使用と建設を禁止する。

だいたいこんな感じで解けた。厳密解じゃないけど、タイトルの下に貪欲法って書いてあるから今回は近似解でもまあいいんじゃないかという解釈。



Indiana - Level 2

まずシミュレートでルートを探索するが、岩がいつどこから来るのか実際に岩が出現するまでわからないので、まだ回転方向のコマンドを決められない。どのマスを通るかだけを記録する。後ろに戻ることが出来ないゲームなので、探索効率化はそこまでしなくても大丈夫。マスごとに入った方向と出た方向の組み合わせ履歴を保存しておいて、同じ組み合わせが現れたらその先は調べないことにする程度。
始まったら通る予定のマスをどんどん通れるように回転させていく。直前になってから変えていたのでは、2回回転させるパターンが間に合わない。
更に余裕がある時は仮ターン進行させることで岩の様子を見て、一番最初に主人公にぶつかるであろう岩を探し、その岩の通り道のどこかのマスを回転させることで道を塞ぐ。

なんだか道作成処理と岩破壊処理の合流ポイントの部分が偶然解けているだけのような気もするが、例題の種類が少なくて正しさが確かめられない。ベリハへ課題持ち越し。

回転方向と進行方向の両方でLEFTとRIGHTがでてくるのややこしいと思った。clockwiseとcounterclockwiseなら……長いし余計わかりにくい。
あと1ターン目に入らないと主人公がどこから来るのかわからなくてシミュレーション開始できないのなんか気持ち悪い。



Thor VS Giants

今までで最もゲームっぽい。

毎度おなじみシミュレートして探索。EASYのがgiantの行動シミュレーションに使える……かと思いきや。
最も単純な実装ではまず斜め移動して軸を合わせてから直線で近付く形になるが、実際にはThorに対する角度が45度周辺の時は斜め、それ以外はまっすぐという感じに近づいてくる。更には重なってしまった時にどう動くかも考えなくてはいけなくて……。
この仕様詳細を左側の説明に書いてないのずるくないか。コーディングを楽しむという目的から外れてるというか。

どうも移動法を完全には調べきれなくて、若干シミュレートと実際の挙動が一致していないが、状況に応じてコマンド調べる優先度入れ替えたりしたら解けたのでそれで済ませた。ちょっと不完全燃焼。

移動法を考えなくてもいいように、giantに触れないように全giantの平均位置に向かって移動してある程度まとまったら攻撃、というシミュレートなし行き当たりばったり方針が推奨されているのか? でも最後の問題は行き詰まるような気がするな。

どうでもいいバグとして、方角を一文字目と最後の文字の切り出しで判断しようとすると、STRIKEのSとEが引っかかるという罠が。なんだこの単語チョイス。



Vox Codei

ボンバーマン。

まず全マスに仮仮爆弾を置いてみて、爆発した時に破壊されるブロックの数を計算する。一番多かったマスを仮爆発させたという体で、更に仮仮爆弾により次の仮爆弾の位置を探すことを繰り返し、ブロックがなくなったら成功として実爆弾設置作業に入る。
失敗した時は1つ目に置いた仮想爆弾の位置を覚えておいて、その場所は選ばないようにまた同じ処理を繰り返す。
実爆弾は3ターン後に爆発するようにして、置きたい場所のブロックがまだ破壊されていなかったら、WAITしてその爆弾設置は後回しにする。

連鎖爆破させないと間に合わない問題とかがあるときつかったところだが、今回はラウンド数設定がガバガバだったので簡単だった。ベリハにはありそう。





ここまで記録
Hard 50%Done
CodingPoints 5,569
GlobalRank 951/313,638
CountryRank 24/9,148

HARDは最初問題見た時はウワッとなるが、ウンウン唸って考えると光明が見えて、試行錯誤続ければ正解に辿りつけたりつけなかったりする、個人的にかなり心地いい難易度と感じる。
今のところ迷路と経路探索とバックトラッキングばかりなので違うタイプの問題もやりたい。後半はパッと見た感じ色々ありそうだから期待。
  1. 2016/01/28(木) 05:09:21|
  2. CodinGame
  3. | トラックバック:0
  4. | コメント:0
<<CodinGame HARD 後編 | ホーム | codingame mediumまで攻略メモや感想など>>

コメント

コメントの投稿

管理者にだけ表示を許可する

トラックバック

トラックバックURLはこちら
http://pseudonym.blog94.fc2.com/tb.php/1068-f7d4d030
この記事にトラックバックする(FC2ブログユーザー)