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

# はじめに

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


# なぜやるのか

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


# 問題

[A - World Cup](https://atcoder.jp/contests/abc262/tasks/abc262_a) (<font color="#808080">Difficulty 8</font>)
[B - Triangle (Easier)](https://atcoder.jp/contests/abc262/tasks/abc262_b) (<font color="#808080">Difficulty 220</font>)
[C - Min Max Pair](https://atcoder.jp/contests/abc262/tasks/abc262_c) (<font color="#808080">Difficulty 362</font>)
[D - I Hate Non-integer Number](https://atcoder.jp/contests/abc262/tasks/abc262_d) (<font color="#00C0C0">Difficulty 1213</font>)
[E - Red and Blue Graph](https://atcoder.jp/contests/abc262/tasks/abc262_e) (<font color="#0000FF">Difficulty 1719</font>)
[F - Erase and Rotate](https://atcoder.jp/contests/abc262/tasks/abc262_f) (<font color="#C0C000">Difficulty 2334</font>)
[G - LIS with Stack](https://atcoder.jp/contests/abc262/tasks/abc262_g) (<font color="#FF0000">Difficulty 3114</font>)
[Ex -  Max Limited Sequence](https://atcoder.jp/contests/abc262/tasks/abc262_h) (<font color="#FF0000">Difficulty 2957</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 - World Cup

`y` を 4 で割ったあまりで答えが変わる問題ですね。
整数を 4 で割ったあまりは 0,1,2,3 の 4 通りあって、その時の答えは以下のようになります。
あまりが `0` のときは `y + 2`
あまりが `1` のときは `y + 1`
あまりが `2` のときは `y + 0`
あまりが `3` のときは `y + 3`

これを素直に全通り書くと答えになります。

```rust
  input! {
    y: usize
  }
  match y % 4 {
    0 => println!("{}", y + 2),
    1 => println!("{}", y + 1),
    2 => println!("{}", y),
    3 => println!("{}", y + 3),
    _ => {}
  }
```

もしくは、1行にまとめてこのように書くこともできます。

```rust
  input! {
    y: usize
  }
  println!("{}", (y + 1) / 4 * 4 + 2);
```


# B - Triangle (Easier) 

グラフの問題ですね。問題には $N$ 頂点 $M$ 辺の単純無向グラフ とあります。

## グラフについて

ここでいうグラフとは、離散数学の[グラフ理論](https://www.google.com/search?q=%E3%82%B0%E3%83%A9%E3%83%95%E7%90%86%E8%AB%96)のことです。
プログラム上でグラフを表現する方法はいくつかありますが、競技プログラミングでは「隣接行列」と「隣接リスト」をよく使います。今回は隣接行列を使います。

隣接行列は、$N$ × $N$ の二次元配列を使った表現方法です。値を `0` で初期化して、たとえば頂点 $1$ と頂点 $2$ の間に辺があるときは値を `1` にします。プログラム上では `graph[1][2] = 1; graph[2][1] = 1;` のように書きます。
※辺に向きがあるグラフ (有向グラフ) の場合は違う更新をします。

隣接行列の利点は、頂点間に辺があるかどうかが高速に分かるところです。
欠点は、$N$ × $N$ のサイズだけメモリを使うところです。

それに対して、隣接リストにはメモリ使用量が少ない代わりに、辺の探索に時間がかかるという特徴があります。詳細は書きませんが場合によって使い分けます。

## 考察です

この問題は、3つの頂点 a,b,c を選んだ時にその3頂点間に辺があるかを調べる問題ですね。
これは `graph[a][b] == 1` かつ `graph[a][c] == 1` かつ `graph[b][c] == 1` であれば条件を満たしています。
これは全探索になるのですが、そうすると計算量が気になるところです。a,b,c を全通り試すと $O(N^3)$ となるのですが、制約より $3≤N≤100$ なので問題ありません。なので、3つの頂点を全探索すれば時間内に答えを出せそうです。

ですがひとつ問題があって、素直に全探索すると重複が出てしまいます。たとえば `(a,b,c)=(1,2,3)` と `(a,b,c)=(3,2,1)` は同じことを意味しているのですが、 a,b,c の値がちがうので重複してしまいます。この重複を除く方法は２つあります。

### 重複を除く方法 1

a,b,c の間に制限を与えます。 $a \lt b < c$ または $a \gt b \gt c$ ということにすると、重複はなくなります。

### 重複を除く方法 2

重複を許してカウントして、最後に重複分を取り除きます。
今回は 3頂点なので、 $3! = 6$ で割ることで重複がないときの個数がわかります。

## 実装です
入力は 1-index でもらいますが、プログラムでは 0-index のほうが扱いやすいです。これは `marker::Usize1` で受け取ることで実現します。

また、上でも書きましたが、グラフの表現に隣接行列を使います。つまり $N$ × $N$ の二次元 vector を使います。
メモリ使用量が $O(N^2)$ となり気になるところですが、制約に $3≤N≤100$ とあるので問題ないです。$N$ が $5000$ くらいまでは隣接行列が使えます。

あとは全探索をします。考察したように重複を必要があって、今回は「重複を除く方法 1」を使います。コードでは `for` をするときの範囲を調整して、$a \gt b \gt c$ を表現しました。
また、(`graph[a][b] == 1` かつ `graph[a][c] == 1` かつ `graph[b][c] == 1`) の判定ですが、記述量を減らすために掛け算をつかっています。`graph[a][b]` が $0$ か $1$ の値をとるため、 (`graph[a][b] == 1` かつ `graph[a][c] == 1` かつ `graph[b][c] == 1`) のときだけ計算結果が 1 になり、それ以外では 0 になります。

コードは以下のようになりました。

```rust
  input! {
    n: usize,
    m: usize,
    uv: [(Usize1, Usize1); m]
  }
 
  let mut graph = vec![vec![0; n]; n];
  for (u, v) in uv {
    graph[u][v] = 1;
    graph[v][u] = 1;
  }
  let mut ans = 0;
  for a in 0..n {
    for b in 0..a {   // b < a となる
      for c in 0..b { // c < b となる
        // c < b < a となる
        ans += graph[a][b] * graph[a][c] * graph[b][c];
      }
    }
  }
  println!("{}", ans);
```


# C - Min Max Pair 

数列 $a$ から2つのペアを選んだ時に、その「数値」と「何番目にあるか」の関係をみる問題ですね。

すこし複雑です。

## 考察です

複雑な問題は実際にやってみるのが重要です。
1. `1,2,3` という数列で考えてみましょう。答えは `1,2` `1,3` `2,3` の3通りですね、
2. `3,2,1` という数列で考えてみましょう。答えは `1,3` の1通りですね。

1 と 2 は意図的に出したのですが、違いがわかりますでしょうか。1 の答えに選ばれるペアは、数値と位置が一致しています。2 の答えに選ばれるペアは、位置を入れ替えると数値と位置が一致します。他に答えになるペアはないので、この2通りについて考えれば良さそうです。

### 1 について

「数値と位置が一致しているもの」同士の組み合わせが答えになります。「数値と位置が一致しているもの」の個数を $N$ として、 $_N C_2 = N * (N - 1) / 2$ で計算できます。

### 2 について

交換先の値が $i$ と等しければ、答えにカウントします。ただ、ひとつ注意点があって、数列を前から順にみていくと、同じペアが2回カウントされてしまいます。これだと答えがずれるので、なにか制限をしましょう。
B問題でも似たような重複除去をしましたが、$a_i \lt i$ という制限をつけます。 $a_i \le i$ とすると、「数値と位置が一致しているもの」も計算してしまうので注意です。
もしくは、計算後に $2! = 2$ で割るといいです。割るときは、1 で計算した値がはいらないように注意します。すこし大変です。

## 実装です

以下のようなコードになりました。

配列は 0-index なので、それに合わせるために `Usize1` を使って入力をもらっています。

1 について、値と位置が同じものの個数を調べます。`enumerate()` と `filter()` のメソッドチェーンで求めてみました。
`enumerate()` は配列を `(index, value)` のタプル配列に変換します。`filter()` は条件に合う要素だけを抽出します。

2 についても `enumerate()` と `filter()` のメソッドチェーンを使って求めました。`a[v]` が交換先の値になります。また、`v < *i` で制限しています。

```rust
  input! {
    n: usize,
    a: [Usize1; n]
  }

  let same_count = a
    .iter()
    .enumerate()
    .filter(|(index, &value)| *index == value)
    .count()
  ;

  let ans = same_count * (same_count - 1) / 2 +
    a.iter()
    .enumerate()
    .filter(|(i, &v)| a[v] == *i && v < *i)
    .count()
  ;
  
  println!("{}", ans);
```



----

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