ハル研究所プログラミングコンテスト2018に参加しました
ハル研究所プログラミングコンテスト2018とは
自分にとっては
- 2度め.
- 2019年卒なので,今回が最後.
今年の成果
- 16位.食べられないクッキー獲得!
- 例年より参加者数が多いらしい.
問題概要
- 20x20のオーブンと,2つのレーン(SmallLane,LargeLane)がある.
- 各レーンには8つの生クッキー(Piece)がある.
- 毎ターン,次のいずれかの行動を取る.
- 何もしない.
- レーンからPieceを1つ取り出し,オーブンに載せる*1.レーンのPieceは自動的に補充される.
- オーブンに載せられたPieceは,Pieceごとに割り当てられる焼きターン数後に自動的に取り出され,Pieceごとに割り当てられるスコアが加算される.
- 補充されるPieceは完全なランダムではなく,「傾向」がある.
- 1000ターン以内に焼き上がったPieceのスコアの総和が,そのステージのスコアになる.
強そうな画像
seed = 100 200 300 400
stage 1 turn 686
動き
ポッキーみたいなクッキーからキーボードみたいなクッキーまで色々
seed = 100 200 300 400
stage 18 です.
— 舞葉 (@m_buyoh) October 18, 2018
アルゴリズム・戦略
観察
- 個体値があるものの,一般に大きいPieceほどスコアは高い.
- 上の動画のような色々なPieceの形が現れるのは稀で,似たPieceの形が現れる場合が殆ど.焼き上がりに20~100ターン程度.
- Stageによっては,大きなPieceは焼き上がるのに80~120ターン必要なPieceが現れるケースも.全体の1割のターン数を消費することになる.
- 小さなPieceは2x3程度のサイズが多く,1~12ターン程度必要.
- かと言って無視出来るターン数ではなく,12ターンのPieceを置いてしまって大きなPieceの配置の妨げになることもあった.
基本戦略
- 「隅から順に配置する貪欲」を各レーンのすべての順列に対して試す.
- 「隅から順に配置する貪欲」とは,以下の順に走査して,一番最初に置ける場所に置く操作を各ピースに対して行うこと*2
- ただし,横棒が多いステージの場合は転置したパターンで走査する.
1 3 5 4 2 11 13 15 14 12 21 23 25 24 22 16 18 20 19 17 6 8 10 9 7
- LargeLaneは再帰枝刈りすると十分高速で,制限時間にも間に合う.
- SmallLaneは間に合わないので,最大1000回乱択する.
評価
- 置くPieceたちとその位置を上の方針で決めた.これを評価したい.
- 評価値は,置くPieceの面積の総和+追加で置けるPieceの面積の総和*3.
- スキマのスコアを数値化したかった
- スコアは使いませんでした.
その他
- 計算したコマンド列を記憶して,置ける順に配置していく.コマンド列が空でなくても毎ターン計算して,スコアを上回るなら更新する.
- 残り数ターンで焼き上がる,Ovenに配置されたPieceは,LargeLaneのPiece配置決定時には見えないようにする.
- 数ターン待ったら大きいクッキーが置けたのに…みたいな事態を避けるため.
- 1000ターン時に生焼けのクッキーは点数化されないので,間に合わないクッキーは置く必要がない.
- こまかいこといろいろ
実装
Util::isIntersect
namespace::Util
の関数を使いましたか?- 初心者の人にも参加しやすくするためか,非常に読みやすい実装です.でも,(少なくともローカルでは)遅いです.*4.
- ボトルネックで使っていた場合,自分で書き直してinline付けてnoexcept付けるだけで(少なくともローカルでは)3倍早くなります.
- 同様にPieceも移植しました(MyPiece).
お気持ち
- 30位以内に入って良かった.
- 有名なアルゴリズムを特に導入しなかったのは残念(去年はTSP・K-meansなど).無理やり挙げるなら,順列列挙,XORShiftぐらい…?
- ソースコードは1000行くらい.
- seedにスコアのばらつきがあって,評価難しい.
- 終盤のハル研の方々が強かった.
おまけ・去年の成果
ブログ書いてなかった.
ハルコンはk-means++とTSPと嘘貪欲なので焼き鈍しも探索もしなかったです(ビームサーチ実装すればよかったと後悔) #ハル研プロコン
— 舞葉 (@m_buyoh) October 27, 2017
結果をツイートして無い… 35~50位くらいだった記憶