【Rust】ABC421まとめ（A~D）

AtCoder Beginner Contest 421

バーチャル参加しA~Cの3完（18分0ペナ）です。Dは遅れてACしました。
灰diffしか解いてないのに1100くらいのパフォが出ていて笑いました。
今回はA~Dまでをまとめていきます。

A - Misdelivery

文字列$S_X$と$Y$が同じかどうかを調べるだけですのでとても簡単です。
腕慣らしにはいいですね。

use proconio::input;

fn main() {
    input! {
        n: usize,
        s: [String; n],
        x: usize,
        y: String,
    }

    if s[x - 1] == y {
        println!("Yes");
    } else {
        println!("No");
    }
}

B - Fibonacci Reversed

普通のフィボナッチ数列の一般項は$f_i = f_{i-2}+f_{i-1}$で定義できますが、
今回は$f_i = \text{rev}(f_{i-2}+f_{i-1})$である点のみが異なります。

よって、関数rev(n: usize)を実装できればforループでこの問題を解けそうです。
Rustでは、usizeに対しては、Stringに変換→Charsイテレータに変換→反転→Stringに変換→Result<usize, ParseIntError>にparse→usizeにunwrapという紆余曲折を経なければならないため少し大変です。

use proconio::input;

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

    fn rev(n: usize) -> usize {
        let res = n.to_string().chars().rev().collect::<String>();
        res.parse::<usize>().unwrap()
    }

    let mut f = vec![0; 10];
    f[0] = x;
    f[1] = y;
    for i in 2..10 {
        f[i] = rev(f[i - 1] + f[i - 2])
    }
    println!("{}", f[9]);
}

C - Alternated

これは、まず最終的に到達しなければならない状態がABABAB...かBABABA...の二択であり、そのどちらかに到達するための操作手順の少ない方を選べば良いということがわかれば非常に解きやすいです。
そのどちらかをゴールとすれば、Aのあるべき位置というのが固定されますので、そこと$S$内のAの位置の差分を足しあげていくことで操作手順を求めることができます。
また、操作によってAを適切な位置に移動することで最終的にはBの位置も適切な位置に移動されますので、Bのことは考えなくて構いません。

350点問題だけに少し頭を捻らなくてはならない問題でした。

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

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

    let mut dist_ab = 0;
    let mut dist_ba = 0;
    let mut cur_a = 0;
    for i in 0..2*n {
        let s = s[i];
        if s == 'A' {
            let should = cur_a * 2;
            dist_ab += (i as isize - should as isize).abs();
            dist_ba += (i as isize - (should + 1) as isize).abs();
            cur_a += 1;
        }
    }
    
    println!("{}", dist_ab.min(dist_ba));
}

D - RLE Moving

これは、、、アイデア自体は比較的難しくなく、尺取法やイベントソートの要領で、いくつかの移動をバッチで処理することで計算量を削減しつつ、青木くんと高橋くんが同じマスに存在した回数（以降$\text{ans}$とします）を数え上げるだけなのですが、移動方向や初期位置の場合分けが思った以上に面倒でした。

まず、初期位置が同じかそうでないかで大きく変わるので、初期位置が同じ場合について考えます。
なお、今回の問題では移動後に同じマスに存在したかどうかが問われているため、移動前に同じマスに存在した場合はカウントしないので注意してください。

初期位置が同じ場合

初期位置が同じ場合、高橋くんと青木くんが同じ方向に進む場合にのみ、二人が移動した分だけ$\text{ans}$が増加します。

初期位置が異なる場合

初期位置が異なる場合、高橋くんと青木くんが同じマスに存在しうるのは以下の2パターンがありえます。もちろんですが、二人が交わるまで移動できるという前提です。
また、この場合はある一点でしか二人が同じマスに存在するということはないので、$\text{ans}$は$1$だけ増加します。

以上、適切に事象を構造化し、再利用できる関数などを用いながら綺麗に実装する必要があります。
一応、全く褒められたものではないのですが私のコードを置いておきますので、よければ参考にしてくださいますと幸いです。

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

fn main() {
    input! {
        rt: isize,
        ct: isize,
        ra: isize,
        ca: isize,
        n: isize,
        m: isize,
        l: isize,
        taka: [(Chars, isize); m],
        aoki: [(Chars, isize); l],
    }
    let mut taka = taka;
    let mut aoki = aoki;
    let mut map = std::collections::HashMap::new();
    map.insert('U', (-1, 0));
    map.insert('D', (1, 0));
    map.insert('L', (0, -1));
    map.insert('R', (0, 1));

    fn when_reach(
        map: &std::collections::HashMap<char, (isize, isize)>,
        rs: isize,
        cs: isize,
        d: &Vec<char>,
        rg: isize,
        cg: isize,
        l: isize,
    ) -> isize {
        let (dr, dc) = map[&d[0]];
        if dr == 0 {
            if rs != rg || (cg - cs) * (dc) < 0 || (cg - cs).abs() > l {
                return -1;
            }
            return (cs - cg).abs();
        } else {
            if cs != cg || (rg - rs) * (dr) < 0 || (rg - rs).abs() > l {
                return -1;
            }
            return (rs - rg).abs();
        }
    }

    fn get_rev_move(d: &Vec<char>) -> char {
        match d[0] {
            'U' => 'D',
            'D' => 'U',
            'L' => 'R',
            'R' => 'L',
            _ => unreachable!(),
        }
    }

    fn find_crossing(
        map: &std::collections::HashMap<char, (isize, isize)>,
        rt: isize,
        ct: isize,
        dt: &Vec<char>,
        ra: isize,
        ca: isize,
        da: &Vec<char>,
    ) -> (isize, isize) {
        let (drt, _dct) = map[&dt[0]];
        let (_dra, _dca) = map[&da[0]];
        let (cross_r, cross_c);
        if drt == 0 {
            cross_r = rt;
            cross_c = ca;
        } else {
            cross_r = ra;
            cross_c = ct;
        }
        (cross_r, cross_c)
    }

    let (mut rt, mut ct, mut ra, mut ca) = (rt, ct, ra, ca);
    let mut cur_t = 0;
    let mut cur_a = 0;
    let mut cnt = 0;
    let mut ans = 0;
    while cnt < n {
        let dt = taka[cur_t].0.clone();
        let da = aoki[cur_a].0.clone();
        let lt = taka[cur_t].1;
        let la = aoki[cur_a].1;
        let l = lt.min(la);

        if rt == ra && ct == ca {
            if dt[0] == da[0] {
                ans += l;
            }
        } else {
            if get_rev_move(&dt) == da[0] && (rt == ra || ct == ca) {
                let dist = (rt - ra).abs() + (ct - ca).abs();
                let t_to_a = if ra - rt == 0 {ca - ct} else {ra - rt};
                let mv = if ra - rt == 0 {map[&dt[0]].1} else {map[&dt[0]].0};
                if dist % 2 == 0 && dist / 2 <= l && t_to_a * mv > 0 {
                    ans += 1;
                }
            } else {
                let crossing = find_crossing(&map, rt, ct, &dt, ra, ca, &da);
                let dist_t = when_reach(&map, rt, ct, &dt, crossing.0, crossing.1, l);
                let dist_a = when_reach(&map, ra, ca, &da, crossing.0, crossing.1, l);
                if dist_t != -1 && dist_t == dist_a {
                    ans += 1;
                }
            }
        }

        cnt += l;
        taka[cur_t].1 -= l;
        aoki[cur_a].1 -= l;
        if taka[cur_t].1 == 0 {
            cur_t += 1;
        }
        if aoki[cur_a].1 == 0 {
            cur_a += 1;
        }
        rt += map[&dt[0]].0 * l;
        ct += map[&dt[0]].1 * l;
        ra += map[&da[0]].0 * l;
        ca += map[&da[0]].1 * l;
    }
    println!("{}", ans);
}

まとめ

今回はC問題まで18分で解くことができ、まだまだJavaScriptでの速さに追いついたとは全く言えないものの、Rustへの慣れを感じることができました。
次回のABCは日曜の午後ということで、変則的な開催時刻なのでみなさんご注意ください。
また次回の記事もよければ読んでくださると励みになります。