Google Code Jam Japanに参加してみた

Oct 2, 2011

通称GCJJ。暇だから参加してみた。

SmallとLargeを解答できた問題が1問以上あれば予選突破らしいので、問題Cを完答できた僕は多分突破できてる。

準備不足を言い訳にしたくはないが準備不足だったと思う。だから実際に問題を解きながら、あるいは予選が終わって今頃色々と気づいたことがある。

GCJの問題は非常にシンプルで（問題文は長いが）、基本的には使用する言語の文法と基礎的なデータ構造/アルゴリズムについて前提知識があれば、あとは地頭力だけで解ける。「このライブラリ、フレームワークを知らないと絶対解けない」「この言語でないと解くのが困難」という問題はおそらく存在しない。

もちろん高度なアルゴリズムを知っていることは有利に働くとは思う。Largeの問題を解くためには素朴な実装では計算量が大きすぎて制限時間内に実行が終了しないことがほとんどだろう。しかし、計算量を減らすためにはもっと簡単な方法がある。

「何をしなくてもよいか」を考えることだ。

例えば、今回の問題A。
僕はこの問題のsmallは解けたがLargeは実行が制限時間内に終了せず時間切れになってしまった。当初（small提出段階）では、カード要素を連結リストとして保持して、リストの要素を実際に移動させることでシャッフルを再現していた。Largeではカード枚数Mは10^9までなので、当然リストでは厳しい。メモリもGBオーダーを必要とするだろう。

僕が行った上記の「素朴」な解法の問題点は、連結リストという問題にはマッチしないデータ構造を採用したことでも他の効率的なアルゴリズムを僕が知らないということでもない。

問題文に示されている一挙手一投足をプログラムで再現しようとしたことだ。この問題Aは、要は最終的なWの位置のカードの数字が分かればよいのであって、それ以外の情報は一切不要だ。しかし僕の解法では、全てが分かる。シャッフル後のW以外の位置のカードの数字や、やろうと思えば、シャッフル途中のカードの順番まで全てだ。

これが不要だということを認識することが計算量を減らす第一歩だ。連結リストでは遅いからもっと効率的なアルゴリズムで実装しよう、という思考に陥ってしまっては答えにはなかなか辿りつけない。不要な処理を効率的に実行したところで不要なものは不要なのだ。

以上の考え方で予選終了後に必死に考えた問題Aの解を以下にコピペしておく。
アルゴリズムは至極単純で、最終的にWの位置にあるカードのシャッフルされる前の位置を計算していくというものだ。

#include <vector>
#include <stdio.h>
#include <utility>
using namespace std;

typedef pair<uint64_t, uint64_t> Pair;

bool isInside( uint64_t pos, uint64_t from, uint64_t to ) {
    return (pos >= from) && (pos <= to);
}

int main(int argc, char const* argv[]) {
    int T, C;
    uint64_t M, W;

    scanf("%d", &T);
    for (int t = 0; t < T; t++) {
        scanf("%lld %d %lld", &M, &C, &W);
        vector<Pair> cuts;
        cuts.resize( C );

        for (int i = 0; i < C; i++) {
            scanf("%lld %lld", &cuts[i].first, &cuts[i].second);
            cuts[i].first--;
        }

        uint64_t pos = W-1;
        for(int i=C; i--;) {
            if( isInside( pos, 0, cuts[i].second-1 ) ) {
                pos += cuts[i].first;
            } else if( isInside(pos, cuts[i].second, cuts[i].first + cuts[i].second-1 ) ) {
                pos -= cuts[i].second;
            }
        }

        printf("Case #%d: %lld\n", t+1, pos+1);
    }
    return 0;
}

トータル40行。最初の解法は300行近くあったから脅威のシェイプアップだ。
この解法では、最終的なWの位置のカードの、各シャッフル前後の位置以外は何もわからない。しかしそれでも答えは出る。

今回の例は非常にシンプルな例だったが、実際の開発現場でも似た様な設計、実装をしているせいでパフォーマンスが落ちている例が多くあるだろう。

何をしなくてよいか。
これからはこれを意識して開発に励もうと思った秋の週末。