Google Code Jam Japan 2011 予選と決勝

Google Code Jam Japan 2011 に参加しました。
Google Code Jamに参加するのは今回で2回目です。予選はなんとか通って、決勝でも1問正解できました。

予選スコア

rank	score	A-small	A-large	B-small	B-large	C-small	C-large
512	23	4:52:59	4:58:02	--	--	5:12:18	--

決勝スコア

rank	score	A-small	A-large	B-small	B-large	C-small	C-large
310	15	1:12:15	1:58:50	誤答1回	--	--	--

予選

予選が13時に始まった後、17時頃に予選が行われていることを知ったので、全然解く時間がありませんでした。

問題A

似たような問題を解いたことがあったのであまり悩みませんでした。
シャッフル後に上からW番目にあるカードの位置を、シャッフルの逆順に追跡していき、シャッフルする前の位置を求めると、それが求めるカードの番号になります。

#include <iostream>
#include <vector>
#include <utility>
using namespace std;

int main() {
    int t;
    cin >> t;
    for (int i = 0; i < t; i++) {
        int m, c, w;
        cin >> m >> c >> w;
        vector<pair<int, int> > cut;
        for (int j = 0; j < c; j++) {
            int a, b;
            cin >> a >> b;
            cut.push_back(make_pair(a, b));
        }
        for (vector<pair<int, int> >::reverse_iterator rit = cut.rbegin(); rit != cut.rend(); rit++) {
            int a, b;
            a = rit->first;
            b = rit->second;
            if (w <= b) {
                w += a - 1;
            } else if (w < a + b) {
                w -= b;
            }
        }
        cout << "Case #" << i + 1 << ": " << w << endl;
    }
}

問題C

問題Aが終わって問題Bを見てみるけど、なんだか難しそう。問題Cの方が提出数と正解数が多かったので問題Cに取り組みました。
問題文中の関数を作って、a + b = N となる a, b (ただしa<=b) の N/2通りについて調べる以外に思いつかず、その方針でいくことに。
smallだけ通って終了。

#include <iostream>
using namespace std;

int func(int x) {
    int res = 0;
    while (x) {
        if (x % 2 != 0) {
            res++;
        }
        x /= 2;
    }
    return res;
}

int main() {
    int t;
    cin >> t;
    for (int i = 0; i < t; i++) {
        int n;
        cin >> n;
        int max = 0;
        for (int j = 0; j * 2 <= n; j++) {
            int temp = func(j) + func(n - j);
            if (max < temp) {
                max = temp;
            }
        }
        cout << "Case #" << i + 1 << ": " << max << endl;
    }
}

決勝

問題A

意味はわかるけど、どうやって解けばいいかわからず小一時間経過。とりあえずsmallだけでも解こうと思い、smallの場合 3 <= K <= 5 なので、エレメントの長さの順列の総当たりで解こうと思い立ちました。
エレメントの順列は数珠順列になっているので、
K = 4 の場合は (4 - 1)! / 2 = 3 通り、
K = 5 の場合でも (5 - 1)! / 2 = 12 通り。
エレメントの配列のインデックスを、全通り2次元配列に格納し、それを使って総当たりで調べ上げます。ソースコードがすごく汚い＞＜

//A-small
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

const int c4[][3] = {
    {1, 2, 3}, {1, 3, 2}, {2, 1, 3},
};
const int c5[][4] = {
    {1, 2, 3, 4}, {1, 2, 4, 3}, {1, 3, 2, 4}, {1, 3, 4, 2}, {1, 4, 2, 3}, {1, 4, 3, 2},
    {2, 1, 3, 4}, {2, 1, 4, 3}, {2, 3, 1, 4}, {2, 4, 1, 3}, {3, 1, 2, 4}, {3, 2, 1, 4},
};
const int MAX_K = 5, c4_n = 3, c5_n = 12;
int elems[MAX_K];
int v[MAX_K];
int K;

double sum() {
    double res = v[0] * v[K - 1];
    for (int i = 0; i < K - 1; i++) {
        res += v[i] * v[i + 1];
    }
    return res / 2 * sin(2 * M_PI / K);
}

int main() {
    int T;
    cin >> T;
    for (int i = 0; i < T; i++) {
        cin >> K;
        fill_n(elems, MAX_K, 0);
        for (int j = 0; j < K; j++) {
            cin >> elems[j];
        }
        v[0] = elems[0];
        double max = 0;
        switch (K) {
        case 3:
            v[1] = elems[1];
            v[2] = elems[2];
            max = sum();
            break;
        case 4:
            for (int j = 0; j < c4_n; j++) {
                for (int k = 1; k < 4; k++) {
                    v[k] = elems[c4[j][k - 1]];
                }
                double s = sum();
                if (s > max) {
                    max = s;
                }
            }
            break;
        case 5:
            for (int j = 0; j < c5_n; j++) {
                for (int k = 1; k < 5; k++) {
                    v[k] = elems[c5[j][k - 1]];
                }
                double s = sum();
                if (s > max) {
                    max = s;
                }
            }
            break;
        }
        cout << "Case #" << i + 1 << ": " << max << endl;
    }
}

largeの場合、3 <= K <= 1000 と、Kが大きいのでこの方法は使えません。
ちょっと考えてみて、隣り合うエレメントの長さの積の和を最大化すればいいと気付くけど、方法がわかりません。
何か法則性でもないかと、K = 5のときにエレメントの長さを全通り出力して調べてみると、大きな数同士が隣り合う場合ほど面積が大きくなっていことが発見できました。
それに望みをかけて、エレメントの長いもの同士が隣り合うようにエレメントを配置することを考えてみました。
最大の長さのエレメントを中央にして、エレメントの長い順番に右,左,右,左…と並べていき、両端のエレメントが隣同士になるように円状に配置します。左右それぞれの端のエレメントの長さを覚えておき、エレメントを並べるときに、新たに並べるエレメントの長さとの積をとって加えていけば、隣り合うエレメントの長さの積の和が計算できます。
smallの結果を出力してdiffをとってみると、提出した結果と一致してたので、この方針のままlargeに提出。正解できていました。

//A-large
#include <iostream>
#include <cmath>
#include <set>
using namespace std;

int main() {
    int T;
    cin >> T;
    for (int i = 0; i < T; i++) {
        int K;
        cin >> K;
        multiset<int> elems;
        for (int j = 0; j < K; j++) {
            int temp;
            cin >> temp;
            elems.insert(temp);
        }
        int prev[2];
        double sum = 0;
        int j = 0;
        for (multiset<int>::reverse_iterator rit = elems.rbegin(); rit != elems.rend(); rit++) {
            if (j == 0) {
                prev[0] = prev[1] = *rit;
            } else {
                sum += prev[j % 2] * (*rit);
                prev[j % 2] = *rit;
            }
            j++;
        }
        sum += prev[0] * prev[1];
        sum *= sin(2 * M_PI / K) / 2;
        cout << "Case #" << i + 1 << ": " << sum << endl;
    }
}

問題B

剰余についてwikipediaを見つつ解いてみたけど、サンプルの最後のケースが不正解。試しに提出してみても、結果は誤答。よくわからないまま時間切れになりました。

//誤答
#include <iostream>
using namespace std;

int calc(int a, int e, int m) {
    a %= m;
    int res = 1;
    for (int i = 0; i < e; i++) {
        res *= a;
        res %= m;
    }
    return res;
}

int main() {
    int T;
    cin >> T;
    for (int i = 0; i < T; i++) {
        int A, B, C;
        cin >> A >> B >> C;
        for (int j = 0; j < B; j++) {
            A = calc(A, A, C);
        }
        cout << "Case #" << i + 1 << ": " << A << endl;
    }
}