RustでAtCoder Beginners Selectionを解いてみた

Rustの勉強を進めており、理解を深めるために[AtCoder Beginners Selection](https://atcoder.jp/contests/abs)を解いてみました。

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

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

### サンプル
``cargo.toml``の``dependencies``に追記します。

```rust:Cargo.toml
[dependencies]
proconio = 0.4.3
```
``input!``マクロを使用することで各変数に標準入力の値を容易に格納することができます。

```rust: main.rs
use proconio::input;

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

    println!("{} {} {}", s, a, b);
}
```
```bash: 入力
sample
21
23
```

```bash: 出力
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!マクロのおかげでかなりスッキリ記述できます。

```rust: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で割り切れるかどうかで偶数か奇数かを判定するオーソドックスな問題です。

```rust: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<sub>1</sub> ,s<sub>2</sub> ,s<sub>3</sub>は1あるいは0

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

```rust: 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<sub>1</sub>,...,A<sub>N</sub>​が書かれています．
>すぬけ君は，黒板に書かれている整数がすべて偶数であるとき，次の操作を行うことができます．
>
> * 黒板に書かれている整数すべてを，2で割ったものに置き換える．
>
>すぬけ君は最大で何回操作を行うことができるかを求めてください．
> 
>制約
>* 1≤N≤200
>* 1≤A<sub>i</sub>≤10<sup>9</sup>

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

```rust: 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<sup>5</sup>)程度なので全探索してちょうど``X``円になる組み合わせを探しています。

```rust: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<sup>4</sup>
> * 1≤A≤B≤36
> * 入力はすべて整数である

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

```rust: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<sub>i</sub>という数が書かれています.
AliceとBobは, これらのカードを使ってゲームを行います. ゲームでは, AliceとBobが交互に1枚ずつカードを取っていきます.Aliceが先にカードを取ります.
2人がすべてのカードを取ったときゲームは終了し, 取ったカードの数の合計がその人の得点になります.2人とも自分の得点を最大化するように最適な戦略を取った時, AliceはBobより何点多く取るか求めてください.
>
> 制約
Nは1以上100以下の整数
a<sub>i</sub>(1≤i≤N) は1以上100以下の整数

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

```rust: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<sub>i</sub>センチメートルです。これらの餅のうち一部または全部を使って鏡餅を作るとき、最大で何段重ねの鏡餅を作ることができるでしょうか。
>
>制約
>* 1≤N≤100
>* 1≤d<sub>i</sub>≤100
>* 入力値はすべて整数である。

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

```rust: 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<sup>7</sup> 
>* Nは整数である。
>* Yは1000の倍数である。

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

```rust: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<sup>5</sup> 
>* S は英小文字からなる。

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

```rust: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<sub>i</sub>に点(x<sub>i</sub> ,y<sub>i</sub>)を訪れる予定です。
>
>AtCoDeerくんが時刻tに点(x,y)にいる時、時刻t+1には点(x+1,y), (x−1,y), (x,y+1), (x,y−1)のうちいずれかに存在することができます。その場にとどまることは出来ないことに注意してください。AtCoDeerくんの旅行プランが実行可能かどうか判定してください。
>
>制約
>* 1≤N≤10<sup>5</sup> 
>* 0≤x<sub>i</sub>≤10<sup>5</sup> 
>* 0≤y<sub>i</sub>≤10<sup>5</sup> 
>* 1≤t<sub>i</sub>≤10<sup>5</sup>  
>* t<sub>i</sub> < t<sub>i+1</sub>(1≤i≤N−1)
>* 入力は全て整数

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

```rust: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);
}
```
## 備考
本記事はこちらのブログにも転載しています。
よかったら覗いてください。

https://shiganaise.com/rust-abs/

## 参考文献
https://github.com/statiolake/proconio-rs

https://qiita.com/Pikka2048/items/a0247e792aa4f8f6dd92

https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8