Hatena::Grouptopcoder

kohyatohの日記

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

2011-02-11

SRM497

| 16:00

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

Easy250PermutationSignatureAC (8min)やるだけ
Medium550CssRulesWAxthml?の構文解析
Hard1000ModuleSequenceUnopened-

Ratingが対数関数みたくなってるんだけど...


09:00 部屋割り

Room 17. id:cafelierさんと一緒の部屋!


09:05 Easy

ん?Iなら今までより一つ大きいやつ置けばいい。Dなら前のを全部1ずつ持ち上げるだけじゃない?

->書いた。サンプル合わない。

Dで持ち上げるとき、Iがあったらそれより前は持ち上げなくていいみたい。

適当に書いてサブミット。230点ぐらい。まあ自分にしては速い方かも。


09:20 Medium

XHTML構文解析きた。

とりあえず構文解析ライブラリを取り出し、正しく構文解析をするところから。


ゴリゴリ書く...どうにかサンプルを正しく構文解析できるようになった。


問題そのものだけど、1タグあたり最低でも30文字使うのでタグの最大数が50*50/30≒100ぐらいになり、memo[タグ番号][bの色][uの色][iの色]でメモ化再帰すればいい。

計算量はタグ数*7^6で大丈夫なはず。


書く...

色として、「未定」を考えてなかった。「未定」をいれて8^6に修正。

残り2分でサンプル合う。軽く見直してサブミット。230点ぐらい。


HardはUnopenedです。


10:20 Challenge

550でメモ化を忘れている人いないかなーと思ったけど、そんなおっちょこちょいな人はいなかった。

250もみんななんだかんだ言って合ってそう。

チャレンジせず。


結果

AC/WA/Opened

230.32 + 0.00 + 0 = 230.32 93位(部屋7位)

2086 -> 2119


550でansの更新部分でなんかおかしなバグが入っててWA.

しかもそれ直してもさらに一箇所タイポしてた。


レーティング的にはまたまたまた微増。


復習

同部屋でシステムテストを落ちたのは3つだけ。

うち一つは自分で、もうひとつは550のタイポだったので、これでチャレンジできないのは仕方がないと思う。


250速かったのは時間に気を配った練習の成果だと思う。

しかし550が。

書くの遅いし、イージーミスで落ちるし。

イージーミスをしてるのは一つ一つがおろそかになったからで、もうすこし気をつけないといけない。

特にタイポとかは見直してもほぼ発見不可能で、コーディング時に気を抜かない様にする、ぐらいしか対策が思いつかない。


Mediumは本気で構文解析しなくてもスタック使えばどうにかなるので、そっちでも書けるようにしておくべき。


それにしても、2200に手が届きそうで届かない現状はどうにかならないものか...

cafeliercafelier2011/02/11 16:14タイポは「できるだけ自分でテストケースを網羅する」で防げるものだけでも防ぎたいなあ、と思っています。今回の私のSystemTest落ちは
for t,c in {b,u,i}×{黒,灰,緑,青,黄,赤,白}: assert solve("<t id='x' style='color:c'></t>")==1
こういう最小例全チェックさえしていればすぐに発見できるものなので…

kohyatohkohyatoh2011/02/11 17:26ありがとうございます。
たしかに、見直して「合ってる!」と思っても、出来る限りテストケースで確かめたほうがいいですね。
テストは普段TLEチェックしかしてなかったので、今度からはこういう入力が複雑な場合は最小例全チェックもやろうとおもいます。

kohyatohkohyatoh2011/02/11 17:40練習の時に、書く->即サブミット->落ちる->修正->即サブミット->...をくり返しているのも問題ですね。
一発でAC取れるよう検証するのも練習にいれないと...