提出 #486952

---

ソースコード 拡げる

#include<cstdio>
#include<cassert>
using namespace std;
bool dp[1<<16][16][6];
char to[1<<16][16][6];
int nrem[1<<16][16][6];
bool check[1<<16][16][6];
bool can[16][6][16];
char s[16][20];
int n,k;
int fac[4]={1,1,2,6};
void decode(char *res,int pre,int rem){
	bool used[20]={};
	for(int i=0;i<k;i++) res[i]=s[pre][k-1-i],used[res[i]-'A']=true;
	for(int i=n-k-1;i>=0;i--){
		int now=rem/fac[i];
		rem%=fac[i];
		int j;
		for(j=0;j<now;j++){
			if(used[j]) now++;
		}
		while(used[j]) j++;
		res[i+k]='A'+j;
		used[j]=true;
	}
}
int encode(char *remc){
	int sz=n-k,res=0;
	for(int i=sz-1;i>=0;i--){
		int cnt=0;
		for(int j=i-1;j>=0;j--){
			if(remc[j]<remc[i]) cnt++;
		}
		res+=cnt*fac[i];
	}
	return res;
}
void build(){
	char tmp[20];
	for(int a=0;a<n;a++){
		for(int b=0;b<fac[n-k];b++){
			decode(tmp,a,b);
			for(int c=0;c<n;c++){
				int now=0;
				bool flag=true;
				for(int d=0;d<k;d++){
					while(now<n&&tmp[now]!=s[c][d]) now++;
					if(now==n) flag=false;
					else now++;
				}
				can[a][b][c]=flag;
			}
		}
	}
}
bool f(int stat,int pre,int rem){
	if(!stat) return true;
	if(check[stat][pre][rem]) return dp[stat][pre][rem];
	check[stat][pre][rem]=true;
	if(stat==(1<<n)-1){
		for(int i=0;i<n;i++){
			for(int j=0;j<6;j++){
				if(f(stat^(1<<i),i,j)){
					to[stat][pre][rem]='A'+i;
					nrem[stat][pre][rem]=j;
					return dp[stat][pre][rem]=true;
				}
			}
		}
		return dp[stat][pre][rem]=false;
	}
	char tmp[20];
	decode(tmp,pre,rem);
	tmp[n]=0;
	for(int i=0;i<n;i++){
		if((stat&(1<<i))&&can[pre][rem][i]){
			bool used[20]={};
			char remc[3];
			int sz=0;
			for(int j=0;j<k;j++){
				used[s[i][j]-'A']=true;
			}
			for(int j=0;j<n;j++){
				if(!used[tmp[j]-'A']) remc[sz++]=tmp[j];
			}
			if(f(stat^(1<<i),i,encode(remc))){
				to[stat][pre][rem]='A'+i;
				nrem[stat][pre][rem]=encode(remc);
				return dp[stat][pre][rem]=true;
			}
		}
	}
	return dp[stat][pre][rem]=false;
}
int main(){
	scanf("%d%d",&n,&k);
	for(int i=0;i<n;i++){
		scanf("%s",s[i]);
	}
	build();
	assert(f((1<<n)-1,0,0));
	int a=(1<<n)-1,b=0,c=0;
	for(int i=0;i<n;i++){
		putchar(to[a][b][c]);
		int na=a^(1<<to[a][b][c]-'A');
		int nb=to[a][b][c]-'A';
		int nc=nrem[a][b][c];
		a=na,b=nb,c=nc;
	}
	putchar('\n');
	return 0;
}

提出情報

コンパイルエラー

./Main.cpp: In function ‘int main()’:
./Main.cpp:96:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&k);
                     ^
./Main.cpp:98:19: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s",s[i]);
                   ^

ジャッジ結果