ABC435 C – Domino

C - Domino

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

atcoder.jp

N個のドミノが並んでいて1番目のドミノを倒した時に全部で幾つのドミノが倒れるかを求める問題。

maxでどこまで倒れるかを常に持っておき、maxがi+1以下の場合ドミノが倒せないと考えてみた。

入力例1で考えてみると、まず一つ目（i=0）のドミノを倒すとi+A[i]未満のドミノが倒れるため2と3のドミノまで倒れる。

この時max=3

iが1の時のドミノA[1]=1なのでi+A[i]=2でmaxは3のまま

次に、iが2の時のドミノがA[2]=1だったとする。

i+A[i]=3となりmaxは3で、maxがi+1=3以下となるため、これまで倒れたどのドミノも次のドミノを倒せない。

以下でACできました。

def i_map(): return map(int, input().split())
def i_list(): return list(map(int, input().split()))

n = int(input())
a = i_list()

ans = 0
ma = 0
for i in range(n):
  ans+=1
  ma = max(ma, i+a[i])
  if ma <= i+1:
    break

print(ans)Code language: Python (python)