hotpepsiの練習帳

GDD 2011 DevQuiz

00:19

ウォームアップクイズ

Google Apps Scriptのクイズがわからなくて全試行してしまった。

Web Game

はじめてのChrome Extension

一度めくったカードを覚えておくようにした。

https://github.com/firewood/topcoder/blob/master/gdd_2011/solver.js

一人ゲーム

1. 数値は最大100万なので、21回半分にするとゼロになる
2. 最初にn回割ったときに数が5の倍数になるかどうかのテーブルを生成しておく。大きさは21個で済む。
3. 割るか除去するかで、なくなるまでBFSでまわす

https://github.com/firewood/topcoder/blob/master/gdd_2011/game.cpp

スライドパズル

さっぱり解き方が分からなかったので、ぐぐって8パズルの解き方とかを読む。

逆方向からも探索するのが良さそうだったので、スタートとゴールからBFSで全探索。

4x4までは解けたので、計算量を減らすために(1)評価値を計算(2)先頭からn個のキューだけ残すことに。

朝まで実行させたら9割方解けたので、残っている問題を閾値を増やして数問解く。

非常に単純な力技だが、最終成績は4961/5000で、予想以上に解くことができた。

評価値はマンハッタン距離ではなく、x^2+y^2としたのが良かったようだ。

https://github.com/firewood/topcoder/blob/master/gdd_2011/puzzle.cpp