AHC016

グラフへの理解を求められていた?苦しかった。あとビジュアライザから得られる情報が少なかったのも辛かったかも… クリークについて、最後思いついたところまで行ったのでいずれもう少し解き進めたい。 ~~パソコン修理中なのでいずれ清書したい…はてなでLatexをうまく書けないので直します！~~ (2022/11/24清書しました！)

問題文

$M$ 個のグラフ(頂点数 $N$ )を作り、出力する。

以下のクエリに100回答える。「出力したグラフの中から1つが選ばれ、辺が繋がっているかどうかが $\epsilon$ の確率で反転され、頂点番号がシャッフルされる。変換される前のグラフはどれかを答えよ。」

答えが間違っていた回数を $E$ として $round\big(10^{9}\times \frac{0.9^{E}}{N} \big)$ を暫定スコアとし、各ケースごとに $round \big(10^{9} \times \frac{暫定スコア}{全参加者中最高の暫定スコア} \big)$ を求め得点とする。

グラフの変換について

グラフの変換の理解がイマイチなので、ビジュアライザを読んでみる。以下はtools/src/bin/tester.rsの46~63行目にコメントを入れたもの

01文字列の受け取り

    let mut gs = vec![];
    for k in 0..input.M {
        let g = read(&mut stdout)?; // 出力された01文字列を受け取る
        let cs = g.chars().collect::<Vec<_>>(); // 扱いやすいようにVec<char>に変換
        if cs.len() != N * (N - 1) / 2 || cs.iter().any(|&c| c != '0' && c != '1') {
            // 01文字列の長さがN*(N-1)/2でなかったり、01以外の文字を含んでいる場合エラー
            return Err(format!("Illegal output (g_{}): {}", k, g));
        }
        let mut g = mat![false; N; N]; // 変換後のグラフ(隣接行列)
        let mut p = 0; // cs(01文字列)をどこまで読み進めたか？
        for i in 0..N {
            for j in i + 1..N {
                // この2重for文で辞書順に(i, j)の組を全探索
                g[i][j] = cs[p] == '1'; // cs[p]が1ならtrue, 0ならfalse
                g[j][i] = g[i][j]; // 無向グラフなので反対側も同様にする
                p += 1;
            }
        }
        gs.push(g);
    }

$G_{s_k}$ から $H_k$ への変換

64~90行目にコメントを入れたもの

    let mut rng = rand_chacha::ChaCha20Rng::seed_from_u64(input.seed);
    let mut E = 0;
    let mut result = String::new();
    for k in 0..Q {
        let mut vs = (0..N).collect::<Vec<_>>();  // 頂点番号をもった配列を初期化
        vs.shuffle(&mut rng);
        let s = input.ss[k]; // 正解の番号
        let mut h = String::new();
        for i in 0..N {
            for j in i + 1..N {
                if gs[s][vs[i]][vs[j]] ^ rng.gen_bool(input.eps) {
                    // エラー率epsilonの確率で辺をもつかどうかが反転
                    h.push('1');
                } else {
                    h.push('0');
                }
            }
        }
        let _ = writeln!(stdin, "{}", h);
        let _ = stdin.flush();
        let t = read_usize(&mut stdout, 0, input.M - 1)?; // 判定した番号
        if s != t {
            E += 1;
            result.push('x');
        } else {
            result.push('o');
        }
    }

もとは同じグラフでも、クエリが違えば違うグラフが生成されるということがわかりますね。
具体例
7頂点を持つ完全グラフをひとつ、辺のない頂点を4つもつグラフ（下図中央）
頂点番号を失い、ノイズが加わったグラフ(下図左)
点線の辺がノイズによって失われた辺、青い辺がノイズによって加えられた辺です。

得点について

$round\big(10^{9}\times \frac{0.9^{E}}{N} \big)$ Nを増やしてでも言い当てる確率を上げたほうが得か？
E(誤答)を増やしてしまっでもNを減らしたほうが得か？

これをみるとNが40を超えると減り方がなだらかになる
(逆に、Nを40以下にするとEが多少増えても点数が増加する？)
正答率80％ぐらいを目指さないと全然点数が上がらないことがわかる
この図の正しい見方を教えてくれ……

相対評価について

$round \big(10^{9} \times \frac{暫定スコア}{全参加者中最高の暫定スコア} \big)$

アイデア

サンプルと同じように辺の個数で判定→ボツ

$ N=100 $とかにすれば辺の個数を0 ~ 4950まで持てるから多少ノイズが乗っても大丈夫？否、でも$N$を大きくすればするほどノイズの影響も大きくなってしまう $\epsilon = 0.40$なら4950*0.4で2000個くらい増減する逆に、$N$をできる限り小さくした場合そこそこの点数が出る(114191306点)

連結成分の大きさで判定→ボツ

頂点を0から順番にi個ずつ連結したグラフを作る。判定の際には各頂点からDFSし、連結成分の頻度を求め、一番多く存在する連結成分の大きさが答え。これはうまくいかない。まずN>=MのNの設定が必要だし、連結成分どうしが簡単につながるので全く正解できない。つらい。

24番目のグラフは本来大きさ24の連結成分が3個あるはずなんだけど、ノイズのせいで全部つながっちゃっているので、判定で75になっている、の図もし頂点シャッフルがなければ、区切りになっている非連結な部分から判定できそうだけど…

$\epsilon$ が低い時だけ頑張る

ABC232Cを参考に同型グラフの判定を行う $N=4$ で11個、 $N=5$ で34個、 $N=6$ で100個以上の同型でないグラフが得られる

10億点ぴったしのスコアは $\epsilon = 0.00$ のときのみ答えた場合のスコア

グラフの特徴量

連結成分(大きさ)→ノイズに弱そう
連結成分(数)→ある大きさ以下を排除したらある程度ノイズに耐えそう？
連結成分(直径)→ノイズに弱そう
連結成分(形)→表現方法は？連結成分の直径を求め、端から端までの次数のリストで表現？
閉路の数→ノイズに弱そう
次数→BTreeMap
辺の数
~~頂点数~~
~~自己辺の数~~今回ひけない

グラフの直径の求め方

適当な点から最遠の頂点を求め、その頂点（V1とする）からまたBFSしてみつけた最遠の点V2までの距離

以下日記

11/11

コロナ療養明け。明日やっと外の空気吸える。開催直前にパソコン壊される。問題文読解。

11/12

パソコンの修理、全然予約取れず…しかも1〜2週間預かりになりそう
エラー率で場合わけ? とりあえずビジュアライザ読むか… とりあえず問題文通りのことはできそう

11/13

まずは提出。エラー率/0.08(この数字は勘)の分バッファを持たせて辺の数で答える、でもめっちゃ点数低い、多分外しまくってるノイズに強いグラフを作らなければ…

例えばグラフの領域いっぱいまで連結成分i個のグラフを敷き詰めるとかなかなかバグって提出できない

エラー0.4でどんな感じになるか実験必要

ローカル環境つくらなければ 01文字列からグラフに変換する関数 →作った

11/14

めっちゃ仕事忙しくて泣く。連結成分の大きさiのグラフを敷き詰める作戦、なんかうまく行かないエラー率0なのに狂う。これ、問題文を理解できていない？？→DFSがバグっていた。でも連結成分の大きさiの作戦だとNが100必要。詰んだ。
あとNが100だとエラー0.01でもめちゃくちゃ狂う。特に連結成分の大きさ、簡単に全部つながるので全く正解できない。つらい。 24番目のグラフは本来大きさ24の連結成分が3個あるはずなんだけど、ノイズのせいで全部つながっちゃっているので、判定で75になっている、の図

11/15

もうグラフの作り方を考えるんじゃなくてランダムにグラフつくって特徴量の近いグラフを探せばいいんじゃないかって思えてきたまず思いつく特徴量を100回試行でどれがどんだけばらけるか、実験してみよう

11/16

グラフの構造体、特徴量を求める関数を実装する。バグりまくって苦しい。
グラフの直径を求めて経路復元するのなんてきっと緑diffとかなのに辛い。
解決策はわかっている、テストを書くことだ。オンラインジャッジに頼らないことだ。
心の中のえびちゃん先生に睨まれている。
$\frac {N \times (N-1)}2 \ge M$ をみたす最小の $N$ を設定し、グラフの番号=辺の本数とする提出をしてとりあえず得点をとる。準備していることは進まない。

11/17

焦り始める。 0番目のグラフの01文字列を全て0に、1番目のグラフの01文字列を全て1にして、それ以降のグラフは今までのグラフとの差異の最小値が大きくなるようにランダム01文字列から山登りして作成

11/18

明日macちゃんを修理に出すのでほぼ最終日。やばい。
次数はUFで初期化する時に調べたほうが早そうなので実装したい。あとN=4で11個、N=5の時点で34個グラフ作れるのでN=6で100個ぐらい作れるんじゃない？ローカルで100個同型じゃないグラフを作れば $\epsilon = 0.00$ のとき完全攻略できるんじゃね？さっそくやってみた、点数改善！でもこれきっとみんな思いついているやつだな…点数の上がり方に対して順位の上がり方が微妙

完全グラフの性質を使ってみる？直径1の連結成分の頂点数だけ信用することにして直径が2以上の連結成分はトリミングする？(次数の少ない頂点を消す) それとも密なグラフの個数で割る？完全グラフが2つつながってたら1個にするイメージ？

11/19

ノイズ、強すぎぃ… ここでパソコンがドナドナされたので試合終了。くやしー！

こんなかんじでした

センターマン！https://t.co/xSHN8qB2S4 pic.twitter.com/aDvJnx4a0b
— ainem (@ainemixion) 2022年11月22日

あいねむの競プロ雑記

AHC016参戦記

AHC016