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

AtCoder Beginner Contest 433

E - Max Matrix 2

問題文

長さ $N$ の整数列 $X=(X_1,X_2,\ldots,X_N)$ 、長さ $M$ の整数列 $Y=(Y_1,Y_2,\ldots,Y_M)$ が与えられます。
以下の条件を全て満たす $N$ 行 $M$ 列の整数行列 $A=(A_{i,j})$ $(1\le i\le N,\ 1\le j\le M)$ が存在するか判定し、存在する場合は一つ求めてください。
- $A$ には $1～NM$ の整数が1つずつ存在する
- $i=1,2,\ldots,N$ に対し $\displaystyle \max_{1\le j\le M} A_{i,j} = X_i$ が成り立つ
- $j=1,2,\ldots,M$ に対し $\displaystyle \max_{1\le i\le N} A_{i,j} = Y_j$ が成り立つ

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

制約

$1\le T\le 10^5$
$1\le N,M$
全てのテストケースにおける $N\times M$ の総和は $2\times 10^5$ 以下
$1\le X_i,Y_j\le N\times M$
入力される値は全て整数

解法

手で解く分には何となくできるが、正確にコードに落とし込むのがちょっと手間取る。

とりあえず簡単に分かるコーナーとして、$X,Y$ に同じ値が2回以上出てきたら不可能。

その他の場合、大きい方から位置を確定させていく。

$F=\{i_1,i_2,...\}$: 最大値を埋め終わり、その行の他の列は何を埋めても $X_i$ に矛盾しない、という行の集合
$G=\{j_1,j_2,...\}$: 最大値を埋め終わり、その列の他の行は何を埋めても $Y_j$ に矛盾しない、という列の集合
$H=\{(i_1,j_1),(i_2,j_2),...\}$: 行も列も最大値を埋め終わり、何を置いてもよい位置の集合

埋めようとしている値が、$X,Y$ に含まれるかで場合分けする。

$X$ にも $Y$ にも含まれる場合、位置は一意に決まる。（$i,j$ とする）
- $H$ に、$\{(i,k)|k \in G\}$ と $\{(k,j)|k \in F\}$ を追加する。
- $F$ に $i$ を追加する。
- $G$ に $j$ を追加する。
$X$ のみに含まれる場合（$i$ とする）
- $G$ が空なら不可能。
- $G$ が空でなければ、適当に $j$ を1つ選んで埋める。
  - $H$ に、$\{(i,k)|k \in G\}$ を追加する。
  - $F$ に $i$ を追加する。
$Y$ のみに含まれる場合（$j$ とする）
- $F$ が空なら不可能。
- $F$ が空でなければ、適当に $i$ を1つ選んで埋める。
  - $H$ に、$\{(k,j)|k \in F\}$ を追加する。
  - $G$ に $j$ を追加する。
どちらにも含まれない場合
- $H$ が空なら不可能。
- $H$ が空でなければ、1つpopして埋める。

Python3

def solve(n, m, xxx, yyy):
    if len(set(xxx)) != n:
        return None
    if len(set(yyy)) != m:
        return None

    pos_x = {x: i for i, x in enumerate(xxx)}
    pos_y = {y: i for i, y in enumerate(yyy)}
    ans = [[-1] * m for _ in range(n)]
    free_i = []
    free_j = []
    free_ij = []
    for a in range(n * m, 0, -1):
        if a in pos_x:
            i = pos_x[a]
            if a in pos_y:
                j = pos_y[a]
                ans[i][j] = a
                for nj in free_j:
                    if ans[i][nj] == -1:
                        free_ij.append((i, nj))
                for ni in free_i:
                    if ans[ni][j] == -1:
                        free_ij.append((ni, j))
                free_i.append(i)
                free_j.append(j)
            elif free_j:
                j = free_j[0]
                ans[i][j] = a
                for nj in free_j:
                    if ans[i][nj] == -1:
                        free_ij.append((i, nj))
                free_i.append(i)
            else:
                return None
        elif a in pos_y:
            j = pos_y[a]
            if free_i:
                i = free_i[0]
                ans[i][j] = a
                for ni in free_i:
                    if ans[ni][j] == -1:
                        free_ij.append((ni, j))
                free_j.append(j)
            else:
                return None
        elif free_ij:
            i, j = free_ij.pop()
            ans[i][j] = a
        else:
            return None

    return ans


t = int(input())
for _ in range(t):
    n, m = list(map(int, input().split()))
    xxx = list(map(int, input().split()))
    yyy = list(map(int, input().split()))
    ans = solve(n, m, xxx, yyy)
    if ans is None:
        print('No')
    else:
        print('Yes')
        for row in ans:
            print(*row)

F - 1122 Subsequence 2

問題文

数字からなる文字列 $S$ が与えられます。
以下の条件を全て満たす文字列 $T$ を 1122文字列と呼びます。
- $T$ は数字からなる空でない文字列
- $|T|$ は偶数
- $T$ の $1$ 文字目から $\frac{|T|}2$ 文字目までは全て同じ数字である
- $T$ の $\frac{|T|}2+1$ 文字目から $|T|$ 文字目までは全て同じ数字である
- $T$ の $1$ 文字目の数字に $1$ を足すと $|T|$ 文字目の数字になる
例えば 1122 や 01 、 444555 などは 1122文字列ですが、 1222 や 90 は 1122文字列ではありません。
$S$ の（連続でなくても良い）部分列であって 1122文字列であるものの個数を $998244353$ で割ったあまりを求めてください。
ただし、ある二つの部分列が文字列として同じでも、取り出された位置が異なるならばそれらは別々に数えるものとします。

制約

$S$ は長さ $1$ 以上 $10^6$ 以下の数字からなる文字列

解法

コンテストのナンバリング(ABC433の433など)に基づく問題テーマはあるが、開催日(11/22)に基づく問題テーマは少し珍しい？

数字毎に、以下を前計算しておく。

$F(d,i):=$ 数字 $d$ が、先頭から $S_i$ までに登場した回数
$B(d,i):=$ 数字 $d$ が、末尾から $S_i$ までに登場した回数

$i$ ごとに、「$S_i$ を $\frac{|T|}{2}$ 文字目（前半の最後の文字）として使うような1122文字列の個数」を数える。
境界となる文字を1つ固定することで、同じものが重複して数えられてしまうのを防いでいる。

$i$ を固定した時に作れる最長の1122文字列は、以下の小さい方による。

$F(S_i,i)$: $i$ 以前から $S_i$ を取れる最大個数
$B(S_i+1,i+1)$: $i+1$ 以降から $S_i+1$ を取れる最大個数
※文字が多くてややこしいので、以降、前者を $l$、後者を $r$ とする。

$k=1,2,...,\min(l,r)$ について、$2k$ の長さを持つ1122文字列が、以下の個数だけ作れる。

$\dbinom{l-1}{k-1} \times \dbinom{r}{k}$

これを全て合計すると答えなのだが、$k$ を全て探索すると $O(|S|^2)$ となってTLEする。

二項係数のこうした計算って、なんか上手いこと綺麗な形になることが多い。
小さい $l,r$ で愚直に計算した結果を観察すると、どうやら以下と等しくなることが分かる。

$\dbinom{l+r-1}{l}$
※ただし、$r=0$ の時は $0$

※この式変形は、ヴァンデルモンドの畳み込みと呼ばれる。

これで階乗の前計算の元、$O(|S|)$ に落ちたので、間に合う。

Python3

def precompute_factorials(n, MOD):
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f = f * m % MOD
        factorials.append(f)
    f = pow(f, MOD - 2, MOD)
    finvs = [1] * (n + 1)
    finvs[n] = f
    for m in range(n, 1, -1):
        f = f * m % MOD
        finvs[m - 1] = f
    return factorials, finvs


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

    fwd = [[0] * (n + 1) for _ in range(10)]
    bwd = [[0] * (n + 1) for _ in range(10)]
    for i in range(n):
        a = aaa[i]
        for j in range(10):
            fwd[j][i] = fwd[j][i - 1]
        fwd[a][i] += 1
    for i in range(n - 1, -1, -1):
        a = aaa[i]
        for j in range(10):
            bwd[j][i] = bwd[j][i + 1]
        bwd[a][i] += 1

    MOD = 998244353
    facts, finvs = precompute_factorials(n, MOD)

    def ncr(n, r):
        return facts[n] * finvs[r] % MOD * finvs[n - r] % MOD

    ans = 0
    for i in range(n):
        a = aaa[i]
        if a == 9:
            continue
        l = fwd[a][i]
        r = bwd[a + 1][i]
        if r >= 1:
            ans += ncr(l + r - 1, l)
            ans %= MOD
    return ans


s = input()
ans = solve(s)
print(ans)

G - Substring Game

問題文

英小文字からなる文字列 $S$ が与えられます。
Alice と Bob がこの文字列を使って以下のようなゲームを行います。
- 空文字列 $T$ を用意する。
- Alice から始めて両者は交互に手番をプレイする。
- 各手番では、プレイヤーは英小文字を一つ選び、 $T$ の末尾に選んだ英小文字を連結させる。ただし、連結させた後の $T$ が $S$ の部分文字列とならないような行動を取ることはできない。
先に手番をプレイできなくなったプレイヤーの負けです。
両者が最善を尽くしたとき、どちらのプレイヤーが勝つかを求めてください。

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

制約

$1\le T\le 10^5$
$T$ は整数
$S$ は英小文字からなる長さ $1$ 以上 $2\times 10^5$ 以下の文字列
全てのテストケースにおける $S$ の長さの総和は $4\times 10^5$ 以下

解法

手番がプレイできなくなるのは、$T$ が $S$ の末尾から何文字かと一致した時に限られる。
それ以外の場合は文字を付け足すことはできる（既に勝敗が決していて消化試合となっているとかはともかく）。

今の $T$ が、何通りの末尾文字列に派生しうるか、付け足せる文字の候補は何があるか、が知りたい。

Suffix Array と Longest Common Prefix を使えばよさそうである。

LCP配列の構築アルゴリズムたち #データ構造 - Qiita

SAとLCPを構築すると、以下のような情報が分かる。

S:aaabbccabaaccabbc

Win:各文字列で終了した場合、文字数の偶奇から 0:先手勝利 1:後手勝利 のどちらになるか
| LCP:次の文字列と先頭何文字一致しているか
| | 接尾辞を辞書順に並べたもの
v v ~~v~~~~~~~~~~~~~~
0 2 aaabbccabaaccabbc
1 2 aabbccabaaccabbc
1 1 aaccabbc
1 2 abaaccabbc
1 4 abbc               *
0 1 abbccabaaccabbc
0 0 accabbc
0 1 baaccabbc
0 3 bbc                *
1 1 bbccabaaccabbc
1 2 bc                 *
0 0 bccabaaccabbc
0 1 c                  *
0 3 cabaaccabbc
0 1 cabbc
1 4 ccabaaccabbc
1   ccabbc

このうち、「LCPと接尾辞の長さが一致しているもの（* をつけたもの）」は、取り除いてよい。
今回のルールでは、自分の手番で $T$ に付け足せる場合は何らかの文字を付け足さないといけないので、 * は「その接尾辞で終了する」ことができない。（後で考えると、取り除かなくてもアルゴリズム上は問題なかったが）

0 2 aaabbccabaaccabbc
1 2 aabbccabaaccabbc
1 1 aaccabbc
1 2 abaaccabbc
0 1 abbccabaaccabbc
0 0 accabbc
0 1 baaccabbc
1 1 bbccabaaccabbc
0 0 bccabaaccabbc
0 3 cabaaccabbc
0 1 cabbc
1 4 ccabaaccabbc
1   ccabbc

そしたら、LCPの大きいものから順にマージしていく。
最も大きいのは、LCP=4 の以下の部分である。

1 4 ccabaaccabbc
1   ccabbc

仮にこのLCPまで $T$ が構築され、$T=ccab$ という状況になったとき、次の1手で確実にどちらかに分岐する。次の手番はLCPの偶奇によって、偶:先手、奇:後手であるとわかる。（この例では先手）

先手の場合、マージ結果は次の遷移先に Win=0 があったら勝ち（マージ後のWinも $0$）。無ければ負け（マージ後のWinは $1$）となる。

後手の場合、マージ結果は次の遷移先に Win=1 があったら勝ち、無ければ負けとなる。

この例では、マージ対象のいずれの Win も $1$ であり、ccab になった時点で後手の勝ちが確定している。
先手は a,b のどちらを付け足そうと負けである。
よって、マージ結果は Win=1 になる。

0 2 aaabbccabaaccabbc
1 2 aabbccabaaccabbc
1 1 aaccabbc
1 2 abaaccabbc
0 1 abbccabaaccabbc
0 0 accabbc
0 1 baaccabbc
1 1 bbccabaaccabbc
0 0 bccabaaccabbc
0 3 cabaaccabbc
0 1 cabbc
1   ccab...  ←マージ

次、LCP=3 の部分は、今度は後手が次の手番となる。

0 3 cabaaccabbc
0 1 cabbc

こちらも、手番は後手だが $T=cab$ になった時点で先手勝ちが確定しており、マージ結果も Win=0 となる。

0 2 aaabbccabaaccabbc
1 2 aabbccabaaccabbc
1 1 aaccabbc
1 2 abaaccabbc
0 1 abbccabaaccabbc
0 0 accabbc
0 1 baaccabbc
1 1 bbccabaaccabbc
0 0 bccabaaccabbc
0 1 cab...    ←マージ
1   ccab...

次、LCP=2 である中の1つ、以下のマージは、先手が自分が勝利できる方（abb…）を選択できるので、先手勝ちである。

1 2 abaaccabbc
0 1 abbccabaaccabbc

このようにしてどんどんマージしていく。LCPが同じものは、好きな順でマージしてよい。

0 1 aa...
0 1 ab...
0 0 accabbc
0 1 baaccabbc
1 1 bbccabaaccabbc
0 0 bccabaaccabbc
0 1 cab...
1   ccab...
↓
0 0 a...
1 0 b...
1   c...
↓
0   ...

最終的に1つになったマージ結果の Win によって答えが分かる。この例の場合は先手勝ちとなる。

Python3

from operator import itemgetter

from atcoder.string import suffix_array, lcp_array


def solve(s):
    n = len(s)
    ss = [ord(c) - 97 for c in s]
    sa = suffix_array(ss, 26)
    lcp = lcp_array(ss, sa)
    win = []
    true_lcp = []
    for si in range(n - 1):
        i = sa[si]
        if lcp[si] == n - i:
            continue
        win.append((n - i - 1) % 2)
        true_lcp.append(lcp[si])
    win.append((n - sa[-1] - 1) % 2)
    m = len(win)
    lll = list(range(-1, m - 1))
    rrr = list(range(1, m + 1))
    merge_order = sorted(enumerate(true_lcp), key=itemgetter(1), reverse=True)
    for si, k in merge_order:
        ll = lll[si]
        lr = rrr[si]
        rl = lll[lr]
        assert rl == si
        if win[si] != win[lr]:
            win[lr] = k % 2
        lll[lr] = ll
        rrr[ll] = lr
    return win[-1] == 0


t = int(input())
for _ in range(t):
    s = input()
    ans = solve(s)
    if ans:
        print('Alice')
    else:
        print('Bob')

目次

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

E - Max Matrix 2

問題文

制約

解法

F - 1122 Subsequence 2

問題文

制約

解法

G - Substring Game

問題文

制約

解法