第９回日本情報オリンピック　予選３

2009年12月17日
情報オリンピック日本委員会

解説

この問題では，配列を利用して問題を解くことが要求されている．

また，発展的な方法としてグラフ構造を用いて答えを求めることも出来る．

想定解法

この問題では，ともだちのともだちの人数を求める必要がある．ここでまず，ともだちの人数を求める方法を考えてみる．

ともだちの人数を求める方法はいくつかあるが，そのなかに配列を利用した方法がある． この方法では，1番からn番の生徒を配列のそれぞれに対応させる． ともだち同士の組み合わせ全体に対して片方が1番であるかを調べて配列に招待されたかどうか印をつける． 最後に印の数を数えれば重複してカウントされることが無い．

上記の方法を拡張すると，ともだちのともだちを求めることが可能になる．
配列をもう一つ用意する．ともだち同士の組み合わせ全体に対して，先ほどの配列で印がついてる人とともだち同士の人を探す．新しい配列のその人に対応する場所に印をつける． このようにすると，ともだちのともだちである人に印がついた配列が完成する． あとは数を数えれば答えが求まる．

もちろん1番の人をカウントしないことや，ともだちの人数も忘れずにカウントする必要がある．