AtCoder Regular Contest 227 A,B 問題メモ

AtCoder Regular Contest 227

CDEが700点3連続構成。時間があればどれかは解けると思ったんだけどなぁ。

A - Fermat Point of Binary Strings

• 長さ $2N$ で、0 と 1 をそれぞれ $N$ 個含む文字列をよい文字列と呼びます。
• よい文字列 $S, T$ に対して、$S$ の隣り合う $2$ 文字を入れ替える操作を $0$ 回以上行って$T$ に一致させるために必要な操作回数の最小値を $\operatorname{dist}(S, T)$ とします。
• よい文字列 $A, B, C$ が与えられます。すべてのよい文字列 $X$ のうち、
• \[\operatorname{dist}(A, X)+\operatorname{dist}(B, X)+\operatorname{dist}(C, X)\]
• の値を最小にするものを $1$ つ求め、その最小値とともに出力してください。

• $1 \le N \le 2 \times 10^5$
• $A, B, C$ はそれぞれ長さ $2N$ のよい文字列
• $N$ は整数

$dist(S,T)$ を求めるのにやることは明らかで、$i=1,2,...,N$ 個目の 1 の出現位置の差を取り、合計すればいい。

S  0 1 0 0 1 1 1 0
   ,-' ,---' | `-,
T  1 0 1 0 0 1 0 1

$S$ 側が $A,B,C$ の3通りになった時も、$i$ 毎に独立に考えていい。

$A,B,C$ における $i$ 個目の 1 の出現位置をそれぞれ $p_a,p_b,p_c$ とする。 $f(x)=|p_a-x|+|p_b-x|+|p_c-x|$ を最小化するには、3つの中で2番目に大きい値を $x$ とするとよい。

∵それより増やすと、1増やすごとに1個以下との距離が1近づき、2個以上との距離が1離れるので、必ず $f(x)$ は大きくなる。 減らす場合も同様。

各 $i$ について $x$ を求め、それを $D$ における $i$ 個目の 1 の位置とすればよい。

Python3

def solve(n, a, b, c):
    pos = [[] for _ in range(n)]
    cnt = [0, 0, 0]
    for i in range(n * 2):
        if a[i] == '1':
            pos[cnt[0]].append(i)
            cnt[0] += 1
        if b[i] == '1':
            pos[cnt[1]].append(i)
            cnt[1] += 1
        if c[i] == '1':
            pos[cnt[2]].append(i)
            cnt[2] += 1
    ans = ['0'] * (n * 2)
    dist = 0
    for i in range(n):
        pos[i].sort()
        x = pos[i][1]
        ans[x] = '1'
        dist += sum(abs(x - pos[i][j]) for j in range(3))
    ans = ''.join(ans)
    return dist, ans


n = int(input())
a = input()
b = input()
c = input()
dist, ans = solve(n, a, b, c)
print(dist)
print(ans)

B - Know Your Place

• 長さ $N$ の非負整数列 $A=(A_1,A_2,\ldots,A_N)$ が与えられます。
• $A$ の要素を並べ替えて得られる数列 $B=(B_1,B_2,\ldots,B_N)$ であって、すべての$i=1,2,\ldots,N$ について次の条件を満たすものが存在するか判定し、存在する場合はそのような数列を $1$ つ構成してください。
  • $B_i$ は、$1\le j\lt i$ かつ $B_j\lt B_i$ を満たす整数 $j$ の個数に等しい。

• $1\le N\le 5\times 10^5$
• $0\le A_i\lt N$
• 入力される数値はすべて整数

$A$ は一旦無視して（あらゆる値があることにして）、$B$ で各 index に置くことができる値で樹形図を書いてみる。

i 0   1   2   3
  0---0---0---0 ...
  |   |   `---3
  |   `---2---0
  |       |---2
  |       `---3 
  `---1---0---0
      |   `---3
      |---1---0
      |   |---1
      |   `---3
      `---2---0
          |---1
          |---2
          `---3

これを元に観察と考察をすると、index $i$ には

• $i$ より大きい値は置けない。（左にある数の個数がそもそも足りないので当然）
• $i$ はいつでも置ける。（左には $i$ 個の数があり、1つ上の条件より、それらは全て $i$ 未満の数なので）
• $i$ 未満の数 $a$ は、「index $[a, i)$ の範囲には、$a$ 未満の数を置いていない」ときに置ける。
  • （index $a$ より左にあるのは必ず $a$ 未満の数で、それだけで $a$ 個あるので、そこから増えてはいけない）

よって、「置ける中で最も大きい数から置いていく」以下の解法が成り立つ。

• 大きい方から取り出すヒープキュー $Q$ を用意する。
• $i=0,1,...,N-1$ の順に、以下を行う
  • $Q$ に $i$ を、$A$ に出現する個数だけ追加する
  • $B_i=Q.pop()$ とする。$Q$ がこの時点で空なら不可能

Python3

from collections import Counter
from heapq import heappush, heappop


def solve(n, aaa):
    cnt = Counter(aaa)
    ans = []
    hq = []
    for i in range(n):
        for k in range(cnt[i]):
            heappush(hq, -i)
        if len(hq) == 0:
            return None
        ans.append(-heappop(hq))
    return ans


n = int(input())
aaa = list(map(int, input().split()))
ans = solve(n, aaa)
if ans is None:
    print('No')
else:
    print('Yes')
    print(*ans)