AtCoder AGC048_C Penguin Skating 解説

C - Penguin Skating

問題概要

個のマスが横一列に並んでいて、左から の番号がついている
匹のペンギンがいて、ペンギン はマス にいる
次の操作を繰り返して、全ての についてペンギン がマス にいる状態にすることは可能か

• 匹のペンギンを選び、目の前に空マスがなくなるまで選んだ方向に移動させる

可能かどうかの判定、可能なら最小操作回数を求める

解説

サンプル 1 の図です。（筆圧さん......）
○が初期状態のペンギンの位置、☆がペンギンのゴールの位置です。

この場合は簡単ですが、次のような場合が難しいです。

例えば「1回操作するだけでゴールに到着できるペンギンから貪欲に動かす」アルゴリズムだとこのケースで間違えてしまいます。

可能かどうかの判定方法を考えます。
まず、ペンギンが移動したあとの形はこうなります。
支柱ともいえるペンギンにぶつかるように複数のペンギンが集まります。

このとき、黒丸のペンギンの番号を 、移動したペンギンの番号を とすると、それぞれのペンギンの位置は となります。2匹のペンギンの間に 匹のペンギンがいることになります。
ちなみに、これは左右逆にしても成り立ちます。
つまり、ペンギンが左に移動するのなら 、ペンギンが右に移動するのなら となる が存在するとき、ペンギン はゴールに到達できる。といえます。
そしてこれを式変形すると となり、 が独立になります。

可能である場合の最小操作回数を求めます。

最小操作回数を求めるためには上の図において、無駄足を踏むペンギンの数を求めなければいけません。
ここで、ペンギンが移動した後の形を挙げます。

先ほどの図に加え、ゴールに到達した後のペンギンも考慮します。
黒丸には初期状態のペンギン、ゴールに到達したペンギンが入ります。
よって、ペンギン が左に移動してゴールに到達するのに必要な無駄足ペンギンの数は次のように計算できます。

• である のうち、 または を満たす最大のものについて、

これにペンギン 自身の移動回数を含め、 となります。
ペンギン が右に移動するときは である条件を満たす の最小値について計算します。

この問題を解くのに必要なステップをまとめます。

• である番兵ペンギンを加える
• 各 について、 を求める
• 各 について次の計算で求められる値の総和を求める
  • ペンギン が左に移動するとき、 であり または を満たす最大の について （ が存在しないのなら不可能）
  • ペンギン が右に移動するとき、 であり または を満たす最小の について （ が存在しないのなら不可能）

実装には python の辞書型 (dict) が便利です。（C++ でいう map でしたっけ）

n, l = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

ans = 0

# 辞書型 + 番兵
# マス0番にいるペンギン-1番を持つ
s = {1:-1}
for i in range(n):
  # もし左に移動するのなら b[i]-i をチェックする
  if a[i] > b[i]:
    if b[i]-i not in s:
      exit(print(-1))
    ans += i - s[b[i]-i]
  # a[i]-i,b[i]-i を満たす i の最大値を更新
  s[a[i]-i] = i
  s[b[i]-i] = i

# マスl+1番にいるペンギンn番を持つ
s = {l+1-n:n}
for i in range(n-1, -1, -1):
  # もし右に移動するのなら b[i]-i をチェックする
  if a[i] < b[i]:
    if b[i]-i not in s:
      exit(print(-1))
    ans += s[b[i]-i]-i
  # a[i]-i,b[i]-i を満たす i の最小値を更新
  s[a[i]-i] = i
  s[b[i]-i] = i

print(ans)

問題設定も面白いし解法も簡潔で面白いのでとても好きです