jonathanasdfの日記 RSSフィード

 | 

2012-02-19TopCoder 533 Div 1

Greedyはいい!!俺にとって:)

Div. Place 268/915

Points: 200

Solved: ---

Challenge: 4 succeeded

Rating: 1379->1473 (+94)

はじめて何も解けなかった、でもRatingが上がった… もう一回でまたyellowにもどろうとがんばろう!

250

これは簡単なDPでした…でもそれを見えた時はもう16分だけが残ってた。要は、

dp[start][end] = max(dp[start][mid]+dp[mid][end])+weight[start]*weight[end])。

最初、greedyでsample testcaseまで合格し(そいつらとっても悪意だ!!)、けど俺がgreedyが本当に正解とは証明できなかった、でbitmask dpを作ったとgreedyを壊すinputが見つかった。

その後は思うとおり。

500

ぜんぜんわからなかった。あとでEuler Tourと聞いたけど俺にできるわけないだろう。

1000

見てもしていなかった。

 |