TopCoder 始めました

TopCoder の Member SRM に初参戦しました (SRM 498 Div2)。

TopCoder は半年ぐらい前に登録して、一度 Practice をやってみたまま、なんとなく時間が合わなくて放置してました。この半年の間に競技プログラマな人といっぱい知り合い、ロジックの引き出しがケタ違いでコーディングが尋常じゃなく速いことを知って、これはやった方がいいと強く思うようになりました。

というわけで TopCoder デビューです。今日は予定が空いていたので、遅くなってもいいだろうと昨晩挑戦してみました。

• AdditionGame (250): 8m36s, 229.67pts
• FoxSequence (500): 20m37s, 349.38pts
• NinePuzzle (950): 29m50s, 542.55pts
• Challenge: 50pts (FoxSequence x 1)

AdditionGame はコーディング遅いなあという感想しかないです。訓練あるのみ。

class AdditionGame {
 public:
  int getMaximumPoints(int A, int B, int C, int N) {
    int res = 0;
    do {
      if (A > B) {
        if (A > C) {
          res += A--;
        } else {
          res += C--;
        }
      } else if (B > C) {
        res += B--;
      } else {
        res += C--;
      }
    } while (--N && A + B + C);
 
    return res;
  } 
};

FoxSequence は速く書かなきゃと思って地味に地道なコードを書きました。見づらい。本当は階差数列をつくって unique して正負を見るのが一番簡単らしいですが、思いつきませんでした……

#include ...
using namespace std;
 
class FoxSequence {
 public:
  pair getArith(const vector<int>& seq, int from) {
    const int end = seq.size() - 1;
    if (from >= end) return make_pair(-1, -1);
    int d = seq[from + 1] - seq[from];
    if (from == end - 1) return make_pair(from + 1, d);
    do {
      ++from;
    } while (from < end && seq[from + 1] - seq[from] == d);
    return make_pair(from, d);
  }
  
  string isValid(vector <int> seq) {
    if (seq.size() < 5) return "NO";
    pair<int, int> r1 = getArith(seq, 0);
    if (r1.first == -1 || r1.second <= 0) return "NO";
    pair<int, int> r2 = getArith(seq, r1.first);
    if (r2.first == -1 || r2.second >= 0) return "NO";
    pair<int, int> r3 = getArith(seq, r2.first);
    if (r3.first == -1) return "NO";
    int next = r3.second ? r2.first : r3.first;
    pair<int, int> r4 = getArith(seq, next);
    if (r4.first == -1 || r4.second <= 0) return "NO";
    pair<int, int> r5 = getArith(seq, r4.first);
    if (r5.first == -1 || r5.first != seq.size() - 1 || r5.second >= 0)
      return "NO";
    
    return "YES";
  }
};

NinePuzzle は一筋縄では行かなさそう。しばらく思考停止してて、いやいや絶対楽する方法があるだろと図をいろいろ描いてみると、任意のペアを入れ替える操作列が必ず存在することが示せたので、ただ色が何個揃ってるか数えるだけでよしという結論。でも思いつくのに時間かかりすぎで、地道に探索書いた人より遅かったりしてて(´・ω・`)

#include ...
using namespace std;
 
class NinePuzzle {
 public:
  static int countChar(const string& str, char ch) {
    int cnt = 0;
    for (size_t i = 0; i < str.size(); ++i) {
      if (str[i] == ch) ++cnt;
    }
    return cnt;
  }
 
  static void countRGBY(const string& str, vector<int>* v) {
    v->clear();
    v->push_back(countChar(str, 'R'));
    v->push_back(countChar(str, 'G'));
    v->push_back(countChar(str, 'B'));
    v->push_back(countChar(str, 'Y'));
  }
  
  int getMinimumCost(string init, string goal) {
    vector<int> iv, gv;
    countRGBY(init, &iv);
    countRGBY(goal, &gv);
 
    int match = 0;
    for (size_t i = 0; i < iv.size(); ++i) {
      match += min(iv[i], gv[i]);
    }
 
    return 9 - match;
  }
};

いろいろ勉強になりました。結果は 1171.60pts でレーティング 1461 の青色。次の回は Div1 がんばります。