Google Code Jam Japan 2011 予選

参加してきた。

result

54点 2:14:34 / 1:21:26 1:21:52 / 2:06:07 2:14:34 / 14:33 15:11
35位

予選通過。

A. カードシャッフル

問題

M枚のカードの山があり、上から順に1,2,...,Mの番号がついている。
以下のカットという操作をC回行う。

上から数えてA[i]枚目から、連続するB[i]枚を取り出し、一番上にもってくる。

全てのカットが終わった後で、W枚目に来るカードは何か。

試行錯誤

えーと、Mは10^9と大きい。
でもCが100以下とかなので、連続するカードは一まとめにして扱えば、
カードは高々300枚とかそんなくらいになるのでシミュレーションできるかな？

ちょっと書くのが面倒そうなので先にB,Cを読む。

（Cを解いてきた後で）
実装始める。
えーと、カードの束をL,L+1,...,Rをひとまとまりに、[L,R]として、

カードが左端から分断される場合
途中から分断される場合
最後まで分断が終わらない場合
途中で分断が終わる場合

みたいな感じに場合わけが必要？？
なんかめんどい。サンプル合わない。+1とか-1とかつけたしたりしてみる。
サンプルあった。
サンプルが弱いので、適当に自分でケースを作って試す。

合わない。デバッグする。
ようやくできた。small提出。通った。largeも提出。

B. 最高のコーヒー

問題

1日に1杯だけコーヒーを飲む人がいる。
N種類のコーヒーがあって、それぞれの賞味期限はti日で、量がci杯分、そのコーヒーを一杯飲んだときの満足度がsiである。
この人が得られる最も高い満足度を求めよ。

試行錯誤

初回問題文が理解できなかったので飛ばしてCへ。

（A,B解き終えた後）
んーと、smallはどうやるんだろう。費用流でいける気がする。
二部グラフで、左側にN個のコーヒーに対応する頂点、右側に日に対応する頂点を作って、満足度を費用とする枝で、左側と右側の頂点を結ぶ。
このグラフに対して最大費用最大流を求めればよくて、ちょっと変形すると最小費用最大流になる。おｋ.

Largeだと日数がバカでかい。どうしよう。
あー、右側の頂点を1日じゃなくて、日の区間にしてやればいい。
頂点1が1日目から10日目とかみたいな感じで。

書いた。サンプル合った。
small提出。合った。おｋ−
largeダウンロード、提出。
提出後ちょっと見直し。

これINF大丈夫か微妙に不安。INFの値を試しに1<<40から1<<62に変えてみる。
diff取ってみる。
あれ？？？答え変わったぞおい！！！INF小さすぎだった。
慌ててリサブミット。

C. ビット数

問題

N = a + bを満たす、非負の整数a,b≧0について、
f(a)+f(b)の最大値を求めよ。
ただしf(x)はxを二進数表記にしたときの1の数である。

試行錯誤

一番ときやすそう。
うーんどうやるんだろ。
下一桁が1のときは1,0とするしかない。
0のときは？

貪欲に1,1にしちゃっていいんじゃないだろうか。
サンプル合う。
うーん。small提出してみる。合っちゃった……
largeも提出。多分大丈夫だろう。

結果発表

全部通ってた。B危なかった。