かっつのメモ帳

主に競プロ　時々日記

HUPC2020参加記

コンテスト参加記

Day1

北海道大学セット　解説


大学同期のばやしこと出た、が僕は当日半年放置してた東京の家に親と共に来ておりフル参加は厳しかった。

ワイルド食べたい。

ばやしこに前半は任せた！wと言ってコンテスト開始。


[0:12] 大学に行く用事があったので家を出る、大学まで歩きながらスマホでD,E問題を読んだ。

ちなみにこの時点でA,Bをばやしこが通していた、Bで遅延セグメント木とか言ってて面白かった。

[0:17] D問題は傾きの同じ2直線を持ってきた時にN個の頂点が全て直線上に存在させることは可能か？という問題に落ちることを伝える。

[0:29] C問題

かっつ「Nの大小で場合分けする雰囲気を感じるな〜」

ばやしこ「あれもしかして前20個だけ見れば良い？」

かっつ「それほんと？N=21とかで嘘にならない？」

かっつ「220ってどれぐらいの大きさだっけ」

ばやしこ「100万」

かっつ「嘘じゃありませんでした、すいませんでした‥‥」

[0:35] ばやしこにCの実装を任せる。


一方その頃感動の再開

[0:45] Nの小さいケースでうっかりTLEをしてしまうが、無事修正して3完　やったぜ

[0:47] ばやしこ「Eは取り敢えず距離とアルファベットを考慮してグラフ作って、(ここに最小頂点被覆問題の説明)に落ちる」

[~1:27] 部屋の掃除をしていた(え？)

[1:34] ここで二部グラフであることに気がつく。そうじゃないと解けるように見えない。

[1:36] かっつ「うーん、二部グラフにして少ない方の頂点集合の個数が答え！w」

[1:47] 自信満々にばやしこに解法伝えて実装してもらうが落ちる(嘘なので、それはそう…)

[1:47~] ばやしこが用事で抜けてコーディング担当がいなくなる。

[2:20] ようやくパソコン触れるようになる、自信満々にEの実装を始める。

[2:36] 落ちる(嘘なので、それはそう…)

ここで自分の嘘にも気が付いた

[2:40] やらかしで焦りながらDを書き始める。

0と1が同じ直線に存在するかしないかの2通りで解けると思ってたので、実際にコードを書き始めてからこれでは足りないことに気が付き頭が真っ白になる。

…が、0と1が同じ直線/1と2が同じ直線/0と2が同じ直線 の場合を調べれば良いだけだったのでget a 事なき。

[2:56] サンプルが弱くて不安だったが、出したら1発で通ってかなり嬉しかった。


感想

二部グラフの最大マッチング、これは思いつかないとダメ。

楽しいセットだったので本当はフルで出たかった、けど少しでもチーム戦ぽいことできて良かった。明日からも楽しみです。


Day2

無職を担当しました　ぴえん

会津大学セット　解説



[0:01] Aを書く。安全運転でサンプル全部試したけど全体9番目とかで早かった。

Bを開く、かなりやりたくない見た目をしてるのでCを先にhotmanに書いて貰う。

[0:08] Cが通る。Bを書き始める。

[0:25] 安全運転で整数型で扱うようにしたり、普通にindexでバグらせたりで遅かったけどノーペナでBが通る。

(今日の僕の仕事はここでおしまいです←！？！？？！？！w)

[0:59] D問題を皆で考察していた。連続する3点を見ればいい、X,Yで独立して考えられる、減らせるスコアの上限は決まっていてこれとKのminが実際に減らせるスコアという話がまとまったところでhotmanが書いて通す。

D問題の実装の間にG問題の式変形をすると普通に解けそうな問題に落ちる。ただ苦手そうな雰囲気はあるので得意そうなhotmanに投げた(せめてD問題の実装ぐらいは僕やるべきだったかなぁ)。

[1:23] Gが通る、hotmanありがとう…


ここから辛い時間が続く(いや何も君やってないけど？)

J問題、外れ方針しか思いつかず辛い

I問題、数学が分からず辛い

Hyado君が詰めてたM問題、grundy数の上手な求め方が分からず辛い


[3:11] Hyado君が8ペナの格闘の末、Mを通す。Grundy数、葉からその頂点の寄与分を愚直に上の頂点に渡していくと O(NK) で求められるの面白い(log はつくかも)。

[3:34] hotmanがJを通す、ありがとう…(2回目)

[4:33] hotmanがIを通す、ありがとう…(3回目)

残り時間、L愚直で行けないかなとか、E絶対典型ぽい見た目してるから解きたかったなぁとか、K問題ヤバすぎとか話してたらコンテスト終了。


感想

8完全体20位(他の早稲田のチームには勝ったぽい)

冷静に考えて俺要らなくない？

せめてupsolve頑張ります　反省の意も込めてK問題やるか………


Day3

この記事書く僕「あれ僕今日何やったっけ」

有志セット　解説


昨日に引き続きICPCチームで出た。コンテスト10分前に起床してそのままコンテストスタート。


[0:02] 準備で出遅れ少し遅かった。A問題AC。

引き続きBを開く、とても辛い気持ちになる。

先にhotmanにCを任せる。

[0:20] CでWAが出る、ここでHyado君がHELPに入った気がする。このタイミングでBがまだ詰まってなくて内心かなり焦っていた。

ひたすら手元でBを試してた(この時xとyの差が共に1以上の時、理論値可能なのでは？と思ってたんだけど時間かけてたのもあり踏み切れなかったな)。

Fで2点swap可能って話をHyadoから聞いてすげーと言ってた記憶もある。


[0:59] C WA [1:08] C RE [1:10] C WA

始まってきたな

話聞いてて思いついた別の解法を話したらhotmanも考えていたらしく、その方針で実装することに→C AC(1:23)

[1:35] B詰まってなくて本当に死にかけ　その間にhotmanがささっとIを通す。

[1:49] 自信ないけど取り敢えず詰めたところまで書いてBを出す　Wrong Answer　辛い。

[2:15] 引き続いてhotmanがM問題を通す、ありがとう…


ここから僕のB, HyadoのFを互いに相談しながら進めていた気がする。

[3:09] 結局hotmanに最初考えてたことを指摘され、それを実装する&コーナーケース指摘を受けて何とかBが通る…

仕事を探すといかにも僕が貢献できそうなDPの見た目のGが放置されてることに気がついたので考える。パッと見解けそうな気がする。

実装する、バグる。　辛い。

ここでHyadoがDを解けたと主張(結局誤読だった)、hotmanがF書くよということでD/F/G3並列で書いていた。

[4:09] F WA [4:29] F WA

G問題よくよく問題文を見るとコストの説明を色々読み落としてることに気が付き修正→サンプルが合う。

自信満々でsubmit!!!→ G WA(4:35)　どうして…

[4:38] D WA　終わった……

[4:56] F WA　終戦………

かっつ「S==Tのケースちゃんと考慮してますか」

hotman「あっ」

一同「まだ間に合う！！行け！！！」

f:id:KKT89:20200917021418p:plain

おいおい　どうやらコピペ範囲をミスったらしい　頼む

f:id:KKT89:20200917021549p:plain
感動のAC

一番の盛り上がりでした。


感想

6完内最下位の36位でした。昨日のリベンジを果たされる結果に。

反省要素としては序盤に詰まってしまったことと、全体を通じてhotman頼りのチームになってしまってることですね…。少なくともG問題は自分が通すべきだったので反省です….。


3日間楽しいセットを運営の方々、作問陣の方々ありがとうございました！！