JOI春合宿2021参加記

JOI 2020/2021の春合宿(合宿ではない)に参加してきました。これで最後です。

競技は結構うまくいったと思っています。以下参加記です。

 競技前日まで

🦊のマスコットを買った、かわいい。後輩からもらったえびちゃんの上に乗せると更にかわいい。

f:id:QCFium:20210326112517j:plain

2日前くらいに原因不明の興奮で4時まで眠れなかったりして大変でした。多分春合宿とは関係ないけど特に心当たりもないので謎。

前日はABCの準備をしてました。最後にNTTとかLCTの実装とかの覚えなきゃいけないものを見直して準備完了。

この夜はよく眠れた

Day 1

行きの電車はJupiterとか春よ来いとか聞いてました。いつ聞いてもいい曲。

参加者の半分が橙以上なのおかしいやろとか言いながら競技会場に乗り込みます。

キーボード / マスコットの預けアナウンスがかかったたところでキーボードを忘れたことに気づきます。配給PCのキーボードはキー間隔若干狭いしいつも使ってるのとFnとCtrl逆だしhomeとendはメーカーが好き勝手なところに置くしで結構苦痛でした。しかもDay 2でキーボードを使うにはDay 1の解析中に預けないといけないのでDay 2もこれでいくのが確定です。嫌だ~~

配給される水がevianって名前でevimaさんだなぁとか考えてた。この水若干硬水らしくて変な味するんで普通にいろはすがいいです。(<-水筒持ってこいや)

問題はaerobatics, fever, foodcourtの3問。しょっぱなからOutput Only(aerobatics)出してきたのでちょっと意表を突かれました。一瞬見たけど保留してfeverを見ます。

例によって脳死で抽象化してこの問題NP困難っぽいよなぁとかまで考えたところで我に返ってちゃんと考察し始めました。各人間2通りの方向しか考えなくて良いのがまず見えてその後手を動かして考察してたら全員方向決まるじゃんって話になりました。

あとはシミュレーションするだけなのでどうせ変なダイクストラするのは分かってたんですが変なダイクストラの実装が重いのは目に見えていて、最初の考察ミスってたら沼なのでとりあえず2乗解を提出して部分点が出るのを確認しました。あとは頑張って実装します。正面衝突するときに相対速度が2になるの忘れてたのと、オーバーフローに悩まされたけど開始2.5時間くらいでACしたはず。

問題開けるときに視界の端っこに入ってfoodcourtがクエリ問題なのが見えたのでそっちを先に考えます。beatsじゃん並列二分探索じゃんとか言いながら実装して出すとTLE、冷静になってbeats要らんやんってなってただの遅延セグ木にしたけど若干TLEして68点、変な21点の部分点回収して89点。あとはちょっと望みがないしあと1時間切ってたのでaerobaticsに移行。

ここで戦略ミスをしたんですがaerobaticsのデータの傾向掴むためにデータの偏りを分析するプログラムを書いてしまいました。そんなのをしている時間があったら貪欲だのランダムをたくさん回すだの書いてる方がよかったです。まぁ仕方がないので最初のテストケースをbitDPで解いて確実に10点は取りました。

あと残りのケースに関して完全ランダムを書いて走らせたんですが、全ての3点組に対して角度を前計算していたせいでメモリ食いすぎてVMがフリーズしてしまいました。終了まであと7分だったのですが回復することなくコンテストが終了してしまいました。4番目のテストケースに対して実行中にフリーズしたため2番目と3番目のテストケースに対してはプログラムの取得がファイルとして残っていて、終了後に提出が認められ、3点を得ることができました。(コンテスト時間の延長は認められませんでした)

 

13 + 100 + 89 (aerobatics + fever + foodcourt) = 202として上々の出だしです。(1位)

SSRSがfoodcourt満点取ってて悔しかった

教訓

foodcourtで100を取れなかった原因は並列二分探索に走ったところで、以下のような問題が永続遅延セグ木か並列二分探索でしか解けないと思い込んでいたことでした。

数列Aに区間addがたくさん飛んでくる。そのあとA_iが初めてxを超えたのはいつ ?みたいな質問がたくさん飛んでくるので答える。(制約全部2 * 10^5)

ここにCodeforcesの並列二分探索の記事がありますが、これを読んでいたため例題を解く一番簡単な方法が並列二分探索だと思い込んでしまっていてそれ以外の解法を全く考えていなかったことは反省です。(それ以外の解法を全く考えなかったことを反省というよりはより計算量がいい解法を知らなかったことを反省かな)

https://codeforces.com/blog/entry/45578

 

あとキーボードは忘れるな。もう少し時間があってaerobaticsでも時間をとれただろうに。

 

Day 2

若干遅刻しました。(競技には全然遅れてないです)

行き聞いてたせいでギラギラが競技中ずっと頭の中流れてました。

今日の問題はescape route, road construction, shopping。一目見てどう見てもroad constructionが解きたいので噛みつきます。二次元セグ木のノード列挙して尺取りみたいなことする重~いlog2つ解を頑張って実装してN <= 10^5すらTLEを貰います。

定数倍高速化もタカが知れていることを悟ってちゃんと考察するとK番目だけまず求めてから残りを求めればいいことに気づきます。これもlog 2つだけど定数倍軽いだろうということで実装してちょっと定数倍高速化してAC

ここまではまぁ良かったんですが...

Shoppingも考察しますが何も分からないので後に回してescape routeの考察を始めます。しばらくすると70点解法(これは本当)が思いつきました。ここで僕はどういうわけか辺の追加や削除に対して最短経路を効率的に更新できると思ってしまって嘘の100点解を"思いついて"しまいました。dynamicなグラフの最短経路はまともに速くならないのを知っていたのに。しっかり実装して0点を取ってデバッグしている間にコンテスト終了。おしまいです

それはそれとしてescape routeのgraderがシェルからの手動入力受け付けてくれなかったのは不満です。(まぁ飛んで5分なんだんけど)

 

0 + 100 + 0(escape route + road construction + shopping) = 100

みんなescape routeの70取ってるせいでかなり後退しました。SSRSに抜かれて首位陥落。

グラフに辺が追加されたり削除されたりするとき最短経路は普通に毎回ダイクストラするよりまともに速くならない。二度と忘れない。

あとShoppingの小課題2でLがそのまま送れるのに気づかなかったのはさすがにちょっとマズいので反省。でも満点の考察を進めると部分点に盲点ができるのどうすればいいんだろ

解説ではroad constructionのlog 1つの解が説明されててすげーってなった

 

Day 3

この日はEidetic Imageがずっと脳内に流れてた。

www.youtube.com

 

この日から自分のキーボードが使えるのでちょっと攻めた

ancient machine, bodyguard, mettings 2の中でbodyguardから考察を始めます。

制約2800, TL 25 sってヤバいなとか言いながら45度回転 + DPは見えて実装、部分点をたくさんもらいます。残りをCHTで高速化してAC。さすがに怖かったのでN^2側にはlog付けなかった。(切片単調でクエリが非負のやつしかこないからできる)

meeting 2を見てちょっと考えると考察が終わったので重心分解してAC。解説によると重心分解しなくてもいいとのこと

残り2:50くらいをancient machineに費やせるので愚直チェッカーとか書きながら地道に考察を進めて、多倍長実装して残り15 分でAC。結構泥臭かったので本当に想定か疑ってたけど想定だった。(ただちゃんとやると64bit超えるの扱わなくて済むらしい)

余った時間でマインスイーパー。斜め後ろに競技者がいないので堂々とできる。ところでこれ運ゲーをことごとく外すんだけど「踏んだところに爆弾があっても矛盾しないなら最初からあったことにする」みたいな処理入ってませんか ?

 

100 + 100 + 100(ancient machine + bodyguard + mettings 2) = 300

全完はかなり嬉しい。首位奪還

 

Day 4

event 2から開く。この日はなんか前半2時間くらい眠くて頭がまじで回ってなくて危機を感じたけどその後はちゃんと働いてくれてよかった。

ってわけで考察スピードが遅いけど1.5時間経ったころには考察完了。2時間ちょいでAC。後で2006年くらいのAPIOで既出みたいな話を見たけどさすがに知るわけない。

次にworst reporter 4を開けて考察。functional graph(小課題途中までは木)なことに気づくのに30分くらいかかった(アホ)

疎なセグ木のマージテク、知ってはいたけど使ったことなかったし忘れてたので平衡二分木書いてごまかす。解説によると階差とればmapだけでいいらしい。木の小課題は全部取って、functional graphの場合も解けてたけど時間微妙だったからnavigation 2も見て考えることに。

残りをnavigation2 に充てる。落ち着いて考えたら良かったんだろうけどworst reporter 4の実装が残ってたんであんまり深く考えられず、36点。

最後にnavigation 2の満点を実装。小課題取るために書いたコードを消し忘れてて最後謎のTLEが出てて20分くらい失ったけどまぁAC。

 

100 + 36 + 100 (event 2 + navigation 2 + worst reporter 4) = 236

そこそこ

yutoさんにnavigation 2で39点くらい取られて負けたけどまぁ満足。(改善の余地はある)

終結果です。

2日目は大反省だけどそれ以外は結構よさげかな... ?

 

f:id:QCFium:20210326161745j:plain

来年以降行く人へ

キーボードは必要なら絶対忘れるな。ちゃんと寝て。

覚えなきゃいけないものは覚えましょう。僕はNTT(畳み込み)をブラックボックスで使ってるので実装暗記みたいなことをしています。これの賛否はありますが直前までに理解してないものは仕方ないので覚えちゃいましょう。シラバスから外れててもぶん殴りに使えるのでいいです。(ただし濫用に注意。複雑なものほど実装に時間がかかるしバグるし定数倍重いので常により簡単なのでできないか考えること)

おいしい部分点は確実に取りましょう。分かる部分点だけで70点とかあったらそれ最初に取っておいた方がいいと思います。(escape routeなど)

今回は部分点の配点気持ち高めだからあんまりなかったけど逆にさんざん実装して10点みたいなやつは後回しにした方がいいと思います。

今回のセットに特有かもしれませんが定数倍の感覚はあると便利です(僕は鈍かった)

 

感想

問題はかなり面白かったです、ありがとうございます。

春合宿に来るとこの期に及んで典型っぽいのが一日一個くらい身につくので未熟さを感じます。失敗を無くして安定させていきたいですね。