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

# はじめに

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


# なぜやるのか

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

# 実は

ABC268 は企業コンで、主催は「ユニークビジョン株式会社」だったのですが、何を隠そうこれは弊社のことです！
よろしければ覗いてみてください -> https://qiita.com/organizations/uniquevision

# 問題

[A - Five Integers](https://atcoder.jp/contests/abc268/tasks/abc268_a) (<font color="#808080">Difficulty 16</font>)
[B - Prefix?](https://atcoder.jp/contests/abc268/tasks/abc268_b) (<font color="#808080">Difficulty 26</font>)
[C - Chinese Restaurant](https://atcoder.jp/contests/abc268/tasks/abc268_c) (<font color="#804000">Difficulty 676</font>)
[D - Unique Username](https://atcoder.jp/contests/abc268/tasks/abc268_d) (<font color="#00C0C0">Difficulty 1309</font>)
[E - Chinese Restaurant (Three-Star Version)](https://atcoder.jp/contests/abc268/tasks/abc268_e) (<font color="#0000FF">Difficulty 1927</font>)
[F - Best Concatenation](https://atcoder.jp/contests/abc268/tasks/abc268_f) (<font color="#0000FF">Difficulty 1807</font>)
[G - Random Student ID](https://atcoder.jp/contests/abc268/tasks/abc268_g) (<font color="#C0C000">Difficulty 2311</font>)
[Ex -  Taboo](https://atcoder.jp/contests/abc268/tasks/abc268_h) (<font color="#FF8000">Difficulty 2560</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 - Five Integers

5個の数字の中に何種類の数字があるかを調べる問題ですね。
いわゆる重複除去というテクニックを使うと楽に解けます。

重複除去には以下のやり方があります。

- ソートしてから重複を取り除く
- `HashSet` を使う
- itertools.unique を使う

というものになります。それぞれ実装を紹介します。


```rust:ソートしてから重複を取り除く
  input! {
    mut abcde: [usize; 5]
  }
  abcde.sort();
  abcde.dedup();
  println!("{}", abcde.len());
```

```rust:HashSet を使う
  input! {
    abcde: [usize; 5]
  }
  let set:HashSet::<usize> = abcde.into_iter().collect();
  println!("{}", set.len());
```

```rust:itertools.unique を使う
  input! {
    abcde: [usize; 5]
  }
  let ans = abcde.into_iter().unique().count();
  println!("{}", ans);
```

itertools.unique はこちら

https://docs.rs/itertools/0.9.0/itertools/trait.Itertools.html#method.unique


# B - Prefix? 

2つの文字列 $S$ と $T$ をもらって、 $S$ が $T$ の先頭にあるかどうかを判定する問題ですね。

## 考察

問題自体は単純に見えます。$S$ と $T$ を同時にひとつづつ見ていって、等しければ OK です。
計算量を考えてみます。$T$ の長さにかかわらず $S$ を1文字ずつ確認することになりますね。そのため、計算量は $O(|S|)$ です。制約より $1 \le |S| \le 100$ なので問題ないですね。

ただ、注意する点がひとつあって、入力例3 のような場合です。$S$ よりも $T$ のほうが文字数が少ないときは $T$ の範囲外参照をしてしまうので注意です。

## 実装

まず、$S$ よりも $T$ のほうが文字数が少ないときは先に弾きます。ガード節とか早期return とか呼ばれるテクニックです。
弾いた後は $S$ よりも $T$ のほうが文字数が多い(か等しい)と言えますね。ここまでくれば、 `enumerate()` などを使って $S$ と $T$ を先頭から 1文字ずつ比較することで答えがわかります。

```rust
  input! {
    s: Chars,
    t: Chars
  }
  if s.len() > t.len() {
    println!("No");
    return;
  }
  for (idx, c) in s.into_iter().enumerate() {
    if c != t[idx] {
      println!("No");
      return;
    }
  }
  println!("Yes");
```


# C - Chinese Restaurant 

中華料理店にあるような回転テーブルをイメージした問題ですね。
((あまり見たことないんですよね...))

## 考察

問題にある操作をすることで、テーブルは $1/N$ ずつまわります。
問題には $0$ 回以上何度でもとありますが、テーブルは $N$回まわせば元の位置に戻ってきます。つまり、 $0$回まわした状態と $N$回まわした状態は同じですね。同様に、例えば $3$回まわした状態と $2N + 3$回まわした状態は同じです。これより、テーブルの状態は全部で $N$通りだと言えます。

> 問題文では mod で書かれているところがあって難しく感じるかもしれません。 mod の部分は 人$0$ と人$N-1$ が隣り合っていることを示しています。例えば $N = 4$ のとき、4人で回転テーブルに座れば、人$0$ と人$3$ が隣り合いますね。 こういうのときは mod を使うと便利で、 $-1 = 3$ と $0 = 4$ だということを表せられます。
> ※ 正確には 「$-1 = 3$」 と 「$0 = 4$」という表現は違っていて、「$-1 \equiv 3 \mod N$」 と 「$0 \equiv 4 \mod N$」 のように書きます

さて、スコアを計算します。操作を $0$回 ($N$ 回、 $2N$ 回、 $3N$ 回... も同じ) したときのスコアを考えてみましょう。たとえば人$1$ は料理$1$ が 人$0$、 人$1$、 人$2$ の前にあるときに喜びます。
人 $i$ が喜ぶ条件は、料理 $i$ が自分の前、両隣にあることですね。つまり、ひとりあたり 3回しらべればスコアがわかります。人は $N$ 人いるので、全体で $3N$ 回の判定をします。

ここまでやったので計算量を考えます。テーブルの状態が $N$ 通りで、状態ひとつにつき $3N$ 回しらべます。なので、全体では $N * 3N$ の計算が必要となり、 $O(N^2)$ ですね。制約より $3 \le N \le 2×10^5$ なので、実行時間内には間に合いそうにないことがわかります。

...間に合わないので高速化を考えましょう。

人 $i$ と料理 $i$ の距離を考えてみます。すると、距離が 1 以下のときにスコアが増えますね。この方針で考えると、人ひとりあたり 3回 (自分の前と両隣) の判定をすれば良さそうです。
※先ほどの方針とは注目している点が違うことに注意です(さきほどは「操作回数」で、こんかいは「人」に注目しています)。
計算量を考えます。人ひとりあたり 3回の判定なので、全体では $3N$ 回になります。つまり、$O(N)$ です。制約より $3 \le N \le 2×10^5$ なので、実行時間に間に合いそうです。

## 実装

実装です。

人をひとりずつ `for` でまわしながらスコアを計算します。

スコアの計算には人 $i$ と料理 $i$ の距離が必要ですね。これは `i - p[i]` で計算できます。通常、距離の計算には絶対値を使いますが、今回は mod をとっているので `i - p[i]` のままで大丈夫です。mod の計算は `%` を使いますが、負の値に対して `%` をとると意図しない挙動になります。なので、 `n` を足して負にならないようにします。

`usize` 同士の引き算があるので、負の値にならないようにしましょう。負になると panic するので注意です。
そういうのを考えたくないときは すべて `isize` でやってもいいです。(そうすると `vec` のインデックスに入れるときに `as usize` が必要になります)

```rust
  input! {
    n: usize,
    p: [usize; n]
  }
  // score[i] = 操作を i 回したときのスコア
  let mut score = vec![0; n];
  for i in 0..n {
    // 人i が喜ぶのは
    // 操作を i - p[i] - 1 回したとき
    score[(n + i - p[i] - 1) % n] += 1;
    // 操作を i - p[i] + 0 回したとき
    score[(n + i - p[i] + 0) % n] += 1;
    // 操作を i - p[i] + 1 回したとき
    score[(n + i - p[i] + 1) % n] += 1;
  }
  println!("{}", score.iter().max().unwrap());
```

# D - Unique Username

弊社の @katsumata_yusuke が解いていますので、見てください！

https://qiita.com/katsumata_yusuke/items/bb67cfa351e1d3a4baee

----

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