Facebook Hacker Cup 2012 Round1

全部解けました！！無事Round2出場決定です。Top100に残ってT-shirtsゲットしたい。。

Checkpoint

　数学の問題。パスカルの三角形を使って解きました。下のコードでは、len[i]に最短路のパターン数がiになる場合における始点-終点間のマンハッタン距離の最小値を格納しています。len[]が分かれば、答えはlen[j] + len[S/j]の最小値です（jはSの約数）。

view plainprint?

1. const int MAX = 10000000;  
2. const int INF = 100000000;  
3. int comb[2][10000];  
4. int len[MAX+1];  
5.   
6. void solve() {  
7.     for (int i = 0; i <= MAX; i++)  
8.         len[i] = i;  
9.   
10.     memset(comb, 0, sizeof(comb));  
11.     comb[0][0] = 1;  
12.     for (int i = 0; i < 10000; i++) {  
13.         int now = i&1;  
14.         int next = (i+1)&1;  
15.   
16.         if (i > 0) {  
17.             for (int j = 0; j <= i; j++) {  
18.                 int k = comb[now][j];  
19.                 if (k <= MAX)  
20.                     len[k] = min(len[k], i);  
21.             }  
22.         }  
23.   
24.         memset(comb[next], 0, sizeof(comb[next]));  
25.         for (int j = 0; j <= i; j++) {  
26.             comb[next][j] = min(INF, comb[next][j] + comb[now][j]);  
27.             comb[next][j+1] = min(INF, comb[next][j+1] + comb[now][j]);  
28.         }  
29.     }  
30.   
31.     int R, S;  
32.     scanf("%d", &R);  
33.     for (int i = 0; i < R; i++) {  
34.         scanf("%d", &S);  
35.   
36.         int ret = INF;  
37.         for (int j = 1; j * j <= S; j++) {  
38.             if (S % j == 0)  
39.                 ret = min(ret, len[j] + len[S/j]);  
40.         }  
41.   
42.         printf("Case #%d: %d\n", i+1, ret);  
43.     }  
44. }  

const int MAX = 10000000;
const int INF = 100000000;
int comb[2][10000];
int len[MAX+1];

void solve() {
    for (int i = 0; i <= MAX; i++)
        len[i] = i;

    memset(comb, 0, sizeof(comb));
    comb[0][0] = 1;
    for (int i = 0; i < 10000; i++) {
        int now = i&1;
        int next = (i+1)&1;

        if (i > 0) {
            for (int j = 0; j <= i; j++) {
                int k = comb[now][j];
                if (k <= MAX)
                    len[k] = min(len[k], i);
            }
        }

        memset(comb[next], 0, sizeof(comb[next]));
        for (int j = 0; j <= i; j++) {
            comb[next][j] = min(INF, comb[next][j] + comb[now][j]);
            comb[next][j+1] = min(INF, comb[next][j+1] + comb[now][j]);
        }
    }

    int R, S;
    scanf("%d", &R);
    for (int i = 0; i < R; i++) {
        scanf("%d", &S);

        int ret = INF;
        for (int j = 1; j * j <= S; j++) {
            if (S % j == 0)
                ret = min(ret, len[j] + len[S/j]);
        }

        printf("Case #%d: %d\n", i+1, ret);
    }
}

Recover the Sequence

　実装問題。最初にord[i] = iとした配列を用意。デバッグ情報を元にマージソートを再現します。ソート完了後のord[]を見ることで、iはもともとord[i]番目にあったんだなということが分かります。

view plainprint?

1. const LL MOD = 1000003;  
2.   
3. vector<int> merge_sort(vector<int> arr) {  
4.     int n = arr.size();  
5.     if (n <= 1)  
6.         return arr;  
7.   
8.     int mid = n/2;  
9.     vector<int> arr1(arr.begin(), arr.begin()+mid);  
10.     arr1 = merge_sort(arr1);  
11.     vector<int> arr2(arr.begin()+mid, arr.end());  
12.     arr2 = merge_sort(arr2);  
13.   
14.     unsigned int p = 0, q = 0;  
15.     for (;p < arr1.size() && q < arr2.size();) {  
16.         int c = getchar();  
17.         if (c == '1') {  
18.             arr[p+q] = arr1[p];  
19.             ++p;  
20.         }  
21.         else {  
22.             arr[p+q] = arr2[q];  
23.             ++q;  
24.         }  
25.     }  
26.   
27.     for (;p < arr1.size(); p++)  
28.         arr[p+q] = arr1[p];  
29.     for (;q < arr2.size(); q++)  
30.         arr[p+q] = arr2[q];  
31.   
32.     return arr;  
33. }  
34.   
35. void solve() {  
36.     int T;  
37.     int N;  
38.     vector<int> ord;  
39.     vector<int> pos;  
40.   
41.     cin >> T;  
42.     for (int t = 0; t < T; t++) {  
43.         cin >> N;  
44.   
45.         ord.resize(N);  
46.         for (int i = 0; i < N; i++)  
47.             ord[i] = i;  
48.   
49.         getchar();  
50.         ord = merge_sort(ord);  
51.   
52.         pos.resize(N);  
53.         for (int i = 0; i < N; i++)  
54.             pos[ord[i]] = i+1;  
55.   
56.         LL ret = 1;  
57.         for (int i = 0; i < N; i++)  
58.             ret = (31 * ret + pos[i]) % MOD;  
59.   
60.         printf("Case #%d: %I64d\n", t+1, ret);  
61.     }  
62. }  

const LL MOD = 1000003;

vector<int> merge_sort(vector<int> arr) {
    int n = arr.size();
    if (n <= 1)
        return arr;

    int mid = n/2;
    vector<int> arr1(arr.begin(), arr.begin()+mid);
    arr1 = merge_sort(arr1);
    vector<int> arr2(arr.begin()+mid, arr.end());
    arr2 = merge_sort(arr2);

    unsigned int p = 0, q = 0;
    for (;p < arr1.size() && q < arr2.size();) {
        int c = getchar();
        if (c == '1') {
            arr[p+q] = arr1[p];
            ++p;
        }
        else {
            arr[p+q] = arr2[q];
            ++q;
        }
    }

    for (;p < arr1.size(); p++)
        arr[p+q] = arr1[p];
    for (;q < arr2.size(); q++)
        arr[p+q] = arr2[q];

    return arr;
}

void solve() {
    int T;
    int N;
    vector<int> ord;
    vector<int> pos;

    cin >> T;
    for (int t = 0; t < T; t++) {
        cin >> N;

        ord.resize(N);
        for (int i = 0; i < N; i++)
            ord[i] = i;

        getchar();
        ord = merge_sort(ord);

        pos.resize(N);
        for (int i = 0; i < N; i++)
            pos[ord[i]] = i+1;

        LL ret = 1;
        for (int i = 0; i < N; i++)
            ret = (31 * ret + pos[i]) % MOD;

        printf("Case #%d: %I64d\n", t+1, ret);
    }
}

Squished Status

　DPの問題。dp[i][j]にcompressed messageのi番目まで見終わったとき最後の文字コードがjとなっているときの場合の数を格納すればOKです。

view plainprint?

1. const LL MOD = 4207849484LL;  
2. LL dp[1024][256];  
3.   
4. void solve() {  
5.     int N;  
6.   
7.     scanf("%d", &N);  
8.     for (int t = 0; t < N; t++) {  
9.         int M;  
10.         string comp;  
11.   
12.         cin >> M >> comp;  
13.         int len = comp.length();  
14.         memset(dp, 0, sizeof(dp));  
15.         dp[0][0] = 1;  
16.   
17.         for (int i = 0; i < len; i++) {  
18.             for (int j = 0; j <= M; j++) {  
19.                 if (dp[i][j] == 0)  
20.                     continue;  
21.   
22.                 int d = comp[i] - '0';  
23.                 int k = 10 * j + d;  
24.   
25.                 if (0 < k && k <= M)  
26.                     dp[i+1][k] = (dp[i+1][k] + dp[i][j]) % MOD;  
27.                 if (k != d && 0 < d && d <= M)  
28.                     dp[i+1][d] = (dp[i+1][d] + dp[i][j]) % MOD;  
29.             }  
30.         }  
31.   
32.         LL ret = 0;  
33.         for (int i = 1; i <= M; i++)  
34.             ret = (ret + dp[len][i]) % MOD;  
35.   
36.         printf("Case #%d: %I64d\n", t+1, ret);  
37.     }  
38. }  

const LL MOD = 4207849484LL;
LL dp[1024][256];

void solve() {
    int N;

    scanf("%d", &N);
    for (int t = 0; t < N; t++) {
        int M;
        string comp;

        cin >> M >> comp;
        int len = comp.length();
        memset(dp, 0, sizeof(dp));
        dp[0][0] = 1;

        for (int i = 0; i < len; i++) {
            for (int j = 0; j <= M; j++) {
                if (dp[i][j] == 0)
                    continue;

                int d = comp[i] - '0';
                int k = 10 * j + d;

                if (0 < k && k <= M)
                    dp[i+1][k] = (dp[i+1][k] + dp[i][j]) % MOD;
                if (k != d && 0 < d && d <= M)
                    dp[i+1][d] = (dp[i+1][d] + dp[i][j]) % MOD;
            }
        }

        LL ret = 0;
        for (int i = 1; i <= M; i++)
            ret = (ret + dp[len][i]) % MOD;

        printf("Case #%d: %I64d\n", t+1, ret);
    }
}