見出し画像

HACK TO THE FUTURE 2023 予選 参加記

ripity

参加記というよりは解法の紹介が主になりそう。まあいいか。

競技プログラミングをやっている人は「やったこと」の項まで読み飛ばしてください。

HTTFとは

フューチャー(株)が主催するプログラミングコンテストです。(ハッシュタグ: #HTTF )
競技プログラマーの未来を技術力で”HACK”してほしいという意味を大会名に込め、今年で6回目の開催となります。
https://atcoder.jp/contests/ahc016 より

だそうです。

これはプログラミングコンテストの中でもヒューリスティックスとかマラソンとか言われるやつで、スコアアタック的なものだと考えてもらえば良いです。今回はいい感じの暗号を考える問題でした(かっ、かっこいい~~!!)。

問題文(引用は一部抜粋):A - Graphorean (atcoder.jp)

数値を一度グラフに変換(エンコード)して送信し、送られてきたグラフを数値に戻す(デコード)作業が必要である。 マシンでグラフを送ると、頂点番号の情報は失われ、更にノイズが入ってしまうため、正しく数値が復元できるように、エンコード・デコードの仕方を工夫しなければならない。
https://atcoder.jp/contests/ahc016/tasks/ahc016_a より

日記

一日目:$${e=0.00}$$のケースを確実に通るコードを書く。

二日目:最終的な解法の原型を書く。

三日目~六日目:パラメータをいじいじして大量提出する。

七日目:さすがに伸びなくなってきたので改善を加える。出力するグラフの種類を試しに増やしてみる。逆に悪化する。

八日目:やる気消滅。

九日目:最初の解法に立ち返って、出力するグラフを大きく分けて2種類に絞ってみる。スコアが上がり、やる気復活。

十日目:細かいところを調整する。

やったこと

概要

おおまかには以下の2行で説明できます。

  • 次数の分布が偏ったグラフを生成する。

  • 次数の期待値から与えられたグラフの添え字を予想する。

エンコードの手法

ジャッジに渡す用のグラフを、以下の2種類の方法で生成しました。

  • 頂点0から順に次数を$${N}$$にしていく($${G=111\dots 111000\dots 000}$$ にする)。

  • 大きめのクリークを作る($${G=000\dots 000111\dots 111}$$ にする)。

どっちを使えば良いかはわからなかったので、適当にシャッフルして渡しました。ここら辺をもう少し詰められるとスコアが上がるんだろうなあ、と思いつつもそこまでやる気力がありませんでした。

デコードの手法

次数が$${D}$$の頂点について、ノイズが入ったときの次数の期待値は次式で表すことができます。

$$
D(1-e)+(N-1-D)e
$$

これは期待値の線形性を用いて説明することができます。各辺について、

  • ノイズが入る前に「ある」ならば、次数の期待値への寄与は$${1-e}$$、

  • ノイズが入る前に「ない」ならば、次数の期待値への寄与は$${e}$$

なので、これに「ある」「ない」辺のそれぞれの本数をかけてやれば良いわけです。下記リンクの「応用例2」と考え方が似ていますね。

期待値の線形性の分かりやすい説明:和の期待値は期待値の和 | 高校数学の美しい物語 (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}$$の特殊ケースを付け足して200行くらいです。

提出コード (c++):https://atcoder.jp/contests/ahc016/submissions/36689123

あとがき

軽めの実装でそこそこ良い点を得られて運がよかったな~、という感じです。深いところまで詰められなかったのは反省点。

「良くない点を改善して、パフォーマンスを高めていく」というマラソンの醍醐味がなんとなくわかった気がします。株式会社フューチャー様、ありがとう────。

この記事が気に入ったら、サポートをしてみませんか?
気軽にクリエイターの支援と、記事のオススメができます!