Zenn
🌲

ABC341E - Alternating Stringを遅延セグ木で解く

2024/04/23に公開
C++
競技プログラミング
AtCoder
セグメント木
遅延セグメント木
tech

過去問精進している際にハマったので整理します。
誤植や誤りを見つけた場合、コメント欄などで指摘していただけるとありがたいです。

想定する読者は

  • 自分
  • ACLの遅延セグ木の仕組みを完全理解しているわけじゃないが、チートシートなどを見ながらだと遅延セグ木問題が解けたりもする。

問題:
https://atcoder.jp/contests/abc341/tasks/abc341_e

問題概要

01010101や10101010101といった、0と1からなる文字列で隣り合う2文字が異なっているものを良い文字列という。L文字目からR文字目までの01を反転させたり、L文字目からR文字目までを文字列として見たときに良い文字列かどうかを問うクエリをいっぱい出すから高速に処理してね。

最初に考えた解法(WA)

  • 良い文字列かどうかという判定は、文字列の奇数文字目を01反転させた後は、「1種類の文字からなる文字列かどうか」という判定になって、考えやすくなる。(ので、そうする。) [1]

  • 1つ目のクエリの区間に対して01を反転させる処理は、区間に対してxorで1を足す操作だと考えられる

  • 2つ目のクエリの区間が良い文字列かどうかを判定する処理は、区間の和が0もしくは(R-L+1)かどうかで判定できる

  • じゃあ遅延セグメント木でいけるじゃん！

Sは整数、fは0か1の整数として、opは普通に整数の和で、mappingは整数に整数のxorを取ったものを返せばいいし、compositionもf^gでいいな。idはxorの単位元と一緒で0を返せばいいね。

ll sum (ll a, ll b) {
  return a + b;
}

ll e() {
  return 0;
}

ll mapping(ll f, ll x) {
  assert(0 <= f && f<=1);
  return x ^ f;
}

ll composition(ll f, ll g) {
  assert(0 <= f && f<=1);
  assert(0 <= g && g<=1);
  return f^g;
}

ll id() {
  return 0;
}
int main() {
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  ll N, Q; cin >> N >> Q;
  string S; cin >> S;
  vector<ll>A(N); 
  for(int i=0; i<N; i++) {
    A[i] = S[i] - '0';
    if (i%2 == 1) A[i] ^= 1;
  }  

  atcoder::lazy_segtree<ll, sum, e, ll, mapping, composition, id> seg(A); 
  for(int q=0; q<Q; q++) {
    int qi, L, R; cin >> qi >> L >> R;
    L--;
    if (qi == 1) {
      seg.apply(L, R, 1);
    } else if (qi == 2) {
      ll sum = seg.prod(L, R);
      if (sum == R - L || sum == 0) cout << "Yes" << endl;
      else cout << "No" << endl;
    }

  }
  return 0;
}

として、サンプルもあったし、提出ｗ！　→　WA[2]

上の解法のどこがダメだったのか

ほんとうは遅延セグ木の仕組みを完全理解したうえで図解とかしながら書いていきたいんですが、理解していないために、遅延セグ木の仕組みを理解していなくてもわかることだけ書きます。

上のFはACLの遅延セグメント木が求める性質を満たしていない

ACLの遅延セグメント木が求める性質というのは、ドキュメント[3] に記載されている以下の条件のことです。

  • Sがモノイドであり、FはSからSへの写像の集合である
  • Fは恒等写像idを含む。
  • Fは写像の合成について閉じている。
  • 任意のf \in F, x, y \in Sに対して、f(x \cdot y) = f(x) \cdot f(y)を満たす

先程の解法はこれらを満たしているでしょうか？確認していきましょう。

Sがモノイドであり、FはSからSへの写像の集合である

Sは整数で、二項演算は和です。和には単位元もありますし(0)、結合律も成り立ちますからSはモノイドです。FはSに対して0とxorをとる写像と、1とxorをとる写像でした。　１つ目の条件は満たしていそうです。

Fは恒等写像idを含む。

Sに対して0とxorを取る写像はまさしく恒等写像です。２つ目の条件も満たしてそうです。

Fは写像の合成について閉じている。

これも満たしていそうです。

任意のf \in F, x, y \in Sに対して、f(x \cdot y) = f(x) \cdot f(y)を満たす

これはパッとはわからないですね。計算してみましょう。先ほども書いた通り、Fは恒等写像と、1とxorを取る写像の集合です。恒等写像は明らかに上の条件を満たしているので、1とxorを取る写像について考えましょう。

右辺は、f(x \cdot y) = (x+y) \oplus 1と変形できます。
左辺は、f(x) \cdot f(y) = (x\oplus1) + (y \oplus 1)ですね。

これはすべてのx,yに対しては成立しません。例えば(x,y) = (2,3), (2,2)などが反例です。[4]
反例いっぱい
この条件は遅延セグメント木の鍵とも言える条件なので、これが成立しない以上上の解法は間違っているということがわかりました。

撃墜ケース

１つ目の提出は以下のようなケースで撃墜できます。

4 2
0010
1 3 4
2 1 4

正解: No

ACできる解法

解説などを見ると遅延でないセグメント木の解法が紹介されていますが、遅延セグメント木でもACできます。

WAとなった解法ではSを区間和としていて、二つ以上の要素をカバーする区間に対するxorを取るときの処理がうまくいかないために正解できないわけですが、区間加算/区間和取得の遅延セグメント木でSを(区間の和、区間の幅)としていたことに思いを馳せてよく考えると、同じようにSを(区間の和、区間の幅)として持つと、

struct S {
    int sum, size;
};

S mapping(F f, S x) {
    if (f == 0) return f;
    else return {x.size - x.sum, x.size};
}

S op (S a, S b){
    return {a.sum + b.sum, a.size + b.size};
}

などすると、上の解法では満たされていなかった条件が満たされることになりますね。

一応、「任意のf \in F, x, y \in Sに対して、f(x \cdot y) = f(x) \cdot f(y)を満たす」ことを確認しておきます。fが恒等写像のときは明らかです。fが1とxorを取る写像のとき、

右辺はf(x \cdot y) = f((x.sum + y.sum, x.size + y.size)) = (x.size + y.size - x.sum - y.sum, x.size + y.size)であり、

左辺はf(x) \cdot f(y) = (x.size - x.sum, x.size) \cdot (y.size - y.sum, y.size)　= (x.size + y.size - x.sum - y.sum, x.size + y.size)で、これらは一致します。

なんだかんだでこの実装をすると、ACできました[5]。

おまけ: ランダムケースをするコードと愚直解のコード

generate.py
import random

N = random.randint(4, 200)
Q = random.randint(1, 100)
print(N, Q)


S = ""
for _ in range(N):
  S += str(random.randint(0,1))

print(S) 
for i in range(Q):
  L = random.randint(1,N)
  R = random.randint(L,N)
  print(random.randint(1,2), L, R)
tle.cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned int uint;
template<class T> inline bool chmax(T& a, const T& b) {if (a<b) {a=b; return true;} return false;}
template<class T> inline bool chmin(T& a, const T& b) {if (b<a) {a=b; return true;} return false;}
const int INTINF = 1000001000;
const int INTMAX = 2147483647;
const ll LLMAX = 9223372036854775807;
const ll LLINF = 1000000000000000000;


// [l, r) が良い数列か？
//
bool is_good(const vector<int>& S, int L, int R) {
  bool ret = true;
  for (int i=L; i+1<=R-1; i++) {
    if (S[i] == S[i+1]) {
      ret = false;
      break;
    }
  }
  return ret;
}

// TLELTLELETLELTLELTELT
int main() {
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  ll N, Q; cin >> N >> Q;
  string S; cin >> S;
  vector<int>A(N); 
  for(int i=0; i<N; i++) {
    A[i] = S[i] - '0';
  }  

  for(int q=0; q<Q; q++) {
    int qi, L, R; cin >> qi >> L >> R;
    L--;
    if (qi == 1) {
      for (int i=L; i<R; i++) A[i] ^= 1;
    } else if (qi == 2) {
      bool res = is_good(A,L,R);
      if (res) cout << "Yes" << endl;
      else cout << "No" << endl;
    }
  }
  return 0;
}

online-judge-tools[6]を導入している場合、
oj g/i "python3 generate.py"
g++ tle.cpp -o tle
oj g/o -c "./tle"
oj t
などすると、1行目でランダムケースを自動生成し、
3行目で愚直解で想定される出力を生成し、4行目でランダムケースに対してテストを実行することができます。

実際、200ケースでテストを回してみたところしっかり落ちるケースが見つかりました。

脚注

  1. この考え方はこの問題より後のコンテストの問題 https://atcoder.jp/contests/abc346/tasks/abc346_d の解説放送で覚えたもの ↩︎

  2. 提出したコード: https://atcoder.jp/contests/abc341/submissions/52707947 ↩︎

  3. 参照: https://atcoder.github.io/ac-library/master/document_ja/lazysegtree.html ↩︎

  4. 逆に、これを満たすようなx,yはない気がします。(証明は考えてませんがプログラムで探索した限り見つかりません)→x,yの偶奇で場合分けして4通りについて計算すれば確かめられますね。 ↩︎

  5. 提出したコード: https://atcoder.jp/contests/abc341/submissions/52725254 ↩︎

  6. 参照: https://github.com/online-judge-tools/oj/blob/master/docs/getting-started.ja.md ↩︎

Discussion