比較的簡単なセットとはいえ、6完を安定して取れていてかなり良い。この調子で維持したいな

A - Shuffled Equation

埋め込むより言語機能に頼って順列全探索を書いたほうが速いという判断。多分そんなことはない気がしてきた。提出

use itertools::Itertools;
use proconio::input;

fn main() {
    let n = 3;
    input!{
        a: [i32; n],
    }
    println!("{}", if
    a.iter()
        .copied()
        .permutations(n).any(|v| v[0]*v[1]==v[2]) {
        "Yes"
    } else {
        "No"
    });
}

B - Who is Missing?

集合のcontains判定なので、setに突っ込んでそれぞれ判定すればよいでしょう。提出

use std::collections::BTreeSet;
use itertools::Itertools;
use proconio::input;

fn main() {
    input!{
        n: usize,
        m: usize,
        a: [usize; m],
    }
    let set = BTreeSet::from_iter(a.iter().copied());
    let ans = (1..=n).filter(|i| !set.contains(i)).collect_vec();
    println!("{}", ans.len());
    println!("{}", ans.iter().join(" "));
}

C - Bib

ゼッケン順に並び替えるのが厄介ですが、人$i$はゼッケン番号${Q_P}_i$を見ているので、そのように実装すればよいです。提出

use itertools::Itertools;
use proconio::input;
use proconio::marker::Usize1;

fn main() {
    input!{
        n: usize,
        p: [Usize1; n],
        q: [Usize1; n],
    }
    let ans = (0..n)
	    .sorted_unstable_by_key(|i| q[*i])
	    .map(|i| 1+q[p[i]])
	    .collect_vec();
    println!("{}", ans.iter().join(" "));
}

D - Doubles

ありうる組み合わせ前通りに対して、尺取りのようなイメージで同じ値の組み合わせを探しながら確率を組み合わせればよいです。「尺取りのようなイメージ」とはつまり、ソートしてランレングス圧縮済みの2つのサイコロ$A, B$について、もし$A_i = B_j$であれば確率に加算して$i, j$をともに1加算、$A_i < B_j$であれば$i$のみ1加算,そうでなければ$j$に1加算を行います。

計算量は、あるサイコロの目$A_{ij}$が呼びされる回数は$N$回になるので、つまり各サイコロについて$K_i$個の目がちょうど$N$回ずつ呼び出される計算になるので$O(N\sum_{i=1}^N{K_i})$時間であり、この問題の制約下で十分高速です。提出

use itertools::{iproduct, Itertools};
use num_rational::Ratio;
use proconio::input;

fn main() {
    input!{
        n: usize,
    }
    static N: usize = 1e5 as usize+2;
    let mut v = vec![];
    let mut sums = vec![];

    for i in 0..n {
        input! {
            k: usize,
            a: [u64; k],
        }
        let a = a.iter()
	        .copied()
	        .sorted_unstable()
	        .dedup_with_count()
	        .collect_vec();
        sums.push(k as f64);
        v.push(a);
    }

    let mut ans :f64 = 0.;
    for i in 0..n {
        for j in i+1..n {
            let mut ii = 0;
            let mut ji = 0;
            let mut sum = 0.;
            while ii < v[i].len() && ji < v[j].len() {
                if v[i][ii].1 == v[j][ji].1 {
                    sum += v[i][ii].0 as f64 / sums[i] * v[j][ji].0 as f64 / sums[j];
                    ii += 1;
                    ji += 1;
                } else if v[i][ii].1 < v[j][ji].1 {
                    ii += 1;
                } else {
                    ji += 1;
                }
            }
            ans = ans.max(sum);
        }
    }
    println!("{}", ans);
}

F - Insert

DをACした時点でEよりFのほうがAC数が多かったため、Fを先に解きました。

さて、軽く考えると次の事実に思い当たります: 「最終的な数列の$P_N$番目の値は$N$である」。これは、一番最後に挿入する(つまり、その後に挿入操作が行われない)ため、その値がそのまま適用されるため比較的すぐに気付けると思います。このような場合に、後ろから見るという手段は有効な場面が多いです¹。

後ろから見るとして、$i$番目の操作を考えましょう。$i$番目の操作では、すでに配置済みの$i+1,i+2, \cdots, N$番目の値を無視して前から$P_i$番目に配置できればよいです。これは、区間和が$P_i$となるような位置を指定すれば良く、また無視をする=更新があるので、一点更新区間和取得のSegment treeを用いることで実現できます。提出

use ac_library::{Monoid, Segtree};
use itertools::Itertools;
use proconio::input;
use proconio::marker::Usize1;

struct Sum;
impl Monoid for Sum {
    type S = i64;
    fn identity() -> Self::S {
        0
    }

    fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S {
        *a + b
    }
}

fn main() {
    input!{
        n: usize,
        p: [usize; n],
    }
    let mut seg: Segtree<Sum> = Segtree::new(n);
    for i in 0..n {
        seg.set(i, 1);
    }

    let mut ans = vec![0; n];
    for (i, pi) in p.iter().enumerate().rev() {
        let idx = seg.max_right(0, |&sum| sum < *pi as i64);
        seg.set(idx, 0);
        ans[idx] = i+1;
    }
    println!("{}", ans.iter().join(" "));
}

E - Cables and Servers

全域木を構成することを考えたいです。そのために、まず「余っている辺」をpick upします。これはUnionFindを用いて連結性を確認しつつ、すでに連結済みの頂点をつなぐ辺が該当します。 余ったケーブルを用いて、初期の状態で頂点$0$の連結成分と非連結なものとを新たに接続することを考えればよい²です。余っている辺が頂点$0$の連結成分同士をつなぐものであれば「現時点でまだ頂点$0$とは連結ではない頂点」と結べば良く³、反対に余っている辺が頂点$0$とは非連結な者同士でつながっている場合は、そのどちらかの端を頂点$0$に繋ぎ変えればよいです。この操作は正しく実装することで線形時間で行うことができるため、十分高速に解くことができます。提出

use ac_library::Dsu;

use itertools::Itertools;
use proconio::input;
use proconio::marker::Usize1;

fn main() {
    input!{
        n: usize,
        m: usize,
        e: [(Usize1, Usize1); m],
    }
    let mut uf = Dsu::new(n);
    let mut amari = vec![];
    for (i, (a, b)) in e.iter().enumerate() {
        if !uf.same(*a, *b) {
            uf.merge(*a, *b);
        } else {
            amari.push(i);
        }
    }

    // 0に集める
    let mut stk = vec![];
    for i in 0..n {
        if !uf.same(0, i) {
            stk.push(i);
        }
    }
    let mut ans = vec![];
    for i in amari {
        if stk.len() == 0 {
            break;
        }
        if uf.same(0, e[i].0) {
            while let Some(x) = stk.pop() {
                if !uf.same(0, x) {
                    ans.push((i, e[i].0, x));
                    uf.merge(e[i].0, x);
                    break;
                }
            }
        } else {
            ans.push((i, e[i].0, 0));
            uf.merge(0, e[i].0);
        }
    }
    println!("{}", ans.len());
    println!("{}", ans.iter().map(|(i, a, b)| format!("{} {} {}", i+1, a+1, b+1)).join("
"));
}

G - Fine Triplets(Upsolve)

分からず。

$B-A=C-B$はすなわち$2B=A+C$なので、そのように式変形をしておきます。ここで、以下のような言い換えを考えます。「$k=1, 2, ..., \cdots, \text{max}(S_i)$について、集合から2数を選んで足したときの値が$k$となるような選び方の総数を求めよ」。この問題が高速に解ければ、元の問題も十分高速に解くことができます。⁴

この問題は高速フーリエ変換(FFT)を用いることで解くことができます⁵。

という多項式$f(x)$に対して、$f(x)^2$を計算した多項式の$x^k$の係数こそが、集合から2数を選んでたしたときの値が$k$となるような選び方の個数になります。ただし、これは重複があることと、同じ値(例えば$k=6$に対して$(3, 3)$)を選んでしまう場合があるので、このようなものを省きながら足し合わせることで答えを得ることができます。提出

use ac_library::convolution_i64;
use proconio::input;

fn main() {
    input!{
        n: usize,
        s: [usize; n],
    }
    static N: usize = 1_000_000 + 2;
    let mut a = vec![0; N];
    for &si in &s {
        a[si] = 1;
    }
    let conv = convolution_i64(&a, &a);
    let ans = s.iter().map(|&si| (conv[2*si]-1)/2).sum::<i64>();
    println!("{}", ans);
}