Google code jam 2010 Round 1A - simezi

参加したよ。

409位 59点 2:38:29
32:38 33:16 / 2:17:41(4 WA) 2:22:29 / - -

またDPで時間取られたよ！！ほんと早くまともにかけるようになれよ！！
とりあえずRound1は通過。

赤と青のブロックを積み上げ(空中にブロックを置くことはできない)、縦または横または斜めのいずれかにk個同じ色が揃ったらその色のプレイヤーが勝ちというゲームがある。

今ある盤面が与えられるが、それを90度時計回りに回転させる。
回転させた後で、ブロックは重力を受けてまっすぐ下に落ち、地面に積みあがった状態になる。
この状態で赤、青のプレイヤーが勝っているかどうか判定せよ。

問題文を読む。うげ、またゲームっぽい問題だ……
と思ったら盤面の状態を判定するだけでよいらしい。助かった……

回転させて重力……とりあえず回転を書く。
重力は最初に隙間を全て右につめておけばいいか。書く。

あとは判定。
うーめちゃくちゃ長くなった。書いた。

あれ？全部勝者なしになっとるｗ
数字読み込んでなかったｗｗｗ

修正。サンプル通った。
small通った。largeも送信。

数列の隣り合う項の差が全てM以下であるときその数列はSmoothであるという。
数列に対し、以下の操作が任意の回数できる

D,I,Mと数列が与えられたとき、この数列をSmoothにするための最小コストを求めよ。

えー……とあからさまにDPぽい。数列の各項が0≦ai≦255とかあからさますぎる。

なんかよくわからんが書いてみよう。
手が止まる。どうしたらいいんだ？

i個目まで使って一番右の数がjのときの最小コストをdp[i][j]としてもてばいいのかな？
しかし漸化式がよくわからない。あたまわるくてしんじゃう！！！

あれトップの人もう全部解きおわってんじゃんｗ

漸化式を冷静に考えよう。
元々aiとmの差がj以下の場合があって？前までとaiを使って最後をjにするには？
前の値kからaiを並べてjをつなぐか、aiを並べてjに変更する？？？

そもそもaiを並べるやりかたはどうなんだ？？
前の値kとaiの差がm以下だったら単にaiを置けばよくて……
差がmより大きかったら？いや、dp配列は最後の値を0-255のパターン全部持ってるんで
それは考える必要ない！！

じゃあj→ai（変更？）→（適当に挿入）→kという作り方があって
これループにすればいいか！
あとaiをデリートするパターン！

実行。サンプル全然あわない。
何がおかしいんだ？もう時間ないしsmallだけで通すかなあ。。。

残り15分くらいまではプリントデバッグしよう。
dpを出力してみる。なんだこれ値がデタラメだ。
あれ？切り上げして1引かないのか？引いちゃだめだな。修正。
添え字も間違ってる。終わってるほどに頭わりーｗｗｗ

直す。サンプルとおった！！！
small実行。

おちたｗｗｗｗなんでだよｗｗｗｗ

あーmって0の場合もあるのか！！
m=0だったら一つ除いて削除すりゃいいんか？急いで修正。

時間切れ。くそが！！！
次のファイルダウンロード。

WA.しかも結構時間かかる。最適化オプションつけよう。

おいd*(n-1)がd*n-1になってるよ！括弧ついてねーよ！

WA.

あ、ちがうだろ！同じ値が何個かあるかもしれないから最大個数のやつ除いて削除。

WA.

そもそもちがう！！
値の変更できんだろクズが！！！！

dpに組み込まないとダメだ。
組み込んだ。okサンプルも正しい。

5度目の正直でsmall通った！！！
largeも実行。やたら時間かかる。これ最適化オプションつけてなかったら絶対に8分かかってるｗ
最大でも256^3*100なんだけどなー。3分くらいで実行終了。submit.

残り12分。Csmallだけできないかな。
読み終わった時点で残り3分。できなさそう。終了。