Facebook Hacker Cup 2012 Round1

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

Checkpoint

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

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]番目にあったんだなということが分かります。

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です。

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);
    }
}