AtCoder Beginner Contest 331振り返り

A - Tomorrow

繰り上がりを計算していく。
変数が多くて混乱した。

use proconio::input;

fn main() {
    input! {
        M: usize,
        D: usize,
        y: usize,
        m: usize,
        d: usize,
    }

    let mut d = (d + 1) % (D + 1);
    if d == 0 {
        d = 1;

        let mut m = (m + 1) % (M + 1);
        if m == 0 {
            m = 1;
            let y = y + 1;
            println!("{} {} {}", y, m, d);
        } else {
            println!("{} {} {}", y, m, d);
        }
    } else {
        println!("{} {} {}", y, m, d);
    }
}

B - Buy One Carton of Milk

たかだか100万なので全部試す。

use itertools::iproduct;
use proconio::input;

fn main() {
    input! {
        n: usize,
        s: usize, // 6
        m: usize, // 8
        l: usize, // 12
    }

    let mut min = usize::MAX;

    for (ns, nm, nl) in iproduct!(0..=100, 0..=100, 0..=100) {
        let x = ns * 6 + nm * 8 + nl * 12;
        if x >= n {
            min = min.min(ns * s + nm * m + nl * l);
        }
    }

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

C - Sum of Numbers Greater Than Me

ここまでしか解けなかった。
大きい順に合計数を数え上げる。BTreeMapやBTreeSetは昇順でiterateしてくれるのでそれを使う。
mapを使いまわしたので可読性を落としたが、なんとなく解けた。

use itertools::Itertools;
use proconio::input;
use std::collections::BTreeMap;
use std::ops::Bound::{Excluded, Unbounded};

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

    let mut map = BTreeMap::new();
    for i in 0..n {
        *map.entry(a[i]).or_insert(0) += 1;
    }

    let mut prev = 0;
    for ai in map.keys().map(|k| *k).rev().collect_vec() {
        let n = *map.get(&ai).unwrap();
        let cur = prev + ai * n;
        map.insert(ai, cur);
        prev = cur;
    }

    let results: Vec<_> = (0..n)
        .map(|i| {
            if let Some((_, &sum)) = map.range((Excluded(&a[i]), Unbounded)).next() {
                sum
            } else {
                0
            }
        })
        .collect();

    let str: String = results.iter().join(" ");
    println!("{}", str);
}

E - Set Meal

Dはキツそうって読みはあたったが、Eも解けなかった。くやしい。
またまた演算量の見積もりミス。
bをソートするというのは思いついたが、それでも最悪計算量 O(n * m) のケースあるんじゃないか？って深読みした。

use itertools::Itertools;
use proconio::{input, marker::Usize1};
use std::collections::{BTreeMap, BTreeSet};

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

    let bb: Vec<_> = (0..m).sorted_by(|&i, &j| b[j].cmp(&b[i])).collect();

    let mut a_to_b = BTreeMap::new();
    for (c, d) in cd {
        a_to_b.entry(c).or_insert(BTreeSet::new()).insert(d);
    }

    let mut ans = 0;
    for i in 0..n {
        for j in 0..m {
            if a_to_b.entry(i).or_insert(BTreeSet::new()).contains(&bb[j]) {
                // 悪い食べ合わせがある
                continue;
            }

            // 悪い食べ合わせがない
            ans = ans.max(a[i] + b[bb[j]]);
            break;
        }
    }
    println!("{}", ans);
}

総括

今回も演算量の見積もりミス。
Dがキツそうって読めたのは成長か。

ABC330はズタボロでレートを落としてしまったので振り返りすらかけなかったが、ABC311についてはだいたいいつものパフォーマンス。