長いので、「1ピース当たりのイチゴの個数の平均値」を(A)と表記する。
問題文では「高橋君 vs 青木君」の(A)で勝負しているが、結局これは「高橋君 vs 全体」と考えてよい。
高橋君の(A)が全体の(A)以上ならよい。
全体の(A)は固定値で、入力から求められる。これを μ とする。
ピース i から数えて、
これらが全て、μ 以上である必要がある。
競プロで「Al~Ar の平均値が x以上」の言い換えで頻出なのが、 「Al−x,Al+1−x,...,Ar−x の総和が0以上」である。
今回の場合、(Ai−μ,Ai+1−μ,...,AN−μ,A1−μ,...,Ai−2−μ) の N−1 項の数列の先頭からの累積和が、全て0以上でなければならない。
で、上記の i=1 からの Ai−μ の累積和を S とすると、 i から j までの累積和は Sj−Si−1 と表される。
これが j=i,i+1,... の全てで0以上となるには、Si−1 が最小となるような i (複数ある場合は、最も小さくなるもの)を選べばよいとわかる。
少しの枝刈りで愚直にシミュレーションすれば通ってしまう。(ジャッジに撃墜ケースがなかっただけと思われる)
i=1,2,...,N の順に、青木君がどこを切っても高橋君の(A)が平均値未満にならないことを O(N) で愚直に確かめる。
最初に見つかった i が答え。
ただし、1ピースのみの情報で判定できるものは最初にしてしまう。
つまり、高橋君が切れ込み i を選んだとき、
青木君は「ピース i−1 のみを取る」または「ピース i のみを高橋君に押しつける」ことができる。
これがそれぞれ「全体平均値を超える」「全体平均値を下回る」ような i なら調べるまでもなくアウト。
この簡単に判定できる2ピースのみ最初に調べてやれば、ランダムケースなら O(N) で調べる前に多くをはじける。
または、O(N) で調べている間に多くはNGになり打ち切れる。
ただ、ランダムでない、以下のような入力でほぼ O(N2) かかってしまうため、嘘解法。
500000 10 10 10 ... 10 9 11 10
とりあえず Bi≤Ai なので、Bi の小さい方から K 枚のファストパスの消費を試みる。
途中で Bi の合計が T を超えるならそこまで。
K 枚使ってしまったら、もうファストパスは使えない。
使わずに新規アトラクションを増やす方法は、以下のいずれかである。
よって、その時点時点で有効な「最小の Ai」と「最小の Aj−Bj+Bk」の小さい方を、 総時間が T を超えない範囲で採用することを繰り返せばよい。
これらをそれぞれ、要素削除可能な優先度付きキューで管理しておけばよい。