あるエンジニアのAtCoder奮闘記

東京都港区にあるアミフィアブル株式会社のエンジニアが、AtCoderで解いた問題について振り返ったりしていく会社公認のブログです。

AtCoder ABC 068 D - Decrease (Contestant ver.) (Python)

irisruneです。流石にABC132Fは難しすぎたので久々に過去問です。

問題

atcoder.jp

操作を行った結果として状態がどのように変わるか、どのような状態が停止状態となるかを把握することが重要です。

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()

公式解説ではいきなり操作を逆から考えていますが、今回は初めに操作を実行順に考えて大筋を掴むアプローチを取りました。

まず、操作を行った結果どのように状態が変化するかを考えると、最も大きい要素の値がN減る一方で他の要素の値が1増えるため、数列の全要素の値の和は1減少することが簡単にわかります。

そこで数列の全要素の値の和に注目してみます。操作の停止条件は数列の最大値がN-1となることであるため、数列の全要素の値の和がN(N-1)より大きければ操作は停止しないということになります。

逆に数列の全要素の値の和がちょうどN(N-1)となるとき操作が停止する場合を考えます。この場合停止状態は数列の全要素の値がN-1となり、ここから操作を逆順に行うことで初期状態を求めます。

実際のプログラム上ではN=50とおき、数列の全要素に1回ずつ逆操作を行うと全要素の値が1ずつ増加することを利用して初期状態を求めています。

ただし、最後にK\mod N回逆操作を行う部分については、数列の初期状態の最大値が10^{16}+1000以下でなければならないことに注意して操作を行う必要があります。K\mod N回の逆操作をすべて数列の同一要素に対して実行すると、その要素の値が前述の条件を満たさないことがあるため、それぞれ別の要素に対して逆操作を行う必要があります。

なお、上記提出コードでは最後のK\mod N回分の逆操作を忠実にシミュレートしていないので少しわかりにくいかもしれません。

雑記

  • AtCoder Problemsを見ていると、合計220ACなのに100ACに到達している言語がないことに気付きました。
    • 実はただの飽き性なだけでは…?
    • 逆に言えば言語を変えるだけで違った体験ができるのはプログラミングのいいところですね。