kmjp's blog

競技プログラミング参加記です

yukicoder : No.689 E869120 and Constructing Array 3

Dの方が簡単だった。
https://yukicoder.me/problems/no/689

問題

整数Kが与えられる。
N要素の整数列A[i]のうち、i<jについてA[i]+A[j]が奇数になるものがK通りになるようなものを構築せよ。

解法

サンプルにヒントがある。
3,4,5,6からなる数列を作ると、3+4と5+6のみ素数となる。
よってAを3,4,5,6から構築することを考えよう。
C[i]をAにおける登場回数とすると、K=C[3]*C[4]+C[5]*C[6]であればよいので、C[3],C[4],C[5]を総当たりし、条件を満たすC[6]を探そう。

int K;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>K;
	for(int a3=0;a3<=200;a3++) {
		for(int a4=0;a4<=200;a4++) {
			if(a3+a4>250) continue;
			int left=K-a3*a4;
			if(left<0 || left>200) continue;
			if(left==0) {
				if(a3+a4<=250) {
					cout<<a3+a4<<endl;
					FOR(i,a3) cout<<3<<" ";
					FOR(i,a4) cout<<4<<" ";
					return;
				}
				continue;
			}
			for(int a5=1;a5<=250-a3-a4;a5++) if(left%a5==0) {
				int a6=left/a5;
				if(a3+a4+a5+a6<=250) {
					cout<<a3+a4+a5+a6<<endl;
					FOR(i,a3) cout<<3<<" ";
					FOR(i,a4) cout<<4<<" ";
					FOR(i,a5) cout<<5<<" ";
					FOR(i,a6) cout<<6<<" ";
					return;
				}
			}
		}
	}
}

まとめ

シンプルで良い問題。