Edit

【pythonでABC095を解説】D - Static Sushi

問題概要

問題ページ

問題文

日本料理店「停止寿司」は円形のカウンターが一つあるだけのシンプルな店です。カウンターの外周の長さは \(C\) メートルで、カウンターの内部に客が立ち入ることはできません。

中橋くんが入店し、カウンターのそばまで案内されました。いま、カウンター上には \(N\) 貫の寿司が置かれています。そのうち \(i\) 貫目は中橋くんがいる位置から \(x_i\) メートル時計回りに進んだ位置に置かれており、\(v_i\) キロカロリーの栄養価を持ちます。

中橋くんはカウンターの外周を自由に歩き回ることができます。寿司が置かれている位置にたどり着いたら、その寿司を食べて寿司が持つ栄養価を摂取することができます(当然、その寿司は消えます)。ただし、歩く際に \(1\) メートルあたり \(1\) キロカロリーを消費します。

満足したら、いつでも好きな位置から店を出ることができます(始めにいた位置に戻らなくても構いません)。店を出るまでに最大で差し引き何キロカロリーを摂取することができるでしょうか?すなわち、退店するまでに摂取した栄養価の合計から消費したエネルギーを引いた値の最大値はいくらでしょうか?なお、他に客はおらず、新たな寿司がカウンターに追加されることもないものとします。また、中橋くんは十分な栄養を蓄えているため、どれだけ歩いてエネルギーを消費しても餓死しないものとします。

制約

  • \(1 ≤ N ≤ 10^5\)
  • \(2 ≤ C ≤ 10^{14}\)
  • \(1 ≤ x_1 < x_2 < ... < x_N < C\)
  • \(1 ≤ v_i ≤ 10^9\)
  • 入力中のすべての値は整数である。

部分点

  • \(N ≤ 100\) を満たすテストセットに正解すると、\(300\) 点が与えられる。

問題の考察

ACコード

import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n, c = list(map(int, input().rstrip('\n').split()))
    xy = [list(map(int, input().rstrip('\n').split())) for _ in range(n)]
    f_cost = xy[0][0]
    f_energy = xy[0][1]
    f = [[f_cost, f_energy, f_energy - f_cost]]
    b_cost = c - xy[-1][0]
    b_energy = xy[-1][1]
    b = [[b_cost, b_energy, b_energy - b_cost]]
    for i in range(1, n):
        f_cost += xy[i][0] - xy[i-1][0]
        f_energy += xy[i][1]
        f.append([f_cost, f_energy, max(f_energy - f_cost, f[-1][2])])
        b_cost += xy[-i][0] - xy[-i-1][0]
        b_energy += xy[-i-1][1]
        b.append([b_cost, b_energy, max(b_energy - b_cost, b[-1][2])])
    mx = 0
    for i in range(n):
        mx = max(mx, f[i][2], b[i][2])
        if n - i - 2 >= 0:
            mx = max(mx, f[i][2] - f[i][0] + b[n - i - 2][2], b[i][2] - b[i][0] + f[n - i - 2][2])
    print(mx)


if __name__ == '__main__':
    solve()

プログラミング

-Edit
-