ZONeエナジー プログラミングコンテスト “HELLO SPACE” C,E,F問題メモ
C - MAD TEAM
問題
例
A B C D E
人1 1 2 3 4 5
人2 9 7 5 3 1
人3 3 1 4 1 5
MAX -------------------
TEAM 9 7 5 4 5 --MIN→ 総合力 4
解法
二分探索+bitDP。
「チームの総合力をある値 $m$ 以上にできるか？」にそれなりに高速に答えられたら二分探索が可能なので、その方向で考えてみる。
例を考えてみると、「3人で、5個の能力全てについて、誰かが $m$ 以上であればOK」であることがわかる。
A B C D E
人1 1 2 3 4 5
人2 9 7 5 3 1
人3 3 1 4 1 5
人1 x x x o o
人2 o o o x x 4以上にできる?
人3 x x o x o
-------------------
o o o o o できる！
人1 x x x x o
人2 o o o x x 5以上にできる?
人3 x x x x o
-------------------
o o o x o ダメ～
すると、各能力値を超えている人が1人でもいればいい、というのは、bit集合のORで表現できそう。
以下のDPを考えると、
$i=1～3000, j=0～3, k=0～31$（bitフラグ）より、全体で $3.8 \times 10^5$ 程度の計算量で達成可能かどうか求められる。
二分探索で $10^9$ 個の値を探索しても、$3.8 \times 10^5 \times \log{10^9} = 1.15 \times 10^7$ 程度の計算量で答えを求められる。
Python3
n = int(input())
abilities = list(tuple(map(int, input().split())) for _ in range(n))
l = 1
r = 10 ** 9 + 1
while l + 1 < r:
m = (l + r) // 2
dp = [[False] * 32 for _ in range(4)]
dp[0][0] = True
for a, b, c, d, e in abilities:
bit = 0
if a >= m:
bit += 1 << 4
if b >= m:
bit += 1 << 3
if c >= m:
bit += 1 << 2
if d >= m:
bit += 1 << 1
if e >= m:
bit += 1
for j in range(1, 3):
for k in range(31):
if dp[j][k]:
dp[j + 1][k | bit] = True
dp[1][bit] = True
if any(dp[j][31] for j in range(1, 4)):
l = m
else:
r = m
print(l)
$m$ 以上かどうか？ の判定では1人の能力パターンはたかだか $32$ 通りしかないので、同じ人は圧縮して、${}_{32}C_{3}$ を全て試す、というのでもよかった。
発展
二分探索が使えなくなる。
「5」つの能力値から「3」人を選ぶ、という設定を利用することで、$O(N^2)$ で解くことができる。
3人を選んだとき、必ず1人は「自身の能力値がチーム能力値に採用される（3人の中で最大である）能力が5個中1個以下」の人が存在する。
（同率の場合は採用されていないものと考える）
そうでないならば、3人がそれぞれ別々の「自身の能力値がチーム能力値に採用されている能力」を2つずつ持つことになり、能力が6つ必要となるので矛盾する。
なので、
となる。
E - Sneaking
問題
解法
その通り実装する……のはE問題にしてはやけに率直だなと思ったが、想定解はもう少し工夫するものだったらしい。
愚直解
愚直解だと、各マスからの遷移がたかだか $R+2$ なので全部で $O(R^2C)$、頂点数が $O(RC)$ で、Dijkstraの計算量に当てはめると $O(R^2C \log{RC})$ となる。
最大値で $2.25 \times 10^9$ なので枝刈りを丁寧にやらないとTLEとなるが、まぁ間に合うことにワンチャン賭けてもいいくらいのオーダーではある。
Dijkstraの実装、本来は
という手段でかなりの枝刈りが見込めるが、下手な実装で
としてしまうと、キューが肥大化してしまうので遅くなる。ちゃんと前者で実装すれば、PyPyでも通る。
通らない場合は、以下の（小手先の）工夫の余地がある。
なんとなく $(i,j)$ がゴールに近い方がよさそうなので、コストが同じ場合そちらを優先的に探索されるようにする
$(cost,i,j)$ をタプルで持つより、bitシフトして1つの整数値として表現する
Python3
$(cost,i,j)$ を1つの整数値として表現している。
from heapq import heappop, heappush
r, c = map(int, input().split())
aaa = [[0]] + [[0] + list(map(int, input().split())) for _ in range(r)]
bbb = [[0]] + [[0] + list(map(int, input().split())) for _ in range(r - 1)]
q = [(1 << 9) + 1]
distances = [[1 << 60] * (c + 1) for _ in range(r + 1)]
distances[1][1] = 0
ans = -1
mask = (1 << 9) - 1
while q:
item = heappop(q)
j = item & mask
i = (item >> 9) & mask
cost = item >> 18
if i == r and j == c:
ans = cost
break
if j < c and cost + aaa[i][j] < distances[i][j + 1]:
distances[i][j + 1] = cost + aaa[i][j]
heappush(q, ((cost + aaa[i][j]) << 18) + (i << 9) + (j + 1))
if j > 1 and cost + aaa[i][j - 1] < distances[i][j - 1]:
distances[i][j - 1] = cost + aaa[i][j - 1]
heappush(q, ((cost + aaa[i][j - 1]) << 18) + (i << 9) + (j - 1))
if i < r and cost + bbb[i][j] < distances[i + 1][j]:
distances[i + 1][j] = cost + bbb[i][j]
heappush(q, ((cost + bbb[i][j]) << 18) + ((i + 1) << 9) + j)
for k in range(1, i):
if cost + 1 + k < distances[i - k][j]:
distances[i - k][j] = cost + 1 + k
heappush(q, ((cost + 1 + k) << 18) + ((i - k) << 9) + j)
print(ans)
よりよい解法
4方向の移動のうち上に移動する場合が、最大 $R-1$ マスに遷移することになり、辺の数がかさみやすい部分である。
ただ、マス $(i,j)$ から上方向へのコストはかなり統一的で、「1マス上が2、2マス上が3、3マス上が4、……」である。
もし、これが「1マス上が1、2マス上が2、3マス上が3、……」だったら、嬉しいことがある。
各マスから1つ上のマスにコスト1の辺を張っておけば、$(i,j)$ からは1つ上のマスへの遷移だけで済む。
2マス以上上のマスへの遷移は、1つ上のマスへの遷移を繰り返すことで表現できる。
□<---, □
|3 ↑1
□<, | □
|2 | ＝ ↑1
□ | | □
1↑ | | ↑1
(i,j)■-'--' ■
よって辺の数が $O(R^2C)$ から $O(RC)$ へと縮小し、計算量が $O(RC \log{RC})$ へと減る。
（実際は、2倍の頂点を持つことなどによりそこまで大幅に改善するわけではない）
元の問題の場合も、マスを2つ持つ（2つの世界線を行き来する）ことで似たことを実現できる。
現世界線のマスからは、
別世界線のマスからは、
別世界線の1つ上のマスへ移動できる（コストは1）
現世界線の同じマスへ移動できる（コストは0）
こうすると、問題文通りのコストを実現しつつ、遷移の数が減らせる。
Python3
from heapq import heappop, heappush
r, c = map(int, input().split())
aaa = [[0]] + [[0] + list(map(int, input().split())) for _ in range(r)]
bbb = [[0]] + [[0] + list(map(int, input().split())) for _ in range(r - 1)]
n = r * c
q = [(1 << 10) + 1]
distances = [[[1 << 60] * (c + 1) for _ in range(r + 1)] for _ in range(2)]
distances[0][1][1] = 0
ans = -1
mask = (1 << 10) - 1
while q:
item = heappop(q)
j = item & mask
i = (item >> 10) & mask
w = (item >> 20) & 1
cost = item >> 21
if i == r and j == c:
ans = cost
break
if w == 0:
if j < c:
nc = cost + aaa[i][j]
if nc < distances[0][i][j + 1]:
distances[0][i][j + 1] = nc
heappush(q, (nc << 21) + (i << 10) + (j + 1))
if j > 1:
nc = cost + aaa[i][j - 1]
if nc < distances[0][i][j - 1]:
distances[0][i][j - 1] = nc
heappush(q, (nc << 21) + (i << 10) + (j - 1))
if i < r:
nc = cost + bbb[i][j]
if nc < distances[0][i + 1][j]:
distances[0][i + 1][j] = nc
heappush(q, (nc << 21) + ((i + 1) << 10) + j)
nc = cost + 1
if nc < distances[1][i][j]:
distances[1][i][j] = nc
heappush(q, (nc << 21) + (1 << 20) + (i << 10) + j)
else:
nc = cost + 1
if i > 1 and nc < distances[1][i - 1][j]:
distances[1][i - 1][j] = nc
heappush(q, (nc << 21) + (1 << 20) + ((i - 1) << 10) + j)
nc = cost
if nc < distances[0][i][j]:
distances[0][i][j] = nc
heappush(q, (nc << 21) + (i << 10) + j)
print(ans)
F - Encounter and Farewell
問題
$N$ 個の星を $N-1$ 個のワープゲートで連結にする
星は $0～N-1$ の番号が付いている
ただし、直接は繋げられない星の制約が $M$ 個ある
制約下でワープゲートを構築する方法があるか判定し、可能なら構築方法を1つ示せ
$2 \le N \le 2^{18}$
$0 \le M \lt N$
解法
グラフ問題。星を頂点、ワープゲートを辺と見立てて、制約がある中で全域木を作れという問題。
制約を逆に考えると、XORが $A_i$ に含まれないような2頂点間には辺を張れる。
よって問題は、「あるグラフが与えられるので、連結か判定し、連結なら全域木を1つ答えよ」と言い換えられる。
グラフの辺はXORが $A_i$ に含まれないような2頂点間全てに張られているものとする。
全域木の一般的な作り方は、
としていくと、$N-1$ 本の辺が選ばれたらそれが全域木の辺となっている。
しかし、今回の問題では $A_i$ の個数が少ない場合、元のグラフの辺は $O(N^2)$ くらいのオーダーになる。これでは間に合わない。
ここで、辺が張られる条件に着目すると、
ある $X$ について、$a \oplus b = X$ となる $a,b$ 全てに辺を張る
ある $Y$ について、$b \oplus c = Y$ となる $b,c$ 全てに辺を張る
この2つの操作を行った後では、既に $a \oplus c = X \oplus Y$ となる $a,c$ 間は $b$ を介して連結状態になっている。
従って、
とするとよい。
実際に $X$ が $C$ に含まれていない場合というのは $O(\log{N})$ に絞られる。
その中で全域木チェックが $O(N)$（Union-Findの結合はほぼ定数として）、$C$ を拡張する操作は全体を合計して $O(N)$ となり、$O(N \log{N})$ で解ける。
Python3
class UnionFind:
def __init__(self, n):
self.table = [-1] * n
def root(self, x):
stack = []
tbl = self.table
while tbl[x] >= 0:
stack.append(x)
x = tbl[x]
for y in stack:
tbl[y] = x
return x
def find(self, x, y):
return self.root(x) == self.root(y)
def unite(self, x, y):
r1 = self.root(x)
r2 = self.root(y)
if r1 == r2:
return False
d1 = self.table[r1]
d2 = self.table[r2]
if d1 <= d2:
self.table[r2] = r1
self.table[r1] += d2
else:
self.table[r1] = r2
self.table[r2] += d1
return True
def get_size(self, x):
return -self.table[self.root(x)]
n, m = map(int, input().split())
aaa = list(map(int, input().split()))
bbb = set(range(1, n)) - set(aaa)
used = {0}
uft = UnionFind(n)
buf = []
for b in bbb:
if b in used:
continue
for i in range(n):
if uft.unite(i, i ^ b):
buf.append(f'{i} {i ^ b}')
used.update(b ^ x for x in list(used))
if len(buf) != n - 1:
print(-1)
else:
print('\n'.join(buf))