コンテンツにスキップ

repovive starter round 10 B - Rise to the Occasion

サイト
repovive.com
コンテスト
repovive starter round 10
問題
B - Rise to the Occasion

長さ nn の整数列 aa と正の整数 x,yx, y が与えられます。カウンタ tt は最初 00 です。aa を好きな順に並べ替えてから順に見ていき、値 vv について t≤vt \le v なら tt を xx 増やし、そうでなければ tt を yy 減らします。最後の tt の最大値を求める問題です(1≤n≤2×1051 \le n \le 2 \times 10^5、1≤x,y≤1091 \le x, y \le 10^9、−109≤ai≤109-10^9 \le a_i \le 10^9)。

aa を昇順に並べてシミュレーションした結果が答えです。

kk 個の値を見た時点の tt は、増やした回数を pp として px−(k−p)y=p(x+y)−kypx - (k - p)y = p(x + y) - ky です。よって、同じ個数を見た時点の 2 つのカウンタの値 t≤t′t \le t' の差は x+yx + y の倍数です。

t≤t′t \le t' のとき、同じ値 vv を見たあとも大小は逆転しません。両方が増える場合と両方が減る場合は明らかです。t≤v<t′t \le v < t' で tt だけが増える場合は、t′≥t+(x+y)t' \ge t + (x + y) なので t′−y≥t+xt' - y \ge t + x です(t>v≥t′t > v \ge t' となることはありません)。

したがって、途中のある時点でカウンタが大きいほうが、残りの並びが同じなら最後のカウンタも大きいか等しいです。

並びの中で u>vu > v が u,vu, v の順に隣り合っているとき、v,uv, u の順に入れ替えても、2 つを見たあとのカウンタは小さくならないことを示します。2 つを見る前のカウンタを tt とします。

  • t≤vt \le v のとき:どちらの順でも 1 つ目で増えて t+xt + x になります。2 つ目で増えるのは、元の順では t+x≤vt + x \le v のとき、入れ替えると t+x≤ut + x \le u のときで、後者のほうが条件が弱いです。
  • v<t≤uv < t \le u のとき:元の順では uu で増えて vv で減り、入れ替えると vv で減って uu で増えます(t−y<t≤ut - y < t \le u なので)。どちらも t+x−yt + x - y です。
  • u<tu < t のとき:どちらの順でも 1 つ目で減って t−yt - y になります。2 つ目で増えるのは、元の順では t−y≤vt - y \le v のとき、入れ替えると t−y≤ut - y \le u のときで、後者のほうが条件が弱いです。

どの場合も、入れ替えたほうが増える回数が多いか等しいので、カウンタも大きいか等しいです。上で示したことから、最後のカウンタも小さくなりません。この入れ替えを繰り返すと昇順になるので、昇順が最適です。

計算量はソートの O(nlog⁡n)O(n \log n) です。

Python
n, x, y = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
t = 0
for v in a:
if t > v:
t -= y
else:
t += x
print(t)