WBC004 D - Photosynthesis 解説

2021年3月18日に開かれたウインドベル(@Twi_Stamp)さん主催の競プロ有志コンテストWind Bel Contest 004 – Good Bye 2A Day 2の解説です。

問題文

ナエムラー(閲覧注意)はレベル で「こうごうせい 」という技を覚えます。 「こうごうせい」で利用される光の波長は です。この区間を 等分したとき、「こうごうせい 」で吸収できるのは 番目の区間の光のみです。しかし、この技を繰り返し使用していると と技のレベルが上がっていきます。

「こうごうせい 」 は のエネルギーを消費する代わりに、区間 を含む連続した 個の区間の光を吸収できます。 区間 の光を吸収すると、 のエネルギーが得られます。

あなたはチャンピオンに挑むため、技のレベルと吸収できる光の波長を最適にしておかなければなりません。 回の「こうごうせい」(技のレベルは問わない)で得られる正味のエネルギー の最大値を求めてください。

制約

• 
• 
• 
• 
• 入力はすべて整数

解説

連続した 個の区間の光を吸収してエネルギーを得る際に のエネルギーを消費するので、あらかじめ、区間 から得られるエネルギー から を引いておきましょう。これを とおくと、次の問題に帰着できます。

数列 が与えられます。 番目の項を含む任意の区間和を取るとき、その最大値を求めてください。

これは典型問題で、方針としては累積和を上手く使うことがカギです。

普通に累積和を使って の区間和を求めるとき、第 項までの累積和テーブルを として として求めますね。これを最大化したいので、 が を含む範囲で はできるだけ大きく、 はできるだけ小さくます。よって、それぞれ の右側の最大値, 左側の最小値を取って来ればOKです。

他にも色々やり方は考えられます。 を始点に左右に2つ累積和を伸ばし、それぞれの最大値を取ってきて足すという方法もポピュラーだと思います。本質的にはさっきのと同じことをしています。

実装例

from itertools import accumulate

def solve():
    # input
    n, k, c = map(int, input().split())
    e = list(map(int, input().split()))
    
    # solve    
    f = [x - c for x in e]
    e = list(accumulate(f, initial=0))
    ans = max(e[k:]) - min(e[:k])

    # output
    print(ans)

t = int(input())
for _ in range(t): solve()

ひとこと

この「左右に分けて累積和を取る」っていうのをセグ木みたいにいっぱい積み込むと、構築 でお好きな区間和取り放題になるデータ構造Disjoint Sparse Tableができます。裏を返せば、Disjoint Sparse Tableを持っていればこの問題は一発だったかもしれません。