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

E - Vitamin Balance

問題文

$N$ 個の食べ物があり、それぞれの食べ物にはビタミン $1,2,3$ のうちちょうど $1$ つのみが含まれています。
具体的には、$i$ 個目の食べ物を食べると、ビタミン $V_i$ が $A_i$ だけ摂取でき、またカロリーが $C_i$ だけ摂取されます。
高橋君は、摂取するカロリーが合計で $X$ 以下となるように、$N$ 個の食べ物のうちいくつか（$0$ 個でも良い）を選んで食べることができます。
このとき、「ビタミン $1,2,3$ のうちもっとも摂取量が少ないものの摂取量」としてあり得る最大の値を求めてください。

制約

$1\leq N \leq 5000$
$1\leq X \leq 5000$
$1\leq V_i\leq 3$
$1\leq A_i\leq 2\times 10^5$
$1\leq C_i\leq X$
入力はすべて整数

解法

各食べ物に入っているビタミンはちょうど1種類だけなので、ビタミンの種類でそれぞれ分けてナップサックDPをすれば、「カロリー $x$ 以下で摂取できるビタミン $v$ の最大量」がそれぞれ求まる。
（「ちょうど $x$」でなく、「$x$ 以下」の最大値を求めておく）

このDP配列があれば、ある $k$ に対し「ビタミン3種をどれも $k$ 以上摂取するのに必要なカロリー」は、 3つのDP配列を二分探索することでおこなえる。

$k$ 自体も二分探索することで、$O(NX + \log{X}\log{(NA_{\max})})$ で答えを求められる。

Python3

from bisect import bisect_left


def knapsack(x, foods):
    calories = [0] * (x + 1)
    for a, c in foods:
        for i in range(x - c, -1, -1):
            calories[i + c] = max(calories[i + c], calories[i] + a)
    return calories


def solve(n, x, foods):
    foods_categorized = [[], [], []]
    for v, a, c in foods:
        foods_categorized[v - 1].append((a, c))
    res1 = knapsack(x, foods_categorized[0])
    res2 = knapsack(x, foods_categorized[1])
    res3 = knapsack(x, foods_categorized[2])
    l = 0
    r = 1 << 30
    while l + 1 < r:
        m = (l + r) // 2
        i = bisect_left(res1, m)
        j = bisect_left(res2, m)
        k = bisect_left(res3, m)
        if i + j + k <= x:
            l = m
        else:
            r = m
    return l


n, x = map(int, input().split())
foods = [tuple(map(int, input().split())) for _ in range(n)]
ans = solve(n, x, foods)
print(ans)

F - Double Sum 3

問題文

長さ $N$ の整数列 $A=(A_1,A_2,\ldots,A_N)$ が与えられます。
$1\le L\le R\le N$ を満たす整数の組 $(L,R)$ に対し $f(L,R)$ を以下のように定義します。
- 何も書かれていない黒板に $R-L+1$ 個の整数 $A_L,A_{L+1},\ldots,A_R$ を順に書き込む。
- 以下の操作を黒板に書かれた整数が全て消えるまで繰り返す。
  - 整数 $l,r$ を選ぶ。ただし、 $l\le r$ かつ黒板に $l$ 以上 $r$ 以下の整数が全て $1$ つ以上書かれているように $l,r$ を選ぶ必要がある。その後、黒板に書かれた $l$ 以上 $r$ 以下の整数を全て消す。
- 黒板に書かれた整数が全て消えるまでに必要な操作回数の最小値を $f(L,R)$ とする。

$\displaystyle \sum_{L=1}^N\sum_{R=L}^N f(L,R)$ を求めてください。

制約

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

解法

区間が与えられたら、最適な操作は一意に決まる。
たとえば、残っている中で最小の要素を $l$ とし、そこから1ずつ増やしていって黒板になくなる直前の要素を $r$ とすればよい。

ある操作によって指定する $(l,r)$ の、$r$ を「リーダー」とする。
区間内に $r$ が複数ある場合は、一番最初に出てくるものをリーダーとすることにする。

各要素につき「自身がリーダーとなるような区間 $(L,R)$」の個数を数えて合計すると、答えと同じことになる。

そのような区間は、以下のように考えられる。

5 1 9 3 5 2 6 9 1 6
        *            ←この5にとって、自身がリーダーとなる区間は、
 |<----|               左端は、「自身または自身+1の要素が出てくるまで」
         |->           右端は、「自身+1の要素が出てくるまで」

これより区間を広げたら、「リーダーを委譲する他の要素が必ず入ってくる」ことになる。
上例の場合は、左端と右端から独立に選んで、$4 \times 2 = 8$ 通りの区間で5がリーダーとなる。

各要素につき、「$A$ 上で自身から前後方向それぞれに、$A_i$ または $A_i+1$ が出てくる直近のindex」を取得できればよい。

値毎に出現indexを列挙しておいて、二分探索すると可能となる。

Python3

from bisect import bisect


def solve(n, aaa):
    pos = [[-1] for _ in range(n + 2)]
    for i, a in enumerate(aaa):
        pos[a].append(i)
    for a in range(n + 2):
        pos[a].append(n)
    ans = 0
    for i, a in enumerate(aaa):
        r1p = bisect(pos[a + 1], i)
        l1 = pos[a + 1][r1p - 1]
        r1 = pos[a + 1][r1p]
        r0p = bisect(pos[a], i)
        r0 = pos[a][r0p]
        l_choice = i - l1
        r_choice = min(r0, r1) - i
        ans += l_choice * r_choice
    return ans


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

G - Permutation Concatenation

問題文

正整数 $N$ が与えられます。
長さ $N$ の正整数列 $A=(A_1,A_2,\ldots,A_N)$ に対し $f(A)$ を次の手順で得られる整数とします。
- $S$ を空文字列とする。
- $i=1,2,\ldots,N$ の順番で以下の操作を行う。
  - $A_i$ を先頭に余分な $0$ を付けない十進数の文字列としてみたものを $T$ とする。
  - $S$ の末尾に $T$ を連結する。
- 最終的な $S$ を十進数の整数としてみた値を $f(A)$ とする。
- 例えば $A=(1,20,34)$ に対し $f(A)=12034$ です。

$(1,2,\ldots,N)$ の順列 $P$ は全部で $N!$ 通りありますが、それら全てに対する $f(P)$ の総和を $998244353$ で割ったあまりを求めてください。

制約

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

解法

数式こねくり回して畳み込みの形に持っていく系問題。

主客転倒して、「ある値 $x$ が答えに寄与する量」を考える。

ある順列に固定した時の $x$ の寄与は、

N = 15    x = 4

o o ... o o 4 o o ... o o
              ~~~~~~~~~~~
       ここに置く数の桁数の合計を s とし、4 * 10^s だけ寄与する

$x$ の寄与を求める時に、$x$ 以外の数は「桁数」だけが重要で、具体的な値は重要ではない。
よって、桁数ごとに同一視して考える。ただ、場合の数を求める上で「桁数毎の個数」は必要なので、それは考慮する。

制約から、桁数は最大でも6までしかない。
1桁の数が9個、2桁が90個、3桁が900個、、、ある。
$N$ と同じ桁数の数の個数はこの限りではないが、$6$ 桁とすると $N-99999 = N-(10^{6-1}-1)$ のように求められる。
また、$x$ と同じ桁数の数は、$x$ 自身があるので1少ない。

上記を踏まえた $d$ 桁の数の個数を $C_d$ とする。

$x$ 以外の $N-1$ 個の要素のうち、 1桁のものが $i$ 個、2桁のものが $j$ 個、3桁のものが $k$ 個、、、 $x$ の右に置かれるような順列を考える。（式の見やすさのため、とりあえず3桁までを考えるとする）

桁毎の具体的な要素の選び方が $\dbinom{C_1}{i}\dbinom{C_2}{j}\dbinom{C_3}{k}$ ある。
右側の要素の並べ方が $(i+j+k)!$、左側の並べ方が $(N-1-i-j-k)!$ ある。
以上のような順列のそれぞれに付き、1つあたり $x \times 10^{i+2j+3k}$ だけ寄与する。

つまり、以下が、答えに対する $x$ の寄与となる。

$\displaystyle \sum_{i=0}^{C_1}\sum_{j=0}^{C_2}\sum_{k=0}^{C_3}x \times 10^i10^{2j}10^{3k}\frac{C_1!}{i!(C_1-i)!}\frac{C_2!}{j!(C_2-j)!}\frac{C_3}{k!(C_3-k)!}(i+j+k)!(N-1-i-j-k)!$

これは「$i$ だけに依存する項」「$j$ だけに依存する項」「$k$ だけに依存する項」「$i+j+k$ に依存する項」「定数項」の積に分解できる。形式的冪級数を使って以下のように表して、

$\displaystyle I(x)=\sum_{t=0}^{C_1} (10^t\dfrac{1}{t!(C_1-t)!})x^t$
$\displaystyle J(x)=\sum_{t=0}^{C_2} (10^{2t}\dfrac{1}{t!(C_2-t)!})x^t$
$\displaystyle K(x)=\sum_{t=0}^{C_3} (10^{3t}\dfrac{1}{t!(C_3-t)!})x^t$
$\displaystyle S(x)=\sum_{t=0}^{N-1} t!(N-1-t)!x^t$

畳み込みによって $I \times J \times K$ を計算した後、$x$ の次数ごとに $S(x)$ の係数をかけることで、 $i+j+k=0,1,2,...,N-1$ それぞれについての上記の式の答えが求められる。

実際は最大6桁の要素まで考慮する必要があるが、同じことを繰り返すだけなので同様の考え方でよい。
これで、$x$ についての寄与が $O(N \log{N})$ で求められた。

$x$ の桁数が同じものは寄与する係数も同じなので、まとめて求められる。
$x$ が $1～6$ 桁それぞれの場合について求め、合計すれば答えとなる。

Python3

import numpy as np


def _convolve(f, g):
    # 小さいうちは愚直の方が高速。convolve_mod()と併用するなら大丈夫だが、単独で使用する場合はオーバーフローに注意
    if len(f) * len(g) < 10000:
        return np.convolve(f, g)

    fft_len = 1
    true_len = len(f) + len(g) - 1
    while fft_len < true_len:
        fft_len <<= 1

    Ff = np.fft.rfft(f, fft_len)
    Fg = np.fft.rfft(g, fft_len)
    Fh = Ff * Fg

    h = np.fft.irfft(Fh, fft_len)
    h = np.rint(h).astype(np.int64)

    return h[:true_len]


def convolve_mod(f, g, p):
    f1, f2 = np.divmod(f, 1 << 15)
    g1, g2 = np.divmod(g, 1 << 15)

    a = _convolve(f1, g1) % p
    c = _convolve(f2, g2) % p
    b = (_convolve(f1 + f2, g1 + g2) - (a + c)) % p

    h = (a << 30) + (b << 15) + c
    return h % p


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):
    MOD = 998244353

    d = len(str(n))
    counts = [0] + [10 ** i - 10 ** (i - 1) for i in range(1, 7)]
    counts[d] = n - 10 ** (d - 1) + 1
    sums = [0] * 7
    INV2 = pow(2, -1, MOD)
    for i in range(1, d):
        sums[i] = (10 ** i - 1 + 10 ** (i - 1)) * counts[i] * INV2 % MOD
    sums[d] = (n + 10 ** (d - 1)) * counts[d] * INV2 % MOD
    # print(counts)
    # print(sums)

    facts, finvs = precompute_factorials(n, MOD)

    arrays0 = [[]]
    arrays1 = [[]]
    for i in range(1, d + 1):
        arr0 = []
        arr1 = []
        pow10 = 1
        base = 10 ** i
        for j in range(counts[i] + 1):
            arr0.append(finvs[j] * finvs[counts[i] - j] * pow10 % MOD)
            if j < counts[i]:
                arr1.append(finvs[j] * finvs[counts[i] - j - 1] * pow10 % MOD)
            pow10 = pow10 * base % MOD
        arrays0.append(np.array(arr0, dtype=np.int64))
        arrays1.append(np.array(arr1, dtype=np.int64))

    facts_ijk = np.array(facts[:-1], dtype=np.int64)
    facts_rev = facts_ijk[::-1]
    facts_cmb = facts_ijk * facts_rev % MOD

    ans = 0
    for i in range(1, d + 1):
        x = np.ones(1, np.int64)
        cf = sums[i]
        for j in range(1, d + 1):
            if i == j:
                x = convolve_mod(x, arrays1[j], MOD)
                cf *= facts[counts[j] - 1]
            else:
                x = convolve_mod(x, arrays0[j], MOD)
                cf *= facts[counts[j]]
            cf %= MOD
        x *= facts_cmb
        x %= MOD
        x *= cf
        x %= MOD
        ans += x.sum()
        ans %= MOD
    return ans


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

目次

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

E - Vitamin Balance

問題文

制約

解法

F - Double Sum 3

問題文

制約

解法

G - Permutation Concatenation

問題文

制約

解法