Google Code Jam 2011 Qualification Round 解答編

Code Jam終わったので自分の解法を晒します。まずは総合的な感想から。

　今回は、去年と比べて問題のレベルが上がりました。

でも上位陣は４問を１時間内に解いてしまってます。。何食べたらそんなに頭がよくなるのだろう？？

　Aは境界値条件、分岐方法の正確さが求められました。Bは、データ構造方法の問題でした。

Cはビット演算の知識、Dは確率の知識が必要な問題でした。

　せっかく24時間あるので、今年は3つの言語で解くという遊びにチャレンジ。

• 問題A、BはC++
• 問題CはHaskell
• 問題DはPython

で解きました。

では、それぞれの問題の解法。。もっといい解き方があったら教えてくださいーー。

---

Problem A. Bot Trust

[解法]

まず、お仕事リストを

　vector timeline

に格納。（値は、BOBBOOなどになる。）

それとは別に、ロボットが押すべきボタンの位置をそれぞれ

　vector blue;

　vector orange;

に格納。

あとは、timelineをループでまわしていけばOK。

ロボットが負の方向に動く場合もあるので、正の方向と負の方向に動く場合で場合分けすると実装しやすいです。

[提出コード]

view plainprint?

1. int main() {  
2.     int t, n;  
3.     scanf("%d", &t);  
4.   
5.     REP(i, t) {  
6.         scanf("%d", &n);  
7.   
8.         vector<char> timeline;  
9.         vector<int> blue;  
10.         vector<int> orange;  
11.   
12.         REP(j, n) {  
13.             int x;  
14.             char r;  
15.   
16.             scanf(" %c %d", &r, &x);  
17.             timeline.push_back(r);  
18.             if (r == 'B')  
19.                 blue.push_back(x);  
20.             else  
21.                 orange.push_back(x);  
22.         }  
23.   
24.         int sz = timeline.size();  
25.         int szBlue = blue.size(), szOrange = orange.size();  
26.         int p = 0, q = 0;  
27.         int bpos = 1, opos = 1;  
28.         int ret = 0;  
29.   
30.         REP(j, sz) {  
31.             if (timeline[j] == 'B') {  
32.                 int pos = blue[p++];  
33.                 ret += ABS(pos - bpos) + 1;  
34.                 if (q < szOrange) {  
35.                     int move = ABS(pos - bpos) + 1;  
36.                     if (opos < orange[q])  
37.                         opos = min(opos + move, orange[q]);  
38.                     else  
39.                         opos = max(opos - move, orange[q]);  
40.                 }  
41.                 bpos = pos;  
42.             } else {  
43.                 int pos = orange[q++];  
44.                 ret += ABS(pos - opos) + 1;  
45.                 if (p < szBlue) {  
46.                     int move = ABS(pos - opos) + 1;  
47.                     if (bpos < blue[p])  
48.                         bpos = min(bpos + move, blue[p]);  
49.                     else  
50.                         bpos = max(bpos - move, blue[p]);  
51.                 }  
52.                 opos = pos;  
53.             }  
54.         }  
55.         printf("Case #%d: %d\n", i+1, ret);  
56.     }  
57.   
58.     return 0;  
59. }  

int main() {
    int t, n;
    scanf("%d", &t);

    REP(i, t) {
        scanf("%d", &n);

        vector<char> timeline;
        vector<int> blue;
        vector<int> orange;

        REP(j, n) {
            int x;
            char r;

            scanf(" %c %d", &r, &x);
            timeline.push_back(r);
            if (r == 'B')
                blue.push_back(x);
            else
                orange.push_back(x);
        }

        int sz = timeline.size();
        int szBlue = blue.size(), szOrange = orange.size();
        int p = 0, q = 0;
        int bpos = 1, opos = 1;
        int ret = 0;

        REP(j, sz) {
            if (timeline[j] == 'B') {
                int pos = blue[p++];
                ret += ABS(pos - bpos) + 1;
                if (q < szOrange) {
                    int move = ABS(pos - bpos) + 1;
                    if (opos < orange[q])
                        opos = min(opos + move, orange[q]);
                    else
                        opos = max(opos - move, orange[q]);
                }
                bpos = pos;
            } else {
                int pos = orange[q++];
                ret += ABS(pos - opos) + 1;
                if (p < szBlue) {
                    int move = ABS(pos - opos) + 1;
                    if (bpos < blue[p])
                        bpos = min(bpos + move, blue[p]);
                    else
                        bpos = max(bpos - move, blue[p]);
                }
                opos = pos;
            }
        }
        printf("Case #%d: %d\n", i+1, ret);
    }

    return 0;
}

---

Problem B. Magicka

[解法]

呪文合成規則を

　char combine[26][26];

に、呪文組み合わせ規則を

　bool opposed[26][26];

に格納。

となえる呪文をstackに詰めていき、逐次上記２つの規則をチェックする。

呪文組み合わせチェックは、26*26見ているけど、これだとLargeの場合タイムオーバーになりそうなので、

基本エレメントだけを取り出して、組み合わせチェックをするといい。（てか最初から8*8でつくれよっ。）

[提出コード]

view plainprint?

1. char combine[26][26];  
2. bool opposed[26][26];  
3. char tmp[16];  
4. char magic[128];  
5. bool emerge[26];  
6. string base = "QWERASDF";  
7.   
8. bool isOppose(stack<char> stk) {  
9.     bool hasBase[8] = {0};  
10.   
11.     while (!stk.empty()) {  
12.         char t = stk.top();  
13.         int pos = -1;  
14.   
15.         REP(i, 8)  
16.             if (base[i] == t)  
17.                 pos = i;  
18.         if (~pos)  
19.             hasBase[pos] = 1;  
20.   
21.         stk.pop();  
22.     }  
23.   
24.     REP(i, 8) REP(j, 8) {  
25.         if (!hasBase[i] || !hasBase[j])  
26.             continue;  
27.         if (opposed[base[i]-'A'][base[j]-'A'])  
28.             return true;  
29.     }  
30.   
31.     return false;  
32. }  
33.   
34.   
35. int main() {  
36.     int t;  
37.     scanf("%d", &t);  
38.   
39.     REP(i, t) {  
40.         int c, d, n;  
41.   
42.         memset(combine, 0x00, sizeof(combine));  
43.         memset(opposed, 0x00, sizeof(opposed));  
44.   
45.         // read combine  
46.         scanf("%d", &c);  
47.         REP(j, c) {  
48.             scanf("%s", tmp);  
49.             combine[tmp[0]-'A'][tmp[1]-'A'] = tmp[2];  
50.             combine[tmp[1]-'A'][tmp[0]-'A'] = tmp[2];  
51.         }  
52.         // read opposed  
53.         scanf("%d", &d);  
54.         REP(j, d) {  
55.             scanf("%s", tmp);  
56.             opposed[tmp[0]-'A'][tmp[1]-'A'] = 1;  
57.             opposed[tmp[1]-'A'][tmp[0]-'A'] = 1;  
58.         }  
59.         // read magic list  
60.         scanf("%d", &n);  
61.         scanf("%s", magic);  
62.   
63.         // solve  
64.         stack<char> ret;  
65.         REP(j, n) {  
66.             if (ret.empty()) {  
67.                 ret.push(magic[j]);  
68.                 continue;  
69.             }  
70.   
71.             int pre = ret.top()-'A';  
72.             int next = magic[j]-'A';  
73.   
74.             if (combine[pre][next]) {  
75.                 ret.pop();  
76.                 ret.push(combine[pre][next]);  
77.             }  
78.             else {  
79.                 ret.push(magic[j]);  
80.                 if (isOppose(ret)) {  
81.                     while (!ret.empty())  
82.                         ret.pop();  
83.                 }  
84.             }  
85.         }  
86.   
87.         // print  
88.         string res = "]";  
89.         while (!ret.empty()) {  
90.             res = ret.top() + res;  
91.             ret.pop();  
92.             if (!ret.empty())  
93.                 res = ", " + res;  
94.         }  
95.         res = "[" + res;  
96.         printf("Case #%d: %s\n", i+1, res.c_str());  
97.     }  
98.   
99.     return 0;  
100. }  

char combine[26][26];
bool opposed[26][26];
char tmp[16];
char magic[128];
bool emerge[26];
string base = "QWERASDF";

bool isOppose(stack<char> stk) {
    bool hasBase[8] = {0};

    while (!stk.empty()) {
        char t = stk.top();
        int pos = -1;

        REP(i, 8)
            if (base[i] == t)
                pos = i;
        if (~pos)
            hasBase[pos] = 1;

        stk.pop();
    }

    REP(i, 8) REP(j, 8) {
        if (!hasBase[i] || !hasBase[j])
            continue;
        if (opposed[base[i]-'A'][base[j]-'A'])
            return true;
    }

    return false;
}


int main() {
    int t;
    scanf("%d", &t);

    REP(i, t) {
        int c, d, n;

        memset(combine, 0x00, sizeof(combine));
        memset(opposed, 0x00, sizeof(opposed));

        // read combine
        scanf("%d", &c);
        REP(j, c) {
            scanf("%s", tmp);
            combine[tmp[0]-'A'][tmp[1]-'A'] = tmp[2];
            combine[tmp[1]-'A'][tmp[0]-'A'] = tmp[2];
        }
        // read opposed
        scanf("%d", &d);
        REP(j, d) {
            scanf("%s", tmp);
            opposed[tmp[0]-'A'][tmp[1]-'A'] = 1;
            opposed[tmp[1]-'A'][tmp[0]-'A'] = 1;
        }
        // read magic list
        scanf("%d", &n);
        scanf("%s", magic);

        // solve
        stack<char> ret;
        REP(j, n) {
            if (ret.empty()) {
                ret.push(magic[j]);
                continue;
            }

            int pre = ret.top()-'A';
            int next = magic[j]-'A';

            if (combine[pre][next]) {
                ret.pop();
                ret.push(combine[pre][next]);
            }
            else {
                ret.push(magic[j]);
                if (isOppose(ret)) {
                    while (!ret.empty())
                        ret.pop();
                }
            }
        }

        // print
        string res = "]";
        while (!ret.empty()) {
            res = ret.top() + res;
            ret.pop();
            if (!ret.empty())
                res = ", " + res;
        }
        res = "[" + res;
        printf("Case #%d: %s\n", i+1, res.c_str());
    }

    return 0;
}

---

Problem C. Candy Splitting

[解法]

Smallは全件探索してもO(2^15)なので間にあいます。LargeはO(2^1000)になるので全探索は不可能。

よく考えると、すべての飴玉のかたまりで排他的論理和を取って0になれば、”エセ”二等分ができることに気付きます。

排他的論理和が0以外なら、No。

0の場合は、(飴玉の総数) - (一番少ないかたまりの中にある飴玉の数)

が答え。

[提出コード]

view plainprint?

1. import Data.Bits  
2. import Text.Printf  
3.   
4. getInt = do   
5.             n <- getLine  
6.             return (read n::Int)  
7.   
8. getInts = do  
9.              n <- getLine  
10.              return (map (\x -> read x::Int) (words n))  
11.   
12. gcjMain x = do  
13.          m <- getInt  
14.          nums <- getInts  
15.          printf "Case #%d: %s\n" x (solve nums)  
16.   
17. solve nums   
18.      | foldl (xor) 0 nums /= 0 = "NO"  
19.      | otherwise           = show $ solve' nums  
20.        where solve' num = (sum nums) - foldl (min) inf nums  
21.              inf        = 100000000  
22. main = do   
23.        n <- getInt  
24.        mapM_ (\x -> gcjMain x) [1..n]  

import Data.Bits
import Text.Printf

getInt = do 
            n <- getLine
            return (read n::Int)

getInts = do
             n <- getLine
             return (map (\x -> read x::Int) (words n))

gcjMain x = do
         m <- getInt
         nums <- getInts
         printf "Case #%d: %s\n" x (solve nums)

solve nums 
     | foldl (xor) 0 nums /= 0 = "NO"
     | otherwise           = show $ solve' nums
       where solve' num = (sum nums) - foldl (min) inf nums
             inf        = 100000000
main = do 
       n <- getInt
       mapM_ (\x -> gcjMain x) [1..n]

---

Problem D. GoroSort

[解法]

これは、強烈。もっと簡単な解法があれば教えてください。。

やり方としては、

①まず数字をdisjoint（共通部分がない or 循環しない）なグループに分ける。

②それぞれのグループで期待値を求める。

③②で求めた期待値を足す。

という流れ。

サイズNのdisjoint groupに対する期待値は、

Xn = 1 + Sigma_{i=0}^n (nCi * f(i) * Xi / n! ), n >= 3

X0 = 0

X1 = 0

X2 = 2

という漸化式で表すことができる。

f(i)は、Nの中で正しい位置にいない要素の数がi個であるもののパターン数。

これは、

fn = (n-1) (f(n-1) + f(n-2)), n >= 2

f0 = 1

f1 = 0

という式で表すことが出来る。

上の式を頑張って手計算すると、ふむふむ、どうやら、

Xn = n, n >= 2

だな。と気付く。

これに気付けば、実装するだけです。

[提出コード]

view plainprint?

1. import sys    
2.     
3. n = raw_input()  
4. n = int(n)  
5.   
6. for i in range(n):  
7.     m = raw_input()  
8.     m = int(m)  
9.       
10.     nums = raw_input()  
11.     nums = nums.split(" ")  
12.     nums = map(int, nums)  
13.     nums = map(lambda x:x-1, nums)  
14.       
15.     grp = []  
16.     used = [0] * m  
17.     for j in range(m):  
18.         if nums[j] == j:  
19.             continue  
20.         if used[j]:  
21.             continue  
22.           
23.         cnt = 0  
24.         k = j  
25.         while used[k] == 0:  
26.             used[k] = 1  
27.             k = nums[k]  
28.             cnt = cnt + 1  
29.           
30.         grp = grp + [cnt]  
31.       
32.     print "Case #%d: %.6lf" % (i+1, sum(grp))  

import sys  
  
n = raw_input()
n = int(n)

for i in range(n):
    m = raw_input()
    m = int(m)
    
    nums = raw_input()
    nums = nums.split(" ")
    nums = map(int, nums)
    nums = map(lambda x:x-1, nums)
    
    grp = []
    used = [0] * m
    for j in range(m):
        if nums[j] == j:
            continue
        if used[j]:
            continue
        
        cnt = 0
        k = j
        while used[k] == 0:
            used[k] = 1
            k = nums[k]
            cnt = cnt + 1
        
        grp = grp + [cnt]
    
    print "Case #%d: %.6lf" % (i+1, sum(grp))