Hatena::Grouptopcoder

TopCoder煮ブログ

本家ブログはこっち → http://d.hatena.ne.jp/nitoyon/

2010-04-04

SRM 466 DIV1

| 10:01 | SRM 466 DIV1 - TopCoder煮ブログ を含むブックマーク はてなブックマーク - SRM 466 DIV1 - TopCoder煮ブログ

悲惨な回。再び1回で blue に降格。

15131429 0pt 577位/798人

LotteryCheating

与えられた N 桁の数を、約数が奇数個になるか 0 にするためには、何個の数を書き換える必要があるかを調べる。

エラトステネスの篩して、素因数分解して、約数の個数を求める関数を作った。時間かかったが submit した。

Intermission に最大の 9999999999 を与えたら返事来なかった。諦めた。System Test の結果見たら、9999999999 で Fail。でも、それ以外の値では問題なさそうだったので、最大値ぐらいは事前に試すべきだった。

上位の人は、小さい数から2乗していって与えられた数と異なる数字の数を列挙していた。「約数が奇数個 ⇔ 平方数」というのを利用している。なるほど...

約数が奇数個 ⇔ 平方数の簡単な証明

たとえば、ある数が N = Πpiai のように因数分解できるとき、約数の数は Π(ai+1) となる。

  • 約数の数が奇数になる→平方数:
    • 約数が奇数ということは、ai+1 が全ての i について偶数である。これはつまり、N が平方数ということになる。
  • 平方数→約数の数が奇数になる:
    • 平方数の場合は全ての an は偶数になってる。つまり、約数の数は奇数となる。

LotteryPyaterochka

5*N のグリッドから5つを選んだときに、一列に3つの数が含まれる確率を求める問題。

N>2 なら、求める条件を満たす行の組み合わせは {5}, {4,1}, {3,2}, {3,1,1} のいずれか。これを数え上げて全体の数で割ればいいはず。ただ、これに気づいたときには残り4分。

勢いで書いてビルドしてテストしたら通ったので submit。と思ったら、Easy の問題を実行していた…。よくよく調べてみたらサンプルすら通らず。なのに誰も Challenge せず。意外に気づかれなかったのか!?

DrawingBlackCrosses

見てない。

感想

Midium の問題から解けばよかったかも(?)。