NECプログラミングコンテスト2021(AtCoder Beginner Contest 229) F,G問題メモ

NECプログラミングコンテスト2021(AtCoder Beginner Contest 229)

なぜかめっちゃ眠かった。

F - Make Bipartite

• $N+1$ 頂点の無向グラフ
• 辺は、以下の $2N$ 本
  • $i=1,2,...,N$ について、頂点 $0$ と $i$ を結ぶ重み $A_i$ の辺
  • $i=1,2,...,N$ について、頂点 $i$ と $i+1$ を結ぶ重み $B_i$ の辺
    • ただし頂点 $N+1$ は $1$ を表すとする
• 辺を削除して全体を二部グラフにしたい
• 削除する必要のある最小の辺の重みの総和を求めよ
• $3 \le N \le 2 \times 10^5$

グラフに見せかけたDP。

グラフは車輪のような形になる。

  ①--②
 / \  / \
⑥--⓪--③
 \ /  \ /
  ⑤--④

二部グラフは、頂点を2グループに分け「同じグループの間には辺が張られていない」状態ならよい。

グループAとBに分け、頂点0の入る方をグループAと決めてしまうとして、 頂点 $0～i-1$ で成立している状態に $i$ を加えることを考える。

• $i$ をAに入れるなら、$A_i$ は削除しないといけない
• $i$ を $i-1$ と同じグループに入れるなら、$B_{i-1}$ は削除しないといけない
• その他の辺は削除しなくてよい

ただし、$i=1$ のとき、2番目の条件は「$1$ と $N$ が同じグループなら $B_N$ は削除」となる。
このループ部分（$B_N$ の辺）がややこしいので、頂点1に関しては2番目の条件は一端無視する。

頂点 $i$ を加えるときの条件から、$i-1$ の入ったグループがどっちだったかさえわかれば、削除しなければならない辺が決まる。

• （仮）$DP[i][g]=$ 頂点 $1～i$ を考え、$i$ の入ったグループが $g=A/B$ の時の、削除すべき辺のコストの最小値

また無視していた $B_N$ については、$DP[N]$ まで計算した後で 「頂点 $1$ と $N$ をそれぞれどちらに入れたか」がわかれば、削除しなければならないかが決まる。

従って、そこでも場合分けしてやればよい。

• $DP[i][f][g]=$ 頂点 $1～i$ を考え、頂点 $1$ は $f=A/B$ に入れ、$i$ の入ったグループが $g=A/B$ の時の、削除すべき辺のコストの最小値

最後に、$DP[N][A][A]$ および $DP[N][B][B]$ には $B_N$ を加算してやれば、全ての辺を考慮できたことになる。

$DP[N]$ の中の4つの値の最小値が答え。

Python3

n = int(input())
aaa = list(map(int, input().split()))
bbb = list(map(int, input().split()))

dp00 = aaa[0]
dp01 = 1 << 60
dp10 = 1 << 60
dp11 = 0
for a, b in zip(aaa[1:], bbb):
    ndp00 = min(dp00 + a + b, dp01 + a)
    ndp01 = min(dp00, dp01 + b)
    ndp10 = min(dp10 + a + b, dp11 + a)
    ndp11 = min(dp10, dp11 + b)
    dp00 = ndp00
    dp01 = ndp01
    dp10 = ndp10
    dp11 = ndp11

dp00 += bbb[-1]
dp11 += bbb[-1]

ans = min(dp00, dp01, dp10, dp11)

print(ans)

G - Longest Y

• '.' と 'Y' からなる文字列 $S$ が与えられる
• $K$ 回まで、隣接する文字をswapできる
• 'Y' をなるべく長く連続させたいとき、可能な最大長を求めよ
• $2 \le |S| \le 2 \times 10^5$

いくつかの気付きと前準備と、添字をバグらせない丁寧さが必要。

答えを二分探索できないか考える。
Yを $x$ 個連続させられるかどうかを $O(|S|)$ くらいで判定できれば可能そう。

$x$ を固定して考える。

Y同士を入れ替える操作は無駄なので、$S$ の中のYの並び順は最初から最後まで変わらないとしてよい。
$S$ の中で $i$ 番目に出現するYのことを $Y_i$ と表すとする。

連続させる一番左のYを $Y_i$ としたら、一番右は $Y_{i+x-1}$ に決まる。

この区間のYを連続させるためのswap回数を求めたい。

基準となるYを1個決める。 基準のYは動かさず、周囲のYを持ってくることを考える
Y..Y.YY....[Y].YY

基準Yから左右それぞれのYとの間にある'.'の個数を数えたら、その和がswap回数
Y..Y.YY....[Y].YY
7  5 44        11  →  7+5+4+4+1+1 = 22

ここで、たとえば基準を1個左にずらした時の変化量は、その間に'.'が $k$ 個あったとして

• 左にあるYの個数 $\times k$ だけ減る
• 右にあるYの個数 $\times k$ だけ増える

なので、最適な基準位置は、区間中央のYであることがわかる。偶数の場合はどちらでもよい。

Y..Y.Y[Y]....Y.YY
3  1 0       4 55  →  3+1+0+4+5+5 = 18

従って、以下が前計算によりパッと求められると嬉しい。

• $R(i,j)=Y_i$ を基準として右側 $Y_{i+1}～Y_j$ のYを $Y_i$ に持ってくる回数
• $L(i,j)=Y_i$ を基準として左側 $Y_j～Y_{i-1}$ のYを $Y_i$ に持ってくる回数

愚直には各 $Y_i$ から各 $Y_j$ の間にある'.'の個数を数えた上で累積和を取っておけばよいのだが、 しかし2次元でテーブルを作ってしまうと $O(|S|^2)$ のためTLE or MLE。

そこで、基準を1個ずらしたときに法則性が無いかを確かめると、

      Y..Y.YY....Y.YY
基準     / | \   | | \
Y0   0  2  5  8 15 23 31
    (  -2 -4 -6 -8-10-12)
Y1      0  1  2  7 13 19
    (     -1 -2 -3 -4 -5)
Y2         0  0  4  9 14

Y3            0  4  9 14
    (           -4 -8-12)
Y4               0  1  2
...

ずらすごとに等差数列を引いた形になっている。
まぁ、ずらしたところから右にある各Yまでにある'.'の個数が一定数ずつ減るので、累積和を取ったら等差で減るのは当然っちゃ当然。

基準を $Y_i$ にする時に追加される等差数列の公差は、直前の $Y_{i-1}$ との間にある'.'の数であり、$R(i,i)$ が0になるように位置を揃える。

• $R(0,:)$
• 基準を $i$ にするときの、$R(0,:)$ からの累積公差
• 基準を $i$ にするときの、$R(0,:)$ からの累積初項
  • 初項＝このまま等差数列を左端まで延長した場合の $Y_0$ の箇所の値

以上の長さ $O(|S|)$ の3つの配列を前計算しておけば、差分計算で $R(i,j)$ を $O(1)$ で求められる。

$L(i,j)$ も同様にすればよい。

すると区間 $[l,l+x)$ のYを連続させるswap回数は、$m$ を区間中点、$r=l+x-1$ として、 $L(m,l)+R(m,r)$ で求められ、これが $K$ 以下なら可能となる。

$x$ ごとに $l$ を全通り試しても $O(|S|)$ で判定でき、全体で $O(|S|\log{|S|})$ となる。

Python3

from itertools import groupby, accumulate

s = input()
k = int(input())
s = s.strip('.')

if s == '':
    print(0)
    exit()

between = [0]

for c, itr in groupby(s):
    if c == 'Y':
        between.extend([0] * (len(list(itr)) - 1))
    else:
        between.append(len(list(itr)))

n = len(between)
dist_fwd = list(accumulate(between))
acc_fwd = list(accumulate(dist_fwd))

between_bwd = between.copy()
between_bwd.append(0)
between_bwd.reverse()
between_bwd.pop()
dist_bwd = list(accumulate(between_bwd))
acc_bwd = list(accumulate(dist_bwd))

# acc_fwd[i] = 左端を基準として、基準～i番目のYまでを基準に集める操作回数
#   基準を1つ右にずらす毎に、等差数列が減算される感じになる。
#   基準を j ずらしたときに減算される等差数列の初項と等差を管理したい。
#   ただし等差は dist_fwd[j] と一致するため、初項の方を求めておく。
#   これにより、j 番目のYを基準とし、j～i のYをjに集める操作回数が O(1) で得られる
first_fwd = [0]
for i in range(1, n):
    first_fwd.append(first_fwd[-1] - between[i] * (i - 1))
first_bwd = [0]
for i in range(1, n):
    first_bwd.append(first_bwd[-1] + between_bwd[i] * (n - i))

dist_bwd.reverse()
acc_bwd.reverse()
first_bwd.reverse()


def check(width):
    l = width // 2
    r = width - l - 1

    for i in range(l, n - r):
        swap = acc_fwd[i + r] - (first_fwd[i] + dist_fwd[i] * (i + r))
        swap += acc_bwd[i - l] - (first_bwd[i] - dist_bwd[i] * (i - l))

        if swap <= k:
            return True

    return False


lo = 1
hi = n + 1
while lo + 1 < hi:
    m = (lo + hi) // 2

    if check(m):
        lo = m
    else:
        hi = m

print(lo)

上記のような七面倒くさいことしなくても、ちょっと発想を変えればもっと楽に計算できる。

公式Editorialの解法。二分探索は一緒。

$S$ からYの箇所のindexを抜き出した配列を $A$ とすると、1回のswapは、どれか1個を±1する操作に対応する。
（Y同士のswapは行わない前提として、異なる $A_i$ が同じ値になる瞬間があってはいけない）

Y..Y.YY....Y.YY    A = (0  3  5  6 11 13 14)
      ×                        ↓+1
Y..Y.Y.Y...Y.YY    A = (0  3  5  7 11 13 14)

Yを連続させるというのは、$A$ に連番をなるべく長く発生させるという問題に言い換えられる。

さらにこれは、あらかじめ $A_i$ から $i$ を引いて $B_i$ とおくことで、「同じ値を」なるべく多く作る問題にできる。

Y....YYYY....YY    A = (0  5  6  7  8 13 14)
                   B = (0  4  4  4  4  8  8)

すると、$[l,r)$ の区間のYを揃えるには、中央 $m$ に揃えるのが最適となるので、

              ■■                 ↓↓      
Bm        ■■■■   →  ↑↑↑■■■■
        ■■■■■       ↑↑■■■■■
    ■■■■■■■       ■■■■■■■
    l     m       r      l     m       r

• $B_m (m-l) - (B_l～B_{m-1}の和) + (B_m～B_{r-1}の和) - B_m (r-m)$

累積和を前計算しておけば操作回数を $O(1)$ で計算できる。