Educational Codeforces Round 115 B. Groups

題意

• あなたは異なる曜日(月曜から金曜の5日間)の2日に授業をすることにします。
• $2n$人の生徒がいます。それぞれの生徒は授業を受けられる日を1, 出られない日を0としてスケジュールを全員が提出しました。
• あなたは各授業がn人ぴったりであるように授業のクラスを分けたいです。
• 各生徒は2つ授業両方には参加できません。

こう考えた

総当たりをします。各曜日を総当たりするには、

for i in range(5):
 for j in range(i+1, 5):
  # i と jの２つの曜日を選んだ

とすればよいです。

さて、i,jを定めたとき、以下を求めることができます。

numboth: iもjも出席できるの学生
numi: iだけに参加できる学生
numj: jだけに参加できる学生
numng: 両方参加できない学生

この時、次のように順に考えます。

• まず、合計の人数が$2n$で$n$人に分けたいのだから$numng$が1人以上いる場合、NGです。(絶対にn人に満たない授業ができてしまいます。)
• numiかnumjがnをよりも多い場合NGです。(もう片方の授業はn人未満になります)
• それ以外の場合、絶対に成立します。$numi+numj+numboth = 2n$なので、$numi + x = n$となる$0 \leq x \leq n$は必ず存在し、$numj + (numboth - x) = n$は明らかです。

この処理をすべてのi,jに対して行い、１つでもOKならYESです。すべてのi,jについて成り立たないならNOです。

実装

def do():
    n = int(input()) // 2
    dat = []
    for i in range(2*n):
        dat.append(list(map(int, input().split())))
    for i in range(5):
        for j in range(i+1, 5):
            cani = canj = canboth = canno = 0
            for ind in range(2*n):
                if dat[ind][i] == dat[ind][j] == 1: canboth += 1
                elif dat[ind][i] == 1: cani += 1
                elif dat[ind][j] == 1: canj += 1
                else: canno += 1
            if canno > 0: continue
            if cani > n or canj > n: continue
            print("YES")
            return
    print("NO")
q = int(input())
for _ in range(q):
    do()