TCO10 Online Round 3

TopCoder

数時間後に演奏会を控えていますが、Round3に出ればTシャツをくれるというので参加してきました。

  • -

250. SieveOfEratosthenes

問題：エラトステネスのふるいで2からmaxNumまでの数を処理したときに、最後にふるわれる数は？

  • maxNumは4以上20億以下。素直にふるいを実行すると死亡。
  • とりあえず、sqrt(maxNum)以下の素数は使う気がしたので、適当に5万以下の素数を求めた。
  • で…？
  • 素数pでふるいをかけるとき，p未満の素数で割り切れる数はふるい済み
    • ふるわれてない数はp以上の整数の積で書ける
    • 50000以下の素数は5000個くらいだし，答えって2つの素数の積だったりしないかなぁ…
    • p以上の3つ以上の素数の積で表せる数がmaxNum以下だったとして
    • そんな数があればpの次の素数の2乗がmaxNum以下になりそう
    • 小さい数を何個か考えたらmaxNum=8の時だけ違うっぽいので、これだけ例外処理
  • というわけで、やった処理はこんな感じに
    • sqrt(maxNum)以下の素数pについて
      • p以上の素数qそれぞれに対してpqがmaxNum以下なら答えを更新
      • pqがmaxNumを超えたらpを次の素数にする
  • サンプルは通ったので、ホントかよ…と思いつつ提出
  • Challengeで3回攻撃されたので、嘘だったか…と思ったけど何故か通った

500. TheChroniclesOfAmber

問題：n人が位置(sX[i], sY[i])から(gX[i], gY[i])に速度1で移動する．任意の時間には誰か1人が別の人の場所にワープできるとすると，全員が目的地に到達するために必要な最小の時間は？

  • 移動を始めてからワープする意味は無さそうなので，最初にワープは済ませてしまう
  • 貪欲は…ダメだろうなぁ…。n人の位置総入れ替えは出来ないし…。
  • 最初にi番目の人がワープしたとすると，i番目の位置は使えなくなる
    • けど，この人が頑張れば残りの位置間では任意のワープができるんじゃね…？
    • 確証は無いけど、分からなすぎるのでそういう事にする
  • 最初に，ワープを使わない場合にかかる時間を調べておく
  • ワープを使う場合の最小はどうやって求めれば良いかなぁ…
    • 使わない場所を決めれば、時間d以内に全員が目的地に着けるかはO(n^2)で判定可能
    • 使わない場所はn通り選べるから、O(n^3)で時間d以内に目的地に着けるか判定可能
  • そうだ、二分探索をしよう。
    • nが最大50でO(n^3)の判定なら、200回くらい回しても時間は大丈夫だろう。
  • というわけで書いたらサンプル通った。ホントかよ…と思いつつ提出。
  • Challengeで2回攻撃されたので、嘘だったか…と思ったけど何故か通った
  • -

結果：AC / AC / -- ，401.97pt, 40位
レーティング：1938 -> 2097

まさかRound3を突破してしまうとは…。しかも根拠が怪しい解法で。
レーティングが高騰しすぎて怖いですが、見合う実力になれるよう頑張りたいです。