ABC265 を Rust で解く (C問題まで)

# はじめに

[AtCoder Beginner Contest 265](https://atcoder.jp/contests/abc265) の C問題までを Rust で解きました！
詳しめに解説をしていこうと思います。
役にたちましたらいいねいただけると嬉しいです。
AC 確認はしてますが、もっとスマートな書き方がありましたら教えてください。


# なぜやるのか

プログラミングは知っているけれどアルゴリズムは知らない、という方に向けて書いています。半分は社内向けです。
また、私は Rust に慣れておらず、その練習のためにやっています。
(コンテスト本番には C++ を使って参加している水色コーダーです。)


# 問題

[A - Apple](https://atcoder.jp/contests/abc265/tasks/abc265_a) (<font color="#808080">Difficulty 18</font>)
[B - Explore](https://atcoder.jp/contests/abc265/tasks/abc265_b) (<font color="#808080">Difficulty 152</font>)
[C - Belt Conveyor](https://atcoder.jp/contests/abc265/tasks/abc265_c) (<font color="#808080">Difficulty 212</font>)
[D - Iroha and Haiku (New ABC Edition)](https://atcoder.jp/contests/abc265/tasks/abc265_d) (<font color="#804000">Difficulty 727</font>)
[E - Warp](https://atcoder.jp/contests/abc265/tasks/abc265_e) (<font color="#00C0C0">Difficulty 1531</font>)
[F - Manhattan Cafe](https://atcoder.jp/contests/abc265/tasks/abc265_f) (<font color="#C0C000">Difficulty 2290</font>)
[G - 012 Inversion](https://atcoder.jp/contests/abc265/tasks/abc265_g) (<font color="#FF8000">Difficulty 2436</font>)
[Ex -  No-capture Lance Game](https://atcoder.jp/contests/abc265/tasks/abc265_h) (<font color="#FF0000">Difficulty 3319</font>)


# 前提

この記事にあるコードはこちらを import しています。

```rust
#[allow(unused_imports)]
use proconio::{input, fastout, marker::Chars, marker::Usize1};
#[allow(unused_imports)]
use std::collections::{HashSet, HashMap, BTreeSet, VecDeque};
#[allow(unused_imports)]
use std::cmp::{max, min};
#[allow(unused_imports)]
use itertools::Itertools;
```


# A - Apple

りんごが

- 1個で $X$ 円
- 3個で $Y$ 円

のときに、ちょうど $N$ 個手に入れるときの最低金額を求める問題です。
ちょうど $N$ 個手に入れるには2通りあって、

- $X$ 円で $N$ 個買う
- $Y$ 円でかって、あまりを $X$ 円で買う

の2通りです。

たとえばりんごが 10個のときは

- $X$ 円で 10個 → ($10X$円)
- $Y$ 円で 3セットと、$X$円で 1個 → ($3Y + X$円)

の 2通りになります。

このふたつの金額を比べれば答えがわかります。
コードはこのようになりました。

```rust
  input! {
    x: usize,
    y: usize,
    n: usize,
  }
  let x_only = x * n;
  let mixed = n / 3 * y + x * (n % 3);
  println!("{}", min(x_only, mixed));
```

# B - Explore 

洞窟を探索する問題です。
問題設定が少し複雑ですね。

## 考察

問題文を言い換えてみます。

> 部屋が $N$ 個ならんでいて、部屋を進むと $A$ の時間を使います。
> また、ボーナス部屋に着くと時間が増えます。
> はじめの持ち時間が $T$ のときに、最後の部屋に着くことはできますか？

と言い換えてみました。
問題設定が複雑ですが、理解すれば実装できそうですね。素直に実装すると計算量は $O(N)$ となります。制約より $2 \le N \le 10^5$ なので、実行時間制限も大丈夫そうです。

## 実装

ボーナス部屋について、サイズ $M$ の `vec` で受け取ることになりますが、このままだと少し扱いにくいです。
そのため、`bonus[i] = 部屋 i についた時にもらえるボーナス` として、サイズ $N$ の `vec` としています。

残り時間を計算するときに `usize` 同士の引き算がでてくるのですが、計算結果が負になるとエラーになるので注意してください。
コードはこのようになりました。

```rust
  input! {
    n: usize,
    m: usize,
    mut t: usize,
	a: [usize; n - 1],
    xy: [(Usize1, usize); m],
  }
  // bonus[i] = 部屋 i についた時にもらえるボーナス
  let mut bonus = vec![0; n + 1];
  for (x, y) in xy {
    bonus[x] = y;
  }
  
  for i in 0..n-1 {
    if t <= a[i] { // 先に t - a[i] をすると、型が usize なのに負になって実行時エラーになるので注意
      println!("No");
      return;
    }
    t -= a[i]; // i から i+1 に移動する
    t += bonus[i + 1]; // 部屋　i+1　のボーナスをもらう
  }

  println!("Yes");
```

# C - Belt Conveyor 

グリッド上を移動する問題ですね。はじめは (0, 0) にいて、マスの文字によって移動先が変わります。
移動し続けて、どこかのマスにとまればその位置を出力します。
永遠に移動し続けるときは `-1` を出力します。

## 考察

2パターンあるので、分けて考えましょう。

### どこかのマスに止まるパターン

以下のような場合ですね。
左側に今回の問題の形式、右側に矢印に直したものを書いてみます。

```
RD  | →↓
RD  | →↓
```

この場合は右下のマスに止まるので、(1, 1) と出力します。移動できなくなったら終了なので、なんとなく実装できそうです。

### 永遠に移動し続けるパターン

以下のようなパターンですね。

```
RD | →↓
UL | ↑←
```

これは動き続けるので、さきほどのような、明確な終了条件がありません。考察が必要です。
ここでキーになるのは、どのルートを動くかです。試してみるとわかりますが、同じところを動き続けますね。これを言い換えると、同じマスに2回以上きたときはループすると言えます。マスA からマスB へ向かうルートがあって、マスB からマスA へ向かうルートがあれば、それはループしますね。
なので、「同じマスに2回以上きたかどうか」を判定します。

> これが難しいというときは、「マスは最大でも 250000 なので、300000回くらい移動してみて、まだ移動していたら `-1` を出力し、止まっていたらいまの座標を出力する」という解き方もあります。

気になるのは計算量ですが、すべてのマスを動いたときは $H * W$ マス移動することになるので $O(H*W)$ です。
制約より $1 \le H, W \le 500$ なので、実行制限時間内に間に合いそうなことがわかります。

## 実装

移動してみて、同じマスに来たら `-1` を出力し、移動できなかったら今いるマスを出力します。なので、「いまどこにいるか」と「来たことのあるマスか」の情報が必要ですね。
「いまどこにいるか」は整数、「来たことのあるマスか」は2次元`vec` でもってみました。

移動する部分はいろいろ書き方がありますが `match` で書いてみました。

コードはこのようになります。

```rust
  input! {
	h: usize,
    w: usize,
    mp: [Chars; h],
  }
  let mut come = vec![vec![false; w]; h];
  let mut y = 0;
  let mut x = 0;
  loop {
    match mp[y][x] { // マスの文字を見て移動する
      'U' if y > 0 => { y -= 1 },
      'D' if y < h - 1 => { y += 1 },
      'L' if x > 0 => { x -= 1 },
      'R' if x < w - 1 => { x += 1 },
      _ => break, // 移動先がなかった
    }
    if come[y][x] { // 同じマスに 2回来た
      println!("-1");
      return;
    }
    come[y][x] = true; // (y, x) のマスに来た
  }
  println!("{} {}", y + 1, x + 1);
```

----

最後まで読んでいただきありがとうございます！