結果

問題 No.2855 Move on Grid
コンテスト
ユーザー navel_tos
提出日時 2025-02-04 22:20:22
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,349 bytes
コンパイル時間 842 ms
コンパイル使用メモリ 82,276 KB
実行使用メモリ 220,456 KB
最終ジャッジ日時 2025-02-04 22:22:04
合計ジャッジ時間 94,722 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 20 TLE * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

#yukicoder2855 Move on Grid

#入力受取
N, M, K = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(N)]

def solve(N, M, K, A):
    #N, Mでは管理しにくいのでH, Wに。さらにAを一次元化
    H, W = N, M
    B = [A[i][j] for i in range(H) for j in range(W)]

    #Bの各要素とindexをソート
    D = {10 ** 9: []}
    for i, Bi in enumerate(B):
        try: D[Bi].append(i)
        except: D[Bi] = [i]
    key = sorted( D.keys(), reverse = True )

    #初期状態の最短路を計算: (0, 0)と(-1, -1)の進入コストも1となる
    C = [h + w + 1 for h in range(H) for w in range(W)]

    #更新。BFSの更新回数が sum(C) <= O( H * W * (H + W - 1) ) で抑えられる点に注意
    dial = [[] for _ in range(H + W)]
    for Bi in key:
        #1. D[Bi]の到達コストを1下げる
        while D[Bi]:
            assert C[ i := D[Bi].pop() ] >= 1
            C[i] -= 1
            dial[ C[i] ].append(i)

        #2. 最短路を更新  Dial algoを回せばOK
        for c in range( C[-1] + 1 ):
            while dial[c]:
                i = dial[c].pop()
                if C[i] < c:
                    continue
                assert C[i] == c
                if i % W < W - 1:
                    if C[ j := i + 1 ] > ( x := c + (B[j] < Bi) ):
                        C[j] = x
                        dial[x].append(j)
                if i < (H - 1) * W:
                    if C[ j := i + W ] > ( x := c + (B[j] < Bi) ):
                        C[j] = x
                        dial[x].append(j)
                if i % W > 0:
                    if C[ j := i - 1 ] > ( x := c + (B[j] < Bi) ):
                        C[j] = x
                        dial[x].append(j)
                if i >= W:
                    if C[ j := i - W ] > ( x := c + (B[j] < Bi) ):
                        C[j] = x
                        dial[x].append(j)

        #3. C[-1] <= Kとなれば答えを出力
        if C[-1] <= K:
            return Bi


#ランテス
def brute(N, M, K, A):
    H, W = N, M
    def bisect(X):  #X以上の整数のみを通過して到達するための最小の無視回数
        DP = [[10 ** 18] * W for _ in range(H)]
        DP[0][0] = ( A[0][0] < X )
        Q, R = [], [(0, 0)]
        while R:
            Q, R = R, Q
            while Q:
                h, w = Q.pop()
                for x, y in [(h + 1, w), (h, w + 1), (h - 1, w), (h, w - 1)]:
                    if x in range(H) and y in range(W):
                        if DP[x][y] > ( t := DP[h][w] + ( A[x][y] < X ) ):
                            DP[x][y] = t
                            if A[x][y] < X: R.append((x, y))
                            else: Q.append((x, y))
                        
        return DP[-1][-1]

    ok, ng = 0, 10 ** 9 + 1
    while abs(ok - ng) > 1:
        if bisect( mid := (ok + ng) // 2 ) <= K: ok = mid
        else: ng = mid
    return ok


from random import randint
def make_test():
    N, M = randint(1, 5), randint(1, 5)
    K = randint(0, N * M)
    A = [[randint(1, 10 ** 3) for _ in range(M)] for _ in range(N)]
    return N, M, K, A
'''
for time in range(1, 10 ** 5 + 1):
    N, M, K, A = make_test()
    assert brute(N, M, K, A) == solve(N, M, K, A)
    if time % 10 ** 4 == 0: print(time)
'''

#答えを出力
print( solve(N, M, K, A) )
0