日立ヴァンタラプログラミングコンテスト2024(AtCoder Beginner Contest 368)
ヴァンターラ ヴァンターラ 愛の国 ヴァンターラ
問題設定がややこしい。
解法も「こうかな?」と思いついたものがWAやTLEになりやすく、
グラフの複雑さから、上手くいかないケースも究明しづらい。
「X2+…+XM が最小」という条件があるが、
「ある電車 i を余分に遅らせることで、他の j が少ない遅延で発車できる」なんてことはないので、
各電車について、時刻表通りではそいつに乗り継ぎ可能だった電車が全て到着し次第、すぐに発車してよい。
(または、遅延無しで発車可能なら時刻表通りとしてよい)
ある電車 i の遅延時間 Xi を計算したいとき、タイミングと、必要な情報を考える。
S_i 以降に駅 B_i に着く電車(T_j \gt S_i である j)がどれだけ遅延しようが、
それは「もともと乗り継ぎ可能でない」電車なので i の遅延時間には影響させなくてよい。
必要なのは、T_j \le S_i である電車のみの遅延時間である。
イベントソートで解ける。
(S_i,1,i),(T_i,0,i) を、全てまとめてソートする。
0,1は、出発/到着の区別と、同率なら到着の方が先に処理されるようにするためのもの。
ソートされたイベントを順に処理する中で、処理中の時刻を t として、以下の情報を管理する。
これで、適切なタイミングを守って更新が実現できる。
出発イベントの時に到着点の \mathrm{Arrival[B_i]} まで更新しようとしてしまうと、上手くいかない。
1 i x
の形式で与えられる。A_i を x に置き換える。2 i x
の形式で与えられる。B_i を x に置き換える。3 l r
の形式で与えられる。以下の問題を解き、答えを出力する。ありがちな解法で考えると、セグメント木に (A_i,B_i) なんかを乗せ、 集約値の区間最大値を取得!としたいところだが、 それまでの v の値によって最適な選択が異なってくる。
Ai = 10, Bi = 3 v=3 のとき v+10 = 13 > v*3 = 9 Aiの加算をした方がよい v=9 のとき v+10 = 19 < v*3 = 30 Biの乗算をした方がよい
よって、セグメント木として「区間の集約値を前計算しておく」ができず、この方法は使えない。
問題文最後の以下の条件を使用する。
出力すべき値が 10^{18} 以下ということは、
区間に含まれる B_i のうち 2 以上のものは60個以下ということになる。
2^{60} \ge 10^{18} で2以上の数を60回かけると超えてしまうし、A_i の加算によっても v は減らないので。
つまり、区間が長いクエリの時でも、区間内の B_i の大半は 1 が敷き詰められているということになる。
「1を乗算」は意味が無いので、B_i=1 の時には必ず「A_i を加算」を選んでよい。 そのような i が連続していれば、A_i の区間和としてセグメント木でまとめて求められる。
結局、v=0 から以下を繰り返せば良い。
A_i に対しては1点更新・区間和を求められるFenwickTreeやセグメント木などで管理。
B_i に対しては、B_i \ge 2 のindexのみを管理するSortedSetや、1点更新・区間maxのセグメント木などで管理し二分探索すればよい。
最大60回の繰り返しで、答えが求まる。計算量は O(N \log{N} \log{(答えの制約上限)})
なんか、感覚的に “クエリ” は “問い合わせ”、つまり「答えを知らないので教えて」という質問であることを想像するので、 こういう風な「実は問う側が答えを分かってることを前提とした解法」は、ちょっと発想の外から殴られたような衝撃を感じる。
まぁ、「計算途中で 10^{18} を超えたら“overflow”を出力して」という仕様だったら別に問う側が知ってなくても成り立つし、 そこから競技プログラミングの問題上、煩雑な部分を省略しただけとも捉えられるので、勝手な感覚ではあるんだけど。