読者です 読者をやめる 読者になる 読者になる

Codeforces Round #223 (Div. 1)

Codeforces

実は参加してました。

D:
数え上げだし解法自明だったので解こうとしたが、変なケースがありはまった。WA*3がつらい。

#include<stdio.h>
#include<algorithm>
using namespace std;
int b[110000];
long long fact[310000];
long long factinv[310000];
long long inv[310000];
pair<int,int> ev[310000];
int main(){
	int a;
	int mod=1000000007;
	fact[0]=1;
	for(int i=1;i<310000;i++)fact[i]=fact[i-1]*i%mod;
	inv[1]=1;
	for(int i=2;i<310000;i++)inv[i]=(mod-(mod/i)*inv[mod%i]%mod);
	factinv[0]=1;
	for(int i=1;i<310000;i++)factinv[i]=factinv[i-1]*inv[i]%mod;
	scanf("%d",&a);
	for(int i=0;i<a;i++){
		scanf("%d",b+i);
	}
	int best=9999999;
	int at=-1;
	for(int i=0;i<a;i++){
		if(b[i]&&best>b[i]){
			at=i;
			best=b[i];
		}
	}
	bool ok=true;
	int now=best;
	for(int i=at;i>=0;i--){
		if(b[i]){
			if(now>b[i]){
				ok=false;
			}
			now=b[i];
		}
	}
	now=best;
	for(int i=at;i<a;i++){
		if(b[i]){
			if(now>b[i]){
				ok=false;
			}
			now=b[i];
		}
	}
	if(!ok){
		printf("0\n");
		return 0;
	}
	int ind=0;
	
	for(int i=0;i<a;i++){
		if(b[i])ev[ind++]=make_pair(b[i],i);
	}
	std::sort(ev,ev+ind);
	//for(int i=0;i<ind;i++)printf("%d %d\n",ev[i].first,ev[i].second);
	int L=0;
	int R=a-1;
	long long ret=1;
	int last=a+1;
	if(ind==1){
		ret=0;
		int l=ev[0].second+1;
		int s=last-ev[0].first;
		int r=s-l;
		if(l>=1&&r>=0){
			ret=(ret+fact[s-1]%mod*factinv[r]%mod*factinv[s-1-r]%mod)%mod;
		}
		if(best!=1){
			r=R-ev[0].second+1;
			s=last-ev[0].first;
			l=s-r;
			if(r>=1&&l>=0){
				ret=(ret+fact[s-1]%mod*factinv[l]%mod*factinv[s-1-l]%mod)%mod;
			}
		}
		printf("%d\n",(int)ret);
		return 0;
	}
	for(int i=ind-1;i>=0;i--){
		if(ev[i].second<at){
			int l=ev[i].second-L+1;
			int s=last-ev[i].first;
			int r=s-l;
			if(l<1||r<0){ret=0;break;}
			ret=ret*fact[s-1]%mod*factinv[r]%mod*factinv[s-1-r]%mod;
			L=ev[i].second+1;
			last=ev[i].first;
			R-=r;
		}else if(ev[i].second>at){
			int r=R-ev[i].second+1;
			int s=last-ev[i].first;
			int l=s-r;
			if(r<1||l<0){ret=0;break;}
			ret=ret*fact[s-1]%mod*factinv[l]%mod*factinv[s-1-l]%mod;
			R=ev[i].second-1;
			last=ev[i].first;
			L+=l;
		}else{
			long long Ret=0;
			int l=ev[0].second-L+1;
			int s=last-ev[0].first;
			int r=s-l;
			long long val=1;
			for(int j=0;j<R-L-s;j++)val=val*2%mod;
			if(l>=1&&r>=0){
				Ret=(Ret+fact[s-1]%mod*factinv[r]%mod*factinv[s-1-r]%mod*val%mod)%mod;
			}
			if(best!=1){
				r=R-ev[0].second+1;
				s=last-ev[0].first;
				l=s-r;
				if(r>=1&&l>=0){
					Ret=(Ret+fact[s-1]%mod*factinv[l]%mod*factinv[s-1-l]%mod*val%mod)%mod;
				}
			}
			ret=ret*Ret%mod;
			R=-1111;
		}
	//	printf("%d %d %d %d\n",i,L,R,(int)ret);
	}
	if(L<=R){
		for(int i=0;i<R-L;i++)ret=ret*2%mod;
	}
	printf("%d\n",(int)ret);
}

C:
よくみるとRMQだけでいけそうな気がしてくる。

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int segtree[3000000];
int sum[3000000];
char str[3000000];
int query(int a,int b,int c,int d,int e){
	if(d<a||b<c)return 999999999;
	if(c<=a&&b<=d)return segtree[e];
	return min(query(a,(a+b)/2,c,d,e*2),query((a+b)/2+1,b,c,d,e*2+1));
}
int main(){
	int a;
	scanf("%s%d",str,&a);
	for(int i=0;i<3000000;i++)segtree[i]=999999999;
	int n=strlen(str);
	for(int i=0;i<n;i++){
		sum[i+1]=sum[i];
		if(str[i]=='(')sum[i+1]++;
		else sum[i+1]--;
		segtree[1048576+i]=sum[i+1];
	}
	for(int i=1048575;i>=1;i--){
		segtree[i]=min(segtree[i*2],segtree[i*2+1]);
	}
	for(int i=0;i<a;i++){
		int b,c;
		scanf("%d%d",&b,&c);b--;c--;
		int m=query(0,1048575,b,c,1);
		m-=sum[b];
		int M=sum[c+1]-sum[b];
		int ret=c-b+1;
		if(m<0){ret+=m;M-=m;}
		if(M>0)ret-=M;
		printf("%d\n",ret);
	}
}

A:
典型的な感じがする。あんまり好きじゃない。

#include<stdio.h>
#include<algorithm>
using namespace std;
int p[110000];
int q[110000];
int x[110000];
int y[110000];
long long t[1100000];
int main(){
	int a;
	scanf("%d",&a);
	int S=0;
	long long now=0;
	for(int i=0;i<a;i++){
		scanf("%d",q+i);
		if(q[i]==1)scanf("%d",x+i);
		else scanf("%d%d",x+i,y+i);
	}
	int b;
	scanf("%d",&b);
	for(int i=0;i<b;i++){scanf("%lld",t+i);t[i]--;}
	int at=0;
	for(int i=0;i<a;i++){
		long long to=now;
		if(q[i]==1)to++;
		else to+=x[i]*y[i];
		while(at<b&&t[at]<to){
			if(q[i]==1)printf("%d ",x[i]);
			else printf("%d ",p[(t[at]-now)%x[i]]);
			at++;
		}
		if(q[i]==1){
			if(S<100000){
				p[S++]=x[i];
			}
			now++;
		}else{
			for(int k=0;k<y[i];k++){
				if(S>=100000)break;
				for(int j=0;j<x[i];j++){
					if(S>=100000)break;
					p[S++]=p[j];
				}
			}
			now+=x[i]*y[i];
		}
	}
}

残り:読む暇なし
全部通る。
Rating: ?