オンサイトで未確認

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年連続出場は厳しかったわけだけど、来年我が大学のチームはさらに力をつけるはず!

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

 

† 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 † 帰国 †

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

 

感想

や、参加記秋田

 

† ACM-ICPC 2017 国内予選 参加記 †

前置き

私は大悪魔、胡桃沢=ウクニキア=マクドウェル…。今日は我が力を世界に知らしめるための第一歩として、ICPC2017国内予選に参加してきたわ!

ちなみに結果はこんな感じよ!↓

f:id:ukuku09:20170714223109p:plain

 

…ふっふっふ、なぁーはっはっはぁー!6完で8位!どう?!これが我がチームの実力よ!予選通過はもらった!

 

今回はこの私がいかにしてこの悪魔的な結果を得たのか、愚かな人間どもにもわかるようにブログにしてやるわ!私の健闘を刮目するがいい!

(ここまでウクニキア↑)

 

 

前日譚

(ここからうく↓)

昨年のICPC国内予選では26位、惜しくも予選敗退。

この悔しさをバネに、この1年は日々精進。来るICPC2017に向けて競プロに心血を注いできました。

…というわけにはいかず、実際にはかなりダレていて、競プロ以外のことに手を出して遊んでいたら、あっという間に同輩の某甜菜においていかれ、終いにはCODE FESTIVAL予選敗退というなんとも不名誉な結果を残してしまったのでした。

 

そして新年を迎え、僕は自分の宿命を思い出し、大悪魔として覚醒。世界の支配者になるべく覇道を行く決意をしたのです。

 

3月、立命館大学での競プロ合宿を終えた後、部内でICPC2017に向けたチーム練習が始まりました。

ダレていたとはいえ、一応AOJ-ICPC埋めをちょこちょこやっていたので、首尾よく(?)†天才†の@beet_aizuくんと†怒髪先生に褒められた†@haji149さんと組めることに。

beetくんとはバンコク大会で同じチームでしたが、はじさんとは実質初めてだったので、チーム戦略をいろいろ考えながら、チーム練習に励みました。

 

5月には弊学の某チームがICPC WFに出場しました。先輩方の活躍に感化され、(また彼らが引退することで学内予選通過の敷居が下がったため、)サボり癖のある僕もちょっと精進に力を入れ始めたり。

 

そしてついに、我がチーム最強の戦略が決定!それは…

???t「うくさんは実装しないで(バグらせるため」

 

??????????

まぁわかるよ(わかるので。

 

ちなみにオンラインコンテストのレートは上がりませんでした(悲しみ。

 

チーム紹介

(ここからウクニキア↓)

大悪魔であるこの私の名を与えられた最凶最悪のチーム、UKUNICHIA…。

その主力砲台はこの1年で圧倒的成長を見せ、部内最強の座まで昇りつめたunratedの申し子、†天才†の異名を持つbeet!

その隣に並び立つは、かの怒髪先生によって鍛えられた正統な後継者、当代ICPC部部長のhaji!!

そしてそんな実力者である二人すら顎で使う暗黒の司令塔(?)がこの私、ukuku09こと胡桃沢=ウクニキア=マクドウェル!!!

この三人でICPC国内予選を通過、人間どもにさらなる恐怖と絶望を届けるため、決戦の地†つくば†へ向かうわ!

 

  • チーム名:UKUNICHIA
  • †全方位天才†:@beet_aizu
  • 考察界のプロ:@haji149
  • マスコット兼印刷係:@ukuku09

 

予選直前

(ここから流れのみ↓)

普通に1限の英語に出席。5限を消したので1限も消せばよかったなぁと後悔しつつ、なんとか乗り越えて一時帰宅。

昼頃に予選会場へ一時集合。練習セッションで1ACを出したのでもう満足。beetくんと学食へ行く。

その後は前日にライブラリの印刷を終えていたので特にやることもなく、暇だったから†やるだけ†をやり始めたら予選開始30分前までバグらせて縁起が悪かった。

 

予選本番

(若干時系列が違うかもだけど許して)

開始と同時に印刷を開始。この数ヶ月で鍛え上げられた僕の印刷スキルが光る。

はじさんがAを瞬殺する。気づいた頃には全てが終わっていた。

とりあえずC以降を読む。Cが僕にも解けそうだったのでbeetくんにあげる(?)。

代わりにBをもらう。beetなのにBを僕に投げるのかなんて思ってない。

Bが読めたのでbeetくんに説明する。わかってもらえたので嬉しかった。

一通り問題文に目を通し終える。Dをはじさんに投げて、Eは†構文解析†っぽかったのでbeetくんにとっておく。

beetくんがCとBを通す。プロ。Eをくれてやる。

はじさんがDの考察に詰まってそうだったのでふろーふろーと鳴いてみる。違うと言われる。

FとHはよくわからなかったのでGを考えることにした。beetくんにも言われたが、フローの気配を感じる。DかGのどっちかがDPでどっちかがフローだなと思う。

Gで悩んでいるとbeetくんに蟻本を見たら?とアドバイスをもらう。俺には蟻本なんて必要ねェッ!みたいな感じでスルーする(コンテスト終了後後悔する)。

Dがフローじゃない方法で解けそうらしいのでGはフローだと確信する。

Gで嘘フローを何種類か思いつく。全部嘘だから嘘だなって思った。

はじさんの解法でbeetくんがDを通す。なんか0WA4完早解きできたっぽいので予選通過できそうだねみたいな雰囲気になる。

残りの問題は全部難しそう。Gの考察っぽいことを説明したらbeetくんが何かひらめく。僕の考察はガン無視だったけど、似たようなことを言いたかったのでまぁいいか。

beetくんがGの解法を生やす。全然フローじゃないけどなんかあってそうなので任せる。そういえば1問も解いてないので0完の危機を感じ始める。

EよりFが解かれているらしいのでFを見る。意味不明。これ解けるの人間じゃないと思う。

即席折り紙で遊んでいたらGの反例が見つかったらしい。見てみると確かに反例っぽい。やっぱりフローなのかなって思って勝手にGの考察を再開。

beetくんがFをひらめいたらしいが、僕にはよくわからなかった。とりあえず実験(折り紙)が無駄になったことはわかった。

はじさんがGは右手法でいけると教えてくれる。適当に反例っぽいものをつくって聞いてみるが、うまく対処できそうなのでおーってなる。

beetくんがFを通した。もう一人でやってるよね?

とりあえず今出た話をしてみる。なんか実装できるっぽい。面倒臭いとか言いながら光の速さで実装を終えやがる。は?

サンプルが合ったらしいので提出を見守る。1個目が通る。おぉ。2個目。うぉーーーーまじか?!?!?! A C 。

Eを考えるべきとか言われたけど戦意喪失。自分の0完が確定して辛くなる。Gはフローで通したかった…。

 

終結

  • beet:BCFGの考察・解法・実装とDの考察・実装
  • haji:Aの考察・解法・実装とDの考察・解法とFの考察
  • ukuku09:>> 印 刷 と 折 り 紙 <<

 

感想

(ここからウクニキア↓)

私の勇姿はどうだったかしら?え?1問も解いてないじゃん、ですって?バカね〜、私に解ける問題はbeetくんもはじさんも解けるんだから、わざわざ私が実装する必要はないのよ!まぁ確かにチームに貢献できなかったのは悔しいけど、そもそも国内予選ごとき私が手を下すまでもないわ。Gはフローでも解けるっぽいことを聞いたから、ちょっと考えてみるわね。とりあえず予選は通過したみたいだし、アジア地区で私の本領発揮ってところかしら?人間どもぉ、私の力にひれ伏すその日までせいぜい悪足掻きでもすることね!

 

AOJ 2370: RabbitWalking

久しぶりにブログを書くわ!自分用メモだけど。

 

問題概要

RabbitWalking | Aizu Online Judge

 

解法

まず"-1"の判定ですが、グラフが奇閉路を含まないことと二部グラフであることは必要十分条件なので、与えられたグラフの各連結成分が二部グラフであるかどうか判定します。もし二部グラフでない連結成分が一つでもあったら"-1"です。

二部グラフ判定はUnionFindやDFSを使って判定できますが、今回は後から各連結成分の各色(ここでは黒と白とします)の個数を利用したいので、DFSで2彩色しながら個数を数えるのが良いと思います。

(後述しますが、正確には各色の個数というより、二部グラフを構成する2つの頂点集合の大きさが必要になります)

 

もしすべての連結成分が二部グラフである場合、辺を0本以上追加して二部グラフを保ったまま各連結成分を連結することができます。

課題から、辺の追加本数を最大化したいので、各連結成分は完全二部グラフにしてしまって良いことが考察できます。さらに、各連結成分を連結してできる二部グラフもまた完全二部グラフにできます。

完全二部グラフの辺の本数は(黒の個数)*(白の個数)なので、結局(各連結成分の黒の個数の和)*(各連結成分の白の和)を最大化すると良さそうです。

 

先ほど各連結成分ごとに適当に2彩色しましたが、連結成分内ですべての頂点の色を反転させても2彩色状態は保たれるので、二部グラフの2つの頂点集合の大きさのみに注目します。

今、いくつかの連結成分を連結してできた完全二部グラフ$K_{n_i,m_i}$と、まだ連結していない連結成分$K_{a_j,b_j}$を連結すると、新たな完全二部グラフとして、$K_{n_i+a_j,m_i+b_j}$または$K_{n_i+b_j,m_i+a_j}$を得ることができます。このようにして得られる完全二部グラフ$K_{n_k,m_k}$における$n_k*m_k$の最大値が求めるべき解です。(あとで元からある辺の数$E$を引きます)

(2つの頂点集合$V_1,V_2$の大きさをそれぞれ$x,y$とする完全二部グラフを$K_{x,y}$と表記しています)

 

これを解くために次のようなDPを考えてみます。

$dp[i][j][k]:=i$番目までの連結成分を用いて$K_{j,k}$を作ることができるか

これを計算すると、$dp[V][j][k]==true$を満たす$j,k$の積の最大値が解となります。

さらに、$k$の最適値は$i$と$j$がわかれば一意に定まるので、$dp[i][j]$としてしまっても良さそうです。しかし、このDPでは計算量が$O(V^2)$になってしまうので当然間に合いません。

 

計算量を落とすためのアイデアとして、各連結成分$K_{a_j,b_j}$における2つの頂点集合の大きさの差分$abs(a_j-b_j)$($c_j$とします)と、$Σmin(a_j,b_j)$($L$とします)を考えます。すべての連結成分を用いてできる完全二部グラフは、どちらの頂点集合の大きさも必ず$L$以上になっているはずです。また、完全二部グラフの$V_1$の大きさの増分はいくつかの$c_j$の和$sum$として表すことができます。全体の頂点数は$V$なので、この完全二部グラフは$K_{L+sum,V-L-sum}$となります。($a_j>b_j$なら、$n_k$に$a_j$を足して$m_k$に$b_j$を足すのは、$n_k$に$b_j+c_j$を足して$m_k$に$b_j$を足すと見なせます)

(補足ですが、求めるべき完全二部グラフは必ずすべての頂点を含んでいます。これは、完全二部グラフの2つの頂点集合の大きさが連結に伴って単調増加するためです)

 

したがって、先のDPは次のように書き直すことができます。

$dp[i][j]:=i$番目までの差分を用いて$j$を作ることができるか

さらに、$c_j$の種類数は$O(√V)$程度に収まるので、個数制限付き部分和問題(詳しくは蟻本P62参照)と見なして$O(V√V)$で解くことができます。

 

gist85ccc57cc00c88617e78bccfb8de48fc

 

すごく冗長、しかも変数や添字が最高にわかりづらいわ…。はぁ〜、なんて悪魔的なのかしらぁ〜!

 

RUPC2017参加記

  • 前置き
  • Day 0: 移動フェーズ
  • Day 1: 立命館セット
  • Day 1.5: 懇親会 & 準備
  • Day 2: 会津セット
  •  Day 2.5: 懇親会
  • Day 3: 北大セット
  • 感想
  • ※お詫び
続きを読む

AtCoder Beginner Contest 007 D: 禁止された数字

問題文

abc007.contest.atcoder.jp

解法

桁DPしてくださいという問題。桁DPがわからない人は pekempey さんの記事がとてつもなくわかりやすいのでそちらを見てください。

pekempey.hatenablog.com

 

AtCoder Beginner Contest 008 D: 金塊ゲーム

問題文

abc008.contest.atcoder.jp

解法

問題文が無駄に長くてわかりづらいが、よくあるやつだと思った。

ある装置を起動させると、その装置を基準に領域が最大4つ(左上・左下・右上・右下)に分割されるので、そのそれぞれについて再帰的に調べていけば良い。