- 0.はじめに
- 1.問題文を読む
- 2.ビジュアライザを見る
- 3.最初の提出
- 4.考察
- 5.油田の基準の位置（左上）から油田位置を確定する
- 6.占いを使用する
- 7.実装が難しい
- 7.バグらせて全消し（再度考察からスタート）
- 8.どんどん占って油田を見つけたらBFSをする
- 9.全部の油田が見つかったかチェックを入れる
- 10.ビジュアライザを見る
- 11.一定間隔で調べてみる
- 12.グラフと考える（雑談）
- 13.重ね合わせる
- 14.ついにひらめいたかもしれない
- 15.実装
- 16.落ち着いて考察をする
- 17.過去ベストと今の比較
- 18.1000テストケースをまわす
- 19.1行ずつ、1列ずつ占いをする
- 20.5日間ぶりに自己ベストを更新
- 21.終わりに
- 22.最終提出するのを忘れていたので提出します
- 23.最終結果（2024/3/1更新）
- 24.復習
- 25.延長戦100位になりました
0.はじめに
はじめまして、もしくはお久しぶりです。競プロ歴5年目突入のかえでです。
今回は、 THIRD プログラミングコンテスト2023（AtCoder Heuristic Contest 030）に参加しました。開催期間は2024年2月9日(金)19:00から2024年2月19日(月)19:00までの11日間の長期コンテストでした。これまでは土曜始まりの日曜終了が多かったのですが、今年は金曜の夜から月曜の夜までの開催になりました。AWTFのヒューリスティック部門ができたため、海外勢のことを考えての時間変更のようです。
時間が長くなったのはうれしいけれども、月曜日には仕事があります。最終日の月曜日に自分が何を考えているのかは気になります。今回は日曜日までのつもりで参加する予定ですが、次からは有休を取りたいと思うようになるのかもしれません。
さて、今回はどんな問題なのでしょうか。この参加記を読んで私といっしょにヒューリスティック問題を解く楽しみを感じてもらえたらうれしいです。そして、AHCの解説には誰でも解法を載せることができるので、ぜひどんな解き方をしたのか書いてもらえたらうれしいです。
それでは始めましょう。
1.問題文を読む
仕事帰りに問題文を読みました。
- N×Nマスの島がある
- M個の油田がある
- 各油田は連結している
- 1マスを選択するとそのマスが油田かどうか明らかになる（コスト1）
- 2マス以上（ｋマス）を選択するとコストは1/√ｋと低くなるが、事前に与えられたパラメータ を用いて抽出しなおした値となり、正しい情報からずれが生じる。
- 油田のマスを全て当てると終了する。間違っていたときはコスト1を払って継続する。
- 少ないコストで全ての油田マスを当てる
2マス以上選択した場合の占いの値
うーん、2マス以上選択したとき、どのような値が返されるのか、いまいちピンときません。ビジュアライザを見ることにします。
2.ビジュアライザを見る
問題文の「例を見る」からリンク先のビジュアライザを開きます。
ビジュアライザを再生してみると、島を9分割して、最初に1回調べ、その後は1マスずつ順番に調べている様子がわかりました。
Score = 176800000
Cost = 176.800000 (+0.000000)
ということがわかります。
PythonのサンプルコードがついているのでC++に書き直します。seed0を実行してみます。
あれ？ずれている。
問題文をよく読んでいないので何が起こっているのかよくわかっていません。このサンプルコードは正解を出していないコードなのかということだけがわかりました。
問題文中の「ツールで用いられる入出力ファイルの仕様」を読みました。ダウンロードしたseedファイルには追加の情報が与えられていました。
その部分の入力読み込みを書き足します。
今度は正しく正解を出せました。
Score = 225000000
Cost = 225.000000 (+0.000000)
が出るようです。サンプルコードの得点は 225000000、「例を見る」のコードは176800000点だったので、「例を見る」のコードのように分割するだけでも得点が上がりそうです。
現在の時刻は22時30分。順位表を見ると、saharanさんの得点がずば抜けていました。
今サンプルコードを提出すると、13,722,735,956点が出るようです。
とりあえず明日はサンプルコードの改善を行いたいと思います。疲れているので今日はもう寝ることにします。
3.最初の提出
翌日です。2024年2月10日土曜日の夜です。昨晩から腹痛に悩まされ、一日寝込んでいました。食中毒のような気がします。やっと少し体調が良くなってきたので、AHCに取り組むことにしました。順位表を見ます。トップはsimanさん、提出者は497人です。サンプルコードの得点は8,829,947,917にまで下がっています。
サンプルコードをローカル用に書き替えます。サンプルコードを少しだけ改善して、全部の油田が見つかったら終了するようにします。seed0のビジュアライザはこんな感じです。
100テストケースのスコア平均がサンプルコードの88%に減少したので、順位表の相対スコアから推測すると、サンプルコードの提出は8,128,182,231、全部の油田が見つかったら終了するようにすると8,937,279,834になりそうです。
提出します。
思った通りの相対スコアになりました。順位は514人中190位です。まだサンプルコードを提出しただけの人が大半のようです。
4.考察
日曜の朝です。体調もやっと回復したようです。よかった。
さて、今回の問題でいつもと違うことは、途中で何回も答えを出せることです。それも間違えたときのペナルティのコストが1ととても小さい（今は小さいと思っていますが、そのうち大きく感じるようになるのでしょうか）。だから、候補がある程度絞れたら、答えの出力を全通り試してみても良いのではないかと思っています。
今やろうと思っていることは油田の左上のマスを見つけること。
最初にマスが存在する範囲を調べておきます。油田の矩形が大きければ存在する範囲が小さいはずなので、そこの部分を調べていきます。点が見つかったら、油田の相対的な位置を調べて、1だったら合っていそう、0だったらこの油田ではないということがわかるはずです。
1個ずつ油田を決定してあげて、残りの油田の個数が少なくなれば、1個の油田の場所（左上のマス）がわかれば、調べなくても答えとして提出しても当たりそうな気がします。
その前に、ビジュアライザでseedを100個くらい眺めていたら、すかすかだな、と思いました。島の中で何もないところが多くあるので動ける範囲が大きく、自分のやり方が非効率な感じがしました。1マスずつ調べないで、3×3マスを最初に調べるだけでもスコアが良くなりそうだと思います。その場合、占いになって、正確な値ではなくなります。
一度に4マス調べたときと、1度に9マス調べたとき、epsによってどれくらい数値が悪化しそうかを計算してみます。調べるコストは4マスのときは1/√4＝1/2。これに4を掛けてコスト2になるのかな。9マスのときは1/√9＝1/3。コストが3なのかなと思います。
やってみます。ん、違いました。4を掛けたり9を掛ける必要はなく、4マスを調べるコストは1/2、9マスを調べるコストは1/3でした。
え、すごいコストが低い。
epsが小さければ必ず使った方が良さそうです。epsが大きいときが悩ましく見えるのですが、これ、絶対に判別できるやつだと思います。過去のAHCでもっとすごいのがあったので。というわけで使わないとダメそうだなと思います。
正しく使えると良いのですが。
そして今やっと気がついたのですが、ビジュアライザでは占いの結果であるResponseが出ます。9マス調べた結果は0。
おお！
eps0.2のとき、どんな値が出るかを試してみたいと思います。というか、ローカルで計算できるのではという気持ちになってきました。ダウンロードしたseedに、何か補正用の値が入っていた気がしています。
seed11で試します。全部0の7マスを調べると1が出ました。4マス、3マスにすると0と0でした。
ふむ。
適当ですが、epsが0.1までは9マス、それより上は4マス単位で調べてみようかと思います。
5.油田の基準の位置（左上）から油田位置を確定する
まずはローカルで占いの結果を出力する関数を書きます。
…と思ったのですが、左上マスから油田を推測する方を先に書きたいと思います。
盛大にバグらせつつも書きました。提出します。
seed0のビジュアライザはこんな感じです。
やっぱり無駄な0が多いのが気になります。
あと、ここで入力の形式に合わせて左上をiが最小値のときの一番小さいjとします。
6.占いを使用する
4マス占いを入れてみます。responseが0なら調べた（1マスを調べて確定したことと同様に扱う）ことにしてとばすことにします。
提出します。
あれ？
相対スコアの得点も0（表示されず）です。
コードを見直すと、占い部分のクエリの出力を行っていませんでした。
修正します。またepsが0.05以下のときのみにします。今度は良さそうに見えましたが1個TLEしました。それでも相対スコアは提出前の得点7,512,742,471、順位245位から少し上がったようです。相対スコアは8,046,439,861、637人中227位になりました。
ビジュアライザでは占い部分を赤で表示することにしました。現在の状況はこんな感じです。
Score = 49654701
Cost = 49.654701 (+0.000000)
この後はコードの入出力部分が煩雑なのでリファクタリングをしたいと思います。また、占いが間違っていたときにもう一度調べる部分を追加したいと思います。
7.実装が難しい
リファクタリングをしながら思ったのですが、処理が複雑でバグらせやすいなあと思います。やりたいと思っていることになかなかたどり着けません。
油田が重なっているときの処理がうまくいきません。
BFSを使って、周辺の油田を探します。100テストケースでエラーが出なくなったので提出します。結果は50ケース中4WA。絶対スコアは0点です。
それでも相対スコアは提出前の269位、7,337,645,941から699人中263位、7,550,993,446に少しだけ上がりました。
そろそろ0時を過ぎるので寝ようかと思います。その前にもう1回だけ提出したいと思います。
おっと。
続きは明日（厳密には今日）考えたいと思います。
7.バグらせて全消し（再度考察からスタート）
コンテスト4日目、2024年2月12日の朝です。今日は建国記念日の振替休日でお休みです。うれしい。
今日は金曜日
就業後AHC
姿勢は前傾
欲しいのは天啓
バグらせて全消し
祈る入青
さて、これはコンテスト初日の昼に書いたXのポストです。結構リズム良く書けたかなと思っていましたが、まさか本当になるとは。
昨日（厳密には今日）寝ながら考えたのですが、やっぱり自分の解法が問題とマッチしないなあと思いました。同じ形の油田が複数あることや、油田が重なっているところを処理するところが難しいので、1対1の対応をつけるのが難しく感じています。
それよりは油田を見つけた後で「調べた結果が矛盾しないよね」というチェックに使った方が良いように思います。
言いかえると、今回の問題は「適当に調べて見つけたらガンガン掘っていく」ということです。占いのコストが低いこと、間違った答えを提出しても挽回するチャンスがあることなどから、調べていないところを順に隈なく調べていくというのは何か違うなあと思うようになりました。
というわけで、コードをシンプルに書きなおすことにしました。
- 占いは矩形で調べることにして、長方形の頂点のうちの左上と右下の座標を入れると、長方形に含まれる全ての格子点の座標を出力するものにする
- 占いの結果を入れるデータ構造を用意する（推定のしかたがわからないので、あらためてbowwowforeachさんのAHC022のブログを読み直そうと思っています。後からリンクを入れる）
- 占いの結果は重複する範囲に行ってもよい
- 方法
- 面積を半分に割っていき、ある程度油田が含まれる確率が高くなったらそのうちの1マスを油田が出るまで調べる
- 1マスの油田が見つかったら、BFSで1マスずつ周囲を隈なく調べる
- 最初の入力で与えられた油田マスの個数と合っていたら答えとして提出する
- 油田の範囲が足りなかったら最初に戻り、別の場所を調べる
こんな感じでしょうか。再度取り組みたいと思います。
8.どんどん占って油田を見つけたらBFSをする
占いの使い方はあまりわからないのですが、とりあえず、常に半分の面積を調べて、残りは全体から占いの結果を入れるみたいな形で補完していきたいと思います。
（時間経過）
夜です。ブログを書くのを忘れていました。リファクタリングをして、7で書いた解法を実装していました。ほぼ全消し。
かなりきれいなコードになりました。関数名はchatGPTにどんな名前をつけるとよいかを教えてもらいながら書きました。ただ英単語だとピンとこないものがあって、そんなときはローマ字に置きかえました。
（時間経過）
やっと提出する形になりました。
久しぶりに提出します。久しぶりのACです。絶対スコアは7511060615点。相対スコアは7,534,055,086、806人中286位になりました。
絶対スコアはかなり減少しましたが、思ったほど順位は上がりません。提出前は706位だったので、それを思えば元に戻ってよかったと思います。
今のseed0のビジュアライザはこんな感じです。色も変えてみました。
ビジュアライザを見ていて思ったのですが、同じクエリを繰り返しているようです。epsの値が小さいときは結果が変わらなそうなので、同じクエリは省略するようにしたいと思います。あとやっぱりBFSは無駄が多そう？
やっと考察の段階に進めてホッとしました。
祝日だった月曜日もあと1時間で終わります。
9.全部の油田が見つかったかチェックを入れる
火曜日の朝です。お布団に入っても考察が止まらなくてなかなか眠れませんでした。格子状にある一定の間隔で掘ったらどうかとか、ライン上にある一定間隔で占いをして多そうなラインを調べるとか。最初の上端のマスを見つける方法も悪くなかったなあなどと思っているところです。
まずは昨日のコードの無駄な部分、全部見つかったのにまだ掘り続けている箇所があったので修正します。少しスコアが改善したので提出します。
絶対スコアは7134241673になり、少し良くなりました。相対スコアも良くなり、6,436,292,148になりました。順位は提出前の315位から271位に上がりました。提出者は827人にまで増えています。
ところで、昨晩トップに大きな変動が起きました。eijirouさんが提出をして、1位になっています。そして、2位以下と大きくスコアを離しました。すごい。
何が起こっているのだろうと興味津々です。自分もがんばって改善を続けたいと思います。
10.ビジュアライザを見る
ビジュアライザを見ながら考察します。気になったものが見つかったので修正します。
- 最後まで見つからなかったときにまだ調べていない全マスを順に調べるようにしていたが、左上から調べるのではなくランダムに変更した
- 範囲を9マスに絞ったのにマスの候補が0になり、繰り返し同じ範囲の抽出を行っていた（2次元を1次元に変換するときのMAXサイズを間違えていたので修正）
100テストケースを試すと少し良くなっていたので提出します。
結果は絶対スコアは6822011720になりました。相対スコアは6,747,596,612になり、順位は提出前の270位から227位に上がりました。
自分にとってはほんの少しの改善で順位がぐっと上がって驚きました。
そうなんだ…。
相対スコアって未だによくわかりません。
11.一定間隔で調べてみる
余談ですが、この問題を読んだときに頭に浮かんだのは「ホルカ×トルカ」というメダルゲームでした。地下の見えない場所に眠った宝をコインで掘り進めるというゲームなのですが、その中にソナーという発掘サポートアイテムがあり、それを使うとどこに何があるかがわかるという効果があります。このゲームに一時はまっていたのを懐かしく思い出しました。
さて、油田がどこにあるかがわかるに越したことはないのですが、適当に掘ってもビジュアライザを見る限り、まあ見つかるかもといった気がしています。
なので、適当な間隔で、例えば5×5マスに1回中央を掘ってみるといったことをしても良いのではないかと思いました。油田が見つかればそこからBFSをすることにします。
油田の形と重ね合わせる最初の方法はその次に試したいと思います。
3×3と5×5と9×9をやってみましたがあまり変わりません。絶対スコアは少し悪くなっているでしょうか。相対スコアも提出をして確認します。3×3を提出しました。
絶対スコアが少し悪くなり、相対スコアも提出前の243位から249位に若干下がりました。
提出した結果は予想した通りでした。
最初の重ね合わせのアイデアに戻りたいと思います。
左端と上端を見つけることを優先したいのですが、まずは横に1行ずつ見ていきたいと思います。
お風呂で考えていたのですが、周りから詰めていくと良いのかなと思います。上下左右、パズルで枠から埋めるのと同じとでもいえば良いでしょうか。とりあえず最初にやっていた上を合わせるコードを入れるようにしたいと思います。
12.グラフと考える（雑談）
寝ている間（実際はお布団に入ってから眠りにつくまでの時間）の考察です。油田は連結しているのでその形を判別するのにグラフを使えないかなあと思いました。グラフの同型判定のことを思い出しました。ABCに出題された問題があるように思いましたがどの問題だったかを思い出せません。過去のAHCでも同じことを考えたなあと思いブログを見返すとありました。HTTF2023予選（AHC016）です。問題はABC232のC問題です。Nが大きいと難しいようです。Nが8くらいまでならできそう。
ブログを読み返して、この回のAHCは本当に何もできなかったなあと思い返します。何もできないのにひたすら何かをしている姿が自分のことなのに健気で泣きそう。もしAHCを始めたけど全然わからなくてくじけそうな人がいたら読むと励まされるかもしれません。
HACK TO THE FUTURE 2023 予選（AtCoder Heuristic Contest 016）参加記 - 競プロ始めました-kaede2020-
13.重ね合わせる
制限時間は3秒あるので、素直に重ねてみたいと思います。BFSをするときには上下左右に広げますが、それを上と左に限定します。すると左上のマスにたどり着くのではないかと。そこを始点として重ね合わせを行いま
す。
田植え方式で掘っていき、油田に当たっ
たら上と左に進めるだけ進みます。
こんな感じ。
ただ、これはたまたまうまくいっていますが、思っているのと違うなあというのもあり、考え中です。
ただ、この形を見て、別のことを考えました。左はこれまでの自分の方法です。今の左のコストは約93、右のコストは76です。あと8マスを見つけるのにコスト17をかけないで済めば、今より改善できます。これならできるかも。周りの0を掘るのを少しでもやめることができれば。
14.ついにひらめいたかもしれない
重ね合わせるときに何もない状態だと候補が多すぎると思ったので、格子状に穴をあけておくことにしました。すると油田を置く候補がそれぞれ58か所、61か所出てきました。多いなと思います。
あ、と思います。格子状の点を線にした方が良いのかもしれない。
100か所、98か所に増えました。
じゃあこれなら？
格子点と十字のラインを入れます。
48か所と46か所。
斜めはどうだ。90か所と65か所。
どうして候補が減らないのでしょうか。
そう、1があるから動けてしまう。ということで1が出たら隣接する0が出るまで掘りたいなと思います。やっぱり。
お風呂に入ってきたら冷静になりました。候補が54か所って別に多くないな、と。
方針が決まりました。
- 格子点を掘る
- 候補を出す
- 候補は占いをする
- 確率的に油田マスがなさそうなところは候補から外す（この辺は考え中）
- 候補が少ない油田、もしくは見ていないマスが少ないもの、もしくは油田マスが多そうなものから試す（この辺は考え中）
- 実際に掘るとき、同じ番号の油田マスの中でどれから掘るのかも思案中
- 予想が外れたら候補から外す
15.実装
実装してみたら、seed0の油田の置き場所候補がそれぞれ6個、8個でした。
え、これ、多いのから調べたら1回で正解になります。
何だかわくわくしてきました。
残念ですが日付が変わりそうなので続きは明日にします。
と思ったのですが、その後30分程かけてコードを書きました。
油田候補を出して一番予測した油田数が多い置き場所を答えとして出し、ダメだったらランダムで埋めるという内容です。予測が当たった分だけ良いスコアを出せるかなあと考えました。
ドキドキしながらて出します。提出前の順位は284位。相対スコアは4,128,638,132です。提出していない間にだいぶ下がっています。
提出して早々にジャッジ結果がTLEに変わります。TLEが17個出て絶対スコアは0点、相対スコアは704,489,123、915人中744位になりました。思った以上に悪いスコアに残念だなあと思います。
100テストケースの結果もあまりよくなかったのでしょうがありません。
明日もう一度考えたいと思います。今度こそ本当にお休みなさい。
16.落ち着いて考察をする
焦ってはいけないと自分に言い聞かせます。seed0のスコアは予想が当たって27206755点を出すことができていますが、これは判別が容易なseedだからです。1回で当たらなくても、少しずつ掘っていけばよいのです。BFSより良いスコアが出せれば良いのだから。TLEを解消する方法を考えたいと思います。
seed1のビジュアライザを見ると、予測のための占いの回数が多いことに気がつきます。1マスずらすたびに占いをしていたからです。また、油田のサイズが小さいため、占いのコストもかさみます。候補が多いときに占いをするのは効率が悪く感じました。
重ね合わせながら、埋めていくことにしました。
うーん...。
場合分けをしようと思います。
ビジュアライザを見ながら少しずつ修正します。実際に埋めてみる条件をepsによって変えてみました。100テストケースの結果は少し持ち直しました。
提出しますが、まだTLEが3つあり、得点は0点です。サンプルコードの相対スコアは2,293,731,454なので、それよりは良くなっているようです。
Mが2以下のときでepsが0.1以下のときは埋めずに推測をするようにしました。
TLEがまだ2つあり、得点は0です。相対スコアはまた少し伸びました。
そういえば、2があったときの対処をもう少し考えてもよいかもしれません。必ず端なので。
久しぶりにACしました。100テストケースで予測をしていましたが、過去のベストよりはかなり悪いスコアです。
だいぶ良くなりはしたものの、相対スコアを見ても2,51,040,103、957人中460位でした。
過去のベストが今相対スコアでどのくらいかを知りたくなったので、2月13日朝のこれまでのベスト、絶対スコアが6822011720だったコードを出し直してみます。（「10.ビジュアライザを見る」で提出したものです。）
すると、相対スコアは966人中318位でした。やはり今でもこちらの方がだいぶ良いようです。なぜ、これが良いのかを考察して、改善してきたコードと合体させることができるといいなと思います。
17.過去ベストと今の比較
100テストケースで過去のベストと今のスコアを比較しました。一つ気がついたのは、Mが大きいときのテストケースが少ないことです。もう少しテストケースを増やしてみたいと思いますが、Mが大きくなったときのスコアが悪いようです。また、Nが大きいときもスコアが悪くなっていそうです。
考えていて思ったのは、Mが2でepsが小さいときは実際に掘る必要はなくて占いだけで良さそうです。逆にMが大きいときは実際に掘ることが必要になりそうです。
と、そこまで考えて、5×5マスくらいで区切って、その範囲にいくつあるかを占って、25で割った数をそのマスに予測として入れておき、その中の1つを掘って1が出たら残りのマスの予測が下がり、0が出たら残りのマスの予測が上がるみたいな更新を入れていくと良さそうだと思います。ある程度5×5マスの占いが信頼できるくらいまで何度か占っておきたいものです。とりあえずepsを100倍した数にしてみようかと思います。epsが0.01なら1回、0.2なら20回というように。コストはそれぞれ0.2、4かかりますが、そんなに悪くなさそうです。
5×5マスを実装中です。まだ途中なので続きは明日行いたいと思います。今回は本当に悪戦苦闘しています。
18.1000テストケースをまわす
5×5マスの予測はそれほど悪くなかったものの、自己ベストは越えられません。予測が間違っていたときに5×5のマスを掘ってしまうのが致命的です。epsが大きいときに予測のために掘る回数を増やしてみましたが、掘るコストが増えてしまうせいか、結果はよくなりませんでした。
悩みがつきません。
1000テストケースをまわしてみます。思ったよりもスコアがばらつくなあと思いました。100テストケースよりも結果が悪くなっています。
5×5マスの予測を入れた後に3×3マスの中央を試し掘りしてみてあてはまる油田を調べることにしました。その後あてはまる油田がなかった調べて油田が合った場所をBFSし、さらにそれでも見つからなかったときは、全ての油田の場所からBFSをします。それでも見つからなかったら、epsが小さいときは掘っていない場所の中から油田のありそうなところを選んで掘り、それ以外はランダムで掘るようにしました。
100テストケースはやっと自己ベストを更新しました。
ドキドキしながら提出します。
結果は絶対スコアも相対スコアも悪くなりました。相対スコアは提出前の3,936,992,490から3,538,365,904に下がっています。順位も332位から423位に下がりました。
あれ？
でも今回はそこまで悪くないと思っているのですが。得点源になっている箇所が悪化しているのかもしれません。相対スコアの場合、トップと差がつくと自分のスコアがほぼ0になってしまうということは経験済みです。ここは注意深く考えたいと思います。
事前に穴を掘っておくのを5×5マスの中央に変更したら、さらにスコアがよくなりました。これならさすがに提出した結果も良くなるのではないでしょうか。
提出した結果です。
あれ？
絶対スコアは少し良くなりました。それでもベストは越えません。相対スコアは下がりました。
謎は深まるばかりです。
悪化しているのはMが少ないときのようです。Mが小さいときのを気をつけるのと、あとは今思いついた、1行ずつN行、1列ずつN列占いをして、結果をクロスさせて一番油田がありそうなところを調べるということをしてみたいと思います。
と思いましたが、まずは推測を5×5だけでなく、4×4、3×3、2×2まで試したいと思います。
あまりよくなりません。
ここで先ほどの謎が解けました。100テストケースの結果を貼っていたつもりが51テストケースまでの結果までしか貼っていませんでした。
ぬか喜びをしました。5×5で占いをしておき、占いの結果が8割以上油田なら掘ります。また、事前に5×5の中央を掘っておくようにしました。
久しぶりに提出をしますが、25個がTLEで得点が0。相対スコアもガクンと落ちてしまいました。
今やっている方法はこんな感じです。
1000テストケースを試しましたが過去のベストを超えられませんでした。
うーん、難しい。疲れてきたので一旦休憩します。
もう一回過去のベストからやり直したいと思います。
19.1行ずつ、1列ずつ占いをする
2024年2月18日の朝です。明日が最終日になりますが月曜日。今日がコンテストに時間を費やせる最後の日です。それでもいつもと違って夜まで時間があるので、精神的には少し楽かもしれません。
昨日寝ながら考えたのですが、今日は1行ずつ、1列ずつ占いをして、結果をクロスして油田の場所を予測したいと思います。
余談ですが、昨夜はABC341に午後9時から参加していたのですが、B問題の意味が何回読んでもわからなくて、ACしたのは67分後。途中でC問題を解いていたのですが、それもバグがみつからず右往左往。B問題をACしたらC問題のバグも見つかり、なんとか3完できました。D問題も誤読していたので、やっぱり睡眠不足と疲れがたまっていたのかもしれません。今日もうまくいかないと感じたときは早めにお昼寝をしたいと思います。
1行ずつ、1列ずつ占いをした結果です。行の結果と列の結果を掛け算しました。seed0、seed2ともに右の正解と比べても悪くなさそうです。
結果の良い場所から掘り進めてみます。
ああ、そうだ、補正するのを忘れていました。全部を足すと油田マスの数になるように調整します。うん、よさそう。
ビジュアライザを見ていると、うまくいっていないseed19を見つけました。
最初の予測だとうまくいっていない箇所があるので、1マスずつ調べたあとに予測を更新したいと思います。そして調べていないマスの中で予測値が一番大きいものを調べていくことにします。油田だったらBFSをします。
書き終えたので提出します。2個TLEしました。相対スコアは3,354,956,697、1066人中461位でした。
BFSから重ね合わせた差分が小さいものを調べるように変更します。
重ね合わせにしたものの、一部は良くなりましたが、一部は悪くなりました。
20.5日間ぶりに自己ベストを更新
油田の数が2個のときだけ重ね合わせをするようにして、それ以外はこれまでの過去のベストの二分探索法で行うようにします。
書き終えたので提出すると、2月13日に出したベストのスコアをやっとほんの少しだけですが更新することができました。絶対スコアは6798256874になり、相対スコアは提出前の480位から403位に上がりました。
M=2のとき、合っているとわかった段階で埋めるのをやめても良いかもしれません。また最初の方針をもう一度使うことにしたので推測の更新をきちんと入れたいと思います。
M=2のとき、1個目が確定し、2個目は合っているとわかった段階でやめました。100テストケースの結果が少しよくなったので提出します。絶対スコアは少しだけ悪くなり、相対スコアは411位から408位に少しだけよくなりました。
1000テストケースをまわしたら、5個ほどUnexpected EOFが出ていて得点が0になっていました。見つからなかったときに今は何種類かの解法を加えていて、ランダムに掘って見つけた後に答えの出力をしていないものがあったので修正しましました。
21.終わりに
コンテスト最終日、2024年2月19日の朝です。今日は仕事なので、今回のコンテストはこれで終了です。現在の順位表の1位はeijirouさんです。
私の現在の順位は439位です。相対スコアがトップの十分の一もありません。難しかった。10日間のコンテストでしたが、あまり改善できなかったなあと思います。どの範囲を推定するかとか一致の判定とか、もっと良い方法がありそうに思います。推定の更新の方法もきちんと勉強しないとなあと思いました。油田は中心から調べ始めることが多かったので、油田の形の左上の位置を見つける良い方法を思いつくことができませんでした。重なっているというのが掘れば2以上の値だとわかるのですが、そこの部分が自分の中で難しく感じました。
それでも取り組み始めるとあっという間に時間が過ぎてしまうという、とても幸せな時間を過ごすことができました。ああでもない、こうでもないと考えている時間はとても楽しいものです。今回も入青はダメかもしれませんが次こそは良い結果を出せますように。
19時にコンテストが終わった後に多くの人が解法をXにポストしてくれることでしょう。他の人の解法を聞くのが楽しみです。そしてコンテストが終わったら、午後10時から感想会スペースを開く予定です。ぜひお気軽に参加してもらえればなあと思っています。
AWTFの対象になったことも関係しているのでしょうか。コンテストの参加者が増えているように思います。もっと増えるといいなあ。そしてまだ参加したことがないけど興味を持っていただけた方がいたら、次はぜひ一緒にコンテストに参加しましょう。一方、すでにコンテストに参加している方はぜひ次のコンテストでも競い合いましょう。
22.最終提出するのを忘れていたので提出します
Mが24より大きいときの分割推測で5×5マスを全て埋めていたので16マス以上のときはやめることにしました。100テストケースの結果はそんなに変わらなかったので提出をします。するとTLEが2個でました。しかし相対スコアは3,505,185,130に上がりました。順位も提出前の445位から384位に上がりました。
全部でACを取るコードよりも、いくつかのテストケースで少しでも良いスコアが出ることの方が相対スコアを上げるのには必要なのかもしれません。ということで、WAが出たままですが、これを最終提出としたいと思います。
と思ったのですが、念のために1000テストケースをまわすと、大量のTLEが発生しました。空っぽの答えを提出していることがあるようです。修正して今度こそ最終提出をします。
23.最終結果（2024/3/1更新）
更新が遅くなりました。システムテストの結果はシステムテスト前の404位から399位に上がりました。3000テストケースは全てACしていました。
解説にリンクが貼ってある詳細順位表（AHC Standings）を見ると私の場合、Mが大きいときが得点源となっていたのですが、実はMが大きいときというのはテストケースの中でごくわずかでした。本当はMが小さいときのスコアが少しでも良くなるようにがんばらなければいけなかったのでした。
成績は振るわなかったものの、ヒューリスティックのレーティングが2上がったことで1600になりました。ついに青になりました！うれしい。
24.復習
その後、推定系の問題が苦手なので復習をしています。ベイズ推定と相互情報量の勉強をしているところです。本当は復習が終わったらブログを更新しようと思っていたのですが、思った以上に時間がかかっているので先に更新をすることにしました。
M=2ののとき限定で占うマスの集合を相互情報量/costが最大になるような山登りを書こうと思っているのですが、うまくいかずにいます。これができるとコストが1を切ることができます。
参考にしているのがAHCラジオとあぷりしあさんの記事です。他の方のブログを読んだり、ベイズ推定の本を読んだりもしています。うまくできたらまた更新したいと思います。
25.延長戦100位になりました
M=2のときのテストケースが50個中5個あります。そのうち4個ACしていて、1個はTLEしたままです。それでも相対スコアは倍になりました。
「占うマスの集合を相互情報量/costが最大になるような山登り」がM=2でも実行時間3秒におさめるのが難しくて、悩みました。あぷりしあさんの2番目の記事のコードも実行時間が制限時間には間に合わない様子。しかし、どこを改良すればわかりませんでした。
全部の候補を見ていると時間が足りないので、占うマスを最初はランダムに選び、1回0.3sで山登りを区切るといったことをしました。最初は乱択で占うマスを選んだベイズ推定から、相互情報量/costが最大になる占いマスの集合に移行していきます。占うマスを乱択で選ぶだけよりもさらにスコアが伸びました。
ベイズ推定も相互情報量もまだ理解できていないところがたくさんあるのですが、動くコードが書けてよかったなぁと思います。記事を書いてくれたあぷりしあさんには感謝しかありません。
それでは次の復習（第一回マスターズ選手権-予選-）へと進みたいと思います。
