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

# はじめに

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


# なぜやるのか

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


# 問題

[A - Anyway Takahashi](https://atcoder.jp/contests/abc269/tasks/abc269_a) (<font color="#808080">Difficulty 8</font>)
[B - Rectangle Detection](https://atcoder.jp/contests/abc269/tasks/abc269_b) (<font color="#808080">Difficulty 68</font>)
[C - Submask](https://atcoder.jp/contests/abc269/tasks/abc269_c) (<font color="#808080">Difficulty 384</font>)
[D - Do use hexagon grid](https://atcoder.jp/contests/abc269/tasks/abc269_d) (<font color="#804000">Difficulty 612</font>)
[E - Last Rook](https://atcoder.jp/contests/abc269/tasks/abc269_e) (<font color="#008000">Difficulty 1030</font>)
[F - Numbered Checker](https://atcoder.jp/contests/abc269/tasks/abc269_f) (<font color="#0000FF">Difficulty 1601</font>)
[G - Reversible Cards 2](https://atcoder.jp/contests/abc269/tasks/abc269_g) (<font color="#FF8000">Difficulty 2440</font>)
[Ex -  Antichain](https://atcoder.jp/contests/abc269/tasks/abc269_h) (<font color="#FF0000">Difficulty 3178</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 - Anyway Takahashi

問題文そのままですね。
引き算があるので `isize` で受け取ることに注意です。
`usize` で受け取ると、 $C-D$ の結果が負になるときに panick します。

```rust
  input! {
	a: isize,
    b: isize,
    c: isize,
    d: isize
  }
  println!("{}", (a + b) * (c - d));
  println!("Takahashi");
```


# B - Rectangle Detection 

入力でもらった文字の中から四角形の領域を切り取る問題ですね。

## 考察

出力する $A,B,C,D$ について考えてみます。

$A$ は四角形の上
$B$ は四角形の下
$C$ は四角形の左
$D$ は四角形の右

になります。
ここで、$A$について言い換えると、「上下方向」の「最小値」と言えますね。
他の要素もいいかえると、

$A$ は「上下方向」の「最小値」
$B$ は「上下方向」の「最大値」
$C$ は「左右方向」の「最小値」
$D$ は「左右方向」の「最大値」

となります。上下方向と左右方向に分解して実装できることがわかりました。

## 実装

$A$ は「上下方向」の「最小値」
について考えます。 `(y, x)` 座標について、「上下方向」は `y` ですね。なので、 $A$ は `y` の最小値を求めます。
ほかの $B,C,D$ についても同様にすると答えがわかります。
`a,b,c,d` は初期値に注意です。`a,c` は最小値を求めるので、マスの最大サイズである 10以上の数にして、`b,d` はマスの最小サイズである 1以下の数にします。

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

```rust
  input! {
	mp: [Chars; 10]
  }
  let mut a = 100;
  let mut b = 0;
  let mut c = 100;
  let mut d = 0;
  
  for y in 0..10 {
    for x in 0..10 {
      if mp[y][x] == '#' {
        a = min(a, y + 1); // a は「上下方向」の「最小値」
        b = max(b, y + 1); // b は「上下方向」の「最大値」
        c = min(c, x + 1); // c は「左右方向」の「最小値」
        d = max(d, x + 1); // d は「左右方向」の「最大値」
      }
    }
  }
  
  println!("{} {}", a, b);
  println!("{} {}", c, d);
```


# C - Submask 

2進数がでてくる問題です。慣れていないとびっくりするかもしれません。

## 考察

問題文は複雑ですが、問題文の出力例1 をみてみると考えやすいです。

$N = 1011_{(2)}$ の時の答えは
$0000_{(2)}$、$0001_{(2)}$、$0010_{(2)}$、$0011_{(2)}$、$1000_{(2)}$、$1001_{(2)}$、$1010_{(2)}$、$1011_{(2)}$ ですね。これらの数値は、$N$ の桁をひとつずつ見て、「0 ならば 0」「1ならば0か1」というものになっています。
これはつまり、整数 `x` について、 `if x | N == N` を満たせば `x` は答えになります。計算量を考えると $O(N)$ なのですが、$0 \le N \lt 2^{60}$ なので、実行時間制限に間に合いません。なにか高速化が必要です。

上に書きましたが「1ならば0か1」なので、$N$の桁で1となる位ひとつにつき2通りの答えができます。これに注目します。問題文より、$N$の桁で 1となる位は15個以下ですね。つまり、答えの数値は最大で $2^{15} = 32768$個です。全探索できそうです。
$N$ の桁で 1となる場所を記憶しておいて、それぞれの場所を使うかどうかを探索します。「使うかどうか」は bit全探索が有効です。

計算量を考えると、$N$ の桁で 1 となっている個数を $n$ とすると、答えの数値をひとつ作るのに $O(n)$ かかります。これが $2^n$ 個あるので、全体では $O(n * 2^n)$ になります。 $1 \le n \le 15$ なので、実行時間制限内に解けそうなことがわかります。


## 実装

実装です。

$N$ の桁で 1 となっている場所を `pos` に保存します。
`mask` の桁を見て、 `i`番目の桁が 1 になっていたら、`pos[i]` を使用します。
( `mask` という名前は [bit mask](https://ja.wikipedia.org/wiki/%E3%83%9E%E3%82%B9%E3%82%AF_(%E6%83%85%E5%A0%B1%E5%B7%A5%E5%AD%A6)) からきています。)

`1<<sz` はシフト演算です。$2^{sz}$ の値が得られます。
`mask >> i` もシフト演算です。$ mask / 2^i$ (切り捨て) の値が得られます。
`if mask >> i & 1 == 1` は、`mask` を2進数で見たときに右から `i` 番目の位が 1 かどうかを判定しています。

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

```rust
  input! {
    n: usize
  }
  
  let mut pos = vec![];
  for i in 0..60 {
    if n >> i & 1 == 1 { // n の右から i 番目の桁が 1 ならば
      pos.push(i);
    }
  }
  
  let sz = pos.len();
  let mut ans = vec![];

  for mask in 0..1<<sz { // 0 から 2 ^ {sz} まで
    let mut score = 0_u64; // usize は 32bit になることがあるので u64 型で
    for i in 0..sz {
      if mask >> i & 1 == 1 { // mask の右から i 番目の桁が 1 ならば
        score += 1 << pos[i]; // 2 ^ {pos[i]} を足す
      }
    }
    ans.push(score);
  }

  ans.sort();
  for v in ans.into_iter() {
    println!("{}", v);
  }
```



----

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