2010-07-12

■ [TCO]TCO10 Algo Round3 01:19

2010-07-10 25:00-（JST）

http://www.topcoder.com/stat?c=coder_room_stats&cr=22744421&rd=14281&rm=305207

350人→150人

Level	タイトル	試合中	あとで	ひとこと
250	SieveOfEratosthenes	AC 67min	-	単純そうで考えにくい問題
500	TheChroniclesOfAmber	AC 16min	-	グラフっぽくてそうじゃない、最近こういうの多い
1000	Passwords	Opened	-	Hardでこんなに問題文が短いのは初めて見た

• Coding
  • 250
    • なんか珍しげな問題だな
    • √N以下で最大の素数かそれよりちょっと小さい素数の倍数になってるやつが答えになるはず
    • 解答が√Nから大きく離れるケースはたぶんなさそうだから大きい順に素数を調べてもTLEはせんでしょ
    • ちょっと実装が迷走気味になったが書けた。提出
  • 500
    • 問題文のストーリーが妙に邪魔くさい…
    • サンプルで、ちょっと進んでからテレポートとかややこしいことしているが、時間0のときに全員テレポートすれば十分では？
      • 時間Tだけ進んだところでp1がp2の位置にテレポートしたのが最適だとして、
      • 全員進む速さは同じだから、p1は時間0でp2の位置にテレポートしても、時間Tのあいだ自力でp2が進んだ方向へ進んで同じ結果になる
    • あとはN人をどう配置するかだけど
    • 人が誰もいなくなった位置へはテレポートできないので、最初にテレポートした人の位置にはもう誰も来れない
    • 逆に、最初にテレポートした人が空き位置ができないよう上手く立ち回れば、残りのN-1カ所の中では人を自由に配置できる
    • なので、[N人に対して]×[i番目以外で一番目的地に近いスタート位置]を、N通りのiについて調べると良い
    • あとは1人も移動しないのが最適という場合もある
    • スタートとゴールを逆にしていてサンプルが通らないなどあったが提出（ここで拾われて良かった…）
  • 1000
    • 余事象を包除原理で計算できないか…？
    • しかしそのためには、入力が20万くらいの2項係数（のmod 1000000009）をO(1)で計算する必要があって
    • できない…
    • 深追いせず、あまり自信がない250をテストする
  • 250
    • コーナーケースがわからないのでとりあえず小さい数から順に入れてみる
    • 入力8 → 答え6　…え!?　それ違う…　
    • コードを順に追っていくと考慮漏れに気づいた。素数×素数の形しか調べていなかった
    • 見ている素数をpとすると、調べないといけないのは、「p×（p未満の素数で割りきれない数）」だ
    • これ問題読んでる途中にちょっと気になったんだけどコーディング中には忘れ去っちゃってたなー
    • 残り時間わずかだったが、幸運にもすぐ正しい形に直せるコードになっていたので修正して提出
      • この形に当てはまるのは8だけらしい。へぇー
• Challenge
  • 250は確実に自分と同じミスをしている人がいる！
  • じっくり読んで1人撃墜成功
    • 見切り発車で投げたらもっと落とせる人たくさんいたかもしれないが
    • ときどき-25のダメージのでかさを味あわされるので最近チャレンジは控えめにしている
    • 確実に落とせそうなときだけ投げる、という方針にしておくのが平均では一番いい結果になるんじゃないでしょうか
• System Test
  • 250も500も通った

結果

• スコア：75.00 + 382.48 + 0.00 + (50*1-25*0) = 507.48
• 順位：23位/325人
• レート：2038→2198

うひょー上がりすぎ。TCOご祝儀相場だ

完全に実力以上のレートになってしまっているがここまできたら次で一気に赤いきたい