buyoh.hateblo.jp

残念な競技プログラミング参加者による学習記録

ハル研究所プログラミングコンテスト2018に参加しました

ハル研究所プログラミングコンテスト2018とは

www.hallab.co.jp

自分にとっては

  • 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

f:id:m_buyoh:20181018203729j:plain

動き

ポッキーみたいなクッキーからキーボードみたいなクッキーまで色々

seed = 100 200 300 400 stage 18 です.

アルゴリズム・戦略

観察

  • 個体値があるものの,一般に大きい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にスコアのばらつきがあって,評価難しい.
  • 終盤のハル研の方々が強かった.

おまけ・去年の成果

ブログ書いてなかった.

結果をツイートして無い… 35~50位くらいだった記憶

*1:回転して置くことは出来ない.

*2:この記事を書いている途中で,この実装にバグがあることに気づいてしまった

*3:一通り置いたうえで,更に同じ種類のPieceを置けるだけ置く

*4:分割コンパイルなのでインライン化されない.が,Combine.cppとコンパイルオプションによっては同等の速度が得られるかも…