【Rust】ABC444感想（A~D）

AtCoder Beginner Contest 444

unrated参加しまして、ABCD4完でした。
今回はA~Dの感想を書きます。

A - Repdigit

Charとして受け取り、重複を削除した結果が一種類の文字であればYes、そうでなければNoを出力します。

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

    let mut n = n;
    n.dedup();
    if n.iter().count() == 1 {
        pr("Yes");
    } else {
        pr("No");
    }
}

B - Digit Sum

$N,K \le 10^5$より、桁和の最大値は$9\times 5=45$です。
$1$から$N$までの自然数を全て調べ、桁和が$1$から$45$のそれぞれについて出現回数を数え上げればよいです。

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

    let mut cnt = vec![0; 50];
    for i in 1..=n {
        let mut val = i;
        let mut res = 0;
        while val > 0 {
            res += val % 10;
            val /= 10;
        }
        cnt[res] += 1;
    }
    if k > 49 {
        pr(0);
    }else {
        pr(cnt[k]);
    }
}

C - AtCoder Riko

まず、$L$の候補としてあり得るのは$\sum_{i \in N} A_i$の約数に限ります。
また、AtCoder Rikoは2本から1本にしか分かれないです。

したがって、方針としては長さ$A_i$のAtCoder Rikoの本数をHashMapに登録して、長さが$L$になるように愚直にマッピングし続け、$L$になるようなペアがなければその$L$は実現不可能というふうに判定していけば良さそうです。

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

    let a = a;
    let mut map: HashMap<u64, u64> = HashMap::new();
    for &e in &a {
        *map.entry(e).or_insert(0) += 1;
    }
    let sum = a.iter().sum();
    let divs = divisors(sum);
    let mut ans = vec![];
    for &div in &divs {
        let mut mp = map.clone();
        let mut cloned_a = a.clone();
        let l = sum / div;
        let mut ok = true;
        while let Some(k) = cloned_a.pop() {
            if *mp.get(&k).unwrap_or(&0) == 0 || k == l {
                continue;
            }
            mp.entry(k).and_modify(|v| *v -= 1);
            if l > k && *mp.get(&(l - k)).unwrap_or(&0) > 0 {
                mp.entry(l - k).and_modify(|v| *v -= 1);
            } else {
                ok = false;
            }
            if ok == false {
                break;
            }
        }

        if ok == true {
            ans.push(l);
        }
    }
    ans.sort();
    pr(&ans.iter().join(" "));
}

D - Many Repunit Sum

各$A_i$について、$1$の位から$A_i$の位まで連続して$1$が並びます。
こうした問題設定ではimos法によって各桁ごとに何回$1$が出現するかを$O(\max_{i \in N} A_i)$で計算することができます。

あとは、ただの多倍長整数の足し算なので、繰り上がりを管理しながら1の位から順に値を確定させることでこの問題を解くことができます。

全体計算量は$O(\max_{i \in N} A_i + N)$でこの問題を解くことができました。

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

    let max = 2 * 10usize.pow(5u32) + 9;
    let mut imos = vec![0; max];
    for &e in &a {
        imos[1] += 1;
        imos[e + 1] -= 1;
    }

    for i in 0..max - 1 {
        imos[i + 1] += imos[i];
    }

    let mut carry = 0;
    let mut ans = vec![];
    for i in 1..max - 1 {
        let val = imos[i] + carry;
        if val == 0 {
            break;
        }
        ans.push(val % 10);
        carry = val / 10;
    }

    ans.reverse();
    pr(ans.iter().join(""));
}

まとめ

C問題はいくつものAtCoder Rikoを1本にまとめられるのだと勘違いして、多くの時間を浪費してしまいました。
しかし、68分で4完できたのでだんだんとRustの書き方も馴染んできたといえます。
引き続き頑張ります。