RustでABC285復習

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

# 復習
## [A - Edge Checker 2](https://atcoder.jp/contests/abc285/tasks/abc285_a)
二つのノード(点)が親子かを答える問題。
親ノードを$p$、子ノードを$c$とすると
```math
c = \left \{
\begin{array}{}
2p \\
2p+1
\end{array}
\right.
```
となっている。
また、$a \lt b$より結ばれているなら$a$が親になるため、
```math
b / 2 == a
```
なら結ばれていて、そうでなければ結ばれていないと判断できる。
```Rust
use proconio::input;


fn main() {
    input! {
        a: usize,
        b: usize,
    }
    if b / 2 == a {
        println!("Yes");
    } else {
        println!("No");
    }
}
```
## [B - Longest Uncommon Prefix](https://atcoder.jp/contests/abc285/tasks/abc285_b)
問題の意味が分からないので書いてある通りに愚直に実装する。
全探索して$S_k == S_{k+1}$なら打ち切る。
```Rust
use proconio::input;
use proconio::marker::Chars;


fn main() {
    input! {
        n: usize,
        s: Chars,
    }
    for i in 1..n {
        let mut l = 0usize;
        while l + i < n {
            if s[l] == s[l+i] {
                break;
            }
            l += 1;
        }
        println!("{}", l);
    }
}

```
## [C - abc285_brutmhyhiizp](https://atcoder.jp/contests/abc285/tasks/abc285_c)
文字列が辞書順で何番目になるかを答える問題。
26進数になっていることに気づけば解ける。
注意点としてはAは0でなく1、Zは25ではなく26になっている。
```Rust
use proconio::input;
use proconio::marker::Chars;


fn main() {
    input! {
        s: Chars,
    }
    let mut ans = 0u64;
    for &si in &s {
        let v = (si as u8 - 'A' as u8) as u64 + 1;
        ans = 26 * ans + v;
    }
    println!("{}", ans);
}
```
## [D - Change Usernames](https://atcoder.jp/contests/abc285/tasks/abc285_d)
ユーザー名を重複した人がいないように変更する問題。
下の図のようにユーザー名をAからB、BからC、CからDに変更したい人がいた場合、それぞれのユーザー名をグラフの頂点と考えて、変更を辺とみなす。
そうしてできたグラフに閉路がなければ希望通り変更できる。閉路があれば変更できない。もっと正確にはグラフが木に(というより$S_i$と$T_i$は相異なるため直線に)なる場合は根から葉までのルートを逆順にたどることで希望通り変更できる。逆にそうできない場合は変更できない。
なぜならユーザー名をAからBに変更したい場合、現状ユーザー名がBの人がいない必要があるからである。これには下記のどちらかの条件を満たす必要がある($T_i$は相異なるため既にユーザー名をBに変更した人はいない)。
* もともとユーザー名がBの人は既にほかのユーザー名に変更している
* もともとユーザー名がBの人はいない

なのでユーザー名をAからBに変更する場合は既にBだった人のユーザー名は変更されている必要がある。それがつまりグラフを逆順に変更するということである。
![d1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3083981/6ef235c2-9472-f660-7b70-c6fe7432556b.png)
逆に下のようにグラフが閉路を持つ場合、AをBにするには先にBをCに変える必要があり、それにはまずCをAに変えなければならないため先にAをBに変える必要があることになり全体として変更ができなくなる。
![d2.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3083981/199991f6-5b60-cd1b-33a9-8b0ea20d1b30.png)
よって閉路があるかどうかを判定すれば答えが出る。閉路の判定はUnionFindを使うとできる。
```Rust
use proconio::input;
use std::collections::{HashSet, HashMap};


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,
        transitions: [(String, String); n],
    }
    let mut id_set = HashSet::new();
    for (s, t) in &transitions {
        id_set.insert(s);
        id_set.insert(t);
    }
    let ids = id_set.iter().collect::<Vec<_>>();
    let mut id_map = HashMap::new();
    for i in 0..ids.len() {
        id_map.insert(ids[i], i);
    }
    let mut uf = UnionFind::new(ids.len());
    for (s, t) in &transitions {
        if !uf.unite(id_map[&s], id_map[&t]) {
            println!("No");
            return;
        }
    }
    println!("Yes");
}
```
## [E - Work or Rest](https://atcoder.jp/contests/abc285/tasks/abc285_e)
休日を1日以上配置して1週間の生産量を最大化する問題。
動的計画法を使って求める。
$dp[i][j]$を$i$日目(曜日$i$)が最後の休日から$j$連勤している場合の生産量の最大値とおく。ここで$j$連勤の間の生産量はカウントしないものとする。そして、存在しない遷移を防ぐため$dp$の初期値は全て$None$にしておく。
また、少なくとも1日は休日を入れないといけないことから$1$日目は休日とする。この制約上仮に$k$日目を休日にするのが最善だとしても全体を$k-1$日分前にシフトすると$1$日目を休日にした場合と同じ結果になるため$1$日目を休日にしても一般性を失わない。
以上から1日目は休日にしたので
```math
dp[0][i] = \left\{
\begin{array}{}
Some(0) \qquad (i = 0) \\
None \qquad (0 < i)
\end{array}
\right.
```
となる。(0-indexedに注意)
$dp$は$dp[i][j]$から$i+1$日目を平日にするか休日にするかで$dp[i+1][j+1]$と$dp[i+1][0]$に遷移する。
![e1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3083981/253bab50-2ac2-26c5-c73f-0da004e40970.png)
この遷移で$dp[i+1][j+1]$への遷移では値は更新せず、$dp[i+1][0]$への遷移でだけ更新する。
このときに$j$連勤分の生産量($mergin[j]$)は
```math
mergin[j] = \left \{
\begin{array}{}
a_{k+1} + 2\sum_{i=1}^{k} a_i \qquad (j = 2k+1)\\
2\sum_{i=1}^{k} a_i \qquad (j = 2k)
\end{array}
\right.
```
となるので、
```math
dp[i+1][0] = Some(dp[i][j].unwrap() + mergin[j])
```
と更新される。
![e2.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3083981/20d76340-729b-6fc7-5841-2cbdddb7a264.png)
最後に$dp[n-1][j]$に対して最後の$j$連勤分の生産量を加算して最大値を取ると答えが求まる。
```Rust
use proconio::input;
use std::cmp::max;


fn main() {
    input! {
        n: usize,
        a: [u64; n],
    }
    let mut mergin = vec![0u64; n+1];
    for i in 1..n {
        mergin[i] = mergin[i-1] + a[(i-1)/2];
    }
    let mut dp = vec![vec![None; n]; n];
    dp[0][0] = Some(0u64);
    for i in 0..n-1 {
        for j in 0..n {
            if dp[i][j] == None {
                continue;
            }
            let v = dp[i][j].unwrap();
            dp[i+1][0] = Some(match dp[i+1][0] {
                Some(d) => max(d, v+mergin[j]),
                None => v,
            });
            if j + 1 == n {
                continue;
            }
            dp[i+1][j+1] = Some(match dp[i+1][j+1] {
                Some(d) => max(d, v),
                None => v,
            });
        }
    }
    let mut ans = 0u64;
    for i in 0..n {
        if let Some(v) = dp[n-1][i] {
            ans = max(ans, v+mergin[i]);
        }
    }
    println!("{}", ans);
}
```
## [F - Substring of Sorted String](https://atcoder.jp/contests/abc285/tasks/abc285_f)
クエリを処理し、文字列の特定の場所の文字を変更したり、特定の部分文字列がソートされた状態の文字列$S$の部分文字列になっているかを判定する問題。
まずソートされた文字列$S$の部分文字列がどのようなものかを考える。
ソートされた文字列は下の図のようにaから辞書順に同じ文字が全て連続した文字列になる。
![f1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3083981/07940257-8e43-9644-7247-8fc9d7016296.png)
そして、ソートされた文字列の部分文字列は最初と最後の文字こそ全て出ているわけではないが、残りの文字は全て出ている。
なので、問題のクエリの2種類目で求められる$l$から$r$までの文字列がソートされた文字列の部分文字列であるというのは、辞書順で$l$番目と$r$番目の間にある文字と同じ文字が全て辞書順に並んでいる文字列になる。
![f2.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3083981/211ea5ea-020f-0400-ee84-22d4a18e0072.png)
この管理はそれぞれがaからzに対応した26個のセグメント木で行う。
具体的には$st[i].query(l, r)$を実行すると$[l, r)$の区間に$i$番目の文字(アルファベットの辞書順で$i$番目、aは$0$でzが$25$)いくつあるかを求められるようにしておく。これは最初と1種類目のクエリで適宜更新する。
2種類目のクエリの処理は、$0$(a)から順に$[l,r]$に文字がないかを確認していき、最初に$0 \lt st[i].query(l, r+1)$となる$i$を探す。
$length_j$を$[l, r]$に含まれる$j$の数と置くと、$[l, r]$がソートされた$S$の部分文字列である場合、
```math
st[i].query(l, r+1) = st[i].query(l, l+length_i)
```
となっている必要があり、
```math
offset = l + \sum_{i=0}^{k-1} length_i \\
```
と置くと、
```math
st[k].query(l, r+1) = st[k].query(l+offset, l+offset+length_k)
```
となっている必要があり、$r$番目の文字までの文字に対しては以下が成り立つ。
```math
st[k].query(l, r+1) = st[k].query(l+offset, l+offset+length_k) = st[k].query(0, n)
```
以上を判断することでこの問題を解くことができる。
```Rust
use proconio::input;
use proconio::marker::{Chars, Usize1};


#[derive(Clone)]
struct SegmentTree {
    n: usize,
    data: Vec<usize>,
}

impl SegmentTree {
    fn new(n: usize) -> Self {
        let mut i = 1;
        while i < n {
            i *= 2;
        }
        SegmentTree {
            n: i,
            data: vec![0; 2*i-1],
        }
    }

    fn add(&mut self, index: usize, value: usize) {
        let mut index = self.n + index - 1;
        self.data[index] += value;
        while 0 < index {
            index = (index - 1) / 2;
            self.data[index] = self.data[2*index+1] + self.data[2*index+2];
        }
    }

    fn sub(&mut self, index: usize, value: usize) {
        let mut index = self.n + index - 1;
        self.data[index] -= value;
        while 0 < index {
            index = (index - 1) / 2;
            self.data[index] = self.data[2*index+1] + self.data[2*index+2];
        }
    }

    fn _query(&mut self, index: usize, l: usize, r: usize, left: usize, right: usize) -> usize {
        if r <= left || right <= l {
            return 0;
        } else if l <= left && right <= r {
            return self.data[index];
        } else {
            let mid = (left + right) / 2;
            return self._query(2*index+1, l, r, left, mid)
                + self._query(2*index+2, l, r, mid, right);
        }

    }

    fn query(&mut self, l: usize, r: usize) -> usize {
        return self._query(0, l, r, 0, self.n);
    }
}


fn main() {
    input! {
        n: usize,
        s: Chars,
        q: usize,
    }
    let mut s = s.iter().map(|&si| (si as u8 - 'a' as u8) as usize).collect::<Vec<_>>();
    let mut st = vec![SegmentTree::new(n); 26];
    for i in 0..n {
        st[s[i]].add(i, 1);
    }
    for _ in 0..q {
        input! {
            t: u64,
        }
        match t {
            1 => {
                input! {
                    x: Usize1,
                    c: char,
                }
                let v = (c as u8 - 'a' as u8) as usize;
                st[s[x]].sub(x, 1);
                st[v].add(x, 1);
                s[x] = v;
            },
            2 => {
                input! {
                    l: Usize1,
                    r: Usize1,
                }
                let mut num = r - l + 1;
                let mut i = 0usize;
                let mut is_valid = true;
                while st[i].query(l, r+1) == 0 {
                    i += 1;
                }
                let length = st[i].query(l, r+1);
                let mut start = l + length;
                if st[i].query(l, start) != length {
                    is_valid = false;
                }
                num -= length;
                i += 1;
                while 0 < num {
                    let length = st[i].query(l, r+1);
                    if st[i].query(start, start+length) != length {
                        is_valid = false;
                    }
                    start += length;
                    num -= length;
                    if st[i].query(l, r+1) != st[i].query(0, n) {
                        break;
                    }
                    i += 1;
                }
                if num == 0 && is_valid {
                    println!("Yes");
                } else {
                    println!("No");
                }
            },
            _ => unreachable!(),
        }
    }
}
```
## [G - Tatami](https://atcoder.jp/contests/abc285/tasks/abc285_g)
現在復習中