VK Cup 2012 Round1

A問題

• ソートしてgreedyにやるだけじゃん。
  • 書いた。submit。pretest WA。なんか言ってるし、とりあえず放置。

B問題

• 割引されるのは一番高くてもstoolの商品なんで、一個ずつ入れるのが良い？
  • これもソートしてgreedyにやるだけじゃん。
  • 書いた。submit。pretest AC。

D問題

• C問題より解かれてるんでこっちに。
  • 木の上でDPする系ですか。2つのsub tree同士をマージすれば良いですね。
  • 書いた。よく見たら5万回再起するけど大丈夫かこれ？
  • 一応手元では最大ケースが通ったのでsubmit。pretest AC。

A問題

• よく見たらxとy逆にしてた…。修正してsubmit。pretest AC。

E問題

• C問題より解きやすそうだったのでこっちに。
  • とりえあえず素数全列挙して、全探索をしてみたら意外と何とかなるんじゃないの？
  • 書いてみた。5桁が1つにつき0.2秒くらいかかってる。
  • …。素数を全部試しているのをやめて、上の桁で決まっている部分だけを計算するようにしてみた。
  • 5桁30個で3秒前後。時間も無いしsubmit。pretest AC。

結果

ooxox 365位 2198→2106。
予想通りEはTLEした。Eは通したかったけど、とりあえず通過したので良しとする。