累積和としゃくとり法
今日は、ABC172で累積和としゃくとり法の複合問題が出たので、
この2つのアルゴリズムを簡単にまとめる。
目次
累積和
実は累積和はABC152 C問題でも出ていたが、当時あまり良くわかっていなくて
いまひとつちゃんと説明できなかった。
累積和は、数列 $ A $ について、最初からi番目の和を求めたリストのこと。
$ A $ の累積和を $ S $ とした時、こんな感じで計算する。
$$ A = [1, 2, 3, 4, 5] $$
として
$$ \begin{eqnarray} &A_0& = 1 \\ &A_0& + A_1 = 1 + 2 =3 \\ &A_0& + A_1 + A_2 = 1 + 2 + 3 = 6 \\ &A_0& + A_1 + A_2 + A_3 = 1 + 2 + 3 + 4 = 10 \\ &A_0& + A_1 + A_2 + A_3 + A_4 = 1 + 2 + 3 + 4 + 5 = 15 \end{eqnarray} $$
というように、最初からひとつずつ項を増やして足していく。
その結果、 数列 $ A $ の累積和 $ S $ は、以下のようになる
$$ S = [1, 3, 6, 10, 15] $$
ライブラリとしては、itertools.accumulateや、numpy.cumsum(list)が使える。
しゃくとり法
しゃくとり法は、ある数列の指定された条件を満たす区間について、最大最小を出す・数え上げをする時に使える。
ここでの「区間」は、連続する部分列であり、半開区間 [a, b)として考える。
「区間」の左端をleft,右端をrightとしたとき、以下の場合なら発動できる。
- leftに対して、条件を満たすrightの最大値f(left)は広義単調増加関数
- leftに対して、条件を満たすrightの最小値f(left)は広義単調増加関数
条件を満たしていることを確認しながら、rightとleftを1つずつずらして確認する。
今回、リストのインデックスと中身を同時に扱うため、enumerate関数を使ってループを回す。
ABC172 C. Tsundoku
蓋を開けたら累積和としゃくとり法の複合だった。
累積和と二分探索でもできるらしいが、略。
考え方として、A,Bの本の山について、例えば山Aの1番目からn番目まで読んだら
トータル何分かかるかを事前に求めておく。
(全く読まない場合は0分なので、それも含める)
これは、累積和でささっと求められる。
次に、Aの山から読む本の冊数を固定し、その時Bの山からいくつ読むか
考える。この時Bから読む本の冊数はB全てから1冊ずつ減らし、
A, Bの読破時間合計が制限時間kに引っかからなくなったら、その時の冊数を答えとして記録する。
できるだけ多く本を読みたいので、全通り試して冊数の最大値を出す。
この部分は、しゃくとり法で実装した。
解説ACしたコード
# coding:utf-8 import itertools n, m, k = map(int, input().split()) a = list(map(int, input().split())) b = list(map(int, input().split())) ans = 0 j = m aa = [0] + list(itertools.accumulate(a)) bb = [0] + list(itertools.accumulate(b)) # print(aa) # print(bb) # しゃくとり法 / Aの山だけ読みつつ、そこにBからいくつ取り出すかで考える for i, a_item in enumerate(aa): if a_item > k: break while a_item + bb[j] > k: j -= 1 ans = max(i + j, ans) print(ans)
