HACK TO THE FUTURE 2023 予選 参加記
参加記というよりは解法の紹介が主になりそう。まあいいか。
競技プログラミングをやっている人は「やったこと」の項まで読み飛ばしてください。
HTTFとは
フューチャー(株)が主催するプログラミングコンテストです。（ハッシュタグ: #HTTF ）
競技プログラマーの未来を技術力で”HACK”してほしいという意味を大会名に込め、今年で6回目の開催となります。
だそうです。
これはプログラミングコンテストの中でもヒューリスティックスとかマラソンとか言われるやつで、スコアアタック的なものだと考えてもらえば良いです。今回はいい感じの暗号を考える問題でした（かっ、かっこいい～～！！）。
問題文（引用は一部抜粋）：A - Graphorean (atcoder.jp)
数値を一度グラフに変換(エンコード)して送信し、送られてきたグラフを数値に戻す(デコード)作業が必要である。 マシンでグラフを送ると、頂点番号の情報は失われ、更にノイズが入ってしまうため、正しく数値が復元できるように、エンコード・デコードの仕方を工夫しなければならない。
日記
一日目：$${e=0.00}$$のケースを確実に通るコードを書く。
二日目：最終的な解法の原型を書く。
三日目～六日目：パラメータをいじいじして大量提出する。
七日目：さすがに伸びなくなってきたので改善を加える。出力するグラフの種類を試しに増やしてみる。逆に悪化する。
八日目：やる気消滅。
九日目：最初の解法に立ち返って、出力するグラフを大きく分けて２種類に絞ってみる。スコアが上がり、やる気復活。
十日目：細かいところを調整する。
やったこと
概要
おおまかには以下の２行で説明できます。
次数の分布が偏ったグラフを生成する。
次数の期待値から与えられたグラフの添え字を予想する。
エンコードの手法
ジャッジに渡す用のグラフを、以下の２種類の方法で生成しました。
頂点０から順に次数を$${N}$$にしていく（$${G=111\dots 111000\dots 000}$$ にする）。
大きめのクリークを作る（$${G=000\dots 000111\dots 111}$$ にする）。
どっちを使えば良いかはわからなかったので、適当にシャッフルして渡しました。ここら辺をもう少し詰められるとスコアが上がるんだろうなあ、と思いつつもそこまでやる気力がありませんでした。
デコードの手法
次数が$${D}$$の頂点について、ノイズが入ったときの次数の期待値は次式で表すことができます。
$$
D(1-e)+(N-1-D)e
$$
これは期待値の線形性を用いて説明することができます。各辺について、
ノイズが入る前に「ある」ならば、次数の期待値への寄与は$${1-e}$$、
ノイズが入る前に「ない」ならば、次数の期待値への寄与は$${e}$$
なので、これに「ある」「ない」辺のそれぞれの本数をかけてやれば良いわけです。下記リンクの「応用例２」と考え方が似ていますね。
期待値の線形性の分かりやすい説明：和の期待値は期待値の和 | 高校数学の美しい物語 (manabitimes.jp)
さて、復号の手法ですが、かなりシンプルです。
$${G_i}$$の各頂点の次数の期待値を昇順にソートしたものを$${dg_{i,0}, dg_{i, 1}, \cdots, dg_{i, N-1}}$$、$${H}$$の各頂点の次数を昇順にソートしたものを$${dh_{0}, dh_{1}, \cdots, dh_{N-1}}$$として、
$$
\sum_{v=0}^{N-1} |dg_{i,v}-dh_v|^{3}
$$
が最小になる$${i}$$を出力します。
実装
さっきの説明以外に$${N}$$の決定や$${e=0.00}$$の特殊ケースを付け足して２００行くらいです。
提出コード (c++)：https://atcoder.jp/contests/ahc016/submissions/36689123
あとがき
軽めの実装でそこそこ良い点を得られて運がよかったな～、という感じです。深いところまで詰められなかったのは反省点。
「良くない点を改善して、パフォーマンスを高めていく」というマラソンの醍醐味がなんとなくわかった気がします。株式会社フューチャー様、ありがとう────。
気軽にクリエイターの支援と、記事のオススメができます！