[go: up one dir, main page]
More Web Proxy on the site http://driver.im/

日本橋ハーフマラソン 2025冬（AHC043）~Railway Company~ 参加記

日本橋ハーフマラソン 2025冬（AHC043）~Railway Company~ 参加記

AHC043に参加して、109位/1,431人 でした。

解法や所感について書いていきます。

解法

「単純化したモデルでビームサーチを実施した後、ビームサーチで得られた結果を実際に作ってみて一番良かったものを返す」をしました。

次節から、それぞれのパートについて詳しく書いていきます。

単純化したモデルでビームサーチ

  • 建設する駅は全部連結にする
  • 新設する駅は、既建設駅の中で最も近いものと最短経路で繋げる

という前提を立てたモデル上でのビームサーチをしています。

具体的には、

Stateは線路や操作履歴の情報は持たず、「ターン数」「建てた駅の位置と順序」「所持金」「ターン収入額」「ペアの片側だけ連結成分に含まれている家職場の数」の情報のみを持ちます。

遷移は、

  • 駅を新規に１つ建て、それを既存の駅連結成分に線路を引いて繋ぐ*1
  • ゲーム終了までWaitし続ける

の２つです。
優先度付きキューを総ターン数ぶん常に持っておいて、ターン数昇順にキューを舐めながら上述の計算を進めていきます。

駅の新設位置候補はある程度絞り込んでいます。
具体的には、フィールド全体を2x2の区画に分かれるようにグリッド状に分割して、各区画から代表マスを１つずつ選出しています。選出基準は、駅を建てた場合に含まれる家職場の数の多さです。
ただし、一番最初の駅の建設位置だけは全マスを候補にしています*2。

ビーム幅は１です（同一ターンのキューで合流しない限り絞られることがないので、ビーム幅は１ですが多様性はある程度保たれています）。

評価関数は、所持金 + (収益 + ペアの片側だけ連結成分に含まれている家職場の数) * 残ターン数 としました。
気持ちとしては、「このままWaitし続けた場合の所持金」が大筋で、そこに片側のみの家職場の多さをちょっとだけ加味したって感じです。

このモデルだと計算量が 建設駅総数(探索の深さ) * ビーム幅 * 候補マス数 * 建設駅総数(遷移の計算) で済みます。

ただし、これだけだと操作列が無いですし実値とも当然乖離し得るので、
ビームサーチ終了後に Tターン目のキューに集まったStateに対して、ちゃんとしたシミュレートを実施し最もスコアが良いものを最終的な回答としています。
そこの手順について、詳しくは次節で説明します。

ビームサーチで得られた結果を実際に作ってみる

前節のビームサーチで得られた結果(駅の建設位置と順序)を実際に作ってみて、最も良かったものを最終回答とします。

具体的な手法は単純で、「ビームサーチで求めた駅の建設順序通りに、連結を保ちながら駅を追加建設していく。連結のための線路のルートは、既存連結成分に繋がる最短経路をBFSで求める。」ということをしました。
ただし１つだけ工夫があって、BFS中に「それ以降に設立される予定の駅の座標」を踏んだ場合はキューに front push *3をすることで、その座標が含まれるパスを優位に扱っています。
駅の建設位置が線路上にあれば、単に駅を建設するだけで*4接続できて有利なためです。

簡易モデル上でのスコア上位のStateから順に時間いっぱいチェックする という実装にしていましたが、実際は全てのテストケースで実行時間に余裕があったため、そもそも全ケースチェックできていました。

ケース0000のビジュアライズ結果

その他解法に対する雑多なコメント

  • ビーム幅は増やすとむしろスコアは悪くなりました。おそらく、同一ターンのキューで出くわす があまり起きないことで多様性を保っていたのに、ビーム幅が増えるとそこが損なわれてしまうため、ではないかなと考えています。
  • 「ビームサーチで得られた結果を実際に作ってみる」パートでは、簡易モデル上でのスコアより実際のスコアの方が大きいケースの方が多そうでした。これは、最短経路で繋げなかったケースのマイナスよりも、線路上に直接駅を建設できたことで線路建設が不要だったケースのプラスの方が大きいためだと思われます。
    • そのためか、実結果でベストスコアが出るのは、簡易モデル上では駅を作りすぎてしまって投資回収が間に合っていないケースに多いようでした*5。

提出コード

Submission #63119698 - RECRUIT Nihonbashi Half Marathon 2025 Winter（AtCoder Heuristic Contest 043）

感想を雑多に

  • 暫定テスト時点では99位とギリギリ２桁順位に滑り込めていたのですが、最終結果で109位まで落ちてしまいました、、とはいえ黄パフォは出せたので満足です。
  • Kが小さいし駅建設費は高いしで、開始当初はほとんど建設できずに終わるゲームなのかな？と思ってたんですが、コンテストを進めるにつれ、案外結構な数が建設ができることが分かっていって面白かったです。
  • 資金繰りの都合で駅の建設順序は重要だと思ってたんですが、Xのタイムラインを見た感じそうでも無さそうで驚きました。
  • 今回コンテスト参加人数が過去最多らしいですね。めでたい。

*1:「新設する駅は、既建設駅の中で最も近いものと最短経路で繋げる」という前提なので、O(建設済み駅数) で計算できます。

*2:家職場を１つも含まないマスは除く

*3:BFSは両端キューで実施してます。

*4:線路を引く必要無く

*5:実結果では、線路上に直接駅を建設できる分の短縮で投資回収が間に合うため

HACK TO THE FUTURE 2025（AHC040）~Packing Uncertain Rectangles~ 参加記

HTTF2025(AHC040)に参加して、88位/1,172人 でした。

解法や所感について書いていきます。

解法

大筋

1ブロックごとで推定 + ルールベースで保険解作り + (正方形容器サイズの二分探索+ビームサーチ)
って感じでした。

ビームサーチが本筋で、ルールベースの方はビームサーチが上手くいかなかった時*1の保険です。 クエリの配分は、(T-10)個を推定、6個をルールベース、4個をビームサーチに使いました。

ビジュアライズ結果例が以下です。推定,ルールベース解,ビームサーチ解 の順で出力しています。

続けて、それぞれのパートの詳細について説明していきます。

1ブロックごとで推定

1ブロックの設置のみでクエリしてサンプリング、ということをしました。
サンプリング数の割り当ては、各ブロック均等になるようにしました*2。

公式解説配信の49:55~ でも説明されているので、詳細はそちらを参照してください。

正方形容器サイズの二分探索+ビームサーチ

正方形型に詰めるのが有利なので*3、所定サイズの正方形枠を用意して、そこへの詰め方をビームサーチで決める方針を取りました。
正方形枠の一辺の長さは二分探索で決めます。判定関数が「ビームサーチで解を見つけられるか」となる感じです。

続けて、それぞれのパートの詳細について説明していきます。

正方形容器サイズの二分探索パート

パッキングを試みる正方形の容器サイズを二分探索で決めます。

探索対象は、「一辺の長さの理論値*4への係数」としました。
具体的には、一辺の長さの理論値が {\frac{sum(w+h)}{2\sqrt{N}}} *5で求められるので、これに掛ける数ができるだけ1.0に近づくように探索します。

探索範囲ですが、ビームサーチはそう連発するわけにもいかないので*6、安全側に寄せて、初回判定で解が確実に得られるであろう範囲で取りました。具体的には、係数が 1.2 の場合にビームサーチが安定して解を見つけられる傾向にあったので、そこが初手に来るように、二分探索のレンジを 1.0~1.4 に設定しました。

ビームサーチパート

正方形容器のサイズの二分探索の判定関数として、それにグッズを詰めるビームサーチを走らせます。

設定はざっくり、

  • 遷移: グッズを１つ置く操作。「回転」「方向」「隣接ブロック」全パターンを扱う。
    • 「重複盤面」と「隣接指定ブロックまで届かなかった場合*7」は除外する
    • 設置シミュレーション結果が怪しいケースは除外する(後述)
  • 評価関数: 置くグッズの i が前半80%の場合は、グッズの原点からのユークリッド距離の合算*8。後半20%の場合はスコア*9で、タイブレークにユークリッド距離の合算を引き続き使う。
  • ビーム幅: Nに反比例させる形で設定。[100, 1250] の範囲。

という感じです。

遷移の、「設置シミュレーション結果が怪しいケースは除外する」についてですが、
以下の図のような、グッズサイズの誤差のために、シミュレーション上では通過できると判断されたところが実際は通過できずに以降全部が崩れる*10、みたいな事例がよく起きるので、その対策として入れてます。

具体的には、設置時に隣接指定ブロック以外とすれ違う場合に、長さを±2σしたら衝突するかどうかが変わる場合に、その遷移は除外するようにしました。

これを入れてもなお壊れることは往々にしてあるため、このパートでの解は４つ提出することでリスクヘッジしています。具体的には、二分探索結果の上位２つから、ビームサーチ結果の上位２つを取っています。

これらによって、入力ケースの75%くらいは壊れずに結果を出せていそうでした*11。

ビームサーチ解のケース0のビジュアライズ

ルールベースで保険解作り

前節のビームサーチパートの説明にあったように、提出ケースの25%ほどはシミュレーションミスで壊れてしまいます。
そうなってもスコアを大きくは損なわないように、短時間で動くルールベースで保険の解答を作っておきます。

大筋の方針は、ビームサーチ同様、正方形容器にグッズを詰める形を取っています。
一行ずつ横幅一杯になるまで詰めて、終わったら次の行に進む、という流れになります。グッズの回転は縦長統一です*12。

もう少し具体的には、

  1. 一つ前に置いたグッズを隣接に指定して、縦長に回転した上で U 操作で置く。
  2. 1 を繰り返し、横幅一杯に埋め切ったら次の行に移って、また 1 を繰り返す

をグッズが無くなるまで実施します。
ただし、１つ上の行の右端に差し込める場合は、例外的にそこに置きます。また最後の行だけは、横幅に余裕がありそうだったら横長に統一して置きます。

正方形容器のサイズは６パターン試して全部提出します。正方形の一辺の理論値の係数を、1.00~1.25倍まで0.05刻みで指定しています。

出来栄えとして、1ブロックごとの推定+このルールベース のみで提出したものが224位、って感じでした。

ルールベース解のケース0のビジュアライズ

提出コード

Submission #60606856 - HACK TO THE FUTURE 2025 (AtCoder Heuristic Contest 040)

その他、思ったことを雑多に

  • 「順番固定、置き方も制限って難しすぎでは」と最初は思ったけど、矩形パッキング問題自体がNP困難な中で不確実性要素まで入ってきてるんだから、むしろ他は制限が掛けられてる方がありがたいか、と思い直したりした。
  • 手元でのスコア指標に、スコア理論値*13 {\frac{sum(w+h)}{\sqrt{N}}} と実スコアの比率を使用していたが、これが有用に感じた。Nやグッズサイズの違いを抑えてテストケース間の比較ができるので。
  • 計測結果の上限下限の丸めに余裕があるの、もしかして今回が初ですかね？割とそこに悩まされていた記憶があり。
  • 上位以外も相対スコアがそれなりの数値になるの珍しいなと思った*14。１ケースが重い分、暫定テストとシステスで結構結果が変わりそうだなと思ってたけど、実際はどうだったんだろう*15。
  • 積んだブロック達の外郭線の長さが評価指標として良さそうかなと思っていたが、難しそうなので避けた。やった人はいるのだろうか。計算や保持データが重くて(?)あんまり上手くはないかも？

解説放送を見た上での反省点（ポエム寄り）

今回は安定操作を用意するのがまず第一優先事項のようだった（そこを詰めれば推論無しでも30位くらいまでいけるらしい）。そういうふうに着想できていなかったのが、もう数ランク上の順位帯に行けなかった直接の原因だとは思うのだけど、とはいえどうすればそういう発想になったのだろうか。

「ユークリッド距離の合算が評価関数としてそこそこ良い」を見つけていたので、そこで満足せずに突き詰めていくと、階段状っぽい形を強制出来ている点に良さがありそう を発見できた可能性はあったのかな、とは一応思いました。
ただ、なんかそういう切り口じゃなくて、問題理解の延長でどこが肝かを察せられう能力がもっと要るような気もしています。こういう能力はどうすると身に付くのだろうか。

あとは、短冊状に区画を区切る、は以前の矩形パッキング回(AHC031)でも出てきたやつなので、思いつきたかったです。
正方形区画に区切るって発想までは出ていたので、そこから更に広げていけると良かったのかなあと思ったり。

終わりに

大筋の方針はやんわり外してしまった中で、まずまず頑張れたんじゃないかなと思いました。
色んな知識を引っ張り出して*16頑張って殴ったって感覚で、色んな過去回が思い起こされました。

これで今年の長期コンは終わりですかね。それなりに満足の行く結果で終えられて良かったです。久々にコンテストで賞金が得られたのも凄く嬉しい。

*1:盤面シミュレーションが実態と食い違ってまずい形になってたとき

*2:割り切れない分は iが若いブロックに優先して振りました。先に置かれるブロックの精度はそれ以降の置く操作にも影響するため重要度が高いはず、という意図でしたが、実際に良くなっていたのかは分かりません。

*3:同一面積なら、正方形が一番W+Hが小さいので。

*4:隙間なく詰められる場合の正方形容器の一辺の長さ

*5:{\sqrt{N}} X{\sqrt{N}} 個で配置するので、幅or高さの合算値{\frac{sum(w+h)}{2}} を{\sqrt{N}} で割れば良い、みたいな気持ち。

*6:ビーム幅を確保したいですし、Nが大きいケースではビーム幅200程度でも3回しか回せないくらいカツカツでした。

*7:例えば、U 操作をするときに、置くブロックの上辺が隣接指定ブロックの下辺のy座標を超えなかったような場合。

*8:端から詰めて置く圧力と、隙間があることに対して減点する効果を狙った。

*9:盤面の W+H

*10:この例だとたぶんid=34が契機。

*11:Nが大きくてTが小さいケースが特にキツそうでした。

*12:なんでなのかはあんまり分かってないですが、ランダムや横長統一よりも明らかにスコアが良さそうでした。ランダムより良いのは統一してる分ロスが少ないから、横長より良いのは縦横両方が大きいグッズがどうせあるから行の縦幅は使い切ったほうが得、とかでしょうか？

*13:正方形容器に隙間なく埋められた場合のスコア

*14:サンプルコードで34G点くらい出るらしい

*15:少なくとも私は普段よりも変動が多かったと思う。

*16:矩形パッキング、区間推定、ビームサーチ、二分探索、zobrist hashingとかとか

AtCoder Heuristic Contest 037 ~Soda~ 参加記

第11回 Asprova プログラミングコンテスト（AHC037）に参加して、98位/985人 でした。

解法について書いていきます。

解法

大筋

貪欲法をしました。

  1. 入力の飲料だけを使用して、一定のルールで解を構築する
  2. 1 の結果を逆順に辿りながら、飲料間に結合点を作り繋ぎ直す

という感じのことをしました。 もう少し詳しいところは次節以降で説明していきます。

解のビジュアライズ結果は以下になります。

ケース0のビジュアライズ結果

「入力の飲料だけを使用して、一定のルールで解を構築する」パート

大筋のパート1の細かい説明です。

以下の手順の操作をしました。

  1. 入力の飲料から min(x, y) が最も小さい物を選択
  2. 既に選択されている飲料の内、1で選んだ飲料とマンハッタン距離が最も小さいものを接続
  3. 1 2を入力の飲料が切れるまで繰り返す

選択方法の気持ちは、壁際から詰めていく感じにしておく方がパート2にとって都合の良い依存順序になるから、って感じです。
(最初は選択順序に x + y を使っていたんですが、min(x, y) の方がスコアが良かったです。例えば (0, 0)-(0, 10^6) みたいなエッジに対して、(1, 10^5) のような点を繋ぎ損なうダメージがでかいからだと思っています。)

ここまでで、以下のようなグラフができます。

1 の結果を逆順に辿りながら、飲料間に結合点を作り繋ぎ直す

大筋のパート2の細かい説明です。

ノード間の最短経路中に中継点を新たに作っても、スコアは悪化しないことを利用して、
あるエッジに中継点を作り、別のエッジを壊してその中継点に繋ぎ直すことでスコアの改善を目指します。

中継点作成のイメージ図

上図がその例です。左側のエッジに右側のエッジを繋ぎ込もうとしています。
②は左側のエッジの最短経路上に中継点(青点)を打つ図です。元の経路と青点を経由するルートでスコアは同一です。
③は両エッジで青点を使うようにエッジを張り替えた図です。こうすることで、左のエッジのスコアを維持しつつ、右のエッジはスコア改善できています。

上述の考えを使って以下の操作を行いました。

  1. パート1で作ったエッジの列に対して、作成順と逆順にエッジを見ていく
  2. 選択したエッジより前のエッジ*1の中から、最短経路中に中継点を作ることで1で選択したエッジのスコア改善ができる場合、最も良いケースを選んで繋ぎ替える。
  3. 1 2をエッジを舐め切るまで続ける

提出コード

Submission #57820282 - 11th Asprova Programming Contest（AtCoder Heuristic Contest 037）

コンテスト後タイムラインを見た所感と反省点

コンテスト後にXのタイムラインに流れてきた、@soiya_ksk さんのこちらの投稿が印象深かったです。私の解法と同じような方向性でありながら、すごくシンプルにまとまっていてかつスコアもかなり高かった*2ので。

砕けた説明をすると、「より右上にある点から優先して結合していく」みたいな感じですかね。

こちらを踏まえた上で自分の解法を振り返ってみると、

① ノード間の結合として捉えた方が自由度が高いのに(たぶん)、自分はエッジ間の結合として捉えてしまっていた。その結果、結合の順序づけの自由度が下がってしまった。
② 考察結果をシンプルに書き下せるくらいに整理することができていなかった。

あたりで特に考察面に課題を感じました。

上手く考察を進めて、この解法まで辿り着きたかったですね。

*1:パート1で先に作った方

*2:23位相当

CodinGame Summer Challenge 2024 ~Olymbits~ 参加記

CodinGame Summer Challenge 2024 ~Olymbits~ コンテストに参加しました。

www.codingame.com

順位は、総合574位、Goldリーグ512位でした。
やった内容と感想について書いていきます。

ルール

「十字キーのみのコントローラー１つで４種のゲームを同時にプレーする」、というゲーム実況動画企画にありそうな感じのゲームでした。

今回もツカモさんがルール要約を作ってくれているので、詳しくはこちらで。
codingame:SUMMERF CHALLENGE 2024 ルール要約 - tsukammoの収穫記

解法

ルールベースをした。

大筋の戦略

  1. ダイビング、アーチェリーはミニゲーム間で一番スコアが低い状態*1の時に専属プレーする形で参加。
    • ただし、ダイビングは確定で1位になれるタイミングでしか入らない。アーチェリーはミニゲーム内で残り７ターン切るまで入らない
    • ダイビングは、以降にどう操作しても単独一位確定になった時点でプレー終了
  2. 1. に当てはまらないケースでは、ハードルとスケートの多数決

という方針を取りました。

ダイビングとアーチェリーは連続してプレーしないとほぼ成果が上がらないはずなので、特別扱いしました。

ハードルとスケートの多数決

2. のハードルとスケートの多数決部分は、それぞれのゲームで各アクションに評価点を割り振って、その合算が一番大きいアクションを選ぶ形を取りました。

ハードルの評価は素直な感じに振ってます。

スケートの評価は、

  • 最後の一手はコケてもいいので3進む
  • コケてる敵のいるマスには入らない
  • 基本的に「1コス2進む」より「0コス2進む」の方を優位に扱う
  • 所持リスクが0のときは「1進む」を低評価

みたいな感じの、確定で良さそうな内容だけを織り込む感じでした。

感想

どうアプローチすればいいのか最後までよく分からなかったコンテストだった。ビジュアライザを見ても何が肝になってるのか全然ピンと来ずだった*2。
今までコドゲで無かったタイプのゲームで、もうちょっと上手いことやってやりたい気持ちはあったのですが。。

この形式のゲームの典型手法みたいなのはあるのだろうか。上位の人がどんな手法を取っていたか気になる。

*1:同率最下位も含む

*2:作ったAIが強くなってる実感をビジュアライザから読み取ることができなかったのが、地味にモチベーション的にもキツかったり。

AtCoder Heuristic Contest 028 ~Lucky Words~ 参加記

ALGO ARTIS プログラミングコンテスト2023 冬（AHC028）に参加して、93位/918人 でした。

解法や所感について書いていきます。

解法

大筋

一単語ずつ選んでいくビームサーチをしました。

遷移は、

  1. 暫定解の末尾との重複度合いの大きさ
  2. 現マスからの近さ

の順で単語に優先度を振って、その上位5個くらいを選んで打鍵、としました。

ノードの評価は通算コストにしました。

提出コード

Submission #49255662 - ALGO ARTIS Programming Contest 2023 Winter（AtCoder Heuristic Contest 028）

解法内でよく分からなかったところ

選んだ単語の打鍵の経路の出し方について、最適経路でない方が良いスコアが出ました。

最初はビームサーチで経路を求めていたのを、後からDP手法(厳密解を出せる(はず))に気付いて書き換える、という流れを経たんですが、DP手法にした方がスコアが悪くなってしまいました。
単純にDPの実装をミスっただけなのか、あるいは、ここの計算が適度に悪い方がビームサーチがむしろ良い塩梅に進む みたいな感じだったのかもしれません。

雑感

  • 「貪欲法をした後、それを使ってビームサーチをする」というテンプレパターンをやった回だった。
  • 最近では珍しく(?)シンプルに考察できる回だった気がする*1。順位とレートの相関の高い回だったんじゃないかなという気がする（確認はしてないですが）。
  • コンテスト後に考えてみたけど、このビームサーチだと利益の先食いみたいなことが起きるだけであんまり嬉しく無さそうな気がした。打鍵コストの低い単語が序盤に当てがわれるだけで、全体を通した効率改善みたいなものに利するわけでは無いように感じる。TLの雰囲気からも感じたが、やっぱりローカルサーチ回だったのだろうか。

*1:ビームサーチや焼きなましに落としやすいというか

AHC022復習 ~「入口と出口の対応確率テーブルを作る」手法を試して、8位相当のスコアを出すまでにやったこと~

今まで統計・推定系の知識がほとんど無いままマラソン系のコンテストを戦って来たのですが、ACH022を経てさすがにこのままじゃ不味いなって気持ち*1になりました。

しかし、公式の解説動画を見ても(私の前提知識が足りなさすぎて)いまいち理解できず、どうしたものかなと思っていたところで、bowwowforeachさんの推定部分を重点的に解説してくれている記事を見つけました。 bowwowforeach.hatenablog.com

こちらがとても分かりやすく、この記事と合わせて改めて公式解説動画を見直したらそちらもある程度ピンと来ました。
おかげで実装できそうな気持ちになったので実際にやってみたら、ありがたいことにコンテスト時の8位相当のスコア*2を出すことができました。

ただ正直、上記２つの資料に沿って実装しただけで、かつ資料の出来もそもそも良いので、正直改めて書く内容も取り立ててはないんですが、
一応実装を通して得た、

  • どの程度のことをするとどのくらいの順位になるかの情報
  • もうちょっと具体的に、どう実装するかみたいな話
  • 配置や計測の回し方の例

といった、本筋である推定の理論・説明以外のところの情報は提示することができそうなので、
補足的な立ち位置の資料として、同じように勉強する人の助けにならないかな、みたいな期待からその辺りを記述した今回の記事を作りました*3。

やったことと、その順位

やったことの内、ある程度スコア*4が向上した内容を節単位で列挙しています。
節タイトルは やったことの概要 (暫定テスト順位) って感じで振ってます。

以降の記述は、前述したbowwowforeachさんの解説記事（以降は「参考記事」と呼びます）の内容を把握していることが前提になります。

参考記事に書かれていることを素直にやる。配置や計測順序は割と適当。 (42位)

参考記事にある、「累積分布関数を使って入口出口の接続確率テーブルを作る」を素直にやると、配置や計測順序で大した工夫をせずともこの順位が取れました。（凄い）

以降は、配置と計測を具体的にどうしたかを書いていきます。

配置

公式解説動画にも出てきた、一点高温を作ってそこを頂点の山にする配置をしました。
以下の画像のような感じになります。

もうちょっと具体的には、
頂点の温度を1,000、その四方を500とし、以降は頂点からのマンハッタン距離が1離れるごとに 1000/L ずつ温度を下げていきました。

山の頂点の座標は、各出口からのマンハッタン距離の総和が一番小さいセルを選んでいます*5。

Sに応じたチューニングとかは特に無いです。

計測の回し方

入口をID順に計測対象にしながら*6、以下の手順を繰り返します。全ての行で最大値が閾値を超えたら終了します。

  1. 入口出口の接続確率テーブル(以降は「確率テーブル」と呼びます)の、対象入口の行の最大値が閾値を超えていない場合、2以降を行う。
  2. 対象入口行の最大値の出口の座標から山の頂点に向けて計測を実行し、参考記事のやり方に沿って確率テーブルを更新する
  3. 確率テーブルの横方向の正規化を、全ての行に対して行う

閾値は98%にしました（seed 0~99で試して、誤回答が出なかったのがこの辺りのラインでした）。

縦方向の正規化 (24位)

公式解説動画*7や参考記事の最後の節に書かれていた内容になります。
実装が楽そうだったのでとりあえずやってみたら、かなりスコアが伸びました。

具体的には、計測ごとに以下を実施しました。

  1. 横方向の正規化を全行に
  2. 縦方向の正規化を全列に
  3. 横方向の正規化を全行に

（正規化の掛け方として適切なのかは不明です。）

閾値の変更 (20位)

42位解の計測の周し方節内で出てくる閾値の値を98%から95%に下げました。

縦方向の正規化を入れたお陰なのか、閾値を下げても誤回答が出なくなったので*8、計測コストを下げるためにこうしました。

計測序盤は山の頂点に近い出口を優先して扱う (17位)

公式解説動画で出てきた、近い出口から扱う手法*9を部分的に導入しました。

具体的には、

  1. 頂点からのマンハッタン距離が10以下の出口を列挙する。
  2. 手順1で列挙した出口に対して、距離が小さい順に手順3を実行する
  3. 対象の出口の確率テーブル列の最大値が95%を超えるまで、「その列の最大尤度の入口を計測対象として、出口座標から山の頂点を指す計測」を繰り返す。
    • この際正規化は、24位解の手順から3を省いたものを行う*10

上記の手順を終えた後は、前節までと同様の手順で計測を進めて完了です。

情報が少ない序盤ほど、確定までに計測回数がかかるはずなので、序盤に距離の短い計測が集まるようにこうしました。

元々は、「距離が10以下の出口」ではなく「全ての出口」を対象にするつもりだったんですが、やってみたところ期待通りにはいかず23位に落ちてしまいました*11。

2024/03/14 追記

実装をミスっていて、対象の出口をきちんと列挙できていないバグが埋まっていたことに気づきました。
8位解に対してここの修正を入れたら、6位に上がりました。確認はしていないですが、この時点でも17位より良い順位になるかもしれません。

Sが小さいケースで山を緩やかにする (8位)

ここまで配置の仕方は42位解のもののままで固定していましたが、
手元の試行結果を見ると、Sが小さいケースで配置コストがネックになっていたので、計測容易さよりも配置コストの低さを優先するようにしました。

大筋の方針は節タイトルの通り、Sが小さいケースで山を緩やかにする感じです。
具体的には、42位解の配置をベースに、Sの大きさごとに以下の変更を加えました。

  • S <= 36
    • 山の頂点の高さを600に下げる
    • 傾斜の温度を1000/Lずつ下げていたところを、500/Lずつに変更*12
  • 49 <= S <= 100
    • 山の頂点の高さを700に下げる
    • 傾斜は1000/Lのまま変更なし
  • S >= 121
    • 変更なし

S<=36のケースの配置例

これで8位スコアを取ることができました*13。

もう少し調整は頑張れる気もしましたが、一桁順位を取れて満足したのと、統計・推定系の知識を学ぶっていう復習の趣旨から外れつつあったので、ここで復習を終えることにしました。

終わりに

率直にやるだけでも42位が取れてびっくりしました。やっぱり知識って大事だな、とか数学の力って凄いな、とかを思いました*14。
コンテスト時に必死こいて作った自作解法はなんだったのだろう、みたいな気持ちにもちょっとなりました*15。

統計・推定の知見が元々ほとんどなかったのですが、分かりやすい資料の存在のおかげで無事に実装することができました。本当にありがたいです。

今回の取り組みを通して、推定系問題への苦手意識もある程度取り除けた気がします。
次に推定系の問題が出たときは良い順位を取りたいな。

*1:レートの伸び悩みだったり、コンテスト後Twitterタイムラインの理解できなさだったり。思ってたより統計・推定の知識が求められる問題の出題頻度高いな、とかも思いました。

*2:暫定テストで

*3:あとは単純に、良いスコアが出たのが嬉しくて何か書きたくなったというのもあります。

*4:暫定テスト順位を基準に見てます

*5:計測コスト削減のため

*6:ID末尾を迎えたら先頭に戻ってループする

*7:51:40~ あたり

*8:100ケースしか試していないので、たまたまそうだっただけかもしれないです。

*9:37:20~ あたり

*10:横->縦->横 でなく、横->縦 で終える。

*11:手元で見た感じ、Sが大きいケースで計測コストが上がっている傾向があるように見えました（100ケースしか試してないですが）。

*12:緩やかかつ範囲を広くするイメージ。

*13:暫定テストのスコアを指標にチューニングした感はあるので、本番テストの順位はこれより低い気がします。

*14:小並感

*15:ちなみにコンテスト時の暫定テスト順位は134位でした。

AtCoder Heuristic Contest 022 ~Exploring Another Space~ 参加記

RECRUIT 日本橋ハーフマラソン 2023夏（AHC022）に参加して、146位/1,070人 でした。

解法や所感について書いていきます。

解法

大筋

上図のように盤面を均等に4分割し、温度は２値だけ使って、右下のエリアの温度だけを高くした配置をしました。
こうすることで、x軸y軸が0の部分の切れ目までの距離を二分探索っぽく特定できるようにして、計測回数をある程度少なく抑えるようにしました。

次の節からもう少し詳しく書いていきます。

配置

盤面を均等に4分割し、右下のエリアの温度だけを高くした配置をします。
奇数長盤面の場合は、赤側の一辺の長さを l/2 + 1 としています。

温度差は S の大きさと見合わせながら決めています。後ほどもう少し詳しく記載します。

推定手順

軸それぞれで独立に、0までの距離を求める方針になります。

最初に移動無しで計測して、出口位置が赤か白かを特定します。

出口位置が赤だった場合の、x=0までの距離を求める手順が以下になります。

  1. (0, -l/2) *1を計測する。基本的には白になるので、その場合２に進みます。特殊ケースである赤の場合の対応は右の注釈に書きました*2。
  2. (-l, -l/2] の区間のどこかが x=0 であることが確定しており、かつ単調非増加であるので、二分探索の要領で x=0 の位置を割り出す。

y軸についても同様の手順を行えば、出口の座標が割り出せます。

初期位置が白だった場合は、まず (+l/2, 0) と (0, +l/2) の計測結果を見ることで、出口がx軸y軸それぞれで l/2 以下の位置にあるかどうかを確認します。
l/2 以下に居ないなら上記の手順１から、居るなら手順２から操作を行い、座標を特定する。その際、探索範囲に赤エリアを含めるために、確認対象でない方の軸を l/2 ずらす必要があります。

温度差と計測確度の設定

信頼区間4.1σにして、計測が間に合う範囲でできるだけ白と赤の温度差を小さくしました。
配置コストが計測コストを下回れる場合は、配置コストと計測コストが近い値になるラインを狙って設定しました。
逆に白をP=0、赤をP=1,000としても計測が間に合わない場合は、信頼区間を最悪3.8σまで落としました。

精度はどうか

実測して見てみました。seed 0~199 の実行結果を確認したところ、

  • 誤回答数０が175ケース
  • 最大誤回答数が３で２ケース

といった感じでした*3。
概ね正解できるし、外してもまともに点数が取れるラインには収まる、くらいな感じといったところでしょうか。

その他工夫

  • 計測回数を抑えるために、計測で端値*4を引いたら標準偏差分はみ出るように値を加えた*5。
  • 二分探索チックな操作をするパートで、絞り込んだ範囲に出口が１つしかない場合は、その時点で確定して計測を打ち切った。

提出コード

Submission #44799051 - RECRUIT Nihonbashi Half Marathon 2023 Summer（AtCoder Heuristic Contest 022）

感想

期間後半くらいに入るまで、Sが大きいケースで１点しか取れない状態が続いていて、中々苦しいコンテストでした。一方である程度点数が取れるようになってからは、追加で色々と試したいことが思い浮かんで、かなり楽しめました。

知見のほとんど無い推論系問題*6でこの順位取れたのはまあ頑張った方ではないかな、と思っている一方で、そんなこと言ってないでちゃんと推論系の知識身につけないと不味いよなって気持ちになりました。コンテスト後のTLを眺めていても、知識不足で何を言っているのか分からないことが多かったですし。。 インタラクティブ問題は概ね推論とセットみたいなところがあるはずなので、AHCを戦っていくなら避けられないだろうなとかを思っています。

とりあえず上位の解法を見つつ、今回の復習を頑張ろうと思います。

追記

2023/09/03
統計・推定解法について扱った復習記事を書きました。

gobi-tk.hatenablog.com

*1:問題文に沿って、計測座標は (Y, X) で表記

*2:盤面の長さが奇数かつ出口点の配置が右端か下端の場合のみ、赤になります。この場合は、その時点で -(l-1) が軸0で確定します。

*3:記載した解法以外の細かい工夫も入ってるので、参考値です。

*4:0か1,000

*5:例えば標準偏差400で、Pの２値を200と800に設定していた場合に1,000を引いたら、( 1,000+(400-200) ) の1,200が計測値として得られた扱いとした。

*6:保有知識の内で今回使えたのは、正規分布の区間推定の信頼区間の式くらいでした..