# JOI本選25 参加記 ## はじめに この記事を書き始めたのはアピールの後だから具体的な時間なんも知らん！ （追記：UpSolveのときに見れたけどめんどいから書き足さん！） ## 本選中の記録 ### A まあ ### B まあセグ木でやるだけ ### C 見た目が怖いけどまあ始点が関係なくて、終点見れば左端ごとに右端の最小値がわかる。$P$ がバカでかいことを見逃していたがとりあえず $P$ が小さいのを投げて正当性を確認する。$P$ がでかいのは座圧すればよいだけで、ほどなくして通った。 ### D しばらくすると無視するのを選んだら伸ばすのは貪欲でいいことがわかって、長さ同じのは生まれないからbit列で管理することを思いついた。 bit列の中で下位互換を持たないことを思いついて、計算量が $O(N2^{\max(A)})$ より抑えられなかったがめちゃくちゃ定数倍が軽そうなんでとりあえず実装してみるとなんか72点入った。しかもTLEしたやつもかなり時間が間に合いそうだった。 というわけで定数倍高速化するが、なぜか最後の小課題は全部通っているのに最後から2番目の小課題の中の108ケース目だけ通らない。時間で打ち切って、答えが21以下なので1/21で当たる宝くじを投げ続けると通った。こんなのが100点でほんとすみません… (追記：MtSakaさんにこの方針の満点コードを見せてもらったので、重複削除を2重ループの中でやってたのをuniqueにすると通った、uniqueで要素数が減る恩恵の方がでかいからそれはそうか) ### E 木が解けそうな気がしたが、考えれば考えるほど嘘っぽいので棄却。 小課題1と2は自明で、3も一番手前の始点を見て管理するとまともな解法が生えたので投げたら通った。4も3をかなり応用すれば解けそうなので実装するが、この時点ですでに55分とかだった。当然間に合わずに終了し、その30秒後くらいに提出できる状態になってしまった。しかもあっていた。 --- というわけで100-100-100-100?-25。D通すのが再現性なさすぎるのでかなりあれだがまあアピールもなく確定したのでセーフということで… あまり誇れないが銀賞っぽい？ぷらにゃさん強すぎる