ABC380

ABC380、出先だったのでUnratedで参加していました。A-Eの5完できて嬉しい✌️

A - 123233

文字列として受け取ってソートした結果が 122333 と一致するかどうかを判定するのが早いと思います。ソートした結果を判定するのはA, B問題でよくみる気がする。
提出

n = list(input())
a = ''.join(sorted(n))

if a == "122333":
    print("Yes")
else:
    print("No")

B - Hurdle Parsing

| で始まるのがちょっと厄介ですが、(0-indexedの)i=1から始めて | が来るまでの - の個数を愚直に数えました。
提出

s = input()
a = []
cnt = 0

for i in range(1, len(s)):
    if s[i] == '-':
        cnt += 1
    else:
        a.append(cnt)
        cnt = 0
        
print(*a)

ところで、Pythonの配列の出力で print(*a) とすると空白区切りになるというの、競技プログラミング以外での使い道があんまりない気がするのですがなんなのでしょうか。

C - Move Segment

難読問題文シリーズ、辛いです。情報を文字 \(c\) が何個ある、というように圧縮します。例えば、入力例1の 010011100011001 であれば [(0, 1), (1, 1), (0, 2), (1, 3), (0, 3), (1, 2), (0, 2), (1, 1)] というように圧縮していくことを考えます。
\(K\) 番目の1の塊の個数を数えたら、それを圧縮済み配列に加えるのではなく、代わりに \(K-1\) 番目の1の塊の個数を増やすことで問題文の操作をしたことにします。これで圧縮した配列を解凍していけば答えが得られます。落ち着いて整理すると簡単ですが、焦ると実装が途端に汚くなる...
デバッグ出力を消し忘れて1ペナ喰らったので、そろそろ提出時にデバッグ出力をしないようにATCODER=1の環境下では動かないデバッグ関数を自作しようと思います。
提出

use proconio::{input, marker::Chars};
fn main() {
    input! {
        _n: usize,
        k: usize,
        s: Chars,
    }

    let mut ans = vec![];
    let mut prev = '_';
    let mut cnt = 0u64;
    let mut idx = 0; // memo
    let mut memo = 0;
    for &c in s.iter() {
        if c == prev {
            cnt += 1;
        } else {
            ans.push((prev, cnt));
            if prev == '1' {
                idx += 1;
                if idx == k - 1 {
                    memo = ans.len() - 1;
                } else if idx == k {
                    ans.pop();
                    ans[memo].1 += cnt;
                }
            }
            cnt = 1;
            prev = c;
        }
    }
    ans.push((prev, cnt));
    if prev == '1' {
        idx += 1;
        if idx == k {
            ans.pop();
            ans[memo].1 += cnt;
        }
    }
    for (c, i) in ans.iter() {
        for _ in 0..*i {
            print!("{}", c);
        }
    }
    println!();
}

D - Strange Mirroring

\(i\) 回操作をして得られた文字列を \(S^{(i)}\) と書きます。また、 \(\text{inv}(S)\) を \(S\) の大文字と小文字を反転させた文字列として定義すると、 \(S^{(i)} = S^{(i-1)} + \text{inv}(S^{(i-1)})\) です。なお、 \(S^{(0)} = S\) です。
さて、問題は次のように言い換えられます: 「正整数 \(x\) が与えられる。 \(x \leq |S^{(i)}|\) を満たす最小の \(i\) について、 \(S^{(i)}\) の \(x\) 番目の文字はなんですか？」。
\(S^{(i)}\) の \(x\) 番目の文字は \(x \leq |S^{(i-1)}|\) なら \(S^{(i-1)}\) の \(x\) 番目の文字と同じであり、そうでないなら \(S^{(i-1)}\) の \(x - |S^{(i-1)}|\) 番目の文字の大文字小文字を反転させたものです。
以上を再帰関数で実装すると、 \(i\) は \(|S|^i \leq x\) を満たす最小の値でありこれが \(\log{x}\) となるので、クエリあたり \(O(\log(x))\) 、全体で \(O(Q\log(x))\) でこの問題が解けます。提出

use itertools::Itertools;
use proconio::{
    input,
    marker::{Chars, Usize1},
};

fn inv(c: char) -> char {
    if b'a' <= c as u8 {
        (b'A' + (c as u8 - b'a')) as char
    } else {
        (b'a' + (c as u8 - b'A')) as char
    }
}

fn dfs(s: &Vec<char>, q: usize, len: usize) -> char {
    if len == s.len() {
        return s[q];
    }

    return if q < len / 2 {
        dfs(s, q, len / 2)
    } else {
        inv(dfs(s, q - len / 2, len / 2))
    };
}

fn main() {
    input! {
        s: Chars,
        q: usize,
        k: [Usize1; q],
    }

    let mut ans = vec![];
    for &x in k.iter() {
        let mut len = s.len();
        while len <= x {
            len *= 2;
        }
        ans.push(dfs(&s, x, len));
    }
    println!("{}", ans.iter().join(" "));
}

以前にちょっと難しい似たような問題を見たことを思い出して、そこから一気に解けました。まあ最初は誤読してたので何ともではあるんですが...

E - 1D Bucket Tool

「隣接するマスの色を全て塗り替える」という操作が重いのでこれを高速化することを考えます。とは言ってもこれを高速化するのは簡単で、隣接するマスで同じ色になった場合はそれ以降に違う色同士になることはあり得ないので、UnionFindで隣接を表現すれば良いです。また、隣接するということは連続であるということなので、連結な成分ごとに「そのグループに含まれる頂点番号の最大と最小」を保持しながらグループの色を管理することで解くことができます。提出
途中まで「隣接する同じ色のマスは塗り替えて、さらにその横の色も変える」だと勘違いしていて無駄に実装量を増やしてしまい、時間を喰ってしまいました。また、同一グループに含まれる頂点の最小の値を取り出すべきなのに最大の値を取り出してしまっていた(しかもサンプルが通ってかなりのケースでACできる)ため１ペナしてしまいもったいなかったです。　

use ac_library::{dsu, Dsu};
use itertools::Itertools;
use proconio::{input, marker::Usize1};
fn main() {
    input! {
        n: usize,
        q: usize,
    }

    let mut uf = Dsu::new(n);
    let mut color = (0..n).collect_vec();
    let mut r = (0..n).map(|i| (i, i)).collect_vec();
    let mut ans = vec![1; n];

    for _ in 0..q {
        input! {
            t: u8,
        }
        match t {
            1 => {
                input! {
                    x: Usize1,
                    c: Usize1,
                }

                ans[color[uf.leader(x)]] -= uf.size(x);
                ans[c] += uf.size(x);
                color[uf.leader(x)] = c;

                // 右へ
                let mut right = r[uf.leader(x)].1;
                let mut left = r[uf.leader(x)].0;

                while right + 1 < n && color[uf.leader(right + 1)] == c {
                    let max_r = r[uf.leader(right + 1)].1;

                    uf.merge(right, right + 1);
                    right = max_r;
                    r[uf.leader(x)] = (left, right);
                }

                while left >= 1 && color[uf.leader(left - 1)] == c {
                    let max_l = r[uf.leader(left - 1)].0;
                    uf.merge(left, left - 1);
                    left = max_l;
                    r[uf.leader(x)] = (left, right);
                }
            }
            2 => {
                input! {
                    c: Usize1,
                }
                println!("{}", ans[c]);
            }
            _ => {
                unreachable!()
            }
        }
    }
}

UnionFindにデータを載せられるようにしていて、これを使えばもっと綺麗に実装できましたね。こういうのを楽に実装するために用意してるんだから使って解いてくれ？

use cps::unionfind::UnionFind;
use itertools::Itertools;
use proconio::{input, marker::Usize1};
use std::iter::repeat;
fn main() {
    input! {
        n: usize,
        q: usize,
    }

    let merge = |x: &(usize, usize), y: &(usize, usize)| -> (usize, usize) {
        (x.0.min(y.0), (x.1.max(y.1)))
    };
    let mut uf = UnionFind::new(n, merge);
    let mut color = (0..n).collect_vec();
    let mut ans = repeat(1).take(n).collect_vec();
    for i in 0..n {
        uf.insert_data(i, (i, i));
    }

    for _ in 0..q {
        input! {
            t: u8,
        }
        match t {
            1 => {
                input! {
                    x: Usize1,
                    c: Usize1,
                }
                ans[color[uf.leader(x)]] -= uf.size(x);
                ans[c] += uf.size(x);
                color[uf.leader(x)] = c;
                loop {
                    let left = uf.get_data(x).unwrap().0;
                    if left == 0 || color[uf.leader(left - 1)] != c {
                        break;
                    }
                    uf.merge(x, left - 1);
                }
                loop {
                    let right = uf.get_data(x).unwrap().1;
                    if right == n - 1 || color[uf.leader(right + 1)] != c {
                        break;
                    }
                    uf.merge(x, right + 1);
                }
            }
            2 => {
                input! {
                    c: Usize1,
                }
                println!("{}", ans[c]);
            }
            _ => unreachable!(),
        }
    }
}

勝ち回ではあるんですが、振り返ってみると誤読による時間の消費や注意力不足によるペナなどが結構多くて勿体無い回でもありました。とはいえ、このセットで20分残して5完できたというのは個人的にはかなり成長を感じます。なおUnrated...

逃した水perfは大きい

A - 123233

B - Hurdle Parsing

C - Move Segment

D - Strange Mirroring

E - 1D Bucket Tool