Hatena::Grouptopcoder

Gus@topcoder

topcoderのid:gusmachineの記録です。普段の日記は揺動散逸日記をどうぞ。
 | 

2010-05-05

! SRM 469

o o opened: 470.47 pts. 66 th

  • 250 208.52 pts 13分
  • 500 261.95 pts 34分
  • 1000 opened

最近にしてはよかったです。

特に500が、あまり早くなかったものの、落としている人が多い中確実に取れたので結果オーライ。

500

500から開いてみました。250を後攻することで、その必要時間を見極めてみるつもり。

  • え、これどうするの。
  • ある組み合わせの映画が見れたら、残り時間はその見る順序を問わず定まる。なので、その組み合わせの映画が見れるとしたら、見る順序は一つだけ保存しておけばいい。
  • でもどうすれば。よくわからないから250に逃げようかな。
  • なるほど。高々20枚だからO(220) の空間でできます。よし解ける。
  • 残り時間を表す変数にlifeと付ける。
  • できた。30分かかってない。最近にしては上出来かも。
  • あれ、operator<<(ostream&, vector)でエラーがおきている。
    • cout.hとテンプレート(vectorを出力)とによる二重定義。とりあえずcout.hを外す。
  • テストケースはpass.
  • 最大ケースで3 secかかる。これはまずい。
  • 計算量はO(N 2N)でぎりぎりだった。これはまずい。
  • とりあえずpprof。std::_Rb_treeが原因。メモの部分をmapでやっていたので。
  • 時間を半分にできればいいのだからmapをhash_mapにできればよいはず。
    • 何か間違えたかな。/usr/include/c++/4.4/backward/backward_warning.h:28:2: warning: #warning This file includes at least one deprecated or antiquated header which may be removed without further notice at a future date. Please use a non-deprecated interface with equivalent functionality instead. For a listing of replacement headers and interfaces, consult the file backward_warning.h. To disable this warning use -Wno-deprecated.
  • よく考えたらvectorで良かった。これで最大ケースが300 msでpass. submit.

BFSで見られる映画の組み合わせを探索します。上記したとおり、ある組み合わせの映画を見る順番は一つだけ保存していればよいです。自然な順番で探索するとはじめに見付かった手順が辞書順最小になるため、そのときの手順だけ保存しておきます。N個の映画に対してノードが2N存在し、一つのノードにつきO(N)の次の手を探すのでO(N 2N)の時間がかかります。ぎりぎりの時間で解けます。

変数lifeはsanの方が良かったかもしれません。

実はO(N4)でできるとか。 なん...だと...

250 pts

  • 映画館の座席のうち、並んで座れるところの個数を返す。ただし映画館が異常に広い。
  • 座席をソートして前から順番になめて、間の個数を返してみる。
  • N * M は掛ける前にcast。
  • 面倒くさいな。
  • できた。submit.

1000 pts

  • open.時間はちょっとあるしなんとかしてみるか。少なくとも考えてみる。
  • O(247)とか無理ですね。どうすればいいんだ。
  • 半分に分けるとできるのかしら。でもどうやって。
  • 以前の半分に分ける方法はなんだっけ。PARTITIONか。全然違うな。
  • 無理。

challenge

500のTLEだけ準備したものの、TLEしそうなものが見つかりませんでした。ただ他の人が次々と撃墜されています。何がおきているのか。

250がかなり遅かったので他の人の解法を確認。全体から座れない席を引く方が早いですね。

system test

同じ部屋で四件も落ちていました。これはもったいない。

反省

  • 250はもうすこし俯瞰すれば早くなるかも。慣れか。
  • テンプレートを直す。
  • hash_mapを使う。
  • やはり250から解く方が迷いがなくて楽かも。

challenge resultsの確認。

どうやってchallenge phaseを得点源にするかについて、他の人の撃墜例を見て勉強します。

まずは自分の部屋から。

TLEを投げている人は2勝3負+25でなぜか微妙。ちょっとはコードを読んだ方がいいのでしょうか。+50と-25とのバランスを考えると相手を見ないでchallengeぶっぱなしてもいいと思っていましたが。例えば今回の場合、tree/mapを使っている人は撃墜対象でしたね。他は読まないとわからない。

250は実装のときに気づいてたけどchallengeのときに忘れていたものの一つです。

ついでにsystem test failedのソースも見てみました。これらは本当にバグっていました。コードは読みにくいしちょっと見つからないし見つける方向ではないと思います。残り6分とかだったら時間かけて見てもいいのかもしれませんが。

さらに他の先生の撃墜も見てみます。

[[iwi]]先生の部屋。この入力はどうやって作ったのでしょう。撃墜された人はTLEじゃなくてWAで落ちてるし。何か他のバグかしら。あるいは単に適度なランダム例で、それがTLEじゃなくてそれ以前のケースで落ちてしまったとかかもしれません。うーん。

さらに見ていった結果。

  • 250は幅1の例で撃墜している例も。
  • 500の残りライフ0生存で落ちている人とかは見あたらない。見つけにくいし。

難しい。結論はありません。

 |