little star's memory

競プロ、なぞなぞ、その他

ヒューリスティック素人によるAHC008参加記

MC Digital プログラミングコンテスト2022（AtCoder Heuristic Contest 008）が開催されました。

今までAHCは問題文が長くて実装量も多そう、そしてレーティングが見えないということで敬遠していましたが、レーティングが正式実装されたので取り組んでみることにしました。

ヒューリスティックは完全に素人です (ちなみにアルゴリズムのレーティングは青です。最近Rated参加していませんが…)。同じようにヒューリスティックが分からない人のためになればと思い、参加記を書くことにしました。

問題概要

30×30のマス目の中にペットと人間がいる。人間は移動または障害物の設置ができる。ペットは動き回る。ある人にとっての満足度は、その人が属する領域の大きさが大きいほど増え、領域内のペットの数が多いほど小さくなる。満足度の平均がスコアとなる。

取り組み

2月12日17時：参加開始。コンテスト自体は12時から始まっていますが、この時間から参加開始したのはこの時間に起きたからです。長い文章は苦手ですが、頑張って読みます。言語はC#にしました (普段はKotlinですが、なんとなくC#を書きたい気持ちになったので)。問題ページからツールをダウンロードしました。ツールはRustを使用しているので、無い方はRust環境を用意しましょう。

19時：最初の提出をしました。下のGIFを見ると分かる通り、今いる場所の四隅を塞ぐシンプルな戦法です。

点数は11,153,340で67位になりました。

22時：残念ながらABCが中止になってしまいました。なのでAHCのコードを少しいじります。犬がいる場合、四隅を塞ぐことに失敗することがあります。そこで、四隅を塞ぐ→移動する→四隅を塞ぐ→…といった感じで犬からの逃避を試みました。点数は11,223,129に上がり、80位になりました。

13日1時：移動する、と書いていましたが、これはランダム移動を実装していました。そこをなるべく遠くへ移動するように変更しました (DFSを使います)。点数は11,377,699に上がりました。111位になりました。

5時：テストツールを複数テストケースまとめて実行したくなりました。当初はツールのRustコードをいじって作ろうと思いましたが、理解できなかったので諦めてPythonで書きました。このように合計スコアと、どのケースでスコアが上がったかがわかるようになっています。

f:id:koboshi_kyopro:20220222035734p:plain

コードの方も方針を変えてみます。

左上に結集して領域を作りながら右へ移動する作戦です。seed=0はこれでうまくいきますが、他のシードでは動物が入り込むので何とかしたいところです。点数は86,800,135と大幅に上昇しました。109位です。

6時：コードを少し綺麗にしました。AHCは期間が長いこともあるので、読みやすいコードを書くことが大切になると思います。

7時：領域の大きさを1行にしてみました。点数は180,109,816となり、桁が上がりました。92位です。

17時：領域内に動物がいるときに領域を区切ることを試みます。大きさが1行なので簡単にできます。領域の大きさが半分以下になると、動物を一匹減らしてもスコアは増えないことに気を付けましょう。スコアは199,832,724になり、129位になりました。

18時：動物がいないときに領域を共有することでスコアを伸ばしました。253,402,873になり、121位。

14日7時：微調整。259,811,367になり、147位。

8時：領域を1行から2行に変えました。左だけ塞げばよかったものが、左と上を塞ぐようになります。他細かく修正して、395,009,647になりました。92位になり、久々に2桁順位になりました。

17日2時：ペットを数える領域の大きさにバグがあったので直しました。が、スコアは下がりました。188位です。

3時：最後に中央に留まるようにしていましたが、中央に到達したら再び左端に戻り、再び中央を目指すという繰り返しにしました。他細かい修正をして、スコアは406,189,261になりました。186位です。

4時：左端に到着したら中央に戻るようにしていましたが、塞いだ場合に左端に戻れない場合があるので修正しました。スコアは409,673,647、順位は185位になりました。

スコアが変わらないはずの修正をしていたらなぜか伸びました (どうして…)。スコアは415,954,953、順位は184位になりました。

22日0時：抜本的な変更をするのを先延ばしにしていたら時間が過ぎ去っていました。意を決してコードを書き換えます。スコアは1,001,325,411と桁が上がり大幅に伸びました。順位は184位です (数日前と変わっていませんね)。

この解法は共有されたビジュアライザに着想を得ています (今回ビジュアライザから得られる情報が普段よりも多いらしいです)。30個の領域を作り、ペットがいる領域を塞いでいきます。ちなみにペット数は最大20です。

3時：最終段階のブロックで動く人数を4人にしていましたが、これを $2\lfloor\frac{M}{2}\rfloor$ 人にするように変更しました。スコアは1,680,124,137と再び大幅に伸び、130位になりました。seed=0だとほぼ見た目変わりませんが一応ビジュアライザも貼ります。

4時：建設途中でも領域を塞ぐようにしてみました。スコアは1,948,960,504となり、124位になりました。

24日7時：建設は5人でやっていましたが、10人いるときには10人で建設するようにし、建設にかかる時間を短縮しました。スコアは2,107,682,731となり20億を超えました。155位です。

8時：出発地点を全員左端にしていましたが、ゴールが左側の場合右端スタートにする方が建設にかかる時間が短くなります。そのためスタート地点の調整を行い、スコアは2,328,150,174になりました。148位です。

11時：建設にM人全員使うようにしました。スコアは2,357,609,762と微増しました。148位です。

12時：建設が終わるタイミングはバラバラですが、建設が終わった後何もしないようになっていました。そこを待機中にペットがいるときに領域を塞ぐように変更しました。スコアは2,641,456,600になり、142位になりました。

13時：M≧6のとき一番下の行の建設を簡略化してスピードアップしました。スコアは2,673,474,832で極微増。

時刻を5で割った余りに応じて、左右を塞いだり中央を塞いだり移動をしたりと場合分けしていましたが、塞ぐのに失敗した場合何も行動しないことがありました。そこを修正してみました。スコアは3,301,156,247となり、30億を超えました。113位になりました。

25日1時：Mが奇数のとき、最後の往復移動で1人余っていました。この1人を動かすようにしたのですが、スコアが下がったので不採用です。別の改善も試してみましたがこちらも不採用。

26日6時：いよいよ最終日です。最初の移動の際、1番目の人が一番上、M番目の人が一番下となるように移動していましたが、これは移動距離が多く、賢くありません。もっと賢い方法はありそうですが、x座標でソートして移動先を決めることにしました。スコアは3,481,805,556となり、137位となりました。

19時：コンテストが終了しました (寝ていたら終わっていました…)。暫定156位でした。

27日：システムテストが終了しました。順位は145位に上がっていました。レーティングは720となり、茶色になりました。

最終提出

atcoder.jp

スコアは69,426,343,413でした。

seed=4ではこのような動きになります。

seed=4で動きを解説していきます。まず図の位置に移動します。

f:id:koboshi_kyopro:20220227174634p:plain

誰をどの位置に移動させるかは、x座標 (上から何マス目か) に基づいて決めます。もっと賢い方法がありそうですが。

その後、次のように障害物の建設を始めます。

f:id:koboshi_kyopro:20220227174859p:plain

下側の方がより速く建設できるようになっています。この段階でも領域内にペットがいるときは塞ぐようにしています。

建設が終わると次のような形になり、人の最終位置は次のようになります。

f:id:koboshi_kyopro:20220227175302p:plain

その後次の場所へ移動します。

f:id:koboshi_kyopro:20220227175404p:plain

あとはひたすら往復して、左右のペアで領域を塞いでいきます。(ここ賢くないですね。ペットがいる位置を探索して塞ぎに行くようにできたらよかったのですが…)

f:id:koboshi_kyopro:20220227175559p:plain

無事に全部のペットを隔離することに成功しました。

失敗すると次のようになります。(seed=51)

f:id:koboshi_kyopro:20220227175930p:plain

まとめ

今回のコンテストでやったこととやらなかったことをまとめます。

やったこと

  • コードを書く
  • ツールを活用する
  • 複数のテストケースをまとめて実行するコードを書く

コードを書きました (当たり前)。公式から提供されるツール・ビジュアライザは非常に便利でした。これらを使わないのはもったいないと思います。あとは複数テストケースまとめて実行してスコア計算できるようにしておくと便利だと思います。

やらなかったこと

  • ペットの情報を活用すること
  • スコア計算
  • 乱択
  • 焼きなましやビームサーチなどの名前だけ知ってるやつ

ペットは5種類おり行動パターンが違っていますが、それを活用することはしませんでした。また、ある段階でのスコアを計算して、次の行動を考えるということもしませんでした。ヒューリスティックと言われて多くの人が想像するであろうランダム要素も取り入れませんでした。勿論焼きなましなども使っていません。(この問題で使えるのかすら知りません…)

逆に言えばこれらを知らなくてもこの程度の順位はとれるということです。必要なアルゴリズム能力もABCのBかCくらいだと思います。より高い順位を目指すなら高度なアルゴリズムや、ヒューリスティック特有の手法が必要になると思います。

感想

ヒューリスティックは長くて面倒なイメージを持っていましたが、実際やってみたら意外と楽しかったです。次も同じように参加できるかはわかりませんが、レーティングが上がるうちはまた参加したいと思っています (AHCは非減少レーティングなのも嬉しいポイント)。

ヒューリスティック特有の知識も少しずつ身に着けられればいいなと思っています。