Mujin Programming Challenge 2017 C - Robot and String (解説を見た)

自分で考察したときは手掛かりが何もなかった。
C - Robot and String

問題

英小文字からなる文字列Sが与えられる。以下の形のクエリにQ回答えよ。

Sの部分文字列S[L[i]...R[i] + 1] (半開区間、L[i]文字目からR[i]文字目までを抜き出した文字列)について、以下の規則で簡約していった結果が空文字列になるか判定せよ:
- 文字列の中に隣接する同じ文字がある場合に、それらの中で一番左のものについて、その同じ2文字を辞書順で次の文字1文字に変換する。ただしzzの変換先は空文字列とする。

制約

1 <= |S| <= 5 * 10^5
1 <= Q <= 10^5

解法

まず、各iについて、S[i...x]が空文字列に簡約されるような最小のx > iを求めたい気分になる。文字列の簡約は左から優先して行われるので、空文字列から始めて、i文字目から文字を追加して簡約して…、という処理をj文字目まで行った結果は、S[i..j]を簡約した結果と同じになる。
i文字目から文字の追加・簡約を繰り返すとき、文字列が最初に空文字列に簡約されるのはいつだろうか? そのような場合はもともと"z"だった文字列に'z'を追加した場合、およびその場合に限られる。よって、各iについてS[i..x]が"z"に簡約されるような最小のx > iを求めたい気分になる。この考察を繰り返すと、各iについてS[i..x]が各文字1文字に簡約されるような最小のx > iを求めたい気分になる。

実は以上の情報がDPをする上で十分である。DP[i] := (S[i...x]が空文字列に簡約されるような最小のx > i), DPS[c][i] := (S[i..x]がc 1文字に簡約されるような最小のx > i)とすると、以下の更新を行えばいいことがわかる(更新はすべてminで、式の中に一つでもinvalidな値がある場合は実行されない):

DPS[c][i] <- DPS[c][DP[i]]
DPS[c + 1][i] <- DPS[c][DPS[c][i]] (c < 'z', ダブリングに似ている)
DP[i] <- DPS['z'][DPS['z'][i]]

これらの更新はどこから始めればよいか? まず、i = n - 1のときは更新なしで正しい答えが手に入る。i = n - 2のときは、DP[n - 1]と各文字cについてDPS[c][n - 1]がわかっていれば正しい答えが手に入る。この考察を帰納的に行うことで、iの降順に更新を行えば良いことがわかる。

以上でDP[i]がわかった。あとはこれをダブリングすれば、各クエリに対してO(log |S|)時間で答えを求めることができる。このダブリングの手法は例えばLCAの計算などで有名なので、ここでは省略する。

登場する典型

ダブリング
再帰的に考察を進め、自己完結したら止める

実装上の注意点

添字の扱い(上限n - 1かnか)に気をつける

提出: #4397603 (Rust)

// This solution was written after the author read the editorial.
fn solve() {
    let out = std::io::stdout();
    let mut out = BufWriter::new(out.lock());
    macro_rules! puts {
        ($($format:tt)*) => (write!(out,$($format)*).unwrap());
    }
    input! {
        s: chars,
        lr: [(usize1, usize)],
    }
    let n = s.len();
    let s: Vec<_> = s.into_iter().map(|x| (x as u8 - b'a') as usize).collect();
    let mut dp = vec![n + 1; n + 1];
    let mut dps = vec![vec![n + 1; 26]; n + 1];
    for i in (0..n).rev() {
        let mut que = BinaryHeap::new();
        que.push((n - i - 1, s[i]));
        while let Some((pidx, ch)) = que.pop() {
            let idx = n - pidx;
            if ch <= 25 {
                if dps[i][ch] <= idx { continue; }
                dps[i][ch] = idx;
                if dps[idx][ch] <= n {
                    que.push((n - dps[idx][ch], ch + 1));
                }
            } else {
                assert_eq!(ch, 26);
                if dp[i] <= idx { continue; }
                dp[i] = idx;
                for j in 0..26 {
                    if dps[idx][j] <= n {
                        que.push((n - dps[idx][j], j));
                    }
                }
            }
        }
    }
    const B: usize = 20;
    let mut dbl = vec![vec![n + 1; n]; B];
    for i in 0..n {
        dbl[0][i] = dp[i];
    }
    for j in 1..B {
        for i in 0..n {
            let stage = dbl[j - 1][i];
            if stage < n {
                dbl[j][i] = dbl[j - 1][stage];
            }
        }
    }
    for (mut l, r) in lr {
        for i in (0..B).rev() {
            if dbl[i][l] <= r {
                l = dbl[i][l];
            }
            if l == n { break; }
        }
        puts!("{}\n", if l == r { "Yes" } else { "No" });
    }
}

まとめ

「1文字に簡約できる範囲を持つDP」という解説の方法が天才すぎて、それっぽい考察の道筋をこじつけるのに苦労した。