2017-04-09

Google code jam 2017 Qualification D. Fashion Show

14:48 |

NxN grid の各 cell に . + x o が置いてある。. を + or x or o に、+ or x を o に書き換えることができる。
スコアを . は 0, +, x は 1, o は 2 とする。合計スコアの最大値とそのときの配置を出力せよ。
縦横の並びそれぞれについて +xo が 2 つあるときは1つは必ず + でないといけない
斜めの並びそれぞれについて +xo が 2 つあるときは1つは必ず x でないといけない
1≦N≦100

全然わからんので実験, 適当なgreedyのやつでsmallをやってみる→手かがりなし :(

(しばらくして)

しかたないので線形計画問題に落とし込む。各cellに .+xo に対応する4つの変数 d p t o を割り当てて
1cell にはどれかしか置けない ... d+p+t+o≦1
もともと + が置いてあったら + or o しか置けない ... -p-o≦-1
もともと x が置いてあったら x or o しか置けない ... -t-o≦-1
もともと o が置いてあったら o しか置けない ... -o≦-1
縦横それぞれ, x or o は 1 個までしか置けない ... 縦横それぞれ, 集合に入る変数について t+o≦1
斜めの線(／＼)それぞれ, + or o は 1 個までしか置けない ... 斜めの線それぞれ, 集合に入る変数について p+o≦1
という条件のもと、Σ0d+1p+1t+2oを最大化する
以上を行列にして simplex 法で解いて解の復元
N=20 くらいまでならさくさく求まる, N=30 (3600変数, 1078制約式) はだめ
まったく解けないよりはましだが、う〜む
🤔

// simplex 法バージョン
// 新たな盤面を計算する部分だけ抜粋
vector<string> solve(const vector<string>& w) {
	int N = w.size();
	int pre = 0;
	REP(y, N) REP(x, N) if(w[y][x]!='.') pre++;

	int vars = 4*N*N;
	int cs = N*N + pre + 2*N + 2*(2*N-1);
	Mat m(cs, Vec(vars));
	Vec b(cs);
	Vec c(vars);
	int base = 0;
	{
		// .+xo
		int score[4] = {0, 1, 1, 2};
		REP(i, N*N) {
			REP(j, 4) m[base][4*i+j] = 1;
			b[base] = 1;
			REP(j, 4) c[4*base+j] = score[j];
			base++;
		}
	}
	// pre
	{
		REP(y, N) REP(x, N) {
			int idx = y*N+x;
			if(w[y][x]=='+') {
				// must be + or o
				m[base][idx*4+1] = -1;
				m[base][idx*4+3] = -1;
				b[base] = -1;
				base++;
			}
			if(w[y][x]=='x') {
				// must be x or o
				m[base][idx*4+2] = -1;
				m[base][idx*4+3] = -1;
				b[base] = -1;
				base++;
			}
			if(w[y][x]=='o') {
				// must be o
				m[base][idx*4+3] = -1;
				b[base] = -1;
				base++;
			}
		}
	}
	// たて Σxo <= 1
	{
		REP(x, N) {
			REP(y, N) {
				int idx = y*N+x;
				m[base][idx*4+2] = 1;
				m[base][idx*4+3] = 1;
			}
			b[base] = 1;
			base++;
		}
	}
	// よこ Σxo <= 1
	{
		REP(y, N) {
			REP(x, N) {
				int idx = y*N+x;
				m[base][idx*4+2] = 1;
				m[base][idx*4+3] = 1;
			}
			b[base] = 1;
			base++;
		}
	}
	// ななめ Σ+o <= 1
	{
		REP(k, 2*N-1) {
			REP(y, N) {
				REP(x, N) {
					if(x+y==k) {
						int idx = y*N+x;
						m[base][idx*4+1] = 1;
						m[base][idx*4+3] = 1;
					}
				}
			}
			b[base] = 1;
			base++;

			REP(y, N) {
				REP(x, N) {
					if((N-1-x)+y==k) {
						int idx = y*N+x;
						m[base][idx*4+1] = 1;
						m[base][idx*4+3] = 1;
					}
				}
			}
			b[base] = 1;
			base++;
		}
	}
	auto p = simplex(m, b, c);
	auto vs = p.second;
	auto rv = w;
	REP(y, N) REP(x, N) {
		rv[y][x] = '.';
		ll sum = 0;
		REP(i, 4) sum += (ll)vs[(y*N+x)*4+i];
		assert(sum==1);
		if(vs[(y*N+x)*4+0]) rv[y][x] = '.';
		if(vs[(y*N+x)*4+1]) rv[y][x] = '+';
		if(vs[(y*N+x)*4+2]) rv[y][x] = 'x';
		if(vs[(y*N+x)*4+3]) rv[y][x] = 'o';
	}
	return rv;
}

(あとで)

o は + と x が両方置いてあることにすると +, x それぞれ独立に最適に置いた時の解と一致して辻褄が合う、らしい
ほ〜〜〜〜〜
思いつく人すごーい

x は縦と横の依存関係がきれいなのでgreedyで (正確に説明できなくてもやもやする)
+ は＼と／を2部グラフにして最大マッチングさせる
書いたことないのでハマる。

+ も greedy でいける模様。
https://code.google.com/codejam/contest/3264486/dashboard#s=a&a=3

Accepted in practice

// 新たな盤面を計算する部分だけ抜粋
vector<string> solve2(const vector<string>& w) {
	int N = w.size();
	vector<string> xs(N, string(N, '.'));
	vector<string> ps(N, string(N, '.'));
	vector<string> rv(N, string(N, '.'));

	// put x
	{
		REP(y, N) REP(x, N) if(w[y][x]=='x' || w[y][x]=='o') xs[y][x] = 'x';
		vector<bool> Ys(N), Xs(N);
		REP(y, N) REP(x, N) if(xs[y][x]=='x') Ys[y]=Xs[x]=true;
		while(1) {
			REP(y, N) REP(x, N) if(xs[y][x]=='.' && !Xs[x] && !Ys[y]) {
				xs[y][x] = 'x';
				Ys[y]=Xs[x]=true;
			}
			if(count(ALL(Xs), true)==N && count(ALL(Xs), true)==N) break;
		}
	}
	// put +
	{
		REP(y, N) REP(x, N) if(w[y][x]=='+' || w[y][x]=='o') ps[y][x] = '+';
		bipartite_matching bm((2*N-1)*2);
		VVI edges(2*N-1, VI(2*N-1));
		vector<bool> usedD0(2*N-1), usedD1(2*N-1);
		REP(y, N) REP(x, N) if(ps[y][x]=='+') {
			int d0 = x+y;
			int d1 = N-1-x+y;
			usedD0[d0] = 1;
			usedD1[d1] = 1;
		}
		REP(y, N) REP(x, N) {
			int d0 = x+y;
			int d1 = N-1-x+y;
			if(!usedD0[d0] && !usedD1[d1]) {
				edges[d0][d1] = 1;
			}
		}
		REP(d0, 2*N-1) REP(d1, 2*N-1) {
			if(edges[d0][d1]) bm.add_edge(d0, 2*N-1+d1);
		}
		int matched=bm.run();
		REP(i, 2*N-1) if(bm.match[i]!=-1) {
			// x+y
			int d0 = i;
			// (N-1-x)+y
			int d1 = bm.match[i]-(2*N-1);
			// d0+d1 = N-1+2y
			int y = (d0+d1-N+1)/2;
			int x = d0-y;
			ps[y][x] = '+';
		}
	}
	REP(y, N) REP(x, N) {
		rv[y][x] = xs[y][x];
		if(ps[y][x]=='+') rv[y][x] = rv[y][x]=='x' ? 'o' : '+';
	}
	return rv;
}

kojingharangの日記

2017-04-09

Google code jam 2017 Qualification D. Fashion Show