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終わってからやる気力は無く寝てしまった.