結果

問題 No.672 最長AB列
ユーザー @abcde@abcde
提出日時 2019-03-16 03:08:15
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 3,570 bytes
コンパイル時間 1,334 ms
コンパイル使用メモリ 159,708 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-01 22:17:25
合計ジャッジ時間 2,131 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 1 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 WA -
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 1 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 1 ms
5,376 KB
testcase_09 AC 15 ms
5,872 KB
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 AC 17 ms
6,000 KB
testcase_18 WA -
権限があれば一括ダウンロードができます

ソースコード

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 = 1; i < len; i++){
        // 左: l番目, 右: r番目.
        int l = i, r = len - 1;
        int a = 0, b = 0;
        while(l < r){
            // 'A', 'B' の 出現数 を 比較.
            // -> A[l - 1], B[l - 1] を使うように, ロジックを修正.
            a = A[r] - A[l - 1], b = B[r] - B[l - 1];
            // if(i == 4) cout << "a=" << a << " r=" << r << " b=" << b << " l=" << l << endl;
            // 同じ場合は, 終了.
            if(a == b) break;
            // 'A', 'B' の 出現数 に差がある場合は, 中心を移動.
            if(b == a + 1 && A[r] < B[r]){
                r--;
                continue;
            }
            if(a == b + 1 && A[r] > B[r]){
                r--;
                continue;
            }
            if(a > b && A[r] >= B[r]){
                r = (l + r - 1) / 2;
                continue;
            }
            if(a > b && A[r] < B[r]){
                l = (l + r + 1) / 2;
                continue;
            }
            if(a < b && A[r] >= B[r]){
                l = (l + r + 1) / 2;
                continue;
            }
            if(a < b && A[r] < B[r]){
                r = (l + r - 1) / 2;
                continue;
            }
        }
        if(a == b) dp[i] = (a + b);
    }
    // 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
    // -> WAとなっている(A: 11個, B: 9個 の 計20個(ABAAABBAAABAAABBABBB) が出力されてた).
    // 
    // ロジック修正後は, 
    // -> 0 0 2 0 2 2 2 4 0 0 0 0 0 6 2 0 0 0 0 2 20 0 18 0 0 0 14 0 0 0 0 0 0 0 0 0 0 0 0 0
    // -> A: 10個, B: 10個 の 計20個(BAAABBAAABAAABBABBBB) が出力された.
    // 
    // ex.
    // BBBBABBABBBBBB
    // -> 4個が正解だが, 2個で出力された.
    // ログ的には, 
    // BBBB ABBAB BBBBB
    // a=2 r=13 b=8 l=4
    // a=2 r=8 b=3 l=4
    // a=1 r=5 b=1 l=4
    // のようになっており, 2分探索で失敗していることが判明.
    // 
    // a=2 r=13 b=8 l=4
    // a=2 r=8 b=3 l=4
    // a=2 r=7 b=2 l=4
    // -> この修正が, どこまで通用するのか不明.
    // 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