Hatena::Grouptopcoder

iwbtr - kmats このページをアンテナに追加 RSSフィード

2012-03-21

TopCoder SRM538 Div2 反省

| 19:38 | TopCoder SRM538 Div2 反省 - iwbtr - kmats を含むブックマーク はてなブックマーク - TopCoder SRM538 Div2 反省 - iwbtr - kmats TopCoder SRM538 Div2 反省 - iwbtr - kmats のブックマークコメント

Div. Place: 205/951

Points: 308.46

Solved: xo-

Challenge: +1 / -2

Rating: 1050 -> 1080 (+30)


個人的にも全体的にも割と荒れ試合だった模様.


538 Div2 300

問題文を読みながら"DFSでいいじゃん"と思ってしまったorz

?*50の場合計算量は2^50・・・DFS, BFSに対する計算量の見積もり癖が無かったのが敗因.

300なめすぎ.テストしなさすぎ.

?が全部Lの場合と全部Rの場合の2通りだけ試せばよかったですね.


538 Div2 500

一方こちらはマトモにやるとTLEになることにしばらく格闘してから気付く.

与えられたパリティビットと同じ偶奇のステップ数になるか,という”偶奇”の一点だけが問題なので,何か簡単な方法があるのだろうとサンプルケースを眺めてみれば,最後に訪れる点(x, y)が(x+y) % 2 == 1であればステップ数は奇数,== 0であれば偶数になることを発見.


(x+y) % 2 == 1になるような点を含んでいれば,1:CAN, 0:CAN

そのような点しかなければ,1:CAN, 0:CANNOT

そのような点が一つもなければ,1:CANNOT, 0:CAN

となる.


next_permutationを使って全探索するとTLEなので,これで1回撃墜.


538 Div2 1050

おおよそどのように組めばいいかは分かるも,そこそこ時間をかけて2問解いた後に解くには割と重かった.


反省点

  • 300をなめた
  • テストをサボった
  • DFSに対する計算量の見積りがあまかった

教訓

  • 普段より高い配点の場合は特にテストに気をつける
  • DFSを使うときは計算量に特に気をつける

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/kmats/20120321