ABC139 E - League - あっとのTECH LOG

問題原文

問題要旨

$N$ 人の選手が以下のルールで総当たりで試合を行う。

１日に最大１試合を行う。
各選手について、試合を行う順番が[tex: A{i1}, A{i2}...] のような形で決められており、この順番でしか試合を行えない。

ルールに基づいた上で、最低何日あれば全ての試合を行えるか。
ただしルールを満たせない場合は−１を出力せよ。

$1 \leq N \leq 10^{5}$

解法

全ての試合が完了するまでの間、各選手について「試合を行えるかをチェックし、行えるなら行う」解法がまず浮かぶ。（全ての選手が試合を行えない状態がきたら−１）
一見高速そうに見えるが、これだと「各日で１試合しか進まない」ようなケースでTLEする。

ここで良く考えると、「ある日に試合を行える可能性がある選手」というのは、 「前の日に試合を行った選手 or 前の日に試合を行った選手と今日試合をするかもしれない選手」 であることがわかる。これをキューなどに詰めて回すようにすれば、各選手について試合を行えるかチェックする回数は $N$ 回になり間に合う。

実装

たいへん笑

N = int(input())
A = [list(map(lambda x: int(x) - 1, input().split())) + [-1] for i in range(N)]  # 番兵
 
ans = 0
matched = 0  # 行った試合数
marker = [0] * N  # 各Aiについてどこまで見たかを管理する
que = list(range(N))  # 次に試合を行えるかもしれない選手を管理
 
while matched < N * (N - 1) // 2:
    already_matched = set()  # すでにその日に試合を行った選手を管理
    next_que = []  # 翌日試合を行える可能性のある選手を管理
 
    while que:
        player = que.pop()
        partner = A[player][marker[player]]
 
        # 互いに試合を行いたいと思い合っている選手がいて、その二人とも当日試合をまだ行っていない
        if A[partner][marker[partner]] == player:
            if not ((player not in already_matched) and (partner not in already_matched)):
                continue
 
            matched += 1
 
            marker[player] += 1
            marker[partner] += 1
 
            already_matched.add(player)
            already_matched.add(partner)
 
            next_que.append(player)
            next_que.append(partner)

        if not next_que:
            print(-1)
            break

    ans += 1
    que = next_que[:]
 
else:
    print(ans)

余談

「試合を行う順番だけ決められている」ので、これは有向グラフという形である試合からある試合への辺が伸びている状態と言い換えることができる。
よって、トポロジカルソートをした上で有向グラフ上での最長経路を求めればよい。ただし、グラフ上に閉路が存在する場合にはどう頑張ってもルールに矛盾してしまうので注意する。

実装は辞書で持つと死ぬので気合で隣接リストとかで持つ。ぶっちゃけ↑の方が楽だと思う。好みとは思うんですが。
最初の解法も、やってることはトポソした有向グラフ上で１つずつ進めていってるのと変わらないですね。

感想

計算量を落とせないか？ではなくて、「無駄な計算はしてないか？」 と考えるのが計算量削減の１つのとっかかりっぽそう。
もちろん他の方法で落ちることもありますけどね。