Google Code Jam 2018 Round1C : C. Ant Stack

あまり時間のない中回答していたので、エイヤで出して通った。
https://codejam.withgoogle.com/2018/challenges/0000000000007765/dashboard/000000000003e0a8

問題

N要素の数列Wが与えられる。
Wの部分列のうち、W[i]がsum(W[0..(i-1)])*6以下であるような最長の数列の長さを求めよ。

解法

LISと同じアプローチを取ると失敗する。
LISは可能な範囲で最長な部分列をさらに伸ばすようにするが、この問題はsumを抑えるようにするためあえて最長を更新しないような位置にW[i]を配置するのが良い場合もあるためである。
以下では割と適当に最長から上位50要素まで見てW[i]を部分列に当てはめる場合を試している。
50に根拠があるわけではないのであまり良い解法ではない。(なんとなく6^2より少し大きめの値を入れただけ)
ただ解法によると最長でもこの数列の長さは139なので、50も上位を探索すれば十分というのは真面目に計算すれば導けそうだ。

int N;
ll W[1010101];
ll S[1010101];

void solve(int TC) {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N+5) S[i]=1LL<<60;
	S[0]=0;
	int ma=0;
	FOR(i,N) {
		cin>>W[i];
		x=upper_bound(S,S+N+1,W[i]*6+1)-S;
		while(S[x]>W[i]*6) x--;
		for(y=x;y>=max(0,x-50);y--) {
			S[y+1]=min(S[y+1],S[y]+W[i]);
			ma=max(ma,x+1);
		}
	}
	
	_P("Case #%d: %d\n",TC,ma);
}

まとめ

時間がないとはいえこんな雑な解法でいいんかな。