Codeforces Round #349 (Div. 1)

いつもと同じ死に方。成長が見られない。相変わらず注意力が灰底辺。

A	B	C	D	E	Place
00:48 (+1)	00:35 (+4)	01:59 (+1)	-	-	59th

A:
メモ化再帰するだけ。メモ化し忘れて1TLE。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stdlib.h>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
char in[11000];
int dp[11000][3];
set<string>S;
char tmp[4];
int n;
int solve(int a,int b){
	if(~dp[a][b])return dp[a][b];
	if(a==n)return dp[a][b]=1;
	int t=0;
	if(a<=n-2){
		if(b!=0||in[a]!=in[a-2]||in[a+1]!=in[a-1]){
			int res=solve(a+2,0);
			if(res){
				t=res;
				tmp[2]=0;tmp[0]=in[a];tmp[1]=in[a+1];string tt=tmp;S.insert(tt);
			}
		}	
	}
	if(a<=n-3){
		if(b!=1||in[a]!=in[a-3]||in[a+1]!=in[a-2]||in[a+2]!=in[a-1]){
			int res=solve(a+3,1);
			if(res){
				t=res;
				tmp[3]=0;tmp[0]=in[a];tmp[1]=in[a+1];tmp[2]=in[a+2];string tt=tmp;S.insert(tt);
			}
		}	
	}
	return dp[a][b]=t;
}
int main(){
	scanf("%s",in);
	n=strlen(in);
	for(int i=0;i<11000;i++)for(int j=0;j<3;j++)
		dp[i][j]=-1;
	for(int i=5;i<=n;i++){
		solve(i,2);
	}
	printf("%d\n",(int)(S.size()));
	for(set<string>::iterator it=S.begin();it!=S.end();it++)printf("%s\n",(*it).c_str());
}

B:
なにも変な要素がないのにひたすらWA。頭が悪すぎる。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stdlib.h>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
vector<int>g[3100];
int dist[3100][3100];
int L[3100][3];
int R[3100][3];
int main(){
	int a,b;scanf("%d%d",&a,&b);
	for(int i=0;i<b;i++){
		int p,q;scanf("%d%d",&p,&q);p--;q--;
		g[p].push_back(q);
	}
	for(int i=0;i<a;i++){
		for(int j=0;j<a;j++)dist[i][j]=-1;
		queue<int>Q;
		Q.push(i);
		dist[i][i]=0;
		while(Q.size()){
			int at=Q.front();Q.pop();
			for(int j=0;j<g[at].size();j++){
				int to=g[at][j];
				if(dist[i][to]==-1){
					dist[i][to]=dist[i][at]+1;
					Q.push(to);
				}
			}
		}
	}
	for(int i=0;i<a;i++){
		L[i][0]=L[i][1]=L[i][2]=-1;
		for(int j=0;j<a;j++){
			if(i==j)continue;
			if(dist[j][i]==-1)continue;
			if(L[i][0]==-1||dist[j][i]>dist[L[i][0]][i]){
				L[i][2]=L[i][1];
				L[i][1]=L[i][0];
				L[i][0]=j;
			}else if(L[i][1]==-1||dist[j][i]>dist[L[i][1]][i]){
				L[i][2]=L[i][1];
				L[i][1]=j;
			}else if(L[i][2]==-1||dist[j][i]>dist[L[i][2]][i]){
				L[i][2]=j;
			}
		}
	}
	for(int i=0;i<a;i++){
		R[i][0]=R[i][1]=R[i][2]=-1;
		for(int j=0;j<a;j++){
			if(i==j)continue;
			if(dist[i][j]==-1)continue;
			if(R[i][0]==-1||dist[i][j]>dist[i][R[i][0]]){
				R[i][2]=R[i][1];
				R[i][1]=R[i][0];
				R[i][0]=j;
			}else if(R[i][1]==-1||dist[i][j]>dist[i][R[i][1]]){
				R[i][2]=R[i][1];
				R[i][1]=j;
			}else if(R[i][2]==-1||dist[i][j]>dist[i][R[i][2]]){
				R[i][2]=j;
			}
		}
	}
	int A,B,C,D;
	int bs=0;
	for(int i=0;i<a;i++){
		for(int j=0;j<a;j++){
			for(int k=0;k<3;k++)for(int l=0;l<3;l++){
				if(L[i][k]==-1||R[j][l]==-1||dist[i][j]==-1)continue;
				if(i==j||i==R[j][l]||j==L[i][k]||L[i][k]==R[j][l])continue;
				if(bs<dist[L[i][k]][i]+dist[i][j]+dist[j][R[j][l]]){
					bs=dist[L[i][k]][i]+dist[i][j]+dist[j][R[j][l]];
					A=L[i][k];B=i;C=j;D=R[j][l];
				}
			}
		}
	}
	set<int>S;
	S.insert(A);
	S.insert(B);
	S.insert(C);
	S.insert(D);
	if(S.size()!=4){
		while(1);
	}
	printf("%d %d %d %d\n",A+1,B+1,C+1,D+1);
}

C:
nCkテーブルをsqrt(N)段ごとに作っておいて一行ずつ下がるやつに係数をつけただけ。一箇所-1し忘れ。

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stdlib.h>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
char in[110000];
int n;
int sz=0;
pair<pair<int,int>,int>p[110000];
int ans[110000];
int SQ=300;
long long fact[110000];
long long inv[110000];
long long finv[110000];
long long C(int a,int b){
	return fact[a]*finv[b]%mod*finv[a-b]%mod;
}
long long val[110000];
long long sum[110000];
long long p26[110000];
long long p25[110000];
int main(){
	fact[0]=finv[0]=1;
	p26[0]=1;
	p25[0]=1;
	inv[1]=1;
	for(int i=2;i<110000;i++)inv[i]=(mod-(mod/i)*inv[mod%i]%mod)%mod;
	for(int i=1;i<110000;i++){
		fact[i]=fact[i-1]*i%mod;
		finv[i]=finv[i-1]*inv[i]%mod;
		p26[i]=p26[i-1]*26%mod;
		p25[i]=p25[i-1]*25%mod;
	}
	int a;scanf("%d",&a);
	scanf("%s",in);
	n=strlen(in);
	while(a--){
		int t;scanf("%d",&t);
		if(t==1){
			scanf("%s",in);
			n=strlen(in);
		}else{
			int b;scanf("%d",&b);
			p[sz]=make_pair(make_pair(b,n),sz);
			sz++;
		}
	}
	std::sort(p,p+sz);
	int at=0;
	for(int i=0;i<340;i++){
		long long ks=1;
		for(int j=i*SQ;j>=0;j--){
			val[j]=C(i*SQ,j)*ks;
			ks=ks*25%mod;
		}
		for(int j=0;j<=i*SQ;j++){
			sum[j]=val[j];
			if(j)sum[j]=(sum[j]+sum[j-1])%mod;
		}
		while(at<sz&&p[at].first.first<(i+1)*SQ){

			if(p[at].first.first<p[at].first.second){
				at++;continue;
			}
			long long now=sum[min(i*SQ,p[at].first.second-1)];

			int r=min(i*SQ,p[at].first.second-1);
			for(int j=0;j<p[at].first.first%SQ;j++){
				if(r==p[at].first.second-1){
					now=now*26%mod;
					now=(now+mod-C(i*SQ+j,r)*p25[i*SQ+j-r]%mod)%mod;
				}else{
					now=now*26%mod;
					r++;
				}
			}

			ans[p[at].second]=(p26[p[at].first.first]+mod-now)%mod;
			at++;
		}
	}
	for(int i=0;i<sz;i++)printf("%d\n",ans[i]);
}