AtCoder Grand Contest 074 A問題メモ

AtCoder Grand Contest 074

残り5分、ギリギリのA一完。終了時間が迫ると急にひらめくことってあるよね。（もっと速く解けるに越したことはない）

A - Communicate Topological Order

問題文

$N$ 頂点 $M$ 辺の単純有向非巡回グラフ $G$ が与えられます。
$(1,2,\ldots,N)$ の順列 $P=(P_1,P_2,\ldots,P_N)$ であって以下の条件を満たすものを特別な順列と呼ぶことにします。
- $G$ のすべての辺 $x_i→y_i$ について、$P_{x_i} \lt P_{y_i}$

特別な順列 $P$ が与えられます。これを使って高橋君と青木君がゲームをします。
- 二人とも $G$ の形は知っています。
- 高橋君は $P$ の各項の値を知っていますが、青木君は $P$ が特別な順列であるということしか知りません。
- 高橋君は $P$ のいくつかの項を選び、その位置と値を青木君に伝えます。
青木君が $P$ のすべての項の値を特定するために高橋君が伝える必要がある項の個数の最小値を求めてください。
$1$ つの入力につき、$T$ 個のテストケースを解いてください。

制約

$1 \leq T \leq 10^4$
$1 \leq N \leq 2 \times 10^5$
$0 \leq M \leq 2 \times 10^5$
$1 \leq x_i,y_i \leq N$
与えられるグラフ $G$ は単純有向非巡回グラフ
$1 \leq P_i \leq N$
$P_1,P_2,\ldots,P_N$ は互いに相異なる
$P_{x_i} \lt P_{y_i}$
全てのテストケースにおける $N$ の総和は $2 \times 10^5$ 以下
全てのテストケースにおける $M$ の総和は $2 \times 10^5$ 以下
入力される値は全て整数

解法

とりあえず最初の頂点番号にあまり意味は無く、$i$ を $P_i$ に置き換えて考えてよい。
置き換えた後の“特別な順列”に関する制約は、「DAGで先頭にある頂点ほど頂点番号が若い」という制約に変化する。

■サンプル1
最初の頂点番号      Piに置き換え
  ／￣↘              ／￣↘
③→④→①      →  ①→②→⑤     置き換え後のグラフでは、
⑤→②              ③→④         (a)→(b)に辺があったら a < b という制約

この制約を青木君も知っている上で、高橋君がいくつかの頂点番号を明かし、青木君が残り全てを埋められたらよい。

サンプルを見ると、まず「全頂点間の大小関係が分かっている頂点群（＝DAG上で一筆書きできる）」だけ残して他を全部教えてあげたら、残りは一意に決まるのはすぐ気付く。

○→○→○    残る番号は1,2,5で、グラフから全て大小関係が決まっている。
③→④        ①→②→⑤ と埋めるしかない！

では $N-最長パス長$ が正解かというと、もっと減らせるパターンがある。

例えば以下の場合、③さえ教えれば、上には①→②と埋めるしかない。その後、残る下の4頂点も一意に決まる。
（実際はもっとパスは枝分かれしたり絡み合ったりしているが、最長パスを取り除くことを繰り返してパスに分解したと考える）

①→②→③          ○→○→③
④→⑤→⑥→⑦  →  ○→○→○→○

もう少し複雑な以下の場合、①④⑤⑦⑩を教えれば、まず上から2列目が決まり、1列目が決まり、4列目が決まる。（教えるべき頂点群は他の組合せもある）
①⑤⑩は最長パスに含まれているものの、敢えて教えることで他の連続した頂点を一気に決める助けとなる。

①→⑤→⑧→⑨→⑩      ①→⑤→○→○→⑩
②→③→⑥→⑦      →  ○→○→○→⑦
④                      ④
⑪→⑫→⑬              ○→○→○

この時、②→③→⑥、⑧→⑨、⑪→⑫→⑬ のように、教えない頂点列の数字の範囲は決して被らない。
（被ってたら入れ替え可能となり、特定できない）

最長パス長を求める時、なんか工夫して「特定の条件を満たすとき、⑥→⑧や⑨→⑪の間にも擬似的な辺を張ってやる」ようなことができれば、最初に考えたとおり $N-最長パス長$ として求められそう。

一般的なDAGで、最長パス長はDPで求められる。
今回は頂点番号が若い方が上流になるように並べているので、$v$ を小さい方から埋めていける。

$v=1,2,...$ の順に、
「$v$ に流入辺を持つ頂点 $u_1,u_2,...$ のうち、$\mathrm{DP}[u_i]$ が最大であるもの $+1$」を $\mathrm{DP}[v]$ としていく。

今回は以下のような遷移も可能とする。

$v$ 未満の頂点を全て確定可能にすることを考える。
- $v$ 未満の頂点だけで構成できる最長パスの1つを $P=(p_1,...,p_k)$ とする。
- 「$P$ に含まれない頂点」と「$p_k$」の $v-k$ 個の頂点を教えれば、$v$ 未満の頂点は全て確定される。
この時、$p_{k-1}$ から $v$ に擬似的な辺を張ることができる。
- この辺を使った $v$ までのパス長は $k$ と一致する。

$p_{k-1}$ が具体的に何かは、パス長のみを求める上で必要ない。

$L_v:=v$ 以下の頂点だけで構成できる最長パス長

をDPと同時に計算しながら、$\mathrm{DP}[v]←L_{v-1}$ という更新も追加してやることで、擬似的な辺を含めた最大パス長が求められる。

Python3

def solve(n, m, edges, ppp):
    links = [[] for _ in range(n)]
    rev_links = [[] for _ in range(n)]
    for u, v in edges:
        pu = ppp[u - 1] - 1
        pv = ppp[v - 1] - 1
        links[pu].append(pv)
        rev_links[pv].append(pu)

    cur_longest = [0] * n
    acc_longest = [0] * n
    cur_longest[0] = 1
    acc_longest[0] = 1
    for v in range(1, n):
        tmp_longest = max(1, acc_longest[v - 1])
        for u in rev_links[v]:
            tmp_longest = max(tmp_longest, cur_longest[u] + 1)
        cur_longest[v] = tmp_longest
        acc_longest[v] = max(acc_longest[v - 1], tmp_longest)

    ans = n - acc_longest[-1]
    return ans


t = int(input())
for _ in range(t):
    n, m = list(map(int, input().split()))
    edges = [list(map(int, input().split())) for _ in range(m)]
    ppp = list(map(int, input().split()))
    ans = solve(n, m, edges, ppp)
    print(ans)

目次

AtCoder Grand Contest 074 A問題メモ

A - Communicate Topological Order

問題文

制約

解法