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

# はじめに

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


# なぜやるのか

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


# 目次

[A - Tires](#a---tires) (<font color="#808080">Difficulty 6</font>)
[B - Mongeness](#b---mongeness) (<font color="#808080">Difficulty 81</font>)
[C - Triangle?](#c---triangle?) (<font color="#808080">Difficulty 301</font>)
[D - 8 Puzzle on Graph](#d---8-puzzle-on-graph) (<font color="#00C0C0">Difficulty 1376</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 - Tires

文字列の後ろをみる問題ですね。
後ろの2文字が `er` かをみてもいいのですが、今回は一番後ろの1文字をみれば判定可能でした。

```rust
fn main() {
  input! {
    s: Chars
  }
  let ans = if s[s.len() - 1] == 'r' { "er" } else { "ist" };
  println!("{}", ans);
}
```

# B - Mongeness 

複雑に見えるかもしれません。ですが制約が小さめですね。

制約が小さめなので全通りを考えるてみると、だいたい $50 * 50 * 50 * 50 = 6.25 * 10^6$ 通りです。
判定1回分は $O(1)$ でできるので、全体の計算量は $O(N^4)$ です。これは計算時間的には間に合うので全探索で解きました。

```rust
fn main() {
  input! {
    h: usize,
    w: usize,
    a: [[usize; w]; h]
  }
  let mut ok = true;
  for y1 in 0..h {
    for y2 in y1 + 1..h {
      for x1 in 0..w {
        for x2 in x1 + 1..w {
          ok &= (a[y1][x1] + a[y2][x2] <= a[y1][x2] + a[y2][x1]);
        }
      }
    }
  }
  println!("{}", if ok { "Yes" } else { "No" });
}
```

# C - Triangle? 

これも複雑に見えますね。ですが、これもB問題と同様に制約が小さめです。
全通りを考えると、だいたい $300 * 300 * 300 = 2.7 * 10^7$ 通りです。

次に、判定1回分を考えます。

3点を選んで結んだ三角形の面積を考えるのは、数学が入ってきて少し複雑そうですね。
複雑なので、別の方法がないか考えてみます。

今回は余事象を考えます。つまり、面積が正ではない場合を考えます。これは 3点が同一直線上にあるときですね。同一直線上にあるときは面積が 0 になります。

面積を求める問題が、同一直線上の判定になりました。これも数学を使いますが、面積を求めるよりは簡単に求められます。
というのも、点1, 点2, 点3 について、「点1 と 点2 の傾き」と「点1 と 点3 の傾き」が等しくなれば同一直線上にあるといえます。
傾きを求めるには `縦の増加量 / 横の増加量` ですね。
ですが、ここで注意点があります。

1. 負の値になることがあるので `usize` は使えない
2. 0除算 になることがある

です。特に 2 が厄介ですが、これは式変形をすれば対応できます。
$(y_1 - y_2) / (x_1 - x_2) == (y_1 - y_3) / (x_1 - x_3)$
$\Leftrightarrow$
$(y_1 - y_2) * (x_1 - x_3) == (y_1 - y_3) * (x_1 - x_2)$
ですね。この形なら0除算は起こりません。

ここまでわかれば実装です。以下のようになりました。

```rust
fn main() {
  input! {
    n: usize,
    xy: [(i64, i64); n]
  }
  let mut ans = 0;
  for i1 in 0..n {
    for i2 in i1 + 1..n {
      for i3 in i2 + 1 ..n {
        let xy1 = xy[i1];
        let xy2 = xy[i2];
        let xy3 = xy[i3];

        // (xy1.1 - xy2.1) / (xy1.0 - xy2.0) == (xy1.1 - xy3.1) / (xy1.0 - xy3.0)
        let ok = (xy1.1 - xy2.1) * (xy1.0 - xy3.0) != (xy1.1 - xy3.1) * (xy1.0 - xy2.0);
        if ok {
          ans += 1;
        }
      }
    }
  }
  println!("{}", ans);
}
```


# D - 8 Puzzle on Graph 

15パズルの発展形を解く問題ですね。

問題の考察をしても効率的な解き方が思いつきません。そういうときはとっかかりとして全探索を考えてみましょう。頂点の数は `9` で固定なので、取り得る状態は全部で $9! = 362880$ 個です。状態数が少ないので全探索で解けそうなことがわかりますね。全探索で解くことを考えてみます。

全探索といえば BFS や DFS や `next_permutation` などがありますが、今回はコマを動かした回数を「最小化」する問題なので、 BFS だと解きやすそうです。

続いて、BFS で使う `queue` に何を `push` するかを考えます。状態を全探索するのですが、状態をどのように表現するかを考えます。
これには `String` を使います。頂点1 にあるコマが 1文字目、頂点2 にあるコマが 2文字目、、、と表現します。空の頂点の場合は `-` としましょう。

BFS と `queue` に入れるものが決まったので、次はコマの移動を考えます。
「空の頂点」と「隣接する頂点」にあるコマが移動可能です。移動元の頂点と移動先の頂点が決まれば、値を `swap` すれことでコマの移動を実現できます。
あとは、同じ状態になることを避けます。無限ループしちゃうので。これは `HashSet` などで一度見た状態を記録すれば大丈夫です。

これまでの部分は、BFS によるグラフの全探索とかなり似ていると思います。

さて、ここまでわかれば実装です。
`String` を使って Rust で書くの大変だった。。。 `String` じゃなくて `Vec<char>` だと、もうちょっと楽に解けるかと思います。

```rust
fn main() {
  input! {
    m: usize,
    mut uv: [(usize, usize); m],
    p: [usize; 8]
  }
  let mut graph = vec![vec![]; 9];
  for (from, to) in uv.iter() {
    let from = from - 1;
    let to = to - 1;
    graph[from].push(to);
    graph[to].push(from);
  }

  let mut goal = vec![10; 9];
  let mut first = p // 最初の状態
    .iter()
    .map(|v| {
      let v = v - 1;
      goal[v] = v; // 最初の状態に含まれる数字を記録する
      v.to_string()
    })
    .collect::<String>()
  ;
  first += "-";
  
  let goal = goal // ゴールの状態
    .into_iter()
    .map(|v| {
      if v == 10 { String::from("-") } // 最初の状態に含まれていないものを "-" にする
      else { v.to_string() } // 最初の状態に含まれていればそのまま使う
    })
    .collect::<String>()
  ;

  let mut shown = HashSet::<String>::new(); // これまでに見た状態
  let mut que = VecDeque::<(String, usize)>::new(); // BFS のプール / VecDeque::<(今の状態, 移動させた回数)>

  que.push_back((String::from(&first), 0));
  shown.insert(String::from(&first));

  while let Some((now, depth)) = que.pop_front() {
    if now == goal { // 終了判定
      println!("{}", depth);
      return;
    }

    let mut to = 0;
    for (idx, c) in now.chars().enumerate() {
      if c == '-' { // "-" になっている頂点に移動する
        to = idx;
      }
    }
    for from in graph[to].iter() { // "-" になっている頂点(to)につながる頂点(from)にあるコマを移動させる
      // now[from] と now[to] を swap する
      // もっとコンパクトに書ける方法あったら教えてください。。。
      let mut next = now.chars().collect_vec();
      next.swap(to, *from);
      let next = next.iter().collect::<String>();
      
      // 数字を移動させた後の状態が next になる
      if shown.contains(&next) { continue } // すでに見たことあるならなにもしない
      shown.insert(String::from(&next));
      que.push_back((String::from(&next), depth + 1));
    }
  }
  println!("-1");
}
```


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