アルゴリズムと数学 104

https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_bx

ランダムにグラフを作ります。1点から少しずつエッジを追加していきます。次に進むノードが既存のノードか新規のノードかを確率で選びますが、新規ノードの確率を少しずつ減らしていきます。

// Graph Master
#![allow(non_snake_case)]

use std::collections::VecDeque;
use std::ops::Range;
use rand::Rng;
use rand::rngs::StdRng;
use rand::seq::SliceRandom;


//////////////////// Graph ////////////////////

type Node = usize;
type Graph = Vec<Vec<Node>>;

const INF: usize = 10000;

fn find_farthest_point(v0: Node, graph: &Graph) -> i32 {
    let N = graph.len();
    let mut q = VecDeque::new();
    q.push_back(v0);
    let mut dists: Vec<i32> = vec![-1; N];
    dists[v0] = 0;
    while let Some(v) = q.pop_front() {
        let d = dists[v];
        for &v1 in graph[v].iter() {
            if dists[v1] == -1 {
                dists[v1] = d + 1;
                q.push_back(v1)
            }
        }
    }
    dists.into_iter().max().unwrap()
}

fn is_diameter_short(graph: &Graph, D: i32) -> bool {
    let N = graph.len();
    (0..N).all(|v0| find_farthest_point(v0, graph) <= D)
}

fn num_edges(graph: &Graph) -> usize {
    graph.iter().map(|v| v.len()).sum::<usize>() / 2
}

fn print_graph(graph: &Graph) {
    println!("{} {}", graph.len(), num_edges(graph));
    for (v1, vs) in graph.iter().enumerate() {
        for &v2 in vs.iter() {
            if v1 < v2 {
                println!("{} {}", v1+1, v2+1)
            }
        }
    }
}


//////////////////// process ////////////////////

fn collect_existing_insertable_nodes(v0: Node, graph: &Graph) -> Vec<Node> {
    graph.iter().enumerate().
        filter(|&(v, vs)| v != v0 && vs.len() < 4 && !graph[v0].contains(&v)).
        map(|(v, _)| v).collect::<Vec<Node>>()
}

fn select_neighbor(v0: Node, graph: &Graph, ratio: f64,
                                    rng: &mut rand::rngs::StdRng) -> Node {
    if rng.gen::<f64>() < ratio {
        return INF
    }
    
    let vs = collect_existing_insertable_nodes(v0, graph);
    if vs.is_empty() {
        INF
    }
    else {
        *(vs.choose(rng).unwrap())
    }
}

fn extend_edges(r: Range<Node>, graph: &mut Graph,
                        ratio: f64, rng: &mut StdRng) -> usize {
    let vs: Vec<Node> = r.collect();
    for _ in 0..4 {
        for &v in vs.iter() {
            if graph[v].len() == 4 {
                continue
            }
            let v1 = select_neighbor(v, graph, ratio, rng);
            if v1 == INF {
                let L = graph.len();
                graph[v].push(L);
                graph.push(vec![v])
            }
            else {
                graph[v].push(v1);
                graph[v1].push(v)
            }
        }
    }
    graph.len()
}

fn make_graph_randomly(rng: &mut StdRng) -> Graph {
    let mut graph: Graph = vec![vec![]];
    let n0 = 0;
    let n1 = 1;
    let n2 = extend_edges(n0..n1, &mut graph, 1.0, rng);
    let n3 = extend_edges(n1..n2, &mut graph, 0.8, rng);
    let n4 = extend_edges(n2..n3, &mut graph, 0.5, rng);
    let n5 = extend_edges(n3..n4, &mut graph, 0.2, rng);
    let _n = extend_edges(n4..n5, &mut graph, 0.0, rng);
    graph
}

fn F(N: usize) -> Graph {
    let seed: [u8; 32] = [13; 32];
    let mut rng: StdRng = rand::SeedableRng::from_seed(seed);
    loop {
        let g = (0..N).map(|_| make_graph_randomly(&mut rng)).
                    filter(|g| is_diameter_short(g, 4)).max_by_key(|g| g.len());
        if let Some(graph) = g {
            return graph
        }
    }
}

fn main() {
    print_graph(&F(100000))
}