code-festival-2016-qualA B - 仲良しうさぎ 【Python解答例】
AtCoder ProblemsのRecommendationがあることを最近知りました (^_^;)
おすすめされたら解きたくなってしまいましたので、記事にしていきたいと思います。
現在のレート 351の自分におすすめされたのはCODE FESTIVAL 2016 qual AのB - 仲良しうさぎ です。
CODE FESTIVAL 2016 qual A B - 仲良しうさぎ
問題文
N 匹のうさぎがいます。 うさぎには 1 から N まで番号が振られています。
各 1≤i≤N について、うさぎ i はうさぎ ai が好きです。
ただし、自分自身が好きなうさぎはいません。 すなわち、ai≠i です。
うさぎ i とうさぎ j のペア (i,j) (i<j) が次の条件を満たすとき、ペア (i,j) は仲良しであるといいます。
うさぎ i はうさぎ j が好きであり、うさぎ j はうさぎ i が好きである。
仲良しなペアの個数を求めてください。
制約
・2≤N≤10^5
・1≤ai≤N
・ai≠i
解答例
n = int(input()) A = list(map(int, input().split())) ans = 0 for i in range(n): if A[A[i]-1] == i + 1: ans += 1 else: print(ans//2)
解説
N匹のうさぎがいて、それぞれ自分以外の1匹のうさぎが好きです。
このなかで両想いのうさぎが何組いるかを答える問題です。
うさぎは全部で20万なので、すべてのうさぎについて両想いか全探索して調べていきました。
i番目のうさぎについてA[A[i]-1] == i + 1が真のとき両想いとなります。
左辺 A[A[i]-1] を説明します。
[ ]内のA[i]-1について、i番目のうさぎが好きなのはA[i]のうさぎです。
A[A[i]-1]の意味は、i番目のうさぎが好きなうさぎが好んでいる個体の番号を調べています(もう恋なんてしないなんて言わないよ絶対…)
配列は0から始まるので[A[i]-1]となっています。
右辺はi番目のうさぎを表しています。
同様に配列が0からなので番号を合わせるために1を足しています。
配列の番号あわせのため1を足したり引いたりしてますが、以上の理由でA[A[i]-1] == i + 1 が真なら両想いになります。
これをすべてのうさぎについて調べていくと両想いのうさぎの数がわかります。
解答するのはペアの数なので、両想いのうさぎの数を2で割れば求める答えとなります。
この考え方でACをとれました。
レコメンドされた問題を解いていくのもおもしろいですね!
実は 初中級者が解くべき精門100 とかまだ終わってないんですけど…気分転換しちゃいました ( ´∀` )
モチベーションの維持が大切!っと自分に信じ込ませて学習を続けていきたいです。