普段は ABC のDまでの問題(まれにEも)を解くために考えたこと、ACできるPython3(PyPy3)コードを紹介していますが、今回の 281では Dを ACできなかったので、簡単にまとめる程度にとどめます。
他の記事は、現在進行形で世間に出ている解説より圧倒的に速く、めちゃくちゃわかりやすいと思ってもらえるような記事を書いてるつもりなのでぜひ読んでください。
この記事は @u2dayo さんの記事を参考にしています。見たことのない方はそちらもご覧ください。とても勉強になります。
また、問題の難易度を表す指標を Atcoder Problems から引用しています。このサイトは勉強した問題を管理するのにとてもオススメです。
質問やご指摘はこちらまで
Twitter : Waaa1471
作者プロフィール
Atcoder ：緑 882
20221231 現在
目次
はじめに
A.Generalized ABC
B.Let's Get a Perfect Score
C.String Delimiter
D.Make Bipartite 2
はじめに
特にC問題以降になると、競技プログラミングに典型的な前提知識、少し難しい数学的考察が必要になり始めます。
しかし、公式解説ではこの部分の解説があっさりしすぎていて競技プログラミング(Atcoder)を始めたばかりの人にはわかりにくい、難しいと感じるのではないでしょうか。
またC++がわからないと、コードの書き方を勉強することが難しいです。一応、参加者全員のコードを見ること自体は可能ですが、提出コードは必ずしも教育的ではありません(ここで紹介する記事も本番で提出したものとは全く異なります)。そんなものから初学者が解説もなしになにか得ることはとても難しいと思います。実際適当に何人かのコードをみたものの、意味がわからずに終わった経験があるのではないでしょうか。
この記事がそんな方々の勉強の助けになればよいなと思っています。
A.Generalized ABC
難易度：灰色 7
解説が十二分に詳しいです。
何も言うことはありません。
ユーザー解説
ユーザー解説
B.Let's Get a Perfect Score
難易度：灰色 72
A問題に続いて解説が十二分に詳しいです。
何も言うことはありません。
公式解説
C.String Delimiter
難易度 ： 灰色 104
今回はpython ユーザーにやさしいですね。解説が十二分に詳しいです。
何も言うことはありません。
公式解説
D.Make Bipartite 2
難易度： 緑色 1154
20221231 修正
考察
二部グラフをなす辺の種類は 以下2通り
➀ 同じ連結成分内において、新たに二部グラフをなせる辺
➁ 別の連結成分どうしを結ぶ任意の辺
つまり連結成分ごとに分類した後、これらの辺を求めることでこの問題を解くことができます。
素直に考えると、➀、➁は次のように求められるでしょうか。
➀ 連結成分ごとに片側の色に注目する。この色を持つ頂点を $V_1,V_2,...V_N$、もう一方の色を持つ頂点の総数を $U$、ある頂点 $X$ と直接辺でつながっている頂点の総数を $S_X$ とすると、
\sum_{k=1}^{N} ( U - S_{V_k} )
で求められる。
例えば、図の赤色の頂点に注目すると、$(2-1)+(2-1)+(2-2) = 2$ 本の辺が二部グラフを生成することになります。
始点を全探索して BFS を行うことで連結成分のグループ分けが可能です。一度調べた頂点を再探索しなければ $O(M)$ で実行可能です。
また、 $S_{V_1} , S_{V_2} .... S_{V_N}$ は $O(M)$で求めることができるので、計算量は全体で $O(M+M)$ となり十分高速です。
➁ 連結成分ごとに (連結成分をなす頂点の数 × それ以外の全ての頂点の数) を求める
⇒ 異なる連結成分のどの頂点を結んでも二部グラフにできるから
各連結成分が持つ頂点の数を $Y_1,Y_2,...Y_M$ とすると、
\frac{\sum_{k=1}^{M} ( N-Y_k ) × Y_k}{2}
で求められる。
➀ で実行した BFS で $Y_1,Y_2,...Y_M$ を求めておけば、計算量は $O(N)$ となって十分高速。( 全ての頂点が非連結の場合、連結成分は N個存在するため )
コード
pypy3
from collections import deque
N,M=[int(nm) for nm in input().split()]
G=[[] for _ in range(N)]
for _ in range(M):
u,v=[int(uv)-1 for uv in input().split()]
G[u].append(v)
G[v].append(u)
# ➀ 同じ連結成分内において、新たに二部グラフをなせる辺
ans1=0
# ➁ 別の連結成分どうしを結ぶ任意の辺
ans2=0
seen=[-1 for _ in range(N)]
# 連結成分が持つ頂点の数を管理
groups=[]
# 始点を全探索して BFS
for i in range(N):
if seen[i]>=0:
continue
que=deque()
que.append(i)
# 始点と同じ色の頂点を 1 , もう一方の色の頂点を 0 でチェック
seen[i]=1
# S1,S2...SN を管理
S=[]
U=0
while que:
now=que.popleft()
if seen[now]==1:
S.append(len(G[now]))
else:
U+=1
for nex in G[now]:
# 二部グラフをなさない場合
if seen[nex]==seen[now]:
print(0)
exit()
if seen[nex]<0:
# 直接つながっている頂点は異なる色を持つ
seen[nex]=seen[now]^1
que.append(nex)
# Σ (U-Sk)
for sk in S:
ans1+=U-sk
groups.append(len(S)+U)
for num in groups:
ans2+=(N-num)*num
# ➁を満たす全ての辺をダブルカウントしてしまっている点に注意
print(ans1+ans2//2)
別解1 ～ 余事象を考える ～
条件を満たす辺 = A.考えられる全ての辺 - B.(二部グラフを壊す辺) - C.(最初から存在した辺)
$A=$ $_NC_2$ , $C = M$ です。
ここで二部グラフ壊す辺とは、各連結成分において同じ色の頂点を結ぶ辺 のことです。これは同じ色の頂点の組み合わせの総数で求めることができます。
また、最初から存在した辺がこれらと重複することを考える必要はありません
なぜなら最初から存在する、かつ、同じ色の頂点を結ぶ ような辺がグラフに含まれる場合、そのグラフはもともと二部グラフではないからです。この状況で条件を満たす辺はありません。
対象の数え上げが簡単ではない場合、このように余事象を考えることが有効なことがあります
コード
pypy3
from collections import deque
N,M=[int(nm) for nm in input().split()]
G=[[] for _ in range(N)]
for _ in range(M):
u,v=[int(uv)-1 for uv in input().split()]
G[u].append(v)
G[v].append(u)
# 余事象で答えを求める
ans=N*(N-1)//2-M
seen=[-1 for _ in range(N)]
for i in range(N):
if seen[i]>=0:
continue
que=deque()
que.append(i)
seen[i]=1
# 各色の頂点の個数を管理
count1=0
count2=0
while que:
now=que.popleft()
if seen[now]==1:
count1+=1
else:
count2+=1
for nex in G[now]:
# 二部グラフをなさない場合
if seen[nex]==seen[now]:
print(0)
exit()
if seen[nex]<0:
# 始点と同じ色の頂点を 1 , もう一方の色の頂点を 0 でチェック
seen[nex]=seen[now]^1
que.append(nex)
# この連結成分における、二部グラフを壊す辺の総数
ans-=count1*(count1-1)//2+count2*(count2-1)//2
print(ans)
別解2 ～ Union-find で管理 ～
同じ連結成分の同じ色の頂点の個数を求めるための Union-findでの管理方法を Twitter で見つけたので紹介します。
図のように 頂点(1,2)の連結を (1,2+n),(2,1+n) における連結と置き換えて、同じ色ごとに管理します。
もし二部グラフでないならば、頂点 X と X+n が同じグループに所属してしまうので、これを uf.find(X,X+N) で検出することができます。
この場合、BFS のように探索することなく、uf.union() を繰り返すだけで各連結成分をグループ分けすることが可能となります。後は同じ連結成分の同じ色の頂点の総数から、二部グラフを壊す辺 の総数を求めればこの問題を解くことができます。
コード
pypy3
class UnionFind():
def __init__(self,n):
self.n = n
self.parents = [-1] * n
def find(self,x):
if self.parents[x] < 0:
return x
else:
self.parents[x] = self.find(self.parents[x])
return self.parents[x]
def union(self,x,y):
x = self.find(x)
y = self.find(y)
if x == y:
return
# 1～n までに親が存在するようにする
if x>y:
x, y = y, x
self.parents[x] += self.parents[y]
self.parents[y] = x
def same(self,x,y):
return self.find(x) == self.find(y)
def roots(self):
return [i for i, x in enumerate(self.parents) if x < 0]
if __name__ =="__main__":
N,M=[int(nm) for nm in input().split()]
uf=UnionFind(2*N)
for _ in range(M):
u,v=[int(uv)-1 for uv in input().split()]
uf.union(u,v+N)
uf.union(v,u+N)
for i in range(N):
# 二部グラフ判定
if uf.same(i,i+N):
print(0)
exit()
ans=N*(N-1)//2-M
# 各連結成分(色別)の個数を、親で管理
groups=[0 for _ in range(N)]
for i in range(N):
groups[uf.find(i)]+=1
for j in range(N):
ans-=groups[j]*(groups[j]-1)//2
print(ans)
補足
-
二部グラフ
アルゴ式_練習問題 -
union-find
PythonでのUnion-Find（素集合データ構造）の実装と使い方
コードでわからないところがあればここで調べてください。
B - Union Find
また、この問題の解説スライドも非常にわかりやすいです。
アルゴ式_さまざまなデータ構造
必ずアルゴ式の10章で練習してください。
終わり
20221231
D 問題の本解答はTLE する解答として編集前に紹介していましたが、間に合う方法が急に降ってきました。ますます本番で解けなかったことが悔しくなりました。