Submission #48986747

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import heapq
from collections import deque
from collections import defaultdict
import math
# １．入力値読み込み
N,K = map(int, input().split())
Sx,Sy = map(int, input().split())
kid_pos = list()
for i in range(N):
    X,Y = map(int, input().split())
    kid_pos.append((X,Y))
# ２．家間直通とサンタ家経由時の差分の値をそれぞれ求める
direct = list() # 直通の場合
via = list()    # サンタの家を経由する場合の差異
dist_X = abs(Sx - kid_pos[0][0])
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

import heapq
from collections import deque
from collections import defaultdict
import math

# １．入力値読み込み
N,K = map(int, input().split())
Sx,Sy = map(int, input().split())

kid_pos = list()

for i in range(N):
    X,Y = map(int, input().split())
    kid_pos.append((X,Y))


# ２．家間直通とサンタ家経由時の差分の値をそれぞれ求める
direct = list() # 直通の場合
via = list()    # サンタの家を経由する場合の差異

dist_X = abs(Sx - kid_pos[0][0])
dist_Y = abs(Sy - kid_pos[0][1])
dist_direct = math.sqrt(dist_X**2 + dist_Y**2)
direct.append(dist_direct)
via.append(0)

for i in range(1,N):
    dist_X = abs(kid_pos[i][0] - kid_pos[i-1][0])
    dist_Y = abs(kid_pos[i][1] - kid_pos[i-1][1])
    dist_direct = math.sqrt(dist_X**2 + dist_Y**2)
    direct.append(dist_direct)
    
    dist_Xa = abs(kid_pos[i][0] - Sx)
    dist_Ya = abs(kid_pos[i][1] - Sy)
    dist_Xb = abs(Sx - kid_pos[i-1][0])
    dist_Yb = abs(Sy - kid_pos[i-1][1])
    dist_via = math.sqrt(dist_Xa**2 + dist_Ya**2) + math.sqrt(dist_Xb**2 + dist_Yb**2) - direct[-1]     # 差異なので直通の場合の値を引く 
    via.append(dist_via)


# ３．dpする
# dp[i] = i番目の家に行くときにサンタの家を経由した場合の、それまでの余分経路長さ最小値 とする。
# dp[i] = dist_via[i] + min(dp[i-K],...,dp[i-1])
# … i番目の家に行くときの余分なコスト + i-1番目の家までに配れるプレゼントを確保できる範囲での最小値
# 右項をスライド最小値を用いることで、dp[i]を求める
dp_deq = deque([])                  # dp[i-K]～dp[i-1]が入るdeque
heap_que = list()
heapq.heapify(heap_que)             # dp_deqにある可能性がある値が入るheap
valid_value_cnt = defaultdict(int)  # dp_deqの値とその個数を管理するdict

for i in range(N):
    # dp_deqの最小値を取り出す
    v = 0

    while len(heap_que) != 0:
        v = heap_que[0]
        if valid_value_cnt[v] == 0:
            heapq.heappop(heap_que)
        else:
            break

    dp_i = via[i] + v

    if len(dp_deq) > K-1:
        v = dp_deq.popleft()
        valid_value_cnt[v] -= 1
    
    heapq.heappush(heap_que,dp_i) 
    dp_deq.append(dp_i)
    valid_value_cnt[dp_i] += 1


# ４．最終的な答えを求める
# dp_deqから最小値を取り出す
v = 0
while len(heap_que) != 0:
    v = heap_que[0]
    if valid_value_cnt[v] == 0:
        heapq.heappop(heap_que)
    else:
        break

# 最後の家からサンタの家まで戻る分の値を求める
dist_X = abs(kid_pos[-1][0] - Sx)
dist_Y = abs(kid_pos[-1][1] - Sy)
dist_return = math.sqrt(dist_X**2 + dist_Y**2)

ans = sum(direct) + v + dist_return
print(ans)

Submission Info

Judge Result