hotpepsiの練習帳

SRM 676

00:29

https://competitiveprogramming.info/topcoder/srm/round/16626/div/1

Div1 Easy (250) WaterTank

問題

• Cリットル入るタンクがある
• N個の連続する区間があり、区間ごとに水量が変わる
• 区間iの長さはt[i]秒で、毎秒x[i]リットルの水がタンクに入る
• タンクがあふれないようにするための出力Rリットル/秒の最小値を求める

方針

• 二分探索
• 各区間で足してみて、あふれない下限を求める
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_676/WaterTank.cpp

Div1 Medium (450) BoardEscape

問題

• r×cの升目がある
• 出口EとトークンTが置かれている
• トークンは初期値kを持っていて、上下左右いずれかに動かすと1減る
• 出口と重なるか、値がゼロになるとトークンは消滅する
• 2人で交互に動かすとき、トークンを動かせなくなったほうが負け
• 両者が最適な戦略を取るとき、勝者を求める

方針

• grundy数 + DFS
• Failed System Test
• Tの残りの数を状態に持つ必要がある
• memo[行][列][Tの残数]でメモ化
• ただしTが4を超えるときは4つごとに同じ状態なので、4 + (T MOD 4)にする
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_676/BoardEscape.cpp

結果

ox- 173.83pt 258th/407 rating 1268 -> 1299 (+31)

yukicoderのおかげで久しぶりにmedium提出できたが、状態の持ち方が悪くて死んだ。

http://togetter.com/li/914302