AHC024解法紹介 〜曲率の離散類似による連結判定〜
問題
コンテスト中の方針
以下の焼きなまし(もどき)
- 近傍
- 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についての言及で気になったものをまとめました。
#AHC024
— eijirou (@eijirou_kyopro) 2023年9月27日
延長戦337,025点
- 遷移は1or2マスの変更
- 生スコアを局所改善
-「普通の焼きなまし」を「高温と低温を繰り返す焼きなまし」にしたら300点ぐらい上がった(山登り+kickのほうがいいかも)
- 二点スタートで少しよくなった
- 行・列の削除を入れてもよくならなかった
あまり上手く理由づけできないが、スコアが離散的すぎて焼きなましの終盤で登り切らないとその周辺の解の良さがわかりづらい、みたいなことかもしれない
- dfsで有効なn点changeを求める
— _____ (@rho__o) 2023年9月27日
- 無駄なランダムウォークを防ぐために新たに有効になった近傍をsetに突っ込んで次の近傍はそのsetから取り出す
などを実装すると337,683が出るらしいです
n点changeは15M回くらい試せている(失敗確率は75%くらい)
詳細はよくわかってないが、延長戦1位解法なのですごい。ランダムウォークが無駄かどうかを事前に把握することは本当に可能なのかな・・・
外出中ふと思ったのですが、AHC024の1~2点変更する遷移って基本十字型を回転させることはできないから、左の解から右の解に到達できなかったりしませんか?
— MON.T+α (@montplusa) 2023年9月27日
(このポイントがスコアにおいて致命的になるかはともかくとして・・・) pic.twitter.com/dN46LsF51w
延長戦をした感じでは、焼きなましの試行回数が十分でないとこの近傍を加えてもあんまりスコア増えなかったけど、ある程度高速化して試行回数が増えるとそれなりに効果ありそう
延長戦解法
以下の焼きなまし
- 近傍
- 1点を隣の色で塗る
- 十字で2マス同時に動かす、連鎖させる
- 十字の回転
- 評価関数:生スコア
- 温度:普通の焼きなまし
連結性の判定は上で解説した方針で穴が1つの場合だけ(正確には、穴あきのタイルそれぞれについて単色の穴を1つまで)個別に対応するようにした。
また、実装をしなおして、諸々高速化した。受理される率が低かったので、隣接する2マスで色が異なるものの集合を管理するようにしたらスコアがかなり改善した。
40M~50Mくらい試行して、受理されるのは4Mくらい
再延長戦
実は最近ALGO ARTISでアルバイトを始めました。(今のところAHCの復習しかしてません / この記事も部分的にはsupported by AAです)この記事の内容を社内で発表したところ、時間短くして複数回実行みたいにした方が良いのでは?というアドバイスをいただいて、そのように書き直したら100点くらい上がりました。
TLギリギリまで使ったりいらないデバッグ出力消したりしたら延長戦1位まで46点差まで迫りましたが、少し届きませんでした。熱烈高速化すれば抜けるくらいの差だと思いますが、1位の点数も高速化で伸ばす余地はあるはずなのでここでやめておきます・・・
コンパイラ変えたら少し速くなるよと教えていただいてClangのC++23にしたら25点上がりました。ここでやめておきます・・・
まとめ
村上宗隆を全打席敬遠すべきか
村上宗隆を全打席敬遠すべきかをOPSの観点から考察します。
OPSの定義
OPSとは長打率と出塁率の和で表されるセイバーメトリクスです。
簡単のため打撃結果として安打(二塁打・三塁打・本塁打を含む)・四球・凡退のみを考えることとします。さらに、打率、長打率、四球率をそれぞれ 、 、 とおきます。このとき、出塁率は となるので、OPSは以下の式で定義されます。
OPSの問題点
上の定義式(*)はOPSの本来の定義とは少し異なるところがあります。本来、四球率がちょうど1となるとき、つまり、打数が0になるときには長打率が定義できないのでOPSも定義できないはずです。(*)の定義式はの範囲では通常のOPSを表しており、ではとしたときの極限の値をOPSの定義として採用していることになります。
これは一見自然な拡張ですが、 となっており、全打席敬遠されたときのOPSが敬遠されなかった場合に期待できる長打率に依存しておりやや不自然です。また、
となっているので、打率がちょうど1のとき以外は全打席敬遠するべきではないという結論になり面白くもありません。
いずれにせよ、村上のような尋常ではない強打者に対して、全打席敬遠という非常識な戦略を考える際にOPSの定義をそのまま用いるのはよくなさそうです。
modified OPS
OPSの問題点は打席数に占める打数の割合()が小さくなったときに相変わらず長打率の影響を大きく受けることにあります。これを改善するためにパラメータ を導入し、modified OPSを以下のように定義します。
日本語で書くと次のようになります。
という範囲は若干恣意的ですが、評価関数の満たすべき公理を適当に定めてあげれば正当化できるはずです。また、modified OPSと通常のOPSの間には以下の関係があります。
解くべき問題とその答え
問題設定は次のように書けます。
解答は次のようになります。-OPSの による2階微分は( の範囲で)
となるので、-OPSは について上に凸な関数となっています。( を固定した場合には で連続であることに注意。)求めたいのは最小値だったので、範囲の両端を比較して小さい方を採用すれば良いです。 のときの -OPSを計算すると
となるので、 つまり全打席敬遠のときに-OPSが最小となる条件は です。
結論:村上宗隆を全打席敬遠すべきか
以上の議論より、全打席敬遠という戦略を採用する条件は「打率と長打率の和が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を記録しているそうです。
多分落合の 1985 の 打率 .367 長打率 .763 の和 1.130 が最大な気がします(?)
— のいみ (@noimi_kyopro) 2022年8月2日
バースの 1986 の .389 + .777 = 1.166 の方が高かったです…
— のいみ (@noimi_kyopro) 2022年8月2日
THIRD プログラミングコンテスト 2021 (AtCoder Heuristic Contest 007)参加記
THIRD プログラミングコンテスト 2021 (AtCoder Heuristic Contest 007)に参加して、優勝しました。
問題
解法
辺が与えられるたび、今の辺を使わない場合に代わりに使うことになる辺の長さの期待値をモンテカルロ法で求めます。
具体的には、今の辺は使わないと仮定し、まだ長さのわからない各辺の長さをの範囲で一様にランダムに決め、クラスカル法によって最小全域木を求めることを考えます。今の辺の両端点が初めて連結になるときの、追加した辺の長さの平均値を求めます。
代わりに使うことになる辺の長さの期待値が今の辺の長さの0.95倍以上となるときに今の辺を採用し、そうでない場合は採用しません。
コード:Submission #27880973 - THIRD PROGRAMMING CONTEST 2021 (AtCoder Heuristic Contest 007)
解説(なぜ0.95倍するのか)
辺を採用するか否かでスコアに影響するのは、とを結ぶパス上の最長の辺の長さの分だと仮定します。辺を採用した場合のこの値はですが、辺を採用しない場合のこの値は厳密には計算できません。(その後の解答プログラムの挙動に依存するため。)その代わりにすべての辺の長さが分かっているとして最小全域木を求めてその際の値を使っていますが、これは実際に達成できる値よりも小さくなっているはずなので、前者を0.95倍して調整します。(0.95という値はいろいろ試して決めるほかないです。)
細かい工夫
辺の長さは高々で抑えられ、実際にはグラフの作り方からもっと小さくなるので、クラスカル法で辺をソートするする際にはバケットソートすると速くて試行回数が増やせます。
延長戦
モンテカルロ法をする際に範囲を少し小さくとるとスコアが改善するという話がありました。
参照:
#AHC007
— bin (@5bin101) 2021年12月12日
14,239,593,099(3位!!)
まだ使用を確定させていない辺の長さを乱数で変化させて、
長さが判明した辺を使うかをx回やって多数決で決める。
xは、i(<M/2)ターン目なら361、そうでないなら701。
乱数で変化させる際、rand(1.13d,2.87d)にした
(これが1と3の場合、14.18Gになる)
試してみるとこの解法でもスコアが良くなりました。
(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で優勝できて良かったです。