Google Code Jam 2011 Qualification Round - div1に上がりたいkeitanxkeitanの日記

Qualification Round

Google Code Jam 2011の予選に参加しました。
24時間かけて4つの問題に挑戦し、25点以上獲得で次のラウンドに進むことができます。各問題には単純なアルゴリズムで十分間に合うsmallと、工夫したアルゴリズムでないとTLEになってしまうlargeの2種類の入力があり、largeの方が得点が高くなっています。また、smallは何度でも挑戦でき、その場で正否が判定されますが、largeはコンテスト中一回しか提出できず、コンテスト終了まで正否がわかりません。
昨年は3つの問題があり33点が予選通過のボーダーラインで、smallは各10点、largeは各23点だったので、少なくとも1問はlargeまで解かなければ予選通過はできなかったのですが、今年はsmallを3つ通せば予選通過できるように設定されていました。
予選通過できたかどうかコンテスト終了までわからない緊張感がなくなったのが残念のような、精神衛生上良かったような・・・。
また、競技者数も昨年より少し増えていたようです。

無事！

予選通過できました！
昨年はA問題とB問題でlargeを間違えて、C問題で何とかlargeを通して辛くも予選通過だったのですが、今年は全問largeまで解くことができました。
AとBは言われた通りに実装する問題で、特に高速化などは意識せずに解けましたが、C-largeとDに大きく時間を取られてしまいました。

A. Bot Trust

ブルーとオレンジのロボットがそれぞれ廊下の上に置かれておりテストをする。
廊下には100個のボタンが一列に1メートル間隔で並んでいて、1から100までラベリングされている。
ブルーとオレンジは廊下のボタン1の位置からスタートする。
1秒間の中でロボットは
・どちらかの方向に1メートル歩く
・今いる場所のボタンを押す
・ボタンを押さずにその場に留まる
のどれかの行動をすることができる。
テストというのは決められた順番でボタンを押すことである。
例えば、
O 2, B 1, B 2, O 4
という順番が与えられたら、まずオレンジがボタン2を押し、その次にブルーがボタン1を押し、・・・という風に実行される。
ブルーとオレンジは最短何秒でテストをクリアできるか？

秒数でループを回してしまうとlargeで落ちてしまうのかもしれないです。順番の何番目か、すなわちターンでループを回せばO(N)（1≦N≦100）で解けます。
次にボタンを押すべきロボットは次のボタンの位置まで移動させてボタンを押させ、その間にもう一方のロボットは次に自分が押すべきボタンの位置まで出来る限り移動します。

#include <cstdio>
#include <vector>
#include <map>

using namespace std;

const int kInf = 1 << 20;

int main() {
  int T;
  scanf("%d", &T);

  for (int t = 1; t <= T; ++t) {
    int N;
    scanf("%d", &N);
    vector<pair<int, int> > blue_seq;
    vector<pair<int, int> > orange_seq;
    for (int i = 0; i < N; ++i) {
      char R;
      int P;
      scanf(" %c %d", &R, &P);
      if (R == 'B') {
	blue_seq.push_back(make_pair(P, i));
      } else {
	orange_seq.push_back(make_pair(P, i));
      }
    }
    blue_seq.push_back(make_pair(-1, kInf));
    orange_seq.push_back(make_pair(-1, kInf));

    int ans = 0;
    int blue_turn = 0, orange_turn = 0;
    int blue_pos = 1, orange_pos = 1;
    for (int turn = 0; turn < N; ++turn) {
      pair<int, int> blue_button = blue_seq[blue_turn];
      pair<int, int> orange_button = orange_seq[orange_turn];
      if (blue_button.second == turn) {
	int distance = abs(blue_button.first - blue_pos);
	int delta = orange_button.first - orange_pos;
	blue_pos = blue_button.first;
	if (abs(delta) < (distance)+1) {
	  orange_pos += delta;
	} else {
	  orange_pos += (delta>0?1:-1) * (distance+1);
	}
	ans += distance+1;
	++blue_turn;
      } else if (orange_button.second == turn) {
	int distance = abs(orange_button.first - orange_pos);
	int delta = blue_button.first - blue_pos;
	orange_pos = orange_button.first;
	if (abs(delta) < (distance)+1) {
	  blue_pos += delta;
	} else {
	  blue_pos += (delta>0?1:-1) * (distance+1);
	}
	ans += distance+1;
	++orange_turn;
      }
    }    
    printf("Case #%d: %d\n", t, ans);
  }
}

B. Magicka

魔法使い（wizardは男。故に魔法少女ではない）であるあなたは、8種類のベースエレメント、すなわちQ、W、E、R、A、S、D、Fを生み出すことができる。
生み出したエレメントはエレメントリストに追加される。
ある特定のベースエレメントのペアは結合し、18種類のノンベースエレメントとなる。
結合ペアがエレメントリストの後ろにある時、2つのエレメントはすぐさまノンベースエレメントになる。
また、ある特定のエレメントのペアは反発し合っている。
あなたがベースエレメントを生み出した後、すぐに結合が起こらない時、エレメントリストに反発ペアが含まれている場合、エレメントリストの全てのエレメントが消えてしまう。
生み出すエレメントのリストが与えられ、すべてのエレメントを生み出し終わった時のエレメントリストはどうなっているか？

Twitterでキーワード「gcj」のタイムラインを見ていたら、問題の読解で詰まっている人が多かったようです。
問題文だけで十分に理解できなくても、サンプルケースがどのようになっているかしっかり確認すれば、問題文と照らし合わせつつ題意がつかめる気がします。
私は結合ペア、反発ペアをそれぞれ26x26の二次元配列に格納して、エレメントリストを操作していきました。
注意すべき点、というほどでもないですが、反発ペアを見つける時はO(N^2)で毎回すべてのエレメントのペアを確認する必要はなくて、新しく末尾に追加されたエレメントとその他のエレメントのペアをO(N)でチェックすれば良いです。仮に全てチェックしても全体のオーダーはO(N^3)（2≦N≦1000）なので、特に問題ないはずです。

#include <iostream>
#include <string>

using namespace std;

char combine_rules[26][26];
bool opposed_rules[26][26];

int main() {
  int T;
  cin >> T;
  for (int t = 1; t <= T; ++t) {
    int C;
    cin >> C;
    memset(combine_rules, '\0', sizeof(combine_rules));
    for (int i = 0; i < C; ++i) {
      string combine_rule;
      cin >> combine_rule;
      int tx = combine_rule[0]-'A';
      int ty = combine_rule[1]-'A';
      char tc = combine_rule[2];
      combine_rules[ty][tx] = tc;
      combine_rules[tx][ty] = tc;
    }

    int D;
    cin >> D;
    memset(opposed_rules, false, sizeof(opposed_rules));
    for (int i = 0; i < D; ++i) {
      string opposed_rule;
      cin >> opposed_rule;
      int tx = opposed_rule[0]-'A';
      int ty = opposed_rule[1]-'A';      
      opposed_rules[ty][tx] = true;
      opposed_rules[tx][ty] = true;
    }
    
    int N;
    string elements;
    cin >> N;
    cin >> elements;
    string element_list = "";
    for (int n = 0; n < N; ++n) {
      element_list += elements[n];
      int len = element_list.length();
      if (len < 2) continue;
      int tx = element_list[len-2]-'A';
      int ty = element_list[len-1]-'A';
      if (combine_rules[tx][ty] != '\0') {
	element_list = element_list.substr(0, len-2);
	element_list += combine_rules[tx][ty];
      }
      len = element_list.length();
      if (len < 2) continue;
      tx = element_list[len-1]-'A';
      for (int i = len-2; i >= 0; --i) {
	int ty = element_list[i]-'A';
	if (opposed_rules[tx][ty]) {
	  element_list = "";
	  break;
	}
      }
    }
    printf("Case #%d: [", t);
    int len = element_list.length();
    for (int i = 0; i < len; ++i) {
      printf("%c", element_list[i]);
      if (i != len-1) printf(", ");
    }
    printf("]\n");
  }
}

C. Candy Splitting

ショーンとパトリックの兄弟が両親からキャンディーの袋詰めをもらった。
キャンディーにはその価値を表す正の整数が書かれており、兄弟はこのキャンディーを2人で分ける。
まず、兄であるショーンがキャンディーを2つの山に分ける。そして、どちらか1つの山を弟パトリックに渡す。
次に、パトリックがそれぞれの山のキャンディーの価値を足し合わせる。もしそこで2つの山の合計が等しくなければパトリックは泣き出してしまう。
不幸なことにパトリックは幼いため、正確に足し算をすることができない。彼は数を二進数で加算することができるのだが、桁上がりを忘れてしまう。例えば、12（二進数で1100）と5（二進数で101）を足し合わせると
　 1100
＋ 0101

-

　 1001
で、9になってしまう。
ショーンは正確に足し算ができ、弟を泣かせずにできるだけ多くのキャンディーを取りたい。
もし可能なら、ショーンはキャンディーの山をパトリックが価値が同じだと思うように2つに分けたい。
すべてのキャンディーの価値が与えられた時、価値が同じように分けることが可能かどうか判定し、もし可能ならショーンが得られるの山の価値の最大値を求めよ。

パトリックの加算の仕方は排他的論理和（XOR）です。C言語やC++ではこれを行う演算子^があるので、パトリック加算はこれを使えば良いです。
キャンディー山を2人で分けるのは分割問題で、2^N通りの分け方があり、これは指数オーダーなのでN=20くらいがまでが限界です。
smallでは2≦N≦15なので、愚直に全通り試す解法でも恐らく通すことができます。
本番では実際に愚直な方法で通したのですが、なぜ「恐らく」かということは後ほど。

愚直な解法

愚直な方法で2つの分割を全通り生成するには、ビット演算を使うことができます。
例えば、2^N通りだったら次のようになります。

  for (int bits = 0; bits < (1<<N)-1; ++bits) {
    for (int i = 0; i < N; ++i) {
      int bit = (bits>>i)&1;
      if (bit == 1) {
	SomeFunc();
      } else {
	TheOtherFunc();
      }
    }
  }

すべての分け方を試してみて、条件を満たす分け方がなかった場合にNOと出力する方法だとO(2^N)になります。
しかし、この問題ではNOの判定はもっと簡単にできるのです。
ある分け方が条件を満たしているならば、ショーン山のパトリック加算での価値の合計false_sean_sumとパトリック山のパトリック加算での価値の合計false_patrick_sumはすべて同じビットが立っているので、それらの排他的論理和、すなわちfalse_sean_sum ^ false_patrick_sumは0になります。・・・（＊）
ここで、ショーン山のキャンディーの数をNs、それぞれのキャンディーの価値をCs1, Cs2, ..., CsNs、パトリック山のキャンディーの数をNp、それぞれのキャンディーの価値をCp1, Cp2, ..., CpNpとすると、false_sean_sumとfalse_patrick_sumはそれぞれ、

false_sean_sum = Cs1 ^ Cs2 ^ ... ^ CsNs
false_patrick_sum = Cp1 ^ Cp2 ^ ... ^ CpNp

となります。
したがって、（＊）と合わせて考えると、ある分け方が条件を満たしているならば、

C1 ^ C2 ^ ... ^ CN = (Cs1 ^ Cs2 ^ ... ^ CsNs) ^ (Cp1 ^ Cp2 ^ ... ^ CpNp) = false_sean_sum ^ false_patrick_sum = 0

となることがわかります。
よって、C1からCNの排他的論理和を計算することによって、条件を満たす分け方が存在するかどうかを判定することができます。

話が長くなりましたが、先ほど「恐らく」と言った理由の1つは、愚直な解法の中でこの判定法を使っていたことです。これにより、2^N通りの分け方を最後まで調べることはなくなりました。

更にもう1つの理由としては、キャンディーの価値を予めソートしておいて、ショーンがより多くの価値の山を得られる分け方から調べていったことです。
もちろんこの方法を使ったところでO(2^N)は変わりませんが、多少の高速化を期待してこうしました。

結局

XORを使った判定法を利用した
キャンディーの価値をソートしておいた

というところで、smallを提出しました。

スマートな解法

smallを提出した後でlargeの解法が思いつかなかったので放置して、DのGoroSortに取り組みましたが、パッと思いついた解法に飛びついてsmallでincorrectを出してしまったので戻ってきました。

O(2^N)という状況を打破してくれるスーパーな解法はDPなのかなぁと思いつつ（DPが苦手です。と同時に、何やらとんでもない計算量の解法しか思いつかない時は、DPが正解なのではないかと思ってしまいます）、ノートに色々な組み合わせで二進数を書いていたら閃きました。

先程のXOR判定法を使って、条件を満たす分け方が存在すると判明したキャンディー山は、どんな分け方をしても条件を満たすのです。（普通の人は判定法を思いついたら、すぐにここまでたどり着くのではないだろうか・・・）

ということで、条件を満たす分け方が存在すると分かったら、あとは1番価値の低いキャンディーをパトリックにあげるだけです。（ひどい）

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

const int kInf = 1 << 20;

int main() {
  int T;
  scanf("%d", &T);
  for (int t = 1; t <= T; ++t) {
    int N;
    scanf("%d", &N);
    vector<int> candies(N);
    for (int i = 0; i < N; ++i) {
      scanf("%d", &candies[i]);
    }

    int candies_sum = 0;
    int true_candies_sum = 0;
    int min_value = kInf;    
    for (int i = 0; i < N; ++i) {
      candies_sum ^= candies[i];
      true_candies_sum += candies[i];
      min_value = min(min_value, candies[i]);      
    }
    if (candies_sum != 0) {
      printf("Case #%d: NO\n", t);
    } else {
      printf("Case #%d: %d\n", t, true_candies_sum - min_value);      
    }    
  }
}

D. GoroSort

吾郎は4本の腕を持っている。
テーブルの上にN個の異なる数字が書かれたエレメント（何だ？）が置かれておりこれをソートしなければならない。
吾郎はアルゴリズムに強くないが、腕っ節には自身がある。
吾郎はまず、2つの手でいくつかのエレメントを押えつける。そして、残りの2つの拳で力いっぱいテーブルを叩く。
すると押さえつけていなかったエレメントがランダムにシャッフルされる。
この操作を繰り返してソートする時、吾郎がテーブルを叩く回数の期待値を求めよ。

まずGoroって誰？ってなる問題。頭の中で操作をシミュレートし続けたせいで、4本腕のロボットが力強くテーブルを叩き続ける絵が頭に焼き付いてしまった。
まず初めにCのlargeから逃げてきて考えたのは、バブルソートの回数を数えればいいんだということ。そしてincorrect。

次にCのlargeを終えて考え直したのは、何も隣接する2つのエレメントを交換しなくてもいいんだということで、ループの度に最もWin-Winの関係になれる2つのエレメントをO(N^2)で探してスワップするという方法。そしてincorrect。

これに微調整を加えて提出。そしてincorrect。

悩みあぐねること数時間。やっと気づいた。
それまでは2つより多いn個のエレメントをシャッフルすると、全てが適切な位置になるのにn!回叩く必要があるので、堅実に2つずつやるべきだと思っていたのですが、正しい位置にないエレメントを残して盛大にテーブルを叩くと、平均して毎回1つは正しい位置に移動するのではないか。

そして正しい位置に移動したエレメントを押さえて、また叩く。すると平均毎回1つずつ正しい位置に収まるので、元の並びの内で正しい位置にない要素の数が求める期待値になるのではないか。

証明をしたわけではないので確証はなかったですが、既に3回incorrectを出しているのでダメもとで提出してみるとcorrect。

仮説は正しかったようで、Contest Analysisを見るとしっかりとした証明が書かれています。

#include <cstdio>
#include <vector>

using namespace std;

int main() {
  int T;
  scanf("%d", &T);
  for (int t = 1; t <= T; ++t) {
    int N;
    scanf("%d", &N);
    vector<int> elems(N);
    for (int i = 0; i < N; ++i) {
      scanf("%d", &elems[i]);
    }

    double ans = 0.0;
    for (int i = 0; i < N; ++i) {
      if (elems[i] != i+1) ++ans;
    }
    
    printf("Case #%d: %lf\n", t, ans);
  }
}

感想

初の満点を取れたのは嬉しい。ですが、

解法を思いつくまで、思いついた解法を実装するまで、と全体的に時間がかかり過ぎ
Cは正しい解法の直前まで行ったのに、そこから悩んでしまった
Dは閃き、勘に依るところが大きかった。強引に実装できたかもしれない

という反省点があります。
Round 1まで2週間弱あるので過去問で練習をしたいと思います。

と反省も多いけれど、やっぱり楽しかった！scoreboardで自分の順位が変動するのはワクワクするし、卒業してしばらく会っていない（というほど会ってなくもなかった）先輩方をFriendsで見つけてやっぱりすごいなぁと感心したり、競技プログラミングに興味を持ち始めて初参戦した後輩がいたり、Twitterのタイムラインで知らない人が同じ気持ちになっていたり。

なんかいいよね！