AtCoder ABC 068 D - Decrease (Contestant ver.) (Python)
irisruneです。流石にABC132Fは難しすぎたので久々に過去問です。
問題
操作を行った結果として状態がどのように変わるか、どのような状態が停止状態となるかを把握することが重要です。
import sys import numpy as np def main(): k = int(input()) n = 50 an = [n - 1 + (k // n) - (k % n) for _ in range(n)] for i in range(k % n): an[i] += n + 1 print(n) print(*an) main()
公式解説ではいきなり操作を逆から考えていますが、今回は初めに操作を実行順に考えて大筋を掴むアプローチを取りました。
まず、操作を行った結果どのように状態が変化するかを考えると、最も大きい要素の値が減る一方で他の要素の値が増えるため、数列の全要素の値の和は減少することが簡単にわかります。
そこで数列の全要素の値の和に注目してみます。操作の停止条件は数列の最大値がとなることであるため、数列の全要素の値の和がより大きければ操作は停止しないということになります。
逆に数列の全要素の値の和がちょうどとなるとき操作が停止する場合を考えます。この場合停止状態は数列の全要素の値がとなり、ここから操作を逆順に行うことで初期状態を求めます。
実際のプログラム上ではとおき、数列の全要素に回ずつ逆操作を行うと全要素の値がずつ増加することを利用して初期状態を求めています。
ただし、最後に回逆操作を行う部分については、数列の初期状態の最大値が以下でなければならないことに注意して操作を行う必要があります。回の逆操作をすべて数列の同一要素に対して実行すると、その要素の値が前述の条件を満たさないことがあるため、それぞれ別の要素に対して逆操作を行う必要があります。
なお、上記提出コードでは最後の回分の逆操作を忠実にシミュレートしていないので少しわかりにくいかもしれません。
雑記
- AtCoder Problemsを見ていると、合計220ACなのに100ACに到達している言語がないことに気付きました。
- 実はただの飽き性なだけでは…?
- 逆に言えば言語を変えるだけで違った体験ができるのはプログラミングのいいところですね。