Who am I?

learningBOXの西村です。QuizGeneratorを2011年頃に作っていたらいろいろ仕事が舞い込んできて法人化して今に至ります。夏頃からAHCに参加していたのですが、今回は社内でおそらく1位を取れたと思うので参戦記を書くことにしました。（社内にAHC青は2名いるようです。）

AHCとは

AtCoder Heuristic Contest（AHC）とは、AtCoderにて定期的に開催されるプログラミングコンテストです。コンテストでは厳密解を出すことが困難な問題が出題され、それに対してなるべく最適な（コストの小さい）解を求めるプログラムを書きます。今回のコンテストは制限時間4時間となっており、AHCとしては短めのコンテストでした。（長い場合は開催期間が1週間を超え、社会生活に著しい影響をもたらす危険性があります。）

問題概要

1～200の番号が書かれた箱があります。これらの箱をランダムに20個積んだ山が10個あります。1番の箱から順番に取り出したいのですが、取り出したい箱の上に別の箱がのっていると邪魔で取り出せないため、あらかじめそれらの箱を別の山にのける必要があります。箱をのけるコストを最小にしてください。

提出回 / 開始からの時間 / 得点 / 順位 / パフォーマンス

以下に提出回ごとに、コンテスト開始からの経過時間、得点、そのまま終わったら何位だったのか、そのまま終わった場合のパフォーマンスがどれぐらいだったのか、やったことや考察を記していきます。

提出1 / 30:53 / 1218950点 / 順位（719/789）パフォーマンス 584

正の得点を得るためのほぼ最小限の実装

https://atcoder.jp/contests/ahc026/submissions/47297856

1番の要素から順番に取り出せばよい。ということで、1番から順番に以下の操作を行うことで正の得点を得ました。
・i番の場所を探す
・i番の上に何か乗っていたらどこかによける
→1か所に積みすぎるとよくなさそうなので、i番の存在しない山をランダムに選ぶ。
・i番を捨てる

提出2 / 42:58 / 1319252点 / 順位（624/789）パフォーマンス 827

移動先は箱の数が一番少ない山とする。

https://atcoder.jp/contests/ahc026/submissions/47298348

山の高さに差がつくとよくないので自分以外で一番低い山によける。
ちょっとした改善だけど、これで緑を確保できました。
アルゴリズムコンテストで緑をとるよりハードル低いですね。

提出3 / 1:04:32 / 1358758点 / 順位（406/789）パフォーマンス 1289

移動先は小さな番号が含まれてない場所とする。

https://atcoder.jp/contests/ahc026/submissions/47299421

1番の箱をのける時点では、2番が含まれている山に200点、3番を190点・・・21番を10点加えた上で評価した。提出のタイミングでは黄パフォ、最終結果でも水色を出せる筋のよい改善だったようです。

提出4  （1:18:17）1359228点 / 順位（403/789）パフォーマンス 1295

箱の個数を評価対象外とし、”直近”の評価を非線形に変更。

https://atcoder.jp/contests/ahc026/submissions/47300118

i番目の箱を動かす段階で、i+j番目の箱のある山に、j**0.88の重みを載せました。得点改善はわずかですが、マジックナンバーが減りコードがすっきりしました。

提出5  （1:54:27）1378811点 / 順位（236/789）パフォーマンス 1619

分割してよける。

https://atcoder.jp/contests/ahc026/submissions/47302042

以下のような山があるとします。

[底] 5 1 10 20 30 2 40 50 60

このとき、1を取り出すためには、[10 20 30 2 40 50 60]を別の山に移動すればよいのですが、1回で取り出さずに、[10 20 30 2]と[40 50 60]の2回に分けるとどうなりますか？

たぶん楽になります。

ということで、i番の箱を取り出す際に i+17 以下の箱がある場合はそれが上になるように分割移動しました。本質的な改善は実はこれでおしまいです。0.88とか17という数字は一見適当に見えますが、すでにある程度しっかり評価はとっており、最終提出（0.875と 15～20のランダム値）とほぼ同じでした。

提出6  （2:24:33）1387894点 / 順位（133/789）パフォーマンス 1886

得点計算の実装と乱択

https://atcoder.jp/contests/ahc026/submissions/47303673

提出5までの処理に対してランダム要素を付け加え複数回実行し、最善の結果を提出しました。提出5で分割する際には17で固定していた範囲を15～20のランダム選択とし、提出4で実装したよけ先の山に対して0~0.1の間のノイズを載せました。乱択を使えばある程度点数が伸びるのは分かっているのですが、あまり早い段階でこれをやり始めてしまうと本質的な改善をやりづらくなってしまうのが悩みどころですね。

提出7  （2:51:52）1388683点 / 順位（127/789）パフォーマンス 1909

性能改善と試行回数の向上

https://atcoder.jp/contests/ahc026/submissions/47306674

ランダム性を使うようになったため、処理速度を上げるだけで多少は点数の上昇が期待できます。i番目の要素の場所を特定するために、全要素探索していたのでそれをやめることで速くなりました。4倍ぐらい速くしたら、優位に点数が向上しました。（C++に実装しなおすことも考えました）

提出8  （3:24:49）1389017点 / 順位（126/789）パフォーマンス 1913

さらなる性能改善

https://atcoder.jp/contests/ahc026/submissions/47306674

関数呼び出しコストの削減などでさらに高速化しました。提出6と比べて7倍程度まで速くなり、わずかながら得点も向上しました。

提出9  （3:43:07）1389271点 / 順位（121/789）パフォーマンス 1926

提出10（3:53:48）1389263点 / 順位（121/789）パフォーマンス 1926

提出11（3:59:32）1389354点 / 順位（119/789）パフォーマンス 1937

提出9～11はほとんど同じコードです。パラメータを微妙に調整することで上がったようにも思いますが、ランダム性によって上がった可能性も否定できない程度の向上でした。短期AHCにおいてはすべての提出の中で最大の得点が採用されるようなので、同じコードであっても追加で提出するのはありかなと思いました。

まとめ

今回のコンテストでは、前半の2時間を本質的な改善、後半の2時間で乱択の実装と性能チューニングを行うというそこそこバランスのいい戦い方ができました。まだまだヒューリスティック初心者で焼きなましやビームサーチなど使えたためしはないのですがコンテスト後にしっかり復習して次につなげたいです。

動画

募集してます

バックエンドエンジニア、インフラエンジニアを中心にエンジニア募集しています。AHCそのままの課題は業務では発生しづらいですが、サーバの負荷特性の調査やボトルネックの改善などAHCやアルゴリズムコンテストでの経験が生きる業務もたくさんあります。