AtCoder Regular Contest 151 C,D,E問題メモ

AtCoder Regular Contest 151

手元の実験で法則性が見えやすい問題がC,Dあたりに置かれていると個人的に解きやすい気がする。

C - 01 Game

問題

$N$ 個のマスが横一列に並ぶ
そのうち $M$ 個には、あらかじめ0または1が書かれている
- $i=1,2,...,M$ につき、マス $X_i$ には $Y_i$ （=0/1）が書かれている
先手と後手がゲームをする
ルール
- マスを1つ選び、0か1を書き込む
- ただし、同じ数字が隣り合うように書き込むことは禁止
- 先に書き込めるマスが無くなった方が負け
どちらが必勝か答えよ
$1 \le N \le 10^{18}$
$0 \le M \le 2 \times 10^5$
初期状態で同じ数字は隣り合っていない

解法

対戦形式の問題では、とりあえずGrundy数を作れないか確認する。

今回の場合、連続した未書き込みマスを1つの山とみれば互いに山は影響し合わないので、これ毎にGrundy数を設定できそう。

Grundy数（Nim数, Nimber）の理論

ただ、$N$ がやたら大きい。
Grundy数で解けるとしたら、プログラムで小さい状態からちまちま計算していくのではなく、良い法則があるはず。

頑張って、小さい区間から確認していくと、以下のようなGrundy数の法則が見つかる。

同じ数に挟まれた区間は1
異なる数に挟まれた区間は0
一方の端のみが数字と接している区間は、長さを $n$ として、$n$
初期書き込みが全くなく、両端とも数字がない区間は、$N \mod{2}$

これを証明していく。
便宜的に、Grundy数がkであることをGkと示す。

前提知識として、「操作により山を複数に分割することができるようなゲームにおいては、分割後の山々のGrundy数のXORを、遷移先のGrundy数として扱えばよい」ことは使われる。

まず、両端が数字に挟まれた区間については、

長さ0
00       ルールに反する書き込み方なので考えなくて良い
01       もう書き込めないのでG0

長さ1
0.0      間に1を書き込んでG0に遷移できるのでG1
0.1      もう書き込めないのでG0

長さ0～k-1の時まで下記が成り立っているとして、
0...0    G1
0...1    G0

長さkの時
0....0   どこに書き込もうと、「G0,G0」か「G1,G1」に分割される。
         →いずれにしろG0のみに遷移できることになり、これ自体はG1となる。
0....1   どこに書き込もうと、「G0,G1」に分割される。
         →いずれにしろG1のみに遷移できることになり、これ自体はG0となる。

数学的帰納法により、間の長さに依らず、同じ数字ならG1、違うならG0とわかる。

一方の端が数字と接する場合、

|0       G0
|.0      G1

区間長 n = 0～k-1 まで、そのGrundy数は Gn であると仮定して、

区間長kの時
|.....0  左からt番目に'1'を書き込むと、「G(t-1),G0」に分割される。
         →G(t-1) に遷移できる。
         →よって 0～k-1 の全てに遷移できるので、これ自体は Gk となる。

h 両端が数字に接しない場合、

偶数の時
|....|    どこに書き込んでも、「G(偶数),G(奇数)」に分割される。
          →このXORは決して0にならないため、これ自体は G0 となる。

奇数の時
|.....|   真ん中に書き込むと、「G(x), G(x)」（同じ値）に分割される。
          →G0に遷移できる。
          どこに書き込んでも「G(偶数),G(偶数)」または「G(奇数),G(奇数)」にしかならない。
          →G1には決してならない
          →これ自体はG1となる。

これで全ての場合が証明できた。

Python3

D - Binary Representations and Queries

問題

長さ $2^N$ の数列 $A=(A_0,A_1,...,A_{2^N-1})$
以下の $Q$ 回の操作を順に行う
- $i$ 回目の操作では$X_i,Y_i$ が与えられる
- $j=0～2^N-1$ のうち、2進数表記で下から $X_i$ 桁目が $Y_i$（=0/1）であるような $j$ につき、
  - $j$ の $X_i$ 桁目を反転させたものを $j'$ とする
  - $A_j$ を、$A_{j'}$ に加算する
全て終了後の $A$ を $\mod{998244353}$ で出力せよ
$1 \le N \le 18$
$1 \le Q \le 2 \times 10^5$

解法

操作の内容ががややこしいが、要は、例えば $N=2$ なら正方形の頂点に数字が書かれていて、

※Ai の添字を2進数で表記

  A10 --- A11
   |       |
  A00 --- A01

$X_i=0$ なら左右方向の辺、$X_i=1$ なら上下方向の辺が、それぞれ加算する・される関係性を示すことになる。
どちらにどちらが加算されるかを $Y_i$ が示すことになる。

$N=3$ なら3次元の立方体で同様の表現ができる。
$N=4$ 以上だと図で示すのは難しくなるが、次元が増えていく。

で、実験してみると、どうも異なる次元（$X_i$）間での操作は、入れ替えても結果が変わらないことに気づく。

a---b      a---(a+b)      a---(a+b)      ※矢印は加算方向
|   |  →  |     |    ↓  |     |
c---d      c---(c+d)    (a+c)-(a+b+c+d)

a---b      a-----b        a---(a+b)
|   |  ↓  |     |    →  |     |
c---d    (a+c)-(b+d)    (a+c)-(a+b+c+d)

一方、同じ次元同士では、操作の順番は入れ替えると結果が変わってしまう。

よって、まず $X_i=1$ のクエリだけを与えられた順番通りに処理、その後 $X_i=2$ について処理、、、と操作をまとめることができそう。

$X_i$ が同じクエリの操作は順番通りにやるしかないが、ここで、ある $A_j$ の結果に影響するような他の $A$ の値というのは、上記の正方形の例えで互いに辺でつながれた同士、つまり $j$ に対して $X_i$ 桁目を反転させた $j'$ の位置にある $A_{j'}$ のみである。

$X_i$ 桁目が'0'である方を $j$、'1'である方を $j'$ と固定すると、 $X_i$ に関する全てのクエリ処理後の $(A_j,A_{j'})$ は、 $(a_iA_j+b_iA_{j'}, c_iA_j+d_iA_{j'})$ というように2数に係数をかけた値の和で表すことができて、この $(a_i,b_i,c_i,d_i)$ は、どの $(j,j')$ に対しても変わらない。

よって、$(a_i,b_i,c_i,d_i)=(1,0,0,1)$ の初期状態から始めて、操作をシミュレーションして係数を求めておけば、

操作のシミュレーションに、全ての $X_i$ をまたいで $O(Q)$
ある $X_i$ にたいして結果を反映させるのに $O(2^N)$、それを $N$ 回

で、$O(N2^N+Q)$ で求めることができる。

Python3

E - Keep Being Substring

問題

長さ $N$ の正整数列 $A$ と、その2つの連続部分列（長さ $P$ の $X$ と長さ $Q$ の $Y$）がある
以下の操作で $X$ を $Y$ に一致させる最小操作回数を求めよ
可能な操作
- $X$ の先頭に好きな整数を1つ加える
- $X$ の先頭の要素を削除する
- $X$ の末尾に好きな整数を1つ加える
- $X$ の末尾の要素を削除する
- ただし、操作後も $X$ は $A$ の空でない連続部分列でなければならない
$1 \le N \le 2 \times 10^5$

例

A:  3  1  4  1  5  7  2
X:  3  1
Y:  1  5  7

    3  1                  先頭を削除
       1                  末尾に5を追加
             1  5         末尾に7を追加
             1  5  7      3回で一致

解法

$A$ の中に同じ連続部分列が複数回出てきたら互いにワープできる、というところが難しい。

ただ、ワープできる文字列は互いに似通っていることから、Suffix Arrayを使うとどこにワープできるかがわかりやすくなりそう。
Suffix Arrayで次に来る文字列と何文字一致しているか、を示すLCP配列も求めておくと、以下のようになる。

A:  6  1  2  7  2  3  4  8  3  4  5  9
↓
 i sa[i] lcp[i]  sa[i]から開始した数列A
 0    1    0     [1 2 7 2 3 4 8 3 4 5 9]
 1    4    1     [2 3 4 8 3 4 5 9]
 2    2    0     [2 7 2 3 4 8 3 4 5 9]
 3    8    2     [3 4 5 9]
 4    5    0     [3 4 8 3 4 5 9]
 5    9    1     [4 5 9]
 6    6    0     [4 8 3 4 5 9]
 7   10    0     [5 9]
 8    0    0     [6 1 2 7 2 3 4 8 3 4 5 9]
 9    3    0     [7 2 3 4 8 3 4 5 9]
10    7    0     [8 3 4 5 9]
11   11    -     [9]

この上で、

Suffix Array上のindex（上表の $i$）を $j$
$A$ 上の開始index（上表の $sa[i]$）を $k$
長さを $l$

とすると、たとえば $X=(3,4,8,3)$ から始まったなら $j=4,k=5,l=4$ である。
複数の場所に $X$ が出てくるかも知れないが、そこは適当な1つを選ぶ。

このとき、操作によって遷移できるのは「A上で伸び縮みさせる」か「SuffixArray上で隣に移動する」かのどちらかと考えてよい。

先頭に1文字くっつける
- $k ← k-1$、$j$ もそれに対応する位置に変化
- $l ← l+1$
先頭を1文字削除
- 長さが1以上の時
  - $k ← k+1$、$j$ もそれに対応する位置に変化
  - $l ← l-1$
- 長さが1の時
  - 末尾に追加してから先頭を削除＝次の文字に遷移
  - $k ← k+1$、$j$ もそれに対応する位置に変化
  - $l=1$ のまま
  - コスト2
SuffixArray上で前の順序に遷移
- $j ← j-1$、$k$ もそれに対応する位置に変化
- $l$ は、削除するのは後からでもできるので、なるべく長く保つことを考えると、
  - $lcp[j-1] \ge l$ ならそのまま $l$、コストは0
  - $lcp[j-1] \lt l$ なら $lcp[j-1]$、コストは元の $l$ との差分
SuffixArray上で次の順序に遷移
- $j ← j+1$、$k$ もそれに対応する位置に変化
- $l$ は、
  - $lcp[j] \ge l$ ならそのまま $l$、コストは0
  - $lcp[j] \lt l$ なら $lcp[j]$、コストは元の $l$ との差分

というような遷移が描ける。これでDijkstraなどで $X$ の位置から $Y$ の位置に最短経路探索し、 $j$ が $Y$ のSuffixArray上の位置まで来たら、あとは末尾に追加して長さを揃えるコストを足して答えが求まりそう。。。

ただ、Dijkstraしようにも、状態が多すぎる。

$j$ と $k$ は表裏一体なので1つにまとめられるとしても、同じ $j$ に対して「$l$ が短いがコストが軽い」「$l$ が長いがコストが若干重い」みたいな2つの状態が発生しうる。

例えば $Y=(1,2,3,4,5)$ の頂点に「コスト1で $l=1$（$[1]$）で到達」「コスト2で $l=3$（$[1,2,3]$）で到達」の場合、最終的に $Y$ まで伸ばすコストも考えると後者の方がよいが、先にDijkstraで探索されるのは前者、のようになる。

これらの扱い方をどうするか。

証明ができていないのだが、「$Y$ が長いのに短い方が先に探索される」「$Y$ が短いのに長い方が先に探索される」のが問題なので、ある $j$ を訪れたときに

そこから最大限縮めたときのコスト（現在のコスト $+l-1$）
そこから末尾まで広げたこときのコスト（現在のコスト $+n-k-l$）

をそれぞれ記録しておいて、過去にその $j$ を訪れた時の値と比較していずれも悪ければ遷移させない、とすると通った。

でも、単にテストケースに見逃されているだけのような気もする。
$Y$ が中くらいの長さで、短い状態と長い状態が先に探索された場合とか。
ちょっとずつ、同じ頂点が過去に訪れた時より良いコストとなり、同じ頂点が何度も更新されてTLEになるとか。

それともそういう探索はされないという性質があるのかな。

Python3

import os
import sys
from heapq import heappop, heappush

import numpy as np


def solve(inp):
    def induce(s, n, sa, ls, sum_s, sum_l, lms):
        sa.fill(-1)
        buf = np.zeros_like(sum_s)

        buf[:] = sum_s
        for d in lms:
            if d == n:
                continue
            sa[buf[s[d]]] = d
            buf[s[d]] += 1

        buf[:] = sum_l
        sa[buf[s[n - 1]]] = n - 1
        buf[s[n - 1]] += 1
        for i in range(n):
            v = sa[i]
            if v >= 1 and ls[v - 1] == 0:
                sa[buf[s[v - 1]]] = v - 1
                buf[s[v - 1]] += 1

        buf[:] = sum_l
        for i in range(n - 1, -1, -1):
            v = sa[i]
            if v >= 1 and ls[v - 1] == 1:
                buf[s[v - 1] + 1] -= 1
                sa[buf[s[v - 1] + 1]] = v - 1

    def suffix_array(s, upper):

        stack = []

        while True:
            n = s.size
            sa = np.zeros(n, np.int64)
            if n < 2:
                break
            if n == 2:
                sa[int(s[0] < s[1])] = 1
                break

            ls = np.zeros(n, np.int64)
            for i in range(n - 2, -1, -1):
                ls[i] = ls[i + 1] if s[i] == s[i + 1] else s[i] < s[i + 1]
            sum_l = np.zeros(upper + 1, np.int64)
            sum_s = np.zeros(upper + 1, np.int64)
            for i in range(n):
                if ls[i]:
                    sum_l[s[i] + 1] += 1
                else:
                    sum_s[s[i]] += 1

            for i in range(upper + 1):
                sum_s[i] += sum_l[i]
                if i < upper:
                    sum_l[i + 1] += sum_s[i]

            lms_map = np.full(n + 1, -1, np.int64)
            m = 0
            for i in range(1, n):
                if ls[i - 1] == 0 and ls[i] == 1:
                    lms_map[i] = m
                    m += 1

            lms = np.zeros(m, np.int64)
            idx = 0
            for i in range(1, n):
                if ls[i - 1] == 0 and ls[i] == 1:
                    lms[idx] = i
                    idx += 1

            induce(s, n, sa, ls, sum_s, sum_l, lms)

            if m == 0:
                break

            sorted_lms = np.zeros(m, np.int64)
            idx = 0
            for v in sa:
                if lms_map[v] != -1:
                    sorted_lms[idx] = v
                    idx += 1
            rec_s = np.zeros(m, np.int64)
            rec_upper = 0
            rec_s[lms_map[sorted_lms[0]]] = 0
            for i in range(1, m):
                l = sorted_lms[i - 1]
                r = sorted_lms[i]
                end_l = lms[lms_map[l] + 1] if lms_map[l] + 1 < m else n
                end_r = lms[lms_map[r] + 1] if lms_map[r] + 1 < m else n
                same = True
                if end_l - l != end_r - r:
                    same = False
                else:
                    while l < end_l:
                        if s[l] != s[r]:
                            break
                        l += 1
                        r += 1
                    if l == n or s[l] != s[r]:
                        same = False
                if not same:
                    rec_upper += 1
                rec_s[lms_map[sorted_lms[i]]] = rec_upper

            stack.append((s, sa, ls, sum_s, sum_l, lms, sorted_lms))

            s = rec_s
            upper = rec_upper

        while stack:
            s, _sa, ls, sum_s, sum_l, lms, sorted_lms = stack.pop()
            n = s.size
            m = lms.size
            for i in range(m):
                sorted_lms[i] = lms[sa[i]]
            induce(s, n, _sa, ls, sum_s, sum_l, sorted_lms)
            sa = _sa

        return sa

    def lcp_array(s, sa):
        n = s.size
        rnk = np.argsort(sa)
        lcp = np.zeros(n - 1, np.int64)
        h = 0
        for i in range(n):
            if h > 0:
                h -= 1
            if rnk[i] == 0:
                continue
            j = sa[rnk[i] - 1]
            while j + h < n and i + h < n:
                if s[j + h] != s[i + h]:
                    break
                h += 1
            lcp[rnk[i] - 1] = h
        return lcp

    def search_check(n, s, start, m, t):
        limit = min(n - start, m)
        for i in range(limit):
            if s[start + i] > t[i]:
                return False
            if s[start + i] < t[i]:
                return True
        return True

    def search(s, sa, t):
        l = 0
        r = s.size
        while l + 1 < r:
            m = (l + r) // 2
            if search_check(s.size, s, sa[m], t.size, t):
                l = m
            else:
                r = m
        return l

    n = inp[0]
    aaa = inp[1:n + 1]
    p = inp[n + 1]
    xxx = inp[n + 2:n + 2 + p]
    q_ = inp[n + 2 + p]
    yyy = inp[n + 3 + p:]

    sa = suffix_array(aaa, n + 1)
    lcp = lcp_array(aaa, sa)
    xi = search(aaa, sa, xxx)
    yi = search(aaa, sa, yyy)

    for i in range(n):
        print(i, sa[i], lcp[i] if i < len(lcp) else -1, aaa[sa[i]:])

    sa_loc = np.zeros(n, np.int64)
    for i in range(n):
        sa_loc[sa[i]] = i

    q = [(0, xi, p)]
    to_max_length_cost = np.full(n, 1 << 60, np.int64)
    ans = 1 << 60

    def is_updatable(cost, sa_i, si, length, updates_cost):
        max_lc = cost + n - si - length
        if to_max_length_cost[sa_i] > max_lc:
            if updates_cost:
                to_max_length_cost[sa_i] = max_lc
            return True
        return False

    while q:
        cost, sa_i, length = heappop(q)
        if cost >= ans:
            break
        if sa_i == yi:
            ans = min(ans, cost + abs(q_ - length))
            continue

        si = sa[sa_i]
        if not is_updatable(cost, sa_i, si, length, True):
            continue
        # print(cost, sa_i, si, length, aaa[si:si + length], q)

        if si > 0:
            nxt_sa_i = sa_loc[si - 1]
            new_cost = cost + 1
            new_length = length + 1
            if is_updatable(new_cost, nxt_sa_i, si - 1, new_length, False):
                heappush(q, (new_cost, nxt_sa_i, new_length))
                # print('push 0', (cost + 1, nxt_sa_i, length + 1))

        if length > 1:
            nxt_sa_i = sa_loc[si + 1]
            new_cost = cost + 1
            new_length = length - 1
            if is_updatable(new_cost, nxt_sa_i, si + 1, new_length, False):
                heappush(q, (new_cost, nxt_sa_i, new_length))
                # print('push 1', (cost + 1, nxt_sa_i, length - 1))
        elif si < n - 1:
            nxt_sa_i = sa_loc[si + 1]
            new_cost = cost + 2
            new_length = length
            if is_updatable(new_cost, nxt_sa_i, si + 1, new_length, False):
                heappush(q, (new_cost, nxt_sa_i, new_length))
                # print('push 2', (cost + 2, nxt_sa_i, length))

        if sa_i > 0 and lcp[sa_i - 1] > 0:
            nxt_sa_i = sa_i - 1
            if length > lcp[sa_i - 1]:
                new_cost = cost + length - lcp[sa_i - 1]
                new_length = lcp[sa_i - 1]
                if is_updatable(new_cost, nxt_sa_i, sa[nxt_sa_i], new_length, False):
                    heappush(q, (new_cost, nxt_sa_i, new_length))
                    # print('push 3', (new_cost, nxt_sa_i, lcp[sa_i - 1]))
            else:
                new_cost = cost
                new_length = length
                if is_updatable(new_cost, nxt_sa_i, sa[nxt_sa_i], new_length, False):
                    heappush(q, (new_cost, nxt_sa_i, new_length))
                    # print('push 4', (cost, nxt_sa_i, length))

        if sa_i < n - 1 and lcp[sa_i] > 0:
            nxt_sa_i = sa_i + 1
            if length > lcp[sa_i]:
                new_cost = cost + length - lcp[sa_i]
                new_length = lcp[sa_i]
                if is_updatable(new_cost, nxt_sa_i, sa[nxt_sa_i], new_length, False):
                    heappush(q, (new_cost, nxt_sa_i, new_length))
                    # print('push 5', (new_cost, nxt_sa_i, lcp[sa_i]))
            else:
                new_cost = cost
                new_length = length
                if is_updatable(new_cost, nxt_sa_i, sa[nxt_sa_i], new_length, False):
                    heappush(q, (new_cost, nxt_sa_i, new_length))
                    # print('push 6', (cost, nxt_sa_i, length))

        # print(q)

    return ans


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit('(i8[:],)', cache=True)(solve)
    print('compiled', file=sys.stderr)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print(ans)

目次

AtCoder Regular Contest 151 C,D,E問題メモ

C - 01 Game

問題

解法

D - Binary Representations and Queries

問題

解法

E - Keep Being Substring

問題

例

解法