AHC024解法紹介 〜曲率の離散類似による連結判定〜

問題

A - Topological Map

 

コンテスト中の方針

以下の焼きなまし(もどき)

  • 近傍
    • 1点を隣の色で塗る
    • 十字で2マス同時に動かす
  • 評価関数:生スコアを使い、以下の値でタイブレークを行う*1
    • 境界線の長さの和
      • 境界線が短い方が全体的にきれいなので小さくしやすそう
    • 各タイルのサイズの2乗和
      • 中央のタイルが大きいままになりがちなので、タイルの大きさを均したい
  • 温度:スコアが悪化しても確率p=50.0%で受理する。25,000回のイテレーションごとにpを0.1%小さくする*2

曲率の離散類似による連結判定

上の方針の実装で主に問題となるのは各タイルの連結性の判定である。wataさんの解説では周囲の3x3だけを見て簡易的に判定しており、shun_PIさんの延長戦解法では5x5を見ることでさらにスコアをあげている:

しゅんぴー(Shun_PI) on X: "関節点判定を5*5にしたら100点上がった(24ビットメモ化)" / X

ここでは、別の判定方法を紹介する。以下の値をそれぞれの頂点の周りでカウントして和をとることで概ね連結性に対応する値が得られる。(1点更新ではその周りの4頂点についてのみこの値を計算し直せば良い、実際には周囲の3x3マスの情報をキーとして差分を前計算できる)

曲率の離散類似

イメージとしてはタイルの縁を反時計回りになぞったときに左に何回曲がったかを数えており、オイラー標数に対応する。タイルに空いている穴の数が変わらない限りこの値を連結性の判定に用いることができ、今回はタイル間の接続判定が保存されるので穴の数は変わらない。というのは間違いで、以下の図右のようなものを穴と認識できないので以下の遷移をrejectしてしまう。

今回の入力ではそれぞれのタイルの穴の数は少ない(多分たかだか2つくらい?)ので、個別に対処すれば局所的な更新だけで連結性判定が完全にできるはず

他の上位解法のまとめ

上位解法というか、AHC024についての言及で気になったものをまとめました。

あまり上手く理由づけできないが、スコアが離散的すぎて焼きなましの終盤で登り切らないとその周辺の解の良さがわかりづらい、みたいなことかもしれない

詳細はよくわかってないが、延長戦1位解法なのですごい。ランダムウォークが無駄かどうかを事前に把握することは本当に可能なのかな・・・

延長戦をした感じでは、焼きなましの試行回数が十分でないとこの近傍を加えてもあんまりスコア増えなかったけど、ある程度高速化して試行回数が増えるとそれなりに効果ありそう

延長戦解法

以下の焼きなまし

  • 近傍
    • 1点を隣の色で塗る
    • 十字で2マス同時に動かす、連鎖させる
    • 十字の回転
  • 評価関数:生スコア
  • 温度:普通の焼きなまし

連結性の判定は上で解説した方針で穴が1つの場合だけ(正確には、穴あきのタイルそれぞれについて単色の穴を1つまで)個別に対応するようにした。

また、実装をしなおして、諸々高速化した。受理される率が低かったので、隣接する2マスで色が異なるものの集合を管理するようにしたらスコアがかなり改善した。

40M~50Mくらい試行して、受理されるのは4Mくらい

再延長戦

実は最近ALGO ARTISでアルバイトを始めました。(今のところAHCの復習しかしてません / この記事も部分的にはsupported by AAです)この記事の内容を社内で発表したところ、時間短くして複数回実行みたいにした方が良いのでは?というアドバイスをいただいて、そのように書き直したら100点くらい上がりました。

TLギリギリまで使ったりいらないデバッグ出力消したりしたら延長戦1位まで46点差まで迫りましたが、少し届きませんでした。熱烈高速化すれば抜けるくらいの差だと思いますが、1位の点数も高速化で伸ばす余地はあるはずなのでここでやめておきます・・・

コンパイラ変えたら少し速くなるよと教えていただいてClangのC++23にしたら25点上がりました。ここでやめておきます・・・

まとめ

  • (今回は)細かい工夫とかせずに焼きなましを信じて高速化するべきだったかも?
  • オイラー標数考えて連結性判定するのはピッタリハマる問題もあるかもしれない(だいたいその場合は3x3での近似判定も使えそうだけど・・・)
  • ちまちま書き換えて高速化するよりも、受理率あげるのは大事かもしれない

*1:どちらを使うかは10,000回ごとに切り替える

*2:特に意味はなくて、焼きなましを実装するのが面倒だった

村上宗隆を全打席敬遠すべきか

村上宗隆を全打席敬遠すべきかをOPSの観点から考察します。

OPSの定義

OPSとは長打率出塁率の和で表されるセイバーメトリクスです。

簡単のため打撃結果として安打(二塁打三塁打本塁打を含む)・四球・凡退のみを考えることとします。さらに、打率、長打率、四球率をそれぞれ  \alpha \beta \gamma とおきます。このとき、出塁率 \gamma+(1-\gamma)\alpha となるので、OPSは以下の式で定義されます。

\displaystyle{ \text{OPS}=\text{OPS}(\alpha,\beta,\gamma)=\beta+\gamma+(1-\gamma)\alpha \tag{*} }

OPSの問題点

上の定義式(*)はOPSの本来の定義とは少し異なるところがあります。本来、四球率がちょうど1となるとき、つまり、打数が0になるときには長打率が定義できないのでOPSも定義できないはずです。(*)の定義式は 0 \leq \gamma \lt 1の範囲では通常のOPSを表しており、 \gamma=1では \gamma \to 1-0としたときの極限の値をOPSの定義として採用していることになります。

これは一見自然な拡張ですが、 \text{OPS}(\alpha,\beta,\gamma=1)=1+\beta となっており、全打席敬遠されたときのOPSが敬遠されなかった場合に期待できる長打率に依存しておりやや不自然です。また、

\displaystyle{ \frac{\partial}{\partial \gamma}\text{OPS}(\alpha,\beta,\gamma)=1-\alpha }

となっているので、打率がちょうど1のとき以外は全打席敬遠するべきではないという結論になり面白くもありません。

いずれにせよ、村上のような尋常ではない強打者に対して、全打席敬遠という非常識な戦略を考える際にOPSの定義をそのまま用いるのはよくなさそうです。

modified OPS

OPSの問題点は打席数に占める打数の割合( 1-\gamma)が小さくなったときに相変わらず長打率の影響を大きく受けることにあります。これを改善するためにパラメータ  m ( 0 \lt m \lt 1) を導入し、modified OPSを以下のように定義します。

\displaystyle{ m\text{-OPS}(\alpha,\beta,\gamma)=(1-\gamma)^m\beta+\gamma+(1-\gamma)\alpha }

日本語で書くと次のようになります。

\displaystyle{ m\text{-OPS}=\left(\frac{\text{打数}}{\text{打席数}}\right)^m \times \text{長打率} + \text{出塁率} }

 0 \lt m \lt 1 という範囲は若干恣意的ですが、評価関数の満たすべき公理を適当に定めてあげれば正当化できるはずです。また、modified OPSと通常のOPSの間には以下の関係があります。

\displaystyle{ \gamma \ne 1 \Rightarrow \text{OPS}(\alpha,\beta,\gamma)=\lim _{m \to +0} m\text{-OPS}(\alpha,\beta,\gamma) }

解くべき問題とその答え

問題設定は次のように書けます。

守備側は四球率を(0以上1以下の範囲で)好きに選ぶことができる。この選択が打率・長打率に影響を与えないとき、 m-OPSを最小にするためには四球率をどのように選べば良いか?

解答は次のようになります。 m-OPSの  \gamma による2階微分は( 0 \leq \gamma \lt 1 の範囲で)

\displaystyle{ \frac{\partial^2}{\partial \gamma ^2}m\text{-OPS}(\alpha,\beta,\gamma)=m(m-1)(1-\gamma)^{(m-2)}\beta \lt 0 }

となるので、 m-OPS \gamma について上に凸な関数となっています。( m を固定した場合には  \gamma=1 で連続であることに注意。)求めたいのは最小値だったので、範囲の両端を比較して小さい方を採用すれば良いです。 \gamma=0,1 のときの  m-OPSを計算すると

\displaystyle{ m\text{-OPS}(\alpha,\beta,0) =\beta+\alpha,\quad m\text{-OPS}(\alpha,\beta,1)=1 }

となるので、 \gamma=1 つまり全打席敬遠のときに m-OPSが最小となる条件は  \beta+\alpha \geq 1 です。

結論:村上宗隆を全打席敬遠すべきか

以上の議論より、全打席敬遠という戦略を採用する条件は「打率と長打率の和が1以上」となります。村上が5打席連続本塁打(の4,5本目)を放った中日戦の前の成績を確認すると

 打率:.316

長打率:.699

となるので、その和は1.015となり、わずかながら1を上回ります。したがって、「村上宗隆は全打席敬遠すべき」という結論になります。

おまけ:過去の打者について

昨年のセ・パ両リーグの「打率+長打率」上位3人は以下の通りで、1.000を超えている打者はいません。

セ・リーグ鈴木誠也(0.956)牧秀悟(0.848)村上宗隆(0.844)

パ・リーグ吉田正尚(0.902)杉本裕太郎(0.853)柳田 悠岐(0.841)

過去には王貞治バレンティンなどが1.000を超えてシーズンを終了しているようです。すべてのデータは確認できていませんが、1973年に王貞治が記録した1.110(打率 .355 長打率 .755)が歴代最高なのではないかと思います。

@noimi_kyoproさんから指摘してもらいましたが、1985年には落合博満が0.367+0.763=1.130を、1986年にはバースが0.389+0.777=1.166を記録しているそうです。

 

THIRD プログラミングコンテスト 2021 (AtCoder Heuristic Contest 007)参加記

THIRD プログラミングコンテスト 2021 (AtCoder Heuristic Contest 007)に参加して、優勝しました。

 

問題

A - Online MST

 

解法

辺が与えられるたび、今の辺を使わない場合に代わりに使うことになる辺の長さの期待値をモンテカルロ法で求めます。

具体的には、今の辺は使わないと仮定し、まだ長さのわからない各辺の長さを d _ i \leq l _ i \leq 3d _ iの範囲で一様にランダムに決め、クラスカル法によって最小全域木を求めることを考えます。今の辺の両端点が初めて連結になるときの、追加した辺の長さの平均値を求めます。

代わりに使うことになる辺の長さの期待値が今の辺の長さの0.95倍以上となるときに今の辺を採用し、そうでない場合は採用しません。

コード:Submission #27880973 - THIRD PROGRAMMING CONTEST 2021 (AtCoder Heuristic Contest 007)

 

解説(なぜ0.95倍するのか)

 iを採用するか否かでスコアに影響するのは、 u _ i v _ iを結ぶパス上の最長の辺の長さの分だと仮定します。辺 iを採用した場合のこの値は l _ iですが、辺 iを採用しない場合のこの値は厳密には計算できません。(その後の解答プログラムの挙動に依存するため。)その代わりにすべての辺の長さが分かっているとして最小全域木を求めてその際の値を使っていますが、これは実際に達成できる値よりも小さくなっているはずなので、前者を0.95倍して調整します。(0.95という値はいろいろ試して決めるほかないです。)

 

細かい工夫

辺の長さは高々 2400 \sqrt {2}で抑えられ、実際にはグラフの作り方からもっと小さくなるので、クラスカル法で辺をソートするする際にはバケットソートすると速くて試行回数が増やせます。

 

延長戦

モンテカルロ法をする際に範囲を少し小さくとるとスコアが改善するという話がありました。

参照:

 

試してみるとこの解法でもスコアが良くなりました。

(14241733941->14243380547)

コード:Submission #27894297 - THIRD PROGRAMMING CONTEST 2021 (AtCoder Heuristic Contest 007)

 

正確なことはわかりませんが、モンテカルロ法をして平均値を求める際には多少分布が歪んでも収束が速い(つまり分散が小さい)方が良いということだと思います。

 

自分語り

こういった記事を書くのは初めてなので簡単に自己紹介をしておきます。

中高生のときは情報オリンピック数学オリンピックに参加していました。JMO、JOIで優勝したこととIMOで銅メダル、IOIで金メダルを獲得したことがあります。

大学に入ってからも競技プログラミングを続けていて、普段はアルゴリズムコンテストに参加しています。ICPCにもUT a.k.a. Isのメンバーとして参加しています。

ヒューリスティックコンテストには2年ちょっと前くらいから参加し始め、2020年5月にあったAsprovaコンテストあたりから熱心に参加するようになりました。

2021年にAHCが始まったときにヒューリスティックコンテストでそれなりに上達することを2021年の目標の一つにしていたので、2021年最後のAHCで優勝できて良かったです。