2011-04 << 2011-05 >> 2011-06

2011-05-08 (日)

*[GCJ] Google Code Jam 2011 (Qualification Round)

終わったようなので書いておく．

Qualification Roundなので簡単ですが，問題文が面白いのと，意味が分かると笑ってしまうような問題だったので面倒とは感じなかったです．

妙に簡単だなぁと思ったのですが，2009-09-04#A1のやつと比べると，やっぱり簡単な問題ですね．

久しぶりにC++を書きました．C++でコンテストをやっていると，

#include <iostream>
using namespace std;

int main() {
    return 0;
}

という6行を無意識に書けるスキルが身につくのですが，しばらくやってなかったら，手が動きませんでした．

C++を忘れてしまったのではないかという不安に襲われましたが，書き始めてみるとだんだん思い出してきます．良いリハビリになりました．

スコアボード確認すると，Bの英文読むのに疲れて途中で休憩した以外は，綺麗に30分ごとに1問解いてる感じです．半分以上は問題を読んでる時間なので，英語できる人が圧倒的に有利だと思う．

submit後にBのソース見たら酷いバグがあってsmallだけたまたま動く状態だったことに気づいたのだけど，やっぱりB-largeだけ間違っていた．Qualification Roundは１問間違うと一気に順位が下がりますね．

以下ネタバレ含みます．自分で問題読むつもりの人は読まないほうが良いでしょう．そもそも問題読まないと書いてある意味が分からないです．

A

２台のロボットに対して，指定された順番にスイッチを押させる問題．

見たままです．念のためlargeを警戒したけど，1秒ごとに状態を処理していっても良かった気がする．

たぶん誰が書いても同じなので，ソースは省略．

B

まどかではないマギカ．英語の読解問題でした．英語が読めれば問題ない．

ただ，small大丈夫だったしlargeも通るだろうと思ってて失敗した．smallはcombineとopposeが全て１つ以下しか出てこないのは罠．10個が1000個になるとかはアルゴリズムの問題だけど，1個が2個以上になるとかだと普通にバグってる可能性があるので気をつけるべきだった．submit後にソース見て気づいたけど手遅れだった．

ソースは省略．

C

Patrikの頭がやばい．頭の悪い弟からキャンディを騙し取る問題．Seanもひどいな．

酷さを伝えるためにソースを貼っておく．Patrikの頭さえ理解できれば一瞬で終わる．

#include <iostream>
using namespace std;

int main() {
    int t,n;
    cin >> t;
    
    for (int i=0;i<t;i++) {
        cin >> n;
        int sean = 0, pat_min = 0x7fffffff, pat_xor = 0;

        for (int j=0;j<n;j++) {
            int c;
            cin >> c;
            sean += c;
            pat_xor ^= c;
            if (c < pat_min) pat_min = c;
        }
        sean -= pat_min;

        if (pat_xor) {
            cout << "Case #" << (i+1) << ": NO"  << endl;
        } else {
            cout << "Case #" << (i+1) << ": " << sean << endl;
        }
    }
    return 0;
}

提出したソースでは，vectorをソートしてpat_min を求めてたけど，O(n)にするために書き換えた．

Patrikの頭のやばさが分かる例が問題に書いてあります．

5 + 4 = 1
7 + 9 = 14
50 + 10 = 56

Patrikがやっているのはキャリーの無い２進の加算，つまり排他的論理和(XOR)ですね．

２つに分けた袋の値がParrikから見て等しいということは，全体のXORを取った時に0にならないといけないわけです．0にならないなら，Patrikから見て等しく分割することは不可能です．

全体が0なので，全体からひとつを除いたもののXOR値は，除いた値と等しい．よって，Seanは最小値を持つCandyをひとつだけPatrikに渡せば，Patrikから見た値は同じにしつつ，他はすべて自分で取れることになります．

Seanは弟に対して酷すぎますね…．

D

ゴローひどい．腕が４本あるとか問題に何も影響が無い．

問題を理解したとき，解法がひどすぎて自分の頭を疑ったのだけど，合っていたっぽい．

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

int main() {
    int t,n;
    cin >> t;
    
    for (int i=0;i<t;i++) {
        cin >> n;

        vector<int> array1;
        vector<int> array2;
        for (int j=0;j<n;j++) {
            int d;
            cin >> d;
            array1.push_back(d);
            array2.push_back(d);
        }
        std::sort(array2.begin(),array2.end());
        int p = 0;
        for (int j=0;j<n;j++) {
            if (array1[j] != array2[j]) p++;
        }

        cout << "Case #" << (i+1) << ": " << p << ".000000" << endl;
    }

    return 0;
}

結果の誤差の話とか問題に書いてあるけど，ただのintなので誤差とか出ません．ランダムにやってる割には優秀なソートアルゴリズムだな，と一瞬思ってしまったけど，五郎がソート結果を知っていないと出来ないソートだったり．

データセット見て気づいたけど，もしかして，要素は1～Nでよかったのかな？それならvectorに入れておく必要すらなかった．

n個の要素をシャッフルした場合に，正しい位置に来るのはnに影響されず常に平均1個であることに気づけば，初期状態で間違った位置にある要素をカウントするだけの問題です．

2011-04 << 2011-05 >> 2011-06