迷いませんか?

継続しないを座右の銘に

ICPC Asia Taipei-Hsinchu Site Programming Contest参加記

ICPC Asia Taipei-Hsinchu Site Programming Contest 参加記

海外遠征、大学から少しでも金が出るんだったら行きたいという気持ちになり、なんかいい感じのやつがあって出たので行きました
台北を選んだのはちょうど大学の文化祭があって前の火曜から次の月曜まで休みになるので公欠取れなくても大丈夫だったからです

チームメイトに台湾に数回いったことがある人がいたので安心して行くことができた

1日目

流石に前泊的な感じのことをしないと体力が死ぬので金曜日に台湾につく
すぐにホテルにいって荷物を預け、台湾といえばという気持ちでかき氷を食べに行く

めっちゃ美味しいんだけど冷たすぎる、ところで台湾は暑すぎる
口の中が甘くなったのでしょっぱいものをということで屋台ではないけど通りで小麦粉を焼いたものに色々挟むみたいなやつを売ってる店があったので適当に買って食べたらお腹いっぱいになって破滅する

他のRegionalに行った人がマッサージを受けていて羨ましすぎたので台湾マッサージを受けに行く
最高にリラックスできたのでめっちゃいい気持ちになる

お腹があまり空かなかったのでそのままホテルに帰って寝る

2日目

適当に起きて、プラクティスに向かう
チームの席は長机を互い違いに二列に並べたものが五列ある感じで、席に座って斜め前に2つ自分の方を向く机があることになるが普通に机の上が見えて、なにこれは...となってしまう

わくわく

オープニングセレモニーとか色々ある
横浜では指示や挨拶はすべて英語で日本語は一切使用されなかったが、中国語を普通に使っていて交互に使われたりすると耳が慣れなくて元々英語のリスニングが苦手なのに一切聞き取れなくなってしまった
ちゃんと聞き取れてないのでわからないがコンテストの本質に関わる、注意事項やコンテストの開始時間以外についての指示は中国語のみで行われていたものもあったと思う
この時点で少しワクワクコンテストの雰囲気が強くなり始める

ラクティス

とりあえずCLionのセットアップとCapsLockをCtrlにするやつをやろうとするが、CapsLockを間違えて押したあとにCapsLockをCtrlに変えてしまい直せなくなってしまう
めっちゃ焦りながらキーボード設定からUSを消して入れ直すをしてI got Kotonakiをする

  • A, Bがやるだけなので、やる
  • Cが貪欲とDPが同じ解にならない最小の金額を求めろってやつで、見たこと、あるな(解けない)をする
  • Dが簡単だったはずなのでそのままやる
  • Cが普通にDPで最小を求めて貪欲と比較すればいいことに気づきできる

上位チームが早すぎて早すぎるでしょ...という気持ちになる

なんか弁当を配られるが台湾の料理を満喫することが目標なのでそれを手にしたまま牛肉麵を食べに行く
肉の硬さに恐ろしくばらつきがあってびっくりしたけどおいしかった、麺が腹にたまる
帰りはタピオカを買って帰る

DDCC予選にでてレートを少しだけ上げる
簡単めのインタラクティブは、たのしいという気持ちになるけどなんか3Nは間に合うという気持ちになる時間でペナルティと時間を無駄にしてしまった
Dは編集距離3(変数名を間違えていた)で通らず、最後まで気づけなかったのでアになってしまった
多分通ったと信じている

もらった弁当を少し食べてみると味が濃かったり色々であまり美味しくなくて悲しくなった

3日目

朝、早起きをして会場に向かう
Cloakに荷物を預けて席につくが9時半近くになってきても周りの席が全然埋まっていないため予知能力が働きコドフォることがわかる
15分コドフォる

なんとか始まる

コンテスト

とりあえずセットアップをしたあと、A問題の概要を聞いてとりあえずDFSをうまく実装すれば行けるな...ということを察して他のを読んでもらう間に書いておこうとする
そしたらその前にCとDが通っていて、他のチームの英語を読む速度に一同驚愕...
上位チームが解いている問題を追っていく感じになってC、Dを通す
H、J、Kが通っているのでとりあえず読んでもらう

JとKはやるだけを感じたので実装を始め、Hが詰めれる自信0になったのでチームメイトに任せる
Kは隣り合ってる必要がないことに気づき適当にpriority_queueとかで実装してAC
Jはstringでやれば、いけるやろ!と思って実装したらTLEになってしまったのでbitsetで実装して1ペナでAC😢

天才チームメイトによりHの式が出てくるのでそれをそのまま書いたら通る、チームメイトが天才過ぎて怖い

Aを1位チームが通したので頑張ってペアプロっぽく実装を始める
メモ化しながらDFSをしていくんですが、こういう同じ盤面が現れうるメモ化DFSの実装は毎回バグらせていて無限にバグらせる
なんとか盤面とかかっている手数の両方をキーにしてメモすることでなんかうまくいくのでAC(無限時間かかった)

M、H、Lあたりを通しているチームがいて、Mは明らかに天才数学ゲーなのでひとまず捨てることを決意する
Hはチームメイトが少し詰めてくれたので更にちょっと式変形して実装して投げてWAになる
構築は、無理
解法自体間違ってるが実装も無限に間違えていたのでそれを少しずつ直しながら投げて無駄なペナルティを積み重ねる
解法を考え直している間にLのために凸包あたりの幾何を写経してもらう

Eが1つ目の要素を-1にしてやるとうまく大体作れることがわかり天才になった気分、そして作問者天才か?台北、すげ~~~~!!!!という気持ちでACする

Lの写経が終わるので凸法を求め、凸包の頂点数が2以下の場合は0、三角形の場合は場合分けし、あとは四角形の対角線となる凸包の頂点対をしゃくとりで求め対角線の両側として凸包上から三角形を最大化するやつを取り出す感じで実装する
3e8みたいな出力にはするなというのを見つけ、まあfixedとsetprecision(10)みたいなことをすればそうならないんですよねという気持ちでそれを書く
結構しゃくとりをバグらせてしまうがサンプルが合うのでとりあえず投げる

WA

泣きながら少し修正して投げるを2回やる

WA x 2

精度かな~やっぱ!wと言いながら#define double long doubleをして投げる

WA

裏の一番上を見ると、余計な0を表示するなと言われているのでfixed setprecision(10)を削除して、2倍して丸めて2で割って出力をして投げる

WA

三角形の面積の2倍が整数だけで計算できることに気づくがそれを実装する時間がないので7完で終わり

終了後

右前のチームの人に、A問題どうやって解きましたか?と英語で聞かれたので圧倒的コミュニケーションスキルと英語力で対応する

僕「あ、えっと...DFS ...」
その人「It takes too much time ?(みたいな感じ)」
僕「え...memorization...? DFS with memorization ...」
その人「(聞き取れない)」
僕「(コードを見せながら) like this ... key is a condition ? state ? and turn ... ?」
その人「I can't read your code ...」
僕「ア...ア...」
その人「Ah... Sorry ...(去っていく)]

自分、英語の勉強いいですか?
これで周りの人とコミュニケーションをとる勇気が0になるので会津の人とすこし話し、8完していることを知って悲しくなる

その後、出力形式とか大丈夫ですか?って言われて、まあ両方対策したつもりなんで大丈夫だと思うんですけどね~~と言う
手元で適当に一辺1e9の正方形で試すと1e18って出力されてなるほどね、となる
fixed setprecision(10)を消した時点で指数表記になっていた。終わり

実際このコードをもう一回なげて試すことはできなかったので本質があっていたかはわからないのでア

表彰式っぽいのが始まると、中国語しか喋らず突然1位から表彰しはじめてyesnoないの?そもそも英語は?となるが国内予選の話っぽいことに気づく

yesnoが始まる前に海外最優秀チームの表彰をしたけどこれは流石にAsiaのことじゃないですか?ネタバレでは???

yesnoが始まり、凍結時点で13位だったんですが下のチームがLを投げまくっていて終わり...という気持ちで眺める

案の定抜かれまくり、悲しくなる

横浜では4完内1位で20位だったと思うんですが、7完内2位で20位になりました
世界一Asiaで20位を取るのが上手です、よろしくおねがいします

yesnoの途中で60位ぐらいから上位10チームがゴールド、そこから20チームぐらいがシルバー、残りがブロンズみたいな感じで表彰がありめっちゃ時間がかかる
20位なのでシルバーだったんですが、もらえる盾が明らかに金色なのでSilverという文字を隠してTwitterに上げるなどをした

ところでこういう上位3チームじゃなくてN割に金銀銅賞を上げる形式紛らわしいし他の界隈には馴染みがなさそうでめっちゃ本来よりすごいと見られてそうで怖すぎる

懇親会が始まり、弁当のことで少し怖くなりながら行くととても美味しそうなので嬉しくなりながらすこし食べる

実は小籠包が食べたかったので懇親会はそのまますぐに抜け出して食べに行く
少し(デザートは一つを除き全種類)食べたのでお腹が少し苦しかったけどとても美味しかった

ちょっと遅くなったけどunratedなのでABCに出てAの提出から大体30分弱で全完する
帰りながら問題は読んでいました...

チームメイトはratedなのに30分遅れ参加していてすごい

寝る

4日目

帰りの便が15時半なので適当にお土産を買う場所を案内してもらいながら色々買っていく
明らかに買いすぎたんですが、コンテスト参加費が一人3000元なはずはないけど念の為とおもいそれだけ引き出してたのでまだまだお金が余ってしまった

空港でタピオカを飲み、終了

おわり

海外遠征、とても楽しいのでやるべきなんだよな、お金が出るなら(来年は国内予選でいい結果出して補助がほしい)
台湾は結構日本語通じたり、そもそもジェスチャーで結構なんとかなったりするので結構よかった
料理も美味しく、最高
問題のセットも、国内予選通過チームが多いからか簡単枠も多くたくさん通せて楽しいしよかった!
E、F、Iは既出で、E、Fに関してはサンプルケースすら丸パクリだったらしい、ワクワクすぎる
来年台湾に行く人はたくさん練習とかバチャをしてこの問題バチャでやったことある!状態にするのがいいと思います(?)