Hatena::Grouptopcoder

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

 | 

2010-12-26

hos' Xmas Contest 2010 11:45 hos' Xmas Contest 2010 - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - hos' Xmas Contest 2010 - nodchipのTopCoder日記 hos' Xmas Contest 2010 - nodchipのTopCoder日記 のブックマークコメント

H: Read Me

  • 問題タイトルにつられてやって来ました
  • www
  • 入力検証器を書けと?
  • じゃあACM-ICPC OB/OG会で書いている入力検証器フレームワークを流用して書いてみましょうか
  • フレームワークでは想定外の入力が与えられたときにassert()で落ちるようになっているので、そこをreturn false;するように一からつくり直してみる
  • 後は入力検証器をガリガリ書くだけ
  • 書けた!
  • 481行!?
  • いつの間にこんなに書いたんだろう自分・・・
  • submit
    • No - 90% Accepted
  • 嫌な予感
  • これデバッグ無理じゃね
  • とりあえず一つずつ調べていってみる
  • いろいろ間違ってた
  • submitするもNo - 90% Accepted
  • もうだめぽ
  • ・・・
  • RejudgeでAccepted
  • ・・・
  • orz
struct UnionFind {
	vector<int> data;
	UnionFind(int size) : data(size, -1) { }
	bool unionSet(int x, int y) {
		x = root(x); y = root(y);
		if (x != y) {
			if (data[y] < data[x]) swap(x, y);
			data[x] += data[y]; data[y] = x;
		}
		return x != y;
	}
	bool findSet(int x, int y) {
		return root(x) == root(y);
	}
	int root(int x) {
		return data[x] < 0 ? x : data[x] = root(data[x]);
	}
	int size(int x) {
		return -data[root(x)];
	}
};

const char* p = NULL;

#define check(b) if(!(b))return false;

#define read_int(lo,hi,n) if(!(read_int_impl(lo,hi,n)))return false;
bool read_int_impl(int lo, int hi, int& n) {
	string s;
	while (*p == '-' || isdigit(*p)) {
		s += *p++;
	}
	ll value;
	if (!(istringstream(s) >> value)) {
		return false;
	}
	if (value < lo || hi < value) {
		return false;
	}
	n = (int)value;
	return true;
}

#define read_space() if(!(read_space_impl()))return false;
bool read_space_impl() {
	if (*p == ' ') {
		++p;
		return true;
	}
	return false;
}

#define read_return() if(!read_return_impl())return false;
bool read_return_impl() {
	if (*p == '\n') {
		++p;
		return true;
	}
	return false;
}

#define read_eof() if(!read_eof_impl())return false;
bool read_eof_impl() {
	if (*p == '\0') {
		++p;
		return true;
	}
	return false;
}

#define read_string(s) if(!read_string_impl(s))return false;
bool read_string_impl(string& s) {
	s.clear();
	while (isgraph(*p)) {
		s += *p++;
	}
	return !s.empty();
}

bool readAsA() {
	//各入力は 1 個以上 100 個以下のテストケースからなる.
	//各テストケースは,整数 a, b, c, d (1 <= a <= 1 000 000 000, 1 <= b <= 1 000 000 000, 1 <= c <= 1 000 000 000, 1 <= d <= 1 000 000 000) を含む 1 行からなる.
	//最後のテストケースの次の行には,4 つの 0 が書かれている.
	int numberOfCases = 0;
	for (;;) {
		int a, b, c, d;
		read_int(0, 1000000000, a);
		read_space();
		read_int(0, 1000000000, b);
		read_space();
		read_int(0, 1000000000, c);
		read_space();
		read_int(0, 1000000000, d);
		read_return();

		if (!(a || b || c || d)) {
			break;
		}

		++numberOfCases;
	}

	check(1 <= numberOfCases && numberOfCases <= 100);
	read_eof();
	return true;
}

bool readAsB() {
	//各入力は 1 個以上 10 個以下のテストケースからなる.
	//各テストケースは,上記で定義された数式 <expression> が 1 つ書かれた 1 行からなる.与えられる数式は 10 000 文字以下である.
	//最後のテストケースの次の行には,1 つの # が書かれている.
	int numberOfCases = 0;
	for (;;) {
		string s;
		read_string(s);
		read_return();

		if (s == "#") {
			break;
		}

		check(s.size() <= 10000);
		REP(i, s.size()) {
			const char c = s[i];
			check(isdigit(c) || c == '-' || c == '+' || c == '(' || c == ')');
		}

		++numberOfCases;
	}

	check(1 <= numberOfCases && numberOfCases <= 10);
	read_eof();
	return true;
}

bool readAsC() {
	//各入力は 1 個以上 10 個以下のテストケースからなる.
	//各テストケースは,以下のような形式である.入力の値はすべて正の整数である.
	//N M
	//s1
	//...
	//sN
	//a1 b1 c1
	//...
	//aM bM cM
	//アクセサリーとマスコットは合わせて N 個あり (2 <= N <= 100),直接つなげる可能性があるアクセサリーやマスコットのペアは M 組ある (1 <= M <= 1 000).
	//アクセサリーやマスコットには 1 番から N 番までの通し番号がついている.i 番のアクセサリーまたはマスコットが「すごくお気に入り」であるとき si = 0 であり,そうでないとき si = 1 である.各テストケースにおいて,si の総和は 10 以下である.
	//aj, bj, cj という行は,aj 番と bj 番のアクセサリーとマスコットをつなげる可能性があり,その<みばえわるさ>が cj であることを表す (1 <= aj < bj <= N, 1 <= cj <= 1 000 000).異なる j, k に対して (aj, bj) = (ak, bk) となることはない.
	//M 組のつなげる候補すべてをつなげると,N 個のアクセサリーとマスコットはすべてつながって,一気に持ち上げられるようになることが保証されている.また,「すごくお気に入り」のアクセサリーまたはマスコットは少なくとも 2 個あることが保証されている.
	//最後のテストケースの次の行には,2 つの 0 が書かれている.
	int numberOfCases = 0;
	for (;;) {
		int N, M;
		read_int(0, 100, N);
		read_space();
		read_int(0, 1000, M);
		read_return();

		check(N != 1);

		if (!(N || M)) {
			break;
		}
		check(1 <= N);
		check(1 <= M);

		int numberOfFavorites = 0;

		int sumS = 0;
		REP(n, N) {
			int si;
			read_int(0, 1, si);
			read_return();

			if (si == 0) {
				++numberOfFavorites;
			}
			sumS += si;
		}

		check(2 <= numberOfFavorites);
		check(sumS <= 10);

		UnionFind uf(N + 1);
		set<pair<int, int> > ab;
		REP(m, M) {
			int a, b, c;
			read_int(1, N - 1, a);
			read_space();
			read_int(a + 1, N, b);
			read_space();
			read_int(0, 1000000, c);
			read_return();
			check(ab.count(MP(a, b)) == 0);
			ab.insert(MP(a, b));
			uf.unionSet(a, b);
		}

		check(uf.size(1) == N);

		++numberOfCases;
	}

	check(1 <= numberOfCases && numberOfCases <= 10);
	read_eof();
	return true;
}

bool readAsD() {
	//各入力は 1 個以上 10 個以下のテストケースからなる.
	//各テストケースは,以下のような形式である.入力の値はすべて正の整数である.各文字の意味は問題文中の通りである.
	//N P Q D
	//d1 a1 b1
	//...
	//dN aN bN
	//1 <= N <= 1 000, 1 <= P <= 1 000, 1 <= Q <= 100 000, 0 < d1 < ... < dN < D <= 100 000, 1 <= ai <= 100 000, 1 <= bi <= 100 000 を満たす.
	//最後のテストケースの次の行には,4 つの 0 が書かれている.
	int numberOfCases = 0;
	for (;;) {
		int N, P, Q, D;
		read_int(0, 1000, N);
		read_space();
		read_int(0, 1000, P);
		read_space();
		read_int(0, 100000, Q);
		read_space();
		read_int(0, 100000, D);
		read_return();

		if (!(N || P || Q || D)) {
			break;
		}
		check(1 <= N);
		check(1 <= P);
		check(1 <= Q);
		check(1 <= D);

		int lastD = 0;
		REP(n, N) {
			int d, a, b;
			read_int(lastD + 1, D - 1, d);
			read_space();
			read_int(1, 100000, a);
			read_space();
			read_int(1, 100000, b);
			read_return();
			lastD = d;
		}

		++numberOfCases;
	}

	check(1 <= numberOfCases && numberOfCases <= 10);
	read_eof();
	return true;
}

bool readAsE() {
	//各入力は 1 個以上 20 個以下のテストケースからなる.
	//各テストケースの 1 行目には,ドーナツの個数を表す整数 N (1 <= N <= 10) が書かれている.
	//続く N 行には,各ドーナツを表す 4 つの整数 a, b, t, k (0 < a <= 100, 0 < b <= 100, 0 <= t < 180, 0 < k < 100) が書かれている.
	//最後のテストケースの次の行には,1 つの 0 が書かれている.
	int numberOfCases = 0;
	for (;;) {
		int N;
		read_int(0, 10, N);
		read_return();

		if (!N) {
			break;
		}
		check(1 <= N);

		REP(n, N) {
			int a, b, t, k;
			read_int(1, 100, a);
			read_space();
			read_int(1, 100, b);
			read_space();
			read_int(0, 179, t);
			read_space();
			read_int(1, 99, k);
			read_return();
		}

		++numberOfCases;
	}

	check(1 <= numberOfCases && numberOfCases <= 20);
	read_eof();
	return true;
}

bool readAsF() {
	//各入力は 1 個以上 10 個以下のテストケースからなる.
	//各テストケースの 1 行目には,整数 M, N, K (1 <= M <= 40, 1 <= N <= 40, 1 <= K <= 1 000 000 000) が書かれている.これは,表のデータが M 行 N 列であること,合計の値が K になるように変換しようとしていることを表す.
	//続く M 行の各行には N 個の非負整数が書かれており,順番に表の内容を表す.これら MN 個の非負整数の和は 1 以上 1 000 000 000 以下である.
	//表の各行の合計や各列の合計の部分は,M, N の値やその後の入力には含まれないことに注意せよ.例えば,問題文中の表の場合は M = 2, N = 3 である.
	//各テストケースの後には空行が 1 つ含まれる.
	//最後のテストケースの次の行には,3 つの 0 が書かれている.
	int numberOfCases = 0;
	for (;;) {
		int M, N, K;
		read_int(0, 40, M);
		read_space();
		read_int(0, 40, N);
		read_space();
		read_int(0, 1000000000, K);
		read_return();

		if (!(M || N || K)) {
			break;
		}
		check(1 <= M);
		check(1 <= N);
		check(1 <= K);

		ll sum = 0;
		REP(m, M) {
			REP(n, N) {
				if (n) {
					read_space();
				}
				int k;
				read_int(0, 1000000000 - sum, k);
				sum += k;
			}
			read_return();
		}
		read_return();

		++numberOfCases;
	}

	assert(1 <= numberOfCases && numberOfCases <= 10);
	read_eof();
	return true;
}

bool readAsG() {
	//各入力は 1 個以上 20 個以下のテストケースからなる.
	//各テストケースは,整数 N, M, A, B (1 <= N <= 100 000, 1 <= M <= 100 000, 1 <= A <= N, 1 <= B <= N) を含む 1 行からなる.
	//最後のテストケースの次の行には,4 つの 0 が書かれている.
	int numberOfCases = 0;
	for (;;) {
		int N, M, A, B;
		read_int(0, 100000, N);
		read_space();
		read_int(0, 100000, M);
		read_space();
		read_int(0, N, A);
		read_space();
		read_int(0, N, B);
		read_return();

		if (!(N || M || A || B)) {
			break;
		}

		check(1 <= N);
		check(1 <= M);
		check(1 <= A);
		check(1 <= B);

		++numberOfCases;
	}

	check(1 <= numberOfCases && numberOfCases <= 20);
	read_eof();
	return true;
}

static const char* END_OF_CASE = "@@@@@@@@@@";
static const char* END_OF_INPUT = "@@@@@@@@@@@@@@@@@@@@";
static char line_buffer[1024 * 1024];

int main() {
	vector<char> input_buffer;
	while (gets(line_buffer)) {
		if (strcmp(END_OF_CASE, line_buffer) == 0) {
			input_buffer.push_back('\0');

			vector<char> answer;
			p = &input_buffer[0];
			if (readAsA()) answer.push_back('A');
			p = &input_buffer[0];
			if (readAsB()) answer.push_back('B');
			p = &input_buffer[0];
			if (readAsC()) answer.push_back('C');
			p = &input_buffer[0];
			if (readAsD()) answer.push_back('D');
			p = &input_buffer[0];
			if (readAsE()) answer.push_back('E');
			p = &input_buffer[0];
			if (readAsF()) answer.push_back('F');
			p = &input_buffer[0];
			if (readAsG()) answer.push_back('G');

			assert(answer.size() != 0);
			while (answer.size() == 0)
				;

			if (answer.size() >= 2) {
				cerr << answer.size() << " " << string(ALL(answer)) << endl;
				cout << "?" << endl;
			} else {
				answer.push_back(0);
				cout << answer[0] << endl;
			}

			input_buffer.clear();

		} else if (strcmp(END_OF_INPUT, line_buffer) == 0) {
			break;
		} else {
			input_buffer.insert(input_buffer.end(), line_buffer, line_buffer + strlen(line_buffer));
			input_buffer.push_back('\n');
		}

	}
}

A: Christmas Trees

  • うわぁ、面倒くさそう
  • でも解けるんだよねこれ?
  • とりあえず考えてみる
  • 区間の中央を表すのが面倒だから座標を二倍化
  • どちらかの家を木の位置か木+1の位置に固定して全部調べる
  • submit
    • No - 60% Accepted
  • 境界条件間違ってるんだろうなぁ
  • 問題を読み直してみる
  • ・・・
  • 二つの家は同じ位置にはないと言っている
  • これか!
  • 修正
  • submit
    • Yes - Accepted
ll count(ll base, ll first, ll second, ll delta) {
	delta += base;
	if (delta < 0) {
		return 0;
	}
	ll numPair = delta / (first + second) * 2;
	if (delta % (first + second) < first) {
		numPair += 1;
	} else {
		numPair += 2;
	}

	return numPair;
}

void check_half(ll first, ll second, ll delta, ll& minValue, ll& maxValue) {
	const ll c0 = count(0, first, second, delta);
	const ll c1 = count(1 - second, first, second, delta);
	minValue = min(minValue, c0);
	minValue = min(minValue, c1);
	maxValue = max(maxValue, c0);
	maxValue = max(maxValue, c1);
}

void check(ll a, ll b, ll delta, ll& minValue, ll& maxValue) {
	check_half(a, b, delta, minValue, maxValue);
	check_half(b, a, delta, minValue, maxValue);
}

ll myabs(ll x) {
	return x > 0 ? x : -x;
}

int main() {
	for (ll a, b, c, d; cin >> a >> b >> c >> d && (a || b || c || d); ) {
		a *= 2;
		b *= 2;
		c *= 2;
		d *= 2;
		ll minValue = 0xFFFFFFFFFFFFFFFLL;
		ll maxValue = -0xFFFFFFFFFFFFFFFLL;
		check(a, b, myabs(c + d), minValue, maxValue);
		if (c != d) {
			check(a, b, myabs(c - d), minValue, maxValue);
		}
		cout << minValue << " " << maxValue << endl;
	}
}

B: Simple Parsing

  • 問題冒頭の皮肉が面白い
  • それはそうとパースです
  • 一昔前だったら避けてた問題
  • 今なら解けるよね?
  • まず偶奇しか要らないのだから、桁のでかい数字は0/1に変換しておく
  • 続いて+と-は等価になるので全部+に変換
  • で、+が連続で続いたら読み飛ばす
  • submit
    • Yes - Accepted
static char line_buffer[16 * 1024];
static char buffer[16 * 1024];
static const char* p = 0;

bool f() {
	bool myResult = false;
	while (*p == '+') {
		++p;
	}
	if (isdigit(*p)) {
		myResult = (bool)(*p & 1);
		++p;
	} else if (*p == '(') {
		++p;
		myResult = f();
		++p;
	} else {
		while ('A')
			;
	}

	if (*p == '+') {
		++p;
		myResult ^= f();
	}

	return myResult;
}

bool isMinus(char c) {
	return c == '-';
}

bool solve() {
	// -を+に変換
	replace_if(line_buffer, line_buffer + strlen(line_buffer), isMinus, '+');

	// ++を取り除く
	char last = 0;
	char* p = line_buffer;
	char* q = buffer;
	while (*p) {
		if (*p == '+' && last == '+') {
		} else if (isdigit(*p) && isdigit(last)) {
		} else if (last) {
			*q++ = last;
		}
		last = *p++;
	}
	*q++ = last;
	*q++ = 0;

	::p = buffer;

	return f();
}

int main() {
	while (gets(line_buffer) && strcmp(line_buffer, "#") != 0) {
		cout << (solve() ? "ODD" : "EVEN") << endl;
	}
}

C: Connect The Decoration

  • 見た感じで全域最小木だけど
  • 幾つかの飾りを外すってどうするんだろう
  • ・・・
  • あ、外して良い飾りって十個までか
  • 2^10回して終わりじゃん
  • submit
    • No - 80% Accepted
  • あれ・・・TLE
  • Primじゃだめ?
  • じゃあKruscalかなぁ
  • submit
    • Yes - Accepted

D: Presents

  • SmallはDPっぽく見えるけど・・・
  • 後回し

E: Donuts

  • 幾何!
  • ・・・
  • これ難しくね?
  • 諦めようorz

F: Christmas Magic

  • とりあえず考えてみようか
  • ・・・
  • DPでどうにかならないのかなぁ
  • 各マスについて切り捨てるか切り上げるかの二通り
  • これで2^1600
  • 状態は[何個目の数字][合計の値]なので2^1600->1600*1600
  • 行けそう、書いてみようか
  • 書けた
  • submit
    • No - Wrong Answer
  • Merry Christmas!の条件が分からないorz

G: Strange Sequence

  • 数論無理です

結果

Rankユーザ名ABCDEFGHScore / Time
19nodchip100/2100/1100/3---/----/-0/2---/-100/7400/771

Dをやっていればもう少し良い点がとれたんじゃないかと思います。残念です。

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