---
# System prepended metadata

title: JOI春合宿対策バチャ2025 Day1
tags: [精進, '2025', JOI, バチャ]

---

2022~2024を順列にしてランダムに並び替え、$P_i$年の春合宿Day1の$i$問目を入れてバチャをしました。  
結果は100-5-0で、終了から2:47秒後に2問目で86点、24:5秒後に2問目で100点を取れました。悔しい。全完できるセットだった...  

## [Two Currencies](https://atcoder.jp/contests/joisp2023/tasks/joisp2023_a)
並列二分探索をすればよいです。  
パスクエリはEulerTourをして、根から頂点Aまでの結果+根から頂点Bまでの結果-2\*根から頂点AとBのLCAまでの結果とすればよいです。  
また、逆辺は負の結果とすると根からある頂点までの結果はセグ木で簡単に求められます。  
これが難易度10初ACだったはず?(当時はMo'sで無理矢理通しました)  

## [Ski 2](https://atcoder.jp/contests/joisp2024/tasks/joisp2024_b)
まず既に上げているのに1つも前のに繋げないのは無駄なので、常に1個以上減ることを考えると高さの状態数は各$H_i$につき$H_i,H_i+1, \dots,H_i+N-1$しか有り得ないので$2N$になり、  
$dp[i][k][j] ←$ (標高$i$まで処理して$k$個の未使用があり、$j$個が標高未確定のときの最小値)  
とすると$O(N^4)$でDPができます。(なにやら算数ができていなさそうな記述がありますが、気付いていません。)  
さらに$k$が増えるとき$j$も同じだけ減るので$k+j$が一致するものの間で遷移することが分かります。なので、これをいいかんじに処理することで$O(N^3)$に落ちます。  
が、結局N=1のときにREを起こしたことで5点で終わり、その後解消することで86点になりました。また、標高の状態数が$2N$ではなく$N^2$なのに気付き考察をすると$j$が0になったときに地点が存在する$i$まで飛ばさせると状態数がNになるので$O(N^3)$になり、24:5秒後にACしました。  
想定解は算数をすることで状態数を抑えてました。確かにそうじゃん...

## [Misspelling](https://atcoder.jp/contests/joisc2022/tasks/joisc2022_c)
間に合わなかった 既ACです。