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

# はじめに

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

# なぜやるのか

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

# 目次

[A - Alloy](#a---alloy) (<font color="#808080">Difficulty 5</font>)
[B - Weak Password](#b---weak-password) (<font color="#808080">Difficulty 64</font>)
[C - Min Difference](#c---min-difference) (<font color="#808080">Difficulty 246</font>)
[D - Querying Multiset](#d---querying-multiset) (<font color="#804000">Difficulty 775</font>)
[E - Safety Journey](#e---safety-journey) (<font color="#00C0C0">Difficulty 1410</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 - Alloy

問題文に条件式があるのでそのままコードにします。
$0 < A + B$ より、 $A = 0,\ B = 0$ の場合はないことに留意して、例えば以下のように書けます。

```rust
fn main() {
  input! {
    a: usize,
    b: usize
  }

  let ans = if b == 0 {
    "Gold"
  } else if a == 0 {
    "Silver"
  } else {
    "Alloy"
  };
  println!("{}", ans);
}
```

# B - Weak Password

問題文が少し複雑です。

文字列、もしくは4桁の数字で受け取って、4つの数字に直します。
文字列の場合は文字にした後、 `'0'` を引くと数字になります。文字は内部的には数値であることを利用しています。
数字の場合は `10^n` で割ってから `% 10` をします。例えば 2 桁目を取り出すときは `100` で割ってから `% 10` をします。

あとは素直に判定すると答えがわかります。 `for` でまとめてもいいと思います。
連番を判定するときは、 `9` の次が `0` になるように `% 10` をしています。

```rust
fn main() {
  input! {
    x: Chars
  }
  let x1 = x[0] as i32 - '0' as i32;
  let x2 = x[1] as i32 - '0' as i32;
  let x3 = x[2] as i32 - '0' as i32;
  let x4 = x[3] as i32 - '0' as i32;

  let mut ans = "Strong";
  if x1 == x2 && x2 == x3 && x3 == x4 {
    ans = "Weak";
  }
  if (x1 + 1) % 10 == x2 && 
     (x2 + 1) % 10 == x3 && 
     (x3 + 1) % 10 == x4 {
      ans = "Weak";
  }
  println!("{}", ans);
}
```

# C - Min Difference

そのままやると $O(NM)$ になって時間内に処理が終わりません。なにか高速化が必要です。

使える高速化としては、しゃくとり法や二分探索があるのですが、今回はしゃくとり法を使います。
しゃくとり法といえば [ABC210-C](https://atcoder.jp/contests/abc210/tasks/abc210_c) でも出ましたね。今回も同様に、範囲をずらしながら配列上を走査します。ただ、動き方は ABC210-C とは少し違うものになるので注意です。

今回は配列を 2 つ使います。
「 $A$ を固定して $B$ を見る場合」と 「 $B$ を固定して $A$ を見る場合」の 2 通りのやり方がありますが、どちらもあまり変わりません。ここでは「 $A$ を固定して $B$ を見る場合」でやります。

まずはひとつの $A_i$ について、答えになり得る $B_i$ を考えましょう。
これは、
・$B$ の要素のうち $A_i$ 以下の最大のもの
・$B$ の要素のうち $A_i$ 以上の最小のもの
の 2 つが候補になりますね。この 2 つは連番になるので、前者を $B_i$ とすると、後者は $B_{i+1}$ になります。
このとき、答えは $min(\ |A_i - B_i|,\ |A_i - B_{i+1}|\ )$ と表せます。

あとは $A_i$ の $i$ を変えながら $A$ をすべて試せば答えがわかります。
$B_i$ の $i$ は前回のものを使いまわすことで、計算量を減らせます。この部分がしゃくとり法です。
(ここで、$B_i$ の $i$ を毎回使いまわさない場合は 二分探索 による解法になります)

範囲外などで $A_i$ に 対応する $B_i$ と $B_{i+1}$ が存在しないこともあるので注意です。

```rust
use num::abs;

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

  a.sort();
  b.sort();

  let mut i = 0;
  let mut ans = 2100100100;
  for v in a {
    while i < m && b[i] <= v {
      ans = min(ans, abs(v - b[i]));
      i += 1;
    }
    if i < m {
      ans = min(ans, abs(v - b[i]));
    } else {
      break;
    }
  }
  println!("{}", ans);
}
```

# D - Querying Multiset

クエリの問題ですね。

操作１と操作３のクエリは、 ヒープか平衡二分探索木をつかえばある程度高速に処理できます (データサイズを $N$ として $O(log N)$ です) 。
ですが、操作２のクエリがヤバいです。
これをそのままやると、データサイズを $N$ として $O(N)$ かかります。全体では $O(NQ)$ になります。
クエリ数 $Q$ は最大で $2 * 10^5$ で、 データサイズ $N$ も最大で $2 * 10^5$ 程度になるので、時間内に処理が終わりません。

そのままやるのは無理なので、操作２のクエリを高速化することを考えます。
全要素の値を書き換えていると、どう頑張っても $O(NQ)$ になるので、全要素を書き換えない方針で考えてみます。追加時と出力時 (操作１と操作３のとき) の値に何か工夫してみましょう。

ここでは、累積和の考え方を使います (はじめは浮かびにくいかもしれませんが、頻出なので覚えておくといいです) 。
ヒープなどのデータ構造と別に、累積和の値を管理します。
累積和を使って追加時に何かの処理をして、出力時に逆の処理をする方針を考えます。
この処理をすることで、追加されている間の操作２の値が反映されるようにしたいです。

実際に試したりすると、追加時には引いて、出力時には足せばいいことがわかります。
こうすると、入力されてから出力されるまでの間に累積和に加算された分がうまく反映されます。

さて、ここまでわかれば実装です。私は `BinaryHeap` を使いました。
また、デフォルトだと最大値から取り出されるのですが、最小値から取り出すために `Reverse` を使っています。

```rust
use std::cmp::Reverse;
use std::collections::BinaryHeap;

fn main() {
  input! {
    q: usize
  }

  // 累積和 accumulate
  let mut acc: i64 = 0;
  let mut que = BinaryHeap::new();

  for _ in 0..q {
    input! { p: usize }
    if p == 1 {
      input! { x: i64 }
      // x - acc を追加する
      // 小さい方から取り出すため Reverse を使う
      que.push(Reverse(x - acc));
    } else if p == 2 {
      input! { x: i64 }
      acc += x;      
    } else {
      // 最小値を出力する
      // 追加したときと逆の計算 (ans + acc) をする
      let Reverse(ans) = que.pop().unwrap();
      println!("{}", ans + acc);
    }
  }
}
```

# E - Safety Journey

DP の問題です。初見では DP だと思えませんでした。

まず、そのままやると計算量がとても大きくなります。 $O(N^2K)$ でしょうか。これでは解けません。
制約を眺めてみると、 $M$ が比較的小さいことがわかります。ここから、余事象をつかうアイデアを思いつきます。

余事象なので、道が 1 つも壊れていない場合の旅の数を考えます。ちなみにこれは完全グラフになりますね。
まず 1 日分の移動で考えます。「ある頂点」にくる旅の数は、「ある頂点」と連結な頂点にある旅の数の総和になります。
「ある頂点」を除いた全頂点の、旅の数の総和とも言えます。これはとても DP らしいですね。

続いて、余事象を考えるので、道が壊れている場合を考慮します。
道が壊れているということは、グラフで言うと連結ではありません。上で総和を出した後、壊れている道の分だけ旅の数を引きます。

これを $K$ 日つづければ、道が壊れていない場合の旅の数がわかります。

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

  let m = 998244353;
  let mut dp = vec![0; n];
  dp[0] = 1;
  for _ in 0..k {
    let sum: i64 = dp.iter().sum();
    
    // 道が1つも壊れていない場合の旅の数を計算する
    let mut next = dp.iter().map(|v| sum - v).collect::<Vec<_>>();

    // 道が壊れて行き来できない分の旅の数を引く
    for &(u, v) in &uv {
      let u = u - 1;
      let v = v - 1;
      next[u] -= dp[v];
      next[v] -= dp[u];
    }

    dp = next.iter().map(|v| v % m).collect::<Vec<_>>();
  }
  println!("{}", dp[0]);
}
```