AtCoder Regular Contest 126 B,C,D問題メモ

AtCoder Regular Contest 126

B - Cross-free Matching

• 平面座標上に $M$ 本の線分がある
• $i$ 番目の線分は $(a_i, 0)$ と $(b_i, 1)$ を結ぶ
• どの2本の線分も点を共有しない（両端を含めて）ように、$M$ 本の中から線分を選びたい
• 選べる最大数を求めよ
• $1 \le M \le 2 \times 10^5$
• $1 \le a_i,b_i \le 2 \times 10^5$

最長増加部分列（Longest Increase Subsequence）の亜種。

$(a_i,0)$ と $(b_i,1)$ を結ぶ線分を、単に $(a_i,b_i)$ と表現することにする。

DPを以下のように定義する。

• $DP[i][k]=a$ が $i$ 以下である線分だけで $k$ 本選ぶときの、最も右の線分のもう一方の端点 $b$ がとれる最小値

$a$ が同じなら $b$ がなるべく小さい方が次に採用できる線分の可能性が広がるので、小さく保って損しない。

$(a_i,b_i)$ を採用するとき、 「既に採用された一番右の線分の $a \lt a_i$」かつ「既に採用された一番右の線分の $b \lt b_i$」という状態に1本加えることができ、自身が新たに一番右の線分となる。

前者の条件は $a_i$ が小さい方から順に調べればよい。

この $DP$ の更新方法はLISと似通っていて、

• 常に狭義単調増加になる
• 二分探索で $DP$ 配列から $b$ の挿入位置を探す
• 位置が $p$ だったとすると $p$ 本目として採用できるので、$DP[i][p]←b$ に更新できる

DP[4]
[0, 3, 4, 8]      ai=5 の線分は (a, b)=(5, 1),(5, 5),(5, 6),(5, 10) の4本があるとする

[0, 1, 4, 8]      (5, 1) を使うと、1本採用したときのbの最小値を1に更新できる
[0, 3, 4, 5]      (5, 5) を使うと、3本採用したときのbの最小値を5に更新できる
[0, 3, 4, 6]      (5, 6) を使うと、3本採用したときのbの最小値を6に更新できる
[0, 3, 4, 8, 10]  (5, 10)は、新たに1本採用できる

[0, 1, 4, 5, 10]  以上をまとめると、DP[5]は左のようになる

$3$ 本目としては $(5,5)$ も $(5,6)$ も採用できるが、より小さい $(5,5)$ が採択される。

$a$ が同じ線分は「全ての挿入位置を求める」→「まとめて更新する」という方法をとる。
さもないと、逐次更新していたら上記の例では $(5,6)$ の時に新たに1本採用できることになってしまう。

[0, 3, 4, 5]      (5, 5) を使って左のように更新した後に
                  (5, 6)について更新しようとすると、
[0, 3, 4, 5, 6]   こうなってしまう

だが、これは $a_i=5$ である2本を同時に採用することになるので、共有点ができてしまう。

Python3

from bisect import bisect_left
from collections import defaultdict

n, m = map(int, input().split())

edges = defaultdict(list)
for _ in range(m):
    a, b = map(int, input().split())
    edges[a].append(b)
dp = [0]

for a in sorted(edges):
    if a not in edges:
        continue

    updates = []
    for b in edges[a]:
        i = bisect_left(dp, b)
        updates.append((b, i))

    for b, i in updates:
        if i >= len(dp):
            dp.append(b)
        else:
            dp[i] = min(dp[i], b)

print(len(dp) - 1)

C - Maximize GCD

• $N$ 個の整数 $A=(A_1,A_2,...,A_N)$ がある
• 好きな整数を1つ選んで1を足す、という操作を $K$ 以下行える
• $gcd(A_1,A_2,...,A_N)$ を最大化せよ
• $2 \le N \le 3 \times 10^5$
• $1 \le A_i \le 3 \times 10^5$
• $1 \le K \le 10^{18}$

工夫してまとめられる計算をまとめる。

まず、$K$ が馬鹿でかい時は、なるべく均して全てを同じ数にするのが最もgcdを大きくできる。

全てを均すと $m=\dfrac{Sum(A)+K}{N}$（切り捨て）となるとして、 実際には数字は減らせないので、$m \ge A_{max}$ なら全てを同じ値にでき、答えは $m$ となる。

以下、そうで無い場合を考える。

操作後の $A$ には $A_{max}-1$ 以下の値が含まれ、gcdが $A_{max}-1$ より大きくなることは無いので、 gcdの候補としては $A_{max}-1$ 以下だけ考えればよいことになる。

$A_i$ の制約が中途半端に小さいのも、gcd候補を全探索できるようにしている感じがある。

大きい順に、gcd候補を $g$ として「合計 $K$ 以下を足すことで全てを $g$ の倍数に出来るか？」を試していく。
一番最初に見つかった可能な $g$ が答え。

制約上、この判定を1回あたり $O(\log{N})$ や $O(\log{A_{max}})$ くらいで行いたい。

$g$ を固定した時、各 $A_i$ を $g$ の倍数にする必要がある。

1つの $A_i$ を $g$ の倍数にするためには、$ceil(\dfrac{A_i}{g}) \times g - A_i$ だけ足す必要がある。

この $ceil(\dfrac{A_i}{g})$ が同じ $A_i$ ごとに計算をまとめることができる。

$ceil(\dfrac{A_i}{g})=c$ となる $A_i$ の個数を $n$、その和を $s$ とすると、$cng - s$ が、加算する必要数となる。

ceilが取り得る値の種類は、$g$ が大きい内は少ない。具体的には $\dfrac{A_{max}}{g}$ 個くらい。

従って、$g$ を全て試しても $\dfrac{A_{max}}{1}+\dfrac{A_{max}}{2}+...+\dfrac{A_{max}}{A_{max}-1}$ で、 全体で $O(A_{max}\log{A_{max}})$ となる。

一見、間に合いそうにないが、枝刈りがそれなりに有効に働いて実際は間に合う。

$ceil$ が同じになる $A_i$ は、$A_i$ をソートしたときに連続している。
最初に $A_i$ をソートし、累積和を取ることで「$g$ に対してceilが同じ $A_i$ の和」を高速に取得できる。

$ceil(\dfrac{A_i}{g})=c$ となる $A_i$ は、 $cg \lt A_i \le (c+1)g$ なる最小と最大の $i$（それぞれ $l,r$ とする）を二分探索で求めることで得られる。

実際には1つ前の $r$ は次の $l$ となるので、

• $l=0$ から始める
• $c=ceil(\dfrac{A_l}{g})$ を計算する
• $A$ から $(c+1)g$ の挿入位置を二分探索で求め、$r$ とする
• $l～r$ の個数と累積和から、当該範囲の $A_i$ を全て $g$ の倍数にするために加算すべき値が求まる
• $l←r$ に更新する

とすると、余計な $c$ を調べることがなくなる。
（※余計な $c$: $ceil(\dfrac{A_i}{g})=c$ となる $i$ が1つも存在しない $c$）

また、$l$ を増やして加算すべき値を求めていく過程で、途中で $K$ を超えたら、 その時点で現在の $g$ は不可能として打ち切ってよい。

前者（余計な $c$ の省略）はあまり効かないテストケースを作れるが、 後者（$K$ を超えたら打ち切り）は「多くの $g$ に対して、ギリギリまで $K$ を超えないで、 でも最終的には $K$ を超えてしまうような $A$」というのは作れないので、有効に働く。

$A_i$ の上限は配列で表現できる範囲なので、はじめから数直線上にプロットしてから累積和を取ってしまえばよい。

つまり、先ほどは

A = (3, 5, 6, 9)  だったら累積和は
 [0, 3, 8,14,23]

としていて、$c$ ごとに挿入可能位置を二分探索しなければならなかったが、

A = (3, 5, 6, 9)

i 0  1  2  3  4  5  6  7  8  9
[ 0  0  0  3  0  5  6  0  0  9 ]   数直線上にプロットして
[ 0  0  0  3  3  8 14 14 14 23 ]   累積和をとる

[ 0  0  0  1  0  1  1  0  0  1 ]   同様に個数も取っておく
[ 0  0  0  1  1  2  3  3  3  4 ]

こうすると、二分探索をせずとも $c$ ごとに $(cg, (c+1)g]$ の範囲の累積和を調べればよくなる。

余計な $c$ を調べてしまうかも知れないが、二分探索を省略できることの方が大きく、上記より高速になる。

Python3

import os
import sys

import numpy as np


def solve(inp):
    n = inp[0]
    k = inp[1]
    aaa = inp[2:]

    a_max = aaa.max()
    mean = (aaa.sum() + k) // n
    if mean >= a_max:
        return mean

    acc_val = np.zeros(a_max + 1, np.int64)
    acc_cnt = np.zeros(a_max + 1, np.int64)
    for a in aaa:
        acc_val[a] += a
        acc_cnt[a] += 1
    acc_val = acc_val.cumsum()
    acc_cnt = acc_cnt.cumsum()

    for d in range(a_max - 1, 1, -1):
        l = 0
        required = 0
        while l < a_max and required <= k:
            r = l + d
            ri = min(r, a_max)
            required += (acc_cnt[ri] - acc_cnt[l]) * r - (acc_val[ri] - acc_val[l])
            l = r

        if required <= k:
            return d

    return 1


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$ を1減らしたときに、足す必要数が増減する差分を管理する、みたいな方向に行っちゃったな。 これだと $g$ が小さくなったときに対象が多くなりすぎてTLEとなる。

D - Pure Straight

• $1～K$ の値からなる長さ $N$ の数列 $A=(A_1,...,A_N)$ がある
  • $1～K$ はそれぞれ少なくとも1個は $A$ に出現する
• 隣接swapを繰り返すことで、$A$ のどこかに「$1,2,3,...,K$」という並びが現れるようにしたい
• 必要な最小swap回数を求めよ
• $2 \le K \le 16$
• $K \le N \le 200$

不要な要素を追い出す操作と、最終的に $1,...,K$ の並びを作る要素同士の並べ替えで、分けて考える。

並べ替えはおなじみ転倒数だが、不要な要素を追い出す回数の考え方が面白い。

先頭からDPをしていく。

• $DP[i,S]=A_i$ まで見て、集合 $S$ の要素を整列した上で並べるための、最小操作回数

大まかにはこんな感じだが、「どこにそれを並べるか」によって操作回数が変わってくるため、少し定義不足である。

まぁ、とりあえず遷移を考える。

$A_i$ を新たに $S$ に加える場合、「$S$ に含まれる、$A_i$ より大きい要素の個数」だけ、操作が発生する。

これは転倒数の更新方法そのものなので、わりとわかりやすい。

スルーする場合、$A_i$ を追い出す必要が発生する。

そのコストは、$\min(|S|, K-|S|)$ となる。

つまり、$|S|$ がまだ半分以下なら左から追い出した方がよく、 半分を超えているなら右から追い出した方がよい、ということを表す。

（答えには直接関係ないが）最終的に $1,2,...,K$ の並びができる位置は、 採用した $K$ 個の要素の内、初期状態で真ん中にあった要素を中心とした位置、となる。

$S$ に含まれない要素はまだ位置や並びも見えていないが、 個数さえ分かっていれば $A_i$ という単独の要素を追い出すコストはわかる、というのがポイント。

Python3

n, k = map(int, input().split())
aaa = list(map(int, input().split()))

pop_count = [0] * (1 << k)
for i in range(1 << (k - 1)):
    pop_count[i << 1] = pop_count[i]
    pop_count[i << 1 | 1] = pop_count[i] + 1

INF = 1 << 60
dp = [INF] * (1 << k)
dp[0] = 0
for a in aaa:
    a -= 1
    bit = 1 << a
    ndp = [INF] * (1 << k)
    for bitset in range(1 << k):
        if dp[bitset] == INF:
            continue

        # 使わないとき
        pc = pop_count[bitset]
        inc = min(pc, k - pc)
        ndp[bitset] = min(ndp[bitset], dp[bitset] + inc)

        if bitset & bit:
            continue

        # 使うとき
        inv = pc - pop_count[bitset & (bit - 1)]
        ndp[bitset | bit] = min(ndp[bitset | bit], dp[bitset] + inv)
    dp = ndp

print(dp[-1])