Problem D : People like people †問題概要 †N(1 <= N <= 10000)人の生徒が、それぞれ最大３人の自分以外の生徒に投票する。（投票しない人もいる） 以下の条件を満たしている生徒の集合をCoreと呼ぶことにする。 その集合内のすべての生徒が ・投票している ・その集合内の人の何人かに投票しているが、その集合外の人には投票していない。 ・その集合内の誰かから投票されている 要素数最大のCoreの要素数(Coreが無ければ0)を出力する。という問題です。 難易度 †普通からやや難。一万人いたときに計算がはまることもある。（谷口） 方針さえ立てば30分以内で解けるボーナス問題。ただし2003ソウル大会では、もっと易しい問題が出題されているから、後回しかな？（菊地） 解法 †ある生徒（ミクルンとでも呼んでおこう）がコアに入っていると仮定すると、ミクルンが投票した人たちもコアに含まれる。その人たちが投票した人もまたコアで…と芋づる式にコアが成長する。しかし、コアのメンバーが誰もミクルンに投票していなければコアの条件を満たさない。 このアルゴリズムのオーダーは最悪の場合でも O(N^2) なので、N=10000でも問題なし。（菊地） 議論・その他 †ファイルを添付する † |
