SRM469

TopCoder

今まではコーディング環境が貧弱で歯痒い思いをしてたけど、今日は新しいマシン + Debian + Emacs + Flymake + TopCoderプラグイン各種 + プリンタと最強の布陣で参戦。
裏を返せば、これで残念な結果だったら私の頭が本格的に残念ということになるわけですが。

250: TheMoviesLevelOneDivOne

  • ただの算数っぽい。
    • ある席が予約されてるなら、右側の人がそこに座れない・左側の人がそこに座れないで2パターン消える。
    • uniqueとか使って重複を除いて、最後に全体から引く。
  • 算数は苦手なのでなかなか答えが合わない。
    • しばらく格闘して…できたっと。
  • Sample通れば大丈夫な気もするけど、とりあえず最大ケース。
  • 答えが10億ぐらい…ってちょっと小さくね？
    • n*(m-1) がオーバーフローしてた！あぶないあぶない。
  • 怖くなって入念にテストしてからsubmit.
  • 189.99

500: TheMoviesLevelTwoDivOne

  • TopCoderではICPCのように落ち着いて考えられないのは、きっと問題文が紙でないからに違いない、と信じて印刷してみた。うん読みやすい。
  • んで、これはただのビットDPなのではないだろうか。
    • 今日はついに500が解けそうな気がする。
  • どれを見ても47だけ増加するってことは、同じ映画の部分集合を見たとき、見た順番がどうであれ、(途中で寝る場合を無視すれば)scary pointは同じであるはずだよね。
    • vector<int> dp[1<<20] を使って部分集合に対する最適解を保存するようなDPでどうだろう。
  • ……書けた。けど合わない。
    • どこにもバグらしきものは見当たらない。ぐぬぬ……
  • ……あれ？
  • 映画が1本しかないCase3でなんで答えが {0, 1} になるの？
  • DPテーブル初期化してねぇ！
    • TopCoderは1ケースずつ実行されるからと思ってサボってたけど、テストはローカルでやってるんだから初期化しないとダメだよ！
  • 直したけどまだ合わない。
  • って、あれ？
    • Case3って1本も見られないはずなのに、なんで答えが { } でなくて { 0 } なの？
    • ...
    • なるほど！その全部を見られるかどうかに関わらず、絶対に 0 .. n-1 の permutation を返さなければならないのか！
      • 盲点だった。
  • 最後に見てない映画を適当に追加すればいいや。sample通った。
  • 最大ケース試してみよう。TLE…
  • vectorを配列に書き換えてみるか。
    • 落ちた……
  • vectorのまま入力サイズを小さくしてみよう。
    • N = 18 で1秒強。 半分弱にまで縮めればいいのか。
    • ……どうやって？
  • なかなか妙案が思い浮かばず無念のタイムアップ。

Challenge Phase

  • まずは500でMLE / TLEしそうな人をチェック。
    • いなかった。
  • じゃあ250で n*(m-1) をオーバーフローさせてそうな人はいないだろうか。
    • 一人いた。撃墜。
  • それだけ。

Result

  • oxx +50.00 239.99 175th
  • 1392 -> 1516
  • 黄色くなったよ！ちょっと信じられない！