個人用メモ帳

2023年5月19日

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

C++の練習を兼ねて, AtCoder Beginner Contest 260 の問題F (Find 4-cycle) を解いてみた.

■感想.
1. 問題Fは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 解説のロジックで, 4-cycle の存在をチェックできる点が興味深く思った.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/abc260/editorial/4437
// 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 S, T, M;
    scanf("%d %d %d", &S, &T, &M);
    vvi L(S);
    rep(i, M){
        int u, v;
        scanf("%d %d", &u, &v);
        --u, --v;
        
        // 隣接リスト.
        L[u].pb(v);
    }
    
    // 2. 二次元配列.
    int matrix[3030][3030];
    rep(i, 3030) rep(j, 3030) matrix[i][j] = -1;
    
    // 3. 探索.
    rep(z, S){
        for(auto &x : L[z]){
            for(auto &y : L[z]){
                // Skip.
                if(x == y) continue;
                
                // -1 の 場合.
                if(matrix[x - S][y - S] == -1){
                    matrix[x - S][y - S] = z;
                    continue;
                }
                
                // 4-cycle あり.
                int w = matrix[x - S][y - S];
                printf("%d %d %d %d\n", x + 1, y + 1, z + 1, w + 1);
                return 0;
            }
        }
    }
    
    // 4. 4-cycle なし.
    puts("-1");
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc260/editorial/4437

// 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 S, T, M;

scanf("%d %d %d", &S, &T, &M);

vvi L(S);

rep(i, M){

int u, v;

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

--u, --v;

// 隣接リスト.

L[u].pb(v);

}

// 2. 二次元配列.

int matrix[3030][3030];

rep(i, 3030) rep(j, 3030) matrix[i][j] = -1;

// 3. 探索.

rep(z, S){

for(auto &x : L[z]){

for(auto &y : L[z]){

// Skip.

if(x == y) continue;

// -1 の場合.

if(matrix[x - S][y - S] == -1){

matrix[x - S][y - S] = z;

continue;

}

// 4-cycle あり.

int w = matrix[x - S][y - S];

printf("%d %d %d %d\n", x + 1, y + 1, z + 1, w + 1);

return 0;

}

// 4. 4-cycle なし.

puts("-1");

return 0;

}

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

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

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

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

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

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

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

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

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

[出力例]
4 5 3 1

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

[出力例]
-1

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

[出力例]
7 11 5 3

[入力例]

2 3 5

1 3

1 4

1 5

2 4

2 5

[出力例]

1 2 4 5

※AtCoderテストケースより

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

4 5 2 1

[入力例]

3 2 4

1 4

1 5

2 5

3 5

[出力例]

-1

※AtCoderテストケースより

[入力例]

4 5 9

3 5

1 8

3 7

1 9

4 6

2 7

4 8

1 7

2 9

[出力例]

1 7 2 9

※AtCoderテストケースより

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

7 9 2 1

[入力例]

3 2 5

1 4

1 5

2 4

3 4

3 5

[出力例]

4 5 3 1

[入力例]

7 5 8

1 8

1 11

3 8

3 9

5 9

5 11

6 9

7 10

[出力例]

-1

[入力例]

5 6 9

1 10

2 7

3 6

3 7

3 11

4 8

4 10

5 7

5 11

[出力例]

7 11 5 3

■参照サイト
AtCoder Beginner Contest 260

2023年5月14日2023年5月15日

■感想.
1. 問題Eは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 実装に苦労したものの, 尺取り法, いもす法の復習ができたので非常に良かったと思う.
3. 再度見直したところ, 前回実装した版(※テストケースで, A[i]がすべて同じで, B[i] が全て異なる場合)は, おそらく, TLE版に見えたため, ロジック修正の上, 再提出した.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

■C++版プログラム(問題E／おそらくTLE版).

// 解き直し.
// https://atcoder.jp/contests/abc260/editorial/4458
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
using P = pair<int, int>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
int ma[202020], mb[202020], ans[202020];

int main(){
    
    // 1. 入力情報.
    int N, M, n = 0;
    scanf("%d %d", &N, &M);
    vvi a(M + 1), b(M + 1);
    set<P> st;
    rep(i, N){
        int u, v;
        scanf("%d %d", &u, &v);
        
        // A[i], B[i] の インデックス i.
        if(!st.count({u, v})){
            a[u].pb(i);
            b[v].pb(i);
            ++n;
        }
        
        // 重複区間をチェックするために保存.
        st.insert({u, v});
    }
    
    // 2. 尺取り法.
    int t = 0, bef = 1;
    repx(l, 1, M + 1){
        // A[i](消滅).
        for(auto &p : a[l - 1]){
            --ma[p];
            if(mb[p] == 0) --t;
        }
        
        // B[i](消滅).
        for(auto &p : b[l - 1]){
            --mb[p];
            if(ma[p] == 0) --t;
        }
        
        // 区間[L, R] が 条件を満たすか？
        int cur = 0;
        repx(r, bef, M + 1){
            // 今回分.
            cur = r;
            
            // A[j](出現).
            for(auto &p : a[r]){
                if(ma[p]) continue;
                ++ma[p];
                if(mb[p] == 0) ++t;
            }
            
            // B[j](出現).
            for(auto &p : b[r]){
                if(mb[p]) continue;
                ++mb[p];
                if(ma[p] == 0) ++t;
            }
            
            // 条件を満たす区間[L, R]が見つかった.
            if(t == n){
                // いもす法.
                // -> 幅 の 下限, 上限 + 1 に, +1, -1 を 設定.
                ++ans[r - l + 1];
                --ans[M - l + 2];
                
                // 終了.
                break;
            }
        }
        
        // 前回分.
        bef = max(cur, l + 1);
    }
    
    // 3. 累積和.
    rep(i, M) ans[i + 1] += ans[i];
    
    // 4. 出力.
    repx(i, 1, M + 1) printf("%d%s", ans[i], (i < M) ? " " : "\n");
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc260/editorial/4458

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

using vvi = vector<vi>;

using P = pair<int, int>;

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

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

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

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

#define pb push_back

int ma[202020], mb[202020], ans[202020];

int main(){

// 1. 入力情報.

int N, M, n = 0;

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

vvi a(M + 1), b(M + 1);

set<P> st;

rep(i, N){

int u, v;

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

// A[i], B[i] のインデックス i.

if(!st.count({u, v})){

a[u].pb(i);

b[v].pb(i);

++n;

}

// 重複区間をチェックするために保存.

st.insert({u, v});

}

// 2. 尺取り法.

int t = 0, bef = 1;

repx(l, 1, M + 1){

// A[i](消滅).

for(auto &p : a[l - 1]){

--ma[p];

if(mb[p] == 0) --t;

}

// B[i](消滅).

for(auto &p : b[l - 1]){

--mb[p];

if(ma[p] == 0) --t;

}

// 区間[L, R] が条件を満たすか？

int cur = 0;

repx(r, bef, M + 1){

// 今回分.

cur = r;

// A[j](出現).

for(auto &p : a[r]){

if(ma[p]) continue;

++ma[p];

if(mb[p] == 0) ++t;

}

// B[j](出現).

for(auto &p : b[r]){

if(mb[p]) continue;

++mb[p];

if(ma[p] == 0) ++t;

}

// 条件を満たす区間[L, R]が見つかった.

if(t == n){

// いもす法.

// -> 幅の下限, 上限 + 1 に, +1, -1 を設定.

++ans[r - l + 1];

--ans[M - l + 2];

// 終了.

break;

}

// 前回分.

bef = max(cur, l + 1);

}

// 3. 累積和.

rep(i, M) ans[i + 1] += ans[i];

// 4. 出力.

repx(i, 1, M + 1) printf("%d%s", ans[i], (i < M) ? " " : "\n");

return 0;

}

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

// AC版.
// 解き直し.
// https://atcoder.jp/contests/abc260/editorial/4458
// 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 ma[202020], mb[202020], ans[202020];

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    vvi a(M + 1), b(M + 1);
    rep(i, N){
        int u, v;
        scanf("%d %d", &u, &v);
        
        // A[i], B[i] の インデックス i.
        a[u].pb(i);
        b[v].pb(i);
    }
    
    // 2. 尺取り法.
    int t = 0, bef = 1, debug = 0;
    repx(l, 1, M + 1){
        // A[i](消滅).
        for(auto &p : a[l - 1]){
        	++debug;
            --ma[p];
            if(mb[p] == 0) --t;
        }
        
        // B[i](消滅).
        for(auto &p : b[l - 1]){
        	++debug;
            --mb[p];
            if(ma[p] == 0) --t;
        }
        
        // 前回分.
        bef = max(bef, l);
        
        // 条件を満たす区間[L, R]が見つかった.
        if(t == N){
            // いもす法.
            // -> 幅 の 下限, 上限 + 1 に, +1, -1 を 設定.
            ++ans[bef - l + 1];
            --ans[M - l + 2];
            
            // 次へ.
            continue;
        }
        
        // 区間[L, R] が 条件を満たすか？
        int cur = 0;
        repx(r, bef, M + 1){
            // 今回分.
            cur = r;
            
            // A[j](出現).
            for(auto &p : a[r]){
            	++debug;
                if(ma[p]) continue;
                ++ma[p];
                if(mb[p] == 0) ++t;
            }
            
            // B[j](出現).
            for(auto &p : b[r]){
            	++debug;
                if(mb[p]) continue;
                ++mb[p];
                if(ma[p] == 0) ++t;
            }
            
            // 条件を満たす区間[L, R]が見つかった.
            if(t == N){
                // いもす法.
                // -> 幅 の 下限, 上限 + 1 に, +1, -1 を 設定.
                ++ans[r - l + 1];
                --ans[M - l + 2];
                
                // 終了.
                break;
            }
        }
        
        // 前回分.
        bef = max(cur, l + 1);
    }
    
    // 3. 累積和.
    rep(i, M) ans[i + 1] += ans[i];
    
    // 4. 出力.
    // printf("debug=%d\n", debug);
    repx(i, 1, M + 1) printf("%d%s", ans[i], (i < M) ? " " : "\n");
    return 0;
    
}

100

101

102

103

104

105

106

107

108

// AC版.

// 解き直し.

// https://atcoder.jp/contests/abc260/editorial/4458

// 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 ma[202020], mb[202020], ans[202020];

int main(){

// 1. 入力情報.

int N, M;

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

vvi a(M + 1), b(M + 1);

rep(i, N){

int u, v;

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

// A[i], B[i] のインデックス i.

a[u].pb(i);

b[v].pb(i);

}

// 2. 尺取り法.

int t = 0, bef = 1, debug = 0;

repx(l, 1, M + 1){

// A[i](消滅).

for(auto &p : a[l - 1]){

++debug;

--ma[p];

if(mb[p] == 0) --t;

}

// B[i](消滅).

for(auto &p : b[l - 1]){

++debug;

--mb[p];

if(ma[p] == 0) --t;

}

// 前回分.

bef = max(bef, l);

// 条件を満たす区間[L, R]が見つかった.

if(t == N){

// いもす法.

// -> 幅の下限, 上限 + 1 に, +1, -1 を設定.

++ans[bef - l + 1];

--ans[M - l + 2];

// 次へ.

continue;

}

// 区間[L, R] が条件を満たすか？

int cur = 0;

repx(r, bef, M + 1){

// 今回分.

cur = r;

// A[j](出現).

for(auto &p : a[r]){

++debug;

if(ma[p]) continue;

++ma[p];

if(mb[p] == 0) ++t;

}

// B[j](出現).

for(auto &p : b[r]){

++debug;

if(mb[p]) continue;

++mb[p];

if(ma[p] == 0) ++t;

}

// 条件を満たす区間[L, R]が見つかった.

if(t == N){

// いもす法.

// -> 幅の下限, 上限 + 1 に, +1, -1 を設定.

++ans[r - l + 1];

--ans[M - l + 2];

// 終了.

break;

}

// 前回分.

bef = max(cur, l + 1);

}

// 3. 累積和.

rep(i, M) ans[i + 1] += ans[i];

// 4. 出力.

// printf("debug=%d\n", debug);

repx(i, 1, M + 1) printf("%d%s", ans[i], (i < M) ? " " : "\n");

return 0;

}

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

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

[入力例]
1 2
1 2

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

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

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

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

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

[入力例]
10 20
5 9
5 15
2 16
8 11
3 10
11 16
8 13
7 17
3 9
4 11

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

[入力例]
25 50
2 26
20 32
9 27
4 11
18 26
2 17
3 26
9 15
8 14
9 17
3 30
5 17
8 25
6 36
20 33
15 37
3 27
6 11
1 22
3 30
6 15
16 43
8 19
10 26
13 20

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

[入力例]
100 250
100 101
100 102
100 103
100 104
100 105
100 106
100 107
100 108
100 109
100 110
100 111
100 112
100 113
100 114
100 115
100 116
100 117
100 118
100 119
100 120
100 121
100 122
100 123
100 124
100 125
100 126
100 127
100 128
100 129
100 130
100 131
100 132
100 133
100 134
100 135
100 136
100 137
100 138
100 139
100 140
100 141
100 142
100 143
100 144
100 145
100 146
100 147
100 148
100 149
100 150
100 151
100 152
100 153
100 154
100 155
100 156
100 157
100 158
100 159
100 160
100 161
100 162
100 163
100 164
100 165
100 166
100 167
100 168
100 169
100 170
100 171
100 172
100 173
100 174
100 175
100 176
100 177
100 178
100 179
100 180
100 181
100 182
100 183
100 184
100 185
100 186
100 187
100 188
100 189
100 190
100 191
100 192
100 193
100 194
100 195
100 196
100 197
100 198
100 199
100 200

[出力例(debug=10301 から debug=401 に 改善した)]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 101 101 101 101 101 101 101 101 101 101 101 101 101 101 101 101 101 101 101 101 101 101 101 101 101 101 101 101 101 101 101 101 101 101 101 101 101 101 101 101 101 101 101 101 101 101 101 101 101 101 101 100 99 98 97 96 95 94 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 74 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

[入力例]
200 1000
250 301
250 302
250 303
250 304
250 305
250 306
250 307
250 308
250 309
250 310
250 311
250 312
250 313
250 314
250 315
250 316
250 317
250 318
250 319
250 320
250 321
250 322
250 323
250 324
250 325
250 326
250 327
250 328
250 329
250 330
250 331
250 332
250 333
250 334
250 335
250 336
250 337
250 338
250 339
250 340
250 341
250 342
250 343
250 344
250 345
250 346
250 347
250 348
250 349
250 350
250 351
250 352
250 353
250 354
250 355
250 356
250 357
250 358
250 359
250 360
250 361
250 362
250 363
250 364
250 365
250 366
250 367
250 368
250 369
250 370
250 371
250 372
250 373
250 374
250 375
250 376
250 377
250 378
250 379
250 380
250 381
250 382
250 383
250 384
250 385
250 386
250 387
250 388
250 389
250 390
250 391
250 392
250 393
250 394
250 395
250 396
250 397
250 398
250 399
250 400
250 401
250 402
250 403
250 404
250 405
250 406
250 407
250 408
250 409
250 410
250 411
250 412
250 413
250 414
250 415
250 416
250 417
250 418
250 419
250 420
250 421
250 422
250 423
250 424
250 425
250 426
250 427
250 428
250 429
250 430
250 431
250 432
250 433
250 434
250 435
250 436
250 437
250 438
250 439
250 440
250 441
250 442
250 443
250 444
250 445
250 446
250 447
250 448
250 449
250 450
250 451
250 452
250 453
250 454
250 455
250 456
250 457
250 458
250 459
250 460
250 461
250 462
250 463
250 464
250 465
250 466
250 467
250 468
250 469
250 470
250 471
250 472
250 473
250 474
250 475
250 476
250 477
250 478
250 479
250 480
250 481
250 482
250 483
250 484
250 485
250 486
250 487
250 488
250 489
250 490
250 491
250 492
250 493
250 494
250 495
250 496
250 497
250 498
250 499
250 500

[出力例(debug=50651 から debug=801 に 改善した)]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 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 201 203 205 207 209 211 213 215 217 219 221 223 225 227 229 231 233 235 237 239 241 243 245 247 249 251 253 255 257 259 261 263 265 267 269 271 273 275 277 279 281 283 285 287 289 291 293 295 297 299 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 300 299 298 297 296 295 294 293 292 291 290 289 288 287 286 285 284 283 282 281 280 279 278 277 276 275 274 273 272 271 270 269 268 267 266 265 264 263 262 261 260 259 258 257 256 255 254 253 252 251 250 249 248 247 246 245 244 243 242 241 240 239 238 237 236 235 234 233 232 231 230 229 228 227 226 225 224 223 222 221 220 219 218 217 216 215 214 213 212 211 210 209 208 207 206 205 204 203 202 201 200 199 198 197 196 195 194 193 192 191 190 189 188 187 186 185 184 183 182 181 180 179 178 177 176 175 174 173 172 171 170 169 168 167 166 165 164 163 162 161 160 159 158 157 156 155 154 153 152 151 150 149 148 147 146 145 144 143 142 141 140 139 138 137 136 135 134 133 132 131 130 129 128 127 126 125 124 123 122 121 120 119 118 117 116 115 114 113 112 111 110 109 108 107 106 105 104 103 102 101 100 99 98 97 96 95 94 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 74 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 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

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

290

291

292

293

294

295

296

297

298

299

300

301

302

303

304

305

306

307

308

309

310

311

312

313

314

315

316

317

318

319

320

321

322

323

324

325

326

327

328

329

330

331

332

333

334

335

336

337

338

339

340

341

342

343

344

345

346

347

348

349

350

351

352

353

354

355

356

357

358

359

360

361

362

363

364

365

366

367

368

369

370

371

372

373

374

375

376

377

378

379

380

381

382

383

384

385

386

387

388

389

390

391

392

393

394

395

396

397

[入力例]

3 5

1 3

1 4

2 5

[出力例]

0 1 3 2 1

※AtCoderテストケースより

[入力例]

1 2

[出力例]

2 1

※AtCoderテストケースより

[入力例]

5 9

1 5

1 7

5 6

5 8

2 6

[出力例]

0 0 1 2 4 4 3 2 1

※AtCoderテストケースより

[入力例]

3 7

1 5

2 4

3 6

[出力例]

0 0 3 4 3 2 1

[入力例]

10 20

5 9

5 15

2 16

8 11

3 10

11 16

8 13

7 17

3 9

4 11

[出力例]

0 0 0 0 0 0 0 0 1 4 6 7 7 7 6 5 4 3 2 1

[入力例]

25 50

2 26

20 32

9 27

4 11

18 26

2 17

3 26

9 15

8 14

9 17

3 30

5 17

8 25

6 36

20 33

15 37

3 27

6 11

1 22

3 30

6 15

16 43

8 19

10 26

13 20

[出力例]

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

[入力例]

100 250

100 101

100 102

100 103

100 104

100 105

100 106

100 107

100 108

100 109

100 110

100 111

100 112

100 113

100 114

100 115

100 116

100 117

100 118

100 119

100 120

100 121

100 122

100 123

100 124

100 125

100 126

100 127

100 128

100 129

100 130

100 131

100 132

100 133

100 134

100 135

100 136

100 137

100 138

100 139

100 140

100 141

100 142

100 143

100 144

100 145

100 146

100 147

100 148

100 149

100 150

100 151

100 152

100 153

100 154

100 155

100 156

100 157

100 158

100 159

100 160

100 161

100 162

100 163

100 164

100 165

100 166

100 167

100 168

100 169

100 170

100 171

100 172

100 173

100 174

100 175

100 176

100 177

100 178

100 179

100 180

100 181

100 182

100 183

100 184

100 185

100 186

100 187

100 188

100 189

100 190

100 191

100 192

100 193

100 194

100 195

100 196

100 197

100 198

100 199

100 200

[出力例(debug=10301 から debug=401 に改善した)]

[入力例]

200 1000

250 301

250 302

250 303

250 304

250 305

250 306

250 307

250 308

250 309

250 310

250 311

250 312

250 313

250 314

250 315

250 316

250 317

250 318

250 319

250 320

250 321

250 322

250 323

250 324

250 325

250 326

250 327

250 328

250 329

250 330

250 331

250 332

250 333

250 334

250 335

250 336

250 337

250 338

250 339

250 340

250 341

250 342

250 343

250 344

250 345

250 346

250 347

250 348

250 349

250 350

250 351

250 352

250 353

250 354

250 355

250 356

250 357

250 358

250 359

250 360

250 361

250 362

250 363

250 364

250 365

250 366

250 367

250 368

250 369

250 370

250 371

250 372

250 373

250 374

250 375

250 376

250 377

250 378

250 379

250 380

250 381

250 382

250 383

250 384

250 385

250 386

250 387

250 388

250 389

250 390

250 391

250 392

250 393

250 394

250 395

250 396

250 397

250 398

250 399

250 400

250 401

250 402

250 403

250 404

250 405

250 406

250 407

250 408

250 409

250 410

250 411

250 412

250 413

250 414

250 415

250 416

250 417

250 418

250 419

250 420

250 421

250 422

250 423

250 424

250 425

250 426

250 427

250 428

250 429

250 430

250 431

250 432

250 433

250 434

250 435

250 436

250 437

250 438

250 439

250 440

250 441

250 442

250 443

250 444

250 445

250 446

250 447

250 448

250 449

250 450

250 451

250 452

250 453

250 454

250 455

250 456

250 457

250 458

250 459

250 460

250 461

250 462

250 463

250 464

250 465

250 466

250 467

250 468

250 469

250 470

250 471

250 472

250 473

250 474

250 475

250 476

250 477

250 478

250 479

250 480

250 481

250 482

250 483

250 484

250 485

250 486

250 487

250 488

250 489

250 490

250 491

250 492

250 493

250 494

250 495

250 496

250 497

250 498

250 499

250 500

[出力例(debug=50651 から debug=801 に改善した)]

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 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 201 203 205 207 209 211 213 215 217 219 221 223 225 227 229 231 233 235 237 239 241 243 245 247 249 251 253 255 257 259 261 263 265 267 269 271 273 275 277 279 281 283 285 287 289 291 293 295 297 299 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 301 300 299 298 297 296 295 294 293 292 291 290 289 288 287 286 285 284 283 282 281 280 279 278 277 276 275 274 273 272 271 270 269 268 267 266 265 264 263 262 261 260 259 258 257 256 255 254 253 252 251 250 249 248 247 246 245 244 243 242 241 240 239 238 237 236 235 234 233 232 231 230 229 228 227 226 225 224 223 222 221 220 219 218 217 216 215 214 213 212 211 210 209 208 207 206 205 204 203 202 201 200 199 198 197 196 195 194 193 192 191 190 189 188 187 186 185 184 183 182 181 180 179 178 177 176 175 174 173 172 171 170 169 168 167 166 165 164 163 162 161 160 159 158 157 156 155 154 153 152 151 150 149 148 147 146 145 144 143 142 141 140 139 138 137 136 135 134 133 132 131 130 129 128 127 126 125 124 123 122 121 120 119 118 117 116 115 114 113 112 111 110 109 108 107 106 105 104 103 102 101 100 99 98 97 96 95 94 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 74 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

■参照サイト
AtCoder Beginner Contest 260

2023年5月7日

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

C++の練習を兼ねて, AtCoder Beginner Contest 248 の問題E (K-colinear Line) を解いてみた.

■感想.
1. 問題Eは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 直線を固定して数え上げていくロジックが, 非常に面白く感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/abc248/editorial/3792
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using P = pair<LL, LL>;
using vp = vector<P>;
using T3 = tuple<LL, LL, 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 a first
#define b second
#define pb push_back

int main(){
    
    // 1. 入力情報.
    int N, K;
    scanf("%d %d", &N, &K);
    vp v;
    rep(i, N){
        LL x, y;
        scanf("%lld %lld", &x, &y);
        v.pb({x, y});
    }
    
    // 2. K = 1.
    if(K == 1){
        puts("Infinity");
        return 0;
    }
    
    // 3. K != 1.
    map<T3, int> m;
    rep(i, N){
        repx(j, i + 1, N){
            // 二点 A, B.
            LL ax = v[i].a, ay = v[i].b;
            LL bx = v[j].a, by = v[j].b;
            
            // 傾き(ベクトル AB).
            LL vx = bx - ax, vy = by - ay;
            LL g = __gcd(abs(vx), abs(vy));
            vx /= g;
            vy /= g;
            if(vx == 0) vy = 1;
            if(vy == 0) vx = 1;
            if(vx < 0){
                vx *= -1;
                vy *= -1;
            }
            
            // 切片(但し, vx倍したものを取得).
            LL c = ay * vx - ax * vy;
            
            // 二点通る(初回のみ, 二回目以降は, 調査済みとして, Skip).
            if(!m.count({vx, vy, c})) m[{vx, vy, c}] = 2;
            else                      continue;
            
            // 全探索.
            rep(k, N){
                // Skip.
                if(i == k || j == k) continue;
                
                // 点 P.
                LL px = v[k].a, py = v[k].b;
                
                // 傾き(ベクトル AP).
                LL wx = px - ax, wy = py - ay;
                
                // 判定.
                if(vx * wy == vy * wx) ++m[{vx, vy, c}];
            }
        }
    }
    
    // 4. 集計.
    int ans = 0;
    for(auto &p : m) if(p.b >= K) ++ans;
    
    // 5. 出力.
    printf("%d\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc248/editorial/3792

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using P = pair<LL, LL>;

using vp = vector<P>;

using T3 = tuple<LL, LL, 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 a first

#define b second

#define pb push_back

int main(){

// 1. 入力情報.

int N, K;

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

vp v;

rep(i, N){

LL x, y;

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

v.pb({x, y});

}

// 2. K = 1.

if(K == 1){

puts("Infinity");

return 0;

}

// 3. K != 1.

map<T3, int> m;

rep(i, N){

repx(j, i + 1, N){

// 二点 A, B.

LL ax = v[i].a, ay = v[i].b;

LL bx = v[j].a, by = v[j].b;

// 傾き(ベクトル AB).

LL vx = bx - ax, vy = by - ay;

LL g = __gcd(abs(vx), abs(vy));

vx /= g;

vy /= g;

if(vx == 0) vy = 1;

if(vy == 0) vx = 1;

if(vx < 0){

vx *= -1;

vy *= -1;

}

// 切片(但し, vx倍したものを取得).

LL c = ay * vx - ax * vy;

// 二点通る(初回のみ, 二回目以降は, 調査済みとして, Skip).

if(!m.count({vx, vy, c})) m[{vx, vy, c}] = 2;

else continue;

// 全探索.

rep(k, N){

// Skip.

if(i == k || j == k) continue;

// 点 P.

LL px = v[k].a, py = v[k].b;

// 傾き(ベクトル AP).

LL wx = px - ax, wy = py - ay;

// 判定.

if(vx * wy == vy * wx) ++m[{vx, vy, c}];

}

// 4. 集計.

int ans = 0;

for(auto &p : m) if(p.b >= K) ++ans;

// 5. 出力.

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

return 0;

}

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

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

[入力例]
1 1
0 0

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

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

[出力例]
3

[入力例]
10 3
30 -22
16 -19
-18 5
6 -12
-36 20
55 -29
-4 -5
77 41
60 -44
90 -66

[出力例]
2

[入力例]
30 3
6 12
-59 11
68 21
-29 60
16 22
63 16
24 93
43 40
36 42
42 52
-88 -53
73 26
-55 59
-8 22
86 35
-10 21
-66 51
13 -87
0 26
78 -36
-53 -57
10 31
-5 18
-28 49
-86 -79
-83 -77
10 47
-76 62
67 17
-26 -99

[出力例]
6

[入力例]

5 2

0 0

1 0

0 1

-1 0

0 -1

[出力例]

※AtCoderテストケースより

[入力例]

1 1

0 0

[出力例]

Infinity

※AtCoderテストケースより

[入力例]

3 2

1 2

2 0

2 1

[出力例]

[入力例]

10 3

30 -22

16 -19

-18 5

6 -12

-36 20

55 -29

-4 -5

77 41

60 -44

90 -66

[出力例]

[入力例]

30 3

6 12

-59 11

68 21

-29 60

16 22

63 16

24 93

43 40

36 42

42 52

-88 -53

73 26

-55 59

-8 22

86 35

-10 21

-66 51

13 -87

0 26

78 -36

-53 -57

10 31

-5 18

-28 49

-86 -79

-83 -77

10 47

-76 62

67 17

-26 -99

[出力例]

■参照サイト
ユニークビジョンプログラミングコンテスト2022（AtCoder Beginner Contest 248）

2023年5月5日

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

C++の練習を兼ねて, AtCoder Beginner Contest 260 の問題C (Changing Jewels) ～問題D (Draw Your Cards) を解いてみた.

■感想.
1. 問題C, Dは, 方針を絞り込めたので, AC版に到達できたと思う.
2. Union-Find木の復習が出来たので, 非常に良かったと思う.
※ 公式のライブラリを拝借させて頂いてます.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using T3 = tuple<LL, LL, 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--)
LL r[11], b[11];

int main(){
    
    // 1. 入力情報.
    int N, X, Y;
    scanf("%d %d %d", &N, &X, &Y);
    
    // 2. 操作.
    queue<T3> q;
    q.push({N, 1, 0});
    while(!q.empty()){
        // キューから取り出す.
        T3 u = q.front();
        q.pop();
        LL l = get<0>(u);
        LL s = get<1>(u);
        LL c = get<2>(u);
        
        // レベル 2 以上か？
        if(l >= 2){
            // 赤い宝石.
            if(c == 0){
                q.push({l - 1, s,     0});
                q.push({l,     s * X, 1});
                r[l - 1] += s;
                b[l] += s * X;
            }
            
            // 青い宝石.
            if(c == 1){
                q.push({l - 1, s,     0});
                q.push({l - 1, s * Y, 1});
                r[l - 1] += s;
                b[l - 1] += s * Y;
            }
        }
    }
    
    // 3. 出力.
    printf("%lld\n", b[1]);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using T3 = tuple<LL, LL, 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--)

LL r[11], b[11];

int main(){

// 1. 入力情報.

int N, X, Y;

scanf("%d %d %d", &N, &X, &Y);

// 2. 操作.

queue<T3> q;

q.push({N, 1, 0});

while(!q.empty()){

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

T3 u = q.front();

q.pop();

LL l = get<0>(u);

LL s = get<1>(u);

LL c = get<2>(u);

// レベル 2 以上か？

if(l >= 2){

// 赤い宝石.

if(c == 0){

q.push({l - 1, s, 0});

q.push({l, s * X, 1});

r[l - 1] += s;

b[l] += s * X;

}

// 青い宝石.

if(c == 1){

q.push({l - 1, s, 0});

q.push({l - 1, s * Y, 1});

r[l - 1] += s;

b[l - 1] += s * Y;

}

// 3. 出力.

printf("%lld\n", b[1]);

return 0;

}

[入力例]
2 3 4

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

[入力例]
1 5 5

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

[入力例]
10 5 5

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

[入力例]
2 5 5

[出力例]
25

[入力例]
3 4 5

[出力例]
200

[入力例]
7 3 2

[出力例]
36720

[入力例]

2 3 4

[出力例]

※AtCoderテストケースより

[入力例]

1 5 5

[出力例]

※AtCoderテストケースより

[入力例]

10 5 5

[出力例]

3942349900

※AtCoderテストケースより

[入力例]

2 5 5

[出力例]

[入力例]

3 4 5

[出力例]

200

[入力例]

7 3 2

[出力例]

36720

■C++版プログラム(問題D／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--)
int ans[202020];

// https://github.com/atcoder/live_library/blob/master/uf.cpp
// UnionFind
// coding: https://youtu.be/TdR816rqc3s?t=726
// comment: https://youtu.be/TdR816rqc3s?t=6822
// -> 一部改変.
struct UnionFind{
    vi d;
    UnionFind(int n = 0): d(n, -1) {}
    int find(int x){
        return (d[x] < 0) ? x : (d[x] = find(d[x]));
    }
    bool unite(int x, int y){
        x = find(x);
        y = find(y);
        if(x == y) return false;
        if(d[x] > d[y]) swap(x, y);
        d[x] += d[y];
        d[y] = x;
        return true;
    }
    bool same(int x, int y){
        return find(x) == find(y);
    }
    int size(int x){
        return -d[find(x)];
    }
};

int main(){
    
    // 1. 入力情報.
    int N, K;
    scanf("%d %d", &N, &K);
    
    // 2. 初期化.
    UnionFind uf(N + 2);
    repx(i, 1, N + 1){
        ans[i] = -1;
        uf.unite(i, i);
    }
    
    // 3. 繰り返し.
    set<int> st;
    rep(i, N){
        // 2-1. カードに書かれた数字.
        int p;
        scanf("%d", &p);
        
        // 2-2. カードを場に置く.
        auto it = st.lower_bound(p);
        if(it == st.end()){
            // 引いたカードをどれにも重ねずに表向きで場に置く.
            st.insert(p);
        }else{
            // カードを乗せる.
            uf.unite(*it, p);
            
            // 表向きのカードを差し替える.
            st.erase(*it);
            st.insert(p);
        }
        
        // 2-3. カードを食べる.
        int r = uf.find(p);
        if(uf.size(r) == K){
            // カードの山を, 場から消滅.
            st.erase(p);
            
            // ターン数.
            ans[r] = i + 1;
        }
    }
    
    // 4. 出力.
    repx(i, 1, N + 1) printf("%d\n", ans[uf.find(i)]);
    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--)

int ans[202020];

// https://github.com/atcoder/live_library/blob/master/uf.cpp

// UnionFind

// coding: https://youtu.be/TdR816rqc3s?t=726

// comment: https://youtu.be/TdR816rqc3s?t=6822

// -> 一部改変.

struct UnionFind{

vi d;

UnionFind(int n = 0): d(n, -1) {}

int find(int x){

return (d[x] < 0) ? x : (d[x] = find(d[x]));

}

bool unite(int x, int y){

x = find(x);

y = find(y);

if(x == y) return false;

if(d[x] > d[y]) swap(x, y);

d[x] += d[y];

d[y] = x;

return true;

}

bool same(int x, int y){

return find(x) == find(y);

}

int size(int x){

return -d[find(x)];

}

};

int main(){

// 1. 入力情報.

int N, K;

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

// 2. 初期化.

UnionFind uf(N + 2);

repx(i, 1, N + 1){

ans[i] = -1;

uf.unite(i, i);

}

// 3. 繰り返し.

set<int> st;

rep(i, N){

// 2-1. カードに書かれた数字.

int p;

scanf("%d", &p);

// 2-2. カードを場に置く.

auto it = st.lower_bound(p);

if(it == st.end()){

// 引いたカードをどれにも重ねずに表向きで場に置く.

st.insert(p);

}else{

// カードを乗せる.

uf.unite(*it, p);

// 表向きのカードを差し替える.

st.erase(*it);

st.insert(p);

}

// 2-3. カードを食べる.

int r = uf.find(p);

if(uf.size(r) == K){

// カードの山を, 場から消滅.

st.erase(p);

// ターン数.

ans[r] = i + 1;

}

// 4. 出力.

repx(i, 1, N + 1) printf("%d\n", ans[uf.find(i)]);

return 0;

}

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

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

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

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

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

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

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

[出力例]
2
5
2
5
-1

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

[出力例]
-1
-1
7
7
-1
9
7
9
9
-1

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

[出力例]
-1
-1
-1
-1
9
-1
-1
-1
6
-1
-1
6
-1
9
-1
6
6
-1
9
9

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

[出力例]
32
36
32
32
18
44
9
44
42
9
-1
-1
-1
21
24
36
23
18
21
36
44
39
39
23
19
-1
21
39
42
23
20
19
42
40
14
14
40
19
24
-1
20
24
14
20
-1
40
-1
-1
18
9

[入力例]
100 5
2 85 38 83 82 21 1 41 17 32 18 68 54 74 60 45 55 69 29 37 99 61 13 100 33 35 77 95 70 87 88 49 80 4 94 9 6 91 98 28 22 20 84 67 93 62 71 57 46 97 72 56 36 8 40 44 10 19 96 26 51 58 43 53 3 79 63 16 78 66 30 64 73 92 81 25 89 27 31 86 52 11 90 12 14 7 24 50 39 76 47 5 23 15 34 48 59 75 42 65

[出力例]
-1
-1
-1
34
92
37
86
-1
37
57
86
92
23
-1
-1
86
23
11
86
-1
23
41
93
93
92
92
78
40
34
78
-1
11
25
-1
37
57
25
23
89
86
11
-1
78
92
34
49
-1
-1
40
89
78
93
-1
34
25
57
49
-1
-1
25
37
46
93
89
-1
89
46
34
37
40
49
57
-1
25
-1
-1
40
89
93
41
-1
11
11
46
23
-1
41
-1
-1
-1
46
-1
49
46
41
78
57
49
40
41

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

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

[入力例]

5 2

3 5 2 1 4

[出力例]

-1

※AtCoderテストケースより

[入力例]

5 1

1 2 3 4 5

[出力例]

※AtCoderテストケースより

[入力例]

15 3

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

[出力例]

-1

※AtCoderテストケースより

[入力例]

5 2

3 1 4 5 2

[出力例]

-1

[入力例]

10 3

5 1 2 7 4 9 3 8 6 10

[出力例]

-1

[入力例]

20 4

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

[出力例]

-1

[入力例]

50 3

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

[出力例]

-1

[入力例]

100 5

2 85 38 83 82 21 1 41 17 32 18 68 54 74 60 45 55 69 29 37 99 61 13 100 33 35 77 95 70 87 88 49 80 4 94 9 6 91 98 28 22 20 84 67 93 62 71 57 46 97 72 56 36 8 40 44 10 19 96 26 51 58 43 53 3 79 63 16 78 66 30 64 73 92 81 25 89 27 31 86 52 11 90 12 14 7 24 50 39 76 47 5 23 15 34 48 59 75 42 65

[出力例]

-1

■参照サイト
AtCoder Beginner Contest 260
Union-Find木

2023年5月3日

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

C++の練習を兼ねて, AtCoder Beginner Contest 299 の問題E (Nearest Black Vertex) を解いてみた.

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

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

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

// 解き直し.
// https://atcoder.jp/contests/abc299/editorial/6249
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
using P = pair<int, int>;
using vp = vector<P>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define a first
#define b second
#define pb push_back
int duv[2020][2020];

int main(){
    
    // 1. 入力情報.
    int N, M, K;
    scanf("%d %d", &N, &M);
    vvi G(N);
    rep(i, M){
        int u, v;
        scanf("%d %d", &u, &v);
        --u, --v;
        G[u].pb(v);
        G[v].pb(u);
    }
    scanf("%d", &K);
    vp c;
    rep(i, K){
        int p, d;
        scanf("%d %d", &p, &d);
        --p;
        c.pb({p, d});
    }
    
    // 2. bfs.
    // https://ja.wikipedia.org/wiki/幅優先探索
    auto bfs = [&](vvi &G, int s){
        // 空のキュー.
        queue<int> q;
        
        // 探索地点 s をキューに追加.
        q.push(s);
        
        // キューを処理.
        while(!q.empty()){
            // キューから取り出す.
            int u = q.front();
            q.pop();
            
            // 取り出した要素を処理.
            for(auto &v : G[u]) if(!duv[s][v] && v != s) duv[s][v] = duv[s][u] + 1, q.push(v);
        }
    };
    
    // 3. 全探索.
    rep(i, N) bfs(G, i);
    /*
    rep(i, N){
        rep(j, N) printf("%d ", duv[i][j]);
        puts("");
    }
    */
    
    // 4. 頂点彩色.
    // -> いずれかの頂点 p[i] で, 距離が d[i] 未満 の 頂点を, 白で塗っていく.
    string ans(N, '1');
    for(auto &x : c){
        int p = x.a;
        int d = x.b;
        rep(i, N) if(duv[p][i] < d) ans[i] = '0';
    }
    
    // 5. 判定.
    // 5-1. 条件 1.
    bool b1 = false;
    rep(i, N) b1 |= (ans[i] - '0');
    
    // 5-2. 条件 2.
    bool b2 = true;
    for(auto &x : c){
        int p = x.a;
        int d = x.b;
        int dMin = 2020202020;
        rep(i, N) if(ans[i] == '1' && duv[p][i] < dMin) dMin = duv[p][i];
        if(d != dMin) b2 = false;
    }
    
    // 6. 出力.
    if(b1 && b2) printf("%s\n%s\n", "Yes", ans.c_str());
    else         puts("No");
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc299/editorial/6249

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

using vvi = vector<vi>;

using P = pair<int, int>;

using vp = vector<P>;

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

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

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

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

#define a first

#define b second

#define pb push_back

int duv[2020][2020];

int main(){

// 1. 入力情報.

int N, M, K;

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

vvi G(N);

rep(i, M){

int u, v;

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

--u, --v;

G[u].pb(v);

G[v].pb(u);

}

scanf("%d", &K);

vp c;

rep(i, K){

int p, d;

scanf("%d %d", &p, &d);

--p;

c.pb({p, d});

}

// 2. bfs.

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

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

// 空のキュー.

queue<int> q;

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

q.push(s);

// キューを処理.

while(!q.empty()){

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

int u = q.front();

q.pop();

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

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

}

};

// 3. 全探索.

rep(i, N) bfs(G, i);

rep(i, N){

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

puts("");

}

// 4. 頂点彩色.

// -> いずれかの頂点 p[i] で, 距離が d[i] 未満の頂点を, 白で塗っていく.

string ans(N, '1');

for(auto &x : c){

int p = x.a;

int d = x.b;

rep(i, N) if(duv[p][i] < d) ans[i] = '0';

}

// 5. 判定.

// 5-1. 条件 1.

bool b1 = false;

rep(i, N) b1 |= (ans[i] - '0');

// 5-2. 条件 2.

bool b2 = true;

for(auto &x : c){

int p = x.a;

int d = x.b;

int dMin = 2020202020;

rep(i, N) if(ans[i] == '1' && duv[p][i] < dMin) dMin = duv[p][i];

if(d != dMin) b2 = false;

}

// 6. 出力.

if(b1 && b2) printf("%s\n%s\n", "Yes", ans.c_str());

else puts("No");

return 0;

}

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

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

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

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

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

[入力例]
1 0
0

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

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

[出力例]
Yes
010

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

[出力例]
Yes
0100100

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

[出力例]
Yes
101011010110101

100

101

102

103

104

105

106

107

108

109

110

[入力例]

5 5

1 2

2 3

3 1

3 4

4 5

1 0

5 2

[出力例]

Yes

10100

※AtCoderテストケースより

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

Yes

11100

[入力例]

5 5

1 2

2 3

3 1

3 4

4 5

1 1

2 1

3 1

4 1

5 1

[出力例]

※AtCoderテストケースより

[入力例]

1 0

[出力例]

Yes

※AtCoderテストケースより

[入力例]

3 2

1 2

2 3

1 1

2 0

3 1

[出力例]

Yes

010

[入力例]

7 7

1 2

2 3

3 1

4 3

6 1

5 1

7 6

1 1

3 1

4 2

5 0

6 2

[出力例]

Yes

0100100

[入力例]

15 15

6 1

2 1

2 4

2 5

12 4

11 4

5 10

5 13

10 13

3 1

3 7

3 8

8 9

14 9

15 9

2 1

5 0

7 1

9 1

11 0

12 2

14 2

15 0

[出力例]

Yes

101011010110101

■参照サイト
東京海上日動プログラミングコンテスト2023（AtCoder Beginner Contest 299）

2023年5月2日

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

C++の練習を兼ねて, AtCoder Beginner Contest 299 の問題C (Dango) ～問題D (Find by Query) を解いてみた.

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

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

■C++版プログラム(問題C／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--)
#define pb push_back

int main(){
    
    // 1. 入力情報.
    int N;
    char c[202020];
    scanf("%d %s", &N, c);
    
    // 2. カウント.
    // 2-1 左 -> 右.
    int ans = -1;
    string s;
    rep(i, N){
        if(c[i] == '-'){
            if(s.size() > 1) ans = max(ans, (int)s.size() - 1);
            s.clear();
            s.pb(c[i]);
            continue;
        }
        if(s.size()) s.pb(c[i]);
    }
    if(s.size() > 1) ans = max(ans, (int)s.size() - 1);
    
    // 2-2. 右 -> 左.
    s.clear();
    repr(i, N - 1, 0){
        if(c[i] == '-'){
            if(s.size() > 1) ans = max(ans, (int)s.size() - 1);
            s.clear();
            s.pb(c[i]);
            continue;
        }
        if(s.size()) s.pb(c[i]);
    }
    if(s.size() > 1) ans = max(ans, (int)s.size() - 1);
    
    // 3. 出力.
    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--)

#define pb push_back

int main(){

// 1. 入力情報.

int N;

char c[202020];

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

// 2. カウント.

// 2-1 左 -> 右.

int ans = -1;

string s;

rep(i, N){

if(c[i] == '-'){

if(s.size() > 1) ans = max(ans, (int)s.size() - 1);

s.clear();

s.pb(c[i]);

continue;

}

if(s.size()) s.pb(c[i]);

}

if(s.size() > 1) ans = max(ans, (int)s.size() - 1);

// 2-2. 右 -> 左.

s.clear();

repr(i, N - 1, 0){

if(c[i] == '-'){

if(s.size() > 1) ans = max(ans, (int)s.size() - 1);

s.clear();

s.pb(c[i]);

continue;

}

if(s.size()) s.pb(c[i]);

}

if(s.size() > 1) ans = max(ans, (int)s.size() - 1);

// 3. 出力.

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

return 0;

}

[入力例]
10
o-oooo---o

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

[入力例]
1
-

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

[入力例]
30
-o-o-oooo-oo-o-ooooooo--oooo-o

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

[入力例]
5
ooooo

[出力例]
-1

[入力例]
12
-o-oo-o-o-o-

[出力例]
2

[入力例]
50
o---o-o--oo-o--ooo-o-o---o--oo-o-ooooo-o-oo--ooo-o

[出力例]
5

[入力例]

o-oooo---o

[出力例]

※AtCoderテストケースより

[入力例]

[出力例]

-1

※AtCoderテストケースより

[入力例]

-o-o-oooo-oo-o-ooooooo--oooo-o

[出力例]

※AtCoderテストケースより

[入力例]

ooooo

[出力例]

-1

[入力例]

-o-oo-o-o-o-

[出力例]

[入力例]

o---o-o--oo-o--ooo-o-o---o--oo-o-ooooo-o-oo--ooo-o

[出力例]

■C++版プログラム(問題D／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;
    scanf("%d", &N);
    
    // 2. 評価関数.
    auto f = [&](int m) -> bool {
        // 2-1. 質問.
        printf("? %d\n", m);
        fflush(stdout);
        
        // 2-2. 応答.
        int s;
        scanf("%d", &s);
        
        // 2-3. 判定結果.
        return (s == 0);
    };
    
    // 3. 二分探索で確認してみる.
    int l = 0, h = N;
    while(l + 1 < h){
        int m = (h + l) >> 1;
        if(f(m)) l = m;
        else     h = m;
        // printf("h=%d l=%d m=%d\n", h, l, m);
    }
    
    // 4. 出力.
    printf("! %d\n", l);
    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;

scanf("%d", &N);

// 2. 評価関数.

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

// 2-1. 質問.

printf("? %d\n", m);

fflush(stdout);

// 2-2. 応答.

int s;

scanf("%d", &s);

// 2-3. 判定結果.

return (s == 0);

};

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

int l = 0, h = N;

while(l + 1 < h){

int m = (h + l) >> 1;

if(f(m)) l = m;

else h = m;

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

}

// 4. 出力.

printf("! %d\n", l);

return 0;

}

※インタラクティブな問題のため, 入出力は, デバッグ時に使用したものを記載している.

[入力例(N = 7, S=0010011)]
7
1
0
0

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

[入力例(N = 12, S=011010010011)]
12
0
0
0
1

[出力例]
? 6
? 9
? 10
? 11
! 10

[入力例(N = 15, S=011001001010011)]
15
0
1
1
0

[出力例]
? 7
? 11
? 9
? 8
! 8

[入力例(N = 25, S=0110010101101010100100101)]
25
0
0
0
1
0

[出力例]
? 12
? 18
? 21
? 23
? 22
! 22

※インタラクティブな問題のため, 入出力は, デバッグ時に使用したものを記載している.

[入力例(N = 7, S=0010011)]

[出力例]

? 3

? 1

? 2

! 2

※AtCoderテストケースより

[入力例(N = 12, S=011010010011)]

[出力例]

? 6

? 9

? 10

? 11

! 10

[入力例(N = 15, S=011001001010011)]

[出力例]

? 7

? 11

? 9

? 8

! 8

[入力例(N = 25, S=0110010101101010100100101)]

[出力例]

? 12

? 18

? 21

? 23

? 22

! 22

■参照サイト
東京海上日動プログラミングコンテスト2023（AtCoder Beginner Contest 299）

2023年5月1日

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

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

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

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

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

// 解き直し.
// https://atcoder.jp/contests/abc292/editorial/5874
// 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);
    rep(i, M){
        int u, v;
        scanf("%d %d", &u, &v);
        --u, --v;
        G[u].pb(v); // 有向辺.
    }
    
    // 2. bfs.
    // https://ja.wikipedia.org/wiki/幅優先探索
    auto bfs = [&](vvi &G, int s, int* d){
        // 空のキュー.
        queue<int> q;
        
        // 探索地点 s をキューに追加.
        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);
        }
    };
    
    // 3. 全探索.
    int ans = -M;
    rep(i, N){
        int d[N];
        rep(j, N) d[j] = 0;
        bfs(G, i, d);
        rep(j, N) ans += (d[j] > 0);
    }
    
    // 4. 出力.
    printf("%d\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc292/editorial/5874

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

rep(i, M){

int u, v;

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

--u, --v;

G[u].pb(v); // 有向辺.

}

// 2. bfs.

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

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

// 空のキュー.

queue<int> q;

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

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

}

};

// 3. 全探索.

int ans = -M;

rep(i, N){

int d[N];

rep(j, N) d[j] = 0;

bfs(G, i, d);

rep(j, N) ans += (d[j] > 0);

}

// 4. 出力.

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

return 0;

}

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

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

[入力例]
292 0

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

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

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

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

[出力例]
5

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

[出力例]
17

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

[出力例]
36

[入力例]

4 3

2 4

3 1

4 3

[出力例]

※AtCoderテストケースより

[入力例]

292 0

[出力例]

※AtCoderテストケースより

[入力例]

5 8

1 2

2 1

1 3

3 1

1 4

4 1

1 5

5 1

[出力例]

※AtCoderテストケースより

[入力例]

5 4

1 2

2 3

3 4

3 5

[出力例]

[入力例]

10 10

1 2

1 3

3 4

2 4

2 5

5 6

5 7

4 8

8 9

8 10

[出力例]

[入力例]

20 20

2 1

2 3

2 13

1 4

1 5

4 5

4 10

10 12

10 11

11 19

11 20

5 9

3 6

6 7

6 8

8 17

8 18

13 15

13 14

14 16

[出力例]

■参照サイト
AtCoder Beginner Contest 292

2023年4月29日

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

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

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

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

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

// 解き直し.
// https://atcoder.jp/contests/abc142/editorial/945
// 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
const int INF = 1010101010;

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    vvi OG(N), RG(N);
    set<int> e[N];
    rep(i, M){
        int a, b;
        scanf("%d %d", &a, &b);
        --a, --b;
        OG[a].pb(b);    // 有向グラフ.
        RG[b].pb(a);    // 経路復元用のグラフ.
        e[b].insert(a); // 有向辺(b -> a).
    }
    
    // 2. bfs.
    // https://ja.wikipedia.org/wiki/幅優先探索
    auto bfs = [&](vvi &G, int s, int* d){
        // 空のキュー.
        queue<int> q;
        
        // 距離ゼロ.
        d[s] = 0;
        
        // 探索地点 s をキュー q に追加.
        q.push(s);
        while(!q.empty()){
            // キューから取り出す.
            int u = q.front();
            q.pop();
            
            // 隣接頂点をチェック.
            for(auto &v : G[u]) if(d[v] == INF && v != s) d[v] = d[u] + 1, q.push(v);
        }
    };
    
    // 3. 最短経路.
    auto f = [&](vvi &G, int s, int* d, vi& r){
        // 空のキュー.
        queue<int> q;
        
        // 探索地点 s をキュー q に追加.
        q.push(s);
        r.pb(s);
        while(!q.empty()){
            // キューから取り出す.
            int u = q.front();
            q.pop();
            
            // 取り出した要素を処理.
            for(auto &v : G[u]){
                // 距離 が 1 小さい場合に, 保存.
                if(d[v] == d[u] - 1){
                    r.pb(v);
                    q.push(v);
                    break;
                }
            }
        }
    };
    
    // 4. 全探索.
    vi ans;
    int dMax = INF;
    rep(i, N){
        // 頂点 i を 始点として, bfs.
        int d[N];
        rep(j, N) d[j] = INF;
        bfs(OG, i, d);
        
        // 頂点 i へ向かう辺に着目して, 最も距離が近い頂点 s を選択.
        int s = -1;
        for(auto &j : e[i]){
            if(d[j] && d[j] < dMax){
                dMax = d[j];
                s = j;
            }
        }
        
        // 存在したら, 経路復元.
        if(s != -1){
            vi cur;
            f(RG, s, d, cur);
            ans = cur;
        }
    }
    
    // 5. 出力.
    int K = ans.size();
    if(!K){
        puts("-1");
        return 0;
    }
    printf("%d\n", K);
    repr(i, K - 1, 0) printf("%d\n", ans[i] + 1);
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

// 解き直し.

// https://atcoder.jp/contests/abc142/editorial/945

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

const int INF = 1010101010;

int main(){

// 1. 入力情報.

int N, M;

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

vvi OG(N), RG(N);

set<int> e[N];

rep(i, M){

int a, b;

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

--a, --b;

OG[a].pb(b); // 有向グラフ.

RG[b].pb(a); // 経路復元用のグラフ.

e[b].insert(a); // 有向辺(b -> a).

}

// 2. bfs.

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

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

// 空のキュー.

queue<int> q;

// 距離ゼロ.

d[s] = 0;

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

q.push(s);

while(!q.empty()){

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

int u = q.front();

q.pop();

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

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

}

};

// 3. 最短経路.

auto f = [&](vvi &G, int s, int* d, vi& r){

// 空のキュー.

queue<int> q;

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

q.push(s);

r.pb(s);

while(!q.empty()){

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

int u = q.front();

q.pop();

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

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

// 距離が 1 小さい場合に, 保存.

if(d[v] == d[u] - 1){

r.pb(v);

q.push(v);

break;

}

};

// 4. 全探索.

vi ans;

int dMax = INF;

rep(i, N){

// 頂点 i を始点として, bfs.

int d[N];

rep(j, N) d[j] = INF;

bfs(OG, i, d);

// 頂点 i へ向かう辺に着目して, 最も距離が近い頂点 s を選択.

int s = -1;

for(auto &j : e[i]){

if(d[j] && d[j] < dMax){

dMax = d[j];

s = j;

}

// 存在したら, 経路復元.

if(s != -1){

vi cur;

f(RG, s, d, cur);

ans = cur;

}

// 5. 出力.

int K = ans.size();

if(!K){

puts("-1");

return 0;

}

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

repr(i, K - 1, 0) printf("%d\n", ans[i] + 1);

return 0;

}

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

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

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

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

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

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

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

[出力例]
3
1
2
8

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

[出力例]
5
2
5
7
8
10

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

[出力例]
7
7
8
9
10
26
27
25

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

[入力例]

4 5

1 2

2 3

2 4

4 1

4 3

[出力例]

※AtCoderテストケースより

[入力例]

4 5

1 2

2 3

2 4

1 4

4 3

[出力例]

-1

※AtCoderテストケースより

[入力例]

6 9

1 2

2 3

3 4

4 5

5 6

5 1

5 2

6 1

6 2

[出力例]

※AtCoderテストケースより

[入力例]

10 10

1 2

2 8

8 1

2 3

2 4

10 3

3 7

9 7

4 5

6 5

[出力例]

[入力例]

13 15

9 1

1 2

2 4

4 6

2 5

6 7

5 7

7 8

8 3

3 10

8 10

10 2

11 7

12 11

13 11

[出力例]

[入力例]

32 34

1 3

3 4

1 2

2 5

5 6

2 7

25 7

7 8

8 9

9 10

11 10

12 13

13 14

10 14

15 14

14 16

16 19

19 17

18 19

19 20

21 20

20 22

22 23

23 24

24 25

31 32

32 23

10 28

28 29

29 30

30 25

10 26

26 27

27 25

[出力例]

■参照サイト
AtCoder Beginner Contest 142

2023年4月23日

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

C++の練習を兼ねて, AtCoder Beginner Contest 297 の問題C (PC on the Table) ～問題E (Kth Takoyaki Set) を解いてみた.

■感想.
1. 問題C ～ E は, 方針を絞り込めたので, AC版に到達できたと思う.
2. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vs = vector<string>;
#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 H, W;
    scanf("%d %d", &H, &W);
    vs v;
    rep(i, H){
        char c[202];
        scanf("%s", c);
        string s(c);
        v.pb(s);
    }
    
    // 2. 操作.
    rep(i, H){
        rep(j, W - 1){
            if(v[i][j + 0] == 'T' && v[i][j + 1] == 'T'){
                v[i][j + 0] = 'P';
                v[i][j + 1] = 'C';
            }
        }
    }
    
    // 3. 出力.
    rep(i, H) printf("%s\n", v[i].c_str());
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vs = vector<string>;

#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 H, W;

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

vs v;

rep(i, H){

char c[202];

scanf("%s", c);

string s(c);

v.pb(s);

}

// 2. 操作.

rep(i, H){

rep(j, W - 1){

if(v[i][j + 0] == 'T' && v[i][j + 1] == 'T'){

v[i][j + 0] = 'P';

v[i][j + 1] = 'C';

}

// 3. 出力.

rep(i, H) printf("%s\n", v[i].c_str());

return 0;

}

[入力例]
2 3
TTT
T.T

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

[入力例]
3 5
TTT..
.TTT.
TTTTT

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

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

[入力例]
5 10
TT..TTTT..
..TTTTTTT.
TTTTT..TTT
.T.TTTTT.T
.TT..T..TT

[出力例]
PC..PCPC..
..PCPCPCT.
PCPCT..PCT
.T.PCPCT.T
.PC..T..PC

[入力例]

2 3

TTT

T.T

[出力例]

PCT

T.T

※AtCoderテストケースより

[入力例]

3 5

TTT..

.TTT.

TTTTT

[出力例]

PCT..

.PCT.

PCTPC

※AtCoderテストケースより

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

PCT..

.PCT.

PCPCT

[入力例]

5 10

TT..TTTT..

..TTTTTTT.

TTTTT..TTT

.T.TTTTT.T

.TT..T..TT

[出力例]

PC..PCPC..

..PCPCPCT.

PCPCT..PCT

.T.PCPCT.T

.PC..T..PC

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using P = pair<LL, LL>;
#define a first
#define b second

int main(){
    
    // 1. 入力情報.
    LL A, B;
    scanf("%lld %lld", &A, &B);
    
    // 2. 操作.
    LL ans = 0;
    queue<P> Q;
    Q.push({A, B});
    while(!Q.empty()){
        // キューから取り出す.
        P u = Q.front();
        Q.pop();
        
        // 大小関係の調整.
        if(u.a < u.b) swap(u.a, u.b);
        
        // カウント.
        LL q = u.a / u.b;
        LL r = u.a % u.b;
        ans += q;
        
        // 終了条件.
        if(r == 0){
            --ans;
            break;
        }
        
        // 更新.
        u.a -= q * u.b;
        
        // 追加.
        Q.push({u.a, u.b});
    }
    
    // 3. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using P = pair<LL, LL>;

#define a first

#define b second

int main(){

// 1. 入力情報.

LL A, B;

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

// 2. 操作.

LL ans = 0;

queue<P> Q;

Q.push({A, B});

while(!Q.empty()){

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

P u = Q.front();

Q.pop();

// 大小関係の調整.

if(u.a < u.b) swap(u.a, u.b);

// カウント.

LL q = u.a / u.b;

LL r = u.a % u.b;

ans += q;

// 終了条件.

if(r == 0){

--ans;

break;

}

// 更新.

u.a -= q * u.b;

// 追加.

Q.push({u.a, u.b});

}

// 3. 出力.

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

return 0;

}

[入力例]
3 8

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

[入力例]
1234567890 1234567890

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

[入力例]
1597 987

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

[入力例]
3141592 6535897

[出力例]
48

[入力例]
20230409 20230423

[出力例]
1445036

[入力例]
1234567890987654321 7

[出力例]
176366841569664902

[入力例]

3 8

[出力例]

※AtCoderテストケースより

[入力例]

1234567890 1234567890

[出力例]

※AtCoderテストケースより

[入力例]

1597 987

[出力例]

※AtCoderテストケースより

[入力例]

3141592 6535897

[出力例]

[入力例]

20230409 20230423

[出力例]

1445036

[入力例]

1234567890987654321 7

[出力例]

176366841569664902

■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--)
LL a[11];

int main(){
    
    // 1. 入力情報.
    int N, K;
    scanf("%d %d", &N, &K);
    set<LL> st;
    rep(i, N){
        scanf("%d", &a[i]);
        st.insert(a[i]);
    }
    
    // 2. 操作.
    LL ans = 0;
    while(K){
        // 先頭要素.
        ans = *st.begin();
        st.erase(st.begin());
        
        // 追加.
        rep(i, N) st.insert(ans + a[i]);
        
        // サイズ調整.
        while(st.size() > K) st.erase(--(st.end()));
        
        // デクリメント.
        --K;
    }
    
    // 3. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

LL a[11];

int main(){

// 1. 入力情報.

int N, K;

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

set<LL> st;

rep(i, N){

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

st.insert(a[i]);

}

// 2. 操作.

LL ans = 0;

while(K){

// 先頭要素.

ans = *st.begin();

st.erase(st.begin());

// 追加.

rep(i, N) st.insert(ans + a[i]);

// サイズ調整.

while(st.size() > K) st.erase(--(st.end()));

// デクリメント.

--K;

}

// 3. 出力.

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

return 0;

}

[入力例]
4 6
20 25 30 100

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

[入力例]
2 10
2 1

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

[入力例]
10 200000
955277671 764071525 871653439 819642859 703677532 515827892 127889502 881462887 330802980 503797872

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

[入力例]
5 123
314 159 265 358 979

[出力例]
1432

[入力例]
10 200000
333 1023 135 777 890 395 256 1234 321 999

[出力例]
201259

[入力例]
10 200000
598249 506436 1006871 522097 887419 682270 723768 608731 485561 195325

[出力例]
5953502

[入力例]

4 6

20 25 30 100

[出力例]

※AtCoderテストケースより

[入力例]

2 10

2 1

[出力例]

※AtCoderテストケースより

[入力例]

10 200000

955277671 764071525 871653439 819642859 703677532 515827892 127889502 881462887 330802980 503797872

[出力例]

5705443819

※AtCoderテストケースより

[入力例]

5 123

314 159 265 358 979

[出力例]

1432

[入力例]

10 200000

333 1023 135 777 890 395 256 1234 321 999

[出力例]

201259

[入力例]

10 200000

598249 506436 1006871 522097 887419 682270 723768 608731 485561 195325

[出力例]

5953502

■参照サイト
AtCoder Beginner Contest 297

2023年4月19日

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

C++の練習を兼ねて, AtCoder Beginner Contest 197 の問題F (Construct a Palindrome) を解いてみた.

■感想.
1. 問題F は, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 幅優先探索の復習が出来たので, 非常に良かったと思う.
3. 個人的には, 解説のロジックで, 計算できる点が, 非常に不思議な印象を受けた.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/abc197/editorial/994
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
using T3 = tuple<int, int, int>;
using vt = vector<T3>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
const int INF = 1010101010;

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    vt e;
    rep(i, M){
        char c[11];
        int a, b;
        scanf("%d %d %s", &a, &b, c);
        --a;
        --b;
        e.emplace_back(a, b, c[0] - 'a');
        e.emplace_back(b, a, c[0] - 'a');
    }
    
    // 2. 拡張グラフ作成.
    int n = N * N;
    vvi G(n);
    for(auto &p : e){
        for(auto &q : e){
            // 頂点を設定.
            int a = get<0>(p);
            int b = get<0>(q);
            int c = get<1>(p);
            int d = get<1>(q);
            int vac = get<2>(p);
            int vbd = get<2>(q);
            
            // 二辺の書かれた文字が異なる場合は, Skip.
            if(vac != vbd) continue;
            
            // 辺を張る.
            G[a * N + b].pb(c * N + d);
            G[c * N + d].pb(a * N + b);
        }
    }
    
    // 3. bfs.
    // https://ja.wikipedia.org/wiki/幅優先探索
    auto bfs = [&](vvi &G, int s, int* d) {
        // 空のキュー.
        queue<int> q;
        
        // 距離ゼロ.
        d[s] = 0;
        
        // 探索地点 s をキュー q に追加.
        q.push(s);
        while(!q.empty()){
            // キューから取り出す.
            int u = q.front();
            q.pop();
            
            // 隣接頂点をチェック.
            for(auto &e : G[u]) if(d[e] == INF && e != s) d[e] = d[u] + 1, q.push(e);
        }
    };
    
    // 4. 頂点の組 (1, N) に対応する頂点 からの 最短距離.
    int d[n];
    rep(i, n) d[i] = INF;
    bfs(G, 0 * N + (N - 1), d);
    
    // 5. 最短距離は？
    int ans = INF;
    rep(i, N){
        rep(j, N){
            // 5-1. 回文長(候補).
            int cur = d[i * N + j] + d[j * N + i];
            
            // 5-2. 偶数長.
            if(i == j) if(!(cur & 1)) ans = min(ans, cur);
            
            // 5-3. 奇数長.
            if(i != j) if(cur & 1) ans = min(ans, cur);
        }
    }
    
    // 6. 出力.
    printf("%d\n", (ans == INF) ? -1 : ans);
    return 0;
    
}

100

// 解き直し.

// https://atcoder.jp/contests/abc197/editorial/994

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

using vvi = vector<vi>;

using T3 = tuple<int, int, int>;

using vt = vector<T3>;

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

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

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

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

#define pb push_back

const int INF = 1010101010;

int main(){

// 1. 入力情報.

int N, M;

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

vt e;

rep(i, M){

char c[11];

int a, b;

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

--a;

--b;

e.emplace_back(a, b, c[0] - 'a');

e.emplace_back(b, a, c[0] - 'a');

}

// 2. 拡張グラフ作成.

int n = N * N;

vvi G(n);

for(auto &p : e){

for(auto &q : e){

// 頂点を設定.

int a = get<0>(p);

int b = get<0>(q);

int c = get<1>(p);

int d = get<1>(q);

int vac = get<2>(p);

int vbd = get<2>(q);

// 二辺の書かれた文字が異なる場合は, Skip.

if(vac != vbd) continue;

// 辺を張る.

G[a * N + b].pb(c * N + d);

G[c * N + d].pb(a * N + b);

}

// 3. bfs.

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

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

// 空のキュー.

queue<int> q;

// 距離ゼロ.

d[s] = 0;

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

q.push(s);

while(!q.empty()){

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

int u = q.front();

q.pop();

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

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

}

};

// 4. 頂点の組 (1, N) に対応する頂点からの最短距離.

int d[n];

rep(i, n) d[i] = INF;

bfs(G, 0 * N + (N - 1), d);

// 5. 最短距離は？

int ans = INF;

rep(i, N){

rep(j, N){

// 5-1. 回文長(候補).

int cur = d[i * N + j] + d[j * N + i];

// 5-2. 偶数長.

if(i == j) if(!(cur & 1)) ans = min(ans, cur);

// 5-3. 奇数長.

if(i != j) if(cur & 1) ans = min(ans, cur);

}

// 6. 出力.

printf("%d\n", (ans == INF) ? -1 : ans);

return 0;

}

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

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

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

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

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

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

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

[出力例]
3

[入力例]
8 13
1 2 c
1 2 b
3 1 a
4 3 b
5 4 a
5 4 c
5 6 c
2 5 c
5 8 a
8 2 a
8 7 a
7 6 b
7 6 c

[出力例]
6

[入力例]
20 50
14 10 c
11 14 m
5 20 t
17 17 t
12 14 f
15 17 m
12 17 r
8 20 q
16 11 z
13 8 g
8 5 g
9 10 c
17 15 k
16 19 i
5 11 b
5 16 h
17 14 c
2 9 u
16 4 t
16 18 k
1 16 p
18 19 r
14 6 z
20 3 x
1 17 x
4 7 w
17 9 a
5 1 d
4 8 f
5 12 o
1 5 h
10 3 e
5 18 h
9 7 r
13 18 d
5 18 s
2 18 j
12 8 l
20 19 h
15 16 k
4 13 p
20 7 b
3 10 x
6 19 j
13 8 e
6 10 i
16 15 j
19 19 t
10 14 e
11 18 t

[出力例]
5

[入力例]
30 150
27 13 i
2 14 r
25 26 k
25 14 s
2 4 y
14 16 l
7 11 a
1 12 c
27 14 w
17 1 z
17 22 l
4 22 u
26 9 w
15 25 w
21 3 e
23 21 x
28 14 y
8 4 b
1 19 h
28 14 a
12 9 r
4 21 i
3 26 p
9 3 o
19 11 j
17 11 k
13 29 i
14 7 t
25 7 t
7 14 z
7 7 p
21 4 l
24 13 t
19 5 b
17 25 s
19 29 q
26 13 c
28 19 j
20 29 k
18 19 h
13 18 b
10 26 q
8 21 i
15 10 t
4 4 p
19 3 c
9 20 w
22 3 i
3 26 f
10 17 r
19 24 f
4 11 j
17 29 k
9 1 h
1 1 a
25 22 e
22 23 h
28 29 b
4 22 t
18 17 p
3 28 w
21 18 c
11 1 m
9 26 m
11 28 l
23 17 o
23 2 a
13 3 u
12 22 c
13 26 x
9 9 j
18 25 w
18 22 u
5 28 h
21 4 t
30 11 q
2 24 c
27 19 u
14 16 e
4 5 r
8 15 d
8 30 l
14 10 u
6 2 j
29 15 z
17 12 j
20 27 l
24 14 o
29 2 f
8 7 j
14 8 u
5 30 d
26 4 o
7 30 e
22 25 c
29 15 z
12 11 h
24 17 q
11 8 n
24 2 f
8 30 u
30 6 a
24 5 q
10 9 h
19 30 f
30 8 s
3 16 c
29 24 a
29 28 l
6 21 k
20 17 x
2 24 n
12 8 t
20 21 q
30 3 a
13 18 z
14 17 t
11 10 a
27 9 p
29 14 z
3 26 p
26 20 m
25 15 z
6 24 h
4 19 h
3 11 z
6 20 t
16 28 v
6 15 z
19 4 l
3 20 o
5 3 u
21 13 h
7 30 a
17 16 o
24 11 m
8 13 x
30 8 k
5 18 y
12 7 m
20 14 i
6 25 v
21 14 f
30 25 m
17 3 j
24 12 a
5 28 i
24 17 q
22 6 o
23 17 h

[出力例]
5

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

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

[入力例]

8 8

1 2 a

2 3 b

1 3 c

3 4 b

4 5 a

5 6 c

6 7 b

7 8 a

[出力例]

※AtCoderのテストケースより

[入力例]

4 5

1 1 a

1 2 a

2 3 a

3 4 b

4 4 a

[出力例]

※AtCoderのテストケースより

[入力例]

3 4

1 1 a

1 2 a

2 3 b

3 3 b

[出力例]

-1

※AtCoderのテストケースより

[入力例]

4 3

1 2 a

2 3 b

3 4 a

[出力例]

[入力例]

8 13

1 2 c

1 2 b

3 1 a

4 3 b

5 4 a

5 4 c

5 6 c

2 5 c

5 8 a

8 2 a

8 7 a

7 6 b

7 6 c

[出力例]

[入力例]

20 50

14 10 c

11 14 m

5 20 t

17 17 t

12 14 f

15 17 m

12 17 r

8 20 q

16 11 z

13 8 g

8 5 g

9 10 c

17 15 k

16 19 i

5 11 b

5 16 h

17 14 c

2 9 u

16 4 t

16 18 k

1 16 p

18 19 r

14 6 z

20 3 x

1 17 x

4 7 w

17 9 a

5 1 d

4 8 f

5 12 o

1 5 h

10 3 e

5 18 h

9 7 r

13 18 d

5 18 s

2 18 j

12 8 l

20 19 h

15 16 k

4 13 p

20 7 b

3 10 x

6 19 j

13 8 e

6 10 i

16 15 j

19 19 t

10 14 e

11 18 t

[出力例]

[入力例]

30 150

27 13 i

2 14 r

25 26 k

25 14 s

2 4 y

14 16 l

7 11 a

1 12 c

27 14 w

17 1 z

17 22 l

4 22 u

26 9 w

15 25 w

21 3 e

23 21 x

28 14 y

8 4 b

1 19 h

28 14 a

12 9 r

4 21 i

3 26 p

9 3 o

19 11 j

17 11 k

13 29 i

14 7 t

25 7 t

7 14 z

7 7 p

21 4 l

24 13 t

19 5 b

17 25 s

19 29 q

26 13 c

28 19 j

20 29 k

18 19 h

13 18 b

10 26 q

8 21 i

15 10 t

4 4 p

19 3 c

9 20 w

22 3 i

3 26 f

10 17 r

19 24 f

4 11 j

17 29 k

9 1 h

1 1 a

25 22 e

22 23 h

28 29 b

4 22 t

18 17 p

3 28 w

21 18 c

11 1 m

9 26 m

11 28 l

23 17 o

23 2 a

13 3 u

12 22 c

13 26 x

9 9 j

18 25 w

18 22 u

5 28 h

21 4 t

30 11 q

2 24 c

27 19 u

14 16 e

4 5 r

8 15 d

8 30 l

14 10 u

6 2 j

29 15 z

17 12 j

20 27 l

24 14 o

29 2 f

8 7 j

14 8 u

5 30 d

26 4 o

7 30 e

22 25 c

29 15 z

12 11 h

24 17 q

11 8 n

24 2 f

8 30 u

30 6 a

24 5 q

10 9 h

19 30 f

30 8 s

3 16 c

29 24 a

29 28 l

6 21 k

20 17 x

2 24 n

12 8 t

20 21 q

30 3 a

13 18 z

14 17 t

11 10 a

27 9 p

29 14 z

3 26 p

26 20 m

25 15 z

6 24 h

4 19 h

3 11 z

6 20 t

16 28 v

6 15 z

19 4 l

3 20 o

5 3 u

21 13 h

7 30 a

17 16 o

24 11 m

8 13 x

30 8 k

5 18 y

12 7 m

20 14 i

6 25 v

21 14 f

30 25 m

17 3 j

24 12 a

5 28 i

24 17 q

22 6 o

23 17 h

[出力例]

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

個人用メモ帳

投稿

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

C++の練習を兼ねて, AtCoder Beginner Contest 260 の問題F (Find 4-cycle) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 260 の問題E (At Least One) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 248 の問題E (K-colinear Line) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 260 の問題C (Changing Jewels) ～問題D (Draw Your Cards) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 299 の問題E (Nearest Black Vertex) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 299 の問題C (Dango) ～問題D (Find by Query) を解いてみた.

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

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

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

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

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

C++の練習を兼ねて, AtCoder Beginner Contest 297 の問題C (PC on the Table) ～問題E (Kth Takoyaki Set) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 197 の問題F (Construct a Palindrome) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 260 の 問題F (Find 4-cycle) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 260 の 問題E (At Least One) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 248 の 問題E (K-colinear Line) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 260 の 問題C (Changing Jewels) ～ 問題D (Draw Your Cards) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 299 の 問題E (Nearest Black Vertex) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 299 の 問題C (Dango) ～ 問題D (Find by Query) を解いてみた.

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

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

C++の練習を兼ねて, AtCoder Beginner Contest 297 の 問題C (PC on the Table) ～ 問題E (Kth Takoyaki Set) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 197 の 問題F (Construct a Palindrome) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 260 の問題F (Find 4-cycle) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 260 の問題E (At Least One) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 248 の問題E (K-colinear Line) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 260 の問題C (Changing Jewels) ～問題D (Draw Your Cards) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 299 の問題E (Nearest Black Vertex) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 299 の問題C (Dango) ～問題D (Find by Query) を解いてみた.

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

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

C++の練習を兼ねて, AtCoder Beginner Contest 297 の問題C (PC on the Table) ～問題E (Kth Takoyaki Set) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 197 の問題F (Construct a Palindrome) を解いてみた.