GoogleCodeJamJapan予選

http://code.google.com/codejam/japan

この日は時間がなくて、結局Bだけ解けなかったが、よく考えたら、解けそう。
というか、えらい3問とも簡単そうに見えた。
やっぱり母国語だと、問題の理解に面倒がない!

A.カードシャッフル

N枚のカードがあって、M回カードを切る。Ai枚目からBi枚をつまんで上に載せる操作をする。M回カードを切り終わったとき、W番目のカードは?という問題。

後ろから遡るプログラムを作る。最後に求めたい番号のカードWが、何番目にくるか求める。
単純だが、計算ミスをしてしまって手こずる。

B.最高のコーヒー

N種類のコーヒーがあって、どれか1つを1日1杯飲むのK日続ける。コーヒーの種類それぞれAi杯残ってて、賞味期限がBi日で、このコーヒー1回飲むときの満足度がSiだ。じゃあ、最大に満足するには毎日どのコーヒーを飲めばいい?という問題。

消費期限があるから、最初から常に満足度最高のコーヒーを飲んでいけばいいじゃない、と思っていたけど、Smallが通らなかった。
よくよく考えたら、先に1番美味しくて長持ちするのを先に飲んでしまったら、2番目に美味しくて長持ちしないのが飲めなくて勿体無いよね、という状況に陥ってしまう。この手は、最初ほど選択肢が多くて、最後になればなるほど(消費期限を超えてしまうから)選択肢が少なくなるパターンだから、選択肢が少ないほうから貪欲に美味しいのを選んでいけば、ポイントが最大になるのよね。

C.ビット数

関数f(x)は、xを2進数で表現したときの1のビット数です。ある整数Nが与えられて、N=a+bとしたとき、f(a)+f(b)の最大値を求めよ、という問題。

aは111111(2)のような全て1の数とすれば良いという仮説を立てて、検証してみて大丈夫だったので、トライしたら通った。数学的には検証していない。

Pythonで助かった

largeは10^18とか出てきて、INTじゃあ使えないんだけど、Pythonの整数型で問題なく扱えたのlaegeでも何も考えずに回答できて助かった。まぁ、Decimal型を使えば良さそうな範囲だから良いのだけど。

結果

AとBのlargeは通っていたので、決勝進出。上位200人にはTシャツプレゼント。頑張ってみたい。