Hatena::Grouptopcoder

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

2012-02-09

Topcoder SRM532 Div2 反省

| 03:58 | Topcoder SRM532 Div2 反省 - iwbtr - kmats を含むブックマーク はてなブックマーク - Topcoder SRM532 Div2 反省 - iwbtr - kmats Topcoder SRM532 Div2 反省 - iwbtr - kmats のブックマークコメント

Div. Place: 554/1361

Points: 234.58

Solved: ox-

Rating: 930 -> 914 (-16)


registerした後仮眠を取って起きたら0:59.250を理解するのに時間がかかった..

systestでは600点問題大虐殺.ただのgreedyで解くとx.xの場合に引っかかることに終盤気付くも950が気になってそっちを優先してしまったorz


532 Div2 250

Mr. Dengklekが数えそこねたアヒルの数の最小値を求める問題.

アヒルに付いた数字の最大値をmax_num, 最小値をmin_numとして,

return (max_num - min_num + 1 + 1 - ducks.size());

するだけ.


532 Div2 600

できるだけ綺麗な鎖の列を作る問題.

鎖を場合分けすると,

  1. "xyz"のように錆のない鎖
  2. "x.."や"xy.", "..z", ".yz"のように片端が錆びている鎖
  3. "x.z"のように中央が錆びている鎖
  4. ".y."のように両端が錆びている鎖

の4通りになる.1番目は何も考えず連結に使えるので,int sumに値を保持しておく.

2番目はそれぞれ左端もしくは右端にしか使えず,3番目は左端・右端両方に使える.

そこで,2番目もしくは3番目に属する鎖は別途vectorなどに保存しておき,そこから"最も値が大きくなる左端・右端の組み合わせ"を探す.

ただし,"x.z"型の鎖はそれ一つで両端に使うことはできないので,そのことに注意する必要がある.

4番目は連結不可なので,4番目に属する鎖の内最も値が大きいものと,1〜3番目を連結した鎖の値を比べる必要がある.


引っかかるポイントはおそらく2つ.

  1. 4番目の鎖の処理を最後に行うのを忘れる
  2. 3番目の鎖の処理を間違う

この内1つ目はExamplesの中にあるので,大抵の人が気付くはず.

2つ目は,初めにint left, rightという左端・右端用の変数を用意しておき,chainsを順に見てその場で大小比較することにより左端候補・右端候補を決めてしまうgreedyな方法を思いついてしまうとハマる.

この方法の場合3番目の鎖の処理で迷うが,それっぽい条件でleftもしくはrightと比較する処理を書くとExamplesは通ってしまう.自分がこれだったorz


例)"..3", "2..", "5.4", "6..", "111"

正解は"5.41116..."で13になる.

しかし,greedyな方法の場合,"5.4"を見たときにこの鎖を右端候補としてしまう可能性がある.

(まだ"6.."を見ていないので,左端候補で間違いないといえるような処理は書けないはず.)

よって,"..31115.4"で12・・というような誤答を返す可能性がある.


コードを書いている途中も"greedyだと無理じゃないかなあ"と思いつつもExamplesが通ってしまったので"まあいいや"と思ってしまった・・

950を解いている途中で無理だということに気付くも時すでに遅し・・Easyはともかく,Mediumは回答の妥当性をちゃんと確かめないと駄目だと痛感..


532 Div2 950

愚直に全探索するとオーダーが大きすぎてしまう問題.

dpでなんとかするのかな.

なんかdpが必要そうな問題は毎回ほとんど手を付けずに終わってる気がする・・


反省点

  • 起きたら開始直前だった
  • 回答の妥当性を確かめずに提出してしまった

教訓

  • 仮眠しなくてもいいように前日・当日の睡眠を調整する
  • 回答の妥当性をちゃんと確かめる,もしくは気になったケースは手でちゃんと確かめてからsubmitする