hotpepsiの練習帳

SRM 576

20:12

Div1 Easy (256) ArcadeManao

問題

• 古いアーケードゲーム
• 水平のプレートがある
• プレート上の水平移動か、梯子でプレート間の垂直移動ができる
• プレート上のどこかにコインがある
• コインを取るのに最小の長さの梯子を求める

方針

• 梯子の長さを0～Xまでのそれぞれで固定して、成立するものが答え
• 変則配点なのでひっかけがありそう
• 到達可能な点同士をunion findでくっつければできる
• 提出
• Passed System Test
• (終了後)
• 普通にDFSで探索すればよかった
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_576/ArcadeManao.cpp

結果

o-- 227th/545 179.18pt rating 1388 -> 1450 (+62)

謎な解き方の割には点数がよかった。割とシンプルに書けた。