AtCoder ARC #056 : D - サケノミ

考察が出来れば実装は簡単。
http://arc056.contest.atcoder.jp/tasks/arc056_d

問題

N個のドリンクがあり、それぞれのおいしさはW[i]である。
各ドリンクiは、偶数時刻M[i][j]にそれぞれのグラスに注がれる(既にそのドリンクが注がれている場合は、それ以上注がない)。

各基数時刻において、注がれたドリンクをすべて飲むことができる。
その時、注がれたドリンクのおいしさW[i]の総和が満足度に加算される。
最適なタイミングでドリンクを飲むとき、満足度の最大値を求めよ。

解法

部分加算と全体の最大値を取るSegTreeを考える。
時刻tの小さい順に、満足度の最大値DP[t]を求めていこう。
とはいえこのDP[t]はSegTreeを使い時刻DP[1]～DP[t-1]の最大値を求めればよい。

時刻t=M[i][j]に到達すると、直前にドリンクを飲み干した時刻t'が(M[i][j-1]+1)～(M[i][j]-1)であった場合、DP[t]=DP[t']+W[i]となる。
よって、部分加算SegTreeで時刻(M[i][j-1]+1)～(M[i][j]-1)の範囲にW[i]を加算していきながら、上記最大値を求めていく。

過去のDP[t']に加算していくのがちょっとややこしいが、それを除けば実装は軽い。

int N;
int W[505050];
int pre[505050];
vector<int> A[1050500];
ll dp[1010101];

template<class V,int NV> class SegTree_2 {
public:
	vector<V> val;
	vector<V> ma;
	SegTree_2(){val.resize(NV*2,0); ma.resize(NV*2,-1LL<<60);}
	
	void update(int x,int y, V v,int l=0,int r=NV,int k=1) {
		if(l>=r) return;
		if(x<=l && r<=y) {
			val[k]+=v;
			ma[k]+=v;
		}
		else if(l < y && x < r) {
			update(x,y,v,l,(l+r)/2,k*2);
			update(x,y,v,(l+r)/2,r,k*2+1);
			ma[k]=max(ma[k*2],ma[k*2+1])+val[k];
		}
	}
};
SegTree_2<ll,1<<21> st;

void solve() {
	int i,j,k,l,r,x,y; string s;
	scanf("%d",&N);
	FOR(i,N) scanf("%d",&W[i]);
	FOR(i,N) {
		scanf("%d",&x);
		FOR(j,x) scanf("%d",&y), A[y].push_back(i);
	}
	
	dp[1]=0;
	st.update(1,2,(1LL<<60)+dp[1]);
	
	ll ret=0;
	for(i=2;i<=1000500;i++) {
		FORR(r,A[i]) st.update(pre[r],i,W[r]), pre[r]=i;
		dp[i]=st.ma[1];
		st.update(i,i+1,(1LL<<60)+dp[i]);
		ret=max(ret,dp[i]);
	}
	cout<<ret<<endl;
	
}

まとめ

うーん、言われてみると単純なんだけど思いつかないもんだな。