JOI 2021/2022 本選参加記

追記

本選通ってた．俺の勝ち！

合計点

ID	Score
A	100
B	100
C	77
D	8
E	19
Sum	304

非公式順位表によると 304 点は 9 人いるらしい．304 点を落としたら春合宿の人数多くした意味ないので，32 人くらいなら 30 人超えてもセーフってことにしましょう．

304 点以上が非公式順位表で 29 人，300 点以上が非公式順位表で 30 人，恐怖の C 満点潜伏 er が一人いるので，怖い．

反省

競プロあんまり触れてないまま本選に出たけれど，一応レート相応の点は取れたのでよかった．

ところで本選突破のハードル上がってませんか？人数増えたけど要求されているレベル高いままと感じた．

春合宿は 30 人くらいいたほうが楽しいと思うので，通せ．

難易度は，5-6-10-10-?? だと思っています．

以下問題ごとに．

A, B を割と速攻で通したのはよかった．

C も嘘からすぐ復活して，77 点とるまでの流れはよかった．が，$O(N^{2}KlogN)$ にこだわってそのあとかなりの時間を使ったのはよくない．TL 1.6s なのと， $ 500 \cdot 500 \cdot 500 \cdot log(500) \fallingdotseq 1.1 \cdot 10^{9} $ で微妙と思ったけど $log$ 解法捨てるべきだったのかも．

D, E はあんまりうまく解けず．C の $log$ 解法に粘って，残り 1 時間半位になった後，安全策で部分点一個一個死守しにいったけど，D はもうちょっと考えるべきだったのかもしれない．解ききれない問題があったときに頭をリセットできないことが分かった．

A: インターカステラー

去年に比べてめっちゃ簡単になっているように感じる．

二分探索で終わり．7 分！

f:id:RheoTommy:20220213202724p:plain

B: 自習

去年に比べてめっちゃ簡単になっていて，うれしい！

これまた二分探索すれば，どうせできるので適当にちゃちゃっと書くと WA る．

f:id:RheoTommy:20220213203008p:plain f:id:RheoTommy:20220213203104p:plain

小課題 1 で WA っているのがわかるので，とりあえず

10 1
1 1 1 1 1 1 1 1 1 1

を試すとバグる．デバッグですぐオーバーフローに気づき，修正．

f:id:RheoTommy:20220213203521p:plain

A, B 合わせて 30 分！めっちゃ順調！

C: 選挙で勝とう

最初の考察

$B_i$ を選ぶなら最初に全部選んでしまったほうがいい
$A_i$ しか選ばないなら，最後に昇順に選べばいい
$B_i$ も選ぶなら小さい順でいいじゃん
- 嘘です

これに基づいて協力者数全探索で終わりじゃんっていって提出．当然 WA.

f:id:RheoTommy:20220213204533p:plain

A_i B_i
--------
1 109
100 101

みたいなときに嘘だなーってなるので，もうちょっと考察を進める．

$B_i$ を選ぶなら最初に全部選んでしまったほうがいい
$A_i$ しか選ばないなら，最後に昇順に選べばいい
協力者数を $K_i$ で固定すると，$\frac{B_i}{1} + \frac{B_j}{1+1} + \cdots + \frac{\sum A_k}{K_i}$ の最小値を求める問題になって，DP で解けそう．
選ぶ $B_i$ に関しては当然昇順がいい．

そこで，$B$ をソートして協力者数 $K_i$ の時の答えを

$dp[i][j][k] = 州を i 個見て，協力者を j 人集めて，票を k 票集めた時の最小時間$

で求める．これで部分点 1, 2, 3, 4, 5 が取れて 66 点．

f:id:RheoTommy:20220213205528p:plain