Livedoorブログからの移動
はてなブログからの移動

arc079.contest.atcoder.jp

解き方

  • 1回の操作で、数列の総和は-1される
    • 操作回数は最低でも\sum a_i - N(N-1)
    • \sum a_i回操作をすると、総和が0になるのでこれが操作回数の上限になる（多分）
  • K回の操作後、条件を満たすかどうかは全体を+Kしたあと、K回どれかの要素を-N-1する操作と考えればO(N)で判断可能
    • ARC075 Dと同じような考え方
  • 最初に上げた値の範囲全部を調べていけばO(N^3)で判定できる

ハマったところ

  • ARC075 Dと類似であることを認識するまでにまず時間がかかった気がする
  • 二分探索を構築できないか迷った時間は結果的には無駄だった

github.com