AtCoder Beginner Contest 237 E,G問題メモ

AtCoder Beginner Contest 237

E - Skiing

問題

$N$ 頂点 $M$ 辺の単純連結無向グラフ
各頂点には標高 $H_i$ が定まっている
頂点 $u$ から $v$ へ移動したとき、以下の満足度を得る
- $H_u \ge H_v$ の場合、$H_u-H_v$
- $H_u \lt H_v$ の場合、$2(H_u-H_v)$（満足度が下がる）
頂点1から移動開始して好きな頂点で終了できるとき、終了までに得た満足度の総和として可能な最大値を求めよ
$2 \le N \le 2 \times 10^5$
$N-1 \le M \le 2 \times 10^5$

解法

ポテンシャルという概念の教育的問題。

満足度を正負逆転させて「コスト」とすると、最短経路問題となる。
しかし負辺を含むので、Dijkstraでは一部の意地悪なケースで計算量が増大し、 $O(2^{\frac{N}{3}})$ かかるケースが作れてしまう。

Bellman-Fordは負閉路さえ含まなければOKだが、そもそも計算量が $O(NM)$ かかる。

以下のように考える。

基本的に各頂点へのコストは、下り道しか通らなければどんな経路でも始点と終点の標高差となる。

しかし途中で登り道を通ると、2点間の標高差を $d$ として、$d$ だけ余分にかかる。
（本来のコストは $2d$ だが、そのうち $d$ は後でまた下るときに回収されるので、追加分だけを考えると $d$ となる）

この「追加分」だけを考えれば負辺は出てこないので、Dijkstraで「各頂点に到達するのに必要な最小の追加分」を求め、それに $H_1$ からの標高差を加味することで、最小コストが求められる。

ポテンシャル

ダイクストラとポテンシャルのはなし - niuez’s diary

一般に、グラフでは以下のようにすると辺のコストを変換できる。

各頂点に、ある値 $p_i$ を決める
各辺の元のコスト $dist(u,v)$ を、$dist'(u,v) = dist(u,v)+p_u-p_v$ に置き換える
それで求めた $s$ からの最短距離を $d'_i$ とすると、本来の答えは $d_i=d'_i+p_i-p_s$

ここで、変換後の辺が非負になるよう上手く $p_i$ を決めるには、以下の条件が満たされればよい。

全ての辺について、$p_u+dist(u,v) \ge p_v$

結局、これを上手く求めるのが難しく、一番シンプルと思われるものが「どっかの頂点からの最短距離」となる。

最短経路探索を高速化したいのに、どっちみち最初に最短経路求めなあかんのかい！となる。
世の中そんなうまい話はなかった。

だが、以下のような場合に有効活用できる。

最短距離でなくても、$p_u+dist(u,v) \ge p_v$ が満たされるようなグラフの性質がある
ちょっとずつ $p_u+dist(u,v) \ge p_v$ が崩れないような変更が行われるグラフ上で、何回も繰り返し最短経路を求める
- 最初の1回をBellman-Fordなどで求めてやれば、次からはそれをポテンシャルとしてDijkstraが使える

2番目は、最小費用流を求めるときなんかに使われる。

今回は1番に当てはまり、$H_i$ を $p_i$ として使うことで、上式が全ての辺で成り立つことがわかる。

Python3

from heapq import heappop, heappush

n, m = map(int, input().split())
hhh = list(map(int, input().split()))
links = [set() for _ in range(n)]
for _ in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    links[u].add((v, max(0, hhh[v] - hhh[u])))
    links[v].add((u, max(0, hhh[u] - hhh[v])))

INF = 1 << 60
dist = [INF] * n
dist[0] = 0

q = [(0, 0)]
while q:
    cost, v = heappop(q)
    if dist[v] > cost:
        continue
    for u, c in links[v]:
        new_cost = cost + c
        if dist[u] > new_cost:
            dist[u] = new_cost
            heappush(q, (new_cost, u))

h0 = hhh[0]
scores = [h0 - h - d for h, d in zip(hhh, dist)]
ans = max(scores)
print(ans)

G - Range Sort Query

問題

$1～N$ の順列 $P_1,P_2,...,P_N$ が与えられる
$Q$ 個のクエリが飛んでくる
- 1 Li Ri : $P_{Li}～P_{Ri}$ を昇順にソートする
- 2 Li Ri : $P_{Li}～P_{Ri}$ を降順にソートする
最終的な順列における $X$ の位置（$P_i=X$ である $i$）を求めよ
$1 \le N \le 2 \times 10^5$
$1 \le Q \le 2 \times 10^5$

解法

なるほどーと唸る上手い解法。
ソート結果全てではなくて、特定の1つの値の位置がわかればいいところがミソ。

ソートって基本的に計算量が大変だけど、シンプルにできる場合が1つある。
それは、要素が $0,1$ のみからなる場合。

$L_i～R_i$ の $1$ の数を数える＝区間の総和をとる（$k$ とする）
昇順なら、末尾 $k$ 個を $1$ に、残りを $0$ に上書きする
- 0 1 1 0 1 0 0 1 → 0 0 0 0 1 1 1 1
降順なら、先頭 $k$ 個を $1$ に、残りを $0$ に上書きする
- 0 1 1 0 1 0 0 1 → 1 1 1 1 0 0 0 0

これも愚直にやったら間に合わないが、区間更新・区間和の取得ができればよいので、遅延評価セグメント木を使えば1回あたり $O(\log{N})$ で効率的に行える。

順列 $P$ を「$X$ 以上なら1、未満なら0」「$X$ より大きいなら1、以下なら0」とした2つの数列に変換すると、 2つはちょうど、$X$ の位置だけが異なった状態となり、その性質はソートしても変わらない。

この2つで個別にクエリを処理し、結果から異なる位置を探せばよい。