2020/5/31バチャ反省(2)

久し振りにABCに出るのでウオーーーーーーーーーーーーーーーーーーーーーーミングアップにバチャをしました。

バチャ概要

リンクです。

難易度は

0~400(灰)*10
800~1200(緑)*2
1200~1400(水色)*1

55分+2ペナで全完。水色の考察をするために組みましたが、グラフだったので瞬殺でした。

解説

緑以上の3問だけ解説と提出を書きます。

Transit Tree Path

考察と方針

クエリでは $x _ jとy _ j$ が与えられ、 $x _ jからKを経由してy _ j$ まで移動する最短距離を求める必要があります。無向グラフなので、 $x _ jからKまでの最短経路$ と $Kからx _ jまでの最短経路$ は同じです。

また、木においてある二点をつなぐ経路は一つしか存在しないため、実は「 $x _ jからy _ jへの経路にKが含まれているか$ 」は気にしなくてよいことが分かります。

つまり、事前にKを始点にした全点への最短経路を求めておき、各クエリにおいて

$Kからx _ jまでの最短経路$
$Kからy _ jまでの最短経路$

を足したものを出力すればよいです。

実装

解説を読むと「経路は一通りなのでKを根にしてDFSすればよいです」とあります(これはつまり、上で言っている「最短経路」が「経路」と言い換えられるということでもあります)が、それに気づかなかったのでKを始点にダイクストラをしました。あとは各クエリにおいて上で書いた値を出力するだけです。

提出

atcoder.jp

計算量

ダイクストラ部分がネックになって、 $O(NlogN)$ です。想定解では $O(N+Q)$ なのでかなり違いますが、通ればいいんです。

STring

考察と方針

とりあえず変化しなくなるまで

X = X.replace("ST", "")

を繰り返せばいいのはわかります。提出します。 $O(N ^ 2)$ なので当然TLEです。

制約的に $O(N)$ が限界なので、大体一回のループで処理を完了しなければなりません。どうしよう....

問題文の通り、、STが1ペアとなって消滅します。これはスタックの説明でよく見る括弧列の対応と同じです。すなわち、要素をスタックに一つずつ追加していって、右端でSTのペアができていたら消す、できていなかったらなにもしない...という流れを繰り返すことで、問題文にあるSTのペアを消していくシミュレーションと同じ結果が得られます。

これはざっくりいうと、「スタックに変更があるたびに右端だけチェックすれば、右端以外はチェック済みなのでSTが含まれていることは無い」ということです。