HUPC2019 参加記

　参加記を書くときの書き出し、迷いがち。

4月〜7月くらい

ほむちゃんが有志コンテストの作問を募集していたので入った。8問コンテストのはずなのに原案が最終的に30問くらいあつまってすごかった。ほむちゃんはday1のほうの作問も忙しそうだったりで大変そうだなぁって思ってた。交通費やばくない？って思ってたら長野県で10万円を得たので無事飛行機を取ることができた。

 

Day0

　19時くらいに北海道に着いて、ほむちゃんとジンギスカンを食べた(ツイートするのを忘れていた、ツイッタラーとしてあるまじき行為)。ほむちゃんのお家にお泊まりして、合鍵をもらってはしゃいだりday2どれくらい解かれるかなぁとか話したりした。

 

Day1

　ほむちゃんと一緒に家を出た(家が同じなのでそれはそう)ので設営のお手伝いをした。

 　コンテストはそすうさとMatsudaさんの3人で出た。てんぷらは後ろから順番に読むことにして、F解けたけど実装したくないーとか言ってとりあえずBをそすうさが解いてくれたりAをまつださんが解いたりしてくれてる間にDを無証明O(1)で通したりEのインタラクティブでオンサイトFAを取ったりCの構文解析を泣きながら書いたりした。最終的にFも配るDPで実装したら意外と重くなくてAC。Gは去年のICPCのHだなぁって思ったけど実装間に合わなくて悲しかった。

　ほむ「オンサイト優勝はhupc_homunokoibitoさんです！」勝ち。

　懇親会はkenkooooooo(oの数を忘れてしまって申し訳ないんですが大は小を兼ねてほしい)さんが「AGCに出ないなんてことありますか？」って言いながらビールがんがん飲んでて面白かった。fixstarsの人事さんに「てんぷらやさん」って言われたけど僕は売られる側なんだよな。

　懇親会を途中抜けして出たAGCは冷えて悲しかったので、お酒を飲んで酔っ払ってほむちゃんに泣きついたりしてた。

Day2

　朝はちゃんと起きれた。この日は運営。

A, B　Hokkaido University

　北大っぽい問題で好き。チーム戦って前半は分担みたいな戦略で臨むチームが多いので、ABが共通問題だと戦略ちょっと乱されそうだなぁと思ったりした。

C　串刺し

　実はこれは最初CPSCOのC(300点)に提案されて全力で止めた問題。HUPCでもBに置かれかけて全力で止めた(この過程でほむちゃん原案の問題がday2から消えたりした、ほむちゃんごめんね)。実際そんなに解かれなかったし証明込みで通したチームってなるともっと少なそう。問題文がてんほむになったのはつぶあんくんの優しさです。

D　Two Colors Sorting

　原案がO(N^2)だったのでO(N√N)になるよって言った。典型の組み合わせで綺麗で好き。bitsetを落とそうとしたらPythonが不可能になったのにbitset自体はど愚直以外何かしら工夫すれば通りますになってしまって厳しかった。C++許さねぇ。本番もbitsetで通したチームのほうが多かった気がする。ちなみに2つを組み合わせるとさらに速くなる→http://noshi91.hatenablog.com/entry/2019/07/16/213823

E　Jam

　原案出しの終盤にダイクストラとかそういう感じの問題ないねってことで生やした。想定は拡張ダイクストラだったけどパンの処理の仕方はいろんなやり方があるみたい。つぶあんくんが色々投げてくれたからテストケース作りはちょっと頑張って、負辺が絡むような操作をするとだいたい落ちるはず。意外と評判がよくて嬉しい。

F　MOD Rush

　原案てんぷら、問題名と問題文と解説ほむっていう分かりにくいてんほむ。超シンプルな設定で解法に調和級数出てくるの面白くないですか？(自画自賛)　もともとEとFが逆だったけどこっちのほうが難しい気がして入れ替えたのにこっちのほうが解かれた。難易度評価難しいね。beetさんに8分で解かれて笑った。

G　Tree

　もともとK=2固定だったのがTester解書いてる途中でK=300でできることに気づいたので変えた。O(NK)の木DPあんまり問題例ないよねということで。原案はつぶあんくんなので「数え上げが出たらてんぷらだと思う」って言われるたびに違うんだよなぁって思ってた。 

H　Revenge of UMG

　もとの問題はこれ。テスター引き受けたときにN=100000で解けないか考えてそのときは無理だと思ったんだけど2ヶ月くらい経ってから考え直したらできたので出した。

　'?'はbitset解を落とすため(?がないと1番出現回数の少ない文字を固定するとかするとすごく速い)と、なんとなく最終問題っぽい見た目にするために足されたあまり本質ではない蛇足。

 

　ということで結果としてかなり後半の問題に関わることになっちゃったので、「てんぷらの好きな問題を集めました」セットになってしまった*1。The Way(双子+tatyam)に2時間切りで全完されたのはちょっと悔しかったけど概ねいい感じの難易度になったっぽくてよかった。

　終わった後ほむの家にもどってちょっと昼寝をして寿司を食べた。北海道は美味しいものが多い。

before

 after

 

Day3

 寝坊すれすれで起きて、ほむちゃんと涙のお別れ。大阪に帰ってきたらクソ暑くてキレた。でもたこ焼きはうまい。

 

 

最後に

　今回は3時間コンテストのcontestantとjudgeを両方できてかなりいい経験をさせてもらえました。オンサイトで関わってくれたみなさん、コンテストに出てくれたみなさん、泊めてくれたほむちゃん、ありがとうございました！！！

 

 

 

 

*1:てんぷらの好きな問題を集めるとHeno Worldが冷えることが知られていて、得意分野がまるでずれてるのがレート以上に結果を出せている理由の1つかも...?