hotpepsiの練習帳

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。複雑な木で持たないといけないかと思ったが、場合わけしてみると結果的にはすごく単純で良かった。

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