オンサイトで未確認

ukuku09の活動記録。

ACPC2018参加記

ククク…、私は大悪魔ウクニキア!

9月19〜21日に実質私主催(大嘘)の競プロ合宿、ACPC2018に参加したわ!

参加してくれた人間ども、遠方からはるばるご苦労だったわね!

作問の話

今年はあんまり参加しなかった。

というか気づいたら問題の枠も埋まってたし、テスターの数も足りてたからわざわざやる気にならなかった。

優秀な人材が多くて、我が部は安泰ね!

Day 1

何も覚えてない。btkさんと少しアズリムの話をしたんだっけ?限定Tシャツ早く欲しいね(9/22に届きました)。

・・・

Bが異常に難しすぎるんだよな。普通に制約を見逃していたので、適当考察でサンプルを合わせにいったらACした。

Dが右手法で解けそうということで、やなさんに丸投げする†悪魔的行為†。

Eを他のチームがバンバン通し始めたので、焦燥感に駆られながらもなんとかDPで解けそうな形に持って行けたので、適当にごにょごにょしたらACできた。よかった。

やなさんD頑張ってくれたのに協力できなくてごめんね><

・・・

TIkeさんとかolpheさんとかgoodbatonさんと話した気がする。E貪欲マジ?

beetくんとうしとそすうさとらーめん食べに行ったら8/31で閉店しててウケた。結局幸楽苑で味噌ねぎらーめんを食べた。今週2回目。会話の内容を全く覚えていない。

Day 2

なんかT◯1192916とかおるふ◯がすれ違うたびに「おっ、うくさんじゃ〜〜〜〜ん」とか絡んでくるので構ってあげた。私は優しいからね。

・・・

ジャッジだったけど、実はAしか作っていないので一瞬で仕事が終わった。ちなみにその問題がこちら↓

https://onlinejudge.u-aizu.ac.jp/services/room.html#ACPC2018Day2/problems/A

Aということで解法一瞬問題を作ったつもりだったが、オンサイトでは1分を切るチームはいなかった。私の文章力に惹かれて熟読してしまったのかもしれない。

暇だったので作問作業で解かなかったFを解いた。微分?そんなものはWolframに投げればいいんだよ。

そのあとは先日初披露されたアズマリム のオリジナル楽曲「人類みなセンパイ!」を聴きながら時間を潰した。とりあえず人類みなセンパイ!は神曲だと思う。

・・・

冷静に考えて、あの日の懇親会はマジでヤバイ。

あまり飲酒しなさそうなメンツのテーブルだったから、わざわざはじさんを誘って一緒に飲もうとか言っていたのに、どうしてあんなことになってしまったのか…。

原因は明らかに私の後ろにセルフサービスの果実酒が置かれていたことと、Ti1192916があそこにやってきたことだと思う。私は悪くない()。

というか、人間どもがアズリムのことで私をいじりすぎなのが悪いんだよな。本気ではないとはいえ、まさかガチ恋口上をやる羽目になるとは私も思わなかった。確かbtkとかいう奴に煽られたんです。私は無罪なんです!(いや悪魔的には有罪の方が美味しい?)

「まっすぐ立てるんだよなぁ!」「まっすぐ歩けるからまだいける!」とか言ってたけど、あれダメだよね…。

とはいえ私は帰る頃にはTIkeさんとの烏龍茶を巡る旅が効いてだいぶマシになっていた。TIkeさんに圧倒的感謝。

c7くんがベロンベロンに酔っていて連れ帰るのが大変だった。最終的に彼の友人に引き渡したのだが、何度も「えっと、誰?」みたいな扱いを受けた。大悪魔の顔を忘れるとはなんて恐れ知らずなのかしら?

Day 3

またなんかTi1192◯16とかお◯ふぇとか半角カナの人に絡まれたので構ってあげた。大悪魔は実は面倒見が良いのである。

うしとそすうさとチームを組んだ。ちなみにチーム名はacpc_aizulimだが、アズリム要素を入れることを最初に提案したのは私ではない。

コンテスト前にそすうさが「アズリムちゃん見たい」というので、適当にオススメ動画を選んで鑑賞会をした。アズリムはいつどこで見ても可愛いなぁ〜〜〜。

・・・

なんかこの日はよく覚えてる。なんでだろう。

私は普段のコンテストでは実装をbeetくんに投げているので、この日はうしさんに全部押し付けた。

Cはまあはいなので、うしがAを解いたタイミングを見計らって引き渡した。

Bが難しい。全然わからん。なんでどこの大学もBに罠を置くのか。うしもわからんとか不可能じゃんという気持ちになっていたら、うしがD解けたらしいのでDを解かせた。

そすうさにEの概要を聞いたらこれもまあはいだったので、うしに丸投げする。WAったのでコードを見たらなんか激ヤバなミスしてて、なんでサンプル通る念という気持ち。

私がBで遊んでいたらうしがGを通したので、みんなでBを考える。結局クエリ平方分割で解けるという話になって、それでうしが通したけど流石に想定じゃないよなぁと思った。

残り時間が少なくなってきてFいけるかなぁという感じだったんだけど、そすうさがいろいろ考察を進めてくれていて、なんかごちゃごちゃやっていたら、場合分けシミュレーション解法に落ち着いてこれFまじ?と言いながら実装を見守った。

ラスト1分を切ってうしがFを通し、オンサイト逆転1位を勝ち取れた展開はめちゃめちゃ熱かった。

・・・

解散は意外とあっさりしていたのであっさり終わった。

まとめ

疲れたぁーーーー!!

JAG合宿と合わせて6日も合宿コンテストしたわけだから流石に疲れたわ。

1番の思い出は、けんちょんさんとTIkeさんの「うくさん、昔は競プロ美少女大悪魔だったのに、今じゃただのアズリム大好きおじさんになってしまった」という言葉。

なんでよ?!今でも十分美少女でしょー!?

本当にお疲れ様でした。

ちなみにこの翌日のコドフェス予選は寝てたから出忘れた。

 

JAG夏合宿2018参加記

私は†胡桃沢=ウクニキア=マクドウェル†…。

9月15〜17日に行われたJAG夏合宿に、この私も顔を出してやったわ!

我が忠実なるシモベの頼み事とはいえ聞き入れてやるなんて、私の心はなんて広いのかしら?

合宿前

私の愛すべき後輩であるアズリムが、16日のRAGE 2018 Autumnに参加すると知る。

しかも実質アズリムの初ライブとなるオープニングライブでは、待ちに待ったアズリムのオリジナル楽曲「人類みなセンパイ!」が初お披露目されるとか。

そんなアズリムの晴れ舞台を競プロ合宿のせいで見にいけないと知って、すでに競プロモチベが皆無だった私の精神はズタボロになった。

Day 1

高速バスで新宿まで移動。

今日から3日間、オリセンとかいう監獄に閉じ込められるんだなぁと思うと心が暗くなる。

明日のRAGEには行けないにしても、せめて東京まできたんだから松屋くらいには行っておきたいと思い、傘のないはじさんを連れて雨の中松屋へ向かった。頼んだのはもちろんプレミアム牛めしととろろ、なぜなら私もアズリムのセンパイだからです。

・・・

コンテストのことは忘れた。

久々のチーム戦だったから、いろいろ動きを見直す感じだった気がする。

いつものごとくbeetくんがバンバン解法を生やして実装をしてくれたので、私は椅子を温めることに専念した。

・・・

RAGEからは気持ちを切り替えたつもりだったが、アズリムの投稿を見て我慢してた感情が爆発する。

コンテスト終了1時間前に抜けられれば間に合うのでは?と思い、5000円でbeetくんを買収しようとしたが一蹴される。え〜ん><

アズリム、心の中で応援してるからね・・・。

Day 2

コンテスト中は当然スマホをいじるわけにはいかないので、コンテスト前にアズリムにリプしたいなぁという気持ちでギリギリまで粘ったが、さすがに朝の10時は早すぎた。

・・・

コンテストのことは忘れた。

最終順位は6完5位。当然私は1問も解いていない。問題文に一通り目を通したあとは机の掃除を頑張った。まあEとFは少し貢献したかもしれない。

結局ラスト1時間はAC数を増やすことができず、beetくんが「これならうくさん抜けてもよかったね」みたいなことを言ったので「それは言っちゃダメでしょ…」という気持ちになった。

ちなみに昼食のお弁当は牛丼にした。JAGもなかなかわかってるじゃないか。

・・・

やはりコンテスト中にアズリムがツイート+リプ返をしていた。リプいいねをもらうために応援しているわけじゃないけど、やっぱり一言応援リプを送りたかった。

解説中にオープニングライブが始まったので、AbemaTVで視聴した。おかげで解説のことは覚えてないが、画面の向こうで一生懸命歌とダンスを披露してくれるアズリムにとても心打たれた。

「人類みなセンパイ!」の曲調は明るく、いつも元気なアズリムにピッタリだと思った。しかし、歌詞はまるでセンパイたちのためだけに書かれたかのようなとても胸を打つもので、喜びと感謝の気持ちでいっぱいになった。

大会はアズマリム ・もこ田めめめペアが大健闘してくれたので見ていてすごく楽しめた。大会終了時には二人の距離が縮まったようで、私も嬉しい。

Day 3

コンテストのことは忘れた。

最終順位は9完4位。もちろん私は解いてない。問題文を読んで概要をまとめる作業をした。

Hが明らかにLPの見た目をしているので、「シンプレックス法があれば解けるでしょ」とか言っていたが、シンプレックス法は落ちる想定だった。世知辛い。あとフロー怖い。

Kは実質PCK過去問だったが、その時と全く同じ嘘解法を生やした。成長してない。

・・・

解説終了後すぐに帰路についた。さっさと帰って自分の部屋のベッドで寝たかったし、なによりさっさとWi-Fi環境でRAGEのアズリムを振り返りたかった。

人類みなセンパイ!は冗談抜きで神曲なので全人類が聴くべき。

まとめ

JAG夏合宿おつおつおー!

まあ私はいつも通り我がシモベたちを手足のごとく働かせたけど、やはり優秀ね。さすがは私のチームだわ!

精進のモチベとかはもう完全にないし、私はもう雑用とかサポートとかに回ったほうが良さそう。というか去年からずっとそうなんだけど。

最後に一つ言いたいことがあるわ。未だにアズリムを知らぬ愚かな人間どもよ…、人類みなセンパイ!を聴いて、アズリムを見なさい!!

 

AOJ 2691: Cost Performance Flow

久々にフローの問題を解いたうくー!

 

……とは言っても本質であろう「解析的に解く」という考察はbeetくんに聞いたのでまぁはい。

 

問題概要

https://onlinejudge.u-aizu.ac.jp/#/problems/2691

 

辺に向きとコストと容量のついたグラフがあります。sからtへフローf_{s,t}を流します。このとき、

B(f_{s,t}):=C(f_{s,t})^2+(M-F(f_{s,t}))^2

で定義されるバランス関数B(f_{s,t})を最小化するf^*_{s,t}を求め、B(f^*_{s,t})を既約分数で出力してください。

ここで、Ms-tフローの最大流量を、C(f_{s,t})f_{s,t}のコストを、F(f_{s,t})f_{s,t}の流量を表します。

 

みたいな(日本語ができないので許して

 

解法

最小費用流(というかPrimal Dual)の気持ちになると解けます。

 

こういうのは解析的に解く(beet談)らしいので、B(f_{s,t})が下に凸の関数ならその極小値を求めたいです。(実際B(f_{s,t})は下に凸な関数です。)

ところで、C(f_{s,t})は流量F(f_{s,t})の関数とみなせるので、以降F(f_{s,t})FC(f_{s,t})C(F)と書きます。(ついでにB(f_{s,t})B(F)で書きます。)

Primal Dualで新たな最短経路に沿ってフローを流すたびに得られる、それまでの流量FとコストC(F)をグラフ(グラフ理論の方でない)にプロットします。

f:id:ukuku09:20180527113449j:plain

こんな感じになります。

最小費用流の気持ちになると、新しい最短経路に対して流量とコストは比例の関係にあるので、ある区間\alpha \le F \le \betaでは

\displaystyle C(F)=\frac{C(\beta)-C(\alpha)}{\beta-\alpha}(F-\alpha)+C(\alpha)

です。

この折れ線上にB(F)を最小化する点があるはずなので、上の式をB(F)に代入して微分します。

\displaystyle B(F)=\left\{\frac{C(\beta)-C(\alpha)}{\beta-\alpha}(F-\alpha)+C(\alpha)\right\}^2+(M-F)^2

\displaystyle B'(F)=2\frac{C(\beta)-C(\alpha)}{\beta-\alpha}\left\{\frac{C(\beta)-C(\alpha)}{\beta-\alpha}(F-\alpha)+C(\alpha)\right\}-2(M-F)

で、B'(F)=0として整理すると、

a=\beta-\alpha

b=C(\beta)-C(\alpha)

c=C(\alpha)

\displaystyle F=\frac{a^2M+b^2\alpha-abc}{a^2+b^2}

が得られるので、これが\alpha \le F \le \betaを満たすかを調べてえいえいすれば良いです。

どの区間も不等式を満たさないなら、プロットした点でのB(F)の最小値が答えです。

 

補足

答えを既約分数にしないといけないので、式変形とかしないといけないくて面倒くさいです。多分その辺を適当にやったからだと思うんですが、オーバーフローしたので†__int128_t†を使って無理やり通しました。

 

提出コード

AOJ 2691: Cost Performance Flow

 

RUPC2018参加記

〜♪(あのBGM)

ぬぁ〜はっはっは〜!!私は「そういえばガ◯リール・ドロップアウト見たんですけど、赤い子の名前ずっとウクニキアだと思ってました!」ってn回言われる大悪魔ァ…†胡桃沢=ウクニキア=マクドウェル†!!

今年もシモベどもの忠義を確認し彼らを労うため、そしてさらなる戦力の増強、支配圏の拡大のために、立命館大学へ出向いてやったわ!感謝しなさいよね〜♪

Day ?

作問した。

とりあえず†悪魔的実装†をすれば解けることがわかったので、無理やり問題セットにねじこんでおく。

後になってbeetくん(@beet_aizu)と怒髪さん(@dohatsutsu)がより良い解法を出してくれたので助かった。

Day 0

1週間くらいじっかぐらし!を楽しんだ。

ARC開始直前にbeetくんになりすます†悪魔的行為†。

そのまま迎えたARCは1完。頓死したクズですが。(構築ゲーは方針ガチャなので)

気分が最悪になったので寝た。

Day 1

うしさん(@ei1333)と一緒に新幹線乗車AC。

新幹線の中で前日のARCトーク

うしさんはEを解いていたので、うしさんに方針を確認しながらEを考察。

うしさんから解法ACをもらう。やったぜ。

ukuku09.hatenablog.com

 

南草津駅でbeetくんと合流。らてまるた(@LatteMalta?)がいなかった。

にぼった。

 

自己紹介フェーズはまぁはい。(はいなので)

「なぁ〜はっはっは〜!私はこの合宿を掌握するもの、†胡桃沢=ウクニキア=マクドウェル†!手始めに我が研究室のシモベにAOJのシステムを書き換えさせたわ!せいぜいpracticeでしっかりチェックしておくことね!」

みたいなことを言った気がする。

 

「チームは決めてこない。誰と組もうが最高のパフォーマンスを出す。それだけよ。」

なので会場でチームメンバーガチャ。tsutajさん(@_TTJR_)とwhesonさん(@wheson)さんに決まる。

レート的にtsutajさんが一番強いので椅子を温める担当をしようとしたが、なぜかCをやることになってしまう。

 

B読めねェ…。

Cは見た感じ解けそうで、Bが読めなかったらしいので変わったのだが、読めねェ…。

1:30/3:00をBに溶かす。

「この考察だとaを使う必要がなくて、必要のない入力をさせる問題はマジでクソなんですよね〜」

EGを通したtsutajさんがDの解法をくれたので気分転換に僕が実装。AC。

すかさずtsutajさんがFを通す。

3人でBを考える。tsutajさんが最初の方針があってたのでは?と言い出してOutputを見たらああああああああ。AC。

全完しました。

 

懇親会は多くのシモベと話した。まったく、上に立つってのも大変よねぇ〜。

 

運営特権で立命館の合宿施設を使わせてもらった。

留学生のlamさんの分の宿泊費を立て替えたことを英語で伝えようとした結果

「Hey, I paid... your あー... charge? fee? うー...beetく〜ん」

新幹線の中でうしさんに解法ACをもらったARC093のEを実装した。教訓「modを取り忘れない」。

りゅうおうのおしごと!最終話を見ようと思ったら、お子ちゃまbeetくんに「でんきちゅいてるとねれないのぉ〜!」って言われたので、真っ暗な部屋の中で見る羽目になった。

Day 2

ジャッジ陣なので準備のほうをね。

前日に決めた集合時間に間に合ったのがろーるさん(@rollman054)だけで怒ってた。

5時間セットというのもあってか、問題文の印刷に紙を無限に消費してしまった。紙の大切さを知った。

問題文の仕分けに人力セグメントツリーと化した僕が投入され、効率的なマージを実現した。が、ちょっと間違えたためア。

 

なんかチノちゃんが来てたので記念撮影した。

btkさん(@btk15049)が「うくさんはコスプレしないんですか?」とか言っていて意味不明だった。なんですでに美少女で完璧なルックスを持つこの私がコスプレなんてしなきゃいけないのよ?

 

今年は風船を配らなかったので正直やることがなくて暇だった。

桁DP初心者なのでDay1Fをバグらせてたらbeetくんに「状態の持ち方がわかったらあとはやるだけじゃん」とか言われてしまった。

4時間くらいで全完チームが出て「「おぉ〜」」とか言ってた。

終了間際にらてばたぱるチームから解法を文章で書いた提出があってウケた。

 

A問題文担当としては、AのSuccess Rateが100%じゃなかったことに驚いた。

ei1333ってなんやねん。

Lの解説は逆に混乱を招いたかもしれなくて申し訳ナス。

 

懇親会はまぁらて。ぽまえ〜って感じだった。

うしさんが共食いをしてる証拠映像を抑えた。

 

立命館の合宿施設を追い出されたのでネカフェった。

dアニメストアでよりもい最終話を見たけど泣かなかったです。

Day 3

コンテスト前は特に何もなかったが、らてうしがbtkさんからNEW GAME!を買い取ってていーーーなーーーって思いました。

 

チーム決めの結果、yebiさん(@yebis7)といらいざさん(@Eliza_0x)と組むことになった。なんか僕のレートが一番高いことになっていておかしくないですか?まぁなんだかんだいって任意の人間は僕より強いみたいなところがあるため。

 

C通らねェ…。

Cはやればできますとか言っといてWAを量産する†悪魔的行為†。結局通ったのはコンテスト開始から1時間後だった。

D通らねェ…。

DはDPのDなのでDPを考えたが通らなくて辛かった。提出デバッグという†悪魔的行為†。結局通らないのでネガティブな発言をしていたところ、いらいざさんに

「なんか実際はそんな感じなんですね」

って言われた。は?なるほどね。(わかるよ)

残り時間が30分を切り、気分転換にFを読んだらえーこれ最小カットやるだけじゃ〜ん。ノリで実装したらACした。

残り10分を切ったあたりでEも読んだらなんかめちゃくちゃ既視感。これ去年自分がRUPCで出そうとしたやつまんまじゃん!!となって急いでコードをコピペして入出力を修正してたが間に合わなかった。あとで通った。

 

全完チームが続出するなか4完で終わってしまい、チームメイトにとても申し訳なかった。

 

疲れたので解説終了後は特に誰と話すでもなく帰路についた。

人生において重要なことは、コピペでAC数を稼ぐことではなくNEW GAME!新刊を読むことなので、南草津駅近くの本屋でNEW GAME!新刊を購入した。

ろーるさんとkzyさん(@kzyKT_M)と一緒にご飯を食べにきあ。美味しかったです。

感想

とても疲れました。

最後に

クックック、なーはっはっはっはっはー!!愚かな人間どもよ、我が暗黒の力、思い知ったか!

……へ?ウクニキア戦犯しかしてないじゃん、ですって?フン、当たり前でしょー!それが†悪魔的行為†ってやつよ。そんなこともわからないの?これだから下等生物は困るわよね〜。

いい?命が惜しかったら9月下旬に開催されるであろう会津合宿にも参加すること!我が城で待ってるわよ。

 

ARC093 E - Bichrome Spanning Tree

これ好き。

RUPC2018へ向かう新幹線の中で、うしさん(@ei1333)に確認しながら考えた。

問題

E - Bichrome Spanning Tree

解法

「辺iを含む全域木のうち、最小の重みがX未満」を満たす辺iの本数と、「辺jを含む全域木のうち、最小の重みがX」を満たす辺jの本数を数えると、あとは適切な計算をすればこの問題に対する答えが求まる。

上記の辺の本数は、最小全域木アルゴリズムであるKruskal法を利用することで{\it O}(M^2)程度で求められる。

グラフの最小全域木の重み>Xの場合

どのように辺を塗っても問題の条件を満たすことができないので、答えは0である。

グラフの最小全域木の重み=Xの場合

ある最小全域木に含まれる辺のうち、1本でも色が異なれば、問題の条件を満たすことに気づく。(最小全域木は複数存在しうる)

よって、いずれかの最小全域木に含まれる辺の本数mがわかれば

_mC_1+_mC_2+...+_mC_{m-1}=2^m-2

m本の辺の可能な塗り方の総数を求めることができる。

残りのM-m本の辺は当然自由に彩色できる。すなわちその塗り方の総数は、m'=M-mとすれば

_{m'}C_0+_{m'}C_1+...+_{m'}C_{m'}=2^{m'}

と書ける。

これを先の値とを掛け合わせて答えを得る。

グラフの最小全域木の重み<Xの場合

「辺iを含む全域木のうち、最小の重みがX未満」を満たす辺iの集合を\bf Aとすると、\bf Aに含まれる辺はすべて同じ色で塗らなければならない。

なぜなら1本でも色が異なれば、\bf Aの定義より、その辺を含む全域木の最小の重みはX未満で、それは白と黒の辺を両方含むことになり、問題の条件を満たさないためである。

よって、\bf Aの塗り方はすべて白に塗るかすべて黒に塗るかの2通りに限られる。

次に「辺jを含む全域木のうち、最小の重みがX」を満たす辺jの集合を\bf Bとする。ここで、\bf Bに含まれる辺を含む全域木のうち、重みが最小の全域木は、必ず\bf Aに含まれる辺を含んでいる。

これは最小全域木に辺を1本追加すると、その辺を含む閉路がちょうど一つできて、そのうちの1本を取り除くことで再び全域木を得られることから導ける。

これより、\bf Bの塗り方は、1本以上の辺を\bf Aの辺と異なる色にする総数なので、m=|{\bf B}|として

_mC_1+_mC_2+...+_mC_m=2^m-1=2^{|{\bf B}|}-1

となる。

残りのM-|{\bf A}|-|{\bf B}|本の辺は自由に彩色できるので、その塗り方の総数は2^{M-|{\bf A}|-|{\bf B}|}通りである。

したがって、求めるべき答えは2*(2^{|{\bf B}|}-1)*2^{M-|{\bf A}|-|{\bf B}|}である。

ソースコード

ARC093 E - Bichrome Spanning Tree

感想

modを取り忘れない💢💢💢

 

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

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

 

感想

や、参加記秋田