ahc016　httf予選参加記

(ほとんどの人が)初めまして
uetaと申します。
電気機械系の大学院1年で研究はなぜか統計系統のことをやっています。

自分は競技プログラミングにはまっています。

ヒューリスティックは経験はなく、初心者レベルです。
今回は自分が考えたことやったことをまとめます。

今回の結果

初めての長期AHC

システムテスト後順位
349位でした。

正直言うともっと行きたかったですが、水色diffだったの結果だけ見れば満足です。

問題について

問題のリンクは下に貼っておきます。

初めて問題文を読んだときの感想は何を言っているのかわからないでした。

繰り返し読んでも理解できず、一度あきらめかけました。
pythonの基本コードがついていて、ようやく理解できました。

簡単にまとめると、
mとeが与えられる。

1. 適切なnを指定せよ

2. n点で作られるグラフをm個送れ

3-機械側. グラフをm個の中から一つ選び、eに従い点に誤差を加える、その後点をランダムに入れ替えて送ってくる

4. 元のグラフが何かを当てる

これで理解できるようになりました。
普段はpythonで書くのですが今回は実行時間を考えてc++に初挑戦しました。

そろそろ、c++で競プロやりたいなと思ったのでそうしました
というのも、pythonで実行時間が遅くてO(n^2*logn^2)が通らなくて
困っていました。
https://atcoder.jp/contests/abc274/tasks/abc274_f
ここら辺の問題が解けなかったので

1.はじめに考えたこと

最初にミス0ならどうなるか
色々、思案を巡らせたとき分割数が思い浮かんだ

分割数とは
例えば、４を分割するときにいくつに分解できる組み合わせがあるかを考えたときに
n=4
1・1・1・1
2・1・1
2・2
3・1
4

の5通りに分解が可能です。
n=5なら
1・1・1・1・1
2・1・1・1
2・2・1
3・1・1
3・2
4・1
5

の7通りに分解が可能です。

これでなら、unionfindで判別ができるなと考えました。
これは数字が増えると爆発的に数が増えるので
n=13で100を超えます。

列挙する方法ググって再帰関数の方法が見つかったので
そのまま使いました。

スタートダッシュと思いましたが、点が思うように上がりませんでした。

2. 辺の数だけで考えればうまくいく？

初めは分割数のコードをそのまま使っていた。
そうすると、エラー率が高いときにミスが多くなり点数が上がらない。
どうしようか？

辺の数 なら、評価が可能ではないかと考えた。

n=100とし、
i番目のグラフには

1/(m-1)*i　本

の辺をつける。

エラー率を用いると、おおよそ何本になるかがわかる。

例えば、m=10の時、n=100で行ったとすると

辺の数は全部で接続可能なのはn*(n-1)/2より4950本で
i(0<=i<=m-1)
i=0: 0本
i=1: 4950/91 = 550本
i=2: 4950/91 = 1100本
i=3: 4950/9*1 = 1650本
・・・

辺はeをもとに誤差が加えられるので、eとして

(送られてきたグラフの辺の数) =（送ったグラフの辺を持たない数)*e+（送ったグラフの辺を持っている数)*(1-e)

これが、帰ってきた、グラフの辺の数になる。

そのまま使っていいんだけど、今回は計算をして

(送られてきたグラフの辺を持つ数) =（送ったグラフの辺を持たない数)*e+（送ったグラフの辺を持っている数)*(1-e)

(送られてきたグラフの辺を持たない数) =（送ったグラフの辺を持たない数)*(1-e)+（送ったグラフの辺を持っている数)*e

これで求められそうだとなる。
これをとくと

q =x*(1-e)+y*e

p =x*e+y*(1-e)

これをxについて説くと

x = \frac{(1-e)*q-e*p}{1-2*e}

総本数はn*(n-1)/2より

x = \frac{(1-e)*q-e*(n*(n-1)/2-q)}{1-2*e}

これで元の値の期待値が求められる。
これで月曜に202位まで上げた。

ここから、適切なnを求めれば、かなり上位行けるのではないかと考えていた時もありました...

3. 分割数より小さくできない？

e=0の時がもっと小さくできないかを考えた。
例えば、

この[0,1,2]のペアって見分けられそうって、でもこれ全列挙するアルゴリズムってあるのかな？

ググりまくったけどなかったので手書きした。
3の時は2種類
4の時は6種類
5の時は19種類
6で60は超えそう？

これをやるとn=6ですべて網羅できるようになる。
各分割数ごとに、グラフの種類が倍増するので
もっと小さいnで実現可能
判別はまず、unionfindで組の数を見分ける。
その後、各グラフがどれに相当するかをあらかじめ手打ちしておいた、種類の情報で見分ける。
判別は各点の辺の接続数
接続数が同じものはdfs等を用いて貪欲に...

貪欲すぎる...

3. 最後のパラメータ設定

相対評価なので自分の点がどれくらいかわからなかった。
多分エラー率が低いところがいけないんだろうなと思ってはいたが、どう直せばいいのか見当がつかなかった。

これまでの方法を貫き通し最適なnに設定するしか思いつかなくて

mが91通り(10から100までの) e が40通り(0.01から0.4)のランダムな入力データを作って
nを4から100まで作って回した。

つまり、nが一つ当たり、4640通りあるので
全部で353,080個回したことになる。

x軸をm 、y軸をe,z軸をnは最も点が高いものnの値として図示した。
pythonのmatplolibを用いてgifを作成している。

力技であるが、これで何とか自分のhttfは終わった。

追記：　なぜ点が低いのか？

なぜ点が小さかったのか
それは簡単にまとめると、送れる情報量が小さかったからである。
また、エラーの影響をもろに受けるからである。

辺がないの時、eの値によって辺が作られる
辺があるの時、eの値によって辺が消される
このようにエラーが起こる。

辺の本数が少ないほど、多いほうに変化する。
また、辺の本数が多いほど、少ないほうに変化する。
下の図は辺が0本の時のn = 10, e=0.4における本数の期待値である。

n = 100, e = 0.4, m=5
mを本数を等しく配置すると

まだギリギリ判別可能そう？
n = 100, e = 0.4, m=50

これだと判別難しいわ...!

グラフの辺情報のみしか使えていないというのは、本来であればグラフとして大きく異なるものでも
辺の本数が同じであれば扱いが同じになってしまうことを意味しています。

グラフとしての情報を送ることができればよかったな。

終わり

これで点は4.8 十億点 349位となった。

youtubeに上がっているhttfの解説動画をみて感動した。
この後真似して作ってみたいと思う。