読者です 読者をやめる 読者になる 読者になる

Qualification Round 解説

さて、先々週の土曜日に行われたGoogle Code Jamの
Qualification Round 1の解説を今更してみます。
かく言う私はついうっかり問題CのLargeを
Time Expiredで落としてしまったため76点という
なんとも恥ずかしいスコアだったのですが、
きっと解説くらいはできるような気がしています(笑)。
コードはかなり汚いので、掲載するのはまたの機会にします。


問題A
http://code.google.com/codejam/contest/dashboard?c=433101#s=p0
日本語訳 ⇒ http://d.hatena.ne.jp/phero/20100508/1273291628


例えばスナッパーが5個あるときを考えてみます。
するとONを1、OFFを0で表すことにすると、

00000    ... 0回スイッチを切り替えた状態
10000    ... 1回スイッチを切り替えた状態
01000    ... 2回スイッチを切り替えた状態
11000    ... 3回スイッチを切り替えた状態
00100    ... 4回スイッチを切り替えた状態
...

という状態遷移となり、最初に電灯が点くのは
11111となったときなので 31回 スイッチを切り替えた時だとわかります。
つまり、
K回切り替えたときに2進数で下N桁が全て1になっているか否かを判定せよ
というだけの問題であるとわかるわけです。


そうとわかれば話は簡単で、

if K & (2 ** N - 1) == 2 ** N - 1:
    print 'Case #%d: ON' % test_case_id
else:
    print 'Case #%d: OFF' % test_case_id

で根幹となる部分が完成ですね。


問題B
http://code.google.com/codejam/contest/dashboard?c=433101#s=p1
日本語訳 ⇒ http://d.hatena.ne.jp/phero/20100508/1273298526


要は t1, t2, t3, ... という整数のリストが与えられた時に
t1 + y, t2 + y, t3 + y, ... の最大公約数をTとして、
Tが最大になるようなyを求めなさい、という問題ですね。


これは2数a, bの最大公約数は(a - b)を割ることができる、
という事実を利用しましょう。
t1 + y と t2 + y の最大公約数Tは、t2 - t1 を割ることができますので、

t1 - t2 , t2 - t3 , t3 - t4 , ... の最大公約数を求める問題に帰着できます。

あとは簡単ですね。
ただ、t1 = t2 のケースや |t1 - t2| = |t2 - t3] のケースなどに
注意をしましょう。


問題C
http://code.google.com/codejam/contest/dashboard?c=433101#s=p2
日本語訳 ⇒ http://d.hatena.ne.jp/phero/20100508/1273299735


問題文がとても親切でわかりやすいですね。

k人乗りのジェットコースターがあって、1日にR回運転される。
並んでいる人はNグループあって、それぞれ g1人、g2人、... gN人。
グループが分断されないように、また順番を抜かしたりしないように乗る。
乗り終わった人(グループ)はまた列の後ろに並ぶ。
この時、1人1ユーロの料金だとして1日にいくらの売上になるか。

Largeの問題では R が 1億以下、kが10億以下、という
なんとも凄まじいリミットになってるので、
単純なループで実装するととても時間内に計算が終わりません。
そこで周期性に着目します。
幸い、N ≦ 1,000 なので、高々1,000回もループさせれば
周期性が現れます。
周期的であることがわかれば、あとはただの割り算の問題ですね。



という感じで、かなり簡単な3問でした。
明日のGoogle Code Jam Round 1 A〜C も
気合を入れて頑張ってみます。