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)) }