読者です 読者をやめる 読者になる 読者になる

学習の栞

学びたいことと、学ぶべきことと、学べることの区別がついてない人間の進捗管理

CODE FESTIVAL 2015 参加記

プログラミング 競技プログラミング

要約

長文・乱文になりそうなので要約を用意しました。

本戦41位。こどふぇ楽しかった。来年もあったら出たい。

記事の大部分は、どのコンテンツで何を考えてたかをだらだら書くだけです。

CODE FESTIVAL 本戦以前

れじすたー

予選Aまで残り10日メールが来たので参加登録した。今年から前泊の基準が東京駅まで片道4時間になってる。早朝の時間帯に出発すると片道4時間ナントカ分掛かるものの、11時に会場に到着することのできる移動方法で最短のものは3時間40分程度らしい。4時間かかると言い張れなくはなかったが、4時間かからないと言って登録。

予選A

予選開始前、予選落ちの恐怖からガクガク震える。心拍数もだいぶ上がってた。予選Aの数日前のこどふぉで典型どころか定型のbitDP問を落としていたこともあり、予選落ちの不安が高まっていた。
結果は全完(45:48)で53位。自分にしては好成績である。しばらく勝ててなかった大学の同期たちに勝てて嬉しかった。
全完して予選通過確定したところで順位表の観測をはじめる。問題のレベルがレベルとはいえ、全完がこんなに出るとは思ってなかった。全完がボーダーが有り得ると思った。後日、全完した人は全員通過したらしいことがわかる。難易度調整すごい。

予選B

こどふぉd2onlyから予選Bへと休憩なしの2連戦。こどふぉで3問解いて撃墜まで済ませたあと、こどふぉ終了と同時に予選Bが始まる。D問題読んで「愚直に塗れば部分点もらえるよなー」と思って制約を見て絶望する。( 競プロサークルの一年生を3完+部分点の早解きで通そうと思ってたので、制約見てかなり厳しそうだと思った ) 5分ぐらい考えて区間で管理してマージすれば計算量的にも間に合うと気づく、辛い実装をやるだけの辛い問題だと分かって辛い気分になりながら実装した。100:18で全完して49位。同期や同じ大学の人より微妙に低い順位取ってて辛い気分になった。
予選Bでは3完部分点で遅くなければ一回目の連絡で通っていたらしい。辞退者が出たりして最終的に3完+部分点までは全員通ったらしく、素晴らしい難易度調整だった。

CODE FESTIVAL 前日まで

ゴルフ企画「短縮王」の問題が公開されて、元々手をつける気はなかったのだけど、twitter上でやってる人が多かったので手をつけた。1バイトを必死に削るのが面白く、ゴルフの魅力の一端に触れたような気がした。

CODE FESTIVAL 前日

研究室のゼミが長引いて研究室を出る時間が遅くなり、当日出発にしておいて正解だったと思った。荷造りをして眠ろうとしたが、眠れなかったのでコードを削ろうとした。削れたのは睡眠時間だけだった。

CODE FESTIVAL 1日目

移動

4:30起床。とれた睡眠時間は2時間程度。身支度をし、始発電車で空港へ向かう。自分が乗る予定だった飛行機が機材に不具合が見つかったため25分遅延する。某社のお金の力もあってANAの飛行機を取っていたのが良かった。これがLCCだったらもっと遅延してたんじゃないのかな。

9時頃羽田に到着。預けた荷物を受け取ってモノレールに乗るが、10時品川には間に合わないことに気づく。メールを送ってバスの乗車予定をキャンセルする。「当日出発にして正解だったな」とか言ってたのは嘘だった。品川駅には10時ちょっと過ぎに到着。さて、歩くかと言って会場の場所を確認したところで品川駅が会場の最寄りでないことに気づく。この時点で携帯の電池が切れたので、準備してあった路線図と地図を使って会場への経路を調べて移動する。JAG夏合宿の教訓が生きた。

10時45分に受付に到着した。なんとか間に合った。

受付 - 本戦前

受付を済ませてTシャツとリストバンドを受け取る。Tシャツ配ってる場所の近くにしょらーさん(@shora_kujira16)が居たのでお話する。ツカサさん(@tsukasa_diary)も居たのでお話しする。JAGの夏合宿以来である。kyos(@kyos1704)さんとかYazaten(@Yazaten)さんとかとお話したのも本戦前だったっけな。

席番は136。斜め前の隣ぐらいにzerokugi(@zerokugi)さんが居た。あとから気づいたのだけど、斜め前がhogloid(@hogloid)さんで自分が座ってた島にプロが2人も居た。

今年のパーカーラインが5完であると言われる。パーカーはばら撒くが、問題の難易度落とす気は無いということか。5完なら余裕かなーとか思いつつ、去年はなんとか5完したものの、1問詰まると5完危うい感じだったことを思い出しパーカー取れない可能性もあるなと思う。

本戦

こどふぇがこどふぉる。45分の遅延。略称がCF同士だし、妥当なのだろうか。延期にはこどふぉで慣れたので何の問題も無い。安心感さえある。ネットワークの不調が原因での遅延だったが、去年の備えをGIZMODOの記事で見ていたので大きな問題にはならないだろうと安心していた。

A,B,Cはやるだけ。
D問題は一瞬セグ木か何かかと思ったが、累積和で解けることに気づく。まあやるだけ。
E問題は考察つめたら数えるだけになったのでAC。

! 0か非ゼロかを反転する。これが登場すると入力の数が何だったかという情報と符号が何だったかという情報が落ちる。
- 符号を反転する。入力の数の情報は保存される。

ということに気づけば、'!'の数と入力された文字列で最初に登場する'-'の数を数えればいいだけと分かる。

E問題参考

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
 
int main() {
	string s;
	int a, b;
	bool flg = true;
	cin >> s;
	a = b = 0;
	for(int i = 0; i < s.size(); i++) {
		if(s[i] == '-') {
			a += flg;
		}
		if(s[i] == '!') {
			b++;
			flg = false;
		}
	}
 
	cout << (a%2 ? "-" : "" ) << (b%2 ? "!" : (b?"!!":"")) << endl;
}

この時点でパーカーが確定し、気が楽になる。

とりあえずF問題を解きに行く。
難しい。6問目以降はさすがにこのレベルの問題を並べてくるか。
しばらく6問目を考えた後、順位表を見に行くとFとGのACがほぼ半々であることが分かり、G問題を読みに行く。林作って掛けるだけだけだと思って実装を始めるが、実装の途中で誤読があることが分かり、残り時間を使ってF問題を考えることを決める。

  • 無限の鍵盤だし、隣にしか移動できないし、ループっぽいグラフは書くよね。
  • 入力は頂点の次数だね。
  • オイラー閉路が作れるかどうか判定すればいいね。
  • ある場所の辺の数を決め打ちすると、できるグラフの形が分かるし上手くいくよね。

まで考察が詰まったので、張る辺の数で二分探できないか考えてみる方針が立つ。

  • フロー流す要領で辺の数を伝えていけば上手く判定できるんじゃね?

と思ったので実装して、オイラーグラフであるかどうかの判定部分をごにょごにょしたら通った。6完。
あとから考えたらこれ二分探必要なさそうなことに気づく。でも通れば勝ちなのでナントカ。

F問題参考

#include <iostream>
#include <vector>
using namespace std;
 
typedef long long ll;
 
int main() {
	vector<ll> C;
	C.resize(7);
	for(int i = 0; i < C.size(); i++) cin >> C[i];
	C[0]--;
	ll l, r, m;
	r = C[0]*2;
	l = 0;
	bool res = false;
	while(l <= r) {
		m = (l+r)/2;
		ll use = m;
		bool flg = true;
		int zero_cnt = m?0:1;
		for(int i = 1; i < C.size(); i++) {
			ll tmp;
			tmp = C[i] * 2 - use;
			if(tmp < 0)  flg = false;
			if(use > 0 && tmp == 0) zero_cnt++;
			use = tmp;
		}
 
		if(flg && m+use==C[0]*2 && zero_cnt <= 1) {
//				cout << m << " " << use << endl;
//				cout << m+use << "," << C[0]*2 << endl;
			res = true;
			break;
		}
		if(m+use>C[0]*2)
			r = m-1;
		else
			l = m+1;
	}
 
	cout << (res ? "YES" : "NO") << endl;
}


残り30分無いくらいで、残りの問題の考察詰めて実装を行うことはほぼ無理だと思ったので、本戦後の解説に向けて読んでいなかった問題を読んだ。

コンテスト結果は6完158:53で40位タイだった。提出IDが自分のほうが遅かったらしく、実質41位。1秒以下の差で負けるのは悔しい。とは言っても実力的に40位台はなかなか取れないので嬉しかった。睡眠時間足りてなくて眠い感じで出場したためにいつものSRMっぽさが出たのが良かったか。

このレベルの問題を解けたことが多くはないので、そろそろ壁を一枚超えることができるのではないかという自信につながった。

本戦後

しょらーさんの近くに行ったら知ってる人が集まってたので本戦の問題についておしゃべりをする。

解説

遅延の影響だろうか、あって無いような解説だった。スライド読もう。

夕食

寿司・肉巻きおにぎり・生春雨・ジェラートを選択。ピザは何処。

LayCurseさんトークライブ

LayCurseさんのトークライブを聞きに行く。が、睡眠不足が祟って半分ぐらいのところから記憶が飛んでる。折角LayCurseさん(自称レアキャラ)のお話を聞ける機会だったのに勿体無かった。

エキシビジョン

りんごさんがエキシビジョンに出ると聞いて、りんごさんのコーディング画面の前に張り付いてた。コーディングしていた時間よりも問題の画面を開いていた時間のほうが長かったように感じる。デバッグも怪しいところを出力して確認するといったようなことはせず、ソースコードと問題文の間を行ったり来たりしているようだった。凄いんだけど全然参考にならない。

チームリレーの顔合わせ

hogloidさんチームだった。名前を奪われた人(@hadrori)の提案により、チーム名がFCCPCに決定。本戦順位で同率40位だったうどんさん(@kw_udon_)とも同じチームだった。顔合わせでtsuburin(@tsubu_taiyaki)さんに話しかけてもらったよ、やったね(自分から声を掛けるのはなかなかハードルが高い)。前日に顔合わせて、少ししゃべりやすくなる制度いいなーと思った。

ホテルにて短縮王

会場からも短縮王A問題に提出していたのだけど、WAが出て通らない。こんな単純な問題が通らないなんておかしい!と思ってたら、出力する文字列を間違えていただけだった。

後日談




CODE FESTIVAL 2日目

会場まで

起床成功。が、眠い。チェックアウトし、バスに乗って会場へ。

あさプロ

今年はhard(1st - 30th), middle(31st - 100th), easy(101st - 200th)の3クラスだった。hardとmiddleの境界は妥当だと思うけども、middleとeasyの境界は昨年どおりでよかったのではないだろうか。
あさプロmiddleに参加。今年のコンテストページに asa! の文字列が無かったのは残念。A,B,Cをやるだけやるだけと言いながら解く。が、C問題でバグにはまってやるだけ感を出せずに辛い思いをした。3完69:57で46位。参加者のレベルが抑えられてるのに前日の本戦より悪い順位というダメな結果だった。
コンテスト終了後にmiddle D (hard B) について言及したツイートでヒストグラムの奴と言ってるのを見かけて頭いいなーと思った。

chokudaiさんトークライブ

chokudaiさんがお話しするというので聴きに行く。chokudaiさんにクソリプを送って許される貴重な機会だったのでここぞとばかりにクソリプを送る。競プロ界で最も有名な素数は1e9+7と1e9+9はちょっと言い過ぎではないだろうか。2と3だと思うんだけど。問題に対する典型的なアプローチのお話とか聞けて面白かった。

昼ごはん

西京焼き弁当を選択。りんごさんトークライブを聞きに行きたかったので急いで詰め込もうとしたがTLEした。

りんごさんトークライブ

人だかりができていて遠目に見ることしかできなかった。目が悪くて回答者の顔が分からない。。。。

書道コーディング

再帰版のgcdとlcmを書いた。1行でシンプルに書けて気に入ってる。

チームリレー

前日顔合わせがあったので、極端に緊張することは無かった。問題の担当は順位順で、順位がいい感じに離れてる人とペアを組んで方針に誤りが無いかを確認してやることになった。自分のペアはyumaさん。H問題の担当になったが、自分の実力でこの難易度の問題が解けるのかどうか不安になる。

ペアを組んだ人が円周率のあの問題を引き当てた。円周率30桁ぐらいなら一応暗記しているものの、不安があるのでその他の方針を考える。が、結局「産医師異国に向こう産後厄無く産婦みやしろに虫散々闇に鳴く頃にや」と有名な語呂合わせを唱えて円周率を書き出す。

自分の担当のH問題を読む。「色が9色... 盤面の大きさが最大で500 * 500 ... 」あれ、これやばい奴では?と思い出力するものを見て問題の解釈が終わったところで数分考える。考えた結果dijkstraやるだけだと思ったが、結構不安だったので2-3人のメンバーと方針を確認する。dijkstraで大丈夫そうだという結論になった。

他の人の問題の方針を聞いたりしながらワイワイやる。

自分のコーディングの時間が廻ってきたが、10分程度消費してしまう。しかもRE吐いてる。配列外参照してるところも無さそうだし、謎。するとresize(H)とすべきところをresize(W)としていると指摘が飛んだので、そこを修正してACした。

その後うどんさんがI通して、yumaさんが円周率の問題通して、hogloidさんがJ問題を通したところで、チームメンバー全員で残ったG問題のデバッグに取り組む。あれじゃないかこれじゃないかとバグがありそうな箇所の指摘が飛ぶ。最後はhogloidさんがredcoderの撃墜力を見せ付けて全完した。

自分がペアプロ好きなほうなのでかなり楽しめた。前日にはチームメンバーが分かっているというのも良かった。

ハッピーアワー

1時間ぐらい時間を取ってしゃべれる時間。と思ってたら表彰もこの枠でやるのね。直前にコンテストがあるとコンテストの問題をネタにおしゃべりできるのでコミュ障の多いコミュニティ的には良かった。

閉会式

まとめ映像流して写真撮って解散。ドローンでの写真撮影だった。あと、カメラマンさんが写真撮ってた。「心をオープンソース」で吹き出す競技プログラマたち。撮影後に心がオープンソースになった場合のライセンスについての雑談がなされる。このあたりは競技プログラマとはいえどプログラマのコミュニティか。

移動

面白かったなーと思いながら帰る。解散が始まったのが17:30頃だったので、帰りの飛行機の19:55には間に合うなーと思いつつ、迷ったら最悪帰れなくなるからと思い遠方特権を発動してblue_jamさん(@blue_jam)と一緒に会場を出る。会場の出口にトイレ5個さん(@chako0407)が居た。

会場に来る時にバスに乗らなかった(というより乗れなかった)おかげで駅までは迷わずに着く。駅のホームドアの高さに圧倒される(福岡の地下鉄のホームドアは胸ぐらいの高さ)。麻布十番で乗り換えて、さらに浜松町で乗り換えてからモノレールだと思っていたが、どういうわけか麻布十番で下りたら都営地下鉄から京急線へ乗り換えなしで行けてそれが羽田空港までつながっていた。で、ちょっとしたトラブル。

福岡へ帰る人々とご飯を食べて、荷物を預けたら出発時刻ぎりぎりになってしまった。遠方特権発動しといてよかった。

福岡空港に着くと荷物の受け取り台のところでclimpet(@climpet)さんと会った。ショートコーディングの話になったので、自分の提出したコードを見せると「あと4バイトは縮みます」と言われた。exit(0)の代わりにグローバル変数に0を代入することでexit statusを0にできることがあるとのこと。試してみたら本当に通った。

これ(89B)が

i,a,b;main(n){for(;~scanf("%d",&n);b+=2*a-n+1)a+=n*!~i--;exit(!puts(b>1?"Pass":"Fail"));}

こう(85B)

i,a,b;main(n){for(;~scanf("%d",&n);b+=2*a-n+1)a+=n*!~i--;a=!puts(b>1?"Pass":"Fail");}

まとめ

CODE FESTIVAL 楽しかった。運営の皆様ありがとうございました。また来年あれば参加したいです。