Google Code Jam Japan 2011 練習問題解いた

ちゃんと3つとも解いた!
これで予選の準備は万端… だといいな。

書いたコードはこっち(GitHub)です。以下は簡単な解説。

A: 数珠つなぎ

スナッパーのOFF/ON状態を0/1で表すと、 0000 -> 0001 -> 0010 -> 0011 -> 0100 みたいになってて、増えていく2進数と同じ形になるので、Kの数を2進数表現したときに下位Nビットが立っているかを調べればOK.

B: 数の集合

多分2つ知ってないといけないことがあると思う。1つは素数のリストの作り方で、これはエラトステネスのふるいっていうのを使った。もう一つは集合を効率よく結合していく方法で、Union-Findっていうアルゴリズムが有名らしい。チャレンジブックで習った。その2つが使えれば、あとはP以上の素数ごとに区間内からその素数の倍数を探して、属してる集合を結合していくだけ。区間の長さを超える素数は2つ以上倍数が見つかる可能性が無いので用は無いです。

C: 遊園地

計算結果をメモしておく工夫と周期的な動きを利用する工夫で計算量を減らせる問題。「iグループ目が先頭の状態でコースターが来たら、何人乗れて、次はどのグループが先頭になるのか」を先に計算しておいて再利用する方法でlargeが10秒くらい。「iグループ目が先頭の状態からいくつかコースターが来たらまたiグループ目が先頭になった」というループ状態を見つけて、その部分の計算をはしょると、largeが0.05秒くらいでした。

解くの時間かかったけど、勉強になるなぁ

GCJ Japan 2011 練習問題/数の集合

職場の先輩がLargeの答えが合わないって言ってたので僕も解いてみた。

やり方は、例えばsampleの通り10-20の区間でP=3の場合、

  1. 3の倍数12,15,18を取り出す。この段階でグループ数は-3
  2. 取り出した数は全部独立してたので、新たにグループが1つできる。グループ数+1
  3. 5の倍数10,15,20を取り出す。この段階でグループ数は-2。(15は独立してないので取り出してもグループが減らない。だから-3じゃない。)
  4. 既にグループに入ってる15を含むので、新たにグループは出来ない(統合される)。グループ数+0

みたいな感じの操作を繰り返す。
どの数がどうグルーピングされるかは気にせず、数の増減だけ見る形で、実行時間は10秒くらい。

結果… ぜんぜん違うアルゴリズムの先輩と答えが一致して、GCJのシステムからは不正解いただきました。
あっれー?二人してなんか特殊なケースを見落としてるのかな。

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

static const int MAX_PRIME_NUMBER = 1000000;

int solve(vector<int>& primes, long long A, long long B, int P) {
    int result = B - A + 1;
    vector<bool> grouped(B - A + 1, false);
    for (int i = 0; i < primes.size(); i++) {
        int divisor = primes[i];
        if (divisor >= P && divisor < B - A + 1) {
            int remNum = 0;
            int addNum = 0;
            bool isInOtherGroup = false;
            int first = (A % divisor == 0 ? 0 : (divisor - A % divisor));
            for (int j = first; j < grouped.size(); j += divisor) {
                if (!grouped[j]) {
                    remNum++;
                    grouped[j] = true;
                } else {
                    isInOtherGroup = true;
                }
            }
            if (!isInOtherGroup) {
                addNum = 1;
            }
            result -= remNum - addNum;
        }
    }
    return result;
}


int main() {
    // prepare prime numbers
    vector<int> primes;
    vector<bool> temp(MAX_PRIME_NUMBER + 1, true);
    for (int i = 2; i <= MAX_PRIME_NUMBER; i++) {
        if (temp[i]) {
            primes.push_back(i);
            for (int j = i; j <= MAX_PRIME_NUMBER; j += i) {
                temp[j] = false;
            }
        }
    }

    // read cases from standard input and print result to standard out
    int N, P;
    long long A, B;
    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> A >> B >> P;
        int result = solve(primes, A, B, P);
        cout << "Case #" << i << ": " << result << endl;
    }

    return 0;
}