ABC146 F - Sugoroku

問題原文

F - Sugoroku

問題要旨

マスからなるすごろくがあり、最初はマス にいる。ゴールマスはマス である。各マスは か であり、 のマスの上に止まることはできない。各ターンでは、 の範囲でコマを進める。最小手数であり、各ターンの進め方が辞書順最小になるようなコマの進め方を求めよ。ただし、そもそもゴールできない時は を出力せよ。

考えたこと

• とりあえず前から出来るだけ遠くに行くようにすればゴールできるかどうかは判定できそう
• 実は↑が移動に必要な要素で、これを後ろから出来るだけ大きいものを使うように移動すればよさそう（間違い）

難しかったこと

• 本番はパニクってた
• 600点だからといって難しく考えすぎた

考えたかったこと

いくつか解法がある。

解法１: 貪欲法

• やりたいことは、「最小手数の達成」と「出来るだけ後ろを大きく、前を小さく」ということ。
• 後ろから大きい方から移動を試すようにすると、 実は上の条件が達成できる。（証明はできないけど、submitするぐらいには正しそうに思える）

実装

N, M = map(int, input().split())
S = input()


# 後ろから貪欲
ans = []
position = N
while position > 0:
    for move in range(M, 0, -1):  # 大きい方から試す
        if position - move < 0:
            continue

        if S[position - move] == '1':
            continue

        ans.append(move)
        position -= move
        break
    else:
        print(-1)
        exit()

print(*ans[::-1])

解法２: DP + セグメント木

• 愚直にやりたいことを考えると、「前から見ていって」「できるだけ小さな動き方から」「この移動は最小手数かどうか？」を判定したい。

• ただし前から逐一判定していては間に合わない。
• 「ゴールから最短何手でここまでこれるか」を元に、「この移動は最小手数に含まれるか？」を判定する。
• とする。
• 更新式は、 となる。愚直にやると当然間に合わない。
• ある区間の最小値はセグメント木によって高速に求めることができるため、それでdpテーブルを埋める。
  
• あとは前から dpテーブルを見ながらシミュレーションすればよい。
• 一見間に合わなそうだけど、 内側のループで時間かかった分だけコマは前に進んでくれるため間に合う。（なんとなく）
• セグ木でなくとも、区間最小値を高速に求められればなんでも良い

実装

N, M = map(int, input().split())
S = input()

# dp[i] := ゴールから最短何手でマスiにたどり着けるか
dp = [float('inf')] * (N + 1)
dp[-1] = 0


# セグメント木を使ってdpテーブルを高速に埋める
RMQ = RangeMinimumQuery(N + 1)
RMQ.update(N, 0)
for i in range(N - 1, -1, -1):
    if S[i] == '1':
        continue

    # RMQ.query(l, r) := [l, r)の最小値
    dp[i] = RMQ.query(i, i + M + 1) + 1
    RMQ.update(i, dp[i])


ans = []
position = 0
while position < N:
    for move in range(1, M + 1):
        if position + move > N:
            continue

        if S[position + move] == '1':
            continue

        # 最短手数にならない
        if dp[position + move] == dp[position]:
            continue

        ans.append(move)
        position += move
        break

    else:
        print(-1)
        exit()

print(*ans)