RustでAtCoder Beginner Contest (ABC249)を解く！

[AtCoder Beginner Contest 249](https://atcoder.jp/contests/abc249)お疲れ様でした！
早速解説です！！(A-Dまで)

質問、感想はこの記事のコメントでも、[twitter](https://twitter.com/okaponta_)でも、大歓迎です！:muscle:

## [問題A](https://atcoder.jp/contests/abc249/tasks/abc249_a)

A問題としてはめちゃむずいです。。

### 考察
方針としては、高橋くんと青木くんそれぞれで進んだ距離を計算して比較します。
進んだ距離は以下で求められます。

- ($A+C$)秒で($A \times B$)だけ進むので、
- $(X/(A+C)) \times (A \times B)$ だけ距離に加算
- 上記の余りを考えると、以下の距離を進む。
    - $A$より余りが大きい場合は$A \times B$
    - $A$より余りが小さい場合は$(余り) \times B$

### 解答
考察をコードに落とし込めばOKです。

```Rust
use proconio::input;

fn main() {
    input! {
        a:i32,b:i32,c:i32,
        d:i32,e:i32,f:i32,
        x:i32
    }
    let tak = distance(a, b, c, x);
    let aok = distance(d, e, f, x);
    let ans = if tak > aok {
        "Takahashi"
    } else if tak == aok {
        "Draw"
    } else {
        "Aoki"
    };
    println!("{}", ans);
}

fn distance(a: i32, b: i32, c: i32, x: i32) -> i32 {
    let mut res = (x / (a + c)) * a * b;
    if x % (a + c) > a {
        res += a * b;
    } else {
        res += (x % (a + c)) * b;
    }
    res
}
```

https://atcoder.jp/contests/abc249/submissions/31216041

## [問題B](https://atcoder.jp/contests/abc249/tasks/abc249_b)

文字列操作を頑張る問題

### 考察

問題文の3つの条件をコードに落とし込めるかどうかを問われています。
大文字が含まれているか、小文字が含まれているかは用意されているメソッドを使うのがいいと思います。

重複がないかどうかは色々やり方が考えられます。
一例として、自分は以下で実装しています。

- `char`をソートする
- 重複を削除する
- もともとの長さと比較して、変化していれば重複あり。


### 解答

大文字判定は`is_uppercase()`
小文字判定は`is_uppercase()`
を使うと比較的楽に実装できます。

```rust
use proconio::{input, marker::Chars};

fn main() {
    input! {
        mut s:Chars,
    }
    let a = s.iter().any(|c| c.is_uppercase());
    let b = s.iter().any(|c| c.is_lowercase());
    let len = s.len();
    s.sort();
    s.dedup();
    let c = len == s.len();
    println!("{}", if a && b && c { "Yes" } else { "No" });
}
```

https://atcoder.jp/contests/abc249/submissions/31180170

## [問題C](https://atcoder.jp/contests/abc249/tasks/abc249_c)

Bit全探索の問題。知ってないとむずいかも。

### 考察

$N \leq 15$なので、Bit全探索が間に合う。
$N$個それぞれについて、選んだか選んでないかを全探索する方法で、
計算量はそれだけで$2^N$になります。

今回はこの制約で間に合うので、$2^N$それぞれについてカウントを求めて最大値を計算します。

### 解答

```rust
use std::collections::HashSet;

use proconio::{input, marker::Chars};

fn main() {
    input! {
        n:usize,
        k:usize,
        s:[Chars;n],
    }
    let mut sets = vec![];
    for ch in s {
        // 計算量落とすためにsetで管理した
        let set = ch.into_iter().collect::<HashSet<_>>();
        sets.push(set);
    }
    let mut ans = 0;
    // bit全探索
    for i in 0..1 << n {
        // A-Zまでの登場回数を記録
        let mut count = vec![0; 26];
        for j in 0..n {
            // bitが立っていれば処理する
            if i >> j & 1 == 1 {
                // A-Zそれぞれについて含まれるか計算
                for k in 0..26 {
                    let ch = (b'a' + k as u8) as char;
                    if sets[j].contains(&ch) {
                        count[k] += 1;
                    }
                }
            }
        }
        let tmp = count.iter().filter(|i| i == &&k).count();
        ans = ans.max(tmp);
    }
    println!("{}", ans);
}
```

https://atcoder.jp/contests/abc249/submissions/31216450

## [問題D](https://atcoder.jp/contests/abc249/tasks/abc249_d)

このロジックで計算量間に合うと思わず手付かずでした・・・
勉強になりました。。。

### 考察

[公式解説](https://atcoder.jp/contests/abc249/editorial/3786)が計算量の詳細な原理まで解説していますが、結論以下で間に合います。

 - $A_i$の各値の重複して出てくる回数を記憶しておく
 - $A_i$の最大値を$M$とおく
 - $A_j \times A_k = A_i$
 - $A_j$を1->$M$まで変化させ、$A_k$を$A_i$を超えない範囲でひとつずつ計算する
 - 以上で、計算量は$O(M \log M)$

### 解答

`map`がちょっと個人的に癖あるなぁと毎回思います。

```rust
use std::collections::HashMap;

use proconio::input;

fn main() {
    input! {
        n:usize,
        a:[usize;n],
    }
    // key...数字,value...登場回数
    let mut map = HashMap::new();
    let mut max = 0;
    for ai in a {
        max = max.max(ai);
        *map.entry(ai).or_insert(0i64) += 1;
    }
    let mut ans = 0;
    // ajは全探索
    for (&aj, val) in map.iter() {
        // akは1からMAXまで
        for ak in 1..=(max / aj) {
            let ai = aj * ak;
            // 登場回数どうしを掛け算。無い場合は0。
            ans += map.get(&ai).unwrap_or(&0) * map.get(&ak).unwrap_or(&0) * val;
        }
    }
    println!("{}", ans);
}
```

https://atcoder.jp/contests/abc249/submissions/31217004

----

Rustでの解説記事結構少ないので書いてみました・・・！
初回で書くの結構大変だったので、問題はA-Dまでです。。慣れてきたらE問題やF問題も書いていきたいと思います:bow:

最後までお読みいただきありがとうございました！:relaxed: