AtCoder Regular Contest 194 (Div. 2) A,B,C,D,E問題メモ

AtCoder Regular Contest 194 (Div. 2)

ちょっと悩みつつ、でも時間内に答えに辿り着ける、というくらいの難易度が一番参加してて楽しい。もちろんそれに当てはまる難易度帯は人によって変わるが、Div.2は自分にとってちょうどよく、Div.1と分けることで頻度が増えたことはありがたい。

A - Operations on a Stack

問題文

長さ $N$ の整数列 $(A_1, A_2, \ldots, A_N)$ が与えられます。また、列 $S$ があり、 $S$ ははじめは空列です。
$i = 1, 2, \ldots, N$ の順に、それぞれの $i$ について、下記の $2$ つの操作のうちちょうど $1$ つを行います。
- $S$ の末尾に $A_i$ を要素として追加する。
- $S$ の末尾の要素を削除する。ただし $S$ が空のときは、この操作を行うことを選択できない。

すべての操作を終えた後の、 $S$ の要素の総和としてあり得る最大値を出力してください。

制約

$1 \leq N \leq 2 \times 10^5$
$-10^9 \leq A_i \leq 10^9$
入力はすべて整数

解法

$i$ 番目の操作でpopを選択したら、 $A_i$ はaddできないという点が特徴的。

この操作でできる $S$ は、以下に言い換えられる。

$A$ から連続する2個の要素を削除して間を詰める、ということを好きなだけおこなった残り
（2個の内、前者を一度addしてpopした要素、後者をpopしたために追加されなかった要素と考える）

先頭から採用するか捨てるか決めていくDPを考える。
$A_i$ を採用しようと思うと、その直前に採用したのが $A_{i-1},A_{i-3},...$ など、奇数個前である状態のみから遷移できる。

$i$ のたびに全ての“奇数個前”を確認していくとTLEするので、DPにはこの累積Maxを持たせるようにすればよい。

$\mathrm{DP}[i]:=A_i$ までを採用か不採用か決め、最後の採用が $i-(0以上の偶数)$ である状態の合計最大値
初期状態・遷移
- $\mathrm{DP}[-1]=-\infty,\mathrm{DP}[0]=0$
- $\mathrm{DP}[i]=\max(\mathrm{DP}[i-1]+A_i,\mathrm{DP}[i-2])$

$\mathrm{DP}[N]$ が答え。

Python3

B - Minimum Cost Sort

問題文

$(1,2,\ldots,N)$ の順列 $P=(P_1,P_2,\ldots,P_N)$ が与えられます。
高橋君は $P$ に対して次の操作を繰り返し( $0$ 回でも良い)行う事ができます。
- $1\leq i\leq N-1$ をみたす整数を $1$ つ選ぶ。コスト $i$ を支払い、 $P_i$ と $P_{i+1}$ を交換する。

$P$ を昇順にソートするために必要なコストの総和の最小値を求めてください。

制約

$2 \leq N \leq 2\times 10^5$
$(P_1,P_2,\ldots,P_N)$ は $(1,2,\ldots,N)$ の順列
入力はすべて整数

解法

「隣り合う要素の交換を繰り返して昇順にソートする」といえばバブルソート。
今回は交換位置によってコストが変わるので、なるべく $i$ が小さい左の方で交換したい。

バブルソートに関する前提知識として、以下がある。

バブルソートの最小swap回数は転倒数と一致する
「(大,小) が隣接する箇所をswapして (小,大) にする」という操作を繰り返せば、操作順に関係なく最小回数でのソートを達成できる

答えの下限を見つけ、その下限を達成する方法を見つけるという考察過程を取る。

$i$ より左にある $P_i$ より大きな値（つまり、 $j \lt i$ かつ $P_i \lt P_j$ を満たす $j$ ）の個数を $L(i)$ として、 $i$ につき $L(i)$ 回のswapは必須である。
また、1回のswapで1しか左に行かないため、 $i-1,i-2,...,i-L(i)$ のコストは必ずかかる。

つまり、全体では $\displaystyle \sum_{i=1}^N \sum_{j=1}^{L(i)} i-j$ は必ずかかる。

ここからコストが増えてしまう場合というのは、まだ「 $i$ より左にあり、 $P_i$ より大きな値」が残っているのに「 $i$ より右にあり、 $P_i$ より小さな値」との関係性を解消するために $P_i$ をswapして右に動かしてしまう操作である。以降の $P_i$ を左に持っていく操作コストが1ずつ増える。

逆に言うと、複数の (大,小) の隣接箇所がある場合、左から操作を優先すれば上記のようなことは発生せず、下限を達成できる。

$L(i)$ は、転倒数と同じような要領で FenwickTree などで求められる。

Python3

        
          
          
              
              from operator import add
 
 
class FenwickTreeInjectable:
    def __init__(self, n, identity_factory, func):
        self.size = n
        self.tree = [identity_factory() for _ in range(n + 1)]
        self.func = func
        self.idf = identity_factory
        self.depth = n.bit_length()
 
    def add(self, i, x):
        i += 1
        tree = self.tree
        func = self.func
        while i <= self.size:
            tree[i] = func(tree[i], x)
            i += i & -i
 
    def sum(self, i):
        i += 1
        s = self.idf()
        tree = self.tree
        func = self.func
        while i > 0:
            s = func(s, tree[i])
            i -= i & -i
        return s
 
    def lower_bound(self, x, lt):
        """
        累積和がx以上になる最小のindexと、その直前までの累積和
 
        :param lt: lt(a, b) で a < b ならTrueを返す関数
        """
        total = self.idf()
        pos = 0
        tree = self.tree
        func = self.func
        for i in range(self.depth, -1, -1):
            k = pos + (1 << i)
            if k > self.size:
                continue
            new_total = func(total, tree[k])
            if lt(new_total, x):
                total = new_total
                pos += 1 << i
        return pos + 1, total
 
    def debug_print(self):
        prev = 0
        arr = []
        for i in range(self.size):
            curr = self.sum(i)
            arr.append(curr - prev)
            prev = curr
        print(arr)
 
 
def solve(n, ppp):
    fwt = FenwickTreeInjectable(n, int, add)
    ans = 0
    for i, p in enumerate(ppp):
        p -= 1
        inv = i - fwt.sum(p)
        fwt.add(p, 1)
        ans += (i + (i - inv + 1)) * inv // 2
    return ans
 
 
n = int(input())
ppp = list(map(int, input().split()))
ans = solve(n, ppp)
print(ans)

            

        
      

C - Cost to Flip

問題文

$0$ と $1$ のみからなる $2$ つの長さ $N$ の整数列 $A = (A_1, A_2, \ldots, A_N)$ と $B = (B_1, B_2, \ldots, B_N)$ が与えられます。
$A$ に対して下記の操作を好きな回数（ $0$ 回でも良い）だけ行うことができます。
1. まず、 $1 \le i \le N$ を満たす整数 $i$ を選び、 $A_i$ の値を反転する（元の値が $0$ ならば $1$ に、 $1$ ならば $0$ に変更する）。
2. その後、操作のコストとして、 $\sum_{k=1}^{N}A_kC_k$ 円を支払う。
上記の手順 2. におけるコストの計算には、手順 1. で変更が加えられた後の $A$ を用いることに注意してください。

$A$ を $B$ に一致させるために支払う合計費用の最小値を出力してください。

制約

$1 \leq N \leq 2 \times 10^5$
$A_i, B_i \in \lbrace 0, 1\rbrace$
$1 \leq C_i \leq 10^6$
入力はすべて整数

解法

$(A_i,B_i)$ の組で $C_i$ を4通りに分類する。 $i$ の順番は実質関係ないので、分類ごとにソートする。

20
1 1 1 1 0 0 1 1 0 0 0 1 0 1 0 1 1 0 1 0
0 0 0 1 1 1 0 1 1 0 0 0 0 0 0 1 0 1 0 0
52 73 97 72 54 15 79 67 13 55 65 22 36 90 84 46 1 2 27 8
↓
(0,0): 8, 36, 55, 65, 84
(0,1): 2, 13, 15, 54
(1,0): 1, 22, 27, 52, 73, 79, 90, 97
(1,1): 46, 67, 72

$A$ を $B$ にするのに変更が必要なのは $(0,1)$ と $(1,0)$ で、このコストを安くするには以下の操作が最適である。

$(1,0)$ のコストが高い方から 1→0 にする
その後、 $(0,1)$ のコストが低い方から 0→1 にする

■上から順に操作

  組  Ci  コスト
(1,0) 97  (1,0)の未操作分+(1,1)の全て  1+22+27+52+73+79+90 + 46+67+72
(1,0) 90  (1,0)の未操作分+(1,1)の全て  1+22+27+52+73+79    + 46+67+72
(1,0) 79  (1,0)の未操作分+(1,1)の全て  1+22+27+52+73       + 46+67+72
  :
(1,0)  1  (1,0)の未操作分+(1,1)の全て                        46+67+72
(0,1)  2  (0,1)の既操作分+(1,1)の全て  2                   + 46+67+72
(0,1) 13  (0,1)の既操作分+(1,1)の全て  2+13                + 46+67+72
  :
(0,1) 54  (0,1)の既操作分+(1,1)の全て  2+13+15+54          + 46+67+72
                                     └──総コストはこれの総和───┘

コストは以下の和となる。「 $G_{0,0}:=(0,0)$ の組に分類された $C_i$ を昇順ソートした列」とする。（他の組も同様）

$G_{0,1}$ の、先頭からの累積和の総和
$G_{1,0}$ の、先頭からの累積和の総和（末尾を除く）
$G_{1,1}$ の総和 × $(|G_{0,1}|+|G_{1,0}|)$

ところで、 $(1,1)$ は「一旦0にしておいて、後から1に戻す」とした方がコストが安くなる場合もある。（この操作を★とする）

$(1,1)$ に分類されたある値 $x$ に対して★の操作をする場合、各 $G$ を以下のようしてからコストを求めたものと言い換えられる。

$G_{1,1}$ から $x$ を除き、 $G_{0,1},G_{1,0}$ の双方に（昇順を保ちつつ） $x$ を追加する

この変更後の各 $G_{i,j}$ を、 $G'_{i,j}$ とする。コストは、 $G_{0,1},G_{1,0}$ の中で $x$ 以下である値の個数をそれぞれ $k,l$ として、

$x$ を 1→0 にするとき、 $\mathrm{sum}(G_{0,1}[1～k]) + \mathrm{sum}(G'_{1,1})$ のコストがかかる
$x$ を 0→1 にするとき、 $\mathrm{sum}(G_{1,0}[1～l])+x + \mathrm{sum}(G'_{1,1})$ のコストがかかる
$x$ が0になっている間、つまり $k+l$ 回分の操作で、 $x$ のコストがかからなくなる

これで差分更新できる。
$G_{0,1},G_{1,0}$ の個数と値のそれぞれに対する FenwickTree などで管理できる。

複数の値に対して★をするときも、1つずつ順番に差分を考えていけばよい。

ただ、 $G_{1,1}$ の全ての部分集合について★を試すわけにもいかない。
$G_{1,1}$ に含まれる任意の2値 $x,y$ について「 $x,y$ 以外の $G_{1,1}$ の要素に対する★操作の有無が同じで、 $x$ にのみ★をおこなう場合と、 $y$ にのみ★をおこなう場合では、 $x$ にのみおこなった方が必ずよい」という関係性が成り立つなら、その順に試していくことができる。

直感的には「値が大きい順」がよさそうで、実際にそれは正しいが、証明しようとすると少し難しい。

physics0523氏によるユーザー解説

ともかく、 $G_{1,1}$ の要素を大きい方から★にした場合のコストを差分で計算していき、その中でコスト最小のものが答えとなる。

ただ、差分の変化を表す関数は凸ではない？
凸なら「途中で差分が非負になったら、もう減少させられなくなったということなので打ち切る」が成り立つはずだが、それだとWAだった。
途中で非負になろうと、全てを試すことにしたらACした。この辺、ちゃんと原因を理解できてない。

Python3

        
          
          
              
              from itertools import accumulate
from operator import add
 
 
class FenwickTreeInjectable:
    def __init__(self, n, identity_factory, func):
        self.size = n
        self.tree = [identity_factory() for _ in range(n + 1)]
        self.func = func
        self.idf = identity_factory
        self.depth = n.bit_length()
 
    def add(self, i, x):
        i += 1
        tree = self.tree
        func = self.func
        while i <= self.size:
            tree[i] = func(tree[i], x)
            i += i & -i
 
    def sum(self, i):
        i += 1
        s = self.idf()
        tree = self.tree
        func = self.func
        while i > 0:
            s = func(s, tree[i])
            i -= i & -i
        return s
 
    def lower_bound(self, x, lt):
        """
        累積和がx以上になる最小のindexと、その直前までの累積和
 
        :param lt: lt(a, b) で a < b ならTrueを返す関数
        """
        total = self.idf()
        pos = 0
        tree = self.tree
        func = self.func
        for i in range(self.depth, -1, -1):
            k = pos + (1 << i)
            if k > self.size:
                continue
            new_total = func(total, tree[k])
            if lt(new_total, x):
                total = new_total
                pos += 1 << i
        return pos + 1, total
 
    def debug_print(self):
        prev = 0
        arr = []
        for i in range(self.size):
            curr = self.sum(i)
            arr.append(curr - prev)
            prev = curr
        print(arr)
 
 
def solve(n, aaa, bbb, ccc):
    ddd = [[[], []], [[], []]]
    for i in range(n):
        ddd[aaa[i]][bbb[i]].append(ccc[i])
    ddd[0][1].sort()
    ddd[1][0].sort()
    ddd[1][1].sort()
 
    fwt_val01 = FenwickTreeInjectable(10 ** 6 + 1, int, add)
    fwt_cnt01 = FenwickTreeInjectable(10 ** 6 + 1, int, add)
    fwt_val10 = FenwickTreeInjectable(10 ** 6 + 1, int, add)
    fwt_cnt10 = FenwickTreeInjectable(10 ** 6 + 1, int, add)
    for c in ddd[0][1]:
        fwt_val01.add(c, c)
        fwt_cnt01.add(c, 1)
    for c in ddd[1][0]:
        fwt_val10.add(c, c)
        fwt_cnt10.add(c, 1)
    cnt01 = len(ddd[0][1])
    cnt10 = len(ddd[1][0])
    acc01 = [0] + list(accumulate(ddd[0][1]))
    acc10 = [0] + list(accumulate(ddd[1][0]))
    acc11 = [0] + list(accumulate(ddd[1][1]))
 
    ans = sum(acc01) + sum(acc10[:-1]) + acc11[-1] * (cnt01 + cnt10)
    tmp = ans
 
    for i in range(len(ddd[1][1]) - 1, -1, -1):
        d = ddd[1][1][i]
        lo_cnt01 = fwt_cnt01.sum(d)
        lo_cnt10 = fwt_cnt10.sum(d)
        lo_val01 = fwt_val01.sum(d)
        lo_val10 = fwt_val10.sum(d)
 
        tmp -= d * (lo_cnt01 + lo_cnt10 - 1)
        tmp += lo_val01 + lo_val10
        tmp += acc11[i] * 2
 
        ans = min(ans, tmp)
 
    return ans
 
 
n = int(input())
aaa = list(map(int, input().split()))
bbb = list(map(int, input().split()))
ccc = list(map(int, input().split()))
ans = solve(n, aaa, bbb, ccc)
print(ans)

            

        
      

D - Reverse Brackets

問題文

長さ $N$ の正しい括弧列 $S$ が与えられます。
あなたは以下の操作を何度でも行うことができます。
- $S$ の連続部分文字列のうち、正しい括弧列であるものを $1$ 個選び、反転させる。
ここで $S$ の $l$ 文字目から $r$ 文字目までからなる連続部分文字列を反転させるとは、以下を行うことを指します。
- $l \le i \le r$ を満たす整数 $i$ に対して同時に $S_i$ を $S_{l+r-i}$ が ( なら ) に、) なら ( に置き換える。(ここでの反転は、通常の反転の定義とは異なる点に注意してください。)

操作終了時にあり得る $S$ の個数を $998244353$ で割ったあまりを求めてください。

制約

$1 \le N \le 5000$
$|S|=N$
$S$ は正しい括弧列

解法

この問題における反転とは、「文字列を画像としてみた場合に鏡映しにする」操作を指す。

()(()()) → (()())()

この操作で、対応する “(” と “)” のペアが変わることはない。

ところで、括弧列は木構造に変換することができる。
1つの頂点は、対応する “(” と “)” のペアを表す。
子は、親の括弧ペアの中に内包される括弧列を表す。子の並び順にも意味があり、括弧列に戻す際には左から順に並べるとする。

()(()()(()))  ↔    ○←ルートとなる仮想頂点
                  ／  ＼
                 ○    ○
                     ／｜＼
                    ○ ○ ○
                          ｜
                          ○

操作とは、この木においては以下のように言い換えられる。

子を持つ任意の頂点 $v$ を選ぶ
$v$ の、1個以上の連続した子の並びを選ぶ
その子達の並びを（孫以降の並びも含め）反転させる

操作を繰り返せば、各頂点において子は好きな順に並べ替えることが可能である。
よって、 $v$ の子の集合を $C_v$ として、 $|C_v|!$ 通りの並べ方がある……？

というのは誤りで、部分木が「同型」であるものは反転させても変わらない。

   ○               ○
 ／  ＼           ／  ＼       同型でない子の順番を入れ替えるのは、
○    ○     →  ○    ○      対応する括弧列も変化する
    ／｜＼           ／｜＼
   ○ ● ●         ○ ● ●
         ｜            ｜
         ○            ○

   ○               ○
 ／  ＼           ／  ＼       同型の子の順番を入れ替えても
○    ○     →  ○    ○      対応する括弧列は変わらない
    ／｜＼           ／｜＼
   ● ● ○         ● ● ○
         ｜               ｜
         ○               ○

木と括弧列の対応関係という意味では子の並び順も意味があると言ったが、今は「子を並べ替えた上で同じにできる2つの部分木」を同一視したいため、子の並び順は無視した同型判定を行う必要がある。

同型のちゃんとした定義は公式Editorial 参照

ある頂点の子の各部分木が、互いに同型であるかを判定したい。
同型のものは同じ値になるような上手いハッシュがあると嬉しい。
部分木のハッシュ化について、以下のような記事がある。

1からの連番に対応する乱数 $R_1,R_2,...$ を決めておく。（木の高さくらいまで）
葉のハッシュ値は $1$ とする。
子を持つ頂点 $v$ のハッシュ値は、
- $v$ の部分木の高さ（最も深い葉からの距離）を $d$ とする。
- 子の各ハッシュ値 $h_1,h_2,...,h_k$ に対し、 $(R_d+h_1)(R_d+h_2)...(R_d+h_k)$ を $v$ のハッシュ値とする。

とすると、衝突確率が $1/mod$ の良いハッシュ値が得られるらしい。

これを元に木DPをおこなうことで答えが求められる。

$\mathrm{DP}[v]:=v$ 以下の部分木から操作により作れる、対応する括弧列の種類数
$\displaystyle \mathrm{DP}[v]=\prod_{u \in C_v}\mathrm{DP}[u] \times (同型を同一視した子の並べ方の個数)$

同型を同一視した子の並べ方の個数は、例えばある頂点の6つの子のうち、3つが同型、2つがまた別の同型だった場合は $\dfrac{6!}{3!2!}$ のように求められる。

同型判定は、今回は制約が小さく $O(N^2)$ が間に合うので、ハッシュ値でなく衝突の危険性のない固有の値で持っても間に合う。例えば部分木を括弧列に戻して状態を表すとして、「子を並べ替えたものの中で辞書順最小のもの」を標準形とし、この標準形が同じかどうかで判定するなど。

Python3

        
          
          
              
              import random
from collections import defaultdict
 
 
def precompute_factorials(n, MOD):
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f = f * m % MOD
        factorials.append(f)
    f = pow(f, MOD - 2, MOD)
    finvs = [1] * (n + 1)
    finvs[n] = f
    for m in range(n, 1, -1):
        f = f * m % MOD
        finvs[m - 1] = f
    return factorials, finvs
 
 
def solve(n, s):
    MOD = 998244353
    children = [[]]
    parent = [-1]
    depth = [0]
    u = 0
    for c in s:
        if c == '(':
            v = len(children)
            children[u].append(v)
            children.append([])
            parent.append(u)
            depth.append(depth[u] + 1)
            u = v
        else:
            u = parent[u]
    m = len(children)
    dp = [-1] * m
    hash = [0] * m
 
    max_depth = max(depth)
    hm = 1000000007
    hb = random.sample(range(5001, hm), k=max_depth + 1)
 
    facts, finvs = precompute_factorials(m, MOD)
    for u in range(m - 1, -1, -1):
        tmp = facts[len(children[u])]
        h = 1
        r = hb[depth[u]]
        variation = defaultdict(int)
        for v in children[u]:
            tmp *= dp[v]
            tmp %= MOD
            h *= r + hash[v]
            h %= hm
            variation[hash[v]] += 1
        for c in variation.values():
            tmp *= finvs[c]
            tmp %= MOD
        dp[u] = tmp
        hash[u] = h
 
    return dp[0]
 
 
n = int(input())
s = input()
ans = solve(n, s)
print(ans)

            

        
      

E - Swap 0^X and 1^Y

問題文

0 と 1 のみからなる長さ $N$ の文字列 $S, T$ と、正整数 $X, Y$ が与えられます。
$i = 1, 2, \ldots, N$ について、 $S$ の $i$ 文字目を $S_i$ で表します。
「下記の操作 A と操作 B のどちらかを行う」ことを好きな回数（ $0$ 回でも良い）だけ繰り返すことで、 $S$ を $T$ に一致させることができるかどうかを判定してください。
- （操作 A） $1 \leq i \leq N-(X+Y)+1, S_{i} = S_{i+1} = \cdots = S_{i+X-1} =$ 0, $S_{i+X} = S_{i+X+1} = \cdots = S_{i+X+Y-1} =$ 1 を満たす整数 $i$ を選び、 $S_{i}, S_{i+1}, \ldots, S_{i+Y-1}$ をそれぞれ 1 に、 $S_{i+Y}, S_{i+Y+1}, \ldots, S_{i+Y+X-1}$ をそれぞれ 0 に変更する。
- （操作 B） $1 \leq i \leq N-(X+Y)+1, S_{i} = S_{i+1} = \cdots = S_{i+Y-1} =$ 1, $S_{i+Y} = S_{i+Y+1} = \cdots = S_{i+Y+X-1} =$ 0 を満たす整数 $i$ を選び、 $S_{i}, S_{i+1}, \ldots, S_{i+X-1}$ をそれぞれ 0 に、 $S_{i+X}, S_{i+X+1}, \ldots, S_{i+X+Y-1}$ をそれぞれ 1 に変更する。
- ※要は、 $X$ 個の 0 のカタマリと $Y$ 個の 1 のカタマリをスワップする。

制約

$1 \leq N \leq 5 \times 10^5$
$1 \leq X, Y \leq N$
$S, T$ はそれぞれ 0 と 1 のみからなる長さ $N$ の文字列
入力はすべて整数

解法

D問題の木の同型判定の発想と似ているが、何らかの標準形を決めてやると、 $S,T$ の標準形が同じかどうかで判定できる。

標準形とは、「一定のルールで操作を繰り返したら、互いに変換可能な列は全部、同じ形に行き着くよ！」というようなルールを定めたときの、最終的に行き着く同じ形のこと。
本問題の場合、おこなった操作は逆順にたどることで元に戻せるので、もし標準形が同じなら $S→標準形→T$ という経緯で変換できることがわかる。

まず、 $S$ と $T$ に含まれる“0”と“1”の個数が違えば絶対無理なのでNo。以下、同じとする。

連続している個数が重要なので、ランレングス圧縮する。
その上で、各連続成分の長さを $X,Y$ で割った商と余りを $d,m$ として、 $[(0,d_1,m_1),(1,d_2,m_2),(0,d_3,m_3),...]$ のような形で持つようにしておく。
この列を、とりあえず「商余ランレングス圧縮列」とでもしておく。

01列に問題の操作をおこなったとき、商余ランレングス圧縮列に対してはどのような操作に言い換えられるか考える。

$m_i=0$ である $i$ は、自身を飛び越えさせることで、 $d_{i-1}$ と $d_{i+1}$ 間で値を移すことができる。

X=3 Y=2
  0000    1111  00000000  ⇔   0      1111  00000000000
(0,1,1) (1,2,0) (0,2,2)     (0,0,1) (1,2,0) (0,3,2)
   ~               ~           ~               ~
                          ⇔ 0000000  1111  00000
                            (0,2,1) (1,2,0) (0,1,2)
                               ~               ~

その際、さらに $m_{i+1}=0$ だと、統合してランレングス圧縮列の項数を減らせる。

  0000    1111  000000    111    →  0000000000   1111111
(0,1,1) (1,2,0) (0,2,0) (1,1,1)       (0,3,1)     (1,3,1)
   a       b       c       d            a+c         b+d

逆に、 $m_i \neq 0,m_{i+1} \neq 0$ の箇所で移動させても、間に $m=0$ である2つの項が間に新たにできるだけである。
特に、この操作により、外側の「…」の部分で操作できないものが操作できるようにはならない。

... 00000   11111 ...   ⇔  ... 00      11     000     111 ...
   (0,1,2) (1,2,1)           (0,0,2) (1,1,0) (0,1,0) (1,1,1)

おこなえる操作はこれで全てである。
なんとなく、標準形を作る際は統合できるものはしておいた方が良さそうなことを考えると、3番目の操作は意味が無く、実質2つである。

以上を踏まえて、次のような標準形が考えられる。

項数を最小化する（ $m=0$ が2つ以上続く箇所を統合する）
その上で、 $d_i$ だけを取り出した列を、辞書順最小化する（寄せられる0,1は右に寄せる）

全て $m_i=0$ である場合が若干例外的で、“0000…001111..11” と “1111…110000..00” とどちらを標準形とするかが定義されないが、この場合は “0000…001111..11” で統一する。

それ以外の場合、項数最小化によって、 $m=0$ が2つ続く箇所はなくなる。あとは

  0000    1111   00000   111111 0000000  →   0      1111     00    111111 0000000000000
(0,1,1) (1,2,0) (0,1,2) (1,3,0) (0,2,1)    (0,0,1) (1,2,0) (0,0,2) (1,3,0) (0,4,1)

のように、 $m_{i-1} \neq 0, m_i=0, m_{i+1} \neq 0$ という箇所が残るので、このような箇所の $d$ をできるだけ右に寄せると形が一意に定まり、標準形として利用できる。

Python3

        
          
          
              
              from itertools import groupby
 
 
def run_length(s, x, y):
    rl = []
    for c, itr in groupby(s):
        c = int(c)
        l = len(list(itr))
        if c == 0:
            d, m = divmod(l, x)
        else:
            d, m = divmod(l, y)
        rl.append((c, d, m))
    return rl
 
 
def normalize(rl):
    """
    ランレングスの項数を最小にする。（m=0 が2つ連続していれば減らせる）
    その中で、d を取り出した配列を辞書順最小にする（なるべく、移動できるX,Y単位のカタマリは右に寄せる）
    """
    # 最初に出てくる m!=0 を探す
    first_nonzero = -1
    sum_d = [0, 0]
    for i in range(len(rl)):
        sum_d[rl[i][0]] += rl[i][1]
        if rl[i][2] != 0:
            first_nonzero = i
            break
    else:
        return [[0, sum_d[0], 0], [1, sum_d[1], 0]]
 
    c = rl[first_nonzero][0]
    if sum_d[c ^ 1] > 0:
        stack = [[c ^ 1, sum_d[c ^ 1], 0], [c, sum_d[c], rl[first_nonzero][2]]]
    else:
        stack = [[c, sum_d[c], rl[first_nonzero][2]]]
 
    for i in range(first_nonzero + 1, len(rl)):
        c, d, m = rl[i]
        if stack[-1][0] == c:
            assert stack[-1][2] == 0
            stack[-1][1] += d
            stack[-1][2] = m
            continue
        if stack[-1][2] == 0:
            if m == 0:
                stack[-2][1] += d
            else:
                d += stack[-2][1]
                stack[-2][1] = 0
                stack.append([c, d, m])
            continue
        stack.append([c, d, m])
 
    return stack
 
 
def solve(n, x, y, s, t):
    if s.count('0') != t.count('0'):
        return False
    if s == t:
        return True
    rls = run_length(s, x, y)
    rlt = run_length(t, x, y)
    return normalize(rls) == normalize(rlt)
 
 
n, x, y = map(int, input().split())
s = input()
t = input()
if solve(n, x, y, s, t):
    print('Yes')
else:
    print('No')

            

        
      

−目次

AtCoder Regular Contest 194 (Div. 2) A,B,C,D,E問題メモ

A - Operations on a Stack

問題文

制約

解法

B - Minimum Cost Sort

問題文

制約

解法

C - Cost to Flip

問題文

制約

解法

D - Reverse Brackets

問題文

制約

解法

E - Swap 0^X and 1^Y

問題文

制約

解法