AtCoder Beginner Contest 187 D,E,F問題メモ

AtCoder Beginner Contest 187

PC新調したら移行作業で正月がつぶれた。

いろんなアプリに依存してると、こういう時に苦労するね。（データ移行がきちんと考えられているアプリばかりではないので）

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$）に注目すると、

何もしないと、$A_i$ の総和だけ $A$ 氏が票を得て、$B$ 氏は0票。よって差分は $-\displaystyle \sum_iA_i$
選挙区 $i$ で演説すると、$A$ 氏が $A_i$ 票減り、$B$ 氏は $A_i+B_i$ 票増え、差分は $2A_i+B_i$ 縮まる
最終的に差分が正になれば勝ち

なので、$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$ が指定される
クエリ
- $t_i=1$ なら、辺 $e_i$ について、$a_{e_i}$ から、$b_{e_i}$ を通らずに移動できる頂点全てに $x_i$ 加算する
- $t_i=2$ なら、辺 $e_i$ について、$b_{e_i}$ から、$a_{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

問題

$N$ 頂点 $M$ 辺の単純無向グラフが与えられる
ここから辺を取り除き、「どの連結成分も、それ単体では完全グラフ」となるようにしたい
あり得る最小の連結成分の個数を求めよ
$1 \le N \le 18$

解法

制約が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の部分集合をイテレートする方法は、以下参照

ビット演算 (bit 演算) の使い方を総特集！〜マスクビットから bit DP まで〜 - Qiita

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)$ でできるらしい。

目次

AtCoder Beginner Contest 187 D,E,F問題メモ

D - Choose Me

問題

解法

E - Through Path

問題

解法

F - Close Group

問題

解法

解法2