ABC188 D - Snuke Prime
備忘録
問題
回答
import sys import os import math import bisect import itertools import collections import heapq import queue import array import time # 時々使う # import numpy as np # from decimal import Decimal, ROUND_HALF_UP # from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall # from collections import defaultdict, deque # 再帰の制限設定 sys.setrecursionlimit(10000000) def ii(): return int(sys.stdin.buffer.readline().rstrip()) def il(): return list(map(int, sys.stdin.buffer.readline().split())) def fl(): return list(map(float, sys.stdin.buffer.readline().split())) def iln(n): return [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)] def iss(): return sys.stdin.buffer.readline().decode().rstrip() def sl(): return list(map(str, sys.stdin.buffer.readline().decode().split())) def isn(n): return [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)] def lcm(x, y): return (x * y) // math.gcd(x, y) MOD = 10 ** 9 + 7 # MOD = 998244353 INF = float('inf') def main(): if os.getenv("LOCAL"): sys.stdin = open("input.txt", "r") N, C = il() period = [] for _ in range(N): a, b, c = il() period.append([a-1, c]) period.append([b, -c]) period.sort() ret, fee, day = 0, 0, 0 for d, m in period: if day != d: ret += min((d - day) * fee, (d - day) * C) day = d fee += m print(ret) if __name__ == '__main__': main()
考え方
N
個のクエリが与えられ、ある期間の合算がC
より上回る日はプライムを使用した方が安くなる。
例えば、例1のように1日目と2日目に4円のサービスを利用して、
2日目に新たに4円のサービスを利用する。
その場合、2日目に利用するサービスは2つとなり、合計して8円の利用料が必要となる。
そのため、2日目だけプライムを使用すると、初日の4円と2日目の6円(プライム料金)の合計で利用料は10円となる。
回答は公式解説の解説を元に実装。
クエリの数だけ累積和を行うようなイメージで理解した。
コンテスト中はいもす法で回答しようとして、がっつりハマった。
累積和で回答するためには、a, b
の最大値である10 ** 9
の要素を持った配列が必要となるが、
numpy
を使用しても手元で10秒程度の時間を要した。
累積和で2秒以内に処理を終わらすためには、要素数が精々10 ** 5
程度の範囲である必要があるっぽい。