AtCoder Regular Contest 193 (Div. 1) A,B,C,D問題メモ

AtCoder Regular Contest 193 (Div. 1)

A - Complement Interval Graph

• 整数 $l, r$ に対し、$l$ 以上 $r$ 以下の整数全体からなる集合を $[l, r]$ で表します。
  • すなわち、$[l, r] = \lbrace l, l+1, l+2, \ldots, r-1, r\rbrace$ です。
• $N$ 組の整数のペア $(L_1, R_1), (L_2, R_2), \ldots, (L_N, R_N)$ が与えられます。
• これに対して、下記で定義される無向グラフ $G$ を考えます。
  • $1, 2, \ldots, N$ と番号付けられた $N$ 個の頂点を持つ。
  • すべての $i, j \in [1, N]$ について次が成り立つ：$[L_i, R_i]$ と $[L_j, R_j]$ の共通部分が空であるとき、かつ、そのときに限り、頂点 $i$ と頂点 $j$ の間に無向辺が張られている。
• また、$i = 1, 2, \ldots, N$ について、頂点 $i$ の重みを $W_i$ で定めます。

• $G$ に関する $Q$ 個のクエリが与えられるので、それらを与えられる順に処理してください。
• $i = 1, 2, \ldots, Q$ について、$i$ 番目のクエリは下記の通りです。
  • $s_i \neq t_i$ を満たす $1$ 以上 $N$ 以下の整数 $s_i, t_i$ が与えられる。
  • $G$ において、頂点 $s_i$ から頂点 $t_i$ へのパスが存在するかを判定せよ。
  • 存在する場合は、そのようなパスの重みの最小値を出力せよ。

• ここで、頂点 $s$ から頂点 $t$ へのパスの重みは、パス上の頂点（両端点である頂点 $s$ と頂点 $t$ を含む）の重みの総和で定義されます。

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq Q \leq 2 \times 10^5$
• $1 \leq W_i \leq 10^9$
• $1 \leq L_i \leq R_i \leq 2N$
• $1 \leq s_i, t_i \leq N$
• $s_i \neq t_i$
• 入力はすべて整数

「$[L_i, R_i]$ と $[L_j, R_j]$ の共通部分が空であるとき、$i,j$ 間に辺がある」という変わったルール。

パスの重みは両端の頂点を含むので、$s,t$ 間に辺がある（$[L_s, R_s]$ と $[L_t, R_t]$ が共通部分を持たない）時は、直接行くのが最適。

直接の辺が無いときでも、実は最適なパターンは少ない。

s       |------|
t            |-------|

a  |--|
b                       |---|
c     |----|
d                 |------|

• ① $s,t$ がともに共通部分を持たない左側の区間の中で、最も $W_i$ の小さい1頂点を経由する（$a$）
• ② $s,t$ がともに共通部分を持たない右側の区間の中で、最も $W_i$ の小さい1頂点を経由する（$b$）
• ③ $s$ と $t$ が交差している（一方が一方を内包していない）場合、$s→d→c→t$ のように、2頂点を経由する

これは、各区間について 「(A)左側・右側のそれぞれで共通部分を持たない中で最も $W_i$ の小さいもの（存在しない場合は $\infty$）」を求めておけば、 ①～③を全て調べた中で最小のものが答えとなる。

(A)は、イベントソートなどで作成できる。

Python3

def solve(n, www, lrs, q, queries):
    events = []
    for i in range(n):
        l, r = lrs[i]
        events.append((l, 0, i))
        events.append((r, 1, i))
    events.sort()

    INF = 1 << 60
    left = INF
    right = [(w, i) for i, w in enumerate(www)]
    right.sort()
    ri = 0
    right_available = [True] * n
    best_left = [INF] * n
    best_right = [INF] * n

    for x, op, i in events:
        if op == 0:
            best_left[i] = left
            right_available[i] = False
        else:
            while ri < n and right_available[right[ri][1]] == False:
                ri += 1
            if ri < n:
                best_right[i] = right[ri][0]
            left = min(left, www[i])

    ans = []
    for s, t in queries:
        s -= 1
        t -= 1
        ls, rs = lrs[s]
        lt, rt = lrs[t]
        base_cost = www[s] + www[t]
        if ls > lt:
            s, t = t, s
            ls, rs, lt, rt = lt, rt, ls, rs
        # print(f'{s=} {t=} {ls=} {rs=} {lt=} {rt=}')
        if rs < lt:
            ans.append(base_cost)
            continue
        tmp = base_cost + best_left[s]
        if rs <= rt:
            tmp = min(tmp, base_cost + best_right[t])
            tmp = min(tmp, base_cost + best_right[s] + best_left[t])
        else:
            tmp = min(tmp, base_cost + best_right[s])
        if tmp < INF:
            ans.append(tmp)
        else:
            ans.append(-1)

    return ans


n = int(input())
www = list(map(int, input().split()))
lrs = [tuple(map(int, input().split())) for _ in range(n)]
q = int(input())
queries = [tuple(map(int, input().split())) for _ in range(q)]
ans = solve(n, www, lrs, q, queries)
print('\n'.join(map(str, ans)))

B - Broken Wheel

• 正整数 $N$ と、0 と 1 のみからなる長さ $N$ の文字列 $s_0s_1\ldots s_{N-1}$ が与えられます。
• $0, 1, 2, \ldots, N$ と番号づけられた $(N+1)$ 個の頂点と、下記の辺からなる単純無向グラフ $G$ を考えます。
  • 各 $i = 0, 1, \ldots, N-1$ について、頂点 $i$ と頂点 $(i+1)\bmod N$ を結ぶ無向辺がある。
  • 各 $i = 0, 1, \ldots, N-1$ について、$s_i = $ 1 のとき、かつ、そのときに限り、頂点 $i$ と頂点 $N$ を結ぶ無向辺がある。
  • 上記の他に辺はない。

• さらに、$G$ の各辺を任意に向きづけして有向グラフ $G'$ を作ります。
  • すなわち、$G$ の各無向辺 $\lbrace u, v \rbrace$ を、$u$ から $v$ への有向辺 $(u, v)$ と $v$ から $u$ への有向辺 $(v, u)$ のどちらか一方で置き換えます。
• 各 $i = 0, 1, \ldots, N$ について、$G'$ における頂点 $i$ の入次数を $d_i$ とおくとき、得られる数列 $(d_0, d_1, \ldots, d_N)$ としてありえるものの個数を $998244353$ で割った余りを出力してください。

• $3 \leq N \leq 10^6$
• $N$ は整数
• $s_i$ は 0 または 1

包除原理とか考えたけど全然まとまらなかった。想定解法はDP。

有向辺の張り方は $2^{N+Sの中の1の個数}$ だけ存在するが、 この中には $d=(d_0, d_1, \ldots, d_N)$ が同じになるものが存在する。

$d$ が同じとなる有向辺の張り方には、必ず有向サイクルが含まれる。
そのサイクルの辺の向きを逆転させたもの同士が同じ $d$ となる。
それ以外に $d$ が同じとなる張り方はない。

略証

ある辺の張り方に対し、ある1辺を反転させつつ、d を保ちたいとする。

  ...→○→○←...      ...→○⇐○←...
       ↓  ↓                ↓  ↓

すると、反転させた辺の両端の頂点の辻褄を合わせるためには、
連鎖的に反転させるしかない。

  ...→○⇐○←...      ...⇐○⇐○←...
       ↓  ↓                ↓  ⇑

連鎖を終わらせるには、どこかの頂点で合流し、サイクルを作るしかない。

以下の方針で答えを求めることを考える。

• $d$ ではなく、「辺の張り方」の方を数え上げる
• 有向サイクルができるような辺の張り方は、反転させたものを同一視する

⓪→①→②
↓  ↑  ↓    ①②③⑧ や ①②③④⑤⑧ の
⑦  ⑧←③    有向サイクルがある
↑  ↑  ↓
⑥→⑤←④

↓①②③⑧を反転  ↘①②③④⑤⑧を反転

⓪→①←②          ⓪→①←②
↓  ↓  ↑          ↓  ↓  ↑
⑦  ⑧→③          ⑦  ⑧←③
↑  ↑  ↓          ↑  ↓  ↑
⑥→⑤←④          ⑥→⑤→④

これらは1つと数えたい。

これは、「時計回りの有向サイクルが含まれない辺の張り方」を数えればよい。

略証?

○→○→○→○    外側の 4x4 のサイクル
↑          ↓
○  ○→○  ○    中ほどの 3x2 のサイクル
↑  ↑  ↓  ↓
○  ○←○  ○    内側の 2x2 のサイクル
↑  ↑  ↓  ↓
○←○←○←○    3つの時計回りサイクルを含む。

○→○→○→○
↑          ↓    外側のサイクルは、元のサイクルは
○  ○←○  ○    中央下の辺が反転したためなくなるが、
↑  ↓  ↑  ↓    代わりに凹を上下反転させたような
○  ○←○  ○    サイクルが新たにできる
↑  ↓  ↑  ↓
○←○→○←○

○←○←○←○
↓          ↑
○  ○→○  ○
↓  ↑  ↓  ↑
○  ○←○  ○
↓  ↑  ↓  ↑
○→○→○→○

①→②→⑤    ①←②→⑤    ①②③④を反転させた結果、
↑  ↓  ↓    ↓  ↑  ↓    それと外部的に接する②⑤⑥③が
④←③←⑥    ④→③←⑥    新たな時計回りサイクルとなった

円環は難しいので、まずは $0$ と $N-1$ が繋がっていない場合を考える。
$i$ と $i+1$ を結ぶ辺を「リム辺」、$i$ と $N$ を結ぶ辺を「スポーク辺」と呼ぶことにする。

N=5  S=01101

⓪--①--②--③--④    ←リム辺
      ＼｜,___／      ←スポーク辺
        ⑤

時計回りサイクルができる条件は、以下を満たす $0 \le i \lt j \le N-1$ が存在することと同じになる。
（厳密には、リム辺だけで作られるサイクルが漏れているが、それは最後に考慮する）

• $N→i$ の向きにスポーク辺が張られている。
• $i$ から $j$ の間のリム辺は、全て → の向きに張られている。
• $j→N$ の向きにスポーク辺が張られている。

よって、DPでは「どこかで $N→i$ の向きにスポーク辺が張られた後、リム辺は全て → の向きである」という状態（これを状態★とする）を 他と区別して持っておけば、状態★から $j→N$ の向きにスポーク辺を張るという遷移を禁止することで、 時計回りサイクルができないように辺の張り方を決めることができる。

このように直線の場合は2つの状態を管理するDPで、数え上げられる。

• $\mathrm{DP}_{直線}[i,j]:=i$ までのリム辺・スポーク辺の張り方を決めた後、｛$j=0/1$：状態★である/ない｝場合の辺の張り方の個数

円環の場合は、ループを跨いで時計回りサイクルができてしまう場合もあるため、それを判別したい。
以下の3状態を、先ほどとは独立に持たせる。

• 0) ⓪からリム辺は全て→の向きである状態が続いているが、まだ $j→N$ の向きに張られたスポーク辺は無い
• 1) ⓪からリム辺は全て→の向きである状態が続いた後で $j→N$ の向きに張られたスポーク辺がある
  • $N-1$ の時に★である場合、時計回りサイクルができてしまうことが確定している
• 2) ⓪から、はじめて $j→N$ の向きにスポーク辺が張られる前に、←の向きに張られたリム辺が存在する
  • $N-1$ の時に★であっても、時計回りサイクルができないことが確定している

• $\mathrm{DP}[i,j,k]:=i$ までのリム辺・スポーク辺の張り方を決めた後、｛$j=0/1$：状態★である/ない｝｛$k=0/1/2$：上記の3状態のどれか｝の場合の辺の張り方の個数

これで、丁寧に遷移を考えてDPした後、ループまたぎの時計回りサイクルができる「$j=0,k=1$」以外の和をとる。

……と、正しい値より2だけ多くなる。
先述したように上記のDPでは、リム辺だけで作られる時計回りサイクルが考慮されていない。
リム辺がサイクルを形成する場合、スポーク辺は「全て $N$ から出る向き」「全て $N$ に入る向き」以外はあり得ない。
（他の場合は、どこかで $N$ を経由する時計回りサイクルができてしまうので、既にDPで除かれている）
よって、この2個をDPの結果から除いたものが、最終的な答えとなる。

例外として、$S$ が全て'0'の場合はシンプルな円環のグラフとなるので、 時計回りサイクルができる辺の張り方は1個となり、$2^N-1$ が答えとなる。

Python3

def solve(n, s):
    MOD = 998244353
    c1 = s.count('1')
    if c1 == 0:
        return pow(2, n, MOD) - 1

    # 閉じる: 時計回りが続いた後、i→N の辺を張る
    # 開く:   i←N の辺を張ったあと、時計回りが続いている。
    # dpの1桁目: 0:開始から時計回りが続いている。まだ閉じられていない。
    #           1:開始から時計回りが続いた後、閉じられた。（今、時計回りが続いているかは関係ない）
    #           2:開始から閉じられる前に時計回りが崩れ、閉じられないことが確定している。
    # dpの2桁目: 0:今現在、開かれている
    #           1:今現在、開かれていない（最後にi←Nの辺が張られた後、時計回りが崩れている）
    dp00 = 0
    dp01 = 1
    dp10 = 0
    dp11 = 0
    dp20 = 0
    dp21 = 0
    for i in range(n):
        if s[i] == '0':
            ndp00 = dp00
            ndp01 = dp01
            ndp10 = dp10
            ndp11 = dp10 + dp11 * 2
            ndp20 = dp20
            ndp21 = dp00 + dp01 + dp20 + dp21 * 2
        else:
            ndp00 = dp00 + dp01
            ndp01 = 0
            ndp10 = dp10 * 2 + dp11 * 2
            ndp11 = dp01 + dp10 + dp11 * 2
            ndp20 = dp00 + dp01 + dp20 * 2 + dp21 * 2
            ndp21 = dp00 + dp01 + dp20 + dp21 * 2
        dp00 = ndp00 % MOD
        dp01 = ndp01 % MOD
        dp10 = ndp10 % MOD
        dp11 = ndp11 % MOD
        dp20 = ndp20 % MOD
        dp21 = ndp21 % MOD
    ans = (dp00 + dp01 + dp11 + dp20 + dp21 - 2) % MOD
    return ans


n = int(input())
s = input()
ans = solve(n, s)
print(ans)

C - Grid Coloring 3

• $H$ 行 $W$ 列のグリッドがあり、はじめすべてのマスは無色です。
• このグリッドに対して、下記の手順を好きな回数だけ繰り返します。
  • まず、$1$ 以上 $C$ 以下の整数 $i$ と、マス $1$ 個を選ぶ。
  • その後、選んだマスおよび、選んだマスと同じ行にあるすべてのマス、選んだマスと同じ列にあるすべてのマスの、合計 $(H+W-1)$ マスを色 $i$ で塗る（すでに色が塗られている場合は、その色を色 $i$ で上書きする）。

• 上記の手順を繰り返して得られる、すべてのマスに色が塗られている グリッドとしてありえるものの個数を $998244353$ で割った余りを出力してください。

• $1 \leq H, W \leq 400$
• $1 \leq C \leq 10^9$
• 入力はすべて整数

重複の除き方がなかなか見えづらい。

公式Editorialを読んだ。

操作を逆順に考える。
逆順の場合、各操作では「（上書きではなく）まだ塗っていないマスのみを塗る」とすることで、最終的な色の配置が元の順で操作した場合と同じになる。
（以降、説明中の「○回目」は、逆順での操作順とする）

ある「最終的な色の配置」から「操作列」を復元する際、重複を除き一意に定まるように復元ルールを決める。
このルールに則った操作列は、1つ1つ異なる最終配置に対応するので、 あり得る操作列の個数を数えることで、答えとなる。

どのようにルールを定めれば良いか調べる。
未決定色配置 $A=((A_{1,1},A_{1,2},...,A_{1,W}),...,(A_{H,1},...,A_{H,W}))$ を、 色を表す数値の2次元配列として、操作結果がこれと一致する操作列を先頭から決めていくことを考える。
操作を決定する毎に、その操作で色が塗られた行または列は抜いて隙間を詰めていき、$A$ は徐々に小さくなっていくことをイメージする。

• 1回目の操作は特殊なので後で考える。
• 2回目以降は「行だけ」「列だけ」の操作に限定してよい。十字に塗る操作も、これらを続けておこなったものと扱う。
  • それぞれ「行操作」「列操作」とする。
• 連続でおこなった行操作は入れ替え可能なので、まとめて「全て同時におこなった1回の操作」と見なす。
  • これを「行同時操作」とする。色は行ごとに異なってもよい。
  • その時点の $A$ で操作可能な行は全て操作する。行同時操作後の $A$ には、もう「全体が1色で塗られている行」は存在してはいけない。
• 列操作も同様。
  • 連続でおこなった列操作は、「列同時操作」として同時におこなわれたと見なす。
  • 列同時操作後の $A$ には、もう「全体が1色で塗られている列」は存在してはいけない。

「行同時操作」「列同時操作」を交互におこなうことで操作列を復元可能となる。
未決定色配置 $A$ のうち、今の行/列操作で確定できるものは全て確定させる、という貪欲なルールにより、操作列は一意に決まる。

このルールに則った操作列を数え上げる。
「この行同時操作をおこなうと、直前の列同時操作で「全体が1色で塗られている列」が残っていたことになってしまう」ようなものを数え上げないように注意して遷移する。

主に注意すべきは以下の2パターンとなる。「行同時操作」の例として説明しているが、行/列逆転させて列同時操作においても同様の議論が成り立つ。

• ある行同時操作において、選択した全ての行を同じ色 $c$ で塗った場合、次の列同時操作で使える色数が $C-1$ 色になる。
  • 行同時操作を $i$ 回目の操作とする。
  • もし $i+1$ 回目の列同時操作で $c$ を使った場合、$i-1$ 回目の列同時操作後に「全体が $c$ で塗られている列」が残っていたことになり、前提に矛盾。
  • よって $c$ は使えず、$C-1$ 色から選ぶことになる。
  • ※ $i$ 回目で2色以上の色で塗った場合は、$i+1$ 回目では $C$ 色全て使える。
• ある行同時操作において、全ての行を操作対象とし、かつ同じ色で塗ることはできない。
  • 全てが同じ色となるので、直前の列同時操作後で「全体が $c$ で塗られている列」が残っていたことになり、前提に矛盾。
  • この遷移は禁止される。

これらを区別して数え上げるため、以下のDPを考える。$i,j$ の小さい方から埋めていけばよい。

• $\mathrm{DP}[i,j,k,l]:=$ 操作列の途中まで決めた結果、残っている未決定配置 $A$ のサイズが $i \times j$ であり、次に操作するのが｛$k=0/1$：行同時操作/列同時操作｝であり、使える色は｛$l$：$C$ 色/$C-1$ 色｝である場合の、残りの操作列の決め方の数

状態数 $O(N^2)$、各 $(i,j)$ に対し“次にいくつの行/列を操作するか”という $O(N)$ の遷移があるので、計算量 $O(N^3)$ となる。

初期状態は以下のようになる。（行同時操作 $(k=0)$ の場合だが、$k=1$ も行列入れ替えれば同様）

• $\mathrm{DP}[i,0,0]=1$
  • 直前の列同時操作において全て塗られた場合、残りマスはないので1通り。
• $\mathrm{DP}[1,j,0]=0, j \gt 0$
  • 残りが1行の場合、必然的に各列が「全体が1色で塗られている列」となり、前提に違反するので0通り。

次に遷移だが、$\mathrm{DP}[i,j,0,l]$ の求め方は、$i$ 行のうち同時操作する行数を $r$ として、

• 行の決め方は $\dbinom{i}{r}$ 通り
• 色の塗り方は $l^r$ 通り
  • うち $l^r-l$ 通りで複数の色が混在し、$l$ 通りで全てが同じ色（それぞれ $l_{\text{next}}=C,C-1$）
• 残るマスの塗り方は、$\mathrm{DP}[i-r,j,1,l_{\text{next}}]$
• ただし $r=i$ かつ全てを同じ色で塗るのは禁止

これらを $r=1～i$ で足し合わせたものとなる。
$i$ と $j$ を入れ替え、$k$ を反転させたものは同じ値になるので、計算を省けば定数倍の改善になる。

最後に、1回目の操作を考える。

• 最初の未決定配置 $A$ には、以下をともに満たす色がちょうど1色存在する。色 $c$ とする。
  • 行全体が $c$ で塗られた行が存在する。
  • 列全体が $c$ で塗られた列が存在する。
• ① 色 $c$ のみで「行同時操作」を行う。（行全体が $c$ で塗られた行を全て操作する）
• ② 色 $c$ のみで「列同時操作」を行う。
• ③ 「行同時操作」を行う。ただし通常と以下の違いがある。
  • 使える色は $c$ 以外の $C-1$ 色（①の前提に矛盾しないように）
  • 操作する行数は $r=0$ でもよい。（①②の後、列操作から始まる場合を考慮）
    • その場合、列同時操作で使える色は $C-1$ 色
  • 操作対象行数が $r \ge 1$ の場合、それらを全て同じ色で塗っても、次の列同時操作で使えるのは $C$ 色
    • ①において $c$ で塗った行と合わせ、混在していると見なせるため
  • $i=1$ でも許容する

①②③のそれぞれで操作する行数（列数）を決めれば、操作列の数はDPを参照することで $O(1)$ で計算できる。
こちらもDPと同様、$O(N^3)$ で全て求められる。

Python3

import numpy as np
from numba import njit


@njit('(i8,i8,i8)')
def solve(h, w, c):
    MOD = 998244353

    def mod_pow(x, a, MOD):
        ret = 1
        cur = x
        while a > 0:
            if a & 1:
                ret = ret * cur % MOD
            cur = cur * cur % MOD
            a >>= 1
        return ret

    def prepare_factorials(n, MOD):
        factorials = np.ones(n + 1, np.int64)
        for m in range(1, n + 1):
            factorials[m] = factorials[m - 1] * m % MOD
        inversions = np.ones(n + 1, np.int64)
        inversions[n] = mod_pow(factorials[n], MOD - 2, MOD)
        for m in range(n, 1, -1):
            inversions[m - 1] = inversions[m] * m % MOD
        return factorials, inversions

    n = max(h, w)
    facts, finvs = prepare_factorials(n, MOD)
    ncr = np.zeros((n + 1, n + 1), np.int64)
    for i in range(n + 1):
        for j in range(i + 1):
            ncr[i, j] = facts[i] * finvs[j] % MOD * finvs[i - j] % MOD

    pow_c = np.ones((n + 1, 2), np.int64)
    for i in range(1, n + 1):
        pow_c[i, 0] = pow_c[i - 1, 0] * c % MOD
        pow_c[i, 1] = pow_c[i - 1, 1] * (c - 1) % MOD

    dp = np.zeros((h + 1, w + 1, 2, 2), np.int64)
    for i in range(h):
        for j in range(w):
            if i > j and 0 <= j < h and 0 <= i < w:
                dp[i, j, 0, :] = dp[j, i, 1, :]
                dp[i, j, 1, :] = dp[j, i, 0, :]
                continue

            for l in (0, 1):
                use_color = c - l
                if j == 0:
                    dp[i, j, 0, l] = 1
                else:
                    result = 0
                    for ii in range(1, i + 1):
                        coloring = dp[i - ii, j, 1, 0] * (pow_c[ii, l] - use_color) % MOD
                        if ii < i:
                            coloring += dp[i - ii, j, 1, 1] * use_color
                            coloring %= MOD
                        result += ncr[i, ii] * coloring
                        result %= MOD
                    dp[i, j, 0, l] = result

                if i == 0:
                    dp[i, j, 1, l] = 1
                else:
                    result = 0
                    for jj in range(1, j + 1):
                        coloring = dp[i, j - jj, 0, 0] * (pow_c[jj, l] - use_color) % MOD
                        if jj < j:
                            coloring += dp[i, j - jj, 0, 1] * use_color
                            coloring %= MOD
                        result += ncr[j, jj] * coloring
                        result %= MOD
                    dp[i, j, 1, l] = result

    result = 1
    for i in range(1, h):
        for j in range(1, w):
            for k in range(w - j + 1):
                choice = ncr[h, i] * ncr[w, j] % MOD * ncr[w - j, k] % MOD
                coloring = choice * pow_c[k, 1] % MOD
                l = 1 if k == 0 else 0
                result += coloring * dp[h - i, w - j - k, 0, l]
                result %= MOD
    result *= c
    result %= MOD
    return result


h, w, c = map(int, input().split())
ans = solve(h, w, c)
print(ans)

D - Magnets

• 0 と 1 のみからなる $2$ つの長さ $N$ の文字列 $A = A_1A_2 \ldots A_N$ と $B = B_1B_2 \ldots B_N$ が与えられます。
• 左右に一列に並んだ $N$ 個のマスがあります。
• $i = 1, 2, \ldots, N$ について、左から $i$ 番目のマスはマス $i$ と呼ばれ、はじめマス $i$ には、$A_i$ = 1 ならばコマが $1$ 個置かれており、$A_i$ = 0 ならばコマは置かれていません。
• 下記の操作を好きな回数（ $0$ 回でも良い）だけ繰り返します。
  • まず、$1$ 以上 $N$ 以下の整数 $i$ を選ぶ。
  • そして、すべてのコマを同時に、マス $i$ に近づく方向に $1$ マス動かす。すなわち、各コマを次が成り立つように動かす： * そのコマの移動前の位置をマス $j$ 、移動後の位置をマス $j'$ とすると、
    • $i \lt j$ ならば $j' = j-1$
    • $i \gt j$ ならば $j' = j+1$
    • $i = j$ ならば $j' = j$

• 上記の操作の繰り返しによって、下記の条件を満たす状態にすることが可能かを判定し、可能な場合はそれまでに操作を行う回数としてありえる最小値を求めてください。
  • すべての $i = 1, 2, \ldots, N$ について次が成り立つ：
    • $B_i = $ 1 であるとき、かつ、そのときに限り、マス $i$ にコマが $1$ 個以上存在する。

• $T$ 個の独立なテストケースが与えられるので、それぞれについて答えを出力してください。

• $1 \leq T \leq 2 \times 10^5$
• $1 \leq N \leq 10^6$
• $T, N$ は整数
• $A, B$ はそれぞれ 0 と 1 のみからなる長さ $N$ の文字列
• $A_i = $ 1 である $i$ が存在する
• $B_i = $ 1 である $i$ が存在する
• すべてのテストケースにわたる $N$ の総和は $10^6$ 以下

操作は以下のように言い換えられる。最初に、$A,B$ ともに両端に'0'を1つずつ付け加えておく。

• $A$ の好きな連続する3要素を選び、うち小さい方から2要素を削除する。両端に0を1つずつ加える。

以下の2段階で一致させる。

• フェイズ1: $A$ にある最左の1～最右の1の間の並びを（左右位置は異なってもいいので）$B$ に一致させる。
• フェイズ2: その後、左右位置を合わせる。

B: 00010001111101100000

A: 10100011011110101011
↓                           何らかの操作で、並びをBにあわせる（フェイズ1）
A: 00000010001111101100
↓                           左右位置を合わせる（フェイズ2）
A: 00010001111101100000

左右位置を一旦無視するフェイズ1では、言い換えた操作のうち「2要素を削除」という部分だけ気にしておけばよい。

並びを合わせるに当たり、何個連続しているかが重要なので、ランレングス圧縮を計算しておく。

• $A$ の両端に便宜的に1個ずつの'0'を追加し、ランレングス圧縮する。
  • $R_A=(p_1,q_2,p_3,q_4,...,q_{k-1},p_k)$
  • $p$ は'0'の連続、$q$ は'1'の連続を表す。
• $B$ も同様
  • $R_B=(r_1,s_2,r_3,s_4,...,r_{l-1},s_l)$
  • $r$ は'0'の連続、$s$ は'1'の連続を表す。

A: 10100011011110101011
    ↓
RA:  0  1  0  1 000 11  0 1111  0   1   0   1   0  11   0
    p1 q2 p3 q4  p5 q6 p7   q8 p9 q10 p11 q12 p13 q14 p15

B: 00010001111101100000
    ↓
RB: 0000  1 000 11111  0 11 000000
      r1 s2  r3    s4 r5 s6     r7

フェイズ1では、左から以下のように $B$ の並びに一致させていく。

• $i=j=2$ で初期化する。

• '1'を合わせる
  • $q_i$ から始まる'1'の並びを $|s_j|$ 個にする。
  • 足りなければ、$p_{i+1}$ を消して $q_{i+2}$ を繋げる。それでも足りなければ $q_{i+4},q_{i+6},...$ も繋げる。
  • '1'が余った場合は適当に消して、ぴったり $|s_j|$ 個に合わせる。
  • $j←j+1$ にする。$i$ も、$q_{x}$ までを使ったとして、$i←x+1$ にする。

• '0'を合わせる
  • $|r_j|$ 個以上連続した $p_i$ が出てくるまで、$i←i+1$ としていく。
    • その過程で個数の足りない $p_i$ とその次の $q_i$ は消していく。
  • $|r_j|$ 個以上連続した $p_i$ が出てきたら、ぴったり $|r_j|$ 個に合わせる。
  • $i←i+1,j←j+1$ にする。

これを交互に繰り返し、$s_{l-1}$ の1の連続まで一致させることができたら、達成可能。
その際にまだ $R_A$ の $p_i,...,q_{k-1}$ が余っている場合は、これも消す。

RB: 0000  1 000 11111  0  11 000000
      r1 s2  r3    s4 r5  s6     r7

Aの並びを合わせた結果
          1 000 11111  0  11
         q2  p5 q6+q8 p9 q10+q12      ←元のRAでの由来となる箇所

ただし、「一度に2個を消す」という操作しかできないため、消したい要素数が奇数の場合は次以降の要素に影響する。

A: ... 111111000111....  1の長さをBに合わせるため波線部の3つの1を消したい。
          ~~~             →奇数のため、次の0の連続を1つ犠牲にしないと
B: ... 111000111000....    ちょうど3つを消すことはできない。

'0'を奇数個消したい場合、以下の左端の'0'を消したいとして

• '011…' → 真ん中の'1'に操作する。次の'1'の連続が1つ短くなる。
• '010…' → 真ん中の'1'に操作する。2つ次の'0'の連続が1つ短くなる。

'1'を奇数個消したい場合、この'1'は2個以上の連続である。
（貪欲に合わせる過程で、'0'に挟まれた長さ1の'1'を削除する操作はできないし求められないので）

• '1101…' → '0'に操作することで、'0'が消え、2つ次の'1'の連続が1つ短くなって今の1の並びに繋がる。
  • 消したいのに次の'1'と繋がってしまうが、繋がった分も消していく。
• '1100…' → 2番目の'1'に操作することで、次の'0'の連続が1つ短くなる。

「今、1を合わせているか0を合わせているか」「次に影響するフラグ」を持ちながら、 これらを場合分けして実装していくとよい。

基本的には以上でよいのだが、考慮から漏れているパターンがある。

フェイズ1では、$A$ の「最左の'1'～最右の'1'の範囲」を $B$ に一致させることを考えてきた。
操作は「2要素を削除する」ものとしてきたが、 「最左の'1'を中心として操作した場合」は範囲から「1要素しか削除しない」ことができる。
（※最右を中心とした操作は、最右の'1'が1個だけ余ったときとして既に考慮されている）

ただし、この操作は2回以上行う必要は無い。2回以上行うなら、より右を中心として2要素の削除を1度におこなった方がよい。

よって、「入力のままの $A$」「最初に最左の'1'を中心として1回操作した後の $A$」を2回調べればよい。

フェイズ1で、$A$ の並びを $B$ にあわせるための操作回数を $t$ 回とする。
（最初に最左の'1'を中心として確定で1回行う分は除く）

操作1回毎に両端に'0'が追加されるので、フェイズ1後の $A$ の最初の'0'の連続は、$|p_1|+t$ となっている。

$A_1$ または $A_N$ に操作することで、1回につき1つ、左右位置をずらせる。

よって、$\mathrm{abs}(|p_i|+t - |r_1|)$ 回の操作で左右位置を合わせられ、フェイズ1の操作回数と合わせて答えとなる。

公式Editorialでは、上記の解法で言い換えた操作をさらに言い換えている。

• $P(x)$ を「ちょうど $x$ 回の操作で $A$ を $B$ にすることができる」という真偽値とする。
• $P(x)$ の判定は、以下のように言い換えられる。
  • $A$ の左端と右端に $x$ 個ずつの'0'を追加する。
  • $A$ を「奇数長」の部分文字列に分割する。
  • 各部分文字列を、その中の最大値に変換する。（'1'が含まれていれば'1'、'0'のみなら'0'）
  • この結果を $B$ にできるか？

'0'が連続する個数は増やせないので、 左端で'0'が連続する個数、右端で'0'が連続する個数は、操作で $A$ の両端に $x$ 個ずつの'0'を追加した後、いずれも $B$ のそれらより多くないといけない。
つまり、少なくとも $m := \max(|r_1|-|p_1|,|r_l|-|p_k|)$ 回以上の操作が必要である。

RA:  0  1  0  1 000 11  0 1111  0   1   0   1   0  11   0
    p1 q2 p3 q4  p5 q6 p7   q8 p9 q10 p11 q12 p13 q14 p15

RB: 0000  1 000 11111  0 11 000000
      r1 s2  r3    s4 r5 s6     r7

Aは、少なくとも |r7|-|p15| の 5 回操作し、
右端に連続する'0'の個数をB以上にしておく必要がある。

ところで、$x \ge m+2$ の時に $P(x)$ が真となる場合、$P(x-2)$ も必ず真となる。
$x \ge m+2$ の時、左端と右端の'0'の連続それぞれに「$B$ と一致させるためには消さなければいけない余分な'0'」が偶数個ずつくっついた状態となっている。その'0'は最初から無かったことにして問題ない。

よって、$P(m),P(m+1)$ の2つの場合のみを調べれば十分である。

そしてこの判定は、上記解法のフェイズ1のような貪欲で可能である。

Python3

from itertools import groupby


def update(ans, l):
    d, r = divmod(l, 2)
    stuck_out = r == 1
    if stuck_out:
        d += 1
    return ans + d, stuck_out


def sub(rla, rlb, init_stuck_out):
    ans = 0
    n = len(rla)
    m = len(rlb)
    i = 1
    j = 1
    state = -1
    stuck_out = init_stuck_out
    while i < n and j < m:
        ca, la = rla[i]
        cb, lb = rlb[j]

        force_stick_out = False
        if stuck_out:
            if state != 0 and ca == 1 and la == 1:
                force_stick_out = True
            else:
                la -= 1

        if state > 0:
            assert cb == 1
            if ca == 0:
                ans, stuck_out = update(ans, la)
                i += 1
            else:
                if state > la:
                    state -= la
                    stuck_out = False
                    i += 1
                else:
                    la -= state
                    state = 0
                    ans, stuck_out = update(ans, la)
                    i += 1
                    j += 1
        elif state == 0:
            assert cb == 0
            if ca == 0:
                if la >= lb:
                    la -= lb
                    state = -1
                    ans, stuck_out = update(ans, la)
                    i += 1
                    j += 1
                else:
                    ans, stuck_out = update(ans, la)
                    i += 1
            else:
                ans, stuck_out = update(ans, la)
                i += 1
        else:
            assert ca == cb == 1
            if la >= lb:
                la -= lb
                state = 0
                ans, stuck_out = update(ans, la)
                i += 1
                j += 1
            else:
                state = lb - la
                stuck_out = False
                i += 1

        if force_stick_out:
            stuck_out = True

    if j < m:
        return 1 << 60

    if i < n:
        assert rla[i][0] == 0
        la = rla[i][1] - int(stuck_out)
        for ii in range(i + 1, n):
            la += rla[ii][1]
        ans, _ = update(ans, la)

    la = rla[0][1] + ans
    lb = rlb[0][1]

    ans += abs(la - lb)
    return ans


def solve(n, a, b):
    rla = [(int(c), len(list(itr))) for c, itr in groupby('0' + a + '0')]
    rlb = [(int(c), len(list(itr))) for c, itr in groupby('0' + b + '0')]
    rla.pop()
    rlb.pop()

    ans1 = sub(rla, rlb, False)
    ans2 = sub(rla, rlb, True) + 1
    ans = min(ans1, ans2)
    if ans >= 1 << 60:
        return -1
    return ans


t = int(input())
for _ in range(t):
    n = int(input())
    a = input()
    b = input()
    print(solve(n, a, b))