SMBCプログラミングコンテスト #1（AtCoder Beginner Contest 458）F,G問題メモ

SMBCプログラミングコンテスト #1（AtCoder Beginner Contest 458）

F - Critical Misread

問題文

英小文字からなる $K$ 個の文字列 $S_i$ が与えられます。
英小文字からなる長さ $N$ の文字列であって、 $S_1,S_2,\dots,S_K$ のいずれも部分文字列 (連続する部分列) として含まないものの個数を $998244353$ で割った余りを求めてください。

制約

$N$ は $1$ 以上 $10^9$ 以下の整数
$K$ は $1$ 以上 $10$ 以下の整数
$S_i$ は英小文字からなる長さ $1$ 以上 $10$ 以下の文字列

解法

Aho-Corasick + ダブリング。

$S_1=$'ababcdcd'、$S_2=$'cdcdefef'、$S_3=$'efefabab' のように文字列が互いに重なり合っている可能性があるので、例えば包除原理などを使って「$S_1,S_2$ を含む文字列」などを求めようにも、どのように重なっているかによってパターン数が異なってきて、全てのケースを網羅するのが難しい。

オートマトンをイメージするとよい。
「今、$S_i$ のどれかに最も長くマッチしている状態」を表す頂点を用意し、遷移を考える。

S = ['abcd', 'bcef']

 0  1  2  3  4
○→a→b→c→d    各Siの末尾である 4:abcd や 8:bcef を表す頂点への遷移は不可とする。
 `→b→c→e→f
    5  6  7  8

このオートマトンをグラフと見なし、禁止された状態への遷移は除外しつつ隣接行列を作ることを目指す。
上例で言うと、3→4 と 7→8 の辺は無いものとして考える。

以下のような隣接行列となる。この隣接行列を $N$ 乗したものは、オートマトンを $N$ 回遷移した後の状態を示している。

上例のオートマトンの隣接行列（4,8 への遷移は除外）
        0  1  2  3  4  5  6  7  8
0 ○   24  1  0  0  0  1  0  0  0
1 a    24  1  1  0  0  0  0  0  0
2 ab   23  1  0  1  0  1  0  0  0
3 abc  22  1  0  0  0  1  0  1  0
4 abcd  0  0  0  0  0  0  0  0  0
5 b    23  1  0  0  0  1  1  0  0
6 bc   23  1  0  0  0  1  0  1  0
7 bce  23  1  0  0  0  1  0  0  0
8 bcef  0  0  0  0  0  0  0  0  0

オートマトンの状態数は最大でも $\sum |S_i| + 1$ なので、$M=\max(S_i)=10$ として、サイズ $O(KM)$ の行列積を $O(\log{N})$ 回行えば $O(K^3M^3 \log{N})$ で求められる。

で、隣接行列の作り方、特に「'abc' まで来て次に 'e' を置いたら、'abcd' にマッチする可能性は無くなったが、今度は 'bcef' の 'bce' までマッチした状態となる」という遷移 3:abc→7:bce のリンクをどのように見つけるか、である。

これは、Aho-Corasick法の failure リンクの挙動と似ている。

Aho Corasick 法 - naoyaのはてなダイアリー

failure の情報によって、現在の頂点の後ろにa～zの文字を置いたときそれぞれについて、遷移先（次に長くマッチする頂点）がどれか分かる。これで隣接行列を作ることができる。

Python3

from collections import deque
from string import ascii_lowercase


class AhoCorasick:

    def __init__(self, patterns):
        self.patterns = patterns
        self.children = [{}]
        self.match = [[]]

        for pi, pattern in enumerate(patterns):
            self._register(pi, pattern)

        self.failure = [0] * len(self.children)
        self._create_failure()

    def _register(self, pi, pattern):
        k = 0
        for c in pattern:
            if c in self.children[k]:
                k = self.children[k][c]
            else:
                j = len(self.children)
                self.children[k][c] = j
                self.children.append({})
                self.match.append([])
                k = j
        self.match[k].append(pi)

    def _create_failure(self):
        children = self.children
        match = self.match
        failure = self.failure

        q = deque(children[0].values())
        while q:
            k = q.popleft()
            b = failure[k]
            for c, j in children[k].items():
                failure[j] = self._next(b, c)
                match[j].extend(match[failure[j]])
                q.append(j)

    def _next(self, k, c):
        while True:
            if c in self.children[k]:
                return self.children[k][c]
            if k == 0:
                return 0
            k = self.failure[k]

    def search(self, target):
        match = self.match
        patterns = self.patterns

        k = 0
        matched = []
        for i, c in enumerate(target):
            k = self._next(k, c)
            matched.extend((i - len(patterns[m]) + 1, i, patterns[m]) for m in match[k])
        return matched


def mul_mat(a, b, MOD):
    n = len(a)
    res = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            for k in range(n):
                res[i][j] += a[i][k] * b[k][j]
                res[i][j] %= MOD
    return res


def pow_mat(a, p, MOD):
    n = len(a)
    res = [[0] * n for _ in range(n)]
    for i in range(n):
        res[i][i] = 1
    tmp = a
    while p:
        if (p & 1) == 1:
            res = mul_mat(res, tmp, MOD)
        tmp = mul_mat(tmp, tmp, MOD)
        p >>= 1
    return res


def solve(n, k, sss):
    MOD = 998244353
    ahc = AhoCorasick(sss)
    match = ahc.match
    v_cnt = len(match)
    arr = [[0] * v_cnt for _ in range(v_cnt)]
    is_ng = [len(match[i]) > 0 for i in range(v_cnt)]
    for i in range(v_cnt):
        if is_ng[i]:
            continue
        for c in ascii_lowercase:
            j = ahc._next(i, c)
            if is_ng[j]:
                continue
            arr[i][j] += 1

    print(arr)

    res = pow_mat(arr, n, MOD)
    ans = sum(res[0]) % MOD
    return ans


n, k = list(map(int, input().split()))
sss = [input() for _ in range(k)]
ans = solve(n, k, sss)
print(ans)

G - Children Yearn for the Evil Kindergarten

問題文

$10^{100}$ 人の園児がゲーム会場にいます。はじめはどの園児もメダルを持っていません。
園児は、脱落か脱出のいずれかをした時点で、またその時点に限り、会場を去ります。
ゲームは $N$ 日からなります。$i$ 日目 ($1 \leq i \leq N$) は以下の一連の処理を順に実行します。
- 会場にいる園児の持っているメダルをすべて回収し、その合計枚数を $s$ とおく。
- $s + A_i$ 枚のメダルを、会場にいる園児のあいだで自由に分配する(会場に園児がいない場合は何もしない)。
- 会場にいる園児のうち、メダル所持数が $B_i$ 枚未満の者は脱落する。メダル所持数が $B_i$ 枚以上の者は、メダルを $B_i$ 枚ずつ失う。
- 会場にいる園児のうち、メダル所持数が $C_i$ 枚以上の者は、各々がこのタイミングで脱出するか会場に残るかを選ぶ。
$N$ 日間が終わった時点で会場に残っている園児は、脱落します。
最終的に脱出する園児の人数としてあり得る最大値を求めてください。

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

制約

$1 \leq T \leq 3 \times 10^5$
$1 \leq N \leq 3 \times 10^5$
$1 \leq A_i \leq 10^6$
$1 \leq B_i \leq 10^6$
$1 \leq C_i \leq 10^6$
全てのテストケースにおける $N$ の総和は $3 \times 10^5$ 以下
入力される値はすべて整数

解法

何故園児がこんなデスゲームじみたことに参加しているのか。

ゲームのルールを少しわかりやすく言い換える。

メダルは管理者が一元管理する。$i$ 日目に $A_i$ 円もらえる。
とりあえずその日を脱落させず生き残らせるのに $B_i$ 円/人
生き残った人を脱出させるのにさらに $C_i$ 円/人

生き残らせる人数 $m$ を二分探索して答えを求める方針を考える。

始めに「最終的に $m$ 人生き残らせることが可能か？」と目標人数を決めてしまえば、とりあえず $m$ 人以外の人は初日で切り捨てていいので（倫理観ゼロの発言）、その日その日を必要人数分、生き残らせるコストが明確になり考えやすい。
制約から、判定問題を $O(N)$ くらいで解きたい。

脱落費用（$C_i$）が小さいときに多くの人を脱出させるのが得っぽいが、その日まで生き残らせるのに毎日コスト（$B_i$）がかかってしまう。

また、$C_i$ が安くても「必要人数を生き残らせた上で脱出させる人を最大化」という貪欲戦略はダメだということが、親切にもサンプル1で示されている。

m=5 人生き残らせることは可能？

■「必要人数を生き残らせた上で脱出させる人を最大化」戦略の場合
 A B C    残存人数  保持メダル
             5          0
16 2 3       5          6       16円もらい、5人×B=10円払う
             3          0       2×C=6 円で 2人を脱出させる
15 2 4       3          9       15円もらい、3人×B= 6円払う
             1          1       2×C=8 円で 2人を脱出させる
 1 3 5       1         -1       1円もらうが、1人×B=3円に足りない
20 5 5                          →5人を脱出させることはできない

■最適戦略
 A B C    残存人数  保持メダル
             5          0
16 2 3       5          6       16円もらい、5人×B=10円払う
             3          0       2×C=6 円で 2人を脱出させる
15 2 4       3          9       15円もらい、3人×B= 6円払う
             2          5       ★ここで、あえて1人のみ脱出させる
 1 3 5       2          0       1円もらい、2人×B=6円払う。2人とも生き残らせられる。
             2          0       ここでは脱出させられない。
20 5 5       2         10       20円もらい、2人×B=10円払う
             0          0       2×C=10円で、2人脱出させる
                                →5人を脱出させることができる。

その日毎に最適な残す人数を決めるのはなかなか難しそうなので、残す人数をキーとしたDPで、全ての場合を試す必要がありそう。

以下のDPを考える。

$\mathrm{DP}[i,j]:=i$ 日目終了後に、$j$ 人が脱出済みの場合に残っている保持メダルの最大値
- 実現不可能な $j$ は null とする

$j$ は、制約から最大 $10^6$ 程度まで取り得る。$i$ が $N$ までを取り得ることを考えると、そのまま更新するのは MLE&TLE。

だが、ひとまずは更新を考えることとする。1日で発生することは以下の通りである。

$A_i$ もらう
- null でない $\mathrm{DP}[i-1,j]$ について、$\mathrm{DP}[i,j] = \mathrm{DP}[i-1,j]+A_i$ とする
生き残らせる
- $\mathrm{DP}[i,j]$ から $B_i \times (m-j)$ を引く
脱出させる
- $T=[0,-C_i,-2C_i,-3C_i,...]$ とし、$\mathrm{DP}[i]$ と $T$ をトロピカル演算で畳み込む
- つまり、$\displaystyle \mathrm{DP}'[i,j]=\max_{p+q=j}(\mathrm{DP}[i,p]+T_q)$ とし、$\mathrm{DP}'[i,*]$ を新たな $\mathrm{DP}[i,*]$ とする。
判定する
- この時点で全ての $\mathrm{DP}[i,*]$ が負またはnullなら、$m$ 人を生き残らせることはできない。
- $\mathrm{DP}[i,m]$ が非負なら、その日で全員脱出成功。
- そうで無い場合、負の $\mathrm{DP}[i,j]$ を null にして次の日へ

         DP
 A B C   0  1  2  3  4  5    m=5
         0  -  -  -  -  -
16 2 3  16  -  -  -  -  -    A: Aiもらう
         6  -  -  -  -  -    B: Bi(m-j) 引く
         6  3  0  -  -  -    C: 畳み込む。以下繰り返し
15 2 4  21 18 15  -  -  -    A
        11 10  9  -  -  -    B
        11 10  9  5  1  -    C
 1 3 5  12 11 10  6  2  -    A
        -3 -1  1  0 -1  -    B
        -3 -1  1  0 -1  -    C
     →  -  -  1  0  -  -    ※負をnullにする
20 5 5   -  - 21 20  -  -    A
         -  -  6 10  -  -    B
         -  -  6 10  5  0    C
                        ^    C 終了時点で j=5 が非負となったので、成功

かなり複雑な更新をしなければならない。特にトロピカル演算の畳み込みは、愚直には $O(j_{\max}^2)$ の計算量がかかる。

ここで重要なのは、$\mathrm{DP}[i,*]$ に対して足されたり畳み込まれたりする数列は全て等差数列であり、全体としては、$y=\mathrm{DP}[i,x]$ にプロットした $(x,y)$ グラフは常に「上に凸な折れ線グラフ」という形状が保たれるという性質である。

これにより、「傾きとその変化点のみを保持する」という “slope trick” が使えるようになる。

slope trick (1) 解説編 | maspyのHP

slope trick では、操作はそれぞれ以下に対応する。

Aの更新（定数を足す）は、折れ線全体を $y$ 軸方向にシフトする。
Bの更新（直線を足す）は、全ての折れ線の傾きを一定値だけ増減させる。
Cの更新（直線とmax畳み込み）は、折れ線の傾きの下限を、直線の傾きに揃える。

また特に本問題では「判定のタイミングで負となった $j$ は無効」としなければならない。
1日の終わりに負である $j$ は、次の日に $A_i$ もらって正になっても、無効として扱わなければならない。

よって、例えば以下の情報で管理する。

$last$: $x$ 座標を正方向に変化させていったとき、$y$ が一度非負になってから、再び負に入る直前の $x$ 座標
$S_l$: $x=last$ の時の $y$ 座標
$stack$: $x=0～last$ にかけての変化点の $(傾きd', 次の変化点またはlastまでの長さ l)$ を積んだリスト
$offset$: 傾きに一律加算する値。stack内に記録された傾き $d'$ に対して、$d'+offset$ がその時点の真の傾きとなる

まず、A,Bの更新は、以下で実現できる。

$S_l+=A_i-B_i(m-last)$
$offset+=B_i$

Cの更新および判定は、

stack の末尾から、$d'+offset \le -C_i$ であるものをpopしていく。それに伴い、$last, S_l$ も更新していく。
- この時点で $S_l \ge 0$ なら、$k=\lfloor S_l/C_i \rfloor$ として、$(-C_i-offset, k)$ をstackに追加する。
$S_l \lt 0$ なら、非負になるまで続けて pop する。
- stack が空になっても非負なら、全てが負になっているということ。実現不可能が確定。
- 途中で非負になったら、最後にpopした直線の真の傾きを $d$ とし、$k=\lfloor S_l/-d \rfloor$ として、$(d-offset, k)$ をstackに追加する。
$last=m$ なら、その日で $m$ 人全員脱出成功。
そうで無い場合、次の日へ

これで、$O(N)$ で判定できる。

Python3

import sys

input = sys.stdin.buffer.readline


def solve(n, abc):
    def check(n, abc, k):
        s0 = 0
        sl = 0
        last = 0
        offset = 0
        stack = []
        for i in range(n):
            a, b, c = abc[i]
            s0 += a - b * k
            sl += a - b * (k - last)
            offset += b
            c = -c
            while len(stack) > 0 and stack[-1][0] + offset <= c:
                d, l = stack.pop()
                d += offset
                sl -= d * l
                last -= l

            # print(f'A {s0=} {sl=} {last=} {offset=} {stack=}')

            while len(stack) > 0 and sl < 0:
                c, l = stack.pop()
                c += offset
                sl -= c * l
                last -= l

            # print(f'B {s0=} {sl=} {last=} {offset=} {stack=}')

            if sl < 0:
                return False

            nl = sl // -c
            if nl > 0:
                stack.append((c - offset, nl))
                last += nl
                sl += c * nl

            # print(f'C {s0=} {sl=} {last=} {offset=} {stack=} {nl=}')

            if last >= k:
                return True

        return last >= k

    l = 0
    r = 1 << 20
    while l + 1 < r:
        mid = (l + r) // 2
        if check(n, abc, mid):
            l = mid
        else:
            r = mid
    return l


t = int(input())
for _ in range(t):
    n = int(input())
    abc = [list(map(int, input().split())) for _ in range(n)]
    ans = solve(n, abc)
    print(ans)

目次

SMBCプログラミングコンテスト #1（AtCoder Beginner Contest 458）F,G問題メモ

F - Critical Misread

問題文

制約

解法

G - Children Yearn for the Evil Kindergarten

問題文

制約

解法