Typical DP Contest : F - 準急、G - 辞書順

ここまでは何とか自力で解けた問題。
http://tdpc.contest.atcoder.jp/tasks/tdpc_semiexp
http://tdpc.contest.atcoder.jp/tasks/tdpc_lexicographical

F - 準急

N個の駅があり、１番目の駅からN番目の駅に移動する準急を走らせる。
このとき、準急がK個以上連続した駅に止まらないようにしたい。
そのような準急の走らせ方を答えよ。

M個の駅の先頭からM駅目についての走らせ方C[M]を求め、そこから再帰的にC[M+1]駅の場合を求める。
M=Kの場合、まず１番目からi駅連続で停車させ、そこから１駅以上飛んで残りの駅数jに対しC[j]を足すと考えればよいので、を求めればよい。
(M==Kの時は、K-1駅停車することはできないので注意)

和が２重になってる上、C[M]からC[M+1]を求めるので、そのままではO(N^3)の時間がかかる。
よって、C[i]の累積和S[i]およびS[i]の累積和SS[i]を計算しながら処理するとO(N)で済む。

ll K,N;
ll mo=1000000007LL;
ll dpdp[1000007],dpdpt[1000007],dpdpt2[1000007];

void solve() {
	int f,r,i,j,k,l, x,y,z;
	
	cin>>N>>K;
	
	dpdp[0]=0;dpdpt[0]=0;dpdpt2[0]=0;
	dpdp[1]=1;dpdpt[1]=1;dpdpt2[1]=1;
	if(K==2) {
		dpdp[2]=0;dpdpt[2]=0;dpdpt2[2]=0;
	}
	else {
		dpdp[2]=1;dpdpt[2]=1;dpdpt2[2]=2;
	}
	
	for(i=2;i<K-1;i++) dpdp[i+1]=(dpdp[i]*2)%mo;
	FOR(i,K-1) {
		dpdpt[i+1] = (dpdpt[i] + dpdp[i+1]) % mo;
		dpdpt2[i+1] = (dpdpt2[i] + dpdpt[i+1]) % mo;
	}
	
	for(i=K;i<=N;i++) {
		if(i==K) for(y=1;y<K-1;y++) dpdp[i] += dpdpt[i-(y+1)];
		else {
			dpdp[i] += dpdpt2[i-2] - dpdpt2[i-K-1];
		}
		
		dpdp[i] = ((dpdp[i]%mo)+mo)%mo;
		dpdpt[i] = (dpdpt[i-1]+dpdp[i]) % mo;
		dpdpt2[i] = (dpdpt2[i-1] + dpdpt[i]) % mo;
	}
	
	cout << dpdp[N] << endl;
	return;
}

G - 辞書順

文字列Sが与えられたとき、その部分文字列のうち辞書順K番目を求めよ。

Sにおいて、'a'～'z'がそれぞれ最初に登場する位置を求める。
それが見つかった場合、その文字列からなる部分文字列を１つ作れる。
また、その文字を部分文字列の先頭とし、残りの文字に対し同様に再帰的に処理をすることで、部分文字列の数を求めることができる。
その累積がK番目になった時点でその部分文字列を答えるとよい。

ただ、最初再帰処理を書いたら|S|<=10^6だったためスタックオーバーフローした。
そこで文字数カウントをDP、K番目を探す処理を手作業で末尾再帰を展開してスタックオーバーフローを避けた。

int L;
string S;
ll K;
ll sst[1000002];
vector<int> P[27];

ll dodo(int cur,ll A,string SS) {
	int c,l;
ret:
	if(cur>=L) return 0;
	FOR(c,26) {
		l = lower_bound(P[c].begin(),P[c].end(),cur) - P[c].begin();
		if(l<P[c].size()) {
			char cc = c + 'a';
			ll t = 1+sst[P[c][l]+1];
			if(A==1) {
				cout << SS << cc << endl;
				exit(0);
			}
			
			if(t>=A) {
				cur = P[c][l]+1;
				A--;
				SS += cc;
				goto ret;
				//return dodo(P[c][l]+1,A-1,SS + cc);
			}
			A -= t;
		}
	}
}

void solve() {
	int f,r,i,j,k,l, x,y,z;
	
	cin>>S>>K;
	L=S.size();
	FOR(i,L) P[S[i]-'a'].push_back(i);
	
	for(int cur=L-1;cur>=0;cur--) {
		int c,l;
		sst[cur]=0;
		FOR(c,26) {
			l = lower_bound(P[c].begin(),P[c].end(),cur) - P[c].begin();
			if(l<P[c].size()) {
				sst[cur] += 1+sst[P[c][l]+1];
				if(sst[cur]>1LL<<60) {
					sst[cur] = 1LL<<60;
					break;
				}
			}
		}
	}
	dodo(0,K,"");
	
	
	return _P("Eel\n");
}

まとめ

Fはあっさり解けて良かった。
Gも迷ったけどこんなもんか。
ただ、スタックオーバーフローがMLE扱いになるのは知らなかった…。