Loading [MathJax]/jax/output/CommonHTML/jax.js

目次

CodeQUEEN 2024 決勝 F,H問題メモ

CodeQUEEN 2024 決勝

F - Divide the Cake

F - Divide the Cake

問題文

制約

解法

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

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

ピース i から数えて、

これらが全て、μ 以上である必要がある。

競プロで「AlAr の平均値が x以上」の言い換えで頻出なのが、 「Alx,Al+1x,...,Arx の総和が0以上」である。

今回の場合、(Aiμ,Ai+1μ,...,ANμ,A1μ,...,Ai2μ)N1 項の数列の先頭からの累積和が、全て0以上でなければならない。

で、上記の i=1 からの Aiμ の累積和を S とすると、 i から j までの累積和は SjSi1 と表される。

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

嘘解法

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

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

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

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

500000
10 10 10 ... 10 9 11 10

H - Good bye, AtCoder Land.

H - Good bye, AtCoder Land.

問題文

制約

解法

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

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

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

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

Python3