子育てプログラマーの日常

とあるプログラマーの日常をだらだらとつづってます。
家族構成 妻:アロマセラピスト 息子:2007年8月生まれ 娘:2011年12月生まれ

Google Code Jam Japan 2011 予選[追記あり]

忘れないうちに、考え方だけメモ
練習問題と同じ3問でした。

解いた順序はB,C,A

問題A

最初に、普通にリストに1〜Mの数値を入れることを考えたんだが、
最大値が109なので、その方法では計算が終わりそうにない。
で、最初の問題でつまずくとまずいと思い、この問題をパスして最後に解いた。

で、問題Bを解く時に、1〜10という様に数値を範囲で扱っていただので、
この問題も同じようにすることで解決

カード枚数10枚で5枚目から2枚カットの場合
  [1-10] → [5-6],[1-4],[7-10]
という感じに扱う。


問題B

解き方の方針としては、コーヒーの種類が最大で100なので、
満足度の高い順、消費期限の短い順にソートして、
満足度の高いものから、消費期限ギリギリとなるように、
飲む日付を決めていく。

問題Aと同じように、飲む日は範囲で扱う


問題C

この問題、解き方を間違えて、大幅に時間をロス
まず、大きい整数を扱うようにclassを定義して、2進数に変換した。

でも、よく考えると、Largeでもunsigned __int64型の範囲に収まる。
その場合、直接ビット列を見ればよかったので、この部分作る必要がなかった。

2進数に変換した後の方針は各桁を下から見ていき、
  1の場合
    2つに分けると必ず0と1、合計に1を追加
  0の場合
    0と0で分けるより、上の桁を考慮して1と1に分けるほうが、
    合計が多くなるので、上の桁を借りてきて2を追加
    上の桁を借りてくるのは、順に上を見ていって最初に1が見つかるまで
    01を反転
というのを繰り返し



とりあえず、全問正解できたんだけど、
Cで無駄なことやってたり、Aで数を範囲で扱うことに気づくのが遅れて、
smallとlargeで違うコードになってたりと、時間のロスが多かった。

決勝は3時間なので、もっと効率良く解かないとな〜
目標はGoogleTシャツ(200位以内でもらえる模様)

ってか、予選通過の通知が来ないのだが、提出ファイルの不備とかがあったらどうしよう...


ところで、カード1枚0.1mmとして計算してもカード全体の厚さが10km…
コーヒーの消費期限にいたっては54億年以上って…


追記
他の人のロジックを見て、軽く凹み中

Aに関しては、この人のように、
最後から逆にカットしたものを戻していって、
最初の位置を逆算する方がはるかに効率が良い

Cに関してはスピードは同じだろうけど、
この人の考えのほうがはるかにスマート

Comments

Comment Form