Problem p03321 (python)

Fixed submission:

"""
Writer:SPD_9X2
https://atcoder.jp/contests/arc099/tasks/arc099_c

なるべく均等に分けるのが正解
制約を受けるのはv-uの辺が存在しない場合
補グラフで考えると、辺がある2点は同じ側に属してはいけない、という問題になる

→2部グラフにならない連結成分がある場合-1

あとは、連結成分ごとにどちらに属すかを決め、その差を最小化すればよい
→dpで見つけられる！

"""
import sys
N,M = map(int,input().split())

AB = []
olis = [ [1] * N for i in range(N) ]
for i in range(N):
    olis[i][i] = 0

for i in range(M):

    A,B = map(int,input().split())
    A -= 1
    B -= 1
    olis[A][B] = 0
    olis[B][A] = 0

non_visit = [True] * N
state = [None] * N
dif = []
ns = [0,0]

#2部グラフ探索

def dfs(p,nst):

    if non_visit[p]:
        non_visit[p] = False
        state[p] = nst
        ns[nst] += 1
        
        for j in range(N):
            if p!=j and olis[p][j] == 1:
                dfs(j,nst^1)
    
    elif nst != state[p]:
        print (-1)
        sys.exit()

    return;

for i in range(N):

    ns = [0,0]

    if non_visit[i]:
        dfs(i,0)
        #print (i)
        dif.append(abs(ns[0]-ns[1]))

dp = [False] * 1500
dp[0] = True

for i in dif:

    ndp = [False] * 1500

    for j in range(1500):

        if dp[j]:
            ndp[(j-i)%1500] = True
            ndp[(j+i)%1500] = True

    dp = ndp

for i in range(N):

    if dp[i] or dp[-1*i]:

        for j in range(N):

            if abs(N-j - j) == i:
                x = j
                y = N-j

                print (x*(x-1)//2 + y*(y-1)//2)
                sys.exit()

Buggy submission (verdict: Runtime Error):

"""

m,k 個に分けた場合 mC2+kC2が答え
分けられるもののうち、差が最小となるようにする。

aとbがつながってない
a = 0とすると b = 1
bとcがつながってない c = 0

ぐる0,ぐる1で分かれる
x,y個に分かれた時、abs(x-y)として差を最小にする。

dpで求めればいいか。


[親、所属(0or1)]でunion-find
"""

import math
import sys

def nCr(n,r):
    if n-r < 0:
        return 0
    return math.factorial(n) // (math.factorial(n-r) * math.factorial(r))

def wantp(n):

    wpl = []
    while n != p[n]:
        wpl.append(n)
        n = p[n]

    for i in wpl:
        p[i] = n
    return n


N,M = map(int,input().split())

link = [[False] * N for i in range(N)]

for i in range(M):

    A,B = map(int,input().split())
    A -= 1
    B -= 1

    link[A][B] = True
    link[B][A] = True


#まず普通にUnion-Findする
p = [i for i in range(N)]
rank = [1] * N
for i in range(N):

    for j in range(N):

        if not link[i][j]:
            ip = wantp(i)
            jp = wantp(j)

            if ip != jp:

                if rank[ip] > rank[jp]:
                    p[jp] = ip
                elif rank[ip] < rank[jp]:
                    p[ip] = jp
                else:
                    p[ip] = jp
                    rank[jp] += 1
                    

dic = {} #親がキーで配列内に属す頂点を入れる(これで分類)

for i in range(N):
    np = wantp(i)
    if np not in dic:
        dic[np] = []
    dic[np].append(i)


side = [-1] * N #0と1サイドで分ける

for i in dic: #整合性の確認

    side[i] = 0
    for j in dic[i]:

        for k in dic[i]:
            if j != k and (not link[j][k]) and side[k] != -1:

                if side[j] == -1:
                    side[j] = side[k] ^ 1
                elif side[j] == side[k]:
                    print (-1)
                    sys.exit()


dic2 = {} #キーは先頭[0の数-1の数を入れる]

for i in range(N):
    np = wantp(i)
    if np not in dic2:
        dic2[np] = 0

    if side[i] == 0:
        dic2[np] += 1
    else:
        dic2[np] -= 1

allnum = [False] * 1401
allnum[0] = [True]

for i in dic2:
    dic2[i] = abs(dic2[i])

#dpで中心に一番近い数を求める

for i in dic2:
    nn = dic2[i]
    nall = [False] * 1401
    
    for j in range(1401):
        if allnum[j]:
            nall[j + nn] = True
            nall[j - nn] = True

    allnum = nall.copy()

ret = 0
while True:
    if allnum[ret] or allnum[-1 * ret]:
        break
    ret += 1

a = N
b = 0

while abs(a-b) != ret:
    a -= 1
    b += 1

ans = 0
print (nCr(a,2) + nCr(b,2))