AtCoder Beginner Contest 244 G,Ex問題メモ

AtCoder Beginner Contest 244

“Good Path” に関する問題がE,F,Gと3問続く、テーマ性のある回だった。

G - Construct Good Path

問題

$N$ 頂点 $M$ 辺の単純無向連結グラフが与えられる
0,1からなる長さ $N$ の文字列 $S$ が与えられる
以下のパスを1つ構築せよ
条件
- 長さ $4N$ 以下
- 頂点 $i$ はパス中に、$S_i=0$ なら偶数回、$S_i=1$ なら奇数回出現する
  - 0回も偶数回と見なす。また、長さ0のパスでもよい
$2 \le N \le 10^5$
$1 \le M \le 10^5$

解法

$S_i=0$ の頂点は訪れなくてもよいが、$S_i=1$ の頂点は少なくとも1回は訪れる必要がある。

まずは（偶奇を無視していいので）'1'の頂点を全て訪れるパスの構築を考えたい。
最終的な答えは、そこから適当に往復なんかを加えれば調整できそう。

特定の全頂点を訪れるパス

グラフで「特定の全頂点を1回は訪れるパス」を考える場合、順番に経路探索などしていては、その順番によっては非常に時間がかかるし、パスも冗長になる。

適当に根付き全域木を構築してその「オイラーツアー」を考えれば、全頂点を訪れられるし、パス長は必ず $2N-1$ となる。

（ACの上では必要無いが）部分木に'1'がない頂点への訪れは不要なので、省略してもよい。

偶奇の調整

オイラーツアーで、一番最後にその頂点を訪れ、親に帰るときに調整を行う。

    ⓟ
    /       オイラーツアー（一部）
   ⓥ       .., p, v, 1, .., 1, v, 2, .., 2, v, 3, .., 3, v, p, ..
  /｜\                                                   ~~~
 ①②③                                                 ここ!
 ：：：

この時点では、自身以外の、自身の部分木に含まれる頂点（①②③など）は、もう訪れることはないので全て $S_i$ と整合しているはずである。していなければならない。

よってそこには触れられないとすれば、「親との行き来」によって調整するしかない、ということがはっきりする。

.., 3, .., 3, v,
             ~~~            もしこの時点で、v の出現回数がSvと合っていなければ
.., 3, .., 3, v, p, v,
                            親との往復を挟むと調整できる

もし仮に、この調整が全ての辺に対して必要になったとしても、1辺ごとに2頂点が追加されるだけなので、「ベースのオイラーツアーで $2N-1$」「調整で $2N-2$ 回」で、$4N$ 回以内に収まる。

唯一、親がない「根頂点」はどうするか、が問題となるが、その場合、もうパスは終了なので、末尾を取り除くことで調整できる。

Python3

from collections import Counter


class UnionFind:
    def __init__(self, n):
        self.table = [-1] * n

    def root(self, x):
        stack = []
        tbl = self.table
        while tbl[x] >= 0:
            stack.append(x)
            x = tbl[x]
        for y in stack:
            tbl[y] = x
        return x

    def find(self, x, y):
        return self.root(x) == self.root(y)

    def unite(self, x, y):
        r1 = self.root(x)
        r2 = self.root(y)
        if r1 == r2:
            return False
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            self.table[r1] += d2
        else:
            self.table[r1] = r2
            self.table[r2] += d1
        return True

    def get_size(self, x):
        return -self.table[self.root(x)]


n, m = map(int, input().split())
links = [set() for _ in range(n)]
uft = UnionFind(n)
for _ in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    if uft.unite(u, v):
        links[u].add(v)
        links[v].add(u)

sss = list(map(int, input()))

subtree_odd_count = [-1] * n
parents = [-1] * n
q = [0]
while q:
    u = q[-1]
    if subtree_odd_count[u] == -1:
        subtree_odd_count[u] = -2
        for v in links[u]:
            if subtree_odd_count[v] != -1:
                parents[u] = v
            else:
                q.append(v)
        links[u].discard(parents[u])
    else:
        q.pop()
        soc = sss[u]
        for v in links[u]:
            soc += subtree_odd_count[v]
        subtree_odd_count[u] = soc

links = list(map(list, links))

euler = []
q = [0]
status = [0] * n
count = [0] * n
while q:
    u = q[-1]
    euler.append(u)
    count[u] ^= 1
    while status[u] < len(links[u]):
        v = links[u][status[u]]
        status[u] += 1
        if subtree_odd_count[v] == 0:
            continue
        q.append(v)
        break
    else:
        q.pop()
        if sss[u] != count[u]:
            if u != 0:
                euler.append(parents[u])
                euler.append(u)
                count[parents[u]] ^= 1
                count[u] ^= 1
            else:
                euler.pop()
                count[u] ^= 1

assert sss == count

ans = [a + 1 for a in euler]

print(len(ans))
print(*ans)

# cnt = Counter(ans)
# print(*(cnt[a] for a in range(1, n + 1)))

Ex - Linear Maximization

問題

2次元座標上の点の集合 $S$ があり、はじめ、空である
$Q$ 個のクエリを処理せよ
クエリ
- 整数 $X_i,Y_i,A_i,B_i$ が与えられる
- 点 $(X_i,Y_i)$ を $S$ に追加した後、$S$ に含まれる点における $A_ix+B_iy$ の最大値を求めよ
$1 \le Q \le 2 \times 10^5$
$|X_i|,|Y_i|,|A_i|,|B_i| \le 10^9$

解法

$B=0$ のとき、答えを与える点はその時点で $S$ にある点の $x$ の最大値または最小値。（$A$ の符号による）
それは簡単に管理できるので分けて考えるとして、以降、$B \neq 0$ とする。

例えばある $(x,y)$ に対する値を $k=Ax+By$ とおくと、よくある直線の式に変形すると $y=-\dfrac{A}{B}x+\dfrac{1}{B}k$ となる。

$B \gt 0$ なら、$(x,y)$ を通る傾き $-\dfrac{A}{B}$ の直線の切片が大きいほどよい
$B \lt 0$ なら、$(x,y)$ を通る傾き $-\dfrac{A}{B}$ の直線の切片が小さいほどよい

これは、$B \gt 0$ なら、傾き $-\dfrac{A}{B}$ の直線を無限の上空からぐい～んと降ろしてきて、最初に引っかかった頂点が最大値を与える、ということになる。

~~--__  ↓↓↓
      ~~--__
            ~~--__  =>  ~~--__     こいつ
  ・                      ・  ~~--__ ↓
      ・     ・               ・    ~・-__
   ・      ・              ・      ・

$B \lt 0$ なら逆に、下から上がってくる直線をイメージする。

点がいっぱい集まってくると、大抵は「どんな傾きであろうと、自身より上の点に邪魔されて絶対に引っかからない点」というのができてくる。

引っかかりうる点の候補は、つまり「凸包」と同じである。

点の追加

最初に点が全て与えられる凸包は、Andrew's Monotone Chain という方法によって構築できるが、今回はそれを応用する。

$B \gt 0$ の場合は（直線を上から降ろすので）上側凸包を使うが、上側凸包は、$x$ 座標順に見ると必ず進行方向が時計回りになっている。

追加することによってそれが崩れないかをチェックしていけばよい。
ソート状態を保った上で途中に追加・削除を行いたいので、平衡二分探索木や、SortedSetなどのデータ構造を用いる。

上側凸包に点 $P=(X,Y)$ を追加したいとき、

$P$ 自身が上側凸包に追加され得るか？
- 既に $x$ 座標が $X$ である他の点 $(X,Y_t)$ が凸包に含まれているとき、
  - $Y_t \gt Y$ なら、凸包には含まれ得ない
  - $Y_t \lt Y$ なら、凸包が更新されるため、続ける（既存の点は削除しておく）
- $P$ のすぐ左の点 $L$ を取得する
- $P$ のすぐ右の点 $R$ を取得する
- $L→P→R$ が時計回りなら含まれる（データ構造に $P$ を追加する）
$P$ を追加したことにより、不要になる点がないか？
- 左側
  - $P$ のすぐ左の点 $L$ を取得する(*)
  - $L$ のすぐ左の点 $LL$ を取得する
  - $LL→L→P$ が時計回りか判定する
    - 時計回りなら、終了
    - 時計回りでないなら、$L$ を削除し、(*)に戻る
      - $P$ の左側に点が1個しかなくなったら終了
- 右側も同様

こうすることにより、上側凸包を更新できる。下側も同様。

クエリへの回答

点の追加と同様、$B$ の正負によって上側凸包か下側凸包かを使い分けるが、ここでは $B \gt 0$ として上側を考える。

上側凸包上で、傾き $-\dfrac{A}{B}$ を下ろしたときに最初に引っかかる点を求めたい。

ここで、凸包を構成する線分を考えると、最初に引っかかる点というのは、凸包を構成する線分の中で傾きが $-\dfrac{A}{B}$ に最も近い線分の一端であるはずである。

上側凸包では、$x$ 座標順に見ると、線分の傾きは、大→小へと、単調減少する。

つまり、二分探索が可能である。
「$-\dfrac{A}{B}$ 以下の、最大の傾きを与える線分」を探索し、その両端のいずれかが最大値を与える点となる。

実装

点の追加では、$x$ 座標をキーに挿入位置を求める
クエリの回答では、傾きをキーに答えとなる線分を求める

「$x$ 座標」と「傾き」のそれぞれをキーとして使いたい場面が出てくる。

ただ、一般的なライブラリにある平行二分探索木では、整列・探索に用いるキーは1種類しか指定できないのが普通。
（というか、たまたま今回はこの2つのソート結果が同じになるという特殊な性質があっただけ）

まぁ、キーを変えられる特殊なデータ構造を実装してもよいのだが、いずれか片方をキーとしてライブラリを使って、もう片方を求める際には、自前の二分探索で求めるのが手っ取り早いだろう。（多少、遅くなるが）

小数が現れないこと、また求めたい操作などを考えると、今回は $x$ 座標をキーにするのがよさそう。