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

# はじめに

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


# なぜやるのか

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


# 目次

[A - AtCoder Quiz 2](#a---atcoder-quiz-2) (<font color="#808080">Difficulty 6</font>)
[B - Maritozzo](#b---maritozzo) (<font color="#808080">Difficulty 18</font>)
[C - Neo-lexicographic Ordering](#c---neo-lexicographic-ordering) (<font color="#808080">Difficulty 260</font>)
[D - Strange Lunchbox](#d---strange-lunchbox) (<font color="#008000">Difficulty 1085</font>)


# 前提

この記事にあるコードはこちらを 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 - AtCoder Quiz 2

問題文にある通りに場合分けしました。

`ans` 変数について、 答えになる値としては `expert` のみが文字列で、ほかは数値ですね。
`if - else if - else` 文ではどの条件でも戻り値の型が一致する必要があるので、型の違う `expert` だけは別の `if` 文で処理しています。

```rust
fn main() {
  input! {
    x: usize
  }

  if 90 <= x {
    println!("expert");
    return;
  }

  let ans = if x < 40 { 40 - x }
    else if x < 70 { 70 - x }
    else { 90 - x };

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


# B - Maritozzo 

文字列を1文字ずつ、インデックスとして扱う問題ですね。
`1`, `2`, `3` の場合それぞれを場合分けして解きました。

```rust
fn main() {
  input! {
    s: [String; 3],
    t: Chars
  }
  let mut ans = String::from("");
  for c in t.into_iter() {
    if c == '1' {
      ans += &s[0];
    }
    if c == '2' {
      ans += &s[1];
    }
    if c == '3' {
      ans += &s[2];
    }
  }
  println!("{}", ans);
}
```


# C - Neo-lexicographic Ordering 

指定されたソート順でソートする問題ですね。

まず `x` の先頭から順にインデックスをつけます。例えば入力例1 の `bacdefghijklmnopqrstuvwxzy` の場合は、
`b` = 0
`a` = 1
`c` = 2
...
となるようにします。これは `enumerate()` を使えばできますね。
こうすることで、変換後の文字の表示順が数値でわかります。

続いて、つけたインデックスを文字にします。つまり、以下のようにします。
`b` = `a`
`a` = `b`
`c` = `c`
...
こうすると、`変換後` = `変換前` の形になって、各文字の変換先がわかりますね。
この変換の式をつかって、 `s` の文字列を変換します。

変換できれば、変換後の文字列でソートすれば、求める順番になります。
ここからさらに逆変換をすれば答えがわかるのですが、少し大変なので、私は変換前の index を保存して解きました。

ちなみにここでは、文字ではなく数値に変換しても大丈夫です。その場合は `map()` の式が以下のようになります。
`.map(|(idx, val)| (val.chars().map(|c| order[c as usize - 'a' as usize].1).collect_vec(), idx))`
この場合は、変換後が文字列ではなく `usize` の `Vec` になります。


余談ですが、 `u8` (文字) を対象に `sort_unstable()` を実行すると、 `usize` を対象に実行した場合よりも高速でした。backet sort でもしているのかなと思いました。

```rust
fn main() {
  input! {
    x: Chars,
    n: usize,
    s: [String; n]
  }
  let mut order = x
    .iter()
    .enumerate()
    .map(|(idx, val)| (val, idx))
    .collect_vec();

  order.sort_unstable();
  
  let mut t = s
    .iter()
    .enumerate() // 下の map() で s の各文字列を 1 文字ずつ変換している
    .map(|(idx, val)| (val.chars().map(|c| order[c as usize - 'a' as usize].1 as u8 as char).collect::<String>(), idx))
    .collect_vec();

  // 変換後の表示順でソート  
  t.sort_unstable();

  // index を使って、変換前の文字列を出力
  for (_, idx) in t.into_iter() {
    println!("{}", s[idx]);
  }
}
```


# D - Strange Lunchbox 

なにやら knapsack 問題と似ています。DP の問題ですね。
knapsack 問題に不安がある場合は [ABC032-D](https://atcoder.jp/contests/abc032/tasks/abc032_d) を解いてみるのをオススメします。

knapsack 問題に似せてDPテーブルを考えてみましょう。
`dp[i][j][k] = i 個みて、たこやき j 個、たいやき k 個のときの弁当の最小個数`
ですね。これを更新して、 `j` と `k` が `x` と `y` 以上の区間を調べればこたえがわかります。
ですが、ここで問題になるのが、 `j` と `k` が最大で 90000 になることですね。
そうすると、DPテーブルのサイズが `dp[301][90001][90001]` になります。
これだと knapsack DP では TLE して、そもそもメモリが足りません。

困りました。困ったときは問題を眺めましょう。すると、今回はたこ焼きとたい焼きの個数は最大でも 300 ですね。
つまり、300 以上の範囲を計算する意味がほとんどなくなります。
計算する意味はあるのですが、「300個以上もっているときの弁当の最小個数」がわかればいいです。

すこしわかりにくいかもしれませんが、300個以上の範囲は「特定の個数だけもっている時の弁当の最小個数」は知らなくてもいいです。
こうすると、300個以上の状態はひとつにまとめられます。
少しの違いですがこれが大きくて、DPテーブルのサイズが `dp[301][301][301]` になりました。
これだと時間内に計算できそうですね。

`dp[i][300][k]` には、「弁当を `i` 個みて、たこやき `300` 個以上、たいやき `k` 個のときの弁当の最小個数」がはいります。
あとは、knapsack 問題の要領で解けば答えがわかります。


```rust
fn main() {
  input! {
    n: usize,
    x: usize,
    y: usize,
    ab: [(usize, usize); n]
  }
  
  let inf = 1001001001;

  // dp[i][x][y] = i 個みて、 たこやき x 個 / たいやき y 個 のときの弁当の最小個数
  let mut dp = vec![vec![vec![inf; 310]; 310]; 310];
  dp[0][0][0] = 0;
  for i in 0..n {
    let (a, b) = ab[i];
    for j in 0..=x {
      for k in 0..=y {
        dp[i + 1][j][k] = min(dp[i + 1][j][k], dp[i][j][k]);

        let nx = min(x, j + a); // x 個以上の状態はまとめる
        let ny = min(y, k + b); // y 個以上の状態はまとめる
        dp[i + 1][nx][ny] = min(dp[i + 1][nx][ny], dp[i][j][k] + 1);
      }
    }
  }

  let ans = if dp[n][x][y] == inf { -1 } else { dp[n][x][y] };
  println!("{}", ans);
}
```




----

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