パナソニックグループ プログラミングコンテスト2024（AtCoder Beginner Contest 375）E,F,G問題メモ
E - 3 Team Division
問題文
$N$ 個の整数が $3$ つのグループ $1,2,3$ に分かれています。
$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$ との関係性から自動的に決まる。
を $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)
ちゃんとした解法
$i,j,k$ からグループ3の合計は自動的に決まるので、DPとしては持たなくてよい。
また、$j,k$ の上限は「全要素の和/3 $\le 500$」まで持てばよい。
python3
from operator import itemgetter
def solve(n, persons):
INF = 1 << 60
total = sum(map(itemgetter(1), persons))
if total % 3 != 0:
return -1
target = total // 3
dp = [[INF] * (target + 1) for _ in range(target + 1)]
dp[0][0] = 0
for a, b in persons:
ndp = [[INF] * (target + 1) for _ in range(target + 1)]
for i in range(target + 1):
for j in range(target + 1):
base = dp[i][j]
if i + b <= target:
ndp[i + b][j] = min(ndp[i + b][j], base + int(a != 1))
if j + b <= target:
ndp[i][j + b] = min(ndp[i][j + b], base + int(a != 2))
ndp[i][j] = min(ndp[i][j], base + int(a != 3))
dp = ndp
ans = dp[target][target]
if ans == INF:
return -1
else:
return ans
n = int(input())
persons = [tuple(map(int, input().split())) for _ in range(n)]
ans = solve(n, persons)
print(ans)
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)$ を求める。
クエリを逆順に処理する。
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$ つの値が異なるかどうか判定してください。
異なる場合は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$ で抑えられる）
※最短経路に含まれうる辺の判定は、以下のようにしてもできる。
頂点 $1$ からと $N$ からDijkstraしておく。
コスト $c$ の辺 $(u,v)$ について、$D(1,u)+c+D(v,N)=D(1,N)$（または $u,v$ 入れ替えたもの）が成立するなら、
その辺は最短経路に含まれる。
この「最短経路に含まれる辺」のみからなるグラフから「橋」を見つければ、それが Yes となる辺となる。
Python3
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))
