The 2019 ICPC Asia Seoul Regional Contest 参加記

参加記 ICPC2019

 okimochi(idsigma, risujiroh, kort0n)で韓国に行ってきました

出発前夜

準備は...ちゃんとしよう...！

公式サイトどれだけ探しても持ち込み資料についてのルールが見つからなかったので、去年Seoul Regonal Contestに参加したbeetに色々聞いて準備しました ありがとうbeet

 

Day.1

 

ハングル1文字も読めなくてビビる ただの記号にしか見えない

空港は大体看板に日本語も書いてあるのでイージーだったが、電車等では基本的に駅名が韓国語でしか表示されないのでかなり大変だった

 

何やかんやでホテルに着く 往復航空券+3泊4日ホテルが3人合計で100k 安すぎておったまげた

 

安宿だからかホテルWi-Fiがあまりに貧弱 まぁ通信容量無制限の海外用ポケットWi-Fi契約してきたしこれを使おう...

...と思うが、何故かポケットWi-Fiがここで不調に かなり険しい気持ちになる

貧弱Wi-Fiに繋げてなんとかクレームを付ける とりあえず空腹なので外で店を探す インターネットも無しに異国の地を歩くの不安すぎた

 

Day.2

寝て起きたら昨日投げたクレームに対応してくれて、ポケットWi-Fiが繋がるようになっていた ありがてぇ...

そして外出する準備をしていると

なんで？

まあ結果的にライブラリの要求仕様は去年と同じだったので問題無かった ありがとうbeet

 

practiceが昼からだったので、それまで近くのショッピングモールを適当に散策する

これすき

これすごい

これおいしい 日本にも出店して

 

良い時間になったのでpracticeに向かう

 

横浜が基本英語進行だと聞いていたのでソウルも英語進行だと思っていたが、入場案内が韓国語でかなり焦る やばい

何だかんだでその辺のスタッフが英語通じたので何とかなった

 

注意事項説明は英語と韓国語両方だった 助かった

「コンテストルームに入ったら、指示があるまでは"DO NOT TOUCH ANYTHING." 失格になります。 "DO NOT TOUCH ANYTHING."」と一生言われてた 多分"DO NOT TOUCH ANYTHING"カウンター30くらい

 

コンテストルームに移り、practiceが始まる

問題は2018 Seoul Regonal Contestから3問

Practice Aは去年のD

Practice Bは去年のE

Practice Cは去年のL

 

 

去年のE...?

 

(解いたことが無い人はこの先を読む前に是非解いてみてほしい

Dashboard - 2018-2019 ACM-ICPC, Asia Seoul Regional Contest - Codeforces

多分考察は新ABC-E程度で、実装は新ABC-E強〜新ABC-F弱程度だと思います)

以下Seoul Regional Contest 2018の重大なネタバレ有り

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

何なのかと言うと、こういうことです

https://twitter.com/kyort0n/status/1188019884766023681?s=20

https://twitter.com/kyort0n/status/1188019884766023681?s=20

f:id:kort0n:20191111121847p:plain

コドフォジムの順位表

 

Eのペナルティを見るとヤバさが分かると思います

 

 

去年のセットはチーム練しており、そのときはAはidsigmaが通しており、BとCは僕が通していた

まあpracticeでは流石に1人1問実装した方が良いということになり、BとCの一方をrisujirohに譲ることにする

risujiroh「どっちやればいい？」

ぼく「Bやって(即答)」

 

 idsigmaがAを通したので、Cをやる エディタをいつも通りの感じにするのが思ったより大変ということが分かってビビる 結局色々妥協するもかなりやりづらくて、初めて実装したときより時間が掛かる

 

riujirohがBを実装して提出すると、WRONG ANSWER

ぼく「よし！！！！！！！！！！！！！！！！！！！！！」

 

時間がないのでコーナーケースを教える ブチ切れてた

 

何だかんだで皆慣れないエディタに苦戦する等の要因で時間ギリギリに 余った僅かな時間で何となくCLionを弄ると、その使いやすさに感動...

ホテルに戻るとこのリプライが届いている

韓国、あったけぇ...

調べたら789の方だったらしい 本当に有難うございました

 

 

CLionの最低限の使い方を覚える 「明日構文解析出たらよろしく」と押し付け合いながら就寝(弊チームは構文解析担当がちゃんと決まっていなくて、いつもは大体手の空いた人がやってます)

 

Day.3

朝が早い

集まると改めて諸々の説明をされる この日の"DO NOT TOUCH ANYTHING"カウンター20くらい

コンテストルームに移る 周りのチームが普通にマウス触ってPCのスリープモード解除しててウケる 前3チームくらい連続して普通にPCのスリープモード解除されてる 治安が悪すぎるだろ

まあスリープモード解除されるくらいは事故でもありそうだし仕方ないかなと思うが、いくつかのチームが開始1分前時点でスリープモード解除した上にログイン画面まで進めていた それはシンプルに不正じゃないか？

 

コンテスト

idsigmaがABCDEFを読み、risujirohがGHIJKLを読み、ぼくが最初にエディタの設定をすることになっていたので、する

エディタの設定を終えると、「EFGHを読め」と言われたので、読む

E:なんか出来そうな見た目 なんかうまい貪欲とかありそうじゃない？←なさそう まあ後回し

F:あーなんか今年の幾何問題不可能そうだな... とりあえずrisujirohに後で読んでと言って放置

G:なんだこれ むずそう

H:出来なくはなさそうだけど、多分解けても実装重いだろうな 後回しでいい

 

idsigmaにIが簡単そうだと言われる 読むと確かに簡単で、実装を始める

なんかこの頃にはもうAが通ってたらしい いつ通ったんだ？

無事実装を終えるも、サンプルが合わない 何故か「隣接する2点の距離をans以下にする」ではなくて、「隣接する2点をans以上離す」で実装してしまっていた は？

 

一旦PCをrisujirohに譲ったらJが通ってた その後Iを通す

その直後、idsigmaにLの解法を伝えられる これはバグらせずにサッと実装して通す

 

「B得意そうだからやって」と言われ、問題概要を伝えられる

考えると、うまいこと部分木の情報を1つの値で表して木dp出来ることが分かる

しかし、risujirohが「これ最大ケースだとlong longでオーバーフローしないか？」と言い始める 確かに...

「とりあえずlong longで提出して、落ちたらint128で書き直して再提出しよう」と言って、実装を始める int128の出力を書くのが面倒だったので説得出来て良かった

 

しかし、ここで伝達ミスで、「全ての葉のペア」ではなく「全ての頂点のペア」だと思って解いてしまっていたことに気付く 大まかな解法が壊れる訳ではないが、遷移式が書き直しになる 伝達ミスは最近のチーム練でも何度もやらかしてたので気をつけてないといけないと思っていたのに油断してしまった...

更に最悪なことに、元のコードを少し弄ったらスパゲッティになって酷いことになる コードを印刷して、Hが解けたと主張するrisujirohにPCを譲る

 

暫くしてバグを発見して直すとサンプルが合う 提出するとAC これに1時間くらい掛かったの本当に酷かった...

 

 

ところで

これがICPC

 

順位表を見るとKがそこそこ通っているので読む

未証明だけど、ある平面を固定したときにそれらを跨るような点の取り方をするのは損だなぁ(雑)という気持ちになる 平面の取り方を全探索すると、これでO(N^4)となる

この先は幾何っぽい考察が必要だねという気持ちになる risujirohがHを通したので、これの続きを投げて、自分はGに移る というか、このセット実質幾何が2問か...

何かこの辺で順位表が凍結する 2年くらい前の韓国大会でも1位チームが残り1問になった時点で凍結されたと聞いたので今年もあるかなと思っていたが、実際1位のCafe Mountainが残り2問になった時点で凍結された 自由すぎるだろーと思っていたけど、そういえばルールで順位表凍結時刻は指定されてないんですよね...

 

Gを考える 色々考えると、左から順番にdpをすれば良いということが分かる これ遷移式が、「2つの異なる区間の中の最小値のうちのmin + 1」みたいになるんですよね こんな遷移式初めて見た...

とりあえず区間minを愚直に求める方法で甘えて残りを実装すると、無事サンプルが合う あとはセグ木を写経して区間minを高速に求められるようにするだけ 勝ったな！

ウッキウキでセグ木を写経してサンプルを試す バグる 人は何故...

写経をミスっていました 提出するとAC

risujirohが「Kの平面全探索は軸を1つfixして、もう1つ通る点を偏角ソートで順番に見ると高速に更新出来るから間に合う」と言い始める なんだそれ やべー

risujirohがKの実装を始める 残りの問題のうち手が出せそうなのはCとEあたり Fはrisujirohが多分無理と言ったので諦める Dはなんも出来る気がしない(これも結局伝達ミスで問題を勘違いしていたんですが...)

眺めていると、Eが解けた気分になる Kと並列で実装を始める(お互い詰まったら印刷して交代)

Kのサンプルが合ったらしいので提出するが、WA というかKのサンプル貧弱すぎるだろ

その後Kを何度か提出していたが、全然通らなくて辛そう

Eの実装が終わる サンプルを試すsample2~sample4はok sample1の3番目の答えだけ合わない

まあこれは後は少し境界条件が間違っているだけだろうという気分になる

暫くしてKが通る なんか尺取りでバグっていたらしい？

 

KをやっていたrisujirohにEの現状を伝える すると、

「サンプル1で3番目の答えって2で合ってるんじゃないの？これとこれとこれを取り除いたら連結成分数2つになると思うけど」

と言われる 確かに？？？？？これ出力例間違ってないか？？？？？

出力例のミスを信じてsubmitすると、一瞬でWAが返ってくる そういえば3番目の答えは頂点を2つ取り除いたときの答えでしたね......

 

残り10分くらいになっていよいよ大幅な書き直しをする時間は無くなってきたので、ドキドキソート評価関数ガチャを始める(こういうのあまり好きじゃないんですが、流石に時間が無かったので...)

結局通らずに終了 以上8完1043ペナでした 凍結時点では1位10完投Cafe Mountain 2位9完789で3位以下は7完以下だった為見た目の順位は良いが、まあ凍結から2時間経ってるのでよそのチームも沢山通しているでしょう...

 

反省点

Bがすぐ通せないの最低 伝達ミスを考慮しても遅すぎる

長いこと順位表が凍結されていたので周りの情報は分かっていなかったのだが、終わってみればEはオンサイト1ACの地雷問だった これ手を付けるべきではなかったのかもしれない...(オンラインミラーはそこそこ通ってた) まあ僕の解法はO(N^2logN)だったんですが、どうやらこの問題はO(N^2logN)はTLがかなり厳しかったらしい？じゃあ実装出来てても厳しかったんだろうか そもそも自分のが本当に合っていたかは分からないんですが

HとKで「試す順番を工夫すれば更新が高速に行えるので計算量を落とせる」に気付かなくて解ききれなかった これ苦手分野なのかもしれない...

 

コンテスト後

日本勢いつものperiscopeをする しかし進行が韓国語...

結果は11位でした

10位以内に入ることも出来なかった 良い順位ではないんですが、でもこれは冷えではなくて多分実力相応くらいなんですよね...

話を聞いてなくて壇上に呼ばれることに気付いていなくて、慌てて壇上に向かう 慌てていたのでiPadを閉じてしまい配信が途切れる 配信聞いてた人すまんな いや11位で表彰されるとは思わなくない？

 

1位のCafe Mountainが全完だった えぇ...

 

 

この夜は何も無かった いいね？

 

Day.4

 

次は来週の横浜ですね 横浜でお会いする皆さん、宜しくお願いします