薊畑

Thistleのブログ

PCK2020参加記

PCKは早く同校制限をなくせ

全列挙と組んだ

 予選

あまり記憶にない。 1-5まで自分が担当して、その後は全列挙が割り振った問題を解く機械になる。 (1番でCEを吐いて精神がお辛くなった) 色々解いた後で12に特攻したが、HLDだと信じてしまい重心分解が見えず… 点数的には通っていたが、同校内4位で無事落選…

もう一つの本戦

実施前、「優勝しないと人権消失」とか言っていた。

3番までを自分が解いて、それ以降は予選と同じく投げられた問題を解いた。 3番が普通にわからなくてDPをしてしまった(頭が悪すぎる) その途中で、4番を全列挙が「これギャグじゃん」とか言いながら通していた。

6番と10番を全列挙が見て、「幾何ばっかじゃん!」というなどしていた。

とりあえず投げられたのが7だったので、実装する。 最初は桁DPかと思って考えようとするが、全列挙が「いや、8進数」と言ってきたので8進数で実装する。 実装途中で、最後に10進数に復号する必要があることが分かったので「は?」という気持ちになったが、筋肉をして通す。

次8を投げられたので、解く。 難しいんだろうなと思いながら見るとただの2番目の最短路問題だったので驚いた。 条件のミスで1WAを出したが、割とすぐにわかって通した。

この辺で2位だった。1位のチームに橙がいるらしく、ビビる。

問題が12番までしか存在しないと思っていたが、ここらへんで13番の存在が発覚する。やばそうなのでとりあえず見なかったことにする。

次に9を見たが、何もわからないので飛ばして12を見る。 見るからにJOIのバブルソートだったが、自分は考えただけで解いていなかったので後悔する。 Qが小さかったので平方分割+BITで通るやろ!という気持ちで実装すると通る。 (MLEが何回か出たが、闇をすると何とかなる)

12の考察中、全列挙が突然「10、区分求積したら通った!」と言い出す。 訳が分からなくなる。

この辺の時点で1位になって、2位と結構差がついていた。もう優勝では?と思い始める。

13番を見ると、全方位木DPで通りそうに見えるが、2~Nまでだと無理なので無理ということにして11番を見る。 全列挙が「これ多分3Nのやつ」と言っていたので、それをベースに考えると解けて、通る。 ここで残り20分くらい。優勝したなと思いだす。

最後は、全列挙が9番を考えていたので、「何もわかんねー」と言う担当をしていた。 2人とも「不変量は何か?」を考えていたので、解けるわけがなかった。(せっかく得意分野が違うんだから別方針を考えるべきだった。反省)

終了後、本戦勢を見に行くと同校内1位であることが判明した。 全列挙の10番が大きかったらしい。解いてくれてよかった…

同校制限をなくしてくれ。

感想

9番は解きたかったから悔しい。 全完チームがいるの、何?

同校制限をなくしてくれ