−目次

パナソニックグループプログラミングコンテスト2024（AtCoder Beginner Contest 375）E,F,G問題メモ
- E - 3 Team Division
  - 問題文
  - 制約
  - 解法
- F - Road Blocked
  - 問題文
  - 制約
  - 解法
- G - Road Blocked 2
  - 問題文
  - 制約
  - 解法
  - 解法2

パナソニックグループプログラミングコンテスト2024（AtCoder Beginner Contest 375）E,F,G問題メモ

パナソニックグループプログラミングコンテスト2024（AtCoder Beginner Contest 375）

E - 3 Team Division

問題文

$N$ 個の整数が $3$ つのグループ $1,2,3$ に分かれています。
- $i$ 個目の整数は $B_i$ で、グループ $A_i$ に属しています。
$0$ 個以上の要素が属するグループを変更することで、すべてのグループの総和が等しくなるようにできるか判定してください。また、すべてのグループの総和が等しくなるようにできる場合は、属するグループを変更する要素の個数として考えられる最小値を求めてください。
ただし、グループ $1, 2, 3$ の他に新たにグループを作ることはできません。

制約

$3 \leq N \leq 100$
$A_i \in \lbrace 1, 2, 3 \rbrace$
各 $x \in \lbrace 1, 2, 3 \rbrace$ に対し、ある $i$ が存在して $A_i = x$
$1 \leq B_i$
$\displaystyle\sum_{i = 1}^{N} B_i \leq 1500$
入力される値はすべて整数

解法

以下は（たぶん）嘘解法で、TLEするケースが作れてしまいそう。

全要素の和が3の倍数で無い場合は不可能。以下、3の倍数とし、1グループ当たりの目標値 $T=\frac{\sum B_i}{3}$ とする。

$1→2,1→3,2→1,2→3$ の4つの移籍する要素の合計値を固定すると、 $3→1,3→2$ は $T$ との関係性から自動的に決まる。

$C_i[j,k]:=$ グループ $i$ から一方へ合計 $j$ 、もう一方へ合計 $k$ の要素を移籍するときの最小個数
- 不可能な場合はINF

を $i=1～3$ に対し前計算し、4つを全探索する。

そのままだと最悪 $(\frac{1500}{4})^4 \simeq 2 \times 10^{10}$ くらいかかるが、

移籍する要素の合計値（ $C_i[j,k]$ に対する有効な $(j,k)$ の個数）の取り得るパターン数の少ない2グループを探索する
$C_i[j,k]$ の値が小さい方から探索し、途中で暫定最小値を上回ったら打ち切る

など小手先の高速化をすると、間に合う。

Python3

        
          
          
              
              import os
import sys
 
import numpy as np
 
 
def solve(inp):
    n = inp[0]
    team0 = []
    team1 = []
    team2 = []
    total = 0
    for i in range(n):
        a = inp[i * 2 + 1] - 1
        b = inp[i * 2 + 2]
        if a == 0:
            team0.append(b)
        elif a == 1:
            team1.append(b)
        else:
            team2.append(b)
        total += b
 
    if total % 3 != 0:
        return -1
 
    target = total // 3
 
    INF = 1 << 60
 
    def make_dp(team):
        s = sum(team)
        dp = np.full((s + 1, s + 1), INF, np.int64)
        dp[0, 0] = 0
        t = 0
        for b in team:
            for i in range(t, -1, -1):
                for j in range(t - i, -1, -1):
                    if dp[i, j] == INF:
                        continue
                    dp[i + b, j] = min(dp[i + b, j], dp[i, j] + 1)
                    dp[i, j + b] = min(dp[i, j + b], dp[i, j] + 1)
            t += b
        return dp
 
    dp0 = make_dp(team0)
    dp1 = make_dp(team1)
    dp2 = make_dp(team2)
    init_sum0 = sum(team0)
    init_sum1 = sum(team1)
    init_sum2 = sum(team2)
 
    available_dp0 = []
    for i2j, i2k in zip(*np.where(dp0 < INF)):
        if init_sum0 - i2j - i2k <= target:
            available_dp0.append((dp0[i2j, i2k], i2j, i2k))
    available_dp1 = []
    for j2i, j2k in zip(*np.where(dp1 < INF)):
        if init_sum1 - j2i - j2k <= target:
            available_dp1.append((dp1[j2i, j2k], j2i, j2k))
    available_dp2 = []
    for k2i, k2j in zip(*np.where(dp2 < INF)):
        if init_sum2 - k2i - k2j <= target:
            available_dp2.append((dp2[k2i, k2j], k2i, k2j))
    available_dp0.sort()
    available_dp1.sort()
    available_dp2.sort()
 
    def sub(is0, is1, is2, adp0, adp1, dp2):
        ans = INF
        for v1, i2j, i2k in adp0:
            if v1 >= ans:
                break
            for v2, j2i, j2k in adp1:
                k2i = target - (is0 + j2i - i2j - i2k)
                k2j = target - (is1 + i2j - j2i - j2k)
                if k2i >= 0 and k2j >= 0 and k2i + k2j <= is2:
                    ans = min(ans, v1 + v2 + dp2[k2i, k2j])
        return ans
 
    l0 = len(available_dp0)
    l1 = len(available_dp1)
    l2 = len(available_dp2)
    if l0 >= l1 and l0 >= l2:
        ans = sub(init_sum1, init_sum2, init_sum0, available_dp1, available_dp2, dp0)
    elif l1 >= l0 and l1 >= l2:
        ans = sub(init_sum0, init_sum2, init_sum1, available_dp0, available_dp2, dp1)
    else:
        ans = sub(init_sum0, init_sum1, init_sum2, available_dp0, available_dp1, dp2)
 
    if ans < INF:
        return ans
    return -1
 
 
SIGNATURE = '(i8[:],)'
if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC
 
    cc = CC('my_module')
    cc.export('solve', SIGNATURE)(solve)
    cc.compile()
    exit()
 
if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit
 
    solve = njit(SIGNATURE, cache=True)(solve)
    print('compiled', file=sys.stderr)
 
inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print(ans)

            

        
      

ちゃんとした解法

$\mathrm{DP}[i,j,k]:=i$ 個目の要素まで見て、グループ1の合計 $j$ 、2の合計 $k$ である時の移籍人数の最小値

$i,j,k$ からグループ3の合計は自動的に決まるので、DPとしては持たなくてよい。
また、 $j,k$ の上限は「全要素の和/3 $\le 500$ 」まで持てばよい。

python3

F - Road Blocked

問題文

AtCoder国には $1$ から $N$ の番号がついた $N$ 個の都市と、 $1$ から $M$ の番号がついた $M$ 本の道路があります。
道路 $i$ は都市 $A_i$ と都市 $B_i$ を双方向に結び長さは $C_i$ です。
$Q$ 個のクエリが与えられるので順に処理してください。クエリは以下の $2$ 種類のどちらかです。
1 i：道路 $i$ が通行止めとなる。
2 x y：通行止めでない道路のみを通るときの都市 $x$ から都市 $y$ への最短距離を出力する。都市 $x$ から都市 $y$ に到達できないときは代わりに -1 を出力する。
なお、 $1$ 種類目のクエリはテストケースごとに $300$ 回以下であることが保証されます。

制約

$2 \leq N \leq 300$
$0 \leq M \leq \frac{N(N-1)}{2}$
$1\leq A_i \lt B_i \leq N$
$(A_i,B_i)$ は相異なる
$1 \leq C_i \leq 10^9$
$1 \leq Q \leq 2\times 10^5$
$1$ 種類目のクエリにおいて、 $1\leq i \leq M$
$1$ 種類目のクエリにおいて与えられる道路は、その時点で通行止めでない
$1$ 種類目のクエリは $300$ 回以下である
$2$ 種類目のクエリにおいて、 $1\leq x \lt y \leq N$
入力は全て整数である

解法

$Q$ の上限は $2 \times 10^5$ と大きいが、そのうちクエリ1は $300$ 回以下という意味ありげな条件が付いている。

$N$ も小さいので、「クエリ1のたびに $O(N^2)$ くらいかけて全点間距離を再計算する」ことが可能ということ。

また、一般的にグラフを切るよりは繋ぐ方がやりやすいので、こういう問題は「クエリを逆順に見る」が有効そう。

ということで、まずクエリで通行止めにならない辺のみを使って Froyd-Warshall で全点間距離 $D(x,y)$ を求める。

クエリを逆順に処理する。

クエリ2の場合、単に $D(x,y)$ を参照する
クエリ1の場合、 $D$ を更新する。
- コスト $c$ の辺 $(a,b)$ が加わることで、2点間の距離 $D(x,y)$ は以下の最小値に更新される。
  - 追加辺を使用しない $D(x,y)$
  - $x→a→b→y$ の順に通過する $D(x,a)+c+D(b,y)$
  - $x→b→a→y$ の順に通過する $D(x,b)+c+D(a,y)$
- これを、全 $(x,y)$ に対して計算する。

Python3

        
          
          
              
              def solve(n, m, q, edges, queries):
    edges = [(a - 1, b - 1, c) for a, b, c in edges]
    queries2 = []
    init_edges = [True] * m
    for query in queries:
        if query[0] == 1:
            i = query[1] - 1
            init_edges[i] = False
            queries2.append((1, i, 0))
        else:
            queries2.append((2, query[1] - 1, query[2] - 1))
    queries = queries2
    queries.reverse()
 
    INF = 1 << 60
    dp = [[INF] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = 0
    for i in range(m):
        if init_edges[i]:
            a, b, c = edges[i]
            dp[a][b] = dp[b][a] = c
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dp[i][j] > dp[i][k] + dp[k][j]:
                    dp[i][j] = dp[i][k] + dp[k][j]
 
    ans = []
    for op, x, y in queries:
        if op == 2:
            if dp[x][y] == INF:
                ans.append(-1)
            else:
                ans.append(dp[x][y])
            continue
        a, b, c = edges[x]
        for i in range(n):
            for j in range(n):
                dp[i][j] = min(dp[i][j], dp[i][a] + dp[b][j] + c, dp[i][b] + dp[a][j] + c)
    ans.reverse()
    return ans
 
 
n, m, q = map(int, input().split())
edges = [tuple(map(int, input().split())) for _ in range(m)]
queries = [tuple(map(int, input().split())) for _ in range(q)]
ans = solve(n, m, q, edges, queries)
print('\n'.join(map(str, ans)))

            

        
      

G - Road Blocked 2

問題文

AtCoder国には $1$ から $N$ の番号がついた $N$ 個の都市と、 $1$ から $M$ の番号がついた $M$ 本の道路があります。
道路 $i$ は都市 $A_i$ と都市 $B_i$ を双方向に結び長さは $C_i$ です。
各 $i=1,\ldots,M$ について、以下の $2$ つの値が異なるかどうか判定してください。
- 全ての道路が通行可能なときの、都市 $1$ から都市 $N$ への最短距離
- 道路 $i$ 以外の $M-1$ 本の道路が通行可能なときの、都市 $1$ から都市 $N$ への最短距離
異なる場合はYes、同じ場合はNoを出力してください。
ただし、一方では都市 $1$ から都市 $N$ に到達可能で、他方では到達不可能なとき、両者の値は異なるとみなします。

制約

$2 \leq N \leq 2\times 10^5$
$1 \leq M \leq 2\times 10^5$
$1\leq A_i \lt B_i \leq N$
$(A_i,B_i)$ は相異なる
$1 \leq C_i \leq 10^9$
全ての道路が通行可能なとき、都市 $1$ から都市 $N$ へは到達可能
入力は全ては整数である

解法

F問題とテーマは似ている。

とりあえず、最短経路に使われ得る辺しかYesになり得ないので、そういう辺を特定したい。

仮に、Dijkstraの結果から「最短経路を1つ」復元するときは、各頂点 $v$ に対して最短経路における前の頂点のうちの1つ（predecessor） $P_v$ を経路探索中に記録しておくと、 $P_N$ から辿ることで復元できる。

今回は、「全ての最短経路に含まれる辺」を特定したいので、 $P_v$ をリストにし、同じ最短距離で $v$ に辿り着ける前頂点を全て記録しておくと、同様に復元できる。
（ $P_v$ のリストの要素の1つを $u$ とすると、 $(u,v)$ が1辺に対応するので、全リストの要素数は辺数 $M$ で抑えられる）

この「最短経路に含まれる辺」のみからなるグラフから「橋」を見つければ、それが Yes となる辺となる。

※最短経路に含まれうる辺の判定は、以下のようにしてもできる。
頂点 $1$ からと $N$ からDijkstraしておく。
コスト $c$ の辺 $(u,v)$ について、 $D(1,u)+c+D(v,N)=D(1,N)$ （または $u,v$ 入れ替えたもの）が成立するなら、その辺は最短経路に含まれる。

Python3

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

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

from heapq import heappop, heappush
 
 
def find_bridge(n, links):
    """
    単純連結無向グラフに対し「その辺を除くと連結成分数が増える」辺を列挙する
 
    Parameters
    ----------
    n : int
        グラフの頂点数
    links : List[List[int]]
        links[u] = [v1, v2, v3, ...]  隣接頂点のリスト
 
    Returns
    -------
    bridges : List[Tuple[int]]
        [(u, v), (u, v), ...]  橋である辺(両端の頂点番号)のリスト
 
    References
    ----------
    https://nupioca.hatenadiary.jp/entry/2013/11/03/200006
 
    Notes
    -----
    単純が保証されない場合、以下のように改変する。
      * ``count[u][v]`` = (u,v)間を結ぶ辺の本数を前計算する
      * 関数内 ``bridges.append((p, u))`` するところで、``count[p][u] >= 2`` なら橋ではない
 
    連結が保証されない場合、以下のように改変する。
      * ``pre, low, status, parents`` をグローバルに出す
      * 引数に ``s`` をとり、``q = [s]`` から探索を開始する
      * 関数外で ``i=0..<n`` について、``pre[i] == -1`` なら ``s = i`` として関数を呼ぶ
    """
    pre = [-1] * n
    low = [1 << 60] * n
    status = [0] * n
    parents = [-1] * n
    bridges = []
    pre_order = 0
    q = [0]
    while q:
        u = q[-1]
        if status[u] < len(links[u]):
            if pre[u] == -1:
                pre[u] = low[u] = pre_order
                pre_order += 1
 
            v = links[u][status[u]]
            status[u] += 1
 
            if v == parents[u]:
                continue
            if pre[u] < pre[v]:
                continue
 
            if pre[v] != -1:
                low[u] = min(low[u], low[v])
                continue
 
            q.append(v)
            parents[v] = u
 
        else:
            q.pop()
 
            p = parents[u]
            if p != -1:
                low[p] = min(low[p], low[u])
 
                if pre[u] == low[u]:
                    bridges.append((p, u))
 
    return bridges
 
 
def dijkstra(n, links, s, t):
    INF = 1 << 60
    costs = [INF] * n
    predecessors = [[] for _ in range(n)]
    costs[s] = 0
    q = [(0, s)]
    while q:
        cost, u = heappop(q)
        if cost > costs[t]:
            break
        if cost > costs[u]:
            continue
        for v, c in links[u]:
            new_cost = costs[u] + c
            if costs[v] < new_cost:
                continue
            elif costs[v] == new_cost:
                predecessors[v].append(u)
            else:
                predecessors[v] = [u]
                costs[v] = new_cost
                heappush(q, (new_cost, v))
    return costs, predecessors
 
 
def solve(n, m, edges):
    links = [[] for _ in range(n)]
    edges2 = [{} for _ in range(n)]
    for i in range(m):
        a, b, c = edges[i]
        a -= 1
        b -= 1
        links[a].append((b, c))
        links[b].append((a, c))
        edges2[a][b] = i
        edges2[b][a] = i
 
    _, predecessors = dijkstra(n, links, 0, n - 1)
 
    links2 = [[] for _ in range(n)]
    q = [n - 1]
    queued = {n - 1}
    while q:
        v = q.pop()
        for u in predecessors[v]:
            links2[u].append(v)
            links2[v].append(u)
            if u not in queued:
                q.append(u)
                queued.add(u)
 
    ans = ['No'] * m
    for u, v in find_bridge(n, links2):
        ans[edges2[u][v]] = 'Yes'
 
    return ans
 
 
n, m = map(int, input().split())
edges = [tuple(map(int, input().split())) for _ in range(m)]
ans = solve(n, m, edges)
print('\n'.join(ans))

解法2

橋を使わなくても求められる。こっちの方が思いつけば簡単。

頂点 $1$ と $N$ からそれぞれ、「最短距離 $D$ 」および「最短距離を実現する経路数 $C$ 」を求める。

各辺 $(u,v,c)$ につき、最短経路に使われるかの判定を行う。これは前の解法の末尾に※で記した補足と同じ。

$D(1,u)+c+D(v,N)=D(1,N)$ なら最短経路に含まれる

最短経路に使われる辺に対し、この辺を通る以外に最短経路がない事を調べるには、以下のようにすれば良い。

$C(1,u) \times C(v,N)=C(1,N)$ なら、この辺を通る以外に最短経路はない

ただし $C$ は非常に大きな数となり得るため、適当にmodを取って管理する。

−目次

パナソニックグループ プログラミングコンテスト2024（AtCoder Beginner Contest 375）E,F,G問題メモ

E - 3 Team Division

問題文

制約

解法

ちゃんとした解法

F - Road Blocked

問題文

制約

解法

G - Road Blocked 2

問題文

制約

解法

解法2

パナソニックグループプログラミングコンテスト2024（AtCoder Beginner Contest 375）E,F,G問題メモ