CodeQUEEN 2024 決勝 F,H問題メモ

CodeQUEEN 2024 決勝

F - Divide the Cake

• イチゴの乗ったケーキが $N$ 個の扇形ピースに区切られています。
• 切れ込みを時計回りの順に切れ込み $1$, 切れ込み $2$, $\ldots$, 切れ込み $N$ と番号をふったとき、時計回りに切れ込み $i$ $(1 \leq i \leq N-1)$ から切れ込み $i+1$ までの間の部分をピース $i$ と呼びます。また、時計回りに切れ込み $N$ から切れ込み $1$ までの間の部分をピース $N$ と呼びます。
• ピース $i$ $(1 \leq i \leq N)$ の上には $A_i$ 個のイチゴが乗っています。
• 高橋君と青木君はこれから以下のゲームをします。
  • まず、高橋君が $N$ 個の切れ込みのなかから $1$ つを選ぶ。選んだ切れ込みを切れ込み $i$ とする。
  • 次に、青木君が高橋君の選んだ切れ込み以外の $N-1$ 個の切れ込みのなかから $1$ つを選ぶ。選んだ切れ込みを切れ込み $j$ とする。
  • 高橋君は切れ込み $i$ から時計回りに見ていって、切れ込み $j$ までの範囲のピースをすべてもらう。
  • 青木君は、残りのピースをすべてもらう。
  • 高橋君がもらったピースの $1$ ピースあたりのイチゴの個数の平均値が青木君がもらったピースの $1$ ピースあたりのイチゴの個数の平均値以上であるとき、高橋君の勝ちです。そうでないとき、青木君の勝ちです。
• 青木君が勝つために最適な切れ込みを選ぶとき、高橋君は必ず勝つためにはどの切れ込みを選べばよいか求めてください。
• そのような切れ込みが、存在しないときは -1 を、複数存在する場合はそのうち番号が最小のものを答えてください。

• $2 \leq N \leq 5 \times 10^{5}$
• $0 \leq A_i \leq 5 \times 10^{5}$

長いので、「1ピース当たりのイチゴの個数の平均値」を(A)と表記する。

問題文では「高橋君 vs 青木君」の(A)で勝負しているが、結局これは「高橋君 vs 全体」と考えてよい。
高橋君の(A)が全体の(A)以上ならよい。
全体の(A)は固定値で、入力から求められる。これを $\mu$ とする。

ピース $i$ から数えて、

• 1個目のピースまでの(A)
• 2個目のピースまでの(A)
• :
• $N-1$ 個目のピースまでの(A)

これらが全て、$\mu$ 以上である必要がある。

競プロで「$A_l～A_r$ の平均値が $x$以上」の言い換えで頻出なのが、 「$A_l-x,A_{l+1}-x,...,A_{r}-x$ の総和が0以上」である。

今回の場合、$(A_i-\mu,A_{i+1}-\mu,...,A_N-\mu,A_1-\mu,...,A_{i-2}-\mu)$ の $N-1$ 項の数列の先頭からの累積和が、全て0以上でなければならない。

で、上記の $i=1$ からの $A_i-\mu$ の累積和を $S$ とすると、 $i$ から $j$ までの累積和は $S_j-S_{i-1}$ と表される。

これが $j=i,i+1,...$ の全てで0以上となるには、$S_{i-1}$ が最小となるような $i$ （複数ある場合は、最も小さくなるもの）を選べばよいとわかる。

少しの枝刈りで愚直にシミュレーションすれば通ってしまう。（ジャッジに撃墜ケースがなかっただけと思われる）

$i=1,2,...,N$ の順に、青木君がどこを切っても高橋君の(A)が平均値未満にならないことを $O(N)$ で愚直に確かめる。
最初に見つかった $i$ が答え。

ただし、1ピースのみの情報で判定できるものは最初にしてしまう。 つまり、高橋君が切れ込み $i$ を選んだとき、 青木君は「ピース $i-1$ のみを取る」または「ピース $i$ のみを高橋君に押しつける」ことができる。
これがそれぞれ「全体平均値を超える」「全体平均値を下回る」ような $i$ なら調べるまでもなくアウト。
この簡単に判定できる2ピースのみ最初に調べてやれば、ランダムケースなら $O(N)$ で調べる前に多くをはじける。
または、$O(N)$ で調べている間に多くはNGになり打ち切れる。

ただ、ランダムでない、以下のような入力でほぼ $O(N^2)$ かかってしまうため、嘘解法。

500000
10 10 10 ... 10 9 11 10

H - Good bye, AtCoder Land.

• AtCoder Land には $N$ 個のアトラクションがあります。
• $i$ 番目のアトラクションには、以下の $2$ 通りの搭乗方法があります。
  • 通常通り搭乗する。$A_i$ 分後に搭乗が終了する。
  • ファストパスを使って搭乗する。$B_i$ 分後に搭乗が終了する。このとき、ファストパスが $1$ 枚消費される。
• あなたはファストパスを $K$ 枚持っています。
• 同じアトラクションに複数回搭乗しないものとすると、 $T$ 分後までに最大でいくつのアトラクションに搭乗できますか？
• 但し、アトラクションを乗り換える時間は無視できること、最後に搭乗するアトラクションについて $T$ 分後までに搭乗が終了している必要があることに注意してください。

• $1 \le K \le N \le 2 \times 10^5$
• $1 \le T \le 10^{18}$
• $1 \le B_i \le A_i \le 10^{12}$

とりあえず $B_i \le A_i$ なので、$B_i$ の小さい方から $K$ 枚のファストパスの消費を試みる。
途中で $B_i$ の合計が $T$ を超えるならそこまで。

$K$ 枚使ってしまったら、もうファストパスは使えない。
使わずに新規アトラクションを増やす方法は、以下のいずれかである。

• まだ乗っていない新たなアトラクションに、$A_i$ 分使って乗る
• 既にファストパスで乗ったアトラクション $j$ に追加で $A_j-B_j$ 分使って「ファストパスを使わなかった」ことにして、まだ乗っていない新たなアトラクション $k$ にファストパスを使って $B_k$ 分で乗る

よって、その時点時点で有効な「最小の $A_i$」と「最小の $A_j-B_j+B_k$」の小さい方を、 総時間が $T$ を超えない範囲で採用することを繰り返せばよい。

• まだ乗っていないアトラクションの $A_i$
• まだ乗っていないアトラクションの $B_i$
• 既にファストパスを使って乗った（かつ、使わなかったことにはしていない）アトラクションの $A_i-B_i$

これらをそれぞれ、要素削除可能な優先度付きキューで管理しておけばよい。

Python3

from heapq import heapify, heappop, heappush, heapreplace


def solve(n, k, t, attractions):
    aaa = []
    bbb = []
    for i in range(n):
        a, b = attractions[i]
        aaa.append((a, i))
        bbb.append((b, i))
    heapify(aaa)
    heapify(bbb)

    ans = 0
    ddd = []
    status = [0] * n
    for _ in range(k):
        b, i = heappop(bbb)
        if b > t:
            return ans
        ans += 1
        t -= b
        status[i] = 1
        heappush(ddd, attractions[i][0] - b)

    while True:
        while len(aaa) and status[aaa[0][1]] != 0:
            heappop(aaa)
        while len(bbb) and status[bbb[0][1]] != 0:
            heappop(bbb)
        if len(aaa) == 0 or len(bbb) == 0:
            return ans
        replace_pass = bbb[0][0] + ddd[0]
        with_no_pass = aaa[0][0]
        if replace_pass <= with_no_pass:
            if replace_pass > t:
                return ans
            t -= replace_pass
            b, i = heappop(bbb)
            ans += 1
            status[i] = 1
            heapreplace(ddd, attractions[i][0] - b)
        else:
            if with_no_pass > t:
                return ans
            t -= with_no_pass
            a, i = heappop(aaa)
            ans += 1
            status[i] = 1


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