PG BATTLE 2022

0-PG_BATTLE_2022.md

Accepted codes of PG BATTLE 2022

see. https://lab.mo-t.com/blog/pgbattle2022report

3-arithmetic_progression.rs

fn main() {
    proconio::input!{
        n: usize,
        mut b: [usize; n],
    }

    b.sort();

    if n == 2 {
        println!("{}", (b[0] + b[1]) / 2);
        return;
    }

    let d = (b[1] - b[0]).min(b[n-1] - b[n-2]);

    for i in 0..n-1 {
        if b[i] + d != b[i+1] {
            println!("{}", b[i] + d);
        }
    }
}

4-reflection.rs

use std::collections::BTreeMap;

fn main() {
    proconio::input!{
        w: i64,
        h: i64,
        t: i64,
        s: (i64, i64),
        g: (i64, i64),
    }

    let sqs: BTreeMap<i64, i64> = (0..1000000).map(|i| (i*i, i)).collect();

    let mut ans = 0;
    ans += count(g.0 - s.0, g.1 - s.1, w, h, t, &sqs);
    ans += count(g.0 - s.0, 2 * h - g.1 - s.1, w, h, t, &sqs);
    ans += count(2 * w - g.0 - s.0, g.1 - s.1, w, h, t, &sqs);
    ans += count(2 * w - g.0 - s.0, 2 * h - g.1 - s.1, w, h, t, &sqs);

    println!("{}", ans);
}


fn count(a: i64, b: i64, w: i64, h: i64, t: i64, sqs: &BTreeMap<i64, i64>) -> i32 {
    let mut ret = 0;

    for x in -t..=t {
        let m2 = t * t - (2 * w * x - a).pow(2);
        if let Some(&m) = sqs.get(&m2) {
            if (m - b).abs() % (2 * h) == 0 {
                ret += 1;
            }

            if m > 0 && (-m - b).abs() % (2 * h) == 0 {
                ret += 1;
            }
        }
    }

    ret
}

5-pattern.rs

use proconio::marker::{Chars, Usize1};

fn main() {
    proconio::input!{
        n: usize,
        m: usize,
        s: Chars,
        t: Chars,
        k: usize,
        ps: [(Usize1, Usize1); k],
    }

    let n_max = 1000000;
    let mut p2 = vec![0; n_max];
    for i in 2..n_max {
        if i%2 == 0 {
            p2[i] = p2[i/2] + 1;
        }
    }
    let mut p2c = vec![0; n_max];
    for i in 1..n_max {
        p2c[i] = p2[i] + p2c[i-1];
    }

    for (x, y) in ps {
        if x == 0 {
            println!("{}", t[y]);
            continue;
        }
        if y == 0 {
            println!("{}", s[x]);
            continue;
        }
        let mut ans = 0;

        for i in 1..=x {
            if s[i] == '1' {
                ans += cm2(x-i+y-1, x-i, &p2c);
            }
        }

        for i in 1..=y {
            if t[i] == '1' {
                ans += cm2(x-1+y-i, y-i, &p2c);
            }
        }

        println!("{}", ans % 2);
    }

}

fn cm2(n: usize, m: usize, p2c: &[usize]) -> usize {
    if p2c[n] == p2c[n-m] + p2c[m] {
        1
    } else {
        0
    }
}

6-two_pawns.rs

use modint::*;

fn main() {
    proconio::input!{
        n: usize,
        s: [proconio::markers::Chars; n],
    }

    type Mint = ModInt998244353;

    let s = s.iter().map(|si| {
        si.iter().enumerate().map(|(i, &c)| {
            if c == '#' {
                1<<i
            } else {
                0
            }
        }).sum::<usize>()
    }).collect::<Vec<_>>();

    let mut dp = vec![vec![vec![Mint::from(0); n+1]; 1<<n]; n+1];
    dp[0][0][0] = 1.into();

    for i in 0..n {
        for b in 0..1<<n {
            let mut c = ((1<<n)-1)^b;
            loop {
                if s[i] & c == 0 {
                    for j in 0..=n {
                        let u = dp[i][b][j];
                        dp[i+1][b|c][j.max(c.count_ones() as usize)] += u;
                    }
                }
                if c == 0 {
                    break;
                }
                c = (c-1) & (((1<<n)-1)^b);
            }
        }
    }

    let mut ans = Mint::from(0);
    for i in 0..=n {
        for b in 0..1<<n {
            ans += dp[n][b][i] * i;
        }
    }

    println!("{}", ans);
}

// Library
// see https://github.com/rust-lang-ja/ac-library-rs
pub mod modint {/* library implementations omitted */}