SRM486 Div1

Topcoder Online Judge

nodchipさんと同じ部屋。

300

  • 問題を読む。
    • +は2倍、*は二乗、-は0に/は0以外だと1になると。そもそもtが1以上だから-を使う必要は無くて、/を使う場合は最初に使うのが最適。
    • +,*の場合は数値は少なくとも2倍ずつは増えていくんで幅優先探索で全部調べればいいじゃないの？
    • しかし、長さ最小で、辞書順って所が危なそうだ。というか考えるのもめんどいのでもうダイクストラでやってしまえ。
  • 書いた。
    • 最小ケース、最大ケースも大丈夫そう。コードを見ても大丈夫そうなのでサブミット。
    • なんでこれ300なの？まあいい次に行こう。

450

  • クイックソートのswap回数の期待値を求める問題。
    • swapされた時に並び順は保存されるのか。
    • それならばどんな経路をたどったとしてもindexの[left,right)の範囲のソートをしたい時は常に同じ列をソートすることになるんじゃないの？
    • じゃあメモ化再帰でいいか。
  • 書いた。
    • 全部0が返ってくる。なんでだ。
    • よく見るとswapする時にretを増加させてない。修正したら一致した。
    • O(n^4)になったけど最大ケースでも一瞬で返ってくるのでサブミット。450だからまあこんなもんか。

1000

  • チャレンジのために問題だけでも見ておこう。
    • 問題が良く分からない。凸包を2つ作れって問題のはずなのになんで点が1個でも許されるの？
    • サンプルと問題文をよく見ると、凸包は別に縮退していても構わないらしいし、ロビンの方には領域を与える必要はないらしい。
    • しかしどうやってやるんだ。点を2つの集合に分割すると共通部分ができる場合があるし。
    • …！去年のICPCアジア地区予選の問題っぽく直線で分割すればいいんじゃないの。
    • 直線の選び方は点を2つ選んできて少し傾ける感じで。
    • 残り10分だとちょっと実装できそうにない。
    • 残り時間は他の問題の見直しとテストケースを考えよう。

Challenge Phase

  • 1000を提出してる人で点が1個の場合に0を返してるかどうかをチェック。
    • nodchipさんは対策してた。もう一人はINFを返していたので撃墜。+50。
  • 300で答えがない場合の出力のコピペミスをチェック。
    • さすがにいないっぽい。
  • 他は全然コーナーケースが思い浮かばなくて終了した。

結果

oox 572.56pts 88位。
思ったより300が落ちてる。あと、今回の1000はちょっとひどい気がする。
コードの見直しに時間をかけ過ぎな気がするけど、まあまあの順位。あと、これからは常に100位以内に入っておきたいところだ。