Edit

【pythonでABC197を解説】E - Traveler

問題概要

問題ページ

E - Traveler
E - Traveler

問題ページへ移動する

問題文

数直線上にボール \(1\) からボール \(N\) までの \(N\) 個のボールがあります。
ボール \(i\) は座標 \(X_i\) にあります。
各ボールには \(1\) 以上 \(N\) 以下の整数で表される色がついていて、ボール \(i\) の色は整数 \(C_i\) で表されます。
今座標 \(0\) にいるあなたは、毎秒 \(1\) の速さで数直線上を動き、全てのボールを回収してから再び座標 \(0\) に戻ります。
このとき、ボールの色を表す整数を回収順に並べた時に広義単調増加となっている必要があります。
ボールを回収するにはボールと同じ座標にいる必要がありますが、ボールを回収できる時に必ずしも回収する必要はありません。
座標 \(0\) を出発してから、全てのボールを回収して再び座標 \(0\) に戻るまでにかかる時間の最小値を求めてください。

制約

  • \(1 \le N \le 2 \times 10^5\)
  • \(|X_i| \le 10^9\)
  • \(X_i \neq X_j (i \neq j)\)
  • \(X_i \neq 0\)
  • \(1 \le C_i \le N\)
  • 入力に含まれる値は全て整数である

問題の考察

ACコード

import sys
import collections


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n = int(input().rstrip('\n'))
    d = collections.defaultdict(list)
    for i in range(n):
        x, c = list(map(int, input().rstrip('\n').split()))
        d[c] += [x]
    f = collections.defaultdict(int)
    q = [0]
    for k in sorted(d.keys()):
        left = min(d[k])
        right = max(d[k])
        f[left] = 10 ** 15
        f[right] = 10 ** 15
        while q:
            now = q.pop()
            left_cost = abs(right - now) + abs(right - left)
            right_cost = abs(left - now) + abs(right - left)
            f[left] = min(f[left], f[now] + left_cost)
            f[right] = min(f[right], f[now] + right_cost)
        q.append(left)
        q.append(right)
    ans = 10 ** 15
    for v in q:
        ans = min(ans, abs(v) + f[v])
    print(ans)


if __name__ == '__main__':
    solve()

-Edit
-