Hatena::Grouptopcoder

kojingharangの日記 RSSフィード

|

2017-04-09

Google code jam 2017 Qualification D. Fashion Show

14:48 |  Google code jam 2017 Qualification D. Fashion Show  - kojingharangの日記 を含むブックマーク はてなブックマーク -  Google code jam 2017 Qualification D. Fashion Show  - kojingharangの日記  Google code jam 2017 Qualification D. Fashion Show  - kojingharangの日記 のブックマークコメント

  • 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部グラフにして最大マッチングさせる
  • 書いたことないのでハマる。
  • 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;
}

2017-04-02

2017 TCO Round1A 1000 PolygonRotation

16:27 |  2017 TCO Round1A 1000 PolygonRotation - kojingharangの日記 を含むブックマーク はてなブックマーク -  2017 TCO Round1A 1000 PolygonRotation - kojingharangの日記  2017 TCO Round1A 1000 PolygonRotation - kojingharangの日記 のブックマークコメント

  • 2次元平面上の凸ポリゴンが整数点座標 x[i], y[i] N 個で与えられる。ポリゴンをy軸中心に回転させたときにできる立体の体積を計算せよ。
  • Y軸上の点は2点与えられる。(0, Ymin), (0, Ymax)
  • 3≦N≦50, -100≦x[i]≦100, -100≦Ymin≦y[i]≦Ymax≦100
  • 同じ場所に2点はない。
  • 時計回り順に与えられる。
  • どの3点も同じ直線上にない。
  • 残り28分くらい
  • んーややこしそうだ
  • 適当なyで切りまくって円錐台の体積の和にするんだろう
  • 2線分の交点の式を検索。
  • まずはy軸に対して左側と右側の線分集合に分ける必要があろう (めんどくさい)
  • おわり

あとで

  • 回転体の断面の d|x|/dy が変化する y 座標群は与えられた y 座標群 ∪ 左側をx=0で反転させた線分集合と右側の線分集合の交点
  • y 座標群を y でソートした上で、それぞれの y 座標に対応する |x| = max(左側のx, 右側のx) を求める
  • y[i], y[i+1] に対応する円錐台の体積の和が答え
  • 落ち着いて冷静にシンプルに書いてみるとできるが本番ではなかなか時間が足りないのう。
  • Accepted in practice
class PolygonRotation {
	public:
	double getVolume(vector <int> x, vector <int> y) {
		int N = x.size();
		int mid;
		REP(i, N) if(x[i]==0) mid=i;
		vector<P> l, r, all;
		REP(i, N) {
			if(i<=mid) {
				r.PB(P{(double)x[i], (double)y[i]});
			}
			if(i>=mid) {
				l.PB(P{(double)-x[i], (double)y[i]});
			}
		}
		l.PB(P{(double)-x[0], (double)y[0]});
		vector<double> ys(ALL(y));
		REP(i, l.size()-1) REP(j, r.size()-1) {
			auto rv = intersection(l[i], l[i+1], r[j], r[j+1]);
			if(rv.first) {
				ys.PB(rv.second.y);
			}
		}
		sort(ALL(ys));
		vector<double> xs(ys.size());
		REP(i, ys.size()) {
			// find max x for ys[i]
			double y = ys[i];
			for(auto& e : {l, r}) {
				REP(j, e.size()-1) {
					double ra = (y - e[j].y) / (e[j+1].y-e[j].y);
					if(0 <= ra && ra <= 1) {
						xs[i] = max(xs[i], e[j].x + ra * (e[j+1].x-e[j].x));
					}
				}
			}
		}
		double ans = 0;
		REP(i, ys.size()-1) {
			double h = ys[i+1]-ys[i];
			double r1 = xs[i];
			double r2 = xs[i+1];
			ans += M_PI*h/3.0*(r1*r1+r1*r2+r2*r2);
		}
		return ans;
	}
};

2017-02-12

SRM 708 Div1 500 PalindromicSubseq

13:01 |  SRM 708 Div1 500 PalindromicSubseq - kojingharangの日記 を含むブックマーク はてなブックマーク -  SRM 708 Div1 500 PalindromicSubseq - kojingharangの日記  SRM 708 Div1 500 PalindromicSubseq - kojingharangの日記 のブックマークコメント

  • 久しぶりの参加。
  • 長さ 1≦N≦3000 の文字列 s が与えられる。
  • X[i] = "s[i] を含む s の部分列のうちそれが回文になるものの個数 mod 10^9+7" とする
  • i in [0, N) に対して (i+1)*X[i] の XOR を求めよ。
  • ひょ〜
  • サンプルを見て初めて問題の意味が分かる
  • SRM 中に出たアイデアや考察
    • 回文ということは中央に軸があるので軸の位置を全部試す感じでいけないか?
    • 軸の左右にどちらもある文字しか使われない
    • L, R より外で回文のとき、内側は何通り?
  • さっぱり
  • おわり
  • あとで
  • 上位陣のをいくつか見る
  • s[i] を必ず採用する時、部分列が回文になるなら s[i] の反対側に対応する同じ文字があるはずである。(s[i] が中央なら s[i] 自身)
  • なるほど

  • s[i] が決まればそれに対応する文字の位置は N 種類
  • s[i], 対応する文字を左から L, R とすると ? ? ? L * * * R ? ? ? という形で表せる
  • 内側(*)だけで回文になる部分列の個数と外側(?)だけで回文になる部分列の個数を N^2 DP で求めておけば
  • L, R が決まったときの組み合わせ総数は 内側回文個数 * 外側回文個数 O(1) で求まる
  • X[i] を計算するときは L, R の組み合わせは N 通りなので X[i] は O(N) で求まる
  • 全体 O(N^2)
  • 内側 : dp1[i][j] ... [i, j] 内の部分列かつ回文の個数
  • 外側 : dp2[i][j] ... [0, i), (j, N) 内の部分列かつ回文の個数
  • として書いてみたが内外共に半開区間の方がいろいろすっきりするのかもしれない。
  • DP2つとそれを組み合わせる処理を正確に書かないといけないので難しい.....
  • Accepted in practice
class PalindromicSubseq {
	public:
	int solve(string s) {
		ll N = s.size();
		// dp1[i][j] ... [i, j] 内での回文の個数
		vector<vector<modll>> dp1(N, vector<modll>(N));
		// dp2[i][j] ... [0, i), (j, N) 内での回文の個数
		vector<vector<modll>> dp2(N, vector<modll>(N));
		RANGE(L, 0, N+1) REP(i, N-L+1) {
			int j = i+L-1;
			if(L==0) {
				if(0<=j && i<N) dp1[i][j] = 1; // empty
			} else {
				modll v = 0;
				// s[i] を採用しない場合 (s[j]は採用するしないどちらも含む)
				if(i+1<N) v += dp1[i+1][j];
				// s[j] を採用しない場合 (s[i]は採用するしないどちらも含む)
				if(0<=j-1) v += dp1[i][j-1];
				// s[i], s[j] 両方採用しない場合が 2 回数えられている分を減らす
				if(0<=j-1 && i+1<N) v -= dp1[i+1][j-1];
				if(s[i]==s[j]) {
					// s[i], s[j] を採用できる。採用するとその内側の組み合わせ総数だけ増える
					if(0<=j-1 && i+1<N) v += dp1[i+1][j-1];
				}
				dp1[i][j] = v;
			}
		}
		for(int L=N;L>=1;L--) REP(i, N-L+1) {
			int j = i+L-1;
			if(L==N) {
				dp2[i][j] = 1; // empty
			} else {
				modll v = 0;
				// 同様
				if(0<=i-1) v += dp2[i-1][j];
				if(j+1<N) v += dp2[i][j+1];
				if(0<=i-1 && j+1<N) {
					v -= dp2[i-1][j+1];
					if(s[i-1]==s[j+1]) {
						// s[i-1], s[j+1] を採用できる。採用するとその外側の組み合わせ総数だけ増える
						v += dp2[i-1][j+1];
					}
				}
				dp2[i][j] = v;
			}
		}
		ll ans = 0;
		REP(i, N) {
			modll X = 0;
			REP(j, N) {
				if(s[i]==s[j]) {
					ll I=i, J=j;
					if(I>J) swap(I, J);
					// ここでは I, J がどちらも採用され I, J が回文にて対応関係にある。
					// 内側は [I+1, J-1] 内の回文の個数
					// 外側は [0, I), (J, N) 内の回文の個数
					// これらの積が "I, J がどちらも採用され回文にて I, J が対応関係にある" 場合の組み合わせ総数。
					X += (I+1<=J-1 ? dp1[I+1][J-1] : modll(1)) * dp2[I][J];
				}
			}
			ans ^= modll(i+1LL)*X;
		}
		return ans;
	}
};

2015-10-14

SRM 671 Div1 300 BearCries

03:16 |  SRM 671 Div1 300 BearCries - kojingharangの日記 を含むブックマーク はてなブックマーク -  SRM 671 Div1 300 BearCries - kojingharangの日記  SRM 671 Div1 300 BearCries - kojingharangの日記 のブックマークコメント

  • なんか久しぶりの参加な気がする。
  • ;__; な顔文字(_は1コ以上)が、1コの顔文字内では順番が保持されたまま何セットか混ざった200文字以内の文字列が与えられる。valid な顔文字に分割する方法は何通りあるか? (mod 10^9+7で)
  • 考察考察
  • ;の個数は偶数じゃないとだめ
  • 両端は;じゃないとだめ
  • 各 _ の両端に来る ; という観点ではどうか? -> 単純な掛け算にならなさそう
  • 最大200文字→3でわって最大66コの顔文字しかない
  • ; までできてる ;_までできてる ;_;までできてる数を別々な状態として持つDPは?
  • -> 新規に _ が現れた場合、今までの ; が ;_ になったのか ;_ が ;_ になったのか一意にきまらない (※後で→元状態から複数の状態に遷移できるので一意に決まらなくてもいいし)
  • わからんし全探索を書く
  • 最初の文字は; である。対応する右の;を決め、その間の _ から全 bit 組み合わせで全通り取る。ただし 1 コ以上。
  • 採用した顔文字を消した後の文字列を再帰的に count で計算する。
  • これは動いた。...が、そこから発展がない...
  • いろんなパティーンの解を印字してぢっと眺むる。
  • おわり
  • あとで
  • Tourist の見ると3次元DP。だが添字の意味が分からず。ほぉ〜??
  • [i][;][;_] なる TL が。
  • ; が来たら新規 ; を作るか ;_ に ; を足して1コ完成させるかすることができる。(; に ; は足せない)
  • _ が来たら ; を ;_+ にするか ;_+ を ;_+ にすることができる。(新規 _ は作れない)
  • で最終的に途中の顔文字がない状態 [N][0][0] が答え
  • 分かってしまえば分かるがどうして分からなかったか分からない
  • どんな指標で状態を同一視するか、状態ごとにどんな演算をするか(これとこれを足しちゃっていいのか??とか)、MECEになってるか、あたりの思考がクリアにできてない感じがする。
  • 今回だと、その指標だと状態から状態への演算がうまくいかん →実はうまくいく みたいな
  • 具体的には ; が来た時 新規 ; と ;_+ → ;_; を別々に加算しちゃってるけど何かこう二重にカウントしちゃってる気がする→だめだ あたり。
  • Accepted in practice
// [i][j][k] ... M[I], I in [0, i] の範囲で, ;で終わってる顔文字が j コ, ;_+ な顔文字が k コあるような状態の個数
modll dp[202][202][202];
class BearCries {
	public:
	int count(string M) {
		CLEAR(dp, 0);
		int N=M.size();
		dp[0][0][0]=1;
		REP(i, N) REP(j, N) REP(k, N) {
			auto cur = dp[i][j][k];
			if(M[i]==';') {
				dp[i+1][j+1][k] += cur; // 新規 ;
				if(k-1>=0) dp[i+1][j][k-1] += cur*modll(k); // ;_+ -> ;_+; (k コある)
			} else {
				dp[i+1][j][k] += cur*modll(k); // ;_+ -> ;_+ (k コある)
				if(j-1>=0) dp[i+1][j-1][k+1] += cur*modll(j); // ; -> ;_+ (j コある)
			}
		}
		return dp[N][0][0];
	}
};

2015-06-05

SRM 660 Div1 250 Coversta

10:36 |  SRM 660 Div1 250 Coversta - kojingharangの日記 を含むブックマーク はてなブックマーク -  SRM 660 Div1 250 Coversta - kojingharangの日記  SRM 660 Div1 250 Coversta - kojingharangの日記 のブックマークコメント

  • N*M のグリッドがあり、各マスに 0-9 の数字が書いてある。Pos[ ] も与えられ、あるマス p に駅を置くと p+P (P in Pos[ ]) なマスがカバーされる。
  • 異なる場所に2駅置いたとき、2駅がカバーするマスに書いてある数字の合計の最大値を求めよ。
  • 2≦N,M≦100, 1≦K=|Pos[]|≦10, -(N-1)≦Pos.x≦N-1, -(M-1)≦Pos.y≦M-1
  • カバー範囲が重なった時の処理がポイントっぽいぞ
  • naiveにやると置き方全てに対して Pos[] のとこを塗って確かめるので N^2 M^2 K -> 10^9 程度 -> むり
  • カバー範囲の重なり方は最大で K^2 個なことに気づく
  • なので「カバー範囲が重なるように2駅置いた時にカバーするマスのパターン」を最大10*10個持っておいて、
  • (1)カバー範囲が重なる2点を置いたときの最大値(N^2 M^2 K)と
  • (2)カバー範囲が重ならない2点を置いたときの最大値(事前にマス→カバー範囲の合計値をNMKで計算しておき重複かどうかをmapで覚えておくとN^2M^2logK)
  • の最大値が答え
  • (1)では、重なり方すべてK^2について最初の点から見た2点目の相対座標と最大K*2点(最初のカバー範囲∪ちょっとずらした範囲)のパターンを覚えておく
  • (2)では2点目の相対座標が(1)で計算した相対座標セットに含まれない=2点のカバー範囲が重ならない、という感じでチェックすればいい。
  • ていうことで N^2M^2logK なので良さそうではあるが、...
  • これで250か, 書いてピッタリ答えが合うとは思えない...
  • IN_RANGE(Value, Min, Max) マクロ大活躍の巻き
  • なぜかサンプルが合った → 3x3 で10ケースくらい手動テストしてOKそうなので 95pt くらいで提出
  • Accepted
  • おー通るのかよ
  • (あとで)K^2+α個で打ち切る NMK^2 解もあるのか。(そっちはなぜそれでいいか腑に落ちてない)
struct Pos {
	int x, y;
	bool operator<(const Pos v) const {
		return x*1000+y < v.x*1000+v.y;
	}
	bool operator==(const Pos v) const {
		return x==v.x && y==v.y;
	}
};
std::ostream& operator<<(std::ostream& os, const Pos& v) {
	os << "("<<v.x<<", "<<v.y<<") ";
	return os;
}

struct Pat {
	Pos ref;
	vector<Pos> pos;
};

class Coversta {
	public:
	int place(vector <string> a, vector <int> X, vector <int> Y) {
		int W=a.size(), H=a[0].size();
		int N=X.size();
		VVI one(W, VI(H));
		vector<Pat> pat;
		map<PII, int> ng;
		REP(x, W) REP(y, H) REP(i, N) {
			if(IN_RANGE(x+X[i], 0, W) && IN_RANGE(y+Y[i], 0, H)) {
				one[x][y]+=a[x+X[i]][y+Y[i]]-'0';
			}
		}
		REP(i, N) REP(j, N) if(i!=j) {
			// i-j
			int dx = X[i]-X[j];
			int dy = Y[i]-Y[j];
			auto key = MP(dx, dy);
			if(ng.count(key)) continue;
			if(dx==0 && dy==0) continue;
			ng[key] = 1;
			vector<Pos> v;
			REP(k, N) v.PB(Pos{X[k], Y[k]});
			REP(k, N) v.PB(Pos{X[k]+dx, Y[k]+dy});
			sort(ALL(v));
			v.erase(unique(ALL(v)), v.end());
			pat.PB({Pos{dx, dy}, v});
		}
		REP(i, pat.size()) {
//			cout<<pat[i].ref<<" -> "<<pat[i].pos<<endl;
//			cout<<pat[i].ref.x<<" "<<pat[i].ref.y<<endl;
		}
		ll ans = 0;
		REP(pi, pat.size()) {
			auto& p = pat[pi];
			REP(x0, W) REP(y0, H) {
				int xx = x0+p.ref.x;
				int yy = y0+p.ref.y;
				if(IN_RANGE(xx, 0, W) && IN_RANGE(yy, 0, H)) {
					ll lans = 0;
					REP(i, p.pos.size()) {
						int ex = x0 + p.pos[i].x;
						int ey = y0 + p.pos[i].y;
						if(IN_RANGE(ex, 0, W) && IN_RANGE(ey, 0, H)) {
							lans += a[ex][ey]-'0';
						}
					}
					ans = max(ans, lans);
				}
			}
		}
//		cout<<"one "<<one<<endl;
		REP(x0, W) REP(y0, H) REP(x1, W) REP(y1, H) if(!(x0==x1 && y0==y1)) {
			int dx = x0-x1;
			int dy = y0-y1;
			PII k = MP(dx, dy);
			if(!ng.count(k)) {
//				cout<<x0<<" "<<y0<<" "<<x1<<" "<<y1<<" -> "<<one[x0][y0]+one[x1][y1]<<endl;
				ans = max(ans, one[x0][y0]+one[x1][y1]);
			}
		}
		return ans;
	}
};
|