Google Code Jam 2018 - Qualification Round
Saving The Universe Again
問題をざっと説明します. まず, 敵の攻撃力の初期値は 1 です. また, 敵は 2 種類の行動が可能で 'S' と 'C' で表されます. 入力では, この 'S' と 'C' からなる文字列 s が与えられます.
- 'S' : 攻撃(Shoot). 現在の攻撃力で攻撃してくる.
- 'C' : 強化(Charge). 現在の攻撃力を 2 倍にする.
また, こちらには敵の攻撃に耐えられるシールドがありますが, 総ダメージ数が D を超えると壊れてしまいます. そこで敵から受ける総ダメージ数を D 以下にするために, 文字列 s のうち隣接する文字を入れ替える操作を複数回行って総ダメージ数を D 以下に減らします. このとき, 最小で何回操作を行えば D 以下に減らすことが出来ますか? という問題です.
考察
'S' 同士, または 'C' 同士を入れ替えても攻撃力は変わらないので, 'S' と 'C' を入れ替えることを考えます. 文字列 s 中のある 'C' について考えたとき, 敵から受ける総ダメージ数は, 'C' を手前に持ってくる場合("... SC ..." -> "... CS ...")は, ある 'C' よりも前に出てきた 'C' の数を m とすると, 2m + 1 - 2m = 2m だけ増えてしまいます. 次に, 'C' を後ろに持っていく("... CS ..." -> "... SC ...")場合は, 2m - 2m + 1 = -2m だけ減ることがわかります. よって, 'C' を後ろに持っていくほうがダメージが減らせることがわかります. また, どの 'C' を後ろに持っていくかですが, 後ろの方にある 'C' を入れ替えた方がダメージが減らせるので, 一番後の 'C' をどんどん後ろに持っていけばよいです. ただし, その 'C' 以降に 'S' がなければその 'C' は動かす必要はないので一つ手前の 'C' を動かします.
これをそのまま実装して AC でした.
#include <iostream> #include <algorithm> #include <string> #include <vector> using std::cin; using std::cout; using std::cerr; using std::endl; //#define DEBUG int main() { cin.tie(0); std::ios::sync_with_stdio(false); int T, D; std::string P; cin >> T; for (int i = 1; i <= T; ++i) { cin >> D >> P; int cnt = 0; bool ans = false, flag; while (true) { flag = false; // 現在のダメージを計算する int total_damage = 0, atk = 1; for (int i = 0; i < int(P.size()); ++i) { if (P[i] == 'C') { atk *= 2; } else { total_damage += atk; } } #ifdef DEBUG cerr << "total damage = " << total_damage << endl; cerr << "last attack point = " << atk << endl; #endif if (total_damage <= D) { ans = true; break; } /** * * 後ろから "CS" を探していって, 見つけたらswapするのが良さそう * でも, S...SCSSSSSSCSSSS とかなら? * ex) * SSCSSSSCSSSS => 2 + 8 + 16 == 26 * SS'SC'SSSCSSSS => 3 + 6 + 16 == 25 * SSCSSSS'SC'SSS => 2 + 10 + 12 == 24 * * --------------------------------------------------------- * * C を前に持ってくるのはダメージが増えるだけなので悪手 * C を後に持ってくるべき(ただし右側に隣接する文字がSの場合のみ) * そのとき, どのCを後に持ってくるかだが, * 任意のCに対して, 隣接するSと入れ替えたときのダメージ量の減少量は * 現在入れ替えようとしているCを除いて, それまでに出てきたCの数を m とすると, * * 2^(m + 1) - 2^(m) == 2^(m)(2 - 1) == 2^(m) * * となるので, 一番後ろのCをさらに後に移動させるべき. * Cの後にSがないときは一つ手前のCを後ろへ移動させる. */ for (int i = int(P.size()) - 1; i >= 1; --i) { if (P[i] == 'S' && P[i - 1] == 'C') { std::swap(P[i], P[i - 1]); cnt++; flag = true; break; } } if (!flag) { ans = false; break; } } if (ans) { cout << "Case #" << i << ": " << cnt << endl; } else { cout << "Case #" << i << ": IMPOSSIBLE" << endl; } } return 0; }
Trouble Sort
独自のソートアルゴリズムを作ったけどソートできない場合があるかもしれないから, そういう場合があれば教えて, という感じの問題です(雑). 独自のソートアルゴリズムについては問題文を参照してください.
考察
よく観察すると, このソートは元のリストに対して, 奇数番目の要素と偶数番目の要素を別々にソートしているだけのようです. つまり, 奇数番目の要素でソートし, 同様に偶数番目の要素でソートしたら 2 つのリストを合わせて, ちゃんとソートされているかを確認すればよいということになります.
#include <iostream> #include <algorithm> #include <ostream> #include <string> #include <vector> using std::cin; using std::cout; using std::cerr; using std::endl; //#define DEBUG std::ostream& operator << (std::ostream& os, std::vector<int> v) { os << "["; for (int i = 0; i < int(v.size()); ++i) { os << v[i] << (i == int(v.size()) - 1 ? "" : ", "); } os << "]"; return os; } int main() { cin.tie(0); std::ios::sync_with_stdio(false); int T; cin >> T; for (int i = 1; i <= T; ++i) { int N; cin >> N; std::vector<int> a(N); for (int j = 0; j < N; ++j) { cin >> a[j]; } std::vector<int> even(N / 2 + N % 2), odd(N / 2); int e_cnt = 0, o_cnt = 0; for (int j = 0; j < N; ++j) { if (j & 1) { odd[o_cnt++] = a[j]; } else { even[e_cnt++] = a[j]; } } std::sort(a.begin(), a.end()); std::sort(even.begin(), even.end()); std::sort(odd.begin(), odd.end()); #ifdef DEBUG cerr << a << endl; cerr << even << endl; cerr << odd << endl; #endif std::vector<int> troubleSortedList(N); e_cnt = o_cnt = 0; for (int j = 0; j < N; ++j) { if (j & 1) { troubleSortedList[j] = odd[o_cnt++]; } else { troubleSortedList[j] = even[e_cnt++]; } } if (a == troubleSortedList) { cout << "Case #" << i << ": OK" << endl; } else { int index = 0; for (int j = 0; j < N; ++j) { if (a[j] != troubleSortedList[j]) { index = j; break; } } cout << "Case #" << i << ": " << index << endl; } } return 0; }
Go, Gopher!
問題が長いのでアでした. 簡単に言うと, 1000 × 1000 の平面上に果樹園を作ります. ここで条件が 2 つあります.
- 果樹園は最低 A マス分なければならない.
- 果樹園は長方形でなければならない.
最初, 平面上は何も手入れされていない更地なので, Gopher くんに指示を出して開墾?してもらいます(開墾するマスを座標(x, y)で指定する). 1 回の指示で 1 マス分開墾してくれます. しかし, Gopher くんは座標(x, y)を指定すると(x, y)を含む周囲8近傍のマスの中からランダムに開墾してしまいます(既に開墾されているかは関係ない). さらに, 指示できる回数は 1000 回までです. このような中で条件を満たすような果樹園を作ってください, という問題です.
考察
制約を見ると, small では A = 20, large では A = 200 だそうなので, 座標 (2, 2 + 3 * i) (0 <= i <= 332) で表される各マスについて, そのマスを含む周囲8近傍が全て開墾されたら次のマスを開墾する, という風に繰り返していけばいけそうです(説明がアなのでソースコードを参照してください…).
#include <iostream> #include <algorithm> #include <vector> #include <cstring> using std::cin; using std::cout; using std::cerr; using std::endl; //#define DEBUG int main() { int T; bool used[1001][1001]; cin >> T; for (int i = 1; i <= T; ++i) { int A, x, y; cin >> A; std::memset(used, false, sizeof used); for (int j = 0; 2 + 3 * j < 1000; ++j) { int cnt = 0; for (int k = 0;;) { cout << 2 << " " << (2 + 3 * j) << endl; cin >> x >> y; if (x == 0 && y == 0) { break; } if (!used[x - 1][y - 1]) { used[x - 1][y - 1] = true; cnt++; } if (cnt == 9) { break; } } if (9 * (j + 1) >= A) { break; } if (x == 0 && y == 0) { break; } } } return 0; }
Cubic UFO
結局解いていません…(幾何?)
あとで解きます(>_<)
次の Round も頑張るぞ～～～!
