tozangezan's diary

勝手にソースコードをコピペして利用しないでください。

AOJ 2507,2503,2502,2410,2277

これだからオンラインジャッジは…(解けるまでずっとデバッグしていたら90分が経過していた)

2507
dp[row][col][真ん中の一番最後につかったもの]でDP。遷移は9つ。

#include<stdio.h>
int dp[102][102][3];
int main(){
	int mod=1000000;
	int a,b;
	scanf("%d%d",&a,&b);
	if(b==1){
		int ret=1;
		for(int i=0;i<a;i++)ret=ret*2%mod;
		printf("%d\n",ret);
		return 0;
	}
	dp[1][0][0]=1;
	a++;
	for(int i=1;i<=a;i++){
		for(int j=0;j<=i;j++){
			for(int k=0;k<3;k++){
			//	printf("%d %d %d: %d\n",i,j,k,dp[i][j][k]);
				for(int l=0;l<3;l++){
					if(l-k==2||k-l==2){
						dp[i+1][i][l]=(dp[i+1][i][l]+dp[i][j][k]*(i-j))%mod;
					}
					else if(l==1){
						dp[i+1][i+1][l]=(dp[i+1][i+1][l]+dp[i][j][k])%mod;
					}
					else if(l==k){
						dp[i+1][j][k]=(dp[i+1][j][k]+dp[i][j][k])%mod;
					}else{
						dp[i+1][i][l]=(dp[i+1][i][l]+dp[i][j][k])%mod;
					}
				}
			}
		}
	}
	int ret=0;
	for(int i=0;i<102;i++)ret=(ret+dp[a+1][i][2])%mod;
	printf("%d\n",ret);
}

2503
やるだけ

#include<stdio.h>
#include<algorithm>
using namespace std;
int d[400];
int p[800];
int q[800];
int r[800];
int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	for(int i=0;i<b;i++){
		scanf("%d%d%d",p+i,q+i,r+i);
	}
	for(int i=0;i<a;i++){
		for(int j=0;j<b;j++)
			d[q[j]]=max(d[q[j]],d[p[j]]+r[j]);
	}
	printf("%d\n",d[a-1]);
}

2502
やるだけ

#include<stdio.h>
#include<algorithm>
using namespace std;
int dp[394][394];
int l[393];
int r[393];
int p[393];
int ans[393];
int main(){
	int a;
	scanf("%d",&a);
	for(int i=0;i<a;i++){
		scanf("%d%d%d",l+i,r+i,p+i);
	}
	for(int i=0;i<394;i++)
		for(int j=0;j<394;j++)
			dp[i][j]=-99999999;
	dp[0][0]=0;
	for(int i=1;i<=a;i++){
		for(int j=0;j<394;j++){
			dp[i][j]=max(dp[i][j],dp[i-1][j]);
			for(int k=l[i-1];k<=r[i-1];k++){
				if(j-k>=0){
					dp[i][j]=max(dp[i][j],dp[i-1][j-k]+p[i-1]);
					dp[i][j]=max(dp[i][j],dp[i][j-k]+p[i-1]);
				}
			}
		}
	}
	int b;
	bool ok=true;
	scanf("%d",&b);
	for(int i=0;i<b;i++){
		int c;
		scanf("%d",&c);
		ans[i]=dp[a][c];
		if(ans[i]<0)ok=false;
	}
	if(ok){
		for(int i=0;i<b;i++)printf("%d\n",ans[i]);
	}else printf("-1\n");
	
}

2410
乱択するだけ。

#include<stdio.h>
#include<algorithm>
using namespace std;
char str[10][11];
int main(){
	int a;
	scanf("%d",&a);
	int gomi;
	for(int i=0;i<a;i++)scanf("%s",str[i]);
	int at=-1;
	for(int i=0;i<a;i++){
		bool ok=true;
		for(int j=0;j<a;j++)if(str[i][j]=='x')ok=false;
		if(ok)at=i;
	}
	if(~at){
		for(int i=0;i<1000;i++){
			printf("%d\n",at+1);
			fflush(stdout);
			scanf("%d",&gomi);
		}
	}else{
		for(int i=0;i<1000;i++){
			printf("%d\n",rand()%a+1);
			fflush(stdout);
			scanf("%d",&gomi);
		}
	}
}

2277
疲れた。解法としては、
n<200なら全部試したほうが安全そうなので全部試す。
そうでないときは、n/2個程度乱択で選び(すでに1が確定したところは使わないようにする)、xor合計が1になったらその値の中で二分探索してその1の位置を決める(ダジャレ)

すでに1が確定したところを除きつつ二分探索の位置を決めるのをすっかり忘れていて90分かかりました。デデドン

#include<stdio.h>
#include<algorithm>
using namespace std;
char str[100000];
int ret[10];
int val[10000];
int used[10000];
int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	int at=0;
	if(a<200){
		for(int i=0;i<a;i++){
			for(int j=0;j<a;j++){
				if(i==j)str[j]='1';
				else str[j]='0';
			}
			printf("?%s\n",str);
			fflush(stdout);
			int c;
			scanf("%d",&c);
			if(c)ret[at++]=i+1;
		}
		printf("!");
		for(int i=0;i<b;i++){
			printf("%d",ret[i]);
			if(i<b-1)printf(" ");
			else printf("\n");
		}
		fflush(stdout);
		return 0;
	}
	for(int i=0;i<a;i++)val[i]=i;
	int n=a/2;
	for(int i=0;i<b;i++){
		int d=0;
		do{
			for(int j=0;j<50000;j++){
				int l=rand()%a;
				int r=rand()%a;
				int z=val[l];
				val[l]=val[r];
				val[r]=z;
			}
			for(int j=0;j<a;j++)str[j]='0';
			int ind=0;
			for(int j=0;ind<n;j++){
				if(!used[val[j]]){
					str[val[j]]='1';
					ind++;
				}
			}
			printf("?%s\n",str);
			fflush(stdout);
			scanf("%d",&d);
		}while(!d);
		int left=-1;
		int right=n+1;
		while(left+1<right){
			int M=(left+right)/2;
			for(int j=0;j<a;j++)str[j]='0';
			int ind=0;
			for(int j=0;ind<M;j++){
				if(!used[val[j]]){
					str[val[j]]='1';
					ind++;
				}
			}
			printf("?%s\n",str);
			fflush(stdout);
			scanf("%d",&d);
			if(d)right=M;
			else left=M;
		}
		int V=0;
		int P=0;
		for(int j=0;V<right;j++){
			if(!used[val[j]]){
			//	str[val[j]]='1';
				V++;P=j;
			}
		}
		used[val[P]]=1;
		ret[at++]=val[P]+1;
	}std::sort(ret,ret+b);
	printf("!");
	for(int i=0;i<b;i++){
		printf("%d",ret[i]);
		if(i<b-1)printf(" ");
		else printf("\n");
	}
	fflush(stdout);
}