Google Code Jam 2010 Qualification Round

出てきた。最近の練習不足の所為で色々と酷かった。
ここには書いてないが、一応毎日TopCoderのSRM過去問微妙に解いてたりはするのだけど。

早起きゲー、英語ゲーとの噂もあるが自分の場合根本的に力が足りてない。
最近生活がだれすぎてるので生活改善から始めることにする。

14:29 / 15:21 / 2:37:21 / 2:38:06 / 1:35:00 / 1:35:39
1WA / / 4WA / / 5WA

99/99点 128位

ひとまずqualは通過！

n個のsnapperが電源から直列につながれており、n個目のsnapperにはライトがつながれている。
各snapperにはオン・オフの状態があり、オンならば電気を通す。
指を一度ならすたびに、電気の通っているsnapperのオン・オフが切り替わる。

k回指をならしたときライトが"ON"であるか"OFF"であるかを答えよ。

各スイッチの状態の図を描く。二進法か。
で、n個目のスイッチがオンかどうかを答える問題だよね？（←誤読）

Submit.→WA.

あれー？10分くらい問題文を読み直す。
あーライトがつながっててそれがオンオフかどうかってことか。
素子の状態に対応する二進数の各桁が全て1ならON.

Submit.→AC.そのままlargeも送信。

Standingを見てみる。どうもCからやっている人が多い？
Cのほうが簡単なのかな。まあCから読もう。

テーマパークにk人乗りのコースターがあり、一日にr回動く。
テーマパークにはnグループの客が来て、i番目のグループの人数はgi人である。
コースターの料金は一人一回1ユーロである。

各グループの客はコースターに並び、コースターに（グループの人が分かれないように、かつ割り込みはしないで）乗れるだけ乗るとコースターは動き出す。
乗り終わった客はまたすぐにコースターに並ぶものとすると、このテーマパークの一日の収入はいくらか。

r≦10^8,n≦1000,k≦10^9,gi≦10^7とする。

明らかにシミュレーションするとダメぽい。
nはとっても小さい。並び順の先頭はいつかループするよねこれ。
ループの部分は掛け算で求めて、それまでとループしきれない残りだけ足せばいい！

がりがり。えーとループ検出はどうすればいいんだ。各ターンの先頭を覚えて線形探索？
がりがり。サンプルあった。

送信。WA.
適当に直す。WA.何か泥沼。パニくる。
適当に直す。WA.
適当に直す。WA.
適当に直す。WA.

えーと、お前バカ？？？ちょっと落ちつけよ自分。

飲み物でも飲みながら一から書き直そう。
あるグループが先頭にくる最初のターンを配列で持てばO(1)でループ判定できるじゃん。
ついでに方針変更。

書いた。
Submit. AC. largeも送る。

あーも頭わるいなー。
問題演習の成果でてない。伸びてないどころかボケてんじゃねーの。

n個の数字tiがある。各tiにyを足した時にtiの最大公約数が最大になるような、最も小さいyを求めよ。

入力は64bitの整数に収まるとは限らない。

問題文の解読に手間取る。slarbosecondsて何？すらぼ秒？造語？意味がわからん。
結局何を求めればいいんだろう。

あ、入力は64bitの整数に収まらないらしい。
Javaつかうかな。今学期からJavaの授業とってるのが微妙に役に立ってるような。

（十数分後）
えーとt1+y,t2+y,……,tn+yの最小公倍数かー。
明らかにy足しても各項間の差は変わらないので、結局差の最小公倍数より大きくはならない。
んで、t1に何か足して、t1+yを差の最小公倍数の倍数にしてやると、他のも同時に全部差の最小公倍数の倍数になる。うん。

という訳で差の最小公倍数gを求めて、t1+yを差の最小公倍数倍にする最小のyを求める。
t1+y ≡ 0 mod gなのでy=((-t1 mod g)+g) mod g

書いた。WA.
なんかもーやる気でない。投げやりに直す。WA.

問題文読み直す。条件を見る。
なんか入力に同じ数があるらしい。
てきとーに線形探索して同じのあったら追加しない処理。

WA.ループの回数ミスっとる。
WA.もう一箇所ループの回数ミスっとる。しね。

AC. largeも送る。

おわってるなーじぶん。

laycurseさんかっこいいなー。はぁはぁ