AtCoder Beginner Contest 250 G,Ex問題メモ

AtCoder Beginner Contest 250

G - Stonks

• ある銘柄の今後 $N$ 日の株価が $P_1,...,P_N$ で与えられる
• この株は、1日に最大1株まで売買できる（しない日があってもよい）
  • 売るときは、株を1株以上持っていなければならない
  • 現在、所持金は十分あり、株は全く持っていない
• $N$ 日後に可能な所持金の増加額の最大値を求めよ
• $1 \le N \le 2 \times 10^5$
• $1 \le P_i \le 10^9$

1日1株までしか売買できない。

$N$ 日時点で現金化してない株を持っていても仕方ないので、売らない株は買う必要が無い。

よって、株をその日に買うかどうか決めることはしないで、 とりあえずリストに貯めておいて、必要になったら過去に遡ってまだ売買していない日の中から選んで買い、その日に売ることができると考えると、見通しが立ちやすい。

貪欲に考える。1日目から順に以下を更新していく。

• $buy$: まだペアとなる売り日の決まっていない、買い日の $P_i$ のリスト
• $sell$: ペアが暫定している売り日の $P_i$ のリスト

$i$ 日目について考えるとき、以下の行動を取れる。

① $buy$ の中に、今日の価格 $P_i$ より安い日があったなら、その最小値 $P_{buy-min}$ で買い、今日 $P_i$ で売ることで、 $P_i-P_{buy-min}$ の利ざやを得ることができる。

• $buy$ から $P_{buy-min}$ をpop
• $sell$ に $P_i$ を追加

② $sell$ の中に、今日の価格 $P_i$ より安い日があったなら、その最小値を $P_{sell-min}$ として、 「$P_{sell-min}$ の日には売らず、持ち続けて $P_i$ で売ったことにする」ことができる。
その場合、既に獲得した利ざや $P_{sell-min}-P_{buy}$ と、後から変更した行動による利ざや $P_i-P_{buy}$ の差分、 $P_i-P_{sell-min}$ だけ、追加で得ることができる。（$P_{buy}$ の具体的な値はわからなくてよい）

• $sell$ から $P_{sell-min}$ をpop、$buy$ に移す
• $sell$ に $P_i$ を追加

③ どちらも可能な場合は、より得する方（$P_{buy-min}$ と $P_{sell-min}$ の小さい方）を取る。

④ どちらもできなければ、$buy$ に $P_i$ を追加する。

$buy$ や $sell$ は優先度付きキューで実装するのがよい。

ただ、正当性は未証明。

基本は上記と同じだが、実装しやすい解法。優先度付きキュー1本で可能。

上記で、一度売ることにした $P_i$ は、最大2回まで（擬似的に）買う側として取り出されうる。

• (買う方, 売る方)
• ①売る方としてペアになるとき
  • $(○、P_i)$ 差分をゲット
• ②後々、より高い価格で売れる日があり、買わなかったことにするとき
  • $(P_i, ○)$ 差分をゲット
• ③さらに後で、より高い価格で売れるとき
  • $(P_i, ○)$ 差分をゲット

②と③とで、答えへの寄与の計算方法（差分）は変わらない。

なので、1つの優先度付きキューで、

• 売るためのペアがなかった場合は、1つだけ追加
• 売るペアがあった $P_i$ は、2つ追加

とすると、優先度付きキューの最小値が $P_i$ より小さいかどうか判定し、小さければ最小値を取り出してペアにする、という処理の繰り返しのみで正しい答えが求まる。

Python3

Ex - Trespassing Takahashi

• $N$ 頂点 $M$ 辺の重み付き単純連結無向グラフ
  • 辺 $(u_i,v_i,c_i)$: $u_i$ と $v_i$ を結ぶ辺があり、通るのに $c_i$ 分かかる
• 頂点のうち、頂点番号 $1～K$ の $K$ 個には家がある
• 以下の $Q$ 個のクエリに答えよ
• クエリ
  • $x_i,y_i,t_i$ が与えられる
    • $x_i,y_i$ は家のある頂点番号（$1 \le x_i,y_i \le K$）
  • 高橋君は、家のある頂点を1度も通らずに連続で $t_i$ 分を超えて移動し続けることができない
  • $x_i$ から $y_i$ までたどり着けるか求めよ
• $2 \le K \le N \le 2 \times 10^5$
• $M \le 2 \times 10^5$

DijkstraとUnion-Findの複合。

2つの $t_i \le t_j$ なるクエリで、$t_i$ の時に行けていた $x_i,y_i$ が、$t_j$ で行けなくなることはない。
よって、クエリを $t_i$ の昇順にソートすることが考えられる。

以下のようなことができればよさそう。

• 経路探索などで、家のある頂点 $a$ と $b$ が現在のクエリ $t_i$ 以内で行けることがわかったら、Union-Findで $a,b$ をつなぐ
• $t_i$ 以内で行ける家のペアが無くなるまで繰り返し、いったん打ち切る
• Union-Findで $x_i,y_i$ が連結かを調べることで、クエリに答える
• 次のクエリ $t_j$ の時は、経路探索はさっき打ち切ったところから再開する
  • 毎回最初からやってたらTLEなので
• 繰り返す

これらをどう実装するか考える。
家はたくさんある場合があるので、各家を始点にした場合それぞれでDijkstra……なんてやってられない。

多始点Dijkstraなどで、各頂点が、「最寄りの家」から何分かかる位置にあるか、は一斉に計算できる。

そして、少し考えれば、各頂点は「最寄りの家」からの距離さえ記録しておけば、 2番目、3番目に近い家からの距離は記録せずとも、各家のペアが $t_i$ 以内に到達可能かは判定できる。

家1 -- 5 -,  ,- 8 -- 家3    ti = 13
           ⓥ
家2 -- 7 -'  `- 9 -- 家4

ⓥの最寄りの家からの距離は、家1からの「5」。
いま、家3からの距離8の更新がDijkstraのキューから取り出された場合を考える。

家3からⓥまで「8」＋ ⓥの最寄り家1からの距離「5」 <= 13
なので、家1と家3は ti=13 のもとで連結させられる。

最寄り家1に寄ることで、家1と連結済みの家には全て到達できる。
家2から家3へも到達可能となる。

一方、次に家4からの距離9の更新がDijkstraのキューから取り出されても、
家4からⓥまで「9」＋ ⓥの最寄り家1からの距離「5」 > 13
なので、連結はさせられない。
実際、家1～3のどれとも、家4からは ti=13 分以内に到達できない。

上のように、各頂点に2つの家から到達できれば、その和で2つの家同士が連結か判定できる。
そして、その判定に必要なのは、探索の前線となるキューに貯まった更新と、「最寄りの家」からの距離である。

これで、記録するメモリ空間 $O(N)$ で、家間の距離を求めることはできる。

家の距離は上記の方法で計算できるとして、 どこまで探索を続けて、どこで打ち切るか、という問題がある。

また、キューから取り出される更新に関して、 「$t_i$ で有効な更新が、無効な更新より後に取り出される」ことにも対処しなければならない。

どういうことかというと、例えば、以下の2つの頂点に対する更新がキューにあったとして、

ti = 13

家1---11---> ○ <-- 10 --最寄り家2       家3---12---> ○ <-- 1 --最寄り家4

いずれも右向き矢印がキューに貯まっている更新で、
左向きは最寄り駅として確定済みだとする。

一般的なDijkstraのように、家からの距離を指標とする場合、
左の更新は、右より先に取り出される。

が、実際に ti=13 の場合に連結するのは、右の方（家3と家4）のみとなる。
左は、先に取り出されるものの、連結してはならない。

かといって、飛ばせばよいわけではなく、
次のクエリで ti = 21 となった場合は、その時に連結しなければならない。

保留リストを作るなどの方法も考えられるが、
なるべくなら、右の方が、左より先に取り出されるようにしたい。

これは、Dijkstraの指標を、 「他の家からの距離が確定済みの場合は、それも足してやって、家間の距離を指標とする」ことでできる。

ti = 13

家1---11---> ○ <-- 10 --最寄り家2       家3---12---> ○ <-- 1 --最寄り家4
（キューの指標値は21）                   （キューの指標値は13）

そうしても、同じ頂点に対する同じ始点からの最短距離は、短い方から順にキューから取り出されることは変わらないので、最短距離が誤って求まることはない。

これで、「指標値が $t_i$ を超えないまで」探索を続けることで、適切なタイミングで打ち切ることができる。

こうした場合に、「キューに突っ込む時点では最寄り家の距離が未確定の頂点に対する更新をどうするか」を迷うが、 とりあえずは最寄りの家からの距離を「0」として、一方だけからの距離を指標値としておけばよい。

その上で、キューから取り出されたとき、

• まだ未確定であれば、今の経路の始点が最寄りの家
• キューに貯まっている間に最寄りの家が確定していた場合は、改めてそれを加算した指標値としてキューに突っ込む

とすればよい。

結局、キューに入れておく値は、(家間の距離, 始点からの距離, 頂点番号, 始点の頂点番号, キューに入れるときに最寄り家の距離は確定していたかフラグ) のようなタプルとなる。（もっと簡略化できるかも）

「ある条件になったら状態を保存していったん呼び出し元に返し、再度呼ばれたら再開する」みたいな処理は、ジェネレータによる実装がやりやすい。

• Pythonのイテレータとジェネレータ - Qiita

もう少しわかりやすい方法。

まず、多始点Dijkstraで、各頂点につき「最寄りの家の頂点番号」と「その距離」を計算する。
これは始点の番号さえ持っておきさえすれば、（解法1のようにコストをいじらなくても）基本的な多始点Dijkstraによって可能。

頂点 $v$ までの最寄り家からの距離を $Dist_v$ とする。

次に、辺を1本ずつ見ていく。もし辺 $i$ の両端をつなぐ頂点の最寄りの家が異なっていた場合、 両端の頂点番号を $a,b$ として、辺 $i$ を経由したときの、それぞれの最寄り家同士の距離は $Dist_a + Dist_b + c_i$ となる。
別の辺を経由することで、同じ家同士に対して複数の異なる距離が求まることもあるが、同じ家同士に対しては最も短いものだけを記録しておく。

「家」を頂点、「家同士の距離」を辺としたグラフを新たに考える。
このグラフ上で、クラスカル法などによって最小全域木を $t_i$ の辺まで構成→クエリに答える→次に小さいクエリ $t_j$ の辺まで構成→……としていけば、 問題に答えることができる。

家同士の組み合わせは $K^2$ 個あって、その全ての距離はとても列挙できないが、 実際は「家 $a$ から $d$ に行くなら、どう行ったって途中で $b$ か $c$ によった方が近い」みたいな例がたくさんあり、 この方法だと辺数の上限で抑えられ、実際に有効な家のペアを効率的に発見できる。

• 解説 - AtCoder Beginner Contest 250 別解

Python3