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

# はじめに

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


# なぜやるのか

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


# 問題

[A - "atcoder".substr()](https://atcoder.jp/contests/abc264/tasks/abc264_a) (<font color="#808080">Difficulty 8</font>)
[B - Nice Grid](https://atcoder.jp/contests/abc264/tasks/abc264_b) (<font color="#808080">Difficulty 55</font>)
[C - Matrix Reducing](https://atcoder.jp/contests/abc264/tasks/abc264_c) (<font color="#804000">Difficulty 758</font>)
[D - "redocta".swap(i,i+1)](https://atcoder.jp/contests/abc264/tasks/abc264_d) (<font color="#804000">Difficulty 414</font>)
[E - Blackout 2](https://atcoder.jp/contests/abc264/tasks/abc264_e) (<font color="#00C0C0">Difficulty 1229</font>)
[F - Monochromatic Path](https://atcoder.jp/contests/abc264/tasks/abc264_f) (<font color="#0000FF">Difficulty 1878</font>)
[G - String Fair](https://atcoder.jp/contests/abc264/tasks/abc264_g) (<font color="#C0C000">Difficulty 2348</font>)
[Ex -  Perfect Binary Tree](https://atcoder.jp/contests/abc264/tasks/abc264_h) (<font color="#FF8000">Difficulty 2660</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 - "atcoder".substr()

"atcoder" という文字列の $L$ 番目から $R$ 番目までを出力する問題ですね。
Rust の文字列は slice ができるので、これを使いましょう。

slice とは、文字列の「$L$ 番目から $R$ 番目まで」を取り出すことのできる書き方です。
文字列だけでなく、 `vec` にも使えます。

```rust
  input! {
    l: usize,
    r: usize,
  }
  let atcoder = "atcoder";
  println!("{}", &atcoder[l - 1..r]);
```


# B - Nice Grid 

特定のグリッドが白色か黒色かを判定する問題です。

## 考察

規則性があるのでうまくやればシンプルに解けそうです。
ですが、「考えるのに時間がかかりそう & 愚直にかいても解けそう」 なので愚直に解きます。どういう解き方かというと、問題文にあるグリッドをコードに書いてしまいます。

## 実装

グリッドを書くと言いましたが、ぜんぶ書くのはちょっと大変です。そのため、以下の処理をすることで、点を左上に移動させました。結果として、書くことになるグリッドが左上部分だけになります。
`let r = min(r, 14 - r) as usize;` で下半分にある点を上半分に線対称に移動しています。
`let c = min(c, 14 - c) as usize;` で右半分にある点を左半分に線対称に移動しています。

また、Rust で文字列の `vec` の 1要素を取得するには slice が必要ですが、書くのが少し複雑になってしまいますね。競プロでは実装速度をあげたいので、 binary を使うことでシンプルに書きます。(このテクは弊社の @aobat に教えていただきました)

```rust
  input! {
    r: Usize1,
    c: Usize1,
  }
  let r = min(r, 14 - r) as usize;
  let c = min(c, 14 - c) as usize;

  let map = [
    b"########",
    b"#.......",
    b"#.######",
    b"#.#.....",
    b"#.#.####",
    b"#.#.#...",
    b"#.#.#.##",
    b"#.#.#.#.",
  ];

  // slice を使うとこうなる -> let ans = if &map[r][l..l+1] == "#" {
  let ans = if map[r][c] == b'#' {
    "black"
  } else {
    "white"
  };

  println!("{}", ans);
```

ちなみに、チェビシェフ距離という概念を使ってうまくやると、このように書けます。

```rust
  input! {
    r: Usize1,
    c: Usize1,
  }
  let r = min(r, 14 - r) as usize;
  let c = min(c, 14 - c) as usize;
  let dist = min(r, c);
  let ans = if dist % 2 == 0 {
    "black"
  } else {
    "white"
  };
 
  println!("{}", ans);
```

# C - Matrix Reducing 

めちゃくちゃ難しい！と思いましたが、制約が小さかったです。この程度のサイズなら全探索ができそうです。

## 考察

全探索をします。全探索で気になるのは計算量ですね。各行と各列にたいして「削除する」「削除しない」の 2通りを考えます。このとき、全組み合わせは $N = H_1 + W_1$ として $2^N$ 通りです。
$1 \le H_1 \le 10$ かつ $1 \le W_1 \le 10$ より、$N$ は最大で $20$ ですね。実装時には探索 1回に $O(N^2)$ 程度かかるので、全体の計算量は $O(N^2・ 2^N)$ でしょうか。 $N \le 20$ で、$2^{20} \risingdotseq 10^6$ であることより、全探索が間に合いそうなことがわかります。

さて、今回の全探索は「削除する」「削除しない」の 2通りをすべて探索します。これは bit全探索という手法を使います。簡単に説明すると、整数を2進数で見て、i番目のbitが 0 ならば「削除する」 / 1 ならば「削除しない」として、整数を増やしながら探索をする方法です[^1]。
たとえば整数が 6 のときは $6_{10} = 110_2$ [^2]より、1番目を「削除する」2番目と3番目を「削除しない」とします[^3]。

## 実装

大まかな流れとして、

1. 行を表す整数を用意する
1. 列を表す整数を用意する
1. 行の整数と列の整数をもとに行列を構築する
1. $B$ と等しければ終了
1. $B$ と違っていれば探索を続ける

というものになっています。

そのままやっても時間内に間に合うのですが、せっかくなので高速化したいです。2進数で見たときに、各桁の1になっている個数 (`popcount` や `count_ones` と呼ばれるもの) が$H_2$ または $W_2$ と違う数字のときは、そこから作られる行列は $B$ と一致することはないですね。やっても意味がないので、行列を作る前に `continue;` して高速化をしています。

また、bit の判定について、`row >> y & 1 == 1` としていますが、 `row & (1 << y) > 0` とする宗派もあります。どちらも結果は同じです。前者の利点は `row >> y & 1` が `0` か `1` を返すことで、後者の利点は考えやすいことなので、お好きなほうをお使いください。

実装はこのようになりました。

```rust
fn main() {
  input! {
    h1: usize,
    w1: usize,
    a: [[u64; w1]; h1],
    h2: usize,
    w2: usize,
    b: [[u64; w2]; h2],
  }
  for row in 0_usize..1 << h1 { // 1. 行を表す整数を用意する
    if row.count_ones() as usize != h2 { // 探索する必要のないものを弾くことで高速化をしている
      continue;
    }
    for col in 0_usize..1 << w1 { // 2. 列を表す整数を用意する
      if col.count_ones() as usize != w2 { // 探索する必要のないものを弾くことで高速化をしている
        continue;
      }

      // 3. 行の整数と列の整数をもとに行列を構築する
      let mut b_row = 0; // いま b の何行目をみているか
      for y in 0..h1 {
        if row >> y & 1 == 1 { // row の y 番目の bit が 1 ならば
          let mut tmp = vec![]; // 探索した結果をこれにいれる
          for x in 0..w1 {
            if col >> x & 1 == 1 { // col の x 番目の bit が 1 ならば
              tmp.push(a[y][x]);
            }
          }
          if tmp == b[b_row] { // 探索した結果 b の行と一致していたら
            b_row += 1; // b の次の行にいく

            // 4. B と等しければ終了
            if b_row == h2 {
              println!("Yes");
              return;
            }
          }
        }
      }
    }
  }
  println!("No");
```



----

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

[^1]: i番目のbitが 0 ならば「削除しない」 / 1 ならば「削除する」 としても解けます。ただ、こちらのほうが実装時に考えやすかったのでこうしています。
[^2]: $6_{10}$ は10進数での6、$110_2$ は2進数での110 を表します。
[^3]: 右端から順に1番目、2番目、、、と数えます。