SRM520

TopCoder

良いするめセットでした。(何を言ってるんだという感じですが)

  • -

250. SRMCodingPhase

問題：SRMの3問それぞれを解くのにかかる時間と、解く時間をluck分縮める権利が与えられるので、得られる最大の点数を求める

  • 点数高い問題から貪欲にluckを使う感じ？
  • 解く問題の組み合わせ全通りについて試しておけば良い気がする。
  • と思ったけど、よく見たらluckが最大で100しかない。
  • なので、各問題で何分縮めるかについて無難に全探索しておいた。
  • しかし、ループで回せる処理を全部書き下したりして残念なコードになった
    • 間違いを埋め込んでないか不安になって提出が遅れてさらに残念だった
    • ループで書くか、書き下すか悩んでた時間も実にムダだったぜ…

500. SRMIntermissionPhase

問題：上位の人から順に解いた問題の組み合わせが与えられるので、考えられるスコアボードが何通りあるか答える。各コーダーの点数はすべてバラバラ。

  • 500がChallengeで1000がSystemTestかなぁと思ってた
  • Intermissionという発想は無かったぜ…
  • 下から見て、増加列の数を調べるDPでも書いておけば良い予感
  • 問題は、解いた問題の組み合わせについて、ある点数を取る方法が何通りあるか
  • 愚直にループ回したら明らかにTLE
  • 1≦a≦Aかつ1≦b≦Bでa+b=Nをみたすa, bの組み合わせの数でも考えてみるか…。
    • 1≦a≦Aかつa+b=Nから、bの取れる範囲はN-A≦b≦N-1
    • つまり、max(1,N-A)≦b≦min(B, N-1)を満たすbの数が答え
    • とりあえず、この場合の数を way(A, B, N) とでも置いておく
  • 同じノリで3個の場合もいけないかなぁ。1≦c≦Cで、a+b+c=Nとかおいて。
    • 同じノリで考えると、N-C≦a+b≦N-1
    • つまり、way(A, B, N-C)+…+way(A, B, N-1)？
    • これも愚直に計算するとTLE乙になってしまうけど…
    • Nが1だけ増えたときを考えてみる
    • way(A, B, N-C+1)+…+way(A, B, N-1)+way(A, B, N)が求めたい数
    • 前の結果を使いまわせるし、余裕で計算できる！
  • というわけで、書いたら通った。

Challenge Phase

  • ぱないコーダーの500を見て、方針が同じ事を確認して安心した
  • -

結果：AC / AC / -- ，+0, 507.13pt, 40位
レーティング：2250 -> 2313


250も500も解くまでグダグダしてしまった感じではアリましたが、
なぜか順位は高めでレーティングも上がったので、勝利したことにしておきます(｀・ω・´)