SRM 365

久しぶりにSRMにも出てみた。
なんだかSRMはレートが下がった思い出しかないので、
なかなか出るのが億劫になっていたのですけども。

http://www.topcoder.com/stat?c=round_overview&er=5&rd=10780

・300点
約数を列挙するだけの問題だったのだけど…。
約数のうち4で割ると1余るもの - 約数のうち4で割ると3余るもの、を求める問題なので、
実際に約数をすべて生成すればそれでよいのだけど、
何を血迷ったかよくわからない考察を始めて、
その考察は合ってたのだけどちょっとした勘違いから実装を間違えて自滅。
アルゴリズムは、前者をd1、後者をd3とすると、
d1 =（4で割ると1余る素因数任意個からなる約数の数）*（4で割ると3余る素因数偶数個からなる約数の数）
d3 =（4で割ると1余る素因数任意個からなる約数の数）*（4で割ると3余る素因数奇数個からなる約数の数）
なのと、n=r^2 から、
（4で割ると3余る素因数偶数個からなる約数の数）-（4で割ると3余る素因数奇数個からなる約数の数）= 1
であるので結局求めるd1-d3は、（4で割ると1余る素因数任意個からなる約数の数）と等しくなる。
そういうわけで、素因数分解しながら掛け算すれば答えが求まるはずだったのであるが…。
なんで間違うのかなあ…ぶくぶく……

・500点
細かい考察が終わる前に書いて提出したので、
いまだになんで通ったのか分からん…。
数三つを選んで、それらを含む"もっとも大きな幅の"等差数列としてaptitudeを計算。
反例があると思ったんだがなあ。より小さな幅の等差数列は、
それによってスコアが上がるならそれが含まれるもので尽くされるのかしらん…。

・1000点
時間があんまり無かったから
これまた反例があるよなあと思いながら
普通に前からトポロジカルソートを書いたら普通に落とされましたとさ。
そうか、うしろからか。

とりあえず0問という最悪の事態は避けられて一安心……
なんかしてる場合じゃないな。