Hatena::Grouptopcoder

kohyatohの日記

 - 非数学系な人のTopCoder参加記です。

2011-02-03

SRM496

| 13:58

ソース・成績(要ログイン)

Easy250ColoredStrokesAC(9min)やるだけ
Medium500OneDimensionalBallsAC(48min)分解
Hard950YetAnotherHamiltonianPathOpened-

ひさしぶりのスピード勝負の回。


21:00 部屋割り

Room 30. なんだか青い部屋。


21:05 Easy

ぱっと見、赤、青それぞれで線分の本数を数えるだけに見える。

要するに、線分が始まるマスを調べればよくて、これは直前のマスと今のマスが同じ色(Gは今調べてる色とみなす)かどうか調べればよい。

境界でバグが出やすいけど、こういう時は前回値を別変数にしておけばよかったはず。


書く。テスト->サンプル通らない!なんで?

->よくみるとif()のなかに前回値の更新が入ってた。直して提出。220点ぐらい。

みんな速いし、220はちょっとまずいなぁ。


21:15 Medium

みんな速解きしててこのままではまずいと少し焦りながら開く。

そのせいか「ボールが衝突すると、くっついて同じ方向に進む」と誤読する。

なにその超物理...


ボールがくっつくなら、必ず同じ座標になってしまうので、secondPictureでボールが重なっていないという条件に反する。

ということは、ボールは一回も衝突してない!

ならば、firstPictureをソートして適当にDPすればいい。


書く。テスト->サンプル通らない!なんで?

手で解いてサンプルと突き合わせても合わないので、問題を読み直す。そして誤読を発見。あちゃー。


ボールがクロスすることがあるので、そのままDPにはできない。

ちょこちょこ紙に書いて試してみる...これ、移動幅をdと決めれば、ボールが干渉するのは2*dごとだけ。

なら、mod 2*dで分類してそれぞれで場合の数を求めて掛け合わせればよい。mod 2*dで分類された中では、互いに2*d以上離れているので、クロスは起こりえず、最初誤読して書いたDPがそのまま使える。


書く...サンプル通らない。

プログラムがバグバグで苦戦。なんとか全部直して提出。210点台。ひどい...


22:05 Hard

なんか間違って開けたけど、500の確かめをしていたので読んでない。


22:20 Challenge

250で境界を見落として、っていうのは、サンプル通らないからないはず。っていうかこの250で落ちるっていうのはありえない気がするので、500で明らかに間違ってそうな人を探す、という方針でいく。

そもそも自分も500落ちそうなのであまり挑戦はできない。


...500でぱっと見落ちそうな人はいない。っていうかみんなコード複雑で読めない。

250にシフト。なんか色塗りをシミュレーションしてる人が多いんだけど、なんでだろう。


終了間際にGのとき無条件で+2している人を見つけて、「え、これなに?」と思ったけど、これで間違えてたらもうとっくに撃墜されてるよなぁ、と思って手を出さず。


結果

AC/AC/Opened

225.74 + 218.18 + 0 = 443.92 134位(部屋2位)

2058 -> 2086


またまた微増。


復習

結局部屋の250が5つもSystem Testで落ちた。

部屋運良かったのに活かせなくてすごくもったいない。

これぐらいの順位だとチャレンジ成功で一気にあがるから、機会は逃がさないようにしないと。


あとは、500が遅い。毎回40分台かかってるし。

500を20分台で解けるように実装力をつけないと。

とりあえずこれからの練習では、Tayamaさんのするめタイマーを使って時間に気を配ります。