【Rust】ABC426まとめ（A~D）

AtCoder Beginner Contest 426

バーチャル参加し、ABCD4完（79分1ペナ）でした。
今回はA~Dをまとめていきます。

A - OS Versions

$X$と$Y$が同じバージョンであるか、または$X$の方が$Y$よりも新しいバージョンである必要があります。
各バージョンが辞書順に新しいというわけでもないので、丁寧に場合分けするのがシンプルでしょう。

以下の組み合わせの時、Yesを出力することでこの問題に正解することができます。

$X$	$Y$
Lynx	Lynx
Lynx	Serval
Lynx	Ocelot
Serval	Serval
Serval	Ocelot
Ocelot	Ocelot

use proconio::input;

fn main() {
    input! {
        x: String,
        y: String,
    }

    if x == "Lynx" || (x == "Serval" && (y == "Serval" || y == "Ocelot")) || (x == "Ocelot" && y == "Ocelot") {
        println!("Yes");
    } else {
        println!("No");
    }
    
}

B - The Odd One Out

問題文より、1回しか出現しない文字は1種類しかありません。
したがってアルファベット26文字の出現回数を調べ、1回しか出現しなかった文字を出力するだけでこの問題を解くことができます。

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

fn main() {
    input! {
        s: Chars,
    }
    
    let mut arr = vec![0; 26];
    for i in 0..26 {
        let c = (b'a' + i as u8) as char;
        for ch in &s {
            if *ch == c {
                arr[i] += 1;
            }
        }
        if arr[i] == 1 {
            println!("{}", c);
            return;
        }
    }
}

C - Upgrade Required

一番シンプルなのは、各位置のPCを配列で管理して、クエリごとにPCを一台ずつ更新するという方法ですが、この場合：

1. バージョンが$X$であるようなPCを探す
2. バージョンが$X$であるPCのバージョンを$Y$に変更する

という二つの処理が必要となりますが、どちらも一つずつ探索して処理するという点で、原理的に$O(NQ)$よりも早くすることはできません。
なお、遅延セグメント木というデータ構造を使うことである程度高速に解くことができますが、今回はそれを使わない解法を紹介します。

ここで、クエリによってどういった変化が起こるのか詳細に見てみましょう。
まず、クエリ$(X,Y)$を行う時、クエリ前に$X$以下のバージョンのPCが$k$個あったとすると、クエリ後に$X$以下バージョンのPCは0台となり、$Y$バージョンのPCはちょうど$k$台増えます。※以下図を参照

▼クエリ$(X,Y)$操作の図示

また、クエリごとに出力を求められているのはアップグレードを適用したPCの台数$k$だけであり、どの位置のPCをアップグレードしたかは今回考える必要がありません。
つまり、各バージョンのPCの台数管理をしておき、高速に$X$以下のバージョンのPC台数さえ求められればこの問題を解くことができます。

では、高速に各クエリで$X$以下のバージョンのPC台数を求める手段を考えましょう。
一つ考えられるのが累積和を使う方法です。
確かに、一番最初のクエリについては事前の累積配列$\text{sum}$を利用して、$\text{sum}[X]$で$X$以下のバージョンのPC台数を求めることができますが、各バージョンのPC台数は動的に変化するため、都度累積和の区間更新が必要となり今回の要件には適しません。

ここで、クエリ$(X,Y)$操作を行った後、$X$以下のバージョンのPC台数は0台となり、今後増える見込みがないことに着目しましょう。
つまり、次に$X'>X$であるようなクエリ$(X',Y')$が来た時には、$X$以下のバージョンを無視して、バージョン$X+1, X+2, \cdots , X'$の合計値を計算することにしても支障はないということです。
これは尺取法と呼ばれるアルゴリズムですが、各バージョンは必ず1回までしか合計値の計算に利用されなくなるためとても効果的にパフォーマンスを改善することができます。

以上、バージョンごとのPC台数管理と尺取法の応用によってこの問題の全体計算量が$O(N+Q)$となり、十分高速にこの問題を解くことができました。

use itertools::Itertools;
use proconio::input;

fn main() {
    input! {
        n: usize,
        q: usize,
        pc: [(usize, usize); q],
    }

    let mut cnt = vec![1; n];
    let mut min = 0;
    let mut ans = vec![];
    for i in 0..q {
        let (mut x, mut y) = pc[i];
        (x, y) = (x - 1, y - 1);
        let mut sum = 0;
        for j in min..=x {
            sum += cnt[j];
            cnt[j] = 0;
        }
        min = (x + 1).max(min);
        cnt[y] += sum;
        ans.push(sum);
    }

    println!("{}", ans.iter().join("\n"));
}

D - Pop and Insert

この問題はアドホックな難問で考察にとても時間を要しました。
また、厳密な証明ができているわけではないので、考察プロセスの開示に留めておきます（もし間違っていたらすみません）。

ある文字列$S$が与えられた時、0(または1)に揃えるための操作回数の最小値の下界は1(または0)の個数、上界は$2N$で抑えることができると考えました。
上界の制約については、どんな文字列であっても端から0(1)に揃えて真ん中に持っていき、0(1)の塊をどんどん大きくすることができるためです。

▼上界が$2N$で抑えられることのイメージ

ここで重要なのは、最初から0か1が塊になっているところに挿入した方が操作回数が明らかに減るということです。直感的には0(1)が連続する最長区間を選択するのがよかろうと思ったのですが、厳密な証明ができなかったのでやめました。
また、全ての0(1)の連続区間に対して、そこに0(1)を集約したときの操作回数を全探索しても計算量的に問題なさそうだったので、こちらの方法でこの問題を解きました。

集約先となる塊の位置さえ決まってしまえば、操作回数の最小値を求めるのは簡単です。
前提として、集約先の塊が0の連続区間だとして説明しますが、1の時でも同じです。
まず、当然ですが元々塊に含まれる0は操作の対象ではありません。
次に、連続していない部分の0については一度端っこで反転させてから再度真ん中に挿入するという2回の操作が必要となります。
さらに、1についてはそのまま真ん中に挿入すれば自動で0になってくれるので1回の操作で十分です。

以上の計算は各塊について$O(1)$で行うことができるので、全体計算量としては$O(N)$となり十分高速にこの問題を解くことができました。
※0101010101010のように、01が交互に出現するような文字列の場合、最悪計算量となります。

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

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

    let mut ans = vec![];
    for _ in 0..t {
        input! {
            n: usize,
            s: Bytes,
        }

        let mut rle = vec![];
        for i in 0..n {
            if i == 0 || s[i] != s[i - 1] {
                rle.push((s[i], 1));
            } else {
                rle.last_mut().unwrap().1 += 1;
            }
        }
        
        let mut min = usize::MAX;
        let ones = s.iter().filter(|&&c| c == b'1').count();
        let zeros = s.iter().filter(|&&c| c == b'0').count();
        for i in 0..rle.len() {
            if rle[i].0 == b'1' {
                min = min.min(zeros + (ones - rle[i].1) * 2);
            } else {
                min = min.min(ones + (zeros - rle[i].1) * 2);
            }
        }
        ans.push(min);
    }
    println!("{}", ans.iter().join("\n"));
}

まとめ

今回はアドホックよりの問題が多く考察が大変でした。
次回はデータベーススペシャリストの試験が翌日に控えていることもあり後日バーチャル参加とします。