Hatena::Grouptopcoder

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

2012-01-21

Topcoder SRM530 div2 反省

| 01:23 | Topcoder SRM530 div2 反省 - iwbtr - kmats を含むブックマーク はてなブックマーク - Topcoder SRM530 div2 反省 - iwbtr - kmats Topcoder SRM530 div2 反省 - iwbtr - kmats のブックマークコメント

Div. Place: 238/911

Points: 234.58

Solved: 1 (250, 00:07)

Rating: 875 -> 929 (+54)

1000をChallengeで落とされ,500をSystestで落とされ意気消沈していたら何故かRatingが上がったでござるの巻.

順位を確認したら謎の238位.1200~1300人くらい参加してるときなら350位くらいか?

Editorialを見ると1000をPassしたのは一人もいないとか・・どういうことなの

緑になれたのはまあ良かったけれど,せめて500は通してもう少し上に行きたかった.


530 Div2 250

ボールが入ったN個の瓶をボールの数順にソートする.ただし瓶の位置は替えず,中のボールを移動させることで行う.このとき移動させるボールの数の最小値を返す問題.

移動前および移動後の瓶内のボールの数の差を取って全瓶の和を取り,1/2すればいいだけ.


530 Div2 500

2次元平面上に置かれた長方形のケーキから型(cutter)を使ってケーキを切り取る.与えられるのは切り取られた後のケーキと型.この2つから,ケーキは型のみを使って切り取られたか否か?という問題.

ケーキを左上から走査し,"."が現れたらそこを左上端としたケーキの一部分と型を比較.切り取られた部分が型に一致したら,その部分に適当な文字("o"など)を入れて次に進む.

全て走査し終わった後にまだ"."が残っているようだと型では切り取れない部分があるということになるので,NOを返す.それ以外ならYES.

・・という方法で解いたところSystestでfailed.走査開始条件を"."にすると,型の左上端が"X"の時に上手くいかない場合があるようだ..


530 Div2 1000

お!霊夢ゥー!

行(row)をステージ数,列(column)を次移行のステージへ進めるか否かの真偽値とするvector<string>が与えられ,スタートからクリアまで何通りの道があるか?という問題.

スタート地点からゴール地点までつながっているパスがいくつあるか,なので,つながっているノード間のパスのみを記憶してたどっていき,ゴールに辿りつけたら答えを+1(でいいはず・・).

が,それを深さ優先探索で書いてしまった.submit後にTLEが気になって20x20のinputを入れてみると0.11秒,これは無理だろうなあと思いつつも直す時間がなく,Challengeでは50x50を突っ込まれ予想通り陥落.

他の人のコードを見ると,スタート地点からあるノードmにたどり着くまでのパスの数を配列a[m]に格納しておき,ノードmからノードnへのパスがあれば,a[n] += a[m]とする・・という手法の人が割といて,なるほどと思った.が,全員落とされていた.はて?

まだちゃんとEditorialを読んでないので,後で復習したい.

というかあのflashは・・


反省点

・深さ優先探索でTLE

・余計な条件の付与で爆死

教訓

・再帰が深くなりそうな場合は幅優先探索で解く

・計算量を落とそうと追加した条件は余計な枝刈りをしていないか確認する

laycrslaycrs2012/01/22 09:30Div2 1000は何通りのパスがあるかという問題ではないですよ.
繰り返しゲームをやるけど,今まで使ったことのない枝を少なくても1個は使わないといけない,という条件で,最大で何回ゲームをやることが出来るか,です.

kmatskmats2012/02/03 03:40Editorialを読んでみたら仰る通りでした.
アルゴリズム以前に読解力不足でした..