ABC065-B - Trained? を解く - 考えて競プロする

ABC065-B - Trained?

結構混乱する問題だ

適当にシミュレーションしてみて、ボタン2が光ればOK、としたいところだが…

光らない場合は無限ループしているということになる

無限ループになった場合にすぐに気づけるよう

一度押したボタンを記録していく必要がある

とりあえず、ボタンの数と同じ長さのリストを用意して

そこにメモしていく方法で解くことにする

以上を踏まえて書いたコードを以下に示す

提出したコード

# 入力
N=int(input())

l=[]
for i in range(N):
  l.append(int(input()))

# 押してない：0
# 押した：1
l2=[0]*N

# 1番目は「押した：1」にしておく
l2[0]=1

# 回数カウント
c=0

i=1
while True:
  # 回数をインクリメント
  c+=1

  # 次のボタン番号を取得
  i=l[i-1]

  # 2番目のライトが光る場合は回数を出力して終了
  if i==2:
    print(c)
    exit()

  if l2[i-1]==1:
    # 無限ループ確定で終了
    print(-1)
    exit()
  else:
    # 押した／押してない を更新
    l2[i-1]=1

提出結果はACでした

解説を見てみたところ

「シミュレーションをN回分回して、2のボタンが光らなかった場合は

ループしていると判断する」というループの判断方法を取っていた

そっちの方が簡単だし良い実装ですね…

解説PDFを読みたい方は以下のリンクからご覧ください