脳log[20230325]

2023年03月25日 (土) [AtCoder] 精進。今日あった ABC295-G「Minimum Reachable City」(黄 diff)。有向グラフがあって、最初は１番の頂点を除いて小さい頂点から自身に向かう辺がある。つまり、ある頂点は自分より大きい頂点に向かう複数の辺を持つ可能性がある一方、自身に向かう辺は必ず１つだけある(頂点１を除いて)。制約には書かれていないけどクエリ１において u>v であり、v->a->b->c->d->u という関係があるときに u->v という辺を追加することになる。u から逆辺をたどって v に到達するまでに通る頂点はすべて v に到達可能になり、クエリ２において答えるべき最小の頂点が v になる。辺を順方向に辿るのは行き先が発散して良くないので、クエリ１による変化は行き先が唯ひとつに決まる逆辺を辿って伝える。しかしクエリのたびに逆辺を辿るのでは O(QN) になって TLE が必至。UnionFind のようにグループを管理して、UnionFind の Find 関数のように経路を圧縮したい。■提出 #40061939 (AC / 350 ms)。UnionFind のようにやりました。R=Root, P=Parent, T=Tell, F=Find. ほとんど扱いが同じである R(根)と P(親)を共通化できるかと思ったけど、根へは到達できるのに対して親へはクエリ１が来て T(ell) 関数が呼ばれるまで到達できない違いがあるので分かれている。実は F(ind) 関数はいらないんじゃないかと取り除いてみたりもしたけど、しっかり答えが違ってきてたしかに役に立っているようだった。■D と E と F の精進はまだだよ。詰まってしまった D を後回しにして E にとりかかってそのまま E と心中した結果 A-C の３完だったんだよ。パフォーマンスも新しいレートも知らないよ。G 問題が(事後でも)解けたくらいのごほうびがないとやってられないよ。■なんとなく脳内イメージが 20210902 で解いた ARC056-B「駐車場」に似ている。似ているだけで、共通点があったりヒントにできるかどうかは知らない。たぶん状況の整理が必要な点が似てるんだろう。さっき例にあげた v->u->v という環状構造があるときに、u->b という辺が追加されたらどうか、b->x (ただし x<v) という辺が追加されたらどうか、そして UnionFind がこっそりうまくやるように、すでに環状構造がある２つの連結成分を繋ぐようなクエリ１が来たらどうなるか、を整理する。ああ、だから F(ind) 関数を省くと良くないのはクエリ１の第２引数である飛び先にすでに別の飛び先がある場合があるからだ。それでなくてもクエリ１でショートカットしているからすべての頂点が最終到達点を必ず知っているわけではない(だから F(ind) 関数が必要)。