AtCoder Beginner Contest 468 D,E,F,G問題メモ

AtCoder Beginner Contest 468

D - Pre-Palindrome

問題文

以下の条件を満たす英小文字からなる文字列を良い文字列とします。
- $1$ 文字以下を書き換えることで回文にすることができる。
- 例えば a、iwai、abcdcza などは良い文字列ですが、abcd、atcoder などは良い文字列ではありません。特に、回文も良い文字列であることに注意してください。
英小文字からなる文字列 $S$ が与えられます。
$S$ の空でない部分文字列（連続な部分列）であって良い文字列であるものの個数を求めてください。
$2$ つの部分文字列は、$S$ から取り出す場所が異なれば文字列として等しくても区別して数えることに注意してください。

制約

$S$ は英小文字からなる長さ $1$ 以上 $10^4$ 以下の文字列

解法

$O(N^2)$ が通るので、各文字・または2文字を中心としたときにどこまで伸ばせるかを愚直に調べて合計すればよい。

範囲外参照にならないよう index を適切に打ち切る点に注意する程度で、最近のDの中では簡単め？

Python3

def solve(s):
    n = len(s)
    ans = 0
    for i in range(n):
        diff = 0
        for j in range(i + 1):
            if i + j >= n:
                break
            if s[i - j] == s[i + j]:
                ans += 1
            elif diff == 1:
                break
            else:
                diff += 1
                ans += 1
        if i == n - 1:
            break
        diff = 0
        for j in range(i + 1):
            if i + j + 1 >= n:
                break
            if s[i - j] == s[i + j + 1]:
                ans += 1
            elif diff == 1:
                break
            else:
                diff += 1
                ans += 1
    return ans


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

発展

$O(N \log{N})$ でも解ける。ローリングハッシュを用いる。

適当な base と mod を決め、→方向と←方向にローリングハッシュを計算しておく。
base の pow, inv_pow も前計算しておくと、任意区間・任意方向のローリングハッシュ値を $O(1)$ で得られる。

こうすれば、「$i$ から左 $k$ 文字と、$j$ から右 $k$ 文字は一致しますか」が $O(1)$ で調べられる。
$k$ を二分探索することで、中心 $c$ から最初に左右で文字が異なる箇所を得られ、そこからもう一度二分探索すれば、1文字変更可能なときの答えが求められる。

変更可能な文字数 $k$ に対しても汎用化でき、$O(Nk\log{N})$ で求められる。

Python3

import random


def solve(s):
    n = len(s)
    MOD = (1 << 61) - 1
    base = random.randrange(1 << 20, 1 << 40)
    aaa = list(map(ord, s))

    # pw[i]=base^i, ipw[i]=base^-i
    pw = [1] * (n + 1)
    ipw = [1] * (n + 1)
    ib = pow(base, MOD - 2, MOD)
    for i in range(n):
        pw[i + 1] = pw[i] * base % MOD
        ipw[i + 1] = ipw[i] * ib % MOD

    # fh: →方向、bh: ←方向のローリングハッシュ
    fh = [0] * (n + 1)
    bh = [0] * (n + 1)
    for i, a in enumerate(aaa):
        fh[i + 1] = (fh[i] + a * pw[i]) % MOD
        bh[i + 1] = (bh[i] + a * ipw[i]) % MOD

    def right(j, k):
        """s[j],s[j+1],...,s[j+k-1] のハッシュ"""
        return (fh[j + k] - fh[j]) * ipw[j] % MOD

    def left(i, k):
        """s[i],s[i-1],...,s[i-k+1] のハッシュ"""
        return (bh[i + 1] - bh[i - k + 1]) * pw[i] % MOD

    def extend(i, j):
        """s[i-t]==s[j+t] が成り立つ t の個数。i から左、j から右に伸ばせる長さ"""
        ok = 0
        ng = min(i + 1, n - j) + 1
        while ng - ok > 1:
            k = (ok + ng) // 2
            if left(i, k) == right(j, k):
                ok = k
            else:
                ng = k
        return ok

    def count(i, j):
        """(i,j) を対の起点として、不一致1個まで許して広げられる回数"""
        k = extend(i, j)
        i -= k
        j += k
        if i < 0 or j >= n:  # 端に到達したら変更する相手がいない
            return k
        return k + 1 + extend(i - 1, j + 1)  # 不一致の1対を飛ばして再度二分探索

    ans = n  # 長さ1の部分文字列
    for c in range(n):
        ans += count(c - 1, c + 1)  # 奇数長の中心
        if c + 1 < n:
            ans += count(c, c + 1)  # 偶数長の中心
    return ans


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

E - Sum of Average

問題文

正整数 $N$ と長さ $N$ の整数列 $A=(A_1,A_2,\ldots,A_N)$ が与えられます。
$f(l,r)$ を $A_l,A_{l+1},\ldots,A_r$ の（算術）平均として定義します。
$\displaystyle \sum_{1\le l\le r\le N} f(l,r)$ を $\text{mod }{998244353}$ で求めてください。

制約

$1\le N\le 5\times 10^5$
$0\le A_i \lt 998244353$
入力される値は全て整数

解法

主客転倒。各 $A_i$ が答えに寄与する係数を求める。

区間 $[l,r)$ に $i$ が含まれる場合、区間長 $w=r-l$ として、$A_i$ は $\dfrac{1}{w}$ 倍だけ平均値に影響、ひいては最終的な答えに寄与する。

よって、$i$ について、長さ $w=1,2,...,N$ の区間で $i$ を含むものがそれぞれ何個あるかがわかればいい。
「$f_i(w):=i$ を含む長さ $w$ の区間が何個あるか」として、$i$ についての寄与は以下となる。

$\displaystyle \sum_{w=1}^{N}f_i(w)\frac{A_i}{w}$

ただ、これを愚直に調べると $O(N^2)$ である。各 $i$ 対し、$w$ を集約した係数、つまり $\displaystyle \sum_{w=1}^{N}f_i(w)\frac{1}{w}$ を、適切な前計算の元で高速に求めたい。

$w$ を増やしていったとき、$f_i(w)$ が規則的な変化をすることを利用する。

N=8  i=3
_ _ o _ _ _ _ _

w   1  2  3  4  5  6  7  8
fi  1  2  3  3  3  3  2  1
    ~~(a)~~  ~(b)~ ~~(c)~~

(a): 左右いずれか近い方が端に到達するまでは、$f_i(w)$ は $1$ ずつ増える。
(b): 一方が端に到達したら、同じ値を続ける
(c): もう一方が端に到達したら、$1$ ずつ減る。

よって、

(a): $1 \times \dfrac{1}{1} + 2 \times \dfrac{1}{2} + ... + k \times \dfrac{1}{k}$
(b): 区間和 $\dfrac{1}{l}+\dfrac{1}{l+1}+...+\dfrac{1}{r}$
(c): $1 \times \dfrac{1}{N} + 2 \times \dfrac{1}{N-1} + ... + k \times \dfrac{1}{N-k+1}$

のそれぞれを前計算しておけばよい。（(a)は前計算するまでも無く、$k$）

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(n, aaa):
    MOD = 998244353
    facts, finvs = precompute_factorials(n, MOD)
    invs = [0] * (n + 1)
    for i in range(1, n + 1):
        invs[i] = facts[i - 1] * finvs[i] % MOD

    acc_invs = [0] * (n + 1)
    for i in range(1, n + 1):
        acc_invs[i] = (acc_invs[i - 1] + invs[i]) % MOD

    rev_acc_i_invs = [0] * (n + 1)
    for i in range(1, n + 1):
        rev_acc_i_invs[i] = (rev_acc_i_invs[i - 1] + i * invs[-i]) % MOD

    ans = 0
    for i in range(n):
        a = aaa[i]
        l = i + 1
        r = n - i
        if l > r:
            l, r = r, l
        coef = (l + rev_acc_i_invs[l] + l * (acc_invs[r - 1] - acc_invs[l])) % MOD
        ans += a * coef
        ans %= MOD
    return ans


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

F - Chmax

問題文

正整数 $N$ と $(1,2,\ldots,N)$ の並び替え $P=(P_1,P_2,\ldots,P_N)$ が与えられます。
変数 $x,y,c$ があります。はじめ $x=y=c=0$ です。
あなたは $k=1,2,\ldots,N$ の順に以下の操作のいずれかを行います：
- 操作 $1$：$x \lt P_k$ ならば $c$ を $1$ 増やす。その後、$x$ を $\max(x,P_k)$ に置き換える。
- 操作 $2$：$y \lt P_k$ ならば $c$ を $1$ 増やす。その後、$y$ を $\max(y,P_k)$ に置き換える。
最終的な $c$ の値の最大値を求めてください。

制約

$1\le N\le 5\times 10^5$
$P$ は $(1,2,\ldots,N)$ の並び替え
入力される値は全て整数

解法

最長増加部分列の発展問題。

はじめ、「$P$ から増加部分列を2系統取って、その長さの合計の最大値」が答えかと思ったが、これだとWAとなる。

N = 7
P = (7, 4, 5, 6, 1, 2, 3)

増加部分列を2系統取ったら (4,5,6) と (1,2,3) が最大で長さ計 6 だが、
実際は、P1=7 で x,y のどちらかは更新しなければならない。
それを考慮すると、正解は 4 となる。

必ず $x,y$ のいずれかは更新しなければならないのが厄介で、「捨てる」ことができない。
特に、最大値 $P_m=N$ 以降は、実質、1系統はロックされ得点の機会はない。

$N$ で更新される直前、$m-1$ までの状態で、$x,y$ のどちらを $N$ で更新すればいいかというと、全体を低く保つ方がいいので、大きい方を更新するのが最適（★）である。
対称的なので、$x$ の方とする。この時、$x=\max(P_1,...,P_{m-1})$ である。この位置を $j$ とすると、$j+1～m-1$ の間は、$x$ 側で得点することはできないことになる。

再帰的に同じことが言える。$x$ の得点機会は、$i=1,...,m$ のうち最大値を更新する箇所ということになる。

                m
P = 3 6 5 2 7 8 9 1 4
    ~ ~     ~ ~ ~      ←x側で得点できるところ

前述の★より、$x$ で得点できる箇所を、わざわざ $y$ 側で更新する意味は無い。

これにより、$y$ 側は「捨てる」ことができるようになる。不要な要素は $x$ 側に押しつければいい。
よって、$y$ 側では（今度こそ）「$x$ で得点できる要素を除いた $P$」についての最長増加部分列が実現できる。

「$x$ の得点機会の個数」+「それを除いた最長増加部分列の長さ」が答えとなる。

Python3

from bisect import bisect


def solve(n, ppp):
    ppp = [p - 1 for p in ppp]
    pos = [0] * n
    for i, p in enumerate(ppp):
        pos[p] = i
    i = n
    lis1 = set()
    for p in range(n - 1, -1, -1):
        if pos[p] < i:
            lis1.add(p)
            i = pos[p]

    lis2 = []
    for p in ppp:
        if p in lis1:
            continue
        i = bisect(lis2, p)
        if i == len(lis2):
            lis2.append(p)
        else:
            lis2[i] = p

    ans = len(lis1) + len(lis2)

    return ans


n = int(input())
ppp = list(map(int, input().split()))
ans = solve(n, ppp)
print(ans)

G - Restricted Permutation

問題文

整数 $N$ と o と x からなる長さ $N$ の文字列 $S$ が与えられます。
以下の条件を満たす $(1,2,\ldots,N)$ の順列 $P=(P_1,P_2,\ldots,P_N)$ の個数を $998244353$ で割ったあまりを求めてください。
$k=1,2,\ldots,N$ に対し、以下の $2$ つは同値となる。
- $S_k=$ o
- $P$ が $(1,2,\ldots,k)$ の順列を連続部分列として含む

制約

$1\le N\le 2000$
$S_i$ は o と x からなる長さ $N$ の文字列

解法

$i=1$ と $N$ では、必ず $S_i=$ o でなければならない。そうで無い場合は答えは $0$。
以下、満たすとする。

$1$ がはじめに1個あって、$2$ 以降をその左右にどのようにくっつけていくかを考える。
くっつけるといっても、単に隣接させたら $S_k=$ x のものに対しても $1～k$ の順列が含まれてしまう。
よって、「$1$ と $2$ の間には、将来的に $3$ 以上の値を挟むよ」というような「しおり」的なものも含めてくっつけていくことを考える。

DPをする。

$\mathrm{DP}[i,j]:=i$ までのくっつけ方を決めて、しおりが $j$ 個あるような並べ方の個数

最初、$\mathrm{DP}[1,0]=1$ である。

ひとまず $S$ は無視して、$i$ についてDPは次のように更新できる。

○:既存の配置要素のカタマリ（i-1以下の要素が1個以上連続したもの）
ｖ:しおり

(1) しおりを増やす場合
    左右端に増やすか、○ｖ○ を ○ｖ(i)ｖ○ にする。

DP[i-1,3]    ○ ｖ ○ ｖ ○ ｖ ○       j+2 箇所に挿入できる。
          ↑    ↑    ↑    ↑    ↑    DP[i,j+1] += (j+2)DP[i-1,j]

(2) しおりを維持する場合
    既存のカタマリの左右いずれかにくっつける。

DP[i-1,3]    ○ ｖ ○ ｖ ○ ｖ ○       2(j+1) 箇所にくっつけられる。
            ^  ^  ^  ^  ^  ^  ^  ^      DP[i,j] += 2(j+1)DP[i-1,j]

(3) しおりを減らす場合
    1つのしおりを選んで、左右をくっつける。j>=1の時のみおこなえる。

DP[i-1,3]    ○ ｖ ○ ｖ ○ ｖ ○       j 箇所を選べる。
                ↑    ↑    ↑          DP[i,j-1] += j * DP[i-1,j]

で、$j=0$ の状態が「$1～i$ の順列が、連続部分列として現れる」状態ということになる。

つまり、

$S_k=$ x の時
- $j=0$ になるような遷移、つまり「$j=0$ からの(2)」「$j=1$ からの(3)」の遷移はおこなってはいけない。
$S_k=$ o の時
- 「$j=0$ からの(2)」「$j=1$ からの(3)」の遷移しかおこなってはいけない。

最終的に $\mathrm{DP}[N,0]$ が答えとなる。

Python3

def solve(n, s):
    if s[0] == 'x' or s[-1] == 'x':
        return 0
    MOD = 998244353
    dp = [1, 0]
    for i in range(1, n):
        if s[i] == 'o':
            dp = [(dp[0] * 2 + dp[1]) % MOD, 0]
            continue
        m = len(dp)
        ndp = [0] * (m + 1)
        for j in range(m):
            ndp[j + 1] += dp[j] * (j + 2)
        for j in range(1, m):
            ndp[j] += dp[j] * 2 * (j + 1)
        for j in range(2, m):
            ndp[j - 1] += dp[j] * j
        for j in range(m):
            ndp[j] %= MOD
        dp = ndp

    return dp[0]


n = int(input())
s = input()
ans = solve(n, s)
print(ans)

目次

AtCoder Beginner Contest 468 D,E,F,G問題メモ

D - Pre-Palindrome

問題文

制約

解法

発展

E - Sum of Average

問題文

制約

解法

F - Chmax

問題文

制約

解法

G - Restricted Permutation

問題文

制約

解法