オンサイトで未確認

ukuku09の活動記録。

† The 2017 ACM-ICPC Asia Tsukuba Regional Contest 参加記 †

くっくっく、なぁーはっはっはぁー!私はいずれ世界を統べる大悪魔、胡桃沢=ウクニキア=マクドウェル!!

12月16〜17日に開催された、ICPCつくば大会2017を掌握してきたわ!

 

f:id:ukuku09:20171219135629p:plain

 

……微妙じゃないし!!

フン、確かに†優勝†は逃したけど、当然今回も下等生物どもに恐怖を植え付けてきてやったわ!なっはっはー!

 

これは我が人間界掌握計画の序章に過ぎない…。しかし愚かな人間どもに私の力を再度知らしめるにはうってつけの舞台だったわ。あの場にいなかった人間どももこの記事を読んで、自分が忠誠を誓うべき相手が誰なのかを正しく理解することね!

 

ちなみに私の予選での活躍を書いた記事はこれ↓

ukuku09.hatenablog.com

Day 0

Kirara Session

前日にきららファンタジアをダウンロード&インストールしたので、バイト先から帰ってきてから日が変わるまでずっとやってた。

Day 1

Traveling

移動中はずっとTwitterしてた。

 

私が行くことを認知してない人間がちょいちょいいてキレた。

チームメイトすら把握してないってどういうことよ?!

https://twitter.com/ei1333/status/941842907912273920

https://twitter.com/ei1333/status/941842907912273920

https://twitter.com/ei1333/status/941842907912273920

Registration

なんで日本なのに英語で会話しなきゃいけないのよぉー!

 

レジ後はそのままコンテスト会場へ。

テーブルは隣がfour-tで正面(?)がlamaltettaだった。

とりあえず持ってきた『競技プログラマー情』を見せびらかして牽制しておく。

 ↑これははじ

 

beetくんがTシャツを裏表逆に着ていてうしさんをリスペクトしているのが窺えた(?)。

 

喉が渇いたのでbeetくんとSnack Areaへ行ったら「Wait a moment.」と言われ、泣く泣くテーブルへ戻る。

 

暇だったのでうしさんに会いに行く。

furu-tuメンバーは全員私と同じ高校出身なので、話が弾んだ。

 

他のチームが普通にSnack Areaで飲み食いしていたので???私もSnack Areaへ。

会津合宿でもおなじみのKlabのエナドリが置いてありおっ、となった。

Opening Ceremony & Practice Session

Opening Ceremonyも英語だったので正直何を言ってるのかよくわからなかった。

 

ぼーっとしてたら突然カウントダウンが始まり???ってなりながらPractice開始。

 

問題文が3部あって神って感じ。A,B,Cの全てに目を通す。どうせCは不可能と思いながら読んだら不可能っぽかったのでbeetくんに説明。

「えーCは不可能で、n個のスイッチがあってその全てが一つのライトのオンオフを切り替えます。スイッチの状態はAとBがあって、最初スイッチは全てAでライトはオフでした。今のスイッチの状態からライトがオンかオフか答えてください…これただの偶奇では」

「はいそうですね」

Bで†数学者†のbeetくんが2次方程式の解の公式を間違えていて面白かった。

遅めの全完。まぁ設定ファイルとか書いていたのでそれはそう。

 

はじさんやbeetくんがキーボードが固くて筋肉痛になりそうだと言うので、私もキーボードを触らせてもらうことに。明日は絶対触れないからね。(※予選参加記参照)

「何か書いてほしいですか?」と募ったところ、はじさんが「じゃあフロー、Dinicで」と言うので、書き始める。

struct edgeの中身を書き終えたところで、

「ところでこんなことしてる暇あるんですか?」

「ないです」

とbeetくんに即答されたので終了。

 

Practiceでやるべきことは問題を解くことではない。Daejeon大会と同様のチェックをbeetくんが順番にこなしていく。

その間私は暇だったので『競技プログラマー情』を読んで明日のコンテストに向けて意識を高めつつ周囲のチームを威圧する。これも立派なマスコットの仕事である。

 

配布されたドキュメントを見たところ、お花を摘みに行く際はスタッフに声をかけなければいけないらしい。コンテスト中のお花摘みは大悪魔にとって重要なイベントである。当然練習しておくべきだと思った。

キョロキョロ周りを見渡すと、見慣れた顔を見つけた。競プロerの魂の教科書『競技プログラマー情』の作者にしてICPC WF2年連続出場を果たしたヅ大の異端児、パブリックアンダーバーサテさんだ。

私はさてさんを呼びつけこう言った。

「きゃないごーとぅーれすとるーむ?」

さてさんは「Ah, Yes.」と言った後に色々言っていたが、私はお花摘みへ行く前の声かけの練習が成功した達成感に満たされていてあまり聞いていなかった。

 

***お花摘み***

 

戻ってくるとbeetくんが「ト●レは自由に言っていいらしいよ」と言っていた。は?勝手に行くなって書いてあるやが。あとト●レじゃなくてお花摘みだし!

もう一度さてさんを呼びつけて確認してみたところ、今日は自由に行ってOKということらしい。なるほど。しかしさっきの言葉を信じて明日うっかり黙ってト●レお花摘みに行ってしまったら危険だった。確認しておいてよかった。

 

だいたいやり終えてだらだらしていたらPractice終了。ライブラリも持ち帰る(チェックしない)ことに困惑する。

Before Welcome Party

Stay hereじゃあないんだよ。

Welcome Partyの会場まではバスでの移動だったため、一度に入りきらない分はコンテスト会場で待機。明日の戦略の見直しなど話しながら時間を潰す。

 

移動用のバスは2台あったが、ほとんどのチームが1台目のバスに詰め込まれた。

Welcome Party

食べ物が茶色かった。

 

beetくんと適当に彷徨っているとうしさんとらてさんを発見したので声をかけた。

 

高校時代の†戦友†のチームメイトのarukukaさんからなぜか芋焼酎をもらう。どうやら私の約500いるシモベの一人で、私への忠義を示すべく買ってきてくれたようだった。

 

チーム紹介フェーズに突入し、各チームが順番に前で30秒くらいスピーチした。

私は直前まで、我がチームで唯一英語の話せるbeetくんがスピーチを行うものだとばかり思っていたが、多くのシモベたちからの要望と期待もあって私がやることになった。

うっかり自分の真名をど忘れする事故があったがなんとか乗り切る。さすが私よね〜♪

AtCoder Regular Contest 087

出た。Dで適当に実装したら通ったので2完。

 

beetくんが橙コーダーになったので、チーム平均黄になったのでは???と思ったが、私のレートが低すぎてそんなことはなかった。

Day 2

Check-in

椅子が一つ減っていた。

これじゃ横になれないね、と話していたら「らてさんは空気椅子でもいいのでは?」とbeetくんが言うので、lamaltettaから椅子を一つ奪ってくる。

が、すぐにらてさんに持って行かれてしまった。赤コーダーの心は狭い。

 

暇を持て余しながらテーブルに突っ伏して開始を待った。

いよいよ本番、がんばるぞい!

Contest

開始と同時にはじさんが設定ファイルを書き始め、その裏でbeetくんと問題文を読む。

Kが短くておっとなったが、G、I、Jが3ページで嫌になった。しかしよく読めばサンプルの説明を丁寧に書いてくれていて、Tsukubaサイコー、一番好きなRegionです。と思った。

beetくんがAとBを書いている間にとりあえずF〜Kまで目を通す。個人的にはFが一番とっつきやすそうだ。

beetくんはCが読めなかったらしいのでDを読み終えたはじさんと一緒にCの解読を始める。確かに読みにくい。

サンプル1を手で試してようやく問題概要を把握し、はじさんと共有する。はじさんに「サンプル2の意味がわからなくない?」と言われ「たし蟹…」と二人で頭を抱える。


大悪魔はコンテスト中頻繁にお花摘みに行くことで有名なので、当然Cを考えながらお花畑へ。もちろんスタッフに声をかけることも忘れない。

「きゃないごーとぅーれすとるーむ?」

 

***お花摘み***

 

お花を摘んできた私は再びCのサンプル2と対峙した。

「…これただ複数人待ってるだけでは?」

私の発言と同時にbeetくんが「甜菜!」と叫んだ。突然自分の品種を叫ぶシモベを心配しかけたが、今になって思えば私に「天才!」と言ったのかもしれない。

とりあえずはじさんにも共有する。beetくんが解けそうな雰囲気を醸し出してきたので、Cはまかせてはじさんと他の問題を共有する。二人でEを考えてみるがよくわからん。

 

***お花摘み***

 

周りを見ると白っぽい風船が上がっていた。どうやらABCの次はIらしい。だがあえてIはやらない。赤い風船がちらほら目についた私はIの考察をはじさんに投げてFを考える。

Fみたいなやつはだいたい最初にdijkstraで求めた情報から答えを求められるものなので、その方針で考えてみる。


***お花摘み***


サンプルお絵描きをしていると解けそうな気持ちになったので、Snack Areaで喉を潤してからbeetくんに伝えるタイミングを待つ。

いつの間にかCを通してIを考えてたが、そんなに捗ってはなさそうだったので、後ろから声をかけて実装方法などは一切考えていない考察をぶつけてみる。

はじさんが写経している間に整理してbeetくんが実装に入る。私の考察を聞いただけで実装方法までわかるなんて、もしかして私の説明上手すぎ?

 

早々に実装を終えサンプルがあったところで提出。

PENDINGが長いので、私がジャッジを眺めている間もbeetくんははじさんとIの考察。

結果を見守る私の目に憎らしい赤い文字列が映る。WA。すぐに印刷して全員でデバッグにかかる。

ここで私の†悪魔的慧眼(デビルズ・アイ)†が光る。グラフの作り方が間違っていることを少しのサンプルを添えて教えてあげる。

コードを修正して提出。WA。なんでや!もしかしてこの私の考察が間違ってる?そんなバカな!とか考えていると、デバッグのプロのはじさんが「そうそうさん」と言った。どうやらデバッグ用に書き換えていた"SOSO3"がそのままになっていたらしい。

三度目の提出でようやくAC。辛そう。

 

***お花摘み***


beetくんとはじさんがIに戻ったので、私はいつも通り一人孤独に不可能に手をつける。別に寂しくない。

Kが変な制約で、bitでほいするんだろうなぁとか思ったけどそれ以上は進まず。制約がフローのHに切り替える。

いろいろグラフを書いてみるが、どちらかの課題のみある時、maxではやってminではやらないので、そもそも貪欲とかdpでいいんじゃないかという気持ちになる。それでいいなら他のチームが解いてそう。

だが、周りを見渡しても緑の風船は全然ない。Hは捨てるべきと判断してIに合流する。別に寂しかったわけではない。

考察を聞いてふむふむする。考察に嘘っぽいところがあったので反例になりそうなケースを考えてみる。反例っぽいのができたとりあえずはじさんに見せる。はじさんがbeetくんに話す。しゅーーりょーー。解けません。

beetくんがGが解けそうみたいなことを言い出して離脱。二人でIをちょっと考えていると、はじさんが本当っぽいことを言う。本当っぽいのでbeetくんに伝える。

policy-1はある区間と重なる区間の数のmax+1になりそう。でもどうやってその数を求めるのかがわからない。そこでbeetくんが「セグ木セグ木」と鳴く。

range countでいけるというが、AC数を見るにもっと楽な方法があるのでは?とはじさんと考えるが思いつかず。時間がもったいないのではじさんがセグ木写経に入る。終わる。

swap(はじ,beet)。range count持ってくるの忘れたーとか言いながらダカダカキーボードを叩き書き上げる。

私が途中†悪魔的妨害(デビルズ・わからんどうやってるの)†をしたが一発ACでいえい。

 

***お花摘み***


「座標変換に使うのでこれの逆行列求めてください」

逆行列さんね、なるほど。古の時代の記憶を呼び起こすと、確か拡大行列を作ってえいえいびーと。ちなみにこれは解説の時に発覚するんですが、実はちょっとだけ間違えてました。使わなくてよかったね。

 

***お花摘み***

 

残り1時間、さすがにあと2問はキツイだろうと思い、Eは捨ててGの解法を共有し、3人で方針を固めていく(というのは嘘で、私はお絵描きしてただけ)。

いろいろ考えているうちにbeetくんが実装を終えてサンプルが合った。提出。PENDINGが長い。私は「通れ〜通れ〜」と後ろから念を送る。

が、その甲斐も虚しく表示された文字列はWRONG ANSWER。印刷されたコードを読み解きながら、おかしなところがないかを探す。

beetくんとはじさんがミスに気づいたらしく、修正して提出。WA。やっぱり合っていたのでは?みたいな話になって戻す。提出したコードが見れないのはクソだと思った。

 

***お花摘み***

 

残り30分を切りbeetくんが怪しいところにassertをかけて提出する。REはせずにWA。

私はもうダメか…と思い始めるも、beetくんは諦めずにひたすらローカルでassertをかけまくる。そしてなぜかassertに引っかかる箇所を見つける。
「は?なんでここ引っかかるんだよ(ブチギレ」

しかしその甲斐あって原因を特定し、修正。カウントダウンが始まる。私が見守る中、beetくんが震える手で提出にかかる。

 

 

「「「最終提出(ファイナル・サブミット)!!!」」」

 

 

PENDING…PENDING…PENDING…

ありったけの念を送り続ける。

PENDING…PENDING…PENDING…

遅い!早く返ってきなさいよー!!

PENDING…PENDING…CORRECT

「はぁ〜〜〜?クソじゃん!!」

会場中に響き渡ったその言葉を発したのが誰だったか、もはや覚えていない。

間も無くしてコンテストが終了。お疲れさまでした。

Commentaries on Problems

解説の前にいろいろあったんですが、

Fの想定解が橋を使った解法っぽくて意外だった。

F,Gの次はEのAC数が多かったが、DP高速化問題だったので私には解けなそう。

 Hはやっぱりフロー。でもグラフがやばくて無理って感じだった。

あとでbeetくんに「うくさんにはHみたいな問題を解いてほしいんですよ」と言われてんんん???となった。マスコットに重労働を強いるのは†悪魔的行為†!

Award and Closing Ceremony 

生YES/NOおじさんだ!!!

凍結時5完+αのチームが割とあって、結構ドキドキした。

Twitterを見る感じnishiyon NO DANPENには負けたんじゃないか、と言う話をbeetくんとしながら順位確定を待つ。

YES...NO...YES...NO...

そしてUKUNICHIAのターン。

 読み方を間違えられた気がしたけど気にしない。

Gの結果はもちろんYES、あとはどこまで上がるかだが…。

「ん、勝った。nishiyon NO DANPENに勝った」

らしい。やったぜ。

 PrimeDragonにはさすがにペナルティで負けた。私はキーボードに触ってないので、実装ミスでのWAに文句は言えない。あと1問解法を生やしたかったわね…。

Closing Party

さっそくdwangoのWA投げ。6回投げて1つも入らないと言う珍事を成し遂げてしまう。

あれはおそらく天使の妨害があった。仕方がないのではじさんの得たテレビちゃんを1つ奪う。

 

企業ブースでもらうものだけもらって話を聞いたりはしない†悪魔的行為†。IBMが無料でTシャツをくれてすごかった。ボールペンが無限に増える。

 

他のオンサイトで特定した人間どもがコネクションハントをやっていたので書いてあげた。

「尊敬する人は?」

「私!」

「好きなチーム名は?」

「UKUNICHIA!」

「チームでの役割は?」

「 マ ス コ ッ ト 」

 

私もindeedのTシャツが欲しかったので、ありがとう祭りぶりにコネクションハントをする。各チームにつき一人にしか答えてもらえないという制約があったものの、その穴を突いて(†不正†)20人分を集め、無事TシャツをGETする。

 

その間に、2回呼び出され企業賞を得る。823(はやぶさ)賞と82(ヤフー)賞らしい。8位はコスパが良い(?)

After Welcome Party

ホテルで怒髪さんの持ってきたゲームをbeetくん以外でやった。成績優秀者は早寝早起きで有名。

と思ったらbeetくんが起きていたので、明日ごちうさガルパン見に行こうぜと話をする。しかし時間と空間的に片方しか見れなそうだったのでごちうさにする。

Day 3

諸々の電車の遅延でごちうさを見れなくなる。仕方がないのでbeetくんと秋葉原ヨドバシカメラエスカレーターを上り下りしたりラーメンを食べたりして帰った。

 道中参加記(これ)を書くも終わらなかったので、私のつくば大会は翌日まで続く。

感想

ククク…どう?私の力を思い知ったかしら?……へ?全部beetくんの力では?ですって?

わかってないわね〜。beetくんは私のシモベ。シモベの力は私の力、私の力は私の力なのよ!!

でも今年はこれくらいで勘弁してあげる。ヅ大からWorld Final3年連続出場は厳しかったわけだけど、来年我が大学のチームはさらに力をつけるはず!

そして次は私の今はまだ封印されし力をもって、全員私の前にひれ伏せさせてあげるわ!!