SRM512

TopCoder

社会人になって初めて平日深夜SRMへと突撃してみた、記念すべき512回目のSRM。

  • -

256. MysteriousRestaurant

問題：曜日ごとに特定のメニューを注文しなきゃいけないレストランで、最大で何日めまで食事できるか求める問題

  • i日目まで食事してみると決め打ちする
  • 各曜日で期間内の金額が一番安いメニューを貪欲に選ぶ
  • その合計が所持金以下ならi日目まで食事はできる
  • というのを、n日食べる→n-1日食べる→… と調べていく感じ
  • 書いたらサンプル通ったので提出、通った

512. SubFibonacci

問題：数字の集合Sから、昇順に数字を取り出してフィボナッチ列の部分列を2つつなげた形にするとき、取り出せる数字の最大数を求める

  • まぁ、きっと2つくらい数字決めればフィボナッチ列特定できるよね
    • f(0) = 0, f(1) = 1, f(n) = f(n-1)+f(n-2) として
    • g(0) = a, g(1) = b なら m≧1のときg(m) = f(m-1)*a+f(m)*b
    • 2つのうち、小さい方をg(0)として良い
    • 大きいほうの数字Mについて、M = f(m-1)*a+f(m)*b となるbを各m≧1で調べる
    • bが整数ならフィボナッチ列として有効
    • 他のS内の数字が、このフィボナッチ列内に含まれるか調べていく
    • g(m)は40項くらいで1億を越えるので、m≦40くらいまで調べれば十分
  • Sの要素をソートしておいて
    • 0〜i番目の要素で作れる最大数 + i+1番目〜n-1番目の要素で作れる最大数
      • 各範囲で2つ数字を取り出して、決めたフィボナッチ内に含まれる数を求める
    • これ各iについて求めていき、その最大値をとれば答え
  • いけそうな気がする。書いたらサンプル通った。
  • 提出する前にS = {1, 2, ..., 50} を試してみる
  • 時間は余裕だけど、答えが11ってホントか…？
    • [47, (1), 48, 49, ]みたいな取り方が可能なことに20分くらいかけて気付いた
  • 大丈夫そうな気がしたので提出、通った

Challenge Phase

  • 512で明らかに嘘っぽい人がいたので、美味しく頂いた
  • {9999, 10000, 10001, 10002, 10003, 10004}で4と返す人がいました^p^
  • -

結果：AC / AC / -- ，+50, 522.63pt, 31位
レーティング：2234 -> 2314


懐かしき2桁順位により、レーティングがだいぶ上がりました。
512で書きあげてから20分くらい悩んでたのが残念な気もしますが、
まぁ落とすよりは良かったという事で…。