Hatena::Grouptopcoder

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

 | 

2010-04-02

Codeforces beta #7 14:36 Codeforces beta #7 - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - Codeforces beta #7 - nodchipのTopCoder日記 Codeforces beta #7 - nodchipのTopCoder日記 のブックマークコメント

Problem A Kalevitch and Chess

  • 塗るラインは16個しか無いので2^16パターン全部試せばOK
  • 計算量は2^16×8位。余裕
  • 一問目にしては重いような・・・

結果:Accepted

int countBits(int x){
	x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
	x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
	x = (x & 0x0f0f0f0f) + ((x >> 4) & 0x0f0f0f0f);
	x = (x & 0x00ff00ff) + ((x >> 8) & 0x00ff00ff);
	x = (x & 0x0000ffff) + ((x >> 16) & 0x0000ffff);
	return x;
}

int main() {
	string board;
	for (int i = 0; i < 8; ++i) {
		string row;
		cin >> row;
		board += row;
	}

	int best = INT_MAX;
	for (int flag = 0; flag < (1 << 16); ++flag) {
		string cand(64, 'W');
		for (int i = 0; i < 16; ++i) {
			if (!(flag & (1 << i))) {
				continue;
			}
			if (i < 8) {
				const int row = i;
				for (int column = 0; column < 8; ++column) {
					cand[row * 8 + column] = 'B';
				}
			} else {
				const int column = i - 8;
				for (int row = 0; row < 8; ++row) {
					cand[row * 8 + column] = 'B';
				}
			}
		}

		if (board == cand) {
			best = min(best, countBits(flag));
		}
	}
	
	cout << best << endl;
}

Problem B Memory Manager

  • サイズが小さいので愚直にシミュレーションすれば良い
  • ・・・良いんだけど重くね?
  • これ重くね?
  • しかも境界条件多くね?
    • alloc
      • メモリが空のとき
      • 先頭に入れるとき
      • メモリとメモリの間に入れるとき
      • 末尾に入れるとき

結果:Accepted

struct Data {
	int identifier;
	int start;
	int end;
};

int main() {
	vector<Data> memory;
	int nextIdentifier = 1;

	int t, m;
	cin >> t >> m;
	for (int commandIndex = 0; commandIndex < t; ++commandIndex) {
		string command;
		cin >> command;

		if (command == "alloc") {
			int n;
			cin >> n;
			int start = INT_MAX;
			int memoryIndex = INT_MAX;
			if (memory.empty()) {
				if (n <= m) {
					start = 0;
					memoryIndex = 0;
				}

			} else {
				if (n <= memory.front().start) {
					start = 0;
					memoryIndex = 0;
				} else {
					for (int i = 0; i + 1 < memory.size(); ++i) {
						if (n <= memory[i + 1].start - memory[i].end) {
							start = memory[i].end;
							memoryIndex = i;
							break;
						}
					}
					if (start == INT_MAX) {
						if (n <= m - memory.back().end) {
							start = memory.back().end;
							memoryIndex = memory.size();
						}
					}
				}
			}

			if (start == INT_MAX) {
				cout << "NULL" << endl;
				continue;
			}

			Data d;
			d.start = start;
			d.end = start + n;
			d.identifier = nextIdentifier++;
			memory.insert(memory.begin() + memoryIndex, d);
			cout << d.identifier << endl;

		} else if (command == "erase") {
			int x;
			cin >> x;
			bool erased = false;
			for (int i = 0; i < memory.size(); ++i) {
				if (memory[i].identifier == x) {
					erased = true;
					memory.erase(memory.begin() + i);
					break;
				}
			}

			if (!erased) {
				cout << "ILLEGAL_ERASE_ARGUMENT" << endl;
			}

		} else if (command == "defragment") {
			if (memory.empty()) {
				continue;
			}

			int move;
			move = memory.front().start;
			memory.front().start -= move;
			memory.front().end -= move;

			for (int i = 1; i < memory.size(); ++i) {
				move = memory[i].start - memory[i - 1].end;
				memory[i].start -= move;
				memory[i].end -= move;
			}
		}
	}
}

Problem C Line

  • これ幾何問題じゃないよね?
  • 数論問題だよね?
  • とりあえずA=0とB=0は別扱いなので書いた
  • 見た感じで拡張gcdのような気がする
  • でも拡張gcdが何なのか分からない
  • Wikipedia先生にお伺いを立ててみる
  • Ax+By=gcd(A,B)の形でないと使えないらしい・・・
  • どうやってこの形に変形するんだろう?
  • とりあえずC%gcd(A,B)!=0は解がないことは分かる
  • A、B、Cをgcd(A,B)で割って、拡張gcdをかけて、出てきたx,yを-C倍すれば良いのかな・・・?

結果:Accepted

typedef long long Int;

Int gcd(Int a, Int b) {
  return b != 0 ? gcd(b, a % b) : a;
}
Int lcm(Int a, Int b) {
  return a * b / gcd(a, b);
}
// a x + b y = gcd(a, b)
Int extgcd(Int a, Int b, Int &x, Int &y) {
  Int g = a; x = 1; y = 0;
  if (b != 0) g = extgcd(b, a % b, y, x), y -= (a / b) * x;
  return g;
}

void ExGCDR(ll a, ll b, ll& s, ll& t, ll& c) {
	if (b == 0) {
		s = 1;
		t = 0;
		c = a;
	} else {
		ll q = a / b;
		ll r = a % b;
		ll s1, t1;
		ExGCDR(b, r, s1, t1, c);
		s = t1;
		t = s1 - t1 * q;
	}
}

int main() {
	ll A, B, C;
	cin >> A >> B >> C;

	if (A == 0) {
		if (C % B == 0) {
			cout << 0 << " " << (-C / B) << endl;
		} else {
			cout << -1 << endl;
		}
		return 0;
	}

	if (B == 0) {
		if (C % A == 0) {
			cout << (-C / A) << " " << 0 << endl;
		} else {
			cout << -1 << endl;
		}
		return 0;
	}

	ll g = gcd(A, B);

	if (C % g != 0) {
		cout << -1 << endl;
		return 0;
	}
	
	A /= g;
	B /= g;
	C /= g;

	ll x, y;
	extgcd(A, B, x, y);
	x *= -C;
	y *= -C;
	cout << x << " " << y << endl;
}

Problem D Palindrome Degree

  • DP臭がする
  • 回文って言ってるくらいだからManacher使ってみる?
  • ルーチンの中で使われている回文の半径を順に調べればdegreeが求められそう
  • Wrong Answer

ここで終了

  • 最後の答えを出す部分が間違っていたらしい
  • 直した
  • TLE
  • 定数最適化してみた
  • Accepted
  • LinesPowerさんによるとハッシュを使っても解けるらしい
int longest_palindrome(char *text, int n, int rad[]) {
	int i, j, k;
	for (i = 0, j = 0; i < 2*n; i += k, j = max(j-k, 0)) {
		while (i-j >= 0 && i+j+1 < 2*n && text[(i-j)/2] == text[(i+j+1)/2]) ++j;
		rad[i] = j;
		for (k = 1; i-k >= 0 && rad[i]-k >= 0 && rad[i-k] != rad[i]-k; ++k)
			rad[i+k] = min(rad[i-k], rad[i]-k);
	}
	return *max_element(rad, rad+2*n); // ret. centre of the longest palindrome
}

char in[5 * 1024 * 1024];
int rad[10 * 1024 * 1024];
int dp[10 * 1024 * 1024];

int main() {
	scanf("%s", in);
	const int n = strlen(in);

	longest_palindrome(in, n, rad);

	dp[0] = 1;
	ll sum = 1;
	for (int i = 1; i < 2 * n; ++i) {
		if (rad[i] == i + 1) {
			if (i % 2 == 0) {
				dp[i] = dp[i / 2 - 1] + 1;
			} else {
				dp[i] = dp[i / 2] + 1;
			}
		}
		sum += dp[i];
	}

	cout << sum << endl;
}

Problem E Defining Macros

  • 構文解析怖いよーーー
  • 以上終了

uenoragaguenoragag2017/11/30 07:39http://price-of-levitra-20mg.mobi/ - price-of-levitra-20mg.mobi.ankor <a href="http://buyventolin-online.mobi/">buyventolin-online.mobi.ankor</a> http://buylevitrageneric.mobi/

auzumaaljetiauzumaaljeti2017/11/30 07:41http://price-of-levitra-20mg.mobi/ - price-of-levitra-20mg.mobi.ankor <a href="http://buyventolin-online.mobi/">buyventolin-online.mobi.ankor</a> http://buylevitrageneric.mobi/

ekuyuqikoqilekuyuqikoqil2017/11/30 07:58http://price-of-levitra-20mg.mobi/ - price-of-levitra-20mg.mobi.ankor <a href="http://buyventolin-online.mobi/">buyventolin-online.mobi.ankor</a> http://buylevitrageneric.mobi/

uxaditvonokobuxaditvonokob2017/11/30 21:01http://price-of-levitra-20mg.mobi/ - price-of-levitra-20mg.mobi.ankor <a href="http://buyventolin-online.mobi/">buyventolin-online.mobi.ankor</a> http://buylevitrageneric.mobi/

obobovokvopobobovokvop2017/11/30 21:02http://price-of-levitra-20mg.mobi/ - price-of-levitra-20mg.mobi.ankor <a href="http://buyventolin-online.mobi/">buyventolin-online.mobi.ankor</a> http://buylevitrageneric.mobi/

itezaobiitezaobi2017/11/30 21:16http://price-of-levitra-20mg.mobi/ - price-of-levitra-20mg.mobi.ankor <a href="http://buyventolin-online.mobi/">buyventolin-online.mobi.ankor</a> http://buylevitrageneric.mobi/

adursofuadursofu2017/11/30 21:26http://price-of-levitra-20mg.mobi/ - price-of-levitra-20mg.mobi.ankor <a href="http://buyventolin-online.mobi/">buyventolin-online.mobi.ankor</a> http://buylevitrageneric.mobi/

ulojatcaruriculojatcaruric2017/12/11 14:19http://price-of-levitra-20mg.mobi/ - price-of-levitra-20mg.mobi.ankor <a href="http://buyventolin-online.mobi/">buyventolin-online.mobi.ankor</a> http://buylevitrageneric.mobi/

ezajumapezajumap2017/12/11 14:19http://price-of-levitra-20mg.mobi/ - price-of-levitra-20mg.mobi.ankor <a href="http://buyventolin-online.mobi/">buyventolin-online.mobi.ankor</a> http://buylevitrageneric.mobi/

awuliwusosafoawuliwusosafo2017/12/11 14:28http://price-of-levitra-20mg.mobi/ - price-of-levitra-20mg.mobi.ankor <a href="http://buyventolin-online.mobi/">buyventolin-online.mobi.ankor</a> http://buylevitrageneric.mobi/

areyemuareyemu2017/12/11 14:32http://price-of-levitra-20mg.mobi/ - price-of-levitra-20mg.mobi.ankor <a href="http://buyventolin-online.mobi/">buyventolin-online.mobi.ankor</a> http://buylevitrageneric.mobi/

erojivanaerojivana2017/12/11 14:32http://price-of-levitra-20mg.mobi/ - price-of-levitra-20mg.mobi.ankor <a href="http://buyventolin-online.mobi/">buyventolin-online.mobi.ankor</a> http://buylevitrageneric.mobi/

ajusameajusame2017/12/11 14:32http://price-of-levitra-20mg.mobi/ - price-of-levitra-20mg.mobi.ankor <a href="http://buyventolin-online.mobi/">buyventolin-online.mobi.ankor</a> http://buylevitrageneric.mobi/

oxuebeizewoxuebeizew2017/12/11 14:46http://price-of-levitra-20mg.mobi/ - price-of-levitra-20mg.mobi.ankor <a href="http://buyventolin-online.mobi/">buyventolin-online.mobi.ankor</a> http://buylevitrageneric.mobi/

icuifarllitoficuifarllitof2017/12/11 14:49http://price-of-levitra-20mg.mobi/ - price-of-levitra-20mg.mobi.ankor <a href="http://buyventolin-online.mobi/">buyventolin-online.mobi.ankor</a> http://buylevitrageneric.mobi/

gabimalemahugabimalemahu2017/12/11 15:00http://price-of-levitra-20mg.mobi/ - price-of-levitra-20mg.mobi.ankor <a href="http://buyventolin-online.mobi/">buyventolin-online.mobi.ankor</a> http://buylevitrageneric.mobi/

ivuicasubivuicasub2017/12/11 23:29http://price-of-levitra-20mg.mobi/ - price-of-levitra-20mg.mobi.ankor <a href="http://buyventolin-online.mobi/">buyventolin-online.mobi.ankor</a> http://buylevitrageneric.mobi/

epabicijepabicij2017/12/11 23:43http://price-of-levitra-20mg.mobi/ - price-of-levitra-20mg.mobi.ankor <a href="http://buyventolin-online.mobi/">buyventolin-online.mobi.ankor</a> http://buylevitrageneric.mobi/

トラックバック - http://topcoder.g.hatena.ne.jp/nodchip/20100402
 |