hotpepsiの練習帳

SRM 706

12:56

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

Div1 Easy (250) MovingCandies

問題

• 升目にいくつかキャンディーが置いてある
• 左上から、キャンディーのあるところだけをたどって右下まで移動する
• キャンディーを何個移動する必要があるかを求める

方針

• 考察1
  • 変更量をコストとしてダイクストラ
  • サンプル1でコストが2と出てWA
  • キャンディーが足りないので、進む先にあるキャンディーも移動しているが、それを考慮していないため
• 考察2
  • memo[もともとキャンディーだった場所を踏んだ数][y][x]=変更量でDFS
  • もともとキャンディーだった場所＋変更量が、全体のキャンディーの数以下のところに行ける
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/srm_7xx/srm_706/MovingCandies.cpp

結果

o-- 91.69pt 204th/384 rating 1434 -> 1454 (+20)

方針が間違っていて一時間以上かかった。再提出しないで通ったのは良かった。

https://togetter.com/li/1072968