提出 #36658214

---

ソースコード 拡げる

#![allow(non_snake_case)]

use itertools::Itertools;
use proconio::{source::line::LineSource, *};
use rand::prelude::*;
use std::{
    collections::HashMap,
    io::{prelude::*, BufReader, Stdin},
};

fn main() {
    get_time();
    let mut stdin = proconio::source::line::LineSource::new(std::io::BufReader::new(std::io::stdin()));
    let input = read_input(&mut stdin);
    if input.eps == 0.0 {
        solve_exact(&input, stdin);
    } else {
        let e = (input.eps * 100.0).round() as usize - 1;
        let m = (input.M - 8) / 3;
        let (ty, N) = STRATEGY[e][m];
        eprintln!("type = {}, N = {}", ty, N);
        if ty == 0 {
            solve_small(&input, stdin, N);
        } else {
            solve_large(&input, stdin, N);
        }
    }
    eprintln!("Time = {:.3}", get_time());
}

/// eps=0 用。
/// 完全一致を調べるだけ。
fn solve_exact(input: &Input, mut stdin: LineSource<BufReader<Stdin>>) {
    let N = if input.M <= 11 {
        4
    } else if input.M <= 34 {
        5
    } else {
        6
    };
    let mut G = vec![];
    find_all_graphs(&mut mat![false; N; N], 0, 1, &mut G);
    G.truncate(input.M);
    println!("{}", N);
    for k in 0..input.M {
        println!("{}", G[k]);
    }
    std::io::stdout().flush().unwrap();
    let mut map = HashMap::new();
    for k in 0..input.M {
        for g in find_all_perms(&str_to_graph(&G[k], N)) {
            map.insert(g, k);
        }
    }
    for _ in 0..Q {
        input! {
            from &mut stdin,
            h: String
        }
        let id = u64::from_str_radix(&h, 2).unwrap();
        println!("{}", map[&id]);
        std::io::stdout().flush().unwrap();
    }
}

/// 頂点数Nのラベルなしグラフを全列挙する
fn find_all_graphs(g: &mut Vec<Vec<bool>>, i: usize, j: usize, list: &mut Vec<String>) {
    let N = g.len();
    if i == N {
        let mut vs = (0..N).collect::<Vec<_>>();
        'lp: while next_permutation(&mut vs) {
            for i in 0..N {
                for j in 0..N {
                    if g[vs[i]][vs[j]] > g[i][j] {
                        continue 'lp;
                    } else if g[vs[i]][vs[j]] < g[i][j] {
                        return;
                    }
                }
            }
        }
        list.push(graph_to_str(g));
    } else if j == N {
        find_all_graphs(g, i + 1, i + 2, list);
    } else {
        find_all_graphs(g, i, j + 1, list);
        g[i][j] = true;
        g[j][i] = true;
        find_all_graphs(g, i, j + 1, list);
        g[i][j] = false;
        g[j][i] = false;
    }
}

/// グラフの頂点に番号を降った隣接行列表現を全列挙する
fn find_all_perms(g: &Vec<Vec<bool>>) -> Vec<u64> {
    let N = g.len();
    let mut vs = (0..N).collect::<Vec<_>>();
    let mut list = vec![];
    loop {
        let mut id = 0u64;
        for i in 0..N {
            for j in i + 1..N {
                id <<= 1;
                if g[vs[i]][vs[j]] {
                    id |= 1;
                }
            }
        }
        list.push(id);
        if !next_permutation(&mut vs) {
            break;
        }
    }
    list.sort();
    list.dedup();
    list
}

/// epsが小さい時用。
/// P(G[s]|H)=P(H|G[s])P(G[s])/P(H)~P(H|G[s]) なので、
/// G[s]からHが生成される確率P(H|G[s])が一番高いもとを選択するのが理論的に最適。
/// Nが小さい場合はこれが厳密に計算出来るので厳密計算して一番高いsを求める。
fn solve_small(input: &Input, mut stdin: LineSource<BufReader<Stdin>>, N: usize) {
    let mut G = vec![];
    for g in get_repr(input.eps, input.M, N) {
        G.push(int_to_graph(g, N));
    }
    println!("{}", N);
    for k in 0..input.M {
        println!("{}", graph_to_str(&G[k]));
    }
    std::io::stdout().flush().unwrap();

    // 2つのラベル付きGとHで異なる辺の個数をd(G,H)と表すと、
    // P(H|G)~Σ_π(ε^d(π(G),H)×(1-ε)^(N(N-1)/2-d(π(G),H)))
    // と計算できるので、予めπ(G)を列挙しておく(高速化のため重複は除去)
    let mut perms = vec![];
    for k in 0..input.M {
        perms.push(find_all_perms(&G[k]));
    }
    let mut es = vec![0.0; N * (N - 1) / 2 + 1];
    for i in 0..es.len() {
        es[i] = input.eps.powi(i as i32) * (1.0 - input.eps).powi((N * (N - 1) / 2 - i) as i32);
    }
    for _ in 0..Q {
        input! {
            from &mut stdin,
            h: String
        }
        let id = u64::from_str_radix(&h, 2).unwrap();
        let mut t = 0;
        let mut max = 0.0;
        for k in 0..input.M {
            let mut sum = 0.0;
            for &g in &perms[k] {
                sum += es[(g ^ id).count_ones() as usize];
            }
            if max.setmax(sum / perms[k].len() as f64) {
                t = k;
            }
        }
        println!("{}", t);
        std::io::stdout().flush().unwrap();
    }
}

// epsが大きい時用。
// ベースとなる頂点数5のグラフをM個用意し、それをD倍に冗長化する。
// 焼き鈍しでHの頂点のクラスタリングをして1/D倍に縮小し、各ベースグラフとの一致具合を調べる。
// D倍にするとベースグラフの頂点を孤立点にするかクリークにするかの選択肢も生じるため、ベースグラフは自己閉路ありとしている。
fn solve_large(input: &Input, mut stdin: LineSource<BufReader<Stdin>>, D: usize) {
    const N1: usize = 5;
    let N = N1 * D;
    let bases = get_bases(input.eps, input.M);
    let mut adjust = vec![];
    let mut G = vec![];
    for &b in &bases {
        let mut h = mat![false; N; N];
        let mut p = 0;
        let mut tmp = vec![0; N1];
        for i in 0..N1 {
            for j in i..N1 {
                if b >> p & 1 != 0 {
                    tmp[i] |= 1 << j;
                    tmp[j] |= 1 << i;
                    for x in 0..D {
                        for y in 0..D {
                            if i * D + x != j * D + y {
                                h[i * D + x][j * D + y] = true;
                                h[j * D + y][i * D + x] = true;
                            }
                        }
                    }
                }
                p += 1;
            }
        }
        G.push(h);
        tmp.sort();
        // 同じ行がある場合にグループ化の自由度が上る分だけHを生成できる確率が高くなるのでその補正
        let mut s = 0;
        let mut add = 0.0;
        while s < N1 {
            let mut t = s;
            while t < N1 && tmp[t] == tmp[s] {
                t += 1;
            }
            for i in 2..=(t - s) * D {
                add += f64::ln(i as f64);
            }
            for i in 2..=(t - s) {
                add -= f64::ln(i as f64);
            }
            s = t;
        }
        // そのまま足すと大きすぎたので0.5倍している
        adjust.push(add * 0.5);
    }
    println!("{}", N);
    for k in 0..input.M {
        println!("{}", graph_to_str(&G[k]));
    }
    std::io::stdout().flush().unwrap();
    let mut perms = vec![];
    for k in 0..input.M {
        let mut vs = (0..N1).collect::<Vec<_>>();
        let mut list = vec![];
        loop {
            let mut p = 0;
            let mut g = mat![false; N1; N1];
            for i in 0..N1 {
                for j in i..N1 {
                    if bases[k] >> p & 1 != 0 {
                        g[vs[i]][vs[j]] = true;
                        g[vs[j]][vs[i]] = true;
                    }
                    p += 1;
                }
            }
            let mut id = 0;
            p = 0;
            for i in 0..N1 {
                for j in i..N1 {
                    if g[i][j] {
                        id |= 1 << p;
                    }
                    p += 1;
                }
            }
            list.push(id);
            if !next_permutation(&mut vs) {
                break;
            }
        }
        list.sort();
        list.dedup();
        perms.push(list);
    }

    let mut rng = rand_pcg::Pcg64Mcg::seed_from_u64(432908);
    let stime = get_time();
    for q in 0..Q {
        input! {
            from &mut stdin,
            h: String
        }
        let H = str_to_graph(&h, N);
        let until = stime + (4.95 - stime) * (q + 1) as f64 / Q as f64;
        let t = estimate(input.eps, input.M, D, N1, &perms, &adjust, H, until, &mut rng);
        println!("{}", t);
        std::io::stdout().flush().unwrap();
    }
}

/// P(H|G[s])を計算するために全ての置換を試すわけにはいかないため、
/// 5つのグループへの頂点の分割を何通りか計算し、グループの置換を全通り試す。
/// 分割を決める問題がmin(x,c-x)の和の最小化という形で非常に非凸度が高く、一発で最適解に到達するのが困難なため、
/// 初期解を別の焼き鈍し易い形の問題を解くことで得て、そこから再度焼き鈍している。
fn estimate(
    eps: f64,
    M: usize,
    D: usize,
    N1: usize,
    perms: &Vec<Vec<i32>>,
    adjust: &Vec<f64>,
    H: Vec<Vec<bool>>,
    until: f64,
    rng: &mut rand_pcg::Pcg64Mcg,
) -> usize {
    let N = N1 * D;
    let rep = 15.0;
    // 確率が非常に小さくなるため、logを取って計算する
    let ln1 = f64::ln(1.0 - eps);
    let ln2 = f64::ln(eps);
    let mut probs = vec![std::f64::NEG_INFINITY; M];
    while get_time() < until {
        // 一段階目の焼き鈍し
        // グループ内の各ベクトルのハミング距離の和を最小化
        let mut h = vec![0u128; N];
        for i in 0..N {
            for j in 0..N {
                if H[i][j] {
                    h[i] |= 1 << j;
                }
            }
        }
        let mut diff = mat![0; N; N];
        for i in 0..N {
            for j in 0..N {
                diff[i][j] = (h[i] ^ h[j]).count_ones() as i32;
            }
        }
        let mut ps = vec![!0; N];
        for i in 0..N {
            ps[i] = i / D;
        }
        let mut vs = vec![vec![]; N1];
        for i in 0..N {
            vs[ps[i]].push(i);
        }
        let mut crt = 0;
        for i in 0..N1 {
            for a in 0..D {
                for b in a + 1..D {
                    crt += diff[vs[i][a]][vs[i][b]];
                }
            }
        }
        let mut best = crt;
        let mut best_ps = ps.clone();
        let stime = get_time();
        let TL = 0.01 / rep;
        let T0: f64 = (N * D) as f64;
        let T1: f64 = 1.0;
        let mut T = T0;
        for iter in 0.. {
            if iter & 31 == 0 {
                let t = (get_time() - stime) / TL;
                if t >= 1.0 {
                    break;
                }
                T = T0.powf(1.0 - t) * T1.powf(t);
            }
            let i = rng.gen_range(0, N1);
            let j = rng.gen_range(0, N1);
            if i == j {
                continue;
            }
            let a = rng.gen_range(0, D);
            let b = rng.gen_range(0, D);
            let mut next = crt;
            for c in 0..D {
                if c != a {
                    next -= diff[vs[i][a]][vs[i][c]];
                    next += diff[vs[j][b]][vs[i][c]];
                }
                if c != b {
                    next -= diff[vs[j][b]][vs[j][c]];
                    next += diff[vs[i][a]][vs[j][c]];
                }
            }
            if crt >= next || rng.gen_bool(f64::exp((crt - next) as f64 / T)) {
                crt = next;
                let tmp = vs[i][a];
                vs[i][a] = vs[j][b];
                vs[j][b] = tmp;
                if best.setmin(crt) {
                    for k in 0..N1 {
                        for h in 0..D {
                            best_ps[vs[k][h]] = k;
                        }
                    }
                }
            }
        }
        ps = best_ps;

        // ニ段階目の焼き鈍し
        // 各ブロックごとに0と1の近い方までの距離の和を最小化
        let mut H2 = mat![0; N; N1];
        let mut count = mat![0; N1; N1];
        for i in 0..N {
            for j in i + 1..N {
                if H[i][j] {
                    count[ps[i].min(ps[j])][ps[i].max(ps[j])] += 1;
                    H2[i][ps[j]] += 1;
                    H2[j][ps[i]] += 1;
                }
            }
        }
        let mut crt = 0;
        for i in 0..N1 {
            for j in i..N1 {
                let m = if i == j { D * (D - 1) / 2 } else { D * D } as i32;
                crt += count[i][j].min(m - count[i][j]);
            }
        }
        let mut best = crt;
        let mut best_ps = ps.clone();
        let stime = get_time();
        let TL = 0.03 / rep;
        // 良い感じの初期解があるので温度は低め
        let T0: f64 = 5.0;
        let T1: f64 = 1.0;
        let mut T = T0;
        for iter in 0.. {
            if iter & 31 == 0 {
                let t = (get_time() - stime) / TL;
                if t >= 1.0 {
                    break;
                }
                T = T0.powf(1.0 - t) * T1.powf(t);
            }
            let i = rng.gen_range(0, N);
            let j = rng.gen_range(0, N);
            if ps[i] == ps[j] {
                continue;
            }
            for k in 0..N1 {
                count[ps[i].min(k)][ps[i].max(k)] -= H2[i][k];
                count[ps[j].min(k)][ps[j].max(k)] -= H2[j][k];
            }
            if H[i][j] {
                count[ps[j].min(ps[i])][ps[j].max(ps[i])] += 1;
            }
            ps.swap(i, j);
            for k in 0..N1 {
                count[ps[i].min(k)][ps[i].max(k)] += H2[i][k];
                count[ps[j].min(k)][ps[j].max(k)] += H2[j][k];
            }
            if H[i][j] {
                count[ps[i].min(ps[j])][ps[i].max(ps[j])] += 1;
                count[ps[i]][ps[i]] -= 1;
                count[ps[j]][ps[j]] -= 1;
            }
            let mut next = 0;
            for i in 0..N1 {
                for j in i..N1 {
                    let m = if i == j { D * (D - 1) / 2 } else { D * D } as i32;
                    next += count[i][j].min(m - count[i][j]);
                }
            }
            if crt >= next || rng.gen_bool(f64::exp((crt - next) as f64 / T)) {
                crt = next;
                if best.setmin(crt) {
                    best_ps = ps.clone();
                }
                for k in 0..N {
                    if H[i][k] {
                        H2[k][ps[j]] -= 1;
                        H2[k][ps[i]] += 1;
                    }
                    if H[j][k] {
                        H2[k][ps[i]] -= 1;
                        H2[k][ps[j]] += 1;
                    }
                }
            } else {
                for k in 0..N1 {
                    count[ps[i].min(k)][ps[i].max(k)] -= H2[i][k];
                    count[ps[j].min(k)][ps[j].max(k)] -= H2[j][k];
                }
                if H[i][j] {
                    count[ps[i].min(ps[j])][ps[i].max(ps[j])] -= 1;
                    count[ps[i]][ps[i]] += 1;
                    count[ps[j]][ps[j]] += 1;
                }
                ps.swap(i, j);
                for k in 0..N1 {
                    count[ps[i].min(k)][ps[i].max(k)] += H2[i][k];
                    count[ps[j].min(k)][ps[j].max(k)] += H2[j][k];
                }
                if H[i][j] {
                    count[ps[j].min(ps[i])][ps[j].max(ps[i])] -= 1;
                }
            }
        }
        ps = best_ps;

        let mut count = mat![0; N1; N1];
        for i in 0..N {
            for j in i + 1..N {
                if H[i][j] {
                    count[ps[i].min(ps[j])][ps[i].max(ps[j])] += 1;
                }
            }
        }
        // G[k]の各置換に対してHの生成確率を計算
        for k in 0..M {
            let mut sum = std::f64::NEG_INFINITY;
            for &g in &perms[k] {
                let mut prob = 0.0;
                let mut p = 0;
                for i in 0..N1 {
                    for j in i..N1 {
                        let c = count[i][j];
                        let m = if i == j { D * (D - 1) / 2 } else { D * D };
                        if g >> p & 1 != 0 {
                            prob += c as f64 * ln1 + (m - c) as f64 * ln2;
                        } else {
                            prob += (m - c) as f64 * ln1 + c as f64 * ln2;
                        }
                        p += 1;
                    }
                }
                sum = ln_add_exp(sum, prob);
            }
            probs[k] = ln_add_exp(probs[k], sum + adjust[k] - (perms[k].len() as f64).ln());
        }
    }
    let mut t = 0;
    for k in 0..M {
        if probs[t] < probs[k] {
            t = k;
        }
    }
    t
}

// 入出力と得点計算

const Q: usize = 100;

#[derive(Clone, Debug)]
struct Input {
    M: usize,
    eps: f64,
}

fn read_input(f: &mut LineSource<BufReader<Stdin>>) -> Input {
    input! {
        from f,
        M: usize, eps: f64
    }
    Input { M, eps }
}

fn str_to_graph(s: &str, N: usize) -> Vec<Vec<bool>> {
    let s = s.chars().collect::<Vec<_>>();
    let mut g = mat![false; N; N];
    let mut p = 0;
    for i in 0..N {
        for j in i + 1..N {
            if s[p] == '1' {
                g[i][j] = true;
                g[j][i] = true;
            }
            p += 1;
        }
    }
    g
}

fn int_to_graph(s: u64, N: usize) -> Vec<Vec<bool>> {
    str_to_graph(&format!("{:01$b}", s, N * (N - 1) / 2), N)
}

fn graph_to_str(g: &Vec<Vec<bool>>) -> String {
    let N = g.len();
    let mut s = String::new();
    for i in 0..N {
        for j in i + 1..N {
            s.push(if g[i][j] { '1' } else { '0' });
        }
    }
    s
}

// ここからライブラリ

pub trait SetMinMax {
    fn setmin(&mut self, v: Self) -> bool;
    fn setmax(&mut self, v: Self) -> bool;
}
impl<T> SetMinMax for T
where
    T: PartialOrd,
{
    fn setmin(&mut self, v: T) -> bool {
        *self > v && {
            *self = v;
            true
        }
    }
    fn setmax(&mut self, v: T) -> bool {
        *self < v && {
            *self = v;
            true
        }
    }
}

#[macro_export]
macro_rules! mat {
	($($e:expr),*) => { vec![$($e),*] };
	($($e:expr,)*) => { vec![$($e),*] };
	($e:expr; $d:expr) => { vec![$e; $d] };
	($e:expr; $d:expr $(; $ds:expr)+) => { vec![mat![$e $(; $ds)*]; $d] };
}

pub fn get_time() -> f64 {
    static mut STIME: f64 = -1.0;
    let t = std::time::SystemTime::now().duration_since(std::time::UNIX_EPOCH).unwrap();
    let ms = t.as_secs() as f64 + t.subsec_nanos() as f64 * 1e-9;
    unsafe {
        if STIME < 0.0 {
            STIME = ms;
        }
        // ローカル環境とジャッジ環境の実行速度差はget_timeで吸収しておくと便利
        #[cfg(feature = "local")]
        {
            (ms - STIME) * 1.3
        }
        #[cfg(not(feature = "local"))]
        {
            ms - STIME
        }
    }
}

pub fn next_permutation<T>(a: &mut [T]) -> bool
where
    T: PartialOrd,
{
    let n = a.len();
    for i in (1..n).rev() {
        if a[i - 1] < a[i] {
            let mut j = n - 1;
            while a[i - 1] >= a[j] {
                j -= 1;
            }
            a.swap(i - 1, j);
            a[i..n].reverse();
            return true;
        }
    }
    a.reverse();
    false
}

/// ln(exp(a)+exp(b))
fn ln_add_exp(a: f64, b: f64) -> f64 {
    if a < b {
        ln_add_exp(b, a)
    } else {
        a + (b - a).exp().ln_1p()
    }
}

// ここから前計算データ

#[rustfmt::skip]
/// 各epsとM(3刻み)のペアについて、どの方式とNのサイズを使うとよいかを予め決めておいたもの
/// 方式0(solve_small): 小さいeps用で指定されたNの値を使用
/// 方式1(solve_large): 大きいeps用で5点のグラフを指定されたDの値だけ冗長化(N=5D)
const STRATEGY: [[(i32, usize); 31]; 40] = [
    [(0, 6), (0, 6), (0, 6), (0, 6), (0, 6), (0, 6), (0, 6), (0, 6), (0, 6), (0, 6), (0, 7), (0, 7), (0, 7), (0, 7), (0, 7), (0, 7), (0, 7), (0, 7), (0, 7), (0, 7), (0, 7), (0, 7), (0, 7), (0, 7), (0, 7), (0, 7), (0, 7), (0, 7), (0, 7), (0, 8), (0, 8), ],
    [(0, 6), (0, 6), (0, 6), (0, 6), (0, 7), (0, 7), (0, 7), (0, 7), (0, 8), (0, 8), (0, 8), (0, 8), (0, 8), (0, 8), (0, 8), (0, 8), (0, 8), (0, 8), (0, 8), (0, 8), (0, 8), (0, 8), (0, 8), (0, 8), (0, 8), (0, 8), (0, 8), (0, 8), (0, 8), (0, 8), (0, 9), ],
    [(0, 6), (0, 6), (0, 7), (0, 7), (0, 7), (0, 8), (0, 8), (0, 8), (0, 8), (0, 8), (0, 8), (0, 8), (0, 8), (0, 8), (0, 8), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), ],
    [(0, 6), (0, 7), (0, 7), (0, 8), (0, 8), (0, 8), (0, 8), (0, 8), (0, 8), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), ],
    [(0, 7), (0, 7), (0, 8), (0, 8), (0, 8), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), ],
    [(0, 7), (0, 8), (0, 8), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (1, 3), (1, 3), (1, 3), (1, 3), (1, 3), (1, 3), (1, 3), (1, 3), (1, 3), ],
    [(0, 8), (0, 8), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (1, 3), (1, 3), (1, 3), (1, 3), (1, 3), (1, 3), (1, 3), (1, 3), (1, 3), (1, 3), (1, 3), (1, 3), (1, 3), (1, 3), (1, 3), (1, 3), (1, 3), ],
    [(0, 8), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (1, 3), (1, 3), (1, 3), (1, 3), (1, 3), (1, 3), (1, 3), (1, 3), (1, 3), (1, 3), (1, 3), (1, 3), (1, 3), (1, 3), (1, 3), (1, 3), (1, 3), (1, 3), (1, 3), (1, 3), (1, 3), ],
    [(0, 8), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (1, 3), (1, 3), (1, 3), (1, 3), (1, 3), (1, 3), (1, 3), (1, 3), (1, 3), (1, 3), (1, 3), (1, 3), (1, 3), (1, 3), (1, 3), (1, 3), (1, 3), (1, 3), (1, 3), (1, 3), (1, 4), (1, 4), (1, 4), (1, 4), ],
    [(0, 9), (0, 9), (0, 9), (0, 9), (0, 9), (1, 3), (1, 3), (1, 3), (1, 3), (1, 3), (1, 3), (1, 3), (1, 3), (1, 3), (1, 3), (1, 3), (1, 3), (1, 3), (1, 3), (1, 3), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), ],
    [(0, 9), (0, 9), (0, 9), (0, 9), (1, 3), (1, 3), (1, 3), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), ],
    [(0, 9), (0, 9), (0, 9), (1, 3), (1, 3), (1, 3), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), ],
    [(0, 9), (0, 9), (1, 3), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), ],
    [(0, 9), (0, 9), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 5), (1, 5), (1, 5), ],
    [(0, 9), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), ],
    [(1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), ],
    [(1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 4), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), ],
    [(1, 4), (1, 4), (1, 4), (1, 4), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 6), ],
    [(1, 4), (1, 4), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 6), (1, 6), (1, 6), (1, 6), (1, 6), ],
    [(1, 4), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 6), (1, 6), (1, 6), (1, 6), (1, 6), (1, 6), (1, 6), (1, 6), (1, 6), (1, 6), (1, 6), (1, 6), (1, 6), (1, 6), (1, 6), (1, 6), (1, 6), (1, 6), (1, 6), ],
    [(1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 6), (1, 6), (1, 6), (1, 6), (1, 6), (1, 6), (1, 6), (1, 6), (1, 6), (1, 6), (1, 6), (1, 6), (1, 6), (1, 6), (1, 6), (1, 6), (1, 6), (1, 6), (1, 6), (1, 6), (1, 6), (1, 6), (1, 6), (1, 6), ],
    [(1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 5), (1, 6), (1, 6), (1, 6), (1, 6), (1, 6), (1, 6), (1, 6), (1, 6), (1, 6), (1, 6), (1, 6), (1, 6), (1, 6), (1, 6), (1, 7), (1, 7), (1, 7), (1, 7), (1, 7), (1, 7), (1, 7), (1, 7), (1, 7), (1, 7), (1, 7), ],
    [(1, 5), (1, 5), (1, 6), (1, 6), (1, 6), (1, 6), (1, 6), (1, 6), (1, 6), (1, 6), (1, 6), (1, 6), (1, 6), (1, 6), (1, 6), (1, 6), (1, 7), (1, 7), (1, 7), (1, 7), (1, 7), (1, 7), (1, 7), (1, 7), (1, 7), (1, 7), (1, 7), (1, 7), (1, 7), (1, 7), (1, 7), ],
    [(1, 6), (1, 6), (1, 6), (1, 6), (1, 6), (1, 6), (1, 6), (1, 6), (1, 6), (1, 6), (1, 6), (1, 7), (1, 7), (1, 7), (1, 7), (1, 7), (1, 7), (1, 7), (1, 7), (1, 7), (1, 7), (1, 7), (1, 7), (1, 7), (1, 7), (1, 7), (1, 7), (1, 7), (1, 7), (1, 8), (1, 8), ],
    [(1, 6), (1, 6), (1, 6), (1, 6), (1, 6), (1, 6), (1, 7), (1, 7), (1, 7), (1, 7), (1, 7), (1, 7), (1, 7), (1, 7), (1, 7), (1, 7), (1, 7), (1, 7), (1, 7), (1, 8), (1, 8), (1, 8), (1, 8), (1, 8), (1, 8), (1, 8), (1, 8), (1, 8), (1, 8), (1, 8), (1, 8), ],
    [(1, 6), (1, 6), (1, 7), (1, 7), (1, 7), (1, 7), (1, 7), (1, 7), (1, 7), (1, 7), (1, 7), (1, 7), (1, 8), (1, 8), (1, 8), (1, 8), (1, 8), (1, 8), (1, 8), (1, 8), (1, 8), (1, 8), (1, 8), (1, 8), (1, 8), (1, 8), (1, 8), (1, 8), (1, 8), (1, 8), (1, 8), ],
    [(1, 6), (1, 6), (1, 7), (1, 7), (1, 8), (1, 8), (1, 8), (1, 8), (1, 8), (1, 8), (1, 8), (1, 8), (1, 8), (1, 8), (1, 8), (1, 8), (1, 8), (1, 9), (1, 9), (1, 9), (1, 9), (1, 9), (1, 9), (1, 9), (1, 9), (1, 9), (1, 9), (1, 9), (1, 9), (1, 9), (1, 9), ],
    [(1, 6), (1, 7), (1, 7), (1, 8), (1, 8), (1, 8), (1, 8), (1, 8), (1, 8), (1, 8), (1, 8), (1, 8), (1, 9), (1, 9), (1, 9), (1, 9), (1, 9), (1, 9), (1, 9), (1, 9), (1, 9), (1, 9), (1, 9), (1, 9), (1, 9), (1, 9), (1, 9), (1, 9), (1, 9), (1, 10), (1, 10), ],
    [(1, 7), (1, 7), (1, 8), (1, 8), (1, 8), (1, 8), (1, 8), (1, 8), (1, 9), (1, 9), (1, 9), (1, 9), (1, 9), (1, 10), (1, 10), (1, 10), (1, 10), (1, 10), (1, 10), (1, 10), (1, 10), (1, 10), (1, 10), (1, 10), (1, 10), (1, 10), (1, 10), (1, 10), (1, 10), (1, 10), (1, 10), ],
    [(1, 7), (1, 8), (1, 9), (1, 9), (1, 9), (1, 10), (1, 10), (1, 10), (1, 10), (1, 10), (1, 10), (1, 10), (1, 10), (1, 10), (1, 10), (1, 10), (1, 10), (1, 10), (1, 11), (1, 11), (1, 11), (1, 11), (1, 11), (1, 11), (1, 11), (1, 11), (1, 11), (1, 11), (1, 11), (1, 11), (1, 11), ],
    [(1, 7), (1, 8), (1, 9), (1, 9), (1, 9), (1, 10), (1, 10), (1, 10), (1, 10), (1, 10), (1, 10), (1, 10), (1, 11), (1, 11), (1, 11), (1, 11), (1, 11), (1, 11), (1, 11), (1, 11), (1, 11), (1, 11), (1, 12), (1, 12), (1, 12), (1, 12), (1, 12), (1, 12), (1, 12), (1, 12), (1, 13), ],
    [(1, 8), (1, 9), (1, 9), (1, 9), (1, 10), (1, 10), (1, 10), (1, 10), (1, 10), (1, 11), (1, 11), (1, 11), (1, 12), (1, 12), (1, 12), (1, 12), (1, 12), (1, 12), (1, 12), (1, 13), (1, 13), (1, 13), (1, 13), (1, 13), (1, 14), (1, 14), (1, 14), (1, 14), (1, 14), (1, 14), (1, 14), ],
    [(1, 8), (1, 10), (1, 10), (1, 10), (1, 11), (1, 11), (1, 11), (1, 12), (1, 12), (1, 12), (1, 12), (1, 13), (1, 13), (1, 13), (1, 13), (1, 13), (1, 13), (1, 13), (1, 13), (1, 14), (1, 14), (1, 14), (1, 14), (1, 14), (1, 14), (1, 15), (1, 15), (1, 15), (1, 15), (1, 15), (1, 15), ],
    [(1, 10), (1, 11), (1, 11), (1, 11), (1, 11), (1, 12), (1, 13), (1, 13), (1, 13), (1, 13), (1, 13), (1, 14), (1, 14), (1, 14), (1, 15), (1, 15), (1, 15), (1, 15), (1, 15), (1, 15), (1, 16), (1, 16), (1, 16), (1, 16), (1, 16), (1, 16), (1, 17), (1, 17), (1, 17), (1, 17), (1, 17), ],
    [(1, 11), (1, 11), (1, 12), (1, 12), (1, 13), (1, 13), (1, 14), (1, 14), (1, 14), (1, 14), (1, 14), (1, 15), (1, 15), (1, 15), (1, 15), (1, 16), (1, 16), (1, 16), (1, 17), (1, 18), (1, 18), (1, 18), (1, 18), (1, 18), (1, 18), (1, 18), (1, 18), (1, 18), (1, 18), (1, 19), (1, 19), ],
    [(1, 13), (1, 13), (1, 13), (1, 15), (1, 15), (1, 15), (1, 15), (1, 16), (1, 16), (1, 16), (1, 16), (1, 18), (1, 18), (1, 18), (1, 18), (1, 18), (1, 19), (1, 19), (1, 19), (1, 19), (1, 19), (1, 19), (1, 20), (1, 20), (1, 20), (1, 20), (1, 20), (1, 20), (1, 20), (1, 20), (1, 20), ],
    [(1, 14), (1, 15), (1, 15), (1, 15), (1, 15), (1, 17), (1, 17), (1, 17), (1, 18), (1, 19), (1, 20), (1, 20), (1, 20), (1, 20), (1, 20), (1, 20), (1, 20), (1, 20), (1, 20), (1, 20), (1, 20), (1, 20), (1, 20), (1, 20), (1, 20), (1, 20), (1, 20), (1, 20), (1, 20), (1, 20), (1, 20), ],
    [(1, 14), (1, 18), (1, 18), (1, 18), (1, 19), (1, 20), (1, 20), (1, 20), (1, 20), (1, 20), (1, 20), (1, 20), (1, 20), (1, 20), (1, 20), (1, 20), (1, 20), (1, 20), (1, 20), (1, 20), (1, 20), (1, 20), (1, 20), (1, 20), (1, 20), (1, 20), (1, 20), (1, 20), (1, 20), (1, 20), (1, 20), ],
    [(1, 15), (1, 18), (1, 19), (1, 19), (1, 20), (1, 20), (1, 20), (1, 20), (1, 20), (1, 20), (1, 20), (1, 20), (1, 20), (1, 20), (1, 20), (1, 20), (1, 20), (1, 20), (1, 20), (1, 20), (1, 20), (1, 20), (1, 20), (1, 20), (1, 20), (1, 20), (1, 20), (1, 20), (1, 20), (1, 20), (1, 20), ],
    [(1, 19), (1, 19), (1, 20), (1, 20), (1, 20), (1, 20), (1, 20), (1, 20), (1, 20), (1, 20), (1, 20), (1, 20), (1, 20), (1, 20), (1, 20), (1, 20), (1, 20), (1, 20), (1, 20), (1, 20), (1, 20), (1, 20), (1, 20), (1, 20), (1, 20), (1, 20), (1, 20), (1, 20), (1, 20), (1, 20), (1, 20), ],
];

// solve_large用の前計算データ
// 冗長化まえの5頂点のグラフで正解確率が高くなりそうなのを予め計算
// 計算方法: 実際にシミュレーションし、一番不正解の多かったグラフを別のグラフに入れ替える山登りをした
// (eps, M)のペア何通りかについて用意したけど1つ固定でもそこまで変わらない

// 0.013, D=4
const GRAPH_12_100: [i32; 100] = [
    30918, 9410, 10374, 31975, 11841, 32192, 11974, 31399, 13410, 27843, 11398, 15822, 3170, 16384, 31366, 10466, 24770, 30307,
    28256, 27682, 9667, 8642, 30434, 32707, 30403, 3650, 13762, 32483, 30305, 25826, 11875, 32358, 3526, 10432, 25667, 11457,
    27714, 28126, 16065, 9250, 28326, 30913, 29280, 26176, 9698, 10435, 28227, 28737, 31814, 3137, 13312, 26851, 27982, 12262,
    28102, 32199, 27713, 28039, 31746, 29410, 32450, 32390, 15554, 29154, 31811, 31840, 25600, 29729, 20390, 20032, 32289, 25539,
    32742, 27712, 11654, 30915, 30178, 29667, 32355, 32705, 11456, 28550, 29730, 16006, 28494, 32706, 32322, 30304, 27746, 25698,
    29216, 32134, 15586, 29634, 30914, 29763, 29281, 16866, 31846, 19846,
];

// 0.008, D=6
const GRAPH_20_100: [i32; 100] = [
    30918, 0, 32734, 10432, 31399, 31366, 31846, 25667, 31746, 25600, 13410, 32199, 12262, 9250, 30913, 11974, 29280, 16038,
    11456, 32192, 25698, 28039, 27875, 20032, 27682, 29729, 27842, 30915, 32288, 28737, 11875, 16064, 32707, 15554, 13346, 32483,
    20390, 30434, 28550, 30305, 28102, 28227, 27714, 9698, 26176, 25539, 29378, 29154, 16067, 3137, 30403, 16366, 27746, 3974,
    8642, 31811, 10374, 9410, 27747, 3170, 25826, 28494, 27982, 30306, 3650, 32326, 28225, 32742, 32450, 31878, 9667, 26851,
    32359, 8674, 10466, 10435, 32193, 30307, 16006, 24770, 30304, 13762, 27713, 26758, 29184, 32355, 3649, 30402, 31937, 27744,
    10467, 27712, 32739, 29667, 13763, 13506, 27782, 11457, 3138, 32390,
];

// 0.013, D=11
const GRAPH_30_100: [i32; 100] = [
    0, 32767, 28672, 32256, 16366, 482, 29249, 11598, 450, 31846, 29122, 10432, 32359, 31746, 3649, 13346, 4070, 32198, 9250,
    29280, 16067, 32707, 32192, 3136, 29378, 15554, 32738, 11457, 12110, 10433, 10435, 16065, 32483, 3974, 32193, 28039, 16064,
    30306, 10466, 32739, 3648, 13410, 30305, 27746, 30915, 31810, 3526, 32134, 3682, 10467, 31811, 9698, 3137, 28550, 27713,
    9667, 13762, 13763, 3170, 3138, 28227, 27683, 29729, 32706, 27747, 32450, 25667, 30918, 32322, 28225, 32355, 30913, 11456,
    32199, 32326, 32352, 11974, 10374, 32291, 30434, 25539, 20390, 27875, 30402, 9666, 30435, 27782, 13506, 26758, 31398, 25826,
    31399, 30403, 32390, 27744, 31878, 31366, 16038, 26112, 26176,
];

// 0.011, D=15
const GRAPH_35_40: [i32; 40] = [
    0, 32767, 28672, 32739, 16366, 31847, 32290, 29282, 19846, 32737, 12110, 32706, 482, 32736, 10433, 450, 10432, 3526, 29281,
    4070, 32135, 3649, 31842, 10434, 28038, 32449, 32451, 32256, 3137, 13762, 10467, 19520, 25026, 31776, 16066, 28898, 29154,
    28102, 11462, 30178,
];

// 0.012, D=17
const GRAPH_35_70: [i32; 70] = [
    0, 32767, 450, 28672, 32256, 32737, 12110, 16366, 16064, 10433, 4070, 3462, 32736, 482, 11598, 29154, 10432, 32321, 32359,
    29281, 3526, 15553, 3649, 3136, 28898, 30306, 32738, 3170, 32135, 32706, 32354, 24770, 31847, 13346, 28738, 32739, 3648,
    16099, 29122, 16066, 32707, 3137, 10466, 32291, 32290, 29248, 32258, 32322, 9698, 15494, 27782, 16067, 11462, 29378, 32323,
    31809, 13763, 11456, 26851, 10467, 31811, 30146, 32134, 32198, 9666, 32451, 32352, 31814, 10374, 32646,
];

// 0.012, D=19
const GRAPH_35_100: [i32; 100] = [
    0, 32767, 450, 482, 28672, 32256, 32736, 32737, 11598, 12110, 32739, 16366, 16064, 29154, 29281, 10432, 10433, 3648, 32738,
    32135, 32706, 3170, 3649, 3137, 32322, 31847, 4070, 32321, 32707, 3136, 28898, 27782, 16067, 16066, 3526, 32354, 9666, 16099,
    29248, 29122, 11462, 32359, 24770, 32451, 3462, 32291, 15494, 10466, 26851, 9698, 10374, 32134, 13763, 31811, 29378, 10467,
    13346, 32290, 32323, 9410, 32352, 31814, 32646, 28738, 11456, 32258, 30146, 31809, 15553, 30306, 29763, 32450, 25667, 3974,
    27746, 32390, 13506, 30913, 13410, 11974, 29282, 32198, 9250, 3682, 11457, 9667, 4038, 29794, 30918, 27747, 32355, 32449,
    26758, 27842, 28770, 32353, 32289, 32358, 31975, 31366,
];

// 0.012, D=17
const GRAPH_36_40: [i32; 40] = [
    32767, 482, 16366, 12110, 3462, 31744, 16065, 32359, 450, 29154, 16384, 3136, 32736, 28672, 32737, 4038, 10467, 10432, 13762,
    28038, 29281, 11598, 16067, 10433, 3648, 3649, 32738, 32739, 32706, 32354, 32448, 24770, 32290, 29248, 32707, 32646, 29729,
    28259, 32323, 32291,
];

// 0.013, D=19
const GRAPH_36_70: [i32; 70] = [
    0, 32767, 32737, 32736, 450, 16366, 28672, 3136, 3648, 10432, 32359, 10433, 482, 29281, 11598, 12110, 28738, 3462, 32739,
    32738, 13346, 32258, 32135, 32706, 10466, 28038, 20454, 32646, 29154, 32707, 3649, 32288, 32450, 32355, 28898, 31842, 11398,
    13794, 32354, 31744, 31811, 16099, 29248, 13762, 31810, 32291, 4038, 3974, 32323, 25026, 3170, 26851, 3137, 32290, 24770,
    28225, 16067, 16064, 30307, 11462, 28224, 3138, 31847, 11457, 27713, 11974, 31846, 3526, 32451, 9666,
];

// 0.020, D=20
const GRAPH_36_100: [i32; 100] = [
    0, 32767, 482, 32737, 29281, 32736, 450, 16366, 10433, 11598, 12110, 32738, 32706, 32354, 28672, 28898, 29154, 32291, 3136,
    32739, 3462, 3649, 3648, 32707, 16099, 32448, 16067, 31744, 29248, 4038, 13762, 3137, 10432, 32323, 11398, 10466, 11462,
    3170, 32288, 32359, 13794, 20454, 3526, 13346, 24770, 28225, 31811, 31847, 32258, 32135, 28038, 26851, 32451, 25026, 31842,
    27713, 28224, 3138, 32290, 9410, 11457, 9666, 30307, 27714, 11974, 28550, 3974, 32450, 28738, 28770, 10467, 10434, 13506,
    10374, 29378, 15494, 29762, 30913, 29794, 25667, 16066, 26816, 32198, 30914, 13410, 31878, 13312, 31846, 32358, 30304, 10435,
    16065, 13763, 15554, 11456, 27747, 32352, 9250, 32449, 28039,
];

// 0.013, D=20
const GRAPH_37_40: [i32; 40] = [
    0, 32767, 450, 32737, 11598, 28672, 16366, 31744, 32355, 32134, 29281, 19846, 32359, 32736, 10433, 20454, 32739, 32290,
    32706, 32738, 31846, 26816, 3136, 3649, 28866, 32448, 25026, 16065, 16866, 31810, 16066, 13794, 28225, 29794, 11398, 20032,
    32289, 4038, 3137, 9667,
];

// 0.022, D=20
const GRAPH_37_70: [i32; 70] = [
    0, 32767, 28672, 16366, 32359, 32736, 482, 31744, 3648, 31847, 450, 32737, 11598, 10432, 10433, 32738, 31810, 32739, 13346,
    3649, 29281, 20454, 13794, 32321, 32354, 16065, 32448, 3136, 32134, 3462, 32706, 10434, 13762, 29282, 29634, 29154, 32288,
    32355, 10466, 4038, 29794, 3138, 29248, 28550, 32291, 3137, 32323, 11974, 32135, 9666, 28866, 27782, 3526, 30307, 16099,
    28494, 27713, 32450, 32707, 32290, 31811, 29410, 32258, 32451, 3974, 13506, 15494, 30914, 10467, 32353,
];

// 0.055, D=20
const GRAPH_37_100: [i32; 100] = [
    0, 32767, 32736, 450, 32737, 10432, 11598, 482, 28672, 3136, 16366, 10433, 32739, 3648, 29281, 32706, 3649, 4038, 29248,
    32738, 31744, 32291, 3462, 32355, 32290, 20454, 31810, 13794, 16065, 3974, 32288, 3137, 32354, 10466, 29154, 32135, 28494,
    32359, 32134, 10434, 32258, 28866, 32707, 3526, 32323, 27782, 28224, 31842, 16099, 11974, 3170, 13346, 31847, 3138, 32451,
    15494, 29282, 27713, 29729, 32450, 32358, 10374, 30306, 30914, 32646, 9698, 30307, 31846, 32448, 9666, 25026, 16067, 10467,
    29762, 30146, 9250, 26850, 29410, 13312, 16066, 9410, 28225, 32352, 11457, 16064, 30913, 13506, 10435, 32321, 13762, 15554,
    28646, 28770, 29122, 29763, 32353, 13410, 11875, 15555, 9667,
];

// 0.025, D=20
const GRAPH_38_40: [i32; 40] = [
    0, 32767, 16366, 28672, 3136, 482, 450, 11598, 3649, 32736, 32737, 29282, 10432, 32359, 16064, 32355, 10434, 32739, 28738,
    28550, 32738, 29281, 10433, 31810, 28866, 32354, 32321, 32706, 31808, 3462, 13794, 4070, 16065, 31847, 3974, 4038, 29634,
    29154, 29729, 13506,
];

// 0.056, D=20
const GRAPH_38_70: [i32; 70] = [
    0, 32767, 28672, 482, 16366, 450, 32736, 32359, 32705, 32134, 32738, 11598, 10433, 3136, 32448, 10466, 32706, 28770, 31847,
    13794, 3649, 29248, 32355, 31779, 28494, 16065, 32739, 32290, 10434, 30146, 32354, 4070, 20032, 29281, 28738, 28224, 3974,
    3462, 3526, 29122, 9666, 29154, 11974, 31744, 32258, 29730, 3137, 28102, 28898, 3138, 32707, 30914, 4038, 15554, 10432,
    28227, 11654, 32135, 28225, 3170, 31810, 11398, 32322, 26816, 31776, 30307, 11462, 27782, 32352, 27713,
];

// 0.119, D=20
const GRAPH_38_100: [i32; 100] = [
    0, 32767, 16366, 450, 32736, 32359, 32738, 11598, 28672, 3136, 32706, 32739, 482, 29281, 32355, 3649, 10433, 31847, 3974,
    28494, 3462, 4070, 3526, 29248, 10466, 28770, 32290, 10434, 29154, 16065, 10432, 32291, 28738, 13794, 4038, 32707, 32354,
    3137, 32258, 11462, 29122, 28898, 29730, 3138, 11398, 28224, 13312, 28227, 26816, 28102, 31842, 32135, 30914, 9666, 31744,
    30146, 15554, 3170, 28550, 32448, 31776, 28225, 31810, 9698, 31811, 20032, 31809, 32451, 16099, 32134, 30307, 16064, 28038,
    32737, 32352, 11457, 24770, 16067, 29728, 32256, 32705, 8674, 27712, 31878, 26850, 15494, 13762, 28866, 10467, 10435, 27747,
    29762, 32353, 29763, 30304, 29634, 31938, 3648, 32321, 11875,
];

// 0.060, D=20
const GRAPH_39_40: [i32; 40] = [
    32767, 16366, 16866, 450, 28672, 32705, 32736, 31847, 3137, 31779, 16064, 31744, 12110, 3648, 10434, 29282, 20454, 32354,
    10433, 32134, 32321, 9666, 32738, 32739, 32706, 30178, 11598, 4038, 3974, 32258, 26816, 28738, 16066, 10466, 3526, 29728,
    29281, 31810, 28866, 11462,
];

// 0.144, D=20
const GRAPH_39_70: [i32; 70] = [
    32767, 16064, 28672, 25058, 32359, 12110, 450, 10434, 32738, 31744, 32706, 3649, 29282, 32736, 31779, 29248, 3462, 30178,
    32192, 30146, 16866, 31847, 4070, 32290, 9666, 12262, 20032, 32739, 32288, 32354, 10433, 11398, 16366, 32321, 3526, 10466,
    28738, 16065, 11654, 19520, 3974, 4038, 16066, 32134, 3138, 8642, 13312, 32707, 29281, 32705, 28550, 3137, 31810, 28259,
    10432, 27982, 32258, 26816, 30914, 11974, 11462, 31809, 0, 16067, 13346, 16334, 27712, 32737, 16384, 3682,
];

// 0.233, D=20
const GRAPH_39_100: [i32; 100] = [
    32767, 16064, 12110, 450, 28672, 16866, 32736, 32706, 3648, 32738, 32192, 4070, 30178, 31847, 3974, 32321, 4038, 3649, 10433,
    29281, 3138, 32134, 3137, 3526, 32288, 10434, 31744, 31779, 12262, 32290, 16366, 10466, 19520, 32739, 16066, 28738, 10432,
    28550, 32359, 32707, 30914, 11462, 30146, 26816, 31842, 29248, 13312, 25058, 29282, 11398, 29728, 28259, 32705, 9666, 0,
    16334, 32449, 16065, 32737, 32734, 16384, 32258, 29154, 31810, 13346, 32358, 28898, 11654, 27982, 27712, 11598, 3462, 32291,
    32742, 27682, 32256, 13506, 30304, 19846, 32451, 29122, 16067, 9216, 13762, 25026, 8642, 27782, 28770, 31878, 10435, 32323,
    29216, 27713, 28227, 32198, 11841, 10467, 32289, 31814, 10374,
];

// 0.138, D=20
const GRAPH_40_40: [i32; 40] = [
    0, 28672, 32767, 482, 10432, 450, 16334, 31779, 4070, 12110, 16064, 32258, 16065, 28770, 3137, 32706, 32359, 32705, 20032,
    31808, 32134, 19846, 29248, 32707, 32355, 3526, 9698, 32736, 10466, 32738, 3649, 4038, 11398, 3974, 29154, 28126, 32192,
    25026, 15554, 29122,
];

// 0.281, D=20
const GRAPH_40_70: [i32; 70] = [
    32767, 16366, 0, 32737, 28672, 10432, 450, 16064, 32706, 3462, 32290, 32736, 32192, 28770, 3649, 482, 12110, 31779, 4070,
    32359, 32355, 20032, 29154, 32738, 8704, 29122, 4038, 3974, 3138, 32707, 10435, 3526, 12262, 10466, 10433, 31847, 29248,
    28102, 29728, 9698, 31808, 32739, 29281, 11654, 27982, 13312, 28225, 32134, 9666, 31776, 3137, 8642, 11462, 30146, 16066,
    19520, 8674, 28038, 28738, 30914, 32256, 32291, 31744, 32449, 16067, 16070, 15553, 16065, 27746, 11974,
];

// 0.391, D=20
const GRAPH_40_100: [i32; 100] = [
    32767, 32736, 10432, 450, 32706, 482, 32738, 12110, 4070, 32359, 29122, 3526, 0, 20032, 3649, 3137, 3974, 16366, 9666, 32707,
    4038, 10433, 9698, 32739, 31779, 32737, 10466, 29154, 28770, 30146, 19520, 29248, 16064, 16065, 32355, 8642, 28738, 28102,
    8674, 10435, 29282, 32290, 31744, 10434, 32256, 28672, 16070, 31808, 3138, 29281, 32134, 3462, 13312, 31776, 29728, 32192,
    30914, 32705, 16384, 28038, 30178, 12262, 29184, 27982, 16066, 32291, 8704, 11462, 32449, 31847, 11598, 32222, 31811, 15822,
    19846, 32451, 32448, 32258, 11654, 28256, 3170, 3682, 16334, 32323, 11841, 8737, 32322, 31809, 28126, 13763, 31846, 25600,
    31842, 13538, 28646, 11430, 31878, 30306, 32353, 32289,
];

fn get_bases(eps: f64, M: usize) -> Vec<i32> {
    match (eps * 100.0f64).round() as i32 {
        a if a <= 12 => &GRAPH_12_100[..],
        a if a <= 20 => &GRAPH_20_100[..],
        a if a <= 30 => &GRAPH_30_100[..],
        a if a <= 35 && M <= 40 => &GRAPH_35_40[..],
        a if a <= 35 && M <= 70 => &GRAPH_35_70[..],
        a if a <= 35 => &GRAPH_35_100[..],
        36 if M <= 40 => &GRAPH_36_40[..],
        36 if M <= 70 => &GRAPH_36_70[..],
        36 => &GRAPH_36_100[..],
        37 if M <= 40 => &GRAPH_37_40[..],
        37 if M <= 70 => &GRAPH_37_70[..],
        37 => &GRAPH_37_100[..],
        38 if M <= 40 => &GRAPH_38_40[..],
        38 if M <= 70 => &GRAPH_38_70[..],
        38 => &GRAPH_38_100[..],
        39 if M <= 40 => &GRAPH_39_40[..],
        39 if M <= 70 => &GRAPH_39_70[..],
        39 => &GRAPH_39_100[..],
        40 if M <= 40 => &GRAPH_40_40[..],
        40 if M <= 70 => &GRAPH_40_70[..],
        40 => &GRAPH_40_100[..],
        _ => unimplemented!(),
    }
    .iter()
    .take(M)
    .cloned()
    .collect_vec()
}

// solve_small用の前計算データ
// 各N(6<=N<=9)に対して、最適なグラフ集合を前計算した
// 計算方法:
//   グラフGの隣接行列全体の集合をL(G)と表すことにする。
//   成功確率は少し式変形すると以下のように表される。
//   P(success)=1/M Σ_H max_s |L(H)|/|L(G[s])| Σ_{G'∈L(G[s])} ε^{d(H,G')}(1-ε)^(N(N-1)/2-d(H,G'))
//   N頂点のグラフはNが小さいので全列挙可能(N=8で12346, N=9で274668)。
//   小さいNで試すと対象性が高い(|L(G)|が小さい)ものしか使われなかったので、Gの候補はL(G)の小さいものに限定し、
//   p[H][G[s]] := Σ_{G'∈L(G[s])} ε^{d(H,G')}(1-ε)^(N(N-1)/2-d(H,G'))
//   を全ての(H,G[s])ペアについて計算しておく。
//   これでGの集合を変更したときの成功確率がHの総数くらいの計算時間で更新出来るようになるので焼き鈍すことが可能。

// eps=0.08 0.84099
const GRAPH9_8: [u64; 100] = [
    268435455, 68719476735, 4265133183, 4135458444, 0, 32767, 31965120, 1893965304, 832061473, 270566475, 811699423, 534739892,
    17045626360, 4058496990, 16540167, 8387558475, 1932864095, 274625312, 831519774, 8538791935, 1067348769, 7672, 811701612,
    33148158, 2000485296, 811728894, 834192491, 1895825400, 864972801, 66059500, 1936584481, 271040459, 4076051967, 270566516,
    4135485439, 31965183, 1895622256, 101599, 332880304, 8538791928, 1894573131, 817652228, 811767223, 1069479860, 1932864070,
    4143689440, 8387559423, 63, 1893986008, 271040500, 832077823, 14917113, 1937099998, 8387558636, 276756331, 33150580,
    8538935147, 811700000, 4058496967, 298269620, 2132566535, 871365855, 811725631, 4294967244, 6402816, 813694975, 255567,
    1936584198, 270567423, 838454527, 270600487, 811726708, 939507678, 935245643, 2134697589, 271546800, 4058496960, 281364628,
    830980062, 15060191, 17112219614, 270597045, 2097151, 833009476, 334495668, 6393054, 832569313, 811767216, 832230755,
    1067450366, 283352575, 299858816, 811710293, 271006655, 7916, 66568140, 1893983820, 4075680843, 2132569823, 4277923553,
];

// eps=0.06 0.8340509628407388
const GRAPH8_6: [u64; 100] = [
    31965120, 16540167, 14917112, 2097151, 8287009, 2131019, 0, 4160436, 268435455, 6393054, 15054783, 2167359, 33148158,
    2571136, 515820, 6480388, 66059500, 2131967, 14917119, 15060843, 63, 16547839, 2131093, 14937968, 255567, 16350, 15060191,
    507851, 2300340, 15592966, 33150580, 6402816, 6466355, 134201310, 6717406, 31965183, 6706529, 237055, 6403925, 16641759,
    15531193, 104052, 2146292, 66059487, 2167296, 7237927, 6420340, 1023, 6807033, 6731595, 6701025, 7239604, 66568140, 32238814,
    6402879, 2579104, 15054720, 104011, 3873, 6395255, 8322046, 33148159, 6462456, 101599, 3145211, 6393632, 31965127, 15062688,
    6739308, 33283576, 2161663, 2132126, 33159084, 7915, 2338635, 2131892, 237048, 15060769, 236, 515807, 14921452, 2319087,
    14937975, 2131385, 2192160, 14917337, 2179039, 15070014, 2167288, 15728120, 6483676, 8320885, 6393855, 6419454, 2322140,
    2198888, 8287231, 15187934, 2579956, 15530099,
];

// eps=0.02 0.94126
const GRAPH7_2: [u64; 100] = [
    255567, 2097151, 33867, 32767, 237048, 515806, 104096, 101599, 0, 64436, 63, 7916, 33942, 104063, 507851, 127777, 237055,
    7672, 127999, 3294, 241524, 104083, 34299, 7903, 39856, 3873, 101612, 515820, 241483, 131070, 1191, 106206, 111559, 35326,
    33952, 104011, 16350, 40683, 255574, 112468, 236, 102399, 33868, 128885, 1023, 33911, 114655, 127806, 102206, 235, 34300,
    515819, 112524, 101736, 223, 128875, 7679, 112575, 3440, 1048059, 1109, 101743, 111582, 102176, 101750, 104021, 3903, 507852,
    507903, 103864, 104444, 102183, 3447, 106359, 515583, 7, 104443, 33983, 35702, 106221, 104103, 3309, 101611, 4094, 104126,
    258041, 7915, 30, 35629, 515807, 128876, 104012, 105982, 114667, 3306, 36788, 101598, 35321, 114656, 39657,
];

// eps=0.04 0.82640
const GRAPH7_4: [u64; 100] = [
    33867, 3873, 7672, 255567, 507851, 0, 101598, 64436, 32767, 2097151, 63, 237055, 104052, 515820, 7915, 101736, 3295, 127777,
    237048, 236, 241535, 34299, 128884, 33877, 16350, 104011, 102398, 515807, 1023, 104083, 48063, 39348, 104096, 241492, 103871,
    111582, 1184, 128875, 34300, 131070, 507852, 104157, 515806, 235, 102207, 101599, 7916, 114655, 255574, 35131, 33868, 102176,
    241483, 106206, 48020, 515819, 30, 33919, 515583, 49140, 101610, 3440, 111559, 7, 7903, 112468, 3294, 258041, 101743,
    1048059, 39584, 111597, 255655, 35839, 3447, 507903, 33959, 40683, 104063, 33942, 255999, 101745, 127806, 104443, 106221,
    34743, 35702, 3309, 104103, 40445, 128885, 104126, 39645, 39419, 102182, 40881, 3577, 237049, 101750, 241613,
];

// eps=0.01 0.98033
const GRAPH6_1: [u64; 37] = [
    236, 1099, 1023, 7915, 1972, 3873, 3294, 32767, 0, 7672, 1191, 3447, 7903, 1184, 16350, 3440, 7916, 223, 1151, 1109, 7, 3903,
    7679, 4094, 1100, 1214, 3309, 235, 1531, 1532, 3306, 63, 3295, 222, 1456, 12, 7902,
];

fn get_repr(eps: f64, M: usize, N: usize) -> Vec<u64> {
    match ((eps * 100.0).round() as i32, N) {
        (_, 9) => GRAPH9_8.iter(),
        (_, 8) => GRAPH8_6.iter(),
        (1, 7) => GRAPH7_2.iter(),
        (_, 7) => GRAPH7_4.iter(),
        (_, 6) => GRAPH6_1.iter(),
        _ => unimplemented!(),
    }
    .take(M)
    .cloned()
    .collect()
}

提出情報

ジャッジ結果