👶

とりまやってみるAHC 〜Algo灰色による初AHC参加記〜（AHC030）

2024/02/27に公開

Python

はじめに

はじめましてtabetaiです。大学院（M1）で機械学習の研究をしています。

タイトルの通り、数理最適化や競プロはからっきしなのですが、今回AHC030で初めてAHCに参加してみたのでつらつらと参加記を書いてみます。なお、解法についての説明はあまりに貧弱で冗長ですが、そこが主眼ではないということで見逃してください。以降精進します。

記事の目的

この記事を読んでくれた方が、初AHC参加ハードルを下げるきっかけになればなと思っています。
「典型手法とか知らなくても、気楽にAHC始められる＆そこそこ楽しめるんだ！」と思っていただけたら何よりです。
（競プロ始めたての自分が布教記事みたいなものを書くのは謎の立場感がすごいですが、自分も友達に布教してもらって楽しかったので、その恩返し的な気持ちで書いています。）

想定読者

競プロにおける典型手法に詳しくないがAHCにも興味がある人
Algoを少しだけやったことがあってAHCにも興味があるが、強い人がたくさんそうでビビっている人
競プロ初心者（Algo灰）がAHCをやるとどうなるのか興味がある人

自分のスペック

できること・知っていること
- Pythonと申し訳程度のC
- 機械学習浅く広く
- 統計学浅く広く
- ほんの少しのAlgo経験（灰）
  - ABCでCが3回に1回解けるくらい
できないこと・知らないこと
- Python以外のプログラミング言語
- 競プロの典型手法
  - 幅/深さ優先探索・二分探索・二部グラフなど簡単なものの概念は知っているけど実装はしたことない、くらいのレベル

大学院で機械学習の研究室にいる人で、このくらいのレベル感の人は結構多いんじゃないかなという気がします。
こういう人あるあるとして、「就活で研究以外にプログラミングについてアピールできるものがない！と急に焦る」というのが（多分）あります。実際に、僕自身それが理由でAtcoderを始めた節もあります。
マイページ登録の際にGithubやKaggle、AtcoderのURL欄を空欄で出すことに一抹の悲しさを覚えている人がいたら仲間です。仲良くしてください。

そもそもAHCとは

一応競プロとかやっていない友達も読むかもしれないので、簡単にAtcoderおよびAHCの説明を置いておきます。ご存じの方は読み飛ばしてください

AtcoderおよびAHCの説明

https://atcoder.jp/
AHCは、AtCoderという競技プログラミングのサイトで開催されているコンテストの名前（Atcoder Heuristic Contest）です。Atcoderには、AlgoとHeuristicの二つのコンテスト部門があり、AHCは後者にあたります。両方の内容的な説明は、以下のサイトがわかりやすいのでそちらをご参照ください。
データサイエンスを齧っている人には、Kaggleみたいな感じというのが手っ取り早いかなと思います。

AHC030（今回の問題）

こちらについても同様に、ご存じの方は読み飛ばしてください。

AHC030の問題説明

https://atcoder.jp/contests/ahc030
一辺Nのグリッドの島の中に、M個の油田が眠っています。
今、油田の形はわかっていますが、その油田がどこにあるかはわかっていません。
実際に特定のマスを掘ったり、特定範囲の油田の存在数を占ったりして、各油田がどのマスに配置されているのか、できるだけ効率的に当ててください。

みたいな問題でした。「効率的に」というのは、掘りや占いにはそれぞれ所定のコストがかかるので、そのコストをできるだけかけずに真の油田配置を当ててね、という意味です。
面白いですね〜ﾜｸﾜｸ

最終的な解法

システムテスト後で358位でした。
提出者全体の中なら上位30%くらい、正解者の中なら真ん中ちょい上くらいの位置です。

解法を一言で表すと：超適当ベイズ更新もどき

事前分布の定義
- ポリオミノの形から事前分布（マスごとの油田数期待値）を定義
  - 確率分布ではないですが、便宜上事前分布と呼称
占いによる事後分布の導出（事前分布を更新）
- 一辺の長さdの正方形の範囲を占う（N-d<dの場合、よしなに長方形とする）
- "占い結果 / 占い範囲のマスの事前分布における総和"を、事前分布の各マスに掛け算し、事後分布とする
  - この時、占いの結果が0の場合のみ0.1をかけるようにする
    - 油田があるのに期待値が0となってしまうマスが出て来るのを防ぐため
掘りおよび掘りによる事後分布更新
- 事後分布において、期待値が高いマスから掘っていく
- 掘った結果が1以上の場合
  - 掘ったマスの隣接マス（上下左右および斜めのうち、存在するマス）に任意の値を乗算し、事後分布を更新
    - 上下左右には $t_{next}$ を乗算
    - 斜めには $t_{cross}$ を乗算
- 掘った結果が0の場合
  - 掘ったマスの隣接マス（上下左右のうち存在するマス）に任意の値 $d_{next}$ を除算し、事後分布を更新
    - こちらは斜めには触れない
3を、掘った油田数=入力された油田面積数（ $d_k$ ）の合計、となるまで続ける

コンペ期間中の推移

やったことを時系列順で記載していきます。
こちらは、コンペ期間中にリアルタイムで取っていたメモ+後日見やすいように一部修正したものです。今思うと間違いだな/非効率だなという部分もあえてそのまま載せているので、初心者の思考の軌跡としてお読みいただければ幸いです。

サンプルコードの提出まで（DAY1）

問題理解
- 思ったより問題文わかりやすい、そして短い。もっと意味不明だと思ってたので、この時点で結構モチベが出る。
- 多少わからんことあるけど、まあそれはサンプルコードprintデバッグしたりして確かめればわかりそう
実行環境理解
- Webとローカルがあるらしい。ﾗ、ﾗｽﾄ... !?（ここで発狂）
- PythonとRとC少ししか触ったことないし、データサイエンス的なコーディングしかしたことないし、Rustなんて無理だよ...
- とりあえずローカルテスタやってみて、まじで無理そうならやめよ
サンプルコード提出
- まあよく分からんけど、とりあえずサンプルコードをコピペして提出っと...お、AHC初提出&レートつくの確定〜〜やったーー

初自作解法提出まで（DAY2）

ローカルテスタの環境構築
- 順位ついてモチベage！すぐ手法改善入りたいけど、まずは鬼門のローカルテスタだ...いよいよRustだ...
- とりあえずローカルテスタを公式の案内通りに入れて...あれ、なんか普通に動いたぞ？環境構築まじで苦手な俺がRust（でできた何か）を使えているだと...!!?!?!?
  - Rustのインストールだけはこのサイトを参考にして、あとは公式の案内通りにやりました。
    - https://zenn.dev/shogo_wada_pro/articles/365e2710a44f5a
サンプルコード改善
- とりあえず占いは使わず、最小限の改善でスコア上げよ。
- 左上から掘っていくのは変えず、 $v(i、j)$ の累積和が油田の面積と等しくなったらコード終了するようにしよ。そしたら余分に掘るの少なくなって総コスト削減できるやろ！
- （すごく軽微な改善だが）記念すべき自作解法提出！スコアも上がった！AHCたーのし！！！！！

占ってみる（DAY2）

やっぱこのゲームのキモは占いだよな。Algo灰色、二分探索すらも実装したことない俺が占い使えたらカッコよくね？（全然褒められたことではない）
→とりあえず占いを使ってみよう。以下思いついた順で方針

全部のマス1つずつ占って、1以上のとこだけ掘ればいいのでは？
- それだと全部掘るよりコストかかるやん。なし
- 程よく雑に、でも効率よく目星をつけられる占いを行うことが大事なのでは？
1行もしくは1列ずつまとめて占って、結果が1以上になった行/列から優先的に掘ろう。
- 採用。ちょっぴりコストが下がる。記念すべき初占い！
- 「行列それぞれ1つずつ占って、片方0のマス目は油田（ほぼ）ないのでは？」と気づく
行列それぞれ1つずつ占って、両方が1のマス目から優先的に掘る
- またちょっとコスト下がった。一旦これ提出しよ！占い使って初提出！

ローカルでの複数入力並列テスト（DAY2）

友達からそのうち使いたくなるかもとのことで、以下を紹介してもらった
- https://zenn.dev/ikoma_3/articles/5c04ab03935f71
（最初はあまり必要性が分からず）ゆーて使わんやろと思っていたが、一回WAをくらい、原因が単一の入力でしかテストしていなかったことだったので、やってみることにした
とりあえず動いたものの、Scoreが全部0になっちゃった→友達に助けを求める。
なんと友達が動くようにコードを書き直してくれた...友達さまさま...

以降に試したこと・考えたこと（DAY3〜）

占いを行列単位ではなく、ある大きさの正方形単位でやってみる（DAY3）
- ちょっとスコア上がった！
簡単な改善ではなく、ちゃんとした（していそうな）解法を考えたい！（DAY5）
- 占いを使うという目標は達成できたので、ある程度ちゃんとした解法に取り組む覚悟を決めた。一度問題を抽象化して考えてみる
- 今回の問題を抽象化すると、以下のようになる
  - 入力では、不確実性（ポリオミノの位置が不明）を含んだ情報が与えられる
  - データ（掘り・占いの結果）を得ると、不確実性が減る（ポリオミノの位置の候補が減る）
  - データは逐次的に与えられる（掘りや占いを行うたびに、その結果が得られる）
- 「あれ、これベイズでは？」 と気づく
- どんな確率分布をベイズ更新するべきかを考え、以下二つの方向性を考えた
  1. マスごとの油田数の分布
    - 最初は、縦軸油田数で、2次元混合多項分布的なイメージを持っていた。
    - しかし、これは確率分布ではないと気づき（縦軸が確率ではないので）、ベイズ更新できなくて絶望。
    - 一方、厳密なベイズ推論はできないが、掘ったら油田あった→周りの油田掘る確率上げる、みたいな簡易的なベイズ推論みたいなものはできるかも？と思う
  2. ポリオミノの各配置パターンの存在確率の分布
    - 占ったり掘ったりする前は一様分布で、何かしらアクションを行うとそれが更新されて偏りのある多項分布になるみたいなイメージ
    - こちらはベイズ推論できそうだが、どういうアルゴリズムでベイズ更新するか思いつかない。。。
      - 多項分布なら共役事前分布はディリクレ分布だが、尤度の計算とかどうすんだ？MCMCも思いつかない。。。
- 2は難しそうなので、一旦1を採用し、1に満足したら2を試してみることにした
マスごとの油田数の分布を用いて、掘っていく順番を決める（DAY6〜）
- 先ほどの方向性1に従い、最終的に最終解法に行き着いた形ですが、それまでに以下のことを試した。
  - 事後分布を更新する位置の選定
    - 入力生成プロセスを考えた際、あるマスに油田がある/ない時、にその上下左右にも油田がありそう/なさそうと言える
    - 一方、斜めはどうか？上下左右と同じようなことが言えそうだが、上下左右よりは関連性が弱そう
      - 上下左右よりも弱めに事後分布更新を行うことにする
  - ハイパーパラメータ探索
    - スコアが高くなるような $d_{next}$ や $d_{cross}$ の値を決定
    - Optunaを使ってやりたかったが、うまくスコアを受け取ってOptunaに渡すことができず、断念。最終的に人力でちまちまやりました。
      - コマンドライン引数を頑張って受け取っている様子
  - NとMに応じて解法を変更
    - 各テストケースの結果とN、Mの値を一緒に保持し、考察していたのですが、結局なんだかよくわからなくなって、道半ばで諦めてしまった。

参加してみて楽しかったこと

自分で一から考えたアルゴリズムを、自分の手で実装できたこと
- 普段触れている機械学習系のコードは、誰かのコードを少し改良するか、既存のものを組み合わせるのがメインで、正直自分で書いてる感はそんなにありません。
- 今回、稚拙ながらも、思考と実装を往復しながら作ったアルゴリズムが動いてACがついてかなり感動しました。「これがプログラミングか...！」となりました。
ベイズのユースケースを知ることができた
- 理由は正直自分でもわからないのですが、ベイズが最適化の文脈でも使えるということを知れて、なんか嬉しかったし、知的好奇心がすごい刺激されました。
- ただ、自分は元々卒論でベイズ統計の理論的な研究をやっていたのもあって、ベイズ的に綺麗な（よくある形の）アプローチに縛られて考えていました。尤度を正規化して計算に使うみたいな発想が出てこなかったのはこれが原因な気がするので、あくまで使えればいい的な発想も持っていきたいと思いました。（適当なこと言ってたらすみません）
解説放送を友達と見る
- Youtubeのwataさんの解説放送を、つよつよの友達と同じくAHC初参加者の計三人で見ました。わからない部分を解説してもらったり、逆に自分が理解できた部分を解説したりして、理解も深まったし、謎の青春感があってとても楽しかったです。
- ちなみに、この解説放送で山登りや焼きなましの概念を初めてちゃんと理解したのですが、なかなか学習体験として良かったです。
  - 以前教科書的に勉強した際はなんかふわっとしか理解できず、すぐ忘れてしまいました。
  - 今回のように、特定の問題設定があり、それにある程度取り組んでいる状態だと、使用目的や入出力データが明確にイメージできる分、ただ勉強するよりも理解が深い気がしました。

AHC参加を通じて得たもの

スキル編

目的に合わせたデータ構造の作成
- （正しいのかわからないが）普段は自分で書かなさそうな構造の辞書やリストを使い、当初は複雑そうで出来なさそうと思っていた処理も気づいたら書けていた。
コマンド/コマンドライン引数の扱い
- 普段あまりターミナルでコマンド実行することがなかったので、この辺りぼんやりとしかわかっていなかった。今回のコンペで、各種コマンドやpy/ipynbファイル上でのコマンドライン引数の扱いを知ることができた。
デバッグ
- プリントデバッグしかしてないが、前よりデバッグの勘所的なものが少し身についた気がする。
git
- コンペ関係ないが、これに合わせてgitも使い始めたので、gitも（個人で使う範囲で）使えるようになった。
テスタの扱い
- 基本的なローカルテスタの扱い方は多分できるようになった。これで以降のAHCに参加する心理的ハードルがだいぶ下がった。友達に手伝って貰わなかったら並列テスタとか多分動いてなかった．まじ感謝．
- ただ、今回サボってビジュアライザを全然使わなかったので、そこは次回に向けて反省点。

マインド編

問題を数学的な問題にうまく落とし込もうという気概
- コンペ中は、ぶっちゃけ数学的な問題にしっかり落とし込むのは難しそうだし面倒そうだからいいやと思っていた。ただ、Youtubeの解説放送でwataさんの解法（相互情報量やベイズ推定の話）を聞いたり，1位のテリーさんの解説記事を見て自分もこれできるようになりたいとめっちゃ思ったし、（箸にも棒にもかかっていないけど）これが思いつかなかったのが結構悔しかった。次回以降は、それが解法として実装できなさそうだとしても、頑張って定式化して綺麗な問題に落とし込みたい。
難しそうと思った実装も、細かい改良を繰り返せば意外となんとかなるという心持ち
- 期間初期は、占いや掘りの結果に応じて掘る場所を決めるのは実装が大変そうで無理だと思っていた。
- ただ、「これできたから次はそれにこれ足してみて．．．」みたいな細かい改良を繰り返しているうちに、気づけば辿り着けていた。（本当に盛りなしで気づいたらそこにいた。）
- やってみれば意外とできるというマインドもそうだし、焦らず、細かい改良を続けていくことへの忍耐も大事。

最後に

ここまでお付き合いいただきありがとうございました。

自分は結局一回も（少なくとも明示的に意識しては）競プロっぽい手法を使いませんでしたし、2日に1回3、4時間程度だけ取り組むという感じで、そこまで根詰めてやってもいないです。（全然遊びとか飲み会行ってました）

それでも、そこそこの順位を取れて、一回でヒューリスティックの色も変わって、楽しさ++になれました！

典型手法を知らないのは全然いいことではないし、勉強すれば見える世界も変わると思います。

ただ、個人的には今回参加してちょっといい順位を取れたことで、教科書的に勉強していくより確実にAlgoの勉強モチベも上がりましたし、（元々ある程度コーディングができる人には）こういう入門の仕方も結構ありなのではないかなと思いました〜
（もちろん自分は強い友達がたまたま近くにいたおかげで色々やりやすかった面はありますが）

最後に、コンテスト主催者の方々、一緒に参加して競ってくれた方々、そして自分をAHCに勧誘して色々教えてくれた研究室の友達に感謝を伝えて終わりたいと思います。

ありがとうございました！