エクサウィザーズ 2019 D - Modulo Operations

問題

atcoder.jp

解法

解説にあるとおり、ある数が使われた後、その数より大きい数を使ったとしても剰余には影響しないので、大きい数から順番に見ていって数列に詰めていくことを考える。

i番目(0 <= i < n )に大きい数 x_i を数列に詰める時、空いている場所は (n-i) ヶ所ある。この (n-i) ヶ所のうち一番前を除く (n-i-1) ヶ所のどこかに詰めると、x_i より小さい数が x_i の前に来ることになり、 x_i は剰余に対して影響しなくなる。一番前に詰めると x_i の前にある数は必ず x_i より大きくなるので、剰余に影響するようになる。

コード

const MOD: usize = 1e9 as usize + 7;

fn main() {
    let s = std::io::stdin();
    let mut sc = Scanner { stdin: s.lock() };
    let n: usize = sc.read();
    let x: usize = sc.read();
    let mut s: Vec<usize> = sc.vec(n);
    s.sort();
    s.reverse();

    let mut dp = vec![0; x + 1];
    dp[x] = 1;
    for i in 0..n {
        let mut next = vec![0; x + 1];
        for j in 0..(x + 1) {
            // unused
            next[j] += dp[j] * (n - 1 - i);
            next[j] %= MOD;

            // used
            next[j % s[i]] += dp[j];
            next[j % s[i]] %= MOD;
        }
        dp = next;
    }

    let mut ans = 0;
    for i in 0..s[n - 1] {
        ans += dp[i] * i;
        ans %= MOD;
    }
    println!("{}", ans);
}

pub struct Scanner<R> {
    stdin: R,
}

impl<R: std::io::Read> Scanner<R> {
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .stdin
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r')
            .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}

エクサウィザーズ 2019 E - Black or White

問題

atcoder.jp

解法

毎回 (i個目を取る時に白が無くなっている確率) + (i個目を取る時に白も黒も無くなっていない確率)/2 を出力する。 (i 個目を取る時に白が無くなっている確率) = (i-1個目を取る時に白が無くなっている確率) + (i-1個目で最後の白を取る確率) で求まる。

コード

use mod_int::ModInt;

const MOD: usize = 1e9 as usize + 7;

fn main() {
    let s = std::io::stdin();
    let mut sc = Scanner { stdin: s.lock() };
    let b: usize = sc.read();
    let w: usize = sc.read();
    let combination = Combination::new(b + w + 1, MOD);
    let mut inv_pow2 = vec![ModInt::new(1); b + w + 1];
    inv_pow2[1] = ModInt::new(2).pow(MOD - 2);
    for i in 1..(b + w) {
        inv_pow2[i + 1] = inv_pow2[i] * inv_pow2[1];
    }
    let mut w_zero = vec![ModInt::new(0); b + w + 1];
    for i in 0..(w + b) {
        if i + 1 > w {
            w_zero[i + 1] = w_zero[i] + combination.get(i - 1, w - 1) * inv_pow2[i];
        }
    }
    let mut b_zero = vec![ModInt::new(0); b + w + 1];
    for i in 0..(b + w) {
        if i + 1 > b {
            b_zero[i + 1] = b_zero[i] + combination.get(i - 1, b - 1) * inv_pow2[i];
        }
    }
    // eprintln!("{:?}", inv_pow2);

    for i in 1..(b + w + 1) {
        // black==0
        let b_zero = if i > b { b_zero[i] } else { ModInt::new(0) };
        // white==0
        let w_zero = if i > w { w_zero[i] } else { ModInt::new(0) };
        let other = ModInt::new(1) - b_zero - w_zero;
        let ans = other * inv_pow2[1] + w_zero;
        // eprintln!("b_zero={} w_zero={} other={}", b_zero.0, w_zero.0, other.0);
        println!("{}", ans.0);
    }
}

pub mod mod_int {
    use super::MOD;
    use std::ops::{Add, AddAssign, Mul, MulAssign, Sub, SubAssign};

    type Num = usize;

    #[derive(Clone, Copy, Debug)]
    pub struct ModInt<T: Copy + Clone>(pub T);

    impl Add<ModInt<Num>> for ModInt<Num> {
        type Output = ModInt<Num>;
        fn add(self, rhs: ModInt<Num>) -> ModInt<Num> {
            self + rhs.0
        }
    }

    impl Add<Num> for ModInt<Num> {
        type Output = ModInt<Num>;
        fn add(self, rhs: Num) -> ModInt<Num> {
            let mut t = rhs + self.0;
            if t >= MOD {
                t = t - MOD;
            }
            ModInt(t)
        }
    }

    impl Sub<Num> for ModInt<Num> {
        type Output = ModInt<Num>;
        fn sub(self, rhs: Num) -> ModInt<Num> {
            let rhs = if rhs >= MOD { rhs % MOD } else { rhs };
            let value = if self.0 < rhs { self.0 + MOD } else { self.0 };
            ModInt(value - rhs)
        }
    }

    impl Sub<ModInt<Num>> for ModInt<Num> {
        type Output = ModInt<Num>;
        fn sub(self, rhs: ModInt<Num>) -> ModInt<Num> {
            self - rhs.0
        }
    }

    impl AddAssign<Num> for ModInt<Num> {
        fn add_assign(&mut self, other: Num) {
            *self = *self + other;
        }
    }
    impl AddAssign<ModInt<Num>> for ModInt<Num> {
        fn add_assign(&mut self, other: ModInt<Num>) {
            *self = *self + other;
        }
    }

    impl SubAssign<Num> for ModInt<Num> {
        fn sub_assign(&mut self, other: Num) {
            *self = *self - other;
        }
    }

    impl SubAssign<ModInt<Num>> for ModInt<Num> {
        fn sub_assign(&mut self, other: ModInt<Num>) {
            *self = *self - other;
        }
    }

    impl Mul<ModInt<Num>> for ModInt<Num> {
        type Output = ModInt<Num>;

        fn mul(self, rhs: ModInt<Num>) -> ModInt<Num> {
            self * rhs.0
        }
    }
    impl Mul<Num> for ModInt<Num> {
        type Output = ModInt<Num>;

        fn mul(self, rhs: Num) -> ModInt<Num> {
            let t = (self.0 * rhs) % MOD;
            ModInt(t)
        }
    }

    impl MulAssign<Num> for ModInt<Num> {
        fn mul_assign(&mut self, rhs: Num) {
            *self = *self * rhs;
        }
    }

    impl MulAssign<ModInt<Num>> for ModInt<Num> {
        fn mul_assign(&mut self, rhs: ModInt<Num>) {
            *self = *self * rhs;
        }
    }

    impl ModInt<Num> {
        pub fn new(value: Num) -> Self {
            ModInt(value)
        }

        pub fn pow(self, e: usize) -> ModInt<Num> {
            let mut result = ModInt::new(1);
            let mut cur = self;
            let mut e = e;
            while e > 0 {
                if e & 1 == 1 {
                    result *= cur;
                }
                e >>= 1;
                cur *= cur;
            }
            result
        }
    }
}

pub struct Combination {
    fact: Vec<usize>,
    inv_fact: Vec<usize>,
    modulo: usize,
}

impl Combination {
    pub fn new(max: usize, modulo: usize) -> Combination {
        let mut inv = vec![0; max + 1];
        let mut fact = vec![0; max + 1];
        let mut inv_fact = vec![0; max + 1];
        inv[1] = 1;
        for i in 2..(max + 1) {
            inv[i] = inv[modulo % i] * (modulo - modulo / i) % modulo;
        }
        fact[0] = 1;
        inv_fact[0] = 1;
        for i in 0..max {
            fact[i + 1] = fact[i] * (i + 1) % modulo;
        }
        for i in 0..max {
            inv_fact[i + 1] = inv_fact[i] * inv[i + 1] % modulo;
        }
        Combination {
            fact: fact,
            inv_fact: inv_fact,
            modulo: modulo,
        }
    }

    pub fn get(&self, x: usize, y: usize) -> ModInt<usize> {
        assert!(x >= y);
        ModInt::new(
            self.fact[x] * self.inv_fact[y] % self.modulo * self.inv_fact[x - y] % self.modulo,
        )
    }

    pub fn h(&self, n: usize, r: usize) -> ModInt<usize> {
        self.get(n + r - 1, r)
    }
}

pub struct Scanner<R> {
    stdin: R,
}

impl<R: std::io::Read> Scanner<R> {
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .stdin
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r')
            .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}

フルマラソンを走った時のメモ

初めてフルマラソンを走った。それなりに準備していったが、思ったとおりには走れなかった。今後も続けていきたい感じはするので、メモを残しておく。

準備として、本番前の2ヶ月は毎週1回20km走った。近所を走るのは苦手なので、毎回わざわざ水戸まで行って、水戸から大洗まで走るというコースで練習していた。これで基礎的な体力はできていたと思う。実際にマラソンでも、折り返し地点まではいつもの練習通りのペースで走れていた。だが、マラソンは42.195kmあるので、折り返しまではチュートリアルで、30kmまでは準備体操、30kmからマラソンが始まっていた。本番では折り返しまで普通に走り、そこから30kmまでペースが落ちていき、30kmから完全に歩くという感じになってしまった。体力が尽きたとか、長時間コンクリートの上を走り続けたので膝が痛くなったとかいったものではなく、前半の分の筋肉痛が後半に早くも出始めていて、足に力が入らなくなっていた。膝が痛くならないようにフォームを気をつけたり、水分補給をこまめに行ったりしていたが、筋肉が痛くなるのは想定外だった。前半に飛ばすと後半バテるというのはスタミナの話ではなく、前半の負荷が後半に筋肉痛として発生して動けなくなるということでもあったらしい。42kmの練習を少なくとも1回はやっておくべきだった。

それ以外の知見

  • 荷物置き場があり、リュック1個くらいなら普通に預けておける。ガバガバの管理なので貴重品などは置けない。
  • 給水所が3kmおきくらいにあり、トイレも1kmおきにあるので、水分に関しては全く不自由しなかった。
  • 給水所には食品もあり、アンパンなども食べられた。
  • 食品の種類は限られているので、アミノ酸ゼリーなど自分の好きな物を携帯している人も多く居た。
  • 冷却スプレーがどのくらい効くのかはわからないが、携帯している人が多かった。練習で必要だと感じたら当日も持っていったほうが良さそう。
  • イヤホンをしている人が結構居た。禁止されていない大会ではイヤホンを持っていっても良いかも知れない。

キーエンス プログラミング コンテスト 2019: E - Connecting Cities

問題

atcoder.jp

解法

A_i の値が大きい方から小さい方に辺を張ると考えても良いので、そう考える。

 i < j < k, A_k \geq A_i, A_k \geq > A_j となるような i, j, k を考え、頂点kからiかjのどちらかに辺を引くことを考える。

  • i-j 間のコストは cost_{i,j} = (j-i) \times D + A_i + A_j
  • j-k 間のコストは cost_{j,k} = (k-j) \times D + A_k + A_j
  • i-k 間のコストは cost_{i,k} = (k-i) \times D + A_i + A_k

 cost_{i,k} < cost_{j,k} の場合、  (j-i) \times D + A_i < A_j だから  cost_{i,j} < 2 A_j < A_k + A_j < cost_{j,k} だから j-k 間に辺が張られるより先に i-k 間および i-j 間にパスが存在するので、 j-k 間に辺が張られることはない。

同様にして  cost_{j,k} < cost_{i,k} の場合、 i-k 間に辺が張られることはない。

よって頂点 k から  i < k, A_i \leq A_k となるような頂点 i へ辺を張ることを考える時、 cost_{i,k} が最小であるような i のみについて考えれば良い。  k < i, A_i \leq A_k となるような i についても同様。

コード

use std::cmp;

const INF: usize = 1e16 as usize;

fn main() {
    let s = std::io::stdin();
    let mut sc = Scanner { stdin: s.lock() };
    let n = sc.read();
    let d: usize = sc.read();
    let a: Vec<usize> = sc.vec(n);

    let mut ai: Vec<(usize, usize)> = a.iter().enumerate().map(|(i, &a)| (a, i)).collect();
    ai.sort();

    let mut left_seg = SegmentTree::new(n, (INF, 0), |a, b| cmp::min(a, b));
    let mut right_seg = SegmentTree::new(n, (INF, 0), |a, b| cmp::min(a, b));

    let mut edges = vec![];
    for (_, i) in ai.into_iter() {
        if i > 0 {
            let (tmp, j) = left_seg.query(0, i);
            if tmp < INF {
                let cost = (i - j) * d + a[i] + a[j];
                edges.push((cost, i, j));
            }
        }
        if i + 1 < n {
            let (tmp, j) = right_seg.query(i + 1, n);
            if tmp < INF {
                let cost = (j - i) * d + a[i] + a[j];
                edges.push((cost, i, j));
            }
        }
        left_seg.update(i, (a[i] + (n - i) * d, i));
        right_seg.update(i, (a[i] + i * d, i));
    }
    edges.sort();

    let mut ans = 0;
    let mut uf = UnionFind::new(n);

    for (cost, i, j) in edges.into_iter() {
        if uf.find(i) == uf.find(j) {
            continue;
        }
        uf.unite(i, j);
        ans += cost;
    }

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

pub struct SegmentTree<T, F> {
    seg: Vec<T>,
    n: usize,
    f: F,
    initial_value: T,
}

impl<T: Copy, F> SegmentTree<T, F>
where
    F: Fn(T, T) -> T,
{
    pub fn new(size: usize, initial_value: T, f: F) -> SegmentTree<T, F> {
        let mut m = 1;
        while m <= size {
            m <<= 1;
        }
        SegmentTree {
            seg: vec![initial_value; m * 2],
            n: m,
            f: f,
            initial_value: initial_value,
        }
    }

    pub fn update(&mut self, k: usize, value: T) {
        let mut k = k;
        k += self.n - 1;
        self.seg[k] = value;
        while k > 0 {
            k = (k - 1) >> 1;
            self.seg[k] = (self.f)(self.seg[k * 2 + 1], self.seg[k * 2 + 2]);
        }
    }

    /// Get the minimum value in the array in the range [a, b)
    ///
    /// # Panics
    ///
    /// Panics if `a >= b`.
    pub fn query(&self, a: usize, b: usize) -> T {
        assert!(a < b);
        self.query_range(a, b, 0, 0, self.n)
    }

    fn query_range(&self, a: usize, b: usize, k: usize, l: usize, r: usize) -> T {
        if r <= a || b <= l {
            self.initial_value
        } else if a <= l && r <= b {
            self.seg[k]
        } else {
            let x = self.query_range(a, b, k * 2 + 1, l, (l + r) >> 1);
            let y = self.query_range(a, b, k * 2 + 2, (l + r) >> 1, r);
            (self.f)(x, y)
        }
    }
}

pub struct UnionFind {
    parent: Vec<usize>,
    sizes: Vec<usize>,
    size: usize,
}

impl UnionFind {
    pub fn new(n: usize) -> UnionFind {
        UnionFind {
            parent: (0..n).map(|i| i).collect::<Vec<usize>>(),
            sizes: vec![1; n],
            size: n,
        }
    }

    pub fn find(&mut self, x: usize) -> usize {
        if x == self.parent[x] {
            x
        } else {
            let px = self.parent[x];
            self.parent[x] = self.find(px);
            self.parent[x]
        }
    }

    pub fn unite(&mut self, x: usize, y: usize) -> bool {
        let parent_x = self.find(x);
        let parent_y = self.find(y);
        if parent_x == parent_y {
            return false;
        }

        let (large, small) = if self.sizes[parent_x] < self.sizes[parent_y] {
            (parent_y, parent_x)
        } else {
            (parent_x, parent_y)
        };

        self.parent[small] = large;
        self.sizes[large] += self.sizes[small];
        self.sizes[small] = 0;
        self.size -= 1;
        return true;
    }
}

pub struct Scanner<R> {
    stdin: R,
}

impl<R: std::io::Read> Scanner<R> {
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .stdin
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r')
            .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}

Codeforces Round #541 (Div. 2) E. String Multiplication

問題

http://codeforces.com/contest/1131/problem/E

ある文字列 S と T が与えられた時、文字列 S の長さを m として S と T の積を  S \cdot T = T + S_1 + T + S_2 + ... + T + S_m + T と定義する。文字列 p1, p2, ..., pN が与えられるので  (...((p_1 \cdot p_2)\cdot p_3)...)\cdot p_N の中で同じ文字が連続して現れる回数の最大値を求めよ。

解法

pN 以外はぶつ切りにされてしまうが、 pN を構成する文字種が全て同じでとき、その文字を c とすると、  (...((p_1 \cdot p_2)\cdot p_3)...)\cdot p_N にの中で c が連続して現れる回数の最大値  C_N は、  C_N = (C_{N-1}+1)\times len(P_N) + C_{N-1} と表される。よって再帰的に求めていくことが出来る。

コード

use std::cmp;

fn main() {
    let s = std::io::stdin();
    let mut sc = Scanner { stdin: s.lock() };

    let n: usize = sc.read();
    let p: Vec<Vec<usize>> = (0..n)
        .map(|_| {
            sc.chars()
                .into_iter()
                .map(|c| c as usize - 'a' as usize)
                .collect()
        })
        .collect();

    let prefix_suffix: Vec<_> = p
        .iter()
        .map(|p| {
            let length = p.len();
            let head = p[0];
            let tail = p[length - 1];
            let prefix = p.iter().take_while(|&&c| c == head).count();
            let suffix = p.iter().rev().take_while(|&&c| c == tail).count();
            (head, tail, prefix, suffix)
        })
        .collect();

    let t = (0..n)
        .rev()
        .skip_while(|&i| {
            let (_, _, prefix, _) = prefix_suffix[i];
            prefix == p[i].len()
        })
        .next()
        .unwrap_or(0);

    let mut ans = vec![[0; 26]; n];
    for i in t..n {
        let (head, tail, prefix, suffix) = prefix_suffix[i];
        let length = p[i].len();

        if i == 0 {
            ans[i] = calc_longest(&p[i]);
        } else if i == t {
            assert!(prefix != length);
            let mut has = [false; 26];
            let mut max = calc_longest(&p[i]);
            for p in p[0..i].iter() {
                for &c in p.iter() {
                    has[c] = true;
                }
            }

            if head == tail && has[head] {
                update_max(&mut max[head], suffix + 1 + prefix);
            }
            if head != tail {
                if has[head] {
                    max[head] += 1;
                }
                if has[tail] {
                    max[tail] += 1;
                }
            }
            ans[i] = max;
        } else {
            let inner = ans[i - 1];
            let mut max = calc_longest(&p[i]);
            update_max(
                &mut max[head],
                cmp::min((inner[head] + 1) * length + inner[head], 1e9 as usize),
            );
            for i in 0..26 {
                if inner[i] > 0 {
                    update_max(&mut max[i], 1);
                }
            }
            ans[i] = max;
        }
    }

    println!("{}", ans[n - 1].iter().max().unwrap());
}

fn calc_longest(last: &Vec<usize>) -> [usize; 26] {
    let mut cur = 1;
    let n = last.len();
    let mut max = [0; 26];
    for i in 1..n {
        if last[i - cur] == last[i] {
            cur += 1;
        } else {
            update_max(&mut max[last[i - cur]], cur);
            cur = 1;
        }
    }
    update_max(&mut max[last[last.len() - 1]], cur);
    max
}

fn update_max<T: PartialOrd>(a: &mut T, b: T) {
    if *a < b {
        *a = b
    }
}

pub struct Scanner<R> {
    stdin: R,
}

impl<R: std::io::Read> Scanner<R> {
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .stdin
            .by_ref()
            .bytes()
            .map(|b| match b {
                Ok(b) => b,
                _ => panic!("{:?}", b),
            })
            .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r')
            .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r')
            .collect::<Vec<_>>();
        match unsafe { std::str::from_utf8_unchecked(&buf) }.parse() {
            Ok(r) => r,
            _ => panic!("Parse Error: {:?}", String::from_utf8(buf)),
        }
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}

AtCoder Regular Contest 102 D - All Your Paths are Different Lengths

問題

atcoder.jp

解法

頂点 v から v+1 へ、長さ 0 の辺と、長さ  2^v の辺を張る。これによって、 0, 1, 2, 3, ... , 2^{(n-1)}-1 の長さのパスが存在することになる。

次に、頂点を  n-2, n-3, ..., 0 の順番で見ていく。頂点 0 から頂点 v へは  0, 1, 2, ... , 2^v-1 の長さのパスが存在するので、頂点 v から頂点 n-1 へ長さ t の辺を張ると、新たに  t, t+1, t+2, ... , t+2^v-1 の長さのパスが追加されることになる。そこで  t=l-2^v として辺を張ることで、  l-2^v, l-2^v+1, ... , l-1 のパスを追加することが出来る。これを繰り返していき、  2^{(n-1)}, ... , l-1 のパスを全て加えることができれば良い。

コード

fn main() {
    let s = std::io::stdin();
    let mut sc = Scanner { stdin: s.lock() };
    let mut l: usize = sc.read();

    let mut r = 0;
    while (1 << (r + 1)) <= l {
        r += 1;
    }

    let n = r + 1;
    let mut graph = vec![vec![]; n];
    for i in 0..r {
        graph[i].push((i + 1, 1 << i));
        graph[i].push((i + 1, 0));
    }

    let sum = (1 << r) - 1;
    for i in (0..(n - 1)).rev() {
        let to_i = (1 << i) - 1;
        if l >= to_i + 1 {
            let new_edge = l - to_i - 1;
            if new_edge > sum {
                // add paths [new_edge, new_edge+1, ..., l-1]
                graph[i].push((n - 1, new_edge));
                l = new_edge;
            }
        }
    }

    println!("{} {}", n, graph.iter().map(|e| e.len()).sum::<usize>());

    for (from, to, w) in graph
        .into_iter()
        .enumerate()
        .flat_map(|(i, e)| e.into_iter().map(move |(to, w)| (i, to, w)))
    {
        println!("{} {} {}", from + 1, to + 1, w);
    }
}

pub struct Scanner<R> {
    stdin: R,
}

impl<R: std::io::Read> Scanner<R> {
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .stdin
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n')
            .take_while(|&b| b != b' ' && b != b'\n')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}

「第3回 RCO日本橋ハーフマラソン 予選」の復習

atcoder.jp

このコンテストに出たのですが、散々な結果だった。ただ、終わった後に流れてきた解法を見ると結構シンプルなものが多かったので、復習した。

A - ツーリストXの旅行計画

A - ツーリストXの旅行計画


分散が出てきてややこしい気持ちになるが、平均値を決め打ちすると、各辺のコストが固定の値になり、純粋な巡回セールスマン問題 (TSP) になる。

画像検索した感じだと 2-opt が初心者でも実装しやすそうに見えるので、実装してみた。

方針

  • 平均値を乱数で決め打ちする。
  • 最初は貪欲にとりあえず解を作る。スタート地点が決まっているので、スタート地点から、その都度、最もコストの低い辺を選びながら、移動していく。
  • 解に含まれている辺から 2 本選び、 2-opt 的に組み換える。これを全ての辺の組について試し、最もコストが減る組み合わせについて組み換える。これの組み換えは300回くらいやる。
  • これらを時間の限り繰り返し、最終的に一番良かった解を出力する。

最初の貪欲解

全くひねりなく、今いる頂点から一番低コストで行ける頂点に行く。

tuple<vector<size_t>, double> greedy() {
  double total_cost = 0.0;
  vector<size_t> res;
  vector<bool> vis(N, false);

  size_t cur = 0;
  vis[cur] = true;
  res.push_back(cur);

  REP(i, (N - 1)) {
    double cur_min = INF;
    size_t cur_next = N;
    REP(next, N) {
      if (vis[next]) {
        continue;
      }
      if (dist[cur][next] < cur_min) {
        cur_next = next;
        cur_min = dist[cur][next];
      }
    }

    total_cost += dist[cur][cur_next];
    res.push_back(cur_next);
    vis[cur_next] = true;
    cur = cur_next;
  }

  res.push_back(0);
  total_cost += dist[cur][0];

  return make_tuple(res, total_cost);
}

2-opt

Wikipedia を見ながら雰囲気で実装した。これも全くひねらず、全ての辺の組について組み換えてみて、一番コストを減らせる組について実際に組み換える。

double improve_2opt(vector<size_t>& path) {
  double cur_improvement = 0.0;
  size_t index_from = 0;
  size_t index_to = 0;

  REP(i, N) {
    auto from1 = path[i];
    auto to1 = path[i + 1];
    auto cost1 = dist[from1][to1];
    for (size_t j = i + 1; j < N; j++) {
      auto from2 = path[j];
      auto to2 = path[j + 1];
      auto cost2 = dist[from2][to2];

      auto prev_cost = cost1 + cost2;
      auto next_cost = dist[from1][from2] + dist[to1][to2];
      if (prev_cost > next_cost && prev_cost - next_cost > cur_improvement) {
        cur_improvement = prev_cost - next_cost;
        index_from = i + 1;
        index_to = j + 1;
      }
    }
  }
  if (index_from == index_to) {
    return 0.0;
  }

  reverse(path.begin() + index_from, path.begin() + index_to);
  return cur_improvement;
}

全体

#include <algorithm>
#include <cassert>
#include <chrono>
#include <cmath>
#include <iostream>
#include <iterator>
#include <tuple>
#include <vector>

using namespace std;

#define REP(i, n) for (size_t(i) = 0; (i) < (n); (i)++)

template <typename T>
std::ostream& operator<<(std::ostream& out, const std::vector<T>& v) {
  if (!v.empty()) {
    out << '[';
    std::copy(v.begin(), v.end(), std::ostream_iterator<T>(out, ", "));
    out << "\b\b]";
  }
  return out;
}

template <typename T1, typename T2>
std::ostream& operator<<(std::ostream& out, const std::pair<T1, T2>& p) {
  out << "[" << p.first << ", " << p.second << "]";
  return out;
}

uint64_t xor_shift64(uint64_t* state) {
  uint64_t x = *state;
  x ^= x << 13;
  x ^= x >> 7;
  x ^= x << 17;
  *state = x;
  return x;
}

/* ここまでテンプレート */

const double INF = 1e18;

size_t N;
double X[200], Y[200];
double dist[200][200];

double calc_distance(double x1, double y1, double x2, double y2) {
  double dx = x1 - x2;
  double dy = y1 - y2;
  return sqrt(dx * dx + dy * dy);
}

double improve_2opt(vector<size_t>& path) {
  double cur_improvement = 0.0;
  size_t index_from = 0;
  size_t index_to = 0;

  REP(i, N) {
    auto from1 = path[i];
    auto to1 = path[i + 1];
    auto cost1 = dist[from1][to1];
    for (size_t j = i + 1; j < N; j++) {
      auto from2 = path[j];
      auto to2 = path[j + 1];
      auto cost2 = dist[from2][to2];

      auto prev_cost = cost1 + cost2;
      auto next_cost = dist[from1][from2] + dist[to1][to2];
      if (prev_cost > next_cost && prev_cost - next_cost > cur_improvement) {
        cur_improvement = prev_cost - next_cost;
        index_from = i + 1;
        index_to = j + 1;
      }
    }
  }
  if (index_from == index_to) {
    return 0.0;
  }

  reverse(path.begin() + index_from, path.begin() + index_to);
  return cur_improvement;
}

tuple<vector<size_t>, double> greedy() {
  double total_cost = 0.0;
  vector<size_t> res;
  vector<bool> vis(N, false);

  size_t cur = 0;
  vis[cur] = true;
  res.push_back(cur);

  REP(i, (N - 1)) {
    double cur_min = INF;
    size_t cur_next = N;
    REP(next, N) {
      if (vis[next]) {
        continue;
      }
      if (dist[cur][next] < cur_min) {
        cur_next = next;
        cur_min = dist[cur][next];
      }
    }

    total_cost += dist[cur][cur_next];
    res.push_back(cur_next);
    vis[cur_next] = true;
    cur = cur_next;
  }

  res.push_back(0);
  total_cost += dist[cur][0];

  return make_tuple(res, total_cost);
}

tuple<vector<size_t>, double> solve(double average) {
  REP(i, N) REP(j, N) {
    auto d = calc_distance(X[i], Y[i], X[j], Y[j]);
    dist[i][j] = (d - average) * (d - average);
    dist[j][i] = dist[i][j];
  }

  vector<size_t> path;
  double total_cost;
  tie(path, total_cost) = greedy();

  REP(i, 300) {
    double improvement = improve_2opt(path);
    if (improvement < 1e-9) {
      break;
    }
    assert(total_cost >= improvement);
    total_cost -= improvement;
  }
  return make_tuple(path, total_cost);
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  auto start = chrono::system_clock::now();

  cin >> N;
  REP(i, N) { cin >> X[i] >> Y[i]; }

  uint64_t random_state = 71;

  vector<vector<size_t>> paths;
  vector<tuple<double, size_t>> costs;
  while (true) {
    double r = xor_shift64(&random_state);
    r /= numeric_limits<uint64_t>::max();

    double average = 200.0 + r * 200.0;
    vector<size_t> path;
    double cost;
    tie(path, cost) = solve(average);
    costs.emplace_back(cost, paths.size());
    paths.emplace_back(path);

    auto ms = chrono::duration_cast<chrono::milliseconds>(
                  chrono::system_clock::now() - start)
                  .count();
    if (ms > 1900) {
      break;
    }
  }
  sort(costs.begin(), costs.end());

  size_t min_cost_index = get<1>(costs[0]);

  const auto& path = paths[min_cost_index];
  REP(i, N) { cout << path[i] << endl; }
}

結果

Submission #4246661 - 第3回 RCO日本橋ハーフマラソン 予選

これで 3766621 点になる。コンテスト本番だと8位くらい。

B - ファーマーXの収穫計画

B - ファーマーXの収穫計画

各マスの数字は一様乱数で決まっているので 8, 7, 6 を思考停止で全部 9 にしてしまっても 1700 手くらいで済みそうという考察が出来るらしい(すごい)。9の島は9個以上の要素が連なっていないと回収できないので、小さい島は他の島と頑張って接続したい。

方針

  • 8, 7, 6 を全て 9 にしてしまう。
  • 小さい島からダイクストラでつなげていって大きい島になるようにする。
  • 一気に回収する。

コード

ビジュアライザを見た限り微妙にバグっているが、疲れたので解散。

#include <algorithm>
#include <cassert>
#include <chrono>
#include <cmath>
#include <iostream>
#include <iterator>
#include <queue>
#include <tuple>
#include <vector>

using namespace std;

#define REP(i, n) for (int(i) = 0; (i) < (n); (i)++)

template <typename T>
std::ostream& operator<<(std::ostream& out, const std::vector<T>& v) {
  if (!v.empty()) {
    out << '[';
    std::copy(v.begin(), v.end(), std::ostream_iterator<T>(out, ", "));
    out << "\b\b]";
  }
  return out;
}

template <typename T1, typename T2>
std::ostream& operator<<(std::ostream& out, const std::pair<T1, T2>& p) {
  out << "[" << p.first << ", " << p.second << "]";
  return out;
}

uint64_t xor_shift64(uint64_t* state) {
  uint64_t x = *state;
  x ^= x << 13;
  x ^= x >> 7;
  x ^= x << 17;
  *state = x;
  return x;
}

// --- template ---

class UnionFind {
 private:
  struct nodeinfo {
    int par;
    int rank;
    int size;
    nodeinfo(int p) : par(p), rank(0), size(1) {}
  };
  std::vector<nodeinfo> node;

 public:
  UnionFind(int n) : node() {
    node.reserve(n);
    for (int i = 0; i < n; ++i) {
      node.push_back(nodeinfo(i));
    }
  }
  int root(int x) {
    if (node[x].par == x) {
      return x;
    }
    return node[x].par = root(node[x].par);
  }
  void unite(int x, int y) {
    x = root(x);
    y = root(y);
    if (x == y) {
      return;
    }
    if (node[x].rank < node[y].rank) {
      node[x].par = y;
      node[y].size += node[x].size;
      node[x].size = 0;
    } else {
      node[y].par = x;
      node[x].size += node[y].size;
      node[y].size = 0;
      if (node[x].rank == node[y].rank) {
        ++node[x].rank;
      }
    }
  }

  bool is_same_set(int x, int y) { return root(x) == root(y); }

  int size(int x) {
    x = root(x);
    return node[x].size;
  }
};

using State = tuple<double, int, int>;
const int DX[] = {0, 0, 1, -1};
const int DY[] = {1, -1, 0, 0};
const int INF = 1e9;

int N, M;
int A[50][50];

auto backward(vector<vector<double>>& dist, int i, int j) {
  vector<tuple<int, int>> ans;
  while (dist[i][j] > 0) {
    auto cur_min = dist[i][j];
    assert(cur_min < INF);
    tuple<int, int> next = make_tuple(i, j);

    REP(d, 4) {
      int ni = i + DX[d];
      int nj = j + DY[d];
      if (ni < 0 || nj < 0 || ni >= N || nj >= N) continue;

      if (dist[ni][nj] < cur_min) {
        next = make_tuple(ni, nj);
        cur_min = dist[ni][nj];
      }
    }

    int ni, nj;
    tie(ni, nj) = next;

    assert(ni != i || nj != j);
    dist[i][j] = INF;
    ans.emplace_back(ni, nj);
    i = ni;
    j = nj;
  }

  return ans;
}

vector<tuple<int, int>> dijkstra(int si, int sj, UnionFind& uf) {
  const int start_size = uf.size(si * N + sj);

  priority_queue<State, vector<State>, greater<State>> q;
  vector<vector<double>> dist(N, vector<double>(N, INF));
  dist[si][sj] = 0;
  q.emplace(0, si, sj);
  while (q.size() != 0) {
    int cost, i, j;
    tie(cost, i, j) = q.top();
    q.pop();

    if (A[i][j] == 9 && uf.size(i * N + j) + start_size >= 9) {
      return backward(dist, i, j);
    }

    REP(d, 4) {
      int ni = i + DX[d];
      int nj = j + DY[d];
      if (ni < 0 || nj < 0 || ni >= N || nj >= N) continue;
      double w = 9.00001 - A[ni][nj];
      if (dist[ni][nj] > dist[i][j] + w) {
        dist[ni][nj] = dist[i][j] + w;
        q.emplace(dist[ni][nj], ni, nj);
      }
    }
  }

  return {};
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  vector<tuple<int, int, int>> ans;

  cin >> N >> M;
  REP(i, N) REP(j, N) {
    cin >> A[i][j];
    auto cost = 9 - A[i][j];
    if (cost <= 3 && cost + ans.size() <= M) {
      A[i][j] += cost;
      REP(z, cost) ans.emplace_back(1, i, j);
    }
  }

  UnionFind uf(N * N);
  REP(i, N) REP(j, N) REP(d, 4) {
    int ni = i + DX[d];
    int nj = j + DY[d];
    if (ni < 0 || nj < 0 || ni >= N || nj >= N) continue;
    if (A[i][j] != A[ni][nj]) continue;
    int from = i * N + j;
    int to = ni * N + nj;
    uf.unite(from, to);
  }

  vector<bool> started(N * N, false);
  vector<vector<tuple<int, int>>> paths;
  vector<tuple<double, int, int>> costs;
  REP(i, N) REP(j, N) {
    if (A[i][j] != 9) continue;
    int x = i * N + j;
    x = uf.root(x);

    if (started[x]) continue;
    started[x] = true;

    int size = uf.size(i * N + j);
    if (size >= 9) continue;

    auto path = dijkstra(i, j, uf);
    int cost = 0;
    for (const auto& t : path) {
      int pi, pj;
      tie(pi, pj) = t;
      cost += 9 - A[pi][pj];
    }

    double cost_per_size = cost;
    cost_per_size /= size;
    costs.emplace_back(cost_per_size, cost, paths.size());
    paths.emplace_back(path);
  }

  sort(costs.begin(), costs.end());
  for (const auto& t : costs) {
    double cps;
    int cost;
    int index;
    tie(cps, cost, index) = t;
    const auto& path = paths[index];
    cost = 0;
    for (const auto& s : path) {
      int i, j;
      tie(i, j) = s;
      int turn = 9 - A[i][j];
      cost += turn;
    }

    if (cost + ans.size() >= M - 200) continue;
    for (const auto& s : path) {
      int i, j;
      tie(i, j) = s;
      int turn = 9 - A[i][j];
      REP(z, turn) ans.emplace_back(1, i, j);
      A[i][j] = 9;
    }
  }

  REP(i, N) REP(j, N) REP(d, 4) {
    int ni = i + DX[d];
    int nj = j + DY[d];
    if (ni < 0 || nj < 0 || ni >= N || nj >= N) continue;
    if (A[i][j] != A[ni][nj]) continue;
    int from = i * N + j;
    int to = ni * N + nj;
    uf.unite(from, to);
  }

  vector<tuple<int, int, int>> candidates;
  vector<bool> done(N * N, false);
  REP(i, N) REP(j, N) {
    int x = i * N + j;
    x = uf.root(x);
    if (done[x]) continue;
    done[x] = true;
    if (uf.size(x) < A[i][j]) continue;
    int value = uf.size(x) * A[i][j];
    candidates.emplace_back(value, i, j);
  }

  sort(candidates.rbegin(), candidates.rend());
  for (const auto& t : candidates) {
    int v, i, j;
    tie(v, i, j) = t;
    ans.emplace_back(2, i, j);
    if (ans.size() == M) break;
  }

  for (const auto& t : ans) {
    int o, i, j;
    tie(o, i, j) = t;
    cout << o << " " << i << " " << j << "\n";
  }
}

結果

Submission #4247854 - 第3回 RCO日本橋ハーフマラソン 予選

503599点になる。本番100位くらい。僕は本番これの半分くらいしかとれなかったので、とりあえずよし。

6まで思考停止で9にしてしまうのはやりすぎ感はあるし、もう少し改善できそう。