AtCoder ABC 228 B – Takahashi’s Secret Python解説

スポンサーリンク

Takahashi’s Secret

高橋君には N 人の友達がいます。N 人の友達はそれぞれ、友達 1 、友達 2 、… 、友達 N というあだ名で呼ばれています。ある日、高橋君はある恥ずかしい秘密を、友達の一人である友達 X に知られてしまいました。
i=1,2,…,N について、友達 i が高橋君の秘密を知ったとき、友達 Aiがまだ高橋君の秘密を知らなければ、友達 i は高橋君の秘密を友達 Aiにも教えてしまいます。高橋君の秘密は最終的に何人の友達に知られることになるでしょうか?

AtCoder Beginner Contest「Takahashi’s Secret」

高橋君の秘密が何人の友達に知れ渡るかを答える問題です。入力例をもとに秘密の伝わり方を見てみます。

入力例1
4 2
3 1<--(これが友達2) 1 2

この場合4人の友達のうち友達2が高橋君の秘密を知っています。友達2に書かれている数字は友達2が次に秘密を教える友達の番号です。ですので、友達2は次に友達1に秘密を教え、友達1は友達3に秘密を教えます。友達3は友達1に秘密を教えますが、すでに友達1は秘密を知っている、すなわちループが発生しているのでこれ以上秘密は伝わりません。よって入力例1では3人が高橋君の秘密を知ることになります。

ここからは実際にコードで書いていきます。

n, x = map(int, input().split())
a = list(map(int, input().split()))

b = [False] * n
cnt = 0

for _ in range(n):
    if b[x - 1] == False:
        b[x - 1] = True
        cnt += 1
        x = a[x - 1]
    else:
        break
        
print(cnt)
    

上記のコードではTrue, Falseを使ってループの管理をしています。初期値でFalse、秘密を知ったらTrueにして、Trueの友達に教えるまで人数をカウントアップしていきます。

n, x = map(int, input().split())
a = list(map(int, input().split()))

b = []
for _ in range(n):
    b.append(x)
    x = a[x - 1]
    
print(len(set(b)))

こちらのコードではflag管理をせずに秘密を知った友達の番号をリストに加えていきます。最後にsetを使って重複した要素を削除してlen関数で秘密を知っている友達の数を数えています。

AtCoderB問題

Posted by cheese