ABC215 を Rust で解く (D問題まで)

# はじめに

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


# なぜやるのか

コンテストから時間をあけて解きなおすことで、記憶へ定着すればいいなと思っています。
また、会社で Rust を使うのですが私はまだ慣れておらず、その練習のためにやっています。
(コンテスト本番には C++ を使って参加している水色コーダーです。)



# 目次

[A - Your First Judge](#a---your-first-judge) (<font color="#808080">Difficulty 7</font>)
[B - log2(N)](#b---log2(n)) (<font color="#808080">Difficulty 68</font>)
[C - One More aab aba baa](#c---one-more-aab-aba-baa) (<font color="#808080">Difficulty 178</font>)
[D - Coprime 2](#d---coprime-2) (<font color="#804000">Difficulty 736</font>)

今回は E問題まで解きたかったのですが、復習しきれておらず、記事にもできませんでした。。。
後日に更新されるかもしれません。


# 前提

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

```rust
#[allow(unused_imports)]
use proconio::{input, fastout, marker::Chars};
#[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 - Your First Judge

もらった文字列をそのまま比較しましょう。
`if` を使えば判定できます。

```rust
fn main() {
  input! {
    s: String
  }
  let ans = if s == "Hello,World!" { "AC" } else { "WA" };
  println!("{}", ans);
}
```

# B - log2(N) 

問題名の通り、 $log_2N$ の整数部分が答えになります。
`log2()` 関数をつかおうとおもったのですが、 `log2()` は `f64` 型で丸め誤差が出そうだったのでやめました。
`2` で割れた回数が `log` の整数部分に一致して誤差も出ないので、今回の問題はこれで十分です。

$N$ を `2` で割っていくと最後は `1` になるのですが、`1` は `2` で割れないので、その時点でループを抜けることに注意です。

```rust

fn main() {
  input! {
    mut n: i64
  }
  let mut ans = 0;
  while n > 1 {
    n /= 2;
    ans += 1;
  }
  println!("{}", ans);
}
```

# C - One More aab aba baa 

天下り的ですが、 C++ でいう `next_permutation()` を使いましょう。
自分で実装すると複雑になっちゃいます。
調べると、 Rust には `permutohedron::LexicalPermutation` という trait がありました。

これは、比較演算子がある vector に対して、辞書順で次の並びにある列を返します。今回の問題そのままですね。
`next_permutation()` の計算量は $O(|S|)$ で、これを $|S|!$ 回くりかえします。
全体で $O(|S| * |S|! )$ となり計算量が心配ですが、制約より $1 \le |S| \le 8$ なので間に合います。

実装は以下のようになります。

```rust
use permutohedron::LexicalPermutation;

fn main() {
  input! {
    s: Chars,
    k: usize
  }
  let mut t = s;
  t.sort_unstable();

  if k == 1 {
    for c in t {
      print!("{}", c);
    }
    return;
  }

  let mut cnt = 1;
  while t.next_permutation() {
    cnt += 1;
    if k == cnt {
      break;
    }
  }

  for c in t {
    print!("{}", c);
  }
}
```


# D - Coprime 2 

`gcd` や素因数を扱う問題ですね。頻出です。

そのままやると $O(NM * \log\ max(A_i) )$ となって、時間内に解けません。高速化しましょう。

すべての $A_i$ に対して $gcd(A_i, k) = 1$ ということは、すべての $A_i$ と互いに素ということですね。これを判定するには、 すべての $A_i$ の素因数が必要です。
計算量を考えましょう。 $A_i$ の素因数を調べるには $O(\sqrt{A_i})$ かかります。すべての $A_i$ の素因数を調べるには $O(N \sqrt{A_i})$ かかります。制約より、この部分は時間内に解けそうですね。

また、「 1 以上 M 以下の整数 k を全て」の部分はエラトステネスの篩に似た方法が使えそうです。
上の考察より、すべての $A_i$ の素因数に対して篩の計算をすることに注意です。たとえば、`2` は素数ですが、$A_i$ の素因数に `2` がなければ、篩を計算するときに素数として扱いません。
この篩の部分の計算量は $O(M\ logM\ logM)$ になります。こちらも時間内に解けそうです。

これで全体で $O(N \sqrt{A_i} + M\ logM\ logM)$ の計算量になりました。

実装は以下になります。

```rust
fn main() {
  input! {
    n: usize,
    m: usize,
    mut a: [usize; n]
  }

  // 重複を除くことで高速化を狙う
  a.sort_unstable();
  a.dedup();

  // A_i の素因数を調べる
  let mut st = HashSet::new();
  for mut v in a.into_iter() {
    let mut p = 2;
    while p * p <= v {
      if v % p == 0 {
        st.insert(p);
      }
      while v % p == 0 {
        v /= p;
      }
      p += 1;
    }
    if v == 1 { continue; } // 1 は答えに含めるので continue
    st.insert(v);
  }

  // 篩に似た処理
  // gcd(A_i, k) = 1 になる k が true になる
  let mut ans = vec![true; m + 1];
  for p in st {
    for i in 1..=m / p {
      ans[i * p] = false;
    }
  }

  let ans = ans
    .into_iter()
    .enumerate()
    .filter(|(idx, val)| *idx != 0 && *val) // 0番目を除きながら、 true になっているものを抽出する
    .map(|(idx, _val)| idx)
    .collect_vec();

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

----

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

----

( E 問題の実装・記事メモ )

まず DP を考える。mint なので。
DP について、漸化式で解く人や、DPの気持ちになって解く人など、、、
bit DP といえば TSP とか。

1文字増えた時の遷移を考える。 4種類。
1. 過去に参加済み
-> 1-1. 同じものに連続参加
-> 1-2. 連続じゃない
2. 過去に参加していない
-> 2-1. それが全体で初参加
-> 2-2. 違うコンテストには参加している

実装する