ふんわりと、以下のようなDPでできそう。
$K$ 個までしか積めない＝最後に家に戻ったのが $K$ 軒前まででないといけない。
よって、$DP[i]$ を求めたいとき、（DP配列をセグメント木などで実装して）
$DP[i-K]～DP[i-1]$ の最小値を得たら $DP[i]$ が求まる、というようなことがしたい。
ただ、それだと上記の定義のままではダメ。
たとえば3軒目を訪ねるとき（$DP[3]$ を埋めるとき）
DP[0]: サ→①→②→③→...
~~ ←DP[0]の値が示す移動
DP[1]: サ→①→サ→②→③→...
~~~~~~~~~~ ←DP[1]の値が示す移動
DP[2]: サ→①→②→サ→③→...
~~~~~~~~~~~~~~ ←┬小さい方がDP[2]の値が示す移動
または │
サ→①→サ→②→サ→③→... │
~~~~~~~~~~~~~~~~~~ ←┘
※サ: サンタの家
DPの示す値の最終位置がサンタの家だと、そこから3軒目に行くまでの距離がそれぞれ異なってしまうので、比較できない。
最終位置は、$DP[3]$ を求める上では3軒目である必要がある。よって、DPを以下で定義しなおして、
DP[3,0]: サ→①→②→③→...
~~~~~~~~~~~~~~
DP[3,1]: サ→①→サ→②→③→...
~~~~~~~~~~~~~~~~~~
DP[3,2]: サ→...→②→サ→③→...
~~~~~~~~~~~~~~~~~~~
これなら同条件で比較でき、$DP[3,0]～DP[3,2]$ の最小値が、3軒目に配るまでの最短距離となっている。
次、1つ進めて $DP[4,*]$ を求めたいとき、
DP[4,0]: サ→①→②→③→④→...
~~~~~~~~~~~~~~~~~~
DP[4,1]: サ→①→サ→②→③→④→...
~~~~~~~~~~~~~~~~~~~~~~
DP[4,2]: サ→...→②→サ→③→④→... （一例）
~~~~~~~~~~~~~~~~~~~~~~~
DP[4,3]: サ→.......→③→サ→④→... （一例）
~~~~~~~~~~~~~~~~~~~~~~~
$DP[4,0]～DP[4,2]$ に関しては、$DP[3,0]～DP[3,2]$ に新たに③→④の距離を加算すればよい。
$DP[4,3]$ に関しては、$DP[3,*]$ の最小値に ③→サ→④ の距離を加算した値を新規追加すればよい。
これで4軒目までの最短距離も求められた。後は繰り返し。
実装上は $i$ の次元は省略して破壊的に更新していくとして、
「区間加算更新」と「区間最小値クエリ」を処理できる遅延評価セグメント木でDPを実装すれば $O(N \log{N})$ で解ける。
$N+1$ 軒目に便宜的にサンタの家を入れておけば、$i=N+1$ まで回した後の $DP[N]$ が答え。
Python3
from operator import add
from typing import TypeVar, Generic, Callable, List
T = TypeVar('T')
U = TypeVar('U')
class LazySegmentTreeInjectable(Generic[T, U]):
def __init__(self,
n: int,
identity_data: Callable[[], T],
identity_lazy: Callable[[], U],
operation: Callable[[T, T], T],
mapping: Callable[[T, U], T],
composition: Callable[[U, U], U],
):
self.n = n
self.depth = n.bit_length()
self.offset = 1 << self.depth
self.identity_data = identity_data
self.identity_lazy = identity_lazy
self.operation = operation
self.mapping = mapping
self.composition = composition
self.data = [identity_data() for _ in range(self.offset << 1)]
self.lazy = [identity_lazy() for _ in range(self.offset)]
@classmethod
def from_array(cls,
arr: List[T],
identity_data: Callable[[], T],
identity_lazy: Callable[[], U],
operation: Callable[[T, T], T],
mapping: Callable[[T, U], T],
composition: Callable[[U, U], U],
):
ins = cls(len(arr), identity_data, identity_lazy, operation, mapping, composition)
ins.data[ins.offset:ins.offset + ins.n] = arr
for i in range(ins.offset - 1, 0, -1):
ins.update(i)
return ins
def push(self, i: int) -> None:
if i < self.offset:
data = self.data
lazy = self.lazy
lz = lazy[i]
lch = i << 1
rch = lch + 1
data[lch] = self.mapping(data[lch], lz)
data[rch] = self.mapping(data[rch], lz)
if lch < self.offset:
lazy[lch] = self.composition(lazy[lch], lz)
lazy[rch] = self.composition(lazy[rch], lz)
lazy[i] = self.identity_lazy()
def update(self, i: int) -> None:
lch = i << 1
rch = lch + 1
self.data[i] = self.operation(self.data[lch], self.data[rch])
def all_apply(self, i: int, d: U) -> None:
self.data[i] = self.mapping(self.data[i], d)
if i < self.offset:
self.lazy[i] = self.composition(self.lazy[i], d)
def propagate(self, l: int, r: int) -> None:
for i in range(self.depth, 0, -1):
if ((l >> i) << i) != l:
self.push(l >> i)
if ((r >> i) << i) != r:
self.push((r - 1) >> i)
def range_update(self, l: int, r: int, d: U) -> None:
l += self.offset
r += self.offset
self.propagate(l, r)
l2 = l
r2 = r
while l < r:
if (l & 1) == 1:
self.all_apply(l, d)
l += 1
if (r & 1) == 1:
r -= 1
self.all_apply(r, d)
l >>= 1
r >>= 1
l = l2
r = r2
for i in range(1, self.depth + 1):
if ((l >> i) << i) != l:
self.update(l >> i)
if ((r >> i) << i) != r:
self.update((r - 1) >> i)
def range_query(self, l: int, r: int) -> T:
l += self.offset
r += self.offset
self.propagate(l, r)
sml = self.identity_data()
smr = self.identity_data()
while l < r:
if (l & 1) == 1:
sml = self.operation(sml, self.data[l])
l += 1
if (r & 1) == 1:
r -= 1
smr = self.operation(self.data[r], smr)
l >>= 1
r >>= 1
return self.operation(sml, smr)
def point_set(self, p: int, d: T) -> None:
p += self.offset
for i in range(self.depth, 0, -1):
self.push(p >> i)
self.data[p] = d
for i in range(1, self.depth + 1):
self.update(p >> i)
def point_get(self, p: int) -> T:
p += self.offset
for i in range(self.depth, 0, -1):
self.push(p >> i)
return self.data[p]
def debug_print(self) -> None:
i = 1
while i <= self.offset:
print(*map('{: 4f}'.format, self.data[i:i * 2]))
i <<= 1
i = 1
while i <= self.offset:
print(*map('{: 4f}'.format, self.lazy[i:i * 2]))
i <<= 1
n, k = map(int, input().split())
sx, sy = map(int, input().split())
direct = [0]
sequence = []
px, py = 0, 0
for _ in range(n):
x, y = map(int, input().split())
direct.append(((sx - x) ** 2 + (sy - y) ** 2) ** 0.5)
sequence.append(((px - x) ** 2 + (py - y) ** 2) ** 0.5)
px = x
py = y
direct.append(0)
sequence.append(0)
sequence[0] = 0
identity_data = lambda: float('inf')
identity_lazy = float
operation = min
mapping = add
composition = add
dp = LazySegmentTreeInjectable(n + 1, identity_data, identity_lazy, operation, mapping, composition)
dp.point_set(0, direct[1])
for i in range(1, n + 1):
l = max(0, i - k)
best = dp.range_query(l, i)
dp.point_set(i, best + direct[i] + direct[i + 1])
dp.range_update(l, i, sequence[i])
ans = dp.point_get(n)
print(ans)
関節点なら、そこから出ている辺の本数と、橋の本数を見る。
(a)全ての辺が橋なら、連結成分は「橋の本数-1」増えて C+橋の本数-1
### ###
|
###-#-### → ### ###
|
### ###
(b)そうで無い場合、橋があるなら、橋の本数分増える。 C+橋の本数
##### ##### 橋でない連結成分が1つ残ったまま、
# | # 橋の本数分だけ新たな連結成分ができる
###-#-### → ### ###
|
### ###
(c)橋が0本の場合、必ず以下のような形となっている。
2本ずつ出る辺が、それぞれペアになってくっついている。
##### #####
# | #
###-#-### → ### ###
| # #
##### #####
よって、この場合は真ん中を消すと2つに分かれ、連結成分数は1増えて C+1 となる。
(b)(c) の場合、連結成分の増減は、グリッドグラフに限った話である点に注意する。
この問題ではよいが、一般のグラフだと成り立たない。
グリッドグラフの最大次数が4であることを利用しているので、
例えば三つ葉のクローバー（♣の茎を取った形）のようなグラフの真ん中（次数6）を消すと、橋が0本と (c) と似たような状況ではあるが3つに分かれる。
一般の場合、関節点と橋の情報だけでは計算できないが、それらを求める際に計算した、DFS木とlowlinkに立ち返ればチェックできる。（公式Editorial参照）
Python3
from operator import add
from typing import TypeVar, Generic, Callable, List
T = TypeVar('T')
U = TypeVar('U')
class LazySegmentTreeInjectable(Generic[T, U]):
def __init__(self,
n: int,
identity_data: Callable[[], T],
identity_lazy: Callable[[], U],
operation: Callable[[T, T], T],
mapping: Callable[[T, U], T],
composition: Callable[[U, U], U],
):
self.n = n
self.depth = n.bit_length()
self.offset = 1 << self.depth
self.identity_data = identity_data
self.identity_lazy = identity_lazy
self.operation = operation
self.mapping = mapping
self.composition = composition
self.data = [identity_data() for _ in range(self.offset << 1)]
self.lazy = [identity_lazy() for _ in range(self.offset)]
@classmethod
def from_array(cls,
arr: List[T],
identity_data: Callable[[], T],
identity_lazy: Callable[[], U],
operation: Callable[[T, T], T],
mapping: Callable[[T, U], T],
composition: Callable[[U, U], U],
):
ins = cls(len(arr), identity_data, identity_lazy, operation, mapping, composition)
ins.data[ins.offset:ins.offset + ins.n] = arr
for i in range(ins.offset - 1, 0, -1):
ins.update(i)
return ins
def push(self, i: int) -> None:
if i < self.offset:
data = self.data
lazy = self.lazy
lz = lazy[i]
lch = i << 1
rch = lch + 1
data[lch] = self.mapping(data[lch], lz)
data[rch] = self.mapping(data[rch], lz)
if lch < self.offset:
lazy[lch] = self.composition(lazy[lch], lz)
lazy[rch] = self.composition(lazy[rch], lz)
lazy[i] = self.identity_lazy()
def update(self, i: int) -> None:
lch = i << 1
rch = lch + 1
self.data[i] = self.operation(self.data[lch], self.data[rch])
def all_apply(self, i: int, d: U) -> None:
self.data[i] = self.mapping(self.data[i], d)
if i < self.offset:
self.lazy[i] = self.composition(self.lazy[i], d)
def propagate(self, l: int, r: int) -> None:
for i in range(self.depth, 0, -1):
if ((l >> i) << i) != l:
self.push(l >> i)
if ((r >> i) << i) != r:
self.push((r - 1) >> i)
def range_update(self, l: int, r: int, d: U) -> None:
l += self.offset
r += self.offset
self.propagate(l, r)
l2 = l
r2 = r
while l < r:
if (l & 1) == 1:
self.all_apply(l, d)
l += 1
if (r & 1) == 1:
r -= 1
self.all_apply(r, d)
l >>= 1
r >>= 1
l = l2
r = r2
for i in range(1, self.depth + 1):
if ((l >> i) << i) != l:
self.update(l >> i)
if ((r >> i) << i) != r:
self.update((r - 1) >> i)
def range_query(self, l: int, r: int) -> T:
l += self.offset
r += self.offset
self.propagate(l, r)
sml = self.identity_data()
smr = self.identity_data()
while l < r:
if (l & 1) == 1:
sml = self.operation(sml, self.data[l])
l += 1
if (r & 1) == 1:
r -= 1
smr = self.operation(self.data[r], smr)
l >>= 1
r >>= 1
return self.operation(sml, smr)
def point_set(self, p: int, d: T) -> None:
p += self.offset
for i in range(self.depth, 0, -1):
self.push(p >> i)
self.data[p] = d
for i in range(1, self.depth + 1):
self.update(p >> i)
def point_get(self, p: int) -> T:
p += self.offset
for i in range(self.depth, 0, -1):
self.push(p >> i)
return self.data[p]
def debug_print(self) -> None:
i = 1
while i <= self.offset:
print(*map('{: 4f}'.format, self.data[i:i * 2]))
i <<= 1
i = 1
while i <= self.offset:
print(*map('{: 4f}'.format, self.lazy[i:i * 2]))
i <<= 1
n, k = map(int, input().split())
sx, sy = map(int, input().split())
direct = [0]
sequence = []
px, py = 0, 0
for _ in range(n):
x, y = map(int, input().split())
direct.append(((sx - x) ** 2 + (sy - y) ** 2) ** 0.5)
sequence.append(((px - x) ** 2 + (py - y) ** 2) ** 0.5)
px = x
py = y
direct.append(0)
sequence.append(0)
sequence[0] = 0
identity_data = lambda: float('inf')
identity_lazy = float
operation = min
mapping = add
composition = add
dp = LazySegmentTreeInjectable(n + 1, identity_data, identity_lazy, operation, mapping, composition)
dp.point_set(0, direct[1])
for i in range(1, n + 1):
l = max(0, i - k)
best = dp.range_query(l, i)
dp.point_set(i, best + direct[i] + direct[i + 1])
dp.range_update(l, i, sequence[i])
ans = dp.point_get(n)
print(ans)