おかゆの競プロ日記(その他もあるよ)

主に自分の解いた問題を載せていきます。

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 つあります.

  1. 果樹園は最低 A マス分なければならない.
  2. 果樹園は長方形でなければならない.

最初, 平面上は何も手入れされていない更地なので, 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 も頑張るぞ~~~!