オンサイトで未確認

ukuku09の活動記録。

† The 2017 ACM-ICPC Asia Daejeon Regional Conetst 参戦記 †

Abstract

くっくっく、なぁ〜はっはっはっはぁ〜!!!人間どもよ、己が支配者の前にひれ伏しなさい!そう!この私こそが、いずれ世界を掌握する唯一無二にして絶対の王、胡桃沢=ウクニキア=マクドウェルよ!

今宵この私が自ら筆をとったのは他でもない……。無知で愚かなお前たちのために、ここに我が偉業を記そうと思ったの!感謝しなさい!

 

私に忠誠を誓ったお前たちなら当然知っていると思うけど、11/10〜11/11に開催されたICPC Daejeon(韓国)大会に参加してきたわ!7月の国内予選で日本を手中に収めたわけだけど、この世界の全てを掌握するためには他の国でも我が力を振るう必要があったのよ。

 

ちなみに結果は全体24th、大学別12thよ!!

 

……ビミョウって言うな!!ふ、フン、まぁいい。そう言ってられるのも今のうち……この記録を読めば、どんなに愚かな人間であろうと、私の†悪魔的活躍†に恐怖することになるわ……。

 

ちゃんと最後まで読みなさいよ!わかった?!

(ここまでウクニキア)

 

 

Day 0 † 出国 †

いろいろありすぎて面倒くさくなったので箇条書き

  • 目が覚めたら服が乾いてなかった
  • 駅まで全力疾走(10秒ぐらいで息切れしたが)
  • 学割を忘れる
  • うさぎがいない…うさぎがいない…うさぎがいない!!(駅前の本屋)
  • 車内で働く
  • うさぎがいない…うさぎがいない…うさぎがいない!!(空港の本屋)
  • 機内でアニソンを聴く
  • beetくん(JS)と同じ部屋に泊まる
  • beetくん(JS)の肌色が

Day 1 † Practice †

Before Practice

日本の高速バスはクソ。あと韓国のタクシー乗り場で待ち行列FIFOは機能しない。

学食で†本場の石焼ビビンバ†を食べた。

 

Practice Session

特に開始の合図もなく、雰囲気でスタート。

マスコットの私に唯一割り当てられた、キーボード持ち込み兼接続係という仕事を見事に果たし、あとはシモベの二人に任せて右端の椅子を温めることに専念。

しようと思ったが、どうやら問題文も読む必要があるらしい。全く、人間とは困ったものだ。

PracticeはA,B,Cの3問。問題を見た私「ん?これ全部知ってるぞ」、勝利を確信(ア。

とりあえずhajiさんが設定ファイルを書いている間に、beetくんと問題を共有。

beetくんにAを投げ、私は”解いたことのある”Bを担当することに。

古の時代の記憶を呼び覚まし、大量のWAと引き換えに、微調整を繰り返してACした気がしてくる。

設定ファイルを書き終えたhajiさんに代わり、beetくんがAを実装。

その間にhajiさんと問題を共有。「これ去年のDaejeonだよね?」

ばちゃでCをhajiさんが通していたので、Cはhajiさんに。私はBの紙実装に入る。

beetくんがAをACするが、紙実装は終わってない。

私が紙実装している間に、beetくんが実験を始める。前もって列挙しておいた項目を順番に調べ、だいたい問題ないことを確認する。

紙実装が終わり、実験のキリの良いところでPCをもらう。右端の椅子とはさようなら。

紙実装しておいたコードに沿ってキーボードを叩く。マイキーボードは最&高。

実装が終わり、サンプルを試したところ、合わない。キレそう。すぐに不足しているパートに気づき、再度考察(という名の想起)。

「実装で殴った気はするけど全然思い出せん…」Cの進捗が気になったのでbeetくんとhajiさんに方針を聞き、「ばちゃの時はそれで通った気がする」

CがWAになる。ところで私は何故か中央に来てしまい、beetくんとhajiさんが私を挟んでCを考察する中、一人黙々とBを考える。

この辺りで愚直な実装でBは解けない気がしてくる。同じ高さが複数あった時、マッチングを考える必要があるのでは?と一瞬思ったが、そんなことをした記憶がなかったので、愚直を頑張って考える(ァ……。

私がBでinf時間消費している間に、二人はCの方針が生えてはWAを出していた。

どうやらばちゃの時はジャッジデータが弱かったらしい。

二人がPCを使っていないタイミングを見計らって、愚直実装でサンプルを合わせにいく。が、実装で詰まってしまい、beetくんに怒られる。

たぶんこの辺りでPracticeが終了した。

反省点は多かったが、明日に活かそうとポジティブシンキング。

……Practice後、hajiさんが「BってWFの問題じゃない?フローのやつ」と言ってきて、なぜ今更言ったし…みたいな気持ちになった。

京大チームがBを通していたので、解法を確認しにいったところ、やはり二部マッチングの問題だったことが判明。

てか私解いたことないじゃん。何が「この問題、ばちゃでやったやつだ!!」だよ。やってないよ。

 

After Practice

京大チームと†本場の焼肉†を食べた。

 

Day 2 † Contest †

Before Contest

 忘れた。No airconditioning.

Contest

流れを忘れたので捏造した。

こどふぉった。

昨日と同様、私は右端の椅子に座る。今日は絶対に離れないぞ!と意気込んでいたが、キーボード接続係だったので開始早々離れてしまった。

光の速さでキーボードをUSBメスに差し込み、急いで右端の椅子に戻る。

戻ってくるとbeetくんから後半の問題を渡される。仕方がないので読む。私が1問読み終えるまでにbeetくんは5問くらい読んでた気がする。

beetくんがすぐに解けそうな問題をいくつか見つけたらしいので、hajiさんと交代する形で実装に入る。

hajiさんが右端に座りたがったので、泣く泣く中央に移動。右端の椅子に座るためなら、大悪魔にすら立ち向かってくる雄姿を讃えたのだ。

hajiさんと問題を共有していると、CがDAGの最長経路で解けそうなことがわかってきたので、あとでbeetくんに投げることにする。

†悪魔的直感(デビルズ・センス)†で、(制約を見ずに)Hが簡単そうだと言ったが、制約を見たbeetくん「やるだけではないです」(HはFFTだった。

beetくんが問題を通して(?)帰ってきたので、問題を共有する。やっぱりCが解けそうだったので任せる(てか共有とかじゃなくて勝手に持っていった気がする)。

hajiさんが「LがDijkstraできるのでは?」と言うので、少し話を聞く。そういえばLの問題概要を忘れたので、beetくんと相談してもらうことにした。

ここから1時間以上Eに時間を使う。その間のチームメイトの動向も把握せず、ひたすらEを考える。(そしてContest後に解法を聞いて自分の頭のNASAに絶望することになる。)

最初は、「G'上の最小全域木に必ず含めたい1辺eを決めたあとは、それ以外の辺で二つの最小全域木を作って最後にeで二つの木をつなぐ」みたいな考察をhajiさんとした。

しかしここで昨日の反省が活きる。サンプルを手で試してみると、どうやら最小全域木アルゴリズムではうまくいかないことがあるらしい。

いろいろな作り方を手で試してみたが、なかなかうまくいかない。

ここで驚くべきことが起こる。なんと順位表が開始2時間ほどで凍結してしまったのだ。どうやら1位のチームが†全完†する前に凍結したようだ。

私がEの沼にのめり込んでいると、beetくんから「解ける目処が立ちそうなんですか?」と言われる。あっあっ、ちょっと厳しいです……Aに戦略的撤退(逃げてないよ)。

順位表は凍結してしまったが、風船は一応配られていたので、順位表の提出と風船の色からどの問題がいいかは推測できた。

そしてこの段階では、Aはそんなに提出されてなかった。それなのになぜAに行ってしまったのか……。

Aを見た瞬間、木の分割統治だと思った。木の分割統治はあまり解いたことがなかったが、「こういうのを解ける形に持っていければシモベたちの私に対する忠誠心が一層強まるのでは?」

なんとか†全方位木DP†とかで解けないかなぁと考察を始める。←なぜ捨てないんですか?

EやAの考察の合間にちょいちょいデバッグを頼まれるが、マスコットなのでコードを眺めるだけ眺めて何もしない(†悪魔的行為†)。

残り1時間半、Aを木DPでやるのは厳しいことがようやくわかってくる。一応二人にアイデアを出してみたが、やはり無理だという判断を受ける。

1時間ぶりにEに戻ってみると、辺eを含むサイクルの数が答えになる気がしてくる。ただそのサイクルというのが難しくて、極小(?)かつ辺eのコストよりも小さい辺から構成されるサイクルを数える必要がありそうだ。

そのようなサイクルの数の数え上げに、なんとなくlowlinkが使えるのではないかと思い始める。ここで私の†悪魔的発言(デビルズ・ライ)†が発動。大嘘な考察をhajiさんにする。

が、自分でダメなことに気づく。さすが優秀な大悪魔である。

その後もサイクルという考え方に取り憑かれ、うーんうーんと頭を捻ってはみるものの、思いつかず、最後は諦めてHのデバッグの手伝いに入るものの、そこでContest終了。

…………どう?!最高に悪魔的な活躍でしょう!?(涙目)

ちなみにEは最小カット。それはそうすぎる。

After Contest

 ARCに参加した。Dでやらかした。Eが解けなかったので解説を見たらフローだった。フロー一生解けない。もう”フロー”っていう文字列も見たくない。

Day 3 † 帰国 †

 寝てたら機内食食べ損ねた。

 

感想

や、参加記秋田