AtCoder Beginner Contest 187 D,E,F問題メモ
D - Choose Me
問題
$A$ 氏と $B$ 氏の2人から1人を選ぶ選挙を行う
選挙区は $N$ 個
$i$ 番目の選挙区の有権者は全員 $A$ 派、$B$ 派のいずれかであり、それぞれ $A_i,B_i$ 人いる
選挙は全ての選挙区からの総得票数の多い方が勝つ
何もしないと、$A$ 派はそのまま $A$ 氏に投票し、$B$ 派はどこにも投票しない
$B$ 氏は選挙区で演説を行うことで、その選挙区の全ての人を $B$ 氏に投票させることができる
$A$ 氏は何もしない
$B$ 氏が勝つために最低限演説を行う必要のある選挙区の数を求めよ
$1 \le N \le 2 \times 10^5$
解法
何もしない $B$ 派にはなるべく投票に行って欲しいし、そのままでは $A$ 氏に投票してしまう $A$ 派にはなるべく寝返って欲しい。
増やしたい指標が2つあるのを、上手く考えて統合する。
得票数の差分（$B-A$）に注目すると、
なので、$2A_i+B_i$ の大きい順に演説するのが得で、その累積和が $\displaystyle \sum_iA_i$ を超えるまで回る必要があるとわかる。
Python3
n = int(input())
aoki = 0
increases = []
for _ in range(n):
a, b = map(int, input().split())
aoki += a
increases.append(2 * a + b)
increases.sort(reverse=True)
ans = 0
takahashi = 0
while aoki >= takahashi:
takahashi += increases[ans]
ans += 1
print(ans)
E - Through Path
問題
$N$ 頂点の木が与えられる
$i$ 番目の辺は $a_i,b_i$ を結ぶ
頂点には数字が書かれていて、はじめ、全て0である
その後、クエリが $Q$ 個与えられる
$i$ 番目のクエリでは、$t_i,e_i,x_i$ が指定される
クエリ
最終的な各頂点の値を求めよ
$1 \le N,Q \le 2 \times 10^5$
解法
木なので、辺の一方の頂点から、もう一方を通らずに移動できる頂点は、部分木となる。
○--○--○--, ,--○
○--Ａ----Ｂ--○
クエリ毎に部分木全てに $x_i$ を足していると時間がかかるので、ＡやＢに「この下には全部 $x_i$ が足されますよー」という情報を記録しておいて最後に復元すれば、全体を辿るのは1発で済む。
○
/ \
Ａ ○ Ｂ以下の部分木に足す場合、Ｂにのみ「xi」足されたことを記録しておいて、
/\ \ 最後に根から集計する
Ｂ○ ○
/\
●●
根は適当な1頂点を決めればよいが、その場合、ＡとＢの位置関係によっては足したい範囲を1つの部分木で表現できない場合もある。
●
/ \
Ａ ● Ａ以下の部分木に足したい……
/\ \ Ａに記録しても根から辿ったときに反映できない……
Ｂ● ●
/\
○○
その場合、いったん、全体に $x_i$ 足してしまう。
その上でＢ以下の部分木にそれを打ち消すように「$-x_i$」足すと考えればよい。
これで「部分木以下全ての頂点に加算」という1つの操作だけにクエリを分解でき、根からの集計が可能になった。
各クエリで、上記どちらの方法を採るかを決めるのに、辺のどちらの頂点が根に近いかを判別する必要がある。
まず最初に根から探索して各頂点の深さなり、親なりを計算しておくと、判別できる。
Python3
n = int(input())
links = [set() for _ in range(n)]
edges = []
for _ in range(n - 1):
a, b = map(int, input().split())
a -= 1
b -= 1
links[a].add(b)
links[b].add(a)
edges.append((a, b))
parents = [-1] * n
q = [(0, -1)]
while q:
v, p = q.pop()
parents[v] = p
for u in links[v]:
if u == p:
continue
q.append((u, v))
q = int(input())
tmp = [0] * n
for _ in range(q):
t, e, x = map(int, input().split())
a, b = edges[e - 1]
if t == 1:
if parents[a] == b:
tmp[a] += x
else:
tmp[0] += x
tmp[b] += -x
else:
if parents[b] == a:
tmp[b] += x
else:
tmp[0] += x
tmp[a] += -x
ans = [0] * n
q = [(0, 0)]
while q:
v, p = q.pop()
ans[v] = ans[p] + tmp[v]
for u in links[v]:
if u == p:
continue
q.append((u, v))
print('\n'.join(map(str, ans)))
F - Close Group
問題
解法
制約がbit演算を物語る。
頂点集合をbitで管理する。全ての集合の組合せの数は多くとも $2^{18}=262144$ で、線形な計算が可能。
76543210
{1,2,4,5} → 00110110 = 54
その上で、以下を事前計算しておく。
$cmp[S]=S$ で表される頂点集合は、1つの連結成分にできる（
誘導部分グラフが完全グラフとなる）
次に以下のDPをする。
$dp[S]=S$ で表される頂点集合からなる
誘導部分グラフが入力だった場合の答え
'1,10,100,…' については自明に1となる。
遷移は、以下のように考えられる。
S = 1101101
これを2グループに分ける分け方を全探索する
1001001 このように分けたとする
0100100
1001001 を1つの連結成分に出来るか？ を cmp より取得
できないなら次へ
できるなら、そう分けたときの答えは DP[0100100] + 1
全分け方について調べ、その中での最小値が、DP[S] となる
最終的に $DP[111 ... 1]$ が答え。
このように、「$N$ 個のbitの集合 $2^N$ 個をイテレートしながら、更にその内部で部分集合をイテレートする」操作は、計算量 $O(3^N)$ となる。
「最初のbit集合に選ばれない」「最初のbit集合には選ばれたが、部分集合には選ばれない」「部分集合にも選ばれる」の3通りを、各bitが独立に持つと考えればよい。
あるbitの部分集合をイテレートする方法は、以下参照
Python3
n, m = map(int, input().split())
links = [0] * n
for i in range(n):
links[i] |= 1 << i
for _ in range(m):
a, b = map(int, input().split())
a -= 1
b -= 1
ab = 1 << a
bb = 1 << b
links[a] |= bb
links[b] |= ab
one_team = [False] * (1 << n)
for i in range(1, 1 << n):
b = i
j = i
k = 0
while j:
if j & 1:
b &= links[k]
j >>= 1
k += 1
if b == i:
one_team[i] = True
dp = [0] * (1 << n)
for i in range(1, 1 << n):
j = i
tmp = 20
while j:
if one_team[j]:
tmp = min(tmp, dp[i ^ j] + 1)
j = (j - 1) & i
dp[i] = tmp
print(dp[-1])
解法2
この問題設定自体、最小クリーク被覆問題 と名前が付いているらしい。
それによると、補グラフ（元のグラフから各頂点間の辺の有無を反転させたグラフ）を考えると、彩色問題に帰結できる。
彩色問題は、グラフ上で直接辺で繋がった2頂点は別の色で塗る、というルールで、$k$ 色で矛盾無く塗れますか or 何色あれば塗れますか、という問題。
「補グラフで辺がある2頂点は別の色」なので、「同じ色の2頂点なら元のグラフで辺がある」ことがいえる。
彩色可能な最小色数を求めればよい。
詳細なアルゴリズムは未調査だが、これは $O(2^NN)$ でできるらしい。