A-small/large, B-small/large, C-small を解いて 75pt, 362位.
あっさり通過できてしまってんー?ってなった.
Problem A. Alphabet Cake
問題概要
のグリッドがあって, それぞれのマスは, 未知のマス ‘?’ かあるアルファベットで表される. アルファベットは種類ごとに高々 回しか出現しない.
‘?’ に上手くアルファベットを割り当てることにより, アルファベットの種類ごとに長方形の区画に分けたい.
割り当て方の一例を出力せよ.
解法
アルファベットが一文字以上存在する行を取り出してみて, その行の ‘?’ について適当に割り当てる.
??A??BB
のような感じであれば
AAABBBB
が一例である.
この操作を行うと, 各行はすべて ‘?’ かアルファベットで埋まっているかのどちらかになる.
あとはすべて ‘?’ の行について, 埋まってる行を適当にクローン(?) させればよい.
ソース
難しすぎる.
#include <bits/stdc++.h> using namespace std; void solve() { int H, W; string S[25]; cin >> H >> W; for(int i = 0; i < H; i++) { cin >> S[i]; } int appear[25] = {}; for(int i = 0; i < H; i++) { for(int j = 0; j < W; j++) { if(S[i][j] != '?') appear[i] = true; } } for(int i = 0; i < H; i++) { for(int j = 0; j < W; j++) { if(S[i][j] == '?') { if(appear[i]) { for(int k = j - 1; k >= 0; k--) { if(S[i][k] != '?') { S[i][j] = S[i][k]; break; } } for(int k = j + 1; k < W; k++) { if(S[i][k] != '?') { S[i][j] = S[i][k]; break; } } } } } } for(int i = 0; i < H; i++) { if(S[i][0] == '?') { if(i > 0 && S[i - 1][0] != '?') { for(int k = 0; k < W; k++) { S[i][k] = S[i - 1][k]; } } } } for(int i = H - 1; i >= 0; i--) { if(S[i][0] == '?') { if(i != H - 1 && S[i + 1][0] != '?') { for(int k = 0; k < W; k++) { S[i][k] = S[i + 1][k]; } } } } for(int i = 0; i < H; i++) { cout << S[i] << endl; } } int main() { int T; cin >> T; for(int i = 1; i <= T; i++) { cout << "Case #" << i << ":" << endl; solve(); } }
Problem B. Ratatouille
問題概要
種類の具材がある.
各具材について 種類のパッケージが つずつあって, それぞれの量は である.
個のパッケージから つずつのパッケージをとってきて料理をつくる. 何人前の料理でもかまわないが, 種類ごとに 人前の具材の量は の 90 % から 110% の範囲である必要がある.
これを セットとして数える.
最大で何セット作れるか求めよ.
解法
結論からいうと 人前の料理を作れるかどうかを, が小さい順に貪欲に作っていけば良い(なんでだろうね).
小さい方からとっていけば, こういうのはだいたい成り立つ(成り立たなかったら諦める).
人前の料理を作れるかという処理は, それぞれの から適正な具材の量(±10%) を計算できるので, その範囲に収まるパッケージがあればそのうち最小のものをとっていけばよい.
ソース
かなり読解に苦労した(30分くらい誤読して ?? ってなってた). 英語は難しいね.
とかいう不穏な定数が見えますね….
自分のパソコンとGCJのテストケースへの†厚い信仰心†があれば通る.
#include <bits/stdc++.h> using namespace std; typedef long long int64; const int64 INF = 1LL << 58; int64 solve() { int N, P, R[50]; multiset< int > t[50]; cin >> N >> P; for(int i = 0; i < N; i++) { cin >> R[i]; } for(int i = 0; i < N; i++) { for(int j = 0; j < P; j++) { int s; cin >> s; t[i].emplace(s); } } int64 ret = 0; for(int i = 0; i < 56000000; i++) { int64 highest = INF; for(int j = 0; j < N; j++) { int64 low = (1LL * R[j] * i * 9 + 9) / 10; int64 high = (1LL * R[j] * i * 11) / 10; if(t[j].empty() || low > *--t[j].end()) return (ret); int64 proc = 0; for(auto &p : t[j]) proc += low <= p && p <= high; highest = min(highest, proc); } if(highest > 0) { for(int j = 0; j < N; j++) { int64 low = (1LL * R[j] * i * 9 + 9) / 10; int64 high = (1LL * R[j] * i * 11) / 10; int64 proc = 0; for(multiset< int >::iterator it = t[j].begin(); it != t[j].end();) { if(low <= *it && *it <= high) { it = t[j].erase(it); ++proc; } else { ++it; } if(proc == highest) break; } } ret += highest; } } return (ret); } int main() { int T; cin >> T; for(int i = 1; i <= T; i++) { cout << "Case #" << i << ": " << solve() << endl; } }
Problem C. Play the Dragon (Small)
自分の体力 , 攻撃力 , 敵の体力 , 攻撃力 が与えられる.
自分が以下のいずれかの命令を実行し, 次に相手が自分に攻撃する, というのを自分か敵の体力が 以下になるまで繰り返す.
- Attack: 現在の攻撃分のダメージを敵に与える.
- Buff: 自分の攻撃力が 増加する.
- Cure: 自分の体力が に回復する.
- DeBuff: 相手の攻撃力が 減少する.
相手を倒すための最短ターンを求めよ. どのようにしても自分が負ける時 “IMPOSSIBLE” を出力せよ.
解法
Small なので色々 以下. 自分の攻撃力などが より大きくなっても無駄なことを利用すると,
dp[ターン][min(100,現在の自分の攻撃力)][min(100,現在の自分の体力)][min(100,現在の相手の攻撃力)] := 現在の相手の体力の最小値
とした動的計画法が適用できる. ターン数が微妙だが, 実験をするとなんとなく 以下になることがわかる.
くらいになる.
ソース
自分のパソコンへの信仰心その .
#include <bits/stdc++.h> using namespace std; void chmin(int &a, int b) { a = min(a, b); } const int INF = 1LL << 30; int dp[101][101][101]; int dp2[101][101][101]; void solve() { int Hd, Ad, Hk, Ak, B, D; cin >> Hd >> Ad >> Hk >> Ak >> B >> D; fill_n(**dp, 101 * 101 * 101, INF); dp[Ad][Hd][Ak] = Hk; for(int i = 0; i < 300; i++) { fill_n(**dp2, 101 * 101 * 101, INF); for(int j = 0; j < 101; j++) { for(int k = 0; k < 101; k++) { for(int l = 0; l < 101; l++) { if(dp[j][k][l] == INF) continue; chmin(dp2[j][k][l], dp[j][k][l] - j); chmin(dp2[min(100, j + B)][k][l], dp[j][k][l]); chmin(dp2[j][Hd][l], dp[j][k][l]); chmin(dp2[j][k][max(0, l - D)], dp[j][k][l]); } } } fill_n(**dp, 101 * 101 * 101, INF); for(int j = 0; j < 101; j++) { for(int k = 0; k < 101; k++) { for(int l = 0; l < 101; l++) { if(dp2[j][k][l] == INF) continue; if(dp2[j][k][l] <= 0) { cout << i + 1 << endl; return; } if(k - l <= 0) continue; dp[j][k - l][l] = dp2[j][k][l]; } } } } cout << "IMPOSSIBLE" << endl; } int main() { int T; cin >> T; for(int i = 1; i <= T; i++) { cout << "Case #" << i << ": "; solve(); } }