- 0.はじめに
- 1.問題文の概要
- 2.最初の提出
- 3.アイデア出し
- 4.長期戦の準備
- 5.得点の計算方法
- 6.2回目の提出
- 7.考察の開始
- 8.5日目の考察
- 9.閑話休題（今回の目標）
- 10.スコア計算を実装する
- 11.動物を閉じ込めることを考える
- 12.動物のいない人だけのエリアを広くすることを考える
- 13.ビジュアライザの共有について
- 14.迷走中
- 15.7日目
- 16.最後の週末（8日目）はBFSをすることにしました
- 17.今日こそは得点を出したい日曜日
- 18.最終週の月曜日（10日目。残り5日）
- 19.最終週の火曜日（11日目。残り4日）
- 20.最終週の水曜日（12日目。残り3日）
- 21.最終週の木曜日（13日目。残り2日）
- 22.最終週の金曜日（14日目。残り1日）
- 23.残り24時間。できる限りの高みを目指す
- 24.最終日（土曜日）
- 25.そして、コンテストが終わります。
- 26.最終結果（2022/2/27更新）
0.はじめに
はじめまして、もしくはお久しぶりです、競プロ歴2年のかえでです。
今回は８回目となるAtCoder Heuristic Contest である、MC Digital プログラミングコンテスト2022に参加しました。
コンテストが始まる直前に、AtCoderから正式にヒューリスティックのRatingが公開されていました。今回のコンテストはいつも以上に注目が集まったのではないかと思います。開催期間は2022年2月12日12時から2月26日19時といつもより期間は長く、最終的な参加者は930名ほどになりました。
ブログを更新するのは久しぶりです。実は書きかけの下書きはたくさんたまっているのですが、書き終わらないまま保存されています。というのも、コンテスト後は放心状態で、最初に何を考えていたのかも最早忘れてしまっていたりするので、なかなか筆が進みません。なので今回は、コンテストと同時並行でブログを書くことにしました。
本日の日付は2月12日。先ほどコンテストが始まったところです。
「ヒューリスティックコンテストって何？」という人も、これを読めば、コンテストに参加した気分を味わっていただけるのではないかと思います。リアルタイムで書いているので、冗長な部分も多いと思います。そんなときは適当に読み飛ばしてもらえればと思います。長くなりますが、最後まで読んでいただければうれしく思います。どうぞよろしくお願いします。
そして、AtCoderのヒューリスティックコンテストでいつも楽しい問題を作ってくださっているwataさん、本当に感謝しています。どうもありがとうございます！これからAtCoderのヒューリスティックコンテストがますます盛り上がっていくことを心より祈っています。
1.問題文の概要
まずは問題文を読みます。
簡単に言うと、30×30サイズのオフィスに、人と動物がいます。
人と動物を分けるように障害物を好きな場所に置くことができます。
最終的に人のスペースが広いほど得点が高くなります。
また、同じスペースに動物がいると得点が低くなります。
動物は制御できません。
人の行動を出力する、インタラクティブ形式の問題です。
人の行動は３種類です。
・何もしない。
・隣のマスに移動する。
・隣のマスに仕切りを作る（通行不能にする）。
これを３００ターン行います。
問題文を読んだ後はビジュアライザを見ます。今回は、入出力例が入ったビジュアライザが用意されていました。初心者にもチャレンジしやすいように、いろいろと考えてくれているのがわかります。
2.最初の提出
まずは自明な解を出力します。そう、「３００ターン、全員何もしない」ことです。
提出すると、結果は無事ACしました。
ホッと一息つきます。
得点は204万1339でした。順位表には同じ点数が並びます。皆同じことを考えていたことがわかります。
この段階で、入力の受け取りと出力の確認ができました。
開始から５０分が経過していました。
3.アイデア出し
アイデアを紙に書き出します。
この時点で考えたのは、次の２つです。
- いくつかに部屋を区切る。
- 動物を閉じ込める。
１の方が実装が簡単そうで、２の方が難しそうです。
１を実装して、結果を確認することを選択します。
4.長期戦の準備
また、並行してローカルテストを使用する準備も進めます。
ここで問題が発生しました。以前使えていたRustが使えません。
再度Rustをインストールしなおしましたが、ローカルテスタを使用すると、エラーが出てしまいます。１日目の数時間を費やしましたがよくわからなかったので、これは後回しにすることにしました。
5.得点の計算方法
もう一つ、避けて通れないのが、スコアの計算です。問題文には下の引用のように書いてありました。いつも思うことですが、読んでも数式の計算方法がぴんと来ません。
得点の計算方法（AtCoder問題文より引用）
そのため、私はローカルテスタのRustのコードを読んで確認することにしています。C++を使用しているのでRustは未履修なのですが、コードの方が理解しやすいと感じています。コードを読むと、BFSをしていることがわかります。そして、（それぞれの人が移動できるエリアのマスの数の和）を900で割り、（人と一緒にいる動物の数をｎとすると）２のｎ乗でさらに割ったものに10の8乗をかけて得点としていました。このスコアは300ターン後に計算されるということで、途中経過は考慮されないようです。
6.2回目の提出
２日目になりました。
まずはそれぞれの人に、動かない、障害物を置く（上下左右）、移動する（上下左右）の９種類のうち、ランダムに合法手*1を選択してみようと思います。
あれ？区切るが簡単そうだと昨日まで言っていましたのに変ですね。区切ることをする前に、まず、ペットや人の現在位置を管理して、動かせるようにする必要がありました。
- ここでつまずきます
・１indexに気づかず、バグらせました。
・ペットの動きは後回しに人の動きだけを実装したら、人やペットのいる場所には障害物を置けないことがわかりました。
そこで、障害物の2次元配列を作るとともに、人とペットの現在位置を管理する配列をを用意しました。
- そしてもう一つ問題がありました
昨日、うまく使えないまま放置していたローカルテストです。これが使えないと、自分のコードを試せません。初期位置しか入力を受け取らないので、その後の動物たちの動きがわからないということに気がつきました。
もう一度問題文を読むと、Windows用のコンパイル済みバイナリがあるとのこと。こちらの「tester.exe」を使用することにしました。これもまた、うまく動作せずに四苦八苦しました。
tester.exe wsl ./a.out <in.txt> out.txt
上の一文をwindows上のcmdから入力して実行できたのは午後もだいぶ経ってからでした。
やったー！よかった。
さて、やっと使えるようになったローカルテスタでしたが、なかなかエラーがなくなりません。それは、問題文で読みとばしていた一文のせいでした。問題文はよく読まなければと、コンテストの度にいつも反省してばかりいます。
AtCoder問題文より引用。重要な箇所に赤線を引きました。
障害物を置いて通行不能にするのに追加の制約があったことに気がつき、やっと２回目のACができました。得点は、1061万7465になりました。
ランダムに合法手を選択すると早い時期に障害物で身動きが取れなくなるようでした。
7.考察の開始
３日目になりました。平日なので、使える時間は早朝と夜です。日中はアイデアを紙に書いたり、実装の方法を考えていました。１日目から提出の早い人たちが、seed０のビジュアライザを共有してくれていました。かなり高得点のビジュアライザを共有してくれる人もいて、まずは真似をしようと思います。今回はとにかく「周りについていく」ことを目標としていました。
さて、どうやって真似をするかですが、30×30の障害物を置いた最終盤面を作成して、その形を目指すようなプログラムを書くのが良いのではないかと考えました。自分の頭や他の人のアイデアを使って、いろいろな盤面を試すことの方が高得点につながるのではないかと思ったのです。
目標とする障害物を置いたマスを0、1で作成し、３日目は終了。
４日目になりました。昼間、考えたアイデアがなかなか良さそうだと思ったので、昨日のアイデアは捨てることにしました。
考えたことは、ウナギの寝床のような細長い通路をたくさん作って、そこに動物を閉じ込めていくということです。動物を閉じ込めることの方が、広いスペースを作ることよりも得点が上がると考えました。動きのイメージは田植えです。
左端に等間隔で並んで、右側に柵を置きながら進む予定です。
しかし微妙なバグが直せません。全然提出できるところまでいけないので、ちょっと弱気になります。Twitterで励ましてもらって、再びがんばるぞと思います。イメージはできているので、がんばって実装するだけなのはわかっています。直せないまま寝る時間が来てしまいました。
４日目の夜は下の図のような状況でした。
バグがあるまま提出すると、得点は、921万0358でした。ランダム解よりも下がっていますが、思ったほど悪くないなと思います。
明日はきちんと柵を並べて、動物を閉じ込めるところまで書き上げようと思います。
５日目です。
バグを修正できました。
ここで、細い通路に注目します。赤い枠を書いた部分に柵を作れば、動物を閉じ込めることができます。できれば通路の奥で閉じ込めたいと思いますが、ぜいたくは言いません。方法としては、通路の自分より左側を突きあたりまで調べて、「動物がいる」かつ「左側に柵を置ける」ときには柵を作ることにします。
（ビジュアライザの障害物が柵に見えるので、いつの間にか表記が障害物ではなく柵となっていますね…。）
さあ、ここまで来たら、提出まであと一息です。
できました。やったー！seed0でのスコアも上がりました。
テストケースを100まわして、WAが出ないかを確認します。
WAが出ないことを確認して、わくわくしながら提出します。
（このジャッジ中のドキドキ感がたまりません。）
結果は…。
806万2530でした。ハイスコアを更新することはできず。…残念。
期待して、落ち込んで、期待して、落ち込んで…。
これがヒューリスティックコンテストでよくある光景なのではないかと思います。
落ち込んでいてもしょうがないので、100のテストケースでスコアが低かったものを見ていこうと思います。今は5日目の早朝なので、続きは夜になります。
8.5日目の考察
実際に実装してみて、このウナギの寝床タイプの柵の置き方は悪くないと思ったので、改善する方法を考えます。
この形が悪くないと思っている理由は、人が一人で柵を置いて封鎖できることです。
朝は左に柵を置くことだけを考えました。
それは、人はみんな右端にいるはずなので、自分の左側は動物しかいないので、動物を閉じ込めれば、スコアが必ず上がると考えたからです。
しかし、スコアの低かったseed1の盤面を見て、人を移動して、下や上に柵を置くことをしなければこれ以上スコアを上げることができなそうだと思います。
そこでやっと、スコア計算のメンバ関数を書くことに決めました（遅い…）。
9.閑話休題（今回の目標）
つらそうに見えるかもしれませんが、実はもう山は越えています。
自分がつらく感じるのは、問題文を理解して合法手をきちんと得ることであり、盤面を正しく記録することであり、正しい出力をすることだからです。
残っているスコア計算は苦手だけど、WAが出る上記のバグとは質が違うと思っています。だから、すでにコンテストの楽しい部分に突入しているのです。
次のアイデアは考えていて、ウナギの寝床をもっと短くして追い込み漁みたい動物を閉じ込められないだろうかとか、集団で移動して動物を追い詰めたいと思っています。まだ動物の動きも考慮していないので、それも実装に組み込みたいところです。３００ターンあるので、ターンごとの戦略も変えることのできるところです。
問題は、アイデアに実装が追い付かないー！というところでしょう。おそらくこれはコンテスタント共通の認識ではないかと思っています。
さて、ここでこっそりと今回の自分の目標を書いておきます。
それは、「順位100位」です。
今は提出者数665人、正解者数583人、私の順位は343位です。
100位の得点は7億0685万9532点、自分の得点は1061万7465点です。
まだ時間はあります。さあ、ここから順位を上げていきますよ。
結果を知りたい方は最後まで読んでくださいね。
10.スコア計算を実装する
5日目の夜になりました。BFSは、お正月にチャレンジしていたCodinGameのLine Racingで何度も書き直していたので、すんなりと書けました。ヒューリスティックコンテストはアルゴのレーティングに関係なく楽しめると聞きます。その通りだと思う一方で、ヒューリスティックコンテストでよく使うアルゴリズム、例えばBFSやDFS、ダイクストラなどは書けるようになっていた方が、より楽しめるのではないかと思っています。
BFSを書くときに、各人が動ける面積と動物の数を数えておいて、4.で確認していた計算式を使ってスコアを計算しました。
11.動物を閉じ込めることを考える
今日こそはハイスコアを取るぞと決意して、取り掛かります。
考えたのは最後の部分。田植えのように全員で柵を並べながら右側に移動した後の動きです。右側に移動する際、動物も集められているのではないかと考えます。一人を残して全員がすみっこに集まり、右側部分を一番得点が高くなるように、動物を通行不能にする柵を置くことを考えました。片方の柵は右上で固定し、もう一方の柵の位置を縦一列全て探索することにしました。
書いている途中で、誘惑に負けて提出してしまいました。それでも３日ぶりに最高得点を更新して、順位も上げることができました。
提出するときはドキドキしてしまって、なんだか手に汗をかいてしまいました。
さあ、落ち着いてちゃんと続きを書きます。
ところが、書き直したものでテストケースをまわしてみると、思うようなスコアが出ません。人が全員移動してから柵でふさげばスコアが上がると思っていました。どうしてだろうと、スコアが低いseed99のビジュアライザを見ました。
動物がくっついて来るので、柵を置けないでいました。結局、動物を閉じ込めることができずにいました。
何とかうまくいかないかなと思いましたが、ここで別の方法を考えます。
とにかく残っている動物の数が２のべき乗の肩に乗るので、動物と同じエリアにいることがものすごくマイナスに思えます。というか、すぐ０になりますよね？狭くても人だけの部屋を作った方が良さそう。
ということで、動物がいないときは、人がウナギの寝床に入って柵で閉じこもってみることにしました。
提出をしてみると、得点は1億0138万7954、順位は283位に上がりました。こちらの考え方の方が良いのだとわかりました。
先ほどのseed99がどうなっているのか、見てみましょう。スコアは、159から108万5069に上がっていました。
12.動物のいない人だけのエリアを広くすることを考える
動物を閉じ込めるより、動物のいないエリアを少しでも確保することがスコア上昇に寄与することがわかり、２つのアイデアでどちらを選択するかを悩みました。
- １人目だけ広いエリアを求める度に出て、残りはウナギの寝床で一人部屋を作る。
- 集団で動物のいないエリアを作る。
集団の場合、これまでのアイデアはここでストップとなります。
ただ、上位との差と残りの時間を考えると、上のアイデアを行っても、得点差はそこまで詰まらない気がします。そして、ここで初めて考慮しないといけないと思ったのが、動物の動きです。牛以外の動物は人よりも動きが早いのです。
先ほどのseed99をよく見てみましょう。犬に襲われている人がいました（そのようにしか見えません）。あ、よく見たら、昔のコードに戻りすぎて、なおしていないバグのせいかもしれません。
ちょっとなおしてきます。
（ここで再提出）
得点は1億1773万9194に上がり、順位も271位に上がりました。
5日目の夜はこれで終了です。
13.ビジュアライザの共有について
６日目です。ブログを書くのが楽しくなってきてしまいました。
ビジュアライザの共有について、思っていることを書きたいと思います。seed0のビジュアライザが共有され、美しい幾何学模様に配置された柵の画像をいくつも見ました。それらは、一様（いちよう）に、「これをやれば、このスコアが取れます！」と教えてくれていました。
今６日目ですが、これらが、「簡単だから初心者もやってみよう」というメッセージにしか見えなくなりました。すなわち、本質は、やっぱり動物をつかまえることだよね、そっちは共有しないよ、というメッセージです。
最初から自分が悩んでいるように、アプローチのしかたは２通りあって、型を作って、そこに動物を閉じ込めたり、人が閉じこもったりするほうが実装が楽で、そこそこの得点が出るようにできています。けれど上位の人が楽しめるように、動物をつかまえる方は難しくて、でもそっちの方が高得点が出るよ、ということではないかと考えています。
私の頭の中には以前チャレンジしたTopCoderのMM129が思い浮かんでいました。農夫が鶏をつかまえるマラソンマッチです。これは二人で鶏を挟み撃ちすることができる人が強くて、私はそこまでの実装ができませんでした。今回はこの鶏よりも動物たちの動きが速くて、複雑になっています。おまけに動物とは隣接できないので、接近戦ができないようになっています。また、同じマスに動物と人が重なることもできるので、人で囲んで追い詰めるといったこともできないようになっています。柵をトラップにして、追い詰めるのかな？とぼんやりと考えています。
さあ、つぶやきはここまでにして、私も自分のできることで高得点を目指したいと思います。続きは帰宅してから。
（６日目の朝でした。）
14.迷走中
６日目の夜です。
日中、悩みました。
そして、ペットを閉じ込めるコードに書き直そうと思いました。ペットの動きを想像してみたら、何となくつかまえられそうな気がしてきました。囲碁の布石が頭に思い浮かびました。うまく閉じ込めることができると、成功時の得点もかなり高くなりそうです。
ところが、帰宅していざコードを書こうと思っても、考えがまとまりません。そのうちに、はっと気がついて、前回のウナギの寝床を長くして提出してみました。
得点が2億1415万6956に上がりました。
（これを書いていたら、動物がいるかどうかの判定が間違っていたので修正して、再提出しました。すると得点は2億0565万3520で、ハイスコア更新はできませんでした。上がると思ったのに上がらない。ペットが一匹いても閉じこもった方が良い場合がある等、この考え方もまた詰めが甘そうでした。）
小さな改善の積み重ねで良いのかを悩んでいましたが、自分の実装力を考えると、やはり、一歩ずつ進むのが良さそうな気がしてきました。
帰宅してから、早く得点を高くしたいと焦る気持ちと、これで良いのかと悩むもやもやした気持ちが消えませんでしたが、やっと落ち着いてきました。
- ６日目夜に試したこと
・最初から細長くふさがっているエリアを作り、右端をふさぐようにする。→得点が２倍になった（段差をやめた）。
・左に動物がいたら、柵でふさいだ。→得点が減少（テストケース的には上がったものと下がったものがあった）
・右端の一歩前まできて右に柵を置けないときは左に動いた。
15.7日目
7日目の夜です。昨日の夜から日中もずっと考えていました。
そして、週末は、BFSを使った方法を書くことに決めました。実装方法もほぼ考えています。
でも今日は金曜日なので、得点を上げる方法を試したいと思っています。
もう、戻るのではなく、前へ進んでいきたいと思います。
共有ビジュアライザで見た十字を実装してみたけど、得点は伸びませんでした（1億1276万9900）
seed99を見てみたら、ペットに囲まれて、柵で通行止めにすることができずにいました。この後、人を移動させたりしましたがパッとせず、夜は更けていきました。
８日目の朝に少しだけ直して提出しました（得点：1億8936万1060）。一番ペットが少ないエリアに人々を移動させたはずなのですが、バグっていますね。
ちょっとだけ直してみました。seed0のスコアが873万3333になりました。しかし他のテストケースの点数が良くなかったので、提出はしましたが、予想した通り8829万0924という得点結果でした。得点を上げるために試した形でしたが、思ったようにいかず、得点は更新できませんでした。ここでストップします。
16.最後の週末（8日目）はBFSをすることにしました
さあ、今日からは別の方法でがんばります。まずは、盤面で、それぞれの人と、全てのペットの動きをBFSで求めます。できあがったのはこんな感じの盤面です。
人のテリトリーを地続きにして、ぎりぎりのラインで柵で囲っていく作戦です。一番優勢な人は動かないようにして、他の人が周りに近づくようにしました。移動途中は一番ペットと近くなる側面に柵を作っていくことにします。
評価関数は敵の陣地を減らすこと（もしくは人の陣地を増やすこと）で、終了条件は、人とペットが行き来できない（遮断される）ことです。
わりとシンプルな考えになった気がします。
ペットが複数回動けることを考慮していないので、それはこれから改善していきたい部分です。
まず、白いエリアを確保することを考えます。
①一番面積の多かった人を調べます。
②それぞれの人から近い仲間を調べて、仲間を経由する順番を決めます。
③仲間を経由して一番面積の多かった人のところに向かいます。
④サイドに柵を作りながら移動します。
⑤一番遠かった人は、一度壁にタッチしてから、仲間の元に向かいます。
⑥一番面積が多かった人も壁タッチをします。
※ペットが含まれていることや、ペットが複数回移動できることが考慮されいませんが、今は気にしないことにします。
さて、４時間経過しました。①、②は順調に実装出来て、楽しいと思っていました。③もまあ、何とかいけそうなところまできました。暗雲が立ち込めたのは④です。思うように柵が作れません。楽しかった気持ちはどんどん、消えていきました。
煮詰まったときは、家事をしたり、お風呂に入ったりすることにしています。今回も同じようにルーティンをこなしながら考察を進めて、何とか改善できるかなというところまで考えがまとまりました。さあ、自分の考え通りに最後まで実装しきることができるのでしょうか。
再開です。21時からはデンソークリエイトプロコン2022（ABC239）が予定されていて、それにも出るつもりです（時刻は19時）。今日は午前中３時間、昼寝をはさんで、午後５時間くらいコードを書いています。自分の体力が残っているのか不安です。
あとちょっと。やっぱり前の人の場所にもたどり着けていないので、次はBFSで経路復元をしようと思います。
今こんな感じです。
ちょっとABC239に参加してきます！
17.今日こそは得点を出したい日曜日
９日目です。もう何日目かよくわからなくなってきました。昨晩はABC239はミスに気がつくのが遅くて惨敗（一応４完）。今朝は４時に目が覚めました。もう少し寝たいと思うものの、結局５時に起床。現在の時刻は朝の６時です。すでにバグを見つけて一つ直しました。体力的には全然さわやかではない朝ですが、作業は順調です。
今考えていることです。
①端から端までのルートを記録して、人を往復させて空いている穴をふさぐ。
②人と人は行き来できる、人とペットは行き来できない、という状態を判定するBFSのメンバ関数を作る。
③ ②を使って、終了判定を作る。
④ ②を使って、次の手を選ぶときの評価関数とする。
BFSの経路復元は、何回も検索している気がします。検索をしているときに出てきた、BFSの経路復元を使ったARCの問題を解いていたら、はまってしまって、２時間使ってしまいました（やっとACしました）。
さて、先に②と③を作りました。「人と人は行き来できる」状態でランダムに柵を作るとなかなか面白くて、ビジュアライザが楽しかったです。
９日目の夜です。昼間やっていたこと
・100テストケースをまわしたら、エラーが出ていて原因を探していた（２時間）
・白黒に色分けして、敵陣が先方にあるときに柵を作るみたいな方法で陣地を作れないかをいろいろな条件で試していた（２～３時間）
・経路復元（ただし経路復元をどう使おうかと思案中）
スコアが上がる方向を模索していただけで、これだというところまでたどり着けず、提出さえできていません。たとえばこんな感じ。
ブログに書いていたら、これではいけないと我に返りました。土日連続でABCがあるので21時からはそれに参加しますが、今日はコンテストの後もがんばろうかと思います。
そろそろ実装力もついたはず。やっぱり幾何学模様で得点をとるべきですね。（何回この思考を行ったり来たりしているのでしょうか）
そういえば、終了判定で、こんなコメントを出すようにして、楽しんでいました。
18.最終週の月曜日（10日目。残り5日）
昨日のABC240も惨敗でした。もう立ち直れないと思っていましたが、競プロerの方たちに元気を分けてもらいました。こんな不甲斐ない自分でも、この場所から離れたくないと思いました。この場所に必死にしがみついている自分がいました。
こつこつとバグを直します。全員が同じスペースにいて、空いている穴がふさがりました。まだ３匹ペットがいますが、これをつかまえることができれば、得点は8倍（2の3乗）になります。結局、土曜日は提出したけど得点を更新できず、日曜日は提出さえもできずに終わりました。へこんだまま迎えた月曜日、やっと一筋の光が差し込んできたように思えました。
夜です。朝、テストケースを100個まわしてみると、エラーが多く出ました。ここで、合法手の見直しをします。何となくあやしいのはわかっていたけど、問題文が理解できずに、後回しにしていた部分です。問題文をもう一度確認します。
①人がそのターンで移動するマスに柵を置こうとするとWAとなる。
②ペットとペットに隣接するマスに柵を置こうとするとWAとなる。
cf（柵が置いてあるところに柵を置こうとすると、何もしない。）
③人とペットがいるマスは通行可能で同じマスに何体でも重なることができる。
①の判定がうまくいかず、人が動ける場所全てを行けないようにしていたのを修正しました。
②複数回ペットが動いたときの現在位置をうまく把握できず、移動中の隣接マスも全て移動禁止にしていたのを修正しました。
③は途中であやふやになっていたので、もう一度コードを確認しました。
これによって、重なったときに人が柵を置けるようになりました。
今さら何やっているのだと思う反面、やっとここまで理解して、盤面を記録して、人を動かせるようになってきたという実感がありました。無心でやったら２時間でできました。
もう、Twitterを見るのをやめました。順位表を見るのをやめました。自分の中に答えはあって、ただそれを実装したかった。自分の考えをコードに落としたかった。
もう一度十字タイプを実装しますが、提出した得点は1億5014万2075でした。
19.最終週の火曜日（11日目。残り4日）
火曜日の朝です。起きたらTwitterを見て、順位表を見ていました。いつもの日常です。昨日の文章を見て消したくなりましたが、これがヒューリスティックコンテストで見る光景かもしれないと考え、そのまま残すことにしました。「実録」っぽいなと思います。自分の精神状態が不安定なのがヤバいですね。昨日は４時間くらいしか寝ていなかったからかもしれません。
冷静に、昨日の続きをすることにしました。
・移動のしかたとタイミングを変える
・穴のふさぎ方を変える
・あと３匹動物をつかまえる
この３つを目標にします。明日は祝日で休みなので、時間が取れるはずです。今日できることをがんばろうと思います。
（時間経過）
夜です（日中は仕事をしているので）。文章に書くことで、冷静になることができて、よかったと思っています。日中、仕事の合間に考えたことをまとめます。
ペットの最大数は20なので、4分割して最小の部屋に行ければMAX5匹になる。2の5乗なら最低点は、全員が同スペース（互いに行き来できる状態）であれば、15×15/900/32×100000000≒78万点。これが100ケースで7800万点。平均1匹つかまえれば1億5600万、2匹なら3億1250万、3匹なら6億2500万、4匹なら12億5000万、5匹なら25億（この場合、ペットの数が０になること）。柵を置くので、実際はもっと減るのでしょうが、とりあえず、この状態を目指すことにしました。
・目標は10億。
そして22時30分。やっとバグがなくなりました。
提出すると得点は3億0316万6627点になり、４日ぶりのHighest更新となりました。
思わずほっとため息をつきました。順位は851人中360位でした。日を追うごとに参加者が増えていっているようでした。
スコアが低かったテストケースを確認します。
seed95のスコアは5731でした。やはり、柵でふさぐことができずにいました。灰色のペットは犬で目的の人のまわりをうろつきます。それぞれランダムに選ばれるのですが、全員同じ場所に人がいるのですから、ここから離れていってくれるわけではありません。対策が必要だと感じました。
次にやることです。
・ペットを閉じ込める
１／４のエリアになって、ペットの数もスペースも減りました。人の人数は５人以上います。方法としては次のように考えました。
・柵を置く前と置いた後のスコアを計算し、最高点の８割くらいまでの得点なら柵を置くことにする。
条件は、「柵を置いても全員が行き来できること」です。
最初は合法手のランダムで柵を置いてみましたが、ビジュアライザで見たところ、思った以上にイマイチなので、ペットに狙いを定める方法に変えようと思いました。
明日は天皇誕生日で祝日です。土曜日の19時までですが、最終日は焦ってしまうに違いありません。明日が実質最後の思ったことをやれる日だと思いました。
そう、ついにペットをつかまえる日が来ました。
20.最終週の水曜日（12日目。残り3日）
朝です。朝起きる度に、昨日とは違うことを考えています。これまで書いたきたことが恥ずかしくなってきて消したくなりますが、実録ってこういうことが起こるのだなと思って、我慢することにします。
というのは、昨日、鳩ノ巣原理を考えていて、一番ペットが少ない部屋への移動を考えていましたが、そうか、逆にペットが多い部屋をつぶしていけば良いのかと思います。
そこで、ふと、これまでのseed0で共有されたビジュアライザを思い出して、はっとしました。そうか、ペットの最大数は20匹だから、20より多い部屋数、例えば、30部屋とか作れば、ペットのいる部屋を全てつぶしても、10部屋残ります。同じサイズの部屋なら、少なくとも３分の１のスペースは人で使えることになります。
条件は全ての部屋が行き来できることです。もし１部屋に2匹以上のペットがいれば、さらにスペースは広く使えることになります。
なるほど、と思いました。最初から部屋を細かく区切った実装をする利点に合点がいきました。
同じ場所に人がいると、犬にからまれて、動けなくなってしまいますが、人がばらければ、影響も小さくなります。一人一人が別の場所にいて、ペットのいる部屋をつぶしていく、それが確実な方法なのではないかと思いました。ただ、部屋数が多くなると、一人が担当する部屋数も増えます。だから通路にしておいて、上下もしくは左右に動くだけで部屋をふさげるようにしているのだなと思いました。
さて、今日は何をしようかとあらためて考えます。下に候補をあげてみました。
①seed0で共有されている盤面を真似してみる。
②昨日の考え通り、動物をつかまえてみる。
③今の形で、ペットの多い部屋をつぶしてみる。
これらについて、どこまでできるかはわかりませんが、やってみたいと思っています。順番的には③→②→①の予定ですが、時間配分的には①に多く時間を割いてみたいと思いました。さあ、今日も一日がんばります。
ちょっとだけ余談です。
コーディング中はYouTubeで音楽をかけっぱなしにしています。適当にかけていたら、ユプシロンさんのフォージェリィが流れてきました。全然知らない方で、初めて聞いた曲だったのですが、かっこよくて、今回のコンテストではこれをよくループ再生して聞いています。テンションが上がって良いです。これからこの曲を聞いたら、このコンテストのことを思い出すようになるんだろうなぁ…。
いつも持て余す自分の気持ちも、文章に書くと落ち着くようです。人と対話しているような気持ちになれ、Twitterもあまり見ずに過ごしています。こんなにも自分の世界にひたっているのは久しぶりかもしれません。
（家事をする）
家事をしながら考察を進めたら、また気が変わりました。①を始めようと思います。
というのは、writerの気持ちを考えてみたら、制約がしっくりときてしまったからです。writerはこれまで参加したことのない多くの人に参加してもらいたいと思っているはずです。
自分が固定の盤面を考えて、部屋をふさいでいくことを考えたとき、昨日まで実装していた正方形がやりやすそうだと考えました。一人４部屋を担当すると、５人で２０部屋。そう、ペットの最大数と同じです。一つの部屋に２匹以上いる部屋をふさげれば、あとは１匹ずついる部屋をふさいでも、１部屋残ります。そこに人が全員集まれば、ペットのいない部屋ができます。ペットのいない部屋にすることが得点を上げる近道なことは、得点計算方法からも、これまで試したことからもわかっています。
やるしかないなと思いました。
あれ？実際にエクセルでマス目を置いて考え始めました。思ったようにうまくいかない…。全ての部屋を行き来できるようにするのは、正方形だと思ったよりも不都合が多くありました。
そして…。なんと、５日目に実装していたウナギの寝床型の配置に戻ってきた自分がいたのでした。もうwriterの話とか消したいのですが...。恥ずかしいな、もう。
下の図のような配置を考えました。二人ペアで上下に動きます。細い通路の中に動物がいたら、左と右から同時にふさぐことにします。３０部屋ありますから、１匹でもいれば閉じ込めてよいはずです。さあ、うまく実装できるでしょうか。がんばりたいと思います。
ん、別に一行ずらす必要はなさそう。
午後になりました。現在時刻は午後1時半。まだ柵を並べることに悪戦苦闘していました。300ターン後にまだ柵を並べ終わっていません。7人以下のときは柵を並べるのをあきらめていればよかったのかも。優先順位の選択が難しいと思います。仕事や家事なら、他の人の影響がなければ、かかる時間をほぼ正しく見積もれるのに…。愚痴を言ってもしょうがないな。ビジュアライザを見るときと、ブログを書くこの時間が、ひと時の休憩でした。
なんかもう午後３時半です。やっと柵を並べました。次は挟み撃ちです。BFSをうまく使えないかな？ペットを始点にすると良いのか、人のペアを上下に動かす方が良いのか。人のペアを上下に動かす方が良さそうです。ペアを作って動かしてみたいと思います。
時刻は午後６時半を過ぎました。疲れました。肩凝りはひどいし、目が疲れてきてしまいました。仕事かな？これは。自分はどうしてこんなにつらいことをしているのだろうかという思いが脳裏をよぎります。今は最後の、柵を置いてペットを閉じ込める部分の実装を書いています。
そして、このブログの文字数が、1万5000字を超えました。ここまで読んでくれている人はいるのでしょうか。ここまで書いて、ここまで読んでもらって、このコードが提出できなかったらどうしよう...。
コンテストが終了してからは、とてもこんな文章は書けないだろうと思います。イマイチな部分は全部カットして、記憶から消え去るのを待つだけなのかもしれません。良い結末を書くには、自分ががんばるしかないのでした。だったら、小説の方が書くことが、楽なのかもしれない…。
そうだ！先に閉じこもる方をやろう（ひよっている！？）。今のポジションでペットがいなかったら、下に柵を置くだけ。これならすぐにできそう。いや、１匹でも２匹でも３匹でも４匹でも５匹でもいい。点数がプラスになるならそれで。
考えなおしました。もう何匹でもいいです。柵を置いてふさぎましょう！
もう現在のコードは1326行になっていました。メイン関数は17行です。自分もがんばっています。
100テストケースをまわすと、5個WAが出ました。しかし、それ以外の得点は明らかに上がっているのがわかりました。修正をして、100ケースともスコアが出るようにしました。期待して提出したものの、結果はREが78個、MLEが14個あり、得点は0でした。
夜９時です。今日中にこのコードをACして終了したいと思います。
え、夜１１時半です。まだACできません。ナニコレ…。明日仕事なのに…。
今日中のACをあきらめました。というか提出しているうちに日付が変わって、木曜日になってしまいました。
21.最終週の木曜日（13日目。残り2日）
朝です。以前ACしたときと比較して、一部のmapをvectorに変え、意図的にendlを入れたところ、ACしました（よかった）。しかし得点はのびませんでした（得点：9886万5002）。ペットの数が少ないときは単純に４分割した方が結果が良さそうです。
また、今朝はtester.exeがウイルス対策ソフトに検知され、ファイルが隔離されて使えなくなるなど、朝からドキドキしてしまいました（ファイルを除外して使えるようになりました）。
昨日の夜は絶望的な気持ちになりましたが、また仕切り直しです。
夜になりました。眠いです。朝からずっと眠いです。昼休みにちょっと寝ましたが、今も眠いです。５時間睡眠くらいになると、きついなと感じ始めます。2週間なので、かなり体調には気を使って参加していましたが、昨日は長時間やり過ぎて疲れが残っています。お風呂に入ると気分がすっきりしたので、実装を始めます。
そしてついに、ペットを閉じ込めました。まだ下の方はバグっています。そういえば、7.考察の開始で人の真似をしてでも周りについていこうと考えていました。やっとその地点に立とうとしていました。
このあとやりたいと思っていることのリストです。
・動物を閉じ込めるのバグをなくす
・無駄のない閉じ込める動きを考える
・動物の数が少なければ「正方形４分割タイプ」、多ければ「動物閉じ込めタイプ」を選択するように切り替えをする
最後までがんばります。
そういえば、今朝、AHC008のコンテスト後に懇親スペースを立てる予約をしました。コンテスト前からスペースの計画は立てていました。実力の伴わない自分がスペースを立てて良いのだろうか、コンテスト中に何度も迷います。それでも、競プロ界に何か貢献をしたいと決意したときから、できることをやろうと思い続けています。もしも自分がAtCoderのヒューリスティックコンテストを広めることができるのであれば、それに挑戦したいと思ったのでした。
あとは、単純にコンテストの後は自分が考えたことを話したくなるし、他の人が考えたことを聞きたくなったりします。だから、とても楽しい時間になるはずです。
phocomさんから以前いただいたリプのことをちょっと思い出していました。
ありがとうございます！！！かえでさんもマラソンの重要な広告塔になっていそうでありがたいです！
— phocom (@_phocom) 2021年11月16日
この引用RTもうれしかったなぁ。
勇気が持てる記事。
— ツカモ (@tsukammo) 2021年7月4日
かえでさん、完全にマラソンインフルエンサーだ。 https://t.co/uaqv6joTte
22.最終週の金曜日（14日目。残り1日）
朝です。ぐっすりと寝ました（でも６時間）。相変わらず昨日までの自分が書いていることが恥ずかしくなりますが、気にしないことにします。
長かったAHC008も終わりが見えてきました。現在の順位は888人中408位です。
とりあえず、目に見えているバグを直します。
テストケースをまわし、十字分割タイプとペット閉じ込め型のスコアを比較しました。
残念な結果でした。閉じ込め型のスコアが低すぎて、これでは良い結果が望めそうもありません。自分の予想では、ペット数が多くなると閉じ込め型の方が良くなるのではないかと思っていました。
今の状態だと、４分割タイプの中央値は1458333、閉じ込めタイプの中央値は12656で全く勝負になりません。
上のグラフは対数目盛でしたので、実際のスコア差も見ます。
閉じ込め型のスコアで、とびぬけて得点が高くなっていたものがありました。ペットの閉じ込めが成功したのだと思います。ビジュアライザで確認します。
一番得点の高かったseed74のビジュアライザです。スコアは4144万4444でした。４分割では届かない得点を取ることができることがわかります。
今日は閉じ込めタイプをもっと良いものにしようと思いました。
23.残り24時間。できる限りの高みを目指す
金曜日の夜です。また日中に考えました。そして、４分割タイプと同じことを今の盤面でできるなと思いました。３人が通路の３か所に横並びでいて、上に柵を置けば上半分と遮断、下に柵を置けば下半分を遮断できます。不利な状況を分析して、早めにその部分を自分たちのテリトリーから切り捨ててしまえば、状況が好転しそうだなと思います。
たとえば、seed0で、柵を置くのが間に合わないと思っていたところは捨ててしまえばよさそうです。
seed0のこのビジュアライザを確認したら、人が動いていなかったので、あれっと思ってコードを修正してもう一度提出すると、得点は9886万5002から2億2808万3148になりました。グラフの数字も変わってきそうなので、後ほどもう一度計算しなおします。
あと、動物の数との関連だけを調べましたが、人の人数も関係しそうなので、グラフを変えてみたいと思います。
なんかやっとヒューリスティックをやってる気分になってきましたが、あと一日で間に合うのかな…。
さて、自分の最高得点が4133万3333。平均でこの点数が取れれば提出した得点は41億になります。その場合、順位は約80位です。上位との差をはかる物差しができたと思いました。いや、これを書いていて雑な気がしてきました。動物の数で最高得点が変動するので、各テストケースの上限を計算した方がいいのかな。でも、最高得点のseed74を確認したら、ペットが12で、人が7だったので、良いことにしました。
お風呂に入っていたときに考えたのですが、人が7人だったことに意味があるように思えてきました。というのは、自分が作る盤面は、7人がベストなのです。5人や6人は少なく、8人以上は余剰人員が出ます。
さて、計算しなおした結果です。
100テストケースをまわすと、提出したときとほぼ同じ結果が出ていました。これまでずっとバグを直し続けていたので、スコアの合計さえ出していませんでした。
人数で出したグラフの方が、分析をするのには正解でした。お互いの苦手を補えるような動きを考えます。自分のコードを思い出しながら考えると、直感的にはこんな感じです。（十字型を使わずに、閉じ込め型で同じような状態を作る方向で考えます。）
・閉じ込め型でもみんな一緒に動く。
・閉じ込め型で柵を並べ終わった後に集合する位置は端ではなく中央にする。
・閉じ込め型でも動物が多い方の半分を遮断して上半分、もしくは下半分だけで残りのペットを閉じ込めることにする。
さあ、実装です。
そうだ、せっかくなので、一人一人の専有面積と専有面積にいるペットの数を出しておこうかな。
と思いましたが、面倒になったので、現在の面積476の場合、今のプログラムだとペットが4匹残っています。ペットが1匹いなくなるとスコアが2倍になります。ただし面積も減るはずなので、実際の得点はここまで上がりません。
・余った人（8人目以降は中央に立つ）
・5人目、6人目は柵を2人分並べない
この２つを実装してテストケースをまわしたら、合計が4億8669万8515になりました。提出します。得点は5億3058万6405になりました。3日ぶりにHighest更新です。順位は318位になりました。
100テストケースの得点を見ると、人数が多かったときにスコアが下がっていたのがほぼ解消されたのがわかりました。もう目指すのは十字型ではないようです。
点数が低いseed58を見ます。バグっていました。動き出しの条件がNGだったので、修正します。
再提出。得点は6億0948万7791になりました。Highest更新。順位は306位です。
再び、得点が低いものを見ます。あ、人数が少ないやつです。コードを修正します。
なおしたけどイマイチだったので、元に戻して別の方法にししたいと思います。
時刻は0時を過ぎました。
24.最終日（土曜日）
実装を考えるので、ちょっと仮眠をとります。寝ながら考察すると、起きたときに考えが整理されていたりするので。
起床しました。（3時間半くらいは寝ちゃったかも）
とりあえず、横をふさぐだけではなく、上下をふさぐという選択肢を追加します。
何で判定するのか悩ましいのですが、いくつか試してみたいと思います。
・ペットの数が半分以下になる。
・スコアが○○以上になる。（具体的な数値は決めていない）
上下をふさぐのは１回くらいしか使いたくない気がしています。
実装してみましょう（中略）。コメントをつけながら、テストケースの結果を見てコードを修正していきます（要するにまだイマイチ）。
ここで白状しましょう。上下にどうやって動かすかを随分と悩みました。結局ループになる配列を事前に用意しておき、ターンで配列数の余りをとって動かしていました。すると、上下に端から端まで人を動かすことができます。ただ、あまりにも無駄が多いので、なおすときが来ました（もっと早くなおすべきでしたがバグがこわくて後回しにしてしまいました）。
今からやることです。
・閉じ込める柵を置く位置を、今の居場所から近い順に探して移動するようにする。
イマイチ。犬がまとわりつくと判定が難しかったです。
配列を変える方向で再トライします。配列を３種類に増やして、人の数で動きを変えてみました。100ケースのうちの最大スコアは4577万7778となりましたが、合計は6億前後で良くなっている感じがしません。時刻は午後12半を過ぎました。コンテストの残り時間は６時間半となりました。
seed99を見て思いました。人員の振り分けがイマイチだでした。
今からやることです。
・人を再配置する。
バグが見つからなくて１５分仮眠しました。起きたら間違っていた箇所に気がつきました。眠るのは大事ですね。
今の時刻は14時を過ぎました。相変わらず、テストケースのスコアが低いものを見ては、修正して、テストケースをまわすということを繰り返しています。今回、修正をしてテストケースをまわすと、100ケースの合計が７億をこえていました。久しぶりのHighest更新かも！とテンションが上がりましたが、提出してみると結果は5億に届きませんでした。テスト用のseedとは違うペットの動きが起こっていると予測され、戸惑いました。コンテストが終了すると、システムテストで1000ケースがジャッジされます。そのときに、自分が思っているのとは違う最終スコアになるかもしれないと、不安に思い始めました。
手元のテストケースでは8億5000万が出ました。提出すると得点は7億1710万0252でした。順位は296位/920人中で、ずっと同じくらいの位置にいるようでした。
100テストケースの合計と提出した得点との差異を考えます。
わからなかったので、別の方法にします（Twitterを見たりして、休憩している自分に気がつきました）。とりあえずもうちょっと人の動きを変えたいと思います。
初期位置を変えました。テストケースでは8億5000万を超えていましたが、提出すると得点は6億3445万7781でした。
再び修正して100ケースまわすと、バグは消えた感じでした。もう合計を計算するのも面倒になってきたので、そのまま提出します。
すると、得点が10億を超えました。
やったー！
思わず叫びます。目標の一つであった得点10億を達成しました。
なんか、涙がにじんできちゃいます。よかった。本当によかった。
コンテストまで残り約２時間。時刻はちょうど午後５時になる少し前のことでした。
ほっとしたら急に眠くなってしまい、今は気力を振り絞って文章を書いています。
最後の提出の100テストケースの結果です。
そういえば、ビジュアライザの動画を貼るのを忘れていました。これについては、後日更新したいと思います。
25.そして、コンテストが終わります。
わくわくするコンテストの時間も終わりに近づいています。（この部分だけ最終日の朝に書いています）。あと半日すれば、スペースで感想を話している頃でしょうか。前回スペースを開いたのはTHIRDプロコン2021（AHC007）の終わった2021/12/12の夜でした。この日は、自分にとってすごく重要な日となりました。これまでいくら自分で理解しようとしてもわからなかったビームサーチやchokudaiサーチなどの話を、このスペースでthunderさん*2がわかりやすく話してくれました（自分が使えるようになるのはまた別の話だと後日気がつくのですが）。プログラミングを「自分のレベルに合わせて教えてもらう」という初めての経験でした。「教えてもらう」ことで、独学ではたどり着けない部分に引き上げてもらうことができると知りました。
自分はもっと強くなれる、もっと強くなりたいと思いました。
これからも自分は競技プログラミングコンテストに参加し続けると思います。
自分の未熟さを感じさせてくれる、成長を感じさせてくれる、そして、情熱を傾けることに何の悔いもない、この競技プログラミングを愛しています。
なかでも、このAHCやTopcoderのMarathon Match、CodinGameなど、長期間のコンテストが大好きです。
この気持ちがいつまでも続くことを願って、この参加記を終わりたいと思います。
そういえば、コンテスト後のスペースにゲストをお呼びしています。square1001さんです。20時頃来てくださる予定です。もし、コンテスト後にこれを読んでくださっている方がいらしたら、ぜひスペースにも話を聞きに来てくださいね。
square1001さんは、私がまだ競プロを知らない頃にたどり着いたE869120さんのQiitaの記事*3で、アルゴリズムパズルを作成されていた方というのが最初にsquare1001さんを知ったきっかけです。ゲームAIに強く、私の尊敬する競プロerのお一人です。きっと楽しい話が聞けるのではないかと楽しみにしています。
そしてついに、このブログの文字数が２万2000字を超えました。400字詰原稿用紙にすると55枚超です。本当に長文となってしまいました。
長くなりましたが、ここまで読んでくださり、本当にどうもありがとうございました！！！そして、もし、この記事を読んで、興味を持ってくださった方がいらしたら、ぜひ私といっしょにヒューリスティックコンテストに参加しませんか。
26.最終結果（2022/2/27更新）
2000個のシステムテストが終わり、最終得点と順位が確定しました。
2000個全てACしていました。
レートの更新もされ、水色になりました。
アルゴと異なり、レートが下がらないこともヒューリスティックコンテストの魅力の一つです。
seed0のビジュアライザです（粗が見えて恥ずかしい…）
コンテスト終了後のスペースはとても楽しく、多くの方から解法を伺うことができました。また、Twitterやブログで公開された解法は、まだ少ししか追うことができていませんが、いくつか読んだだけでもわくわくが止まりません。これから一つずつゆっくりと読みたいと思っています。
昨日公開したこのブログも、多くの方に読んでもらえて、とてもうれしく思っています。
今は祭りの後の寂しさですが、ゆっくり寝て回復したら、また次のコンテストにチャレンジしたいと思います。
最後まで読んでくださり、本当に、本当にどうもありがとうございました！！！
コンテスト、楽しかったー！！！
*1:一般的な言葉なのかよくわかっていませんが、選ぶことのできる全ての選択肢のことを指しています。
*2:thunderさんのすごさがわかるおすすめな記事です。文中に「人にゲームAI教えたらけっこう楽しかった」と書かれているのですが、これは私のことだと思っています。
世界四連覇AIエンジニアがゼロから教えるゲーム木探索入門 - Qiita
*3:私が競プロに興味を持つきっかけになった、自分にとって特別な記事です。
