Zenn
Closed10

ABC 231 E 以降

Python
abc
abc231
kyasbalkyasbal

コンテスト中に考えてたこと

試行 その1.

  1. 壁を壊さずに行ける範囲をグループ分けする (幅優先探索)
  2. 各グループの隣接する壁から再帰的に壁を壊し、違うグループに至るまでの最小の破壊数を求める(幅優先探索)
  3. 各グループからグループへの移動に必要な破壊する壁の数が求まるのでこれをグラフ的に扱い、ダイクストラで解く
#!/usr/bin/env python3
from heapq import heappop,heappush
from typing import List,Tuple


INF = 10**10

# N: 都市の数
# Q: グラフ: [(next_city,cost)] * N
# s: スタートとする都市
# -> 各都市への距離
def dijkstra(N:int,Q:List[Tuple[int,int]],s:int)->List[int]:
    dist = [INF]*N
    que = [(0,s)] # スタート
    dist[s] = 0
    while que:
        c,v = heappop(que)
        if dist[v] < c:
            continue
        for cost,t in Q[v]:
            if dist[v] + cost < dist[t]:
                dist[t] = dist[v] + cost
                heappush(que,(dist[t],t))
    return dist


def main():
    H,W = map(int,input().split())
    DIRS = [(1,0),(-1,0),(0,1),(0,-1)]
    M = []
    for i in range(H):
        M.append(list(input()))
    WALL = -2
    NOT_SET = -1
    GM = [[WALL if M[i][j] == "#" else NOT_SET for j in range(W)] for i in range(H)]
    GW = [set()]
    group_id = 0
    for i in range(H):
        for j in range(W):
            if GM[i][j] != NOT_SET:
                continue
            next = [(i,j)]
            visited = set([(i,j)])
            while next:
                i,j = next.pop()
                GM[i][j] = group_id
                for dx,dy in DIRS:
                    ni = i + dx
                    nj = j + dy
                    if ni >= 0 and nj >= 0 and ni < H and nj < W:
                        if GM[ni][nj] != WALL and (ni,nj) not in visited:
                            next.append((ni,nj))
                            visited.add((ni,nj))
                        elif GM[ni][nj] == WALL:
                            GW[-1].add((ni,nj))
            group_id += 1
            GW.append(set())
    if GM[0][0] == GM[H-1][W-1]:
        print(0)
        exit()
    GC = group_id
    INF = 10**10
    GD = [[INF] * GC for i in range(GC)] # グループ間の距離
    for i in range(GC):
        GD[i][i] = 0
    NW = [(0,2),(1,2),(-1,2),(0,-2),(1,-2),(-1,-2),(2,0),(2,-1),(2,1),(-2,0),(-2,-1),(-2,1)]
    CH = [(0,1),(1,0),(0,-1),(-1,0),(1,-1),(-1,1),(-1,-1),(1,1)] + NW
    for i in range(GC):
        punch_count = 1
        visited = set()
        next = list(GW[i])
        while next:
            nn = []
            while next:
                wi,wj = next.pop() # 壊すとする壁の位置
                for ci,cj in CH:
                    ni = wi + ci
                    nj = wj + cj
                    if ni >= 0 and nj >= 0 and ni < H and nj < W and GM[ni][nj] != WALL:
                        # 壁じゃないどこかにたどり着いた
                        if GD[i][GM[ni][nj]] > punch_count:
                            GD[i][GM[ni][nj]] = punch_count
                for ci,cj in NW:
                    ni = wi + ci
                    nj = wj + cj
                    if ni >= 0 and nj >= 0 and ni < H and nj < W and GM[ni][nj] == WALL and (ni,nj) not in visited:
                        # 壁じゃないどこかにたどり着いた
                        visited.add((ni,nj))
                        nn.append((ni,nj))
            next = nn
            punch_count += 1
    P = [[] for i in range(GC)]
    for i in range(GC):
        for j in range(GC):
            if GD[i][j] != INF and j != i:
                P[i].append((GD[i][j],j))
    dist = dijkstra(GC,P,GM[0][0])
    print(dist[GM[H-1][W-1]])

正直、よく小さいデータセットに限りACできるまでこの実装を持ってこれたと思うが、TLE
https://atcoder.jp/contests/abc213/submissions/24886479

kyasbalkyasbal

試行2. (この実装途中でコンテスト終了)

そもそも、グループ分けしなくても単純な幅優先探索でもいいのではないか?

  • 壁じゃない場合は上下左右を次の手の候補として探索
  • 壁である場合は、上下左右に加え、その壁を含む2x2の範囲を壊して行ける範囲を含める
#!/usr/bin/env python3
from heapq import heappop,heappush
def main():
    H,W = map(int,input().split())
    DIRS = [(1,0),(-1,0),(0,1),(0,-1)]
    CH = [(0,1),(1,0),(0,-1),(-1,0),(1,-1),(-1,1),(-1,-1),(1,1)]
    M = []
    for i in range(H):
        M.append(list(input()))
    next = [(0,0)]
    dp = [[INF] * W for i in range(H)]
    dp[0][0] = 0
    while next:
        nn = []
        while next:
            i,j = next.pop()
            for dx,dy in DIRS:
                ni = i + dx
                nj = j + dy
                if ni >= 0 and nj >= 0 and ni < H and nj < W:
                    if M[ni][nj] == "#":
                        for cx,cy in CH:
                            nni = ni + cx
                            nnj = nj + cy
                            if nni >= 0 and nnj >= 0 and nni < H and nnj < W:
                                if dp[nni][nnj] > dp[i][j] + 1:
                                    nn.append((nni,nnj))
                                    dp[nni][nnj] = dp[i][j] + 1
                    else:
                        if dp[ni][nj] > dp[i][j]:
                            dp[ni][nj] = dp[i][j]
                            nn.append((ni,nj))
        next = nn
    print(dp[H-1][W-1])

試行1より実装は単純なのに早かった。しかし、3テストケース分 TLE。
https://atcoder.jp/contests/abc213/submissions/24892631

kyasbalkyasbal

試行3.

普通に壁の数をコストとして最小の壁を壊す経路を探索し、経路復元をしてその経路に必要な破壊する数を考えてみる。
実装を残していなかったが、最短コストを更新する際に、そのマスに行くのにどこのマスから遷移したかを覚えておく。

しかし、この手法はそもそも上手くいかない。

例えば、テストケース1では、こんな経路が出てくる。(Bが壊す壁)
壊す壁の数は2で最小ではあるが、この位置の2つの壁は同時に壊せないために、合計の壁の数では最小だが、壁を壊すためのパンチの数が最小ではない。

['.', '.', 'B', '.', '.']
['#', '.', '#', '.', '#']
['#', '#', '.', 'B', '#']
['#', '.', '#', '.', '#']
['.', '.', '#', '.', '.']

同様にテストケース3もこんな感じ

['.', '#', '#', '#', '#', '#', '#', '#']
['B', '#', '#', '#', '#', '#', '#', '#']
['B', '#', '#', '#', '#', '#', '#', '#']
['B', '#', '#', '#', '#', '#', '#', '#']
['B', '#', '#', '#', '#', '#', '#', '#']
['B', '#', '#', '#', '#', '#', '#', '#']
['B', '#', '#', '#', '#', '#', '#', '#']
['B', 'B', 'B', 'B', 'B', 'B', 'B', '.']

本当は曲がりくねったほうが、一度に壊せる、実際に通る壁の数が増えるのだがそうならない。

kyasbalkyasbal

試行4.

試行2を改善する方法を考える。　そもそも、次の手が壁なのか、壁じゃないのかの状態を同じキューに入れているために可能性の低い手を優先して計算してしまっている。

01-BFS的な考え方で、次の遷移先が壁なら、探索候補のキューに左から追加、壁でないなら探索候補のキューに右から追加すれば、壁以外から先に探索できるのではないか?

def main():
    H,W = map(int,input().split())
    DIRS = [(1,0),(-1,0),(0,1),(0,-1)]
    NW = [(0,2),(1,2),(-1,2),(0,-2),(1,-2),(-1,-2),(2,0),(2,-1),(2,1),(-2,0),(-2,-1),(-2,1)]
    CH = [(0,1),(1,0),(0,-1),(-1,0),(1,-1),(-1,1),(-1,-1),(1,1)] + NW
    M = []
    for i in range(H):
        M.append(list(input()))
    D = [[INF]*W for i in range(H)]
    P = [[None]*W for i in range(H)]
    D[0][0] = 0
    que = deque([(0,(0,0))]) # (punch_count,position)
    while que:
        cost,pos = que.pop()
        i,j = pos
        if D[i][j] < cost:
            continue # 別の手段でもっと早くたどり着いてるので探索しない
        if M[i][j] == "#":
            for dx,dy in CH: # (i,j)は壁なので、これを壊すとしてたどり着けるすべての場所を次のキューに入れる
               ni = i + dx
               nj = j + dy
               if ni >= 0 and nj >= 0 and ni < H and nj < W:
                   if D[ni][nj] > D[i][j] + 1:
                       D[ni][nj] = D[i][j] + 1
                       P[ni][nj] = (dx,dy)
                       if M[ni][nj] == "#": # (ni,nj)は壁なのであまり優先しない
                            que.appendleft((D[i][j],(ni,nj)))
                       else:
                            que.append((D[i][j],(ni,nj)))
        else:
            for dx,dy in DIRS: # (i,j)は壁でないので、単に上下左右を探索する
               ni = i + dx
               nj = j + dy
               if ni >= 0 and nj >= 0 and ni < H and nj < W:
                   if D[ni][nj] > D[i][j]:
                       D[ni][nj] = D[i][j]
                       P[ni][nj] =(dx,dy)
                       if M[ni][nj] == "#": 
                            que.appendleft((D[i][j],(ni,nj)))
                       else:
                            que.append((D[i][j],(ni,nj)))

これはAC。
https://atcoder.jp/contests/abc213/submissions/24898374

なるほど、幅優先探索の候補のキューでは、どの順序で探索するかが大きく速度に影響する。
実際、だからダイクストラ等では優先度付きキューを用いているのだからそれは納得がいく。

ちなみに両方ともappendleftしてみるとやっぱり遅い。
https://atcoder.jp/contests/abc213/submissions/24898390

kyasbalkyasbal

思ったこと

制約的に　O(N^2) だと厳しい。何とか最初に k=1 の状態で計算を行って、それをもとに次の kの値を逐次的に出していけないだろうか?

kyasbalkyasbal

いや、そもそも各 k に対して和を計算しなければならないので、 愚直な解法では O(N^3) になるのか。

このスクラップは2021/08/09にクローズされました