SRM661 Div2(Easy, Med)復習 —ワーシャルフロイドに惑う—

昨日の朝にあったSRM661に参加しました。

DIV1に上がってやるぜとか意気込んでたのにEasyしか解けなかった..しかも結果的にはMedはけっこう簡単だったみたいで、非常につらい。

Hardにたどり着けてないので宿題に..こんなことばっか言ってるなあ。

Easy (250) : FallingSand

(問題文のおおよその意訳)

正方形のマス目に分かれた長方形のボードが与えられ、いくつかのマスに障害物が、いくつかのマスに砂粒がある。この盤を立てたときの最終的なボードの状態を答えよ。ただし障害物は動かず、砂粒は何も無いマスにのみ落ちるものとする。(一マスに砂粒は一つしか入らない)。

これは単にシミュレーションするだけでした。stringで与えられるのがちょっとめんどくさいですね。

class FallingSand:
    def simulate(self, board):
        b = [list(s) for s in board]
        r = len(b)
        c = len(b[0])
        for i in range(c):
            for j in range(r-2,-1,-1):
                if b[j][i] == "o":
                    for k in range(j,r-1): 
                        if b[k+1][i] == ".":
                            b[k][i] = "."
                            b[k+1][i] = "o"
                            continue
                        break
        ans = tuple("".join(s) for s in b)
        return ans

Med (500) : BridgeBuildingDiv2

(問題文のおおよその意訳)

大きさがN( $2 \le N \le 11$ )の２つの節点列A,Bが与えられる。それぞれの列の隣り合う接点は辺で結ばれており、Aのi番目の節点とi+1番目の節点の間の辺の長さはa[i]、Bのi番目の節点とi+1番目の節点の間の辺の長さはb[i]である。ここで、長さ0のK本( $1 \le K \le N-1$ )の新しい辺をAの節点とBの節点の間に加えることを考える(ただし、辺を加えられるのはAのi番目の節点とBのi番目の節点(i=0,1, ... , N-1)の間のみ)。

新しい辺を加えてできたグラフについて、二節点間の最短距離のうち最大のものをグラフの直径と定義する。グラフの直径が最小になるようにK本の辺を加えたときのグラフの直径を求めよ。

f:id:Tawara:20150613010359p:plain

全点対距離..いつか勉強したワーシャルフロイドを使うときが来た！と、思ったのですが、N本からK本を選んで新しい辺を加え、そこから計算することを考えると、計算量は $_NC_k \times (2N)^3$ 、N = 11, K = 6のときなら $_{11}C_6 \times (22)^3 = 4919376 \fallingdotseq 5.0 \times 10^6$ 。ああ、pythonあかんやつやんこれ..

それでC++で実装しようとしたんですけど、組み合わせの列挙どうしたら良いんやってあーだこーだしてて終了致しましたorzやっぱ普段からやってないと駄目ですね。

どうやら全点についてダイクストラ法を用いると、計算量が $_NC_k \times (2N+(2(N-1)+K)) \log2N$ ぐらいなんでそれで行けたっぽい..のですが、やっぱpythonでもワーシャルフロイドで通したい！ってことで考えてみました。

ワーシャルフロイドでは、ある中継点kを考えたときの(i-k間の距離＋ k-j間の距離)と現時点のi-j間の距離の小さい方をi-j間の距離とするのを繰り返すことで全節点対の最短距離を求めます。ここで、通常は中継点に全節点を用います。今回はAの節点を0, .., N-1、Bの節点をN, ..., 2N-1 として

for k in range(2*N):
        for i in range(2*N):
                for j in range(2*N):
                        d[i][j] = min(d[i][j], d[i][k]+d[k][j])

をK本の新しい辺の加え方ごとにやることになります。ただこれでは計算量がよろしくない。

よくよく考えると、新しい辺を加えたときにある二節点間の最短距離が更新されるなら、その経路は絶対にいずれかの新しい辺を通ることが分かります。となれば、まず節点列A,Bそれぞれの中で全節点対の最短距離を求めておいた後に、新しく加えた辺の両端の節点のみを中継点としてワーシャルフロイドを実行すればいけそう。

for k in inter: #interはいずれかの新しい辺の両端の節点
        for i in range(2*N):
                for j in range(2*N): 
                        d[i][j] = min(d[i][j],d[i][k]+d[k][j])

というわけで以下のようになりました。

import itertools, copy

MAX = 1000
class BridgeBuildingDiv2:
    def minDiameter(self, a, b, K):
        N = len(a)+1
        d = [[MAX for j in range(2*N)] for i in range(2*N)]

        ## 距離の初期化
        for i in range(2*N):
            d[i][i] = 0

        for i in range(N-1):
            d[i][i+1] = d[i+1][i] = a[i]
            d[N+i][N+i+1] = d[N+i+1][N+i] = b[i]

        ## 節点列A,Bごとに全節点対の最短距離を計算
        for i in range(N-2):
            for j in range(i+2,N):
                d[i][j] = d[j][i] = d[i][j-1] + d[j-1][j]
                d[N+i][N+j] = d[N+j][N+i] = d[N+i][N+j-1] + d[N+j-1][N+j]

        ans = MAX
        ## 新しい辺の加え方ごとにワーシャルフロイドを行う
        for bridge in itertools.combinations(range(N),K):
            tmpd = copy.deepcopy(d)
            for k in bridge:
                tmpd[k][N+k] = tmpd[N+k][k] = 0
            ## 中継点は新しい辺の両端のみ
            inter = list(bridge) + [N+i for i in bridge]
            for k in inter:
                for i in range(2*N):
                    for j in range(2*N): 
                        tmpd[i][j] = min(tmpd[i][j],tmpd[i][k]+tmpd[k][j])

            ans = min(ans, max(max(tmpd[i]) for i in range(2*N)))
        return ans

最悪計算量はN=11, K=6のときの $_{11}C_6 \times (2\times 6) \times (22)^2 = 2683296 \fallingdotseq 2.7 \times 10^6$ 。え？あんまり変わってない？いやpythonは $10^6$ の世界入るととってもシビアなんでちょっとの削減がめっちゃ大事です。

さあシステムテストだ！

f:id:Tawara:20150613123942p:plain

やりました！ワーシャルフロイドは見た目より速いって聞いてたけど $2.7 \times 10^6$ でも通るもんなんですねえ。テストケースに一番最悪のケースが無いのもありますが、手元ではいけてました。いやー満足した！

かに見えた..

ところで、通常のワーシャルフロイドだとシステムテストではどれくらいかかるのでしょうか？まあTLEになるんでしょうけど気になるからやってみましょう！

f:id:Tawara:20150613123946p:plain

って通るんかーい！！僕のここまでの苦労は何だったんでしょうか... システムテストの最悪ケースは N= 11, K=7なので、計算量は $_{11}C_7 \times (22)^3 = 3513840 \fallingdotseq 3.5 \times 10^6$ 、まあたしかに雑魚いから仕方ないか？