情報オリンピック2012/2013の本戦での3問目の「夜店」を解説を読みながらACすることができたので,自分なりの解説を残しておこうと思います.
問題リンク:
atcoder.jp
問題概要
個の夜店があり,インデックスが小さい順に遊んでいく.
各夜店には遊ぶと得られる楽しさと遊ぶのに必要な時間が設定されている.
JOIくんは時刻から時刻までの間に夜店をめぐる.
しかし,時刻Sには大きな花火があがるので遊ばないでおく.
JOIくんが実現できる楽しさの和の最大値を求めよ.
重要な制約
考察
まず簡単な全探索を考えます.
各店を遊ぶ/遊ばないの2通りを決めて,条件を満たすかを調べていくと全探索が可能です.
このアルゴリズムの計算量は なので の場合の部分点(10点) を得ることができます.
ここで問題文をよく見ると,時刻 までの最大の楽しさは,
dp[i+1][j] := 店iまで見て,時刻jまでに実現できる最大の楽しさの和
とすることでで求められることがわかります.*1
時刻までの答えは簡単に求められることがわかったので,時刻から時刻までの解を求めることを考えます.
上のDPテーブル上で時刻からまでの答えを考えるときには,普通にナップサックするだけでは答えが求められません(どこの店まで訪れたかわからないため).
新たなDPテーブルとしてdp2を dp2[i][j] := 時刻 から店 i~Nを訪れたときに実現できる最大の楽しさの和 とします.
そうすることによって,答えをdp[i+1][S] + dp2[i][S]とすることができます.
ここで,遷移を考えます.普段のナップサックではdp[0][0]で選択肢が最小ですが,dp2テーブルの遷移はdp2[N][T]が一番選択肢が少なく, dp2[0][S]が一番多い選択肢を持ちます.
DPの遷移でmaxを使う特性上,選択肢が多い方から少ない方へ遷移することは難しく,今回は選択肢が少ない方から多い方へ遷移することにします.
すると,遷移は
のとき dp2[i-1][j] = max(dp2[i-1][j] , dp2[i][j+B[i-1]] + A[i-1])
そうでないとき dp2[i-1][j] = dp2[i-1][j]としてDPテーブルを更新することができます.
よって答えは dp[i][S] + dp2[i+1][S]の和の最大値となります.
実装
import sys
input = lambda: sys.stdin.readline().rstrip()
def main():
N,T,S = map(int, input().split())
A = [0]*N
B = [0]*N
dp = [[0] * (S+1) for _ in range(N+1)]
dp2 = [[0] * (T-S+3) for _ in range(N+1)]
for i in range(N):
ai,bi = map(int, input().split())
A[i] = ai
B[i] = bi
for i in range(N):
for j in range(0,S+1):
dp[i+1][j] = dp[i][j]
if j-B[i] >= 0:
dp[i+1][j] = max(dp[i+1][j], dp[i][j-B[i]] + A[i])
for i in reversed(range(1,N+1)):
for j in reversed(range(S, T+1)):
dp2[i-1][j-S] = dp2[i][j-S]
if j+B[i-1] <= T:
dp2[i-1][j-S] = max(dp2[i-1][j-S], dp2[i][j-S+B[i-1]] + A[i-1])
ans = -1
for i in range(N):
ans = dp[i][S] + dp2[i+1][S-S] if dp[i][S]+dp2[i+1][S-S] > ans else ans
print(ans)
return
if __name__ == '__main__':
main()
しかし,上記コードではPythonで提出すると5000msほどかかるためTLE,しかしPyPyを使うと140MBほど使ってしまうため128MB制限に引っかかりMLEしてしまいます.
なので,Cythonで書いた以下のコードを提出するとACすることができます
from libc.stdio cimport scanf, printf
cdef int N,T,S
cdef int[3100] A, B
cdef int[3100][3100] dp, dp2
cdef int i,j,ans
scanf("%d %d %d", &N, &T, &S)
for 0 <= i < N:
scanf("%d %d", &A[i], &B[i])
for 0 <= i < N:
for 0 <= j <= S:
dp[i+1][j] = max(dp[i+1][j], dp[i][j])
if j-B[i] >= 0:
dp[i+1][j] = max(dp[i+1][j], dp[i][j-B[i]] + A[i])
for i in reversed(range(1,N+1)):
for j in reversed(range(S, T+1)):
dp2[i-1][j] = max(dp2[i-1][j], dp2[i][j])
if j+B[i-1] <= T:
dp2[i-1][j] = max(dp2[i-1][j], dp2[i][j+B[i-1]] + A[i-1])
def main():
ans = -1e9
for i in range(N):
ans = max(ans, dp[i][S] + dp2[i][S])
print(int(ans))
return
if __name__ == '__main__':
main()
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ll long long
#define uint unsigned int
#define all(x) (x).begin(),(x).end()
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
const int INF = 1000000000;
int main() {
IOS;
int N,T,S;
cin >> N >> T >> S;
vector<int>A(N);
vector<int>B(N);
for (int i=0; i<N; i++){
cin >> A[i] >> B[i];
}
vector<vector<int>>dp(N+1, vector<int>(T+1));
for (int i=0; i<N; i++){
for (int j=0; j<=S; j++){
chmax(dp[i+1][j], dp[i][j]);
if (j-B[i] >= 0)chmax(dp[i+1][j], dp[i][j-B[i]] + A[i]);
}
}
vector<vector<int>>dp2 (N+1, vector<int>(T+1));
for (int i=N; i>=1;i--){
for (int j=T; j>=S; j--){
chmax(dp2[i-1][j], dp2[i][j]);
if (j+B[i-1]<=T) chmax(dp2[i-1][j], dp2[i][j+B[i-1]]+A[i-1]);
}
}
int ans = -INF;
for (int i=0; i<N; i++) chmax(ans, dp[i][S]+dp2[i+1][S]);
cout << ans << endl;
}