[ABC229] G - Longest Y

[Q] https://atcoder.jp/contests/abc229/tasks/abc229_g

にぶたん + 累積和で15msくらい。O(NlogN)。
1. それぞれの 'Y' について、0indexからのドット数 A[] をとる
2.  A[] の累積和 acc[] をとる
3. 要素数で二分探索。要素は連続して取る。つど、開始indexを全探索する。
swap回数は、選んだ要素の中央値との差分。

Q 入力例1
YY...Y.Y.Y.
2

1. 'Y' について、0index からのドット数におきかえる。
YY...Y.Y.Y.
00123344556
A[] = {0,0,3,4,5}

2. 累積和
acc[] = {0,0,3,7,12}

3. にぶたん。取得要素数で探索をする。
low = 1
high = 5+1 (A.size() まで解答になるよう、A.size()+ちょい までとる)
low が答えになる。

mid = (high + low)/2

・mid = 3 のとき // 3 要素をとるよ
開始indexを全探索する。
1) A[0]~A[2] = {0,0,3}
中央値は A[1] = 0
cost = abs(0-0) + abs(0-0) + abs(3-0) = 3
これは K=2より大きいのでダメ。

2) A[1]~A[3] = {0,3,4}
中央値はA[2] = 3
cost = abs(3-0) + abs(3-3) + abs(4-3) = 4 > 2
K=2より大きいのでダメ。

3) A[2]~A[4] = {3,4,5}
中央値はA[3] = 4
cost = abs(4-3) + abs(4-4) + abs(5-4) = 2
これは、K=2以下なのでOK。 low = 3 が解答候補。

low = 3
high = 6
・mid = 4 のとき
1) A[0]~A[3] = {0,0,3,4}
中央値は A[1] = 0  // べつに A[2] でもいい。 A[1] 以上 A[2] 以下ならなんでもいい。
cost = abs(A[1]-A[0]) + abs(A[1]-A[1]) + abs(A[2]-A[1]) + abs(A[3]-A[1]) = 7
これは K=2 より大きいのでダメ。

2) A[1]~A[4] = {0,3,4,5}
中央値は A[2] = 3  // べつに A[3] でもいい。 A[2] 以上 A[3] 以下ならなんでもいい。
cost = abs(A[2]-A[1]) + abs(A[2]-A[2]) + abs(A[3]-A[2]) + abs(A[4]-A[2]) = 6
これは K=2 より大きいのでダメ。

low = 3
high = 4
high - low = 1 で、差分が1以下になってしまったので終了。 low = 3 が解答。

Q. 要素数の偶奇でcostの取り方が違う？（切り口がまずいだけかも？）
目が痛くなるメモ

A.
きすう   acc[R] + acc[L-1] - acc[median] - acc[median-1]
ぐうすう acc[R] + acc[L-1] - acc[median]*2

数式をこねて見出した。それはそう。



A[] = {1,2,3,4,5,6}
acc[] = {1,3,6,10,15,21}
を考える。

・要素が 5 個の場合(きすう)
A[1]~A[5]をとるとする。{2,3,4,5,6}
中央値 median = 開始index + (要素数-1)/2 = 1 + (5-1)/2 = 3
mval = A[3] = 4

cost = mval-A[1] + mval-A[2] + mval-A[3] + A[4]-mval + A[5]-mval
                               ---------消える
     = mval + mval - mval - mval - A[1] - A[2] + A[4] + A[5]
     = - A[1] - A[2] + A[4] + A[5]
     = acc[5] + acc[0] - acc[median] - acc[median-1]
    // 543210 +   0    -     3210    -      210   =  54-21のできあがり



・要素が 4 個の場合（ぐうすう）
A[1]~A[4] をとるとする {2,3,4,5}
中央値 median = 開始index + (要素数-1)/2 = 1 + (4-1)/2 = 2
mval = A[2] = 3

cost = mval-A[1] + mval-A[2] + A[3]-mval + A[4]-mval
     = - A[1] - A[2] + A[3] + A[4]
     = acc[4] + acc[0] - acc[median] - acc[median]
    // 43210 +   0    -     3210    -     3210   =  43-21のできあがり

実装

int main(){
 cincout();
 
 string S;
 ll K;
 cin >> S >> K;
 ll N = S.size();
 vector<ll> A;
 ll dot = 0;
 rep(i, N){
   if (S[i] == 'Y') A.push_back(dot);
   else ++dot;
 }
 ll asz = A.size();
 if (asz == 0){
   cout << 0 << endl;
   return 0;
 }

 // 累積和
 ll acc[asz];
 acc[0] = A[0];
 rep(i, asz-1) acc[i+1] = acc[i] + A[i+1];
 
 // にぶたん
 ll low = 1;
 ll high = asz+10;
 while(high-low > 1){
   ll mid = (high+low)/2; // 要素数
   rep(i, asz-mid+1){ // 開始index
     ll med = i + (mid-1)/2; // 中央index
     ll r = i+mid-1;
     // ぐうすう acc[R] + acc[L-1] - 2*acc[med]
     // きすう acc[R] + acc[L-1]  - acc[med] -acc[med-1]
     ll cost = acc[r] - 2*acc[med];
     if (i>0) cost += acc[i-1];
     if (mid%2) cost += A[med];
     if (cost <= K){
       low = mid;
       break;
     }
   }
   if (low != mid) high = mid;
 }
 cout << low << endl;
}

https://atcoder.jp/contests/abc229/submissions/27555430
Q. 本番とけたの？
A. だめー。
にぶたんは最初から粘って考えてた。中身をどうとるか迷った、セグ？累積？いもす？距離間の距離でとってみる？
結局、距離間の距離でしゃくとりかもって思ったけど沼。
お風呂入ったら中央値選択が思いついた

可能性高そうな最初の直感は、きっとあってる。諦めないで。