JOI2010本選A 旅人

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

累積和

はじめに

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

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

問題

https://atcoder.jp/contests/joi2010ho/tasks/joi2010ho_a

この問題では累積和の計算が求められます。

Pythonの場合、itertools.accumulateを用いると良いでしょう。

コード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import itertools
MOD = 10**5
N, M = map(int, input().split())
D = [0] # 先頭に0を入れておくと、累積和の差分計算の際に楽
for n in range(N-1):
d = int(input())
D.append(d)
C = []
for m in range(M):
c = int(input())
C.append(c)

csum = list(itertools.accumulate(D))
cur = 1
ans = 0
for c in C:
next = cur + c # 移動
ans += abs(csum[next-1]-csum[cur-1]) # 絶対値を足す
cur = next # 次の移動開始地点
ans %= MOD
print (ans)

記事情報

  • 投稿日:2020年5月4日
  • 最終更新日:2020年5月8日