結果

問題 No.672 最長AB列
コンテスト
ユーザー @abcde
提出日時 2019-03-16 02:28:26
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 2,270 bytes
コンパイル時間 1,384 ms
コンパイル使用メモリ 159,708 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-07-01 22:16:41
合計ジャッジ時間 2,669 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 7 WA * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
const int LIMIT = 2 * 1e6;

int main() {
    
    // 1. 入力情報取得.
    string S;
    cin >> S;
    
    // 2. 'A', 'B' の 出現数 の 累積和は？
    int len = S.size();
    int A[len], B[len];
    
    for(int i = 0; i < len; i++) A[i] = 0, B[i] = 0;
    if(S[0] == 'A') A[0]++;
    if(S[0] == 'B') B[0]++;
    for(int i = 1; i < len; i++){
        A[i] = A[i - 1], B[i] = B[i - 1];
        if(S[i] == 'A') A[i]++;
        if(S[i] == 'B') B[i]++;
    }
    // ex. 
    // BBAAABAAABBAB
    // 'A' の 累積出現数 -> 0 0 1 2 3 3 4 5 6 6 6 7 7 
    // 'B' の 累積出現数 -> 1 2 2 2 2 3 3 3 3 4 5 5 6 
    // for(int i = 0; i < len; i++) cout << A[i] << " ";
    // for(int i = 0; i < len; i++) cout << B[i] << " ";

    // 3. 文字列S の i番目までの最長AB列を順次求めていく.
    // -> これを, dp[i] と置いてみる.
    int dp[len];
    for(int i = 0; i < len; i++) dp[i] = 0;
    
    // 各文字(S[i])から探索開始した時に, 'A', 'B' の 出現数 が等しくなる場所を, 2分探索.
    for(int i = 0; i < len; i++){
        // 左: l番目, 右: r番目.
        int l = i, r = len - 1;
        while(l < r){
            // 'A', 'B' の 出現数 を 比較.
            int a = A[r] - A[l], b = B[r] - B[l];
            // cout << "a=" << a << " r=" << r << " b=" << b << " l=" << l << endl;
            // 同じ場合は, 終了.
            if(a == b) break;
            // 'A', 'B' の 出現数 に差がある場合は, 中心を移動.
            if(a > b && A[r] >= B[r]) r = (l + r - 1) / 2;
            if(a > b && A[r] < B[r])  l = (l + r + 1) / 2;
            if(a < b && A[r] >= B[r]) l = (l + r + 1) / 2;
            if(a < b && A[r] < B[r])  r = (l + r - 1) / 2;
        }
        dp[i] += A[r] - A[l];
        dp[i] += B[r] - B[l];
    }
    // ex.
    // BBABBAABABAAABBABAAABAAABBAAABAAABBABBBB
    // S[i]スタートの最長AB列の長さ
    // -> 4 4 4 0 0 0 0 0 0 0 0 6 6 2 0 2 0 0 0 20 0 18 0 0 0 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0
    // for(int i = 0; i < len; i++) cout << dp[i] << " ";
    
    // 4. 後処理.
    int ans = 0;
    for(int i = 0; i < len; i++) ans = max(ans, dp[i]);
    cout << ans << endl;
    return 0;
    
}
0