Hatena::Grouptopcoder

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

 | 

2010-10-05

Maximum-Cup 2010 12:04 Maximum-Cup 2010 - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - Maximum-Cup 2010 - nodchipのTopCoder日記 Maximum-Cup 2010 - nodchipのTopCoder日記 のブックマークコメント

Problem A 10165 さいたまトラップ

  • タイトルからしてさいたまする気満々・・・
  • でもこれさいたまトラップ無くね?
  • せいぜい24:00:00丁度の時の境界条件くらいか
  • submit
  • Compile Error・・・orz
  • C++を選んで再submit
    • Accepted
int main() {
	for (int N; cin >> N && N; ) {
		map<string, ll> trapToTime;
		REP(n, N) {
			string name;
			int h, m, s;
			char c;
			cin >> name >> h >> c >> m >> c >> s;
			trapToTime[name] = h * 3600 + m * 60 + s;
		}

		int M;
		cin >> M;

		ll rest = 0;
		REP(m, M) {
			string name;
			ll number;
			cin >> name >> number;
			rest += trapToTime[name] * number;
		}

		// TODO:そもそも中断することはないとはどういう意味?
		ll past = 0;
		while (rest != 0 && past < 24 * 60 * 60) {
			const ll t = min(rest, 60 * 60LL);
			past += t;
			rest -= t;
			if (rest == 0) {
				break;
			}
			past += 10 * 60;
		}

		if (24 * 60 * 60 <= past) {
			printf("IMPOSSIBLE\n");
		} else {
			printf("%02d:%02d:%02d\n", (int)(past / 3600), (int)(past / 60 % 60), (int)(past % 60));
		}
	}

}

Problem B 10167 鶴亀算

  • 連立方程式解くだけだよね?
    • これ系の問題解けたこと無いけど
  • ライブラリあったっけ・・・
  • Spagetti Source に LU分解 がある!
  • submit
  • Runtime Error
  • 入力のパースで一列に係数がN個未満の時にassertに引っかかっているっぽい
  • 修正
  • submit
    • Accepted
struct Dictionary {
	map<string, int> nameToIndex;
	vector<string> indexToMap;
	int getIndex(const string& name) {
		map<string, int>::iterator it = nameToIndex.find(name);
		if (it != nameToIndex.end()) {
			return it->second;
		} else {
			const int index = nameToIndex.size();
			nameToIndex[name] = index;
			indexToMap.push_back(name);
			return index;
		}
	}
	const string& getName(int index) const {
		return indexToMap[index];
	}
};

//#ifdef assert
//#undef assert
//#endif
//
//void assert(bool e) {
//	while (!e) { }
//}

int main() {
	int N;
	cin >> N;
	string line;
	getline(cin, line);

	matrix mat(N, array(N));
	array a(N);

	Dictionary animals;
	Dictionary organs;

	REP(n, N) {
		string line;
		getline(cin, line);
		istringstream iss(line);

		string animal, has;
		iss >> animal >> has;
		assert(has == "has");

		const int animalIndex = animals.getIndex(animal);
		REP(m, N) {
			if (m) {
				string AND;
				if (!(iss >> AND)) {
					break;
				}

				assert(AND == "and");
			}

			number num;
			string organName;
			iss >> num >> organName;
			mat[organs.getIndex(organName)][animalIndex] = num;
		}
	}

	string there, are;
	cin >> there >> are;
	assert(there == "There");
	assert(are == "are");
	REP(n, N) {
		if (n) {
			string AND;
			if (!(cin >> AND)) {
				break;
			}

			assert(AND == "and");
		}

		number num;
		string organName;
		cin >> num >> organName;
		a[organs.getIndex(organName)] = num;
	}

	const LUinfo lu = LU_decomposition(mat);
	const array x = LU_backsubstitution(lu, a);

	vector<pair<string, ll> > answers;
	REP(n, N) {
		answers.push_back(make_pair(animals.getName(n), (ll)(x[n] + 0.5)));
	}
	sort(ALL(answers));

	REP(n, N) {
		cout << answers[n].first << ": " << answers[n].second << endl;
	}
}

LU分解 http://www.prefield.com/algorithm/math/LU.html

Problem C 10168 And then there were ...

  • ああ・・・ううんと・・・
  • 探索くらいしか思いつかないけど・・・
  • 書くのも面倒だしTLE怖いし・・・
  • パス!

Problem D 10169 北海道のレストラン

  • 全点間最短距離をワシャフロ(ワーシャル・フロイド法)して終わりだよね?
  • submit
    • Wrong Answer
  • な・・・なんだって・・・!?
  • これが噂のさいたまトラップか!?
  • とりあえず問題文を隅々まで読んでみる
  • ・・・
  • 店長・・・?
    • 勤続100年?
    • 本店は1番?
      • これか・・・
  • 修正
  • submit
    • Wrong Answer
  • な・・・なんだって・・・!?
  • long longに直せば通るかなぁ
  • submit
    • Wrong Answer
  • な・・・なんだって・・・!?
  • ・・・
  • もしかしてグラフに二重辺があったりする?
  • submit
    • Acceted
int main() {
	// なんだって!?
	// 店長は本店勤務で勤続100年だって!?
	for (int N, M; scanf("%d%d", &N, &M), (N || M); ) {
		// オーバーフローに対応した
		static ll g[128][128];
		fill_n((ll*)g, sizeof(g) / sizeof(ll), INT_MAX);
		REP(n, N) {
			g[n][n] = 0;
		}

		static int r[128];
		static int y[128];
		REP(m, M) {
			scanf("%d%d", &r[m], &y[m]);
			--r[m];
		}

		int E;
		scanf("%d", &E);
		REP(e, E) {
			int s, t, w;
			scanf("%d%d%d", &s, &t, &w);
			--s;
			--t;
			// 複数のエッジに対応する
			g[s][t] = min(g[s][t], (ll)w);
			g[t][s] = min(g[t][s], (ll)w);
		}

		REP(k, N) {
			REP(i, N) {
				REP(j, N) {
					g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
				}
			}
		}

		// int溢れない?
		vector<int> bestRestaurants;
		ll bestCost = INT_MAX;
		REP(n, N) {
			ll cost = 0;
			cost += g[0][n] * 100;
			REP(m, M) {
				cost += g[r[m]][n] * y[m];
			}

			if (bestCost > cost) {
				bestCost = cost;
				bestRestaurants.clear();
				bestRestaurants.push_back(n + 1);
			} else if (bestCost == cost) {
				bestRestaurants.push_back(n + 1);
			}
		}

		// 1足すのを忘れない
		REP(i, bestRestaurants.size()) {
			if (i) {
				putchar(' ');
			}
			printf("%d", bestRestaurants[i]);
		}
		puts("");
	}
}

Problem E 10170 ガンマン対決

  • これライブアライブの西部編?
  • とりあえずゲーム木探索をするだけに見える
  • そして自分はゲーム木探索がまともに書けたことがない!
  • パス!

Problem F 10172 Rectangle^2

  • 数式ゴリゴリするだけだよね・・・?
  • でも数式面倒くさいよね・・・。
  • 他に解ける問題あるよね・・・?
  • パス・・・

Problem G 10174 Arithmetic Geometric Sequence

  • 頭使う問題か・・・
  • m=0と1の時は別処理が必要
  • 残りをどうするか・・・
  • こういう時はきっと二分探索するんだよね・・・
  • ある数i以下の数の個数は求められないかな?
  • それぞれの数列について求めて足すとTLEしそう・・・
  • 数列を並べて縦方向に見たらどうだろう
  • 0乗、1乗、2乗と見ていくと個数は割り算と対数で求められそう
  • long longのオーバーフロー怖いからlong double使っておく
  • submit
    • Accepted
ll f(ll m, ll target) {
	// オーバーフロー注意
	long double value = 1;
	ll result = 0;
	while (value < target + 0.5) {
		result += (ll)(target / value);
		value *= m;
	}
	return result;
}

int main() {
	int T;
	cin >> T;
	REP(t, T) {
		ll m, x;
		cin >> m >> x;
		if (m == 0) {
			cout << 0 << endl;
			continue;
		} else if (m == 1) {
			cout << 1 << endl;
			continue;
		}

		// 整数用二分探索
		ll L = 0;
		ll R = 1LL << 62;
		while (L + 1 < R){
			ll M = (L + R) / 2;
			if (f(m, M) < x){
				L = M;
			} else {
				R = M;
			}
		}

		cout << L + 1 << endl;
	}
}

Problem H 10166 Best Route

  • ポイントが最大になればいいんだよね?(<-間違い)
  • ダイクストラと幅優先探索組み合わせればよくね?
  • 書いた・・・
  • submit
    • Wrong Answer
  • 何か間違ったのかなぁ
  • ・・・
  • 移動回数最小の中でポイント最大化?
  • 書きなおしてみる
  • ・・・
  • なんか手元のテストケースと答えが合わない
  • 間に合わないorz

Problem I 10175 ブロックタワー

  • 面倒そうなのでパス

Problem J 10176 ORIGINAL NECKLACE

  • 編集距離のコストを変えるだけじゃね?
  • どの宝石を操作するかはトラックバックすればいい
  • submit
    • Accepted
struct Dictionary {
	map<string, int> nameToIndex;
	vector<string> indexToMap;
	int getIndex(const string& name) {
		map<string, int>::iterator it = nameToIndex.find(name);
		if (it != nameToIndex.end()) {
			return it->second;
		} else {
			const int index = nameToIndex.size();
			nameToIndex[name] = index;
			indexToMap.push_back(name);
			return index;
		}
	}
	const string& getName(int index) const {
		return indexToMap[index];
	}
};

enum {
	None,
	Insert,
	Delete
};

int main() {
	int N;
	ll C;
	while (cin >> N >> C && (N || C)) {
		Dictionary dic;
		vector<ll> costs;
		REP(n, N) {
			string name;
			ll cost;
			cin >> name >> cost;
			dic.getIndex(name);
			costs.push_back(cost);
		}

		int A;
		cin >> A;
		vector<int> a;
		REP(i, A) {
			string name;
			cin >> name;
			a.push_back(dic.getIndex(name));
		}

		int B;
		cin >> B;
		vector<int> b;
		REP(i, B) {
			string name;
			cin >> name;
			b.push_back(dic.getIndex(name));
		}

		static ll d[1024][1024];
		static int mode[1024][1024];
		d[0][0] = 0;
		mode[0][0] = None;

		// 取り外す
		for (int i = 1; i <= a.size(); ++i) {
			d[i][0] = d[i - 1][0] + costs[a[i - 1]] / 2;
			mode[i][0] = Delete;
		}

		// 挿入
		for (int j = 1; j <= b.size(); ++j) {
			d[0][j] = d[0][j - 1] + costs[b[j - 1]];
			mode[0][j] = Insert;
		}

		for (int i = 1; i <= a.size(); ++i) {
			for (int j = 1; j <= b.size(); ++j) {
				// 取り外す
				d[i][j] = d[i - 1][j] + costs[a[i - 1]] / 2;
				mode[i][j] = Delete;

				// 挿入
				if (d[i][j] > d[i][j - 1] + costs[b[j - 1]]) {
					d[i][j] = d[i][j - 1] + costs[b[j - 1]];
					mode[i][j] = Insert;
				}

				// 抜かさない
				if (a[i - 1] == b[j - 1]) {
					if (d[i][j] > d[i - 1][j - 1]) {
						d[i][j] = d[i - 1][j - 1];
						mode[i][j] = None;
					}
				}
			}
		}

		const ll finalCost = d[a.size()][b.size()];
		if (finalCost < C) {
			cout << finalCost << endl;

			vector<int> modes;
			vector<int> aIndexes;
			vector<int> bIndexes;
			int lastAIndex = a.size();
			int lastBIndex = b.size();
			do {
				assert(lastAIndex >= 0);
				assert(lastBIndex >= 0);

				modes.push_back(mode[lastAIndex][lastBIndex]);
				aIndexes.push_back(lastAIndex);
				bIndexes.push_back(lastBIndex);

				switch (mode[lastAIndex][lastBIndex]) {
				case None:
					--lastAIndex;
					--lastBIndex;
					break;
				case Insert:
					--lastBIndex;
					break;
				case Delete:
					--lastAIndex;
					break;
				}
			} while (lastAIndex != 0 || lastBIndex != 0);

			reverse(ALL(modes));
			reverse(ALL(aIndexes));
			reverse(ALL(bIndexes));

			int currentIndex = 1;
			REP(i, modes.size()) {
				const int mode = modes[i];
				const int aIndex = aIndexes[i];
				const int bIndex = bIndexes[i];
				
				switch (mode) {
				case None:
					{
						++currentIndex;
						break;
					}
				case Insert:
					{
						cout << "Insert " << currentIndex << " " << dic.getName(b[bIndex - 1]) << endl;
						++currentIndex;
						break;
					}
				case Delete:
					{
						cout << "Delete " << currentIndex << endl;
						break;
					}
				default:
					assert(false);
					break;
				}
			}

		} else {
			cout << "Reasonable" << endl;
		}

		cout << endl;
	}
}

結果

RankACPenaltyProblem AProblem BProblem CProblem DProblem EProblem FProblem GProblem HProblem IProblem J
2565600:20 (1)02:21 (2)(1)01:14 (4)01:38 (0)(3)03:03 (0)

全体で6位、公式参加で2位という好成績でした。

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