- 2009-02-25 (Wed) 13:26
- プログラミング
３ヶ月振りにTopCoderに参戦．
250点：安定ソートしろ．以上．
500点：平方数で割り切れる数をある区間内で数え上げろと．区間幅が1000000しかなく，区間の開始点が1000000000000なので，エラトステネスの篩よろしく区間分の配列に平方数の倍数でチェック入れるだけ．
1000点：最大50個の数字が与えられる．与えられた数を組にして，全ての組で和が素数になるように組を作れと．答えるのは，このルールを満たすように組を作ったときに，最初の数と組になりうる数全部．最初の数は固定でいいとして，足したら素数になる相手を全部試しつつその残りで完全マッチングできるかチェックする．和を素数にしなきゃならんので，グラフは奇数と偶数の二部グラフになる．おわり．マッチングの探索をナイーブに書きすぎてシステムテストで落ちた…
そして入試なんか消えてしまえ．
- Newer: AWK - はじめ