MM102 & ふみこん

感想

勉強になりました。
少しだけ復習したので一時メモ。続きをやったら更新したいね。

ふみこん

思考

  • 超自明な方針として区間1だけの操作に限ってみる。
    すると上げるところと下げるところを貪欲に組み合わせていけば最適(?)解が求まる。
  • そこから区間を広げてみる。このとき区間内の上げ下げしたい量は一定ではないため増減させる量の決め方は自明ではないが、区間のいずれも目標値を超えないようにするだけでそれなりに上がるらしい。
  • 最上位に行くにはもう少し工夫が必要。

todo

  • コード読む

Future Meets You Contest(Open) - Future Meets You Contest(Open) | AtCoder

MM102

思考

  • 貪欲も難しい
  • トラックにいくつ乗せても運送料変わらないので纏められるなら纏めたほうが良い(もちろんこれはトラックのコストなどにより変わってくるので、本来はコンテスト時に調査するべき内容)
  • 配達先はフィールド全体に点在しているので、トラックに全荷物纏めたあとにフィールドをぐるっと回りつつ配達する
  • これでそこそこのスコア

todo

  • 上位3人wleite氏の解を読む

MM 102 - Togetter

https://community.topcoder.com/longcontest/?module=ViewProblemStatement&compid=68860&rd=17264