AtCoder Beginner Contest 329振り返り

A - Spread

JOINを使えばよい

use itertools::Itertools;
use proconio::{input, marker::Chars};

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

    let str = s.iter().join(" ");
    println!("{}", str);
}

実はそのまま出力してもいい。

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

    for c in s.iter() {
        println!("{}", c);
    }
}

B - Next

最初に最大値を取得し、それを取り除いて最大値を検索する。

use proconio::input;

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

    let max = *a.iter().max().unwrap();
    let ans = a.iter().filter(|&&x| x != max).max().unwrap();
    println!("{}", ans);
}

C - Count xxx

違う文字が見つかるまで右に検索していく。
違う文字が見つかったらそれを記録する。

use std::collections::BTreeSet;

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

fn main() {
    input! {
        n: usize,
        s: Chars,
    }

    #[derive(Debug, PartialEq, Eq, PartialOrd, Ord)]
    struct K {
        c: char,
        len: usize,
    }

    let mut memo: BTreeSet<K> = BTreeSet::new();

    let mut l = 0;
    for r in 0..n {
        if s[l] != s[r] {
            l = r;
        }
        let len = r - l + 1;
        memo.insert(K { c: s[l], len });
    }
    println!("{}", memo.len());
}

D - Election Quick Report

「候補者→投票数」のマップと「投票数→最小番号の候補者」のマップを作っておく。

ここまでしか解けなかった。

use std::collections::BTreeMap;

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

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

    let mut voted = vec![0; n];
    let mut min_idx: BTreeMap<usize, usize> = BTreeMap::new();

    let mut max_v = 0;
    let mut max_i = a[0];

    for i in a.into_iter() {
        let v = voted[i] + 1;
        voted[i] = v;

        // 最小点数更新
        if let Some(&j) = min_idx.get(&v) {
            let m = i.min(j);
            min_idx.insert(v, m);
        } else {
            min_idx.insert(v, i);
        }

        if v >= max_v {
            // 順位が変わるかも?
            if max_v == v {
                // 同点
                if let Some(&j) = min_idx.get(&v) {
                    // 既に点数あるひとがいる
                    max_i = i.min(j);
                    max_v = v;
                } else {
                    max_i = i;
                    max_v = v;
                }
            } else {
                // 最高得点を記録
                max_v = v;
                max_i = i;
            }
        }

        println!("{}", max_i + 1);
    }
}

E - Stamp

スタンプをおせるだけおしていく。隣接するところにもスタンプをおす。
解説見て後から実装したがこれ実装するのは結構しんどい。
速めに見切りをつけるべきだった。

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

fn main() {
    input! {
        n: usize,
        m: usize,
        mut s: Chars,
        t: Chars,
    }

    let mut stack: Vec<usize> = Vec::new();

    let mut cnt = 0;
    for i in 0..(n - m + 1) {
        stack.push(i);
    }

    while let Some(i) = stack.pop() {
        if cnt == n {
            println!("Yes");
            return;
        }

        if !(0..m).all(|j| t[j] == s[i + j] || '?' == s[i + j]) {
            // スタンプをおせない
            continue;
        }

        // スタンプをおす
        let mut stamped = false;
        for j in 0..m {
            if s[i + j] != '?' {
                s[i + j] = '?';
                cnt += 1;
                stamped = true;
            }
        }

        // スタンプを推す意味がない
        if !stamped {
            continue;
        }

        for j in -(m as i64)..=(m as i64) {
            let i = (i as i64) + j;
            if i < 0 || i as usize + m > n {
                continue;
            }
            stack.push(i as usize);
        }
    }

    println!("No");
}

F - Colored Ball

順位表からE問題よりF問題を解いてる人が多かったので見切りをつけてF問題へ。
ナイーブな実装でTLEを起こして先にすすめず。
少ないほうから多いほうへコピーすれば計算量を減らせる。

これは所有権があるRustだとremoveしてinsertするだけで十分間に合う。

use std::collections::BTreeMap;

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

fn main() {
    input! {
        n: usize,
        q: usize,
        c: [Usize1; n],
        queries: [(Usize1, Usize1); q]

    }

    let mut boxes = BTreeMap::new();
    for i in 0..n {
        let mut b = BTreeMap::new();
        b.insert(c[i], 1);
        boxes.insert(i, b);
    }

    for (a, b) in queries {
        let mut x = boxes.remove(&a).unwrap();
        let mut y = boxes.remove(&b).unwrap();

        if x.len() <= y.len() {
            for (k, cnt) in x {
                *y.entry(k).or_insert(0) += cnt;
            }
            println!("{}", y.keys().len());
            boxes.insert(a, BTreeMap::new());
            boxes.insert(b, y);
        } else {
            for (k, cnt) in y {
                *x.entry(k).or_insert(0) += cnt;
            }
            println!("{}", x.keys().len());
            boxes.insert(a, BTreeMap::new());
            boxes.insert(b, x);
        };
    }
}

総括

E問題を速めに見切るスキルとD問題をささっと解ければもっとパフォーマンスでてたかなぁ。
レーティング変動なし。