AtCoder Grand Contest 074 A,B問題メモ

AtCoder Grand Contest 074

時間ギリギリの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)に辺があったら Pa < Pb
  ／￣↘              ／￣↘
③→④→①      →  ①→②→⑤     置き換え後:
⑤→②              ③→④         (a)→(b)に辺があったら a < b
P=(5,4,1,2,3)

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

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

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

「なるべく長いDAG上での一筆書き」といえば、最長パスとなる。
では $N-最長パス長$ が正解かというと、もっと減らせるパターンがある。

例えば以下の場合、③さえ教えれば、上には①→②と埋めるしかない。その後、残る下の4頂点も一意に決まる。
（実際はもっとパスは枝分かれしたり絡み合ったりしているが、一番決めやすいように都合良くパスに分解したと考える）

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

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

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

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

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

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

• $v=1,2,...$ の順に、
• $\mathrm{DP}[v]=$「$v$ に流入辺を持つ頂点群 $u=\{u_1,u_2,...\}$ に対し、$\max_{u_i \in u}\mathrm{DP}[u_i]+1$」としていく。

この過程で、「擬似的な辺を張れる条件」を考える。

たとえば $v=8$ について求める際、「$8$ 未満の頂点だけで作れる最長パス長」はわかっている。

①→⑤
②→③→⑥→⑦    ←最長パス（長さ4）
④

擬似的な辺の意味するところは、「⑦以下の頂点は全て特定できる状態にした上で、新たな最長パスを⑧から開始する」際に、 ⑦以下で教えずに済む最大頂点数を、⑧からのパス長に加えておく、という処理になる。

この例で「⑦以下の頂点を全て特定するために必要な頂点」を考えると、 ①④⑤⑦の4つ、つまり「最長パスに含まれない頂点」と「最長パスの末尾頂点」を教えれば、残りの頂点は一意に決まる。 この時、最長パスの末尾から2番目の頂点⑥→追加頂点⑧に擬似的な辺を張ることができる。

①→⑤→⑧
        ↑
○→○→○→⑦
④

一般化してまとめると、

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

新たな擬似的な辺によって作られる $v$ までの最長パス長は、$k$ と一致する。

• $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)

解法1と同じように $i$ を $P_i$ に置き換え、制約を「$u→v$ に辺があったら $u \lt v$」とする。

現在調べている頂点を $i$ とし、$i=1$ で初期化する。また $Ans=0$ で初期化する。
$i \gt N$ となるまで以下を繰り返すと $Ans$ が答えとなる。

• 頂点 $i$ 以降で最初にある「入次数が $0$ でない頂点」を $j$ とする。（無い場合は $j=N+1$）
  • $i～j-1$ の $(j-i)$ 個の頂点は全て入次数が $0$ である。これを1グループとする。
  • $Ans$ に $(グループサイズ-1)$ を加算する。
• グループ頂点（$i～j-1$）を、辺を含めてグラフから除外する。
• $i←j$ として、最初に戻る。
  • この時、新たな $i$ の入次数は必ず $0$ である。（残っている中で頂点番号最小なので）

同じグループに分類された頂点は、番号を入れ替えても制約に違反せず成立してしまう。

• あるグループに、元のグラフで流入していた頂点番号は必ず $i-1$ 以下
• あるグループから流出先にある頂点番号は必ず $j$ 以上
• グループ間に大小関係の情報は無い

つまり同じグループから2頂点以上を教えないことにすると、特定できなくなってしまう。
1頂点なら消去法で特定できるので、少なくとも教えなければならない頂点数の下限はこれになる。

そして、教えない頂点を上手く選ぶことで、下限が達成できる。 具体的には、「各グループの中で最初の頂点 $i$ を教えないことにする」とよい。

①→⑤→⑧→⑨→⑩      ○→⑤→⑧→○→○    グループ分割の内訳:
②→③→⑥→⑦      →  ②→○→○→○        ①②, ③④⑤, ⑥, ⑦⑧, ⑨, ⑩⑪, ⑫, ⑬
④                      ④
⑪→⑫→⑬              ⑪→○→○            →①③⑥⑦⑨⑩⑫⑬ は教えずに済む

教えられた頂点だけ埋めた初期状態（上図右）で、入次数が $0$ なのは必ず1個のみ。
手続き上、他の入次数 $0$ の頂点は「各グループの中で最初の頂点」になり得ない。

この1個が①となる。そうでなければ、①を配置できる場所が無くなる。
①を埋めたら、次に番号がない頂点（上例では③）未満をグラフから削除すれば、再帰的に同じことが言える。

B - Swap if Equal Length and Sum

• $0$ と $1$ からなる長さ $N$ の整数列 $A=(A_1,A_2,\dots,A_N),\; B=(B_1,B_2,\dots,B_N)$ が与えられます。
• $A$ に対して、以下の操作を $\lfloor\frac{N}{2}\rfloor$ 回まで行えます。
  • 以下の $3$ 条件を満たす $4$ 整数 $a,b,c,d$ を選ぶ。
    • $1 \leq a \leq b \lt c \leq d \leq N$
    • $b-a=d-c$
    • $\sum_{i=a}^{b}{A_i}=\sum_{i=c}^{d}{A_i}$
  • $(A_a,A_{a+1},...,A_b)$ と $(A_c,A_{c+1},...,A_d)$ を入れ替える。
• $A$ を $B$ に一致させることが可能かどうかを判定して、可能ならばその操作手順を $1$ つ構成してください。

• $1$ つの入力につき、$T$ 個のテストケースを解いてください。

• $1 \leq T \leq 25000$
• $2 \leq N \leq 2 \times 10^5$
• $0 \leq A_i \leq 1$
• $0 \leq B_i \leq 1$
• 全てのテストケースにおける $N$ の総和は $2\times 10^5$ 以下
• 入力される値は全て整数

可能不可能が分かっても、構築のフェイズも結構難しい。

$1$ の個数が同じじゃないと無理なのはすぐ分かる。他に条件はあるか？

愚直実験してみると、意外とできるパターンは少ないことが分かる。

A = (0, 0, 1, 1, 0, 1, 0, 1)
      ↓作れるのは以下のみ
    (0, 0, 1, 0, 1, 1, 1, 0)
    (0, 0, 1, 1, 0, 1, 0, 1)
    (0, 1, 0, 0, 1, 1, 0, 1)
    (0, 1, 0, 1, 0, 0, 1, 1)
    (1, 0, 0, 0, 1, 0, 1, 1)

どれかの“1”が $1$ 個左に動いたら、他の“1”が $1$ 個右に動いている。
つまりは、どれかのindexが $k$ 減ったら、どれかが $k$ 増えていないといけない。
「“1”の位置するindexの総和」が不変量となっている。

これは交換によって左区間の“1”のindexは軒並み一定量増えて、右区間は同じだけ減る、という説明で簡単に示せる。

“1”のindexの総和が違う場合は無理とわかる。

“1”の総和及びindexの総和が一致したとする。この場合は実際に構築可能であることを示す。

実際に手で操作を試すと、「長さも、“1”の個数も同じ2区間」って、意外と取れないことがわかる。
一方の区間にもう一方の長さを合わせようと区間を伸ばせば、“1”の個数が合わなくなってしまったりする。
もちろん、動かせる区間を全探索している余裕はない。

確実に長さと個数を合わせやすい単純な方法として、「1回で動かす“1”は必ず1個」でできないか、と考える。1個ずつの場合、操作は以下のように言い換えられる。

• 左に “0” が $k$ 個以上ある “1” と、右に “0” が $k$ 個以上ある “1” のペアを選ぶ。
• それぞれ、左と右に $k$ 個ずつ動かす

これは、“00…01” と “100…0” を交換することに相当する。
言い換えた後の操作においては、（見た目上は）“1”の順序は初期状態から入れ替わらないと見なせる。

$A$ の $i$ 番目の “1” を、$B$ の $i$ 番目の “1” の位置に持っていくとして、 「左に動かしたいグループ」「右に動かしたいグループ」に分ける。（動かさなくていいのは無視）

   1  2  3  4  5  6  7  8
A (0, 0, 1, 0, 1, 1, 1, 0)    左グループ  3→1
   ,-----'     |  `-,`--,
B (1, 0, 0, 0, 1, 0, 1, 1)    右グループ  6→7, 7→8

左グループと右グループから1つずつ選んで動かせばよいが、 困ったことに、$6→7$ のように「他の“1”に妨害され動かせない（希望の位置まで持っていけない）」ような“1”もある。
上例では、$6→7$ より先に $7→8$ を処理しないといけない。

この順番をどうするか。

ところで妨害は、左グループと右グループの間では発生せず、常に同グループの中のみで発生する。
（$A$ での位置→$B$ での位置 を線で結んだとき、線がクロスすることはないので）

つまり、左グループの最も左の“1”、右グループの最も右の“1”は、必ず妨害されずに希望の位置まで持っていける。 この2つをペアにし、希望の位置までの距離が短い方に合わせて移動させればよい。
足りなかった方は残留し、希望の位置まで到達できた方はグループから除外する。

ここで、“1” は $N/2$ 個以下としてよい。（“1” の方が多かった場合、“0” と “1” を反転させても答えは変わらない）
つまり、両グループを併せた要素数は $N/2$ 以下である。
上記の方法で、1回の操作によって必ずいずれかのグループから少なくとも1個の要素が除外されるので、 $N/2$ 回以下の操作回数で必ず実現できる。

Python3

def solve(n, aaa, bbb):
    k = sum(aaa)
    if k != sum(bbb):
        return None
    if k > n // 2:
        aaa = [a ^ 1 for a in aaa]
        bbb = [b ^ 1 for b in bbb]
        k = n - k

    pos_a = [i for i, a in enumerate(aaa) if a == 1]
    pos_b = [i for i, b in enumerate(bbb) if b == 1]
    if sum(pos_a) != sum(pos_b):
        return None

    # pos_a[i] の"1"を pos_b[i] の"1"に持っていくとき、
    # * 左右どちらに動かしたいか
    # * desire:動かしたい距離
    # * room:現時点で他に邪魔されず単独で動かせる距離
    # 左右で desire = room であるものの中から貪欲にマッチング
    ml = []
    mr = []
    move_left = [False] * k
    desires = [0] * k
    rooms = [0] * k
    pos_a.append(n)
    pos_a.append(-1)
    remain_l = 0
    remain_r = 0
    for i in range(k):
        pa = pos_a[i]
        pb = pos_b[i]
        if pa == pb:
            continue
        if pa < pb:
            desire = pb - pa
            room = min(desire, pos_a[i + 1] - pa - 1)
            if desire == room:
                mr.append(i)
            desires[i] = desire
            rooms[i] = room
            remain_r += 1
        else:
            desire = pa - pb
            room = min(desire, pa - pos_a[i - 1] - 1)
            if desire == room:
                ml.append(i)
            desires[i] = desire
            rooms[i] = room
            move_left[i] = True
            remain_l += 1

    operations = []
    while remain_l > 0 and remain_r > 0:
        li = ml[-1]
        ri = mr[-1]
        l_room = rooms[li]
        r_room = rooms[ri]
        w = min(l_room, r_room)
        pl = pos_a[li] + 1
        pr = pos_a[ri] + 1
        # print(f'{li=} {l_room=} {ri=} {r_room=} {w=}')
        if pl < pr:
            operations.append((pl - w, pl, pr, pr + w))
        else:
            operations.append((pr, pr + w, pl - w, pl))

        desires[li] -= w
        desires[ri] -= w
        rooms[li] -= w
        rooms[ri] -= w
        pos_a[li] -= w
        pos_a[ri] += w
        if desires[li] == 0:
            ml.pop()
            remain_l -= 1
        if desires[ri] == 0:
            mr.pop()
            remain_r -= 1

        if li < k - 1:
            if move_left[li + 1] == True:
                if rooms[li + 1] < desires[li + 1]:
                    rooms[li + 1] = min(desires[li + 1], rooms[li + 1] + w)
                    if rooms[li + 1] == desires[li + 1]:
                        ml.append(li + 1)
        if 0 < ri:
            if move_left[ri - 1] == False:
                if rooms[ri - 1] < desires[ri - 1]:
                    rooms[ri - 1] = min(desires[ri - 1], rooms[ri - 1] + w)
                    if rooms[ri - 1] == desires[ri - 1]:
                        mr.append(ri - 1)

    assert len(operations) <= n // 2

    return operations


t = int(input())
for _ in range(t):
    n = int(input())
    aaa = list(map(int, input().split()))
    bbb = list(map(int, input().split()))
    ans = solve(n, aaa, bbb)
    if ans is None:
        print('No')
    else:
        print('Yes')
        print(len(ans))
        for a, b, c, d in ans:
            print(a, b, c, d)