RustでABC286復習

# はじめに
Rustの勉強のために[AtCoder](https://atcoder.jp/home)のコンテストでRustを使うことにしました。
解説を読んだりして自分がわかった範囲で復習します。

# 復習
## [A - Range Swap](https://atcoder.jp/contests/abc286/tasks/abc286_a)
数列の一部を入れ替える問題。
愚直に実装するだけだが数列$A$をコピーしてから入れ替えると実装が楽になる。
``` Rust
use proconio::input;
use proconio::marker::Usize1;


fn main() {
    input! {
        n: usize,
        p: Usize1,
        q: Usize1,
        r: Usize1,
        s: Usize1,
        a: [u64; n],
    }
    let mut ans = a.clone();
    for i in p..=q {
        ans[i] = a[r+i-p];
    }
    for i in r..=s {
        ans[i] = a[p+i-r];
    }
    println!("{}", ans.iter().map(|&x| x.to_string()).collect::<Vec<_>>().join(" "));
}
```
## [B - Cat](https://atcoder.jp/contests/abc286/tasks/abc286_b)
「na」を「nya」に置換する問題。
前から文字列を見ていき、「n」「a」が見つかれば「n」「y」「a」を入れて、そうでない場合はその文字を入れる。
```Rust
use proconio::input;
use proconio::marker::Chars;


fn main() {
    input! {
        n: usize,
        s: Chars,
    }
    let mut i = 0usize;
    let mut ans = vec![];
    while i < n {
        if i + 1 < n && s[i] == 'n' && s[i+1] == 'a' {
            ans.push('n');
            ans.push('y');
            ans.push('a');
            i += 1;
        } else {
            ans.push(s[i]);
        }
        i += 1;
    }
    println!("{}", ans.iter().collect::<String>());
}
```
## [C - Rotate and Palindrome](https://atcoder.jp/contests/abc286/tasks/abc286_c)
文字列をシフトしたり入れ替えてできるだけ安く回文を作る問題。
$n$はたかだか$5000$なので一つずつずらした場合にかかる費用を全て調べて最小値を取れば良い。
回文にするために必要な費用は、対応する2か所が同じかを比較し、異なっている場合は$B$円払ってどちらかに合わせる。$N$が奇数の場合は真ん中の文字は比較対象が自身なので見なくてよい。
文字列を$i$回移動した場合、初期費用$iA$をかけて費用を計算する。すべての$0 \lt i \lt N$に対して費用を計算して最小値が答えになる。
![c1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3083981/d788881e-dc13-d901-884f-8927a324f1b4.png)
```Rust
use proconio::input;
use proconio::marker::Chars;
use std::cmp::min;


fn main() {
    input! {
        n: usize,
        a: u64,
        b: u64,
        s: Chars,
    }
    let mut ans = None;
    for i in 0..=n {
        let mut v = i as u64 * a;
        for j in 0..(n+1)/2 {
            if s[(i+j)%n] != s[(n+i-j-1)%n] {
                v += b;
            }
        }
        ans = Some(match ans {
            Some(a) => min(a, v),
            None => v,
        });
    }
    println!("{}", ans.unwrap());
}
```
## [D - Money in Hand](https://atcoder.jp/contests/abc286/tasks/abc286_d)
持っている硬貨を使用してぴったりお金を払うことができるか判定する問題。
$1 \lt N \lt 50$なので半分全列挙を考えたくなるが、$1 \lt B \lt 50$も考えるととても大きな数になるのでナップザック問題と同様に$DP$で考える。
$dp[v]$を$v$円ちょうど払うことができるかで表し、
まず、
```math
dp[0] = true \\
dp[i] = false (0 \lt i)
```
で初期化する。
ここから各$A_i$に対して$X$から$0$にかけて、$dp[j]$が$true$なら$1 \le k \le B_i$に対して$dp[j+kA_i]$を$true$とするように更新する。このとき$0$から$X$にかけて更新すると$dp[j]$が$true$のとき<b>任意の自然数</b>$k$に対して$j+kA_i$が$true$になってしまうので注意。
最終的に$dp[X]$が$true$なら答えはYesでそうでないなら答えはNoになる。
```Rust
use proconio::input;


fn main() {
    input! {
        n: usize,
        x: usize,
        coins: [(usize, usize); n],
    }
    let mut dp = vec![false; x+1];
    dp[0] = true;
    for &(a, b) in &coins {
        for v in (0..x).rev() {
            if x < v + a || !dp[v] {
                continue;
            }
            let mut v = v;
            for i in 0..b {
                v += a;
                if x < v {
                    break;
                }
                dp[v] = true;
            }
        }
    }
    if dp[x] {
        println!("Yes");
    } else {
        println!("No");
    }
}
```
## [E - Souvenir](https://atcoder.jp/contests/abc286/tasks/abc286_e)
任意の2頂点間の経路のうち最短で、できるだけ合計で高い価値を持つお土産を買える経路を見つけ、その経路の距離とお土産の価値の合計を答える問題。
事前に任意の2頂点間で答えを出しておいてクエリはその答えを出すだけにする。
答えの作り方は都市$U$から都市$V$への経路での答えを$ans[U][V]$で管理し、BFS(幅優先探索)で求める。$ans$は最初全て$None$で初期化する。
BFSでは訪れた都市に対して、訪れたことがない都市だった場合は$ans$を更新し、訪れたことのある都市だった場合は距離が等しくお土産の価値が高い場合に更新する。距離が「より短い」ではなく「等しい」で良いのはBFSで探索しているため距離が長い経路を先に見つけることはないためである。
この方法で答えを求めると、ある都市から他のすべての都市への経路での答えを辺の数である$O(N^2)$で求めることができ、全体で$O(N^3)$でも解けることができる。
なお、BFSの代わりにダイクストラ法を使用すると全体の計算量は$O(N^3 \log N)$になり間に合わない。
```Rust
use proconio::input;
use proconio::marker::{Chars, Usize1};
use std::collections::VecDeque;
use std::cmp::max;


fn main() {
    input! {
        n: usize,
        a: [u64; n],
        s: [Chars; n],
        q: usize,
        queries: [(Usize1, Usize1); q],
    }
    let mut ans: Vec<Vec<Option<(u64, u64)>>> = vec![vec![None; n]; n];
    for i in 0..n {
        let mut queue = VecDeque::new();
        queue.push_back((0u64, None, i));
        while let Some((dist, src, node)) = queue.pop_front() {
            let value = a[node] + match src {
                Some(orig_src) => {
                    if let Some((_, v)) = ans[i][orig_src] {
                        v
                    } else {
                        0
                    }
                }
                None => 0u64,
            };
            if let Some((orig_dist, orig_value)) = ans[i][node] {
                if orig_dist == dist {
                    ans[i][node] = Some((orig_dist, max(orig_value, value)));
                }
                continue;
            }
            ans[i][node] = Some((dist, value));
            for next_node in 0..n {
                if s[node][next_node] == 'Y' {
                    queue.push_back((dist+1, Some(node), next_node));
                }
            }
        }
    }
    for &(u, v) in &queries {
        match ans[u][v] {
            Some((dist, value)) => {
                println!("{} {}", dist, value);
            },
            None => {
                println!("Impossible");
            },
        }
    }
}
```
## [F - Guess The Number 2](https://atcoder.jp/contests/abc286/tasks/abc286_f)
インタラクティブ問題で$N$の値を求める。
下の図のように$l$個の値(図では$4$と$2$)でサイクルができるように$A$を構築すると一番最初の値(緑枠)が$N=0$のときとの差が$N$を$l$で割った際の余りと同じ値になる。
![f1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3083981/63088ae3-be6e-a9ec-aabd-6ff33f014463.png)
小さい数の組み合わせで大きな数を調べたいときは$2$のべき乗を利用したくなるが、今回は意味がないので中国余剰定理を使用する。
中国余剰定理は平たく説明すると、整数$S$と互いな素な整数$x_i$($1 \le i \le T$)に対し、
```math
Y \equiv S \, \mathrm{mod} \, \prod_{i=1}^{T} x_i
```
を満たす整数$Y$は一意に定まるというもの。
これを利用して$N \le 10^9 \le \prod_{i=1}^T x_i$かつ、$\sum_{i=1}^{T} x_i \le M$を満たす$x_i$を見つける。
小さい方から素数をカウントしていくと$\prod_{i=1}^T x_i$は$10^9$未満になるので、$2$と$3$の代わりに$4$と$9$を入れる。

ここから答えを求める。
$ i \ne j$となる$x_i$、$x_j$に対して
```math
y_i \equiv S \, \mathrm{mod} \, x_i \\
y_j \equiv S \, \mathrm{mod} \, x_j
```
となる$S$を求めるには$0 \le k \le j$に対して
```math
(x_i * k + y_i) % x_j = y_j
```
となる$k$を求める。
これをすべての$x_i$に対して行うと答えが求まる。
```Rust
use proconio::input;
use proconio::source::line::LineSource;
use std::io::{self, BufReader, stdin};


const MAXM: usize = 110;

fn main() {
    let mut source = LineSource::new(BufReader::new(stdin()));
    let mut is_prime = vec![true; MAXM+1];
    is_prime[0] = false;
    is_prime[1] = false;
    let mut primes = vec![4, 9];
    for i in 0..=MAXM {
        if !is_prime[i] {
            continue;
        }
        if 3 < i {
            primes.push(i);
        }
        let mut j = i+i;
        while j <= MAXM {
            is_prime[j] = false;
            j += i;
        }
    }
    let mut a = vec![];
    let mut i = 0usize;
    let mut index  = 0usize;
    let mut prime_references = vec![];
    while index + primes[i] < MAXM {
        prime_references.push((primes[i], index));
        for j in 0..primes[i]-1 {
            a.push(index+j+2);
        }
        a.push(index+1);
        index += primes[i];
        i += 1;
    }
    let m = a.len();
    println!("{}", m);
    println!("{}", a.iter().map(|&x| x.to_string()).collect::<Vec<_>>().join(" "));
    input! {
        from &mut source,
        b: [usize; m],
    }
    let mut product = 1usize;
    let mut m = 0usize;
    for &(p, start) in &prime_references {
        let m1 = m;
        let m2 = (b[start]+p-start-1) % p;
        for j in 0..p {
            if (product * j + m1) % p == m2 {
                m = product * j + m1;
            }
        }
        product *= p;
    }
    println!("{}", m);
}
```

## [G - Unique Walk](https://atcoder.jp/contests/abc286/tasks/abc286_g)
グラフの中で特定の辺を1回だけ通るウォークがあるか判定する問題。
まず、$x$に含まれていない辺は自由に通っても通らなくてもいいので$x$に含まれない辺だけで行き来できる頂点のグループは自由に行き来できる。
次に$x$に含まれる辺を1度だけ通るということは、その辺の両端の頂点は
* ウォークの始点
* ウォークの終点
* ほかの$x$に含まれる辺の両端の頂点から$x$に含まれない辺のみを$0$回以上通って到達できる頂点

のどれかになる。また、最後の場合同じ頂点から2つ以上の他の頂点に行ってはならない。
以上を踏まえると、$x$の両端の頂点は最後の場合の条件を満たす相方を、最後に相方のいない頂点が2つ以下になるようにできるか調べればよい。最後に相方のいない頂点が2つのときウォークの両端は異なっていて、すべての頂点に相方がいる場合はウォークの始点と終点は同じになっている。
相方の調べ方は、
1. UnionFindを使用して$x$に含まれない辺のみで行き来できる頂点のグループを作り
1. $x$の辺の両端の頂点がどのグループに属するか調べ、
1. 同じグループの頂点が既にあれば相方としてSetから削除し、同じグループの頂点がなければSetに加える

以上の結果としてSetに存在するグループの数が2以下であればこのようなウォークは存在し、3以上であればこのようなウォークは存在しない。
```Rust
use proconio::input;
use proconio::marker::Usize1;
use std::collections::HashSet;


struct UnionFind {
    roots: Vec<i64>,
}

impl UnionFind {
    fn new(n: usize) -> Self {
        UnionFind {
            roots: vec![-1; n],
        }
    }

    fn root(&mut self, x: usize) -> usize {
        if self.roots[x] < 0 {
            return x;
        } else {
            self.roots[x] = self.root(self.roots[x] as usize) as i64;
            return self.roots[x] as usize;
        }
    }

    fn is_same(&mut self, x: usize, y: usize) -> bool {
        self.root(x) == self.root(y)
    }

    fn size(&mut self, x: usize) -> usize {
        let root_x = self.root(x);
        (-self.roots[root_x]) as usize
    }

    fn unite(&mut self, x: usize, y: usize) -> bool {
        if self.is_same(x, y) {
            false
        } else {
            let mut root_x = self.root(x);
            let mut root_y = self.root(y);
            if self.size(root_x) < self.size(root_y) {
                std::mem::swap(&mut root_x, &mut root_y);
            }
            self.roots[root_x] -= (self.size(root_y)) as i64;
            self.roots[root_y] = root_x as i64;
            true
        }
    }
}

fn main() {
    input! {
        n: usize,
        m: usize,
        edges: [(Usize1, Usize1); m],
        k: usize,
        x: [Usize1; k],
    }
    let mut x_set = HashSet::new();
    for &xi in &x {
        x_set.insert(xi);
    }
    let mut uf = UnionFind::new(n);
    for i in 0..m {
        if !x_set.contains(&i) {
            let (u, v) = edges[i];
            uf.unite(u, v);
        }
    }
    let mut groups = HashSet::new();
    for &xi in &x {
        let (u, v) = edges[xi];
        let roots = vec![uf.root(u), uf.root(v)];
        for &root in &roots {
            if !groups.insert(root) {
                groups.remove(&root);
            }
        }
    }
    if groups.len() <= 2 {
        println!("Yes");
    } else {
        println!("No");
    }
}
```