AHCとは？

AHCとはAtCoder Heuristic ContestのことでAtCoder社が開催するマラソン形式のコンテストです。マラソン形式とは答えが決まっておらず、少しでもスコアをより良いものにして、他の競技者とそのスコアで勝負すると言ったものです。この形式のコンテストはほとんど参加したことがないのですが、AHCはこれから定期的(1ヶ月に1回くらい？)開催されるらしく、レートもつくので試しに参加してみました。今から、問題の概要と僕が考えた方針とその結果について書いていこうと思います。

問題の概要

AHC001問題文リンク
簡単まとめると、10000✕10000の広告枠に依頼された広告の矩形領域を振り分けていく問題です。 広告主からは領域に入れて欲しい座標と希望の面積が与えられるます。 その希望座標を含むように、できるだけ希望面積に近くなるように矩形領域を提供するようなプログラム作成せよという問題です。 厳密にいうと嘘の部分もあるのですが大体はこんな感じです。

方針について

今回、僕は全ての広告を横または縦で切った領域に分けるという方針をとりました。 全く同じx座標,あるいはy座標に複数の希望された座標がある場合は切った方向と垂直に分けるようにしています。 何を言っているか分からないと思うので以下の画像のようになるようプログラムを組んだんだなーと思ってもらえたら十分です。

こんな分割の仕方をする会社に広告の掲示頼みたくないと思うの普通ですが、なんとこんな分割の仕方で要件の88%達成したことになります！
次はこのような分割を組み合わせていくコードを書きました。
このときに分割するラインの場所やそのラインの増加数をランダムに決め、結果が良くなったらそのデータを保存していくと言った方法をとりました。
この「結果が良くなったらそのデータを保存していく」といった方法を山登り法というので良ければ調べて見てください。
ちなみに実は焼き鈍し法（山登り法の派生）っぽく一定の確率でラインを減らすといったプログラムも実装したのですが結果が悪くなった（と思っていた）ので その結果は下のようになりました。（これ時間計測ミスっていてちゃんと直したらかなり点数が上がりました！）

結果

得点は45391057665点(およそ90%)で順位は565位/1389位でした。
僕のプログラムの結果が悪かった理由は空白の面積が大きすぎたところですね。 広告の希望面積の合計はちょうど広告を貼れる全体の面積(10000✕10000)にいっちするので空白が多いとそれだけ点数が下がることになります。
実際、トップ層の人達は空白面積が少なく、点数の最大値に対して99%以上の得点を出していました。（すごいですね！）

最後に

方針とか雑になりましたがマラソン形式のコンテストはこんな感じでした。
まあ、結果はあまり良くなかったですが楽しかったので、皆さんも良ければ参加してみてください！