🙆‍♀️

AGC024 C - Sequence Growing Easy

2022/11/23に公開約600字

問題のリンク

  • 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

Discussion

ログインするとコメントできます