kotamanegiの取り扱い説明書

のんびり趣味の事を書いてます。

ICPC 2020 国内予選 参加記

2020年11月6日に開催されたICPC2020 国内予選にチームonionsで参加しました。 メンバーはjupiroさん・kuhakuくん・kotamanegiです。 最初に結果を書くと、ABCDFの5完で11位でした。

コンテスト前

今年はリモートでの参加だったので、恐怖に打ち震えながら寝そべっていました。

コンテスト中

今年は並列コーディング可だったので、jupiroさんがA、kuhakuくんがB、僕がCを解くという役割で挑みました。 コンテストが始まってCを見ると(実際はDを間違って開いてました)、ガチガチの構文解析ゲーだったので解き始めてしまいました。 AとBのAC報告が上がった所で、Cにしては難しいなと思って他の問題を読もうとしたところで、ようやくDを見ていたことに気付きました。 本来のCを見ると、愚直解で通りそうな問題だったので書いてACを取りました。

その後Dに戻って書いていると、誤読している事が発覚。 ちゃんと問題を読んでみると不等号が、不等号ではなくmin,maxに近い働きをしていると気付きます。 どこかで見たことがあるなと思っていたら、O(n * 2n)の全探索である事に気づいてAC。

続いてEを見ると、4分割できる所までは気づきましたがそこから先が分からず断念。 諦めてFを見ると、Link-Cut木を持っていると簡単に出来そうな事に気づきます。 Link-Cut木は持っていないのでmergeの時に頂点を追加するUnion-Findを書いてAC。

ここで残り時間がわずかになっていたので、Eを書ききれる気力もなく順位表を眺めていました。

コンテスト後

いい生活は今年で20周年で賞を受賞したかもしれません。 横浜のカタログギフトが楽しみです。

反省

F問題に時間をかけすぎました。 もっと実装ゲーを早く通せるようになりたい。