hotpepsiの練習帳

SRM 530 Div2

02:43

不参加

Easy (250) GogoXBallsAndBinsEasy

問題

• N本のビンがあり、それぞれT[x]個のボールが入っている。
• Tの個数は昇順にソートされている。
• T[x]の順番をシャッフルしたものをS[x]として、ビンからビンへコスト1でボールを1個移動できる。
• 状態Sから状態Tへの移動量が最大となるSを求める。

方針

• 先頭と末尾の両端から差を取って加算
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_530/GogoXBallsAndBinsEasy.cpp

Medium (500) GogoXCake

問題

• ケーキとケーキカッターがある。
• ケーキカッターには刃が有効な部分と無効な部分があり、刃をあてるときには有効な部分にケーキがなければならない。
• 食い散らかしたケーキの結果から、ケーキカッターでその結果が生成可能か求める。

方針

• 総当りで位置をなめていって、ケーキカッターの形にフィットしたら、ケーキに戻す
• 最終的に全てがケーキに戻っていればYES
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_530/GogoXCake.cpp

Hard (1000) GogoXReimuHakurai

問題

• 小説が0から(N-1)までの全Nステージある
• あるステージAから次のステージBへのルートがあるかどうかのフラグが与えられる
• 前のステージへは戻れない
• それまでに通っていないルートを1通りとして何通りのルートがあるか求める

方針

• DPらしい
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_530/GogoXReimuHakurai.cpp

感想

hardを誰もACしていないという珍しい回。サンプルだけ通るコードだと死。