こんにちは。カケハシでデータサイエンティストとして働いている川渕です。 2024年3月3日にAtCoderで開催された第一回マスターズ選手権-予選-にカケハシのメンバーと参加してきたので、決勝前に参加記を書いておきたいと思います。

なお、対象読者はAHC(Atcoder Heuristic Contest)参加者とするので、細かい内容については説明を省かせて頂くことをお許しください。

チーム結成から予選まで

最適解が求まらない系の最適化問題が社内にありそうな気がしたので、カケハシ入社前の2023年の秋くらいから趣味と実益を兼ねてAHCへの参加を始めました。 AHCは一人でやっていても十分おもしろいのですが、マスターズ選手権の開催が発表された時にチーム戦も一度は経験してみたいと思い、社内のSlackでチームメンバーの募集をかけました。

メンバー募集には苦労しましたが、Musubi Insightのチームでテックリードをやっている横田さんが反応してくれて無事に2人チームを結成することができました。（SNSとかで募集すればもう少し簡単だったろうなと思いますが、入社したばかりだったので社内の人との関係を持ちたいというこだわりがありました。）

チームとして参加することになってからは過去問解法やビジュアライザーの作り方についての勉強会を隔週ペースで開催していました。過去問解法の研究はそれまでも多少やっていたのですが、勉強会を行うことでこれまで以上にさまざまなアルゴリズムに対して理解を深める機会になりました。

その他、予選の前日までに行ったこと

今後こういうことがあるか分かりませんが備忘録的な目的で書き残しておこうと思います。

相談用のDiscordサーバーの作成
解法共有用のリポジトリの準備
ビジュアライザーの作り方と共有方法の決定（こちらの記事を参考にしていました）
役割分担決め
チーム名の決定と参加登録（KKHSというチーム名になりました）

予選当日

万全に準備を整えたところでいざ本番と思ったのですが、諸々の事情により横田さんがほぼ参加できないことになってしまいました。戦力ダウン感は否めませんが、まあ28歳以上の人間にはよくあること（？）ですから、こういうトラブルも含めてマスターズ選手権と思って気持ちを切り替えます。とはいえ、完全に1人になっていたかというとそうでもなく、Discord上でアイデアを話し合ったりなど最低限のコミュニケーションは行っていました。

13:00 予選開始

何はともあれ、予選開始です。とりあえず問題を読んでみます。

問題の概要は以下のような感じです。

高橋君と青木君がグリッド上を移動しながらグリッドに書かれた数字を交換していく
隣接マス同士の数字の差の2乗和ができるだけ小さくなるように並び替える

問題を読んで思ったことは色々とありますが、個人的に印象に残っているのは以下の2点です。

最初と最後のターンの状態が見られるだけでも役に立ちそうなので、その程度の簡易的なビジュアライザーは片手間でも作れそう。（ただ、結局時間がなくてビジュアライザーは最後まで作れませんでした。）
高橋君と青木君の行動の順序が「交換してから移動する」になっているのが嫌かもしれない。（「いい場所に移動してから交換する」というアルゴリズムを考えたいと思ったので、順序が逆なのはちょっと面倒でした。）

なお、この問題にはtという盤面の形状を定める特殊なパラメーターがあり、それについてもっと注意を払うべきだったと今は思うのですが、単純に不注意で当日は見落としてしまいました。（通常のAHCだと盤面の形状はテストケース毎にランダムに決まるのに対し、同じ盤面を使い回すことでチームとしての分担をしやすくしていたようです。）

貪欲法の実装

ひとまず何か簡単に実装できそうな手法として、各ターンで取りうる行動の組み合わせを全通り比較してもっともスコアが改善する行動を選ぶ貪欲法を実装しました。要するに、一歩動いて交換するというのを繰り返す仕組みで、それを実装したのが以下のコードです。

この提出のスコアは405,352,941で、提出した時点では34位でした。貪欲法を実装した後はそれを拡張してビームサーチにするという計画を立てていたので、まだ本命の手法を残した状態でこの順位はなかなか良いのではと（その時は）思っていました。

ビームサーチの実装

次の1手だけを考えて最適な行動を選んでいたのを、何手か先まで読んで最適な行動を選べばもっと良くなるんじゃないかと素朴に考えてビームサーチを実装しました。実装し慣れた手法でもないので不安に思いつつも無事に実装はできてこれでひと安心と思ったのですが、手元でテストしてみるとスコアが悪化するということが判明しました。方針自体が悪いのか、実装に何かミスがあるのか分かりませんが、残り時間も1時間をきっており順位も80位くらいまで落ちてしまっている状況だったので、安心していたところから一転して何か手を打たないとまずいという状況に陥ってしまいました。

貪欲法の改善

ビームサーチがイマイチだった原因について色々と考えてみたい気もしましたが、時間もあまり残されていなかったので短時間で実装できて確実にスコアが上がる改善をするよう方針転換しました。

以下でも述べるようにこの貪欲法にはさまざまな改善点がありそうなのですが、その時目をつけたのは初期値の選び方についてでした。改善前の手法では初期値をランダムに選んでいたのですが、選ばれる初期値によって得られるスコアが大きく変わってしまうというのは明白だったので、初期値を変えて貪欲法を最終ターンまで回すのを時間ギリギリまでひたすら繰り返すような実装に変更しました。

これによりスコアは538,211,700となり、そこでコンテストが終了しました。

結果

チームKKHSの最終スコアは538,211,700で最終順位は75位となりました。条件を満たした上位50チームが予選通過ということなのでこの順位だと流石に厳しいかなと思っていたのですが、後日AtCoderからメールが来て予選通過できていたということが分かりました。（補足: マスターズ選手権は日本国内に在住の28歳以上で構成されたチーム上位50位までが決勝に参加でき、予選の順位表には28歳未満・海外在住・個人参加者・決勝進出を希望しないチームなども含まれているので、それらを除外した上位50チームが決勝に進出できます。）

後で調べてみたところによるとかなりギリギリの予選通過だったようで、最後の方針転換がなければ予選落ちしていたようです。何でもやってみるもんですね。予選はギリギリ通過でしたが、頑張って準備して決勝ではできるだけ良い順位を目指したいと思いました。

解き直し

参加記については以上なのですが、折角なので解き直しを行った結果をここで共有したいと思います。解き直しの方針として、ここでは自分の解法を突き詰めた結果としてどこまでいけたかにフォーカスしてみることにします。強い人のエレガントな解法を真似するという方向の解き直しも別途やりたいと思っていますがここでは取り上げません。

差分更新

まず1つ目の改善点は、数字を交換した後のスコアの計算を毎回盤面全体で行っていたのを、差分だけ更新するということです。割と基本的なテクニックだと思うのですが、当日は慌てすぎていてやり忘れてしまっていたので、ここではそれを直してみたいと思います。

この結果、スコアは635,533,110（61位相当）になりました。今回の手法は試行回数を稼げたかどうかでスコアが大きく変わってしまうものだったので、これを直すだけでかなりの改善が得られるようでした。 61位なら余裕で予選突破だったわけなので、今後こういうのは後回しにせず序盤でさっさとやってしまおうという良い戒めになりました。

数歩先まで見る貪欲法

上で実装した貪欲法は1歩移動して交換というのを繰り返すものでしたが、実際は数歩くらい先まで見た方が良かったです。そこで、BFSで移動先の候補を列挙して、その中からもっともスコアが改善する候補を選ぶようにしてみます。

これにより、スコアは725,915,636（49位相当）になりました。これくらいは普通に思いつきたいですが、当日は思い通りに動いてくれないビームサーチに気を取られすぎていたので仕方なかった気もします。

評価関数の変更

数歩先まで見る貪欲法を適用するのであれば、近くに移動する時と遠くに移動する時で異なる評価を与えたい気がします。たとえば、1歩移動してスコアが10改善するのと、10歩移動してスコアが10改善するのとでは、ターン数を消費しない分だけ前者の方が優れています。それを踏まえて、貪欲法における評価関数を単純なスコアの改善量から、スコアの改善量をターン数で除したものに変更してみます。

これによりスコアはもう少し改善して、785,307,232（35位相当）になりました。なお、この評価関数は解説放送で説明されていたのと同じものになります。

移動と交換を分けない

「交換してから移動する」という順序になっているのが嫌だったというのと関係する話なのですが、上で実装した「数歩先までみる貪欲法」は以下を繰り返す実装になっていました。

数歩先まで移動する
移動しないでその場で交換を行う

このような実装をしてしまうと、1回交換する度に1ターンむだに消費してしまうことになりとても良くないです。そこで、限られたターン数をできる限り効率的に使えるよう、以下のように実装を変更しました。

数歩先まで移動する
次の移動の時の最初のターンで交換も行う

これによりスコアはさらに改善して、910,831,095（22位相当）になりました。これくらいのスコアが予選で出せれば個人的には満足でした。

まとめ

以上、地味めな改善ばかりでしたが、貪欲法を突き詰めるだけでもそこそこ良いところまでいけることが分かりました。ちなみに、解き直しの過程でビームサーチを使った解法も試してみたのですが、とくにt=19（100×100のもっとも大きい盤面）のケースなどで盤面全体を周回しきれない感じがあり上手く実装した貪欲法には勝つことができませんでした。ビームサーチを使って強い貪欲法よりも明確に良い結果が得られたという方、もしいらしたら教えてください。