Osmium_1008のブログ

コンテストの感想とかどうでもいいこととか書き溜めるかもしれません

JOI'22 二次予選参加期

はじめに

Osmium_1008のJOI参加期にブログ名変えた方がいい気がしてきました。例によってむっちゃ適当です。

結果

問題名 得点 経過時間
A 100 00:01:27
B 100 00:09:07
C 100 00:30:37
D 100 00:58:43
E 100 01:49:44
計 500 01:49:44

序盤で詰まらなくなってて成長を感じます。(誰)

行動

競技前後にどのようなことを考えていたかでです。

競技直前

コーヒーを飲んだ上で手元にポカリとラムネとチョコを用意しました。あとノートも

競技中

A問題

どうみてもやるだけなのでやります。

ここまで1分ちょい

B問題

これも適当にDFSで通りそうなのでやります。

ここまで10分

C問題

一方向ずつ考えて合わせるで通りそうなことがわかるので実装すると普通に通ります。

ここまで30分 なんか今回簡単になったなーとか思いはじめます

D問題

普通に前回と前々回を index とする DP で通るので通します。(次見る場所と前々回の見る場所を同時に動かせることを気付くのにちょっと時間かかった)

ここまで1時間弱 え

E問題

とりあえず自明な小課題2を通してから考えると切り離せるようにしたUnionFind(名前を知らない)(切り離しは

size[par[i]]-=size[i];
par[i]=i;

とかで実現できる←(12/12 18:00追記)多分これsizeあたりでちょっと計算量落ちてる けど無視) を使って

  • 各州内の道路はさきにマージしておく。
  • 州のペアごとにクエリを分ける。
  • 2州の間の道路をマージしてクエリを処理する。(判定するだけ)
  • 切る

をやるだけで O((M+Q)log²NlogQ) とかになるので(Map使いまくったりしてなければもっと落ちるはず)通りました。

ここまで1時間50分

競技終了後

いつものスプレッドシートを見るとやはり全完が結構多いのでボーダー417点ぐらいかなーと謎の予想を立てましたが 通る人数160人も確保されてることを考えると多分200点台のどこかで通りそうな気もします。

今年はノートはDで index の足し引きを考える時にちょっと使いました。

感想など

3完+αぐらいかなーと予想してむっちゃ覚悟してたら割と早く全完できたので結構拍子抜けしてました。 やはりノート書いた方が実装早くなりそうとも感じました。

提出したコード(Gist)