Hatena::Grouptopcoder

ir5は引退した

 | 

2011-05-03

~反省~

23:13

SRM495以降結果があまり良くなくてついに赤色閥から外されてしまったので反省をします.

SRM495以降

495以降調子よくない.(70位が調子いいか自分にとって調子悪いかの境目)

死因リスト

  • 495: Easy簡単だったのにわけわからん実装に走る,Mediumで思考の詰めが甘くて落ちる
  • 497: Easyが若干遅い上にMediumが手に負えるものではない(木は苦手)
  • 501: Mediumで配列の境界外参照に気付かず長時間はまる
  • 502: Mediumで思考の詰めが甘い,resubmission
  • 503: MediumでN=1を試してなくてresubmission, challengeで-25
  • 505: 300で思考の詰めが甘い,500で単純なケースをテストしてなくて気付くと時間切れ,challengeで-25

反省

  • 思考の詰めをちゃんとするということと急いで解くということの間には実に悩ましいトレードオフがあるが,前者を優先すべき.(前者が適当だと急いでも0ptsになって大怪我だしそもそも自分が悩むくらいなら適当にやって落ちるであろう人々がたくさんいる,はず)
  • submitする前にN=1とか自明なケースで試す.ここ最近はコード書き終わっても「どうせ合ってる」とか思って全然テストしないことばかりだったし明らかに良くない.
    • 全体をざっと眺めるくらいのこともした方がいいかもしれない.これも最近全然やっていないことだった.
    • 解法が分かってれば何がEdgeCaseになるか分かるはずで… あとexampleはあまりあてにしないほうがよいかもしれない
  • Challenge下手だからやるなってことはないのだけど,高々1つしか通らないことが分かってるときは極力しない方がよさげ,negative scoreは本当に悲惨…

  • 上に挙げた問題の中で「自分には手におえないししょうがない」と思えるのは496のMediumだけなので,それ以外は理想的な時間で通せるようにしておきたい

Member SRM 505

22:42

大怪我.


DivLevelProblemNameStatus
1300RectangleAreaFailed System Test
1500SetMultiplesFailed System Test
11000見てないOpened

300

  • ややこしそう
  • bd=ab*cd/ad であるので,列の2辺の行の2辺の合計4つのうち3つが決まると,あと1つが一意に決定される.基本的にはそれを伝播させるだけでいいのでは.
  • 書く.提出.

500

  • 数論かー
  • なんか2つの区間のunionとか気持ち悪いので,とりあえず区間が1つだけのときを考える.
    • 区間が1つで閉じているときはk=2さえ考えればよい? そうっぽい.
  • 問題は区間[A,B]が区間[C,D]に吸収されるときである.なんか依存関係とか考えると色々ややこしそう…?
    • と思ったけど,「bがaの倍数で,cがbの倍数なら,aもcの倍数である」という推移律が自明にあるので,それを使うと,まず区間[A,B],[C,D]を独立に考えてk=2で圧縮して,その後[A,B]の方で残ったものを[C,D]に吸収してもらう,というのが良さそうである.
  • うむ.吸収.で,どうやるの?

    • 愚直にやるとTLEするし高速にやらないといけないが…
  • kを愚直に1ずつ増やすとだめだけど,kはある程度大きくなると中間のステップをスキップできるようになって十分速くなるのでは? という気がする.多分正しい.
  • 書く.バグりまくる.
    • テスト.大きいケースでの時間は大丈夫.良さそうなので提出.時間掛かりすぎ…

1000

  • 時間ないし開いただけ.

300(再)

  • 解法がかなり嘘くさい気がしてきたのだがCounterExampleが思いつかなかったので放置.

500(再)

  • またresubmissionなんてことはやめてもらいたいが…
    • 500,501,503,504とかでテストする.3が返ってくる.
    • ?
    • …またかよorz
    • 原因を探す.分からない.時間が無い.発見したがもうすでにCoding Phase is ended...

Challenge Phase

  • なんか300でdfsしてる人がいて怪しい気がしたけどそんなことはなかったらしくて-25.

System Test

通らない

xxx -25.00pts 2358→2171


さすがにもう赤から落ちることは無いだろうと思っていたら黄色に戻ってしまった.終わってる… TopCoder様は相当お怒りのようである.

300はアイデアは正しいけど,セルを更新する順序を適当にやりすぎたのが原因だった模様.500は本当にしょーもないミスだったしもうなんか嫌や…

Challengeの成功率もここ最近はかなり低くてやばい気がするしどうすればいいかわからんね.

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/ir5/20110503
 |