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

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

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

解法2

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

公式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)$ で計算できる。

programming_algorithm/contest_history/atcoder/2021/1127_abc229.txt · 最終更新: 2021/12/03 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0