Hatena::Grouptopcoder

kohyatohの日記

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

2011-02-28

SRM498

| 22:30

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

Easy250FoxSequenceAC (18min)実装
Medium450FoxStonesAC (30min)やるだけ
Hard1000FoxJumpingCompiledできない...

きつね回。そして速解き回。


26:00 部屋割り

Room 19. 普通。


26:05 Easy

実装ゲー来た。

なんか考えがまとまらず時間を浪費。

しかもバグを出して時間を浪費。

提出。180点ぐらい。おいぉぃ...


実装ゲーならChallengeが期待できるなぁ、と思ったけど、サンプル見るとなかなか親切なので撃墜ケースが思いつかない。


26:25 Medium

450だし簡単なんだろう...と思って開くが、なかなか思いつかない。

サンプルでマークが全部一直線に並んでるけど引っ掛けっぽい。


...

...

うーん...とりあえず、1つのマークに絞って考えると、そのマークを囲む四角の中なら交換できて、そうでないなら交換できない。

で、そういう束縛が全てのマークについて成り立つ。

要するに、全てのマークからの距離の組み合わせによって交換できるかどうかが決まる。

全てのマークからの距離の組み合わせが同じ石がn個あるなら、その中での順列はn!通り。

それを掛け合わせていけばいい。


書く...サンプル合わない。

問題分を見返すと、距離がmax(dx, dy)になってる!普通にマンハッタン距離(dx+dy)だと思ってた!

書き直す->サンプル合う。最大ケースもよし。提出。250点ぐらい。終わった...


26:50 Hard

まだHardできれば巻き返せるかも!


...と思ったけど甘かった。

とりあえずメモ化探索だけ書いたけどTLE.


27:20 Challenge

450で変なことしてる人がいないか必死に探す...いない。

あきらめかけつつ250のコードを見ていると、a=0の場合にYESを返しているひとを発見。撃墜。


結果

AC/AC/Opened

186.38 + 258.69 + 0 + 50 = 495.07 231位(部屋7位)

2119 -> 2105


微減。あーあ。

最近volatilityが下がってきてる。

ここらへんのレートで安定されても、もどかしいだけなんだけど...


復習

速解き回での遅さが改善されてなかった。


250は差分数列を作れば実装簡単かつ堅牢だったらしいし、450はmapにvector突っ込んでも時間的に全然大丈夫。

無駄なコードが多い。計算量の見極めが甘い。


なんかこう、もっと見極めて、過不足なくちょうどいいコードを書けるようにしないといけない。

実行時間で最適とか、コードが最短とかよりも、コーディング時間最短を目指すべき。

もっというと、コーディング時間だけでなくて、考える時間も含めて、開いてからサブミットまでの時間を最小化するようにしないといけない。


あと、1000とかまだ解けないので、難しい問題もどんどん解かないと。

やはり赤コーダーになるにはもうひとつ突き抜ける必要がある。