2次元平面の各格子点上に9個以下の点がある。（本質だけに絞ると）距離が√0、√1、√2･･･になる点のペアがそれぞれ何個ずつあるかを答えよ。座標のサイズは縦横1024以下。
12月14日,式に一部間違いがあったので修正しました
競技プログラミングAdventCalender2017の12日目の記事です。この記事では、最近コンテストでしばしば見かける「インラインDP」というテクニックに付いて説明します。まぁ「インラインDP」と呼んでいるのはおそらく自分だけで、他の人たちは「segtreeを使ったDP高速化のやつ」とか「実家」（典型テクニックだから、という意味で）とか呼んでいますが、おそらくこの呼び方が自分では一番中身をあらわしていると思うので、それで行こうと思います。
さて、インラインDPの例題として次の問題の解法を考えていきましょう。
まずこの問題を解くためには、
dp[何個目までのクエリを処理したか][1つ目のコマの場所][2つ目のコマの場所]:=それを達成する最小の秒数
という状態を持ってDPすれば解けます。しかし、i個目のクエリを処理した直後は、必ず片方のコマはに置かれているので、
dp[何個目までのクエリを処理したか][もう片方のコマの場所]:=それを達成する最小の秒数
という状態を持てばいいです。これは以下のような2次元DPで、i個目までのクエリを処理した、というもののiを0からNまで加算しつつ埋めていけば解けます。しかしこれでは状態量が最大NQとなり、実行時間的にもメモリ的にも到底収まりません。
そこで、計算量を改善するために、まずは遷移を考えてみましょう。dp[i][j]、つまりi番目までのクエリを処理して2つのコマがそれぞれ位置と位置
にある場合、次のi+1番目のクエリを処理するために、
・位置にあるコマを位置
に動かす
・位置にあるコマを位置
に動かす
という2通りの方法があり、それぞれに対応するDPの更新式は
となります。
ここで、更新式の遷移元ではなく遷移先に注目すると（界隈でよく言われている呼び方で言うと、配るDPから貰うDPに変換すると）
となります。すると、dp[i+1]という1次元配列（つまりDPテーブルのi+1行目）は、dp[i]という1次元配列（つまりDPテーブルのi行目）と比較して、（全体に||という定数を足した上で）
番目の要素しか変化していないということがわかります。このように、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（私が勝手に名付けただけですが）というテクニックです。
ただし、その1回の更新では
というものを求めなければいけないので、これを愚直に計算すると1回の更新につきO(N)かかってしまい、全体の計算量がO(NQ)になってしまいます。しかし、これも競プロの問題でよく使われるテクニックで解決できます。これにはまず各k=1,...,Nに対して
を満たす配列を持っておきます。すると、
となるので、配列dpl,dprそれぞれのある連続区間の最小値を求めればよくなります。連続区間の最小値は皆さんご存知のようにsegtreeを用いればO(logN)で求めることが出来るので、1次元配列をそのまま持つのではなく、
という補正を行った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の説明をするためにあえて無視をしていたのですが、この問題を解くためには「全体に||という定数を足した上で」1箇所を更新しなければいけませんでした。StarrySky木などを使えばSegtreeの全体に加算するということも出来ますが、このコードでは全体にいくつ足されたか、という情報をまた別に持っています（ただし、
の最小値を更新する際にその分を考慮しなくてはいけません）これもよく使われるテクニックなので抑えておきましょう。
さて、この問題以外にもこの「インラインDP」のテクニックを使って解くことの出来る問題を載せておきます（ここに乗せるということ自体が一種のネタバレで申し訳ございませんがご了承ください
さて、この記事は参考になりましたでしょうか。式や図が分かりにくくて理解できないって場合はこの記事のコメント欄やtwitterまでお願いします。出来る限り対処したいと思います。この記事を読んでくれた皆さんが来年以降も競技プログラミングを楽しんでくれることを、そしてこの記事が少しでもお役に立てることを祈りつつ、良いお年を！
競技プログラミングアドベントカレンダー2016(その2)の24日目の記事です、前回の記事に続いて、2011年から2016年の6年間を振り返ります。
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年ではないですが、この年の練習が後々に生きてきたかなーと勝手に思ってます。
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つも落ちてましたｗ結果的にはオンサイトは大分遠かったわけですが、またチャンスがあるところをものにできなかったなーという気持ちでした。
またこの年にはDeNA社がTopcoderのスポンサーになり、DeNAの本社でTopcoderMeetUpが何回か行われました。みんなで集まってSRMに参加、終了後にはすぐにwriter直々の解説が行われました（この回には日本人writerが割り当てられるように調整されていたんでしょうね）さらに寿司を含む飯も無料で食べることができたというすばらしいイベントでしたｗ
そして忘れてはいけない日本競プロ界における重要な変換点、この年にAtcoder社が立ち上がり日本語でのコンテストARCが開催されるようになりました。またARCだけではなくAtcoderのシステムを利用した企業主催のオンサイト付きコンテストも行われるようになり、前編でも紹介したKlab社主催の天下一プログラマーコンテストがこの年から復活しました。自分ももちろんオンサイト進出を狙って予選に参加したのですが結果は遠く及ばず･･･表彰式だけ見学させてもらいましたが、あの場に立ってる人が羨ましいなぁ、自分も立てたらなぁ･･･という思いでした。
自分としてもこの年には競プロ関連で色々な方にお会いできましたし、またチーム戦という新たな楽しみ方も見つかったり、そしてAtcoder社が誕生して日本の競プロ界が大きく変わり始めたりと、「世界が広がった」1年だったなぁと思います。
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ヶ月前に突然ページができて最初はみんな「何だあの謎なコンテストは？」と思って「謎コン」という呼び名が付いていた位なのですがｗ、蓋を開けてみたら問題はAtcoder監修ということもありちゃんとしてて、さらに上位陣には賞金に加えてアメリカへのツアーも付いているという気合の入りまくっていたコンテストでした。
この年はまたさらに色々なイベントに参加して色々な方にお会いできて、前年以上に世界が広がった年だなぁと思いましたね。
TopcoderRating:2432->2714(年41回参加/計209回参加)
CodeforcesRating:2308->2108(年3回参加/計48回参加)*3
まずこの年の頭には前年にあったリクルートプログラミングコンテストの本選でアメリカに行ってきました。ちなみに本選は卒論提出と卒論発表の間という凄まじい日程で、許可して下さった指導教員には本当に感謝という感じですね。さらに当日は大雪で出発が遅れたりとドタバタでスタッフの方は本当に大変だったでしょうね･･･（参加者同士で「俺がこの立場になったら何もかも捨てて1週間くらい家で寝てるわ」とか話してましたｗ）
そして前に記事としても書きましたが、この年は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日でコンテストだけではなく様々なコンテンツも提供されるという国内では最大規模のイベントになりました。
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大好きで、それだけに悲しいことなのですが、これはもう仕方ないかなぁ･･･
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社に感謝するとともにこの時期に学生でいられて本当に運が良かったなぁという感じですね。
そして個人としては、改めて振り返ってみても本当に大学生活は競プロ一色だったなぁとｗTopcoderも本当に300回近くも参加してたんですね･･･自分は本当に競プロ以外の能力が一切ない人間なんでこの後社会でやっていけるのか不安でしかないですが、まぁでも競プロ自体は好きなんでちょっとまだ当分は離れられそうにないですね･･･
来年も日本の競プロ界がさらに盛り上がることを、そして自分もまだまだ競プロを楽しめることを祈りつつ、皆さん良いお年を！
競技プログラミングアドベントカレンダー2016の8日目の記事です。私が競技プログラミングと呼べるものを始めたのは2006年の10月か11月くらい、なので今年でもう競プロ暦が丸10年になります。という訳で、それを記念（？）して2006年から2016年まで1年ごとに競プロに関してどんな1年だったかを、レーティングの変化等も交えつつまずは最初の5年に関して振り返ってみようかなと思います。単なる自分語りではなく当時の競プロ界とかもちらっと触れられるようにしようかと思いましたが結局単なる熱い自分語りになってしまいそうなｗそんな内容ですがよろしければ見ていって下さい。
全ての始まりはこの年の9月末ぐらいかな？に科学部で同級生が「そろそろ情報オリンピックに向けての対策を始めないとなぁ」と呟いたことでした。別に私に対して誘うとかそういった感じのニュアンスでは全く無かったのですが、それを聞いて何かふと「自分も参加してみようかな」と思いました。
で、帰って情報オリンピックの公式ページから過去問を見てみました。確かに、最初の問題ならどういう風な処理をすれば答えが求まるかは何となく分かるような…。ただこの当時自分はプログラミングといえば、VisualBasicでフォームにボタンやらテキストボックスやらを配置してゲーム（とはとても呼べないものでしたが）を作るといった経験しかなく、いわゆる競プロで求められるコンソールプログラム的なものは全くピンと来ませんでした。
そこで書店でC言語の入門書を購入し、if文やfor文、配列や関数の使い方、ファイルからの入出力などを適宜自分で書きながら覚えていきました（ちなみにこの時買った入門書でサクラエディタが紹介されてたのでそれから10年以上たった今でも使っていますｗ）。練習として、当時生物の授業でランダムウォークで生命の子孫が収束していく実験をおはじきを使ってやったのでそれをシュミレートするプログラムを書いたり、数学の授業でランダムに配った時ポーカーのそれぞれの役が出る確率の話をしてたので役判定のプログラムを書いて実験したりしてました。
そうしてある程度プログラムを書くことに慣れたところで公式ページから過去問に挑戦してみました。正しくプログラムが書けると、100万回や1000万回の処理であっても、プログラムに入力を与えると一瞬で出力を返し、かつそれが公式ページに正しい答えと一致するというところに感動しました。競プロを始めて最初の感動は、アルゴリズムを工夫してどうこうではなく手数が大量にかかることでもプログラムが一瞬で答えを返してくれるというところでしたね（同意して下さる方はどれだけいるでしょうか）。
そして迎えた情オリ予選本番は、当時はまだ復活して2回目ということで予選通過のレベルはそこまで高くなく（代表になる方々は今と遜色無いレベルでしたが）、落ち着いて取り組めたこともあり初参加で予選通過を果たすことができました。こうして競プロに初めて触れた1年はかなり満足のいく形で終えることができました。
TopcoderRating:初参加→883(年5回参加/計5回参加)
そうして迎えた初の情オリ本選でしたが、流石にこちらは通過することができませんでした。その後はこういった形式の問題を練習する方法がよく分からず（情オリの公式ページにある過去問も少なかったですし）、どうしたものかと思っていたのですが、私が競プロを始めるきっかけとなった科学部の同級生の言葉が再び転機となります。
高1の夏休み、科学部の部室で彼がTopcoderというサイトを紹介してくれました。定期的にコンテストが行われていて、こんな感じでArenaにプログラムを打ち込むと自動で正誤判定が行われるよって感じのことを科学部においてあったパソコンで実演してくれました。ちなみにこの年は最初に日本人にTopcoderが広まり始めた年（もちろんその前から始めていた日本人の方もいる）なのですが、恐らくchokudaiさんが見つけて色々な方に布教していたのではないかと思われます。彼もどうやらSuperconでchokudaiさんから布教されたものと思われます。
早速これだ！と思って始めようとしたのですが、登録の大変さに挫折…。その後すぐに2学期が始まってしまい中々始められずにいたのですが、9月末の体育祭の代休に1日使って何とか登録したのを覚えています。そして初参加のSRMがいきなりUnrated回になったりしつつ、Rateがつき始めたらあっという間に灰色に…。最初のころは電子辞書を使って知らない単語をひとつずつがんばって訳そうとしていたので文章把握に大量に時間を消費し（流石にすぐ諦めて翻訳サイトを使うようになりましたが）、さらに言語自体にも慣れてなかったのでコンパイルエラーが出ると全く原因が分からなかったりしました（コンパイルエラーのメッセージも英語で出力されますしね。まぁ慣れてないと日本語でもどこが悪いのか分からなかったりしますが）。
ちなみにこれは参加3回目のSRMの本番中に書いたコードです。やることは分かってコードは書けたのですが何故かコンパイルが全然通らず、原因が全く分からないままコンテスト終了。そのときのコードがこれです。原因分かりますか？そう、配列なのにもかかわらず添え字を入れてないんですｗあまりに初歩的なミスですが当時の自分では最後まで見つけることができませんでした。本当にひどすぎますよね…
そうこうしているうちに2度目の情報オリンピック予選。Topcoderをしばらくやっていた所為で出力をprintfではなくreturnで返そうとしてしまうというのがあったけど流石にある程度慣れたお陰か前の年よりは危なげなく通過することができました。この年の間はまだ全然でしたが、Topcoderという間違いなく自分の競プロ人生において最も重要なものとの出会いを果たした1年でした。
TopcoderRating:883->1340(年20回参加/計25回参加)
迎えた2度目の情報オリンピック本選は、プログラムはある程度書けるようにはなってはいたものの、計算量の概念とかアルゴリズムを改善するとかを全然知らなかったので結局解けたと思った問題でも部分点しか取ることができず2年連続で落選。さらにTopcoderでも毎回全然思うように問題を解くことができず灰色から抜け出せる気配も無く、かなり競プロへのモチベが下がって、引退というほどではないですがもうSRMに参加するのはしばらくやめておこうという気分になりました。
そういう訳で数ヶ月ほど離れていたのですが、ある時ふと「またちょっとやってみようかな」という気分になって久しぶりにSRMに参加してみたりしました。するとその回ではそこそこの結果を残すことができ、そこから競プロへのモチベが回復していきました（実は自分の競プロ歴の中でもかなり重要なポイントだったと思います。もう1回やってみようと思わなかったり、或いは思ってもここで惨敗してまた叩きのめされたらどうなっていたんでしょう？）。
その後はまた上手くいかない回があったりしてちょっと上がったレートもすぐに元に戻ってしまったのですが、それでも本番中に解けなかった問題を後で復習したりするようになりました。そうこうしてるうちにやっと力がつき始めたのか、SRM409にて漸く半年以上ぶりにグリーンコーダーに復帰できました（同じコンテストでrng_58氏が日本人の高校生として初めてレッドコーダーになってました。ぱない）。その後は参加したコンテストの復習に加えてSRMの過去問も解いたりするように。この頃はよくchokudaiさんにSkypeで問題に関する質問をしてましたね（これは相当ためになったと思いますし、いつも答えて下さって本当にありがとうございました）。そうしてくると当然目標はDiv1、ブルーコーダーとなるのですが、結構レートのアップダウンが続いて中々届かずやきもきしてました。この頃は毎回コンテストが始まる直前はPCの前で緊張で体がガクガク震えてましたねｗそんな中SRM422で遂に念願のDiv1昇格。一度落ちますがすぐ次のSRMで復帰して、以降はずっとDiv1ですね。
そんな訳でDiv1の過去問にも挑戦するようになりました。この時代のSRMのDiv1Medは今から見ると「典型DP」と呼べるようなタイプの問題が非常に多く、SRMの過去問埋めを通してかなりDPの基礎的な力は身についたと思います。3度目の挑戦となった情報オリンピックの予選はちょっとミスってひやっとするも何とか通過。それまではまともにしてなかった「競プロの練習」というものをするようになったという意味で、この1年の特に後半はターニングポイントになりましたね。
自分のTopcoderへの熱が徐々に高まっていくと同時に、それまでは全然気にしてなかったレーティング上位勢のハンドルとかも見るようになりました。この頃のTopcoderは完全にPetr,ACRush,tomekの3強でしたね。国内ランキングではnyaさんやLaycurseさんといった辺りが1位争いをしていました。1ページにつき50人ずつ表示されるので、開いた瞬間に表示される国内上位50人に入るのが目標でした。またどの国の参加者のレーティングが高いかというランキングもあって、日本の順位の変動に一喜一憂したりもしてました。*1
さらにこの頃からTopcoderやSRMで検索して色々な方の参加記や記事を読むようになりましたね。特にgentooさん（恐らく日本で最初にTopcoderが紹介されたであろう記事に載っていた夷藤勇人さんです）の日記は何度も読み返しましたね。過去問を埋めていく過程でこの日記で触れているところまで遡ったら「確かに日記でこう書いてあったなぁ」と感慨に浸ったり。またTopcoder部というのが一番最初にできた頃だったと思うのですが、そこの一員であったtomerunさんやnaoya_tさんを一方的にライバル視してたり、cafelierさんがあっという間にRedcoderまで駆け上がったのを見て驚いたりしてましたｗ
TopcoderRating:1340->1890(年11回参加/計36回参加)
年が明けてからも相変わらずコンスタントにSRMの過去問を解いていました。2月頭くらいに5日くらい連続で何人かの競技プログラマーがTopcoderのArena上に集まって過去問を解くという練習会的なイベントがあったのですが、そこで一緒になったAyokura氏とwrong氏のプロフィールを見てみるとそれぞれ高校生・中学生とのこと。これはもしかして情報オリンピックの本選に2人とも来るのでは？と思ってたら案の定本選の懇親会でこの2人を見つけることができ、「あの練習会で一緒だったよね」と話すことができました。最初にコンテストサイトで名前(HN)を知った人とリアルで会う、というのはこれが恐らく初めてで感動しました。
その情報オリンピック本選のコンテストに関しては、練習をつんでいたお陰かかなり危なげなく通過。最後の年にして初めて合宿に進むことができました。しかし合宿では上位4人に入ることができず代表落ちとなりました。これで情オリの代表になるチャンスは完全に失われてしまったので、流石にショックでしたね…。
しかしある程度競プロにはまってきてたからか、その後もモチベーションが落ちることはありませんでした。むしろ情オリの資格を完全に失った高3の時が多分一番高校の間では競プロの練習をしてたんじゃないのかというｗ（この辺我ながらかみ合わないなーとも思うけど）。この頃に色々なアルゴリズムだったり、またDPの色々なパターンを身に付けられたと思います。この年は基本SRMが月2回しかなかったので参加回数としてはあまり多くはありませんでしたが、初めてイエローコーダーに昇格し、また初めて本番中にDiv1のMedium問題を通すことができました。
またこの年は初めてマラソンマッチにも参戦してみました。思いついた改善をしてみたらスコアが上がる、その様子がビジュアライザーで見ることができる、っていうのは面白いなぁとは思いましたが…。何か上位陣とはやっていることが全然違うというか、今のやり方では明らかに越えられない壁があるというか…。その後もマラソンマッチには何回か参加はしましたがどうにもちゃんとできてる感じがしなくて結局最近は全然参加してないですね。
ちなみに、この年には「天下一プログラマーコンテスト」の予選にも参加しました。え？と思った方もいるかもしれませんが、そう、Klab社主催のあの「天プロ」です。天プロは今のような形で開催されているのは2012年からですが、実はこの年にもちょっと形式は違うものの開催されていました。この年はチーム戦参加可能かつ予選はマラソンマッチっぽい形式（要するにSupercon予選みたいなやつ）でした。私は高校の後輩と予選に参加したのですが残念ながら通過できず。本選は数日間にわたって開催され、予選と決勝が存在したらしいです（今年のコドフェスみたいな感じ？）、楽しそう。チーム参加可能だったにもかかわらず優勝は個人で参加したwataさんだったらしいですね。流石だ…。またwataさんといえば、この年に行われたSRM443において日本人として初めてのTarget(レート3000)になっていましたね。日本人Targetはこれまで6人しかいません。
最後に、この年にはchokudaiさんによる最強最速アルゴリズマー養成講座の連載も始まりました。個人記事以外でこういうまとまったTopcoderに関する記事が出るのはこれが多分初めてじゃないでしょうか？これによってまたTopcoderに参加する日本人の層も広がった気がします（しかし、前半の説明は結構いいと思うんですが、後半に載ってる例題が難しすぎて、せっかく興味持ってくれた人も心折れちゃうんじゃないかと個人的には思ってましたね…まぁchokudaiさんも当時はまだ若かったですし、この辺の試行錯誤がきっと今のAtcoder運営にも生きてるんじゃないかということで）。
TopcoderRating:1890->2288(年31回参加/計67回参加)
CodeforcesRating:初参加->1996(年10回参加/計10回参加)*2
この年の最初の方は大学受験があったので流石にSRMには参加せず。とはいえ全く競プロから離れて受験に集中ということもできなかったので、SRMの結果をチラッと見たり問題を考えたりはしていました。センター試験終了直後のSRMは流石に出てもいいかなと思って出ようとしたのですが、早寝早起きの生活をしていたので深夜まで起きてられず寝落ち…。結局SRMへの復帰は受験終了後まで待つこととなりました（しかし同級生のrng_58氏やlyrically氏はそんな受験直前でありながらSRMに参加し続けて何と高校生Targetになっていました。やば過ぎる…）
そして大学受験も終了し、SRMに復帰…の前にTopcoderで参加したのはTCHSというコンテストでした。TCHSはSRMと同じ形式のコンテストですが高校生のみが参加可能です。2008年ごろまではSRMと同じタイミングで定期的に開催されていました。自分がこの時参加したのはトーナメントでしたがそれもどうやらこの年が最後だったようですね（自分も高校卒業直前にギリギリ参加できてよかった）。TCHSではtouristとneal_wuが圧倒的な2強だったと覚えています。
また、この年からCodeforcesという新たなコンテストサイトも生まれました。日本人で元々Topcoderに参加していた人たちの間では始まってかなり早い段階から名前が広まった気がします。自分も初めて参加したのはContest#4とかでした。ただこの回は確かキューが混みまくっていて、コンテスト半ばで出した提出の結果がコンテスト終了直前になってやっと分かるというレベルでしたｗ
もちろんTopcoderも。この年からSRMは月3回にまた増えましたし、さらにこの年からTCOへの参加資格も得たのでかなりの回数参加できましたね。レートが2000に乗ってからはまたアップダウンが続いて（Div1を目指していた頃と同じように）やきもきしていましたが、SRM478で遂に念願のRedcoderに！Topcoderを初めて3年弱、始めた頃はどんなレベルか想像もできませんでしたが、その憧れの境地に自分が到達することができました。流石に嬉しかったですね。
前述の様にこの年からTCO,GCJへの参加資格を得て、初めてのトーナメント形式のコンテストへの参加となりました*3。GCJは500人通過のR2を予想に反して通過できてR3まで進めました。もっと神がかっていたのはTCOで、毎回「次のRoundでこの順位を取ったら通過できない」というギリギリの順位で通過し続け、何と60人参加24人通過のオンライン最終ラウンドまでたどり着きます。その最終ラウンドも1問通して27位。毎年数名辞退者は出ると聞いていたので期待していたのですが、結局辞退者は2人で次点という何とも悲しい結果に。もちろん自分の実力からしたらここまでこれた地点で相当幸運なのですが、それでも何で最後の最後でちょっと足りなかったのかなーと嘆きましたね。
コンテスト参加以外でこの年の競プロに関する（自分の中での）大きな出来事は、まずは何といってもTwitterを始めたことですね。競プロ勢の人たちをフォローして、コンテスト終了直後には色んな感想が流れてきたり問題に関する議論が起こったりするのを見たり参加したりするのが楽しかったです。
次に、色んな競プロ勢の方々とリアルに会う機会ができ始めたってことですかね。ICPCへの参加（練習含む）を通してwataさんやkitamasaさん、shimejitanさんやkohyatohさんといったコンテストサイト上で名前を知っていた方々とリアルでお会いできました。またいわゆるオフ会的な集まりにも参加するようになって、この年のUTPCの懇親会ではkinabaさん(cafelierさん)やtomerunさんといった参加記をよく読んでた方々に会うことができて嬉しかったです。
最後に、（放送自体は既に前年からあったと思うのですが）診断人さんのニコニコ生放送を見るようになったということですね。この年はほぼ毎回SRMの後に放送されていた気がします。自分もほぼ毎回見てましたね、とても楽しかったです。特にBGMとしてよく流れていたPinkRoseは完全にこのニコ生の音楽として自分の中では定着しましたｗ
とりあえずこれで前半の5年は終了です（前半といっても半分よりは短いですけど）。いやー自分でも振り返ってみて懐かしいというか、もう10年もたつんだなーというか。しかし、この地点で既にRedcoderになれてたのにそのあとの5年はどうだったんだろう、この頃には始めてもいなかったけどいま自分より強い人とか普通にいるよな…とか考えると悲しくなるのでやめておきましょうｗ
後編もこのアドベントカレンダーの記事として24日に上げる予定です（間に合えば、ですが･･･）しかし、最初の5年は始めたばかりということで色々書くことがありましたが、後半は変化が無くて何を書けばいいのやら･･･。
*1：サイトのデザイン変更で恐らくこのあたりはもう見られないんですよね。悲しい…
*2：Codeforcesは当時の色分けで書いています。間違ってるかもしれないけど
*3：本文の流れ上こういう書き方にしましたが実はGCJは2009年の地点ですでに18歳だったので参加してQual及びR1は通過してたりします
2014年の6月にロシアのエカテリンブルグで行われたICPC世界大会に参加してきました。この記事はその時の記録です。
きっちり荷造りを済ませて8時からのSRMに参加する。が、Medで問題を勘違いした所為で実装が間に合わなかった上、Easyでは>=2と書くところを>2と書いていた所為でまさかの0完。WF直前に幸先最悪だが、まぁこれで悪運は全て取れたとプラスに解釈しておく。
その後、Skypeでチームメイトと重要な持ち物について確認する。この時tozanがQuest云々言ってたけどよく分からないしコンテストに必須じゃないならいいやとスルーし（当時はここまでQuestが深く関わるとは思う余地も無かった）、翌日に備え11時過ぎに就寝。
きっちり時間通り起床しサッカーを見ながら朝食を食べる。日本点入れられそうな気配が無いなぁ。家を出て日暮里から京成線の特急へ。何かアナウンスしてる到着予定時刻が調べたときと違うなーと思う。電車に乗ってると他の特急成田空港行きの電車と並走。あー確かに乗り換え案内で調べた時に途中で他の電車に乗り換えるとか書いてあったような気がするなーと思って乗り換える青砥だかで乗り換える（今思うと10分くらい早く着くために乗り換えの際に荷物を置き忘れるなどのリスクを負うのはどうなんだという気もしたけどまぁいいや）。*1
で、成田空港に到着して指定された待ち合わせ場所に行ってみるも誰もいない。まさか一番乗り？いや流石に金子先生はもう着てるはず･･･と思ってたらやっぱり少し離れた場所にみんないた。あとサッカーの結果を確認したらあのままスコアレスドローだったらしい。もう完全にドイツ大会の再現じゃん･･･。
台湾大会の時も見送って下さった金子先生の奥様に今回も見送られて出国ゲートをくぐる。その後スタッフの山口先生と合流、搭乗。早速台湾大会の時の飛行機で嵌ったインフライトテトリスを探すも、案の定40ライン消しのタイムアタックが無い奴だった･･･。結局あの後も飛行機には結構乗ってるんだけど40ライン消しタイムアタックはまだ出来てないなぁ。リクルートツアーの時には入ってはいたけどコントローラがジョイスティックでロクに操作できなかったし。
そんな訳で飛行機の中で特にやることも無かったけど、寝ようとしても2時間くらいごとに目が覚めてしまう。そんな訳で眠気も取れないまま中継地のイスタンブール到着。食事を取ったのち空港内の書店で時間を潰す。自分はこういう海外の書店に来た時は日本について書かれてるもの（旅行ガイドブックとか）を探すぐらいしかしてないけど皆さんはどうされてるんでしょう。何かトルコには有名なパズルの雑誌だか形式だかがあるらしいとtozanが言って探してたような。
そして搭乗時間が近づき乗り換えの便へ。エカテリンブルク行きの飛行機なので明らかにICPC参加者と思われるグループがちらほら。何かみんなめっちゃ強そうで気圧される。受験の時周りがみんな頭良さそうに見えるっていうのがあるあるネタらしいものの自分はそういうの感じたこと無かったけど、ここに来て初めてそれを実感する。
離陸。流石に時間も時間なので今度は多少は機内で眠れた。
早朝にエカテリンブルク空港着。着陸した瞬間に機内から拍手が起こったんだが何だったんだｗ前年の世界大会では電通大チームが飛行機から荷物が出てこないというトラブルに見舞われたらしいので少し警戒してたけどちゃんと荷物は出てきた。空港に既にICPCの看板があったので記念撮影。主催者が用意したバスに乗ってホテルへ。
ホテルに着いてチェックイン。ICPC関連の色々なグッツを受け取る。デバッグ用サイコロが面白いｗ
その後は鍵を貰って部屋へ。眠気が溜まってたので即行でベッドに突っ伏して寝る。
数時間後、部屋の電話が鳴って起こされる。昼飯に行くとのこと。ロビーに降りてメンバー（金子先生含む）に加えて山口先生・鷲崎先生と共にホテルの近くの飯屋へ（あれは何料理って言うんだろ･･･）。その後はちょっと近所を散策。公開されてたPVにあった巨大キーボードも実際に見る。もちろん踏んで遊ぶｗ
他にも鍵の橋とか（これ他にもっと有名なところがなかったっけ？）
有名らしいビートルズの壁絵（とも違うか、何て言うんだろ？）とか
色々と見て回る。
ホテルに戻ってきた後自分はまたちょっと寝る。起きた後はチームメイトの部屋に行って、デバッグの練習という名目で自分でやってバグらせてたAOJのCommonPalindromesをデバッグして貰う。UnionFindの仕様で知らない点があったことに気付いた。あと貰ったグッツの中にあったmp3プレイヤー的なもの、チームメイトは使えてロシア語の謎の音源が入ってるとか言ってたけど正直自分は聴き方が分からない。
その後はまたちょっと時間があって、コーチの金子先生と夜どこに食べに行くか相談。貰ったマップを見ながら色々考えたけどやっぱりよく分からないものを食べに行く勇気がなかったのでピザ屋へ。しかし英語すら通じないので写真と見比べながら食べたいピザの名前（ロシア語）を紙に必死に書き写して渡すというエクストリーム注文に。
それにしても夜になってもめっちゃ明るいなぁ、流石夏至付近で緯度がたかい土地だけのことはある。でもまぁカーテンを閉めたら普通に問題なく眠れた。
確か10時過ぎとかでこんな感じの明るさ
この日の夜にTeamRegistrationがあって大会として始まるみたい。朝食をホテルで食べた後、最後に練習としてちょっと幾何の問題を解いておこうかということになり、自分は出発前のチーム練習でやった2010年のWFのセットから、練習中には解けなかった3D幾何のK問題に取り組む。ライブラリを使いつつサンプルが通るまでにはなったものの提出するとWA。ここでまたチームメイトの助けを借りて何とか修正しAC。そうしたら丁度昼飯ぐらいの時間になったので金子先生を呼んで昼食へ向かう。昨日と同じく安牌と言うことでバーガーキングへ。
ホテルに戻ったらまた夜のRegistrationまで暫く自由時間･･･かと思ったら割とすぐに電話でよばれる。何かRegistrationに向かうバスがもうすぐ出るらしい。必ずしもこれに乗らなきゃダメってこともなかったみたいだけど、まぁとりあえず必要なものを持ってそのバスに乗って出発。既に色々なチームがいる。順番待ちの間にライブラリの最終確認を済ますもまだ時間が余りそう。tozanはその場で厚紙に自分のtwitter等のアカウントと狼の絵を描いて簡易名刺を作って国際交流をしていた。コミュ力のプロだ･･･。
自分も何かしないと（使命感）とおもって、話しかけやすそうなゲームやってる人に話しかけてみる。setやってるところに割り込んで指摘したら間違ってたｗ何ともはずかしいｗあと何かトランプやってる人に話しかけたらブリッジを知ってるらしい、感動。ただちょっとこの場でやるには面子が足りないみたい、残念。オランダの大会で貰ったペンを持って来て見せたら受けたかなぁとちょっと後悔。あと"I am an ace of Japan yorth team."とでも言っておけば良かったかなと（大分誇張ではあるが）。
そしてチーム登録。パスポート･学生証のコピーやら本番で持ち込むものやらを渡す。そしてTシャツ・名札・資料を貰い、チームで写真撮影。名札の紐の長さまで指定される。細かすぎィ！
その後は会場でビュッフェ形式の夕食。ここで他の日本チームと一堂にかいする。テーブルに付いて資料を開けてみたらチーム番号が72番ｗｗあと75番の東工大とは向かい合わせらしい。去年は東大と電通大が向かい合わせだったし東大はそういう運命？
用事を済ませて会場の外へ。何かラジコンやら巨大チェッカーやら色々置いてある。
そして、tozanとQuestで激しく争っているらしいケープタウン大の人々と遭遇。一緒に写真をとったりする。
そしてまたバスに乗ってホテルに帰宅。就寝。
この日は開会式。まずはIBMTeckTrekなるもの。一応聞いてみようという意志はあったけど英語だし普通に途中で寝てた疑惑。
その後は昼食。ハンバーガーがあるんだけど、列に並んでパンや肉や野菜やチーズが順番に渡される形式だった。開会式までちょっと時間があったので会場を一通り見て回ったり、みんなが落書きできる壁に折角だからと何か書いたり。tozanはQuestの点数稼ぎのために色々と奮闘。山口先生もなんか協力的で、他のRegionのコーチと写真を撮るというQuestのために上海交通大のコーチを紹介したりしてた。
そして開会式。最初にエカテリンブルグの紹介的なPVで地理的にアジアとヨーロッパの中間に位置するから･･･という理由で箸でピザを食べる演出が出てきて一同笑い。そしてエラい人の話や参加全チームの紹介、あと色々余興的なもの。いかにもロシアっぽい衣装で踊りを披露した人がいたけど、曲がチャルダッシュだったのが個人的に印象に残った（かつて浅田真央がFSの曲として使ってたので）。てかハンガリーの曲やんそれ。あと太鼓の上に水をたらして、太鼓を叩くと水しぶきが上がるって演出もあったけど、あれ膜は痛まないんですかね。大丈夫ですかね。
そして夕食をとって、会場内のIBMチリゾーンとかいうところでちょっと話を聞く。ポップコーンも貰う、うまい。とりあえず今日はまだ余裕もあるし歩いてホテルまで帰ってみようかということに。ほんとおそい時間でも外は完全に真昼間だなぁ。
この日はリハーサル。まず開会式とかやった会場まで前日と同様にバスで行って、そこからコンテストの会場まで徒歩で移動。めっちゃ本格的な体育館だ。ICPCのルール説明の映像が流れてるけどめっちゃ分かりやすい。そして入場して自分達の机へ。スリープ中のディスプレイに東大の校章がデカデカと表示されてる。こういうのでなきゃ大学の校章なんて意識しないなぁと。確かにイチョウだったな。
そしてリハーサル開始。大文字と小文字は区別しないという今まで見たことないことが書いてあったので、そういうのも含めてTLEやスタックオーバーフローの基準などいつも通り色々と試す。その後は普通に練習用問題を解く（全部WFの過去問）。tozanが13年のH問題で、メモ化していないためTLEするという自分が家で解いた時と全く同じはまり方をしてて面白かったｗあとはKMP使う問題を自分が書くことになりそうになってえー面倒だしやだよーとただをこねてたらevimaさんから「いやこれは本当にここをこう使うだけなので簡単ですよ」と言われたのでいやいやながらも何とか書き上げる。本番でこういう問題が出たら自分は書きたくないのでお願いしますよと何度も念を押しておく（単なる人間の屑だ）。
リハーサル終了後はまた開会式の会場に戻って昼食。その後練習セッションで出た質問に対して答えるセッションがあったけど、特に重要なことは何も無さそうだった。
それが終わると夕食まで数時間特に予定がない。tozanは相変わらずまたQuestの点数稼ぎに奔走。バスに乗って一旦ホテルに帰って休んでるのもありかなーと思ったけど、何か勿体ない気もするし折角だからこの会場でやってみようと思って大縄跳びに挑んでみる。いい年して何やってるんだかｗ
しかしやり終わると何か頭がくらくらするというか立ちくらみと言うかそんな感じが。とりあえずすぐ日陰に移動して休む。気温はそこまで高くないけど日はめっちゃ高いんで軽い日射病的なものにかかったんだろうか･･･。バスは1時間に1本しか来ないのでそれまで会場内の椅子に横になって休む。こうなるならとっととバスに乗ってホテルに戻っておけば良かった、よりによって本番前日に何やってるんだ自分アホか･･･orz
そしてバスが来てホテルへ。1時間弱だけどベッドの上でちゃんと睡眠をとってまたバスで会場に戻って夕食。その場で明日朝の集合時間だけ決めて自分はまたとっととバスに乗ってホテルに帰る。後から聞いた話だと、この夜にチームメイト二人はQuest埋めも兼ねてエカテリンブルグの街を色々見て回り、路面電車にも乗ったりしていたらしい。台湾大会の時にも思ったけど二人ともバイタリティに溢れすぎでしょ（自分が無さ過ぎるという節）。
朝起きてまずサッカーの結果を確認。まぁコロンビア相手に勝てるとは思ってなかったけど惨敗かぁ、完全にドイツ大会の再現でしたね。
朝食を食べてコンテスト会場へ。流石に緊張感が出てくる。諸々の荷物を金子先生に預けてチーム入場。自分達の机が入り口の近くだったんですぐ座ってしまったけど、後から金子先生に聞いたところみんなで正面まで行ってトロフィーにタッチしてから席に着こうみたいなアナウンスがあったらしい。英語リスニング力の無さｗ
入場完了からコンテスト開始まで数十分くらい、偉い人の紹介やルールのアナウンスが行われる。基本的に既知のことばっかりだったけど、気になったのは1時間前に順位表凍結＆風船の供給もストップされるけど、風船が3個未満のチームに関しては風船が運ばれるとのこと。なるほど、ある種の救済措置だし、どうせ上位争いに関しては影響無いしだしで結構いいルールかもね。でも3つとかだったらそこまで該当チームいないでしょ（とこの時は思っていた）。
そして開始直後の段取りなどを確認しているうちにコンテストスタート。
とりあえずテーブルの上に用意されてた水のペットボトルを開けようとする･･･もキャップが回らない。tozanに手渡したら普通に開いた。握力がなくて悲しみ。
まずはAをよむ。ゲームだったのでちょっと紙に書いて色々実験してみる･･･が、いまいち法則がつかめない。それ以外の問題も平行して読み進めていくも全然自明枠が無いような･･･実際10分くらいたっても周りもどこも1問も通してないしやっぱりそうなのか。
漸く全体で最初のACが出る、Kか。確かにいかにも見たことありそうなO(NlogN)で処理する系の問題だけど･･･すぐには出てこないな。そうこうしてる間にtozanがCは積分するだけの幾何なので行けそうといったので任せることに。書き始めて暫くするとCにもACが出たのでやっぱりそれでよさそうと確信する。
C,K以外にACが出てるDもよむも、確かに他より簡単そうなもののやっぱり分からない。するとevimaさんがKはダブリングで行けるのではないかと発言。確かに行けそうだったので自分が実装担当ということでその後を詰めることに。程なくしてevimaさんもDが解けたといったので3人でC,D,Kを平行して書く。
何度か入れ替わりながらデバッグしつつCのサンプルがあったらしいので提出、AC。とりあえず最初のACを出せて一安心。その後もD,Kと立て続けにAC(といっても既にこの地点で2時間近く経過)。解法が出てる問題がなくなったので解けてなくてACが出てるB,E,I辺りをよんでみる。Iは最大クリークっぽいけどサイズ的にも辛そうだしそのまんまじゃ問題としてどうかって気もするんできっとグラフの性質を使う系だろうとか発言する。*2
それ以外だとBが明らかに普通の（まだ解けそうな）問題に見えるな･･･ただ読んでるうちに「discreteとcontinuousってどっちが離散でどっちが連続だったっけ？」と分からなくなってevimaさんに聞くと「continuousが連続に決まってるじゃないですか！」といわれる。そりゃそうか。とりあえず連続の方の処理はできそうで、離散の方はナップザックDPすれば求まるけど愚直にやると間に合わないオーダー。でも関数の形が特殊だし、どうせmongeDPができてオーダーが落ちるやつじゃね？と当たりをつける。実際に手元でちょっとやってみると遷移が交差することが無さそうなのでそれで良さそう。アリゴリズムは週刊スパゲッティーソースで一度読んだだけだけど思い出しながら書いていく。
その頃evimaさんもEに関して「これkinabaさんの記事でよんだことがある」と発言。*3何でそんなの覚えてるんだ凄すぎでしょ。本人は記事のアルゴリズムを完全には記憶し切れなかったことを悔やんでいたけど、何とか思い出しつつ自力の考察も交えつつ解法をひねり出していく。
そしてBが書き上がり、サンプルも通って提出。WA。ここからEを書くのと交互にデバッグ。答えが0以下になり得るとか、それもメッチャでかいマイナスになりうるからinfの値を結構でかくしなきゃいけないとか、色々変更はしてみたけど相変わらずWAは取れない。連続パートはもう何度も修正して間違って無い気がして、あと間違ってるとしたらDPパートだけだろうから愚直DPを書いてdiffをとってみることを決断する。
Eのコーディングが一旦開いたタイミングで交代。愚直DPと、ランダムでテストデータを生成するコードを両方書いて、テストデータを作って2つのDPに食わす。やはり途中から全然結果が異なってる。でも一体何が原因でこうなっているんだろう。この時既に残りは1時間を切ってる。このままBもEも通らずに終わるのかな･･･というのが頭をよぎりつつも必死で原因を探す。何か-infばかりの時どこで最小値を取るかっていう扱いがおかしそう？と思って修正してみると愚直DPと合うようになる。そして投げるとAC。良かったと思うが、これもっとスムーズに通せていればメダルに届いてたかもしれないのにな･･･と思う。
残り30分、後はEに集中するしかない。何度かevimaさんに解法を説明してもらおうとしたけど自分の頭が足りないのか理解できない。ただサンプルが通るところまでは来てたみたいなので提出、WA。もう自分としては解法はあってるということにするしかないなと思って、とにかくコーナーケースっぽいグラフを入力の形にしてevimaさんに渡すというのを繰り返す。すると何回か修正したあと投げてみると、何とAC!正直通るとは全く思ってなかったから驚いた。チームメイトとハイタッチ。さらに会場に向かって手を振ったり机のカメラに向かってマスコットをかざしたりしてはしゃぐ。
残り10分くらいでは何もできないので、コンテスト中ずっと手を付けられなかったランチボックスを今更取り出して食べ始める。あと机の上も整理しておく。最後のカウントダウンにも参加、するとちょうど終了と同じくらいのタイミングで近くにいた精華大学チームから歓声が聞こえる。Standingsをみると提出してるのは5問だけ。うわー実は今まで勝ってたのに最後の最後で抜かれたのかーくやしいなと思う。*4
流石に銅メダルには届いたかなぁと思う。銀メダルまで可能性はあるけど、まずメダルが取れるかどうかが重要なのでそこはとりあえず置いておく。凍結前の順位表を見つつ、下のほうの順位で抜かれてる可能性があるチームを探す。うーん、最悪のパターンでは圏外に落ちてるけど流石にそんなことはないかなぁ。しかし不安は尽きない。
暫く時間が空いたのち閉会式。色々な余興とか、歴代優勝校の読み上げとかが行われるけど、こっちは気が気じゃないので早く結果発表してくれ～緊張感から解放させてくれ～ってなってた。
そして遂に結果発表の時。例のYes/Noおじさんが登場する。おぉあの読み上げが生で聞けると感動。ホスト校であるUrFUのPendingが通ると後ろから大歓声が。いいなこういうの。虐殺セットだったんでPendingも基本通ってないけど、上の方に来ると流石にYesの割合がめっちゃ多くなる。さすがだ。そして東大のPending、もちろん知ってただけど2問ともYes、ここで一瞬ではあるけど順位表で2位まで浮上してビックリ。この辺りでメダルは確定したので一安心。安心したところで食欲も戻ってきたのでランチボックスの残りのサンドイッチを再び食べ始める。
ここからはメダル圏内なので各チームよばれるごとに表彰が行われて流れがゆっくりになり、サンドイッチを食べる時間も十分にあった。そして暫くして銀メダルも確定、手で小さくガッツポーズ。金子先生に「去年の優勝チーム(ITMO)に勝ったじゃん！」と言われる（まぁ今年はtouristいないんだけど）。
そして東大がよばれて壇上へ。メンバー全員でぬいぐるみを持ってそれを客席に向かって振りながら向かうｗ一人ずつ名前を言ってメダルをかけられて盾を持って撮影。そしてメンバー全員でお偉いさん方と撮影。もしメダル取れたらめっちゃ喜ぶだろうなーと大会前は思ってたけど、あまりに運が良かった感じなのでむしろ帰りの飛行機は落ちないか大丈夫だろうかとか考えてたｗその後は壇上で待機。てか今更だけどずっと立って待機とかつらい。12位で最初に壇上によばれたチームは待つ時間がメッチャ長くなってつらそう。
壇上で待ってる間、金子先生が6位で隣だったSJTUのメンバーの1人に「去年のチームのメンバーは今年もでちゃうと引退になるから今年はこのチームが･･･」みたいな事情を日本語で説明していた。てか日本語通じるのか、すごいな。*5あとどっかのチームが表彰されるときにQueenのDon't stop me nowが流れてきてこれ町田樹がソチのエキシビジョンで滑ったやつやん！ってなってた。開会式のチャルダッシュとしいフィギュア色の強い曲のチョイスでしたね（そう思うのはお前だけ）。
そしていよいよラスト2校、SPbSUとMSUの優勝争い。凍結前4完だったSPbSUがなんと凍結後に3問通してて凍結前6完だったMSUをこの地点で逆転。MSUの最後のPendingは･･･Yes！も、順位の移動は起きない。結果はわずか39分のペナルティ差でSPbSUが優勝。彼らが壇上に上がったときにはトロフィーも授与され、そしてパーン！とクラッカーがステージの四方から鳴る。射出される場所が目の前だったんで軽くびびったｗ
そして閉会式も終了し、WFも全日程終了。山口先生がとりあえずメダル獲得の記念写真を取りたいことなので人が殆どいなくなってガラガラになったホールで撮影。その後外に出ると何かめっちゃ高い竹馬とか一輪車とかに乗って曲芸してる人達がいる。夕食は完全に出遅れたのでめっちゃ離れたところしか席が空いてない。tozanがQuestの優勝賞品としてタブレットを受け取ってた。てか本大会で上位な上にQuestでも優勝するとか冷静に考えてやばすぎでしょ。争ってた人のいるケープタウン大は結局0完だったし。
最後に京大・東工大・筑波大と一緒に日本勢全員で写真撮影。最後なので折角だからと会場の周りの出し物を色々と見て回ったけどまぁ特にやることも無かったのでバスに乗ってホテルへ。
まずチームメイトの部屋でコンテスト本番の机に置いてあった配布物の分配。自分は電卓を引き取る。そういや8桁の電卓で12345678を起点にコラッツ予想を試そうとしても途中でオーバーフローするけど、12桁の電卓で123456789012を起点にすると収まるんだよねーと言いながらその場で実演。途中に334が出てきてみんなで「な阪関」と突っ込みｗ
その後部屋に戻って荷造りを済ませる。済ませたところでホテルのラウンジで日本勢が酒チャレンジをしているとの情報が入ったので合流する。と言っても酒は別に好きじゃないので盛り合わせのフルーツだけ食べる。B問題の解法を聞かれたのでちょっと説明。そして明日も早いんで就寝。
朝早く起きて出発。バスではなく普通の車で関係者の方に空港まで送ってもらう。空港の椅子に座ると気を抜くと寝てしまいそうなぐらい寝い。
飛行機に乗ってイスタンブール着。ここでまた6時間ぐらい待ち時間があるので、手荷物を空港のロッカーに預け山口先生・鷲崎先生と共にここでしばし観光タイム。空港内にVodaPhoneの看板があって、そういや日本でも10年前には展開してたななつかしいなと思って撮影。
ガイドを頼んでいた現地在住の日本人の方と合流。電車に乗って市内へ出て昼食。トルコということでケバブを食べる。何か日本人としてはケバブはあのトルティーヤみたいな皮に巻いたものっていうイメージがあったけど実際にはもっと広いものを指すらしい。あとヨーグルトドリンクがあって美味しそうと思って飲んでみたけど、甘さがなくてむしろしょっぱさと酸味がある感じ。まぁこれはこれでなのかもだけど甘いのを想定して飲んだので驚きが。調子に乗って頼みすぎてたら残す羽目になって反省。
また食事中にガイドの方から色々話を聞く。ラマダーン（断食）の期間はバスの運転手とかも気が立ってて集中力をなくしがちだから事故が多くて怖いらしい。流石にまずいでしょそれｗ
そして寺院に入るために並ぶ。暑い外で並ばされるのでペットボトルの水を売る売り子がいるんだけど、「ワンリラワンリラワンリラワンリラウナリラウナリラウナリラウナリラ」ってずっと言っててめっちゃ耳に残るｗ（リラ＝トルコのお金の単位 ウナ＝トルコ語で1だと思われる）
そして寺院へ。おぉこれは素晴らしい光景。帰りがけにして漸くこの旅行で初めて観光らしい観光ができたと自分の中でも納得。そしてまた電車で空港へ。tozanがガイドの方にICPCの説明とかしてておーコミュ力すげーとか思う。ロッカーから手荷物を回収して成田行きの飛行機へ搭乗。寝る。
飛行機は墜落することなく無事成田へ到着、解散。コーチの金子先生、そして基本一緒に行動して色々と助けてくださった山口先生、本当にありがとうございました。そしてチームメイトの2人も本当にありがとう！皆さんのお陰で期待以上の結果を残すことができました。
*1：しかも後から気付いたけど成田スカイアクセス線経由だと到着ホームが違うから電車賃も若干高くなる。皆さんも成田空港に行く時はこのトラップに気をつけましょう。
*2：実際はただの最大クリークでした。この年のセットは難易度が高い割に既出・知識ゲーが多くて正直どうなのという気も。まぁそのお陰でいい結果が残せたので文句は言えませんが･･･
*3：こちらの記事になります。ちなみに自分は2年近く経った今もまだ理解できてない･･･
*4：しかし結果発表見てみたら通って無かったしあの歓声は何だったのか不思議。ギリギリで提出できたことに対する歓声？
*5：後から分かりましたがTankEngineer氏でした。今年の世界大会金メダルおめでとうございます。