第26回全国高等専門学校プログラミングコンテスト 競技部門 プログラム解説
やるべきことやっただけという感じのビームサーチ。 なお気付かなかっただとかでやり漏らし多数。
ビームサーチは始めて書いたので変な点もあるかも。
https://github.com/kmyk/procon26
厳密解
まず書いた全探索をするやつ。 ビームサーチと共通の部分はまずこちらで実装/試験してからビームサーチにも適用した。
石の設置可能性判定 文字列検索の応用
石を構成するマスをvector<point_t>
と保持し、舐める。
ただし、Boyer-Moore法とかのように、盤面と石のマスのそれぞれに関してそのマスで衝突が発生した場合に次に何マスずらして探索再開すればよいかを事前計算しておき、それに従って処理を減らした。
石を構成するマスと盤面の衝突の判定は、進行方向奥のものから順に行なうと速い。
石を64bit整数に詰め込むことも考えたが、石をずらす場合の処理に対応できないと誤認して選択肢から外してしまった。 他の人のプログラム解説見て気付いた。
石の回転/反転 同一物の無視
ある回転/反転をして他の回転/反転の結果と同一なものは無視する。
ビームサーチ
石を順番に前から見ていく。 その石に関し、回転/反転/場所を全て見ていって、置けるなら次の状態候補に追加。 最後の石まで見終わったら終わり。
評価関数
純粋にそのひとつの盤面の状態からのみの関数。 置いた石の面積、周囲の長さ、小さい非連結成分の数などに固定の係数を掛け、今見ている石が何番目かを使って傾きを付け、足し合わせるだけ。
視覚化
真っ先にやっておくべきだった。
全然性能がでず困っていたときに、そういえば視覚化してないなとこれを書いたら、バグが埋まっていることが判明して最高だった。 あと本番座ってるだけで暇だけど、これがあると眺めてて楽しい。
石をちょうど嵌めれるときは必ずそう置く
heuristicな枝刈り。効果があったので採用。
石による盤面の分割
石を置くと盤の空白成分が複数に分割されることがある。 特に、1x1や2x1の小さな非連結成分は重要である。 そのような新たにできる小さな非連結成分に関してカウントし、全く同様の非連結成分のみを作る置き方に関しては1度のみ行なうようにした。
小さな空白/石の数
小さい空白の数が小さい石の数を上まわると多めにペナルティを与えるよう評価関数を書いた。
周囲の長さ
盤面の障害物の縁の長さが短かいほど盤面として綺麗な形であるので、これを小さく保つように評価関数を書いた。
盤面のハッシュ値
盤面から空白か否かの情報だけを取りだしbitset<32*32>
を作る。
ビームに採用された盤面のこれをunordered_set
に入れていき、同様のものは二度とビームに入れない。
これをしていたのでchokudai化は容易であった。
時間の自動調整
まず細いビーム幅で走らせ、その所用時間と制限時間から、ぎりぎり間に合うビーム幅を計算し実行する。
メモリは見ていないので、制限時間が長い決勝ではoom killerを招いた。
chokudai化
2日目の朝に突貫で行なった。 あまり有効に作用していたようには見えなかった。
optionで有効化する。
並列化
プログラムは1threadで動くので複数独立したprocessを立ち上げ、簡易な並列化をした。
提出器
簡単なpythonのscript。 1日目リハーサル後から1回戦の間で急いで作った。 最高得点をfileに保存しておきそれより良いものが流れてくると提出を行う。 なので複数同時に実行でき、必ず最良の解を提出してくれる。
反省
非決定性
ない。
乱数を入れておくべきだった。決勝の最中に気付いた。
多様性
ない。
最初の10石ぐらいで、盤面のどの場所から埋めていくかが決定してしまう。 ついでに言うと非決定性がないので、複数回実行しても毎回だいたい同じように埋める。
パス
しない。
後半の大きな石はほぼ必ず使われない。
計画性
ない。
半年ほど準備期間があったのにほぼ何もせず、長野県に行ってから必死で書いてた。 殆どの期間、チームのふたりに何を任せればいいかすら分かっていなかったので、結局本体のコードは私しか触っていない。 せっかく作ってもらった手動用のguiも、ハブもLANケーブルも持って行ってなかったので一切使えず。申し訳ない。