AtCoder Regular Contest 215 A～D問題メモ

AtCoder Regular Contest 215

A - Zombie

• 左右に広がった長さ $L$ の道路があります。この道路上に $N$ 体のゾンビがおり、 $i$ 体目は道路の左端から距離 $A_i$ の地点にいます。$L$ および $A_i$ はすべて偶数です。
• あなたはゾンビの餌を $K$ 個持っており、好きな時刻に、道路の両端を含む道路上の好きな位置に餌を置くことができます。
  • ただし、餌は1つずつ置き、道路上に同時に $2$ つ以上の餌が存在する時刻があってはいけません。
• 道路上に餌が存在するとき、各ゾンビは餌に向かって単位時間あたり $1$ の速さで進みます。ある餌と同じ位置に $1$ 体以上のゾンビが辿り着いたとき、その餌は食べられて瞬時に消滅します。
• 道路上に餌が存在しないとき、ゾンビは移動しません。
• 道路上に餌を置く時刻と位置を適切に定めたときの、道路上に餌が存在する時間の総和の最大値を求めてください。

• $T$ 個のテストケースが与えられるので、それぞれについて答えを求めて下さい。

• $1 \le T \le 10^5$
• $1 \le N \le 2 \times 10^5$
• $1 \le K \le 10^9$
• $2 \le L \le 10^9$
• $0 \le A_i \le L$
• $L$ は偶数
• $A_i$ はすべて偶数
• 全てのテストケースにおける $N$ の総和は $2 \times 10^5$ 以下
• 入力される値は全て整数

ゾンビは座標昇順に並べ直し、ゾンビ $i$ と $i+1$ の距離を $B_i$ で表す。

また、$B_{left}$ を道路の左端から最も左のゾンビまで、$B_{right}$ は右端から最も右のゾンビまでの距離とする。

餌を置くのに良さそうな位置が3種類ある。

• ①隣り合う2体のゾンビのちょうど真ん中
  • ゾンビ $i$ と $i+1$ の間に餌を置いたとして、餌が存在する時間は $B_i/2$
  • Bの変化
    • $B_{left}+=B_i/2$
    • $B_{right}+=B_i/2$
    • $B_i=0$
• ②道路の左端
  • 餌が存在する時間は $B_{left}$
  • Bの変化
    • $B_{right}+=B_{left}$
    • $B_{left}=0$
• ③道路の右端
  • 餌が存在する時間は $B_{right}$
  • Bの変化
    • $B_{left}+=B_{right}$
    • $B_{right}=0$

いずれの操作も、両端 $B_{left},B_{right}$ と、①で選ばれた $B_i$ 以外の値は変わらない。

②③をおこなってから①をおこなうなら、その前に①をおこなった方がいいことがわかる。

①を、$B_1,...,B_{N-1}$ の大きい方から何回か処理し、 その後、②→③→②→…（または逆）に交互に $K$ 回の残りをおこなうのが最適となる。

①をおこなう回数を全探索すればよい。

Python3

def solve(n, k, l, aaa):
    def get_ans(shrink, k):
        left = aaa[0] + shrink
        right = l - (aaa[-1] - shrink)
        if k == 0:
            return 0
        return max(left, right) + (left + right) * (k - 1)

    aaa.sort()
    betweens = []
    for i in range(n - 1):
        betweens.append(aaa[i + 1] - aaa[i])
    betweens.sort(reverse=True)
    ans = get_ans(0, k)
    between_times = 0
    for i in range(min(k, n - 1)):
        between_times += betweens[i] // 2
        tmp = between_times + get_ans(between_times, k - i - 1)
        ans = max(ans, tmp)
    return ans


t = int(input())
for _ in range(t):
    n, k, l = list(map(int, input().split()))
    aaa = list(map(int, input().split()))
    ans = solve(n, k, l, aaa)
    print(ans)

B - Stolen Necklace

• $2N$ 個の宝石が左右一列に並んでおり、左から $i$ 番目の宝石の種類は $A_i$ です。ここで、 $A_i$ は $1$ 以上 $N$ 以下の整数であり、どの種類の宝石も $2$ つずつ存在します。
• ここに以下の条件を満たすように仕切りを入れたいです。
  • それぞれの仕切りの位置は整数 $i$ ($1 \le i \le 2N - 1$) により表され、左から $i$ 番目の宝石と $i + 1$ 番目の宝石の間を仕切ることを意味する。
  • 同じ位置に $2$ つ以上の仕切りは存在しない。
  • 仕切りの個数 $K$ は $N$ 以下である。
  • 仕切りを $K$ 個入れることにより、宝石の列は $K + 1$ 個の区間に分かれる。このとき、左から奇数番目の区間にある宝石をすべて集めると、種類 $1,2,\ldots,N$ の宝石がちょうど $1$ つずつ得られる。
• この条件を満たすように仕切りを入れる方法を $1$ つ出力してください。ただし、このような方法が必ず存在することが証明できます。

• $T$ 個のテストケースが与えられるので、それぞれについて答えを求めて下さい。

• $1 \le T \le 10^5$
• $1 \le N \le 2 \times 10^5$
• $1 \le A_i \le N$ ($1 \le i \leq 2N$)
• どの種類の宝石も $2$ つずつ存在する、つまり各 $x$ ($1 \le x \le N$) について、$A_i = x$ なる $i$ はちょうど $2$ つ
• 全てのテストケースにおける $N$ の総和は $2 \times 10^5$ 以下
• 入力される値は全て整数

なるべく判断を後回しにする。

先頭から区切りを入れる位置を決めていく。今の区間が、奇数番目か偶数番目かの状態を持っておくとして、

• ある値の1回目の出現では、直前の要素と区切りを入れない。
  • 今の状態によって、奇数番目に入ったか偶数番目に入ったかをメモする
• 2回目の出現では、メモを参照し、1回目の方と偶奇が逆になるように、必要なら区切りを入れる

この方法なら、区切りの数は $1～N$ のそれぞれで最大1回ずつとなり、条件を満たす。

Python3

def solve(n, aaa):
    take = True
    taken = [0] * n  # 0:未出現, 1:出現して取った、-1:出現して取らず
    ans = []
    for i in range(n * 2):
        a = aaa[i] - 1
        if taken[a] == 0:
            if take:
                taken[a] = 1
            else:
                taken[a] = -1
            continue
        if take:
            if taken[a] == 1:
                ans.append(i)
                take = False
        else:
            if taken[a] == -1:
                ans.append(i)
                take = True
    return ans


t = int(input())
for _ in range(t):
    n = int(input())
    aaa = list(map(int, input().split()))
    ans = solve(n, aaa)
    print(len(ans))
    print(*ans)

C - Strong Surname

• 異なる名字を持つ $N$ 人の人がおり、$i$ 番目の人の名字はパラメータ $(X_i,Y_i,Z_i)$ を持っています。異なる名字が同一のパラメータを持つこともあります。
• 今から $N - 1$ 回、以下のことが起こります。
  • ある二人が親となり、その子供が一人出現する。親の二人は亡くなる。子供は、両親の名字のうち強い方を選んで自分の名字とする。パラメータ $(x_1,y_1,z_1)$ を持つ名字がパラメータ $(x_2,y_2,z_2)$ を持つ名字よりも強いとは、$x_1 \gt x_2$ かつ $y_1 \gt y_2$ かつ $z_1 \gt z_2$ を満たすことである。親の名字に強弱が付けられないとき、子供は名字を両親の名字からランダムに選ぶ。

• $N$ 人のうち、その人の名字が最後の一人の名字となりうる人の数を求めて下さい。
• $T$ 個のテストケースが与えられるので、それぞれについて答えを求めて下さい。

• $1 \le T \le 2 \times 10^5$
• $2 \le N \le 2 \times 10^5$
• $1 \le X_i, Y_i, Z_i \le N$
• 全てのテストケースにおける $N$ の総和は $2 \times 10^5$ 以下
• 入力される値は全て整数

$(2,2,2)$ と $(1,1,1)$ しかいなければ $(1,1,1)$ は残り得ない。
だが、そこに $(2,2,1)$ がいれば、以下のようにして残り得るようになる。

• $(2,2,2)$ と $(2,2,1)$ は強弱が付けられないので、ランダムの結果 $(2,2,1)$ が残る
• $(2,2,1)$ と $(1,1,1)$ は強弱が付けられないので、ランダムの結果 $(1,1,1)$ が残る

より一般に、以下のように2グループ $A,B$ に分けられるとき、$B$ は残り得ない。

• グループ $A$ の、パラメータそれぞれの最小値を $X_A,Y_A,Z_A$ とする
• グループ $B$ の、パラメータそれぞれの最大値を $X_B,Y_B,Z_B$ とする
• $X_A \gt X_B,Y_A \gt Y_B,Z_A \gt Z_B$ である

まず、$X_i,Y_i,Z_i$ のいずれかが最大値であるものは、確実にグループAに含まれる。
暫定のグループA、および $X_A,Y_A,Z_A$ を管理しつつ、以下のようにすると答えが求められる。

• $X_A,Y_A,Z_A$ の初期化
  • $X_i$ が最大となる $i$ の集合を $S$ とし、$Y_A←\min_{i \in S}Y_i,Z_A←\min_{i \in S}Z_i$ で更新する。
  • $Y_i$ が最大となる $i$ の集合を $S$ とし、$X_A←\min_{i \in S}X_i,Z_A←\min_{i \in S}Z_i$ で更新する。
  • $Z_i$ が最大となる $i$ の集合を $S$ とし、$X_A←\min_{i \in S}X_i,Y_A←\min_{i \in S}Y_i$ で更新する。
• まだグループAに選ばれていない $i$ をグループAに追加していく。
  • $X_A \le X_i$ なる $i$ があれば追加し、$Y_A←Y_i,Z_A←Z_i$ でmin更新する。
  • $Y,Z$ についても同様
  • 追加できるものがなくなれば終了

これで最終的なグループAのサイズが答えとなる。

Python3

from operator import itemgetter
from atcoder.dsu import DSU


def solve(n, names):
    names2 = [(i, x, y, z) for i, (x, y, z) in enumerate(names)]
    xxx = sorted(names2, key=itemgetter(1), reverse=True)
    yyy = sorted(names2, key=itemgetter(2), reverse=True)
    zzz = sorted(names2, key=itemgetter(3), reverse=True)

    leader = xxx[0][0]
    uft = DSU(n)
    x_lim = xxx[0][1]
    y_lim = yyy[0][2]
    z_lim = zzz[0][3]
    xi = 0
    yi = 0
    zi = 0
    while True:
        updated = False
        while xi < n and xxx[xi][1] >= x_lim:
            uft.merge(leader, xxx[xi][0])
            y_lim = min(y_lim, xxx[xi][2])
            z_lim = min(z_lim, xxx[xi][3])
            xi += 1
            updated = True
        while yi < n and yyy[yi][2] >= y_lim:
            uft.merge(leader, yyy[yi][0])
            x_lim = min(x_lim, yyy[yi][1])
            z_lim = min(z_lim, yyy[yi][3])
            yi += 1
            updated = True
        while zi < n and zzz[zi][3] >= z_lim:
            uft.merge(leader, zzz[zi][0])
            x_lim = min(x_lim, zzz[zi][1])
            y_lim = min(y_lim, zzz[zi][2])
            zi += 1
            updated = True
        if not updated:
            break
    return uft.size(leader)


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

D - cresc.

• 長さ $N+1$ の数列 $A = (A_1,A_2, \ldots, A_{N + 1})$ に対して、以下のような方法で長さ $N$ の数列 $S = (S_1, S_2, \ldots, S_{N})$ を得ることを考えます。
  • 各 $i$ ($1 \le i \le N$) について、 $S_i=A_i+A_{i + 1}$ とする。

• 以下の条件を全て満たす長さ $N$ の数列 $S$ の個数を $10^9 + 7$ で割った余りを求めて下さい。
  • 広義単調増加である。
  • ある $0$ 以上 $M$ 以下の整数からなる長さ $N+1$ の数列 $A$ であって、$A$ から前述の方法で $S$ を得ることができるものが存在する。

• $1 \le N, M \le 10^7$
• 入力される値は全て整数

久々に、mod 998244353 ではなく $10^9+7$ 指定。一応、畳み込みでも解けるようだが、その方法は取ってくれるなということか。

$S$ が広義単調増加となる $A$ の構造を考えると、

• 奇数番目を取りだした数列を $B_1,B_2,...,B_{\lceil (N+1)/2 \rceil}$
• 偶数番目を取りだした数列を $C_1,C_2,...,C_{\lfloor (N+1)/2 \rfloor}$

として、$B,C$ それぞれが広義単調増加ならよい。

B[i]      B[i+1]    至る所において、S[i] <= S[i+1] であるためには、
     C[i]           B[i] <= B[i+1] または C[i] <= C[i+1] であればよい
`-----' '-----'
 S[i]   S[i+1]

だが、任意の $x$ に対し「$B$ の全てに $x$ 加算し、$C$ の全てに $-x$ 加算した」ものは、同じ $S$ を生成する。
この重複を除かなければならない。

このため、できる限り $B$ を減らしたもののみを数えることにする。

つまり、$k=\lceil (N+1)/2 \rceil$、$l=\lfloor (N+1)/2 \rfloor$ として、 以下のいずれかであるようなものを数えればよい。

• $B_1=0$
• $C_{l}=M$

$0～m$ からなる $n$ 項の広義単調増加な数列の個数は、差分を考えることで ${}_{n+1}H_{m}$ で求められる。

• $a$:$B$ で、先頭を $0$ に固定した数列の個数: ${}_{k}H_{m}$
• $b$:$B$ で、先頭も自由な数列の個数: ${}_{k+1}H_{m}$
• $c$:$C$ で、末尾を $M$ に固定した数列の個数: ${}_{l}H_{m}$
• $d$:$C$ で、末尾も自由な数列の個数: ${}_{l+1}H_{m}$

$ad+bc-ac$ が答えとなる。
「$B_1=0$ かつ $C_{l}=M$」な数列は2回数えられているので、1回分除く。

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, m):
    MOD = 1_000_000_007

    if n == 1:
        return m * 2 + 1
    if n == 2:
        ans = 0
        for i in range(m + 1):
            ans += m * 2 + 1 - i
        ans %= MOD
        return ans

    facts, finvs = precompute_factorials(n + m, MOD)

    def nhr(n, r):
        return facts[n + r - 1] * finvs[n - 1] % MOD * finvs[r] % MOD

    odd_n = (n + 1) // 2
    even_n = (n + 1) - odd_n

    e_zero = nhr(even_n, m)
    e_free = nhr(even_n + 1, m)
    o_m = nhr(odd_n, m)
    o_free = nhr(odd_n + 1, m)

    ans = e_zero * o_free + e_free * o_m - e_zero * o_m
    ans %= MOD

    return ans


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