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

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