C++ の動作確認をしてみた（９６２）

C++の練習を兼ねて, AtCoder Grand Contest 045 の問題B (01 Unbalanced) を解いてみた.

■感想.
1. 問題Bは, 方針が見えなかったので, 解説を参考に実装して, ようやく, AC版に到達できた.
2. 個人的には, 解説のロジックで, 計算可能であることが, 非常に不思議な印象を受けた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

本家のサイト AtCoder Grand Contest 045 解説の各リンクをご覧下さい.

■C++版プログラム(問題B／AC版).

// 解き直し.
// https://img.atcoder.jp/agc045/editorial.pdf
// C++20(GCC 12.2)
#include <bits/stdc++.h>
using namespace std;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
const int INF = 2020202020;
int cum[1010101], rMaxCum[1010101], u1[1010101], u1Cum[1010101], u2[1010101], u2Cum[1010101];

int main(){
    
    // 1. 入力情報.
    char c[1010101];
    scanf("%s", c);
    string s(c);
    int n = s.size();
    
    // 2. 事前準備(以降, 解説通り).
    // 2-1. 初期化.
    rep(i, n) u1[i] = u2[i] = (s[i] == '1') ? +1 : -1;
    
    // 2-2. 累積和(左から計算).
    // -> cum[0] = 0 も 考慮する.
    rep(i, n) cum[i + 1] = (s[i] == '1') ? cum[i] + 1 : cum[i] - 1;
    
    // 2-3. 累積和の最大値(右から計算).
    rep(i, 1010101) rMaxCum[i] = -INF;
    repr(i, n, 0) rMaxCum[i] = max(rMaxCum[i + 1], cum[i]);
    
    // 3. z.
    int z = -INF;
    rep(i, n + 1) z = max(z, cum[i]);
    
    // 4. 貪欲アルゴリズム.
    // 4-1. z 基準.
    int cnt = 0;
    rep(i, n){
        // 次へ.
        if(s[i] != '?') continue;
        
        // '?' を '1' に 変更できるか？
        // 累積和(左側).
        if(cum[i + 1] + 2 * (cnt + 1) > z) continue;
        
        // 累積和(右側).
        if(rMaxCum[i + 1] + 2 * (cnt + 1) > z) continue;
        
        // '?' を '1' に 変更.
        u1[i] = +1;
        
        // インクリメント.
        ++cnt;
    }
    
    // 4-2. (z + 1) 基準.
    cnt = 0;
    rep(i, n){
        // 次へ.
        if(s[i] != '?') continue;
        
        // '?' を '1' に 変更できるか？
        // 累積和(左側).
        if(cum[i + 1] + 2 * (cnt + 1) > z + 1) continue;
        
        // 累積和(右側).
        if(rMaxCum[i + 1] + 2 * (cnt + 1) > z + 1) continue;
        
        // '?' を '1' に 変更.
        u2[i] = +1;
        
        // インクリメント.
        ++cnt;
    }
    
    // 5. 計算準備(アンバランス度).
    // 5-1. f(z).
    int f1 = INF;
    rep(i, n) u1Cum[i + 1] = u1Cum[i] + u1[i];
    rep(i, n + 1) f1 = min(f1, u1Cum[i]);
    
    // 5-2. f(z + 1).
    int f2 = INF;
    rep(i, n) u2Cum[i + 1] = u2Cum[i] + u2[i];
    rep(i, n + 1) f2 = min(f2, u2Cum[i]);
    
    // 6. 出力.
    printf("%d\n", min(z - f1, z + 1 - f2));
    return 0;
    
}

// 解き直し.

// https://img.atcoder.jp/agc045/editorial.pdf

// C++20(GCC 12.2)

#include <bits/stdc++.h>

using namespace std;

#define repex(i, a, b, c) for(int i = a; i < b; i += c)

#define repx(i, a, b) repex(i, a, b, 1)

#define rep(i, n) repx(i, 0, n)

#define repr(i, a, b) for(int i = a; i >= b; i--)

const int INF = 2020202020;

int cum[1010101], rMaxCum[1010101], u1[1010101], u1Cum[1010101], u2[1010101], u2Cum[1010101];

int main(){

// 1. 入力情報.

char c[1010101];

scanf("%s", c);

string s(c);

int n = s.size();

// 2. 事前準備(以降, 解説通り).

// 2-1. 初期化.

rep(i, n) u1[i] = u2[i] = (s[i] == '1') ? +1 : -1;

// 2-2. 累積和(左から計算).

// -> cum[0] = 0 も考慮する.

rep(i, n) cum[i + 1] = (s[i] == '1') ? cum[i] + 1 : cum[i] - 1;

// 2-3. 累積和の最大値(右から計算).

rep(i, 1010101) rMaxCum[i] = -INF;

repr(i, n, 0) rMaxCum[i] = max(rMaxCum[i + 1], cum[i]);

// 3. z.

int z = -INF;

rep(i, n + 1) z = max(z, cum[i]);

// 4. 貪欲アルゴリズム.

// 4-1. z 基準.

int cnt = 0;

rep(i, n){

// 次へ.

if(s[i] != '?') continue;

// '?' を '1' に変更できるか？

// 累積和(左側).

if(cum[i + 1] + 2 * (cnt + 1) > z) continue;

// 累積和(右側).

if(rMaxCum[i + 1] + 2 * (cnt + 1) > z) continue;

// '?' を '1' に変更.

u1[i] = +1;

// インクリメント.

++cnt;

}

// 4-2. (z + 1) 基準.

cnt = 0;

rep(i, n){

// 次へ.

if(s[i] != '?') continue;

// '?' を '1' に変更できるか？

// 累積和(左側).

if(cum[i + 1] + 2 * (cnt + 1) > z + 1) continue;

// 累積和(右側).

if(rMaxCum[i + 1] + 2 * (cnt + 1) > z + 1) continue;

// '?' を '1' に変更.

u2[i] = +1;

// インクリメント.

++cnt;

}

// 5. 計算準備(アンバランス度).

// 5-1. f(z).

int f1 = INF;

rep(i, n) u1Cum[i + 1] = u1Cum[i] + u1[i];

rep(i, n + 1) f1 = min(f1, u1Cum[i]);

// 5-2. f(z + 1).

int f2 = INF;

rep(i, n) u2Cum[i + 1] = u2Cum[i] + u2[i];

rep(i, n + 1) f2 = min(f2, u2Cum[i]);

// 6. 出力.

printf("%d\n", min(z - f1, z + 1 - f2));

return 0;

}

[入力例]
0??

[出力例]
1
※AtCoderのテストケースより

[入力例]
0??0

[出力例]
2
※AtCoderのテストケースより

[入力例]
??00????0??0????0?0??00??1???11?1?1???1?11?111???1

[出力例]
4
※AtCoderのテストケースより

[入力例]
01??10?1?0

[出力例]
2

[入力例]
10?0??101??

[出力例]
1

[入力例]
0010??0???01010?00110?101011?0?101111?0??0?111?010

[出力例]
4

[入力例]
??111110100000000???1100??0???11110???0000??1100111110000111??11??1110111111??001111?111100111110000

[出力例]
16

[入力例]
00?11??011111?0101000??11???01??10?10??0?1?0011??1?00?00???10?0011?0?1001011?110000??0010?001010?1??1110?01011?00111?10?1?1??00?10?00??111?000?11?001?01??11?0100?00111???1???????1?001011011?0?0?1?0?0?

[出力例]
5

[入力例]
010?00??10?001????1111??0110111?101?0111001?1?10?11?1??1?01?10?0100000001?101??1?1?????00????1?1??00?0111?1?11?000?011????0000100001010?110?0??100110?0001100???100?000111?00?110?0?10011?011010??01?0001?01??1001010??1???1?00110?10000?0100????1001?110101?1?11000?000011010101?????01?01110???1?010110011101?000??1?010110100?0?1?10101001?01???11100?110100110?11?11100100101?101110?11110?010?1??0?00??0010001?010??10?1000?01?1010???00000?111?1??101??00100??0???1???0001011001101010?0011?1111?0??1001110?0?1?1?1?1??00?0??100?001011??10??10010???1??100?0?0?0?1110?00?111??101???11011000001?100?1??1000?111?1?01110101101?1?1??011?010?1?01011?11??001?110?10?10?1011?0?1?10????110?100100100100?0??00101???111000?10?011?0?0?????1?1010??0011000??0???01?10?1?1001?00??0??0?011011?00??10?011??1?100110?1??011010?101?1??10011?111100??111101111?1???1?101?1?110?1?01101?1???1011101?111001?0????0??011?0?000???01?11?001?011?0?11001001101?0??0??0?1011?1111???101100?1?01??0110101011?1??10?1????00???01?1?11000100?10?0??

[出力例]
8

[入力例]

0??

[出力例]

※AtCoderのテストケースより

[入力例]

0??0

[出力例]

※AtCoderのテストケースより

[入力例]

??00????0??0????0?0??00??1???11?1?1???1?11?111???1

[出力例]

※AtCoderのテストケースより

[入力例]

01??10?1?0

[出力例]

[入力例]

10?0??101??

[出力例]

[入力例]

0010??0???01010?00110?101011?0?101111?0??0?111?010

[出力例]

[入力例]

??111110100000000???1100??0???11110???0000??1100111110000111??11??1110111111??001111?111100111110000

[出力例]

[入力例]

00?11??011111?0101000??11???01??10?10??0?1?0011??1?00?00???10?0011?0?1001011?110000??0010?001010?1??1110?01011?00111?10?1?1??00?10?00??111?000?11?001?01??11?0100?00111???1???????1?001011011?0?0?1?0?0?

[出力例]

[入力例]

010?00??10?001????1111??0110111?101?0111001?1?10?11?1??1?01?10?0100000001?101??1?1?????00????1?1??00?0111?1?11?000?011????0000100001010?110?0??100110?0001100???100?000111?00?110?0?10011?011010??01?0001?01??1001010??1???1?00110?10000?0100????1001?110101?1?11000?000011010101?????01?01110???1?010110011101?000??1?010110100?0?1?10101001?01???11100?110100110?11?11100100101?101110?11110?010?1??0?00??0010001?010??10?1000?01?1010???00000?111?1??101??00100??0???1???0001011001101010?0011?1111?0??1001110?0?1?1?1?1??00?0??100?001011??10??10010???1??100?0?0?0?1110?00?111??101???11011000001?100?1??1000?111?1?01110101101?1?1??011?010?1?01011?11??001?110?10?10?1011?0?1?10????110?100100100100?0??00101???111000?10?011?0?0?????1?1010??0011000??0???01?10?1?1001?00??0??0?011011?00??10?011??1?100110?1??011010?101?1??10011?111100??111101111?1???1?101?1?110?1?01101?1???1011101?111001?0????0??011?0?000???01?11?001?011?0?11001001101?0??0??0?1011?1111???101100?1?01??0110101011?1??10?1????00???01?1?11000100?10?0??

[出力例]

■参照サイト
AtCoder Grand Contest 045

C++の練習を兼ねて, AtCoder Grand Contest 045 の 問題B (01 Unbalanced) を解いてみた.

コメントを残す コメントをキャンセル

C++の練習を兼ねて, AtCoder Grand Contest 045 の問題B (01 Unbalanced) を解いてみた.

コメントを残すコメントをキャンセル