初回 -> はじめに
ABC104を解きました。
3完です！
C問題はコンテスト時間を過ぎて解きました。
| 問題 | 時間 | アルゴリズム | 実行時間 |
|---|---|---|---|
| A | 2min | - | 8ms |
| B | 13min | - | 8ms |
| C | 102min | bit全探索+貪欲法 | 5ms |
まとめ
先にまとめを載せます。これ自体は最後に書いてます。
char型は内部では文字コードを数値で持っているので、その性質を小文字の判定に使えます。
C問題は2種類のアルゴリズムを組み合わせる問題ですね。
実はknapsackライクのDPでも解けて、初めはDPで解きました。
ですが、bit全探索を使うほうが単純で実行速度も速いのでこちらを載せます。
はじめから思いつきたかった。
DPの練習ができたのでいいということにします。。。
A - Rated for Me
int r;
cin >> r;
if (r < 1200) cout << "ABC";
else if (r < 2800) cout << "ARC";
else cout << "AGC";
入力値が1200未満・2800未満・それ以上の3通りを調べれば答えがわかります。
B - AcCepted
string s;
cin >> s;
bool ok = (s[0] == 'A');
int cnt = 0;
for(int i = 1; i < s.length(); ++i)
{
if (s[i] == 'C') cnt += ((2 <= i && i <= s.length() - 2) ? 1 : 2);
else ok &= ((int)'a' <= (int)s[i] && (int)s[i] <= (int)'z');
}
ok &= (cnt == 1);
cout << (ok ? "AC" : "WA");
1文字目がAかどうかを判定
2文字目以降にCが来たら「何文字目か」と「これまでに出たCの個数」を判定
2文字目以降にC以外が来たら小文字かどうかを判定
で答えがわかります。
char型は内部では文字コードを数値で持っているので、その性質を小文字の判定に使いました。
C - All Green
int d, g, p_input, c_input;
cin >> d >> g;
g /= 100;
vector<int> point(d);
vector<int> comp(d);
for(int i = 0; i < d; ++i)
{
cin >> p_input >> c_input;
c_input /= 100;
point[i] = p_input;
comp[i] = p_input * (i + 1) + c_input;
}
int mask = 1 << d;
int ans = INF;
while(mask--, mask >= 0)
{
int score = 0;
int cost = 0;
for(int i = 0; i < d; ++i)
{
if ((mask & (1 << i)) == 0) continue;
score += comp[i];
cost += point[i];
}
if (score >= g)
{
ans = min(ans, cost);
continue;
}
for(int i = d - 1; i >= 0; --i)
{
if(mask & (1 << i)) continue;
int rest = (g - score) / (i + 1);
score += min(rest, point[i] - 1) * (i + 1);
cost += min(rest, point[i] - 1);
if (score >= g)
{
ans = min(ans, cost);
break;
}
}
}
cout << ans;
各難易度の問題をコンプリートすると追加点がもらえます。
追加点がなければただの貪欲法なのですが、追加点があることで複雑になっています。
そこで、コンプリートする場合としない場合とで分けます。
コンプリートするかしないかをbit全探索をして、しない難易度の問題を貪欲法で解きます。
全探索は $O(2\ ^n)$ ですが、問題の難易度は最大で10通りなので計算が間に合います。
コンプリートによるスコアと解いた問題数を記憶した後、解いていない難易度について貪欲法に入ります。
点数の高い方からコンプリート1問手前まで問題を解いて、目標スコアを超えた時点での解いた問題数がわかります。
これを $2\ ^d$ 回続けて、最小となった問題数が答えです。
以上です。ありがとうございました。