ABC223 を Rust で解く (E問題まで)

# はじめに

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


# なぜやるのか

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


# 目次

[A - Exact Price](#a---exact-price) (<font color="#808080">Difficulty 6</font>)
[B - String Shifting](#b---string-shifting) (<font color="#808080">Difficulty 86</font>)
[C - Doukasen](#c---doukasen) (<font color="#808080">Difficulty 354</font>)
[D - Restricted Permutation](#d---restricted-permutation) (<font color="#008000">Difficulty 1069</font>)
[E - Placing Rectangles](#e---placing-rectangles) (<font color="#00C0C0">Difficulty 1510</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 - Exact Price

もらった入力が100で割り切れるかを判定する問題ですね。
 `x % 100 == 0` で判定できますが、 `x = 0` のときだけは対象外なことに注意です。

```rust
fn main() {
  input! {
    x: usize
  }
  let ans = if x % 100 == 0 && x > 0 { "Yes" } else { "No" };
  println!("{}", ans);
}
```


# B - String Shifting 

python の `numpy.roll` のような挙動ですね。

Rust  は range を使って String の slice ができるのでこれを利用します。
ひとつの文字列を作るのには $O(1)$ かかって、長さ `N` の文字列をシフトさせてできる文字列は `N` 通りあるので、すべての対象文字列を探索しても時間的に間に合います。
作った文字列を記憶しておいて、ソートすれば先頭と最後尾が答えになります。

```rust
fn main() {
  input! {
    s: String
  }
  let mut pool = vec![];
  for i in 0..s.len() {
    let nx = s[i..].to_string() + &s[0..i];
    pool.push(nx);
  }
  pool.sort_unstable();
  println!("{}", pool[0]);
  println!("{}", pool.pop().unwrap());
}
```


# C - Doukasen 

`距離 = 速さ * 時間` の式をうまく使う問題です。

ちょっと複雑ですね。 (思考停止で二分探索をやりたくなる...)
二分探索でも解けますが、愚直にやるともっとシンプルに解けます。

左側と右側から同時に火をつけて2つの火がぶつかるときは、燃えた距離は違いますがかかった時間は同じです。これを利用します。
また、ぶつかるときの時間は、片方だけから燃やしたときにかかる時間の半分になります。
方針としては、左側のみから火をつけたときに導火線が燃え尽きる時間を計算した後、半分の時間でどこまで燃えるかを計算します。

距離が $A_i$ で速さが $B_i$ なので、燃えるのにかかる時間は $A_i / B_i$ ですね。この総和が全体でかかる時間になります。
全体の時間がわかれば、その半分の時間まで1本ずつ燃やしていけばいいです。

導火線の途中で半分の時間を超えるときがあるので、そこの処理に注意です。


```rust
fn main() {
  input! {
    n: usize,
    ab: [(f64, f64); n]
  }
  let all_time: f64 = ab.iter().map(|(a, b)| a / b).sum();
  let mut length = 0.0;
  let mut time = 0.0;
  for (a, b) in ab.into_iter() {
    if time + a / b < all_time / 2.0 { // 導火線が燃えても時間が来ないとき
      length += a;
      time += a / b;
    } else { // 導火線の途中で燃え尽きるとき
      let res = all_time / 2.0 - time;
      length += res * b;
      break;
    }
  }
  println!("{}", length);
}
```


# D - Restricted Permutation 

トポロジカルソートの問題ですね。

通常のトポロジカルソートは Queue を使うのですが、その代わりに 最小Heap を使うと解けます。
問題の発想は [ABC208-D](https://atcoder.jp/contests/abc208/tasks/abc208_d) に似ていて、アルゴリズムの挙動を知っているかが問われる問題だと感じました。

トポロジカルソートは有向非巡回グラフ (DAG: Direcred Acyclic Graph) を並べ替えるアルゴリズムです。
通常のソートとは違ってグラフが対象で、頂点を並べ替えるソートです。
トポロジカルソートで頂点を (例えば左から右に) 並べ替えると、グラフの有向辺を書いたときにすべての辺が左から右に向かうようになります。逆に言うと、右から左に向かう辺がなくなります。

通常のソート結果は一意なのですが、トポロジカルソートの結果は一意ではありません。辺の向きが左から右に向いていれば頂点の並びは何でもいいです。

...という前提があって、複数考えられるソート結果の中で、辞書順最小を求める問題です。

トポロジカルソートの詳しい実装はここでは書きませんが(すみません)、入り次数が 0 になったものから Queue につめて順に処理しますよね。この処理を数値の小さい順にやれば答えになります。
具体的には、 Queue を 最小Heap にすれば大丈夫です。

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

  let mut deg = vec![0; n]; // 入り次数
  let mut graph = vec![vec![]; n];
  for (mut a, mut b) in ab.into_iter() {
    a -= 1; b -= 1;
    graph[a].push(b);
    deg[b] += 1;
  }

  let mut sorted = vec![];
  let mut que = BinaryHeap::new();
  for v in 0..n {
    if deg[v] == 0 { // 入り次数が 0 のものを最小Heap にいれる
      que.push(Reverse(v));
    }
  }
  while let Some(Reverse(now)) = que.pop() {
    sorted.push(now + 1);
    for to in graph[now].iter() {
      deg[*to] -= 1;
      if deg[*to] == 0 { // 入り次数が 0 になったら最初Heap にいれる
        que.push(Reverse(*to));
      }
    }
  }

  if sorted.len() < n { // サイズが N 未満だとトポロジカルソート失敗 (DAG じゃなかった)
    println!("-1");
  } else {
    for i in 0..n {
      println!("{}", sorted[i]);
    }
  }
}
```


# E - Placing Rectangles 

長方形を敷き詰める問題ですね。

ABCには珍しく、考察だけの問題でした(ABCは暗記に考察をちょっと足した問題が多く出る旨をちょくだいさんが言っていました)。

方針としては、まず長方形のひとつを辺いっぱいに沿って配置します。そのあと、残った空間に残りの2つの長方形を敷き詰められるかを判定します。これを組み合わせを変えて複数回やります。

配置できた図を考えると、3つのうち1つは辺を伸ばすと辺に沿って配置することができます。なので、3つのうち1つが辺に沿って配置できる長方形だと決め打ちします。こうすると長方形の配置がひとつ決まるので、のこりの2つを配置できれば答えがわかります。1つめの辺をY軸に沿って伸ばすとすると、のこりの2つの配置方法は縦に並べる (`川`の字) か横に並べる (`に`の字) かですね。
これを、組み合わせを変えて複数回ためせば答えがわかります。

ひとつ注意なのが、長方形を辺いっぱいに沿って配置すると、縦の長さは「辺の長さと同じ」で、横の長さは「面積を縦の長さで割って切り上げたもの」になります。

ここまでわかれば実装です。以下のようになりました(あんまりスマートじゃない...)。

```rust
fn main() {
  input! {
    mut x: i64,
    mut y: i64,
    a: i64,
    b: i64,
    c: i64
  }

  // check(面積1, 面積2, 面積3, 横, 縦) = この条件で敷き詰めることができるか
  let check = |a: i64, b: i64, c: i64, x: i64, y: i64| -> bool {
    let mut tx = x;
    let mut ret = false;

    // a を辺いっぱいに配置する
    tx -= (a - 1) / y + 1;

    // b, c を横に配置する
    if tx > 0 {
      let mut ty = y;
      ty -= (b - 1) / tx + 1;
      ty -= (c - 1) / tx + 1;
      ret |= ty >= 0;
    }

    // b, c を縦に配置する
    tx -= (b - 1) / y + 1;
    tx -= (c - 1) / y + 1;
    ret |= tx >= 0;

    ret
  };

  let mut ans = false;
  ans |= check(a, b, c, x, y); // a先頭, x横, y縦
  ans |= check(b, c, a, x, y); // b先頭, x横, y縦
  ans |= check(c, a, b, x, y); // c先頭, x横, y縦

  ans |= check(a, b, c, y, x); // a先頭, y横, x縦
  ans |= check(b, c, a, y, x); // b先頭, y横, x縦
  ans |= check(c, a, b, y, x); // c先頭, y横, x縦

  println!("{}", if ans { "Yes" } else { "No" });
}
```


----

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