Hatena::Grouptopcoder

hotpepsiの練習帳

2017-02-05

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

トラックバック - http://topcoder.g.hatena.ne.jp/firewood/20170205