COLOCON 2018 D - すぬけそだて――トレーニング――

• 問題

問題概要

N,X,t[N]が与えられる。
スタミナXを持っていて、単位時間に1回復する。
t[i]にログインできるとして、j(1<=j<=N)回プレイした時に使える最大のスタミナはいくつか、全て出力せよ。
なおゲームをプレイするとその度に使い切るものとする。
1<=N<=3500,1<= X ,t[i] <= 10⁹,t[i] < t[i+1]

解法

dp[i][j] := i回プレイして、t[j]に最後にログインした時の使ったスタミナの最大値
(最後にいつログインしたかによって残ってるスタミナが決まるため)
とすると、O(N³)のDPが組める。
for i in N
for j in N
dp[i][j] = max_(1<=k<j)(dp[i-1][k]+min(X,t[j]-t[k]))

ただしこれは間に合わない。
遷移はスタミナが満タンになる直前か満タンになった直後のみを考えれば十分なため(解説に詳しく書いてある)、
dp[i][j]からの遷移を考える際には、t[k]-t[j]<=X、すなわちt[k]<=t[j]+Xを満たす最大のkを求め、
k(スタミナが満タンになる直前)とk+1(スタミナが満タンになった直後)への遷移のみを考えれば良い。
コードではind[i]として二分探索で求めている。
t[N]まで行っても最大まで回復しない時は、kが最後になり、k+1はdpからはみ出すので考えなくても良い。

メモ

やっぱりDP弱すぎる。

コード

#include<stdio.h>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<utility>
#include<memory>
#include<cmath>
#include<stack>
#include<tuple>
#include<numeric>
#include<cassert>

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define pb push_back
#define DEBUG false

using namespace std;

using ll = long long;
using P = pair<int,int>;
using Pl = pair<int,ll>;
using Pd = pair<double,double>;
using T = tuple<double,double,int>;

const int mod=1e9+7,INF=1<<30;
const double EPS=1e-12,PI=3.1415926535897932384626;
const ll LINF=1LL<<60;
const int MAX_N = 5003, MAX_C = 30;
const ll lmod = 1e9+7;

int N; ll X;
ll t[MAX_N],dp[MAX_N][MAX_N];
int ind[MAX_N];

int main(){
    cin >> N >> X ;
    rep(i,N) scanf("%lld",t+i);
    rep(i,N){
        // ind[i] := iからスタミナがXを超えない最大のjを選ぶ
        ind[i] = int(upper_bound(t,t+N,t[i]+X)-t)-1;
    }
    t[N] = 0;
    fill(dp[0],dp[0]+N,X);
    rep(i,N){
        ll _max = 0;
        rep(j,N){
            _max = max(_max,dp[i][j]);
            dp[i+1][ind[j]] = max(dp[i+1][ind[j]],dp[i][j]+min(X,t[ind[j]]-t[j]));
            dp[i+1][ind[j]+1] = max(dp[i+1][ind[j]+1],dp[i][j]+min(X,t[ind[j]+1]-t[j]));
        }
        printf("%lld\n",_max);
    }
  return 0;
}