ARC079 E: Decrease (Judge ver.)

arc079.contest.atcoder.jp

解き方

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

ハマったところ

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

github.com