Hatena::Grouptopcoder

nodchipのTopCoder日記 このページをアンテナに追加 RSSフィード

 | 

2011-02-14Bitwise 2011 このエントリーを含むブックマーク このエントリーのブックマークコメント

"sonogensouwobuchikorosu"という一人チームで出場しました。チーム名の由来はお察し下さい。

Problem NoSubmissions ReceivedSubmissions EvaluatedStatus of Last SubmissionTest Files Cleared for Last Submission Score for Last Evaluation
122Time Limit Exceeded0/30/300
266Accepted3/3100/100
300 0/30/300
422Accepted3/3200/200
51111Accepted3/3100/100
644Accepted3/3200/200
755Compile Error0/30/200
811Time Limit Exceeded1/320/200
900 0/30/200
1000 0/30/300

Problem 1 Traffic Safe City

  • さっぱり方針が立たない
  • 適当に書いて出してみよう
    • Wrong Answer
  • じゃあ巡回セールスマンのDPっぽく書いてみようか・・・
    • Time Limit Exceeded
  • 分からないorz

Problem 2 Save Me Please, Doctor!

  • abbabaabbaababba...
  • なんか折り返したりab反転させたりしていくっぽい
  • 入力上限が書いてないのが気になるけど反転させてく感じで書いてみる
    • Wrong Answer +部分点
  • 多分めちゃめちゃでかい整数が与えられるんだろうなぁ
  • 適当な多倍長整数で計算してみる
    • Time Limit Exceeded
  • ・・・
  • 解き方違うのかなぁ?
  • ・・・
  • もしかしてビット演算的な何か?
  • まさか立ってるビットの数の偶奇だったりする?
  • それっぽい
  • 多倍長整数でpopcountをしなきゃいけないのか
  • JavaのBigIntegerでも移植してみようか
    • Accepted
// 立っているビットの数を数える
int countPop(ull x){
	x = (x & 0x5555555555555555ULL) + ((x >> 1) & 0x5555555555555555ULL);
	x = (x & 0x3333333333333333ULL) + ((x >> 2) & 0x3333333333333333ULL);
	x = (x & 0x0f0f0f0f0f0f0f0fULL) + ((x >> 4) & 0x0f0f0f0f0f0f0f0fULL);
	x = (x & 0x00ff00ff00ff00ffULL) + ((x >> 8) & 0x00ff00ff00ff00ffULL);
	x = (x & 0x0000ffff0000ffffULL) + ((x >> 16) & 0x0000ffff0000ffffULL);
	x = (x & 0x00000000ffffffffULL) + ((x >> 32) & 0x00000000ffffffffULL);
	return x;
}

static ll bitsPerDigit[] = { 0, 0,
	1024, 1624, 2048, 2378, 2648, 2875, 3072, 3247, 3402, 3543, 3672,
	3790, 3899, 4001, 4096, 4186, 4271, 4350, 4426, 4498, 4567, 4633,
	4696, 4756, 4814, 4870, 4923, 4975, 5025, 5074, 5120, 5166, 5210,
	5253, 5295};
static int digitsPerInt[] = {0, 0, 30, 19, 15, 13, 11,
	11, 10, 9, 9, 8, 8, 8, 8, 7, 7, 7, 7, 7, 7, 7, 6, 6, 6, 6,
	6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 5};
static int intRadix[] = {0, 0,
	0x40000000, 0x4546b3db, 0x40000000, 0x48c27395, 0x159fd800,
	0x75db9c97, 0x40000000, 0x17179149, 0x3b9aca00, 0xcc6db61,
	0x19a10000, 0x309f1021, 0x57f6c100, 0xa2f1b6f,  0x10000000,
	0x18754571, 0x247dbc80, 0x3547667b, 0x4c4b4000, 0x6b5a6e1d,
	0x6c20a40,  0x8d2d931,  0xb640000,  0xe8d4a51,  0x1269ae40,
	0x17179149, 0x1cb91000, 0x23744899, 0x2b73a840, 0x34e63b41,
	0x40000000, 0x4cfa3cc1, 0x5c13d840, 0x6d91b519, 0x39aa400
};

int parseInt(char* source, int start, int end) {
	int result = source[start++] - '0';

	for (int index = start; index<end; index++) {
		int nextVal = source[index] - '0';
		result = 10*result + nextVal;
	}

	return result;
}

static ll LONG_MASK = 0xffffffffL;
static void destructiveMulAdd(vector<int>& x,  int y, int z) {
	// Perform the multiplication word by word
	ll ylong = y & LONG_MASK;
	ll zlong = z & LONG_MASK;
	int len = x.size();

	ll product = 0;
	ll carry = 0;
	for (int i = len-1; i >= 0; i--) {
		product = ylong * (x[i] & LONG_MASK) + carry;
		x[i] = (int)product;
		carry = ((ull)product) >> 32;
	}

	// Perform the addition
	ll sum = (x[len-1] & LONG_MASK) + zlong;
	x[len-1] = (int)sum;
	carry = ((ull)sum) >> 32;
	for (int i = len-2; i >= 0; i--) {
		sum = (x[i] & LONG_MASK) + carry;
		x[i] = (int)sum;
		carry = (ull)sum >> 32;
	}
}

// Constructs a new BigInteger using a char array with radix=10
int bitCount(char* val) {
	int cursor = 0, numDigits;
	const int len = strlen(val);

	numDigits = len - cursor;
	//signum = sign;

	// Pre-allocate array of expected size
	int numWords;
	if (len < 10) {
		numWords = 1;
	} else {    
		int numBits = (int)((((unsigned int)numDigits * (unsigned int)bitsPerDigit[10]) >> 10) + 1);
		numWords = ((unsigned int)numBits + 31) >> 5;
	}

	vector<int> magnitude(numWords);

	// Process first (potentially short) digit group
	int firstGroupLen = numDigits % digitsPerInt[10];
	if (firstGroupLen == 0)
		firstGroupLen = digitsPerInt[10];
	magnitude[numWords - 1] = parseInt(val, cursor,  cursor + firstGroupLen);
	cursor += firstGroupLen;

	// Process remaining digit groups
	while (cursor < len) {
		int groupVal = parseInt(val, cursor, cursor + digitsPerInt[10]);
		cursor += digitsPerInt[10];
		destructiveMulAdd(magnitude, intRadix[10], groupVal);
	}

	int bc = 0;      // offset by one to initialize
	// Count the bits in the magnitude
	for (int i=0; i<magnitude.size(); i++)
		bc += countPop(magnitude[i]);
	return bc;
}

int main() {
	int T;
	scanf("%d", &T);
	REP(t, T) {
		static char line[1024 * 1024];
		static char n[1024 * 1024];
		static char k[1024 * 1024];
		scanf("%s%s%s", line, n, k);
		const char ch = line[0];

		const int len = strlen(k);
		int remain = 1;
		for (int i = len - 1; i >= 0 && remain; --i) {
			--k[i];
			if (k[i] < '0') {
				k[i] += 10;
				remain = 1;
			} else {
				remain = 0;
			}
		}

		int answer = ch - 'a' + bitCount(k);
		answer &= 1;

		char out[2] = {0, 0};
		out[0] = answer + 'a';
		puts(out);
	}
}

Problem 3 Repairing the Roof

  • ・・・
  • これスーパーコン2010で出題されてたよね?
  • しかも蟻本のコラムにさらっと書いてあったよね?
  • しかもwata先生がなんとかという方法で多項式時間で解けると言っていた気がする
  • とりあえず関連する資料を読みあさってみる
  • この問題は平面グラフにおける完全マッチングの個数の数え上げに帰着できるらしい
  • そしてこの数え上げは隣接行列をちょっと加工した感じの行列のPfaffianを計算すればいいらしい(<-合っているかどうか分からない)
  • FKT algorithmというのだろうか?
  • 早速ネット上のコードを参考に書いてみた
  • ・・・
  • 答えが合わないorz
  • 後でwata先生に教えていただこうorz

Problem 4 Round and Round

  • やるだけボーナス問題きた!
    • Wrong Answer
  • ( ゚д゚)
  • これ一発で通せないのは駄目だろ自分orz
  • Forumの情報を参考に色々修正してみた
    • Accepted
int main() {
	int T;
	cin >> T;
	REP(t, T) {
		string line;
		cin >> line;

		const int N = line.size();
		map<pair<int, int>, int> points;
		int x = 0;
		int y = 0;
		bool yes = true;
		REP(n, N) {
			static const int dx[] = {1, 0, -1, 0};
			static const int dy[] = {0, 1, 0, -1};
			const int dir = line[n] - '0';
			x += dx[dir];
			y += dy[dir];
			if (++points[MP(x, y)] > 1) {
				yes = false;
				break;
			}
		}

		if (yes && x == 0 && y == 0) {
			puts("YES");
		} else {
			puts("NO");
		}
	}
}

Problem 5 Abducted!!!

  • 読む気がしない・・・、読む気がしないよこの変数の数
  • とりあえず気合を入れて読んでみる
  • あれ?これって実は書いてある内容自体は簡単じゃね?
  • 手元に式を書きだしてみる
  • ようするに
    • gx+hy \le j の元で
    • ax^2+bxy+cy^2+dx+ey を最大化させればよいらしい
  • とりあえず全探索してみようか
    • Time Limit Exceeded +部分点
  • 高速化するためには凸関数の最大値付近を探索するとかかなぁ?
    • Wrong Answer +部分点
  • あと、x、yがそれぞれ最大になるとき
    • Wrong Answer +部分点
  • そんじゃあ三分探索したときの解の周辺も入れてみる?
    • Wrong Answer +部分点
  • x、yの最大値の周辺も入れちゃえ!
    • Accepted
static const int DELTA = 30;

int main() {
	int T;
	scanf("%d", &T);
	REP(t, T) {
		ll aa, bb, cc, dd, ee, gg, hh, jj;
		scanf("%lld%lld%lld%lld%lld%lld%lld%lld", &aa, &bb, &cc, &dd, &ee, &gg, &hh, &jj);
		const double a = aa;
		const double b = bb;
		const double c = cc;
		const double d = dd;
		const double e = ee;
		const double g = gg;
		const double h = hh;
		const double j = jj;
		//const double centerY = (j - g * centerX) / h;

		//{
		//	const double x = centerX;
		//	const double y = centerY;
		//	const double answer = a * x * x + b * x * y + c * y * y + d * x + e * y;
		//	cout << x << " " << y << " " << answer << endl;
		//}

		ll bestAnswer = -1;
		{
			const double centerX = -pow(2*a*pow(h,2)-2*b*g*h+2*c*pow(g,2),-1)*((b*h-2*c*g)*j+d*pow(h,2)-e*g*h);
			for (int dx = -DELTA; dx <= DELTA; ++dx) {
				const ll x = centerX + dx;
				const ll y = (j - g * x) / h;
				if (x < 0 || j < x * g || y < 0 || j < y * h) {
					continue;
				}

				const ll answer = aa * x * x + bb * x * y + cc * y * y + dd * x + ee * y;
				bestAnswer = max(bestAnswer, answer);
			}
		}

		{
			const double centerY = pow(2*a*pow(h,2)-2*b*g*h+2*c*pow(g,2),-1)*((2*a*h-b*g)*j+d*g*h-e*pow(g,2));
			for (int dy = -DELTA; dy <= DELTA; ++dy) {
				const ll y = centerY + dy;
				const ll x = (j - h * y) / g;
				if (x < 0 || j < x * g || y < 0 || j < y * h) {
					continue;
				}

				const ll answer = aa * x * x + bb * x * y + cc * y * y + dd * x + ee * y;
				bestAnswer = max(bestAnswer, answer);
			}
		}

		{
			ll loX = 0;
			ll hiX = j / g;
			while (loX + 2 < hiX) {
				const ll midLoX = (loX * 2 + hiX) / 3;
				const ll midLoY = (j - g * midLoX) / h;
				const ll midHiX = (loX + hiX * 2) / 3;
				const ll midHiY = (j - g * midHiX) / h;
				const ll ansLo = aa * midLoX * midLoX + bb * midLoX * midLoY + cc * midLoY * midLoY + dd * midLoX + ee * midLoY;
				const ll ansHi = aa * midHiX * midHiX + bb * midHiX * midHiY + cc * midHiY * midHiY + dd * midHiX + ee * midHiY;
				if (ansLo < ansHi) {
					loX = midLoX;
				} else {
					hiX = midHiX;
				}
			}
			const ll centerX = (loX + hiX) / 2;
			for (int dx = -DELTA; dx <= DELTA; ++dx) {
				const ll x = centerX + dx;
				const ll y = (j - g * x) / h;
				if (x < 0 || j < x * g || y < 0 || j < y * h) {
					continue;
				}

				const ll answer = aa * x * x + bb * x * y + cc * y * y + dd * x + ee * y;
				bestAnswer = max(bestAnswer, answer);
			}
		}

		{
			ll loY = 0;
			ll hiY = j / h;
			while (loY + 2 < hiY) {
				const ll midLoY = (loY * 2 + hiY) / 3;
				const ll midLoX = (j - h * midLoY) / h;
				const ll midHiY = (loY + hiY * 2) / 3;
				const ll midHiX = (j - h * midHiY) / h;
				const ll ansLo = aa * midLoX * midLoX + bb * midLoX * midLoY + cc * midLoY * midLoY + dd * midLoX + ee * midLoY;
				const ll ansHi = aa * midHiX * midHiX + bb * midHiX * midHiY + cc * midHiY * midHiY + dd * midHiX + ee * midHiY;
				if (ansLo < ansHi) {
					loY = midLoY;
				} else {
					hiY = midHiY;
				}
			}
			const ll centerY = (loY + hiY) / 2;
			for (int dy = -DELTA; dy <= DELTA; ++dy) {
				const ll y = centerY + dy;
				const ll x = (j - h * y) / g;
				if (x < 0 || j < x * g || y < 0 || j < y * h) {
					continue;
				}

				const ll answer = aa * x * x + bb * x * y + cc * y * y + dd * x + ee * y;
				bestAnswer = max(bestAnswer, answer);
			}
		}

		{
			const ll centerX = j / g;
			for (int dx = -DELTA; dx <= DELTA; ++dx) {
				const ll x = centerX + dx;
				const ll y = (j - g * x) / h;
				if (x < 0 || j < x * g || y < 0 || j < y * h) {
					continue;
				}

				const ll answer = aa * x * x + bb * x * y + cc * y * y + dd * x + ee * y;
				bestAnswer = max(bestAnswer, answer);
			}

		}

		{
			const ll centerY = j / h;
			for (int dy = -DELTA; dy <= DELTA; ++dy) {
				const ll y = centerY + dy;
				const ll x = (j - h * y) / g;
				if (x < 0 || j < x * g || y < 0 || j < y * h) {
					continue;
				}

				const ll answer = aa * x * x + bb * x * y + cc * y * y + dd * x + ee * y;
				bestAnswer = max(bestAnswer, answer);
			}
		}

		//for (ll x = 0; x * g <= j; ++x) {
		//	const ll y = (j - x * g) / h;
		//	const ll answer = a * x * x + b * x * y + c * y * y + x * d + y * e;
		//	bestAnswer = max(bestAnswer, answer);
		//	cout << x << " " << y << " " << answer << endl;
		//}
		printf("%lld\n", bestAnswer);
	}
}

Problem 6 Mr. Bean Helping Out! Finally!

  • これ多倍長ゲーだよねぇ
  • まずは多倍長なし64bit整数だけで書いてみる
    • Wrong Answer +部分点
  • とりあえず多倍長で書きなおしてみた
    • Time Limit Exceeded
  • うむむ
  • 待てよ・・・、N<=460だから埋め込めるんじゃ・・・
  • 書いてみた
    • Accepted
  • 埋め込みゲーかよ!?
int main() {
	//vector<BigInteger> fact;
	//fact.push_back(1);
	//for (int i = 1; i <= 461; ++i) {
	//	fact.push_back(fact.back() * i);
	//}

	//for (int n = 1; n <= 460; ++n) {
	//	BigInteger lo = fact[n];

	//	BigInteger hi = 0;
	//	for (int k = 0; k <= n; ++k) {
	//		hi = hi + fact[k] * fact[n - k];
	//	}

	//	const BigInteger g = lo.gcd(hi);
	//	lo = lo / g;
	//	hi = hi / g;

	//	putchar('"');
	//	if (lo == BigInteger(1)) {
	//		hi.print();
	//		puts("\",");
	//	} else {
	//		hi.print();
	//		putchar('/');
	//		lo.print();
	//		puts("\",");
	//	}
	//}

	int T;
	cin >> T;
	REP(t, T) {
		int n;
		cin >> n;
		cout << kAnswers[n] << endl;
	}
}

Problem 7 Thrown Out of the Party!

  • さっぱり方針が立たない
  • 次数でソートしてクリークを見つけるコードを投げてみる
    • Time Limit Exceeded
  • プロファイラを使って定数高速化してみる
    • Time Limit Exceeded
  • 無理っぽいorz

Problem 8 Garden Disaster

  • なんか問題文が良く分からない
  • ようは数直線上に区間が与えられて、クエリとして与えられる区間内に、一部は含まれるが真には含まれない区間が幾つ存在するかを求めればよいらしい
  • なんかロシアゲーっぽい
  • とりあえず愚直なコードを書いてみる
    • Time Limit Exceeded +部分点
  • セグメント木とか平方分割とかで速くなりそうだけど、やり方が思いつかないorz
int main() {
	int T;
	scanf("%d", &T);
	REP(t, T) {
		int R, N;
		scanf("%d%d", &R, &N);

		vector<pair<int, int> > roses;
		REP(n, N) {
			int P, Q;
			scanf("%d%d", &P, &Q);
			roses.push_back(MP(P, n));
			roses.push_back(MP(Q, n));
		}

		sort(ALL(roses));

		int M;
		scanf("%d", &M);
		REP(m, M) {
			vector<char> memo(N);
			int P, Q;
			scanf("%d%d", &P, &Q);
			if (P > Q) {
				swap(P, Q);
			}

			int answer = 0;
			for (vector<pair<int, int> >::iterator it = upper_bound(ALL(roses), MP(P, INT_MAX)), itEnd = lower_bound(ALL(roses), MP(Q, INT_MIN)); it != itEnd; ++it) {
				if (memo[it->second]) {
					--answer;
				} else {
					memo[it->second] = true;
					++answer;
				}
			}

			printf("%d\n", answer);
		}
	}
}

Problem 9 Dinner with Sachin

  • 問題を理解する気力がありませんでしたorz

Problem 10 Showtime!

  • 幾何に突っ込む余裕がありませんでしたorz

まとめ

  • 約3000チーム中11位と、自分にしてはかなりの好成績!
  • HETARE-Algorithmerがir5さんなのかcosさんなのかd_kamiさんなのかkamingさんなのか分からない
  • ネタで考えたチーム名が1ページ目に表示できたので満足
  • 数え上げの問題を完全に捨てて幾何に突っ込むべきだったかもしれない
  • 入力上限が記述されていないのは、そういうコンテストだからなのだろうか?
トラックバック - http://topcoder.g.hatena.ne.jp/nodchip/20110214
 |