いわゆるJOI2023春合宿というやつで情報オリンピックの代表を決めるやつです。 3問5時間のセットを4セット全部走りました。 春合宿の参加者はライブラリや検索が禁止なので自分もそれに則ってやりました。 ただ環境はいつも使ってる VSCode 等を使いました。
問題概要はこちらから
Day 1
A currencies, B festival2, C passport,
24:00:00 start
0:29:10 C 0
問題文を勘違いしていて実装したので当然 $0$ 点
1:12:01 A 100
銀貨を使う枚数が少ない関門から貪欲に銀貨を使えば金貨の残る枚数を最大化できる。
どの関門まで銀貨を使えばいいかを並列二分探索することで求めることができる。
問題を見てすぐに解放が思いついて、そんなに難しくなかった。が、実装が大変そうなので C の実装をした後にやった。
2:01:39 B 51
区間スケジューリング問題の答えが前から貪欲にとったときと同じになる並び替え方を求めればいい。
状態をまとめることで $3$ 乗のdpになった
2:53:12 C 0
3:00:30 C 54
$dp_{l,r}$ を $l$ から $r$ まで行ける状態の時、後何回パスポートを取ればいいかという $dp$ を 01BFS の要領でやると $O(N^{2})$ になる。
点数は
100/ 51/ 54/205
終わった後にライブスコアボードを見ると 100/10/100/210 をとっている人が多かった。
また、ぱっと見で日本人が見つからなくて寂しかった。
Day 2
一昨日はトヨタコンが、 昨日は TOEIC -> TechFulの残り -> ABC -> Day1 があったため、疲れで頭痛がすごかったが、少し治まったところで走り始めた。
A conveyor, B council, C mizuyokan2
20:30:40 start
0:47:06 B 16
結局以下の問題が解ければいいところまではすぐに気がついた。
長さ $N$ の $0$ 以上 $2^{M}$ 未満の整数列 $A,B$ が与えられるので、
$$min_{i\neq j}(popcount(A_{i},B_{j}))$$
を全ての $i$ について求めてください。
よく分からなかったので $O(N^{2})$ を提出する。
1:09:59 C 15
この時点でやべーってなったので簡単に取れる部分点を回収することにする。
普通にdpすれば 2 乗にはなるので実装して提出。
1:26:46 A 15
葉っぱから順番に辺の向きを決めることができる。
わかったらその辺を子供から親の向きにすることで上の辺を調べるときにこの辺を辿ることがなくなる。
2:24:33 B 100
上記の問題をちゃんと考えるとゼータ変換を向きを変えて2回すればいいことに気づく。 具体的には $dp_{i}$ を $A=i$ のときの答えとすると、 $dp_{!B_{j}}=0$ としてゼータ変換の要領で 各 bit ごとに $1\rightarrow 0$ の向きにコスト $0$ で更新した後、 $0\rightarrow 1$ の向きにコスト $1$ で更新すればいい。
$i\neq j$ については単純に答えを上から二つ持てばいい。
3:24:10 A 25
この部分点は木が線のときのものだが、距離 $3$ ごとに荷物を置くことで木が高々長さ $4$ のグラフに分解されるのでそうしたら適当にやればいい
4:45:33 A 100
直径が小さいときは全ての葉についてその葉につながっている辺について向きを決めることで直径の半分くらいの回数で求まるがこれでは線グラフのときにダメ。
線グラフのときのように頂点をうまく置くことでたくさんの辺について決め、グラフを分解したい。
そこで荷物を置く頂点を以下の条件を満たすように決める。
- 根ではないかつ、子孫のうち距離 $2$ 以内に荷物の載っている頂点は存在しない。(向きが決まっている辺は切れているものとして考える。)
これは BFS 逆順に 木DP をして決めた。
計算量は何にも分からないが、 $30$ 回以内に収まらないものも特に思いつかないので、実装して提出するとなんか通る。
点数は
100/100/ 15/215
Aはなんか面白かったです。想定解とか計算量が気になる。
Day 3
A chorus, B cookies, C tourism
14:00:00 start
0:28:45 A 0
$K$ の値で下に凸になりそうなので、エイリアンdpとか monge みたいなことをすればいい。
$[l,r)$ 匹目のビーバーを取った時のswapの回数は $i$ 体目の アルトの前にいるバスの匹数を $C_{i}$ とすると $\sum_{i=l,...,r-1} \max(0,C_{i}-l)$ となるため、2乗のdpができてこれを実装したけどなんかバグったのでとりあえず放置
1:02:08 B 0
1:06:49 B 70
これは似たような問題をAtCoderで最近見ていた
なので、特に何も考えなくても $O(M(\sum A)^{2})$ のdpが思いついて実装したら $M=1$ でバグらせてたため $0$ 点。直して $70$ 点
1:27:38 A 61
バグが見つかったので直した
2:17:14 C 28
2:25:11 C 35
オイラツアー順に並び替えていれば辿るべき頂点の数はわかる
辿るべき頂点は数列の範囲で与えられるので Mo を使うことで $O(N\sqrt N \log(N))$ になるので実装すると $28$ 点しか取れなくて、線グラフのときの部分点も取れてなかったので回収
3:04:53 A 100
dp をよくよく観察するとこの間の TUPC みたいな感じに一次式の最大値を求めるような形式で求めることができる。
仮に全ての $i$ に対して $i\leq C_{i}$ が成り立っていると仮定すると、
$dp_{l}+\sum_{i=l,...,r-1} \max(0,C_{i}-l)=dp_{l}+(r-l)l-\sum_{i=0,...,l} C_{i}+\sum_{i=0,...,r-1} C_{i}=rl+(dp_{l}-\sum_{i=0,...,l} C_{i}-l^{2})+\sum_{i=0,...,r-1} C_{i}$
つまり $r$ に関する一次式になる。
なので、convex_hull_trick に似たものを実装すればいい。加える $1$ 次式の $x$ の係数が短調減少なので凸包の要領で加えていけば良い。
そして、最小値を求めたい $x$ の値は単調増加なので二分探索する必要はなく、 dp の計算量は $O(N)$ になるので、全体で $O(N\log N)$
3:22:12 B 25
3:33:34 B 25
3:38:00 B 85
$dp_{i,j}:=$ 大きい方から $i$ 番目までの箱の大きさの和が $j$ となるような箱の詰め方の $i$ 番目の箱の大きさの一例
この dp は普通にやると$O((\sum A)^{2}M)$ になるが、調和級数の考え方で $O((\sum A)^{2} \log M)$ に落ちる。
3:48:04 C 35
4:03:09 C 35
Mo を適当に高速化したりとかしたけど何にもなく。
4:21:22 B 85
4:33:11 B 100
小手先の高速化をしたらなんか通った。
具体的には、今まで $i$ の探索範囲を $\sum A$ までしていたのを $i$ 個で詰められることが確定したら終わりにしたり、 詰められないことが確定したら切ったりなど 。
点数は
100/100/ 35/235
Cで満点をとっている人が多くて悲しかった。
Aの満点がライブスコアボードでは比較的少なかった気がする。 日本人優遇問題？
このセットは知識で殴った感じがする。
Day 4
A battle, B guard, C travel
21:00:00 start
1:12:19 C 0
1:17:57 C 0
1:21:40 C 0
1:32:14 C 0
1:35:17 C 100
A,B が競プロ感なくてよく分からなかったため、 C を見たらいつもの競プロの感じがしたので考察する。
考察すると、どこからスタートしても向きを変える回数は $O(\log X)$ で収まることがわかったので、 どの場所で向きを変えるかをseg木の二分探索を用いて求めた。
計算量は $O(Q \log QN)$
TLE が怖かったので、 min_left や max_right を実装したが、割と余裕そうだったので別にいらなかったかも。
1:52:31 A 18
2:29:07 A 45
2:47:28 A 57
$(i+j)$ を $8$ で割ったあまりでマスを場合分けすると、使えるマスは $8$ マス中 $6$ マス以上あるので、8文字の情報を入れることができる。
これ以降はいくつかのマスに決められた値を入れることで $X,Y$ を確定させることを考えた。
######## #AAAAAAA #ABBBBBB #AB..... #AB..... #AB..... #AB..... #AB.....
このように埋めると $X,Y$ が確定でき、残りの $25$ マスを自由に使える。
この AB はもっと減らすことができて、
######## #BBBBBBB #ABB...A #A...... #A...... #A...... #A...... #A......
この配置でも $X,Y$ が確定できる。 よって残りの $33$ マスを自由に使える、
これ以上減らせるか考えたが、 $X,Y$ の候補は $64$ 通りで、上の例の AB の数はそれぞれ $7,9$ 個で、 $64-1=7\times 9$ であることからこれ以上少なくできないと判断した。
追記
$1$ つの AB の組に対して、禁止になる $X,Y$ の組み合わせが $1$ つしかないと思っていたが実際に考えると $2$ つのときもあることがわかった。
例えば上の例で3行目2列目の A と2行目2列目の B は $(X,Y)=(1,0),(7,0)$ の二つの可能性を潰している。
よってこの理論的には $33\leq(Aの数) \times (Bの数)$ が十分条件でありことがわかった。
つまり、 AB の数は合わせて 12 個までは可能性があるということだ。
自分は 13 個が限界だった。
######## #ABBBB.. #A....A. #A....A. #A....A. #B....A. #....... #.......
$L^{*}=36$ で 62 点
3:05:49 B 12
3:12:29 B 25
3:18:28 B 37
3:29:59 B 50
4:01:12 B 58
4:02:18 B 76
適当な予想をつけ提出すると最初のケースが通った。
その後、どっかを根として頂点ごとに (子の数) $\times$ (混雑度) の和の最大値が答えになると予想し、線グラフの時に求めると通る。
また、この値は頂点ごとに (次数-1) $\times$ (混雑度) の和に混雑度の最大値を加えたものと同じなので、普通の木の場合も求まる。
普通のグラフのときは多分最小全域木で、上記の考察から辺の重みは端点の混雑度の和でいい。
$Q=0$ のときは以上で終わり。 $Q\neq 0$ のときは元ある辺以外にもはって良い場合の最小全域木を求める必要がある。
加える辺については混雑度の最も低い頂点と結べば良い。その頂点を根として
$dpx_{i,j}$ を $i$ 以下で $j$ 本辺を切った場合のコストの減少値
$dpy_{i,j}$ を $i$ 以下で $j$ 本辺を切ってかつ、 $i$ の連結成分のうちの一つと根の間に辺をはった場合のコストの減少値
とすれば二乗の木dpになる。これで76点(制約を勘違いして一回58点を取ってしまった)
部分点であるのを良いことにして考察を進めた感じがある。
得点は
57/ 76/100/233
まとめ
合計で $888$ 点でした。オンラインコンテスト上では $16$ 位です。
春合宿の問題はパッっとみで難しくて敬遠していたのですが、今回のセットはどれも 5 時間考えたり実装してて楽しかったです。
