Eが解けなかった。
コンテスト後のツイート
G セグ木二本使う。Bについてはmaxを、Aについては和をもつ。Bで1が連続するようなら、セグ木上の二分探索で次の1でない値を探し、そこまでのAの和を加算。
— titia (@titia_til) August 24, 2024
E - Train Delay
解説・解説放送を見てACしたが、ACした後も自分のコードが正しいか自信が持てず乱択で比較したりしてしまった。（正しかったよう）
出発時刻が早い列車から見ていこうというのは良いが、それ以外に何を持てば良いのかが難しい。
各駅ごとに、（本来の到着時刻, 遅れたときの到着時刻）を全て持ってそれら全てについて調べればもちろん良いのだがそれでは計算量が間に合わない。
ある列車について、その発車時刻より以前に本来の到着時刻があった列車全てについて調べ、遅延に原因する列車が特定できたとき、（調べた範囲の他の列車については忘れて）その列車についてのみ覚えておけば良い。ここが重要。
なぜそれで良いのかが整理できなかったのだが、それ以降の発車時刻のものは、今回遅延原因だった列車とは本来乗り換え可能だったから、ということ。
ここで迷う人は結構いるんじゃないかと思う。ただ、自分が図を描いたり色々してもしばらく理解できなかったことをこうやって言葉だけで書いても伝わらないとは思うけれど……。
0 件のコメント:
コメントを投稿