競プロ

AtCoder Beginner Contest 397 参加記

 

AtCoder Begginger Contest 397に参加しました。

青が見えてきたように感じます。最近の精進の成果が出てきて良いですね。

問題の解き方

A. Thermometer

10進数小数で与えられた入力に対して、大小比較をする問題です。誤差が怖いので文字列で受け取って比較しました。

use proconio::input;

fn main() {
    input! {
        x: String,
    }

    if x >= "38.0".to_string() {
        println!("1");
    } else if x >= "37.5".to_string() {
        println!("2");
    } else {
        println!("3");
    }
}

他にも、

(x * 10.0).round()

なども良さそうですね。

B. Ticket Gate Log

前から見ていき、現在が奇数番目か偶数番目かを管理していきました。もっと簡単に連続する部分を数えてもよかったようです。思いつきませんでした。

use proconio::{input, marker::Bytes};

const A: [u8; 2] = [b'i', b'o'];

fn main() {
    input! {
        s: Bytes,
    }

    let mut i = 0;
    let mut ans = 0;
    for &s in &s {
        if s == A[i % 2] {
            i += 1;
        } else {
            ans += 1;
        }
    }
    if i % 2 == 1 {
        ans += 1;
    }

    println!("{ans}");
}

\(i \mod 2\) が偶数であることと、現在が前から見て偶数番目の文字 (0-indexed) であることが同値です。計算量は、 \(O(|S|)\) です。

C. Variety Split Easy

\(A[..i]\) と \(A[..i + 1]\) の種類数の差は、 \(A[..i]\) に \(A[i]\) があるかどうかで \(1\) 増えるかどうかが決まります。 \(A[i..]\) と \(A[i + 1..]\) の種類数の差は、 \(A[i + 1..]\) に \(A[i]\) があるかどうかで \(1\) 減るかどうかが決まります。このように、集合にある要素を加えた（減らした）際の種類数の増減は、 \(O(1)\) で計算できます。

以上のようにして、 \(A[..i]\) と \(A[i..]\) の種類数を別々に管理して更新していきます。種類数の部分をライブラリにしておきました。

use std::hash::Hash;

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

fn main() {
    input! {
        n: usize,
        a: [Usize1; n],
    }

    let mut l_cnt = Counter::new(&[]);
    let mut r_cnt = Counter::new(&a);

    let mut ans = 0;
    for &a in &a {
        l_cnt.incr(a);
        r_cnt.decr(a);
        ans = ans.max(l_cnt.variety() + r_cnt.variety());
    }

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

pub struct Counter<T: Copy + Eq + Hash> {
    values: std::collections::HashMap<T, usize>,
}

impl<T: Copy + Eq + Hash> Counter<T> {
    pub fn new(a: &[T]) -> Self {
        let mut values = std::collections::HashMap::new();
        for &a in a {
            *values.entry(a).or_insert(0) += 1;
        }
        Self {
            values,
        }
    }

    pub fn incr(&mut self, x: T) -> usize {
        *self.values.entry(x).or_insert(0) += 1;
        *self.values.get(&x).unwrap()
    }

    pub fn decr(&mut self, x: T) -> usize {
        let a = *self.values.get(&x).unwrap_or(&0);
        if a <= 1 {
            self.values.remove(&x).unwrap();
            0
        } else {
            self.values.insert(x, a - 1);
            a - 1
        }
    }

    pub fn variety(&self) -> usize {
        self.values.len()
    }
}

計算量は、 \(O(N)\) です。

D. Cubes

これが解けませんでした。解答を見るに、\(x^3 – y^3 = N\) ならば \(x – y \le N^{\frac{1}{3}}\) であることが本質です。どのようにしたら思いつくことができるのでしょうか。

E. Path Decomposition of a Tree

まず、このような分解は存在すれば一意です。よって、ある点を決めて木DPをしながら、子側から分解していくこととします。

途中の状態を考えます。

子が \(3\) つに分かれている場合は、どのようにしても分解できません。

子が \(2\) つに分かれている場合は、その部分と自身を合わせたパスが分解できるなら全て消すことができます。それ以外は不可能です。

子が \(1\) つに分かれている場合は、そのまま繋げます。

これを判定すれば良いです。

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

fn main() {
    input! {
        n: usize,
        k: usize,
        uv: [(Usize1, Usize1); n * k - 1],
    }

    let mut e = vec![vec![]; n * k];
    for &(u, v) in &uv {
        e[u].push(v);
        e[v].push(u);
    }

    let x = f(0, 0, &e, k);
    if x < !0 {
        println!("Yes");
    } else {
        println!("No");
    }
}

fn f(p: usize, i: usize, e: &Vec<Vec<usize>>, k: usize) -> usize {
    let mut child = vec![];
    for &j in &e[i] {
        if j == p {
            continue;
        }
        let x = f(i, j, e, k);
        if x == !0 {
            return !0;
        }
        if x > 0 {
            child.push(x);
        }
    }
    if child.len() == 0 {
        1 % k
    } else if child.len() == 1 {
        let ans = 1 + child[0];
        ans % k
    } else if child.len() == 2 {
        let ans = 1 + child[0] + child[1];
        if ans % k == 0 {
            0
        } else {
            !0
        }
    } else {
        !0
    }
}

計算量は、 \(O(NK)\) となります。

F. Variety Split Hard

Cと同様に探索しようとすると、 \(O(N^2)\) かかってしまいます。高速化をしなければなりません。

\(A[..i]\) と \(A[i..j]\) と \(A[j..]\) に分割するとします。この部分の \(i\) を固定して考えます。このとき、後半部分の分ける位置 \(j\) の選び方として、なるべく同じ数字が左右に分割される位置に選ぶのが最適です。そこで、 \(A[i..]\) のなかに二つ以上存在する数に関してその先頭と末尾の間に \(j\) を選ぶことで種類数を \(1\) 増やすことができます。これを遅延セグ木で管理して、 \(i\) の差分更新をすることで答えがわかります。

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

fn main() {
    input! {
        n: usize,
        a: [Usize1; n],
    }

    let mut l_cnt = Counter::new(&[]);
    let mut r_cnt = Counter::new(&a);
    let mut duplication = LazySegmentTree::<O>::new(&vec![0; n]);
    let mut idxs = vec![vec![]; n];
    for (i, a) in a.iter().enumerate().rev() {
        idxs[*a].push(i);
    }
    for idx in idxs.iter() {
        if idx.len() > 1 {
            duplication.act(idx[idx.len() - 1]..idx[0], 1);
        }
    }

    let mut ans = 0;
    for &a in &a {
        l_cnt.incr(a);
        r_cnt.decr(a);
        let x = idxs[a].pop().unwrap();
        if idxs[a].len() > 1 {
            duplication.act(*idxs[a].last().unwrap()..idxs[a][0], 1);
        }
        if idxs[a].len() > 0 {
            duplication.act(x..idxs[a][0], !0);
        }
        ans = ans.max(l_cnt.variety() + r_cnt.variety() + duplication.fold(..));
    }

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

計算量は、 \(O(N \log N)\) となります。

感想

ABCEFと解けたのでかなりの勝ちでした。Dで詰まった時は大敗を覚悟しましたが、EFと無事に解けたのでよかったです。

木に関しては苦手意識がありましたが、最近の練習で理解が深まったように思います。全方位木DPの練習をしたことで木の性質をなんとなく理解しました。

Fのような差分更新は個人的には得意な考察かもしれません。セグ木を思いつけたのはどうしてなんでしょうか。

CTAサンプル

これはCTAサンプルです。
内容を編集するか削除してください。

RELATED POST