C++ の動作確認をしてみた（４１２）

C++の練習を兼ねて, AtCoder Regular Contest 113 の問題C (String Invasion) を解いてみた.

■感想.
1. 問題Cは, 方針が見えなかったので, 解説を参考に実装して, AC版に到達できたので, 良かったと思う.
2. 不思議な数え上げ方をする感じがして, 個人的には, 非常に面白い問題に感じた.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/arc113/editorial/710
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vi = vector<int>;
#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--)
#define pub push_back
#define pob pop_back

int main(){
    
    // 1. 入力情報.
    char c[202020];
    scanf("%s", c);
    string S(c);
    
    // 2. 本質的なブロックの位置を保存.
    vi vl, vr;
    char bef = S[0], cur, befBlock = '#', curBlock = '#';
    int cnt = 1;
    S.pub('#'); // 番兵(追加).
    repx(i, 1, S.size()){
        // 2-1. 今回分更新.
        cur = S[i];
        
        // 2-2. 評価.
        if(bef == cur){
            // インクリメント.
            cnt++;
            
            // 今回のブロックを保存.
            curBlock = cur;
        }else{
            if(cnt > 1){
                // 前回のブロックと異なれば, 登録.
                if(befBlock != curBlock){
                    // 今回のブロックの出現位置を保存.
                    vl.pub(i - cnt);
                    vr.pub(i - 1);
                    
                    // 前回のブロックを保存.
                    befBlock = bef;
                }
            }
            
            // 初期化.
            cnt = 1;
        }
        
        // 2-3. 前回分更新.
        bef = cur;
    }
    S.pob(); // 番兵(削除).
    
    // 3. 各本質的なブロックに対するポテンシャルを計算し, 加算.
    LL ans = 0;
    int vlSize = vl.size(), sl = S.size();
    rep(i, vlSize){
        // 3-1. 一番最後でない本質的なブロック.
        LL p = 0;
        if(i < vlSize - 1){
            // (vr[i] + 1) ～ (vl[i + 1] - 1)文字目で, B の文字 と異なるもの.
            char B = S[vr[i]];
            repx(j, vr[i] + 1, vl[i + 1]) if(B != S[j]) p++;
            
            // vl[i + 1] ～ 文字列 S の 末尾まで.
            p += (LL)sl - (LL)vl[i + 1];
        }
        
        // 3-2. 一番最後の本質的なブロック.
        if(i == vlSize - 1){
            // (vr[i] + 1) ～ 文字列 S の 末尾までで, B の文字 と異なるもの.
            char B = S[vr[i]];
            repx(j, vr[i] + 1, sl) if(B != S[j]) p++;
        }
        
        // 3-3. 集計.
        ans += p;
    }
    
    // 4. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc113/editorial/710

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vi = vector<int>;

#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--)

#define pub push_back

#define pob pop_back

int main(){

// 1. 入力情報.

char c[202020];

scanf("%s", c);

string S(c);

// 2. 本質的なブロックの位置を保存.

vi vl, vr;

char bef = S[0], cur, befBlock = '#', curBlock = '#';

int cnt = 1;

S.pub('#'); // 番兵(追加).

repx(i, 1, S.size()){

// 2-1. 今回分更新.

cur = S[i];

// 2-2. 評価.

if(bef == cur){

// インクリメント.

cnt++;

// 今回のブロックを保存.

curBlock = cur;

}else{

if(cnt > 1){

// 前回のブロックと異なれば, 登録.

if(befBlock != curBlock){

// 今回のブロックの出現位置を保存.

vl.pub(i - cnt);

vr.pub(i - 1);

// 前回のブロックを保存.

befBlock = bef;

}

// 初期化.

cnt = 1;

}

// 2-3. 前回分更新.

bef = cur;

}

S.pob(); // 番兵(削除).

// 3. 各本質的なブロックに対するポテンシャルを計算し, 加算.

LL ans = 0;

int vlSize = vl.size(), sl = S.size();

rep(i, vlSize){

// 3-1. 一番最後でない本質的なブロック.

LL p = 0;

if(i < vlSize - 1){

// (vr[i] + 1) ～ (vl[i + 1] - 1)文字目で, B の文字と異なるもの.

char B = S[vr[i]];

repx(j, vr[i] + 1, vl[i + 1]) if(B != S[j]) p++;

// vl[i + 1] ～文字列 S の末尾まで.

p += (LL)sl - (LL)vl[i + 1];

}

// 3-2. 一番最後の本質的なブロック.

if(i == vlSize - 1){

// (vr[i] + 1) ～文字列 S の末尾までで, B の文字と異なるもの.

char B = S[vr[i]];

repx(j, vr[i] + 1, sl) if(B != S[j]) p++;

}

// 3-3. 集計.

ans += p;

}

// 4. 出力.

printf("%lld\n", ans);

return 0;

}

[入力例]
accept

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

[入力例]
atcoder

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

[入力例]
anerroroccurred

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

[入力例]
jugemujugemugokonosurikirekaijarisuigyonosuigyomatsuunraimatsufuraimatsukunerutokoroni

[出力例]
28

[入力例]
fnmgqmvyzllkwafhvhbsghxfnthbvxqxzyolcflkofndhdrdmdkyklpwperzvhupkvjfropbglivpkqijhppipnyurjaxffcsonfqmcnbbrkeszfngkwysaudpumenkyyqzokaieootkngnpunkvvo

[出力例]
332

[入力例]
gwvgigonsomqaoxokvrekkdysazfhnultxnllhknycptocjeroqogzmvltybuizxykbxzcgwjvtrptachepcxgaggzigfnmhoajcxbrqrqndiaxaeyrnuffnlvvgqnxtmazocowkeitvsqoqxbbmanpfoczjxlxhczhjvgwqsqadtiygxsiqtodiyzmifubgqjvkffgzzxmquflrsmifsujqjuhvtykkxbvnokxfnbpcnnryiyywvewsbzzrsezsnvueilqsevxacomiywlviuvjhdzvxegceocklfacloph

[出力例]
1701

[入力例]

[出力例]

※AtCoderのテストケースより

[入力例]

atcoder

[出力例]

※AtCoderのテストケースより

[入力例]

anerroroccurred

[出力例]

※AtCoderのテストケースより

[入力例]

jugemujugemugokonosurikirekaijarisuigyonosuigyomatsuunraimatsufuraimatsukunerutokoroni

[出力例]

[入力例]

fnmgqmvyzllkwafhvhbsghxfnthbvxqxzyolcflkofndhdrdmdkyklpwperzvhupkvjfropbglivpkqijhppipnyurjaxffcsonfqmcnbbrkeszfngkwysaudpumenkyyqzokaieootkngnpunkvvo

[出力例]

332

[入力例]

gwvgigonsomqaoxokvrekkdysazfhnultxnllhknycptocjeroqogzmvltybuizxykbxzcgwjvtrptachepcxgaggzigfnmhoajcxbrqrqndiaxaeyrnuffnlvvgqnxtmazocowkeitvsqoqxbbmanpfoczjxlxhczhjvgwqsqadtiygxsiqtodiyzmifubgqjvkffgzzxmquflrsmifsujqjuhvtykkxbvnokxfnbpcnnryiyywvewsbzzrsezsnvueilqsevxacomiywlviuvjhdzvxegceocklfacloph

[出力例]

1701

■参照サイト
AtCoder Regular Contest 113

C++の練習を兼ねて, AtCoder Regular Contest 113 の 問題C (String Invasion) を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 113 の問題C (String Invasion) を解いてみた.

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