C++ | 個人用メモ帳

2021年6月6日2021年6月6日

C++ の動作確認をしてみた（４７６）

C++の練習を兼ねて, AtCoder Beginner Contest 203 の問題F (Weed) を解いてみた.

■感想.
1. 問題Fは, 方針が見えなかったので, 解説を参考にして, ようやく, AC版に到達出来た.
2. 苦手な動的計画法の訓練を積めたので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/abc203/editorial/1964
// C++(GCC 9.2.1)
#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--)
int a[202020], f[202020], dp[202020][31];

int main(){
    
    // 1. 入力情報.
    int N, K;
    scanf("%d %d", &N, &K);
    rep(i, N) scanf("%d", &a[i + 1]);
    
    // 2. sort.
    sort(a, a + N + 1);
    
    // 3. f を 計算.
    int l = N, r = N;
    while(r){
        // 3-1. 判定.
        while(a[r] < 2 * a[l]) --l;
        
        // 3-2. 設定, および, デクリメント.
        f[r--] = l;
    }
    
    // 4. dp更新.
    repx(i, 1, N + 1) dp[i][0] = i;
    repx(i, 1, N + 1) repx(j, 1, 31) dp[i][j] = min(dp[i - 1][j] + 1, dp[f[i]][j - 1]);
    
    // 5. 操作回数を取得.
    int ans1 = 0, ans2 = 0;
    repr(j, 30, 0) if(dp[N][j] <= K) ans1 = j, ans2 = dp[N][j];
    
    // 6. 出力.
    printf("%d %d\n", ans1, ans2);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc203/editorial/1964

// C++(GCC 9.2.1)

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

int a[202020], f[202020], dp[202020][31];

int main(){

// 1. 入力情報.

int N, K;

scanf("%d %d", &N, &K);

rep(i, N) scanf("%d", &a[i + 1]);

// 2. sort.

sort(a, a + N + 1);

// 3. f を計算.

int l = N, r = N;

while(r){

// 3-1. 判定.

while(a[r] < 2 * a[l]) --l;

// 3-2. 設定, および, デクリメント.

f[r--] = l;

}

// 4. dp更新.

repx(i, 1, N + 1) dp[i][0] = i;

repx(i, 1, N + 1) repx(j, 1, 31) dp[i][j] = min(dp[i - 1][j] + 1, dp[f[i]][j - 1]);

// 5. 操作回数を取得.

int ans1 = 0, ans2 = 0;

repr(j, 30, 0) if(dp[N][j] <= K) ans1 = j, ans2 = dp[N][j];

// 6. 出力.

printf("%d %d\n", ans1, ans2);

return 0;

}

[入力例]
4 1
2 3 4 9

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

[入力例]
3 3
2 3 5

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

[入力例]
9 8
137 55 56 60 27 28 133 56 55

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

[入力例]
30 8
51 104 6 87 96 44 90 11 9 90 82 50 98 52 105 44 63 92 99 37 92 33 32 73 72 57 41 102 109 96

[出力例]
2 3

[入力例]
50 10
348 207 216 593 462 219 37 612 36 1191 149 496 1042 259 452 206 529 70 52 540 418 63 709 917 915 466 265 21 32 824 228 705 1129 835 101 59 1020 1087 300 431 1049 1153 1119 678 1069 839 1175 258 148 833

[出力例]
3 9

[入力例]

4 1

2 3 4 9

[出力例]

2 1

※AtCoderテストケースより

[入力例]

3 3

2 3 5

[出力例]

0 3

※AtCoderテストケースより

[入力例]

9 8

137 55 56 60 27 28 133 56 55

[出力例]

1 4

※AtCoderテストケースより

[入力例]

30 8

51 104 6 87 96 44 90 11 9 90 82 50 98 52 105 44 63 92 99 37 92 33 32 73 72 57 41 102 109 96

[出力例]

2 3

[入力例]

50 10

348 207 216 593 462 219 37 612 36 1191 149 496 1042 259 452 206 529 70 52 540 418 63 709 917 915 466 265 21 32 824 228 705 1129 835 101 59 1020 1087 300 431 1049 1153 1119 678 1069 839 1175 258 148 833

[出力例]

3 9

■参照サイト
AtCoder Beginner Contest 203（Sponsored by Panasonic）

2021年6月5日

C++ の動作確認をしてみた（４７５）

C++の練習を兼ねて, AtCoder Beginner Contest 203 の問題E (White Pawn) を解いてみた.

■感想.
1. 問題Eは, 方針が見えなかったので, 解説を参考にして, ようやく, AC版に到達出来た.
2. 集合操作について, 実装方法によっては, TLE版となってしまうので, 非常に勉強になったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/abc203/editorial/1962
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;
using vp = vector<P>;
#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 a first
#define b second
#define pb push_back
#define all(x) x.begin(), x.end()

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    vp v;
    rep(i, M){
        int x, y;
        scanf("%d %d", &x, &y);
        v.pb({x, y});
    }
    v.pb({2 * N + 1, 2 * N + 1}); // 番兵.
    
    // 2. sort.
    sort(all(v));
    
    // 3. 到達可能な場所は？(解説通り).
    set<int> st, a, b;
    st.insert(N);
    int xBef = -1, xCur, yCur;
    rep(i, M + 1){
        // 3-1. 今回分更新.
        xCur = v[i].a;
        yCur = v[i].b;
        
        // 3-2. 到達可能な場所(集合)を更新.
        if(xBef != -1 && xBef != xCur){
            // set<int> ret;
            // set_difference(all(st), all(b), inserter(ret, ret.end()));
            // swap(st, ret);
            // st.merge(a);
            
            // TLE防止.
            // -> extreme_00.txt などで, TLE版となるので, ロジック修正(仮).
            for(auto &p : a) st.insert(p);
            for(auto &p : b) st.erase(p);
            a.clear();
            b.clear();
        }
        
        // 3-3. 集合 A に追加する場合.
        if(st.count(yCur - 1) || st.count(yCur + 1)){
            if(!st.count(yCur)) a.insert(yCur);
        }
        
        // 3-4. 集合 B に追加する場合.
        if(!st.count(yCur - 1) && !st.count(yCur + 1)){
            if(st.count(yCur)) b.insert(yCur);
        }
        
        // 3-5. 前回分更新.
        xBef = xCur;
    }
    
    // 4. 出力.
    printf("%d\n", st.size());
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc203/editorial/1962

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using P = pair<int, int>;

using vp = vector;

#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 a first

#define b second

#define pb push_back

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

int main(){

// 1. 入力情報.

int N, M;

scanf("%d %d", &N, &M);

vp v;

rep(i, M){

int x, y;

scanf("%d %d", &x, &y);

v.pb({x, y});

}

v.pb({2 * N + 1, 2 * N + 1}); // 番兵.

// 2. sort.

sort(all(v));

// 3. 到達可能な場所は？(解説通り).

set<int> st, a, b;

st.insert(N);

int xBef = -1, xCur, yCur;

rep(i, M + 1){

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

xCur = v[i].a;

yCur = v[i].b;

// 3-2. 到達可能な場所(集合)を更新.

if(xBef != -1 && xBef != xCur){

// set<int> ret;

// set_difference(all(st), all(b), inserter(ret, ret.end()));

// swap(st, ret);

// st.merge(a);

// TLE防止.

// -> extreme_00.txt などで, TLE版となるので, ロジック修正(仮).

for(auto &p : a) st.insert(p);

for(auto &p : b) st.erase(p);

a.clear();

b.clear();

}

// 3-3. 集合 A に追加する場合.

if(st.count(yCur - 1) || st.count(yCur + 1)){

if(!st.count(yCur)) a.insert(yCur);

}

// 3-4. 集合 B に追加する場合.

if(!st.count(yCur - 1) && !st.count(yCur + 1)){

if(st.count(yCur)) b.insert(yCur);

}

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

xBef = xCur;

}

// 4. 出力.

printf("%d\n", st.size());

return 0;

}

[入力例]
2 4
1 1
1 2
2 0
4 2

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

[入力例]
1 1
1 1

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

[入力例]
5 7
1 4
3 8
2 3
1 6
4 3
5 7
6 9

[出力例]
5

[入力例]
7 18
10 11
6 13
2 5
8 12
7 4
2 8
13 13
4 10
5 3
6 9
11 1
7 2
8 6
1 6
8 10
4 12
12 11
3 4

[出力例]
11

[入力例]

2 4

1 1

1 2

2 0

4 2

[出力例]

※AtCoderテストケースより

[入力例]

1 1

[出力例]

※AtCoderテストケースより

[入力例]

5 7

1 4

3 8

2 3

1 6

4 3

5 7

6 9

[出力例]

[入力例]

7 18

10 11

6 13

2 5

8 12

7 4

2 8

13 13

4 10

5 3

6 9

11 1

7 2

8 6

1 6

8 10

4 12

12 11

3 4

[出力例]

■参照サイト
AtCoder Beginner Contest 203（Sponsored by Panasonic）

2021年6月4日2021年6月4日

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

C++の練習を兼ねて, AtCoder Beginner Contest 203 の問題C (Friends and Travel costs) ～問題D (Pond) を解いてみた.

■感想.
1. 問題Dは, 方針が見えなかったので, 解説を参考にして, ようやく, AC版に到達出来た.
2. 二分探索の復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using P = pair<LL, LL>;
using vp = vector<P>;
#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 a first
#define b second
#define all(x) x.begin(), x.end()

int main(){
    
    // 1. 入力情報.
    int N;
    LL K;
    scanf("%d %lld", &N, &K);
    vp v;
    rep(i, N){
        LL a, b;
        scanf("%lld %lld", &a, &b);
        P p;
        p.a = a;
        p.b = b;
        v.pb(p);
    }
    
    // 2. sort.
    sort(all(v));
    
    // 3. 最終的に, たどり着く予定の村を計算.
    LL cur = 0, bef = 0;
    rep(i, N){
        // 所持金を補充できる村まで到達できる場合.
        if(K >= (v[i].a - bef)){
            cur = v[i].a;
            K -= (v[i].a - bef);
            K += v[i].b;
            bef = cur;
        }
    }
    
    // 4. 所持金が余っていた場合.
    cur += K;
    
    // 5. 出力.
    printf("%lld\n", cur);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using P = pair<LL, LL>;

using vp = vector;

#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 a first

#define b second

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

int main(){

// 1. 入力情報.

int N;

LL K;

scanf("%d %lld", &N, &K);

vp v;

rep(i, N){

LL a, b;

scanf("%lld %lld", &a, &b);

P p;

p.a = a;

p.b = b;

v.pb(p);

}

// 2. sort.

sort(all(v));

// 3. 最終的に, たどり着く予定の村を計算.

LL cur = 0, bef = 0;

rep(i, N){

// 所持金を補充できる村まで到達できる場合.

if(K >= (v[i].a - bef)){

cur = v[i].a;

K -= (v[i].a - bef);

K += v[i].b;

bef = cur;

}

// 4. 所持金が余っていた場合.

cur += K;

// 5. 出力.

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

return 0;

}

[入力例]
2 3
2 1
5 10

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

[入力例]
5 1000000000
1 1000000000
2 1000000000
3 1000000000
4 1000000000
5 1000000000

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

[入力例]
3 2
5 5
2 1
2 2

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

[入力例]
10 2
7 3
1 1
3 2
2 2
22 2
18 2
19 3
11 1
12 1
16 1

[出力例]
10

[入力例]
15 5
19 2
7 3
2 1
6 3
6 1
9 1
4 3
1 1
6 2
19 3
9 1
8 3
2 1
6 3
5 2

[出力例]
35

[入力例]
20 3
27 1
28 2
17 3
30 3
15 3
19 1
2 3
3 1
4 2
2 2
2 2
9 3
19 3
1 2
10 3
1 3
1 1
6 2
7 1
12 1

[出力例]
45

[入力例]

2 3

2 1

5 10

[出力例]

※AtCoderテストケースより

[入力例]

5 1000000000

1 1000000000

2 1000000000

3 1000000000

4 1000000000

5 1000000000

[出力例]

6000000000

※AtCoderテストケースより

[入力例]

3 2

5 5

2 1

2 2

[出力例]

※AtCoderテストケースより

[入力例]

10 2

7 3

1 1

3 2

2 2

22 2

18 2

19 3

11 1

12 1

16 1

[出力例]

[入力例]

15 5

19 2

7 3

2 1

6 3

6 1

9 1

4 3

1 1

6 2

19 3

9 1

8 3

2 1

6 3

5 2

[出力例]

[入力例]

20 3

27 1

28 2

17 3

30 3

15 3

19 1

2 3

3 1

4 2

2 2

9 3

19 3

1 2

10 3

1 3

1 1

6 2

7 1

12 1

[出力例]

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

// 解き直し.
// https://atcoder.jp/contests/abc203/editorial/1955
// C++(GCC 9.2.1)
#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--)
int a[808][808];

int main(){
    
    // 1. 入力情報.
    int N, K, maxA = 0;
    scanf("%d %d", &N, &K);
    rep(i, N){
        rep(j, N){
            scanf("%d", &a[i][j]);
            maxA = max(maxA, a[i][j]);
        }
    }
    
    // 2. 評価関数.
    auto f = [&](int x) -> bool {
        // 2-1. 二次元累積和
        int S[808][808];
        rep(i, 808) rep(j, 808) S[i][j] = 0;
        repx(i, 1, N + 1){
            repx(j, 1, N + 1){
                S[i][j] = S[i - 1][j] + S[i][j - 1] - S[i - 1][j - 1] + (a[i - 1][j - 1] > x);
            }
        }
        
        // 2-2. 中央値 を 評価.
        bool ok = false;
        int mIndex = K * K / 2 + 1;
        repx(i, K, N + 1){
            repx(j, K, N + 1){
                int y = S[i][j] - S[i - K][j] - S[i][j - K] + S[i - K][j - K];
                if(y < mIndex){
                    ok = true;
                    break;
                }
            }
            if(ok) break;
        }
        return ok;
    };
    
    // 3. 二分探索で確認してみる.
    int l = -1, h = maxA, m;
    while(l + 1 < h){
        m = (h + l) >> 1;
        if(f(m)) h = m;
        else     l = m;
        // printf("h=%d l=%d m=%d\n", h, l, m);
    }
    
    // 4. 出力.
    printf("%d\n", h);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc203/editorial/1955

// C++(GCC 9.2.1)

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

int a[808][808];

int main(){

// 1. 入力情報.

int N, K, maxA = 0;

scanf("%d %d", &N, &K);

rep(i, N){

rep(j, N){

scanf("%d", &a[i][j]);

maxA = max(maxA, a[i][j]);

}

// 2. 評価関数.

auto f = [&](int x) -> bool {

// 2-1. 二次元累積和

int S[808][808];

rep(i, 808) rep(j, 808) S[i][j] = 0;

repx(i, 1, N + 1){

repx(j, 1, N + 1){

S[i][j] = S[i - 1][j] + S[i][j - 1] - S[i - 1][j - 1] + (a[i - 1][j - 1] > x);

}

// 2-2. 中央値を評価.

bool ok = false;

int mIndex = K * K / 2 + 1;

repx(i, K, N + 1){

repx(j, K, N + 1){

int y = S[i][j] - S[i - K][j] - S[i][j - K] + S[i - K][j - K];

if(y < mIndex){

ok = true;

break;

}

if(ok) break;

}

return ok;

};

// 3. 二分探索で確認してみる.

int l = -1, h = maxA, m;

while(l + 1 < h){

m = (h + l) >> 1;

if(f(m)) h = m;

else l = m;

// printf("h=%d l=%d m=%d\n", h, l, m);

}

// 4. 出力.

printf("%d\n", h);

return 0;

}

[入力例]
3 2
1 7 0
5 8 11
10 4 2

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

[入力例]
3 3
1 2 3
4 5 6
7 8 9

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

[入力例]
5 3
1 7 0 2 0
5 8 11 5 3
7 4 2 0 9
10 4 2 11 6
10 11 2 10 5

[出力例]
2

[入力例]
9 3
28 10 6 18 23 17 1 4 21
20 27 9 27 5 2 17 21 13
29 19 6 28 5 13 12 1 21
18 1 20 1 0 8 23 19 9
24 6 25 27 15 13 27 1 22
28 29 5 27 12 10 15 24 26
8 13 25 15 9 24 14 1 28
22 5 29 0 22 18 6 24 16
28 10 0 1 22 22 26 20 29

[出力例]
5

[入力例]
32 7
65 302 174 805 691 317 96 25 215 498 476 740 428 319 304 583 91 880 727 872 647 895 475 158 211 182 905 227 752 240 996 219
713 461 72 587 322 269 777 242 43 811 571 80 432 403 893 60 901 129 704 450 40 905 98 695 966 712 406 711 235 673 901 176
202 160 672 710 118 466 519 921 940 493 276 128 710 846 113 908 602 947 677 641 383 891 96 776 887 793 709 299 344 249 865 43
924 751 512 221 577 759 440 275 600 377 528 469 23 770 431 278 442 682 195 686 503 987 469 983 407 568 321 319 215 745 568 63
63 467 425 770 245 66 673 700 783 303 153 174 965 539 722 101 509 223 933 944 335 736 230 837 574 368 402 429 510 225 16 143
113 422 610 116 934 492 862 97 711 91 714 126 511 87 972 793 758 433 660 950 569 634 267 387 850 38 773 119 734 111 922 802
359 953 720 953 44 306 414 185 346 383 362 105 854 796 192 575 819 165 910 645 712 650 38 587 51 109 246 824 279 438 478 99
652 895 50 338 555 182 129 237 28 730 932 921 400 74 8 6 336 900 665 701 772 835 723 537 682 480 999 730 322 278 868 644
285 896 25 60 819 992 126 436 642 0 174 242 82 465 194 56 975 81 404 423 678 742 321 810 822 161 261 119 228 794 27 298
367 340 310 485 971 822 333 311 813 847 222 980 411 406 771 437 336 889 82 853 525 695 26 922 348 46 725 319 500 705 154 69
519 648 111 459 157 886 302 638 932 965 996 557 769 494 667 238 53 549 121 447 738 393 467 536 431 87 791 970 959 273 943 914
486 523 189 465 197 493 534 944 7 551 366 766 102 764 742 353 383 71 846 532 117 251 88 433 344 704 781 579 44 403 661 844
694 330 542 890 50 120 701 540 339 396 175 587 408 22 174 866 963 940 426 84 336 683 306 224 771 841 383 283 896 434 473 888
556 129 36 563 276 646 569 756 238 799 960 568 829 443 191 463 639 622 869 492 877 255 489 758 960 188 295 906 334 274 872 456
684 368 731 801 969 572 642 321 317 468 550 251 961 158 149 369 341 389 653 863 827 596 63 239 711 334 118 80 226 857 578 974
275 997 1 107 368 690 108 578 881 136 57 807 480 194 399 104 418 335 305 897 123 920 673 198 75 600 370 91 49 874 951 872
762 924 600 634 906 160 901 212 238 653 252 607 294 320 883 994 45 823 738 786 873 465 425 295 10 289 896 279 547 831 272 202
66 829 570 733 809 686 351 501 619 39 42 176 994 552 676 103 606 409 75 729 921 650 875 454 526 627 541 806 725 166 689 733
770 876 801 767 80 742 343 19 556 2 545 975 125 508 361 99 605 192 271 762 500 924 431 988 277 110 193 668 628 429 553 408
355 715 414 350 479 612 548 346 788 892 447 435 652 329 173 950 342 811 137 870 10 215 345 439 383 341 792 197 413 76 833 841
966 118 32 947 78 568 893 863 577 91 602 31 303 24 187 783 479 698 849 850 246 907 483 107 427 430 737 744 231 681 566 43
780 62 362 651 869 226 141 809 57 796 289 954 498 440 227 279 352 986 585 977 154 874 148 24 225 236 794 701 441 27 209 186
309 37 903 877 970 58 542 8 718 568 78 339 816 984 612 164 481 908 902 945 728 533 70 296 346 503 751 446 473 645 339 130
781 672 847 416 578 690 56 622 124 126 883 255 970 274 144 379 12 676 724 181 845 792 376 319 171 545 653 662 117 24 409 594
779 336 932 512 5 610 876 130 564 691 354 711 211 990 99 10 377 364 26 102 153 437 982 686 769 609 813 502 708 520 929 101
367 377 544 637 268 131 584 257 631 171 592 584 214 391 254 562 62 142 220 375 81 945 746 863 206 194 615 954 202 62 480 45
226 276 237 377 261 506 842 292 323 406 638 258 492 498 136 104 15 486 941 476 615 8 805 250 409 538 762 89 591 897 690 751
937 512 882 870 471 934 166 736 555 38 66 455 284 776 676 516 887 431 745 865 701 629 755 247 796 143 261 546 467 353 3 963
504 692 639 704 604 279 945 283 607 279 304 532 5 323 403 893 901 0 636 667 487 346 128 934 417 56 394 139 736 771 231 6
735 469 202 300 347 871 705 709 979 688 573 817 104 358 107 707 798 617 352 292 245 179 950 711 497 949 62 903 852 318 244 247
457 217 444 501 678 449 567 184 476 697 261 689 669 256 665 304 214 927 946 611 619 625 627 921 346 76 962 875 334 319 247 91
922 275 258 425 867 257 817 55 793 666 438 806 68 191 567 702 15 833 294 369 592 762 563 471 449 748 940 948 97 795 401 779

[出力例]
321

[入力例]

3 2

1 7 0

5 8 11

10 4 2

[出力例]

※AtCoderテストケースより

[入力例]

3 3

1 2 3

4 5 6

7 8 9

[出力例]

※AtCoderテストケースより

[入力例]

5 3

1 7 0 2 0

5 8 11 5 3

7 4 2 0 9

10 4 2 11 6

10 11 2 10 5

[出力例]

[入力例]

9 3

28 10 6 18 23 17 1 4 21

20 27 9 27 5 2 17 21 13

29 19 6 28 5 13 12 1 21

18 1 20 1 0 8 23 19 9

24 6 25 27 15 13 27 1 22

28 29 5 27 12 10 15 24 26

8 13 25 15 9 24 14 1 28

22 5 29 0 22 18 6 24 16

28 10 0 1 22 22 26 20 29

[出力例]

[入力例]

32 7

65 302 174 805 691 317 96 25 215 498 476 740 428 319 304 583 91 880 727 872 647 895 475 158 211 182 905 227 752 240 996 219

713 461 72 587 322 269 777 242 43 811 571 80 432 403 893 60 901 129 704 450 40 905 98 695 966 712 406 711 235 673 901 176

202 160 672 710 118 466 519 921 940 493 276 128 710 846 113 908 602 947 677 641 383 891 96 776 887 793 709 299 344 249 865 43

924 751 512 221 577 759 440 275 600 377 528 469 23 770 431 278 442 682 195 686 503 987 469 983 407 568 321 319 215 745 568 63

63 467 425 770 245 66 673 700 783 303 153 174 965 539 722 101 509 223 933 944 335 736 230 837 574 368 402 429 510 225 16 143

113 422 610 116 934 492 862 97 711 91 714 126 511 87 972 793 758 433 660 950 569 634 267 387 850 38 773 119 734 111 922 802

359 953 720 953 44 306 414 185 346 383 362 105 854 796 192 575 819 165 910 645 712 650 38 587 51 109 246 824 279 438 478 99

652 895 50 338 555 182 129 237 28 730 932 921 400 74 8 6 336 900 665 701 772 835 723 537 682 480 999 730 322 278 868 644

285 896 25 60 819 992 126 436 642 0 174 242 82 465 194 56 975 81 404 423 678 742 321 810 822 161 261 119 228 794 27 298

367 340 310 485 971 822 333 311 813 847 222 980 411 406 771 437 336 889 82 853 525 695 26 922 348 46 725 319 500 705 154 69

519 648 111 459 157 886 302 638 932 965 996 557 769 494 667 238 53 549 121 447 738 393 467 536 431 87 791 970 959 273 943 914

486 523 189 465 197 493 534 944 7 551 366 766 102 764 742 353 383 71 846 532 117 251 88 433 344 704 781 579 44 403 661 844

694 330 542 890 50 120 701 540 339 396 175 587 408 22 174 866 963 940 426 84 336 683 306 224 771 841 383 283 896 434 473 888

556 129 36 563 276 646 569 756 238 799 960 568 829 443 191 463 639 622 869 492 877 255 489 758 960 188 295 906 334 274 872 456

684 368 731 801 969 572 642 321 317 468 550 251 961 158 149 369 341 389 653 863 827 596 63 239 711 334 118 80 226 857 578 974

275 997 1 107 368 690 108 578 881 136 57 807 480 194 399 104 418 335 305 897 123 920 673 198 75 600 370 91 49 874 951 872

762 924 600 634 906 160 901 212 238 653 252 607 294 320 883 994 45 823 738 786 873 465 425 295 10 289 896 279 547 831 272 202

66 829 570 733 809 686 351 501 619 39 42 176 994 552 676 103 606 409 75 729 921 650 875 454 526 627 541 806 725 166 689 733

770 876 801 767 80 742 343 19 556 2 545 975 125 508 361 99 605 192 271 762 500 924 431 988 277 110 193 668 628 429 553 408

355 715 414 350 479 612 548 346 788 892 447 435 652 329 173 950 342 811 137 870 10 215 345 439 383 341 792 197 413 76 833 841

966 118 32 947 78 568 893 863 577 91 602 31 303 24 187 783 479 698 849 850 246 907 483 107 427 430 737 744 231 681 566 43

780 62 362 651 869 226 141 809 57 796 289 954 498 440 227 279 352 986 585 977 154 874 148 24 225 236 794 701 441 27 209 186

309 37 903 877 970 58 542 8 718 568 78 339 816 984 612 164 481 908 902 945 728 533 70 296 346 503 751 446 473 645 339 130

781 672 847 416 578 690 56 622 124 126 883 255 970 274 144 379 12 676 724 181 845 792 376 319 171 545 653 662 117 24 409 594

779 336 932 512 5 610 876 130 564 691 354 711 211 990 99 10 377 364 26 102 153 437 982 686 769 609 813 502 708 520 929 101

367 377 544 637 268 131 584 257 631 171 592 584 214 391 254 562 62 142 220 375 81 945 746 863 206 194 615 954 202 62 480 45

226 276 237 377 261 506 842 292 323 406 638 258 492 498 136 104 15 486 941 476 615 8 805 250 409 538 762 89 591 897 690 751

937 512 882 870 471 934 166 736 555 38 66 455 284 776 676 516 887 431 745 865 701 629 755 247 796 143 261 546 467 353 3 963

504 692 639 704 604 279 945 283 607 279 304 532 5 323 403 893 901 0 636 667 487 346 128 934 417 56 394 139 736 771 231 6

735 469 202 300 347 871 705 709 979 688 573 817 104 358 107 707 798 617 352 292 245 179 950 711 497 949 62 903 852 318 244 247

457 217 444 501 678 449 567 184 476 697 261 689 669 256 665 304 214 927 946 611 619 625 627 921 346 76 962 875 334 319 247 91

922 275 258 425 867 257 817 55 793 666 438 806 68 191 567 702 15 833 294 369 592 762 563 471 449 748 940 948 97 795 401 779

[出力例]

321

■参照サイト
AtCoder Beginner Contest 203（Sponsored by Panasonic）

2021年6月1日

C++ の動作確認をしてみた（４７３）

C++の練習を兼ねて, AtCoder Beginner Contest 201 の問題E (Xor Distances) を解いてみた.

■感想.
1. 問題Eは, 方針が見えなかったので, 解説を参考にして, ようやく, AC版に到達出来た.
2. 実装に非常に苦労したものの, XOR計算, および, 幅優先探索を復習することが出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/abc201/editorial/1827
// C++(GCC 9.2.1)
#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 MOD = 1e9 + 7;

struct edge{
    int t; // 次の頂点.
    LL c;  // コスト.
};

vector<edge> G[202020];
LL d[202020];
LL xDist[66][2];  // kビット目が, 0, 1 である頂点の個数を保存.
int memo[202020]; // 訪問済みフラグ.

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N - 1){
        int u, v;
        LL w;
        scanf("%d %d %lld", &u, &v, &w);
        u--, v--;
        
        edge e;
        e.t = v;
        e.c = w;
        G[u].pb(e);
        
        e.t = u;
        e.c = w;
        G[v].pb(e);
    }
    
    // 2. 頂点 1 から 各頂点までの距離を計算.
    // https://ja.wikipedia.org/wiki/幅優先探索
    auto bfs = [&](int s){
        // 2-1. 空のキュー.
        queue<int> q;
        
        // 2-2. 探索地点 s をキュー q に追加.
        q.push(s);
        while(!q.empty()){
            // 2-3. キューから取り出す.
            int u = q.front();
            q.pop();
            
            // 2-4. 取り出した要素を処理.
            for(auto &e : G[u]){
                // 2-5. XORを計算.
                if(!memo[e.t] && e.t != s){
                    d[e.t] = d[u] ^ e.c;
                    memo[e.t] = memo[u] + 1;
                    q.push(e.t);
                }
            }
        }
        return;
    };
    bfs(0);
    
    // 3. 2 の 冪乗 を 保存(通常版, MOD版).
    vl cPow2, mPow2;
    int count = 0;
    cPow2.pb(1);
    mPow2.pb(1);
    while(count < 61){
        // 通常版.
        LL p = 2 * cPow2.back();
        cPow2.pb(p);
        
        // MOD版.
        LL q = 2 * mPow2.back();
        q %= MOD;
        mPow2.pb(q);
        
        // インクリメント.
        count++;
    }
    
    // 4. 各ビットに関して, 0, 1 となる頂点の個数を保存.
    rep(i, N){
        rep(j, 61){
            if(d[i] & cPow2[j]) xDist[j][1]++;
            else                xDist[j][0]++;
        }
    }
    
    // 5. 集計.
    LL ans = 0;
    rep(i, 61){
        ans += (xDist[i][0] * xDist[i][1]) % MOD * mPow2[i] % MOD;
        ans %= MOD;
    }
    
    // 6. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

110

111

// 解き直し.

// https://atcoder.jp/contests/abc201/editorial/1827

// C++(GCC 9.2.1)

#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 MOD = 1e9 + 7;

struct edge{

int t; // 次の頂点.

LL c; // コスト.

};

vector<edge> G[202020];

LL d[202020];

LL xDist[66][2]; // kビット目が, 0, 1 である頂点の個数を保存.

int memo[202020]; // 訪問済みフラグ.

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

rep(i, N - 1){

int u, v;

LL w;

scanf("%d %d %lld", &u, &v, &w);

u--, v--;

edge e;

e.t = v;

e.c = w;

G[u].pb(e);

e.t = u;

e.c = w;

G[v].pb(e);

}

// 2. 頂点 1 から各頂点までの距離を計算.

// https://ja.wikipedia.org/wiki/幅優先探索

auto bfs = [&](int s){

// 2-1. 空のキュー.

queue<int> q;

// 2-2. 探索地点 s をキュー q に追加.

q.push(s);

while(!q.empty()){

// 2-3. キューから取り出す.

int u = q.front();

q.pop();

// 2-4. 取り出した要素を処理.

for(auto &e : G[u]){

// 2-5. XORを計算.

if(!memo[e.t] && e.t != s){

d[e.t] = d[u] ^ e.c;

memo[e.t] = memo[u] + 1;

q.push(e.t);

}

return;

};

bfs(0);

// 3. 2 の冪乗を保存(通常版, MOD版).

vl cPow2, mPow2;

int count = 0;

cPow2.pb(1);

mPow2.pb(1);

while(count < 61){

// 通常版.

LL p = 2 * cPow2.back();

cPow2.pb(p);

// MOD版.

LL q = 2 * mPow2.back();

q %= MOD;

mPow2.pb(q);

// インクリメント.

count++;

}

// 4. 各ビットに関して, 0, 1 となる頂点の個数を保存.

rep(i, N){

rep(j, 61){

if(d[i] & cPow2[j]) xDist[j][1]++;

else xDist[j][0]++;

}

// 5. 集計.

LL ans = 0;

rep(i, 61){

ans += (xDist[i][0] * xDist[i][1]) % MOD * mPow2[i] % MOD;

ans %= MOD;

}

// 6. 出力.

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

return 0;

}

[入力例]
3
1 2 1
1 3 3

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

[入力例]
5
3 5 2
2 3 2
1 5 1
4 5 13

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

[入力例]
10
5 7 459221860242673109
6 8 248001948488076933
3 5 371922579800289138
2 5 773108338386747788
6 10 181747352791505823
1 3 803225386673329326
7 8 139939802736535485
9 10 657980865814127926
2 4 146378247587539124

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

[入力例]
15
1 2 66
1 3 56
1 14 116
2 13 38
2 7 35
3 8 62
3 4 119
3 5 100
8 11 61
8 12 24
12 15 98
5 6 51
6 10 17
6 9 33

[出力例]
6676

[入力例]
30
1 2 35602115828
1 3 22757985030
12 1 57881173395
3 23 31451467027
2 4 71178814495
2 5 70797358384
4 13 16378852590
4 14 11561949674
14 15 82226686406
15 24 18199117551
15 25 89529557518
15 26 40691756988
3 6 89216868118
3 7 35330113570
6 17 50417795719
6 16 41609715734
7 11 62551724670
7 8 12021988188
11 20 9352400257
11 21 26634079489
11 22 9183357474
8 9 48768608557
8 10 61676251453
10 18 96417487449
10 19 4131160740
18 29 90504109457
18 30 78998085309
19 27 82962407376
19 28 8006021346

[出力例]
134435348

[入力例]

1 2 1

1 3 3

[出力例]

※AtCoderテストケースより

[入力例]

3 5 2

2 3 2

1 5 1

4 5 13

[出力例]

※AtCoderテストケースより

[入力例]

5 7 459221860242673109

6 8 248001948488076933

3 5 371922579800289138

2 5 773108338386747788

6 10 181747352791505823

1 3 803225386673329326

7 8 139939802736535485

9 10 657980865814127926

2 4 146378247587539124

[出力例]

241240228

※AtCoderテストケースより

[入力例]

1 2 66

1 3 56

1 14 116

2 13 38

2 7 35

3 8 62

3 4 119

3 5 100

8 11 61

8 12 24

12 15 98

5 6 51

6 10 17

6 9 33

[出力例]

6676

[入力例]

1 2 35602115828

1 3 22757985030

12 1 57881173395

3 23 31451467027

2 4 71178814495

2 5 70797358384

4 13 16378852590

4 14 11561949674

14 15 82226686406

15 24 18199117551

15 25 89529557518

15 26 40691756988

3 6 89216868118

3 7 35330113570

6 17 50417795719

6 16 41609715734

7 11 62551724670

7 8 12021988188

11 20 9352400257

11 21 26634079489

11 22 9183357474

8 9 48768608557

8 10 61676251453

10 18 96417487449

10 19 4131160740

18 29 90504109457

18 30 78998085309

19 27 82962407376

19 28 8006021346

[出力例]

134435348

■参照サイト
マイナビプログラミングコンテスト2021（AtCoder Beginner Contest 201）

2021年5月30日

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

C++の練習を兼ねて, AtCoder Regular Contest 121 の問題A (2nd Greatest Distance) ～問題B (RGB Matching) を解いてみた.

■感想.
1. 問題Bは, 方針が見えなかったので, 解説を参考にして, ようやく, AC版に到達出来た.
2. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;
using vp = vector<P>;
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 a first
#define b second
#define all(x) x.begin(), x.end()
int ox[202020], oy[202020];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    vp px, py;
    rep(i, N){
        int x, y;
        scanf("%d %d", &x, &y);
        // 平行移動.
        x += 1e9;
        y += 1e9;
        
        // オリジナル座標を保存.
        ox[i] = x;
        oy[i] = y;
        
        // {x, i} を 保存.
        px.pb({x, i});
        
        // {y, i} を 保存.
        py.pb({y, i});
    }
    
    // 2. sort.
    sort(all(px));
    sort(all(py));
    
    // 3. チェビシェフ距離を保存.
    // -> hand_01.txt で, WA版となったので修正.
    vi ans;
    set<P> st; // インデックスが出現済かのチェック.
    // 3-1. X成分について, 最大四通り保存.
    for(auto &i : {N - 1, N - 2}){
        for(auto &j : {0, 1}){
            if(!st.count({px[i].b, px[j].b}) || !st.count({px[j].b, px[i].b})){
                st.insert({px[i].b, px[j].b});
                st.insert({px[j].b, px[i].b});
                ans.pb(max(px[i].a - px[j].a, abs(oy[px[i].b] - oy[px[j].b])));
            }
        }
    }
    
    // 3-2. Y成分について, 最大四通り保存.
    for(auto &i : {N - 1, N - 2}){
        for(auto &j : {0, 1}){
            if(!st.count({py[i].b, py[j].b}) || !st.count({py[j].b, py[i].b})){
                st.insert({py[i].b, py[j].b});
                st.insert({py[j].b, py[i].b});
                ans.pb(max(py[i].a - py[j].a, abs(ox[py[i].b] - ox[py[j].b])));
            }
        }
    }
    
    // 4. sort.
    sort(all(ans));
    reverse(all(ans));
    
    // 5. 出力.
    printf("%d\n", ans[1]);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using P = pair<int, int>;

using vp = vector;

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 a first

#define b second

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

int ox[202020], oy[202020];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

vp px, py;

rep(i, N){

int x, y;

scanf("%d %d", &x, &y);

// 平行移動.

x += 1e9;

y += 1e9;

// オリジナル座標を保存.

ox[i] = x;

oy[i] = y;

// {x, i} を保存.

px.pb({x, i});

// {y, i} を保存.

py.pb({y, i});

}

// 2. sort.

sort(all(px));

sort(all(py));

// 3. チェビシェフ距離を保存.

// -> hand_01.txt で, WA版となったので修正.

vi ans;

set st; // インデックスが出現済かのチェック.

// 3-1. X成分について, 最大四通り保存.

for(auto &i : {N - 1, N - 2}){

for(auto &j : {0, 1}){

if(!st.count({px[i].b, px[j].b}) || !st.count({px[j].b, px[i].b})){

st.insert({px[i].b, px[j].b});

st.insert({px[j].b, px[i].b});

ans.pb(max(px[i].a - px[j].a, abs(oy[px[i].b] - oy[px[j].b])));

}

// 3-2. Y成分について, 最大四通り保存.

for(auto &i : {N - 1, N - 2}){

for(auto &j : {0, 1}){

if(!st.count({py[i].b, py[j].b}) || !st.count({py[j].b, py[i].b})){

st.insert({py[i].b, py[j].b});

st.insert({py[j].b, py[i].b});

ans.pb(max(py[i].a - py[j].a, abs(ox[py[i].b] - ox[py[j].b])));

}

// 4. sort.

sort(all(ans));

reverse(all(ans));

// 5. 出力.

printf("%d\n", ans[1]);

return 0;

}

[入力例]
3
0 0
1 2
4 0

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

[入力例]
4
0 0
0 0
1 0
0 1

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

[入力例]
20
407 361
167 433
756 388
-551 -47
306 -471
36 928
338 -355
911 852
288 70
-961 -769
-668 -386
-690 -378
182 -609
-677 401
-458 -112
184 -131
-243 888
-163 471
-11 997
119 544

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

[入力例]
5
222 555
111 222
-222 333
333 -111
-555 -222

[出力例]
777

[入力例]
7
-1 1
-2 2
-3 3
-4 4
-5 5
-6 6
-7 7

[出力例]
5

[入力例]
5
-1 -1
2 2
3 3
4 4
5 5

[出力例]
5

[入力例]
60
72 36
59 93
14 60
31 23
35 43
80 68
70 22
33 90
39 -39
80 -39
40 10
91 25
9 49
99 -11
18 35
-44 -12
3 63
-53 61
98 40
36 -24
45 33
-44 71
38 70
62 79
62 51
-44 20
34 66
79 52
90 74
76 54
30 69
9 42
92 59
75 71
58 -1
7 85
66 46
-53 59
22 43
58 86
22 29
5 -37
43 48
65 50
61 25
11 20
16 21
84 77
43 50
56 82
47 88
40 86
45 74
75 26
31 59
48 48
25 44
24 30
3 12
22 44

[出力例]
152

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

[入力例]

0 0

1 2

4 0

[出力例]

※AtCoderのテストケースより

[入力例]

0 0

1 0

0 1

[出力例]

※AtCoderのテストケースより

[入力例]

407 361

167 433

756 388

-551 -47

306 -471

36 928

338 -355

911 852

288 70

-961 -769

-668 -386

-690 -378

182 -609

-677 401

-458 -112

184 -131

-243 888

-163 471

-11 997

119 544

[出力例]

1766

※AtCoderのテストケースより

[入力例]

222 555

111 222

-222 333

333 -111

-555 -222

[出力例]

777

[入力例]

-1 1

-2 2

-3 3

-4 4

-5 5

-6 6

-7 7

[出力例]

[入力例]

-1 -1

2 2

3 3

4 4

5 5

[出力例]

[入力例]

72 36

59 93

14 60

31 23

35 43

80 68

70 22

33 90

39 -39

80 -39

40 10

91 25

9 49

99 -11

18 35

-44 -12

3 63

-53 61

98 40

36 -24

45 33

-44 71

38 70

62 79

62 51

-44 20

34 66

79 52

90 74

76 54

30 69

9 42

92 59

75 71

58 -1

7 85

66 46

-53 59

22 43

58 86

22 29

5 -37

43 48

65 50

61 25

11 20

16 21

84 77

43 50

56 82

47 88

40 86

45 74

75 26

31 59

48 48

25 44

24 30

3 12

22 44

[出力例]

152

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

// 解き直し.
// https://atcoder.jp/contests/arc121/editorial/1927
// C++(GCC 9.2.1)
#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
#define all(x) x.begin(), x.end()

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    vl r, g, b;
    rep(i, N * 2){
        LL x;
        char c[11];
        scanf("%lld %s", &x, c);
        if(c[0] == 'R') r.pb(x);
        if(c[0] == 'G') g.pb(x);
        if(c[0] == 'B') b.pb(x);
    }
    
    // 2. 出現回数が, すべて偶数だった場合.
    int lr = r.size(), lg = g.size(), lb = b.size();
    bool fr = (lr & 1), fg = (lg & 1), fb = (lb & 1);
    if(!fr && !fg && !fb){
        puts("0");
        return 0;
    }
    
    // 3. sort.
    sort(all(r));
    sort(all(g));
    sort(all(b));
    
    // 4. 二色間の不満の最小値を計算.
    // 4-1. (赤, 緑).
    LL rg = 202020202020202020;
    rep(i, lr){
        int at = lower_bound(all(g), r[i]) - g.begin();
        if(at)      rg = min(rg, abs(r[i] - g[at - 1]));
        if(at < lg) rg = min(rg, abs(r[i] - g[at]));
    }
    
    // 4-2. (緑, 青).
    LL gb = 202020202020202020;
    rep(i, lg){
        int at = lower_bound(all(b), g[i]) - b.begin();
        if(at)      gb = min(gb, abs(g[i] - b[at - 1]));
        if(at < lb) gb = min(gb, abs(g[i] - b[at]));
    }
    
    // 4-3. (青, 赤).
    LL br = 202020202020202020;
    rep(i, lb){
        int at = lower_bound(all(r), b[i]) - r.begin();
        if(at)      br = min(br, abs(b[i] - r[at - 1]));
        if(at < lr) br = min(br, abs(b[i] - r[at]));
    }
    
    // 5. 不満の総和(最小値)を計算.
    LL ans = 0;
    // 5-1. (R, G, B) = (奇, 奇, 偶).
    if(fr && fg && !fb) ans = min(rg, gb + br);
    
    // 5-2. (R, G, B) = (奇, 偶, 奇).
    if(fr && !fg && fb) ans = min(br, rg + gb);
    
    // 5-3. (R, G, B) = (偶, 奇, 奇).
    if(!fr && fg && fb) ans = min(gb, br + rg);
    
    // 6. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc121/editorial/1927

// C++(GCC 9.2.1)

#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

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

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

vl r, g, b;

rep(i, N * 2){

LL x;

char c[11];

scanf("%lld %s", &x, c);

if(c[0] == 'R') r.pb(x);

if(c[0] == 'G') g.pb(x);

if(c[0] == 'B') b.pb(x);

}

// 2. 出現回数が, すべて偶数だった場合.

int lr = r.size(), lg = g.size(), lb = b.size();

bool fr = (lr & 1), fg = (lg & 1), fb = (lb & 1);

if(!fr && !fg && !fb){

puts("0");

return 0;

}

// 3. sort.

sort(all(r));

sort(all(g));

sort(all(b));

// 4. 二色間の不満の最小値を計算.

// 4-1. (赤, 緑).

LL rg = 202020202020202020;

rep(i, lr){

int at = lower_bound(all(g), r[i]) - g.begin();

if(at) rg = min(rg, abs(r[i] - g[at - 1]));

if(at < lg) rg = min(rg, abs(r[i] - g[at]));

}

// 4-2. (緑, 青).

LL gb = 202020202020202020;

rep(i, lg){

int at = lower_bound(all(b), g[i]) - b.begin();

if(at) gb = min(gb, abs(g[i] - b[at - 1]));

if(at < lb) gb = min(gb, abs(g[i] - b[at]));

}

// 4-3. (青, 赤).

LL br = 202020202020202020;

rep(i, lb){

int at = lower_bound(all(r), b[i]) - r.begin();

if(at) br = min(br, abs(b[i] - r[at - 1]));

if(at < lr) br = min(br, abs(b[i] - r[at]));

}

// 5. 不満の総和(最小値)を計算.

LL ans = 0;

// 5-1. (R, G, B) = (奇, 奇, 偶).

if(fr && fg && !fb) ans = min(rg, gb + br);

// 5-2. (R, G, B) = (奇, 偶, 奇).

if(fr && !fg && fb) ans = min(br, rg + gb);

// 5-3. (R, G, B) = (偶, 奇, 奇).

if(!fr && fg && fb) ans = min(gb, br + rg);

// 6. 出力.

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

return 0;

}

[入力例]
1
1 R
2 G

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

[入力例]
1
1 B
2 B

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

[入力例]
10
585 B
293 B
788 B
222 B
772 G
841 B
115 R
603 G
450 B
325 R
851 B
205 G
134 G
651 R
565 R
548 B
391 G
19 G
808 B
475 B

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

[入力例]
5
98 R
102 R
120 G
7 B
6 G
120 B
109 G
52 G
36 G
86 R

[出力例]
7

[入力例]
50
11244743 B
5877149 B
5099161 G
1208388 G
1648015 G
3217963 G
11108936 R
4512846 R
10124520 R
2074767 R
8806995 G
2282762 G
7053673 G
2677487 R
7801965 R
11788960 B
10571032 R
4599279 G
1388012 B
11206734 G
11187751 R
8937750 R
9137969 R
1472865 G
7856676 B
7150864 B
11772619 B
8227625 R
11934812 R
2422385 B
3797610 B
1625819 G
7740320 G
4874554 R
6450228 R
6270440 G
9044072 G
11323991 G
9005953 R
2933852 G
3548266 G
5176481 R
5019226 G
1856370 R
4647775 G
980522 G
180201 R
6965382 R
8372851 G
2160152 R
9430055 B
1001030 G
12327675 R
6563200 R
1863499 G
9586292 G
1434649 R
6703481 R
11164197 G
8360086 G
3664837 B
5710294 G
7038426 R
3582456 G
4453263 B
3958311 B
3182379 B
628331 G
3797981 G
9503947 G
12044492 R
11378209 G
4543606 R
6054089 B
8452268 G
12178767 B
1306080 R
11467141 R
9516770 G
3402052 G
7283144 G
10900531 G
12170455 G
8432463 G
6337490 B
5242718 B
10205154 R
4084846 B
1237260 R
1056401 G
1166758 G
3866554 G
4518124 G
9219884 B
377518 G
2593292 G
7634244 B
11914718 R
9352220 R
5863932 B

[出力例]
5278

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

[入力例]

1 R

2 G

[出力例]

※AtCoderのテストケースより

[入力例]

1 B

2 B

[出力例]

※AtCoderのテストケースより

[入力例]

585 B

293 B

788 B

222 B

772 G

841 B

115 R

603 G

450 B

325 R

851 B

205 G

134 G

651 R

565 R

548 B

391 G

19 G

808 B

475 B

[出力例]

※AtCoderのテストケースより

[入力例]

98 R

102 R

120 G

7 B

6 G

120 B

109 G

52 G

36 G

86 R

[出力例]

[入力例]

11244743 B

5877149 B

5099161 G

1208388 G

1648015 G

3217963 G

11108936 R

4512846 R

10124520 R

2074767 R

8806995 G

2282762 G

7053673 G

2677487 R

7801965 R

11788960 B

10571032 R

4599279 G

1388012 B

11206734 G

11187751 R

8937750 R

9137969 R

1472865 G

7856676 B

7150864 B

11772619 B

8227625 R

11934812 R

2422385 B

3797610 B

1625819 G

7740320 G

4874554 R

6450228 R

6270440 G

9044072 G

11323991 G

9005953 R

2933852 G

3548266 G

5176481 R

5019226 G

1856370 R

4647775 G

980522 G

180201 R

6965382 R

8372851 G

2160152 R

9430055 B

1001030 G

12327675 R

6563200 R

1863499 G

9586292 G

1434649 R

6703481 R

11164197 G

8360086 G

3664837 B

5710294 G

7038426 R

3582456 G

4453263 B

3958311 B

3182379 B

628331 G

3797981 G

9503947 G

12044492 R

11378209 G

4543606 R

6054089 B

8452268 G

12178767 B

1306080 R

11467141 R

9516770 G

3402052 G

7283144 G

10900531 G

12170455 G

8432463 G

6337490 B

5242718 B

10205154 R

4084846 B

1237260 R

1056401 G

1166758 G

3866554 G

4518124 G

9219884 B

377518 G

2593292 G

7634244 B

11914718 R

9352220 R

5863932 B

[出力例]

5278

■参照サイト
AtCoder Regular Contest 121

2021年5月30日

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

C++の練習を兼ねて, AtCoder Regular Contest 120 の問題D (Bracket Score 2) を解いてみた.

■感想.
1. 問題Dは, 方針が見えなかったので, 解説を参考にして, ようやく, AC版に到達出来た.
2. 問題Dで, stack の復習ができたので, 良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/arc120/editorial/1567
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using P = pair<int, 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 a first
#define b second
P a[404040];
int c[404040]; // 白色 … 0, 黒色 … 1.
char ans[404040];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N * 2){
        int x;
        scanf("%d", &x);
        P p;
        p.a = x;
        p.b = i;
        a[i] = p;
    }
    
    // 2. sort.
    sort(a, a + N * 2);
    
    // 3. 白黒で塗り分ける.
    repx(i, N, N * 2) c[a[i].b] = 1;
    
    // 4. 括弧列を生成.
    stack<P> st; // {色, 位置}.
    rep(i, N * 2){
        if(st.empty()){
            st.push({c[i], i});
            continue;
        }
        P p = st.top();
        if(p.a != c[i]){
            st.pop();
            ans[p.b] = '(';
            ans[i]   = ')';
        }else{
            st.push({c[i], i});
        }
    }
    
    // 5. 出力.
    rep(i, N * 2) printf("%c", ans[i]);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc120/editorial/1567

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using P = pair<int, 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 a first

#define b second

P a[404040];

int c[404040]; // 白色 … 0, 黒色 … 1.

char ans[404040];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

rep(i, N * 2){

int x;

scanf("%d", &x);

P p;

p.a = x;

p.b = i;

a[i] = p;

}

// 2. sort.

sort(a, a + N * 2);

// 3. 白黒で塗り分ける.

repx(i, N, N * 2) c[a[i].b] = 1;

// 4. 括弧列を生成.

stack st; // {色, 位置}.

rep(i, N * 2){

if(st.empty()){

st.push({c[i], i});

continue;

}

P p = st.top();

if(p.a != c[i]){

st.pop();

ans[p.b] = '(';

ans[i] = ')';

}else{

st.push({c[i], i});

}

// 5. 出力.

rep(i, N * 2) printf("%c", ans[i]);

return 0;

}

[入力例]
2
1 2 3 4

[出力例]
(())
※AtCoderテストケースより

[入力例]
2
2 3 2 3

[出力例]
()()
※AtCoderテストケースより

[入力例]
25
15 34 74 100 33 22 82 59 48 94 20 14 120 83 35 100 44 20 14 113 4 122 116 92 28 59 24 32 49 3 50 93 104 32 85 50 49 61 92 78 55 55 50 94 49 108 69 19 69 56

[出力例]
(())(())()(())()((()()))()((((())()(()))()()())())

[入力例]
50
11641 11322 7163 7244 3976 7791 7281 699 3094 4504 202 8464 8790 794 4252 543 2151 2824 5560 8375 12278 4939 413 9317 9325 11267 95 11559 12048 5875 3671 5987 335 8900 2825 2480 8890 6940 1068 10774 4915 7193 2371 10944 2737 10753 9995 611 191 11053 3762 1512 1149 4373 10958 12226 4535 3183 2006 6402 2918 8013 10403 4542 7955 733 525 9262 11905 7275 11489 9912 5127 4503 12028 7866 7454 3260 3111 7735 4613 3454 2098 10405 2728 1536 8755 7409 4002 5896 965 7901 2502 2619 5937 2678 6457 3000 4962 7431

[出力例]
(((()(())))(()))(())()()(()((()()())(()()()()(())())))(())()()()()()(((())((())()))())(()()())()()()

[入力例]

1 2 3 4

[出力例]

(())

※AtCoderテストケースより

[入力例]

2 3 2 3

[出力例]

()()

※AtCoderテストケースより

[入力例]

15 34 74 100 33 22 82 59 48 94 20 14 120 83 35 100 44 20 14 113 4 122 116 92 28 59 24 32 49 3 50 93 104 32 85 50 49 61 92 78 55 55 50 94 49 108 69 19 69 56

[出力例]

(())(())()(())()((()()))()((((())()(()))()()())())

[入力例]

11641 11322 7163 7244 3976 7791 7281 699 3094 4504 202 8464 8790 794 4252 543 2151 2824 5560 8375 12278 4939 413 9317 9325 11267 95 11559 12048 5875 3671 5987 335 8900 2825 2480 8890 6940 1068 10774 4915 7193 2371 10944 2737 10753 9995 611 191 11053 3762 1512 1149 4373 10958 12226 4535 3183 2006 6402 2918 8013 10403 4542 7955 733 525 9262 11905 7275 11489 9912 5127 4503 12028 7866 7454 3260 3111 7735 4613 3454 2098 10405 2728 1536 8755 7409 4002 5896 965 7901 2502 2619 5937 2678 6457 3000 4962 7431

[出力例]

(((()(())))(()))(())()()(()((()()())(()()()()(())())))(())()()()()()(((())((())()))())(()()())()()()

■参照サイト
AtCoder Regular Contest 120

2021年5月28日

C++ の動作確認をしてみた（４７０）

C++の練習を兼ねて, AtCoder Beginner Contest 202 の問題C (Made Up) ～問題D (aab aba baa) を解いてみた.

■感想.
1. 問題Dは, 動的計画法が使えそうに見えたので, 実装してみたところ, AC版に到達できた.
2. 苦手な動的計画法の訓練を積めたので, 非常に良かったと思う.
3. 問題Dは, 動的計画法を使いながら, 文字列を確定させていく処理が, 個人的には, 非常に面白いと感じた.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#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--)
int a[101010], b[101010], c[101010];
LL bc[101010];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%d", &a[i]);
    rep(i, N) scanf("%d", &b[i]);
    rep(i, N){
        scanf("%d", &c[i]);
        c[i]--;
    }
    
    // 2. b[c[j]] を 保存.
    rep(i, N) bc[b[c[i]]]++;
    
    // 3. 条件を満たす 整数の組(i, j) を 計算.
    LL ans = 0;
    rep(i, N) ans += bc[a[i]];
    
    // 4. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

int a[101010], b[101010], c[101010];

LL bc[101010];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

rep(i, N) scanf("%d", &a[i]);

rep(i, N) scanf("%d", &b[i]);

rep(i, N){

scanf("%d", &c[i]);

c[i]--;

}

// 2. b[c[j]] を保存.

rep(i, N) bc[b[c[i]]]++;

// 3. 条件を満たす整数の組(i, j) を計算.

LL ans = 0;

rep(i, N) ans += bc[a[i]];

// 4. 出力.

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

return 0;

}

[入力例]
3
1 2 2
3 1 2
2 3 2

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

[入力例]
4
1 1 1 1
1 1 1 1
1 2 3 4

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

[入力例]
3
2 3 3
1 3 3
1 1 1

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

[入力例]
20
10 1 3 9 12 12 11 12 6 5 12 3 10 1 3 7 10 6 7 2
8 1 6 7 3 2 12 8 10 10 8 11 1 11 1 12 10 11 11 6
11 1 1 4 9 2 7 10 7 7 2 12 1 8 4 9 10 9 5 1

[出力例]
39

[入力例]
100
21 21 14 17 15 19 11 21 4 14 5 18 15 19 3 4 13 10 4 18 20 22 21 14 14 19 17 18 19 5 15 5 10 3 17 10 2 12 15 16 9 19 2 5 19 15 9 9 10 11 10 5 16 18 1 7 17 4 2 13 18 17 18 6 16 9 7 1 14 18 10 10 3 18 18 1 7 18 22 22 7 18 4 3 2 13 20 16 3 18 19 16 2 20 18 17 8 10 8 19
13 22 13 18 15 20 1 20 18 8 21 6 1 3 18 12 4 8 1 17 12 8 1 5 16 10 2 3 14 16 2 21 20 11 6 8 5 17 10 5 2 8 1 10 21 18 18 10 21 22 22 6 3 19 22 7 13 14 7 20 6 12 7 20 6 22 15 14 8 22 3 7 19 21 16 5 15 22 7 20 11 2 7 9 22 10 16 7 20 12 13 6 20 17 19 8 22 21 13 6
4 11 18 9 11 3 16 22 1 15 3 13 1 21 7 15 11 9 22 10 14 14 17 15 2 22 12 1 16 4 17 2 21 15 19 11 3 19 9 5 7 4 13 19 17 11 22 22 15 9 14 14 2 19 13 13 16 13 18 6 7 14 7 22 7 18 17 18 21 10 13 10 22 8 11 4 18 3 15 7 6 11 17 16 19 10 18 9 13 21 3 8 2 2 20 3 12 10 15 11

[出力例]
455

[入力例]

1 2 2

3 1 2

2 3 2

[出力例]

※AtCoderテストケースより

[入力例]

1 1 1 1

1 2 3 4

[出力例]

※AtCoderテストケースより

[入力例]

2 3 3

1 3 3

1 1 1

[出力例]

※AtCoderテストケースより

[入力例]

10 1 3 9 12 12 11 12 6 5 12 3 10 1 3 7 10 6 7 2

8 1 6 7 3 2 12 8 10 10 8 11 1 11 1 12 10 11 11 6

11 1 1 4 9 2 7 10 7 7 2 12 1 8 4 9 10 9 5 1

[出力例]

[入力例]

100

21 21 14 17 15 19 11 21 4 14 5 18 15 19 3 4 13 10 4 18 20 22 21 14 14 19 17 18 19 5 15 5 10 3 17 10 2 12 15 16 9 19 2 5 19 15 9 9 10 11 10 5 16 18 1 7 17 4 2 13 18 17 18 6 16 9 7 1 14 18 10 10 3 18 18 1 7 18 22 22 7 18 4 3 2 13 20 16 3 18 19 16 2 20 18 17 8 10 8 19

13 22 13 18 15 20 1 20 18 8 21 6 1 3 18 12 4 8 1 17 12 8 1 5 16 10 2 3 14 16 2 21 20 11 6 8 5 17 10 5 2 8 1 10 21 18 18 10 21 22 22 6 3 19 22 7 13 14 7 20 6 12 7 20 6 22 15 14 8 22 3 7 19 21 16 5 15 22 7 20 11 2 7 9 22 10 16 7 20 12 13 6 20 17 19 8 22 21 13 6

4 11 18 9 11 3 16 22 1 15 3 13 1 21 7 15 11 9 22 10 14 14 17 15 2 22 12 1 16 4 17 2 21 15 19 11 3 19 9 5 7 4 13 19 17 11 22 22 15 9 14 14 2 19 13 13 16 13 18 6 7 14 7 22 7 18 17 18 21 10 13 10 22 8 11 4 18 3 15 7 6 11 17 16 19 10 18 9 13 21 3 8 2 2 20 3 12 10 15 11

[出力例]

455

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#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
LL C[61][61];
LL dp[66][2]; // i番目を, 'a', 'b' のいずれを設定するか保存.

int main(){
    
    // 1. 入力情報.
    int A, B;
    LL K;
    scanf("%d %d %lld", &A, &B, &K);
    
    // 2. パスカルの三角形で, 事前計算.
    rep(i, 61){
        rep(j, 61){
            if(!j || j == i) C[i][j] = 1LL;
            else             C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
        }
    }
    // rep(i, 20){
    //     rep(j, 20) printf("%lld ", C[i][j]);
    //     puts("");
    // }
    
    // 3. dp更新.
    string ans = "";
    int resA = A, resB = B;
    dp[0][0] = 1;
    dp[0][1] = 1 + C[resA + resB - 1][resB];
    repx(i, 1, A + B + 1){
        // 3-1. 前回分取得.
        if(dp[i - 1][1] <= K){
            dp[i][0] = dp[i][1] = dp[i - 1][1];
            ans.pb('b');
            resB--;
        }else{
            dp[i][0] = dp[i][1] = dp[i - 1][0];
            ans.pb('a');
            resA--;
        }
        assert(resA >= 0);
        assert(resB >= 0);
        
        // 3-2. i番目が, 'b' となる場合の開始番号.
        dp[i][1] += C[resA + resB - 1][resB];
    }
    // rep(i, 10) printf("%lld %lld\n", dp[i][0], dp[i][1]);
    
    // 4. 出力.
    printf("%s\n", ans.c_str());
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

#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

LL C[61][61];

LL dp[66][2]; // i番目を, 'a', 'b' のいずれを設定するか保存.

int main(){

// 1. 入力情報.

int A, B;

LL K;

scanf("%d %d %lld", &A, &B, &K);

// 2. パスカルの三角形で, 事前計算.

rep(i, 61){

rep(j, 61){

if(!j || j == i) C[i][j] = 1LL;

else C[i][j] = C[i - 1][j - 1] + C[i - 1][j];

}

// rep(i, 20){

// rep(j, 20) printf("%lld ", C[i][j]);

// puts("");

// }

// 3. dp更新.

string ans = "";

int resA = A, resB = B;

dp[0][0] = 1;

dp[0][1] = 1 + C[resA + resB - 1][resB];

repx(i, 1, A + B + 1){

// 3-1. 前回分取得.

if(dp[i - 1][1] <= K){

dp[i][0] = dp[i][1] = dp[i - 1][1];

ans.pb('b');

resB--;

}else{

dp[i][0] = dp[i][1] = dp[i - 1][0];

ans.pb('a');

resA--;

}

assert(resA >= 0);

assert(resB >= 0);

// 3-2. i番目が, 'b' となる場合の開始番号.

dp[i][1] += C[resA + resB - 1][resB];

}

// rep(i, 10) printf("%lld %lld\n", dp[i][0], dp[i][1]);

// 4. 出力.

printf("%s\n", ans.c_str());

return 0;

}

[入力例]
2 2 4

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

[入力例]
30 30 118264581564861424

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

[入力例]
3 2 5

[出力例]
ababa

[入力例]
1 1 1

[出力例]
ab

[入力例]
1 1 2

[出力例]
ba

[入力例]
1 3 4

[出力例]
bbba

[入力例]
5 3 25

[出力例]
abaababa

[入力例]
10 17 1234567

[出力例]
abaabbabbabbabbbababbbbbaba

[入力例]
25 11 123456789

[出力例]
aaaabbababaabaaaabbaaaaabaaabaabbaaa

[入力例]

2 2 4

[出力例]

baab

※AtCoderテストケースより

[入力例]

30 30 118264581564861424

[出力例]

bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

※AtCoderテストケースより

[入力例]

3 2 5

[出力例]

ababa

[入力例]

1 1 1

[出力例]

[入力例]

1 1 2

[出力例]

[入力例]

1 3 4

[出力例]

bbba

[入力例]

5 3 25

[出力例]

abaababa

[入力例]

10 17 1234567

[出力例]

abaabbabbabbabbbababbbbbaba

[入力例]

25 11 123456789

[出力例]

aaaabbababaabaaaabbaaaaabaaabaabbaaa

■参照サイト
エイシングプログラミングコンテスト2021（AtCoder Beginner Contest 202）

2021年5月27日

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

C++の練習を兼ねて, AtCoder Regular Contest 120 の問題C (Swaps 2) を解いてみた.

■感想.
1. 問題Cは, 解答方針が見えなかったので, 解説を参考に実装して, ようやく, AC版に到達できた.
2. 個人的には, 問題の背景に, 転倒数の性質が使われている部分が, 非常に面白いと感じた.
3. Binary Indexed Tree の復習が出来たので, 非常に良かったと思う.
※ 公式のライブラリを拝借させて頂いてます.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/arc120/editorial/1921
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#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 a first
#define b second
int a[202020], b[202020];

// Binary Indexed Tree (Fenwick Tree)
// https://youtu.be/lyHk98daDJo?t=7960
template<typename T>
struct BIT{
    int n;
    vector<T> d;
    BIT(int n = 0) : n(n), d(n + 1) {}
    void add(int i, T x = 1){
        for(i++; i <= n; i += i & -i) d[i] += x;
    }
    T sum(int i){
        T x = 0;
        for(i++; i; i -= i & -i) x += d[i];
        return x;
    }
    T sum(int l, int r){
        return sum(r - 1) - sum(l - 1);
    }
};

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    set<int> aSet, bSet;
    map<int, int> m;
    rep(i, N){
        scanf("%d", &a[i]);
        a[i] += (i + 1);
        aSet.insert(a[i]);
        m[a[i]]++;
    }
    rep(i, N){
        scanf("%d", &b[i]);
        b[i] += (i + 1);
        bSet.insert(b[i]);
    }
    
    // 2. A, B の 集合を比較.
    if(aSet != bSet){
        puts("-1");
        return 0;
    }
    
    // 3. A, B の 値を, 1 ～ N に収まるように変換.
    int idx = 0;
    for(auto &p : m) p.b = ++idx;
    rep(i, N) a[i] = m[a[i]], b[i] = m[b[i]];
    
    // 4. B の それぞれの出現位置を保存.
    vector<deque<int>> dq(idx + 1);
    rep(i, N) dq[b[i]].push_back(i + 1);
    
    // 5. 転倒数 を 計算.
    BIT<LL> ft(N + 1);
    LL ans = 0;
    rep(i, N){
        // 5-1. 数列 a[i] に対する 数列 B の 位置は？
        int pos = dq[a[i]].front();
        dq[a[i]].pop_front();
        
        // 5-2. 上記の場所に, 1 を 加算.
        ft.add(pos, 1LL);
        
        // 5-3. 区間[pos + 1, N] の 合計は？
        LL t = ft.sum(pos + 1, N + 1);
        
        // 5-4. 集計.
        ans += t;
    }
    
    // 6. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc120/editorial/1921

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

#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 a first

#define b second

int a[202020], b[202020];

// Binary Indexed Tree (Fenwick Tree)

// https://youtu.be/lyHk98daDJo?t=7960

template<typename T>

struct BIT{

int n;

vector<T> d;

BIT(int n = 0) : n(n), d(n + 1) {}

void add(int i, T x = 1){

for(i++; i <= n; i += i & -i) d[i] += x;

}

T sum(int i){

T x = 0;

for(i++; i; i -= i & -i) x += d[i];

return x;

}

T sum(int l, int r){

return sum(r - 1) - sum(l - 1);

}

};

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

set<int> aSet, bSet;

map<int, int> m;

rep(i, N){

scanf("%d", &a[i]);

a[i] += (i + 1);

aSet.insert(a[i]);

m[a[i]]++;

}

rep(i, N){

scanf("%d", &b[i]);

b[i] += (i + 1);

bSet.insert(b[i]);

}

// 2. A, B の集合を比較.

if(aSet != bSet){

puts("-1");

return 0;

}

// 3. A, B の値を, 1 ～ N に収まるように変換.

int idx = 0;

for(auto &p : m) p.b = ++idx;

rep(i, N) a[i] = m[a[i]], b[i] = m[b[i]];

// 4. B のそれぞれの出現位置を保存.

vector<deque<int>> dq(idx + 1);

rep(i, N) dq[b[i]].push_back(i + 1);

// 5. 転倒数を計算.

BIT<LL> ft(N + 1);

LL ans = 0;

rep(i, N){

// 5-1. 数列 a[i] に対する数列 B の位置は？

int pos = dq[a[i]].front();

dq[a[i]].pop_front();

// 5-2. 上記の場所に, 1 を加算.

ft.add(pos, 1LL);

// 5-3. 区間[pos + 1, N] の合計は？

LL t = ft.sum(pos + 1, N + 1);

// 5-4. 集計.

ans += t;

}

// 6. 出力.

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

return 0;

}

[入力例]
3
3 1 4
6 2 0

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

[入力例]
3
1 1 1
1 1 2

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

[入力例]
5
5 4 1 3 2
5 4 1 3 2

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

[入力例]
6
8 5 4 7 4 5
10 5 6 7 4 1

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

[入力例]
15
1 1 3 1 9 10 2 3 9 0 3 4 6 2 9
1 1 3 1 4 10 12 3 1 4 3 4 11 2 3

[出力例]
17

[入力例]
100
6 29 11 49 18 34 32 11 31 30 19 7 25 32 48 22 10 6 22 45 20 5 16 27 34 24 46 17 40 27 24 33 39 48 30 33 3 21 41 24 24 4 8 13 9 30 27 3 25 26 17 15 40 10 44 40 16 45 41 43 4 7 20 18 13 10 9 42 26 22 31 42 25 18 4 5 30 10 43 38 44 29 2 36 1 35 29 19 0 4 14 15 10 3 21 4 17 16 18 13
6 12 16 15 18 18 20 19 21 21 27 26 26 25 25 24 23 22 22 21 24 24 23 26 26 25 24 25 25 25 26 25 26 25 28 28 27 27 26 25 24 23 24 24 24 23 22 24 24 23 23 22 23 22 21 20 21 21 21 21 21 20 20 21 21 22 22 24 23 23 23 23 23 23 23 23 23 22 23 23 22 21 22 23 22 21 23 23 24 24 23 22 23 22 22 22 23 23 23 25

[出力例]
696

[入力例]
200
26 55 51 41 20 33 64 21 31 3 21 2 28 47 12 64 19 60 8 12 64 22 30 19 35 36 37 63 24 19 0 33 18 42 34 38 6 57 19 0 63 32 52 57 12 54 66 21 36 29 25 66 18 56 5 39 19 59 59 9 64 0 10 23 26 60 62 22 16 46 20 58 38 12 15 44 8 15 8 54 13 55 0 20 58 62 66 44 61 4 66 49 50 22 56 54 56 26 19 26 41 14 58 13 24 31 17 64 50 48 44 17 18 0 8 21 14 34 26 8 49 18 45 26 64 37 43 19 49 66 2 53 23 20 55 40 35 10 9 8 5 59 61 30 26 66 52 53 62 44 27 23 27 1 32 34 54 31 57 64 3 49 41 33 12 61 63 25 12 42 16 2 15 39 0 43 23 18 31 54 49 39 18 15 11 38 58 42 25 27 63 57 22 66 48 60 51 0 58 59
12 12 22 23 22 21 22 23 34 22 25 27 27 26 26 16 26 26 26 29 39 31 30 30 32 31 31 32 22 31 31 30 31 31 34 33 32 33 32 33 33 32 33 32 31 32 32 32 34 35 34 33 32 32 32 31 33 32 32 31 30 31 31 30 30 29 28 32 32 34 33 38 38 39 39 40 39 38 38 37 37 36 35 36 38 38 37 37 37 36 37 37 36 35 35 35 34 34 34 34 36 35 34 36 36 36 36 35 36 36 36 36 35 34 33 34 33 32 32 32 32 31 31 31 30 30 30 30 30 31 32 32 35 36 35 35 35 34 35 34 34 33 33 33 33 32 33 33 36 37 36 36 36 35 35 34 36 36 37 36 35 35 35 35 34 34 34 33 32 34 33 38 38 37 36 36 35 35 35 35 35 35 36 37 39 38 40 42 41 40 43 51 52 54 54 58 59 59 60 60

[出力例]
1992

[入力例]

3 1 4

6 2 0

[出力例]

※AtCoderテストケースより

[入力例]

1 1 1

1 1 2

[出力例]

-1

※AtCoderテストケースより

[入力例]

5 4 1 3 2

[出力例]

※AtCoderテストケースより

[入力例]

8 5 4 7 4 5

10 5 6 7 4 1

[出力例]

※AtCoderテストケースより

[入力例]

1 1 3 1 9 10 2 3 9 0 3 4 6 2 9

1 1 3 1 4 10 12 3 1 4 3 4 11 2 3

[出力例]

[入力例]

100

6 29 11 49 18 34 32 11 31 30 19 7 25 32 48 22 10 6 22 45 20 5 16 27 34 24 46 17 40 27 24 33 39 48 30 33 3 21 41 24 24 4 8 13 9 30 27 3 25 26 17 15 40 10 44 40 16 45 41 43 4 7 20 18 13 10 9 42 26 22 31 42 25 18 4 5 30 10 43 38 44 29 2 36 1 35 29 19 0 4 14 15 10 3 21 4 17 16 18 13

6 12 16 15 18 18 20 19 21 21 27 26 26 25 25 24 23 22 22 21 24 24 23 26 26 25 24 25 25 25 26 25 26 25 28 28 27 27 26 25 24 23 24 24 24 23 22 24 24 23 23 22 23 22 21 20 21 21 21 21 21 20 20 21 21 22 22 24 23 23 23 23 23 23 23 23 23 22 23 23 22 21 22 23 22 21 23 23 24 24 23 22 23 22 22 22 23 23 23 25

[出力例]

696

[入力例]

200

26 55 51 41 20 33 64 21 31 3 21 2 28 47 12 64 19 60 8 12 64 22 30 19 35 36 37 63 24 19 0 33 18 42 34 38 6 57 19 0 63 32 52 57 12 54 66 21 36 29 25 66 18 56 5 39 19 59 59 9 64 0 10 23 26 60 62 22 16 46 20 58 38 12 15 44 8 15 8 54 13 55 0 20 58 62 66 44 61 4 66 49 50 22 56 54 56 26 19 26 41 14 58 13 24 31 17 64 50 48 44 17 18 0 8 21 14 34 26 8 49 18 45 26 64 37 43 19 49 66 2 53 23 20 55 40 35 10 9 8 5 59 61 30 26 66 52 53 62 44 27 23 27 1 32 34 54 31 57 64 3 49 41 33 12 61 63 25 12 42 16 2 15 39 0 43 23 18 31 54 49 39 18 15 11 38 58 42 25 27 63 57 22 66 48 60 51 0 58 59

12 12 22 23 22 21 22 23 34 22 25 27 27 26 26 16 26 26 26 29 39 31 30 30 32 31 31 32 22 31 31 30 31 31 34 33 32 33 32 33 33 32 33 32 31 32 32 32 34 35 34 33 32 32 32 31 33 32 32 31 30 31 31 30 30 29 28 32 32 34 33 38 38 39 39 40 39 38 38 37 37 36 35 36 38 38 37 37 37 36 37 37 36 35 35 35 34 34 34 34 36 35 34 36 36 36 36 35 36 36 36 36 35 34 33 34 33 32 32 32 32 31 31 31 30 30 30 30 30 31 32 32 35 36 35 35 35 34 35 34 34 33 33 33 33 32 33 33 36 37 36 36 36 35 35 34 36 36 37 36 35 35 35 35 34 34 34 33 32 34 33 38 38 37 36 36 35 35 35 35 35 35 36 37 39 38 40 42 41 40 43 51 52 54 54 58 59 59 60 60

[出力例]

1992

■参照サイト
AtCoder Regular Contest 120
Binary Indexed Tree (Fenwick Tree)

2021年5月26日

C++ の動作確認をしてみた（４６８）

C++の練習を兼ねて, 競プロ典型 90 問の問題046 (I Love 46) を解いてみた.

■感想.
1. 問題046は, 数え上げ方が, 非常に面白いと感じた.
2. 手強い問題が非常に多い気もするけど, 時間を見つけて, 引き続き, 取り組んでいきたいと思う.

詳細は, 本家のサイト(GitHub) 競プロ典型 90 問の問題046 をご覧下さい.

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#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--)
LL ca[46], cb[46], cc[46];

int main(){
    
    // 1. 入力情報.
    int N, t;
    scanf("%d", &N);
    rep(i, N * 3){
        scanf("%d", &t);
        
        // 出現回数保存.
        if(i < N)           ca[(t % 46)]++;
        else if(i >= N * 2) cc[(t % 46)]++;
        else                cb[(t % 46)]++;
    }
    
    // 2. 数え上げる.
    LL ans = 0;
    rep(b, 46){
        // a, b, c の 和が, 46 で割り切れるケースを加算.
        LL d = 0;
        rep(a, 46) rep(c, 46) if((a + b + c) % 46 == 0) d += ca[a] * cc[c];
        
        // 加算.
        ans += cb[b] * d;
    }
    
    // 3. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

LL ca[46], cb[46], cc[46];

int main(){

// 1. 入力情報.

int N, t;

scanf("%d", &N);

rep(i, N * 3){

scanf("%d", &t);

// 出現回数保存.

if(i < N) ca[(t % 46)]++;

else if(i >= N * 2) cc[(t % 46)]++;

else cb[(t % 46)]++;

}

// 2. 数え上げる.

LL ans = 0;

rep(b, 46){

// a, b, c の和が, 46 で割り切れるケースを加算.

LL d = 0;

rep(a, 46) rep(c, 46) if((a + b + c) % 46 == 0) d += ca[a] * cc[c];

// 加算.

ans += cb[b] * d;

}

// 3. 出力.

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

return 0;

}

[入力例]
3
10 13 93
5 27 35
55 28 52

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

[入力例]
3
10 56 102
16 62 108
20 66 112

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

[入力例]
20
238 395 46 238 264 114 354 52 324 14 472 64 307 280 209 24 165 194 179 248
270 83 377 332 173 21 362 75 66 342 229 117 124 481 48 235 376 13 420 74
175 427 76 278 486 169 311 47 348 225 41 482 355 356 263 95 170 156 340 289

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

[入力例]
46
16 11 8 33 3 13 1 22 27 18 34 7 38 39 10 0 28 1 1 4 23 32 33 26 27 7 31 35 1 15 3 8 26 38 29 38 17 23 6 24 5 27 35 38 21 34
2 31 10 4 6 34 19 6 33 28 37 8 13 12 16 20 17 15 33 36 24 5 31 33 30 8 14 4 6 20 22 23 33 1 35 16 26 18 25 25 1 16 22 35 8 2
1 26 13 32 23 22 34 23 28 17 5 37 1 7 27 16 16 15 22 7 14 2 22 10 35 32 14 28 26 4 35 18 6 30 39 36 32 23 26 20 26 5 24 3 4 39

[出力例]
2121

[入力例]

10 13 93

5 27 35

55 28 52

[出力例]

※AtCoderテストケースより

[入力例]

10 56 102

16 62 108

20 66 112

[出力例]

※AtCoderテストケースより

[入力例]

238 395 46 238 264 114 354 52 324 14 472 64 307 280 209 24 165 194 179 248

270 83 377 332 173 21 362 75 66 342 229 117 124 481 48 235 376 13 420 74

175 427 76 278 486 169 311 47 348 225 41 482 355 356 263 95 170 156 340 289

[出力例]

183

※AtCoderテストケースより

[入力例]

16 11 8 33 3 13 1 22 27 18 34 7 38 39 10 0 28 1 1 4 23 32 33 26 27 7 31 35 1 15 3 8 26 38 29 38 17 23 6 24 5 27 35 38 21 34

2 31 10 4 6 34 19 6 33 28 37 8 13 12 16 20 17 15 33 36 24 5 31 33 30 8 14 4 6 20 22 23 33 1 35 16 26 18 25 25 1 16 22 35 8 2

1 26 13 32 23 22 34 23 28 17 5 37 1 7 27 16 16 15 22 7 14 2 22 10 35 32 14 28 26 4 35 18 6 30 39 36 32 23 26 20 26 5 24 3 4 39

[出力例]

2121

■参照サイト
046 – I Love 46

2021年5月25日

C++ の動作確認をしてみた（４６７）

C++の練習を兼ねて, AtCoder Regular Contest 120 の問題A (Max Add) ～問題B (Uniformly Distributed) を解いてみた.

■感想.
1. 規則性に気付けたので, AC版に到達出来たと思う.
2. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#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--)
LL a[202020], aMax[202020], aCum[202020];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%lld", &a[i]);
    
    // 2. i番目までの最大値を保存.
    rep(i, N) aMax[i + 1] = max(aMax[i], a[i]);
    
    // 3. 累積和.
    rep(i, N) aCum[i + 1] = aCum[i] + a[i];
    rep(i, N) aCum[i + 1] += aCum[i];
    
    // 4. 出力.
    repx(i, 1, N + 1) printf("%lld\n", aMax[i] * i + aCum[i]);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

LL a[202020], aMax[202020], aCum[202020];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

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

// 2. i番目までの最大値を保存.

rep(i, N) aMax[i + 1] = max(aMax[i], a[i]);

// 3. 累積和.

rep(i, N) aCum[i + 1] = aCum[i] + a[i];

rep(i, N) aCum[i + 1] += aCum[i];

// 4. 出力.

repx(i, 1, N + 1) printf("%lld\n", aMax[i] * i + aCum[i]);

return 0;

}

[入力例]
3
1 2 3

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

[入力例]
10
7 6 1 4 5 11 7 11 8 3

[出力例]
14
34
55
80
110
175
227
290
361
435

[入力例]

1 2 3

[出力例]

※AtCoderのテストケースより

[入力例]

7 6 1 4 5 11 7 11 8 3

[出力例]

110

175

227

290

361

435

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#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 LL MOD = 998244353;
int board[1010][1010]; // マスの色(0: 色なし, 1: 赤, 2: 青).
int cnt[1010][3];      // 出現回数(0: 色なし, 1: 赤, 2: 青).

int main(){
    
    // 1. 入力情報.
    int H, W;
    scanf("%d %d", &H, &W);
    rep(i, H){
        char c[505];
        scanf("%s", c);
        rep(j, W){
            if(c[j] == 'R') board[i][j] = 1;
            if(c[j] == 'B') board[i][j] = 2;
        }
    }
    
    // 2. 右上から左下に向かって, マスの色を確認.
    rep(k, H + W - 1){
        rep(i, H + W - 1){
            int j = k - i;
            if(j >= 0) cnt[k][board[i][j]]++;
            else       break;
        }
    }
    // rep(i, H + W - 1) printf("n=%d r=%d b=%d\n", cnt[i][0], cnt[i][1], cnt[i][2]);
    
    // 3. 色なしのみをカウント.
    // -> 赤, 青が混在している場合は, 着色不可能と判定.
    // -> 開始地点, 終了地点も, '.' となる場合があるので, 注意.
    LL ans = 1;
    int noColor = 0;
    rep(i, H + W - 1){
        if(cnt[i][1] && cnt[i][2])   ans = 0;
        if(!cnt[i][1] && !cnt[i][2]) noColor++;
    }
    
    // 4. 塗り方の総数は？
    rep(i, noColor) ans <<= 1, ans %= MOD;
    
    // 5. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

#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 LL MOD = 998244353;

int board[1010][1010]; // マスの色(0: 色なし, 1: 赤, 2: 青).

int cnt[1010][3]; // 出現回数(0: 色なし, 1: 赤, 2: 青).

int main(){

// 1. 入力情報.

int H, W;

scanf("%d %d", &H, &W);

rep(i, H){

char c[505];

scanf("%s", c);

rep(j, W){

if(c[j] == 'R') board[i][j] = 1;

if(c[j] == 'B') board[i][j] = 2;

}

// 2. 右上から左下に向かって, マスの色を確認.

rep(k, H + W - 1){

rep(i, H + W - 1){

int j = k - i;

if(j >= 0) cnt[k][board[i][j]]++;

else break;

}

// rep(i, H + W - 1) printf("n=%d r=%d b=%d\n", cnt[i][0], cnt[i][1], cnt[i][2]);

// 3. 色なしのみをカウント.

// -> 赤, 青が混在している場合は, 着色不可能と判定.

// -> 開始地点, 終了地点も, '.' となる場合があるので, 注意.

LL ans = 1;

int noColor = 0;

rep(i, H + W - 1){

if(cnt[i][1] && cnt[i][2]) ans = 0;

if(!cnt[i][1] && !cnt[i][2]) noColor++;

}

// 4. 塗り方の総数は？

rep(i, noColor) ans <<= 1, ans %= MOD;

// 5. 出力.

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

return 0;

}

[入力例]
2 2
B.
.R

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

[入力例]
3 3
R.R
BBR
...

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

[入力例]
2 2
BB
BB

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

[入力例]
2 2
..
..

[出力例]
8

[入力例]
5 10
RR..B...RR
R.......RB
..B...R.B.
.......B..
B...R.B..B

[出力例]
128

[入力例]
20 25
.R..B....R...............
R........B..B............
......R..................
.......B.................
B........B..R............
.....B.........B..R......
........................R
...B.....................
............B.........R..
.B..B....................
...............R.........
..B......B..............B
.......................B.
.................R.......
.............R...........
...............R....B....
.........................
.........................
.........................
........................R

[出力例]
75497471

[入力例]

2 2

[出力例]

※AtCoderのテストケースより

[入力例]

3 3

R.R

BBR

...

[出力例]

※AtCoderのテストケースより

[入力例]

2 2

[出力例]

※AtCoderのテストケースより

[入力例]

2 2

[出力例]

[入力例]

5 10

RR..B...RR

R.......RB

..B...R.B.

.......B..

B...R.B..B

[出力例]

128

[入力例]

20 25

.R..B....R...............

R........B..B............

......R..................

.......B.................

B........B..R............

.....B.........B..R......

........................R

...B.....................

............B.........R..

.B..B....................

...............R.........

..B......B..............B

.......................B.

.................R.......

.............R...........

...............R....B....

.........................

........................R

[出力例]

75497471

■参照サイト
AtCoder Regular Contest 120

C++の練習を兼ねて, AtCoder Beginner Contest 203 の 問題F (Weed) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 203 の 問題E (White Pawn) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 203 の 問題C (Friends and Travel costs) ～ 問題D (Pond) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 201 の 問題E (Xor Distances) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 121 の 問題A (2nd Greatest Distance) ～ 問題B (RGB Matching) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 120 の 問題D (Bracket Score 2) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 202 の 問題C (Made Up) ～ 問題D (aab aba baa) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 120 の 問題C (Swaps 2) を解いてみた.

C++の練習を兼ねて, 競プロ典型 90 問 の 問題046 (I Love 46) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 120 の 問題A (Max Add) ～ 問題B (Uniformly Distributed) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 203 の問題F (Weed) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 203 の問題E (White Pawn) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 203 の問題C (Friends and Travel costs) ～問題D (Pond) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 201 の問題E (Xor Distances) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 121 の問題A (2nd Greatest Distance) ～問題B (RGB Matching) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 120 の問題D (Bracket Score 2) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 202 の問題C (Made Up) ～問題D (aab aba baa) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 120 の問題C (Swaps 2) を解いてみた.

C++の練習を兼ねて, 競プロ典型 90 問の問題046 (I Love 46) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 120 の問題A (Max Add) ～問題B (Uniformly Distributed) を解いてみた.