読者です 読者をやめる 読者になる 読者になる

/home/cympfh/

数式を $$ で囲んで書いてますが面倒くさいので、いちいち、はてな書式にしたりしません

D問題: トレジャーハント - AtCoder Beginner Contest 035 | AtCoder

プロコン

Sun Mar 27 00:37:32 JST 2016

ABC 035 - D問題

問題

枝に時間コストのある有向グラフが与えられる. ノードは 1 から N まであって、N は 1e5程度. ノード 1 からちょうど時間  T を掛けて枝を巡ってノード1に戻ってくることをする. ただし任意のノードでは0秒以上自由に滞在してよい. また各ノード i には 1 以上の滞在ポイント A_i があって、ノード i に時間 t だけ滞在したとき、滞在ポイントが t \times A_i だけ溜まって加算される. これの合計を最大化したい.

解法

いつも滞在時間をゼロにするなら、ただのパスを巡るだけの問題である. 二箇所以上に滞在するのは無駄だと分かる. それは例えば異なる二箇所に注目して

 A_i t_i + A_j t_j \leq \max(A_i,A_j) \cdot (t_i + t_j)

ということ. もちろんゼロ箇所に滞在するというのはおかしい. スタート地点でずっと滞在すれば少なくとも 1 より大きな滞在ポイントが得られるから.

以上から滞在箇所はちょうど 1 つである. ノード u だとする.

1 \rightarrow uu \rightarrow 1 を巡る最短時間を計算して、残り時間を一杯、ノード u で滞在したときの滞在ポイントを P_u とする. もちろん巡るだけで時間が足りない場合もあるのでそこは適当に処理. で、 \max_u P_u が答え.

一頂点から全頂点まで (1 \rightarrow u) の最短時間は、ダイクストラ法による. 一番素朴なダイクストラ { O(V^{2}) } で、これだと、今は遅い. 優先度付きキュー (あるいは二分ヒープ) を使うことで、O((E+V) \log V) になる. 問題の制約をよく見ると、E のサイズも 1e5 程度と制限されてるので、こちらで行けるのだと想定が出来る.

帰り際の時間を計算するために、「全頂点から一頂点」(u \rightarrow 1) の最短時間が必要であるが、本当に全頂点からダイクストラをすると頂点の自乗以上の時間が必要なので遅い. しかしゴールは決まってるのだから、逆辺を辿るダイクストラだと思えば良いだけ.

参考になるであろうリンク

解答

本質的でない所

入力を受け取る部分を自前で書いてたんだけど、それがおっそくて、 バッファなんてキューにすべきだと前から分かってたはずなのに調べるのを忘れててただのベクターにしてた (pop O(n) かけてた) のが原因でずっとTLEしてた. Vec の確保が遅いのか?と悩んでたけど、これは普通にヒープに領域確保するので遅くない.