【Rust】ABC430感想（A~E）

AtCoder Beginner Contest 430

後日バーチャル参加してA~Cの3完でした。
今回はA~Eの感想を書きます。

A - Candy Cookie Law

飴を$A$個以上持っていて、かつクッキーを$B$個未満しか持っていない時にYes、それ以外のときNoを出力すればよいですね。

use proconio::input;

fn main() {
    input! {
        a: usize,
        b: usize,
        c: usize,
        d: usize,
    }

    if c >= a && d < b {
        println!("Yes");
    }else {
        println!("No");
    }
}

B - Count Subgrid

正方形領域を文字列として認識し、ハッシュセットに格納した個数を数えればよいです。
Rustは部分文字列の結合の仕方に癖があるのでなかなか速く書けないです。

use proconio::input;
use proconio::marker::Chars;
use std::collections::HashSet;

fn main() {
    input! {
        n: usize,
        m: usize,
        s: [Chars; n],
    }

    let mut set = HashSet::new();
    for i in 0..=n-m {
        for j in 0..=n-m {
            let mut str = String::new();
            for k in i..i+m {
                str += &s[k][j..j+m].iter().collect::<String>();
            }
            set.insert(str);
        }
    }

    println!("{}", set.len());
}

C - Truck Driver

左端$l$を右にずらしていくと、区間$[l, r]$内に含まれる文字の個数が一定以上であるようにするためには$r$も右にずらしていく必要があります。
したがって、ここでは尺取法を利用することができそうです。
$A$以上と$B$未満の二つありますが、後者は初めて$B$以上となる位置の一つ手前と考えれば$B$未満であるような右端が求められますね。

考え方自体はそこまで難しくないのですが、インデックスエラーがなかなか取れず、かなりの時間をかけてしまいました。

use proconio::input;
use proconio::marker::Chars;

fn main() {
    input! {
        n: usize,
        a: usize,
        b: usize,
        s: Chars,
    }

    let mut ans = 0;
    let mut r_a = 0;
    let mut r_b = 0;
    let mut cnt_a = 0;
    let mut cnt_b = 0;
    for l in 0..n {
        if l > 0 {
            if s[l - 1] == 'a' {
                cnt_a -= 1;
            } else {
                cnt_b -= 1;
            }
        }

        while r_a < n && cnt_a < a {
            if s[r_a] == 'a' {
                cnt_a += 1;
            }
            r_a += 1;
        }

        while r_b < n && cnt_b < b {
            if s[r_b] == 'b' {
                cnt_b += 1;
            }
            r_b += 1;
        }

        if cnt_a >= a && cnt_b < b {
            ans += n - r_a + 1;
        }else if r_b > r_a{
            ans += r_b - r_a;
        }
    }
    println!("{}", ans);
}

D - Neighbor Distance

新規の人$i$を挿入した時に、既存の人のうち$d$が変化するのは$i$の右隣と左隣だけですね。
したがって、BTreeMapでも用意しておいて、二分探索で高速に右隣と左隣の人の座標を求められるようにすれば、各$i$につき$O(logN)$の計算量しかかからないので全体計算量は$O(NlogN)$となりこの問題を解くことができます。

RustのBTreeMapではlower_bound()もありますが、range()を使わなければならない、というのは初見の私にとって罠でした。

use proconio::input;
use std::collections::BTreeMap;
use itertools::Itertools;

fn main() {
    input! {
        n: usize,
        x: [isize; n],
    }

    let mut a = BTreeMap::new();
    let mut d = vec![isize::MAX; n + 1];
    a.insert(0, n);
    let mut ans_val =0;
    let mut ans = vec![];
    for i in 0..n {
        let v = x[i];
        if let Some((&r_val, &r_idx)) = a.range(v..).next() {
            let next_rd = d[r_idx].min(r_val - v);
            if d[r_idx] != isize::MAX {
                ans_val += next_rd - d[r_idx];
            } else {
                ans_val += r_val - v;
            }
            d[r_idx] = next_rd;
            d[i] = r_val - v;
        }
        if let Some((&l_val, &l_idx)) = a.range(..v).next_back() {
            let next_ld = d[l_idx].min(v - l_val);
            if d[l_idx] != isize::MAX {
                ans_val += next_ld - d[l_idx];
            } else {
                ans_val += v - l_val;
            }
            d[l_idx] = next_ld;
            d[i] = d[i].min(v - l_val);
        }
        ans_val += d[i];
        a.insert(v, i);
        ans.push(ans_val);
    }
    println!("{}", ans.iter().join("\n"));
}

E - Shift String

ローリングハッシュを知っていれば簡単で、$A$の二倍化して左端と右端を一つずつ右にずらしていき$B$と一致する箇所があるかどうかを調べれば良いだけです。
コンテスト後、人から借りたライブラリで難なくAC。

use itertools::Itertools;
use proconio::input;
use proconio::marker::Chars;

fn main() {
    input! {
        t: usize,
    }

    let mut ans: Vec<isize> = vec![];
    for tc in 0..t {
        input! {
            a: Chars,
            b: Chars,
        }
        let n = a.len();
        let chained_a: Vec<char> = a.iter().cloned().chain(a.iter().cloned()).collect();
        let a_hash_table: RHash<BASE, HASH> = chained_a.iter().map(|&c| c as u32).collect();
        let b_hash_table: RHash<BASE, HASH> = b.iter().map(|&c| c as u32).collect();
        for i in 0..n {
            if ans.len() == tc + 1 {
                break;
            }
            let a_hash = a_hash_table.range_hash(i..i + n);
            let b_hash = b_hash_table.range_hash(0..n);
            if a_hash == b_hash {
                ans.push(i as isize);
            } else if i == n - 1 {
                ans.push(-1);
            }
        }
    }
    println!("{}", ans.iter().join("\n"));
}

まとめ

C問題は灰色かと思いましたが意外とみなさん苦労されていたようで、遅解き3完でも緑パフォが出て驚きました。
最近DSUやBIT、SegTree等のライブラリを使って問題を解いてみました。
整数周り（Combinationやゼータメビウス関数など）のライブラリも使いこなせるようにならないと厳しいですが、レート維持には現状でも十分でしょうか。
引き続き、JavaScript時代の力を取り戻せるようにがんばります。