kmjp's blog

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

yukicoder : No.452 横着者のビンゴゲーム

問題の意図を読み間違えて手間取った。
http://yukicoder.me/problems/no/452

問題

N*Nマスのビンゴカードを持った人がM人いる。
ここで異なる数字が書かれた玉をX個同時に引いたとき、どんな引き方をしても同時に複数人がビンゴにならないようにしたい。
条件を満たす最大のXを求めよ。

解法

各人がビンゴとなるのは、N個の玉の組み合わせのうち、縦横斜めの計(2N+2)通りのいずれかを含む場合である。

複数人ビンゴにならないようにしたいので、2人ビンゴになる最小の玉の数を求め、1引けばよい。
2人のビンゴとなる玉の組み合わせを総当たりしよう。
2人同時にビンゴとなるのは、2つの組み合わせをマージ(重複は取り除く)したときのマス目の数字の数以上の玉を引く場合である。
よってそのような数の最小値を求め、最後に1引けばよい。

int N,M;
int C[101][101];
vector<vector<int>> V[202];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		FOR(y,N) FOR(x,N) cin>>C[y][x];
		FOR(y,N) {
			V[i].push_back(vector<int>());
			FOR(x,N) V[i].back().push_back(C[y][x]);
			sort(ALL(V[i].back()));
		}
		FOR(x,N) {
			V[i].push_back(vector<int>());
			FOR(y,N) V[i].back().push_back(C[y][x]);
			sort(ALL(V[i].back()));
		}
		V[i].push_back(vector<int>());
		FOR(y,N) V[i].back().push_back(C[y][y]);
		sort(ALL(V[i].back()));
		V[i].push_back(vector<int>());
		FOR(y,N) V[i].back().push_back(C[y][N-1-y]);
		sort(ALL(V[i].back()));
	}
	int mi=1010;
	FOR(y,M) FOR(x,y) {
		FORR(v1,V[y]) FORR(v2,V[x]) {
			int num=0,i1=0,i2=0;
			while(i1<N || i2<N) {
				if(i1==N) num++, i2++;
				else if(i2==N) num++, i1++;
				else if(v1[i1]==v2[i2]) num++,i1++,i2++;
				else if(v1[i1]<v2[i2]) num++,i1++;
				else num++,i2++;
			}
			mi=min(mi,num-1);
		}
	}
	_P("%d\n",mi);
	
	
}

まとめ

最初「複数人ビンゴが登場しないように、(指定した玉を選べる場合に)最大何個まで玉を引けるか」という問題と勘違いした。
こちらだと最適解はなんなんだろうね。