すぬけそだて――トレーニング――

競技プログラミング AtCoder

問題文

D: すぬけそだて――トレーニング―― - COLOCON -Colopl programming contest 2018- | AtCoder

考察

M<=5000なので、o(n^2)くらいまでは行ける。
最終的なスコアには上限がありそう(x+T_(n-1)-t_1くらい)
スタミナの上限があるので、回復しきったら早めに消費した方がよい。
また、スタミナがXに比べて少ないときに、(そのほかのより良い候補がある中で)わざわざスタミナを消費する必要はなさそう。(このよい候補というのはスタミナがXに近い値の時の候補)


ざっと調べたらこんな感じになると思う。

そして、最近よくはまっているところでもあるけれど探索系の問題で、下手に貪欲には知らないことが大事だということを押さえておきたいところ。頭いいひとが証明できない貪欲は間違っているって言ってた。
つまり、探索系の問題は基本的にすべての事象を考慮できることを考えてから、無駄な操作を省くというのがよいうのではないかというのが最近の感覚。
枝刈探索とかDPとかになるかな～？


ということでDPです。
dp[i][j] := i個選ぶことを考えて最後がjの時の最大値
挙げるDPになりそうだけれど、普通に考えると遷移にo(n)かかるので、遷移を限定する必要がある。
その遷移の限定がXの前後二個のみに限定するという話。
それ以前に消費しても二度手間になるし、その後に消費するのはあふれたスタミナがもったいないという話ですね。

ということで今回は事前に各T_iからX時間前後の候補を求めておき遷移をo(1)にするとめでたく全体の計算量がo(n^2)になりましたと。

#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<cstring>
#include<functional>
#include<stack>
#include<queue>
#include <iomanip>
#include<map>
#include<limits>
#include<cmath>
#include<algorithm>
#include<bitset>
#include<utility>
#include<complex>
#include<cstdlib>
#include<set>
#include<cctype>

#define DBG cerr << '!' << endl;
#define REP(i,n) for(int (i) = (0);(i) < (n);++i)
#define rep(i,s,g) for(int (i) = (s);(i) < (g);++i)
#define rrep(i,s,g) for(int (i) = (s);i >= (g);--(i))
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {for(int W = 0;W < (n);W++)cerr << v[W] << ' ';cerr << endl << endl;}
#define SHOW2d(v,i,j) {for(int aaa = 0;aaa < i;aaa++){for(int bbb = 0;bbb < j;bbb++)cerr << v[aaa][bbb] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(10)

using namespace std;

typedef long long ll;
typedef vector<int> iv;
typedef vector<iv> iiv;
typedef vector<string> sv;

ll nxt[5010];
ll nxt1[5010];
ll dp[5010][5010];

int main()
{
	ll n,x;cin >> n >> x;
	vector<ll> v(n);
	
	REP(i,n)
	{
		int tmp;cin >> tmp;
		v[i] = tmp;
	}
	
	REP(i,n)
	{
		vector<ll>::iterator it = lower_bound(ALL(v),v[i]+x);
		if(it == v.end())
		{
			nxt[i] = n-1;nxt1[i] = n-2;
		}
		else
		{
			nxt[i] = it-v.begin();nxt1[i] = nxt[i]-1;
		}
	}
	
//	SHOW1d(nxt,n);
//	SHOW1d(nxt1,n);
	
	REP(i,n)dp[1][i] = x;
	
	for(int i = 1;i <= n;i++)
	{
//		SHOW1d(dp[i],n);
		for(int j = i-1;j < n;j++)
		{
			dp[i][j] = max(dp[i][j],dp[i-1][j]);
			dp[i+1][nxt1[j]] = max(dp[i+1][nxt1[j]],dp[i][j]+min(x,v[nxt1[j]]-v[j]));
			dp[i+1][nxt[j]] = max(dp[i+1][nxt[j]],dp[i][j]+min(x,v[nxt[j]]-v[j]));
		}
	}
	
	REP(i,n)
	{
		ll mx = 0;
		REP(j,n)
		{
			mx = max(mx,dp[i+1][j]);
		}
		cout << mx << endl;
	}
	
	return 0;
}

本番では解けなかったからなあ。
必要な要素はすべて列挙で来ていたので、なかなか残念な感じですね。
segtreeでの計算量軽減とかmongeとか使えないので早めに使えるようになりたいですねえ。