ハル研究所プログラミングコンテスト2018 参加記
ハル研究所プログラミングコンテスト2018に参加しました。ランキングは応募締め切り時点で14位でした。
追記(11/16): 結果発表より14位入賞しました。
問題概要
クッキーをオーブンでたくさん焼く
クッキーは長方形で大きさ、焼き時間、点数が設定されている(ランダム)
生地置き場には常に8個のクッキー生地があるように補充される
大きい生地のある置き場と小さな生地のある置き場の2つがある
1ターンにできる行動は「生地を置く」または「何もしない」
1ステージ1000ターン
20ステージの総点数がスコア
置き場にある16個のクッキーの他にどんなクッキーが補充されるかはわからないのでそこをどう処理するかがポイントです。とりあえずスタートは「各クッキーに対して左上から順に置けるマスを探索して置けたら置く」を書いて2.25M点でした。
score 2.25M
作戦1: 面積でソート
点数を稼ぐにはたくさんの生地をオーブンに置きたいです。また大きい生地は小さい生地に比べ点数がとても高いです。そこで隙間なく大きな生地をオーブンに置いていくために大きい生地から貪欲に置くことにしました。小さな生地は隙間におけるので後回しにします。いろいろ試した結果、面積が大きいものから置くのが最も点数が高くなりました。これ以降もこれを採用しています。 また、置いても1000ターン目までに焼き終わらないものは無視するようにしました。
スコア 2.25M -> 2.38M
作戦2: 囲まれているところに置く
veiwerを眺めていると大きな生地がオーブンのど真ん中に居座って邪魔になっている状況を発見しました。今までは置ける場所を見つけた瞬間にそこに置いていたので他にもっと「いい感じ」の置ける場所がないか探索するようにしました。具体的には生地を置いたとき「周囲何マスが生地またはオーブンの淵であるか」を数えてその数が最も大きくなる場所に置くようにしました。同じ値同士ならその中で最も左上の点にします。
score 2.38M -> 2.41M
作戦3: 重みをつける
仮に置く場所が囲まれていても周りが数ターン後に焼きあがってしまうのでは結局孤立してしまい意味がないので「置く生地に対して何ターン早く焼きあがるのか」で先の方針に重みをつけます。置く生地より後に焼きあがるのは無視することにして max(dif,0) を周囲の各マスで求めて総和をとります。(dif=自分の焼き時間-そのマスにある生地の残り焼き時間+1) この値が小さいほどターンが過ぎても孤立しずらいことになるので最も小さくなる点に置きます。置いた瞬間1ターン経過するのでそれを加味して+1します
score 2.41M -> 2.51M
作戦4: 邪魔になる小さなクッキーを置かない
またveiwerを眺めていると小さな生地が置いてあるせいで大きな生地が置けていない状況を発見しました。試しに小さな生地置き場からまったく置かないコードを実行してみると意外と点数が落ちませんでした。むしろ点数が上がっているステージすらあります。つまり大きな生地を置くだけでかなり点数が稼げるということなので、なるべく大きな生地を置いてからどうしようもない隙間があるときだけそこに小さな生地を置くという方針にしました。
score 2.51M -> 2.56M
作戦5: いままでに出てきた大きな生地を記録してがんばる
この辺で締め切り前日。次にどんな生地がくるか予想して将来小さなクッキーが邪魔になるかどうか判定したかったので頑張って確率っぽいものを出してパラメータをちょこちょこいじりながら点数UPを狙いました。ラッキーなことにいい感じの値をひけたのでPONと点数が上がりましたが理由がよくわかっていないので複雑な気持ちです...
score 2.56M -> 2.59M
応募締め切り時点でのスコアは 2,594,947 になりました。
感想
今回初参加でしたが目標のTOP30に入賞出来そうでうれしいです。マラソン経験はまだ浅く焼きなましやビームサーチができないのでそれをしなくてもスコアを稼げた問題でなんとかなった感じはあります。また来年あれば参加したいと思います。
楽しく深い題材のコンテストを開催してくださったハル研究所のみなさんありがとうございました！
