AGC024 C - Sequence Growing Easy

問題のリンク

• X_iがA_iになるためには、X_(i-1)=A_i-1, X_(i-2)=A_i-2 ... X_(i-A_i)=0となっている瞬間がないといけない・・・(1)
• 例えば、A_5 = 3になってほしいなら、A_2=0, A_3=1, A_4=2になっている瞬間が必要。
• したがって、以下の2パターンは確実に-1になる。

1. i - A_i < 0
2. A_i > A_(i+1)

• これ以外の場合は、構築可能。以下、実装の一例。
  まず、D_i = i - A_iを満たす配列Dを用意する。ここで、以下の2パターンは-1になる。

1. D_i < 0
2. D_i > D_(i+1)
   これ以外の場合を考える。i=1,2,...N-1について、　　
   D_i = D_(i+1)ならば、回数は1回のみ増える。なぜならば、もとの数列ではA_i+1=A_(i+1)となっているため、A_iを構築した後に1回の操作のみでA_(i+1)を作ることができるからである。　　
   それ以外の場合、回数はA_(i+1)だけ増える。(∵(1)) 以下の図が理解しやすいかもしれない。
   AC code