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

C++の練習を兼ねて, AtCoder Regular Contest 166 の問題A (Replace C or Swap AB) ～問題B (Make Multiples) を解いてみた.

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

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

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

// 解き直し.
// https://atcoder.jp/contests/arc166/editorial/7182
// C++20(GCC 12.2)
#include <bits/stdc++.h>
using namespace std;
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 pb push_back
#define all(x) x.begin(), x.end()

int main(){
    
    // 1. 入力情報.
    int T;
    scanf("%d", &T);
    
    // 2. テストケース.
    rep(i, T){
        // 2-1. 各テストケース.
        int N;
        scanf("%d ", &N);
        char x[N + 1], y[N + 1];
        scanf("%s %s", x, y);
        string X(x), Y(y);
        
        // 2-2. 'C' の 位置をチェック.
        bool ok = true;
        vi yc;
        rep(j, N){
            if(Y[j] == 'C'){
                yc.pb(j);
                if(X[j] != 'C') ok = false;
            }
        }
        yc.pb(N);
        
        // 2-3. 例外.
        if(!ok){
            puts("No");
            continue;
        }
        
        // 2-4. 各区切りごとに判定.
        int s = 0;
        for(auto &e : yc){
            vi xa, xc, ya;
            repx(j, s, e){
                // 'A', 'C' の インデックスを集める.
                if(X[j] == 'A') xa.pb(j);
                if(X[j] == 'C') xc.pb(j);
                if(Y[j] == 'A') ya.pb(j);
            }
            
            // 次へ.
            s = e + 1;
            
            // 文字列 X に含まれる 'A' が 多い.
            if(xa.size() > ya.size()){
                ok = false;
                continue;
            }
            
            // 文字列 X に含まれる 'A' が 少ない.
            if(xa.size() + xc.size() < ya.size()){
                ok = false;
                continue;
            }
            
            // 文字列 X に 含まれる 'A' を 調整.
            int cur = -1;
            while(xa.size() < ya.size()) xa.pb(xc[++cur]);
            
            // sort.
            sort(all(xa));
            
            // 比較.
            rep(j, xa.size()) if(xa[j] > ya[j]) ok = false;
        }
        
        // 2-5. 出力.
        printf("%s\n", ok ? "Yes" : "No");
    }
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc166/editorial/7182

// C++20(GCC 12.2)

#include <bits/stdc++.h>

using namespace std;

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 pb push_back

#define all(x) x.begin(), x.end()

int main(){

// 1. 入力情報.

int T;

scanf("%d", &T);

// 2. テストケース.

rep(i, T){

// 2-1. 各テストケース.

int N;

scanf("%d ", &N);

char x[N + 1], y[N + 1];

scanf("%s %s", x, y);

string X(x), Y(y);

// 2-2. 'C' の位置をチェック.

bool ok = true;

vi yc;

rep(j, N){

if(Y[j] == 'C'){

yc.pb(j);

if(X[j] != 'C') ok = false;

}

yc.pb(N);

// 2-3. 例外.

if(!ok){

puts("No");

continue;

}

// 2-4. 各区切りごとに判定.

int s = 0;

for(auto &e : yc){

vi xa, xc, ya;

repx(j, s, e){

// 'A', 'C' のインデックスを集める.

if(X[j] == 'A') xa.pb(j);

if(X[j] == 'C') xc.pb(j);

if(Y[j] == 'A') ya.pb(j);

}

// 次へ.

s = e + 1;

// 文字列 X に含まれる 'A' が多い.

if(xa.size() > ya.size()){

ok = false;

continue;

}

// 文字列 X に含まれる 'A' が少ない.

if(xa.size() + xc.size() < ya.size()){

ok = false;

continue;

}

// 文字列 X に含まれる 'A' を調整.

int cur = -1;

while(xa.size() < ya.size()) xa.pb(xc[++cur]);

// sort.

sort(all(xa));

// 比較.

rep(j, xa.size()) if(xa[j] > ya[j]) ok = false;

}

// 2-5. 出力.

printf("%s\n", ok ? "Yes" : "No");

}

return 0;

}

[入力例]
6
3 ABC ABC
1 C B
1 B C
2 AB BA
2 BA AB
3 CCB ABA

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

[入力例]
7
5 ABABA BABAB
5 ABCBC BBABA
5 CCCCC CBABC
5 BBAAA AAABB
5 AAABB BBAAA
5 ACACB BAACB
5 ACACB BBACA

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

[入力例]
10
1 C B
2 AB BA
3 ACB ACC
4 ACBC ABAA
5 ACAAC ABBAA
6 ACBBCC BCBAAB
7 ABCABCB BACABCB
8 BACCABAA BBAABBAA
9 ABCABCABC ABCBABAAA
10 ABCBCABBCA BACBABBAAA

[出力例]
Yes
Yes
No
Yes
Yes
No
Yes
No
Yes
Yes

[入力例]

3 ABC ABC

1 C B

1 B C

2 AB BA

2 BA AB

3 CCB ABA

[出力例]

Yes

※AtCoderのテストケースより

[入力例]

5 ABABA BABAB

5 ABCBC BBABA

5 CCCCC CBABC

5 BBAAA AAABB

5 AAABB BBAAA

5 ACACB BAACB

5 ACACB BBACA

[出力例]

Yes

※AtCoderのテストケースより

[入力例]

1 C B

2 AB BA

3 ACB ACC

4 ACBC ABAA

5 ACAAC ABBAA

6 ACBBCC BCBAAB

7 ABCABCB BACABCB

8 BACCABAA BBAABBAA

9 ABCABCABC ABCBABAAA

10 ABCBCABBCA BACBABBAAA

[出力例]

Yes

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

// 解き直し.
// https://atcoder.jp/contests/arc166/editorial/7183
// C++20(GCC 12.2)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vl = vector<LL>;
#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 pb push_back
const LL INF = 2e18;
LL A[202020], dp[202020][8];

int main(){
    
    // 1. 入力情報.
    int N;
    LL a, b, c;
    scanf("%d %lld %lld %lld", &N, &a, &b, &c);
    rep(i, N) scanf("%lld", &A[i]);
    
    // 2. 事前準備.
    LL gAB = __gcd(a, b);
    LL gBC = __gcd(b, c);
    LL gCA = __gcd(c, a);
    LL gABC = __gcd(gAB, c);
    LL lAB = a / gAB * b;
    LL lBC = b / gBC * c;
    LL lCA = c / gCA * a;
    LL lABC = lAB / __gcd(lAB, lBC) * lBC;
    
    // 3. 倍数チェック.
    auto f = [&](LL n, LL a, LL b, LL c) -> int {
        int ret = 0;
        if(n % a == 0) ret |= 1;
        if(n % b == 0) ret |= 2;
        if(n % c == 0) ret |= 4;
        return ret;
    };
    
    // 4. dp更新.
    // -> 第二成分は, 以下のルールを, ORでとった結果をインデックスに指定.
    // a の 倍数 => 1
    // b の 倍数 => 2
    // c の 倍数 => 4
    rep(i, N + 1) rep(j, 8) dp[i][j] = INF;
    dp[0][0] = 0;
    rep(i, N){
        // 何もしない.
        vl op;
        op.pb(A[i]);
        
        // a の倍数.
        op.pb((A[i] + a - 1) / a * a);
        
        // b の倍数.
        op.pb((A[i] + b - 1) / b * b);
        
        // c の倍数.
        op.pb((A[i] + c - 1) / c * c);
        
        // lcm(a, b) の倍数.
        op.pb((A[i] + lAB - 1) / lAB * lAB);
        
        // lcm(b, c) の倍数.
        op.pb((A[i] + lBC - 1) / lBC * lBC);
        
        // lcm(c, a) の倍数.
        op.pb((A[i] + lCA - 1) / lCA * lCA);
        
        // lcm(a, b, c) の倍数.
        op.pb((A[i] + lABC - 1) / lABC * lABC);
        
        // 4-2. 各状態ごとに, dp更新.
        rep(j, 8){
            // 状態.
            int s = f(op[j], a, b, c);
            
            // 遷移(状態 k からの遷移先は, 状態 (s | k)).
            rep(k, 8){
                //  状態 s が 状態 k の 部分集合の場合.
                if((k & s) == s){
                    dp[i + 1][s | k] = min(dp[i + 1][s | k], dp[i][k]);
                    continue;
                }
                
                //  状態 s が 状態 k の 部分集合でない場合.
                // -> 操作回数(op[j] - A[i]) を 考慮する必要がある.
                dp[i + 1][s | k] = min(dp[i + 1][s | k], dp[i][k] + op[j] - A[i]);
            }
        }
    }
    
    // 5. 出力.
    printf("%lld\n", dp[N][7]);
    return 0;
    
}

100

// 解き直し.

// https://atcoder.jp/contests/arc166/editorial/7183

// C++20(GCC 12.2)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vl = vector<LL>;

#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 pb push_back

const LL INF = 2e18;

LL A[202020], dp[202020][8];

int main(){

// 1. 入力情報.

int N;

LL a, b, c;

scanf("%d %lld %lld %lld", &N, &a, &b, &c);

rep(i, N) scanf("%lld", &A[i]);

// 2. 事前準備.

LL gAB = __gcd(a, b);

LL gBC = __gcd(b, c);

LL gCA = __gcd(c, a);

LL gABC = __gcd(gAB, c);

LL lAB = a / gAB * b;

LL lBC = b / gBC * c;

LL lCA = c / gCA * a;

LL lABC = lAB / __gcd(lAB, lBC) * lBC;

// 3. 倍数チェック.

auto f = [&](LL n, LL a, LL b, LL c) -> int {

int ret = 0;

if(n % a == 0) ret |= 1;

if(n % b == 0) ret |= 2;

if(n % c == 0) ret |= 4;

return ret;

};

// 4. dp更新.

// -> 第二成分は, 以下のルールを, ORでとった結果をインデックスに指定.

// a の倍数 => 1

// b の倍数 => 2

// c の倍数 => 4

rep(i, N + 1) rep(j, 8) dp[i][j] = INF;

dp[0][0] = 0;

rep(i, N){

// 何もしない.

vl op;

op.pb(A[i]);

// a の倍数.

op.pb((A[i] + a - 1) / a * a);

// b の倍数.

op.pb((A[i] + b - 1) / b * b);

// c の倍数.

op.pb((A[i] + c - 1) / c * c);

// lcm(a, b) の倍数.

op.pb((A[i] + lAB - 1) / lAB * lAB);

// lcm(b, c) の倍数.

op.pb((A[i] + lBC - 1) / lBC * lBC);

// lcm(c, a) の倍数.

op.pb((A[i] + lCA - 1) / lCA * lCA);

// lcm(a, b, c) の倍数.

op.pb((A[i] + lABC - 1) / lABC * lABC);

// 4-2. 各状態ごとに, dp更新.

rep(j, 8){

// 状態.

int s = f(op[j], a, b, c);

// 遷移(状態 k からの遷移先は, 状態 (s | k)).

rep(k, 8){

// 状態 s が状態 k の部分集合の場合.

if((k & s) == s){

dp[i + 1][s | k] = min(dp[i + 1][s | k], dp[i][k]);

continue;

}

// 状態 s が状態 k の部分集合でない場合.

// -> 操作回数(op[j] - A[i]) を考慮する必要がある.

dp[i + 1][s | k] = min(dp[i + 1][s | k], dp[i][k] + op[j] - A[i]);

}

// 5. 出力.

printf("%lld\n", dp[N][7]);

return 0;

}

[入力例]
3 3 4 5
8 9 11

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

[入力例]
3 3 4 5
14 11 59

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

[入力例]
6 10 20 30
8 17 5 28 39 13

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

[入力例]
1 999997 999998 999999
123456789123456789

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

[入力例]
5 3 5 12
79 83 59 111 98

[出力例]
1

[入力例]
10 7 13 31
79 54 3 65 88 51 38 73 123 78

[出力例]
3

[入力例]
100 2022 2023 2024
2981 4736 3411 8068 10584 389 2608 9985 684 11830 172 7465 1191 11411 5304 7646 1078 2925 6130 5694 411 6933 11928 3835 2154 8225 5906 3628 2216 10621 3409 7540 10503 11075 10477 2243 6708 412 11670 4915 11346 2017 5480 12087 9548 8264 7241 1148 509 4393 4078 9366 11422 6376 9437 5159 2238 5775 6517 3782 9302 7383 2867 3699 8125 2688 3944 6273 9013 7226 2275 5231 804 5789 5393 5683 10756 2671 6203 233 4354 7395 12073 3130 8366 995 5174 387 10195 393 11277 4502 7461 10823 10032 9122 3627 3388 6191 2374

[出力例]
76

[入力例]
300 31415 92653 58979
95878 11042 74842 71977 8434 71909 4719 71599 5217 115259 40165 40023 73330 14444 43158 40431 69014 46069 3575 48234 111675 76805 119595 120108 48976 99043 115430 73364 68890 45442 46584 42696 16106 39204 56507 87346 71220 65320 28459 22532 120425 51503 123041 104636 86123 24584 31166 49145 51897 85658 112667 16456 46553 31285 40940 96766 112717 15172 82933 96285 35222 84816 105328 123100 98971 70784 81388 25100 35509 26758 84449 96854 115706 47557 93362 2091 50288 17447 119007 23813 56200 69886 28646 51117 69959 80929 48759 115929 102536 33102 101192 98958 33201 17629 31347 83487 100317 3081 115347 37719 97540 92178 110187 22675 88385 9638 93384 46722 69302 64303 84737 29052 109422 114147 67049 54142 89624 41003 63736 40848 44403 69120 74396 32825 31020 20000 13853 42940 110681 105457 122320 65108 27384 30617 53446 86286 39140 58644 33762 55193 110992 51746 73785 34559 13628 59067 56068 34389 108449 22996 3143 100820 85122 11175 85321 113463 31329 86003 114600 80049 78543 95285 70209 21235 79741 104283 404 102283 38151 97825 12259 8721 9886 111445 116702 94793 18335 72040 76328 26314 43995 109237 120473 110066 50128 118544 30007 93924 20116 119344 59713 118653 61229 5823 106022 58536 12814 110755 14807 82060 11455 31816 55103 44137 109484 73331 65863 97384 93461 70888 83773 78645 91691 26985 19185 26087 53981 43703 43333 101604 69706 18417 85362 64956 34082 117355 28363 92691 118224 79433 52262 19876 12428 89844 65977 57152 43797 73580 13914 108756 18039 24535 21199 64947 9724 121639 88604 64034 101861 55770 27244 6891 74806 113840 68011 76634 51062 13570 106890 121794 89934 32532 45758 17043 111584 31058 60756 36975 62134 98955 93366 56236 45379 119759 97802 75866 58850 30659 90726 21983 3572 3959 14085 85735 64424 112289 36558 10951 19387 53368 58845 11335 106045 93872 13491 18563 42606 84514 99811 10140

[出力例]
672

[入力例]

3 3 4 5

8 9 11

[出力例]

※AtCoderのテストケースより

[入力例]

3 3 4 5

14 11 59

[出力例]

※AtCoderのテストケースより

[入力例]

6 10 20 30

8 17 5 28 39 13

[出力例]

※AtCoderのテストケースより

[入力例]

1 999997 999998 999999

123456789123456789

[出力例]

876537210887543205

※AtCoderのテストケースより

[入力例]

5 3 5 12

79 83 59 111 98

[出力例]

[入力例]

10 7 13 31

79 54 3 65 88 51 38 73 123 78

[出力例]

[入力例]

100 2022 2023 2024

2981 4736 3411 8068 10584 389 2608 9985 684 11830 172 7465 1191 11411 5304 7646 1078 2925 6130 5694 411 6933 11928 3835 2154 8225 5906 3628 2216 10621 3409 7540 10503 11075 10477 2243 6708 412 11670 4915 11346 2017 5480 12087 9548 8264 7241 1148 509 4393 4078 9366 11422 6376 9437 5159 2238 5775 6517 3782 9302 7383 2867 3699 8125 2688 3944 6273 9013 7226 2275 5231 804 5789 5393 5683 10756 2671 6203 233 4354 7395 12073 3130 8366 995 5174 387 10195 393 11277 4502 7461 10823 10032 9122 3627 3388 6191 2374

[出力例]

[入力例]

300 31415 92653 58979

95878 11042 74842 71977 8434 71909 4719 71599 5217 115259 40165 40023 73330 14444 43158 40431 69014 46069 3575 48234 111675 76805 119595 120108 48976 99043 115430 73364 68890 45442 46584 42696 16106 39204 56507 87346 71220 65320 28459 22532 120425 51503 123041 104636 86123 24584 31166 49145 51897 85658 112667 16456 46553 31285 40940 96766 112717 15172 82933 96285 35222 84816 105328 123100 98971 70784 81388 25100 35509 26758 84449 96854 115706 47557 93362 2091 50288 17447 119007 23813 56200 69886 28646 51117 69959 80929 48759 115929 102536 33102 101192 98958 33201 17629 31347 83487 100317 3081 115347 37719 97540 92178 110187 22675 88385 9638 93384 46722 69302 64303 84737 29052 109422 114147 67049 54142 89624 41003 63736 40848 44403 69120 74396 32825 31020 20000 13853 42940 110681 105457 122320 65108 27384 30617 53446 86286 39140 58644 33762 55193 110992 51746 73785 34559 13628 59067 56068 34389 108449 22996 3143 100820 85122 11175 85321 113463 31329 86003 114600 80049 78543 95285 70209 21235 79741 104283 404 102283 38151 97825 12259 8721 9886 111445 116702 94793 18335 72040 76328 26314 43995 109237 120473 110066 50128 118544 30007 93924 20116 119344 59713 118653 61229 5823 106022 58536 12814 110755 14807 82060 11455 31816 55103 44137 109484 73331 65863 97384 93461 70888 83773 78645 91691 26985 19185 26087 53981 43703 43333 101604 69706 18417 85362 64956 34082 117355 28363 92691 118224 79433 52262 19876 12428 89844 65977 57152 43797 73580 13914 108756 18039 24535 21199 64947 9724 121639 88604 64034 101861 55770 27244 6891 74806 113840 68011 76634 51062 13570 106890 121794 89934 32532 45758 17043 111584 31058 60756 36975 62134 98955 93366 56236 45379 119759 97802 75866 58850 30659 90726 21983 3572 3959 14085 85735 64424 112289 36558 10951 19387 53368 58845 11335 106045 93872 13491 18563 42606 84514 99811 10140

[出力例]

672

■参照サイト
AtCoder Regular Contest 166

C++の練習を兼ねて, AtCoder Regular Contest 166 の 問題A (Replace C or Swap AB) ～ 問題B (Make Multiples) を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 166 の問題A (Replace C or Swap AB) ～問題B (Make Multiples) を解いてみた.

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