1日1株までしか売買できない。
N 日時点で現金化してない株を持っていても仕方ないので、売らない株は買う必要が無い。
よって、株をその日に買うかどうか決めることはしないで、 とりあえずリストに貯めておいて、必要になったら過去に遡ってまだ売買していない日の中から選んで買い、その日に売ることができると考えると、見通しが立ちやすい。
貪欲に考える。1日目から順に以下を更新していく。
i 日目について考えるとき、以下の行動を取れる。
① buy の中に、今日の価格 Pi より安い日があったなら、その最小値 Pbuy−min で買い、今日 Pi で売ることで、 Pi−Pbuy−min の利ざやを得ることができる。
② sell の中に、今日の価格 Pi より安い日があったなら、その最小値を Psell−min として、
「Psell−min の日には売らず、持ち続けて Pi で売ったことにする」ことができる。
その場合、既に獲得した利ざや Psell−min−Pbuy と、後から変更した行動による利ざや Pi−Pbuy の差分、
Pi−Psell−min だけ、追加で得ることができる。（Pbuy の具体的な値はわからなくてよい）
③ どちらも可能な場合は、より得する方（Pbuy−min と Psell−min の小さい方）を取る。
④ どちらもできなければ、buy に Pi を追加する。
buy や sell は優先度付きキューで実装するのがよい。
ただ、正当性は未証明。
基本は上記と同じだが、実装しやすい解法。優先度付きキュー1本で可能。
上記で、一度売ることにした Pi は、最大2回まで（擬似的に）買う側として取り出されうる。
②と③とで、答えへの寄与の計算方法（差分）は変わらない。
なので、1つの優先度付きキューで、
とすると、優先度付きキューの最小値が Pi より小さいかどうか判定し、小さければ最小値を取り出してペアにする、という処理の繰り返しのみで正しい答えが求まる。
DijkstraとUnion-Findの複合。
2つの ti≤tj なるクエリで、ti の時に行けていた xi,yi が、tj で行けなくなることはない。
よって、クエリを ti の昇順にソートすることが考えられる。
以下のようなことができればよさそう。
これらをどう実装するか考える。
家はたくさんある場合があるので、各家を始点にした場合それぞれでDijkstra……なんてやってられない。
多始点Dijkstraなどで、各頂点が、「最寄りの家」から何分かかる位置にあるか、は一斉に計算できる。
そして、少し考えれば、各頂点は「最寄りの家」からの距離さえ記録しておけば、
2番目、3番目に近い家からの距離は記録せずとも、各家のペアが ti 以内に到達可能かは判定できる。
家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) で、家間の距離を求めることはできる。
家の距離は上記の方法で計算できるとして、 どこまで探索を続けて、どこで打ち切るか、という問題がある。
また、キューから取り出される更新に関して、 「ti で有効な更新が、無効な更新より後に取り出される」ことにも対処しなければならない。
どういうことかというと、例えば、以下の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）
そうしても、同じ頂点に対する同じ始点からの最短距離は、短い方から順にキューから取り出されることは変わらないので、最短距離が誤って求まることはない。
これで、「指標値が ti を超えないまで」探索を続けることで、適切なタイミングで打ち切ることができる。
こうした場合に、「キューに突っ込む時点では最寄り家の距離が未確定の頂点に対する更新をどうするか」を迷うが、
とりあえずは最寄りの家からの距離を「0」として、一方だけからの距離を指標値としておけばよい。
その上で、キューから取り出されたとき、
とすればよい。
結局、キューに入れておく値は、(家間の距離, 始点からの距離, 頂点番号, 始点の頂点番号, キューに入れるときに最寄り家の距離は確定していたかフラグ) のようなタプルとなる。（もっと簡略化できるかも）
「ある条件になったら状態を保存していったん呼び出し元に返し、再度呼ばれたら再開する」みたいな処理は、ジェネレータによる実装がやりやすい。
もう少しわかりやすい方法。
まず、多始点Dijkstraで、各頂点につき「最寄りの家の頂点番号」と「その距離」を計算する。
これは始点の番号さえ持っておきさえすれば、（解法1のようにコストをいじらなくても）基本的な多始点Dijkstraによって可能。
頂点 v までの最寄り家からの距離を Distv とする。
次に、辺を1本ずつ見ていく。もし辺 i の両端をつなぐ頂点の最寄りの家が異なっていた場合、
両端の頂点番号を a,b として、辺 i を経由したときの、それぞれの最寄り家同士の距離は Dista+Distb+ci となる。
別の辺を経由することで、同じ家同士に対して複数の異なる距離が求まることもあるが、同じ家同士に対しては最も短いものだけを記録しておく。
「家」を頂点、「家同士の距離」を辺としたグラフを新たに考える。
このグラフ上で、クラスカル法などによって最小全域木を ti の辺まで構成→クエリに答える→次に小さいクエリ tj の辺まで構成→……としていけば、
問題に答えることができる。
家同士の組み合わせは K2 個あって、その全ての距離はとても列挙できないが、 実際は「家 a から d に行くなら、どう行ったって途中で b か c によった方が近い」みたいな例がたくさんあり、 この方法だと辺数の上限で抑えられ、実際に有効な家のペアを効率的に発見できる。