Hatena::Grouptopcoder

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

 | 

2015-03-07

AtCoder Regular Contest 035 22:50 AtCoder Regular Contest 035 - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - AtCoder Regular Contest 035 - nodchipのTopCoder日記 AtCoder Regular Contest 035 - nodchipのTopCoder日記 のブックマークコメント

A - 高橋くんと回文

  • やるだけ
  • と思ったらOnlineJudgeHelperが動かない・・・
  • デバッグしようとしたらeclipseにPyDev入ってなかった
  • 急いでPyDevを入れる
  • 今度はPythonのインタプリタが入ってなかった
  • インタプリタを入れる
  • デバッグ実行してみる
  • ログイン処理ができてない・・・
  • なぜだぁorz
  • しょうがないので手動で頑張る
  • AC
bool isPari(const string& S) {
	for (int l = 0, r = S.size() - 1; l < r; ++l, --r) {
		if (S[l] == S[r] ||
			S[l] == '*' ||
			S[r] == '*') {
			continue;
		}
		return false;
	}
	return true;
}

int main() {
	std::ios::sync_with_stdio(false);

	string S;
	cin >> S;

	cout << (isPari(S) ? "YES" : "NO") << endl;
}

B - アットコーダー王国のコンテスト事情

  • 時間の小さいものから順番に解いていけばいい
  • 同じ時間で解ける問題がk問ある場合は、k!通りの解き方があるので掛けていく
  • AC
const int MOD = 1000000007;

int main() {
	std::ios::sync_with_stdio(false);

	int N;
	cin >> N;
	static ll T[16 * 1024];
	map<int, int> bucket;
	REP(n, N) {
		cin >> T[n];
		++bucket[T[n]];
	}

	sort(T, T + N);
	ll sum = 0;
	ll passed = 0;
	REP(n, N) {
		passed += T[n];
		sum += passed;
	}
	cout << sum << endl;

	static ll bikkuri[16 * 1024];
	bikkuri[0] = 1;
	for (int i = 1; i < 16 * 1024; ++i) {
		bikkuri[i] = bikkuri[i - 1] * i % MOD;
	}

	ll ans = 1;
	for (const auto& p : bucket) {
		ans *= bikkuri[p.second];
		ans %= MOD;
	}

	cout << ans << endl;
}

C - アットコーダー王国の交通事情

  • N≦400とあるからワーシャルフロイドっぽい気がする
  • 多分XとYの間の距離を更新したときに部分的に更新すればよいのだと思う
  • とありあえず書いてみる
  • サンプルは合った
  • 出してみる
  • WA
  • ・・・
  • 4テストケースだけ通ってない
  • 64bit整数にしてみる
  • AC
  • ・・・?
  • 32bit超えないはずなのになぜ・・・?
int main() {
	std::ios::sync_with_stdio(false);

	int N, M;
	cin >> N >> M;
	static ll g[512][512];
	REP(i, 512) REP(j, 512) {
		g[i][j] = INT_MAX / 3;
	}
	REP(i, 512) {
		g[i][i] = 0;
	}

	REP(m, M) {
		int A, B, C;
		cin >> A >> B >> C;
		--A;
		--B;
		g[A][B] = g[B][A] = C;
	}

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

	ll sum = 0;
	REP(i, N) REP(j, i) {
		sum += g[i][j];
	}

	int K;
	cin >> K;
	REP(k, K) {
		int X, Y, Z;
		cin >> X >> Y >> Z;
		--X;
		--Y;
		if (g[X][Y] <= Z) {
			cout << sum << endl;
			continue;
		}

		sum -= g[X][Y];
		sum += Z;
		g[X][Y] = g[Y][X] = Z;

		// i -> X -> j
		REP(i, N) REP(j, i) {
			ll current = g[i][j];
			ll updated = g[i][X] + g[X][j];
			if (current > updated) {
				sum -= current - updated;
				g[i][j] = g[j][i] = updated;
			}
		}

		// i -> Y -> j
		REP(i, N) REP(j, i) {
			ll current = g[i][j];
			ll updated = g[i][Y] + g[Y][j];
			if (current > updated) {
				sum -= current - updated;
				g[i][j] = g[j][i] = updated;
			}
		}

		cout << sum << endl;
	}
}

D - 高橋くんとマラソンコース

  • これ対数取ればいいのかなぁ?
  • 経路の数は{}_{a+b}C_{a}とかだった気がするので対数を取れば足し引きで計算できる
  • 最後はBIT的な何かでやれば良さそう
  • 時間切れ
  • 試しに書いてみる
  • サンプルが通らないorz
  • あれれ・・・

結果

順位ユーザ名高橋くんと回文アットコーダー王国のコンテスト事情アットコーダー王国の交通事情高橋くんとマラソンコース得点 / Total
81 nodchip 100 19:18 100 27:42 100 (3) 76:47 - 300 (3) 91:47

競技プログラミング業界のレベル上がり過ぎなのでは・・・?

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