Educational Codeforces Round 39 (Div.2)

誤読で本番1問も解けなかった(完).

A - Partition

数列を左と右に分けて左をB, 右をCとした時の最大値だと勝手に思い込んでいたけど,
そうではなくて, ある数がBとCのどちらに属するかは自由に決めていいので,
単にプラスならB, マイナスならCに放り込めばいいだけだった.

#include <bits/stdc++.h>

using namespace std;

int main(void) {
  int n;
  cin >> n;
  int a[n];
  for(int i = 0; i < n; i++) {
    cin >> a[i];
  }

  int sum = 0;
  for(int i = 0; i < n; i++) {
    if(a[i] < 0) {
      sum -= a[i];
    }
    else {
      sum += a[i];
    }
  }

  cout << sum << endl;
}

B - Weird Subtraction Process

問題文通り愚直に書いたらTLEした. 以下の提出を参考にした.

http://codeforces.com/contest/946/submission/35997312

引き算を%で余りとる計算に変えるとループが圧倒的に少なくなった. そりゃそうだ.
ビット演算をこんな風に使うの面白い.

#include <bits/stdc++.h>

using namespace std;

long long a, b;

int main(void) {
  cin >> a >> b;
  // ビット演算
  while(a && b) {
    if(a >= 2 * b) {
      a %= 2 * b;
    }
    else if(b >= 2 * a) {
      b %= 2 * a;
    }
    else {
      break;
    }
  }
  cout << a << " " << b << endl;
}

C - String Transformation

これもaからzまで連続している必要があると勘違いしていたけどそうではなかった.
a~zが連続している必要があるなら置き換えられない文字が出てきた場合にもう一度'a'から
探しなおす(インクリメントする変数を'a'にリセットする)操作が必要だけど,
そうではないのでその部分を削除した.

// Subsequenceは連続していなくてもよい
// abczzzzzzzefgh...でもよい
#include <bits/stdc++.h>

using namespace std;

int main(void) {
  string s;
  cin >> s;

  char c = 'a';
  for(int i = 0; i < s.length(); i++) {
    if(s[i] <= c) {
      s[i] = c;
      c++;
      if(c > 'z') {
	cout << s << endl;
	return 0;
      }
    }
  }
  cout << "-1" << endl;
}

誤読を防ごう. めんどくさがらずに毎回Google翻訳にかけよう.