- 0.はじめに
- 1.問題文の音読とビジュアライザの表示
- 2.最初の提出
- 3.最初の考察
- 4.問題文の概要
- 5.Mに対して最小のNを求める
- 6.エラー率0の場合のコードを書く
- 7.エラー率（ε）からグラフを予測する
- 8.相殺（そうさい）
- 9.シミュレーション（モンテカルロ法）
- 10.デバッグ中（スコア計算を書いて、テストケースを100個試す）
- 11.デコードのノイズ（ε）とNのサイズを考察する
- 12.Nを大きくしたらエラーを消せる？
- 13.エラー率が高かったらNを小さくする
- 14.復元（ランダムに並び替えるとは何かについて考える）
- 15.問題点のリストアップ
- 16.グラフの同型判定
- 17.終わりに
- 18.最終結果（2022年11月22日）
0.はじめに
はじめまして、もしくはお久しぶりです、競プロ歴約3年のかえでです。
今回は、HACK TO THE FUTURE 2023 予選（AtCoder Heuristic Contest 016）に参加しました。開催期間は2022年11月11日(金)19:00から2022年11月20日(日)19:00までの9日間続いた長期コンテストになります。
この参加記は「ヒューリスティックコンテストとは何なのだろう」と思う人に、何を目的としたコンテストなのか、とか、その楽しさがどこにあるのかを感じてもらいたいと思ってこの記事を書いています。備忘録的な要素が強く、無駄なことも多く書いてあります。しかしその分、リアルに感じてもらえるのではないかと思っています。
だから、これを読んだ人が、「自分だったらもっと良い得点が取れそう」と思ってくれたら、自分はこの参加記を書いてよかったなと思います。その一方で、きちんとした解説を読みたい方には、おすすめできないと思っています。コンテストの解説ページからいくつもの解説記事へのリンクがアップされると思うので、ぜひ自分に合った解説記事を見つけてもらいたいと思います。また、解説放送も予定されているので、ぜひそちらをご覧ください。
私はAHCが大好きです。継続的にコンテストを開いてくださるAtCoder、興味のつきない作問をしてくださるwataさん、いつも本当にありがとうございます。また、毎年HTTFでは徹夜でvisualizer仕上げてくださっているtsukammoさんに敬意を表して、コンテストに参加したいと思います。最後に、これからもヒューリスティックコンテストがますます盛り上がっていくことを心より祈っています。
1.問題文の音読とビジュアライザの表示
現在の時刻は2022年11月11日20時。コンテストが開始してから1時間が経過しました。
今日やろうと思っていることは、問題文の音読と、ビジュアライザを動かすことです。ビジュアライザでどんな問題かを感じることができれば、今日の目標は達成です。
問題文を音読しました。
...よくわかりません。ところどころ目に入った文字をつなげると、
値 グラフ（エンコード）→（+ノイズ）→（デコード）グラフ 値
といった感じでしょうか。グラフは「鍵」なのかなと思います。形が一意のグラフを作れるのかなとぼんやりと考えます。
お風呂に入りながら、バーコードは一部分が欠けても正しいものを復元できるようになっていたなあと思います。ノイズが入るということは一部の情報が正しくなくなるということ。長くするほど一部が欠けても復元は容易そうなので、短い方が得点が高いという問題とも合致します。
さて、よくわからないから、ビジュアライザを見ようと思うけど、これまたよくわかりません。問題文にあったpythonのサンプルコードをコードテストで出力してみるけど、途中から「…」になって最後まで出力されません。
しょうがないので、pythonのサンプルコードをc++に書き直します。
seed0を入力してアウトプットをビジュアライザに入れます。そうしてやっとビジュアライザを見ることができました。
何だこれ？
モードが他にも選択できます。
何だ？？
あ、これが直感的かも。
2番目との違いがわからないな。
これも使いやすそう。
ええと、グラフを表示していて、表示のしかたを選択できるのだな、というところまでわかりました。今日はもう寝ます。
明日も問題文の音読からやります。
2.最初の提出
2日目。音読を開始します。
グラフを識別したいということがわかりました。Mは最大100なので、N=100として、辺の数を全て異なるようにしたら、ノイズがなければ全て正解になるということで合っているのでしょうか。
サンプルコードを修正します。N=100のとき、辺の数はN(N-1)/2を計算すると4950本。大きい...。
出力サイズが大きすぎて、ターミナルで最初の出力部分がスクロールでたどれなくなってしまったので、テキストでの入出力に書き直します。
最近、ローカル実行との切り替えにONLINE_JUDGEを使うようになりました。とても便利です。
#ifdef ONLINE_JUDGE提出時に実行される#elseローカル用処理#endif
コードを書き直して、出力結果をビジュアライザにコピペします。スコアが2,993になったのはNが増えたせいとして、正解も増えていないので、理解していなさそう…。青が正解、赤が不正解のようなのですが…。その考えで合っているのかな？
N=10にしてみました。スコアが29,969になりました。上がっています。
Nの最小は4なので4で出力してみます。正解は増えていないように見えますが、スコアは74,923になっています。
適当に答えを出す場合、Nが小さいほどスコアが良くなるということがわかりました。とりあえず提出してみようかなと思います。最初の提出結果です。
順位は420人中91位、得点は1,282,114,488点でした。今回は相対スコアになるということで、得点の見方は、まだよくわかっていません。現在のトップはShun_PI さんで、得点は34,455,300,154点です。トップとは34倍の開きがあると考えて良いのでしょうか。
追記：自分の提出を見たら、変動しない本来の得点を見ることができました。2106852点でした。1テストケースの満点は1000000000なので得点率0.004％。（本当に？）
さて、問題文の意味がわかっていない自分がこの位置にいるのですが、他の人もこんなにわかっていないのでしょうか。今回、難しい問題なのかな？
とりあえず、グラフを当てる（推定する）ゲームというのは合っていそう。
わからないのは、ビジュアライザの使い方と、ローカルのノイズ生成部分。
問題文より引用
3.最初の考察
もう一度、問題文を音読したいと思います。
- エラー率が0なら、並び替えをしたら、元のグラフと一致するのでそれを出力すればよい。
- エラー率が最大の0.4なら、並び替えをして、一致するグラフがあったとしても、それは正しくない？
そんなことを考えれば良いのでしょうか。もう少し具体的に考えてみます。
今、デコードされたグラフが1111111111だったとします。でも、エラー率が0.4なら、実は1111110000、1111110001、1111110011、1111110111（1の並びは順不同）とかのグラフの方がエンコード前のグラフとして可能性が高いのではないか、みたいなことを考えれば良いのかな。
期待値を足せばよいのでしょうか。
数学の問題なのかな。
グラフの辺の有無について、頂点番号が消えて並べ替えをしたとして、維持できる情報って何なのだろうと考えます。グラフの形を復元できるのでしょうか。
グラフの同型判定をする問題がアルゴであったなと思います。使えるといいなと思って、記憶をたどって探しました。M-SOLUTIONS プロコンオープン2021(AtCoder Beginner Contest 232)の「C - Graph Isomorphism」です。とりあえずメモ。
あ、ビジュアライザの見方が少しわかったかも。
①不正解のときのグラフ
赤枠内は右上にあるグラフ番号をわかりやすいように移動してみました。一番左が与えられたグラフ、真ん中がシャッフル前、右が予測グラフ。ということで、一番右が自分の予想なのかな。
②正解のときのグラフ
というわけで、全て0のグラフか、辺が1のグラフしか正解していないことがわかりました。ん？そんなに正解しないのはさすがにおかしいので、コードを見直したいと思います。
---（時間経過）---
あー！！！！！わかった。危なかった。全然問題文の意味が全然分かっていませんでした。何度も音読して読んでいたのに…。
なんと、数をグラフに直していませんでした…。自分でエンコードするって書いてあったのに。
すごい！2日目に問題文の誤読に気がつけたのは、進歩だなと思いました（←前向き）。ちょっと太字にしておきましょう。大事なことなので。
- 音読は大事。
問題文を理解できて、ホッとしました。でもローカルでノイズを加えるには、どうやったらいいのでしょうか。わかっていないことはまだまだありそうです。
なるほど～。
だから、例えば数を2進数で表すと、0と1になってグラフと相性が良さそうだけど、並びがシャッフルされてしまうから別の数字になってしまう、という問題があるということなのですね。
数字を0と1で表現して、なおかつ並び順を変えても同じになるってどういう方法があるのでしょうか。考えなければいけないところが、やっとわかってきたようです。
ということで2回目の提出。
N=4にして、受け取った値をそのまま提出すれば得点が上がりそう。
ほら。
あ、・・・。
意気揚々と提出をしてWAをもらいました。
問題文を確かめに戻ります。100個のクエリで受け取るのは文字列って書いてありますね、はい。サンプルコードも文字列（string）だったのに整数（int）で入力を受け取りました。
ダメじゃん…。
まずはローカルと提出の差分を埋めなければならなそうです。
（余談だけど、今回のHTTFのテーマ曲は、米津玄師さんの「KICKBACK」です。）
ローカルのコードを、値をグラフにしてから入力として受け取るように修正しました。（まだランダムに並び替えてもいなければ、ノイズも加えていない状態です。）
seed0のビジュアライザで確認します。これで合ってそうだと思います。エラー率が0なら、5までは正しく数えられて、それ以降を間違えてしまう感じ。seed0はM=10なので、6,7,8,9が区別のつかない状態になります。
ここで、seed0のepsを0（最小のエラー率）から0.4（最大のエラー率）に変更すると、ビジュアライザが変わりました。H[0]の場合、ノイズが加算されて与えられたグラフでは、あるはずの辺が2本消えてしまっています。
ふむふむ。
エラー率が0.4のときに、4本全てある元の形の割合は0.6*0.6*0.6*0.6＝0.1296、1本欠けているのは0.6*0.6*0.6*0.4*4＝0.3456、2本欠けているのは0.6*0.6*0.4*0.4*6＝0.3456、3本欠けているのは0.6*0.6*0.6*0.4*4＝0.1536、4本とも無いのは0.4*0.4*0.4*0.4＝0.0256の割合で出現するので、1本欠けたときか、2本欠けたときにこのグラフになると答えれば正答率が高くなるということですね。
他のものも同様に考えて渡されたグラフがどのグラフかを推定すると、複数のグラフが候補として出てきそうです。それぞれの出現確率を出して、いちばん良さそうなものを選択するというのが今回の問題だと理解しました。今度こそ合っているといいな。
（※11/19追記：ビジュアライザの青色実線は追加された辺、赤色破線は削除された辺です。）
4.問題文の概要
さて、だいぶやるべきことがわかってきたような気もするので、そろそろ問題文の概要を書きたいと思います。
- （入力）4以上100以下の整数Mが与えられる。
- （入力）0以上0.4以下のエラー率εが与えられる。
- （出力）4以上100以下の整数Nを決める。
- （出力）'0'もしくは’1'のみが含まれる、長さN(N-1)/2の文字列を作り、M行出力する・・・①
- （クエリ入力）①の各文字にエラー率εで01を反転し、並び順を入れ替えたものが与えられる・・・②
- （クエリ出力）②が①のどの行のものかを推測して、数値を出力する。
- クエリは100回行われる。
得点の計算方法（AtCoder問題文より引用）
5.Mに対して最小のNを求める
コンテスト3日目、2022年11月13日です。今日も問題文の音読から始めます。
また、よく理解していなかった箇所を見つけました。Nはどのテストケースでも共通にする必要があるのかと思っていました。Mを受け取ってから適切なNを設定すれば良いのですね。
辺があるのを1として、単純に1の数を数えるならば、Mより大きくなるように、Nの頂点数を決めれば良いことがわかります。
あれ？Nは15までで良いんだ。
Nが大きい方が、正確に当てられそうなイメージはあるのですが、正直なところ、よくわかっていません。Mに応じて、Nの数を適切に決めて、まずはノイズ0の場合の出力を出せるようにコードを書きたいと思いました。
6.エラー率0の場合のコードを書く
2022年11月13日午後5時です。Mの数からNを決めて、エラー率を考慮しないコードを書いて提出しました。相対スコアは836,957,028、順位は275位/736人中でした。同じ得点が18人並んでいました。
絶対スコアは114191306点で、最初の提出より得点が約54倍になりました。得点率は0.228％。先は長そうです。トップとの差は50倍です。
え…、そんなにあるのですね。
7.エラー率（ε）からグラフを予測する
最初の考察で考えていた、エラー率から期待値を求めたいと思います。その次は100個のクエリの出現率を加算したいと思います。エラー率は最大0.4、0.01刻みなので40種類。Mは91種類。たいした数ではない（？）し、計算を間違えそうなので、最初にエクセルで計算しておいて、配列に読み込みたいと思います。
エラー率の値によって、どのグラフを選ぶのかを決めてしまいたいと思います。
書けるのですか？（心の声）
というわけで、E8さんの1冊目の著書「アルゴリズム×数学」本を取り出します。P88からの3.4章「確率・期待値とアルゴリズム」を見ながら計算を進めようと思います。
8.相殺（そうさい）
コンテスト4日目、2022年11月14日夜です。期待値の計算ですが、面倒臭くなってまだやっていません。日中は、もっと楽な方法はないかと、仕事の合間に考察をしていました。
「エラー率によってbitが反転するってどういうことなんだろう」ということをずっと考えていました。
たとえば、1111100000みたいなグラフがあったとして、エラー率をかけると、一定の割合で、01が反転したとします。でもそれって、見かけ上変わらないんじゃない？と思います。
相殺（そうさい）して見かけ上は変わらない状態にできればいいと思います。
でもどうやって？
ヒラメキました。すごく簡単な方法。
エラー率でノイズが加わったグラフに、もう1回エラー率でbitを反転させれば元に戻るんじゃない？
天才かな。
実装も簡単だし。
そういえば乱数のseed値を指定すると、同じ乱数を発生させることができるんだっけ、そんなことを思い出しながら、実装をします。未だローカルでのジャッジができないままでいました。Ｅ8さんの2冊目の本、「競技プログラミングの鉄則」の7章「ヒューリスティック」に乱数のことが書いてあったような…。補足ですが自分の使用言語はc++です。
rand()関数は大変お手軽ですが、乱数の質がやや悪いです。そこで良質な乱数を生成する方法として、XORシフトやメルセンヌ・ツイスタなどが知られています。本書の範囲外ですが、興味のある方はインターネットなどで調べてみてください。
ということで調べてみました。
メルセンヌ・ツイスタ
調べてみると、今自分が使っていたものでした。さらに調べていくうちに、ちょうど良さそうなものを見つけました。
std::bernoulli_distribution ベルヌーイ分布（確率 p で 1 を、確率 q = 1 − p で 0 をとる、離散確率分布）
これを使って、与えられたグラフにこの確率をかけて、結果を出力するようにしました。提出してみます。結果は絶対スコアが91450821と、エラー率を考慮しないときより下がってしまいました。
そうか、１回だから結果が安定しないんだ...と思います。
あ！
5秒あるから、何回も計算すればいいんだ。それで一番多かったのを出力すれば良さそう。
おお、やっとヒューリスティックコンテストっぽくなってきました。ただいまの実行時間は13ms。時間があまりに余っています。
そうかー、自分でエクセルで計算しなくても、シミュレートすればいいんだなー。もしかして文字列をbit演算にして高速化するとかもできちゃうのかな。
夢がふくらんできました。
わくわく。
ええと、クエリは100個なので、1個あたり5000/100＝50ms。では45msで試行してみます。
---(時間経過)---
そうじゃないじゃん。お風呂に入っている間に考えましたが、元の文字列は自分で作っているのだから、自分でできあがりが何かを予測した方がいいなと思います。
時間いっぱい元の文字列からエラー率をかけて別の文字列を同じ試行回数ずつ行ってカウントし、エンコードした文字列を受け取ったら、できあがった文字列の元の文字列のカウントが多いものを答えとして出力すればいいのでは。
ああ、文章だとわかりづらいですね。
表の行列を入れ替えるイメージです。実装してから値を出力して表を貼りたいと思います。
がんばるぞ！
9.シミュレーション（モンテカルロ法）
書きました。シミュレートするとこんな感じ。
提出してみたらWAになりました。
そろそろ100ケーステストケースをまわさないといけないのかもしれません...。
何とか配列のコードを修正して再提出します。
・・・泣いた。
（45個目まではWAではなかったことを知っています。）
50ケース中1ケースWAが出ています。
何これ～？
もう一度配列周りのコードを確認して提出します。
ACしました。
しかし得点は上がらず、113966594点でした。
うーん、よくわからない。
まずはローカルテストを正しくできるようにしたいと思います。
ノイズを足してみました。
それっぽくなったかな？
カウントが間違っていそうなのもあわせて修正して再度提出しました。ACしましたが、Highestは更新できませんでした。114097304点。
何でだろう～。
10.デバッグ中（スコア計算を書いて、テストケースを100個試す）
昨日のコードの振り返り。たとえばM=10,eps=0.4だと、N=5で0,2,3,5,7,8,9,9,9,9を返すコードになっていて、1と4と6が使われていないからそれで正答率が下がっていそう。使ったら値を減衰させて、2のかわりに1を使うようにするみたいにしてみようかと思います。
お、正答率が少し上がったかな？
提出しましたが、得点は113871939点で、微減。
さすがにおかしいな、と思いました。
そして気がつきました。ここまでブログを読んできた人は、気がついたでしょうか？私のミスに。エラー率を使用してデコードした状態を作るときに、0を反転して1にするのを忘れていました。
早速修正します。自分の中のイメージと試行結果は合っているのですが、これでは識別できないなと思います。epsが高いときは、Nを増やさないといけなそう。
提出してみます。結果は87404733点。下がっちゃいました。まあ、識別できていないから、しょうがないかな。
ええと、白状しますがまだ自分でスコア計算をしていません。書きます。
---（時間経過）---
書きました。テストケースを100個試します。テストケースをまわした結果を見てわかったのですが、エラー率0のときしか正答を出せていないということ。
11.デコードのノイズ（ε）とNのサイズを考察する
きちんと出力が意図されている通りになっているかを確認したいと思います。
seed0,eps=0.05のときの試行結果は以下の表の通りです。
ん、まだ100％出力が合っててもいいんじゃないかな、これ。早くも間違え過ぎのような。
ん、やっぱり思っているのと違う。これは合っていてほしい。
コードを見直します。
うーん、合っていそうです。そうか、こんなにずれるんだ。自分でノイズを生成して加えると、”1”ずれることの影響が大きいんだなと思います。だからepsに合わせてNを大きくしていく必要があるということなのかと思いました。
epsが0のときは、最小のNが良いけど。
よく考えると、100個のテストケースのスコアも何だかあやしく思えてきました。今回はテストケースを1000個くらいに増やしたいと思います。
12.Nを大きくしたらエラーを消せる？
たとえば、Nを2の倍数にしたら、1ずれても大丈夫。3の倍数にしたら、2ずれても大丈夫。4の倍数にしたら3ずれても…みたいな考えをしたらどうかなと考えています。「1ずれる」とは与えられたグラフの辺の数とエンコード前のグラフの辺の数です。
イメージするものはあるものの、なかなか実装のバグが取れません。
一度提出すると、WA。絶対スコアは0点でしたが、順位表の相対スコアは数値が更新されていました。相対スコアは今回初めて導入されたのでよくわかっていませんでしたが、WAのときも相対スコアは0にならないということがわかりました。
うーん、とりあえずREの原因を調べて、ACすること。自分の思った通りに答えが出力されているかをチェックすること。あとはどうやったらいいか、もう一度考察してみたいと思います。
13.エラー率が高かったらNを小さくする
2022年11月17日時刻は朝4時半です。眠れないので起きました。眠りが浅くて目が覚めると、次はこうしてみようかなと頭に思い浮かぶので、面倒なので今からやることにしました。
今さらですが、得点の減衰です（10×0.9^ε）。これをNで割ることになります。
クエリで予想が外れていくとこんな感じに得点が減少していきます。
また、エラー率が0.4なんて、予測しても当たらないんじゃないかな、という気持ちになってきました。コイントスが0.5なので、そのずれを予測するのは自分には無理そうだなと思いました。
だったら、エラー率が上がったら、Nを小さくしていって、ランダムで出力した方が得点が高いのではないかと思います。
①Mとエラー率εから計算した予測が1ずれる限界みたいなものを計算して、そこからN＝4にして、ランダムに答えを出力する（もしくは出ていない数値を選んでいく）。
うーん、やっぱりNは適切なサイズのNが良さそう？次の案に進みたいと思います。
②今シミュレートしてる結果は毎回同様になるはずなので、これを記録しておいて使えば、5秒は他に使えるのではないかと思ったので、シミュレート結果を出力する。
あれ？もしかしてまた問題文を誤読している？
ここで何か不安になってきて、問題文を読み返します。
AtCoder問題文より引用
2の辺が含むか否かを反転するのって、回数が辺ごとに違うのかな？
(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)だと0が3回、1が3回、2が3回、3が3回…。同じでいいんだよね？サッカーの試合数と同じなら同じ回数になっていないとおかしいよね。
一応シミュレーションして違うか違わないかを後で確かめてみよう。
話を元に戻して、M=10のときのエラー率を0.01ずつ変更してみます。
---（時間経過）---
ちょっと脱線してしまうのかもしれないけど、ビジュアライザを見ていたら、なんかわかったかも？自分が間違えたクエリなのですが、一番左が与えられたノイズ入りデコードグラフで、真ん中が元のグラフ、右が自分の予想。思ったより元の形が予想できるのかな？
ほら。ノイズの入り方が特徴的？
これがどういうことなのかを考えてみます。
シャッフルされた01文字列を1を左側に、0が右側になるように交換していきます。連続した0の数によって、epsの値から何個くらい1になるかを予測しておいて、その数になったら交換をストップする。最後に連続した1の数を数えて出力すればいい、みたいなことをしたら良さそうな気がしてきました。
↓ノイズを加えてシャッフル後の与えられたグラフ
001010000100000110001000010000000010000100100001001111111000000001000100100110
↓左右から0と1を交換していったグラフ
111111111111111111111000010000000010000000000000000000000000000000000000000000
そういえば、全然ビジュアライザを使いこなせていません。去年のHTTF予選もそうだったなあ…、ふと、思い出します。
気を取り直して、0が0個から100個まで、epsが0から0.01刻みに0.4までのとき、平均何個1に変わるかを求めたいと思います。
14.復元（ランダムに並び替えるとは何かについて考える）
20224年11月18日金曜日、コンテスト8日目になりました。コンテストは明後日の日曜日の午後7時までです。今日は、昨日考えていた方法で復元をしたいと思います。
昨日と1点変更したいと思っているのは、どこまで0と1を交換するかという話。エラー率の平均まで交換するのではなく、1と1の間を埋めることができる間、0と1を入れ替えたいと思います。
あと、Nは適切な大きさのNに戻したいと思います。
とにかく当てないと得点が上がらないとわかったので、偶然ではなく、少しでも正解に近づくようにがんばりたいと思います。
---（時間経過）---
夜です。日中考えました。まとめです。
- 0と0を入れ替えても変わらない
- 1と1を入れ替えても変わらない
- 1と0を入れ替えると変わる
どういうことかというと、自分が作る文字列は左から必要な数だけ1を並べ、その後連続して0で埋めます。だから並び替え前の状態には、左の0と右の1を交換することになります。
昨日考えていた例を持ってきます。
↓ノイズを加えてシャッフル後の与えられたグラフ
001010000100000110001000010000000010000100100001001111111000000001000100100110
↓左右から0と1を交換していったグラフ
111111111111111111111000010000000010000000000000000000000000000000000000000000
これをさらに交換するには、1から0の領域にはみ出していくしかないわけです。
これをやるかどうかを調整していく必要があると思っているのですが、今はやらないことにしたいと思っています。何か確率的に起こりにくい気がしているので。この辺がぱっと計算できるといいなと思うのですが、この置きたい場所って1箇所しかないから文字列の長さ分の1の確率とかでいいのかな。さらに2個連続は（文字列の長さ分の1）×（文字列の長さ分の1）みたいな確率？うーん、合っているのかよくわかりません。
というわけで、1と0をそれぞれ連続させるように左と右に振り分けるような入れ替えを行いたいと思います。
実装しました。
テストケースをまわしました。
提出しました。
（ドキドキ）
あれ？何だろ、この点数。テストケース、ものすごい高得点だったのに...。
あ、テストケースをまわしたローカルの入力にノイズを足すのを忘れていました…。
さあ、気を取り直して。
テストケースの結果、上がってはいるものの、合っているのかわからないので、#vを使ってみたいと思います。
うーん、使い方を間違えていそう。結局自分でデバッグ出力することに。
これは合っていました。他も合っている感じ。
というわけで次のことを考えます。
答えていない数字があったり、最大で4回も同じ数字を回答しています。M=76のときなので、答えの個数は1個か2個にした方が良さそうだと思います。答えをすでに使っていたら、Mの半分より小さいときは答えを1増やしていき、Mの半分より大きいときは答えを1減らしていきたいと思います。
結論としては、うまくいきませんでした。
15.問題点のリストアップ
2022年11月19日の朝です。コンテストは明日で終わります。8日間、何をすべきかよくわからないまま時間が過ぎてしまいました。今考えていることです。
①クエリが進んでもフィードバックができていないので精度が上がらない。
各クエリのグラフを受け取った後は、最初のクエリから今までのグラフを元にもう一度計算をし直す必要があるはず。そこが自分の実装には抜けているなと思います。予測のずれを修正していかないといけないのに。
②乱数のseed値を使っているかの確認。
何か、毎回出力結果が違う気がするので、考察を生かせていない気がしています。
③ビジュアライザを有効に使えていない。
ビジュアライザで頂点の予測を使えていないので、これをしないと始まらない気がしています。（昨日は#vで頂点番号を出力するということがわかっていなかった。）
④グラフであることの意味がわかっていない
多分ここが最大のダメな点っぽくて、問題文の意味が理解できていない気がしています。なんか2次元に展開できないのかなぁ。この辺りのダメな感じは、ビジュアライザが使えていないのと連動していそう。
問題点を書き出してみたら考えることがたくさんあったので、まだやるべきことはありそうです。ただ、Twitterで「問題が楽しい」というツイートを見ると、ちょっと泣きそう。面白いところまでたどり着けていない自分…。最近のAHC、こんなのばっかりだなぁ。
ただわかっているのは、1027人提出していて、自分の順位は今872位だけど543位の点数は出せるということ。過去の自分の提出と同じ点数で、次の提出をしていない人がいるので、相対スコアの中の絶対的指標として参考にさせてもらっています。だから、参加者の半分の人は自分と同じように、問題の意図がつかめず、もがいているのかもしれないと想像することにします。
ビジュアライザでM=10、eps=0.01のテストケース100個をダウンロードしたので、これとビジュアライザで、考察していきたいと思います。（ビジュアライザとダウンロードしたファイルが連動するみたい。）
0.01で何とかできれば、その先でも何とかできそうな目処が立ちそう。
考えていたのですが、今は1を1、0を0と数えていますが、別の方法で数を数えることができないでしょうか。
数値の演算は、足す、引く、かける、割る（MOD）...。
0と1を同数にして数を数えられないか、とか、移動回数で数を数えられないか等。
考えている間、今のコードでM=10,eps=0.01のダウンロードしたテストケースを100個実行します。
結果をビジュアライザで見ていたら、自分の思っているものと違う出力がありました。何で予想時に辺を足したのかな？
そっか、100回に1回くらいは…。ん、ホント？
---（時間経過）---
また、別のことを考えました。1と0を使っているから分からないのかもと思ったので、0から連番をつけて、ノイズにしたものは、Xにして、どんな動きをするのかを考えてみたいと思います。ノイズを加えてから並び替えるという順序に、もしかしたら自分の気づいていない意味があるのかも？
やってみました。
何かわかる？うーん、よくわからないな...。
うーん、辺の数をもとに考えているけど、それが良くない？N頂点の数をもとに考えると何か違う景色が見えるのかな？
0を表したいときは0個、1を表したいときは9個、2を表したいときは9+8＝17個、3を表したいときは9+8+7＝24個みたいに、1の数を変えてみたらどうだろう？
---（時間経過）---
先ほどの案をやる前にコードのリファクタリングをしていました。テストケースをまわしたら、点数が上がっています。
？？？
というわけで一回提出しておきたいと思います。
え？上がってない？いや、そんなはずはない。出力がおかしくないかな？
・・・はい、間違えていました。
もう一回提出したいと思います。
長期コンテストでの提出間隔は30分です。この時間が長いですね、とても。長期コンテストのつらいところです。
100テストケースの結果はこんな感じ。というか、1000ケース位まわさないとダメなのですが。
提出結果です。83657064点でした。順位表だと1043人中621位です。（ちなみに自分の最高スコアの順位は555位）
あれ～。そうか、まだまだですね。
がんばっていこう。
そういえば、何もしないで辺の数を数える自分の最高スコアは389,864,086 点でした。（自分はなぜこの点数を先に出しておかなかったのでしょうか。）これよりも増えないとHighest更新ができないのでした。
とりあえず、m*epsが1を超えるまでは何も変えないようにしようかな。
というか、とても残念なことに気がついてしまいました。最高スコアだったコードのスコア計算をしてみたら、本当にこれで合っているのか疑問に思い始めました。手元のテストケースではほぼ同じ点数が出ているのに、提出すると結果の点数が大きく変わります。これは、自分で生成しているグラフが間違っているのかも…。
そうだとしたらどうしたらいいのかな…。
行き詰っていますが、seedから1000ケース生成して、1000個のテストケースを試しました。手元の100テストケースでは随分と結果が違うと思いましたが、1000ケースの平均で比べるとそこまで違いがないようです。
よかった。
今回、50ケースだけだと、Mとepsの組み合わせによって、かなり点数が変わってくるのかもしれません。
16.グラフの同型判定
コンテスト最終日の朝です。全面を1にしたものを1にする、半分を1にしたものを2にするといった割合で数値を表現できないかとか、いろいろな数値の表し方を考えているものの、うまく考えがまとまりません。問題文を読みます。
100101は4点が直線上につながったグラフを表す（AtCoder問題文より引用）
100
10
1
頂点（0,1,2,3）が直線で結ばれているグラフ。辺は3つだけど、頂点は4つある。自分には辺の有無しか見えていないので、やはり何かがわかっていないのだろうなあと思います。
---（時間経過）---
ノイズが0のものをさらに高得点にできないかと考えてみようと思います。言い替えると、Nを減らせないかということ。さらに言うと、今は1の数の和で数値を計算していますが、別の方法でカウントできないかということ。たとえば、辺が3のとき頂点は4なので、3×4＝12にできれば、文字列の1の数は3だけど、12を表せるとか。あとは、Union Find で連結すると、グループ数が一つ減るからそれで数を表すみたいなもの。それこそ2進数。鍵を作っておいて差分か和を取るとか。ああ、そうか、辺がないということも情報だから、N=4なら、頂点は4、辺の数は6、グループの数は1~4、その辺りの数字を組み合わせて6種類より多くの区別ができないかな。んー、それとも頂点を入れ替えても辺が変わらない並びがあるのかな？
---（時間経過）---
あーーーーーーーーーーーーーーっ！
やっぱり間違えていました。昨日よかったって書いてしまったけど、よくなかった。ノイズの加え方を間違っていました。辺をシャッフルしていました、はい。ほら、頂点を入れ替えても形が違う判定ができるのは知っていて、3.最初の考察で書いていました。
グラフの同型判定をする問題がアルゴであったなと思います。使えるといいなと思って、記憶をたどって探しました。M-SOLUTIONS プロコンオープン2021(AtCoder Beginner Contest 232)の「C - Graph Isomorphism」です。とりあえずメモ。
これは去年の12月くらいに出た問題で、しかも自分はそのとき解けずに解説を見ていたのだけど、コードを写しただけ状態。なので、もう一度すぬけさんの解説放送を見てきたいと思います。時刻は12時15分。残り7時間を切りました。
何と！肝心な解説のところで、すぬけさんのマイクがミュートになっているという回でした…。あー、気づいてくれました、最後にちょっとだけ「次数は同じでも形は違う。隣接関係が大事。」と話していました。
N=4のときのグラフの形。これで合ってるかな。描いてみました。ということは、12種類判別できる？12種類以上あるのかもよくわからない。とりあえず、N=4でM=10に対応できるかどうか、やってみたいと思います。
①000000
②100000
③100100
④110100
⑤100001
⑥101101
⑦110111
⑧111111
⑨110110
⑩111101
⑪100101
⑫100110
あ、違った！11種類でした。⑦と⑩が同じ形でした。
おお、重複していない感じ。何種類できるかというのがよくわからないので、N＝4以外に拡張したり、どのようにグラフを作ったりしたら良いかが分からずにいます。1000ケース試したところ、17％くらい得点がアップしていそうなのですが、提出したら微減していました。
グラフの同型判定について検索してみました。Nが大きくなると5秒で解くのは難しそうです。自分の実装もnext_permutationを使って、順列で判定しているので、Nの階乗通り試しています。N＝5のときは何種類できるのかな？
調べたら、34種類らしいです。実装できるかな。
---（時間経過）---
え、書くの難しい。検索したりして、ここまで調べました。これを辞書順の10文字の長さの01文字列に書き直すのに手間取っています。ﾀｽｹﾃ～。
N＝5のときの各頂点の次数
00000
11000
21100
22200
11110
22110
22220
31110
32210
33220
33330
21111
22211
22222
32111
32221
33211
33222
33321
33332
41111
42211
42222
43221
43322
43331
43333
44222
44332
44433
44444
（33222、32221、22211が2種ある。）
ここでコンテストの時間が尽きてしまいそうです。ごめんなさい・・・。
17.終わりに
時間はコンテスト最終日の朝に遡ります（「終わりに」を書いているのが11月20日の朝だということ）。
昨日は結果が出ないことに対して焦る気持ちが生じて、開催期間中、いちばん気持ちがへこみました。この参加記を公開することにも迷いが生じました。AHCの感想会スペースも、自分が開いて良いのだろうかと思いました。それでもコンテスト最終日の今日は、気持ちが随分と落ち着きました。そして、他の人の解法が気になり始めました。どのようなことを考えて、どのような実装をしていたのか、それを知りたいと思いました。自分が未熟なことは十分にわかっています。この記事が役に立つかどうかとか、私自身の力量がどの程度なのかということを考えれば、分不相応なことをしているのかもしれません。それでも、自分が一生懸命考えてたどり着けなかったからこそ、他の人の発想がすごいと素直に思えるのではないかと思っています。それはコンテストに真剣に参加した者にしか与えられない境地ではないかと思います。だからスペースも開催するし、同じ気持ちを少しでも疑似体験してもらえればと思うので、参加記も公開します。
前回のAHC015（Halloween Candy）でも、「こんな簡単に高得点が取れます」という解法がありました。でも、それに気がつくことは、とても難しいことでした。この難しさは、コンテストに参加した人にしかわからないのではないかと思っています。
コンテストに参加して良い結果を出すこと、それを目指しています。だから、うまくいかなかったときは残念に思います。それでも、次のコンテストが開催される予定があって、またチャレンジすることができる、そのことがとてもうれしいのです。
失敗しても終わりじゃない。
だから私はまた参加したいと思います。次は良い結果を出すために。
これで、私の参加記は終了です。長い文章を最後まで読んでくださってありがとうございました。そして、少しでもヒューリスティックコンテストに興味を持ってくださったなら、次はぜひ一緒に私と参加しましょう。
18.最終結果（2022年11月22日）
2022年11月22日の朝です。システムテストが終わり、最終順位が出ていました。最終順位は、1117人中574位でした。暫定テストでは660位でしたので、暫定テスト時より86ほど順位が上がりました。
2000テストケースの絶対スコアと各テストケースの得点グラフです。
AtCoder - AHC016 (Hack to the Future 2023 Qual) - Graphorean - Statisticshttps://t.co/9XBPX6j5pC#AHC016 #HTTF
— Wladimir Leite (@wleite) 2022年11月22日
PS: I still need to review some details.
Heuristic Ratingは5上がり、1351になりました。
