AtCoder Beginners Selection (ABS) をRustで解いてみた

もはや何番煎じか分かりませんが。。。

入力関数（read1, readn）

fn read1<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn readn<T: std::str::FromStr>(delimiter: &str) -> Vec<T> {
    let s = read1::<String>();
    s.split(delimiter).map(|e| e.parse().ok().unwrap()).collect::<Vec<T>>()
}

以下の回答では、 main() の前に上記のコードを書いています。

read1() ：１行の標準入力を型 T の値として返す
readn(delimiter) ：１行の標準入力を delimiter で区切り、Vec<T> として返す

解答

PracticeA - Welcome to AtCoder

fn main() {
    let a = read1::<i32>();
    let bc = readn::<i32>(" ");
    let b = &bc[0];
    let c = &bc[1];
    let s = read1::<String>();
    println!("{} {}", a+b+c, s);
}

やるだけ。

ABC086A - Product

fn main() {
    let ab = readn::<i32>(" ");
    let a = &ab[0];
    let b = &ab[1];
    if a * b % 2 == 0 {
        println!("Even");
    } else {
        println!("Odd");
    }
}

はい。

ABC081A - Placing Marbles

fn main() {
    let s1s2s3 = read1::<String>();
    let mut ans = 0;
    for i in 0..3 {
        let s: i32 = s1s2s3[i..i+1].parse().ok().unwrap();
        ans += s;
    }
    println!("{}", ans);
}

文字列として受け取って、１個ずつ整数にして足す。

ABC081B - Shift only

fn main() {
    let N = read1::<u32>();
    let mut A = readn::<u32>(" ");
    let mut cnt = 0;
    'solve:
    loop {
        for i in 0..N {
            if A[i as usize] % 2 == 0 {
                A[i as usize] /= 2;
            } else {
                break 'solve;
            }
        }
        cnt += 1;
     }
    println!("{}", cnt);
}

シミュレーション。１個ずつ２で割っていって、行けるとこまで回数を数える。 Rust は 'solve: で示した部分のように、多重ループの中で break によって脱出する先を指定できるのが非常に便利。

ABC087B - Coins

fn main() {
    let a = read1::<u32>();
    let b = read1::<u32>();
    let c = read1::<u32>();
    let x = read1::<u32>();

    let mut ans = 0;

    for a_num in 0..a+1 {
        for b_num in 0..b+1 {
            for c_num in 0..c+1 {
                if 500 * a_num + 100 * b_num + 50 * c_num == x {
                    ans += 1;
                }
            }
        }
    }
    println!("{}", ans);
}

単純に全探索する。

ABC083B - Some Sums

fn main() {
    let nab = readn::<i32>(" ");
    let n = nab[0];
    let a = nab[1];
    let b = nab[2];

    let mut ans = 0;

    for i in 1..n+1 {
        let mut num = i;
        let mut sum = 0;
        loop {
            if num == 0 {
                break;
            }
            sum += num % 10;
            num /= 10;
        }
        if sum >= a && sum <= b {
            ans += i;
        }
    }
    println!("{}", ans);
}

1 から N まで N 通りの num を全探索。 num の１の位を抽出→10で割る→１の位を抽出→…を、各 num が 0 になるまで繰り返す。

ABC088B - Card Game for Two

fn main() {
    let n = read1::<i32>();
    let mut a = readn::<i32>(" ");
    let mut alice = 0;
    let mut bob = 0;

    if n % 2 == 1 {
        a.push(0);
    }
    a.sort();
    for i in 0..(n+1)/2 {
        bob += a[(2 * i) as usize];
        alice += a[(2 * i + 1) as usize];
    }

    println!("{}", alice - bob);
}

カードをソートして、大きい方から交互に取っていく。 N の値が奇数のときは Bob の取る枚数が一枚少なくなるが、はじめから 0 のカードを１枚追加しておけば OK 。

ABC085B - Kagami Mochi

use std::collections::HashSet;

fn main() {
    let mut uniq = HashSet::new();

    let n = read1::<u32>();
    for _ in 0..n {
        uniq.insert(read1::<u32>());
    }
    println!("{}", uniq.len());
}

（鏡餅の段数）＝（unique な直径の鏡餅の枚数）。 HashSet を使えば一発。

ABC085C - Otoshidama

fn main() {
    let ny = readn::<i32>(" ");
    let n = ny[0];
    let y = ny[1];

    let yukichi_max = y/10000;
    if yukichi_max > n {
        println!("-1 -1 -1");
    } else {
        let mut flag = true;
        'solve:
        for i in 0..yukichi_max+1 {
            let ichiyou_max = (y - 10000 * i) / 5000;
            if ichiyou_max > n - i {
                continue;
            } else {
                for j in 0..ichiyou_max+1 {
                    if 10000 * i + 5000 * j + 1000 * (n - i - j) == y {
                        println!("{} {} {}", i, j, n - i - j);
                        flag = false;
                        break 'solve
                    }
                }
            }
        }
        if flag {
            println!("-1 -1 -1");
        }
    }
}

TLE に注意。最高額紙幣（一万円札、または一万円札の枚数を固定した状態での五千円札）をフルに使っても金額 Y に達しないなら、その時点で不可能。一万円札と五千円札の枚数が決まれば、自動的に千円札の枚数が決まるので、千円札に関しては全探索する必要がない。

ABC049C - 白昼夢 / Daydream

その１

fn main() {
    let s = read1::<String>();
    let length = s.len();
    let mut pos = 0;
    let mut flag = 0;

    while pos < length {
        if pos+7 <= length && s[pos..pos+7] == "dreamer".to_string() {
            pos += 7;
            flag = 2;
        } else if pos+6 <= length && s[pos..pos+6] == "eraser".to_string() {
            pos += 6;
            flag = 1;
        } else if pos+5 <= length && s[pos..pos+5] == "dream".to_string() {
            pos += 5;
            flag = 0;
        } else if pos+5 <= length && s[pos..pos+5] == "erase".to_string() {
            pos += 5;
            flag = 0;
        } else if flag > 0 {
            pos -= flag;
            flag = 0;
        } else {
            break;
        }
    }
    if pos == length {
        println!("YES");
    } else {
        println!("NO");
    }
}

文字列の前から、取れる限り長い文字列を取る。取りすぎたせいで後の文字列が構成不能になっているなら、取りすぎた分を戻す。
（dreamerase → "dreamer" ase → "dream" erase → "dream" "erase" のように、取りすぎた "er" を戻す）
戻してもどうしようもない場合は不可能。

その２

fn main() {
    let s = read1::<String>();
    let length = s.len();
    let mut pos = length;

    while pos > 0 {
        if pos >= 7 && s[pos-7..pos] == "dreamer".to_string() {
            pos -= 7;
        } else if pos >= 6 && s[pos-6..pos] == "eraser".to_string() {
            pos -= 6;
        } else if pos >= 5 && s[pos-5..pos] == "dream".to_string() {
            pos -= 5;
        } else if pos >= 5 && s[pos-5..pos] == "erase".to_string() {
            pos -= 5;
        } else {
            break;
        }
    }
    if pos == 0 {
        println!("YES");
    } else {
        println!("NO");
    }
}

単語のお尻に付いている "er" だけが問題なので、お尻から調べていけば戻す必要がない。

ABC086C - Traveling

fn main() {
    let mut v: Vec<Vec<i32>> = vec!(vec!(0, 0, 0));
    let n = read1::<u32>();
    for _ in 0..n {
        v.push(readn::<i32>(" "));
    }

    let mut flag = true;
    for i in 0..n {
        let dt = (v[i as usize][0] - v[(i+1) as usize][0]).abs();
        let dx = (v[i as usize][1] - v[(i+1) as usize][1]).abs();
        let dy = (v[i as usize][2] - v[(i+1) as usize][2]).abs();
        if dx + dy > dt || (dt - (dx + dy)) % 2 != 0 {
            flag = false;
            break;
        }
    }
    if flag {
        println!("Yes");
    } else {
        println!("No");
    }
}

同じところを行ったり来たりすれば、２手分の時間をつぶせる。すなわち、旅行計画が破綻するのは、移動時間が足りない or 移動時間の余りが奇数のとき。

まとめ

Rust はいいぞ。