Google Code Jam: Qualification Round

Google Code JamQualification Roundに参加しました!


Google Code Jam(GCJ)とはGoogleが主催するプログラミングの大会です。
http://code.google.com/codejam/contest/

今回行われたQualification Roundの問題一覧はこちらです。


私はProblem AProblem Bを解いて、50ptで無事Qualificationを通過できました。
Problem Cは解き方を思いつかず、途中で諦めてしまいました。
もっと精進します。
約1〜2週間後に次のRound 1があるので、そちらでも勝ち残れるよう頑張りたいと思います。


ちなみに私の登録名はmickey24で、順位は1649位でした。
Qualification Roundなので順位は関係なく、25pt以上取れた人は全員次のRound 1に進めます。


以下、Problem AとProblem Bで私が書いたソースコード(C++)です。
興味のある方はどうぞ。

Problem A: Saving the Universe

簡単なDP(動的計画法)で解きました。
これくらいのコードをさらっと書ければ十分でしょうか。


A.cpp

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

int main()
{
  int N;
  cin >> N;

  string t;
  for (int a = 1; a <= N; a++) {
    int s;
    cin >> s;
    getline(cin, t);

    string se[s];
    for (int i = 0; i < s; i++) {
      getline(cin, se[i]);
    }

    int q;
    cin >> q;
    getline(cin, t);

    int sw[s][q+1];
    fill(&sw[0][0], &sw[s-1][q]+1, 0);

    for (int i = q-1; i >= 0; i--) {
      getline(cin, t);

      for (int j = 0; j < s; j++) {
        if (se[j] == t) {
          sw[j][i] = INT_MAX;
          for (int k = 0; k < s; k++) {
            if (j != k) {
              sw[j][i] = min(sw[j][i], sw[k][i+1] + 1);
            }
          }
        }
        else {
          sw[j][i] = sw[j][i+1];
        }
      }
    }
    
    int ans = INT_MAX;
    for (int i = 0; i < s; i++) {
      ans = min(sw[i][0], ans);
    }

    cout << "Case #" << a << ": " << ans << endl;
  }
  
  return 0;
}

Problem B: Train Timetable

ちょっと長いです。
電車の発車(FROM)、到着(TO)、turnaround完了(READY)ごとにevent構造体のインスタンスを作り、それを時刻でソートして早い時刻のイベントから処理しています。
FROMイベントが来るたびに必要な電車の数をインクリメントし、READYイベントで電車が補充された時はデクリメントしています。
ちなみに、最初にソースを作成したときはeventのインスタンスをmultisetではなくsetに入れていたため、同じ時刻に同じ種類のイベントが複数あったときに1回分しか処理されないというバグが入ってしまい、2回ほどIncorrectをもらいました。
あと、Correctで通した後に、TOイベントとREADYイベントは統合してもよかったことに気付きました。
まだまだですね。


B.cpp

#include <iostream>
#include <algorithm>
#include <string>
#include <set>
using namespace std;

const int TO_A = 0;
const int TO_B = 1;
const int READY_A = 2;
const int READY_B = 3;
const int FROM_A = 4;
const int FROM_B = 5;

struct event
{
  int type;
  int min;
  int param;
  event(int type, int min, int param = 0) : type(type), min(min), param(param) {}
  bool operator <(const event &rhs) const {
    if (min != rhs.min) { return min < rhs.min; }
    if (type != rhs.type) { return type < rhs.type; }
    return param < rhs.param;
  }
};

int tomin(const string &t)
{
  int m = 0;
  m += (t[0]-'0')*600;
  m += (t[1]-'0')*60;
  m += (t[3]-'0')*10;
  m += (t[4]-'0')*1;
  return m;
}

int main()
{
  int N;
  cin >> N;

  for (int a = 1; a <= N; a++) {
    int t;
    cin >> t;
    
    int na, nb;
    cin >> na >> nb;

    multiset<event> que;
    for (int i = 0; i < na; i++) {
      string s1, s2;
      cin >> s1 >> s2;
      que.insert(event(FROM_A, tomin(s1), tomin(s2)));
    }
    for (int i = 0; i < nb; i++) {
      string s1, s2;
      cin >> s1 >> s2;
      que.insert(event(FROM_B, tomin(s1), tomin(s2)));
    }

    int train_a = 0;
    int train_b = 0;
    int max_train_a = 0;
    int max_train_b = 0;
    while (!que.empty()) {
      event e = *que.begin();
      que.erase(que.begin());

      switch (e.type) {
      case READY_A:
        train_a--;
        break;
      case READY_B:
        train_b--;
        break;
      case FROM_A:
        que.insert(event(TO_B, e.param));
        max_train_a = max(++train_a, max_train_a);
        break;
      case FROM_B:
        que.insert(event(TO_A, e.param));
        max_train_b = max(++train_b, max_train_b);
        break;
      case TO_A:
        que.insert(event(READY_A, e.min + t));
        break;
      case TO_B:
        que.insert(event(READY_B, e.min + t));
        break;
      }
    }

    cout << "Case #" << a << ": " << max_train_a << " " << max_train_b << endl;
  }
    
  return 0;
}


Problem Cは後で解いてみようと思います。