RustでAtCoder Beginners Selectionを解いてみた

Rustの勉強を進めており、理解を深めるためにAtCoder Beginners Selectionを解いてみました。

標準入力の扱い

Rustだと標準入力の扱いが厄介であり、Pythonなどに比べると記載が冗長になりがちです。その問題を解決するために、proconioというクレートを導入します。

proconioとは

proconioとは「AtCoderと一緒に使うことを目的とした、競技プログラミングのための簡単なIOライブラリ」です。statiolakeさんが開発されました。（大変助かっています！ありがとうございます）

サンプル

cargo.tomlのdependenciesに追記します。

Cargo.toml

[dependencies]
proconio = 0.4.3

input!マクロを使用することで各変数に標準入力の値を容易に格納することができます。

main.rs

use proconio::input;

pub fn main() {
    input! {
        s: String,
        a: i32,
        b: i32,
    }

    println!("{} {} {}", s, a, b);
}

入力

sample
21
23

出力

sample 21 23

AtCoder Beginners Selection

では、さっそく問題を見ていきましょう。

PracticeA: Welcome to AtCoder

問題文
高橋君はデータの加工が行いたいです。
整数a,b,cと、文字列 s が与えられます。a+b+c の計算結果と、文字列sを並べて表示しなさい。

制約
1≤a,b,c≤1,000
1≤∣s∣≤100

input!マクロのおかげでかなりスッキリ記述できます。

practicea.rs

use proconio::input;

pub fn main() {
    input! {
        a: i32,
        bc: [i32; 2],
        s: String
    }

    println!("{} {}", a + bc[0] + bc[1], s);
}

ABC086A: Product

問題文
シカのAtCoDeerくんは二つの正整数a,b を見つけました。aとbの積が偶数か奇数か判定してください。

制約
1≤a,b≤10000
a,b は整数

2で割り切れるかどうかで偶数か奇数かを判定するオーソドックスな問題です。

abc086a.rs

use proconio::input;

pub fn main() {
    input! {
        ab: [i32; 2],
    }

    if ab[0] * ab[1] % 2 == 0 {
        println!("Even");
    } else {
        println!("Odd");
    }
}

ABC081A: Placing Marbles

問題文
すぬけ君は1,2,3 の番号がついた3 つのマスからなるマス目を持っています。各マスには0か1が書かれており、マスiにはs_iが書かれています。
すぬけ君は 1 が書かれたマスにビー玉を置きます。ビー玉が置かれるマスがいくつあるか求めてください。

制約

• s₁ ,s₂ ,s₃は1あるいは0

proconioのCharsを利用することで読み取った文字列をCharの配列として保持しています。そのため、各文字に対する処理が容易に記述できています。

abc081a.rs

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

pub fn main() {
    input! {
        ss: Chars,
    }

    let mut cnt = 0;
    for s in ss {
        if s == '1' {
            cnt = cnt + 1
        }
    }
    println!("{}", cnt);
}

ABC081B: Shift only

問題文
黒板にN個の正の整数A₁,...,A_N​が書かれています．
すぬけ君は，黒板に書かれている整数がすべて偶数であるとき，次の操作を行うことができます．

• 黒板に書かれている整数すべてを，2で割ったものに置き換える．

すぬけ君は最大で何回操作を行うことができるかを求めてください．

制約

• 1≤N≤200
• 1≤A_i≤10⁹

全ての要素が2ⁱで割り切れるどうかをチェックし、割り切れなければ処理を打ち切っています。2の階乗は2_i32.pow(i)で表します。

abc081b.rs

use proconio::input;

pub fn main() {
    input! {
        n: i32,
        aa: [i32;n],
    }

    let mut cnt = 1;

    loop {
        let mut break_flag = false;
        for a in &aa {
            if a % (2_i32.pow(cnt)) != 0 {
                break_flag = true;
            }
        }
        if break_flag {
            break;
        };

        cnt = cnt + 1;
    }

    println!("{}", cnt - 1);
}

ABC087B: Coins

問題文
あなたは、500円玉をA枚、100円玉をB枚、50円玉をC枚持っています。これらの硬貨の中から何枚かを選び、合計金額をちょうどX円にする方法は何通りありますか。
同じ種類の硬貨どうしは区別できません。2 通りの硬貨の選び方は、ある種類の硬貨についてその硬貨を選ぶ枚数が異なるとき区別されます。

制約

• 0≤A,B,C≤50
• A+B+C≥1
• 50≤X≤20,000
• A,B,Cは整数である
• Xは50の倍数である

全探索したとしても計算量は高々O(10⁵)程度なので全探索してちょうどX円になる組み合わせを探しています。

abc087b.rs

use proconio::input;

pub fn main() {
    input! {
        a: i32,
        b: i32,
        c: i32,
        x: i32,
    }

    let mut cnt = 0;
    for i in 0..a + 1 {
        for j in 0..b + 1 {
            for k in 0..c + 1 {
                if 500 * i + 100 * j + 50 * k == x {
                    cnt = cnt + 1;
                }
            }
        }
    }

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

ABC083B: Some Sums

問題文
1以上N以下の整数のうち、10進法での各桁の和がA以上B以下であるものの総和を求めてください。

制約

• 1≤N≤10⁴
• 1≤A≤B≤36
• 入力はすべて整数である

nをcharの配列に変換して更に数値に変換する記載が分かりづらいですが、n_string.chars()により各文字のイテレータが取得できるのでmapを用いて各要素を数値に変換しています。また、イテレータに対してfoldを使用することで畳み込みで合計を計算しています。

abc083b.rs

use proconio::input;

pub fn main() {
    input! {
        input: [i32; 3],
    }

    let n = input[0];
    let a = input[1];
    let b = input[2];

    let mut res = 0;

    for n in 0..n + 1 {
        let n_string = n.to_string();
        let n_iter = n_string.chars().map(|n| n.to_digit(10).unwrap());
        let n_sum: i32 = n_iter.fold(0, |sum, n| sum + n as i32);

        if n_sum >= a && n_sum <= b {
            res = res + n;
        }
    }

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

ABC088B: Card Game for Two

問題文
N枚のカードがあります.i 枚目のカードには, a_iという数が書かれています.
AliceとBobは, これらのカードを使ってゲームを行います. ゲームでは, AliceとBobが交互に1枚ずつカードを取っていきます.Aliceが先にカードを取ります.
2人がすべてのカードを取ったときゲームは終了し, 取ったカードの数の合計がその人の得点になります.2人とも自分の得点を最大化するように最適な戦略を取った時, AliceはBobより何点多く取るか求めてください.

制約
Nは1以上100以下の整数
a_i(1≤i≤N) は1以上100以下の整数

aaを昇順に並べた後に末尾から取り出して（popして）、AliceとBobの持ち点に加算して、最後にその差を計算しています。popはOption型を返すので、unwrap()してSome()を取り出しています。

abc088b.rs

use proconio::input;

pub fn main() {
    input! {
        n: i32,
        mut aa: [i32;n],
    }

    aa.sort();
    let mut sum_a = 0;
    let mut sum_b = 0;

    loop {
        if aa.is_empty() {
            break;
        }
        sum_a = sum_a + aa.pop().unwrap();

        if aa.is_empty() {
            break;
        }
        sum_b = sum_b + aa.pop().unwrap();
    }

    println!("{}", sum_a - sum_b);
}

ABC085B: Kagami Mochi

問題文
X 段重ねの鏡餅(X≥1) とは、X枚の円形の餅を縦に積み重ねたものであって、どの餅もその真下の餅より直径が小さい（一番下の餅を除く）もののことです。例えば、直径10、8、6センチメートルの餅をこの順に下から積み重ねると3段重ねの鏡餅になり、餅を一枚だけ置くと1段重ねの鏡餅になります。

ダックスフンドのルンルンはN枚の円形の餅を持っていて、そのうちi枚目の餅の直径は
d_iセンチメートルです。これらの餅のうち一部または全部を使って鏡餅を作るとき、最大で何段重ねの鏡餅を作ることができるでしょうか。

制約

• 1≤N≤100
• 1≤d_i≤100
• 入力値はすべて整数である。

餅の配列であるddを昇順に並べた後に後ろから要素をpopします。取り出した餅の直径が直前に取り出したものと一致していると餅を重ねることができないため、不一致の場合のみcntをインクリメントしています。

abc085b.rs

use proconio::input;

pub fn main() {
    input! {
        n: i32,
        mut dd: [[i32;1]; n],
    }

    let mut dd = dd.concat();
    dd.sort();
    dd.reverse();

    let mut x = 0;
    let mut cnt = 0;

    loop {
        if dd.is_empty() {
            break;
        }
        let y = dd.pop().unwrap();

        if x != y {
            cnt = cnt + 1;
        }

        x = y;
    }

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

ABC085C: Otoshidama

問題文
日本でよく使われる紙幣は、10000円札、5000円札、1000円札です。以下、「お札」とはこれらのみを指します。
青橋くんが言うには、彼が祖父から受け取ったお年玉袋にはお札がN枚入っていて、合計でY円だったそうですが、嘘かもしれません。このような状況がありうるか判定し、ありうる場合はお年玉袋の中身の候補を一つ見つけてください。なお、彼の祖父は十分裕福であり、お年玉袋は十分大きかったものとします。

制約

• 1≤N≤2000
• 1000≤Y≤2×10⁷
• Nは整数である。
• Yは1000の倍数である。

前述したABC087B:Coinsと似ていますが、a,b,cに対して全探索するとO(N³)となり計算量がO(10⁹)でTLEするためa,bに対して全探索を行います。正確には、cはa,bが定まれば一意に定まるため探索する必要がありません。

abc085c.rs

use proconio::input;

pub fn main() {
    input! {
        ny: [i32;2],
    }

    let n = ny[0];
    let y = ny[1];

    let mut mai_10000 = -1;
    let mut mai_5000 = -1;
    let mut mai_1000 = -1;

    for i in 0..n + 1 {
        for j in 0..n + 1 - i {
            let sum = 10000 * i + 5000 * j + 1000 * (n - i - j);

            if y == sum {
                mai_10000 = i;
                mai_5000 = j;
                mai_1000 = n - i - j;
                break;
            }
        }
    }

    println!("{} {} {}", mai_10000, mai_5000, mai_1000);
}

ABC049C: 白昼夢

問題文
英小文字からなる文字列Sが与えられます。
Tが空文字列である状態から始め、以下の操作を好きな回数繰り返すことで
S=T とすることができるか判定してください。

• T の末尾に dream dreamer erase eraser のいずれかを追加する。

制約

• 1≦∣S∣≦10⁵
• S は英小文字からなる。

先頭から探索してしまうと、例えばdreamまで一致していた場合に追加された文字列がdreamなのかdreamerなのか判定できません。そのため末尾から探索して一致した文字列を取り除くことで重複を防いでいます。

abc049c.rs

use proconio::input;

pub fn main() {
    input! {
        mut s: String,
    }

    let search_strings = ["dream", "dreamer", "erase", "eraser"];
    let mut res = "NO";

    loop {
        if s.is_empty() {
            res = "YES";
            break;
        }

        let mut s_sliced = s.clone();
        for search_str in search_strings.iter() {
            if s.ends_with(search_str) {
                s_sliced = s[..s.len() - search_str.len()].to_string();
            }
        }

        if s_sliced == s {
            break;
        }

        s = String::from(s_sliced);
    }

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

ABC086C: Traveling

問題文
シカのAtCoDeerくんは二次元平面上で旅行をしようとしています。AtCoDeerくんの旅行プランでは、時刻0に点(0,0)を出発し、1以上N以下の各iに対し、時刻t_iに点(x_i ,y_i)を訪れる予定です。

AtCoDeerくんが時刻tに点(x,y)にいる時、時刻t+1には点(x+1,y), (x−1,y), (x,y+1), (x,y−1)のうちいずれかに存在することができます。その場にとどまることは出来ないことに注意してください。AtCoDeerくんの旅行プランが実行可能かどうか判定してください。

制約

• 1≤N≤10⁵
• 0≤x_i≤10⁵
• 0≤y_i≤10⁵
• 1≤t_i≤10⁵
• t_i < t_i+1(1≤i≤N−1)
• 入力は全て整数

時刻1あたり距離1を移動できるため、t_i+1 - t_i = abs(x_i+1 - x_i)+abs(y_i+1 - y_i)であれば時間内に過不足なくぴったり移動できます。
もし時間が余った(t_i+1 - t_i > abs(x_i+1 - x_i)+abs(y_i+1 - y_i))としても、余った時間が2nであれば行って戻ってくることができるため、移動可能になります。

abc086c.rs

use proconio::input;

pub fn main() {
    input! {
        n: i32,
        txy: [[i32;3];n],
    }

    let mut t_0 = 0;
    let mut x_0 = 0;
    let mut y_0 = 0;
    let mut res = "Yes";

    for txy_i in txy {
        let (t_1, x_1, y_1) = (txy_i[0], txy_i[1], txy_i[2]);

        let elapsed_time = t_1 - t_0;
        let distance = (x_1 - x_0).abs() + (y_1 - y_0).abs();

        if (elapsed_time - distance < 0) || ((elapsed_time - distance) % 2 != 0) {
            res = "No";
            break;
        }

        t_0 = t_1;
        x_0 = x_1;
        y_0 = y_1;
    }

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

備考

本記事はこちらのブログにも転載しています。
よかったら覗いてください。

参考文献