AtCoder Grand Contest 059 A,B問題メモ

AtCoder Grand Contest 059

むずかった。。。

A - My Last ABC Problem

• A,B,Cの3種類の文字からなる、長さ $N$ の文字列 $S$ が与えられる
• $S$ の部分文字列 $T$ に対して、以下の操作を行うことを考える
• 操作
  • 好きな区間 $[l,r]$ と、好きな置き換え $(X,Y,Z)$ を指定する
    • $(X,Y,Z)$ は、('A','B','C') の並べ替え
  • 文字列 $T_l ... T_r$ 中の 'A','B','C' を、それぞれ $X,Y,Z$ で置き換える
• この操作を繰り返して、$T$ を全て同一の文字にするのに必要な最小操作回数を考える
• 以下の $Q$ 個のクエリに答えよ
  • $L_i,R_i$ が与えられる
  • $S$ の $L_i～R_i$ 文字目を切り出した文字列を $T$ として、上記の最小操作回数を求めよ

T:  A B B C B C A
     |-----|        (A,B,C)→(C,A,B)
    A A A B B C A
         |-----|    (A,B,C)→(C,B,A)
    A A A B B A A
         |---|      (A,B,C)→(B,A,C)
    A A A A A A A

3回で全てを同じ文字にできた

まず、異なる文字が隣接している箇所と個数に着目する。

ある区間を指定して適切に置き換えると、 「区間両端の境目の異なる文字が隣接している箇所を同じにすることができる」が、 「それ以外の異なる文字が隣接している箇所は絶対にそのまま残る」ことがわかる。
（異なる文字同士は置き換えても異なる文字同士なので）

よって、1回の操作で2個の「異なる文字が隣接している箇所」しか潰せないので、 全て同じにするには、$T$ 内のそのような箇所数を $X$ として、$ceil(\frac{X}{2})$ は必ずかかる。

ややこしいことに、かならず2個ずつ潰せるかというとそうでもない。

例えば'AB'と'BC'は同時に潰せない。
'B'を、左端では'A'に、右端では'C'に置き換えたいが、同じ文字を異なる文字に置き換えることはできない。

また、'BC'と'AB'も同時に潰せない。
左端では'C'を'B'に、右端では'A'を'B'に置き換えたいが、異なる文字を同じ文字に置き換えることはできない。

まとめると、以下のようになる。
A→B→C→A を“昇順”としたときに「+(昇順)になる関係性同士」「-(逆順)になる関係性同士」で上手くいっていない。
ただし「AB同士」など文字列が全く同じ同士では可能である。

  右端 AB BC CA BA CB AC
左端 +------------------
  AB | ○ × × ○ ○ ○  ┐
  BC | × ○ × ○ ○ ○  │+になる関係性
  CA | × × ○ ○ ○ ○  ┘
  BA | ○ ○ ○ ○ × ×  ┐
  CB | ○ ○ ○ × ○ ×  │-になる関係性
  AC | ○ ○ ○ × × ○  ┘

+と-の関係性のわかりやすさのため、A,B,C を 0,1,2で置き換える。

「同じ文字列同士のペア」と「+と-の関係性のペア」で、操作による変化は異なってくる。

これは、操作区間内の（境界を除く）+と-で累積和を取ったときに、以下の場合のみ操作できる。

• “+“に属する隣接ペアは、$\mod{3}$ が $2$ になる場合
• ”-“に属する隣接ペアは、$\mod{3}$ が $1$ になる場合

0 1 2 0 2 1 0 1
 |-----------|    (0,1,2)→(1,0,2)  
0 0 2 1 2 0 1 1   置き換え方は、必ずその2つを入れ替えることとなる

このとき、+/-の関係性で見ると、全て逆転する

0 1 2 0 2 1 0 1
 + + + - - - +
 |-----------|
 0 - - + + + 0
0 0 2 1 2 0 1 1

こちらでは、基本的に+/-の関係性は全て保存される。
ただし、区間内の累積和が $\mod{3}$ で $0$ になる場合（01と10みたいなペア）は、 「全て保存」「全て逆転」の好きな方を選択できる。

0  1  2  0  2  1
 +1 +1 +1 -1 -1
 ↓          ↓          (0,1,2)→(2,0,1)
  0 +1 +1 -1  0
0  0  1  2  1  1

以下の操作が思いつく。

• なるべく+と-を（他の+/-の関係性を保ったまま）打ち消し合う
• 最終的に +の連続、または -の連続が残る
• 残った中で左から最初に異なる位置を $l$、真ん中くらいのそれと同じ文字列になる箇所を $r$ として1回操作する
• 区間に挟まれた部分のみがひっくり返り、同数くらいの+と-になるので、それらを再び打ち消し合う
• 残った少数のものは、長さ1の区間で個別に処理する

最後の残った少数の処理の仕方は、3番目の処理で適切な位置を指定することで + or - の連続 3つまでを考えればよくて、以下のようになる。

連続    例  操作回数
   0     A    0
   1    AB    1
   2   ABC    2
   3  ABCA    2

これで、ほとんどの操作で同時に2つの「異なった文字が隣接する箇所」を潰せる。

唯一、「最後の処理で残った連続数が2の場合、個別にしか潰せない」ことで、 $ceil(\frac{X}{2})$ より操作回数がかさんでいる。

これを、その前の過程で、たとえば「+と-のペアなどにして上手く1回で処理」できないことを示せば、 上記の操作方針が最適と言える。

+と-の個数を調整できるのは、以下の場合のみ、区間内の+と-を逆転させることが可能である。

• ”+“の関係性同士で、区間両端を除く+/-の累積和 $\mod{3}$ が2のとき（ABとABのような隣接）
• ”-“の関係性同士で、区間両端を除く+/-の累積和 $\mod{3}$ が1のとき（BAとBAのような隣接）
• 区間両端を除く+/-の累積和 $\mod{3}$ が0のとき（ABとBAのような隣接）

1つめと2つめは対称なので、1,3つめのみを考える。

操作可能な場合とその変化を考えると、操作によって、$T$ 全体の+と-の総和 $\mod{6}$ は変化しないことが分かる。

... + (+ * 2 mod 6) + ...   → この部分の総和 mod 6 = 4
↓
... 0 (- * 2 mod 6) 0 ...   → この部分の総和 mod 6 = -2 = 4

... + (+ * 5 mod 6) + ...   → この部分の総和 mod 6 = 1
↓
... 0 (- * 5 mod 6) 0 ...   → この部分の総和 mod 6 = -5 = 1

... + (+ * 0 mod 6) - ...   → この部分の総和 mod 6 = 0
↓
... 0 (+ * 0 mod 6) 0 ...   → この部分の総和 mod 6 = 0

... + (+ * 3 mod 6) - ...   → この部分の総和 mod 6 = 3
↓
... 0 (- * 3 mod 6) 0 ...   → この部分の総和 mod 6 = -3 = 3

つまり $T$ 全体の+/-の総和が $2 \mod{6}$ の場合、最終的に残るのは、+の連続でもこれ以下にはできないし、 -の連続に置き換えたとしても4にしかならない。

よって、この操作が最適と言える。

+の関係性、-の関係性の位置をそれぞれ記録し、累積和を取って、 クエリ毎に $L_i～R_i$ の中に含まれる各個数を取得できるようにしておく。

それぞれの個数を $p,q$ とすると、$P=\min(p,q)$ だけ打ち消しあい、$D=|p-q|$ だけ連続が残る。

$Q=\frac{D}{6}$、$R=D \mod{6}$ とすると、適切な位置で反転させることで、$Q*3$ 個の+/-ペアを作れ、$R$ 個のこる。

$R=0～5$ については、事前に手元で計算すると $E=(0,1,2,2,3,3)$ であることがわかる。

答えは、$P+3Q+E[R]$ となる。

Python3

from itertools import accumulate

n, q = map(int, input().split())
s = ['ABC'.index(c) for c in input()]

inc = [0] * n
dec = [0] * n

for i in range(n - 1):
    c1 = s[i]
    c2 = s[i + 1]
    if c1 == c2:
        continue
    d = (c2 - c1) % 3
    if d == 1:
        inc[i + 1] = 1
    else:
        dec[i + 1] = 1

inc_acc = list(accumulate(inc))
dec_acc = list(accumulate(dec))

buf = []
pre = [0, 1, 2, 2, 3, 3]
for _ in range(q):
    l, r = map(int, input().split())
    ans = 0
    inc_cnt = inc_acc[r - 1] - inc_acc[l - 1]
    dec_cnt = dec_acc[r - 1] - dec_acc[l - 1]

    pair = min(inc_cnt, dec_cnt)
    diff = max(inc_cnt, dec_cnt) - pair

    d, m = divmod(diff, 6)
    buf.append(pair + (d * 3) + pre[m])

print('\n'.join(map(str, buf)))

B - Arrange Your Balls

• 色 $C_1,C_2,...,C_N$ の $N$ 個のボールを好きな順で円周上に並べることを考える
• 並べた後、異なる色が隣接している箇所の、色のペア $(X,Y)$ を数える（順序は問わない）
• 色のペアの種類数を最小化するような並べ方の例を1つ求めよ
• $T$ 個のテストケースが与えられるので、全てについて求めよ
• $1 \le T \le 5 \times 10^4$
• $3 \le N \le 2 \times 10^5$
• 1つの入力ファイルの $N$ の総和 $\le 2 \times 10^5$

C = (1 1 2 3)

1 1 2 3 と並べると、(1,2),(2,3),(3,1) という3つのペア
1 2 1 3 と並べると、(1,2),(1,3) という2つのペア

1つ以下にはできないので、後者の並べ方が答え

ソートして並べることで、色の種類数を $k$ として、$k$ は達成できる。

また、色が2色以上ある場合、各色は必ず異なる1つ以上の色と接しなければならないので、 色を頂点、隣接ペアを辺としたグラフで全体が連結じゃないといけないことを考えると、$k-1$ 以下にはできない。

要は、$k-1$ にできますか、という問題である。

基本方針として、個数の少ない色を多い色で包み込むのがよい。

ソートして並べると（3色以上の場合）両端が必ず異なる2色となるのに対し、 包み込むと、包み込まれた色は1色としか接しないで済む。

同じ色はいくら隣り合っていてもペアにカウントされないので、包み込まれる色は連続させてよい。

とりあえず、最も多い1色で、少ない方から包み込んで損しなさそう。
最も多い色を $M$、個数を $m$ とすると、$m-1$ 種類の数を包める。

M C1 ... C1 M C2 ... C2 M C3 ... C3 M

同様に多い色で少ない色から包み込んだパーツを用意して

N C4 ... C4 N C5 ... C5 N C6 ... C6 N
O C7 ... C7 N C8 ... C8 N C9 ... C9 O O
                                      ~(余り)

それを並べてみたが、WA。この場合、ペア数は $k-1$ でなく $k$ となっている。

M ... M N ... N O ... O O

包み込んだ色の種類数 + (M,N),(N,O),(O,M) = k

仮にパーツが2つ（以下）なら、$k-1$ を達成できる。

M ... M N ... N

包み込んだ色の種類数 + (M,N) = k-1

3つ以上の場合も、例えば上記の例では O が余っているので、 そこに M…M を埋め込んでしまえば、(M,N)のペアを減らせ、$k-1$ を達成できる。

O ... O M ... M O N ... N

包み込んだ色の種類数 + (O,M),(N,O) = k-1

よって、「最大まで包み込んだパーツ」自身も、包まれる候補の1つとして再帰的に包み込めばよい。

操作としては、例えば以下のようにすればよい。

• 色ごとに個数を数え、(個数, 色) で昇順ソートし、両端キューに入れる
• 末尾（個数最大）から1つ取り出す（色 $M$、個数 $m$ とする）
• 先頭（個数の小さい方）から最大 $m-1$ 個取り出す
• (M, C1+, M, C2+, … , M) というパーツにする
  • C1+は、色C1をその個数分だけ並べた物を表す
• パーツを両端キューに先頭から入れる
  • パーツであることがわかるようにしておく
  • 次に包み込まれる対象として取り出された場合は、パーツのまま包み込む

上記の過程を、「キューの個数が2個以下」になるか、「最大の色の個数が1」になるまで繰り返す。

前者なら $k-1$ を達成可能、後者なら達成不可能であり、いずれも残りを繋げて終了。

（最初の例では、M,N,Oで包み込んだパーツが複数同時に生成されたが、 上記の方法をとると、同時に生成されるパーツは最大1つとなる）

ただし、パーツを再帰的に包み込む際、 「新たな配列を用意し、そこにパーツの中身を全て移す」ことを繰り返しているとTLEとなるので、少し工夫が必要。

Pythonのように型が自由な言語であれば、[O, [N, [M, …, M], N, …, N], O] のように入れ子リストのまま作成し、 最後に1次元になおすのが楽かな。

Python3

import sys

from collections import Counter, deque

sys.setrecursionlimit(100005)


def flatten(l, buf):
    for el in l:
        if isinstance(el, str):
            buf.append(el)
        else:
            flatten(el, buf)


t = int(input())

for _ in range(t):
    n = int(input())
    ccc = Counter(input().split())
    cnt_list = []
    for c, cnt in ccc.items():
        cnt_list.append([cnt, c])

    cnt_list.sort()
    q = deque(cnt_list)

    while len(q) > 2 and q[-1][0] >= 2:
        cnt, c = q.pop()

        loop = min(cnt - 1, len(q))
        new_part = []
        for _ in range(loop):
            cnt2, c2 = q.popleft()
            new_part.append(c)
            if cnt2 == -1:
                new_part.append(c2)
            else:
                new_part.extend([c2] * cnt2)
        new_part.extend([c] * (cnt - loop))

        q.appendleft([-1, new_part])

    ans = []
    for cnt, c in q:
        if cnt == -1:
            flatten(c, ans)
        else:
            ans.extend([c] * cnt)

    print(*ans)