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