読者です 読者をやめる 読者になる 読者になる

ゆらのふなびと

競プロ, Python, C++

square869120Contest #1 D - square1001の通学経路 (square1001's School Road)

競プロ DP

問題

D: square1001の通学経路 (square1001's School Road) - square869120Contest #1 | AtCoder

左下が(1, 1), 右上が(W, H)の格子状の地図がある。

条件「K個のマス(左下が(Xi, Yi))のそれぞれについて、その周囲の4点のうち少なくとも1つを通る」を満たす最短経路は何通りあるか。

ただし、右か上に1つずつしか進めないものとする。

解法

解法1

自力でACしたコードだが、あんまりきれいじゃない。

考え方はこう。マスがx座標で昇順にソートされているものとすると、あるマスP_iから次のマスP_i+1に行くまでの最短経路の数は、P_iの左下からP_i+1の右上までの経路を数え上げれば十分。これを隣接するすべてのマスに対して行えばよい。

ただ、P_iの左下.y == P_i+1の右上.y のような場合には昇順で処理していくと間違うので、実際は降順(ゴールからスタートへ)で行っている。

(H, W) == (2, 2)のときは例外として分けてしまったけど、そうじゃなくても書けるのだろうか。

MOD = 1000000007
H, W, K = map(int, input().split())
P = []      #lower left(0-index)([x, y])
for i in range(K):
    x, y = map(int, input().split())
    x -= 1; y -= 1;
    P.append([x, y])
if not [0, 0] in P:
    #append start
    P.append([0, 0])
if W > 1 and H > 1 and not [W-2, H-2] in P:
    #append goal
    P.append([W-2, H-2])
P.sort(reverse = True)
 
##initialize
dp = [[0 for x in range(W+1)] for y in range(H+1)]
dp[H-1][W-1] = 1 #[y, x]!!
if W > 1:
    dp[H-1][W-2] = 1
if H > 1:
    dp[H-2][W-1] = 1
    
for i in range(len(P)-1):
    x2, y2 = P[i]
    x2 += 1; y2 += 1    #upper right
    x1, y1 = P[i+1]     #lower left
    
    for x in range(x2-2, x1-1, -1):
        #upper side
        dp[y2][x] = dp[y2][x2-1]
    for y in range(y2-2, y1-1, -1):
        #right side
        dp[y][x2] = dp[y2-1][x2]
        
    for x in range(x2-1, x1-1, -1):
        for y in range(y2-1, y1-1, -1):
            #inside
            dp[y][x] = dp[y][x+1] + dp[y+1][x]
            dp[y][x] %= MOD
            
if H == W == 2:
    print(2)
else:
    print(dp[0][0])

解法2

条件より、各マスについて、そのマスの周囲になく右下がりの対角線を延長した直線状にある点は通れない。(たとえば入力例1では(1,4), (4,1))

このことに注意して、最短経路を左下から数え上げる動的計画法的なアレをやればよい。

TLを見る限りこっちがメインのやり方っぽい。自分もやってみたが、以下のコードではTLEしたPythonが重いのか、あるいは何か間違ってるのか。とりあえずメモとして置いておく

def fill(x0, y0):
    x, y = x0+1, y0
    while x < W and y > 1:
        x += 1; y -= 1;
        dp[y][x] = -1
    x, y = x0, y0+1
    while x > 1 and y < H:
        x -= 1;  y += 1;
        dp[y][x] = -1
 
MOD = 1000000007
H, W, K = map(int, input().split())
dp = [[0 for x in range(W+1)] for y in range(H+1)]
dp[0][1] = 1
for i in range(K):
    x, y = map(int, input().split())
    fill(x, y)
 
for x in range(1, W+1):
    for y in range(1, H+1):
        if dp[y][x] != -1:
            dp[y][x] = max(dp[y][x-1], 0) + max(dp[y-1][x], 0)
            dp[y][x] %= MOD
 
print(dp[H][W])