JOI2015本選A 鉄道旅行

この記事で使うアルゴリズム

累積和

いもす法

はじめに

カテゴリー競プロ初中級者100問では、Qiitaにて@e869120さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編:目指せ水色コーダー!】としてまとめられている100問をPythonで解いています。

全問題の一覧はこちらです

問題

https://atcoder.jp/contests/joi2015ho/tasks/joi2015ho_a

この問題では累積和を応用したいもす法というアルゴリズムで解くことができます。

方針

それぞれの鉄道について独立に、紙の切符とICカードのどちらを使った方が安いかを考えます。そのためにはA,B,Cの情報に加えて、その鉄道を何回利用するかが分かれば良いです。

これはいもす法を用いて高速に求めることが可能です。いもす法の詳細は以下のページに書いています。

ABC014C AtColor

コード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
import itertools
N, M = map(int, input().split())
P = list(map(int, input().split()))
A = []
B = []
C = []
for n in range(N-1):
a,b,c = map(int, input().split())
A.append(a)
B.append(b)
C.append(c)
imos = [0] * N
for m in range(M-1):
if P[m] < P[m+1]:
imos[P[m]-1] += 1
imos[P[m+1]-1] -= 1
else:
imos[P[m]-1] -= 1
imos[P[m+1]-1] += 1
csum = list(itertools.accumulate(imos))
ans = 0
for n in range(N-1):
cnt = csum[n]
ans += min(A[n]*cnt, B[n]*cnt+C[n])
print (ans)umulate(imos))
print (max(csum))

記事情報

  • 投稿日:2020年6月21日
  • 最終更新日:2020年6月21日