JOI難易度６ 夜店

問題原文

https://www.ioi-jp.org/joi/2011/2012-ho-prob_and_sol/2012-ho.pdf#page=7

問題要旨

祭りは時刻０から時刻 まで行われる祭りにおいて、 つの夜店からいくつかを選んで、順番通りに遊ぶことを考える。
夜店 の楽しさは で、遊ぶのに かかる。出来るだけ多く楽しみたいが、 時刻 に花火が上がるため、その時間帯には遊ぶことができない。（花火が上がる瞬間に遊び始める、遊びおわるはOK）
楽しさの合計を最大化せよ。

• 
• 

解法

こういう中間でぶった斬られるようなものは、２つの dpテーブルで挟み込むようなことを考えればよい。
つまり、

• 夜店１ 〜 i で遊ぶものを選んだ時の最大値（花火が上がる前に遊ぶ）
• 夜店 i 〜 N の中から遊ぶものを選んだ時の最大値 （花火が上がった後で遊ぶ）

の２つの dpテーブルについて計算しておいて、各 について答えを計算すればいい。
ベースとなる考え方は、

atcoder.jp

の解法１と同じ。

at274.hatenablog.com

そしてこれは当時書いた解説。
よかったらどうぞ。

実装

およそ [tex: 10⁷] ステップがあり、TLは１秒、メモリも128MBと割と怖かった。（PyPyはメモリめっちゃ使うため）
ので、１次元で計算して、各結果をメモっておいて、最後に各 についての答えを導くことにした。
TL, メモリともに超余裕。（ここまでする必要なかったかも）

import sys
my_input = sys.stdin.readline
N, T, S = map(int, my_input().split())
shops = [list(map(int, my_input().split())) for _ in range(N)]

dp1 = [0] * (S + 1)  # 前から
dp2 = [0] * (T - S + 1)  # 後ろから

dp1_result, dp2_result = [], []
ans = 0
for i in range(N):
    af, bf = shops[i]
    for t in reversed(range(S + 1)):
        if t + bf <= S:
            dp1[t + bf] = max(dp1[t + bf], dp1[t] + af)

    ab, bb = shops[-i-1]
    for t in reversed(range(T - S + 1)):
        if t + bb <= T - S:
            dp2[t + bb] = max(dp2[t + bb], dp2[t] + ab)

    dp1_result.append(dp1[-1])
    dp2_result.append(dp2[-1])

dp1_result = [0] + dp1_result
dp2_result = dp2_result[::-1] + [0]

for r1, r2 in zip(dp1_result, dp2_result):
    ans = max(ans, r1 + r2)

print(ans)

感想

旧ABCの「高橋くんとカード」とかも似た考え方が使えた気がする。
割と後から答えを求める方が添字周りで爆発しなくて良さそうだなと少し思った。