AtCoder Grand Contest 018 B - Sports Festival

「3月中に毎日1問解いて黄色になろう！」キャンペーン10問目。

問題概要

N人の人はM種類のスポーツの内開催されていて一番好きなスポーツにしか出ない。一番スポーツがばらけるように開催するかしないか選んだ時、一番人が集まるスポーツの人数を求めよ。

https://beta.atcoder.jp/contests/agc018/tasks/agc018_b

解説

2部グラフですね。フローが流せます。

全部容量1にして、全体をまとめるs,tは特に考えません。N人の状態について、「何番目まで得意なスポーツがやっているか見たか」という情報を持たせます。この優先順序でフローを流します。

流した後、M個のスポーツについて最も集まっている＝逆辺の本数が最も多いものの個数をretとします。retより小さい解を求めるにあたって、ret以上の本数が流れているスポーツを開催する理由はありません。フラグを折った後に、逆辺に沿って流して、次の順位を見ます。

このようにすると、M個のスポーツが無くなる前にループが終わる＝M個のスポーツ全てについてret未満の辺が入っているということになるので、前に戻ってそれより小さい解を探し、最後まで見終わってしまったらそこでプログラムを止めます。

計算量は一番外側（retを更新）が最悪O(M)、その内側のチェックO(M)、イテレータ部分O(M)、戻す作業O(N)なのでO(M²(M+N))という感じでしょうか。ちょっと分かりませんが…

https://beta.atcoder.jp/contests/agc018/submissions/2252848

import sys
n,m=map(int,input().split())
a=[list(map(int,input().split())) for i in range(n)]
for i in range(n):
    for j in range(m):
        a[i][j]-=1
itr=[0 for i in range(n)]
opend=[True for i in range(m)]
back=[[] for i in range(m)]
for i in range(n):
    back[a[i][0]].append(i)
ret=10**9
while True:
    tmp=0
    for i in range(m):
        tmp=max(tmp,len(back[i]))
    ret=min(ret,tmp)
    for i in range(m):
        if len(back[i])>=ret:
            opend[i]=False
            for j in range(len(back[i])):
                source=back[i][j]
                while not opend[a[source][itr[source]]]:
                    itr[source]+=1
                    if itr[source]==m:
                        print(ret)
                        sys.exit()
                back[a[source][itr[source]]].append(source)
            back[i]=[]

感想

自然とフローが浮かんだので進歩？