Google Code Jam Qualification Round 2018
AB--のLarge2完です. あまり知識ゲーではなかったのでなんとかqual突破できた.
あまり書くこと無い気がする.
A - Saving The Universe Again
一番ダメージが小さい場合は'S'がすべて左端に寄っている場合であるから
'S'の数がシールドの耐久値より多ければ"IMPOSSIBLE".
そうでない場合は,
1. 今の文字列のダメージを計算.
2. 耐えられないなら文字列の一番後ろの"CS"を"SC"にして1に戻る.
3. 耐えられるなら出力して終了.
最近はデバッグ用の出力を消さずにコメントアウトで残してます.
#include <bits/stdc++.h> using namespace std; int main(void) { int t; cin >> t; int d[t]; string p[t]; for(int i = 0; i < t; i++) { cin >> d[i] >> p[i]; // cout << endl; // cout << "d[" << i << "]: " << d[i] << endl; // cout << "p[" << i << "]: " << p[i] << endl; } for(int i = 0; i < t; i++) { int numberofS = 0; for(int j = 0; j < p[i].length(); j++) { if(p[i][j] == 'S') { numberofS++; } } if(numberofS > d[i]) { cout << "Case #" << i + 1 << ": IMPOSSIBLE" << endl; continue; } int change = 0; while(true) { int damage = 0; int beam = 1; for(int j = 0; j < p[i].length(); j++) { if(p[i][j] == 'C') { beam *= 2; } else if(p[i][j] == 'S'){ damage += beam; } } // cout << "damage: " << damage << endl; if(damage <= d[i]) { break; } int tmp = p[i].rfind("CS"); // cout << tmp << endl; // cout << tmp + 1 << endl; p[i][tmp] = 'S'; p[i][tmp + 1] = 'C'; // cout << "p[" << i << "]: " << p[i] << endl; change++; } cout << "Case #" << i + 1 << ": " << change << endl; } }
B - Trouble Sort
TroubleSortはインデックスが奇数番目同士, 偶数番目同士を入れ替える.
奇数番目と偶数番目が入れ替わることはない. よって入力配列を奇数番目と
偶数番目に分けてソートし, 最後に交互に1列に並べてソートできているか
どうかを確かめればよい.
#include <bits/stdc++.h> using namespace std; int n; int v[1000000]; int main(void) { int t; cin >> t; vector <string> answer(t); for(int i = 0; i < t; i++) { cin >> n; vector <int> odd, even; for(int j = 0; j < n; j++) { cin >> v[j]; if(j % 2 == 0) { even.push_back(v[j]); } else { odd.push_back(v[j]); } } sort(even.begin(), even.end()); sort(odd.begin(), odd.end()); vector <int> w; for(int j = 0; j < n / 2 + 1; j++) { if(j < even.size()) { w.push_back(even[j]); } if(j < odd.size()) { w.push_back(odd[j]); } } bool nondec = true; int index; for(int j = 1; j < n; j++) { if(w[j] < w[j - 1]) { // cout << "v[" << j << "]: " << v[j] << endl; // cout << "v[" << j - 1 << "]: " << v[j - 1] << endl; nondec = false; index = j - 1; break; } } if(nondec) { answer[i] += "Case #" + to_string(i + 1) + ": OK"; } else { answer[i] += "Case #" + to_string(i + 1) + ": " + to_string(index); } } for(int i = 0; i < t; i++) { cout << answer[i] << endl; } }
ABLarge解けてるから大丈夫だろうと思いABCに移動, ABC終わってからやる気力は無く寝てしまった.