C++ | 個人用メモ帳

2023年7月19日

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

C++の練習を兼ねて, AtCoder Beginner Contest 309 の問題C (Medicine) ～問題E (Family and Insurance) を解いてみた.

■感想.
1. 問題C ～ E は, 方針を絞り込めたので, AC版に到達できたと思う.
2. 個人的には, 幅優先探索, 深さ優先探索の訓練を積めたので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

■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--)
#define a first
#define b second

int main(){
    
    // 1. 入力情報.
    int N;
    LL K;
    scanf("%d %lld", &N, &K);
    map<LL, LL> m;
    rep(i, N){
        LL a, b;
        scanf("%lld %lld", &a, &b);
        m[1] += b;
        m[a + 1] -= b;
    }
    
    // 2. K 錠以下となる日は？
    LL ans = 0, bef = 0;
    for(auto &x : m){
        if(bef + x.b <= K){
            ans = x.a;
            break;
        }
        bef += x.b;
    }
    
    // 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--)

#define a first

#define b second

int main(){

// 1. 入力情報.

int N;

LL K;

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

map<LL, LL> m;

rep(i, N){

LL a, b;

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

m[1] += b;

m[a + 1] -= b;

}

// 2. K 錠以下となる日は？

LL ans = 0, bef = 0;

for(auto &x : m){

if(bef + x.b <= K){

ans = x.a;

break;

}

bef += x.b;

}

// 3. 出力.

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

return 0;

}

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

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

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

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

[入力例]
15 158260522
877914575 2436426
24979445 61648772
623690081 33933447
476190629 62703497
211047202 71407775
628894325 31963982
822804784 50968417
430302156 82631932
161735902 80895728
923078537 7723857
189330739 10286918
802329211 4539679
303238506 17063340
492686568 73361868
125660016 50287940

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

[入力例]
20 50
35 89
113 68
12 91
47 39
50 102
31 44
113 70
45 66
100 93
80 68
51 93
105 17
74 99
112 68
47 106
119 121
86 36
95 13
76 48
17 10

[出力例]
120

[入力例]
30 123456789
7243344 39645001
110611721 58764066
54943571 7858259
27652310 45631404
108885402 58254068
63309952 54581014
14961992 64159015
50683657 90394950
114601656 67985265
27910507 21684920
14643649 75065657
81812380 68477230
99446454 110995892
28245926 89882812
19853288 72407860
9336074 108313969
56279010 58943019
32548337 96665548
90304960 21889493
32324555 100548176
50649146 67321897
14707156 3434551
119127221 33695514
70909013 99071221
15471945 54145916
110898063 49158872
15649382 75510226
21230601 28253500
71654589 9111419
120392263 8725587

[出力例]
110898064

100

101

102

103

104

105

[入力例]

4 8

6 3

2 5

1 9

4 2

[出力例]

※AtCoderテストケースより

[入力例]

4 100

6 3

2 5

1 9

4 2

[出力例]

※AtCoderテストケースより

[入力例]

15 158260522

877914575 2436426

24979445 61648772

623690081 33933447

476190629 62703497

211047202 71407775

628894325 31963982

822804784 50968417

430302156 82631932

161735902 80895728

923078537 7723857

189330739 10286918

802329211 4539679

303238506 17063340

492686568 73361868

125660016 50287940

[出力例]

492686569

※AtCoderテストケースより

[入力例]

20 50

35 89

113 68

12 91

47 39

50 102

31 44

113 70

45 66

100 93

80 68

51 93

105 17

74 99

112 68

47 106

119 121

86 36

95 13

76 48

17 10

[出力例]

120

[入力例]

30 123456789

7243344 39645001

110611721 58764066

54943571 7858259

27652310 45631404

108885402 58254068

63309952 54581014

14961992 64159015

50683657 90394950

114601656 67985265

27910507 21684920

14643649 75065657

81812380 68477230

99446454 110995892

28245926 89882812

19853288 72407860

9336074 108313969

56279010 58943019

32548337 96665548

90304960 21889493

32324555 100548176

50649146 67321897

14707156 3434551

119127221 33695514

70909013 99071221

15471945 54145916

110898063 49158872

15649382 75510226

21230601 28253500

71654589 9111419

120392263 8725587

[出力例]

110898064

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
#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

int main(){
    
    // 1. 入力情報.
    int N1, N2, M;
    scanf("%d %d %d", &N1, &N2, &M);
    int N = N1 + N2;
    vvi G(N);
    rep(i, M){
        int a, b;
        scanf("%d %d", &a, &b);
        --a;
        --b;
        G[a].pb(b);
        G[b].pb(a);
    }
    
    // 2. bfs.
    // https://ja.wikipedia.org/wiki/幅優先探索
    auto bfs = [&](vvi &G, int s, int* d){
        // 空のキュー.
        queue<int> q;
        
        // 探索地点 s をキュー q に追加.
        q.push(s);
        while(!q.empty()){
            // キューから取り出す.
            int u = q.front();
            q.pop();
            
            // 隣接頂点をチェック.
            for(auto &v : G[u]) if(!d[v] && v != s) d[v] = d[u] + 1, q.push(v);
        }
    };
    int d1[N], d2[N];
    rep(i, N) d1[i] = d2[i] = 0;
    bfs(G, 0, d1);
    bfs(G, N - 1, d2);
    
    // 3. 最大値は？
    int ans1 = 0, ans2 = 0;
    rep(i, N) ans1 = max(ans1, d1[i]);
    rep(i, N) ans2 = max(ans2, d2[i]);
    
    // 4. 出力.
    printf("%d\n", ans1 + ans2 + 1);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

using vvi = vector<vi>;

#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

int main(){

// 1. 入力情報.

int N1, N2, M;

scanf("%d %d %d", &N1, &N2, &M);

int N = N1 + N2;

vvi G(N);

rep(i, M){

int a, b;

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

--a;

--b;

G[a].pb(b);

G[b].pb(a);

}

// 2. bfs.

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

auto bfs = [&](vvi &G, int s, int* d){

// 空のキュー.

queue<int> q;

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

q.push(s);

while(!q.empty()){

// キューから取り出す.

int u = q.front();

q.pop();

// 隣接頂点をチェック.

for(auto &v : G[u]) if(!d[v] && v != s) d[v] = d[u] + 1, q.push(v);

}

};

int d1[N], d2[N];

rep(i, N) d1[i] = d2[i] = 0;

bfs(G, 0, d1);

bfs(G, N - 1, d2);

// 3. 最大値は？

int ans1 = 0, ans2 = 0;

rep(i, N) ans1 = max(ans1, d1[i]);

rep(i, N) ans2 = max(ans2, d2[i]);

// 4. 出力.

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

return 0;

}

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

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

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

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

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

[出力例]
11

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

[出力例]
9

[入力例]

3 4 6

1 2

2 3

4 5

4 6

1 3

6 7

[出力例]

※AtCoderテストケースより

[入力例]

7 5 20

10 11

4 5

10 12

1 2

1 5

5 6

2 4

3 5

9 10

2 5

1 4

11 12

9 12

8 9

5 7

3 7

3 6

3 4

8 12

9 11

[出力例]

※AtCoderテストケースより

[入力例]

5 7 10

1 2

2 5

3 4

4 5

6 7

6 8

8 10

9 10

11 9

11 12

[出力例]

[入力例]

6 9 13

2 1

3 1

3 4

5 3

4 6

8 7

7 10

10 9

9 14

13 14

11 10

12 11

15 11

[出力例]

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
#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
int memo[303030], insurance[303030];

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    vvi G(N);
    repx(i, 1, N){
        int p;
        scanf("%d", &p);
        --p;
        G[i].pb(p);
        G[p].pb(i);
    }
    int y[N];
    rep(i, N) y[i] = -1;
    rep(i, M){
        int a, b;
        scanf("%d %d", &a, &b);
        --a;
        y[a] = max(y[a], b);
    }
    
    // 2. dfs.
    // https://ja.wikipedia.org/wiki/深さ優先探索
    function<void(vvi&, int, int, int)> dfs = [&](vvi &G, int cur, int bef, int d) {
        // 終了条件.
        if(memo[cur]) return;
        
        // 訪問済みフラグ.
        memo[cur] = 1;
        
        // 補償対象者か？
        if(d >= 0) ++insurance[cur];
        
        // 隣接頂点.
        for(auto &nex : G[cur]){
            if(nex == bef) continue;
            dfs(G, nex, cur, max(d - 1, y[nex]));
        }
    };
    dfs(G, 0, -1, y[0]);
    /*
    rep(i, N) printf("%d ", insurance[i]);
    puts("");
    */
    
    // 3. 集計.
    int ans = 0;
    rep(i, N) ans += (insurance[i] > 0);
    
    // 4. 出力.
    printf("%d\n", ans);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

using vvi = vector<vi>;

#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

int memo[303030], insurance[303030];

int main(){

// 1. 入力情報.

int N, M;

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

vvi G(N);

repx(i, 1, N){

int p;

scanf("%d", &p);

--p;

G[i].pb(p);

G[p].pb(i);

}

int y[N];

rep(i, N) y[i] = -1;

rep(i, M){

int a, b;

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

--a;

y[a] = max(y[a], b);

}

// 2. dfs.

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

function<void(vvi&, int, int, int)> dfs = [&](vvi &G, int cur, int bef, int d) {

// 終了条件.

if(memo[cur]) return;

// 訪問済みフラグ.

memo[cur] = 1;

// 補償対象者か？

if(d >= 0) ++insurance[cur];

// 隣接頂点.

for(auto &nex : G[cur]){

if(nex == bef) continue;

dfs(G, nex, cur, max(d - 1, y[nex]));

}

};

dfs(G, 0, -1, y[0]);

rep(i, N) printf("%d ", insurance[i]);

puts("");

// 3. 集計.

int ans = 0;

rep(i, N) ans += (insurance[i] > 0);

// 4. 出力.

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

return 0;

}

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

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

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

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

[入力例]
15 5
1 2 5 1 5 6 6 4 4 8 8 3 13 14
1 1
4 1
12 1
8 2
14 1

[出力例]
11

[入力例]
25 7
1 2 2 1 1 6 6 5 4 4 7 7 8 8 3 3 11 11 19 19 12 22 22 24
3 1
16 1
19 1
18 2
22 2
14 1
12 1

[出力例]
13

[入力例]

7 3

1 2 1 3 3 3

1 1

1 2

4 3

[出力例]

※AtCoderテストケースより

[入力例]

10 10

1 1 3 1 2 3 3 5 7

2 1

5 1

4 3

6 3

2 1

7 3

9 2

1 2

6 2

8 1

[出力例]

※AtCoderテストケースより

[入力例]

15 5

1 2 5 1 5 6 6 4 4 8 8 3 13 14

1 1

4 1

12 1

8 2

14 1

[出力例]

[入力例]

25 7

1 2 2 1 1 6 6 5 4 4 7 7 8 8 3 3 11 11 19 19 12 22 22 24

3 1

16 1

19 1

18 2

22 2

14 1

12 1

[出力例]

■参照サイト
デンソークリエイトプログラミングコンテスト2023（AtCoder Beginner Contest 309）

2023年7月14日

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

C++の練習を兼ねて, AtCoder Beginner Contest 308 の問題F (Vouchers) ～問題G (Minimum Xor Pair Query) を解いてみた.

■感想.
1. 問題G は, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 実装に苦労したものの, std::multiset の復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vl = vector<LL>;
using PQ = priority_queue<LL>;
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, M;
    scanf("%d %d", &N, &M);
    vl P(N), L(M), D(M);
    rep(i, N) scanf("%lld", &P[i]);
    rep(i, M) scanf("%lld", &L[i]);
    rep(i, M) scanf("%lld", &D[i]);
    vp v(M);
    rep(i, M){
        v[i].a = L[i];
        v[i].b = D[i];
    }
    
    // 2. sort.
    sort(all(P));
    sort(all(v));
    
    // 3. 最小の金額は？
    LL ans = 0;
    int j = 0;
    PQ pq;
    rep(i, N){
        // 3-1. 利用可能なクーポンを保存.
        while(j < M){
            if(v[j].a > P[i]) break;
            pq.push(v[j].b);
            ++j;
        }
        
        // 3-2. 加算.
        ans += P[i];
        
        // 3-3. クーポン適用.
        if(!pq.empty()){
            ans -= pq.top();
            pq.pop();
        }
    }
    
    // 4. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vl = vector<LL>;

using PQ = priority_queue<LL>;

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, M;

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

vl P(N), L(M), D(M);

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

rep(i, M) scanf("%lld", &L[i]);

rep(i, M) scanf("%lld", &D[i]);

vp v(M);

rep(i, M){

v[i].a = L[i];

v[i].b = D[i];

}

// 2. sort.

sort(all(P));

sort(all(v));

// 3. 最小の金額は？

LL ans = 0;

int j = 0;

PQ pq;

rep(i, N){

// 3-1. 利用可能なクーポンを保存.

while(j < M){

if(v[j].a > P[i]) break;

pq.push(v[j].b);

++j;

}

// 3-2. 加算.

ans += P[i];

// 3-3. クーポン適用.

if(!pq.empty()){

ans -= pq.top();

pq.pop();

}

// 4. 出力.

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

return 0;

}

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

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

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

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

[入力例]
12 7
103 48 123 114 10 39 69 113 54 72 21 110
54 102 98 75 122 83 99
43 91 89 69 112 80 86

[出力例]
375

[入力例]
100 150
882 1159 678 1049 838 992 1091 749 311 258 411 68 107 785 491 1085 262 351 313 688 12 150 208 517 684 841 511 452 610 799 165 2 421 811 604 896 291 230 298 362 713 1035 53 1064 731 1165 1147 51 846 182 440 324 1113 190 702 651 22 689 23 198 290 848 589 51 597 1028 387 396 951 707 91 507 613 436 4 387 802 560 60 522 695 828 1121 504 35 1174 994 156 211 86 12 73 1072 24 158 1071 989 542 1015 258
956 950 238 584 866 695 858 303 1055 549 528 750 810 373 621 56 1046 837 405 402 900 570 977 928 1090 1114 1124 1026 396 521 571 63 1178 459 468 919 463 372 826 380 553 68 1031 623 961 883 491 697 393 275 1045 620 15 125 970 928 801 433 1084 1150 40 986 204 646 846 830 1067 250 1201 765 77 370 91 1007 393 717 1180 100 290 1043 318 311 235 836 708 683 155 365 521 142 878 1127 20 152 1084 458 1043 38 753 1143 846 132 1049 371 95 67 490 364 1148 77 681 905 519 500 793 288 211 95 802 1156 1069 611 334 312 479 1218 766 39 199 866 887 755 540 106 664 1038 517 932 1038 1185 872 1160 671 158 200 940 40 877 845 777
507 283 238 584 687 301 238 303 205 51 129 750 232 42 556 56 208 837 205 402 164 487 306 355 222 404 654 358 157 521 92 63 776 266 256 573 463 271 70 380 50 68 174 596 662 287 491 358 393 275 186 136 15 125 604 884 605 433 735 722 40 485 93 557 839 172 543 250 881 234 77 301 91 816 327 335 427 100 88 752 318 288 235 66 253 683 155 365 88 99 728 500 20 152 56 458 589 38 96 790 341 132 772 371 95 45 299 364 735 77 569 240 48 94 206 288 211 34 535 882 383 611 334 30 479 675 240 39 199 159 348 200 80 106 356 786 517 895 563 783 761 359 453 42 200 547 40 223 85 593

[出力例]
15000

[入力例]

3 3

4 3 1

4 4 2

2 3 1

[出力例]

※AtCoderテストケースより

[入力例]

10 5

9 7 1 5 2 2 5 5 7 6

7 2 7 8 2

3 2 4 1 2

[出力例]

※AtCoderテストケースより

[入力例]

12 7

103 48 123 114 10 39 69 113 54 72 21 110

54 102 98 75 122 83 99

43 91 89 69 112 80 86

[出力例]

375

[入力例]

100 150

882 1159 678 1049 838 992 1091 749 311 258 411 68 107 785 491 1085 262 351 313 688 12 150 208 517 684 841 511 452 610 799 165 2 421 811 604 896 291 230 298 362 713 1035 53 1064 731 1165 1147 51 846 182 440 324 1113 190 702 651 22 689 23 198 290 848 589 51 597 1028 387 396 951 707 91 507 613 436 4 387 802 560 60 522 695 828 1121 504 35 1174 994 156 211 86 12 73 1072 24 158 1071 989 542 1015 258

956 950 238 584 866 695 858 303 1055 549 528 750 810 373 621 56 1046 837 405 402 900 570 977 928 1090 1114 1124 1026 396 521 571 63 1178 459 468 919 463 372 826 380 553 68 1031 623 961 883 491 697 393 275 1045 620 15 125 970 928 801 433 1084 1150 40 986 204 646 846 830 1067 250 1201 765 77 370 91 1007 393 717 1180 100 290 1043 318 311 235 836 708 683 155 365 521 142 878 1127 20 152 1084 458 1043 38 753 1143 846 132 1049 371 95 67 490 364 1148 77 681 905 519 500 793 288 211 95 802 1156 1069 611 334 312 479 1218 766 39 199 866 887 755 540 106 664 1038 517 932 1038 1185 872 1160 671 158 200 940 40 877 845 777

507 283 238 584 687 301 238 303 205 51 129 750 232 42 556 56 208 837 205 402 164 487 306 355 222 404 654 358 157 521 92 63 776 266 256 573 463 271 70 380 50 68 174 596 662 287 491 358 393 275 186 136 15 125 604 884 605 433 735 722 40 485 93 557 839 172 543 250 881 234 77 301 91 816 327 335 427 100 88 752 318 288 235 66 253 683 155 365 88 99 728 500 20 152 56 458 589 38 96 790 341 132 772 371 95 45 299 364 735 77 569 240 48 94 206 288 211 34 535 882 383 611 334 30 479 675 240 39 199 159 348 200 80 106 356 786 517 895 563 783 761 359 453 42 200 547 40 223 85 593

[出力例]

15000

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

// 解き直し.
// https://atcoder.jp/contests/abc308/editorial/6707
// 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 main(){
    
    // 1. 入力情報.
    int Q;
    scanf("%d", &Q);
    
    // 2. クエリ回答.
    map<int, int> mXor;
    multiset<int> mst;
    rep(i, Q){
        // 2-1. クエリ入力情報.
        int f;
        scanf("%d", &f);
        
        // 2-2. クエリ 1.
        if(f == 1){
            int x;
            scanf("%d", &x);
            
            // 要素数で分岐.
            // 0個.
            int n = mst.size();
            if(n == 0){
                mst.insert(x);
                continue;
            }
            
            // 1個.
            if(n == 1){
                ++mXor[*mst.begin() ^ x];
                mst.insert(x);
                continue;
            }
            
            // 2個以上.
            // -> 最初, 中間, 最後で分岐.
            mst.insert(x);
            auto itr = mst.lower_bound(x);
            if(itr == mst.begin()){
                ++itr;
                ++mXor[*mst.begin() ^ *itr];
            }else if(itr == --mst.end()){
                --itr;
                ++mXor[*(--mst.end()) ^ *itr];
            }else{
                int l = *(--itr);
                ++itr;
                int r = *(++itr);
                --mXor[l ^ r];
                if(mXor[l ^ r] == 0) mXor.erase(l ^ r);
                ++mXor[l ^ x];
                ++mXor[x ^ r];
            }
        }
        
        // 2-3. クエリ 2.
        if(f == 2){
            int x;
            scanf("%d", &x);
            
            // 要素数で分岐.
            // 1個.
            int n = mst.size();
            if(n == 1){
                mst.erase(x);
                continue;
            }
            
            // 2個以上.
            // -> 最初, 中間, 最後で分岐.
            auto itr = mst.lower_bound(x);
            if(itr == mst.begin()){
                int l = *mst.begin();
                int r = *(++itr);
                --mXor[l ^ r];
                if(mXor[l ^ r] == 0) mXor.erase(l ^ r);
            }else if(itr == --mst.end()){
                int l = *(--itr);
                int r = *(--mst.end());
                --mXor[l ^ r];
                if(mXor[l ^ r] == 0) mXor.erase(l ^ r);
            }else{
                int l = *(--itr);
                ++itr;
                int r = *(++itr);
                ++mXor[l ^ r];
                --mXor[l ^ x];
                if(mXor[l ^ x] == 0) mXor.erase(l ^ x);
                --mXor[x ^ r];
                if(mXor[x ^ r] == 0) mXor.erase(x ^ r);
            }
            mst.erase(mst.find(x));
        }
        
        // 2-4. クエリ 3.
        if(f == 3) printf("%d\n", mXor.begin()->first);
    }
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

110

// 解き直し.

// https://atcoder.jp/contests/abc308/editorial/6707

// 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 main(){

// 1. 入力情報.

int Q;

scanf("%d", &Q);

// 2. クエリ回答.

map<int, int> mXor;

multiset<int> mst;

rep(i, Q){

// 2-1. クエリ入力情報.

int f;

scanf("%d", &f);

// 2-2. クエリ 1.

if(f == 1){

int x;

scanf("%d", &x);

// 要素数で分岐.

// 0個.

int n = mst.size();

if(n == 0){

mst.insert(x);

continue;

}

// 1個.

if(n == 1){

++mXor[*mst.begin() ^ x];

mst.insert(x);

continue;

}

// 2個以上.

// -> 最初, 中間, 最後で分岐.

mst.insert(x);

auto itr = mst.lower_bound(x);

if(itr == mst.begin()){

++itr;

++mXor[*mst.begin() ^ *itr];

}else if(itr == --mst.end()){

--itr;

++mXor[*(--mst.end()) ^ *itr];

}else{

int l = *(--itr);

++itr;

int r = *(++itr);

--mXor[l ^ r];

if(mXor[l ^ r] == 0) mXor.erase(l ^ r);

++mXor[l ^ x];

++mXor[x ^ r];

}

// 2-3. クエリ 2.

if(f == 2){

int x;

scanf("%d", &x);

// 要素数で分岐.

// 1個.

int n = mst.size();

if(n == 1){

mst.erase(x);

continue;

}

// 2個以上.

// -> 最初, 中間, 最後で分岐.

auto itr = mst.lower_bound(x);

if(itr == mst.begin()){

int l = *mst.begin();

int r = *(++itr);

--mXor[l ^ r];

if(mXor[l ^ r] == 0) mXor.erase(l ^ r);

}else if(itr == --mst.end()){

int l = *(--itr);

int r = *(--mst.end());

--mXor[l ^ r];

if(mXor[l ^ r] == 0) mXor.erase(l ^ r);

}else{

int l = *(--itr);

++itr;

int r = *(++itr);

++mXor[l ^ r];

--mXor[l ^ x];

if(mXor[l ^ x] == 0) mXor.erase(l ^ x);

--mXor[x ^ r];

if(mXor[x ^ r] == 0) mXor.erase(x ^ r);

}

mst.erase(mst.find(x));

}

// 2-4. クエリ 3.

if(f == 3) printf("%d\n", mXor.begin()->first);

}

return 0;

}

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

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

[入力例]
70
1 64
1 46
1 25
1 5
1 7
1 9
3
1 51
1 5
1 91
1 6
3
1 63
1 5
2 5
2 5
2 5
1 99
1 60
3
1 40
1 7
1 71
3
1 41
2 7
2 7
1 109
3
1 53
1 29
2 91
1 19
3
1 20
2 25
1 9
3
1 32
1 92
1 47
2 9
2 9
3
1 97
1 61
1 76
3
1 70
3
1 32
1 119
3
1 33
1 0
3
1 67
1 59
1 113
3
1 55
1 39
1 111
1 7
3
1 100
1 95
1 93
1 73
3

[出力例]
2
0
1
0
1
1
0
1
1
1
0
0
0
0
0

[入力例]
100
1 4282
1 7381
1 1971
1 7717
3
1 9166
1 14740
1 2856
1 5936
3
1 9121
1 16763
1 4997
1 9073
1 2740
1 3412
3
1 18735
1 3380
1 16133
3
1 7979
1 3992
2 7717
1 15625
3
1 6495
1 10890
1 8630
3
1 5937
1 2855
1 17854
1 9165
1 13490
3
1 19882
1 12257
1 10890
1 9119
3
1 19385
2 10890
1 21787
1 8272
3
1 20361
1 9119
1 14030
2 10890
1 8838
3
1 17845
1 22167
2 9119
1 17863
3
1 13961
2 9119
1 20044
2 2855
1 9074
3
1 5934
1 12072
1 15797
3
1 3120
2 5934
1 17048
1 1624
3
1 2152
1 18494
1 2740
1 17666
3
1 16868
2 2740
1 10406
3
1 13483
1 11639
2 2740
1 16260
3
1 12921
1 11414
2 14740
1 6595
3
1 17845
1 7618
1 9122
1 19740
3
1 1111
2 17845
1 1112
3

[出力例]
752
752
111
96
96
96
1
0
1
0
1
1
1
1
0
1
1
1
0
1

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

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

[入力例]

1 2

1 10

1 3

2 2

1 10

[出力例]

※AtCoderテストケースより

[入力例]

1 64

1 46

1 25

1 5

1 7

1 9

1 51

1 5

1 91

1 6

1 63

1 5

2 5

1 99

1 60

1 40

1 7

1 71

1 41

2 7

1 109

1 53

1 29

2 91

1 19

1 20

2 25

1 9

1 32

1 92

1 47

2 9

1 97

1 61

1 76

1 70

1 32

1 119

1 33

1 0

1 67

1 59

1 113

1 55

1 39

1 111

1 7

1 100

1 95

1 93

1 73

[出力例]

[入力例]

100

1 4282

1 7381

1 1971

1 7717

1 9166

1 14740

1 2856

1 5936

1 9121

1 16763

1 4997

1 9073

1 2740

1 3412

1 18735

1 3380

1 16133

1 7979

1 3992

2 7717

1 15625

1 6495

1 10890

1 8630

1 5937

1 2855

1 17854

1 9165

1 13490

1 19882

1 12257

1 10890

1 9119

1 19385

2 10890

1 21787

1 8272

1 20361

1 9119

1 14030

2 10890

1 8838

1 17845

1 22167

2 9119

1 17863

1 13961

2 9119

1 20044

2 2855

1 9074

1 5934

1 12072

1 15797

1 3120

2 5934

1 17048

1 1624

1 2152

1 18494

1 2740

1 17666

1 16868

2 2740

1 10406

1 13483

1 11639

2 2740

1 16260

1 12921

1 11414

2 14740

1 6595

1 17845

1 7618

1 9122

1 19740

1 1111

2 17845

1 1112

[出力例]

752

111

■参照サイト
CodeQUEEN 2023 予選 (AtCoder Beginner Contest 308)

2023年7月7日2023年7月7日

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

C++の練習を兼ねて, AtCoder Beginner Contest 308 の問題C (Standings) ～問題E (MEX) を解いてみた.

■感想.
1. 問題C ～ E は, 方針を絞り込めたので, AC版に到達できたと思う.
2. 個人的には, 問題D で, 幅優先探索の復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

■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--)
#define all(x) x.begin(), x.end()

struct CoinToss {
    LL a, b, c;
    bool operator < (const CoinToss& rhs) const {
        return (a * (rhs.a + rhs.b) > rhs.a * (a + b)) || ((a * (rhs.a + rhs.b) == rhs.a * (a + b)) && (c < rhs.c));
    }
};

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    vector<CoinToss> v(N);
    rep(i, N){
        scanf("%lld %lld", &v[i].a, &v[i].b);
        v[i].c = i + 1;
    }
    
    // 2. sort.
    sort(all(v));
    
    // 3. 出力.
    rep(i, N) printf("%d%s", v[i].c, (i < N - 1) ? " " : "\n");
    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 all(x) x.begin(), x.end()

struct CoinToss {

LL a, b, c;

bool operator < (const CoinToss& rhs) const {

return (a * (rhs.a + rhs.b) > rhs.a * (a + b)) || ((a * (rhs.a + rhs.b) == rhs.a * (a + b)) && (c < rhs.c));

}

};

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

vector<CoinToss> v(N);

rep(i, N){

scanf("%lld %lld", &v[i].a, &v[i].b);

v[i].c = i + 1;

}

// 2. sort.

sort(all(v));

// 3. 出力.

rep(i, N) printf("%d%s", v[i].c, (i < N - 1) ? " " : "\n");

return 0;

}

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

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

[入力例]
2
1 3
2 6

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

[入力例]
4
999999999 1000000000
333333333 999999999
1000000000 999999997
999999998 1000000000

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

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

[出力例]
3 4 5 2 1

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

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

[入力例]

1 3

3 1

2 2

[出力例]

2 3 1

※AtCoderテストケースより

[入力例]

1 3

2 6

[出力例]

1 2

※AtCoderテストケースより

[入力例]

999999999 1000000000

333333333 999999999

1000000000 999999997

999999998 1000000000

[出力例]

3 1 4 2

※AtCoderテストケースより

[入力例]

0 1

1 2

2 0

3 1

3 2

[出力例]

3 4 5 2 1

[入力例]

1 2

4 1

11 10

5 4

1 8

8 2

7 10

4 1

0 5

8 6

[出力例]

2 6 8 10 4 3 7 1 5 9

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

// 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 h first
#define w second
const int INF = 2020202020, dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};
int board[505][505], memo[505][505];

int main(){
    
    // 1. 入力情報.
    int H, W;
    scanf("%d %d", &H, &W);
    rep(i, 505) rep(j, 505) board[i][j] = memo[i][j] = INF;
    rep(i, H){
        char c[505];
        scanf("%s", c);
        rep(j, W){
            if(c[j] == 's') board[i][j] = 0;
            if(c[j] == 'n') board[i][j] = 1;
            if(c[j] == 'u') board[i][j] = 2;
            if(c[j] == 'k') board[i][j] = 3;
            if(c[j] == 'e') board[i][j] = 4;
        }
    }
    
    // 2. bfs.
    // https://ja.wikipedia.org/wiki/幅優先探索
    auto bfs = [&](P s) -> void{
        // 空のキュー.
        queue<P> q;
        
        // 探索開始地点が条件を満たしてない.
        if(board[s.h][s.w]) return;
        
        // 訪問済み.
        memo[s.h][s.w] = 0;
        
        // 探索地点 s をキュー q に追加.
        q.push(s);
        while(!q.empty()){
            // キューから取り出す.
            P c = q.front();
            q.pop();
            
            // 現在文字.
            int cur = board[c.h][c.w];
            
            // 上下左右を見る.
            rep(i, 4){
                // x: 列方向, y: 行方向 で考える.
                int nh = c.h + dy[i];
                int nw = c.w + dx[i];
                
                // 訪問不可能なマスは, Skip.
                if(nh < 0 || nh >= H || nw < 0 || nw >= W || board[nh][nw] == INF) continue;
                
                // 訪問先文字.
                int nex = board[nh][nw];
                
                // 訪問可能 かつ 未訪問 であれば, 最短距離を設定.
                if(memo[nh][nw] == INF && nex == (cur + 1) % 5){
                    memo[nh][nw] = memo[c.h][c.w] + 1;
                    q.push({nh, nw});
                }
            }
        }
    };
    bfs({0, 0});
    
    // 3. 出力.
    printf("%s\n", memo[H - 1][W - 1] == INF ? "No" : "Yes");
    return 0;
    
}

// 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 h first

#define w second

const int INF = 2020202020, dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};

int board[505][505], memo[505][505];

int main(){

// 1. 入力情報.

int H, W;

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

rep(i, 505) rep(j, 505) board[i][j] = memo[i][j] = INF;

rep(i, H){

char c[505];

scanf("%s", c);

rep(j, W){

if(c[j] == 's') board[i][j] = 0;

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

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

if(c[j] == 'k') board[i][j] = 3;

if(c[j] == 'e') board[i][j] = 4;

}

// 2. bfs.

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

auto bfs = [&](P s) -> void{

// 空のキュー.

queue<P> q;

// 探索開始地点が条件を満たしてない.

if(board[s.h][s.w]) return;

// 訪問済み.

memo[s.h][s.w] = 0;

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

q.push(s);

while(!q.empty()){

// キューから取り出す.

P c = q.front();

q.pop();

// 現在文字.

int cur = board[c.h][c.w];

// 上下左右を見る.

rep(i, 4){

// x: 列方向, y: 行方向で考える.

int nh = c.h + dy[i];

int nw = c.w + dx[i];

// 訪問不可能なマスは, Skip.

if(nh < 0 || nh >= H || nw < 0 || nw >= W || board[nh][nw] == INF) continue;

// 訪問先文字.

int nex = board[nh][nw];

// 訪問可能かつ未訪問であれば, 最短距離を設定.

if(memo[nh][nw] == INF && nex == (cur + 1) % 5){

memo[nh][nw] = memo[c.h][c.w] + 1;

q.push({nh, nw});

}

};

bfs({0, 0});

// 3. 出力.

printf("%s\n", memo[H - 1][W - 1] == INF ? "No" : "Yes");

return 0;

}

[入力例]
2 3
sns
euk

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

[入力例]
2 2
ab
cd

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

[入力例]
5 7
skunsek
nukesnu
ukeseku
nsnnesn
uekukku

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

[入力例]
15 11
snutghbldly
soklwsjxmii
biesxbksmrr
ezxnuwubdjj
hvwskeshnl
wnicaunupkx
ffblnsekgoz
qqqkuhuvxid
qqqetipergn
tttsnhqubln
yyynukelgps
nrlasxkukch
zmnxuounetn
zbgknusnsuv
phokakenmnu

[出力例]
No

[入力例]
30 25
skiomhacwfkafimcrvbqxwoai
nufnexufygjwrycsasljzarvq
pkfazxcdzlzguzxzdqwafcaaq
iesnhesupiudqrrrsqdlmznpb
mvhuzknphrmamxtdrnqscfhnc
wlukeuuohmukqzywzowekgvwn
wldcsnknlasoeoetwkuhfmnpt
pekunsevbkdqenjuqsclgumfj
sswwfwxgrubryhvnrplesonge
anaiavxwjqtwlbdnaesknrogq
tukerjjvazkyxdcdjknuuzxbx
ryqsnukezrikzqvpnupakfzwj
whfagpasqcyrehpeswvaesayx
ctwhrbtndeyndmzkcetnpnsbl
kosfhxjukeqztthuicwemuked
xwcvwzchjshaqtsnrseuvojsi
jnabnryfxnukemekbwuaekuna
yravsmhdvywfsjkecwsksbiht
tmtrwqptyylaneukkwlunukyf
jeemxcxyjrbpuindsbrzbrezs
wxxmxjekunsekaszuzfkunsql
uxqexoszjgsnukeluyfetovrf
hyvrsknubwevhpdjsetsnafqw
uhatbihknukiyvnnllfzukezi
jiwtergeszqexapybhuwztspw
cstuslolbouninupufyjiunao
xmqpegtadpbdryaolohdekjte
lwxhvpxeqlxsgoitiyzosqesn
ecyenmbsxlyzkkwjzenfnukku
mnhwyfpsqcsdlqfojeywmmtes

[出力例]
Yes

[入力例]
75 50
sjwbxqzfwknxcbhgjonlobwnqyveiazvaxqvwixktnvoxgkkim
ndvnixsficwuarwlmlbklowjapvczpqlxmcrhuyejgwntqhntt
uukewtqmnbtjvypobefunvmkyrststfrkeafofadjpqwzwookg
knhseiftrluyrizoflrbonbwwfdluamnhaqnqpeufaushddnzo
esfnwcndypqyuflcakdxfczfpicqdcdcqudobrycrrdhruaffy
nozukeivbojircbotmpwlvndoacrxshbziwqypijxrcwsxednm
tdyvrsgqtawusitwxozemczgpbqirxvavpfhcfhlslcwuuubpz
stlsunwkehvxeuaqiwgulysylpaulrzqbjdqngekquagdofnqr
nsuqjutooiwaceeylxjrelxaliefnvzytwfeszrhfhqiajdgot
hzdhbkbscbuluwgcrkwerjhywfiqothraawvzedmuvsqfngdhv
wkvqpesnjrmpszdvfbfuvhwiruecwkpgwqtajkcivcflmpxbrr
meyrbdvukbzzqhzpuxucvihjgbkflfvdfaflmiydgkqscebker
ojnekunseplmgtyziprylgcbijfkkgwtjpfrilrqkxzdtvcvyb
cujsudrwcoozvpbewvlnzpkzytodvsivotdyoojnwfbgssshde
hzcnjctmdakobdtwwrllxtyjuiorubbcxervnlotwsfkbbfuup
ybnufmofgqkhxpqxmtqyyvnomjpqysqqjzsnwatrsytjwgneub
dxhkunwngvylhdfkacugpfcjjogvjgrghtzlrutlxllpniuxle
ilnesnhcuwhwbotbjlcpznuquqsmdzgyegzctnkxghffidqtjb
jcetlukeyvoxwufnsmjnpgmupykuysumlbekgjprttodtgboof
egaanjasnthjoltkmwjxfupcbojlrxlcdpqhddtfumsurnriwi
zsyqyxgeukesnukdwllmnjgztrlqmmzhuffuxwofmduyvukhzv
hwlywruitgcruaezlpyqpsgfplfzearxegrmzbbwjgjjxgonns
utqnvudqqilmcusqnrzghjmvibkhbyrtpjqsxpwrzhrfjilxjg
aawwdirgmcuofinmxlppruvsfpueoeuzdsjsuuwqxblajcwfpf
lbbwfjbjodnhnpuqoyfnkecaquksjyyxyecfwdkdenkydtrgjs
acmlgumjwhcttbkisyktpbbubqxikjwqaetdhlbtoqkbogdhbn
mcygqwomflkbftesnukexakdksqvsycbeujghmavramlijamld
chefsqcetmynklfqgiasnukeaaavzyjrxnomilnddranevsolg
mixpgpcpjhtygiwygidndcsspibqbwpcxlmqppvykeqkloname
dknfnsexdgehoivqurhuqbmnjdkgfxflubkhayonladaufusew
xutojxtnjbdkizuhlyhkjxaunisicwdtbtrppefrjfoajmokde
ghqcmemdvxcnxcogrssevbkkuxyynyfehnyfoggtsybjkzzrhl
rrcxbkjibqtmpzhxlanelnsepzwefzpecvqmtyvovcsnilgcep
tjssoziqntenvqwpwpuekuwteuleveajteqdstnsdyryhjvybd
mameshtifwbhoshrgxkesnuaynwvcprbzhqkkqeaiyvgbtkrvh
ictecttspdjkqxyoeerjqikwcuxgzwltiiiwolsfzwezjjyrfn
jajvnsohngvzcvlvfpglkaeszjagruowhkdqdjbtogjhcueumn
ahlfuwvzybdetepnetybuepnflyslqgtouphpydcgxzqwfwkjj
xfaukwakjlkuefzwdhnrlvpuyuwinowsfladqazxfapbjrwczm
xlmnhxpbecomfgfcehglckoknvhqtxewxblaradsmwyyivywfy
rytpjiuyykoignzvqntqpzsesnbeddkqqsjbxbxzxsqjbsijcb
lwuxjsftfdvsbnzmnvljceufnukeiltmaaqbnuaagohdfvcuwo
anjvaywwrqlwxjdqhiaypjyatdusnorybmvyrjjxwynvijmqak
vhqpdwcmwysdzjjpsufirydxemfoukhfaxyrsjxtpekqpjqmda
shugheraxwlbfvzfmxsanhhoknlfcesvrzilhylbtbgmkgbimf
ibtflhcmajvzggylhcqalscbojuntcnnmgdfksztkdghlhmzvi
dswyhdgrnkutnrxrumjpqrgrnbgxjiueubqycmdarujuiwiqrq
wyasqrnjqvaijwhfdxzsykaadrutbskgfnydcinwswgcytryel
afnskzmdycrevmindguhibwlnvoegrepxtnuizqqnfadevcnku
ukxjpxkhpttrpabqpvgacuwqztmtghssydxqpzfuzfqncciqyh
pmaxftsnauxzdctlzobjyderarhjawnukesvzikgbbtnkfgjje
gygtodoukwpmlgxqeimmwccidrmxnwjiuqnqthrdsaqxauukht
egdvzucbzedkpvhvblvqjkkfngqdjnnideuukehhjidfmvpcwn
hbtdimvghgxqedgqlzjgpwyttvqnetqoquksmzzqgcdazfdurd
kaessfsbxssujdouugtgkeuegoxqqkbyhfeirfvmiqzlmwtnwa
aklctewxvtkkwnnswqgbztcghdsgpkgjwbsphraacmyrmsqzez
dniqhdqmfonvigwhqfqvracwcvhdfttfzrnigxymvzazpeyieh
orubqbecyvhampinjcmtcjzwqithlrwngsuqdbsuutbpagphio
pkrruaxemnpiyrfasachdrbvdwsqmlmdrlklwmdwydugycqemo
jlnyzuhwnojgjujwpgdqvttkkclnecpzpvesnukefimsayxxgh
jvieywspsoxuhdmalmyaxqdeouzikmecofypmaishlozomrvfr
prjpigjskkrkaavtoyjeikftsimpjnvlimzkvnfnjpkcbijjgs
omddbtixdmjwdtnavotayjqumchujthecmluedoupdaubtfxpu
cmqncxyzgwodldnfrxugvfdfcflmivsihxbkseskabytsjbosa
psapvbjjaoxovkwwdlhjbykkanbbkrsmejevlgceswxsjsmmsb
acrrqxpplgqmfqhpthcxjrqztwvxcpmmfgyeezkongvwryrgju
pnrvrjuklqmgwaciukkifteciplqvmlqjprtvtmguyjckxpazx
ysdnxacyxycmxekjcrcrihigmeqbwjarecpvrlrfkpmxvqvvyq
vcytyvttafpwnrgrszwksygibkwszcttkpavzinnesnujvmvkb
xwwdoerbqsyzazlipioyifpottnhiqllyerfcupptoakroloxj
jnjinqfmvoweotpmlhasaytlrlpfrgykyyjcgxeqohbesbuywg
mcwccvpfnkpgpexpxnvcqrjhlmekxgmddiplrqugtycintzcho
ubhiiirboygwpgqutzwkbfrktegpzcglkrohqxfvahrvukeszw
bmkmzfdppbbgblcqonksogzysnwpxyxitmvvdneyobpbrxjnqj
sxijddridzhdqpdbgspldnkrdfrrzvoxsouaekjdzaiskgluke

[出力例]
Yes

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

167

[入力例]

2 3

sns

euk

[出力例]

Yes

※AtCoderテストケースより

[入力例]

2 2

[出力例]

※AtCoderテストケースより

[入力例]

5 7

skunsek

nukesnu

ukeseku

nsnnesn

uekukku

[出力例]

Yes

※AtCoderテストケースより

[入力例]

15 11

snutghbldly

soklwsjxmii

biesxbksmrr

ezxnuwubdjj

hvwskeshnl

wnicaunupkx

ffblnsekgoz

qqqkuhuvxid

qqqetipergn

tttsnhqubln

yyynukelgps

nrlasxkukch

zmnxuounetn

zbgknusnsuv

phokakenmnu

[出力例]

[入力例]

30 25

skiomhacwfkafimcrvbqxwoai

nufnexufygjwrycsasljzarvq

pkfazxcdzlzguzxzdqwafcaaq

iesnhesupiudqrrrsqdlmznpb

mvhuzknphrmamxtdrnqscfhnc

wlukeuuohmukqzywzowekgvwn

wldcsnknlasoeoetwkuhfmnpt

pekunsevbkdqenjuqsclgumfj

sswwfwxgrubryhvnrplesonge

anaiavxwjqtwlbdnaesknrogq

tukerjjvazkyxdcdjknuuzxbx

ryqsnukezrikzqvpnupakfzwj

whfagpasqcyrehpeswvaesayx

ctwhrbtndeyndmzkcetnpnsbl

kosfhxjukeqztthuicwemuked

xwcvwzchjshaqtsnrseuvojsi

jnabnryfxnukemekbwuaekuna

yravsmhdvywfsjkecwsksbiht

tmtrwqptyylaneukkwlunukyf

jeemxcxyjrbpuindsbrzbrezs

wxxmxjekunsekaszuzfkunsql

uxqexoszjgsnukeluyfetovrf

hyvrsknubwevhpdjsetsnafqw

uhatbihknukiyvnnllfzukezi

jiwtergeszqexapybhuwztspw

cstuslolbouninupufyjiunao

xmqpegtadpbdryaolohdekjte

lwxhvpxeqlxsgoitiyzosqesn

ecyenmbsxlyzkkwjzenfnukku

mnhwyfpsqcsdlqfojeywmmtes

[出力例]

Yes

[入力例]

75 50

sjwbxqzfwknxcbhgjonlobwnqyveiazvaxqvwixktnvoxgkkim

ndvnixsficwuarwlmlbklowjapvczpqlxmcrhuyejgwntqhntt

uukewtqmnbtjvypobefunvmkyrststfrkeafofadjpqwzwookg

knhseiftrluyrizoflrbonbwwfdluamnhaqnqpeufaushddnzo

esfnwcndypqyuflcakdxfczfpicqdcdcqudobrycrrdhruaffy

nozukeivbojircbotmpwlvndoacrxshbziwqypijxrcwsxednm

tdyvrsgqtawusitwxozemczgpbqirxvavpfhcfhlslcwuuubpz

stlsunwkehvxeuaqiwgulysylpaulrzqbjdqngekquagdofnqr

nsuqjutooiwaceeylxjrelxaliefnvzytwfeszrhfhqiajdgot

hzdhbkbscbuluwgcrkwerjhywfiqothraawvzedmuvsqfngdhv

wkvqpesnjrmpszdvfbfuvhwiruecwkpgwqtajkcivcflmpxbrr

meyrbdvukbzzqhzpuxucvihjgbkflfvdfaflmiydgkqscebker

ojnekunseplmgtyziprylgcbijfkkgwtjpfrilrqkxzdtvcvyb

cujsudrwcoozvpbewvlnzpkzytodvsivotdyoojnwfbgssshde

hzcnjctmdakobdtwwrllxtyjuiorubbcxervnlotwsfkbbfuup

ybnufmofgqkhxpqxmtqyyvnomjpqysqqjzsnwatrsytjwgneub

dxhkunwngvylhdfkacugpfcjjogvjgrghtzlrutlxllpniuxle

ilnesnhcuwhwbotbjlcpznuquqsmdzgyegzctnkxghffidqtjb

jcetlukeyvoxwufnsmjnpgmupykuysumlbekgjprttodtgboof

egaanjasnthjoltkmwjxfupcbojlrxlcdpqhddtfumsurnriwi

zsyqyxgeukesnukdwllmnjgztrlqmmzhuffuxwofmduyvukhzv

hwlywruitgcruaezlpyqpsgfplfzearxegrmzbbwjgjjxgonns

utqnvudqqilmcusqnrzghjmvibkhbyrtpjqsxpwrzhrfjilxjg

aawwdirgmcuofinmxlppruvsfpueoeuzdsjsuuwqxblajcwfpf

lbbwfjbjodnhnpuqoyfnkecaquksjyyxyecfwdkdenkydtrgjs

acmlgumjwhcttbkisyktpbbubqxikjwqaetdhlbtoqkbogdhbn

mcygqwomflkbftesnukexakdksqvsycbeujghmavramlijamld

chefsqcetmynklfqgiasnukeaaavzyjrxnomilnddranevsolg

mixpgpcpjhtygiwygidndcsspibqbwpcxlmqppvykeqkloname

dknfnsexdgehoivqurhuqbmnjdkgfxflubkhayonladaufusew

xutojxtnjbdkizuhlyhkjxaunisicwdtbtrppefrjfoajmokde

ghqcmemdvxcnxcogrssevbkkuxyynyfehnyfoggtsybjkzzrhl

rrcxbkjibqtmpzhxlanelnsepzwefzpecvqmtyvovcsnilgcep

tjssoziqntenvqwpwpuekuwteuleveajteqdstnsdyryhjvybd

mameshtifwbhoshrgxkesnuaynwvcprbzhqkkqeaiyvgbtkrvh

ictecttspdjkqxyoeerjqikwcuxgzwltiiiwolsfzwezjjyrfn

jajvnsohngvzcvlvfpglkaeszjagruowhkdqdjbtogjhcueumn

ahlfuwvzybdetepnetybuepnflyslqgtouphpydcgxzqwfwkjj

xfaukwakjlkuefzwdhnrlvpuyuwinowsfladqazxfapbjrwczm

xlmnhxpbecomfgfcehglckoknvhqtxewxblaradsmwyyivywfy

rytpjiuyykoignzvqntqpzsesnbeddkqqsjbxbxzxsqjbsijcb

lwuxjsftfdvsbnzmnvljceufnukeiltmaaqbnuaagohdfvcuwo

anjvaywwrqlwxjdqhiaypjyatdusnorybmvyrjjxwynvijmqak

vhqpdwcmwysdzjjpsufirydxemfoukhfaxyrsjxtpekqpjqmda

shugheraxwlbfvzfmxsanhhoknlfcesvrzilhylbtbgmkgbimf

ibtflhcmajvzggylhcqalscbojuntcnnmgdfksztkdghlhmzvi

dswyhdgrnkutnrxrumjpqrgrnbgxjiueubqycmdarujuiwiqrq

wyasqrnjqvaijwhfdxzsykaadrutbskgfnydcinwswgcytryel

afnskzmdycrevmindguhibwlnvoegrepxtnuizqqnfadevcnku

ukxjpxkhpttrpabqpvgacuwqztmtghssydxqpzfuzfqncciqyh

pmaxftsnauxzdctlzobjyderarhjawnukesvzikgbbtnkfgjje

gygtodoukwpmlgxqeimmwccidrmxnwjiuqnqthrdsaqxauukht

egdvzucbzedkpvhvblvqjkkfngqdjnnideuukehhjidfmvpcwn

hbtdimvghgxqedgqlzjgpwyttvqnetqoquksmzzqgcdazfdurd

kaessfsbxssujdouugtgkeuegoxqqkbyhfeirfvmiqzlmwtnwa

aklctewxvtkkwnnswqgbztcghdsgpkgjwbsphraacmyrmsqzez

dniqhdqmfonvigwhqfqvracwcvhdfttfzrnigxymvzazpeyieh

orubqbecyvhampinjcmtcjzwqithlrwngsuqdbsuutbpagphio

pkrruaxemnpiyrfasachdrbvdwsqmlmdrlklwmdwydugycqemo

jlnyzuhwnojgjujwpgdqvttkkclnecpzpvesnukefimsayxxgh

jvieywspsoxuhdmalmyaxqdeouzikmecofypmaishlozomrvfr

prjpigjskkrkaavtoyjeikftsimpjnvlimzkvnfnjpkcbijjgs

omddbtixdmjwdtnavotayjqumchujthecmluedoupdaubtfxpu

cmqncxyzgwodldnfrxugvfdfcflmivsihxbkseskabytsjbosa

psapvbjjaoxovkwwdlhjbykkanbbkrsmejevlgceswxsjsmmsb

acrrqxpplgqmfqhpthcxjrqztwvxcpmmfgyeezkongvwryrgju

pnrvrjuklqmgwaciukkifteciplqvmlqjprtvtmguyjckxpazx

ysdnxacyxycmxekjcrcrihigmeqbwjarecpvrlrfkpmxvqvvyq

vcytyvttafpwnrgrszwksygibkwszcttkpavzinnesnujvmvkb

xwwdoerbqsyzazlipioyifpottnhiqllyerfcupptoakroloxj

jnjinqfmvoweotpmlhasaytlrlpfrgykyyjcgxeqohbesbuywg

mcwccvpfnkpgpexpxnvcqrjhlmekxgmddiplrqugtycintzcho

ubhiiirboygwpgqutzwkbfrktegpzcglkrohqxfvahrvukeszw

bmkmzfdppbbgblcqonksogzysnwpxyxitmvvdneyobpbrxjnqj

sxijddridzhdqpdbgspldnkrdfrrzvoxsouaekjdzaiskgluke

[出力例]

Yes

■C++版プログラム(問題E／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
#define a first
#define b second
int a[202020], mCum[202020][3], xCum[202020][3];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%d", &a[i]);
    char c[202020];
    scanf("%s", c);
    string s(c);
    
    // 2. MEX.
    map<string, LL> mex;
    rep(i, 3){
        rep(j, 3){
            rep(k, 3){
                string key;
                key.pb('0' + i);
                key.pb('0' + j);
                key.pb('0' + k);
                
                set<int> st;
                st.insert(i);
                st.insert(j);
                st.insert(k);
                rep(x, 4){
                    if(!st.count(x)){
                        mex[key] = x;
                        break;
                    }
                }
            }
        }
    }
    // for(auto &x : mex) printf("%s %lld\n", x.a.c_str(), x.b);
    
    // 3. 累積和.
    rep(i, N){
        rep(j, 3){
            mCum[i + 1][j] = mCum[i][j];
            xCum[i + 1][j] = xCum[i][j];
        }
        if(s[i] == 'M') ++mCum[i + 1][a[i]];
        if(s[i] == 'X') ++xCum[i + 1][a[i]];
    }
    
    // 4. 集計.
    LL ans = 0;
    rep(i, N){
        // Skip.
        if(s[i] != 'E') continue;
        
        // 左側 M, 右側 X.
        int e = a[i];
        rep(m, 3){
            // Skip(左側 M なし).
            LL mCount = mCum[i + 1][m];
            if(mCount == 0) continue;
            
            rep(x, 3){
                // Skip(右側 X なし).
                LL xCount = xCum[N][x] - xCum[i + 1][x];
                if(xCount == 0) continue;
                
                // MEX の キー.
                string key;
                key.pb('0' + m);
                key.pb('0' + e);
                key.pb('0' + x);
                
                // 加算.
                ans += mex[key] * mCount * xCount;
            }
        }
    }
    
    // 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--)

#define pb push_back

#define a first

#define b second

int a[202020], mCum[202020][3], xCum[202020][3];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

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

char c[202020];

scanf("%s", c);

string s(c);

// 2. MEX.

map<string, LL> mex;

rep(i, 3){

rep(j, 3){

rep(k, 3){

string key;

key.pb('0' + i);

key.pb('0' + j);

key.pb('0' + k);

set<int> st;

st.insert(i);

st.insert(j);

st.insert(k);

rep(x, 4){

if(!st.count(x)){

mex[key] = x;

break;

}

// for(auto &x : mex) printf("%s %lld\n", x.a.c_str(), x.b);

// 3. 累積和.

rep(i, N){

rep(j, 3){

mCum[i + 1][j] = mCum[i][j];

xCum[i + 1][j] = xCum[i][j];

}

if(s[i] == 'M') ++mCum[i + 1][a[i]];

if(s[i] == 'X') ++xCum[i + 1][a[i]];

}

// 4. 集計.

LL ans = 0;

rep(i, N){

// Skip.

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

// 左側 M, 右側 X.

int e = a[i];

rep(m, 3){

// Skip(左側 M なし).

LL mCount = mCum[i + 1][m];

if(mCount == 0) continue;

rep(x, 3){

// Skip(右側 X なし).

LL xCount = xCum[N][x] - xCum[i + 1][x];

if(xCount == 0) continue;

// MEX のキー.

string key;

key.pb('0' + m);

key.pb('0' + e);

key.pb('0' + x);

// 加算.

ans += mex[key] * mCount * xCount;

}

// 5. 出力.

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

return 0;

}

[入力例]
4
1 1 0 2
MEEX

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

[入力例]
3
0 0 0
XXX

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

[入力例]
15
1 1 2 0 0 2 0 2 0 0 0 0 0 2 2
EXMMXXXEMEXEXMM

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

[入力例]
10
0 0 2 2 2 1 1 0 1 0
MMEMEMEXXM

[出力例]
30

[入力例]
100
0 2 1 0 2 2 0 1 1 0 1 1 0 0 0 2 1 1 2 0 0 0 2 2 0 0 0 0 1 1 2 1 0 0 1 1 1 0 0 2 0 2 2 2 2 2 0 1 2 1 0 2 0 1 0 1 2 1 0 1 2 2 1 1 1 1 2 2 1 1 2 0 1 0 1 1 1 0 0 1 1 1 0 0 0 2 1 1 1 1 1 0 2 1 1 0 0 2 1 2
MEXMMMXMXXMMXMMEEXEEEXEEEMXMXEMMMEXEXMEXEXMXXMEEEXXEMMXMEXMEXEMXMXXXEEXEMEEMXXMEXEMXEMMEMMXXXEEEEMXX

[出力例]
11356

[入力例]
500
2 1 0 0 0 0 0 2 0 1 1 2 0 1 1 0 2 0 0 0 2 0 1 1 1 0 0 0 0 2 2 1 2 1 1 2 1 2 0 0 2 1 1 1 0 2 1 1 1 1 0 1 2 2 0 1 2 0 1 0 1 2 1 2 0 0 0 1 0 0 2 0 2 0 0 0 1 1 0 2 2 1 1 0 0 2 1 0 0 2 1 2 2 0 2 1 0 2 0 1 1 0 1 0 0 2 1 1 2 2 2 1 1 2 0 1 2 2 1 1 1 2 0 1 0 1 2 2 2 0 0 1 1 0 2 1 2 1 1 0 0 2 0 1 2 2 0 2 1 0 0 1 2 1 2 2 2 1 0 2 0 2 2 2 1 0 0 0 1 2 0 1 2 2 2 0 0 1 2 1 1 0 0 2 1 2 0 1 2 0 0 0 1 1 1 1 0 2 0 1 0 2 1 1 1 1 1 2 2 1 1 1 2 1 1 2 0 1 0 1 2 2 1 1 0 1 0 0 1 2 0 0 0 1 0 2 1 2 2 2 1 1 1 1 0 2 0 2 1 2 2 0 1 2 2 2 0 1 2 0 2 1 2 0 1 1 0 1 0 0 0 0 1 1 1 1 1 0 1 0 1 1 2 0 1 2 2 2 2 2 2 1 2 1 2 1 1 2 1 1 1 2 2 2 0 1 1 1 2 2 1 1 2 1 2 1 0 1 2 1 1 0 2 1 2 2 1 1 0 0 2 0 2 2 2 1 0 2 1 0 2 0 0 2 2 1 0 0 1 1 0 2 2 1 0 1 2 0 1 0 1 1 0 0 0 0 0 0 1 0 1 0 1 1 2 2 2 1 2 1 1 0 2 0 0 0 1 2 0 2 0 0 1 0 0 1 0 2 2 2 0 2 2 0 1 2 2 2 2 2 1 1 1 1 0 2 1 2 1 1 1 2 2 1 2 1 0 0 0 2 1 2 2 0 0 2 0 2 2 2 1 2 0 0 1 2 2 2 0 2 0 0 0 0 0 0 0 2 0 1 1 2 0 2 0 2 1 0 1 1 0 1 2 0 0 1 1 1 0 2 1 1 0 2 0 2 1 2 0 0 0 0 1 1 1 0 1 0 2 2
XMEEMMMXEEEXXXMXXMMXMMXEEMMMMMMMEEXMEXMMXMEXMXXMXXMMMMMXEXEMXEEMEMXXEXMMMMMXEMMMXMMEMXMEXXEEXEEXEMEMEXMXMEXEXMEEXMMMMMMXXXMEXXMEEMXMXEEMMXXMXMMMMEMMMMEMXXEMXEMEXEXXXEEXXXMXMXEMMXXXEMXMXMMMXXXEXXXXMXMEXXXMXEMEEEMMEEXXMXMEXEMXXEXMEMMXEXXXEMXEEEXEEMXMXXMXMEXEEMXXMMXEXMMMXMEMEXEEXXXEEMMXXXMMXXMXXEMMEMEXMXXMEXXEMXXXEMEEEMEEXMXXEXMEMEEEXEXXEXMMMEEEXEXEMXMXXEEMMMEEXXXXXXEXXEEEEMEXEEMMEMXMXEXXEXXEMXMXXXMEXMEMEXEMEXXEEXEEEXEEEMXEEMXEMEEEXXMEEXEXXXMEMMMXEXEMXMXMXEXEEMXXEMMEEMXEEXEXMEXXXMEEEEMXMEXMMEEXXMEE

[出力例]
1265815

[入力例]

1 1 0 2

MEEX

[出力例]

※AtCoderテストケースより

[入力例]

0 0 0

XXX

[出力例]

※AtCoderテストケースより

[入力例]

1 1 2 0 0 2 0 2 0 0 0 0 0 2 2

EXMMXXXEMEXEXMM

[出力例]

※AtCoderテストケースより

[入力例]

0 0 2 2 2 1 1 0 1 0

MMEMEMEXXM

[出力例]

[入力例]

100

0 2 1 0 2 2 0 1 1 0 1 1 0 0 0 2 1 1 2 0 0 0 2 2 0 0 0 0 1 1 2 1 0 0 1 1 1 0 0 2 0 2 2 2 2 2 0 1 2 1 0 2 0 1 0 1 2 1 0 1 2 2 1 1 1 1 2 2 1 1 2 0 1 0 1 1 1 0 0 1 1 1 0 0 0 2 1 1 1 1 1 0 2 1 1 0 0 2 1 2

MEXMMMXMXXMMXMMEEXEEEXEEEMXMXEMMMEXEXMEXEXMXXMEEEXXEMMXMEXMEXEMXMXXXEEXEMEEMXXMEXEMXEMMEMMXXXEEEEMXX

[出力例]

11356

[入力例]

500

2 1 0 0 0 0 0 2 0 1 1 2 0 1 1 0 2 0 0 0 2 0 1 1 1 0 0 0 0 2 2 1 2 1 1 2 1 2 0 0 2 1 1 1 0 2 1 1 1 1 0 1 2 2 0 1 2 0 1 0 1 2 1 2 0 0 0 1 0 0 2 0 2 0 0 0 1 1 0 2 2 1 1 0 0 2 1 0 0 2 1 2 2 0 2 1 0 2 0 1 1 0 1 0 0 2 1 1 2 2 2 1 1 2 0 1 2 2 1 1 1 2 0 1 0 1 2 2 2 0 0 1 1 0 2 1 2 1 1 0 0 2 0 1 2 2 0 2 1 0 0 1 2 1 2 2 2 1 0 2 0 2 2 2 1 0 0 0 1 2 0 1 2 2 2 0 0 1 2 1 1 0 0 2 1 2 0 1 2 0 0 0 1 1 1 1 0 2 0 1 0 2 1 1 1 1 1 2 2 1 1 1 2 1 1 2 0 1 0 1 2 2 1 1 0 1 0 0 1 2 0 0 0 1 0 2 1 2 2 2 1 1 1 1 0 2 0 2 1 2 2 0 1 2 2 2 0 1 2 0 2 1 2 0 1 1 0 1 0 0 0 0 1 1 1 1 1 0 1 0 1 1 2 0 1 2 2 2 2 2 2 1 2 1 2 1 1 2 1 1 1 2 2 2 0 1 1 1 2 2 1 1 2 1 2 1 0 1 2 1 1 0 2 1 2 2 1 1 0 0 2 0 2 2 2 1 0 2 1 0 2 0 0 2 2 1 0 0 1 1 0 2 2 1 0 1 2 0 1 0 1 1 0 0 0 0 0 0 1 0 1 0 1 1 2 2 2 1 2 1 1 0 2 0 0 0 1 2 0 2 0 0 1 0 0 1 0 2 2 2 0 2 2 0 1 2 2 2 2 2 1 1 1 1 0 2 1 2 1 1 1 2 2 1 2 1 0 0 0 2 1 2 2 0 0 2 0 2 2 2 1 2 0 0 1 2 2 2 0 2 0 0 0 0 0 0 0 2 0 1 1 2 0 2 0 2 1 0 1 1 0 1 2 0 0 1 1 1 0 2 1 1 0 2 0 2 1 2 0 0 0 0 1 1 1 0 1 0 2 2

XMEEMMMXEEEXXXMXXMMXMMXEEMMMMMMMEEXMEXMMXMEXMXXMXXMMMMMXEXEMXEEMEMXXEXMMMMMXEMMMXMMEMXMEXXEEXEEXEMEMEXMXMEXEXMEEXMMMMMMXXXMEXXMEEMXMXEEMMXXMXMMMMEMMMMEMXXEMXEMEXEXXXEEXXXMXMXEMMXXXEMXMXMMMXXXEXXXXMXMEXXXMXEMEEEMMEEXXMXMEXEMXXEXMEMMXEXXXEMXEEEXEEMXMXXMXMEXEEMXXMMXEXMMMXMEMEXEEXXXEEMMXXXMMXXMXXEMMEMEXMXXMEXXEMXXXEMEEEMEEXMXXEXMEMEEEXEXXEXMMMEEEXEXEMXMXXEEMMMEEXXXXXXEXXEEEEMEXEEMMEMXMXEXXEXXEMXMXXXMEXMEMEXEMEXXEEXEEEXEEEMXEEMXEMEEEXXMEEXEXXXMEMMMXEXEMXMXMXEXEEMXXEMMEEMXEEXEXMEXXXMEEEEMXMEXMMEEXXMEE

[出力例]

1265815

■参照サイト
CodeQUEEN 2023 予選 (AtCoder Beginner Contest 308)

2023年7月1日

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

C++の練習を兼ねて, AtCoder Regular Contest 162 の問題C (Mex Game on Tree) を解いてみた.

■感想.
1. 問題C は, 方針が見えなかったので, 解説を参考に実装したところ, AC版に到達出来た.
2. 実装に苦労したものの, 個人的には, 深さ優先探索の訓練を積めたので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/arc162/editorial/6380
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
#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

int main(){
    
    // 1. 入力情報.
    int T;
    scanf("%d", &T);
    
    // 2. dfs.
    // https://ja.wikipedia.org/wiki/深さ優先探索
    auto dfs = [](auto&& self, vvi &G, int cur, int bef, int N, int K, int* m, int* s, int* a, int* f, vvi &aCount) -> void {
        // 部分木サイズ(往路).
        ++s[cur];
        
        // 終了条件.
        if(m[cur]) return;
        
        // 訪問済みフラグ.
        m[cur] = 1;
        
        // 隣接頂点.
        for(auto &nex : G[cur]){
            if(nex == bef) continue;
            self(self, G, nex, cur, N, K, m, s, a, f, aCount);
        }
        
        // 部分木サイズ(復路).
        if(bef != -1) s[bef] += s[cur];
        
        // 書き込まれた整数(復路で調整).
        if(a[cur] != -1) ++aCount[cur][a[cur]];
        if(bef != -1) rep(i, N + 1) aCount[bef][i] += aCount[cur][i];
        
        // f[cur] = K となりうるか？
        // 0 ～ K - 1 の 未使用個数(n), -1 の頂点数(m1) を 集計.
        int n = 0, m1 = 0;
        rep(i, N + 1){
            if(i < K && !aCount[cur][i]) ++n;
            m1 += aCount[cur][i];
        }
        m1 = s[cur] - m1;
        
        // 判定(K が 使用済でないことが大前提).
        bool alice = false;
        if(!aCount[cur][K]){
            // 0 ～ K - 1 の 未使用個数 が 0個, かつ, -1 の頂点数 が 1個以下.
            if(n == 0 && m1 <= 1) alice = true;
            
            // 0 ～ K - 1 の 未使用個数 が 1個, かつ, -1 の頂点数 が 1個.
            if(n == 1 && m1 == 1) alice = true;
        }
        
        // 保存.
        f[cur] = alice;
    };
    
    // 3. テストケース.
    rep(i, T){
        // 3-1. 各テストケース.
        int N, K;
        scanf("%d %d", &N, &K);
        vvi G(N);
        repx(j, 1, N){
            int p;
            scanf("%d", &p);
            --p;
            G[p].pb(j);
            G[j].pb(p);
        }
        int a[N];
        rep(j, N) scanf("%d", &a[j]);
        
        // 3-2. 部分木.
        int subTree[N], memo[N], f[N];
        vvi aCount(N, vi(N + 1, 0));
        rep(j, N) subTree[j] = memo[j] = f[j] = 0;
        dfs(dfs, G, 0, -1, N, K, memo, subTree, a, f, aCount);
        // rep(j, N) printf("f[%d]=%d\n", j, f[j]);
        
        // 3-3. f[v] = K が 存在するか？
        bool ok = false;
        rep(j, N) if(f[j]) ok = true;
        
        // 3-4. 出力.
        printf("%s\n", ok ? "Alice" : "Bob");
    }
    return 0;
    
}

100

// 解き直し.

// https://atcoder.jp/contests/arc162/editorial/6380

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

using vvi = vector<vi>;

#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

int main(){

// 1. 入力情報.

int T;

scanf("%d", &T);

// 2. dfs.

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

auto dfs = [](auto&& self, vvi &G, int cur, int bef, int N, int K, int* m, int* s, int* a, int* f, vvi &aCount) -> void {

// 部分木サイズ(往路).

++s[cur];

// 終了条件.

if(m[cur]) return;

// 訪問済みフラグ.

m[cur] = 1;

// 隣接頂点.

for(auto &nex : G[cur]){

if(nex == bef) continue;

self(self, G, nex, cur, N, K, m, s, a, f, aCount);

}

// 部分木サイズ(復路).

if(bef != -1) s[bef] += s[cur];

// 書き込まれた整数(復路で調整).

if(a[cur] != -1) ++aCount[cur][a[cur]];

if(bef != -1) rep(i, N + 1) aCount[bef][i] += aCount[cur][i];

// f[cur] = K となりうるか？

// 0 ～ K - 1 の未使用個数(n), -1 の頂点数(m1) を集計.

int n = 0, m1 = 0;

rep(i, N + 1){

if(i < K && !aCount[cur][i]) ++n;

m1 += aCount[cur][i];

}

m1 = s[cur] - m1;

// 判定(K が使用済でないことが大前提).

bool alice = false;

if(!aCount[cur][K]){

// 0 ～ K - 1 の未使用個数が 0個, かつ, -1 の頂点数が 1個以下.

if(n == 0 && m1 <= 1) alice = true;

// 0 ～ K - 1 の未使用個数が 1個, かつ, -1 の頂点数が 1個.

if(n == 1 && m1 == 1) alice = true;

}

// 保存.

f[cur] = alice;

};

// 3. テストケース.

rep(i, T){

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

int N, K;

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

vvi G(N);

repx(j, 1, N){

int p;

scanf("%d", &p);

--p;

G[p].pb(j);

G[j].pb(p);

}

int a[N];

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

// 3-2. 部分木.

int subTree[N], memo[N], f[N];

vvi aCount(N, vi(N + 1, 0));

rep(j, N) subTree[j] = memo[j] = f[j] = 0;

dfs(dfs, G, 0, -1, N, K, memo, subTree, a, f, aCount);

// rep(j, N) printf("f[%d]=%d\n", j, f[j]);

// 3-3. f[v] = K が存在するか？

bool ok = false;

rep(j, N) if(f[j]) ok = true;

// 3-4. 出力.

printf("%s\n", ok ? "Alice" : "Bob");

}

return 0;

}

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

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

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

[出力例]
Alice
Bob
Alice
Bob
Alice

[入力例]

4 2

1 1 2

-1 -1 3 1

6 4

1 2 2 1 3

-1 -1 -1 -1 -1 -1

[出力例]

Alice

Bob

※AtCoderのテストケースより

[入力例]

5 3

1 1 3 3

1 0 -1 2 0

7 4

1 1 2 2 3 3

0 0 -1 2 2 -1 -1

11 5

1 2 3 3 2 1 7 7 9 9

0 1 -1 2 3 4 -1 2 -1 4 5

9 4

1 1 1 1 3 3 4 5

1 0 3 3 -1 0 0 -1 2

20 5

1 1 2 2 3 3 5 5 6 6 7 7 8 8 10 10 11 11 13

-1 0 4 1 2 0 1 3 -1 -1 1 3 0 2 1 2 3 1 2 3

[出力例]

Alice

Bob

Alice

Bob

Alice

■参照サイト
AtCoder Regular Contest 162

2023年6月28日

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

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

■感想.
1. 問題F は, 方針が見えなかったので, 解説を参考に実装したところ, AC版に到達出来た.
2. 個人的には, 幅優先探索の復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/abc302/editorial/6411
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
#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

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    vvi G(N + M);
    rep(i, N){
        int a;
        scanf("%d", &a);
        rep(j, a){
            int s;
            scanf("%d", &s);
            --s;
            G[i + 0].pb(s + N);
            G[s + N].pb(i + 0);
        }
    }
    
    // 2. bfs.
    // https://ja.wikipedia.org/wiki/幅優先探索
    auto bfs = [&](vvi &G, int s, int* d){
        // 空のキュー.
        queue<int> q;
        
        // 探索地点 s をキュー q に追加.
        q.push(s);
        while(!q.empty()){
            // キューから取り出す.
            int u = q.front();
            q.pop();
            
            // 隣接頂点をチェック.
            for(auto &v : G[u]) if(!d[v] && v != s) d[v] = d[u] + 1, q.push(v);
        }
    };
    int d[N + M];
    rep(i, N + M) d[i] = 0;
    bfs(G, N, d);
    
    // 3. 出力.
    printf("%d\n", d[N + M - 1] ? d[N + M - 1] / 2 - 1 : -1);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc302/editorial/6411

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

using vvi = vector<vi>;

#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

int main(){

// 1. 入力情報.

int N, M;

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

vvi G(N + M);

rep(i, N){

int a;

scanf("%d", &a);

rep(j, a){

int s;

scanf("%d", &s);

--s;

G[i + 0].pb(s + N);

G[s + N].pb(i + 0);

}

// 2. bfs.

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

auto bfs = [&](vvi &G, int s, int* d){

// 空のキュー.

queue<int> q;

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

q.push(s);

while(!q.empty()){

// キューから取り出す.

int u = q.front();

q.pop();

// 隣接頂点をチェック.

for(auto &v : G[u]) if(!d[v] && v != s) d[v] = d[u] + 1, q.push(v);

}

};

int d[N + M];

rep(i, N + M) d[i] = 0;

bfs(G, N, d);

// 3. 出力.

printf("%d\n", d[N + M - 1] ? d[N + M - 1] / 2 - 1 : -1);

return 0;

}

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

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

[入力例]
1 2
2
1 2

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

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

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

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

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

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

[出力例]
3

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

[出力例]
5

[入力例]

3 5

1 2

2 3

3 4 5

[出力例]

※AtCoderテストケースより

[入力例]

1 2

[出力例]

※AtCoderテストケースより

[入力例]

3 5

1 3

2 4

2 4 5

[出力例]

-1

※AtCoderテストケースより

[入力例]

4 8

1 3 5

1 2

2 4 7

4 6 7 8

[出力例]

※AtCoderテストケースより

[入力例]

5 10

1 2

1 3 4

3 5 6

6 8

8 9 10

[出力例]

[入力例]

8 15

1 2

2 3 4

5 6

8 9 7

5 9 10 4

10 11

12 13 11

12 14 15

[出力例]

■参照サイト
トヨタ自動車プログラミングコンテスト2023#2(AtCoder Beginner Contest 302)

2023年6月24日2023年6月24日

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

C++の練習を兼ねて, AtCoder Regular Contest 162 の問題A (Ekiden Race) ～問題B (Insertion Sort 2) を解いてみた.

■感想.
1. 問題A ～ B は, 方針が見えなかったので, 解説を参考に実装したところ, AC版に到達出来た.
2. 個人的には, 問題B で, 解説のロジックで, 操作手順を構築できることが, 非常に興味深く感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/arc162/editorial/6497
// 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 main(){
    
    // 1. 入力情報.
    int T;
    scanf("%d", &T);
    
    // 2. テストケース.
    rep(i, T){
        // 2-1. 各テストケース.
        int N;
        scanf("%d", &N);
        int p[N], pMin = N + 1, ans = 0;
        rep(j, N) scanf("%d", &p[j]);
        
        // 2-2. 累積min.
        repr(j, N - 1, 0){
            if(pMin > p[j]){
                pMin = p[j];
                ++ans;
            }
        }
        
        // 2-3. 出力.
        printf("%d\n", ans);
    }
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc162/editorial/6497

// 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 main(){

// 1. 入力情報.

int T;

scanf("%d", &T);

// 2. テストケース.

rep(i, T){

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

int N;

scanf("%d", &N);

int p[N], pMin = N + 1, ans = 0;

rep(j, N) scanf("%d", &p[j]);

// 2-2. 累積min.

repr(j, N - 1, 0){

if(pMin > p[j]){

pMin = p[j];

++ans;

}

// 2-3. 出力.

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

}

return 0;

}

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

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

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

[出力例]
1
3
3
5
3

[入力例]

2 1

1 2 3 4

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

[出力例]

※AtCoderのテストケースより

[入力例]

2 5 4 3 1

5 6 1 7 9 4 3 8 2 10

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

10 24 21 8 2 16 1 22 13 14 15 9 11 26 3 17 5 6 18 25 20 4 19 27 30 23 12 29 7 28

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

[出力例]

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

// 解き直し.
// https://atcoder.jp/contests/arc162/editorial/6532
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;
using vi = vector<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;
    scanf("%d", &N);
    vi p(N);
    rep(i, N){
        scanf("%d", &p[i]);
        --p[i];
    }
    
    // 2. 転倒数.
    int t = 0;
    rep(i, N) repx(j, i + 1, N) t += (p[i] > p[j]);
    
    // 3. 例外.
    if(t & 1){
        puts("No");
        return 0;
    }
    
    // 4. 操作手順の構築.
    vi z(N);
    iota(all(z), 0);
    int M = -1;
    vp ans;
    while(++M < 2001){
        // 4-1. 終了条件.
        if(p == z) break;
        
        // 4-2. P[m] != m となる最小の m は？
        int m = N, k = N;
        rep(i, N){
            if(i == p[i]) continue;
            if(m > p[i]){
                m = p[i];
                k = i;
            }
        }
        
        // 4-3. 操作(k = N - 1).
        vi q;
        if(k == N - 1){
            rep(i, N - 3) q.pb(p[i]);
            q.pb(p[N - 2]);
            q.pb(p[N - 1]);
            q.pb(p[N - 3]);
            ans.pb({N - 1, N - 3});
        }
        
        // 4-4. 操作(k < N - 1).
        if(k < N - 1){
            int idx = -1;
            rep(i, m) q.pb(p[i]);
            q.pb(p[k + 0]);
            q.pb(p[k + 1]);
            repx(i, m, N){
                if(i == k + 0 || i == k + 1) continue;
                q.pb(p[i]);
            }
            ans.pb({k + 1, m});
        }
        
        // 4-5. 入れ替え.
        p = q;
    }
    
    // 5. 出力.
    printf("%s\n%d\n", "Yes", M);
    for(auto &x : ans) printf("%d %d\n", x.a, x.b);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc162/editorial/6532

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using P = pair<int, int>;

using vi = vector<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;

scanf("%d", &N);

vi p(N);

rep(i, N){

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

--p[i];

}

// 2. 転倒数.

int t = 0;

rep(i, N) repx(j, i + 1, N) t += (p[i] > p[j]);

// 3. 例外.

if(t & 1){

puts("No");

return 0;

}

// 4. 操作手順の構築.

vi z(N);

iota(all(z), 0);

int M = -1;

vp ans;

while(++M < 2001){

// 4-1. 終了条件.

if(p == z) break;

// 4-2. P[m] != m となる最小の m は？

int m = N, k = N;

rep(i, N){

if(i == p[i]) continue;

if(m > p[i]){

m = p[i];

k = i;

}

// 4-3. 操作(k = N - 1).

vi q;

if(k == N - 1){

rep(i, N - 3) q.pb(p[i]);

q.pb(p[N - 2]);

q.pb(p[N - 1]);

q.pb(p[N - 3]);

ans.pb({N - 1, N - 3});

}

// 4-4. 操作(k < N - 1).

if(k < N - 1){

int idx = -1;

rep(i, m) q.pb(p[i]);

q.pb(p[k + 0]);

q.pb(p[k + 1]);

repx(i, m, N){

if(i == k + 0 || i == k + 1) continue;

q.pb(p[i]);

}

ans.pb({k + 1, m});

}

// 4-5. 入れ替え.

p = q;

}

// 5. 出力.

printf("%s\n%d\n", "Yes", M);

for(auto &x : ans) printf("%d %d\n", x.a, x.b);

return 0;

}

[入力例]
5
1 4 2 3 5

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

[入力例]
2
2 1

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

[入力例]
4
3 4 1 2

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

※但し, 上記のプログラムでは, 以下の内容が出力される.
Yes
1
3 0

[入力例]
5
1 2 3 4 5

[出力例]
Yes
0

[入力例]
5
5 3 4 1 2

[出力例]
Yes
2
4 0
4 2

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

[出力例]
No

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

[出力例]
Yes
5
3 0
5 1
4 2
6 4
6 4

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

[出力例]
Yes
8
4 0
3 1
5 2
6 3
7 4
9 5
8 6
9 7

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

[出力例]
Yes
11
11 0
8 1
10 2
9 4
14 5
8 6
11 7
13 8
11 9
14 10
14 12

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

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

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

[入力例]

1 4 2 3 5

[出力例]

Yes

3 1

※AtCoderのテストケースより

[入力例]

2 1

[出力例]

※AtCoderのテストケースより

[入力例]

3 4 1 2

[出力例]

Yes

3 0

1 2

3 0

※AtCoderのテストケースより

※但し, 上記のプログラムでは, 以下の内容が出力される.

Yes

3 0

[入力例]

1 2 3 4 5

[出力例]

Yes

[入力例]

5 3 4 1 2

[出力例]

Yes

4 0

4 2

[入力例]

2 3 5 6 1 7 4

[出力例]

[入力例]

4 7 1 3 2 6 5

[出力例]

Yes

3 0

5 1

4 2

6 4

[入力例]

2 5 3 1 4 9 10 7 6 8

[出力例]

Yes

4 0

3 1

5 2

6 3

7 4

9 5

8 6

9 7

[入力例]

8 10 5 7 9 2 15 3 4 13 1 11 12 6 14

[出力例]

Yes

11 0

8 1

10 2

9 4

14 5

8 6

11 7

13 8

11 9

14 10

14 12

[入力例]

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

[出力例]

Yes

19 0

13 1

32 2

17 4

44 5

37 6

33 7

42 8

37 9

20 10

49 47

49 11

37 12

35 13

34 14

44 15

34 16

36 17

38 18

29 19

25 20

30 21

38 22

26 23

40 24

39 25

49 47

49 26

30 27

35 28

40 29

37 30

47 31

41 32

40 33

36 34

39 35

49 47

49 36

39 37

44 39

48 40

48 41

49 42

46 43

49 45

49 47

■参照サイト
AtCoder Regular Contest 162

2023年6月18日

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

C++の練習を兼ねて, AtCoder Beginner Contest 302 の問題C (Almost Equal) ～問題E (Isolation) を解いてみた.

■感想.
1. 問題C ～ E は, 方針を絞り込めたので, AC版に到達できたと思う.
2. 個人的には, 問題E で, グラフの性質を復習できたので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vs = vector<string>;
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 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);
    vs ss;
    rep(i, N){
        char c[11];
        scanf("%s", c);
        string s(c);
        ss.pb(s);
    }
    
    // 2. 条件を満たす列は？
    vi z(N);
    iota(all(z), 0);
    string ans = "No";
    do {
        vs t;
        rep(i, N) t.pb(ss[z[i]]);
        bool ok = true;
        rep(i, N - 1){
            int c = 0;
            rep(j, M) c += (t[i][j] == t[i + 1][j]);
            if(c != M - 1) ok = false;
        }
        if(ok){
            ans = "Yes";
            break;
        }
    } while(next_permutation(all(z)));
    
    // 3. 出力.
    printf("%s\n", ans.c_str());
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vs = vector<string>;

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

vs ss;

rep(i, N){

char c[11];

scanf("%s", c);

string s(c);

ss.pb(s);

}

// 2. 条件を満たす列は？

vi z(N);

iota(all(z), 0);

string ans = "No";

do {

vs t;

rep(i, N) t.pb(ss[z[i]]);

bool ok = true;

rep(i, N - 1){

int c = 0;

rep(j, M) c += (t[i][j] == t[i + 1][j]);

if(c != M - 1) ok = false;

}

if(ok){

ans = "Yes";

break;

}

} while(next_permutation(all(z)));

// 3. 出力.

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

return 0;

}

[入力例]
4 4
bbed
abcd
abed
fbed

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

[入力例]
2 5
abcde
abced

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

[入力例]
8 4
fast
face
cast
race
fact
rice
nice
case

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

[入力例]
6 5
peach
ppple
peale
peple
peace
apple

[出力例]
Yes

[入力例]
3 5
mango
mengo
melon

[出力例]
No

[入力例]
12 6
almond
chssis
aherry
alerry
chesis
almory
cherry
almony
cherrs
cheris
almrry
cassis

[出力例]
Yes
※整数 N, M が, 問題文の制約条件から範囲外であるケース.

[入力例]

4 4

bbed

abcd

abed

fbed

[出力例]

Yes

※AtCoderテストケースより

[入力例]

2 5

abcde

abced

[出力例]

※AtCoderテストケースより

[入力例]

8 4

fast

face

cast

race

fact

rice

nice

case

[出力例]

※AtCoderテストケースより

[入力例]

6 5

peach

ppple

peale

peple

peace

apple

[出力例]

Yes

[入力例]

3 5

mango

mengo

melon

[出力例]

[入力例]

12 6

almond

chssis

aherry

alerry

chesis

almory

cherry

almony

cherrs

cheris

almrry

cassis

[出力例]

Yes

※整数 N, M が, 問題文の制約条件から範囲外であるケース.

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

// 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 all(x) x.begin(), x.end()

int main(){
    
    // 1. 入力情報.
    int N, M;
    LL D;
    scanf("%d %d %lld", &N, &M, &D);
    vl a(N), b(M);
    rep(i, N) scanf("%lld", &a[i]);
    rep(i, M) scanf("%lld", &b[i]);
    
    // 2. sort.
    sort(all(a));
    sort(all(b));
    
    // 3. 贈り物の価値の和の最大値は？
    LL ans = -1;
    rep(i, N){
        // 下限.
        int j = lower_bound(all(b), a[i] - D) - b.begin();
        if(j == M) --j;
        if(abs(a[i] - b[j]) <= D) ans = max(ans, a[i] + b[j]);
        
        // 上限.
        j = lower_bound(all(b), a[i] + D) - b.begin();
        if(j == M) --j;
        if(abs(a[i] - b[j]) <= D) ans = max(ans, a[i] + b[j]);
    }
    
    // 4. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 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 all(x) x.begin(), x.end()

int main(){

// 1. 入力情報.

int N, M;

LL D;

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

vl a(N), b(M);

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

rep(i, M) scanf("%lld", &b[i]);

// 2. sort.

sort(all(a));

sort(all(b));

// 3. 贈り物の価値の和の最大値は？

LL ans = -1;

rep(i, N){

// 下限.

int j = lower_bound(all(b), a[i] - D) - b.begin();

if(j == M) --j;

if(abs(a[i] - b[j]) <= D) ans = max(ans, a[i] + b[j]);

// 上限.

j = lower_bound(all(b), a[i] + D) - b.begin();

if(j == M) --j;

if(abs(a[i] - b[j]) <= D) ans = max(ans, a[i] + b[j]);

}

// 4. 出力.

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

return 0;

}

[入力例]
2 3 2
3 10
2 5 15

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

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

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

[入力例]
1 1 1000000000000000000
1000000000000000000
1000000000000000000

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

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

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

[入力例]
10 15 33
2 14 35 28 31 93 101 11 50 109
109 99 87 39 101 113 4 111 79 97 3 19 64 73 108

[出力例]
222

[入力例]
150 150 12345
29315 62041 88435 30962 108342 98665 72206 75580 82745 70105 101998 63827 58428 42596 29561 50404 72526 69050 55709 70445 68274 106379 50469 106719 46598 29782 85795 61712 78407 74611 60350 80264 46298 48622 49142 103791 80946 84109 111328 94370 39094 25431 73386 34178 111000 84267 75779 21706 18091 20078 56393 35562 111319 99360 38846 94907 51755 109372 76783 31346 31462 82198 82720 62795 45231 82800 56334 51967 62878 106704 84073 74117 107228 84205 39582 22300 96337 95778 59807 68475 87081 92427 16764 54567 98948 94276 44480 73132 75536 111138 65747 61867 54304 93939 14337 73368 21742 103551 15748 105197 24708 24563 34747 27392 57874 69158 99289 56249 92557 16447 109913 75772 41517 103713 31983 55702 80392 80688 100564 17154 51857 93403 57836 49412 85462 29513 100445 95726 69441 107026 71043 51406 98733 56138 36554 105099 90159 68202 23212 36646 47958 22722 42933 67280 61845 33234 105603 86333 34412 53028
60787 110103 29371 110894 30087 48699 28676 78336 74869 57500 56756 46546 37384 63364 23510 84577 99265 27770 62039 71736 88130 60640 35491 74785 72217 54189 71155 54038 75022 90588 21577 28828 40681 20374 60882 48587 88796 86334 82568 48818 46683 39930 95201 18876 28074 21336 40545 40769 47797 47354 39012 65010 48130 30273 84531 24012 97205 77083 71350 38229 76499 105789 47724 41761 90861 42086 53687 104844 22783 63669 13650 109988 32651 64522 19166 47357 29940 95228 63995 21455 25043 26304 68528 46581 40259 57392 83122 32753 17369 78788 38892 85916 14269 25745 68023 85569 44178 14915 82560 24233 49087 73222 60376 109596 34480 66875 43698 35218 44358 51197 38378 80109 95652 21125 53259 102847 47722 58953 36099 63642 93494 75552 84131 58441 104331 46576 55196 75272 47702 61211 106846 26586 75321 88512 83834 19559 110055 77270 35582 87882 17262 21208 99715 34379 94776 55994 73831 21843 23720 81490

[出力例]
222222

[入力例]

2 3 2

3 10

2 5 15

[出力例]

※AtCoderテストケースより

[入力例]

3 3 0

1 3 3

6 2 7

[出力例]

-1

※AtCoderテストケースより

[入力例]

1 1 1000000000000000000

1000000000000000000

[出力例]

2000000000000000000

※AtCoderテストケースより

[入力例]

8 6 1

2 5 6 5 2 1 7 9

7 2 5 5 2 4

[出力例]

※AtCoderテストケースより

[入力例]

10 15 33

2 14 35 28 31 93 101 11 50 109

109 99 87 39 101 113 4 111 79 97 3 19 64 73 108

[出力例]

222

[入力例]

150 150 12345

29315 62041 88435 30962 108342 98665 72206 75580 82745 70105 101998 63827 58428 42596 29561 50404 72526 69050 55709 70445 68274 106379 50469 106719 46598 29782 85795 61712 78407 74611 60350 80264 46298 48622 49142 103791 80946 84109 111328 94370 39094 25431 73386 34178 111000 84267 75779 21706 18091 20078 56393 35562 111319 99360 38846 94907 51755 109372 76783 31346 31462 82198 82720 62795 45231 82800 56334 51967 62878 106704 84073 74117 107228 84205 39582 22300 96337 95778 59807 68475 87081 92427 16764 54567 98948 94276 44480 73132 75536 111138 65747 61867 54304 93939 14337 73368 21742 103551 15748 105197 24708 24563 34747 27392 57874 69158 99289 56249 92557 16447 109913 75772 41517 103713 31983 55702 80392 80688 100564 17154 51857 93403 57836 49412 85462 29513 100445 95726 69441 107026 71043 51406 98733 56138 36554 105099 90159 68202 23212 36646 47958 22722 42933 67280 61845 33234 105603 86333 34412 53028

60787 110103 29371 110894 30087 48699 28676 78336 74869 57500 56756 46546 37384 63364 23510 84577 99265 27770 62039 71736 88130 60640 35491 74785 72217 54189 71155 54038 75022 90588 21577 28828 40681 20374 60882 48587 88796 86334 82568 48818 46683 39930 95201 18876 28074 21336 40545 40769 47797 47354 39012 65010 48130 30273 84531 24012 97205 77083 71350 38229 76499 105789 47724 41761 90861 42086 53687 104844 22783 63669 13650 109988 32651 64522 19166 47357 29940 95228 63995 21455 25043 26304 68528 46581 40259 57392 83122 32753 17369 78788 38892 85916 14269 25745 68023 85569 44178 14915 82560 24233 49087 73222 60376 109596 34480 66875 43698 35218 44358 51197 38378 80109 95652 21125 53259 102847 47722 58953 36099 63642 93494 75552 84131 58441 104331 46576 55196 75272 47702 61211 106846 26586 75321 88512 83834 19559 110055 77270 35582 87882 17262 21208 99715 34379 94776 55994 73831 21843 23720 81490

[出力例]

222222

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

// 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 main(){
    
    // 1. 入力情報.
    int N, Q;
    scanf("%d %d", &N, &Q);
    set<int> G[N];
    int ans = N;
    
    // 2. クエリ回答.
    rep(i, Q){
        // 2-1. クエリタイプ.
        int t;
        scanf("%d", &t);
        
        // 2-2. 操作 1.
        if(t == 1){
            int u, v;
            scanf("%d %d", &u, &v);
            --u, --v;
            
            // 他のどの頂点とも辺で結ばれていない頂点の数.
            ans -= (G[u].size() == 0);
            ans -= (G[v].size() == 0);
            
            // 辺追加.
            G[u].insert(v);
            G[v].insert(u);
        }
        
        // 2-3. 操作 2.
        if(t == 2){
            int v;
            scanf("%d", &v);
            --v;
            
            // 他のどの頂点とも辺で結ばれていない頂点の数.
            if(G[v].size()) ++ans;
            for(auto &x : G[v]) ans += (G[x].size() == 1);
            
            // 辺削除.
            for(auto &x : G[v]) G[x].erase(v);
            G[v].clear();
        }
        
        // 2-4. 出力.
        printf("%d\n", ans);
        
    }
    return 0;
    
}

// 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 main(){

// 1. 入力情報.

int N, Q;

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

set<int> G[N];

int ans = N;

// 2. クエリ回答.

rep(i, Q){

// 2-1. クエリタイプ.

int t;

scanf("%d", &t);

// 2-2. 操作 1.

if(t == 1){

int u, v;

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

--u, --v;

// 他のどの頂点とも辺で結ばれていない頂点の数.

ans -= (G[u].size() == 0);

ans -= (G[v].size() == 0);

// 辺追加.

G[u].insert(v);

G[v].insert(u);

}

// 2-3. 操作 2.

if(t == 2){

int v;

scanf("%d", &v);

--v;

// 他のどの頂点とも辺で結ばれていない頂点の数.

if(G[v].size()) ++ans;

for(auto &x : G[v]) ans += (G[x].size() == 1);

// 辺削除.

for(auto &x : G[v]) G[x].erase(v);

G[v].clear();

}

// 2-4. 出力.

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

}

return 0;

}

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

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

[入力例]
2 1
2 1

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

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

[出力例]
3
1
1
2
1
3
5
3
2
1
0
0
1
2
5

[入力例]

3 7

1 1 2

1 1 3

1 2 3

2 1

1 1 2

2 2

1 1 2

[出力例]

※AtCoderテストケースより

[入力例]

2 1

[出力例]

※AtCoderテストケースより

[入力例]

5 15

1 1 3

1 5 4

1 3 4

2 1

1 2 3

2 4

2 3

1 1 5

1 1 3

1 3 4

1 2 5

1 1 2

2 2

2 5

2 3

[出力例]

■参照サイト
トヨタ自動車プログラミングコンテスト2023#2(AtCoder Beginner Contest 302)

2023年6月11日

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

C++の練習を兼ねて, AtCoder Beginner Contest 303 の問題E (A Gift From the Stars) を解いてみた.

■感想.
1. 問題Eは, 方針を絞り込めたので, AC版に到達できたと思う.
2. 個人的には, グラフの性質を復習できたので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// C++(GCC 9.2.1)
#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 all(x) x.begin(), x.end()
#define pb push_back

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    set<int> G[N];
    rep(i, N - 1){
        int u, v;
        scanf("%d %d", &u, &v);
        --u, --v;
        G[u].insert(v);
        G[v].insert(u);
    }
    
    // 2. 葉っぱを保存.
    queue<int> q;
    rep(i, N) if(G[i].size() == 1) q.push(i);
    
    // 3. 星を抽出.
    vi ans;
    while(!q.empty()){
        // キューから取り出す.
        int u = q.front();
        q.pop();
        
        // 次数がゼロか？
        if(!G[u].size()) continue;
        
        // 星 の 中心.
        int s = *G[u].begin();
        
        // レベル保存.
        ans.pb(G[s].size());
            
        // 隣接頂点.
        for(auto &s1 : G[s]){
            // 星を構成する辺を削除.
            G[s1].erase(s);
            
            // 星を構成する頂点を処理.
            for(auto &s2 : G[s1]){
                // Skip.
                if(s == s2) continue;
                
                // 星どうしを結ぶ辺を削除.
                G[s2].erase(s1);
                
                // 新たな葉っぱを追加.
                if(G[s2].size() == 1) q.push(s2);
            }
            
            // 星を構成する頂点を削除.
            G[s1].clear();
        }
        
        // 星 を 削除.
        G[s].clear();
    }
    
    // 4. sort.
    sort(all(ans));
    
    // 5. 出力.
    int n = ans.size();
    rep(i, n) printf("%d%s", ans[i], (i < n - 1) ? " " : "\n");
    return 0;
    
}

// C++(GCC 9.2.1)

#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 all(x) x.begin(), x.end()

#define pb push_back

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

set<int> G[N];

rep(i, N - 1){

int u, v;

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

--u, --v;

G[u].insert(v);

G[v].insert(u);

}

// 2. 葉っぱを保存.

queue<int> q;

rep(i, N) if(G[i].size() == 1) q.push(i);

// 3. 星を抽出.

vi ans;

while(!q.empty()){

// キューから取り出す.

int u = q.front();

q.pop();

// 次数がゼロか？

if(!G[u].size()) continue;

// 星の中心.

int s = *G[u].begin();

// レベル保存.

ans.pb(G[s].size());

// 隣接頂点.

for(auto &s1 : G[s]){

// 星を構成する辺を削除.

G[s1].erase(s);

// 星を構成する頂点を処理.

for(auto &s2 : G[s1]){

// Skip.

if(s == s2) continue;

// 星どうしを結ぶ辺を削除.

G[s2].erase(s1);

// 新たな葉っぱを追加.

if(G[s2].size() == 1) q.push(s2);

}

// 星を構成する頂点を削除.

G[s1].clear();

}

// 星を削除.

G[s].clear();

}

// 4. sort.

sort(all(ans));

// 5. 出力.

int n = ans.size();

rep(i, n) printf("%d%s", ans[i], (i < n - 1) ? " " : "\n");

return 0;

}

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

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

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

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

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

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

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

[出力例]
2 2 2 2 3 3 5 5

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

[出力例]
2 3 3 4 5 8 10

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

[入力例]

1 2

2 3

3 4

4 5

5 6

[出力例]

2 2

※AtCoderテストケースより

[入力例]

3 9

7 8

8 6

4 6

4 1

5 9

7 3

5 2

[出力例]

2 2 2

※AtCoderテストケースより

[入力例]

8 3

8 18

2 19

8 20

9 17

19 7

8 7

14 12

2 15

14 10

2 13

2 16

2 1

9 5

10 15

14 6

2 4

2 11

5 12

[出力例]

2 3 4 7

※AtCoderテストケースより

[入力例]

1 2

5 2

3 2

3 4

6 3

4 7

7 12

4 8

13 8

19 13

9 6

20 9

9 11

14 9

10 9

11 18

18 21

22 21

17 10

15 10

16 10

33 28

28 32

28 31

28 30

28 29

15 25

25 26

25 27

23 16

24 23

17 33

[出力例]

2 2 2 2 3 3 5 5

[入力例]

1 2

1 3

1 4

5 4

6 5

24 5

9 5

15 5

6 7

7 8

10 9

10 14

10 12

10 13

10 11

25 30

25 28

25 26

25 31

25 27

25 32

25 29

24 25

16 15

16 17

18 16

19 18

20 19

21 20

23 20

22 20

33 22

34 33

39 34

40 34

41 34

37 34

43 34

36 34

42 34

35 34

38 34

[出力例]

2 3 3 4 5 8 10

■参照サイト
日鉄ソリューションズプログラミングコンテスト2023（AtCoder Beginner Contest 303）

2023年6月10日

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

C++の練習を兼ねて, AtCoder Beginner Contest 303 の問題C (Dash) ～問題D (Shift vs. CapsLock) を解いてみた.

■感想.
1. 問題C, Dは, 方針を絞り込めたので, AC版に到達できたと思う.
2. 個人的には, 苦手な動的計画法の訓練を積めたので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 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 a first
#define b second

int main(){
    
    // 1. 入力情報.
    int N, M, H, K;
    char c[202020];
    scanf("%d %d %d %d %s", &N, &M, &H, &K, c);
    string S(c);
    set<P> st;
    rep(i, M){
        int x, y;
        scanf("%d %d", &x, &y);
        st.insert({x, y});
    }
    
    // 2. 移動.
    P cur = {0, 0};
    bool ok = true;
    rep(i, N){
        // 2-1. 体力消費.
        --H;
        
        // 2-2. 判定.
        if(H < 0){
            ok = false;
            break;
        }
        
        // 2-3. 移動.
        if(S[i] == 'R') ++cur.a;
        if(S[i] == 'L') --cur.a;
        if(S[i] == 'U') ++cur.b;
        if(S[i] == 'D') --cur.b;
        
        // 2-4. 体力回復.
        if(H < K && st.count(cur)){
            st.erase(cur);
            H = K;
        }
    }
    
    // 3. 出力.
    printf("%s\n", ok ? "Yes" : "No");
    return 0;
    
}

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

#define b second

int main(){

// 1. 入力情報.

int N, M, H, K;

char c[202020];

scanf("%d %d %d %d %s", &N, &M, &H, &K, c);

string S(c);

set<P> st;

rep(i, M){

int x, y;

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

st.insert({x, y});

}

// 2. 移動.

P cur = {0, 0};

bool ok = true;

rep(i, N){

// 2-1. 体力消費.

--H;

// 2-2. 判定.

if(H < 0){

ok = false;

break;

}

// 2-3. 移動.

if(S[i] == 'R') ++cur.a;

if(S[i] == 'L') --cur.a;

if(S[i] == 'U') ++cur.b;

if(S[i] == 'D') --cur.b;

// 2-4. 体力回復.

if(H < K && st.count(cur)){

st.erase(cur);

H = K;

}

// 3. 出力.

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

return 0;

}

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

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

[入力例]
5 2 1 5
LDRLD
0 0
-1 -1

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

[入力例]
10 7 10 3
RULUDRDLDL
-2 1
1 3
-7 1
-2 -1
-6 1
-3 2
-3 1

[出力例]
Yes

[入力例]
100 15 20 5
RUDDRLULURLDULUDURRDRDRLRLURDDULRDRULULDRURUDULRURDRLUURRRLLRDDDUURRLLUDUDLUURDUUURLULDULLUDLRULUUUU
7 -7
-4 3
5 -9
-2 -3
6 -3
1 -8
4 -4
-5 -10
6 7
10 -7
6 2
-7 -1
-10 -7
5 -10
-4 -2

[出力例]
No

[入力例]
250 25 30 32
DRRUDRULRULRUDLDLDLLUDUURULUULDLUDRUURRURDRLURLLRRRLUDLLLRLRDDUDRUUDRRUDLRUDLDUULRUULLRUUUDDLULDURRLRRDURRULLRDRLRDRUULLDLDRLDLDLULDUUURLUURRRLURULDLURDLRLLURDRURRURRLUULLUDLULURUURRDRRDDRRLRLULURDULULRUDLUDLUDLURDLRULDRULRDLULDULDRUUDDUUDDUDLDLDURUR
7 8
6 7
-9 2
6 4
5 6
-2 -5
-1 2
1 3
-4 4
-1 -2
3 -3
-2 5
2 -8
3 1
3 -5
3 21
-1 3
0 20
1 4
2 22
1 21
0 13
1 7
-2 3
-1 9

[出力例]
Yes

[入力例]

4 2 3 1

RUDL

-1 -1

1 0

[出力例]

Yes

※AtCoderテストケースより

[入力例]

5 2 1 5

LDRLD

0 0

-1 -1

[出力例]

※AtCoderテストケースより

[入力例]

10 7 10 3

RULUDRDLDL

-2 1

1 3

-7 1

-2 -1

-6 1

-3 2

-3 1

[出力例]

Yes

[入力例]

100 15 20 5

RUDDRLULURLDULUDURRDRDRLRLURDDULRDRULULDRURUDULRURDRLUURRRLLRDDDUURRLLUDUDLUURDUUURLULDULLUDLRULUUUU

7 -7

-4 3

5 -9

-2 -3

6 -3

1 -8

4 -4

-5 -10

6 7

10 -7

6 2

-7 -1

-10 -7

5 -10

-4 -2

[出力例]

[入力例]

250 25 30 32

DRRUDRULRULRUDLDLDLLUDUURULUULDLUDRUURRURDRLURLLRRRLUDLLLRLRDDUDRUUDRRUDLRUDLDUULRUULLRUUUDDLULDURRLRRDURRULLRDRLRDRUULLDLDRLDLDLULDUUURLUURRRLURULDLURDLRLLURDRURRURRLUULLUDLULURUURRDRRDDRRLRLULURDULULRUDLUDLUDLURDLRULDRULRDLULDULDRUUDDUUDDUDLDLDURUR

7 8

6 7

-9 2

6 4

5 6

-2 -5

-1 2

1 3

-4 4

-1 -2

3 -3

-2 5

2 -8

3 1

3 -5

3 21

-1 3

0 20

1 4

2 22

1 21

0 13

1 7

-2 3

-1 9

[出力例]

Yes

■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--)
LL dp[303030][2];

int main(){
    
    // 1. 入力情報.
    LL X, Y, Z;
    scanf("%lld %lld %lld", &X, &Y, &Z);
    char c[303030];
    scanf("%s", c);
    string S(c);
    int N = S.size();
    
    // 2. dp更新.
    dp[0][1] = Z;
    rep(i, N){
        if(S[i] == 'a'){
            dp[i + 1][0] = X + min(dp[i][0], dp[i][1] + Z);
            dp[i + 1][1] = Y + min(dp[i][0] + Z, dp[i][1]);
        }
        if(S[i] == 'A'){
            dp[i + 1][0] = Y + min(dp[i][0], dp[i][1] + Z);
            dp[i + 1][1] = X + min(dp[i][0] + Z, dp[i][1]);
        }
    }
    
    // 3. 出力.
    printf("%lld\n", min(dp[N][0], dp[N][1]));
    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 dp[303030][2];

int main(){

// 1. 入力情報.

LL X, Y, Z;

scanf("%lld %lld %lld", &X, &Y, &Z);

char c[303030];

scanf("%s", c);

string S(c);

int N = S.size();

// 2. dp更新.

dp[0][1] = Z;

rep(i, N){

if(S[i] == 'a'){

dp[i + 1][0] = X + min(dp[i][0], dp[i][1] + Z);

dp[i + 1][1] = Y + min(dp[i][0] + Z, dp[i][1]);

}

if(S[i] == 'A'){

dp[i + 1][0] = Y + min(dp[i][0], dp[i][1] + Z);

dp[i + 1][1] = X + min(dp[i][0] + Z, dp[i][1]);

}

// 3. 出力.

printf("%lld\n", min(dp[N][0], dp[N][1]));

return 0;

}

[入力例]
1 3 3
AAaA

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

[入力例]
1 1 100
aAaAaA

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

[入力例]
1 2 4
aaAaAaaAAAAaAaaAaAAaaaAAAAA

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

[入力例]
7 5 3
aAAAAAaAaAAaaaAaaaAaAAAAAAaaaAAaAaaAAAAaaaaaAaaAAAaaAAaaaAAAAaaAAaaaaaaAAaaAAaAaAaaaaaAaAaAaaaAAaAaA

[出力例]
578

[入力例]
2022 2023 2024
aAAAAaAaaaaaAAaaaaAAaaaaAaAAAaAAAAaaAaaaAaAaAAAAAAAaAAAAAaAaAAaaAaAAAAaAAAAAaaAAAAaAAaAAAaaaAaAAaaaaAaAAAAAAaaAAaAAaAAaaaaaaaaaAaaAaAAaAAAAAAaaaaaAaAAAaAaaAaAaaAaaAaaaaAAaaaAAaaaaAAaaAaaAaAaAAAaAaaAaaAAAaaaaaaaAAaaAAaaaAAAaaAAAaaaAaAAaAAaaAaaAAAaAAaAAAAaaAAaaAaaaAaAaAaaAaAAaAaAaAAAAaaAaAaAAaAAAaAAAaaaaAAaAAAaaaAAAaaAaaaaAAaAaAaAaAaAAaaAAaAAaAAAaaaAAAAaAaAaAaAAAaaAAAAAAAAaAAaaaaaAaaAaaAaaaAAAAaaaaAaaaAAAaaAAAAAAaaAAAaAaAaAAAaaAaAAAAaaAAaAaaaAaaAaaAAAaaAAAaaaaaaaaAAaaAaAaaAAaAaaAaAAaAAAAAAaAaaAAaA

[出力例]
1011261

[入力例]

1 3 3

AAaA

[出力例]

※AtCoderテストケースより

[入力例]

1 1 100

aAaAaA

[出力例]

※AtCoderテストケースより

[入力例]

1 2 4

aaAaAaaAAAAaAaaAaAAaaaAAAAA

[出力例]

※AtCoderテストケースより

[入力例]

7 5 3

aAAAAAaAaAAaaaAaaaAaAAAAAAaaaAAaAaaAAAAaaaaaAaaAAAaaAAaaaAAAAaaAAaaaaaaAAaaAAaAaAaaaaaAaAaAaaaAAaAaA

[出力例]

578

[入力例]

2022 2023 2024

aAAAAaAaaaaaAAaaaaAAaaaaAaAAAaAAAAaaAaaaAaAaAAAAAAAaAAAAAaAaAAaaAaAAAAaAAAAAaaAAAAaAAaAAAaaaAaAAaaaaAaAAAAAAaaAAaAAaAAaaaaaaaaaAaaAaAAaAAAAAAaaaaaAaAAAaAaaAaAaaAaaAaaaaAAaaaAAaaaaAAaaAaaAaAaAAAaAaaAaaAAAaaaaaaaAAaaAAaaaAAAaaAAAaaaAaAAaAAaaAaaAAAaAAaAAAAaaAAaaAaaaAaAaAaaAaAAaAaAaAAAAaaAaAaAAaAAAaAAAaaaaAAaAAAaaaAAAaaAaaaaAAaAaAaAaAaAAaaAAaAAaAAAaaaAAAAaAaAaAaAAAaaAAAAAAAAaAAaaaaaAaaAaaAaaaAAAAaaaaAaaaAAAaaAAAAAAaaAAAaAaAaAAAaaAaAAAAaaAAaAaaaAaaAaaAAAaaAAAaaaaaaaaAAaaAaAaaAAaAaaAaAAaAAAAAAaAaaAAaA

[出力例]

1011261

■参照サイト
日鉄ソリューションズプログラミングコンテスト2023（AtCoder Beginner Contest 303）

2023年6月2日

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

C++の練習を兼ねて, AtCoder Regular Contest 161 の問題A (Make M) ～問題B (Exactly Three Bits) を解いてみた.

■感想.
1. 問題A, Bは, 方針を絞り込めたので, AC版に到達できたと思う.
2. 個人的には, 問題B で再帰処理の復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// C++(GCC 9.2.1)
#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 all(x) x.begin(), x.end()

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    vi a(N);
    rep(i, N) scanf("%d", &a[i]);
    
    // 2. sort.
    sort(all(a));
    
    // 3. 整数列 S.
    vi s(N);
    rep(i, N / 2 + 1) s[2 * i] = a[i];
    repx(i, N / 2 + 1, N) s[2 * (i - N / 2) - 1] = a[i];
    
    // 4. M型チェック.
    bool ok = true;
    repex(i, 1, N - 1, 2){
        // s[i - 1] < s[i] かつ, s[i] > s[i + 1] か？
        if(s[i - 1] < s[i] && s[i] > s[i + 1]) continue;
        else                                   ok = false;
    }
    
    // 5. 出力.
    printf("%s\n", ok ? "Yes" : "No");
    return 0;
    
}

// C++(GCC 9.2.1)

#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 all(x) x.begin(), x.end()

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

vi a(N);

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

// 2. sort.

sort(all(a));

// 3. 整数列 S.

vi s(N);

rep(i, N / 2 + 1) s[2 * i] = a[i];

repx(i, N / 2 + 1, N) s[2 * (i - N / 2) - 1] = a[i];

// 4. M型チェック.

bool ok = true;

repex(i, 1, N - 1, 2){

// s[i - 1] < s[i] かつ, s[i] > s[i + 1] か？

if(s[i - 1] < s[i] && s[i] > s[i + 1]) continue;

else ok = false;

}

// 5. 出力.

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

return 0;

}

[入力例]
5
1 2 3 4 5

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

[入力例]
5
1 6 1 6 1

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

[入力例]
5
1 6 6 6 1

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

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

[出力例]
Yes

[入力例]
9
7 9 3 5 5 5 5 5 10

[出力例]
No

[入力例]
21
12 1 12 1 2 7 4 15 7 3 10 1 8 12 15 6 1 7 3 10 8

[出力例]
Yes

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

[出力例]
Yes

[入力例]

1 2 3 4 5

[出力例]

Yes

※AtCoderのテストケースより

[入力例]

1 6 1 6 1

[出力例]

Yes

※AtCoderのテストケースより

[入力例]

1 6 6 6 1

[出力例]

※AtCoderのテストケースより

[入力例]

1 5 3 7 5 5 3

[出力例]

Yes

[入力例]

7 9 3 5 5 5 5 5 10

[出力例]

[入力例]

12 1 12 1 2 7 4 15 7 3 10 1 8 12 15 6 1 7 3 10 8

[出力例]

Yes

[入力例]

101

5 5 8 10 3 4 2 8 6 8 8 10 2 4 6 9 10 9 3 9 1 6 2 6 8 4 7 3 1 4 2 1 2 4 4 1 9 6 8 5 6 4 2 6 4 3 4 7 2 8 2 6 2 6 5 10 2 4 8 7 3 5 3 1 7 7 5 5 1 1 8 7 3 10 9 6 7 4 6 6 6 1 7 2 4 6 9 5 5 10 9 9 6 10 8 4 5 9 6 10 3

[出力例]

Yes

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

int main(){
    
    // 1. 入力情報.
    int T;
    scanf("%d", &T);
    
    // 2. f(X).
    auto dfs = [&](auto&& self, LL n) -> LL {
        // 2-1. 終了条件.
        if(n < 7) return -1;
        
        // 2-2. 3個.
        int bits = __builtin_popcountll(n);
        if(bits == 3) return n;
        
        // 2-3. 3個より多い.
        if(bits > 3){
            LL ret = 0;
            int u = 3;
            repr(i, 60, 0){
                if(n & (1LL << i)){
                    --u;
                    ret += (1LL << i);
                }
                if(!u) break;
            }
            return ret;
        }
        
        // 2-4. 上記以外.
        return self(self, n - 1);
    };
        
    // 3. テストケース.
    rep(i, T){
        LL N;
        scanf("%lld", &N);
        printf("%lld\n", dfs(dfs, N));
    }
    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 main(){

// 1. 入力情報.

int T;

scanf("%d", &T);

// 2. f(X).

auto dfs = [&](auto&& self, LL n) -> LL {

// 2-1. 終了条件.

if(n < 7) return -1;

// 2-2. 3個.

int bits = __builtin_popcountll(n);

if(bits == 3) return n;

// 2-3. 3個より多い.

if(bits > 3){

LL ret = 0;

int u = 3;

repr(i, 60, 0){

if(n & (1LL << i)){

--u;

ret += (1LL << i);

}

if(!u) break;

}

return ret;

}

// 2-4. 上記以外.

return self(self, n - 1);

};

// 3. テストケース.

rep(i, T){

LL N;

scanf("%lld", &N);

printf("%lld\n", dfs(dfs, N));

}

return 0;

}

[入力例]
4
16
161
4
1000000000000000000

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

[入力例]
30
1
2
3
4
5
6
7
8
9
10
11
25
32
34
63
102
144
299
1024
9475
12345
67108866
536870916
12345654321
1099511627777
123456787654321
1225899906842624
36528797018963988
567460752303423488
999999999999999999

[出力例]
-1
-1
-1
-1
-1
-1
7
7
7
7
11
25
28
28
56
100
140
296
896
9472
12320
58720256
536870915
11811160064
962072674304
123145302310912
1213860837064704
36451009484029952
504403158265495552
936748722493063168

[入力例]

161

1000000000000000000

[出力例]

161

-1

936748722493063168

※AtCoderのテストケースより

[入力例]

102

144

299

1024

9475

12345

67108866

536870916

12345654321

1099511627777

123456787654321

1225899906842624

36528797018963988

567460752303423488

999999999999999999

[出力例]

-1

100

140

296

896

9472

12320

58720256

536870915

11811160064

962072674304

123145302310912

1213860837064704

36451009484029952

504403158265495552

936748722493063168

■参照サイト
AtCoder Regular Contest 161

C++の練習を兼ねて, AtCoder Beginner Contest 309 の 問題C (Medicine) ～ 問題E (Family and Insurance) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 308 の 問題F (Vouchers) ～ 問題G (Minimum Xor Pair Query) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 308 の 問題C (Standings) ～ 問題E (MEX) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 162 の 問題C (Mex Game on Tree) を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 162 の 問題A (Ekiden Race) ～ 問題B (Insertion Sort 2) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 302 の 問題C (Almost Equal) ～ 問題E (Isolation) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 303 の 問題E (A Gift From the Stars) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 303 の 問題C (Dash) ～ 問題D (Shift vs. CapsLock) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 161 の 問題A (Make M) ～ 問題B (Exactly Three Bits) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 309 の問題C (Medicine) ～問題E (Family and Insurance) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 308 の問題F (Vouchers) ～問題G (Minimum Xor Pair Query) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 308 の問題C (Standings) ～問題E (MEX) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 162 の問題C (Mex Game on Tree) を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 162 の問題A (Ekiden Race) ～問題B (Insertion Sort 2) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 302 の問題C (Almost Equal) ～問題E (Isolation) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 303 の問題E (A Gift From the Stars) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 303 の問題C (Dash) ～問題D (Shift vs. CapsLock) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 161 の問題A (Make M) ～問題B (Exactly Three Bits) を解いてみた.