SRM483

TopCoder

最近忙しくて間が開いてしまったけど。

250: BestApproximationDiv1

  • 愛用キーボードの Majestouch Tenkeyless (茶軸) が動かない・・・。
    • あれこれいじくり回してみる。ケーブルが断線してるっぽいなぁ。
    • 仕方ない。弾幕シューティング用キーボード (日本語配列・安物) で頑張ろう・・・。
    • 13分遅れぐらいで開始。
  • 長々と問題文書かれてるけど、そんなに大変じゃない全探索だよね。
    • sprintf で文字列にして、共通prefixを取っておしまい。
      • って、あれ。sprintf("%.6lf") って勝手に四捨五入とかしてくれなかったっけ？
        • ・・・ええい、ちょっと長めに出力して頭8文字切り出そう。
  • かたかたかた。いつもよりキーが重い・・・。
  • サンプル出てきた。submit.
  • Division Summaryを見てみる。900が結構提出されてるなぁ。
    • まぁいいや、500行こう。

500: Bribes

  • Greedy...じゃないし、やっぱりDPかなぁ。
  • 賄賂抵抗力は最大500ぐらいなので、最大10人ぐらいまでしか届かない。
    • 10人ずつのグループに分けて全探索して上手いことマージするとか？
      • どうマージしていいのか分からんなぁ・・・。
  • 左側に2人以上賄賂が必要な人がいたとしても、適当に2i掛けてmaxとれば、1人だけ賄賂が必要だとみなして構わないよね。
    • dp[n][l] := 左から n人目まで贈賄するかどうか決めて、左側に l だけ賄賂パワーを送らなければいけないときの最小コスト、とかどうだろうか。
      • その時点で右側にもいくらか賄賂パワーが送られていることになるので困るなぁ。
    • dp[n][l][r] := 左から n人目まで贈賄するかどうか決めて、左側に l だけ賄賂パワーを送らなければいけなくて、右に既に r だけ賄賂パワーが送られてるときの最小コスト、なのかな？
    • 時間もメモリも O(n * 500 * 500) ぐらいになりそうな気がする。けどいまいち自信がもてない。
  • そういえば、Division Summaryはどうなった？
    • 900がとんでもない勢いで解かれてる！500捨てよう。

900: Sheep

  • えーと、二分探索するだけ？急いで実装せねば。
  • setを使って頑張る。
    • いやいや、同じ重さのがあるからmultisetじゃないと。
      • そういえば、multisetを使うのはこれが初めてだ。
  • ...バグった。同じ重さのがあるとうまく動かない？
    • erase(iter) は *iter に等しい要素を全て削除するみたいだ。
      • あれ、そんな仕様だったっけ？
  • とか言ってるうちにタイムアップ。

Challenge Phase

  • 今日の撃墜ポイントは・・・
    • 250: 分母 <= maxDen を < maxDen と勘違いしてる人を探してみよう。
  • 開く閉じる開く閉じる開く閉じるいないなぁ開く閉じるさすがにいないか開くいた！
  • +50.00
  • あれ？250でsprintfを使ってる人がぜんぜんいない？
    • 人と違うことをしてると不安になります。

System Test

  • 900が阿鼻叫喚なのを見つめつつ250が無事に通る。
    • そうか単調でないのか。書く前に当然はっきりさせなければならないはずだけど、みんな出してたし疑いもしなかったなぁ。
  • oxx +50 258.37
  • 部屋の500と900がまさかの全滅でRoom1位。平和な部屋でよかった。