Hatena::Grouptopcoder

skyaozoraの日記

2018-07-04

AOJ2563 The J-th Number

22:28

問題概要

英語だけど短いし問題文を読んで

続きを読む

2018-07-03

AOJ2290 Attack the Moles

16:57

問題概要

問題文

日本語だし書くの面倒だから問題文を見て

続きを読む

2018-07-02

AOJ2560 Point Distance

23:10

問題概要

問題文

2次元平面の各格子点上に9個以下の点がある。(本質だけに絞ると)距離が√0、√1、√2・・・になる点のペアがそれぞれ何個ずつあるかを答えよ。座標のサイズは縦横1024以下。

続きを読む

2017-12-12

「インラインDP」というテクニックに関して

22:17

12月14日,式に一部間違いがあったので修正しました

競技プログラミングAdventCalender2017の12日目の記事です。この記事では、最近コンテストでしばしば見かける「インラインDP」というテクニックに付いて説明します。まぁ「インラインDP」と呼んでいるのはおそらく自分だけで、他の人たちは「segtreeを使ったDP高速化のやつ」とか「実家」(典型テクニックだから、という意味で)とか呼んでいますが、おそらくこの呼び方が自分では一番中身をあらわしていると思うので、それで行こうと思います。

さて、インラインDPの例題として次の問題の解法を考えていきましょう。

ARC073F問題 Many Moves

まずこの問題を解くためには、

dp[何個目までのクエリを処理したか][1つ目のコマの場所][2つ目のコマの場所]:=それを達成する最小の秒数

という状態を持ってDPすれば解けます。しかし、i個目のクエリを処理した直後は、必ず片方のコマはx_iに置かれているので、

dp[何個目までのクエリを処理したか][もう片方のコマの場所]:=それを達成する最小の秒数

という状態を持てばいいです。これは以下のような2次元DPで、i個目までのクエリを処理した、というもののiを0からNまで加算しつつ埋めていけば解けます。しかしこれでは状態量が最大NQとなり、実行時間的にもメモリ的にも到底収まりません。

f:id:skyaozora:20171212085509p:image

そこで、計算量を改善するために、まずは遷移を考えてみましょう。dp[i][j]、つまりi番目までのクエリを処理して2つのコマがそれぞれ位置x_iと位置jにある場合、次のi+1番目のクエリを処理するために、

・位置x_iにあるコマを位置x_{i+1}に動かす

・位置jにあるコマを位置x_{i+1}に動かす

という2通りの方法があり、それぞれに対応するDPの更新式は

dp[i+1\][j\]=min(dp[i+1\][j\]\:,\:dp[i\][j\]+|x_i-x_{i+1}|)

dp[i+1\][x_i\]=min(dp[i+1\][x_i\]\:,\:dp[i\][j\]+|j-x_{i+1}|)

となります。

ここで、更新式の遷移元ではなく遷移先に注目すると(界隈でよく言われている呼び方で言うと、配るDPから貰うDPに変換すると)

dp[i+1\][j\]=dp[i\][j\]+|x_i-x_{i+1}| (j!=x_{i})

dp[i+1\][j\]=\min_{k=1,...,N}dp[i\][k\]+|k-x_{i+1}| (j=x_{i})

となります。すると、dp[i+1]という1次元配列(つまりDPテーブルのi+1行目)は、dp[i]という1次元配列(つまりDPテーブルのi行目)と比較して、(全体に|x_i-x_{i+1}|という定数を足した上で)x_{j+1}番目の要素しか変化していないということがわかります。このように、DPテーブルのi行目とi+1行目が1箇所しか異なっていない場合、インラインDPというテクニックを用いて計算量を減らすことが出来ます。

どうするかというと、まずDPテーブルを愚直に2次元で持つのではなく、1次元で持ちます。そして最初はその1次元配列をDPテーブルの1行目で初期化し、次にその配列の1箇所のみを更新してDPテーブルの2行目を表し、その配列の1箇所をのみ更新してDPテーブルの3行目を表し・・・ということを繰り返していくことで、更新回数がO(Q)回、空間計算量もO(N)でDPテーブルをQ行目まで計算することが出来ます。これがインラインDP(私が勝手に名付けただけですが)というテクニックです。

f:id:skyaozora:20171212085506p:image

ただし、その1回の更新では

\min_{k=1,...,N}dp[k\]+|k-x_{i+1}|

というものを求めなければいけないので、これを愚直に計算すると1回の更新につきO(N)かかってしまい、全体の計算量がO(NQ)になってしまいます。しかし、これも競プロの問題でよく使われるテクニックで解決できます。これにはまず各k=1,...,Nに対して

dpl[k\]=dp[k\]+N-k

dpr[k\]=dp[k\]+k

を満たす配列を持っておきます。すると、

\min_{k=1,...,N}dp[k\]+|k-x_{i+1}|

=min(\min_{k=1,...,x_{i+1}-1}dpl[k\]-N+x_{i+1}\:,\:\min_{k=x_{i+1},...,N}dpr[k\]-x_{i+1})

となるので、配列dpl,dprそれぞれのある連続区間の最小値を求めればよくなります。連続区間の最小値は皆さんご存知のようにsegtreeを用いればO(logN)で求めることが出来るので、1次元配列をそのまま持つのではなく、

dpl[k\]=dp[k\]+N-k

dpr[k\]=dp[k\]+k

という補正を行ったdpl,dprをそれぞれsegtreeとして持つことで、全体の計算量O(QlogN)でこの問題を解くことが出来ました。このように、この「インラインDP」というテクニックを用いる場合、単純な1次元配列を用いるだけでは解けずsegtreeやBITといったデータ構造を用いる必要があることが多いです。そのため「segtreeを用いたDPの高速化テク」と呼んでる人たちが多いですが、それだともうちょっと指す範囲が広そうなのと、自分はこのテクニックで一番重要なのは

「1次元配列の一部だけを更新していくことによって、実際には2次元であるDPを上から下まで計算できる」

という点だと思っているので、そこを表せそうな「インラインDP」という名前をつけてみました。

最後にこの問題の解答コードを載せます

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define pf push_front
typedef long long lint;
typedef complex<double> P;
#define mp make_pair
#define fi first
#define se second
typedef pair<int,int> pint;
#define All(s) s.begin(),s.end()
#define rAll(s) s.rbegin(),s.rend()
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
#define N 262144
lint dat[2][N*2+10];
lint inf=1145141919810364364LL;
//[a,b)の最小値
//外からは(a,b,0,0,n)として呼ぶ
lint query(int a,int b,int id,int k=0,int l=0,int r=N){
	if(r<=a || b<=l) return inf;
	if(a<=l && r<=b) return dat[id][k];
	lint vl=query(a,b,id,k*2+1,l,(l+r)/2);
	lint vr=query(a,b,id,k*2+2,(l+r)/2,r);
	return min(vl,vr);
}
void update(int id,int k,lint a){
	k+=N-1;
	dat[id][k]=a;
	while(k>0){
		k=(k-1)/2;
		dat[id][k]=min(dat[id][k*2+1],dat[id][k*2+2]);
	}
	return;
}
int x[252521];
int main()
{
	lint sum=0,out=inf,out2=inf;int n,q,a,b;
	cin>>n>>q>>a>>b;x[0]=a;
	rep(i,2) rep(j,N*2+5) dat[i][j]=inf;
	update(0,b,n-b);update(1,b,b);
	rep(i,q) cin>>x[i+1];
	rep(i,q){
		lint dif=abs(x[i]-x[i+1]);
		sum+=dif;
		lint ne=min(query(0,x[i+1]+1,0)-(n-x[i+1]),query(x[i+1],n+1,1)-x[i+1]);
		update(0,x[i],ne-dif+n-x[i]);update(1,x[i],ne-dif+x[i]);
	}
	rep(i,n+1) out=min(out,dat[0][i+N-1]-(n-i));
	rep(i,n+1) out2=min(out2,dat[1][i+N-1]-i);
	assert(out==out2);
	cout<<out+sum<<endl;
}

さて、インラインDPの説明をするためにあえて無視をしていたのですが、この問題を解くためには「全体に|x_i-x_{i+1}|という定数を足した上で」1箇所を更新しなければいけませんでした。StarrySky木などを使えばSegtreeの全体に加算するということも出来ますが、このコードでは全体にいくつ足されたか、という情報をまた別に持っています(ただし、dp[x_{i+1}\]の最小値を更新する際にその分を考慮しなくてはいけません)これもよく使われるテクニックなので抑えておきましょう。

関連問題

さて、この問題以外にもこの「インラインDP」のテクニックを使って解くことの出来る問題を載せておきます(ここに乗せるということ自体が一種のネタバレで申し訳ございませんがご了承ください

ARC085F問題 NRE

ARC056D問題 サケノミ

AGC015E問題 Mr.Aoki Incubator

最後に

さて、この記事は参考になりましたでしょうか。式や図が分かりにくくて理解できないって場合はこの記事のコメント欄やtwitterまでお願いします。出来る限り対処したいと思います。この記事を読んでくれた皆さんが来年以降も競技プログラミングを楽しんでくれることを、そしてこの記事が少しでもお役に立てることを祈りつつ、良いお年を!

2016-12-24

競技プログラミングを始めての10年を振り返る(後編)

23:44

競技プログラミングアドベントカレンダー2016(その2)の24日目の記事です、前回の記事に続いて、2011年から2016年の6年間を振り返ります。

2011年(B1→B2)

TopcoderRating:2288->2353(年31回参加/計98回参加)

CodeforcesRating:1996->2254(年16回参加/計26回参加)

診断人さんのニコ生による「Topcoder占い」で幕を明けた2011年。年始にはその診断人さん主催によるオフ会があり、いつも放送で声だけは聞いていた診断人さんに初めてお会いできました。

Codeforcesは前年末にRed(当時のボーダーは2000)直前まで迫ったもののアップダウンが続いて中々届かないという状況が続いてもどかしさを感じてました(そんなのばっかりだな)。それでも何とかRedcoderに到達、Topcoderと併せてダブルRedcoderとなりました。

この年で特筆することと言えばGCJJの開催ですね。GoogleJapanの方々のお陰でGCJの日本限定コンテストが行われました。元々は3月開催予定でしたが震災の影響で10月へ延期となりましたが、日本語の問題文でGCJ形式のトーナメント、決勝の後には日本語での解説放送も行われました。また上位200人*1は翌年2月に行われるGoogleJapan本社での懇親会に招待されました。

そして本家のGCJ。この年は都合によりTCOに出れないこともあり気合を入れて望んだのですが、昨年は通過したR2で敗退・・・。成績が後退してしまうのはショックでしたね(悲劇がこの年のみに留まらないとはこの時は知る由も無く・・・)。そういえばこの年のGCJオンサイトは日本で行われたんでしたっけ。rng_58氏が前年のTCO優勝に続いて世界大会2連勝を達成していました。やばすぎ。

SRMは年明けから結構上手く行った回が続いて、割と問題が解けるようになったかな?という手ごたえを得たりしたもののそこからまたレーティングは上がったり下がったり。夏に一瞬レート2500超えを達成するもそこからは伸び悩んで最終的には年始から100も上がらずR2353で終了。ちなみにこの年はSRMの参加者が相当増えて、何度か参加上限を増やしたけどそれでも登録の締め切り時間より前に参加上限の人数に達して締め切られるということがよく起こっていました。

一方Redcoderになって一安心していたCodeforcesですが、何と秋にレーティングの基準が変更され2200からRedcoderとなり自分はイエローコーダーとなってしまいました。そこからやばい!何とかレーティングを上げないと!と思いコンテストに頑張って参加してみたら幸運にも2回続けて高順位を取り、一気にレートを200近く上げてRedcoderに復帰できました。特に2回目のコンテストである#97では今でもコドフォでは自己最高タイである11位。提出の後に間違いに気づいて再提出して正解したり、Pretestで2回弾かれたものの2回ともコーナーケースに気づいて正解できたりと、今振り返っても印象に残る「神ってる」コンテストの1つだったなぁと思います。

この年は過去問を解いてたのも含めて結構Topcoder一色な1年だったかなーという気がしますね。SRMは参加者が多くてそれだけで盛り上がってる感があって楽しかったですし、その後毎回のように診断人さんのニコ生も聞いていましたし。特に何か大きなことがあった1年ではないですが、この年の練習が後々に生きてきたかなーと勝手に思ってます。

2012年(B2→B3)

TopcoderRating:2353->2604(年35回参加/計133回参加)

CodeforcesRating:2254->2279(年8回参加/計34回参加)

この年には、まずは前年に開催されたGCJJの上位入賞者の人が集まっての懇親会が行われました。それまで参加してた競プロ系のオフ会よりも参加人数が相当多かったこともあり初めてお会いする方も多かったですね。

またこの年の3月にJAG主催で開催された冬コンテストにICPCのチームで参加したのですが、結構上手く行って*2、「他の人がPCを使ってる間に紙上コーディングで準備をしておく」「WAしたコードを印刷してPCを使わずデバッグする」「複数人の考察を合わせて解法にたどり着く」といった面白さも感じてチーム戦も楽しいじゃないかと思うようになりました。この年はICPCで初めて国内予選を突破して夏合宿及びアジア地区予選に参加、そこでもまた色々な競プロ勢の方と初めて会うことができました。

一方Topcoderに関しては、年明け最初のコンテストでいきなり前年のレート上昇分を溶かすと、0点も経験して何と1年以上ぶりにイエローコーダーに逆戻りしてしまいました。流石に落ち込んでいたのですが、その後はチャレンジで荒稼ぎできた回が2度あったこともあって一気に上昇、SRM546では初めて本番中にDiv1Hardも通せたりもして一気に最高でR2700台まで上昇。年末の状態でも年始よりかなりレートを上げた状態で終えることができました。

しかしSRMは全体的に好調だったもののTCOは上手くいかず、オンライン最終ラウンドまで残ることができませんでした。そしてGCJ、昨年落ちたR2は何とかギリギリながら通過すると、R3もLargeが全て通ればオンサイトという状況に。終了直後ドキドキしながらリロードすると結局Largeが2つも落ちてましたw結果的にはオンサイトは大分遠かったわけですが、またチャンスがあるところをものにできなかったなーという気持ちでした。

またこの年にはDeNA社がTopcoderのスポンサーになり、DeNAの本社でTopcoderMeetUpが何回か行われました。みんなで集まってSRMに参加、終了後にはすぐにwriter直々の解説が行われました(この回には日本人writerが割り当てられるように調整されていたんでしょうね)さらに寿司を含む飯も無料で食べることができたというすばらしいイベントでしたw

そして忘れてはいけない日本競プロ界における重要な変換点、この年にAtcoder社が立ち上がり日本語でのコンテストARCが開催されるようになりました。またARCだけではなくAtcoderのシステムを利用した企業主催のオンサイト付きコンテストも行われるようになり、前編でも紹介したKlab社主催の天下一プログラマーコンテストがこの年から復活しました。自分ももちろんオンサイト進出を狙って予選に参加したのですが結果は遠く及ばず・・・表彰式だけ見学させてもらいましたが、あの場に立ってる人が羨ましいなぁ、自分も立てたらなぁ・・・という思いでした。

自分としてもこの年には競プロ関連で色々な方にお会いできましたし、またチーム戦という新たな楽しみ方も見つかったり、そしてAtcoder社が誕生して日本の競プロ界が大きく変わり始めたりと、「世界が広がった」1年だったなぁと思います。

2013年(B3→B4

TopcoderRating:2604->2432(年35回参加/計168回参加)

CodeforcesRating:2279->2308(年11回参加/計45回参加)

この年はTopcoderのレーティングに関しては伸び悩みましたねぇ。一度も2700台に乗ることも無く、年末には一時2300台にまで落ちました。これまで年末のレーティングで比較したらずっと単調増加で来たのですがついにそれが止まってしまいました。

さらにGCJ、これまで4回の参加においてR2は敗退→通過→敗退→通過となっていて、順番的にこの年は敗退だなぁとちょっといやな予感はしつつも流石にもう実力的に大丈夫だろうと思っていたのですが、何とLargeが1つ落ちてこの年も敗退。2年前以上にショックでしたね・・・

一方TCOは何とか勝ち進み、R3BではMediumが得意なDPだった上素早く解けてこれはついにオンサイトに届いたか!?と思ったらEasyでしょうもないミスをしていて結局この年も届かず。もちろん人数を考えると相変わらず全然届かなくて当然ではあるのですが、そうはいってもチャンスはあるなーという思いと、でもそのチャンスをことごとく逃してきてるんだよなーという思いと。

ただ嬉しいこともありまして、この年も開かれた天下一プログラマーコンテスト。予選Aは惨敗し、予選Bもマラソンっぽい感じの問題が出てこれもう駄目だなーと半ばあきらめかけていたのですが、運良く構成法を思いついてギリギリ予選通過、初のオンサイトコンテスト進出を果たしました。自分の中でひとつ壁を越えた感じがあってとても嬉しかったですね。さらに本戦も数え上げが丁度いい難易度で出たおかげで入賞を果たし初めて賞金を得ることができました。(天プロはこの年から3年連続で本戦出場、入賞を果たせたのでかなり相性のいいコンテストでしたね)

そしてこの年もICPCアジア地区予選に参加。競プロ界の知り合いも前年より増えましたし、観光もあって前年以上に楽しむことができました。またこの年は海外のアジア地区予選にも参加しました。(引率の金子先生本当にありがとうございました)

そして12月にはリクルート主催のプログラミングコンテストが開催されました。1ヶ月前に突然ページができて最初はみんな「何だあの謎なコンテストは?」と思って「謎コン」という呼び名が付いていた位なのですがw、蓋を開けてみたら問題はAtcoder監修ということもありちゃんとしてて、さらに上位陣には賞金に加えてアメリカへのツアーも付いているという気合の入りまくっていたコンテストでした。

この年はまたさらに色々なイベントに参加して色々な方にお会いできて、前年以上に世界が広がった年だなぁと思いましたね。

2014年(B4M1

TopcoderRating:2432->2714(年41回参加/計209回参加)

CodeforcesRating:2308->2108(年3回参加/計48回参加)*3

まずこの年の頭には前年にあったリクルートプログラミングコンテストの本選でアメリカに行ってきました。ちなみに本選は卒論提出と卒論発表の間という凄まじい日程で、許可して下さった指導教員には本当に感謝という感じですね。さらに当日は大雪で出発が遅れたりとドタバタでスタッフの方は本当に大変だったでしょうね・・・(参加者同士で「俺がこの立場になったら何もかも捨てて1週間くらい家で寝てるわ」とか話してましたw)

そして前に記事としても書きましたが、この年はICPCの世界大会にも参加しました。問題に相当恵まれたりチームメイトが神だったりしたおかげで期待を大きく上回る7位銀メダル獲得!最高の形でICPCを終えることができました。*4

そして個人コンテストとしては、GCJは隔年の法則通り?R2を通過。この年は過去最高の111位、さらにLarge1つ落ちても大丈夫という余裕があったので流石にもう来年で隔年は終わりでしょとこの時は思ってました。そして運命のR3は何と明らかな早解きセット。通過ボーダーと同じ点は取れましたが20分ほど届かず48位。2年前に続いてR3まで残ればやっぱワンチャンあるなぁとは思いましたが、この年で届かないなら一体いつ届くんだという思いでした。

一方TCOは前年同様R3まで残ると、R3BではEasyでかつて自分が考えたことがある問題が出たおかげで一瞬で解け、さらにチャレンジも上手く行ってMedが通せないながらもOnsite進出を果たしました!OnsiteではPetr,tourist,tomekといった名前だけは知っていた世界トップの参加者とリアルに会えて本当に感動でしたね。

また自分は他の予定と不幸にも衝突してしまったため参加できませんでしたが、この年からリクルート主催のコードフェスティバルというコンテストが開催されました(新たなコンテストというか、前年の「謎コン」を進化させた感じでしょうか)。200人がオンサイトに進出、さらに1泊2日でコンテストだけではなく様々なコンテンツも提供されるという国内では最大規模のイベントになりました。

2015年(M1M2

TopcoderRating:2714->2539(年34回参加/計243回参加)

CodeforcesRating:2108->2412(年7回参加/計55回参加)

この年の頭には「ドワンゴからの挑戦状」というまた新たなオンサイトつきプロコンが生まれました。今までの各種企業主催コンテストも採用の一環ということだったのでしょうが、このコンテストは学生の中でも特に就活生に当たる学年に枠の大半が割かれ、さらに上位入賞者には採用のプロセスを一部スキップできるという、特に採用に大きく関わったコンテストでしたね。

この年のGCJ、隔年の法則から言うとR2で落ちる年でしたが流石に今年こそは本当にもう大丈夫だろう、と思ってたら何とまた敗退。しかも1111位という初参加の年を除いたら最悪の順位で上位1000人に与えられるTシャツすらゲットできませんでした。

この年からTCOのオンサイト進出人数が24人から12人に減ってしまいました。流石にR3まで進めたもののOnsiteは無理、前年に経る直前にいけて本当によかったという感じでした。ただその代わりというか、4回行われたR2は各地でオンサイトイベントが行われ、日本でもR2Cでオンサイトイベントが行われました。(国内ではかなり久しぶりのAtcoderの絡まない競プロのイベントだったのではないかと)

TCO以外の普段のSRMではこの年の前半はかなり調子がよく、SRM660で初の1位をとったりして一時期レーティングが2900に乗りました。これはワンチャンTargetいけるか?と思ってたらその後0完を3回やらかしてあっという間に急落。やはり単なる確率の偏りでしたね・・・

また前の年の終わりごろから予兆はありましたが、この年にSRMの参加者ががくっと減っていきましたねぇ。もともと減り始めたところに、コンテスト中のトラブルが続いたりサイトのデザイン変更で見づらくなったりして歯止めが利かなくなった感じですね。自分はTopcoderを通して相当競プロが上達したというのもあってTopcoder大好きで、それだけに悲しいことなのですが、これはもう仕方ないかなぁ・・・

2016年(M2→社会人1年目)

TopcoderRating:2539->2595(年21回参加/計264回参加)

CodeforcesRating:2412->2299(年5回参加/計60回参加)

Atcoder:初参加->2661(年13回参加/計13回参加)*5

この年のGCJはまた隔年どおりというか通過することができました(ただLarge1個落ちたら即死という状況でしたし、ほんとGCJのR2は安定する気が全然しない・・・)。しかしR3は、2年前・4年前の時はワンチャンあるかなと思ったものの、今回は全然通過できる気配もないまま終了。これもうGCJOnsiteは一生無理っぽいですね・・・

一方TCOはOnsite枠がさらに減って8人に。流石にもう絶望ですね。SRMへの参加者減もとまる気配がなく、もう(Topcoderは)駄目みたいですね・・・。

またこの年の夏にはAtcoderのコンテストの国際化が始まりました。レーティングもいったんリセットされ、Topcoder/Codeforcesの様に色つきのレーティングとして表示されるようになりました。AtcoderGrandContestという新たなコンテストも始まり、ARC/ABCも含めて普段のコンテストでは英語でも問題文が提供されるようになりました。またその流れもあってか、この年からはAtcoder上で予選が行われるコードフェスティバルに海外勢も招待されるようになりましたね。Topcoderがこういう状況になってる今、このままAtcoderが世界でもCodeforcesに次ぐ地位を得ていって欲しいですね。

まとめ?

うーん前半以上にまとまりがない上単なる自分語りの成分が多くなってしまったような(GCJ,TCOの結果は毎年入れなくても良かったかも)。さらに当日ギリギリまで書いてたため誤字脱字等いっぱいあるかも・・・(気が付いたら後でこっそり修正しておきます)

とりあえずこの期間の日本の競プロ界全体においては、何と言ってもAtcoder社の存在が相当大きかったですよね。日本語のコンテストサイトが登場したことによってかなり参加者も増えたでしょうし、何より企業コンテストがうまれてオンサイトイベントの数が相当増えたのが大きな変化でしたね(それまではICPCのアジア地区予選かオフ会的なものくらいでしたし・・・)本当にAtcoder社に感謝するとともにこの時期に学生でいられて本当に運が良かったなぁという感じですね。

そして個人としては、改めて振り返ってみても本当に大学生活は競プロ一色だったなぁとwTopcoderも本当に300回近くも参加してたんですね・・・自分は本当に競プロ以外の能力が一切ない人間なんでこの後社会でやっていけるのか不安でしかないですが、まぁでも競プロ自体は好きなんでちょっとまだ当分は離れられそうにないですね・・・

来年も日本の競プロ界がさらに盛り上がることを、そして自分もまだまだ競プロを楽しめることを祈りつつ、皆さん良いお年を!

*1:日本人だけでこれは多すぎる気もしますが自分の記憶では200人だったような・・・違ったら指摘お願いします

*2:何とこの年の世界大会で銅メダルを獲得したアンダースコアーズにこのコンテストでは勝利していました(まぁ明らかに彼らが上手くいってなかったんでしょうけど)

*3:知ってる人は知ってると思いますが、この年は春にコドフォのサーバーの大規模なトラブルがありコンテスト数回分のレート変動が飛びました。私も実際にはもう3回参加しています。

*4:このあと国内予選なんか受けてませんよ

*5:全て12/24現在