- 0.はじめに
- 1.問題文を読んでサンプルコードを提出する
- 2.同じ場所で何回も測定を行い、平均を取ってみる
- 3.ランダムからの山登り
- 4.温度設定を変える
- 5.測定する場所を広げる
- 6.測定回数の調整
- 7.ついにひらめいた！
- 8.9マスで一意に定める形と1,0の判定方法を考える
- 9.予測判定に確率を使用する
- 10.新しいアイデア
- 11.現状分析
- 12.中央1点に温度設定をする
- 13.コンテスト終了まで残り2日
- 14.コンテスト最終日
- 15.終わりに
- 16.最終結果（2023年8月21日更新）
0.はじめに
はじめまして、もしくはお久しぶりです、競プロ歴3年半のかえでです。
今回は、RECRUIT 日本橋ハーフマラソン 2023夏（AtCoder Heuristic Contest 022）に参加しました。開催期間は2023年8月11日(金)12:00から2023年8月20日(日)19:00までの10日間。2週間弱の長期コンテストです。
この参加記は、ヒューリスティック・コンテストをもっと盛り上げたいという思いから書いています。上位にはなかなか行けず特別なことはできないのですが、お会いした方からブログを読みましたと声をかけていただくこともあり、うれしく思っています。役に立つものではないかもしれませんが、これからも続けていきたいと思っています。ぜひ軽い読み物として楽しんでもらえたらと思います。そして、AtCoderのAHCの解説には誰でも投稿することができるので、たくさんの方の解法が記事となって残ることを望んでいます。みなさんもぜひコンテストに参加して自分の解法を投稿してくださいね。
それでは、今回もがんばっていきましょう。
1.問題文を読んでサンプルコードを提出する
問題文を読んでみました。文章が長いので、まだよく理解できていません。ちょっとずつ整理していければと思います。
・自分たちの世界にN個の出口セルがあり、Another SpaceにもワームホールがN個ある。1対1対応だが、どこにつながっているのかが不明。求められているのは、その対応を調べて答えること。
・温度設定と距離の話。ここはよくわからず。
・測定誤差の話。ここもよくわからず。
・気温を測定するにはエネルギーが必要だが、それを最小にしたい。
・スコアの計算。ここもよくわからず。
というわけで、少しずつ何が問題でどうやって解決していたら良いかを考えていきたいと思います。
サンプルコードをダウンロードし、ローカル版テスタ・ビジュアライザ・入力ジェネレータもダウンロードします。inフォルダ内の0000.txtを使ってサンプルコードの出力をout0000.txtに書き出します。
自分はWSLを使用しているので、こんな感じ。
g++ sample_submission.cpp
./a.out <0000.txt >out0000.txt
out0000.txtに出力された値を、Web版ビジュアライザに貼り付けます。
seed0のビジュアライザは下図のようになりました。見方はよくわかっていませんが、右側の赤と黄緑に色づけられた表を見た感じ、推測が的中したのは1個だったのかなぁ。（追記：ローカルジャッジ用の読み込みをしていないので、実際に提出したときとは異なる出力が出ています。）
サンプルコードをそのまま提出してみます。
順位表を見ると、相対スコアは26,084,745、提出者205人中ちょうど100位でした。
時刻は2023年8月11日16時で開始から4時間経過しています。現在のトップはShun_PIさんで、相対スコアは34,570,844,995でした。
なお、0000.txtから正解部分を切り取ってビジュアライザに貼り付けたところ全て緑になったので、予測が当たっているときは緑になるとわかりました。
2.同じ場所で何回も測定を行い、平均を取ってみる
さて、サンプルコードは提出してみたものの、問題に関してはまだよくわかりません。連続性のある温度設定を一面に行い、出口セルの温度測定をして、一番差が少ない場所につながっていると考えても良いのでしょうか。やってみようと思ったのですが、お散歩しながら考察をして帰ってきたら考えが変わりました。
一番極端なシンプルな例を考えてみました。
- 出口セルが1個だと考えて、N個の候補から1個選ぶことにする。
これならできそうな気がしました。やることを整理します。
＜やること＞
1個だけすごく高い温度に設定する。全ての出口セルで測定する。いちばん高い温度だったものを出口セルのワームホールとする。
うん、うまくいきません。
何で？と思ったのですが、インタラクティブの応答部分をローカルでは自分で出力しなければいけなかったからです。コードを書きなおそうと思うもののサンプルコードから書き直すのがうまくいきません。一から書こうか迷いますが、サンプルコードがきれいなので、これに合わせて書きたいと思いました。順位表を見ると、いつの間にかサンプルコードのスコアが11,792,359まで下がっていました。トップのスコアが伸びているのだと思います。
まだ手探り状態なので、何かを提出したい気持ちになります。サンプルコードが1回しかその場所で測定をしていないので、同じ場所で10回測定をして平均を取るコードに変えて提出しました。
変えた部分はサンプルコードの1行だけです。
int measured_value = judge.measure(i_in, 0, 0);
これを10回のループにして、値の和を10で割りました。
するとスコアが伸びました。
なるほど～。
20回測定した平均だとどうなるのかなぁ。提出をするとスコアが少し伸びました。
maxは100回まで計測できそうなので（出口セルの数がMAX100で測定回数のMAXが10000なので）、スコアが下がるまで試してみたい気分になりました。提出間隔が30分に1回と制限されているので、30分おきに平均を取る回数を10回ずつ増やして提出します。途中までスコアがどんどん伸びていきました。
70回以降はでこぼこしている感じです。正解が増えれば得点が伸びるし、測定のコストが増えすぎるとスコアが下がるのでしょうか。誤差の与え方が各seedによって違うようなので（入力Sで与えられる）、誤差に合った測定回数にすると良さそうだなあと思います。
2日目です。時刻は2023年8月12日の8時です。yuusanlondonさんが1位になっていました。相対スコアは44,493,304,661です。
自分の相対スコアを貼り忘れていましたので90回の平均を取ったものを提出し直します。2023年8月12日午後1時で520人中242位、相対スコアは60,416,490でした。トップのスコアは45,106,423,939です。過去に相対スコアの見方を教えてもらった気がするのですが忘れてしまいました。覚えているのは全部のテストケースでトップを取ると、50,000,000,000になり、これが相対スコアの満点になります。サンプルコードの相対スコアは12,245,619になっています。
これまで同じ場所で測定をしていましたが、上下左右に同じ温度設定をしておいて、上下左右で測定をしてあげると精度が上がるのかなあと思いました。サンプルコードでは10差の温度設定になっていました。設定できる温度の上限は1000で、出口セルの最大個数は100だったので、10差がMAXに見えます。上下左右を入れるとか、周囲8方向を入れると10差を50差、90差にできるので、出口セルの差を検出しやすくなるのではないかと考えました。測定コストが上がるので、加減が必要なのかもしれませんが。
記録しておく必要なデータも何となくわかってきました。
- 各場所の温度設定（すでにある）
- 各場所の測定回数
- 各場所の測定回数の和（和でなく数列で1個ずつ計測データを取るのも良さそう。両端のデータをはじいて平均を取りたい気もするので。）
30分間隔でスコアを調べている間にローカルでの出力ができるようにコードを修正しました。seed0での結果は95個のうち72個的中していて、scoreは4995でした。
100テストケースを実行します。
#!/bin/bash
./a.out <0000.txt >output0000.txt
./a.out <0001.txt >output0001.txt
./a.out <0002.txt >output0002.txt
./a.out <0003.txt >output0003.txt
./a.out <0004.txt >output0004.txt
このような中身の100個分の実行を書いたrenzoku.shというファイルを作っておいて./renzoku.shで実行しています。
ほとんどのケースでスコアが1でした。
いちばんよかったseed3のスコアは2,942,492で、61個全てが正解していました。Sが4と小さいからかもしれません。ただ、相対スコアを採用しているので、実際の得点が良いとは限りません。こういった場合はもっと試行回数を少なくした方が良いのだと思います。
逆にスコアが1だったseed4のビジュアライザです。Sが529と大きな値です。誤差が大きいので、10刻みの違いを検出できないのだろうなあと思います。
スコア計算を実装しようと思います。計算式がよくわからなくて、毎回後回しにしていたのですが、これは本当に大事というか当たり前だと思うようになりました。自分の成長を感じます。
スコアには配置時コストと計測時コストがあります。
- 配置時コスト
AtCoder問題文より引用
- 計測時コスト
AtCoder問題文より引用
- 得点
AtCoder問題文より引用
だいたい正しい（誤差1くらい）スコア計算ができるようになりました。
よかった。
Sの値で試行回数を変えてみたのですが、うまくいきませんでした。記録せずに100テストケースをまわしたスコアを見ていたので、時間は経っているものの成果無し。こういう時間を減らしていきたいです。
100個測定してそのうちの上下10個ずつをカットして平均を求めることで、少しだけhighestを更新しました。絶対スコアは9,473,622、相対スコアは61,931,052、順位は556人中274位です。
サンプルケースだと、1個も予測されないものとか、複数予測されるものがあるので、1対1対応になっていません。ここをうまく改善できればと思います。
3.ランダムからの山登り
休憩をしたら考えがリセットされました。
0からN-1のランダムな並び替えからスタートして、2個選んでswapし、スコアが良くなるように時間内山登りをしようと思います。山登りに使用するのは、先ほど使用した100回同じ場所で測定してソートし、11番目から90番目までの80個の和の平均を使用します。
書けたので提出しました。絶対スコアは10,451,665、相対スコアは71,121,094で、592人中293位になりました。
4.温度設定を変える
ワームホール（出口セル）の上下左右の温度設定を半減した値にしました。
微増しました。
思った以上に配置時設定の影響があるのかもしれません。問題文中の「グリッドはトーラスを成している。 つまり、最も上の行から1マス上に移動すると同じ列の最も下の行に到達する。左右も同様である。」という文を思い出します。できるだけ差が無いように値を設定し、ワームホール（出口セル）のある場所に来たら、温度を上げていきます。周囲の温度が低く、真ん中の温度が高い設定のグリッドができました。
seed0のスコアは1,484,260になり、桁がひとつ大きくなりました。ビジュアライザもきれいになりました。
提出をすると、絶対スコアは45,255,143、相対スコアは318,044,271まで上がりました。順位は652人中255位になりました。
だいぶ上がったー！
温度設定を1000をNで割って加算することにしました。絶対スコアは下がったのですが、相対スコアは上がっていました。提出前は303Mでした。
5.測定する場所を広げる
ワームホール（出口セル）でしか測定をしていませんでしたが、前後左右および斜め方向にも測定場所を広げていきたいと思います。バグらせるのを減らすために、まずはy方向に1マスだけ移動した場所を測定するようにします。同じ場所を60回、移動した場所を40回にして平均を取ります。ランダムで2箇所選んで入れ替えてみて、それぞれの差を足したときに小さくなる時、スワップして山登りをしました。
100テストケースで結果を見ると、同じ場所で測定するよりも、スコアがぐんと良くなりました。隣り合った場所での温度の傾斜がわかると、特定する要素が増えるのだと思います。
わくわくしながら提出をします。
結果は、絶対スコアが下がってしまいました。相対スコアも下がっています。
おかしいな。
うーん。
100テストケースの結果は上がっていましたし、seed0のスコアも3547358に上がっていました。
コードを見直して、再度提出してみました。
すると、もっと下がりました。
うーん、これは何か提出とローカルで違いが起きていそうです。
ランダム要素もあるので、いちばんよかったものを再提出してみたいと思います。ただの上振れだったのか、そのときの方が良い解法だったのかがわかると思います。
やってみました。
一回の提出ごとにスコアが大きく変動することがわかりました。いちばんよかった提出は45,255,143から35,392,798に下がり、いちばん最後の提出は27,800,702から38,203,200に上がりました。
6.測定回数の調整
2023年8月14日、コンテスト4日目の朝になりました。今考えていることは、与えられた標準偏差Sに応じて対応を変えることです。測定しながら標準偏差を計算し、与えられたS以内なら測定を終了したいと思います。
また、Sが大きいものに関しては、何もしないで全て同じ提出にして1個だけ当てた方がまだ得点があるのではないかと思います。何もしないで1個だけ当てたときは得点が1になりました。相対スコアで得をすることはあるのでしょうか。（なさそうなのでこれはやめました。）
考察をしている間に、気がつきました。条件を見落としている～！
AtCoder問題文より引用
出力される値が負の数がないということです。ということは、平均を取っていてはダメですね。ヒストグラムを作成して、最頻値に変えたいと思います。そのためにも、どのような値が出力されるのか、誤差として加えられる値を見てみたいと思います。
seed0の0番目（530を設定）を100回測定したときの値です。平均は531.21になりました。標準偏差は29.64です。
seed4の0番目（530を設定）を100回測定したときの値です。平均は229.52になりました。標準偏差は282.94です。これを推測することは難しそう...。
ヒストグラムを作ってもうまくできるものとできないものがありそうです。
10回ごとに標準偏差を計算して、標準偏差が10以下かSの半分以下のときは測定をやめることにします。また、0番目と1番目の温度設定を同じにしているミスを見つけたので修正します。
また、温度設定を、Sの3倍か1000をNで割った数の小さい方にしました。
100テストケースの平均は4,118,496、 その前の平均1,488,525の 約2.7倍にスコアが増えました。提出すると絶対スコアは131,926,513、相対スコアは481,435,953になり、796人中354位になりました。順位はあまり良くなっていませんが、久しぶりに絶対スコアと相対スコアの両方を上げることができました。
隣接セル1個と合わせて調べてみるようにします。50回50回ずつに分けて、同様に計算します。スコアが良くなるものと悪くなるものがありました。提出すると絶対スコアは129,753,979に下がりましたが、相対スコアは486,088,710に上がりました。799人中354位でした。
Sが10より小さいものは隣接セルを測定することをやめました。
0より下と1000より上がカットされているので、正規分布に従うなら平均値ではなく、中央値に変更しようかな。
中央値にしてみましたがそこまで良くなりません。
標準偏差が大きいものの設定温度の差を30,50,100といろいろと変えてみることにします。（温度設定が同じものが複数出る）
テストケースを実行してみますが全然良くなっていない様子でした。
何か他に方法がないかと検索をします。「ノイズ除去」で調べている中に、測定しながら平滑化フィルタを通して精度を上げていくというものがありました。
ローパスフィルタをやってみました。似た値は出るものの、平均を取る方法に比べて良くはなりませんでした。
7.ついにひらめいた！
なかなか良くならないまま時間が過ぎています。朝や夜など、空いた時間には順位表を眺めています。改善して点が上がっているときは、お気に入りの人を抜いたり、抜かれたりするするのが良いモチベになるのですが、改善できずに停滞し始めると苦しくなります。落ち込まないように気持ちを切り替えるのがなかなか難しいなあと思います。
測定回数の考察はストップして、グリッドの温度設定をもう少しうまくできないだろうかと考えることにしました。標準偏差の大きさを考えると、山みたいに温度を上げるのではなく別の方法が必要に思えました。一筆書きのルートを作ると良いのではないかと思いました。十字にしてルートを作る方が良いのかな、と思います。ペンと紙で紙に書き出してグリッド上に線をつないでいきます。２点間をつないでワンセットにしてみる？
ふと、思い浮かんだのは点字。
Nは100個だから点字みたいに一意に決められる点の集合セットを作っておけば良いのではないかと思います。測定する点は7個で128種類作れます。100種類を7点なら各点を10回は試行できます。温度設定を高くすれば、標準偏差が大きくても識別できそう。7点がONかOFFかがわかれば良いのです。
天才じゃない？これ。
久しぶりに思いました。外出先で思い浮かんだので、わくわくしながら帰宅しました。コードを書きます。
思ったようなスコアが出ません。使用するマスの個数を7個から9個に変更しました。これまで100テストケースのうち、37個が1以下の値でした。それが、ついにスコアが出るようになりました。
やったぁ！
100テストケースの結果を待たずに提出をすることにします。スコアの計算がバグっているのはわかっています。
どきどきしながらジャッジが進むのを見つめます。
結果が出ました。
あれ？
下がっています。おかしいなぁ。
相対スコアは584,672,613から283,297,117に下がり、順位も384位から433位に下がってしまいました。
Sの大きさによって、方法を変えるようにしました。Sが10より小さければ1箇所のみで判定。50より小さければグラデーションの一山を作って9か所測定。それ以上はQRコード型で測定。提出すると絶対スコアが最高スコアを更新して、182,262,491になりました。
相対スコアも803,533,581になり、863人中373位になりました。
うーん、天才ではなかったみたいです（わかっていますが）。それでももうちょっと考察を進めるとまだスコアが上がりそうな気がしました。
8.9マスで一意に定める形と1,0の判定方法を考える
2023年8月16日の夜です。昨日はうまくいきませんでしたが、もう一度考えます。昨日は、判定に使う9マス内に複数の出口セルがあるとき、重複部分の判定ができなくなるので、違う値を足していました。例えば、100で埋めたいところを150で埋めるといったことをして9マスの中に0と100以外にも250（100+150を足した数）が存在するといったことが起きていました。重複する部分をうまく重なる形を選択するようにして、0と100だけで構成するように変更したいと思います。
512個のQRコード（点字型からQRコード型に呼び名を変えました）型を作りましたが、Lが小さい時には複数の出口セルの判定用マスが重なってしまうので、別の形をしづらくなります。それでもかなり接近した出口セルがあっても違う形を選択できるようでした。最終的にグリッドのマスの数（L×L）と出口セル（N）の数を比較して、マスの数が出口セルの2倍以上あるときに使い、それ以外は従来のグラデーション温度設定を使うことにしました。2倍以上だと出口セルのうち2、3個別の形を選べなくなるseedが出現しました。
seed17を見るとグリッドのマスの数は出口セルの3.7倍くらいです。ぎゅうぎゅうに見えますが、それでも識別できています。
また、Sが小さい時には9マス測定するよりも1マス測定するだけで選ぶことができるので、グラデーション型を使った方がスコアが高くなりました。Sが9までの場合はグラデーション型、10以上はQRコード型を使用するように場合分けをしました。
途中、調整している間の提出はスコアが下がり、意気消沈。16日も順位を上げることはできませんでした。
2023年8月17日の夜になり、先ほど記述した場合分けで提出をすると、ついにスコアが上がりました。絶対スコアが最高スコアを更新し、222,872,896になりました。相対スコアも2倍近くの1,513,490,069 になり、順位も938人中343位になりました。提出前は457位まで下がっていたので順位が一気に100以上上がりました。
おおー！うれしい！
感慨深くてしばらく順位表を眺め続けていました。
調整している間に感じたのは、調整の変わっていない部分のスコアがぶれることです。QRコード型の並びをシャッフルして使っているせいかもしれません。どれがよいか決めようにもインタラクティブなのでやり直すわけにもいきません。
…と考えていたら、そうか、どこを測定するかを変えていく必要があるのかと思いました。たとえば残りが2枚になったとき、ずれている部分だけを測定すればよいはずです。また、同じだと思う部分がずれていたら予測とずれているので、これまでの予測をもう一度やり直す必要があります。
使うべきQRコード型と測定していく最適な箇所があり、最初から最後まで9か所を10回ずつ測定するよりももっと良い方法がありそうだと思いました。
9.予測判定に確率を使用する
それから測定して平均と標準偏差を求めていましたが、確率に変更しようと思いました。測定誤差の標準偏差がわかるので、測定値が設定温度とどの程度離れているかでその値が出る確率が求まります。
標準正規分布表というものを見つけたので、それを使うことにしました。測定の度にそれぞれの確率を足していきます。差がついたら測定を終了します。どのくらいの差が必要かわからないので、プリントデバッグをして様子をみます。適当に差を1にしてみました。
100テストケースを回すとスコアが上がっていました。提出をすると、最高スコアを更新しました。絶対スコアは260,810,144、相対スコアは1,893,848,712で、943人中325位です。トップとはものすごく差があるのですが、一歩ずつ改善できていてうれしく思いました。
次に、測定値で出した確率が一方の出現確率が5％以下の値が出たら測定を終了するという条件を追加しました。うーん、イマイチ。1%以下にしてみました。うーん、イマイチ。何でだろう…。Sが10以上のときという条件を忘れていたので加えました。100テストケースのスコアは上がっていたので提出します。
結果は下がりました。
下振れかな？同じものをもう一度提出します。
もっと下がりました。
！
何でー？
ただ下がりはするものの、以前よりは良いスコアなので、良くなっているものと悪くなっているものが混在していそうです。
使用しているQRコード型の良いものと良くないものの評価が事前にできると良いなあと思います。
あと心のどこかから期待値を求めましょうという声も聞こえてきます。有意な差を求めればいいのだから…。そういえば、z検定を使えそうな気もしてきました。良く知らないけど。
調べてみると、z検定は2群のデータが対応しておらず、かつ2つの母集団は正規分布に従っていて、かつ2つの母集団の分散が既知であるときに有用のことなので、使用しても良さそうです。説明を読んでいると棄却限界値という言葉がでてきて、さっきやろうとしていたことはこれだと思いました。
10.新しいアイデア
さて、これの続きをやろうと思っていたのですが、お皿を洗っていたら、また、ひらめきました。
グリッドに十字に温度設定をしたらどうだろうか、と。すると地図のように場所を特定できるのではないかと思いました。
イメージとしては各出口セルから十字の温度設定の位置を測定します。垂直方向、水平方向の両方がわかれば終了します。設置時のスコアを下げることができそうだと思う一方、測定時のスコアは1マス移動するごとに100ずつスコアが増えるので、かなり増えると思います。差し引きどうなのかと、精度はどうなのかと思いますが、今の想像では良さそうに思います。棄却限界値が役に立ちそうです。
全部を調べると距離も遠くなり大変な気もしますが、ひとつずつ決めていけば、だんだん調べる箇所は減っていくはずです。
んー、コードの修正が大掛かりになりそうです。
11.現状分析
何をしようか迷います。これまでの結果をクロス集計にしてみました。Nの数よりも、L（グリッドサイズ）とS（誤差の標準偏差）に影響を受けているように見えたので、適当な間隔に区切って、平均を求めます。ちなみにこれは全テストケースのMAXを使っていて、これを出せるコード自体は存在していません。（ある条件にすると一方は上がるけど一方は下がるみたいな状態です。）
注意しなければいけないのはこれは絶対スコアで、順位は相対評価なので一概にスコアが低いからダメというわけではありません。Sが大きいとスコアを上げるのが難しいはずなので、その中で少しでもスコアを上げる必要があります。
12.中央1点に温度設定をする
結局やってみたのは、中央に1個だけ温度を設定しました。十字に並べていくと2点測定することになるので、1点の方が良さそうだと思いました。
各出口セルから中央1点の相対場所を記録しておいて測定します。合っていないときは0の場所を測定することになります。途中で配置時コストを下げるために中央1点の上下左右に4分の1の値を設定することにしました。
全ての可能性を調べていくのでN!の計算量がかかります。Sが100以下のときは1回のみの測定、それ以上は3回測定して平均を取ります。温度はMIN(S*6,1000)に設定しました。
100テストケースの結果です。上の表と見比べてみてもらうとわかるのですが、30<S<=300のときと、L<=20のときに良くなっていることがわかります。
提出をしました。絶対スコアは201,059,859になり、相対スコアは3,308,263,055になりました。順位は974人中266位です。
驚くほど上がりました。
…うれしい。
場合分けをすればまだ良くなるはずです。今の時間は2023年8月18日の23時。残りはあと2日です。どこまでがんばれるかなー。
13.コンテスト終了まで残り2日
2023年8月19日朝です。残り2日になりました。最高スコアを寄せ集めると倍くらいのスコアを出せます。しかし、これが難しい。
S<1のときはグラデーション型。S<=30もしくはS>=400のときはQRコード型、それ以外は中央1点型にしてみました。
結果はHighestを更新し、絶対スコアが304,014,702、相対スコアは4,566,174,989、993人中216位になりました。ついに推定パフォーマンスが青になりました。
それでも100テストケースの結果はMAXに比べると85%くらいの得点です。残念なことに最高得点を出したときに何をしていたのかがわからなくなってきました。Excelで条件を記録しながら100テストケースの結果を保存していたのですが、段々雑になってきていたところでした。点数が良くなってくるときは、いろいろなケースを試してみたくなって、記録がおろそかになってしまいがちなので良くないですね。
うーん、煮詰まってしまいました。
そうだ、それぞれの方法で何点が出るのかを試してみよう。ただ、点数が毎回ブレるんだよなあ...。それもまた未解決のままでした。
14.コンテスト最終日
2023年8月20日7時です。朝になったので起きたものの、眠いです…。昨日もABCに参加した後はあまりの眠さにすぐに寝てしまいました。コンテスト中は眠くなかったのですが。
さて、今作っているタイプはグラデーション型、QRコード型、中央1点型の3種類です。それぞれ100テストケースの結果を見ます。
実はグラデーション型はSとLの両方が小さいときしか他に比べてスコアが良くないということがわかりました。条件をS<=5かつL<=20とすることにします。
QRコード型はS>=400とします。
それ以外を中央1点型にしました。
3種類の中では中央1点型が強い！
上記の場合分けをして100テストケースを回します。コンテスト終了後はシステムテストがあり3000テストケースの結果で最終順位が決まります。L,N,Sの条件によって違う結果が出そうなので、今の暫定スコアや順位をあまり信頼しない方が良い気がしてきました。100テストケースでも全然全てのパターンを網羅できていないので、50ケースなら尚更です。
さて、場合分けをして提出をしました。絶対スコアはこれまでの最高スコアを更新して388,582,377になりました。相対スコアは4,459,619,662から4,450,924,178に下がり、順位は253位から254位になりました。現在の提出者は1042人です。
全然変わらりませんでした…。
そうなのかー。
場合分けはここでストップして、もう少し配置時の温度設定の値と測定方法を改善したいと思います。
中央1点型で確率が0.5のときに測定を終了することにしました。
提出をします。
絶対スコアはこれまでの最高スコアを更新して398,299,027になりました。相対スコアは4,735,433,115に上がり、順位は1042人中240位になりました。
少し上がりました。
うれしい。
中央1点型の判定を平均がこれまでは温度設定の2分の1より大きければOKとしていたものを3分の2以上でOKに変更しました。また、中央1点の温度設定をmin(10S,1000）にしました。
提出します。
絶対スコアはこれまでの最高スコアを大きく更新して527,979,105になりました。相対スコアも6,719,845,466に上がり、順位は1042人中185位になりました。
おおー！
すごい上がった！！！
感無量。
これまでなかなか出せなかった全てのカテゴリでのHighestを更新することができました。全部はブログに載せていませんが、毎回100テストケースの結果を下のような表で比較しています。
何か改善できることがないかなあ…。測定回数が減らせると良いのだけど…。テストケースの結果を見ていると間違いが1個だけあるものがありました。
おかしいな。あ、そうか。中央1点型だと予測がひとつになるようにしていないことに気がつきました。該当がなかったものときの処理が抜けていそうです。該当がなかったときは上限を10000回としてもう一度測定することにしました。もしすでに選ばれているものがあれば、精度の高い方を選ぶことにして、はじかれたものをもう一度測定します。
やってみたのですが結果は良くなりませんでした。時刻は最終日の午後6時。提出は30分間に1回なのでチャンスはあと2回。最終提出を間違えるのがこわいので、ここで終わりにしたいと思います。
システムテスト前のトップはJirotechさんの47,621,267,916です。
私の現在の暫定順位は1066人中201位。絶対スコアは527,979,105、相対スコアは6,725,917,529です。seed0のスコアは12,190,662でした。
15.終わりに
あと1時間でコンテストが終了します。序盤、スコアが上がらない時間が長く続き、苦しいスタートでした。後半は少しずつスコアを上げて、暫定順位は過去最高の順位で終わることができそうです。この後システムテストがあり、その後の順位が最終順位となります。システムテストでは順位が大きく変動すると思いますが、耐えて欲しいなと思います。
とても面白い問題でした。最終日までいろいろなアイデアを試すことができました。参加者の人たちもきっといろいろな解法で解いているのだろうと思います。コンテスト終了後に他の方たちの解法を聞くのを今からわくわくしながら待っています。
コンテスト終了後2023年8月20日の21時からはTwitterXのスペースで感想会を開く予定です。コンテスト期間中は内容について言及することができないので、私を含め、コンテストに参加したみなさんは話したいことがたくさんあるのではないでしょうか。どうぞ気軽に参加してくださいね。来てくださるのを楽しみに待っています。
余談ですが、私のやっていることは意味があることなのだろうか、私で良いのだろうかと悩むことがしばしばあります。もっとできる人はたくさんいます。参加記や感想会スペースを行うのに、もっと適任な人がいるだろうと思っています。それでも「続けることに価値がある」、そう思っているから、これからも続けるのだろうと思います。良いときも悪いときも全て受け入れること、私は私なんだとどこかで開き直ること、それを自分に言い聞かせながら。
続けるということに関して言うならば、自分の中の感情が動けば、それで良いのだと思います。良い結果が出たらやったー！と喜び、ダメだったら悔しいと思う。そんな気持ちを味わうことのできる競技プログラミングは本当に最高です！
このブログやスペースをきっかけにヒューリスティック・コンテストに興味を持ってくださる方がいたらとてもうれしく思います。次はぜひ、私と一緒にコンテストに参加して一喜一憂しましょう。
そして最後に、長い文章をここまで読んでくださり、本当にありがとうございました！
16.最終結果（2023年8月21日更新）
システムテストが終了し、順位が確定しました。暫定202位でしたが、結果は1070名中203位でした。ほとんど変わらなくてよかった。そしてパフォーマンスは初の青パフォの1727を出すことができました。Ratingは1384から62上がって1446に上がりました。うれしい！
3000テストケースは全てACしていました。平均と各テストケースのスコアをグラフにしてみたところ、下図のようになりました。このテストケース、Sが後ろに行くほど大きくなっているのだろうなあと思いました。スコアに段差があるので、もうちょっとうまく調整したかったなあと思います。また、確率や推定の部分はもう少しきちんと扱えるようになりたいと思いました。
