Hatena::Grouptopcoder

SRM diary(Sigmar)

SigmarのTopcoder SRM参加記録など雑記です。
社会人になってから競技プログラミングを始めました。どこまで行けるか分かりませんが合間を見つけてアルゴリズムの勉強をしています。

2010-04-04SRM466 Div1

SRM466 Div1 250 LotteryCheating

| 22:49 | SRM466 Div1 250 LotteryCheating - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM466 Div1 250 LotteryCheating - SRM diary(Sigmar) SRM466 Div1 250 LotteryCheating - SRM diary(Sigmar) のブックマークコメント

約数の個数が奇数の数を0~10000000000までの間で列挙できれば解けるような問題です。
実は「約数の個数が奇数の数」⇔「平方数」(Wikipedia)ということだそうなのですが、全く気づきませんでした。予備知識としては常識の範囲なんでしょうか?
正直いって、250の問題でその場でこの法則に気づくのは難しい気がします。500点くらいのレベルかと・・・

SRM466 Div1 500 LotteryPyaterochka

| 22:49 | SRM466 Div1 500 LotteryPyaterochka - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM466 Div1 500 LotteryPyaterochka - SRM diary(Sigmar) SRM466 Div1 500 LotteryPyaterochka - SRM diary(Sigmar) のブックマークコメント

250の解法が全然思いつかなかったので、こちらを開きました。場合の数を列挙するだけで解けるので、どう考えても250よりこっちのほうが簡単に思えます。。
250と500の内容が入れ替わってるのかと思いました。
source

トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20100404