■ [本番][TCO]TCO09 Algo Qual1 
Coding Phase中に何か問題が発生したそうでCoding Phaseが10分伸びた。
http://www.topcoder.com/stat?c=coder_room_stats&cr=22744421&rd=13742&rm=300349
| Level | タイトル | 試合中 | あとで | 感想 |
|---|---|---|---|---|
| 1000 | PrimePairs | × 57min | ○ | また素数か、と思わせつつGraph。二部グラフのマッチングなんだけど、そのへんはまだ勉強してない。 というわけでオレオレアルゴリズムでゴー。再帰+メモ化でやってみたらサンプル通ったので提出。 しかしいろいろテストしてたらすごく遅いケースがあることを発見したので変な枝刈りを追加して再提出 →やっぱり駄目だった。WA |
| 500 | SquareFreeNumbers | ○ 14min | - | brute force。入力が巨大だと見せかけておいて実際は最大範囲100万なので全部調べられる。 エラトステネスのふるいみたく、素数の2乗で割り切れるものをふるっていって生存数を数える |
| 250 | SortingWithPermutation | ○ 3min | - | greedy。未使用の中で最小のものを探して前から順に詰めていく。 サイズ的にO(N^2)でOKなので単純に書けばよい |
Challenge: 1000点問題で偶然発見した遅いテストケースを使って2人撃墜成功（1人失敗）
234位/1301人 予選通過
レート 1755 → 1783
