2018-04-29から1日間の記事一覧
C 柱柱柱柱柱 Submission #2433397 - AtCoder Beginner Contest 040 問題概要 N本の柱の高さが与えられる。i番目の柱をa_iとすると、一つまたは二つ隣の柱に飛び移るときにabs(a_i - a_i+1)またはabs(a_i-a_i+2)のコストがかかるとき、N番目の柱に着くまでに…
A Zero-Sum Ranges agc023.contest.atcoder.jp 問題概要 長さNの整数列Aが与えられた時、空でない連続する部分列でその総和が0になるものの個数を求める問題。 取った方針 部分列の和を高速に求めたい場合は累積和の利用を考える。S[i] = A[1]+...A[i]なる累…