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

AtCoder Beginner Contest 400

ABC300の前後、何回かDDos攻撃でアクセス困難になり、Unratedになることがあった。
そこから100回。今も攻撃はあるだろうけど、安定してRatedで無事開催できててすごい。

E - Ringo's Favorite Numbers 3

• 正整数 $N$ に対し、$N$ が 400 number であることは以下の $2$ つの条件をともに満たすことであると定義します。
  • $N$ の素因数はちょうど $2$ 種類である。
  • $N$ の各素因数 $p$ について、$N$ が $p$ で割り切れる回数は偶数回である。より厳密には、$N$ の各素因数 $p$ について $p^k$ が $N$ の約数であるような最大の非負整数 $k$ は偶数である。

• $Q$ 個のクエリが与えられるので、それぞれについて答えてください。各クエリでは、整数 $A$ が与えられるので、$A$ 以下の最大の 400 number の値を求めてください。ただし、本問題の制約下では $A$ 以下の 400 number は常に存在します。

• $1 \leq Q \leq 2 \times 10^5$
• 各クエリについて、$36 \leq A \leq 10^{12}$
• 入力される値はすべて整数

$10^{12}$ 以下の “400 number” を全て求めてソートしておくことができれば、各クエリには二分探索で求められる。

$f(a,b,c,d)$ を、「$(a番目の素数)^{2b}(c番目の素数)^{2d}$ として表される 400 number」と定義して、 一番小さい $f(1,1,2,1)$ から経路探索のように求めていく。

$(a,b,c,d)$ からは、以下の4つに遷移する。

• $a+1 \lt c$ の場合、$(a+1,b,c,d)$
• $(a,b+1,c,d)$
• $(a,b,c+1,d)$
• $(a,b,c,d+1)$

$10^{12}$ を超えたら打ち切り、また一度訪れた組を再度調べないように注意すると、 $10^{12}$ 以下の “400 number” の個数を $K$ として、$O(K)$ で全列挙できる。

Python3

from bisect import bisect


def get_primes(n):
    """ nまでの素数リスト """
    candidates = [0, 1] * (n // 2 + 1)
    if n % 2 == 0:
        candidates.pop()
    candidates[1] = 0
    candidates[2] = 1
    for p in range(3, int(n ** 0.5) + 1, 2):
        if candidates[p]:
            for m in range(p * p, n + 1, 2 * p):
                candidates[m] = 0
    return [p for p, b in enumerate(candidates) if b]


def solve(q, queries):
    primes = get_primes(550000)
    limit = 10 ** 12
    cand = {36}
    q = [(36, 0, 2, 1, 2)]
    while q:
        p, a, b, c, d = q.pop()
        if b == 2 and d == 2:
            x = primes[a]
            y = primes[c + 1]
            pp = x ** 2 * y ** 2
            if pp <= limit and pp not in cand:
                cand.add(pp)
                q.append((pp, a, 2, c + 1, 2))

            if a + 1 < c:
                x = primes[a + 1]
                y = primes[c]
                pp = x ** 2 * y ** 2
                if pp <= limit and pp not in cand:
                    cand.add(pp)
                    q.append((pp, a + 1, 2, c, 2))

        x = primes[a]
        y = primes[c]
        pp = x ** (b + 2) * y ** d
        if pp <= limit and pp not in cand:
            cand.add(pp)
            q.append((pp, a, b + 2, c, d))

        pp = x ** b * y ** (d + 2)
        if pp <= limit and pp not in cand:
            cand.add(pp)
            q.append((pp, a, b, c, d + 2))

    cand = sorted(cand)
    ans = []
    for a in queries:
        i = bisect(cand, a)
        ans.append(cand[i - 1])
    return ans


q = int(input())
queries = [int(input()) for _ in range(q)]
ans = solve(q, queries)
print('\n'.join(map(str, ans)))

F - Happy Birthday! 3

• 半径で切って $N$ 等分された円形のケーキがあります。
• 各ピースには時計回りに $1, 2, \ldots, N$ の番号が付けられています。また、$1 \leq i \leq N$ なる整数 $i$ についてピース $i$ をピース $N + i$ とも呼ぶこととします。
• はじめ、すべてのピースの色は色 $0$ です。
• あなたは、以下の操作を好きな回数行うことができます。
  • $1 \leq a, b, c \leq N$ なる整数 $a, b, c$ を選ぶ。$0 \leq i \lt b$ なる各整数 $i$ に対してピース $a + i$ の色を色 $c$ に変更する。この操作にはコストが $b + X_c$ かかる。

• $1 \leq i \leq N$ なるすべての整数 $i$ に対してピース $i$ の色を色 $C_i$ にするために必要なコストの合計の最小値を求めてください。

• $1 \leq N \leq 400$
• $1 \leq C_i \leq N$
• $1 \leq X_i \leq 10^9$
• 入力される値はすべて整数

操作は、平たく言うと「好きな扇形を好きな1色に塗りつぶす」となる。

制約メタ読みで区間DPに当たりを付ける。
円環であっても区間 $[l,r)$ は定義できる。「$l \gt r$ の場合は $1$ と $N$ の境界を跨いでいる区間」と解釈すればよい。

• $\mathrm{DP}[l,r]:=$ 区間 $[l,r)$ を塗るのに必要なコスト

初期状態は、各 $i$ に対し以下となる。

• $\mathrm{DP}[i,i]=0$
• $\mathrm{DP}[i,i+1]=X_{C_i}+1$

$\mathrm{DP}[l,r]$ を求める時、それより幅の短い区間は全て求まっているとして、 $[l,m)$ と $[m,r)$ に分割する箇所 $m=l+1,...,r-1$ を全探索する。

• ピース $l$ を色 $C_l$ に塗る際に $m$ を跨がない場合は、単純に足し合わせ。
  • $\mathrm{DP}[l,m]+\mathrm{DP}[m,r]$
• $C_l=C_m$ の時に限り、ピース $m$ を塗る際に、$l$ まで一緒に塗っていたことにできる。
  • 追加分のコストは、区間を伸ばした分 $m-l$
  • $\mathrm{DP}[l+1,m]+\mathrm{DP}[m,r]+(m-l)$

一見、なんかもっと他の遷移も考えなきゃいけないように思うが（$m$ を塗る際に $l$ までは一緒には塗らないが、その手前のどこかまでは一緒に塗る場合、など）、 その場合は他の分割箇所 $m$ でちゃんと考慮されるので、上記の遷移だけでいける。

これでDPを埋めていき、幅 $N$ の区間に対するDPの結果の中での最小値が答え。
（※定義上、幅 $N$ の区間の格納場所は $\mathrm{DP}[i,i]$ となり、初期状態の幅0の区間とダブってしまうので、幅 $N$ の場合だけはどこか別の場所に記録しておくとよい。他の区間を求める時に参照されることはないし）

計算量は $O(N^3)$

Python3

def solve(n, ccc, xxx):
    ccc = [c - 1 for c in ccc]
    INF = 1 << 60
    dp = [[INF] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = 0
        dp[i][(i + 1) % n] = xxx[ccc[i]] + 1
    ans = INF
    for w in range(2, n + 1):
        for l in range(n):
            r = (l + w) % n
            c0 = ccc[l]
            tmp = INF
            for m in range(l + 1, l + w):
                k = m % n
                tmp = min(tmp, dp[l][k] + dp[k][r])
                if ccc[k] == c0:
                    tmp = min(tmp, dp[(l + 1) % n][k] + dp[k][r] + m - l)
            if w == n:
                ans = min(ans, tmp)
            else:
                dp[l][r] = tmp
    return ans


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

G - Patisserie ABC 3

• ABC 洋菓子店で働くパティシエである高橋君は、AtCoder Beginner Contest 400 を記念したケーキのセットを販売することにしました。
• ABC 洋菓子店にはケーキ $1$, ケーキ $2$, $\ldots$, ケーキ $N$ の $N$ 種類のケーキが販売されています。
• 各ケーキは綺麗さ、おいしさ、人気度の $3$ つの非負整数値を持ちます。具体的にはケーキ $i$ の綺麗さ、おいしさ、人気度はそれぞれ $X_i,Y_i,Z_i$ です。
• 高橋君はケーキを被りのない $K$ 個のペアにして売り出すことを考えました。
  • 形式的に説明すると、$2K$ 個の 相異なる $1$ 以上 $N$ 以下の整数 $a_1,b_1,a_2,b_2,\ldots,a_K,b_K$ を選んでケーキ $a_i$ とケーキ $b_i$ をペアにすることにしました。
  • ケーキ $a_i$ とケーキ $b_i$ をペアにした時のペアの価格は $\max(X_{a_i}+X_{b_i}, Y_{a_i}+Y_{b_i}, Z_{a_i}+Z_{b_i})$ とします。ただし、$\max(P,Q,R)$ で $P,Q,R$ のうち最大の値を表します。
• $K$ 個のペアの価格の総和としてあり得る最大の値を求めてください。
• $T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

• $1\leq T\leq 1000$
• $2\leq N \leq 10^5$
• 各入力ファイルについて、すべてのテストケースの $N$ の総和は $10^5$ 以下である。
• $1\leq K \leq \lfloor \frac{N}{2}\rfloor$ （実数 $x$ に対し、$\lfloor x\rfloor$ で $x$ 以下の最大の整数を表す。）
• $0\leq X_i,Y_i,Z_i \leq 10^9$
• 入力はすべて整数

ケーキの「強み」を、「そのケーキの3つのカテゴリの中で最大値を取るものの1つ」とする。
（$(X_i,Y_i,Z_i)=(3,4,5)$ なら、ケーキ $i$ の強みはカテゴリ $Z$。同率の場合は適当に1つ）

以下のような問題に言い換えられる。

• 整数の多重集合 $S_x,S_y,S_z$ があり、最初は空である。
• 各ケーキ $i$ につき、以下のいずれか1つをおこなう。
  • $X_i$ を $S_x$ に追加する
  • $Y_i$ を $S_y$ に追加する
  • $Z_i$ を $S_z$ に追加する
  • 何もしない
• 最終的に、以下の条件を満たすような分け方に対し、
  • $|S_x|+|S_y|+|S_z|=2K$
  • $|S_x|,|S_y|,|S_z|$ は全て偶数
• スコアを $sum(S_x)+sum(S_y)+sum(S_z)$ とする。スコアの最大値を求めよ

集合の中でのペア分けは適当にやればよい。 （$S_x$ に追加したケーキ $i,j$ をペアにしたとき、実際には $X_i+X_j$ より $Y_i+Y_j$ が最大となるようであれば、 $i,j$ は $S_y$ に入れていた方が全体の総和は大きくなるため、そもそもが最大値となる分け方ではなかったことになる）

集合に追加する $2K$ 個の要素はなるべく値の大きいもの（そのケーキの強みであるもの）を選びたい。

ケーキを $\max(X_i,Y_i,Z_i)$ の大きい順に並べ、indexを振りなおす。

ケーキ $1～2K$ につき、そのケーキの強みを採用する（$X_i$ が最大値なら $S_x$ に追加する）のが素朴な上限である。
この結果、「$|S_x|,|S_y|,|S_z|$ は全て偶数」が満たされていれば、明らかにそれが答え。

だが、実際は奇数個の集合ができることもありうる。
その場合、強み以外を使ったり、$2K+1$ 以降のケーキを使ったりして、組み替える必要がある。

これを、どう上手く処理するか？

ところで、「どのカテゴリを使うか」はともかく「どのケーキを使うか」という観点では、 「最適解には、$1～2K$ のケーキのうち使わないのが2個以下であるものが存在する」ということが証明できる。

• potato167氏によるユーザー解説

• もし、使わなかったうち2つの強みが共通している場合
  • その2つを使っていたことにして損しない。
  • よって、使わなかったケーキ同士で、強みは全て異なっている。
  • 4個以上だと絶対被るので、使わないのは最大でも3個。
• 使わなかったのが3個で、強みが全て異なる場合
  • $2K+1$ 個目のケーキの強みが例えば $X$ なら、使わなかった3個のうち、$X$ が強みであるものとペアにして損しない。

また、$S_x,S_y,S_z$ は要素数の偶奇だけが重要のため、具体的な個数はどうでもよい。

以上から、以下のDPでケーキ $1～2K$ の使用状態を網羅できる。

• $\mathrm{DP}[i][j][k][l][m]:=$
  • ケーキ $i$ まで見て、
  • 採用していないのが $j=\{0,1,2\}$ 個で、
  • $|S_x|$ の偶奇が $k=\{0,1\}$ で、
  • $|S_y|$ の偶奇が $l=\{0,1\}$ で、
  • $|S_z|$ の偶奇が $m=\{0,1\}$ である分け方のスコア

$k,l,m$ は、実装上は3bitのフラグでまとめてしまえばよい。状態数 $48K$ で求められる。

後は、$2K+1～N$ で、各パラメータが大きいケーキの上位2個までを求め、DP結果の不採用数に応じて穴を埋めたものが答えとなる。
（またはDPを継続して、$2K+1$ 以降は今度は採用するたびに $j$ を減らしていく、という実装もでき、そちらの方が楽かも）

Python3

def solve(n, k, cakes):
    cakes = [(max(c), *c) for c in cakes]
    cakes.sort(reverse=True)
    INF = 1 << 60
    dp = [[-INF] * 8 for _ in range(3)]
    dp[0][0] = 0
    for i in range(k * 2):
        m, x, y, z = cakes[i]
        ndp = [[-INF] * 8 for _ in range(3)]
        for key in range(8):
            for j in range(3):
                ndp[j][key ^ 0b001] = max(ndp[j][key ^ 0b001], dp[j][key] + x)
                ndp[j][key ^ 0b010] = max(ndp[j][key ^ 0b010], dp[j][key] + y)
                ndp[j][key ^ 0b100] = max(ndp[j][key ^ 0b100], dp[j][key] + z)
            for j in range(2):
                ndp[j + 1][key] = max(ndp[j + 1][key], dp[j][key])
        dp = ndp

    ans = dp[0][0]
    if n == k * 2:
        return ans

    sub = [[-1, -1] for _ in range(3)]
    for i in range(k * 2, n):
        for j in range(3):
            if sub[j][0] == -1 or cakes[sub[j][0]][j + 1] < cakes[i][j + 1]:
                sub[j][0], sub[j][1] = i, sub[j][0]
            elif sub[j][1] == -1 or cakes[sub[j][1]][j + 1] < cakes[i][j + 1]:
                sub[j][1] = i
    ans = max(
        ans,
        dp[1][0b001] + cakes[sub[0][0]][1],
        dp[1][0b010] + cakes[sub[1][0]][2],
        dp[1][0b100] + cakes[sub[2][0]][3],
    )
    if n == k * 2 + 1:
        return ans

    assert sub[0][0] >= 0 and sub[0][1] >= 0
    assert sub[1][0] >= 0 and sub[1][1] >= 0
    assert sub[2][0] >= 0 and sub[2][1] >= 0

    def get_xy(x, y):
        if sub[x][0] != sub[y][0]:
            return cakes[sub[x][0]][x + 1] + cakes[sub[y][0]][y + 1]
        return max(
            cakes[sub[x][0]][x + 1] + cakes[sub[y][1]][y + 1],
            cakes[sub[x][1]][x + 1] + cakes[sub[y][0]][y + 1],
        )

    ans = max(
        ans,
        dp[2][0b011] + get_xy(0, 1),
        dp[2][0b101] + get_xy(0, 2),
        dp[2][0b110] + get_xy(1, 2),
        dp[2][0b000] + max(cakes[sub[j][0]][j + 1] + cakes[sub[j][1]][j + 1] for j in range(3)),
    )
    return ans


t = int(input())
for _ in range(t):
    n, k = map(int, input().split())
    cakes = [tuple(map(int, input().split())) for _ in range(n)]
    ans = solve(n, k, cakes)
    print(ans)