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

ヘクトのメモ

なんとなくいろいろ書いていくと思います.

JAG 夏合宿 2016 Day4 M

本番で手をつけていない問題の復習をまとめる.

問題文
以下の条件を満たす0と1から構成される n \times nの正方行列を考える.

  • 各行に含まれる1の数は x a \le x \le b
  • 各列に注目したときに1である要素の間に0の要素があってはならない.

このとき,クエリが q個与えられる.

  • 以上の条件を満たす正方行列について辞書順で t_i番目の行列を出力せよ.

制約
 1 \le n \le 10, 1 \le a \le b \le n, 1 \le q \le 1000, 1 \le t_i \le 10^{18}

解法

  • 前計算パート

条件を満たす行列の総数を数える.

DP 各列の状態を 3^nで表す.
0: 1を未使用かつ0 
1: 1を使用中
2: 1を使用済みかつ0

遷移のパターン数 2^nを全て試すと計算量が O(6^n)でTLEするので,
必要な遷移だけに注目すると,計算量が O(5^n)に落とせる.

  • クエリパート

あとはよくある辞書順貪欲で答えを求める.
答えが存在するかどうかは,前計算で配るDPではなく貰うDPでやると O(1)
1クエリあたりの計算量は O(n2^n)


全体の計算量は O(5^n + qn2^n)

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
using namespace std;

using ll=long long;
int n,a,b,q;

int three=1,two=1;

ll dp[12][59049];

using pii=pair<int,int>;
vector<pii> mov[59049];
bool ones[1024];
bool ok[59049];
char bit[1024][11];

inline void prepare(){
	rep(loop,n) three*=3,two*=2;

	rep(cur,three){
		int parm[10],tmp=cur,nxt=0;
		rep(i,n) parm[n-1-i]=tmp%3,tmp/=3; 
		rep(i,n) nxt=3*nxt+(parm[i]?2:0);
		if(nxt==three-1) dp[n][cur]=1LL;
	}

	rep(mask,two){
		rep(i,n){
			if(mask&(1<<(n-1-i)))
				bit[mask][i]='1';
			else
				bit[mask][i]='0';
		}
		bit[mask][n]='\0';	
	}

	rep(mask,two){
		ones[mask]=0;
		int tmp=__builtin_popcount(mask);
		if(tmp<a||b<tmp) continue;
		ones[mask]=1;
	}
			
	rep(cur,three){
		int parm[10],tmp=cur,mask=0;
		rep(i,n) parm[n-1-i]=tmp%3,tmp/=3; 
		rep(i,n) if(parm[i]!=2) mask|=(1<<i);
		
		for(int smask=mask;;smask=(smask-1)&mask){
			if(ones[smask]){
				int nxt=0;
				rep(i,n){
					nxt=3*nxt;
					if(smask&(1<<i))
						nxt+=1;
					else
						nxt+=(parm[i]?2:0);
				}
				mov[cur].push_back(pii(smask,nxt));
			}

			if(smask==0) break;
		}
		reverse(begin(mov[cur]),end(mov[cur]));
	}
}



const ll limit=1LL<<60;

//struct CWW{CWW(){ios::sync_with_stdio(false);cin.tie(0);}}cww;

int main(void){
	scanf("%d %d %d %d",&n,&a,&b,&q);
	prepare();
	
	for(int i=n-1;i>=0;--i)rep(cur,three){
		for(auto &it:mov[cur]){
			int mask=it.first,nxt=it.second;
			dp[i][cur]+=dp[i+1][nxt];
		}
	}
	
	
	rep(loop,q){
		if(loop) puts("");

		ll t;
		scanf("%lld",&t);
		if(t>dp[0][0]){
			puts("No such matrix.");
		}else{
			int cur=0;
			rep(pos,n){
				int seq=-1,tar=-1;
				for(auto &it:mov[cur]){
					int mask=it.first,nxt=it.second;
					ll nt=t-dp[pos+1][nxt];
					seq=mask,tar=nxt;
					if(nt<=0) break;
					t=nt;
				}

				puts(bit[seq]);
				cur=tar;
			}
		}
	}

	return 0;
}