NIKKEI Programming Contest 2019 C,D,E メモ

全国統一プログラミング王決定戦予選/NIKKEI Programming Contest 2019

C - Different Strokes

問題

$N$ 皿の料理を、先手と後手が順に1つずつ選んで食べる
$i$ 番目の料理は、先手が食べると先手に $A_i$、後手が食べると後手に $B_i$ の幸福度が入る
両者は「自分の得た幸福度 - 相手の得た幸福度」を最大化しようと料理を選ぶ
最終的な「先手の得る幸福度 - 後手の得る幸福度」を求めよ

解法

わざわざ相手の幸福度下げなくてもいいじゃん……とは思いつつ、我々の感じる幸福とは他者との相対性の中でしか認知できないものかも知れない（？）

行動原理が先手後手で一緒なので、料理ごとに何らかの共通の評価指標（選ぶべき優先順位）があって、先手が1,3,5,..番目、後手が2,4,6,..番目を選んでいくような形になるのかな？と見当をつける。

行動原理は「自分が得る幸福度を高める」「相手に高い幸福度を取らせない」の2つの評価軸がある。例を作ると、

        Ai  Bi    先手は料理1を選ぶと、5-3 = 2
料理1:   5   1          料理2を選ぶと、2-1 = 1
料理2:   2   3    よって自分の得を優先して料理1を選ぶ

        Ai  Bi    先手は料理1を選ぶと、5-4 = 1
料理1:   5   1          料理2を選ぶと、2-1 = 1
料理2:   2   4    よってどちらも同じ

        Ai  Bi    先手は料理1を選ぶと、5-5 = 0
料理1:   5   1          料理2を選ぶと、2-1 = 1
料理2:   2   5    よって相手の損を優先して料理2を選ぶ

などと少しずつ変えていくと、評価指標は $A_i+B_i$ であるかも、と思いつく。

公式解説の通り、まず一旦「どちらかが全てを取ってしまった状態」から1つずつ「もらっていく」と考えると多少は思いつきやすい。

変数を使うと整理しやすい。

        Ai  Bi    先手は料理1を選ぶと、a1 - b2
料理1:  a1  b1          料理2を選ぶと、a2 - b1
料理2:  a2  b2

$a_1-b_2 \gt a_2-b_1$ なら料理1を選ぶ
同じ料理に属する変数を同じ側に持ってくると、$a_1+b_1 \gt a_2 + b_2$
和が大きい方を選ぶのがよいことがわかりやすい

import sys

n = int(input())
ab = [tuple(map(int, line.split())) for line in sys.stdin.readlines()]
abd = [(a + b, a, b) for a, b in ab]
abd.sort(reverse=True)
print(sum(x[1] for x in abd[::2]) - sum(x[2] for x in abd[1::2]))

D - Restore the Tree

問題

$N$ 頂点の根付き有向木 $G$
- 辺は親から子に向かって張られている
- 根は頂点1とは限らない
$G$ に $M$ 本の有向辺を追加して $G'$ を作成した
- 追加辺 $(u→v)$ を張る時、必ず $u$ は $v$ の祖先となっているように張る
この $G'$ が与えられたとき、元の根付き木 $G$ を復元せよ
答えは、各頂点 $1,2,..,N$ の親をそれぞれ出力せよ

解法

追加辺 $(u→v)$ は、ショートカットとしてしか張られない。つまり、本来の木 $G$ でも、複数の頂点を経由して $u$ から $v$ に行けるような$(u→v)$にしか辺は張られない。また、$G'$ に二重辺は無いので、必ず $v$ は $u$ から見て孫以降である。（親子関係なら $G$ に元から辺があるので、更に追加すると二重辺になる）

G                G'  ○OK              ×NG
    根               根                根
  ／  ＼           ／┃＼            ／  ＼
○      ○       ○  ┃  ○━━┓  ○      ○←━┓
｜    ／  ＼     ｜  ↓／  ＼  ┃  ｜    ／  ＼  ┃
○   ○    ○    ○   ○    ○ ┃  ○   ○━→○ ┃
           ｜               ｜↙   ┃         ｜／
           ○               ○     ┗━━━→ ○

根の確定

根は、$G'$ で流入辺が無い唯一の頂点。

Gの復元

根以外の頂点 $v$ には、本来の木 $G$ においては、$(親→v)$ となる辺が存在し、これが唯一の流入辺となる。

しかし $G'$ では追加辺によって流入辺が複数ある可能性がある。その中で本当の親は、最も根からの距離が遠い頂点である。

つまり、BFSをした時に、最も遅く確定される頂点である。

事前処理
- 各頂点、流入辺の数を数えておく
- 流入辺０本の頂点が根
根からBFS
- 探索時、親の頂点番号を伝えながら行う
- 頂点 $v$ に、仮親 $p$ から探索が広げられたとする
- $v$ の流入辺カウントを1減らす
- もし流入辺カウントが0、つまり $v$ にとって最後の流入辺なら…
  - $(p→v)$ が本来の流入辺で確定、$p$が本来の親
  - 親が確定した時のみ、$v$ から各子に探索を広げる

    １            G' とする
  ↙｜↘
２  ｜  ３──┐  数字は頂点番号とする
↓  ↓↙  ↘  ｜
４  ５     ６ ｜  ただし以降の図では、数字は親の頂点番号とする
    ↓     ↓↙
    ７     ８

    根            根から1段階、幅優先探索を進めた
  ↙｜↘
１  ｜  １──┐  ←ここは、流入辺が1つのみなので、確定
↓  ↓↙  ↘  ｜
○  (1)    ○ ｜  ←ここの(1)は、探索は来たものの、流入辺2本に対して1回目の探索
    ↓     ↓↙       探索に使われた辺はショートカットであり、未確定
    ○     ○     ←親が確定するまでは、探索は広げない

    根            2段階目
  ↙｜↘
１  ｜  １──┐
↓  ↓↙  ↘  ｜
２   ３    ３ ｜  ←ここは確定
     ↓    ↓↙     先ほど未確定だった真ん中も、流入辺2本中2回目の探索が来たので、確定
     ○    (3)    ←(3)は流入辺2本に対して1回目の探索なので未確定

    根            3段階目
  ↙｜↘
１  ｜  １──┐
↓  ↓↙  ↘  ｜
２   ３    ３ ｜
     ↓    ↓↙
     ５    ６

深さ優先探索をしてしまうと、流入辺の親の内、どれが根から最も遠いか、という判定が難しい。こういう時は幅優先探索で、根からの距離を1ステップずつ確定させて行く。

import sys
from collections import deque

n, m = list(map(int, input().split()))
links = [set() for _ in range(n)]
in_counts = [0] * n
for line in sys.stdin.readlines():
    a, b = list(map(int, line.split()))
    a -= 1
    b -= 1
    links[a].add(b)
    in_counts[b] += 1

root = 0
for v, ic in enumerate(in_counts):
    if ic == 0:
        root = v
        break

parents = [-1] * n
q = deque([(c, root) for c in links[root]])

while q:
    v, p = q.popleft()
    in_counts[v] -= 1
    if in_counts[v] == 0:
        parents[v] = p
        q.extend((c, v) for c in links[v])

print('\n'.join(str(p + 1) for p in parents))

E - Weights on Vertices and Edges

問題

$N$ 頂点 $M$ 辺のグラフ
頂点、辺にそれぞれ重み $X_1,X_2,...,X_N$ と $Y_1,Y_2,...,Y_M$ が設定されている
ここから、いくつかの辺を取り除いて、以下の条件を満たすようにする
- 全ての連結成分について、連結成分内の頂点の重みの合計 $\geq$ 連結成分内の辺の重みの最大値
取り除く必要のある辺の最小数を求めよ

解法

考えたこと

初期状態のグラフについて、頂点の総和より大きな重みの辺があったら、必ず取り除く必要がある
取り除いた後、まだ全ての頂点が連結なら、その連結成分は条件を満たしている
分割されていれば、分割後の各連結成分で同じことをやる
再帰的に条件を満たすまでやれば、答えは求まる
けど計算量かかりすぎそう
- 毎回端っこの頂点が1つずつ落とされるようなグラフの場合、$O(NM)$ ……かどうかよくわからんけど、とりあえず無理なくらいかかる

使う辺の重みの最大値を決めてしまい、二分探索とかで条件を満たすか調べる？
でも連結成分によって可能な最大値が異なるので、単調性が成り立たない

公式解法

当たり前だが、どうしても使用不可な辺以外は、取り除く必要は無い。なので、各辺、使用可能か使用不可かを求める。どういう辺が使用不可なのか？

値が $Y_i$ である辺 $i$ を「使用可能」と仮定した場合、少なくともそこから $Y_i$ 以下の辺を介して繋がる辺は必ず使用可能。仮定上、$Y_i$ を含む連結成分の頂点の合計は $Y_i$ 以上なので、同じ連結成分に含められる $Y_i$ 以下の辺を取り除く意味は無い。

このように、辺 $i$ から値 $Y_i$ 以下の辺だけを介して繋げられる連結成分を「辺 $i$ の連結成分」と称することにする。

辺 $i$ の連結成分の頂点の合計が $Y_i$ より大きい場合、$i$ は使用可能である。

逆に $Y_i$ に満たなかった場合でも即座に使用不可とは断定できず、$Y_i$ より大きい値を持つ辺によって連結成分が広がり、頂点の合計が増え、使える可能性がある。

そこで、$Y_i$ が大きい辺から順に使えるかどうか確定していく。

自分より大きい値の辺 $e$ の連結成分に含まれ、$e$ が使用可能だった場合、自分も使用可能
自分より大きい値を持ち、自分を連結成分に含んでくれるような使用可能な辺が無い場合、自分 $i$ から探索して $Y_i$ 以下の辺で連結成分を求める
- 連結成分の頂点合計が $Y_i$ 以上なら使用可能、未満なら、今度こそ使用不可が確定

とすると順次確定できることが分かる。

しかし次に問題となるのは計算量で、ほとんどの辺が使用不可能だった場合、毎回各辺から連結成分の探索が行われることになる。これでは $O(M^2)$ ？となり、無理。

事前計算

そこで、毎回探索しなくて済むよう、各辺「自身から探索を始めた場合、使用可能かどうか」を効率的に事前計算しておく。

利用するデータ構造
- UnionFind木
- 現時点の各連結成分の頂点の合計を記録する配列
  - $N$ 要素の配列で、UnionFind木での結合が発生するたび、根にあたる頂点の値を更新していく

$Y_i$ が小さい方から、UnionFind木で繋いでいく。辺 $i$ は頂点 $a,b$ を結んでいるとする。

辺 $i$ まで調べた時、$Y_i$ 以下の値を持つ辺で繋げられる連結成分は既に結合されているので、 DFSなどの探索をしなくても「$a$ を含む連結成分の頂点合計」と「$b$ を含む連結成分の頂点合計」を調べるだけで、辺 $i$ の連結成分の頂点合計を求められる。

既に$a,b$が同じ連結成分に属する場合
- その連結成分の頂点合計が $Y_i$ 以上なら使用可能、未満なら(自分からの探索では)不可
異なる連結成分の場合
- 結合し、新しい連結成分の頂点合計←2つの連結成分の頂点合計の和とする
- 新しい連結成分の頂点合計が $Y_i$ 以上なら使用可能、未満なら(自分からの探索では)不可

処理順序による懸念事項

同じ値を持つ辺が複数ある場合、どちらを先に処理するかで使用可能かの判定が変わってしまう場合がある。

同じ値の辺 $e,f$ が同じ連結成分に属する場合、先に処理された方 $e$ の処理時点では、本来 $f$ によって繋がる箇所がまだ繋がってない。そのため、頂点合計が過小評価され、本来使用可能なのに不可と判定される可能性がある。大丈夫？と不安になる。

しかし、$f$ は正しい連結成分で判定されている。この後の $Y_i$ の大きい方から確定させていく本処理で「後に事前計算した方を、先に本処理する」という順序さえ守れば、

$f$ が使用可能なら $e$ もその連結成分に含まれるため、$e$ の判定結果に依らず使用可能
$f$ が使用不可なら、$e$ も使用不可と判定されているはずで、合致する

となり、$e,f$ の最終的な結果は同じになるので、問題ない。

import sys


class UnionFind:
    def __init__(self, n):
        self.table = [-1] * n

    def _root(self, x):
        if self.table[x] < 0:
            return x
        else:
            self.table[x] = self._root(self.table[x])
            return self.table[x]

    def find(self, x, y):
        return self._root(x) == self._root(y)

    def union(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            if d1 == d2:
                self.table[r1] -= 1
        else:
            self.table[r1] = r2


def dfs(s, lim):
    q = [s]
    visited[s] = True

    while q:
        v = q.pop()
        for y, u, i in links[v]:
            if y > lim:
                continue
            use[i] = 2
            if visited[u]:
                continue
            visited[u] = True
            q.append(u)


n, m = map(int, input().split())
xxx = list(map(int, input().split()))
links = [set() for _ in [0] * n]
links2 = []
for i, line in enumerate(sys.stdin.readlines()):
    a, b, y = map(int, line.split())
    a -= 1
    b -= 1
    links[a].add((y, b, i))
    links[b].add((y, a, i))
    links2.append((y, a, b, i))

srt_links = sorted(links2)

uft = UnionFind(n)
connected_sum = xxx[:]
use = [0] * m  # 0: ambiguous, 1: usable, 2: fixed

for y, a, b, i in srt_links:
    if uft.find(a, b):
        r = uft._root(a)
    else:
        ra = uft._root(a)
        rb = uft._root(b)
        uft.union(a, b)
        r = uft._root(a)
        connected_sum[r] += connected_sum[rb if r == ra else ra]
    if connected_sum[r] >= y:
        use[i] = 1

ans = 0
visited = [False] * n
for y, a, b, i in reversed(srt_links):
    if use[i] == 2:
        continue
    if use[i] == 0:
        ans += 1
        continue
    dfs(a, y)

print(ans)

目次