JOI 2021/2022 本選参加記

JOI 本選に参加してきましたギリギリ春は通ってそう（行くとは言ってない）

得点獲得の記録

合計 346 点

それはそう

これ難易度 5 ってほんと？の気持ちです　ダイクストラと同レベルは、嘘じゃないかな…

A が始まって B に取り掛かりますどうみても二分探索なのでコードを書くも、0 点が出て困惑

考察ミスを疑って小課題 1（max の min をとるだけ）を通すと通るので、バグを確信結局オーバーフローでした

Cyanmond が、本選前に書いた気をつけることリストに「kaage」って書いてたおかげで気づけたらしくて、先輩として嬉しいです（全く嬉しくない）（参考 : JOI2021本選参加記）

嘘貪欲だった。$B[i]$ は昇順に取った方が良いのは当たり前なのだが、途中で取らないという選択肢がないのは、やばい（やばいので）

嘘貪欲をちょっと修正したら 10 点取れたが、嘘貪欲に違いはない。

嘘貪欲に気づき、DP を考える。そもそもメモリ制約に DP と書いてあるんだから最初から考えろよ

$B$ の昇順に考えるべきなのはそうなので、ソートして考えるとわりとすぐに分かる。得る協力者の数を決め打ちして、

$dp[i][j][k] = i$ 番目までで、$j$ 人の協力者を得て、$k$ 個の州を取るまでにかかる時間

とすると、$O(N^2K^2)$ で解ける。

まず、部分点を考えると、添字 $k$ がいらなくなる。

取らない州がある場合も、取らない州のあとに協力者を持ってくるのは明らかに損なので、「協力者と票だけ取る州の混合部分」と「票だけ取る州と何もしない州の混合部分」に分けることができる。そうすると、結局どんな場合でも添字 $k$ はいらなくなって、あとは票だけ取る州を貪欲に決めればよくなる。

こうして $O(NK^2)$ まで落ちるので、満点

自明 $O(N^2M)$ で辺を張って、お好きなように

自明、これは難易度 4

ほぼ自明、$O(H^2W^2)$ で長方形を列挙して、$O(HW\log HW)$ で判定すると、$O((HW)^3 \log HW)$ で、まあ通る

log 落とすとあと 5 点取れるらしい

残り 30 分くらいで、行ける場所が区間になるのに気付く大急ぎで実装して取る

もとの区間の計算にセグ木を使うとこれが取れる

あとはどう考えてもダブリングするだけで満点なのだが、時間が足りず

B のバグに時間かけたり C の考察が遅かったりするから ARC でいつも失敗するんですよ！？！？！？！？