Hatena::Grouptopcoder

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

|

2015-05-09

AtCoder Beginner Contest 023 23:00 AtCoder Beginner Contest 023 - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - AtCoder Beginner Contest 023 - nodchipのTopCoder日記 AtCoder Beginner Contest 023 - nodchipのTopCoder日記 のブックマークコメント

A - 加算王

  • 割って足す
int main() {
	std::ios::sync_with_stdio(false);
	int N;
	cin >> N;
	cout << (N / 10 + N % 10) << endl;
}

B - 手芸王

  • 中央から左右に向けて規則通りになっているかどうかを調べる
  • for文1つ省けた
const string ABC = "abc";

bool check(const string& s) {
	if (s.size() % 2 == 0) {
		return false;
	}

	for (int i = 0; i >= -(int)(s.size() / 2); --i) {
		if (s[s.size() / 2 + i] != ABC[(i + 301) % 3]) {
			return false;
		}
	}
	for (int i = 0; i <= (int)(s.size() / 2); ++i) {
		if (s[s.size() / 2 + i] != ABC[(i + 301) % 3]) {
			return false;
		}
	}
	return true;
}

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

	int N;
	cin >> N;
	string S;
	cin >> S;
	if (check(S)) {
		cout << S.size() / 2 << endl;
	}
	else {
		cout << -1 << endl;
	}
}

C - 収集王

  • 各行各列にアメが何個置かれているかを調べ、個数を足してKとなる行と列の組み合わせをまとめて求める
  • これだけだとアメの置いてある場所の計算が合わないので、つじつま合わせで足し引きする
int main() {
	std::ios::sync_with_stdio(false);

	int R, C, K, N;
	cin >> R >> C >> K >> N;
	static int rs[1024 * 1024];
	static int cs[1024 * 1024];
	static int rCounter[1024 * 1024];
	static int cCounter[1024 * 1024];
	REP(i, N) {
		cin >> rs[i] >> cs[i];
		++rCounter[rs[i]];
		++cCounter[cs[i]];
	}

	map<int, ll> counterToNumR;
	map<int, ll> counterToNumC;
	REP(r, R) {
		++counterToNumR[rCounter[r + 1]];
	}
	REP(c, C) {
		++counterToNumC[cCounter[c + 1]];
	}

	ll answer = 0;
	REP(k, K + 1) {
		answer += counterToNumR[k] * counterToNumC[K - k];
	}

	REP(n, N) {
		int r = rs[n];
		int c = cs[n];
		if (rCounter[r] + cCounter[c] == K) {
			--answer;
		}
		if (rCounter[r] + cCounter[c] == K + 1) {
			++answer;
		}
	}

	cout << answer << endl;
}

D - 射撃王

  • 答えで二分探索
  • 仮の答えで辻褄が合うかどうかは、ぎりぎりの高さになるまでの時間をそれぞれ調べて、スケジューリングできるかどうかを調べる。
int N;
ll H[1024 * 1024];
ll S[1024 * 1024];

bool check(ll answer) {
	static ll times[1024 * 1024];
	REP(n, N) {
		times[n] = (answer - H[n]) / S[n];
		while (times[n] * S[n] + H[n] > answer) {
			--times[n];
		}
	}

	sort(times, times + N);

	REP(n, N) {
		if (times[n] < n) {
			return false;
		}
	}
	return true;
}

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

	cin >> N;
	REP(n, N) {
		cin >> H[n] >> S[n];
	}

	// 整数用二分探索
	ll L = 0;
	ll R = 1LL << 60;
	while (L + 1 < R){
		ll M = (L + R) / 2;
		if (check(M)){
			R = M;
		}
		else {
			L = M;
		}
	}

	while (!check(L)) {
		++L;
	}

	cout << L << endl;
}

結果

順位ユーザ名加算王手芸王収集王射撃王得点 / Total
22nodchip100 01:21100 09:34100 29:52100 (2) 58:01400 (2) 68:01
トラックバック - http://topcoder.g.hatena.ne.jp/nodchip/20150509

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

2015-01-24

Single Round Match 647 Div 1 03:49 Single Round Match 647 Div 1 - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - Single Round Match 647 Div 1 - nodchipのTopCoder日記 Single Round Match 647 Div 1 - nodchipのTopCoder日記 のブックマークコメント

Easy 250 BuildingTowersEasy

  • 前と後から1ずつ高さを増やしていくのでは・・・。
  • Passed System Test
class BuildingTowersEasy {
public:
	int maxHeight(int N, vector <int> x, vector <int> t) {
		map<int, int> restrictions;
		REP(i, x.size()) {
			restrictions[x[i]] = t[i];
		}

		vector<int> heights(N + 1);
		for (int n = 2; n <= N; ++n) {
			heights[n] = heights[n - 1] + 1;
			if (restrictions.count(n)) {
				MIN_UPDATE(heights[n], restrictions[n]);
			}
		}

		for (int n = N - 1; n >= 1; --n) {
			MIN_UPDATE(heights[n], heights[n + 1] + 1);
		}

		return *max_element(ALL(heights));
	}
};

Medium 500 CtuRobots

  • とりあえずあるロボットの集合が与えられたときに最も遠くまで行く戦略は・・・
  • capの昇順に並べて一番手前のやつが他のやつ全員に燃料を分け与えるパターン? (←間違い)
  • とりあえずその部分を書いてみる
  • 答えが合わなかった・・・
  • ・・・

hard 1000 ConvenientBlock

  • 最小カットかな?
  • 書いてみる
  • 答えが合わない・・・

Challenge Phase

  • とりあえず250をさらっと見ていく
  • ・・・
  • 読めない・・・
  • 26:00にコードリーディングとか無理ゲー
  • 諦めよう

System Test

oxx 222.61pts 133位 1870→1892 レーティング相当の順位だったようです。

dwangoプログラミングコンテスト dwangoからの『挑戦状』 予選 22:19 dwangoプログラミングコンテスト dwangoからの『挑戦状』 予選 - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - dwangoプログラミングコンテスト dwangoからの『挑戦状』 予選 - nodchipのTopCoder日記 dwangoプログラミングコンテスト dwangoからの『挑戦状』 予選 - nodchipのTopCoder日記 のブックマークコメント

A - プレミアム会員

  • やるだけ
  • AC
int main() {
	std::ios::sync_with_stdio(false);

	int n, x;
	cin >> n >> x;
	cout << 540 * x + 525 * (n - x) << endl;
}

B - ニコニコ文字列

  • 部分文字列って飛び飛びになっても良い方だっけ? (←間違い)
  • だとするとdp[2][|S|]だよなぁ・・・
  • 書いてみる
  • 答え合わない
  • 飛び飛びにならない方か・・・
  • なら文字カウントするだけか
  • AC
int main() {
	std::ios::sync_with_stdio(false);

	string S;
	cin >> S;
	ll answer = 0;
	ll n = 0;
	for (char ch : S) {
		if (ch == '2') {
			if (n % 2 == 0) {
				++n;
			}
			else {
				n /= 2;
				answer += n * (n + 1) / 2;
				n = 1;
			}
		}
		else if (ch == '5') {
			if (n % 2 == 1) {
				++n;
			}
			else {
				n /= 2;
				answer += n * (n + 1) / 2;
				n = 0;
			}
		}
		else {
			n /= 2;
			answer += n * (n + 1) / 2;
			n = 0;
		}
	}

	n /= 2;
	answer += n * (n + 1) / 2;
	n = 0;

	cout << answer << endl;
}

C - ゲーマーじゃんけん

  • ああ、これは期待値をメモ探するだけの私が解けない問題ですね。
  • とりあえず取り組んでは見る
  • f(n)をメモ探で書けばいいはずだけど、無限ループする場合があるのでそこをどうにかしないといけなかったはず
  • 確か移行するとか何とかだった気がする。
  • f(n) = \sum^{n}_{i=1} w(i) * (f(i) + 1.0) の形になるはずで、右辺のf(n)を左辺に持ってくればいいのかな?
  • W = \sum^{n-1}_{i=1} w(i) * (f(i) + 1.0) と置いて、f(n) = (W + w(n)) / (1.0 - w(n)) だそうだ
  • っていうかw(i)ってどうやって計算するんだっけ・・・
  • (|グー|+|チョキ|+|パー|)!/|グー|!/|チョキ|!/|パー|! か。高校時代にやった気がする。
  • へぇ
  • とりあえず書いてみる
  • AC
double dp[128];
double fact[128];

double hoge(int a, int b, int c) {
	return fact[a + b + c] / fact[a] / fact[b] / fact[c];
}

double dfs(int N) {
	if (N == 1) {
		return 0.0;
	}

	double& r = dp[N];
	if (r != -1.0) {
		return r;
	}

	double weight[128];
	CLEAR(weight);
	vector<int> hands;
	for (int g = 0; g <= N; ++g) {
		for (int c = 0; c + g <= N; ++c) {
			int p = N - g - c;

			vector<int> hands;
			if (g) {
				hands.push_back(g);
			}
			if (c) {
				hands.push_back(c);
			}
			if (p) {
				hands.push_back(p);
			}
			sort(ALL(hands));

			if (hands.size() == 1) {
				weight[N] += 1.0;
			}
			else {
				int rare = hands[0];
				switch (count(ALL(hands), rare)) {
				case 1:
					weight[hands[0]] += hoge(g, c, p);
					break;
				case 2:
					weight[hands[0]] += hoge(g, c, p);
					break;
				case 3:
					weight[N] += hoge(g, c, p);
					break;
				}
			}
		}
	}

	double sum = accumulate(weight, weight + N + 1, 0.0);
	REP(i, N + 1) {
		weight[i] /= sum;
	}

	double p = 0.0;
	for (int n = 1; n < N; ++n) {
		p += weight[n] * (dfs(n) + 1.0);
	}

	double w = weight[N];
	r = (p + w) / (1.0 - w);

	return r;
}

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

	fill_n(dp, sizeof(dp) / sizeof(dp[0]), -1.0);
	fact[0] = 1.0;
	for (int i = 1; i < 128; ++i) {
		fact[i] = fact[i - 1] * i;
	}

	int N;
	cin >> N;
	double r = dfs(N);
	printf("%.20f\n", r);
}
  • これ系の問題久々に解けた気がする

D - タクシー

  • とりあえず全員時計回りに移動させて、適当に反時計回りに移動させ直せばいいんじゃないかな?
  • 反時計回りに移動させるときに1人ずつ移動させずに複数人まとめて移動させることもできそう。
  • とりあえず書いてみる。
  • RE 15
  • ありゃ・・・
  • バケツソートを配列でやったところで死んでる。
  • これをmapで書き直せば・・・
  • ・・・
  • サンプル通らなくなった
  • 時間切れorz
int main() {
	std::ios::sync_with_stdio(false);
 
	int N, L;
	cin >> N >> L;
	static ll a[128 * 1024];
	static ll b[128 * 1024];
	static ll c[128 * 1024];
	CLEAR(a);
	CLEAR(b);
	CLEAR(c);
	REP(n, N) {
		cin >> a[n] >> b[n] >> c[n];
		ll sub = MIN(b[n], c[n]);
		b[n] -= sub;
		c[n] -= sub;
	}
	a[N] = L;
 
	// index番目の都市から時計回りに何人移動するか?
	static ll initialMoving[128 * 1024];
	CLEAR(initialMoving);
	ll moving = 0;
	REP(n, N * 2) {
		int index = n % N;
 
		int out = MIN(c[index], moving);
		moving -= out;
		c[index] -= out;
 
		moving += b[index];
		b[index] = 0;
 
		initialMoving[index] += moving;
	}
 
	map<ll, ll> initialMovingToCost;
	REP(n, N) {
		initialMovingToCost[initialMoving[n]] += a[n + 1] - a[n];
	}
 
	// [人数] = cost
	static ll bucket[128 * 1024];
	CLEAR(bucket);
	ll current = 0;
	for (const auto& movingToCost : initialMovingToCost) {
		bucket[movingToCost.first] = movingToCost.second;
		current += movingToCost.first * movingToCost.second;
	}
 
	static ll sumToLower[128 * 1024];
	CLEAR(sumToLower);
	sumToLower[0] = bucket[0];
	for (int n = 1; n < 128 * 1024; ++n) {
		sumToLower[n] = sumToLower[n - 1] + bucket[n];
	}
 
	static ll sumToUpper[128 * 1024];
	CLEAR(sumToUpper);
	sumToUpper[128 * 1024 - 1] = bucket[128 * 1024 - 1];
	for (int n = 128 * 1024 - 2; n >= 0; --n) {
		sumToUpper[n] = sumToUpper[n + 1] + bucket[n];
	}
 
	ll best = current;
	for (int n = 0; n < 128 * 1024 - 2; ++n) {
		current -= sumToUpper[n + 1];
		current += sumToLower[n];
		MIN_UPDATE(best, current);
	}
 
	cout << best << endl;
}

E - 電波局

  • よくわからないのでとりあえず10点だけ取っておく
  • WA 10
int main() {
	std::ios::sync_with_stdio(false);

	int N, M;
	cin >> N >> M;
	static bool houses[1024][1024];
	CLEAR(houses);

	REP(m, M) {
		int a, b, c;
		cin >> a >> b >> c;
		for (int j = 1; j <= c; ++j) {
			for (int k = 1; k <= j; ++k) {
				houses[a + j - 1][b + k - 1] = true;
			}
		}
	}

	int Q;
	cin >> Q;
	REP(q, Q) {
		int d, e, f;
		cin >> d >> e >> f;
		int counter = 0;
		for (int j = 1; j <= f; ++j) {
			for (int k = 1; k <= j; ++k) {
				if (!houses[d + j - 1][e + k - 1]) {
					++counter;
				}
			}
		}
		cout << counter << endl;
	}
}

結果

順位ユーザ名プレミアム会員ニコニコ文字列ゲーマーじゃんけんタクシー電波局得点 / Total
33nodchip100 01:26100 16:58100 52:4915 99:5110 72:23325 99:51
トラックバック - http://topcoder.g.hatena.ne.jp/nodchip/20150124

2015-01-19

Codeforces Round #286 (Div. 1) 09:28 Codeforces Round #286 (Div. 1) - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - Codeforces Round #286 (Div. 1) - nodchipのTopCoder日記 Codeforces Round #286 (Div. 1) - nodchipのTopCoder日記 のブックマークコメント

A. Mr. Kitayuta, the Treasure Hunter

  • 日本人writerとは聞いていたけど、ここまで露骨なタイトルをつけてくるとは・・・
  • ・・・
  • というか一問目からDP!?
  • かんべんして欲しい。
  • 見た感じdp[前回のジャンプ距離][総距離]だけど
  • 30000^2になるからそのままではダメ
  • 多分速度は√30000回くらいしか変わらないからdp[512][30000]すればよさそう
  • Accepted
static const int OFFSET = 256;
static const int INVALID = INT_MIN;

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

	int N, D;
	cin >> N >> D;
	static int gems[32 * 1024];
	CLEAR(gems);
	REP(n, N) {
		int p;
		cin >> p;
		++gems[p];
	}

	static int dp[OFFSET * 2][32 * 1024];
	fill_n((int*)dp, sizeof(dp) / sizeof(int), INVALID);
	dp[OFFSET][D] = gems[D];
	for (int d = 0; d < 30000; ++d) {
		for (int speedDelta = -OFFSET; speedDelta < OFFSET; ++speedDelta) {
			int speedIndex = speedDelta + OFFSET;
			int speed = D + speedDelta;
			if (dp[speedIndex][d] == INVALID) {
				continue;
			}

			for (int delta = -1; delta <= 1; ++delta) {
				int nextSpeed = speed + delta;
				if (nextSpeed == 0) {
					continue;
				}
				int nextSpeedDelta = nextSpeed - D;
				int nextSpeedIndex = nextSpeedDelta + OFFSET;
				int nextD = d + nextSpeed;
				if (nextD > 30000) {
					continue;
				}

				MAX_UPDATE(dp[nextSpeedIndex][nextD], dp[speedIndex][d] + gems[nextD]);
			}
		}
	}

	int bestAnswer = 0;
	for (int d = 0; d <= 30000; ++d) {
		for (int speed = 0; speed < OFFSET * 2; ++speed) {
			MAX_UPDATE(bestAnswer, dp[speed][d]);
		}
	}

	cout << bestAnswer << endl;
}

B. Mr. Kitayuta's Technology

  • なんだこれorz
  • 強連結成分分解してDAGの最長パス求めて距離が2以上離れたエッジを削除とかそんな感じ?
  • ・・・
  • 違うっぽい
  • じゃあ最小全域有向木とか?
  • 書いてみる
  • ・・・
  • Spaghetti Sourceのライブラリが動かないorz

C. Mr. Kitayuta vs. Bamboos

  • 分かりませんでした

D. Mr. Kitayuta's Colorful Graph

  • 分かりませんでした
  • なんでこんなに解けるんだろう

E. Mr. Kitayuta's Gift

  • 分かりませんでした

結果

#Who=A 500B 1000C 1750D 1750E 2500
243Japan nodchip472 472 00:14

1906->1951 少し上がりました。レーティングに幅が出ているからなのか、このくらいの順位でもレーティングが上がるようです。

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

2015-01-17

AtCoder Beginner Contest #017 23:00 AtCoder Beginner Contest #017 - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - AtCoder Beginner Contest #017 - nodchipのTopCoder日記 AtCoder Beginner Contest #017 - nodchipのTopCoder日記 のブックマークコメント

A - プロコン

  • やるだけ
int main() {
	std::ios::sync_with_stdio(false);

	int answer = 0;
	REP(i, 3) {
		int s, e;
		cin >> s >> e;
		answer += s * e / 10;
	}
	cout << answer << endl;
}

B - choku語

  • 先頭から見ていく
int main() {
	std::ios::sync_with_stdio(false);

	string X;
	cin >> X;
	int index = 0;
	while (index < X.size()) {
		if (X.substr(index).find("ch") == 0) {
			index += 2;
		}
		else if (X.substr(index).find("o") == 0) {
			++index;
		}
		else if (X.substr(index).find("k") == 0) {
			++index;
		}
		else if (X.substr(index).find("u") == 0) {
			++index;
		}
		else {
			break;
		}
	}

	cout << (index == X.size() ? "YES" : "NO") << endl;
}

C - ハイスコア

  • 特定の宝石を取らない時の最高得点を計算するのはO(N)
  • 宝石の種類で全部回してO(NM)
  • RE 100
  • 複数の宝石について「特定の宝石を取らない時の最高得点を計算する」を同時に行いたい
  • 多分BIT的な何かが必要になる気がする
  • BITのライブラリ持ってない・・・
  • どうしよう・・・
  • ネット上でBITライブラリが落ちてないかどうかググってみる
  • hos様の解説スライドが見つかった
  • 適当に読んでみる
  • ・・・
  • なんかimos法っぽいページが入ってる
  • ・・・
  • これimos法で行けるじゃん
  • AC 101
int main() {
	std::ios::sync_with_stdio(false);

	int N, M;
	cin >> N >> M;
	static ll imos[128 * 1024];
	ll sum = 0;
	REP(n, N) {
		int l, r, s;
		cin >> l >> r >> s;
		imos[l] += s;
		imos[r + 1] -= s;
		sum += s;
	}
	ll answer = 0;
	for (int i = 1; i <= M; ++i) {
		imos[i] += imos[i - 1];
		MAX_UPDATE(answer, sum - imos[i]);
	}

	cout << answer << endl;
}

D - サプリメント

  • 今見ている種類と同じ種類のサプリが出るまで足し合わせる・・・? (←間違い)
  • なんかWAが出る・・・
  • なんでだろう・・・
  • 計算量の大きい愚直な方法に切り替えてみる
  • まだWAが出る・・・
  • ・・・
  • これ、今見ている種類以外のサプリメントも考えないとダメ・・・?
  • ダメっぽいorz
  • 1ヶ所変えてみる
  • AC 100
  • 通った・・・
int main() {
	std::ios::sync_with_stdio(false);

	int N, M;
	cin >> N >> M;
	static ll f[128 * 1024];
	REP(n, N) {
		cin >> f[n];
	}

	static int flavorToLastIndex[128 * 1024];
	fill_n(flavorToLastIndex, sizeof(flavorToLastIndex) / sizeof(int), -1);
	static int lastSameFlavorIndex[128 * 1024];
	REP(n, N) {
		lastSameFlavorIndex[n] = flavorToLastIndex[f[n]];
		flavorToLastIndex[f[n]] = n;
	}

	static ll dp[128 * 1024];
	static ll dpSum[128 * 1024];
	dp[0] = 1;
	dpSum[0] = 1;
	int from = -1;
	REP(n, N) {
		dp[n + 1] = (dp[n + 1] + dpSum[n]) % MOD;
		MAX_UPDATE(from, lastSameFlavorIndex[n]);
		if (from != -1) {
			dp[n + 1] = (dp[n + 1] - dpSum[from] + MOD) % MOD;
		}
		dpSum[n + 1] = (dpSum[n] + dp[n + 1]) % MOD;
	}

	cout << dp[N] << endl;
}

結果

順位ユーザ名プロコンchoku語ハイスコアサプリメント得点 / Total
22nodchip100 01:09100 04:22101 (1) 67:37100 (3) 78:32401 (4) 98:32

なんとか4完できました。腕がかなりなまっているのを感じます・・・。

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