KUPC 2011 D: 列の構成

その他のコンテスト

問題概要

長さN(<10^3)のビット列を出力する問題。制限は、ある長さN/2の部分和がN/8~3*N/8となること。その制約はK(

考えたこと

  • いきなり難しくなった。
  • でもDだし実は簡単なんじゃないの？重なってる部分の多い所から、とかで案外行けるのかなあ？
  • うーん、反例が頑張ったら作れそうな気がする。
  • 総和がN/2になるようなビットだと、部分和の期待値は4/Nだから案外上手く行くはずなんだよね。
  • ランダムで結構行けるんじゃないか？Writerから想像するにその可能性も案外あるんではないか？
  • Nが大きい所では大数の法則が効くし、小さい所では試行回数が増やせるから案外行けるきがする。
  • 一回の試行にO(N*K)かかる方法で書いてみる。送信したら余裕で通った。

本番で通ったコード

#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX_N = 1008;
int N, LB, UB, K;

int ans[MAX_N];
int cards[MAX_N/2][MAX_N];

//なってる？
bool check(){
	for(int i=0; i<K; i++){
		int cnt = 0;
		for(int j=0; j<N/2; j++){
			cnt += ans[cards[i][j]];
		}
		if(cnt < LB || UB < cnt){
			return false;
		}
	}
	return true;
}

//ランダム
void solve(){

	for(int i=0; i<N/2; i++){
		ans[i] = 1;
	}

	for(;;){
		random_shuffle(ans, ans+N);
		if(check()) break;
	}
}

int main(){

	scanf("%d%d",&N,&K);
	LB = N/8;
	UB = 3*LB;

	for(int i=0; i<K; i++){
		for(int j=0; j<N/2; j++){
			scanf("%d", cards[i]+j);
			cards[i][j]--;
		}
	}

	solve();

	for(int i=0; i<N; i++){
		printf("%d", ans[i]);
	}
	puts("");

	return 0;
}

反省

一応大数の法則が効くだろうという大雑把な見積りはあったけど、こういうのはちゃんと期待計算量みたいなのを見積もれたほうが好ましい。テストケースが複数あるので、「一つのテストケースに対しては確率95%で正解します」とかだと全然足りないし。