Hatena::Grouptopcoder

hotpepsiの練習帳

2011-12-21

Codeforces 98 Div2

02:42

A. Postcards and photos

問題

  • 2種類の文字からなる文字列を受け取る
  • 先頭から、連続する同じ種類かつ5文字以内の文字列を除去する
  • 最小手数を求める

方針

  • すごく短く書けそうだが...
  • ベタに書いた
  • 同じかつ5文字ならflush、違う文字ならflush、ループ終了後flush

B. Permutation

問題

  • 不完全な数列が与えられる
  • 1からnまで1ずつ単調増加する数列に直す最小手数を求める

方針

  • 最大5000しかないのでフラグで持ってしまってよい
for (i = 0; i < n; ++i) {
	f[x[i]] = 1;
}
int ans = n;
for (i = 1; i <= n; ++i) {
	ans -= f[i];
}

C. History

問題

  • 区間(開始年,終了年の組)の配列が与えられる
  • ある区間が別の区間に含まれている総数を求める

方針

  • std::pairで格納
  • 開始年でソート
  • ある区間iと、その次の区間jのみを見ればよい
  • 区間iの終了年より区間jの終了年が手前ならカウント+1
  • そうでなければiにjを代入
  • 区間jの開始年は区間iの開始年よりあとなので、終了年の判定だけでよい
  • 区間iより区間jの終了年がうしろならば、それよりあとの区間は区間iを判定に使わなくて良い
sort(x.begin(), x.end());
for (i = 0; i < (n-1); i = j) {
	for (j = i + 1; j < n; ++j) {
		if (x[j].second >= x[i].second) {
			break;
		}
		++ans;
	}
}

結果

oox-- 406+674=1080pt 586th rating 1568 -> 1493

CがTLE。複雑な木で持たないといけないかと思ったが、場合わけしてみると結果的にはすごく単純で良かった。

素直に書くのがなかなか難しい。

トラックバック - http://topcoder.g.hatena.ne.jp/firewood/20111221