Google Code Jam 2011 World Final 行き?

http://code.google.com/codejam/
まだちゃんとした情報が出たわけではないのですが，GCJの最終ラウンドに行けることになりそうです．GCJ(Google Code Jam)はGoogle社の主宰するプログラミングコンテストで，3ラウンド目では最終ラウンドの枠上位25名を競います．で，今回僕は25位でした．なんというかすごくギリギリ．
開催日程は7/29らしいです．がんばってきたいと思います．

いやな誤差

ComputationalGeometry

ぼくは幾何の問題を解くときいつもccw周りは

#include <complex>
using namespace std;
typedef complex<double> P;
const double EPS=1e-8, PI=acos(-1.0);

double dot(P a,P b) { return real(conj(a)*b); }
double cross(P a,P b) { return imag(conj(a)*b); }
int ccw(P a, P b, P c) {
    b -= a; c -= a;
    if (cross(b, c) > +EPS)   return +1;    // counter clockwise
    if (cross(b, c) < -EPS)   return -1;    // clockwise
    if (dot(b, c) < 0)     return +2;       // c--a--b on line
    if (norm(b) < norm(c)) return -2;       // a--b--c on line
    return 0;                               // a--c--b
}

みたいにしていた．cross(b, c)をEPSで評価してるのは誤差を考慮するため．


なんとなくいや〜な感じはしていたのだけど，大体の問題で上手くいってるし別にいいかなぁと思って放置していた．なんとなくいやな感じがするというのは，cross(b,c)は長さに関して2次式で誤差の積み重ねが強いのにそれを右辺が吸収できていない感じがしていたからだ．
具体的には，もし真の値 a=(x1,y1), b=(x2,y2) に適当な誤差が加わって a'=(x1+ε1, y1+δ1), b'=(x2+ε2, y2+δ2) となっていたとすると，これで外績をとったときの誤差は a'×b' - a×b ≒ (ε1*y2+δ2*x1) - (δ1*x2+ε2*y1) のようになって，もとの誤差に長さ(大きい値かもしれない!)が掛かった風になってしまう．これはあまりよくない．


というわけで今日は多分これが原因でWAを喰らってしまったので，修正して次のようにすることにした．absを取っているので若干遅くはなるが，次のものなら誤差にはそこそこ強そう，な気がする．本当に直ったのかよくわからないけどWAがACになったのでとりあえず満足することにしている．小数誤差の類のエラーは本当に直ったのかそれとも駄目なのかが目で確認しずらいのでなかなか扱いにくいもんです．

#include <complex>
using namespace std;
typedef complex<double> P;
const double EPS=1e-8, PI=acos(-1.0);

double dot(P a,P b) { return real(conj(a)*b); }
double cross(P a,P b) { return imag(conj(a)*b); }
int ccw(P a, P b, P c) {
    b -= a; c -= a;
    double len = abs(b)*abs(c)
    if (cross(b, c) > +EPS*len)   return +1;    // counter clockwise
    if (cross(b, c) < -EPS*len)   return -1;    // clockwise
    if (dot(b, c) < 0)     return +2;       // c--a--b on line
    if (norm(b) < norm(c)) return -2;       // a--b--c on line
    return 0;                               // a--c--b
}

Member SRM 501

問題文を開いた瞬間，前のSRMで自分が作ったFox Cielというキャラクターが一人で勝手に何かやっているのが目に映って，まるでドッペルゲンガーを眺めているような気分に．


Hardはアイデア自体は綺麗なものの実際に実装してみるとなかなか阿鼻叫喚になって良いです．

掛け算をした

Math

高速フーリエ変換(FFT)というテクニックを使って掛け算をしました．
問題：http://www.spoj.pl/problems/MUL/
コード：https://gist.github.com/854921


再帰してるせいか結構遅い．Spaghetti SourceにあるFFTが速いという噂なので気が向いたら試してみたいです．

writerやりました

TopCoder

TopCoderのSRM498で初めてwriter(作問者)をやらせていただきました．問題とか結果はこちら→ http://www.topcoder.com/stat?c=round_overview&er=5&rd=14427
今回は参加者が定員オーバーするくらいたくさんいたり，問題がいつもに比べてかな〜り簡単だったりととても異常な回となったのではないかと思われます (見ていた側としても，みんな想定してたものと違う解法使ってたり，予想してたよりも遥かに多い人数に解かれていたり，予想がかなり外れた点もありました)．なんにせよ，各位の感想が気になるところです．


writerを申請する手順はTopCoder部の「SRMに出題」を参考にしてやりました．申請してからAcceptされるまでに2ヶ月半くらいかかったような気がします．人によって待たされる期間が結構違うっぽいですね．(このへんどういう具合でやっているのかよくわからない…．) writerは割と待たされることが多いので気長にやる必要があると思います．