【Rust】ABC433感想（A~D）

AtCoder Beginner Contest 433

後日バーチャル参加して、60分4ペナでのA~D4完でした。
D問題は型推論でi32となりオーバーフローしていて、
usizeと型注釈を書いていれば40分0ペナでした。
今回はA~Dの感想を書きます。

A - Happy Birthday! 4

$i(\ge 0)$年後に$X + i = (Y + i) \times Z$が成立することがあればYes、そうでなければNoを出力します。
問題は$i$の上限をどこまでにするかですが、極端な例として$X=1,Y=100,Z=2$の場合、$100$年後に$X'=X+100=101,Y'=Y+100=200$となり$Y'/X'$が$2$を下回ってしまいます。
したがって、$X,Y$をどのような値にしても$100$年後に比が$2$倍以上になることはないため、$0\le i < 100$の範囲を全探索すればよいです。

use proconio::input;

fn main() {
    input! {
        x: usize,
        y: usize,
        z: usize,
    }

    let mut f = false;
    for i in 0..100 {
        if x + i == (y + i) * z {
            f = true;
        }
    }
    if f {
        println!("Yes");
    }else {
        println!("No");
    }
}

B - Nearest Taller

全体の人数が少ないため、一人一人について自分より左の人の身長を順番に確認し、自分より身長の高い人がいればその人を答えるというアルゴリズムで解くことができます。

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

    let mut ans = vec![];
    for i in 0..a.len() {
        let v = a[i];
        let mut res = -1;
        for j in (0..i).rev() {
            if a[j] > v {
                res = (j + 1) as isize;
                break;
            }
        }
        ans.push(res);
    }
    println!("{}", ans.iter().join("\n"));
}

C - 1122 Substring 2

x(x+1)のように、今見ている数字が$x$、それよりちょうど一つ右にある数字が$x+1$であるような境界を全て検出し、それらの境界全てについて$\text{min}(l:=左にxが連続で何文字続くか、r:=右にx+1が連続で何文字続くか)$を計算し、その総和をとります。

例えば11222333であれば、2,3文字目の間に一つ目の境界があり、$\text{min}(l,r)=2$です。
また、5,6文字目に二つ目の境界があり、$\text{min}(l,r)=3$です。
したがって、この問題の答えは$5$となります。

一つの文字について高々2回までしか参照しないため、全体計算量は$O(N)$で抑えることができ、十分高速です。

use proconio::input;
use proconio::marker::Chars;

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

    let mut ans = 0;
    for i in 0..s.len() -1 {
        if s[i] as usize + 1 == s[i + 1] as usize {
            let mut l = 0;
            let mut r = 0;
            for j in (0..=i).rev() {
                if s[j] == s[i] {
                    l += 1;
                }else {
                    break;
                }
            }
            for j in (i + 1)..s.len() {
                if s[j] == s[i + 1] {
                    r += 1;
                }else {
                    break;
                }
            }
            ans += l.min(r);
        }
    }
    println!("{}", ans);
}

D - 183183

当然、全ての組み合わせを試すと$N(N-1)/2$通りあるので間に合いません。

そこで、あらかじめ各$A_i$について、$A_i \times 10^j \pmod M$した結果を$\text{mods}$テーブルに格納しておきます。
より具体的には、$\text{mods}[*]$の各要素はHashMap(key: 剰余, value: 剰余がkeyとなるような要素の個数)をもち、$\text{mods}[j]$を参照することで任意の桁シフト$j$についてどの剰余がどれだけ存在するかがわかるようになっています。

すると何が嬉しいかというと、ある$j$桁の要素$A_i$を$f(*, A_i)$つまり右側の整数として選択した時、左側の整数は$j$桁分桁シフトしたときの剰余が$(M-(A_i \pmod M)) \pmod M$であるような要素全てを選択することで条件を満たすからです。
これは、前計算で得た$\text{mods}[j]$を参照して$O(1)$で高速に得ることができます。
なお、$A_i \pmod M =0$のとき、$M-(A_i \pmod M)=M$となるため、いささか冗長ですが$(M-(A_i \pmod M)) \pmod M$が正しいです。

実装コード量としてはそれほど多くなく、簡潔に書くことができます。

use proconio::input;
use std::collections::HashMap;

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

    let mut mods= vec![HashMap::new(); 11];
    for &e in &a {
        let mut cur = e;
        for i in 1..11{
            cur = (cur * 10) % m;
            *mods[i].entry(cur).or_insert(0) += 1;
        }
    }

    let mut ans: usize = 0;
    for &e in &a {
        let len = e.to_string().len();
        if mods[len].contains_key(&((m - e % m) % m)) {
            ans += mods[len].get(&((m - e % m) % m)).unwrap();
        }
    }
    println!("{}", ans);
}

まとめ

ratedで出ていたら、またD問題でオーバーフローの変な凡ミスをしなければ水色パフォが出ていたようです。
戦えなくはないかもしれませんが、水色になるのはまだまだ遠い気がします。