ABC381

全体的に辛い回でした。そもそも早ときするタイプではないのですが、にしても全部の問題で時間をかけてしまっていて反省しないとなぁという気持ちです。

A - 11/22 String

まず、文字列に含まれる / が1つしかないことを確認して、そこで分割します。このとき / が1つではない場合はNoが答えです。
そうでないとき、分割した前がすべて1, 後ろがすべて2, 前後の長さが同じであれば11/22文字列なので、これを確認すればよいです。
提出

use itertools::Itertools;
use proconio::input;
fn main() {
    input!{
        n: usize,
        s: String,
    }

    let sv = s.split("/").collect_vec();
    if sv.len() != 2 || s.chars().filter(|c| *c == '/').count() != 1 {
        println!("No");
        return;
    }

    let a = sv[0].to_string();
    let b = sv[1].to_string();

    if a.chars().map(|c| if c == '1' { '2' } else { '@' }).eq(b.chars()) {
        println!("Yes");
    } else {
        println!("No");
    }
}

B - 1122 String

ランレングス圧縮して、文字に重複がないことと出現するすべての長さが2になっていることを確認すれば良いです。実装では文字の重複を見ているというよりは出現する文字が全部0 or 2であることを確認しています。
提出

use itertools::Itertools;
use proconio::{input, marker::Chars};
fn main() {
    input!{
        s: Chars,
    }

    let v = s.iter().dedup_by_with_count(|a, b| a == b).collect_vec();

    let v2 = s.iter().fold(vec![0; 26], |mut v, &c| {
        v[c as usize - 'a' as usize] += 1;
        v
    });

    if v2.iter().all(|x| *x == 0 || *x == 2) && 
        v.iter().all(|(cnt, _)| *cnt == 2) {
            println!("Yes");
        } else {
            println!("No");
        }
}

C - 11/22 Substring

ランレングス圧縮して、長さが1の / を全探索します。各 / について、min(一つ前にある 1 の塊の個数, 一つ後ろにある 2 の塊の個数) * 2 + 1が連続な11/22文字列の長さになるので、これのmaxを取れば答えになります。特に、 / が一つでもあればそれが長さ1の11/22文字列になるという罠があります(サンプルで気づきました)。
提出

use cps::chlibs::ChLibs;
use itertools::Itertools;
use proconio::{input, marker::Chars};
fn main() {
    input!{
        _n: usize,
        s: Chars,
    }

    let v = s.iter().dedup_by_with_count(|a, b| a == b).collect_vec();
    let mut ans = 0;

    if v.len() >= 2 {
	    for i in 0..v.len() - 2 {
	        if *v[i].1 == '1' && *v[i+2].1 == '2' && *v[i+1].1 == '/' && v[i+1].0 == 1 {
	            ans.chmax(v[i].0.min(v[i+2].0) * 2 + 1);
	        }
	    }
    }

    if ans == 0 && s.contains(&'/') {
        ans = 1;
    }
    println!("{}", ans);
}

ちなみに、よく問題を読むと与えられる文字列は必ず / を含むので長さ1が解の下界なので最後の / が含まれるかを判定している条件式は問題分を読んでいない証拠です。お前はABC379-Cで何を学んだんだ。それとは関係なく、文字列がすべて / で構成される場合はランレングス圧縮後の長さが1になり、この場合のvalidateを忘れていて1REを出しました。

D - 1122 Substring

大戦犯枠。やることはシンプルな尺取り法なのですが、引っ掛かりポイントにことごとく引っかかって大量のWAを出しました。例えば、 1 1 1 2 2 3 3 3 は長さ6の1122数列である、とか 1 1 2 2 3 3 2 2 のときの更新をミスっていて 3 3 2 2 が1122数列なのに 3 3 まで消してしまう、など。
この問題もランレングス圧縮して解いたのですが、場合分けが多くなりすぎて辛く、2個ずつ伸ばす方針で解いたほうが簡単に解けるみたいです。
提出

use cps::chlibs::ChLibs;
use itertools::Itertools;
use proconio::{input, marker::Usize1};
fn main() {
    input!{
        n: usize,
        a: [Usize1; n],
    }

    let v = a.iter()
        .copied()
        .dedup_by_with_count(|x, y| x == y)
        .collect_vec();

    let mut l = 0;
    let mut r = 0;

    let mut cnt = 0u64;
    let mut seen = vec![false; n];
    let mut ans = 0u64;

    while r < v.len() {
        if v[r].0 == 2 {
            if seen[v[r].1] {
                for i in l..r {
                    if v[i].1 == v[r].1 {
                        l = i + 1;
                        break;
                    } else {
                        seen[v[i].1] = false;
                        cnt -= 1;
                    }
                }
            } else {
                seen[v[r].1] = true;
                cnt += 1;
                ans.chmax(cnt * 2);
            }
            r += 1;
        } else if v[r].0 == 1 {
            for i in l..r {
                seen[v[i].1] = false;
            }
            cnt = 0;
            r += 1;
            l = r;
        } else {
            if !seen[v[r].1] {
                ans.chmax((cnt + 1) * 2);
            }
            for i in l..r {
                seen[v[i].1] = false;
                if v[i].1 == v[r].1 {
                    ans.chmax(cnt * 2);
                } else {
                    cnt -= 1;
                }
            }
            l = r;
            seen[v[r].1] = true;
            cnt = 1;
            r += 1;
        }
    }
    ans.chmax(cnt * 2);
    println!("{ans}");
}

どうにもテストケースが弱かったらしく、Affter contestが20ケース(!?)ありましたがちゃんと通ってました。

E - 11/22 Subsequence (upsolve)

難しい。パット見は左右からの累積個数を持って / 毎の長さを区間maxを取得できるセグ木に載せることで解けそうに見えましたが、この方針だと全然だめです 。
ここで、 \(L\) から \(R\) の区間で長さ \(2m+1\) の11/22文字列を作れるか？という問題を考えます 。これは、 1 , 2 , / の出現位置を持っておくことで以下のように解くことができます。

idx <- l
idx <- idx以上で最小の1のindexから、1だけ数えてm個先のindex
idx <- idx以上で最小の/のindex
idx <- idx以上で最小の2のindexから、2だけ数えてm個先のindex

if idx <= r:
  作成可能
otherwise:
  作成不可能

この判定はidx以上文字のインデックスを見つける部分がボトルネックで、 \(O(\log{N})\) で解くことができます。この部分問題の単調性を利用して答えの二分探索を行うことで、全体で \(O(Q\log^2{N})\) となり高速に解くことができます。
提出

use cps::veclibs::VecLibs;
use proconio::{input, marker::{Chars, Usize1}};

fn to_index(c: char) -> usize {
    match c {
        '/' => 0,
        '1' => 1,
        '2' => 2,
        _ => unreachable!(),
    }
}

fn judge(v: &Vec<Vec<usize>>, m: usize, l: usize, r: usize) -> bool {
    /* 長さ2*m+1の部分文字列があるか */
    let mut idx = l;
    if m != 0 {
        let k = v[to_index('1')].lower_bound(idx);
        if k + m - 1 >= v[to_index('1')].len() {
            return false;
        }
        idx = v[to_index('1')][k + m - 1];
    }

    {
        let k = v[to_index('/')].lower_bound(idx);
        if k >= v[to_index('/')].len() {
            return false;
        }
        idx = v[to_index('/')][k];
    }

    if m != 0 {
        let k = v[to_index('2')].lower_bound(idx);
        if k + m - 1 >= v[to_index('2')].len() {
            return false;
        }
        idx = v[to_index('2')][k + m - 1];
    }

    if idx <= r { true } else { false }
}

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

    let mut v = vec![vec![]; 3];
    for (i, &c) in s.iter().enumerate() {
        v[to_index(c)].push(i);
    }

    for _ in 0..q {
        input! {
            l: Usize1,
            r: Usize1,
        }

        let mut ok = !0;
        let mut ng = r-l+1;

        while ng.wrapping_sub(ok) > 1 {
            let m = ng.wrapping_add(ok) / 2;
            if judge(&v, m, l, r) {
                ok = m;
            } else {
                ng = m;
            }
        }
        if ok == !0 {
            println!("0");
        } else {
            println!("{}", ok * 2 + 1);
        }
    }
}

この手の答えの二分探索は「言われればわかるし解けるけど、言われないとそもそも答えの二分探索をしようと思わない」というところがあって、今回はDに時間がかかっていてそもそも時間がなかったですが時間があっても解けなかったと思います。500点の壁だなぁと思いつつ、これをどうやって越えていくかが難しいところです。

11/22開催の回なので1122にフォーカスした問題がたくさんありましたね。全体的に苦手な問題が多くて辛かったです。配点から早ときできるかが勝負になる事は読めていて、早ときが苦手なのは重々承知なので見え透いた敗北ではありましたが...