AtCoder Beginner Contest 430 E,F,G問題メモ

AtCoder Beginner Contest 430

E - Shift String

問題文

0, 1 からなる長さの等しい文字列 $A,B$ が与えられます。
$A$ に対して以下の操作を $0$ 回以上何度でも行うことができます。
- $A$ の先頭の文字を末尾に移動させる。
$A=B$ とするために必要な最小の操作回数を求めてください。
但し、どのように操作しても $A=B$ とできない場合、代わりに $-1$ と出力してください。

$T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

$1 \le T \le 10000$
$A,B$ は 0, 1 からなる文字列
$2 \le |A|=|B| \le 10^6$
ひとつの入力について、 $|A|$ の総和は $10^6$ を超えない

解法

「$A+A$（$A$ を2つ連結した文字列）の中で最も最初に現れる $B$ はどこですか」という文字列検索の問題と分かれば単純。

Pythonでの楽な解法

Python組込の文字列検索アルゴリズム（str.find）は、使用するアルゴリズムを柔軟に切り替えるが、文字列が長い場合、KMP法とBM法を組み合わせて両側からいい感じに高速化するTwo-Wayアルゴリズムが採用されているらしい。

Two-way_string-matching_algorithm
cpython/Objects/stringlib/fastsearch.h at main
- If the strings are long enough, use Crochemore and Perrin's Two-Way algorithm, which has worst-case O(n) runtime …(略)

計算量は $O(N+M)$ の上、C言語で実装されているため、これに任せれば間に合う。

ただし、PyPyやCodonではTLEとなる。意外な結果。

正規解法

ちゃんとやろうとすると、ローリングハッシュ、Suffix Array、Z-Algorithm などで解ける。

ローリングハッシュを用いる場合、文字が 0 と 1 のみのため base を $2$ としたくなるが、安易にそれを採用すると 998244353 や 1000000007 などの有名modでハッシュ衝突するように仕組まれていた。

確認する素数をもう少し増やすと通ったが、確率的解法であることをちゃんと自覚し、メタ的に読まれやすい実装は避けるべきだね。

あと、複数試すなら mod より base を変えた方が精度が上がりやすくなるとのこと。

Xユーザーの熨斗袋さん: 「(定期) Rolling Hash は mod ではなく base の方をランダムにするだけで落ちなくなります。精度上げたい時も mod ではなく base を複数組み合わせるだけで良いです。あと 2^61-1 を使ってください」 / Twitter

Python3

def solve(aaa, bbb):
    n = len(aaa)
    aaa = list(map(int, aaa))
    bbb = list(map(int, bbb))

    def sub(mod):
        ha = 0
        hb = 0
        for i in range(n):
            ha = (ha * 2 + aaa[i]) % mod
            hb = (hb * 2 + bbb[i]) % mod

        if ha == hb:
            return 0

        p = pow(2, n, mod)

        for i in range(n):
            ha *= 2
            if aaa[i] == 1:
                ha -= p
                ha += 1
            ha %= mod
            if ha == hb:
                return i + 1

        return -1

    ans1 = sub(998244353)
    ans2 = sub(998244853)
    ans3 = sub(1000000007)
    ans4 = sub(1012924417)
    if ans1 == -1 or ans2 == -1 or ans3 == -1 or ans4 == -1:
        return -1
    return max(ans1, ans2, ans3, ans4)


t = int(input())
for _ in range(t):
    aaa = input()
    bbb = input()
    ans = solve(aaa, bbb)
    print(ans)

F - Back and Forth Filling

問題文

整数 $N$ と長さ $N-1$ の L, R からなる文字列 $S$ が与えられます。
横一列に並んだ $N$ 個のマス目に、以下の条件を全て満たすように整数を書き込むことを考えます。
- 全てのマスに整数が $1$ つ書かれている。
- 整数 $1,2,\dots,N$ が書かれているマスが $1$ つずつ存在する。
- $S$ の $i$ 文字目が L であるとき、 $i+1$ は $i$ より左に書き込まれている。
- $S$ の $i$ 文字目が R であるとき、 $i+1$ は $i$ より右に書き込まれている。

$C_i$ を「左から $i$ マス目に書き込まれる整数としてありうるものの個数」とします。
$C_1,C_2,\dots,C_N$ を求めてください。

$T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

$1 \le T \le 20000$
$2 \le N \le 3 \times 10^5$
$S$ は長さ $N-1$ の L, R からなる文字列
ひとつの入力について、 $N$ の総和は $3 \times 10^5$ を超えない

解法

$x=1,2,...,N$ と $i=1,2,...,N$ に対して以下の問題を考える。

最初に数字 $x$ をマス $i$ に置いたとして、残りを問題なく置けるか？

答えが Yes なら $C_i$ に1加算する。全ての $(x,i)$ の組に対して処理したら答えとなる。
このままだと $O(N^2)$ だが、各 $x$ に対してYesとなる $i$ は連続した区間となるので、 imos法で $O(N)$ に高速化できる。

端の $x=1,N$ は割愛するとして、他は、挟まれているアルファベットと、その連続個数による。

同じ文字に挟まれている場合

               x
... R L L ... L L ... L L R R ...
     |----a----|----b----|
              ↓
    
 ... o ←L-- o ←L-- o ←L-- x ←L-- o ←L-- o ←L-- o ...
`----------- b -------'              `-------- a -----------'

Lに挟まれ、その左右の連続個数が $a$ と $b$ だった場合、 $x$ の右に $a$ 個、左に $b$ 個、他の数字を置くスペースが必要。
逆にこれさえ満たせば $x$ を置くことができる。

Rの場合は左右逆。

違う文字に挟まれている場合

               x
... R L L ... L R ... R R L L ...
     |----a----|----b----|
              ↓

          |-------- a ----------|
   ↙--L-- o ←L-- o ←L-- o ...
  x
   `---R----→ o --R→ o --R→ o ...
              |-------- b ----------|

左にL、右にRで挟まれている場合、右側に $a+b$ 個、他の数字を置くスペースがあればよい。

左にR、右にL の場合は左右逆。

これに従って、各数字の置ける範囲をimos法で足し込んでいけば $C_i$ が求められる。

Python3

from itertools import accumulate


def solve(n, s):
    fwd_cons = [0] * n
    bwd_cons = [0] * n
    streak = 1
    for i in range(1, n - 1):
        fwd_cons[i] = streak
        if s[i - 1] == s[i]:
            streak += 1
        else:
            streak = 1
    fwd_cons[n - 1] = streak
    streak = 1
    for i in range(n - 2, 0, -1):
        bwd_cons[i] = streak
        if s[i - 1] == s[i]:
            streak += 1
        else:
            streak = 1
    bwd_cons[0] = streak

    acc = [0] * (n + 1)

    bc = bwd_cons[0]
    if s[0] == 'L':
        acc[bc] += 1
        acc[n] -= 1
    else:
        acc[0] += 1
        acc[n - bc] -= 1
    fc = fwd_cons[-1]
    if s[-1] == 'L':
        acc[0] += 1
        acc[n - fc] -= 1
    else:
        acc[fc] += 1
        acc[n] -= 1

    for i in range(1, n - 1):
        fc = fwd_cons[i]
        bc = bwd_cons[i]
        if s[i - 1] == s[i] == 'L':
            acc[bc] += 1
            acc[n - fc] -= 1
        elif s[i - 1] == s[i] == 'R':
            acc[fc] += 1
            acc[n - bc] -= 1
        elif s[i - 1] == 'L' and s[i] == 'R':
            acc[0] += 1
            acc[n - fc - bc] -= 1
        else:
            acc[fc + bc] += 1
            acc[n] -= 1

    acc = list(accumulate(acc))
    return acc[:-1]


t = int(input())
for _ in range(t):
    n = int(input())
    s = input()
    ans = solve(n, s)
    print(*ans)

G - Range Set Modifying Query

問題文

$N$ 個の集合 $S_1, \ldots,S_N$ があります。最初、全ての集合は空集合です。
以下の形式のクエリが $Q$ 個与えられるので順に処理してください。
- タイプ $1$：1 L R x の形式で与えられる。$L \leq i \leq R$ を満たす各 $S_i$ に対し、$x$ を追加する。
- タイプ $2$：2 L R x の形式で与えられる。$L \leq i \leq R$ を満たす各 $S_i$ に対し、$x$ を削除する。
- タイプ $3$：3 L R の形式で与えられる。$L \leq i \leq R$ を満たす $S_i$ のうちの、要素数の最大値と、それを達成する集合の個数を求める。

制約

$1\leq N \leq 3\times 10^5$
$1\leq Q \leq 3\times 10^5$
各クエリにおいて、$1 \leq L \leq R \leq N$
タイプ $1,2$ のクエリにおいて、$1 \leq x \leq 60$
入力は全て整数

解法

Segment Tree Beats というデータ構造の練習問題。（使わなくても工夫次第で解ける）

Lazy Segment Tree を応用したデータ構造

LazySegTree で区間更新・区間取得したい。
しかし、区間更新の際、持たせている情報だけでは「たまに」上手く区間へのmappingができないことがある。
その場合、上手くmappingができるところまで作用素を子に伝えて、ボトムアップで求める。

               ↓d                   ←区間1に作用素dをmappingしたいが、
|-------------- 1 --------------|      上手くmappingできない
       ↓d             ↓d
|------ 2 ------|------ 3 ------|    ←子に伝えて、mappingできるか試す。
   ↓d     ↓d          OK!
|-- 4 --|-- 5 --|                    ※厳密には作用素dは、伝播の過程で
   OK!   ↓d ↓d                       既に各ノードのlazyに溜まっている他の作用素と
        | 10| 11|                      合成させながら下に伝えていく
         OK! OK!

|-------------- 1 --------------|
        ↑              ↑
|------ 2 ------|------ 3 ------|    その後、ボトムアップでマージしていけば、
    ↑      ↑                       区間1に作用素dをmappingした結果が得られる。
|-- 4 --|-- 5 --|
          ↑  ↑
        | 10| 11|

ただし、伝播の回数が多くなりすぎると結局、計算量がかさんでしまう。
これは問題の性質次第であり、使える場合と使えない場合がある。

本問題への適用

この問題の場合、クエリ3に答えるには以下の情報があればSegTreeでマージできる。

区間中の $S_i$ の最大要素数
区間中で最大要素数となる $S_i$ の個数

クエリ1と2の更新では、仮に「区間内の全ての $S_i$ で、$x$ を含む/含まないが一致している」場合は、追加・削除による相対的な要素数は変わらないので、

各要素を含む/含まないが、区間内の全ての集合で一致しているか（bitset）
一致している場合、全て含んでいるのか、全て含んでいないのか（bitset）

の情報が追加であれば、区間に対してmappingをおこなえる。

しかし、含む/含まないが混じっている場合は上手くおこなえない。
この場合は、区間の $x$ を含む/含まないが一致するようになるまで上図のように子に伝播させる。

さて、問題はこの伝播回数がTLEにならない程度に収まるか、という点である。

$x$ のmappingが失敗するノード、つまりは区間内で要素 $x$ を含む/含まないが混じっているノードは、クエリ 1 or 2 によって、$L$ または $R$ の上側をカバーする区間として最大 $2 \log{N}$ 個生成される。

|===============================|
|===============|===============|    |===|: クエリによって
|=======|-------|-------|=======|           含む/含まないが
|---|---|---|---|---|---|===|---|           混在するようになる箇所
|-|-|L|-|-|-|-|-|-|-|-|-|R|-|-|-|

mapping の失敗は |===| の区間で発生する。
1回おこなうと、|===| は必ず混在しない状態 |—| に変化する。
よって、失敗は $O(Q \log{N})$ 回の発生で抑えられる。

（……と思ったんだが、公式Editorialによるとそれに加えて $O(N \max(x))$ も必要らしい。ちゃんと理解できてない）

よって、Beats に載せることができる。

Pythonでの実装

定数倍が重くなるので、CPython だと厳しい。
PyPyも、わざわざ再帰を使わないような書き方にするなど試したが、TLEが取れなかった。

早速、本コンテストから利用できるようになったCodonを使ってACできたが、それでも 3.8 sec なので、そもそも実装に無駄がある可能性がある。

LazySegTree の自作ライブラリは、mappingやcompositionの型で混乱しないようにGenerics型を用いてtypehintを与えていたが、 Codonにコンパイルさせる場合、なかなかこのtypehintを上手く解釈してくれず（させる方法が分からず）、結局、全て取り払ってコンパイラに型推論を任せることで通るようになった。
この辺、コンテスト中の高速化手段とするのであればもう少し調べておく必要がある。

Python3

MAX_X = 60


# Codon では、Generic型を複数の関数に渡って共有するのが難しい？（やり方が分かってないだけかも）
# 型推論が優秀なので、敢えて型指定を無くした方がコンパイルが上手くいった。。。今回の場合は。

class SegmentTreeBeatsInjectable:
    def __init__(self,
                 n: int,
                 id_data,
                 id_lazy,
                 operation,
                 mapping,
                 composition,
                 ):
        self.n = n
        self.depth = 64 - (n - 1).__ctlz__()
        self.offset = 1 << self.depth
        self.id_data = id_data
        self.id_lazy = id_lazy
        self.operation = operation
        self.mapping = mapping
        self.composition = composition
        self.data = [id_data] * (self.offset << 1)
        self.lazy = [id_lazy] * self.offset

    def init_array(self, init):
        for i, d in enumerate(init):
            self.data[i + self.offset] = d
        for i in range(self.offset - 1, 0, -1):
            self.update(i)

    def push(self, i: int) -> None:
        if i < self.offset:
            lazy = self.lazy
            lz = lazy[i]

            lch = i << 1
            rch = lch + 1
            self.all_apply(lch, lz)
            self.all_apply(rch, lz)
            lazy[i] = self.id_lazy

    def update(self, i: int) -> None:
        lch = i << 1
        rch = lch + 1
        self.data[i] = self.operation(self.data[lch], self.data[rch])

    def all_apply(self, i: int, d) -> None:
        data = self.data
        lazy = self.lazy
        offset = self.offset

        mp_stack = [(i, d)]
        need_update = []

        while mp_stack:
            j, e = mp_stack.pop()
            data[j] = self.mapping(data[j], e)
            if data[j][0] >= 0:
                if j < offset:
                    lazy[j] = self.composition(lazy[j], e)
                continue
            need_update.append(j)
            ne = self.composition(lazy[j], e)
            lazy[j] = self.id_lazy
            lch = j << 1
            rch = lch + 1
            mp_stack.append((lch, ne))
            mp_stack.append((rch, ne))

        for j in reversed(need_update):
            self.update(j)

    def propagate(self, l: int, r: int) -> None:
        last_pushed = 0
        for i in range(self.depth, 0, -1):
            if ((l >> i) << i) != l:
                k = l >> i
                self.push(k)
                last_pushed = k
            if ((r >> i) << i) != r:
                k = (r - 1) >> i
                if last_pushed != k:
                    self.push(k)

    def range_update(self, l: int, r: int, d) -> None:
        l += self.offset
        r += self.offset
        self.propagate(l, r)

        l2 = l
        r2 = r
        while l < r:
            if (l & 1) == 1:
                self.all_apply(l, d)
                l += 1
            if (r & 1) == 1:
                r -= 1
                self.all_apply(r, d)
            l >>= 1
            r >>= 1
        l = l2
        r = r2

        last_updated = 0
        for i in range(1, self.depth + 1):
            if ((l >> i) << i) != l:
                k = l >> i
                self.update(k)
                last_updated = k
            if ((r >> i) << i) != r:
                k = (r - 1) >> i
                if k != last_updated:
                    self.update(k)

    def range_query(self, l: int, r: int):
        l += self.offset
        r += self.offset
        self.propagate(l, r)

        sml = self.id_data
        smr = self.id_data
        while l < r:
            if (l & 1) == 1:
                sml = self.operation(sml, self.data[l])
                l += 1
            if (r & 1) == 1:
                r -= 1
                smr = self.operation(self.data[r], smr)
            l >>= 1
            r >>= 1
        return self.operation(sml, smr)

    def point_set(self, p: int, d) -> None:
        p += self.offset
        for i in range(self.depth, 0, -1):
            self.push(p >> i)
        self.data[p] = d
        for i in range(1, self.depth + 1):
            self.update(p >> i)

    def point_get(self, p: int):
        p += self.offset
        for i in range(self.depth, 0, -1):
            self.push(p >> i)
        return self.data[p]

    def debug_print(self) -> None:
        i = 1
        while i <= self.offset:
            buf = []
            for j in range(i, i << 1):
                a0, a1, a2, a3 = self.data[j]
                buf.append(f'({a0},{a1},{a2:0{MAX_X}b},{a3:0{MAX_X}b})')
            suffix = '-' * (self.offset // i - 1) * 24 + '|'
            print(suffix.join(buf) + suffix)
            i <<= 1
        i = 1
        while i <= self.offset:
            print(*self.lazy[i:i * 2])
            i <<= 1


id_data = (0, 0, (1 << MAX_X) - 1, 0)
id_lazy = (0, 0)


def operation(a, b):
    a0, a1, a2, a3 = a
    b0, b1, b2, b3 = b
    c2 = a2 & b2 & ~(a3 ^ b3)
    c3 = a3 & c2
    if a0 == b0:
        return (a0, a1 + b1, c2, c3)
    if a0 > b0:
        return (a0, a1, c2, c3)
    return (b0, b1, c2, c3)


def mapping(a, b):
    b0, b1 = b
    if b0 == b1 == 0:
        return a
    a0, a1, a2, a3 = a
    b01 = b0 | b1
    if b01 & a2 != b01:
        return (-1, 0, 0, 0)  # 更新失敗

    ad = (~a3 & b0).popcnt()
    a0 += ad
    a3 |= b0
    rm = (a3 & b1).popcnt()
    a0 -= rm
    a3 ^= (a3 & b1)
    return (a0, a1, a2, a3)


def composition(a, b):
    a0, a1 = a
    b0, b1 = b
    if b0 > 0:
        a0 |= b0
        a1 ^= a1 & b0
    if b1 > 0:
        a1 |= b1
        a0 ^= a0 & b1
    return (a0, a1)


def solve(n, q, queries):
    init = [(0, 1, (1 << MAX_X) - 1, 0)] * n
    lst = SegmentTreeBeatsInjectable(n, id_data, id_lazy, operation, mapping, composition)
    lst.init_array(init)
    buf = []
    for query in queries:
        if query[0] == 1:
            _, l, r, x = query
            lst.range_update(l - 1, r, (1 << (x - 1), 0))
        elif query[0] == 2:
            _, l, r, x = query
            lst.range_update(l - 1, r, (0, 1 << (x - 1)))
        else:
            _, l, r = query
            ans = lst.range_query(l - 1, r)
            max_size, count = ans[0], ans[1]
            buf.append(f'{max_size} {count}')
    return buf


n, q = list(map(int, input().split()))
queries = [list(map(int, input().split())) for _ in range(q)]
ans = solve(n, q, queries)
print('\n'.join(ans))

目次

AtCoder Beginner Contest 430 E,F,G問題メモ

E - Shift String

問題文

制約

解法

Pythonでの楽な解法

正規解法

F - Back and Forth Filling

問題文

制約

解法

同じ文字に挟まれている場合

違う文字に挟まれている場合

G - Range Set Modifying Query

問題文

制約

解法

Lazy Segment Tree を応用したデータ構造

本問題への適用

Pythonでの実装