2003/Contest/ソウル大会

Problem D : People like people

問題概要

N(1 <= N <= 10000)人の生徒が、それぞれ最大3人の自分以外の生徒に投票する。(投票しない人もいる)

以下の条件を満たしている生徒の集合をCoreと呼ぶことにする。

   その集合内のすべての生徒が
   ・投票している
   ・その集合内の人の何人かに投票しているが、その集合外の人には投票していない。
   ・その集合内の誰かから投票されている

要素数最大のCoreの要素数(Coreが無ければ0)を出力する。という問題です。

難易度

普通からやや難。一万人いたときに計算がはまることもある。(谷口)

方針さえ立てば30分以内で解けるボーナス問題。ただし2003ソウル大会では、もっと易しい問題が出題されているから、後回しかな?(菊地)

解法

ある生徒(ミクルンとでも呼んでおこう)がコアに入っていると仮定すると、ミクルンが投票した人たちもコアに含まれる。その人たちが投票した人もまたコアで…と芋づる式にコアが成長する。しかし、コアのメンバーが誰もミクルンに投票していなければコアの条件を満たさない。

このアルゴリズムのオーダーは最悪の場合でも O(N^2) なので、N=10000でも問題なし。(菊地)

議論・その他


ファイルを添付する

[添付ファイル一覧] [全ページの添付ファイル一覧]
アップロード可能最大ファイルサイズは 10,240KB です。

管理者パスワード:

Last-modified: 2009-11-06 (金) 13:26:46 (3094d)