GCJ 2011 Round1C

440位で通過。
http://www.go-hero.net/jam/11/name/phyllo
なんかもうグダグダだった。

A. Square Tiles

解けた。

タイルをあまりなく埋める問題。あまっちゃだめだからどう見てもgready。書く。提出。1A、1Bから比べると難易度が下がりすぎてるような気がして、少し不安になるけどlargeも提出。

C. Perfect Harmony

smallだけ解けた。

ハーモニーを作るために自分が出すべき音(整数値)をこたえる問題。ハーモニーは、ある音が他の音を割り切れる整数値のときハモっているという。
largeが点数高いからとりあえずsmallだけ通そう。LからHまですべて試してもいいよね。書く。提出。
largeを考える。lcmとかgcm使うにしても間に合うかどうか、、というよりどうやって使えばいいだろう、、、わからないので、Bへ。

B. Space Emergency

解けた。

宇宙船が決められたルートをブースターをうまく使って最短時間で行く場合の最小時間を求める問題。問題読んでるときダイクストラか？と思ったけど、ルートは決まってるので、ブースターをどのタイミングで使うかどうか。
というか問題が微妙にわからない。けど、とりあえずサンプルで補完。。
時刻tまではどこにいても使えないからそれまでに通れる星間は地道に通るしかない。残りの星間で一番長いところからブースターを使っていくようにするgreedyでいけそうかな。。。
書く。バグる。あれ、、というか途中からブースターを使うとき、その時間が小数の場合とかあって最終的に整数値って場合もありえるかも、、、
グダグダしてきたけどとりあえずsmall。出力結果を見る。おかしい！！値大きすぎだろう！！
よく見るとなんかL=0の時どうせ使わないから足すだけだなぁと思い、別処理にする。値が直る。。。？？？
再度提出。AC。
largeもどうせ計算量そんなにいかないと思って確認しつつ提出。

反省

とりあえず、440位で1000位以内なので通過。
上位の人が抜けてるので全体では低いかもしれないけど、通過できただけでうれしい：）
Round2がんばりましょう。

• 問題解釈が怪しいときはサンプルで補完するにしても、もう一度読み直してそれであってるかどうかはちゃんと確認する