目次
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つの値の最小値が答え。
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|})$ となる。
解法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)$ で計算できる。