world final warmup 2

なんだかんだで後二週間を切っている。
進まぬ準備。
Haskellerだけに、作業を遅延評価してしまっているようだ。


そんなわけで、この前の acm.uva.es の world final warmup 2 に
参加した。またもや世界大会レベルの難問ぞろい
(一問むちゃくちゃ簡単なのがあるけどな…)
http://acm.uva.es/cgi-bin/OnlineJudge?Volume:108
問題はここの10830〜10839の十問。
書けば通るだろうと思われたチェスの必勝手探索問題に
早い段階で手を付けてしまって大きく時間をロスしたので
開始から5時間には3問しか解けなかった。
実装系問題には簡単には手を付けるなということか。
しかし、以降24時間までの延長戦で怒涛の追い上げを見せて
結局7問正解の12/250位。
ここのコンテストでこんな順位取れたの初めてだよ…。


ところで、解いているときに発見的に分かったことなのだが、
\Large\sum_{i=1}^{n} n mod i
これを効率よく(というかO(n^{\frac{1}{2}})で)求めるアルゴリズムがあるんだな。
解いている人が異常に多かったのだが、有名なことだったのだろうか。
しかし、整数は奥が深い…。