ZONeエナジープログラミングコンテスト “HELLO SPACE” C,E,F問題メモ

人はエナジードリンクを飲むのがきつくなってきたときに老いを実感する。

C - MAD TEAM

問題

$N$ 人の人がいて、各人、パワー・スピード・テクニック・知識・発想力の5種類の能力値を持っている
この中から3人を選んでチームを作る
チームの「総合力」は以下のように決定する
- チームの各能力値は、3人の最大値をとる
- チームの総合力は、チームの能力値の最小値である
上手く3人を選んで、達成できるチームの総合力の最大値を求めよ
$3 \le N \le 3000$

例

          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を考えると、

$DP[i][j][k]=i$ 番目の人までのうち $j$ 人を採用することで、$m$ 以上の能力の集合が $k$ となるものを作れる（True/False）

$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つの能力値の「min」でなく「sum」ならどうするか？

二分探索が使えなくなる。

「5」つの能力値から「3」人を選ぶ、という設定を利用することで、$O(N^2)$ で解くことができる。

3人を選んだとき、必ず1人は「自身の能力値がチーム能力値に採用される（3人の中で最大である）能力が5個中1個以下」の人が存在する。（同率の場合は採用されていないものと考える）

そうでないならば、3人がそれぞれ別々の「自身の能力値がチーム能力値に採用されている能力」を2つずつ持つことになり、能力が6つ必要となるので矛盾する。

なので、

各能力について、最大の人の能力値を求めておく
3人中2人を固定して暫定のチーム能力値を計算した後、どれか1つを最大の人の能力値と置き換える
その中で最大のものが答え

となる。

E - Sneaking

問題

グリッドを左上 $(1,1)$ から右下 $(R,C)$ まで移動する
移動の条件
- $(1,1)～(R,C)$ の長方形の外にはいけない
- コスト
  - コストを表す値 $A_{i,j}$ と $B_{i,j}$ が与えられる
  - $(i,j)$ から1つ右に移動するコストは、$A_{i,j}$
  - $(i,j)$ から1つ左に移動するコストは、$A_{i,j-1}$
  - $(i,j)$ から1つ下に移動するコストは、$B_{i,j}$
  - $(i,j)$ から $k$ マス上に移動するコストは、$1+k$
最小コストを求めよ
$2 \le R,C \le 500$

解法

その通り実装する……のはE問題にしてはやけに率直だなと思ったが、想定解はもう少し工夫するものだったらしい。

愚直解

愚直解だと、各マスからの遷移がたかだか $R+2$ なので全部で $O(R^2C)$、頂点数が $O(RC)$ で、Dijkstraの計算量に当てはめると $O(R^2C \log{RC})$ となる。最大値で $2.25 \times 10^9$ なので枝刈りを丁寧にやらないとTLEとなるが、まぁ間に合うことにワンチャン賭けてもいいくらいのオーダーではある。

Dijkstraの実装、本来は

始点から各頂点までの暫定の最小コストを管理する
遷移時、現頂点から遷移した場合のコストと、遷移先の暫定コストを比較して、最小を更新できないならキューに突っ込まない

という手段でかなりの枝刈りが見込めるが、下手な実装で

とりあえず遷移先全部heapqに放り込んどいて、popした時に初めて訪れた頂点なら次に遷移する

としてしまうと、キューが肥大化してしまうので遅くなる。ちゃんと前者で実装すれば、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）
別世界線のマスからは、
- 別世界線の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$ 個のワープゲートで連結にする
- $N$ は2べき（$n$ を整数として $N=2^n$と表現できる）
星は $0～N-1$ の番号が付いている
ただし、直接は繋げられない星の制約が $M$ 個ある
- $A_1,A_2,...,A_M$ が与えられる
- $a \oplus b$ が $A_i$ のどれかになるような星 $a,b$ 間にはワープゲートを構築できない（$\oplus$ はbitXORの記号とする）
制約下でワープゲートを構築する方法があるか判定し、可能なら構築方法を1つ示せ
$2 \le N \le 2^{18}$
$0 \le M \lt N$

解法

グラフ問題。星を頂点、ワープゲートを辺と見立てて、制約がある中で全域木を作れという問題。

制約を逆に考えると、XORが $A_i$ に含まれないような2頂点間には辺を張れる。

よって問題は、「あるグラフが与えられるので、連結か判定し、連結なら全域木を1つ答えよ」と言い換えられる。
グラフの辺はXORが $A_i$ に含まれないような2頂点間全てに張られているものとする。

全域木の一般的な作り方は、

Union-Findで連結状態を管理する。はじめは全頂点バラバラとする
辺を任意の順番で見ていって、その辺が結ぶ2頂点が未連結ならその辺を使うこととし、Union-Find上でも結合する

としていくと、$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$ を介して連結状態になっている。

従って、

「既に連結状態となっているXORの集合 $C$」を $\{0\}$ で初期化する
$1～2^N-1$ のうち $A_i$ に含まれないような $X$ を任意の順に試す
- もし既に $X$ が $C$ に含まれていたら、$a \oplus b=X$ となる全ての $(a,b)$ は既に連結状態なので飛ばす
- まだ $X$ が $C$ に含まれていなければ、
  - $a \oplus b=X$ となる辺 $(a,b)$ を全域木に加えられるか全て試す
    - この操作の最初の時点ではどの $(a,b)$ も連結では無いはずだが、先に処理された同じ $X$ を持つ辺によって他が連結になるかも知れないので、順番に試す
  - $C$ に、$(Cの各要素) \oplus X$ を加える

とするとよい。

実際に $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))

目次

ZONeエナジー プログラミングコンテスト “HELLO SPACE” C,E,F問題メモ

C - MAD TEAM

問題

例

解法

発展

E - Sneaking

問題

解法

愚直解

よりよい解法

F - Encounter and Farewell

問題

解法

ZONeエナジープログラミングコンテスト “HELLO SPACE” C,E,F問題メモ