repovive starter round 10 B - Rise to the Occasion
- サイト
- repovive.com
- コンテスト
- repovive starter round 10
- 問題
- B - Rise to the Occasion
長さ の整数列 と正の整数 が与えられます。カウンタ は最初 です。 を好きな順に並べ替えてから順に見ていき、値 について なら を 増やし、そうでなければ を 減らします。最後の の最大値を求める問題です(、、)。
を昇順に並べてシミュレーションした結果が答えです。
カウンタが大きいほうが得
Section titled “カウンタが大きいほうが得”個の値を見た時点の は、増やした回数を として です。よって、同じ個数を見た時点の 2 つのカウンタの値 の差は の倍数です。
のとき、同じ値 を見たあとも大小は逆転しません。両方が増える場合と両方が減る場合は明らかです。 で だけが増える場合は、 なので です( となることはありません)。
したがって、途中のある時点でカウンタが大きいほうが、残りの並びが同じなら最後のカウンタも大きいか等しいです。
隣り合う 2 つの入れ替え
Section titled “隣り合う 2 つの入れ替え”並びの中で が の順に隣り合っているとき、 の順に入れ替えても、2 つを見たあとのカウンタは小さくならないことを示します。2 つを見る前のカウンタを とします。
- のとき:どちらの順でも 1 つ目で増えて になります。2 つ目で増えるのは、元の順では のとき、入れ替えると のときで、後者のほうが条件が弱いです。
- のとき:元の順では で増えて で減り、入れ替えると で減って で増えます( なので)。どちらも です。
- のとき:どちらの順でも 1 つ目で減って になります。2 つ目で増えるのは、元の順では のとき、入れ替えると のときで、後者のほうが条件が弱いです。
どの場合も、入れ替えたほうが増える回数が多いか等しいので、カウンタも大きいか等しいです。上で示したことから、最後のカウンタも小さくなりません。この入れ替えを繰り返すと昇順になるので、昇順が最適です。
計算量はソートの です。
Python
n, x, y = map(int, input().split())a = list(map(int, input().split()))a.sort()t = 0for v in a: if t > v: t -= y else: t += xprint(t)