画像は公式Visualizerからお借りしています(Seed=0)
はじめに
本日は、AtCoderにて9/17~10/1に行われましたAHC014の参加記録を記していきます。今回は最初に軽く最終提出を紹介します。また、最終提出に至るまでいろいろな提出を行ったのでそれらを日記風に時系列順にまとめて紹介をする流れになります。解説、検討というよりはどちらかというと日記です。
なお、過去の自分の提出を見て振り返りながら書いているので、心情描写についてコードを書いた当時の心情と一致していない可能性もあります。
最終提出のプログラム
・Go言語
・評価値による貪欲
・評価値に多少の乱数を入れて時間いっぱい貪欲をやり直す
システムテスト前 50ケース最高記録 53.0M(58位)
システムテスト後 50ケースあたり 52.4M(60位)
でした
コンテスト日記
9/17~9/20 コンテスト参加検討期
今回は開催期間が2週間もあり、休日も多いので時間が取れるのではないか、と思い参加登録。このときはやる気十分だった。
しかし、問題文を見るや否や、やっぱりやめておくか、となった。恥ずかしい話、最近はAtCoderのコンテストに出ていなかったので問題文のN,M,p,iや得点の計算式を受け入れることができなかったのである。
以降、しばらく自分のいない順位表を眺めるだけであった。
最初の週末を何も提出することなく過ごした自分に、天啓が降りる。それは、自明解である(気づくの遅くないか？)。入力を無視して０を出力すると、なんとACだというのだ。これを何の気なしに出してみると14M改善した(0M→14M)。斯くして正の得点を得た私は、抜け出せないコンテストの沼に足を突っ込んでしまったのである。
9/21~9/22基本方針確定期
自明解の発見は14Mもの改善をもたらしたが、順位はあまり芳しくなかった。自分のプログラムで特に違和感を感じたのは、まだ格子上に点が置けるのに置かない点である。この問題を解消するため、各座標に対し、その場所に新たに点を置けるかどうかを返す関数を実装することにした。(正確にはその点を起点として作ることのできる四角形を列挙する関数)
これが、書くのが遅い私にとっては難所となった。なおこれを書き終えたところであまり実用的な実行速度ではなかったのだが、このときの私はまだ何も知らなかった。
(少し実装の紹介)
判定の仕組みは非常に簡単である。スタートの座標から1マスずつ一直線に移動しながら、そこに点があるか、すでに間に線が引かれたかを確認する。線があればその段階で四角形は作れないことがわかるので中断する。すでに点がある座標に到着したら、時計回りに90度回転し、1マスずつ進んでゆく。これを繰り返し、スタートの座標に無事もどることができるか見れば良い。図付きの説明は最後の「よくありそうな質問」で。
この関数を実装し、置くことが可能な点を左下から探して見つけ次第おいていくことができるようになったのはn時間の実装作業の後だった。単純だが、スコアは自明解の比ではない。これを提出することにより・・・と思ったら提出していなかった。あまりに遅かったようで、ビット演算での処理が今後行えるよう点と線の情報をbitboardにしてから提出していた。(盤の情報をbitboardにするのはマラソンの問題で大いに役立つテクニックなので、もし知らなかった方がいれば一度調べてみてほしい)これにより16.5Mの改善(14.0M→30.5M)に成功する。
このとき、上で述べていた判定の関数が遅かったので二手先などは考えず「この座標に点を置くこと亅に対して得点をつけることにした。すなわち貪欲である。この方針は最後まで貫くことになる。
で、さっそくの手詰まりである。手動でテストケースをプレイしていても何もわからない。中心から遠いところに点がある方がいいのでは？と思い始めたころに上位の人が共有しているVisualizerを確認してみると、なんとめちゃくちゃ点が埋まっているではないか。
したがって、「小さい長方形から優先して作る」というのが続いての目標となった。これは得点として長方形の外周の長さ×-1を採用することで完成した。申し訳程度に同じ大きさの長方形なら中心から遠いのほうを採用した。(30.5M→32.0M)
ここで、一番小さい斜めの長方形の外周が8と計算されていたのでそれも斜めでない場合と同じ4となるように計算方法を変えて再提出した(32.0M→33.9M)
また実行時間2sと勘違いしていたので5sに変更(33.9M→34.0M)
（ランダム要素がないのに微増したということは一部のケースで2sでは間に合わず切り上げていたということに・・・）
さすがに実行速度が遅すぎてこれはやっていられない、と思い就寝。天井を見ながら「コンテストが終わるまでに40Mに到達する」を目標に掲げる。翌日は最低限の高速化に努めた。一番重かったテストケースがおおよそ3倍速に。(2300ms→800ms)
(点と辺のbitboardを上方向、右上方向、右方向、右下方向でもつことで長方形の大きさにかかわらず同じ時間で長方形が作れるか判定できるようになりました。このあたりの話は最後の「よくありそうな質問」で。)
時間に余裕ができたのでがちゃがちゃ評価関数をいじってみたけどほとんど変わらなかった。多分あまり本質的な部分ではなかった。(34.0M→34.2M)
時間に余裕ができたので、評価関数に若干の乱数を入れて時間いっぱいやり直すことにするとこれはかなり改善した(34.2M→37.2M)。とはいえ、一番重いケースだと6回くらいしか試せていないので乱数次第でかなり得点がぶれるようだ。乱数の取りうる範囲を狭めてみると多少得点は変わったが(37.2M→37.4M)、よくなったのかどうかわからなかった。
で、またしても手詰まりである。上位の人が共有しているVisualizerを確認してみる。よく見ると、小さい長方形が市松模様のように並んでいるではないか。こうして、「市松模様の形になるようにおける場合は特に優先するのがよいのではないか」という天啓を得る。雑な実装、より適切な実装、市松模様判定の高速化の段階を経て得点が伸びる。(37.4M→38.3M→40.3M→40.8M)
（実は作ろうとしている長方形で各頂点で辺をもう1マス伸ばしたところにすでに線が引かれているかでわかるのである。
一本でもひかれていれば、市松模様が繋がる。）
斯くして布団から天井を見て掲げた40Mの目標を早くも達成するのであった。
9/23~9/27 現実逃避期
思いつくことを実装しきって40Mに到達したことで、非常に高い満足感を得るとともに、今の自分ではもうこれ以上は伸ばせないだろうという思いが湧き上がる。最終結果を知る今から見ればこの方針のまま少なくともあと13Mも改善できる余地があるのだが、一度こういう気持ちになってしまうと本当に何も思いつかないのでどうしようもないのである。
うーん、AHCやめるかぁ・・・。
この期間中何もしなかったわけではない。ローカルで50ケース程度の得点をとってみた。するとMが小さい（すなわち初期状態に置かれている点が少ない）場合は小さい長方形を優先的に選んだことでむしろ得点が悪化していることに気づく。おそらく小さい長方形を連鎖的にうまく作ることができないのだろう。よってMが小さいケースについては長方形の大きさによる評価値の影響を小さくし、苦し紛れの改善に成功する(40.8M→41.2M)。成功したのか？乱数の運程度の誤差ではないのか？とも思われるが、とりあえず成功したことにしないとこの期間の進捗はなくなってしまうのでこれは成功したことにする。
9/28 運命の日
コンテストも終わりが近づいている。なんか順位もむちゃくちゃ下がっている。「ああ、やはり対戦botを作るタイプのコンテストのほうが得意なのかなあ。こういった得点最大化タイプのコンテストだと、自分のプログラムの粗削り感があらわれてしまうんだよなあ。」と思いながら試行錯誤していたところの出来事である。22日から変わらず市松模様の理想をベースに評価を加えていたところ、3M近く改善したのだ(41.2M→44.0M)。やはり市松模様が正解だと思うとともに久しぶりの大幅改善でやる気がよみがえってくる。
また、ローカルテストで、Nが小さいときは選択肢が少ないため何度やり直してもほとんど決まった結果が出ていた。そのため、Nが小さいときは乱数の影響を多くしていろいろなパターンが出るのを期待した。(44.0M→44.8M)
なぜ、40Mで止まっていた最高点を大幅に塗り替えられたのか。おそらくこれを読んでいる人（そもそもいるのだろうか）のほとんどはこの改善が気になることだろう。実際、この改善は自分のモチベーションとしても40Mから50Mへの要素としても重要な部分であり、おそらくほかにこれを実装している人はいないだろう。が、残念ながら語ることができない。なぜならば、「バグ」だったからである。私はこの時追加したものがバグでどのような評価を与えているかわかっていないからである。この時の私はバグには気づいていなかったので自分の発想が正しかったのだと思い込んでいる。一応、バグによる評価値の加減は最後の「よくありそうな質問」で述べている。
9/29~9/30 高速化期
いよいよもう方針転換はできないころである。高速化して試せる回数を増やすほかないかと思う頃にまたしても自分に天啓が降りる。それは、有効な手を調べる際のループ回数の減少による高速化である。
アイデアは以下のとおりである。
・初期盤面ではN*N個の各座標から8方向に長方形を作ることができるか調べ、評価
・調べた結果を保存する
・最良の点を決定した後、次にその点を使って長方形を作ることができるかもしれない座標を、暫定的に作ることができる場所として調べた結果に追加する
・調べた結果を参照して、長方形を作ることができる場所が本当に長方形を作ることができるか調べ、評価
・調べた結果を保存する
・最良の点を決定した後、次にその点を使って長方形を作ることができるかもしれない座標を、暫定的に作ることができる場所として調べた結果に追加する
以下繰り返し
（この調べた結果もbitを使って保存するとかなり速かった）
これにより実行速度が大幅に改善した（5倍速くらい？）。これを提出することで数日の停滞を巻き返してゆく。(44.8M→46.2M→47.2M→49.4M)
これをきっかけとして、ほかの場所もいろいろと無駄があるのではないかという気がして、次々と高速化してゆく。この間、問題となっていたバグ部分を高速化しようとした結果さらに違うバグになっているのだが、なぜか気づかなかった。
これに評価値の調整を行い51.0Mまで到達する。
また、高速化とセットで、ちょっと乱数の倍率を変更してみる。高速化のおかげで回数が稼げるので、前半は乱数要素少なめに貪欲を行ってもらい、貪欲のやり直し回数を重ねるごとに乱数を大きくすることで評価関数の型にはまりすぎて出にくかった結果にも多少到達できるようになった。仮に後半部分で良い結果が出なくても、前半部分で十分高得点が期待できるので良い方法に感じた。
また、ついにバグに気づく。バグを取り除いてみる。ローカルで3M下がる。バグを戻してみる。ローカルで3M上がる。よって、バグを許容する。さらに、バグを改変してスコアの安定化に成功する。
乱数の運に左右されるので多少上下しつつ、最高53.0Mに到達する。
10/1 お祈り期
もはや簡単に高速化できる場所はなくなった。実装の遅さに定評のある私は、一日にかけるコード量など微々たるものである（ちなみに短期コンテストにめったに出ない理由もそれである。逃げていても上達しないとわかってはいるが・・・）。雑なものを書いてそれが最終提出になってしまっては大事故である。したがって最終日は順位表の礼拝に努め、システムテストの得点の向上を祈った。
まとめ
AHCに参加したのは久しぶり（おそらくAHC003以来？）になりますが、まさか黄色パフォーマンスに到達でき、レートも今回で水色になれるとは思っていませんでした。地道に実装力が上がっているということなんでしょうか・・・？長らく間が空いてしまいましたが、次回以降のAHCも時間を作って取り組んでみたいと思いました。
（短期コンテストは苦手意識があるのでぜひ長期コンテストを・・・）
よくありそうな質問
・結局盤面ってどのように記録したの？
点、辺をそれぞれ上方向、右上方向、右方向、右下方向の四種類に分けて盤面を記録しました。以下の3*3の盤面での点の取り方を紹介します。辺は点の例の時に出てくる矢印に沿って同じように記録します
上方向は左の矢印から順に100,001,111（2進数）となります。
右上方向は上から順に001,000,100,110,100（2進数）となります。
右方向は上から順に101,100,110（2進数）となります。
右下方向は100,100,101,010,000（2進数）となります。
この形で持っておくことでの恩恵については詳細は省きますが、長方形が作れるかってどう判定したの？で若干触れます
・長方形が作れるかってどう判定したの？
上でも使用した3*3の盤面を使用して紹介します。
上のようにまず新しく起きたい場所からある方向に進みます。すでに点がある座標に到着したら、時計回りに90度回転し、また1マスずつ進んでいきます。これを繰り返し、スタートの座標に無事もどることができるか見れば良いです。上の例では戻ってきたので作ることができます。また、上の例の座標スタートでは、ほかの角度から始めるともどってこれません。
別の場所を起点にして何個か失敗パターンを載せておきます。
この次にぶつかる点までの距離は、一つ上の項目「結局盤面ってどのように記録したの？」で紹介したbitboardでは、1になっている位二つの間の距離を見ればよいです。このときbit演算を用いることであまり長さに影響なく高速に求めることができます。間に線がすでにあるかどうかについても同様に高速に求めることができます
・一応バグの部分教えて
一応、どんな値が加算されているかはコードを読んでわかっているので部分的に紹介しておきます。
「赤の四角を作る」という行動に対する評価値を考えるとき、緑の4辺にまだ一本も線が引かれていない場合、黄色の4頂点でまだおかれていない点の数だけ減点する。というものです。これを赤緑黄色の位置を90度ずつ回し計四回考えます。座標がずれた結果上のようなおかしなことになったのですが、上の赤の長方形と黄色のエリアの関連性が結果としてきれいな市松模様を構築することにつながったのだと思います。
・なんで焼かないの？
貪欲を時間いっぱいやり直すという方針をとったのは、当初、置くことができる座標を調べるのが非常に遅く、1回解を出すのに500msはかかるだろうと踏んでいたからです。本当は高速になり始めたころに焼きなましを考えるべきだったと思いますが、焼きなましのための一部破壊ができるようなデータ構造になっていなかったので、実装が間に合わないと判断しました。（嘘である。実行速度が遅かったのも理由だが、実はmontplusaは焼きなましの方法を知らないのでコンテストで焼きなませたことがないのである。そろそろ学ぶべきか・・・）
・天啓、多すぎでは？
天啓を得られるか、天啓が降りてくるかは運にもよるので今回は運がよかったと思いますが、より天啓を得やすくするためにできることもあります。（なんかスピリチュアルに聞こえますが違います）
・手動で試してみる（今回は手動で試してもあまり良い発想が得られませんでした）
・twitterで共有されていたVisualizerを見る
・トイレ、風呂、食卓、公共交通機関、外出先などあらゆる場所で問題を思い出してみる
このほか他コンテストの経験が活きる、他コンテストの解説記事が活きるなど、様々なきっかけで天啓を得ることができるので、天啓が得られそうなことをしてみるといいかもしれません。
（そもそも、私の「天啓を得る」の水準が低く、実は小発見程度である可能性もあります）
