ABC469Dを解いた【候補の絞り込み】

筆者はレート800前後の茶～緑コーダ

ABC469のD問題を解いていく

実装コード

答えの組 (x, y) は必ず1回目の大会の決勝進出者のどちらかなので、候補を2人に絞って相方を数え上げる。

• N, M と各大会の決勝進出者 (a, b) を0-indexedで受け取る
• 1回目の決勝進出者 AB[0][0] と AB[0][1] をそれぞれ x にして、同じ処理を2回する
• x が決勝に出ていない大会だけを見て、その回数を t、各プレイヤーの決勝進出回数を C[i] とする
• t == 0 なら x だけで全大会を満たすので、x 以外のどのプレイヤー i と組んでもよい
• t > 0 なら残り t 大会すべてに出ている C[i] == t のプレイヤー i だけが相方になれる
• 条件を満たす組は (min(i, x), max(i, x)) の形で集合 S に入れ、2通りの間の重複を除く
• 最後に len(S) を出力する

main.py

from bisect import bisect_left, bisect_right, insort_left, insort_right
from collections import defaultdict, Counter, deque
from functools import reduce, lru_cache
from itertools import product, accumulate, groupby, combinations
import sys
import os
def rI(): return int(sys.stdin.readline().rstrip())
def rLI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def rI1(): return (int(sys.stdin.readline().rstrip())-1)
def rLI1(): return list(map(lambda a:int(a)-1,sys.stdin.readline().rstrip().split()))
def rS(): return sys.stdin.readline().rstrip()
def rLS(): return list(sys.stdin.readline().rstrip().split())
IS_LOCAL = int(os.getenv("ATCODER", "0"))==0
err = (lambda *args, **kwargs: print(*args, **kwargs, file=sys.stderr)) if IS_LOCAL else (lambda *args, **kwargs: None)

def main():
    N, M = rLI()
    AB = []
    for _ in range(M):
        a, b = rLI()
        AB.append((a - 1, b - 1))

    S = set()

    x = AB[0][0]
    C = [0] * N
    t = 0
    for a, b in AB:
        if x == a or x == b:
            continue
        C[a] += 1
        C[b] += 1
        t += 1

    if t == 0:
        for i in range(N):
            if i != x:
                S.add((min(i, x), max(i, x)))
    else:
        for i in range(N):
            if C[i] == t:
                S.add((min(i, x), max(i, x)))

    x = AB[0][1]
    C = [0] * N
    t = 0
    for a, b in AB:
        if x == a or x == b:
            continue
        C[a] += 1
        C[b] += 1
        t += 1

    if t == 0:
        for i in range(N):
            if i != x:
                S.add((min(i, x), max(i, x)))
    else:
        for i in range(N):
            if C[i] == t:
                S.add((min(i, x), max(i, x)))

    print(len(S))

if __name__ == '__main__':
    main()

感想

「答えの組には必ず1回目の決勝進出者が入る」という絞り込みがポイントで、
そこさえ気づけば、あとは片方を固定して残りの大会に全部出ているプレイヤーを数えるだけなので、C[i] == t の判定で一気に片付くのが良かった。