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

AtCoder Beginner Contest 391

E - Hierarchical Majority Vote

問題文

長さ $3^n \; (n \geq 1)$ の $01$ 列 $B=B_1 B_2 \dots B_{3^n}$ に対して、長さ $3^{n-1}$ の $01$ 列 $C=C_1 C_2 \dots C_{3^{n-1}}$ を得る操作を以下のように定めます。
- $B$ の要素を $3$ つずつまとめて多数決を取る。すなわち、$i=1,2,\dots,3^{n-1}$ について、$B_{3i-2},B_{3i-1},B_{3i}$ のうち最も多く現れる値を $C_i$ とする。

長さ $3^N$ の $01$ 列 $A = A_1 A_2 \dots A_{3^N}$ が与えられます。$A$ に上の操作を $N$ 回適用して得られる長さ $1$ の列を $A' = A'_1$ とします。
$A$ の要素のいくつかを $0$ から $1$ または $1$ から $0$ へ変えることを考えたとき、$A$ の要素を最小で何個変えれば、$A'_1$ の値が変わるか求めてください。

制約

$N$ は $1$ 以上 $13$ 以下の整数
$A$ は $0,1$ からなる長さ $3^N$ の文字列

解法

各段階で多数決を取る3つ組を子、その結果を親とする完全3分木をイメージする。

         １             ← 最終的な A'
    ／   ｜   ＼
  ０     １     １
 /｜\   /｜\   /｜\
０１０ ０１１ １０１    ← 初期状態の A

以下の木DPをする。

$\mathrm{DP}[v]:=(b,c)$
- $b=$ 自身の値（0/1）
- $c=$ 自身の値を変えるのに、初期状態から変える必要がある最小個数

一番下の層から上に向かって求めていく。
一番下の層の左から $i$ 番目の葉の値は $(A_i,1)$ である。

子を持つ頂点の値を求める。$b$ は自明として、$c$ は以下のようになる。

$3$ つの子の $b$ が全て同じ値なら、$c$ の小さい方から2つの和
$3$ つの子の $b$ が1対2なら、多い方の $c$ の小さい方

$\mathrm{DP}[根]$ の $c$ の値が答えとなる。

Python3

def solve(n, aaa):
    bbb = [(a, 1) for a in aaa]
    for i in range(n - 1, -1, -1):
        ccc = []
        for j in range(3 ** i):
            ac0, ac1, ac2 = sorted(bbb[3 * j:3 * j + 3])
            a0, c0 = ac0
            a1, c1 = ac1
            a2, c2 = ac2
            if a0 == 1:
                ccc.append((1, c0 + c1))
            elif a1 == 1:
                ccc.append((1, c1))
            elif a2 == 1:
                ccc.append((0, c0))
            else:
                ccc.append((0, c0 + c1))
        bbb = ccc
    return bbb[0][1]


n = int(input())
aaa = list(map(int, input()))
ans = solve(n, aaa)
print(ans)

F - K-th Largest Triplet

問題文

長さ $N$ の整数列 $A=(A_1,A_2,\ldots,A_N), B=(B_1,B_2,\ldots,B_N),C=(C_1,C_2,\ldots,C_N)$ および整数 $K$ が与えられます。
$1\leq i,j,k\leq N$ を満たす整数 $i,j,k$ の選び方 $N^3$ 通りそれぞれに対して $A_iB_j+B_jC_k+C_kA_i$ の値を計算したとき、その中で大きい方から $K$ 番目の値を求めてください。

制約

$ 1\leq N\leq 2\times 10^5$
$ 1\leq K\leq \min(N^3,5\times 10^5)$
$1\leq A_i,B_i,C_i\leq 10^9$
入力は全て整数

解法

$f(i,j,k)=A_iB_j+B_jC_k+C_kA_i$ とする。
式変形とかしたくなるような形だが、あんまり関係ない。

式が単調性を持つことと、$K$ が大きくないことが鍵。
単調性: $A_p \ge A_q$ なら $f(p,j,k) \ge f(q,j,k)$ となる性質。他の変数に関しても同様。

$A,B,C$ を降順ソートすると、$f(1,1,1)$ が必ず最大値となり、次に大きいのは $f(2,1,1),f(1,2,1),(1,1,2)$ のいずれかとなる。
（同じ値になることはあっても）これらを飛び越えて $f(2,2,1)$ や $f(1,3,1)$ の方が大きくなる、ということはない。

よって、優先度付きキューで $(f(i,j,k),i,j,k)$ を大きい順に取り出し、$i,j,k$ のいずれかを+1したものを（追加していなければ）追加する、ということを $K$ 回繰り返せば、$K$ 回目に取り出される値が答えとなる。

Python3

import os
import sys
from heapq import heappop, heappush

import numpy as np


def solve(inp):
    n, t = inp[:2]
    aaa = inp[2:2 + n]
    bbb = inp[2 + n:2 + n + n]
    ccc = inp[2 + n + n:]

    def get(i, j, k):
        return -(aaa[i] * bbb[j] + bbb[j] * ccc[k] + ccc[k] * aaa[i])

    aaa.sort()
    bbb.sort()
    ccc.sort()
    aaa = aaa[::-1]
    bbb = bbb[::-1]
    ccc = ccc[::-1]
    checked = {(0, 0, 0)}
    q = [(get(0, 0, 0), 0, 0, 0)]
    for _ in range(t - 1):
        v, i, j, k = heappop(q)
        if i == n - 1 or (i + 1, j, k) in checked:
            pass
        else:
            heappush(q, (get(i + 1, j, k), i + 1, j, k))
            checked.add((i + 1, j, k))
        if j == n - 1 or (i, j + 1, k) in checked:
            pass
        else:
            heappush(q, (get(i, j + 1, k), i, j + 1, k))
            checked.add((i, j + 1, k))
        if k == n - 1 or (i, j, k + 1) in checked:
            pass
        else:
            heappush(q, (get(i, j, k + 1), i, j, k + 1))
            checked.add((i, j, k + 1))

    return -q[0][0]


SIGNATURE = '(i8[:],)'
if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', SIGNATURE)(solve)
    cc.compile()
    exit()

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

    solve = njit(SIGNATURE, cache=True)(solve)
    print('compiled', file=sys.stderr)

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

G - Many LCS

問題文

長さ $N$ の英小文字列 $S$ および整数 $M$ が与えられます。各 $k=0,1,\ldots,N$ に対して以下の問題を解いてください。
長さ $M$ の英小文字列は $26^M$ 通りあるが、そのうち $S$ との最長共通部分列の長さが $k$ であるようなものの個数を $998244353$ で割った余りを求めよ。

制約

$ 1\leq N\leq 10$
$ 1\leq M\leq 100$
$N,M$ は整数
$S$ は長さ $N$ の英小文字列

解法

DPの値を状態に持つDP。

$S,T$ が所与の時の一般的なLCS長は、以下のDPで求められる。（$i,j$ を添字に持ち、$k$ を値とする方法もある）

$\mathrm{DP_{basic}}[i,k]:=T[:i]$ と $S[:j]$ から長さ $k$ の共通部分列が作れるとき、$j$ の取り得る最小値
- $T[:i]$ は $T$ の先頭 $i$ 文字を表すとする。$S[:j]$ も同様。

つまり、$\mathrm{DP}[i]$ は、添字 $k$ に対する数列となる。

今回はこの数列を値に持ち、以下のようにする。

$\mathrm{DP}[i,L]:=\mathrm{DP_{basic}}[i] = L$ となるような長さ $i$ の文字列の個数

$L$ は性質上、狭義単調増加であり、$1～N$ が含まれるか含まれないかなので、$2^N$ 通りの状態しかない。
DPの状態数は $O(2^NM)$ となる。

$\mathrm{DP}[i-1,L]$ から $\mathrm{DP}[i,*]$ への遷移を考える。
これは $i$ 文字目に「$S$ に出てくるどれか1文字を置く」「それ以外の文字を置く」の、最大 $N+1$ 通りを全て試せばよい。

置く文字を決めると、一般的なLCS長のDPに基づき、$O(N)$ で $L$ を更新できる。
置く文字を $a$ とした時の更新後の $L$ を $L_a$ とし、$\mathrm{DP}[i,L_a] += \mathrm{DP}[i-1,L]$ と遷移する。
$S$ に出てこない文字の場合は $L$ は更新されないので、$\mathrm{DP}[i,L] += \mathrm{DP}[i-1,L] \times (出てこない文字数)$ となる。

$\alpha=\min(N,文字の種類数)$ として、$O(2^NN\alpha M)$ で全て求められる。

Python3

from collections import defaultdict


def solve(n, m, s):
    MOD = 998244353
    s = [ord(c) - 97 for c in s]

    pos = defaultdict(list)
    for i, c in enumerate(s, start=1):
        pos[c].append(i)
    for ls in pos.values():
        ls.sort(reverse=True)
    others = 26 - len(pos)

    dp = {(0,): 1}
    for _ in range(m):
        ndp = defaultdict(int)
        for sdp, pattern in dp.items():
            for ls in pos.values():
                ldp = list(sdp)
                if ls[0] > ldp[-1]:
                    ldp.append(ls[0])
                i = len(ldp) - 1
                for j in ls:
                    while ldp[i] >= j:
                        i -= 1
                    ldp[i + 1] = min(ldp[i + 1], j)
                tdp = tuple(ldp)
                ndp[tdp] += pattern
                ndp[tdp] %= MOD
            ndp[sdp] += pattern * others
            ndp[sdp] %= MOD
        dp = ndp

    ans = [0] * (n + 1)
    for sdp, pattern in dp.items():
        ans[len(sdp) - 1] += pattern
    for i in range(n + 1):
        ans[i] %= MOD
    return ans


n, m = map(int, input().split())
s = input()
ans = solve(n, m, s)
print(*ans)

目次

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

E - Hierarchical Majority Vote

問題文

制約

解法

F - K-th Largest Triplet

問題文

制約

解法

G - Many LCS

問題文

制約

解法