金魚亭日常

読書,ガジェット,競技プログラミング

Google Code Jam Kickstart 2017 Round B

Google Code Jam の学生を対象としたやつ? 就職につながる感じなんだろうか.

年中いつでも登録できて,数か月おきにコンテストが開催されるらしい.

とりあえず,過去問を解いてみた

ちなみに,AtCoder などのようにソースコードを提出するのではなく,解答を提出する.

A. Math Encoder

Dashboard - Kickstart Round B 2017 - Google Code Jam

例題を試していたら組合せ数に法則性が見えてきて,

  • ある(最小値,最大値)の組をとる部分数列の個数は,2の累乗

になりそうだったので,それで提出.

large は,素朴に書くと Ruby だと時間がかかって答えが出なさそうだったので,C++に変更. なお,解答を提出するので時間がかかっても答えが出ればよい.

C++ だと最初負の数が出てきて,どうやらオーバーフローしているみたいだと気づき,適宜 109+7 で割った余りを使うように変更.

最終的に,Ruby の方もC++ の解答に合わせて書き直すと速くなった(最初は2の10000乗とか計算していた).