新規
編集
添付
時間制限:1000ミリ秒
メモリ制限:10000KB
きみだれ？
問題 
フレンドリー小学校1年の最初の登校日には、各々の児童は知りあいでない児童と1分間の会話を行う習慣がある。ボブが見知らぬ顔を見かけると、彼は「君だれ？」と言う。すると相手は「僕チャーリー。君は？」と言う。そしてボブは「僕ボブ！」と言い、そして彼らは1分間会話する。これは非常に可愛らしい。そして、1分話しおえたら、彼らは別れて、それぞれまた挨拶しなければならない相手を探す。これには時間がかかる。29人または30人の互いに見知らないクラスでは、これは29分かかる。先生からしてみれば、アルファベットの勉強時間のほうが大事である。もちろん、誰も互いに知り合いでないような1年のクラスというのは珍しい。普通は隣人や遊び友達がいるので、彼ら同士は1分間の会話は必要ではない。
2人の先生が1年を担任することとなった。時間を節約するため、クラス分けは人数差が最大でも1人であるように2つに分けられ、かつ彼らの挨拶ができるだけ短く終わるようにしたい。入学してくる児童は60人を超えることはない。
どのように児童をクラスに割りあてればよいだろうか？あなたの仕事は、この質問に答えるソフトウェアを書くことである。
入力
学校レコードは各児童の友達関係を示す数値の列からなる。もし29人の児童がいるなら、彼らは1から29までの番号がつけられる。各児童のレコードは、最初にその児童のID(この場合は1から29の番号)が書いてあり、次にその児童の知り合いの数が書いてあり、その次にはそれら知り合いをあらわす番号がリストされている(順番に特別な意味はない。)例えば、次のレコード
17 4 5 2 14 22
は、児童17は4人と知り合いである: 5,2,14,22。 全ての児童レコードを結合した数字の列として、入学児童全体のレコードが提供される。例えば、
1 1 2 2 1 1
は、互いに知りあう2人のみが入学するクラスを意味するデータベース全体である。また、
1 2 3 4 2 2 3 4 3 2 1 2 4 2 1 2
は、1は2を知らず、3は4を知らないが、他のペアは互いを知っていることを意味する。
データベースは無矛盾性が検証されているので、AがBを知っていれば、BはAを知っている。
出力
出力は、挨拶にかかる最短時間を記した1つの数字のみである。例えば、さきの2人の児童のみからなるデータについては、
0
のみが正答となる。
入力例
1 2 3 4 2 2 3 4 3 2 1 2 4 2 1 2
出力例
0
ヒント
問題をより扱いやすくするために、以下のような言い換えができる。ちょうど2つのクラスがある。どちらも30名を超えることはない。児童は可能な限り均等にクラスに配分される。児童の孤独度を、その児童が知らないクラス内の児童の数とする。あなたはクラスを、最も孤独な児童の孤独度が最小となるように改良しなければならない。例えばサンプルデータについては、1と3を最初のクラスに、2と4を次のクラスに配分すれば、彼らは互いを知る時間が要らなくなる。
出典
South Central USA 1998
