Loading [MathJax]/jax/output/CommonHTML/jax.js

−目次

NIKKEI Programming Contest 2019 C,D,E メモ

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

C - Different Strokes

C - Different Strokes

問題

解法

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

行動原理が先手後手で一緒なので、料理ごとに何らかの共通の評価指標（選ぶべき優先順位）があって、先手が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を選ぶ

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

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

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

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

1
2
3
4
5
6
7
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

D - Restore the Tree

問題

解法

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

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

根の確定

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

Gの復元

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

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

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

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

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

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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

E - Weights on Vertices and Edges

問題

解法

考えたこと

公式解法

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

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

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

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

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

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

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

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

事前計算

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

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

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

処理順序による懸念事項

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

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
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)