SRM458 div1 (practice)

Topcoder Online Judge

250

  • ボールが弾性衝突する問題
    • しかも12個しかボール無いんで向きを全通り調べてsubmit。AC。
    • この問題ボールが10万個とかでも解けそうな気がするんですが。

450

  • コインの価値を決めて支払うコインの枚数を最小化する問題。
    • 全探索で行けるんじゃね。なんか400万通りしか無いらしい。
    • てきとうに実装。TLE。
    • 枝刈りを入れる。ランダムケースでTLE。
    • コインを全部作ってから調べるんじゃなくて、作りながら支払えば枝刈りがもっと効くんじゃね。
    • 書いた。ランダムケースで間に合うのでsubmit。AC。

900

  • 解説見たら答えが全部載ってた。

結果

oo- 420.26pts 109位くらい。
450は普通にDPで解くもんらしい。もうちょい考えてからコード書けばよかった。