Google Code Jam Japan 2011

参加しました。
結果は、BのLarge以外は全て解けたので、予選通過できました。

問題A. カードシャッフル

smallは愚直にカードのリストを作って、問題文通りにシャッフルすれば解ける。

/// <summary>まともにやる</summary>
private int small()
{
    // カード配列の初期化
    var cards = new List<int>(M);
    for (int i = 0; i < M; i++)
    {
        cards.Add(i + 1);
    }

    // シャッフル操作
    for (int c = 0; c < C; c++)
    {
        var temp = cards.GetRange(A[c] - 1, B[c]);
        cards.RemoveRange(A[c] - 1, B[c]);
        temp.AddRange(cards);
        cards = temp;
    }

    return cards[W - 1];
}

largeはカード枚数が莫大なので、リストが作れない。
最終的にWの位置のカードがわかればいいので、最後にWの位置に来るカードは、最初にどの位置にあったのかを、最後から逆にシャッフル操作をして求める。

/// <summary>工夫する</summary>
private int large()
{
    var w = W;
    // 逆シャッフル
    for (int c = C - 1; 0 <= c; c--)
    {
        // w < 追加部分の場合
        if (w <= B[c])
        {
            w += A[c] - 1;
        }
        // 追加部分 < w < 削除部分の場合
        else if (w < A[c] + B[c])
        {
            w -= B[c];
        }
        // 削除部分 < wの場合
        else
        {
            // skip
        }
    }
    return w;
}

問題B. 最高のコーヒー

できるだけおいしいコーヒーを消費期限前に飲みまくろうという問題。
初日はすべて期限前だが、最終日はほとんど期限切れのため、最終日からさかのぼって飲むコーヒーを決めるといい。

/// <summary>まともにやる</summary>
private ulong small()
{
    parse(lines, t);
    ulong satisfaction = 0; //累積満足度
    // 最終日から順に消費期限内かつ残数1以上を割り当てる
    for (ulong k = K; 0 < k; k--)
    {
        var ok = coffee.Where((c) => (c.t >= k && c.c > 0));
        if (ok.Count() == 0) continue;
        var max = ok.Max((c) => (c.s));
        var drink = ok.First((c) => (c.s == max));
        drink.c--;
        satisfaction += max;
    }
    return satisfaction;
}

largeは日数が莫大なので、1日ずつやっていては終わらない。コーヒーの種類が比較的少ないので、同じ物を続けて飲むことが多くなるということに気付けば解ける。

/// <summary>工夫する</summary>
private ulong large()
{
    ulong satisfaction = 0; //累積満足度
    parse(lines, t);
    IEnumerable<Coffee> temp = coffee;
    // 最終日から順に消費期限内かつ残数1以上を割り当てる
    for (ulong k = K; 0 < k; k--)
    {
        // 残0を消しておく
        temp = temp.Where((c) => (c.c > 0));
        if (temp.Count() == 0) break;
        // 期限前を選択
        var ok = temp.Where((c) => (c.t >= k));
        if (ok.Count() == 0)
        {
            // 一番期限の近い日までスキップ
            var newerDate = temp.Max((c) => (c.t));
            k = newerDate + 1;
            continue;
        }
        var smax = ok.Max((c) => (c.s));
        var drink = ok.First((c) => (c.s == smax));
        // 何日同じ物を飲み続けるかを求める
        var other = temp.Where((c) => (c.s > drink.s));
        // 他に無いなら、残日数、あるだけ飲み続ける
        if (other.Count() == 0)
        {
            var only = (k < drink.c) ? k : drink.c;
            drink.c -= only;
            satisfaction += smax * only;
            k -= only - 1;
        }
        else
        {
            // 消費期限の一番近い飲み物まで飲み続け
            var tmax = other.Max((c) => (c.t));
            var only = (drink.c < k - tmax) ? drink.c : k - tmax;
            drink.c -= only;
            satisfaction += smax * only;
            k -= only - 1;
        }
    }
    return satisfaction;
}

問題C. ビット数

ある数字を2つの数字に分けるとき、一番ビットが多く立つように分けるという問題。
smallは愚直に総当たりで解ける。

/// <summary>まともにやる</summary>
private int small()
{
    var P = 0;
    for (ulong i = 0; i <= N / 2; i++)
    {
        var p = bit(i) + bit(N - i);
        P = (P > p) ? P : p;
    }
    return P;
}

largeは法則を見つけて解かないと終わらない。自分は、下位ビットから見て行って、0の場合⇒1+1に分ける、という感じで解いていった。

/// <summary>工夫する</summary>
private int large()
{
    ulong N1 = N;
    ulong N2 = 0;
    int last = 63;
    // 最上位の1の場所を得る
    for (; 0 <= last; last--)
    {
        if (((1ul << last) & N1) > 0) break;
    }

    // 最下位ビットから見ていき、0ならnから引きN2に足す、1なら何もしない
    for (int i = 0; i < last; i++)
    {
        ulong temp = 1ul << i;
        if ((temp & N1) == 0)
        {
            N1 -= temp;
            N2 += temp;
        }
    }
    return bit(N1) + bit(N2);
}