Codeforces 909 問題解説
問題URL
A B C D E F 難易度：赤 黄 緑 青 緑 紫
解説
A
問題概要：2つの文字列が与えられる。非空の接頭辞を連結した文字列の中で辞書順最小のものを求める。
アルゴリズムラベル：貪欲
解法分析： 辞書順比較は左から順に文字を比較し、どちらかが終了するか異なる文字が見つかるまで続ける。このため、貪欲法が有効。前後の文字列の接頭辞を比較しながら、小さい方を優先的に選ぶ。 コードは省略。
B
問題概要： nを入力すると、n(n+1)/2個の区間が生成される。これらの区間を並べ替えることで、重ならないように結合できる最小の区間数を求める。
アルゴリズムラベル：数学、構築、貪欲
解法分析： いくつかのアプローチがある。
- パターン発見（方法1） 答えをnの関数として表すと、以下のようになる： 0, 1, 2, 4, 6, 9, … 答えはfloor((n+1)/2) * ceil((n+1)/2)で表される。
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
n++;
cout << (n/2) * ((n+1)/2) << endl;
return 0;
}
- パターン発見（方法2） 再帰式f_i = 2f_{i-1} - 2f_{i-3} + f_{i-4}が成り立つ。
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
if (n == 1) puts("1");
else if (n == 2) puts("2");
else if (n == 3) puts("4");
else if (n == 4) puts("6");
else {
int a = 1, b = 2, c = 4, d = 6, e;
n -= 4;
while (n--) {
e = 2*d - 2*b + a;
a = b;
b = c;
c = d;
d = e;
}
printf("%d\n", d);
}
return 0;
}
- 証明： 各区間[i, i+1]をカバーする区間数は(i+1)(n-i)。最大値が層数の下限となる。 答えは(floor(n/2)+1) * ceil(n/2)。
C
問題概要： Python風のコード（printとforのみ）が与えられる。合法なインデントのパターン数を1e9+7で求める。
アルゴリズムラベル：動的計画法
解法分析： dp[i][j]をi行目のインデントレベルjのパターン数とする。 for文の場合は前のレベルから+1、print文の場合は任意のレベルから遷移可能。
#include <bits/stdc++.h>
using namespace std;
int dp[5010][5010], sum[5010], n, cnt = 0;
string s, lst;
const int mod = 1e9 + 7;
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> s;
lst = s;
dp[1][0] = 1;
for (int i = 2; i <= n; i++) {
cin >> s;
if (lst == "f") {
for (int j = 1; j <= i; j++) {
dp[i][j] = dp[i-1][j-1];
}
} else {
for (int j = i; j >= 0; j--) {
dp[i][j] = (dp[i][j+1] + dp[i-1][j]) % mod;
}
}
lst = s;
}
int ans = 0;
for (int i = 0; i <= n; i++) ans = (ans + dp[n][i]) % mod;
cout << ans << "\n";
return 0;
}
D
問題概要： 直線上に配置された点が与えられる。各操作で、少なくとも1つの隣接点が異なる色を持つ点を削除する。操作回数を求める。
アルゴリズムラベル：最適化された暴力法
解法分析： 同じ色の区間を圧縮し、各操作で端点を削除する。
#include <bits/stdc++.h>
using namespace std;
string s;
int a[1000010], cnt = 1;
char c[1000010];
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> s;
a[1] = 1; c[1] = s[0];
for (int i = 1; i < s.size(); i++) {
if (s[i] == s[i-1]) {
a[cnt]++;
} else {
a[cnt+1] = 1;
c[cnt+1] = s[i];
cnt++;
}
}
int ans = 0;
while (cnt > 1) {
for (int i = 1; i <= cnt; i++) {
if (i == 1 || i == cnt) a[i]--;
else a[i] -= min(2, a[i]);
}
int tmp = 0;
for (int i = 1; i <= cnt; i++) {
if (a[i] == 0) continue;
if (c[i] == c[tmp]) c[tmp] += c[i];
else {
tmp++;
c[tmp] = c[i];
a[tmp] = a[i];
}
}
ans++;
cnt = tmp;
}
cout << ans << '\n';
return 0;
}
E
問題概要： （解説なし）
F
問題概要： （解説なし）