ZONeエナジー プログラミングコンテスト “HELLO SPACE”
人はエナジードリンクを飲むのがきつくなってきたときに老いを実感する。
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×105 程度の計算量で達成可能かどうか求められる。
二分探索で 109 個の値を探索しても、3.8×105×log109=1.15×107 程度の計算量で答えを求められる。
m 以上かどうか? の判定では1人の能力パターンはたかだか 32 通りしかないので、同じ人は圧縮して、32C3 を全て試す、というのでもよかった。
二分探索が使えなくなる。
「5」つの能力値から「3」人を選ぶ、という設定を利用することで、O(N2) で解くことができる。
3人を選んだとき、必ず1人は「自身の能力値がチーム能力値に採用される(3人の中で最大である)能力が5個中1個以下」の人が存在する。 (同率の場合は採用されていないものと考える)
そうでないならば、3人がそれぞれ別々の「自身の能力値がチーム能力値に採用されている能力」を2つずつ持つことになり、能力が6つ必要となるので矛盾する。
なので、
となる。
その通り実装する……のはE問題にしてはやけに率直だなと思ったが、想定解はもう少し工夫するものだったらしい。
愚直解だと、各マスからの遷移がたかだか R+2 なので全部で O(R2C)、頂点数が O(RC) で、Dijkstraの計算量に当てはめると O(R2ClogRC) となる。 最大値で 2.25×109 なので枝刈りを丁寧にやらないとTLEとなるが、まぁ間に合うことにワンチャン賭けてもいいくらいのオーダーではある。
Dijkstraの実装、本来は
という手段でかなりの枝刈りが見込めるが、下手な実装で
としてしまうと、キューが肥大化してしまうので遅くなる。ちゃんと前者で実装すれば、PyPyでも通る。
通らない場合は、以下の(小手先の)工夫の余地がある。
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(R2C) から O(RC) へと縮小し、計算量が O(RClogRC) へと減る。
(実際は、2倍の頂点を持つことなどによりそこまで大幅に改善するわけではない)
元の問題の場合も、マスを2つ持つ(2つの世界線を行き来する)ことで似たことを実現できる。
こうすると、問題文通りのコストを実現しつつ、遷移の数が減らせる。
グラフ問題。星を頂点、ワープゲートを辺と見立てて、制約がある中で全域木を作れという問題。
制約を逆に考えると、XORが Ai に含まれないような2頂点間には辺を張れる。
よって問題は、「あるグラフが与えられるので、連結か判定し、連結なら全域木を1つ答えよ」と言い換えられる。
グラフの辺はXORが Ai に含まれないような2頂点間全てに張られているものとする。
全域木の一般的な作り方は、
としていくと、N−1 本の辺が選ばれたらそれが全域木の辺となっている。
しかし、今回の問題では Ai の個数が少ない場合、元のグラフの辺は O(N2) くらいのオーダーになる。これでは間に合わない。
ここで、辺が張られる条件に着目すると、
この2つの操作を行った後では、既に a⊕c=X⊕Y となる a,c 間は b を介して連結状態になっている。
従って、
とするとよい。
実際に X が C に含まれていない場合というのは O(logN) に絞られる。
その中で全域木チェックが O(N)(Union-Findの結合はほぼ定数として)、C を拡張する操作は全体を合計して O(N) となり、O(NlogN) で解ける。