アドベントカレンダー日記2日目

今日は競プロサークルのバチャに参加したのでその問題からひとつ．

ZONeコンテストのE問題です．

(R,C) の位置にUFOがあるんで (1,1) から上下左右に移動してUFOに到達する最小コストを求めましょう，という問題です．ダイクストラの探索でできますね． PriorityQueue にコスト付き座標を突っこんで探索しましょう．

上左右への移動は普通に移動のコストがあたえられています．しかし，下への移動は移動距離+1のコストがかかります．この下方向のコスト計算がぜんぜんわかりませんでした．

ある座標から下方向の座標全てをなめるとTLEになります．下方向を現在の座標の近いほうから見てよりはやいルートがあるならそれより下は探索しないというのでもう少し速くなりますが，これでもTLEになります．(でもこれ C++ なら通ってしまいそうじゃないですか？)

なので下全体を見るのは無理ということであきらめ，情報を残しておいてあとから確認しましょう．

実際に通した全体のコードはこれです．

Submission #27630041 - ZONe Energy Programming Contest

上半分は入力なので大事なのは下半分ダイクストラの処理部分

    gone = falses(R,C)
    vals = fill(MAXINT, R,C)
    sagecheck = falses(R,C)
    ans = 0

    while !isempty(pq)
        k, v = dequeue_pair!(pq)
        r, c = k

        gone[r,c] = true
        vals[r,c] = v
        if r < R
            vsa = (v - vals[r+1,c]) 
            if 1 == vsa && sagecheck[r+1,c]
                sagecheck[r,c] = true
            elseif 2 == vsa
                sagecheck[r,c] = true
            end
        end

        if r == R && c == C
            ans = v
            break
        end

        nr,nc = r,c+1
        if c < C && !gone[nr,nc]
            nk = (nr,nc)
            pq[nk] = min(get(pq, nk, MAXINT), v + as[r,c])
        end

        nr,nc = r, c-1
        if 1 < c && !gone[nr,nc]
            nk = (nr,nc)
            pq[nk] = min(get(pq, nk, MAXINT), v + as[nr,nc])
        end

        nr,nc = r+1,c
        if r < R && !gone[nr,nc]
            nk = (nr,nc)
            pq[nk] = min(get(pq, nk, MAXINT), v + bs[r,c])
        end

        nr, nc = r-1, c
        if 1 < r && !gone[nr,nc]
            nk = (nr,nc)
            pq[nk] = min(get(pq, nk, MAXINT), v + (sagecheck[r,c] ? 1 : 2))
        end
    end
    println(ans)

です．重要なのが

        if r < R
            vsa = (v - vals[r+1,c]) 
            if 1 == vsa && sagecheck[r+1,c]
                sagecheck[r,c] = true
            elseif 2 == vsa
                sagecheck[r,c] = true
            end
        end

ここで上の座標へのコストと今来た座標へのコストの差が1か2なら下に降りる処理の続きでさらに降りられコストを減らすことができます．コストの差が1と2の場合で条件を変えるのを思いつくのに時間がかかりました．あとはこれを使ってコストを変える処理をいれれば完成です．

        nr, nc = r-1, c
        if 1 < r && !gone[nr,nc]
            nk = (nr,nc)
            pq[nk] = min(get(pq, nk, MAXINT), v + (sagecheck[r,c] ? 1 : 2))
        end

シンプルですね．通すのに 12WA+TLE+RE しました．GG

今日の日記は以上です．ではまた明日ー

おさかなせいざ

プログラミングメモや日記がわりに

アドベントカレンダー日記2日目