パスワードを忘れた? アカウント作成
218070 journal

Yak!の日記: Google Code Jam 2010 Qualification Round

日記 by Yak!

結果はまだ未確定だと思われるがとりあえず全問正解 99 点で Rank 550。Qualification Round だと Rank 自体には意味がないけれども。ソースコードは公式の Ranklist から取れるはずなので全体は省略して適当に抜粋。

問題を解いた順番は A → C → B。素直に難易度順のはず。A と C は C++、B はなんと OCaml である。実はそれでかなり苦労することになったのだが。以下、各問題について。

A. Snapper Chain

まずは、小さなセットでいいから手でやってみる。と、「あ、れ?」そう、これ普通にビットカウントになる。じゃ、K の N ビット目を採ればいいじゃん、と恒例の早合点。しかも困った事にそれで問題中の sample は通ってしまう。ということで速攻 Incorrect。下位から 1 が連続してないと駄目。ループで確認しようかと思って実際に書いたが色気を出して以下のように変更。

if((((((1<<n)-1)&k)+1)>>n)&1) {

下位 n ビットでマスクして +1 した時に n+1 ビット目が立てば n ビット 1 が連続、としている。

C. Theme Park

単純に解くだけなら書かれている事を素直に実装すればいいのだが、どれくらい高速化しておくべきかでちょっと迷う。結局、queue の各位置で、次に進む位置(↓の second)、何 euro 入るか(↓の first)の結果をキャッシュしておく形で実装。実際これで十分だったようだ。なお、同じグループを複数乗せることはできないという制約は sample input 実行してから追加。駄目駄目である。

for(ULL rr=0;rr<r;++rr) {
    if(t[idx].first != 0) {
        result += t[idx].first;
        idx = t[idx].second;
    } else {
        ULL pidx = idx;
        ULL sum = 0;
        while(sum+group[idx]<=k) {
            sum += group[idx];
            ++idx; if(idx == n) idx = 0;
            if(idx == pidx) break;
        }
        t[pidx].first = sum;
        t[pidx].second = idx;
        result += sum;
    }
}

B. Fair Warning

ぱっと見、どうやって解くか分からなかった。そんな奇をてらった問題でもないのできっと似たような問題を解いたことがある人も多そうだとは思ったが。で、小さな例を書いたりすることしばし。階差数列(or 最初の要素を引いた数列 t1-t0,t2-t0,...)の GCD が T となるので、その倍数となるように y を定めれば良さそうということに気付く(説明は後述)。

で、後はコーディングなのだが多倍長計算をしなければならない。Google Code Jam では全てのソースコードをアップロード(or サイズが大きい場合はリンクを提供)しなければならない。で、何故か「標準で多倍長計算できる言語でやるべき」と思い込む。今から思えば GMP とか使ってリンク張れば良かっただけな気が。まぁとにかくその時はそう思い込んでいたので、Perl は Math::BigInt があるが標準とは言いかねるのでパス、Java はほとんど使った事ないのでパス、OCaml だってほとんど使った事ないだろとは思ったものの、OCaml でやってみたいとは思っていたので OCaml を選択。入力の時点からリファレンスと首っ引きでちょっとずつ結果を確認しながら書いていたわけだが 12:30 くらい?で完了。最初からぴったりになっているケースが抜けていたが他はコンパイル OK の時点で sample(+α) で普通に通った事に感動。「型チェック最強」とか思いながら submit したら incorrect。で、sample 見たら同じ数字が入っているケースがある!問題文には

ti≠tj for some i,j.

とあり「なんで some なんだろう、こういう時は普通 any で書くんじゃねーの?」と思ったのだが、本当に some のままの意味だった。つまり「いずれかの組では異なる数字の場合がある=全部同じ数字の場合は無い」ということである(注:実は今回のアルゴリズムには関係ない)。で、「これだ!」と思って直して output が変わったので再度 submit したらやっぱり incorrect。output 見ている時に「何でここの結果が変わってるんだろ?」とか疑問に思ったのに不用意である。で、OCaml のデバッグに不慣れな点もあって(寝落ちしつつ)数時間悩んでいた訳だが遂に問題点が判明。

let rresult = if modulo == Big_int.zero_big_int then

OCaml をご存じの方なら分かると思うが == は「物理的等値」を判断する演算子である。つまり module が Big_int.zero_big_int と同じ「実体」を指しているかを判断することになり値として 0 であるかを判断しているわけではない。正しくはこうである。

let rresult = if Big_int.eq_big_int modulo Big_int.zero_big_int then

これで無事に通った。慣れない言語は使うもんじゃない、といったところだろうか。

以下、「階差数列の GCD が T となるので、その倍数となるように y を定めれば良い」ことの簡単な説明(保証無し)と C++ 版ソースをつける。

以下、整数 n が整数 m の約数であることを、記号 | を用いて n | m と表す。また t0 が ti の最小値とする(こうしても一般性を失わない)。まず 2 つの数 t0 と t1 で考える。題意から T | (t0+y) かつ T | (t1+y) である。従って、T | ((t0+y) - (t1+y)) ⇔ T | ((t0 - t1)) となる。このうち最大の T を選べば良いから t0-t1 の最大約数を採ればよい。実際、この時 t0、t1 それぞれを T で割った余りは等しいので適当な y を採って t0+y、t1+y 双方を T の倍数とすることができる。以上の議論を自然な形で 3 つ以上の場合に拡張してやればよい。

T | ((ti - t0)) for i = 1,...,n-1 から ti と t0 を T で割った余りが等しいこと、すなわち全ての i について ti を T で割った余りが等しいことが言える。結果、最大の T として (ti - t0) の GCD を採れることが言える(少なくとも T は ((ti - t0)) for i = 1,...,n-1 を割り切れなければならない。このうち最大のものが GCD。実際 ti を T で割った余りが等しいことから適当な y を採って ti+y 全てを GCD の倍数にできる)。

以下 C++ 版ソースだが、後付けで書いているせいもあるにしろ慣れない OCaml よりよっぽどすっきりしている……。

#include <iostream>
#include <algorithm>
#include <numeric>
#include <vector>
 
// The library GMP can be obtained from http://gmplib.org/
// I used 4.3.1.
#include <gmpxx.h>
 
using namespace std;
 
struct GCD
{
    mpz_class operator()(mpz_class& v1, mpz_class &v2) const
    {
        mpz_class r;
        mpz_gcd(r.get_mpz_t(), v1.get_mpz_t(), v2.get_mpz_t());
        return r;
    }
};
 
int main(void)
{
    int n;
    cin >> n;
    for(int nn = 0; nn < n; ++nn) {
        mpz_class result = 0;
        int n;
        cin >> n;
        vector<mpz_class> v(n);
        for(int i=0;i<n;++i) cin >> v[i];
        sort(v.begin(), v.end());
        vector<mpz_class> d(n);
        adjacent_difference(v.begin(), v.end(), d.begin());
        mpz_class t;
        if(n == 2) {
            t = d[1];
        } else {
            t = accumulate(d.begin()+2, d.end(), d[1], GCD());
        }
        if(v[0] % t == 0) {
            result = 0;
        } else {
            result = t - v[0] % t;
        }
 
        cout << "Case #" << nn+1 << ": " << result << endl;
    }
 
    return 0;
}

この議論は賞味期限が切れたので、アーカイブ化されています。 新たにコメントを付けることはできません。
typodupeerror

皆さんもソースを読むときに、行と行の間を読むような気持ちで見てほしい -- あるハッカー

読み込み中...