結果
問題 | No.2855 Move on Grid |
ユーザー |
![]() |
提出日時 | 2025-02-04 22:20:35 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,574 ms / 3,000 ms |
コード長 | 3,349 bytes |
コンパイル時間 | 536 ms |
コンパイル使用メモリ | 81,792 KB |
実行使用メモリ | 130,816 KB |
最終ジャッジ日時 | 2025-02-04 22:21:25 |
合計ジャッジ時間 | 46,670 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 40 |
ソースコード
#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( brute(N, M, K, A) )