C++ | 個人用メモ帳

2022年1月8日

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

C++の練習を兼ねて, 第九回アルゴリズム実技検定の問題K (ガソリンスタンド) を解いてみた.

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

■C++版プログラム(問題K／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
#define a first
#define b second

int main(){
    
    // 1. 入力情報.
    int N, M, Q, K;
    scanf("%d %d %d %d", &N, &M, &Q, &K);
    vi gasStation;
    map<int, int> m;
    rep(i, K){
        int a;
        scanf("%d", &a);
        a--;
        gasStation.pb(a);
        m[a] = 1;
    }
    vvi G(N);
    rep(i, M){
        int u, v;
        scanf("%d %d", &u, &v);
        u--;
        v--;
        G[u].pb(v);
        G[v].pb(u);
    }
    
    // 2. ガソリンスタンドの番号付け.
    int idx = -1;
    for(auto &p : m) p.b = ++idx;
    
    // 3. bfs.
    // https://ja.wikipedia.org/wiki/幅優先探索
    auto bfs = [&](vvi &G, int s, vvi &d){
        // 空のキュー.
        queue<int> q;
        
        // 探索地点 s をキュー q に追加.
        q.push(s);
        while(!q.empty()){
            // キューから取り出す.
            int u = q.front();
            q.pop();
            
            // 取り出した要素を処理.
            for(auto &e : G[u]) if(!d[m[s]][e] && e != s) d[m[s]][e] = d[m[s]][u] + 1, q.push(e);
        }
    };
    
    // 4. 各ガソリンスタンドから, 各街までの最短距離.
    vvi d(K, vi(N));
    for(auto &p : gasStation) bfs(G, p, d);
    
    // 5. クエリ回答.
    rep(i, Q){
        // クエリ情報.
        int s, t;
        scanf("%d %d", &s, &t);
        s--, t--;
        
        // 道を通る回数の最小値.
        int ans = 2020202020;
        for(auto &p : gasStation) ans = min(ans, d[m[p]][s] + d[m[p]][t]);
        
        // 出力.
        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

#define a first

#define b second

int main(){

// 1. 入力情報.

int N, M, Q, K;

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

vi gasStation;

map<int, int> m;

rep(i, K){

int a;

scanf("%d", &a);

a--;

gasStation.pb(a);

m[a] = 1;

}

vvi G(N);

rep(i, M){

int u, v;

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

u--;

v--;

G[u].pb(v);

G[v].pb(u);

}

// 2. ガソリンスタンドの番号付け.

int idx = -1;

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

// 3. bfs.

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

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

// 空のキュー.

queue<int> q;

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

q.push(s);

while(!q.empty()){

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

int u = q.front();

q.pop();

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

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

}

};

// 4. 各ガソリンスタンドから, 各街までの最短距離.

vvi d(K, vi(N));

for(auto &p : gasStation) bfs(G, p, d);

// 5. クエリ回答.

rep(i, Q){

// クエリ情報.

int s, t;

scanf("%d %d", &s, &t);

s--, t--;

// 道を通る回数の最小値.

int ans = 2020202020;

for(auto &p : gasStation) ans = min(ans, d[m[p]][s] + d[m[p]][t]);

// 出力.

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

}

return 0;

}

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

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

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

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

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

[出力例]
3
4
3
5
3
3
5

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

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

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

[入力例]

3 2 1 1

1 2

2 3

3 2

[出力例]

※AtCoderテストケースより

[入力例]

5 6 2 2

3 1

1 2

2 3

2 4

1 5

2 5

3 5

5 5

5 4

[出力例]

※AtCoderテストケースより

[入力例]

12 15 7 3

9 3 11

1 2

1 3

2 4

2 5

3 5

5 6

5 11

6 8

6 7

7 8

7 9

8 10

8 12

9 10

11 12

1 2

5 4

1 6

1 10

5 8

5 6

2 7

[出力例]

[入力例]

20 28 10 5

7 3 15 16 17

1 2

1 3

2 5

2 6

2 7

3 4

3 5

4 9

5 8

6 11

7 12

8 9

8 10

8 11

8 13

9 10

11 12

11 13

11 14

13 15

13 17

13 18

14 16

15 16

17 19

17 20

18 19

19 20

1 5

1 12

1 10

1 14

8 14

2 20

4 19

10 11

10 14

10 18

[出力例]

■参照サイト
第九回アルゴリズム実技検定

2022年1月8日2022年1月8日

C++ の動作確認をしてみた（６１５）

C++の練習を兼ねて, AtCoder Beginner Contest 116 の問題D (Various Sushi) を解いてみた.

■感想.
1. 問題Dは, 方針が見えなかったので, 解説を参考に, AC版に到達できた.
2. 個人的には, 優先順位付きキューを活用することで, 解説のロジックが, 実装できることに, 非常に面白く感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

本家のサイト AtCoder Beginner Contest 116 解説をご覧下さい.

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

// 解き直し.
// https://img.atcoder.jp/abc116/editorial.pdf
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using P = pair<int, int>;
using vp = vector<P>;
using PQD = priority_queue<P>;
using PQA = priority_queue<P, vector<P>, greater<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, K, t, d;
    scanf("%d %d", &N, &K);
    vp v;
    rep(i, N){
        scanf("%d %d", &t, &d);
        v.pb({d, t});
    }
    
    // 2. sort.
    sort(all(v));
    
    // 3. 集合 S.
    LL dSum = 0;
    map<int, int> m;
    PQA sIn;
    repr(i, N - 1, N - K){
        sIn.push({v[i].a, v[i].b});
        m[v[i].b]++;
        dSum += (LL)v[i].a;
    }
    
    // 4. 集合 S 以外.
    PQD sOut;
    rep(i, N - K) sOut.push({v[i].a, v[i].b});
    
    // 5. 寿司の入れ替え.
    LL ans = dSum + (LL)m.size() * (LL)m.size();
    while(!sIn.empty()){
        // 集合 S から, 取り出す.
        P x = sIn.top();
        sIn.pop();
        
        // ネタ の 種類数 が, 減る場合は, Skip.
        if(m[x.b] == 1) continue;
        
        // ネタ の 種類数 が, 変わらない場合は, おいしさ基礎ポイント, ネタの個数 を 更新.
        dSum -= x.a;
        m[x.b]--;
        
        // 集合 S 以外 を見る.
        while(!sOut.empty()){
            // 集合 S 以外 から 取り出す.
            P y = sOut.top();
            sOut.pop();
            
            // 集合 S に 含まれない ネタ を探す.
            if(!m.count(y.b)){
                // おいしさ基礎ポイント, ネタの個数 を 更新.
                dSum += y.a;
                m[y.b]++;
                
                // 満足度更新.
                ans = max(ans, dSum + (LL)m.size() * (LL)m.size());
                
                // 集合 S に 追加.
                sIn.push({y.a, y.b});
                
                // 次へ.
                break;
            }
        }
    }
    
    // 6. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://img.atcoder.jp/abc116/editorial.pdf

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using P = pair<int, int>;

using vp = vector;

using PQD = priority_queue;

using PQA = priority_queue<P, vector, greater>;

#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, K, t, d;

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

vp v;

rep(i, N){

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

v.pb({d, t});

}

// 2. sort.

sort(all(v));

// 3. 集合 S.

LL dSum = 0;

map<int, int> m;

PQA sIn;

repr(i, N - 1, N - K){

sIn.push({v[i].a, v[i].b});

m[v[i].b]++;

dSum += (LL)v[i].a;

}

// 4. 集合 S 以外.

PQD sOut;

rep(i, N - K) sOut.push({v[i].a, v[i].b});

// 5. 寿司の入れ替え.

LL ans = dSum + (LL)m.size() * (LL)m.size();

while(!sIn.empty()){

// 集合 S から, 取り出す.

P x = sIn.top();

sIn.pop();

// ネタの種類数が, 減る場合は, Skip.

if(m[x.b] == 1) continue;

// ネタの種類数が, 変わらない場合は, おいしさ基礎ポイント, ネタの個数を更新.

dSum -= x.a;

m[x.b]--;

// 集合 S 以外を見る.

while(!sOut.empty()){

// 集合 S 以外から取り出す.

P y = sOut.top();

sOut.pop();

// 集合 S に含まれないネタを探す.

if(!m.count(y.b)){

// おいしさ基礎ポイント, ネタの個数を更新.

dSum += y.a;

m[y.b]++;

// 満足度更新.

ans = max(ans, dSum + (LL)m.size() * (LL)m.size());

// 集合 S に追加.

sIn.push({y.a, y.b});

// 次へ.

break;

}

// 6. 出力.

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

return 0;

}

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

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

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

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

[入力例]
6 5
5 1000000000
2 990000000
3 980000000
6 970000000
6 960000000
4 950000000

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

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

[出力例]
70

[入力例]
20 7
8 764
5 313
10 861
6 544
8 1262
5 182
7 1202
3 130
5 850
3 981
5 590
10 771
6 50
4 1255
3 552
10 631
3 848
6 659
4 1091
6 1089

[出力例]
7777

[入力例]
50 10
11 6619934
5 1624101
12 5451794
3 9857183
5 1985828
11 11345963
2 5757194
3 6881103
9 1920811
14 8507495
14 5235040
10 4128252
15 1491606
11 768521
12 9822790
13 10069095
7 7116817
12 6611197
4 1247639
2 36843
9 10277716
3 19857
2 11561672
15 631937
5 7841766
13 2487890
13 13479705
8 1159151
2 12291992
7 2711313
7 1707463
10 985172
10 9394217
9 1626609
6 8081696
12 10331209
7 11885741
12 12131871
8 4794885
6 11949323
14 43035
10 9376463
3 12689389
12 7496508
3 8502162
14 4333674
10 15789860
6 9809565
9 7026972
5 1091517

[出力例]
123456789

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

[入力例]

5 3

1 9

1 7

2 6

2 5

3 1

[出力例]

※AtCoderテストケースより

[入力例]

7 4

1 1

2 1

3 1

4 6

4 5

[出力例]

※AtCoderテストケースより

[入力例]

6 5

5 1000000000

2 990000000

3 980000000

6 970000000

6 960000000

4 950000000

[出力例]

4900000016

※AtCoderテストケースより

[入力例]

12 5

1 2

2 5

1 7

1 5

7 10

7 3

5 10

4 4

1 6

2 9

5 8

4 9

[出力例]

[入力例]

20 7

8 764

5 313

10 861

6 544

8 1262

5 182

7 1202

3 130

5 850

3 981

5 590

10 771

6 50

4 1255

3 552

10 631

3 848

6 659

4 1091

6 1089

[出力例]

7777

[入力例]

50 10

11 6619934

5 1624101

12 5451794

3 9857183

5 1985828

11 11345963

2 5757194

3 6881103

9 1920811

14 8507495

14 5235040

10 4128252

15 1491606

11 768521

12 9822790

13 10069095

7 7116817

12 6611197

4 1247639

2 36843

9 10277716

3 19857

2 11561672

15 631937

5 7841766

13 2487890

13 13479705

8 1159151

2 12291992

7 2711313

7 1707463

10 985172

10 9394217

9 1626609

6 8081696

12 10331209

7 11885741

12 12131871

8 4794885

6 11949323

14 43035

10 9376463

3 12689389

12 7496508

3 8502162

14 4333674

10 15789860

6 9809565

9 7026972

5 1091517

[出力例]

123456789

■参照サイト
AtCoder Beginner Contest 116

2022年1月7日2022年1月7日

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

C++の練習を兼ねて, AtCoder Beginner Contest 100 の問題D (Patisserie ABC) を解いてみた.

■感想.
1. 問題Dは, 方針が見えなかったので, 解説を参考に, AC版に到達できた.
2. 解説にある符号を考慮した全探索で, 最大値を抽出するロジックが, 個人的には, 非常に面白く感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

本家のサイト AtCoder Beginner Contest 100 解説をご覧下さい.

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

// 解き直し.
// https://img.atcoder.jp/abc100/editorial.pdf
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vl = vector<LL>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
#define all(x) x.begin(), x.end()
LL x[1010], y[1010], z[1010];

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    rep(i, N) scanf("%lld %lld %lld", &x[i], &y[i], &z[i]);
    
    // 2. 全探索.
    LL ans = -202020202020202020;
    rep(i, 1 << 3){
        // 2-1. 符号.
        int s[3];
        rep(j, 3) s[j] = (i & (1 << j)) ? 1 : -1;
        
        // 2-2. 綺麗さ, おいしさ, 人気度 の (符号付き)合計.
        vl v;
        rep(j, N) v.pb(x[j] * s[0] + y[j] * s[1] + z[j] * s[2]);
        
        // 2-3. sort.
        sort(all(v));
        
        // 2-4. 大きい順に, M個.
        LL t = 0;
        rep(j, M) t += v[N - 1 - j];
        
        // 2-5. 最大値更新.
        ans = max(ans, t);
    }
    
    // 3. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://img.atcoder.jp/abc100/editorial.pdf

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vl = vector<LL>;

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

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

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

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

#define pb push_back

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

LL x[1010], y[1010], z[1010];

int main(){

// 1. 入力情報.

int N, M;

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

rep(i, N) scanf("%lld %lld %lld", &x[i], &y[i], &z[i]);

// 2. 全探索.

LL ans = -202020202020202020;

rep(i, 1 << 3){

// 2-1. 符号.

int s[3];

rep(j, 3) s[j] = (i & (1 << j)) ? 1 : -1;

// 2-2. 綺麗さ, おいしさ, 人気度の (符号付き)合計.

vl v;

rep(j, N) v.pb(x[j] * s[0] + y[j] * s[1] + z[j] * s[2]);

// 2-3. sort.

sort(all(v));

// 2-4. 大きい順に, M個.

LL t = 0;

rep(j, M) t += v[N - 1 - j];

// 2-5. 最大値更新.

ans = max(ans, t);

}

// 3. 出力.

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

return 0;

}

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

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

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

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

[入力例]
10 5
10 -80 21
23 8 38
-94 28 11
-26 -2 18
-69 72 79
-26 -86 -54
-72 -50 59
21 65 -32
40 -94 87
-62 18 82

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

[入力例]
3 2
2000000000 -9000000000 4000000000
7000000000 -5000000000 3000000000
6000000000 -1000000000 8000000000

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

[入力例]
5 3
144 15 -62
51 -54 131
135 -84 33
56 15 -20
-85 121 51

[出力例]
555

[入力例]
10 5
1040 -428 453
145 267 -916
177 664 1270
1111 -1139 800
-666 1125 872
214 -251 1048
663 103 -242
-696 964 108
1095 135 -450
915 193 -719

[出力例]
7777

[入力例]
30 12
2380290 -3874089 2225751
1397296 6482937 -1511776
936588 3280145 -5529143
3729139 798728 -1827712
4073447 -5934867 18870583
1465042 -2344443 1453900
4976600 4863530 1155788
831766 -6177751 6705880
-1387521 6911937 1305672
-2164290 1147022 9051983
-2071730 4990138 1143816
1486505 -8642625 1439353
2296136 -1319424 1215097
950669 1626133 2240346
-9345210 2486543 3900715
1967137 -1407849 1349998
1166523 3341920 2021650
-1377692 -2914269 1199173
1368469 -5705370 1025103
1823988 3869999 -1537211
-6939050 -1096274 -7844622
816106 -1355430 1813427
1202876 -249023 2224158
1120622 -9998050 4192084
-4739977 1249319 -1557077
992298 6869258 -1207735
1746909 1898002 -6951358
1903970 -8996164 1959390
-1541635 8794420 5602718
-4950188 1212287 1628534

[出力例]
123456789

100

101

102

103

104

105

106

107

108

109

110

111

112

113

[入力例]

5 3

3 1 4

1 5 9

2 6 5

3 5 8

9 7 9

[出力例]

※AtCoderテストケースより

[入力例]

5 3

1 -2 3

-4 5 -6

7 -8 -9

-10 11 -12

13 -14 15

[出力例]

※AtCoderテストケースより

[入力例]

10 5

10 -80 21

23 8 38

-94 28 11

-26 -2 18

-69 72 79

-26 -86 -54

-72 -50 59

21 65 -32

40 -94 87

-62 18 82

[出力例]

638

※AtCoderテストケースより

[入力例]

3 2

2000000000 -9000000000 4000000000

7000000000 -5000000000 3000000000

6000000000 -1000000000 8000000000

[出力例]

30000000000

※AtCoderテストケースより

[入力例]

5 3

144 15 -62

51 -54 131

135 -84 33

56 15 -20

-85 121 51

[出力例]

555

[入力例]

10 5

1040 -428 453

145 267 -916

177 664 1270

1111 -1139 800

-666 1125 872

214 -251 1048

663 103 -242

-696 964 108

1095 135 -450

915 193 -719

[出力例]

7777

[入力例]

30 12

2380290 -3874089 2225751

1397296 6482937 -1511776

936588 3280145 -5529143

3729139 798728 -1827712

4073447 -5934867 18870583

1465042 -2344443 1453900

4976600 4863530 1155788

831766 -6177751 6705880

-1387521 6911937 1305672

-2164290 1147022 9051983

-2071730 4990138 1143816

1486505 -8642625 1439353

2296136 -1319424 1215097

950669 1626133 2240346

-9345210 2486543 3900715

1967137 -1407849 1349998

1166523 3341920 2021650

-1377692 -2914269 1199173

1368469 -5705370 1025103

1823988 3869999 -1537211

-6939050 -1096274 -7844622

816106 -1355430 1813427

1202876 -249023 2224158

1120622 -9998050 4192084

-4739977 1249319 -1557077

992298 6869258 -1207735

1746909 1898002 -6951358

1903970 -8996164 1959390

-1541635 8794420 5602718

-4950188 1212287 1628534

[出力例]

123456789

■参照サイト
AtCoder Beginner Contest 100

2022年1月6日

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

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

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

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

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

// 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, M;
    scanf("%d %d", &N, &M);
    set<int> st[N];
    rep(i, M){
        int a, b;
        scanf("%d %d", &a, &b);
        a--, b--;
        
        // 辺(a, b) のみ保存(a < b に 注意).
        st[a].insert(b);
    }
    
    // 2. 連結成分の個数は？
    int ans[N + 1];
    rep(i, N + 1) ans[i] = 0;
    UnionFind uf(N + 2);
    repr(u, N - 1, 0){
        // 2-1. 頂点 u を 追加.
        // -> 連結成分 が, 1 増加したと見る.
        ans[u] = ans[u + 1] + 1;
        
        // 2-2. 頂点 u に 隣接している辺 を 追加.
        for(auto &v : st[u]){
            // UnionFind木で, 根(連結成分) が 異なる場合, 辺を追加.
            // -> 連結成分 が, 1 減少したと見る.
            if(!uf.same(u, v)){
                uf.unite(u, v);
                ans[u]--;
            }
        }
    }
    
    // 3. 出力.
    repx(i, 1, N + 1) printf("%d\n", ans[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--)

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

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

set<int> st[N];

rep(i, M){

int a, b;

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

a--, b--;

// 辺(a, b) のみ保存(a < b に注意).

st[a].insert(b);

}

// 2. 連結成分の個数は？

int ans[N + 1];

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

UnionFind uf(N + 2);

repr(u, N - 1, 0){

// 2-1. 頂点 u を追加.

// -> 連結成分が, 1 増加したと見る.

ans[u] = ans[u + 1] + 1;

// 2-2. 頂点 u に隣接している辺を追加.

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

// UnionFind木で, 根(連結成分) が異なる場合, 辺を追加.

// -> 連結成分が, 1 減少したと見る.

if(!uf.same(u, v)){

uf.unite(u, v);

ans[u]--;

}

// 3. 出力.

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

return 0;

}

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

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

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

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

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

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

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

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

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

[入力例]

6 7

1 2

1 4

1 5

2 4

2 3

3 5

3 6

[出力例]

※AtCoderテストケースより

[入力例]

8 7

7 8

3 4

5 6

5 7

5 8

6 7

6 8

[出力例]

[入力例]

15 15

1 2

2 3

1 3

4 5

5 6

4 6

7 8

8 9

7 9

10 11

11 12

10 12

13 14

14 15

13 15

[出力例]

[入力例]

36 40

1 2

1 3

1 4

1 5

1 6

2 7

2 27

2 28

3 10

3 29

3 30

4 19

4 35

4 36

5 16

5 33

5 34

6 13

6 31

6 32

7 8

7 9

8 26

9 26

10 11

10 12

11 22

12 22

13 14

13 15

14 23

15 23

16 17

16 18

17 24

18 24

19 20

19 21

20 25

21 25

[出力例]

■参照サイト
NECプログラミングコンテスト2021(AtCoder Beginner Contest 229)
Union-Find木

2022年1月5日

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

C++の練習を兼ねて, 第九回アルゴリズム実技検定の問題J (回転と反転) を解いてみた.

■感想.
1. 問題Jは, 方針を絞り込めたので, AC版に到達できた.
2. 実装に苦労したものの, 回転操作, 反転操作に関する数学的な知識を復習できたので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

本家のサイト第九回アルゴリズム実技検定の各リンクをご覧下さい.

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

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

// 変換表(二面体群).
// https://ja.wikipedia.org/wiki/二面体群
// a: 反時計回り(90度), b: 上下反転 と見て, 以下の8個を設定.
// 0: e
// 1: a
// 2: a * a
// 3: a * a * a
// 4: b
// 5: a * b
// 6: a * a * b
// 7: a * a * a * b
int t[8][8] = {
    {0, 1, 2, 3, 4, 5, 6, 7},
    {1, 2, 3, 0, 5, 6, 7, 4},
    {2, 3, 0, 1, 6, 7, 4, 5},
    {3, 0, 1, 2, 7, 4, 5, 6},
    {4, 7, 6, 5, 0, 3, 2, 1},
    {5, 4, 7, 6, 1, 0, 3, 2},
    {6, 5, 4, 7, 2, 1, 0, 3},
    {7, 6, 5, 4, 3, 2, 1, 0}
};

int main(){
    
    // 1. 入力情報.
    int N, Q;
    scanf("%d %d", &N, &Q);
    
    // 2. マス目初期化.
    int ans[N][N];
    rep(i, N) rep(j, N) ans[i][j] = 0;
    
    // 3. クエリ.
    vector<T3> q;
    int qs = 0; // クエリ終了時点のマス目の状態.
    rep(i, Q){
        // パターン取得.
        int f;
        scanf("%d", &f);
        
        // パターン①.
        if(f == 1){
            int x, y;
            scanf("%d %d", &x, &y);
            x--, y--;
            q.emplace_back(f, x, y);
        }
        
        // パターン②.
        if(f == 2){
            char c[11];
            scanf("%s", c);
            
            // 時計回り(90度).
            if(c[0] == 'A'){
                q.emplace_back(f, -1, 1);
                qs = t[qs][3];
            }
            
            // 反時計回り(90度).
            if(c[0] == 'B'){
                q.emplace_back(f, -1, 3);
                qs = t[qs][1];
            }
        }
        
        // パターン③.
        if(f == 3){
            char c[11];
            scanf("%s", c);
            
            // 上下反転.
            if(c[0] == 'A'){
                q.emplace_back(f, -1, 4);
                qs = t[qs][4];
            }
            
            // 左右反転.
            if(c[0] == 'B'){
                q.emplace_back(f, -1, 6);
                qs = t[qs][6];
            }
        }
    }
    
    // 4. マス目の状態は？
    for(auto &p : q){
        // クエリ情報.
        int f = get<0>(p);
        int ca = get<1>(p);
        int cb = get<2>(p);
        
        // パターン①.
        if(f == 1){
            int na = N - 1 - ca;
            int nb = N - 1 - cb;
            if(qs == 0) ans[ca][cb] ^= 1;
            if(qs == 1) ans[nb][ca] ^= 1;
            if(qs == 2) ans[na][nb] ^= 1;
            if(qs == 3) ans[cb][na] ^= 1;
            if(qs == 4) ans[na][cb] ^= 1;
            if(qs == 5) ans[cb][ca] ^= 1;
            if(qs == 6) ans[ca][nb] ^= 1;
            if(qs == 7) ans[nb][na] ^= 1;
        }
        
        // パターン② or ③.
        if(f != 1) qs = t[cb][qs];
    }
    
    // 5. 出力.
    rep(i, N){
        rep(j, N) printf("%d", ans[i][j]);
        puts("");
    }
    return 0;
    
}

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

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

// 変換表(二面体群).

// https://ja.wikipedia.org/wiki/二面体群

// a: 反時計回り(90度), b: 上下反転と見て, 以下の8個を設定.

// 0: e

// 1: a

// 2: a * a

// 3: a * a * a

// 4: b

// 5: a * b

// 6: a * a * b

// 7: a * a * a * b

int t[8][8] = {

{0, 1, 2, 3, 4, 5, 6, 7},

{1, 2, 3, 0, 5, 6, 7, 4},

{2, 3, 0, 1, 6, 7, 4, 5},

{3, 0, 1, 2, 7, 4, 5, 6},

{4, 7, 6, 5, 0, 3, 2, 1},

{5, 4, 7, 6, 1, 0, 3, 2},

{6, 5, 4, 7, 2, 1, 0, 3},

{7, 6, 5, 4, 3, 2, 1, 0}

};

int main(){

// 1. 入力情報.

int N, Q;

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

// 2. マス目初期化.

int ans[N][N];

rep(i, N) rep(j, N) ans[i][j] = 0;

// 3. クエリ.

vector<T3> q;

int qs = 0; // クエリ終了時点のマス目の状態.

rep(i, Q){

// パターン取得.

int f;

scanf("%d", &f);

// パターン①.

if(f == 1){

int x, y;

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

x--, y--;

q.emplace_back(f, x, y);

}

// パターン②.

if(f == 2){

char c[11];

scanf("%s", c);

// 時計回り(90度).

if(c[0] == 'A'){

q.emplace_back(f, -1, 1);

qs = t[qs][3];

}

// 反時計回り(90度).

if(c[0] == 'B'){

q.emplace_back(f, -1, 3);

qs = t[qs][1];

}

// パターン③.

if(f == 3){

char c[11];

scanf("%s", c);

// 上下反転.

if(c[0] == 'A'){

q.emplace_back(f, -1, 4);

qs = t[qs][4];

}

// 左右反転.

if(c[0] == 'B'){

q.emplace_back(f, -1, 6);

qs = t[qs][6];

}

// 4. マス目の状態は？

for(auto &p : q){

// クエリ情報.

int f = get<0>(p);

int ca = get<1>(p);

int cb = get<2>(p);

// パターン①.

if(f == 1){

int na = N - 1 - ca;

int nb = N - 1 - cb;

if(qs == 0) ans[ca][cb] ^= 1;

if(qs == 1) ans[nb][ca] ^= 1;

if(qs == 2) ans[na][nb] ^= 1;

if(qs == 3) ans[cb][na] ^= 1;

if(qs == 4) ans[na][cb] ^= 1;

if(qs == 5) ans[cb][ca] ^= 1;

if(qs == 6) ans[ca][nb] ^= 1;

if(qs == 7) ans[nb][na] ^= 1;

}

// パターン② or ③.

if(f != 1) qs = t[cb][qs];

}

// 5. 出力.

rep(i, N){

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

puts("");

}

return 0;

}

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

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

[入力例]
3 3
1 1 1
3 A
3 B

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

[入力例]
4 8
2 A
1 4 2
2 A
1 2 2
3 B
3 B
3 A
1 3 1

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

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

[出力例]
01000
00000
00000
00100
10010

[入力例]
6 5
1 2 3
2 A
3 B
1 3 2
3 A

[出力例]
000000
000000
000000
000000
000000
000000

[入力例]
10 20
1 2 3
2 A
3 B
1 1 9
3 A
1 7 6
3 B
1 3 7
3 A
1 8 3
2 A
3 B
1 3 5
3 A
3 B
1 3 7
3 A
2 B
2 A
1 10 1

[出力例]
0000000000
0000000001
0010010000
0000000000
0000001000
0000000000
0010000000
0000001000
0000000100
1000000000

[入力例]
20 50
1 3 18
2 B
3 A
1 17 1
2 B
1 12 10
2 A
2 A
1 7 18
3 A
1 2 13
2 B
1 5 5
2 A
3 B
1 13 18
3 A
3 B
3 A
1 15 10
2 B
2 A
2 A
1 5 7
1 10 1
3 B
2 B
3 A
1 6 17
3 A
3 B
1 15 10
2 A
1 3 20
3 A
3 A
1 8 9
3 B
1 13 6
3 A
1 18 17
2 A
1 17 5
2 B
3 A
3 B
1 4 13
3 A
2 B
1 6 15

[出力例]
00010000010000000100
00000000000000000000
00100000000000000000
00000000000000000000
00000000000000000000
00000001010000100000
00001000000000000100
00100000000000001000
00000000001000000000
00000000000000000000
00000000000000000000
00000000000010000000
00000000000000000000
00000000000000000000
00000000001000001000
00000000000000010000
00000000000000010100
00000000000000000000
00000000000010000000
00000000000000000000

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

[入力例]

3 2

1 1 1

2 A

[出力例]

001

000

※AtCoderテストケースより

[入力例]

3 3

1 1 1

3 A

3 B

[出力例]

000

001

※AtCoderテストケースより

[入力例]

4 8

2 A

1 4 2

2 A

1 2 2

3 B

3 A

1 3 1

[出力例]

0000

0100

0000

※AtCoderテストケースより

[入力例]

5 15

3 A

2 B

1 1 1

3 B

2 A

2 B

1 2 3

2 B

1 3 2

3 A

1 4 5

3 B

1 3 4

1 2 5

2 A

[出力例]

01000

00000

00100

10010

[入力例]

6 5

1 2 3

2 A

3 B

1 3 2

3 A

[出力例]

000000

[入力例]

10 20

1 2 3

2 A

3 B

1 1 9

3 A

1 7 6

3 B

1 3 7

3 A

1 8 3

2 A

3 B

1 3 5

3 A

3 B

1 3 7

3 A

2 B

2 A

1 10 1

[出力例]

0000000000

0000000001

0010010000

0000000000

0000001000

0000000000

0010000000

0000001000

0000000100

1000000000

[入力例]

20 50

1 3 18

2 B

3 A

1 17 1

2 B

1 12 10

2 A

1 7 18

3 A

1 2 13

2 B

1 5 5

2 A

3 B

1 13 18

3 A

3 B

3 A

1 15 10

2 B

2 A

1 5 7

1 10 1

3 B

2 B

3 A

1 6 17

3 A

3 B

1 15 10

2 A

1 3 20

3 A

1 8 9

3 B

1 13 6

3 A

1 18 17

2 A

1 17 5

2 B

3 A

3 B

1 4 13

3 A

2 B

1 6 15

[出力例]

00010000010000000100

00000000000000000000

00100000000000000000

00000000000000000000

00000001010000100000

00001000000000000100

00100000000000001000

00000000001000000000

00000000000000000000

00000000000010000000

00000000000000000000

00000000001000001000

00000000000000010000

00000000000000010100

00000000000000000000

00000000000010000000

00000000000000000000

■参照サイト
第九回アルゴリズム実技検定

2022年1月4日

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

C++の練習を兼ねて, 第九回アルゴリズム実技検定の問題I (直通エレベーター) を解いてみた.

■感想.
1. 問題Iは, 方針を絞り込めたので, AC版に到達できた.
2. ダイクストラ法(応用版, 座標圧縮)の復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

本家のサイト第九回アルゴリズム実技検定の各リンクをご覧下さい.

■C++版プログラム(問題I／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
#define pb push_back
const LL INF = 2e18 + 1;

struct edge{
    int n; // 次の頂点.
    LL c;  // コスト.
    bool operator < (const edge &E) const{ return c > E.c; }
};

vector<edge> G[202020];
LL a[101010], b[101010], c[101010];

int main(){
    
    // 1. 入力情報.
    LL N;
    int M;
    scanf("%lld %d", &N, &M);
    map<LL, int> m;
    rep(i, M){
        scanf("%lld %lld %lld", &a[i], &b[i], &c[i]);
        m[a[i]] = 1;
        m[b[i]] = 1;
    }
    m[1] = 1;
    m[N] = 1;
    
    // 2. 座標圧縮.
    int idx = -1;
    for(auto &p : m) p.b = ++idx;
    
    // 3. グラフ構築(階段).
    LL cBef, cCur;
    int vBef = -1, vCur;
    for(auto &p : m){
        // 今回分更新.
        cCur = p.a;
        vCur = p.b;
        
        // 辺を追加.
        if(vBef != -1){
            G[vBef].pb(edge{vCur, cCur - cBef});
            G[vCur].pb(edge{vBef, cCur - cBef});
        }
        
        // 前回分更新.
        cBef = cCur;
        vBef = vCur;
    }
    
    // 4. グラフ構築(エレベーター).
    rep(i, M){
        int u = m[a[i]];
        int v = m[b[i]];
        G[u].pb(edge{v, c[i]});
        G[v].pb(edge{u, c[i]});
    }
    
    // 5. ダイクストラ法.
    // https://ja.wikipedia.org/wiki/ダイクストラ法
    auto dijkstra = [&](int s, LL* d, int* memo){
        // 初期化.
        priority_queue<edge> pq;
        
        // 始点設定.
        d[s] = 0;
        pq.push({s, 0LL});
        
        // キュー pq が 空になるまで, 探索.
        while(!pq.empty()){
            // 探索を継続するために, 頂点を取得.
            edge e = pq.top();
            pq.pop();
            int cn = e.n;
            LL cc = e.c;
            
            // 訪問済みフラグ設定.
            if(memo[cn]) continue;
            memo[cn]++;
            
            // 各隣接する頂点について, 距離を確認し, 移動コストを更新.
            for(auto &g : G[cn]){
                // 移動コスト更新.
                int nn = g.n;
                LL nc = cc + g.c;
                if(d[nn] > nc) d[nn] = nc, pq.push({nn, nc});
            }
        }
    };
    
    // 6. 各頂点までの, 最短コストを求める.
    LL d[idx + 1];     // 頂点 0 からの距離.
    int memo[idx + 1]; // 訪問済みフラグ.
    rep(i, idx + 1) d[i] = INF, memo[i] = 0;
    dijkstra(0, d, memo);
    
    // 7. 出力.
    printf("%lld\n", d[idx]);
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

110

111

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

#define pb push_back

const LL INF = 2e18 + 1;

struct edge{

int n; // 次の頂点.

LL c; // コスト.

bool operator < (const edge &E) const{ return c > E.c; }

};

vector<edge> G[202020];

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

int main(){

// 1. 入力情報.

LL N;

int M;

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

map<LL, int> m;

rep(i, M){

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

m[a[i]] = 1;

m[b[i]] = 1;

}

m[1] = 1;

m[N] = 1;

// 2. 座標圧縮.

int idx = -1;

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

// 3. グラフ構築(階段).

LL cBef, cCur;

int vBef = -1, vCur;

for(auto &p : m){

// 今回分更新.

cCur = p.a;

vCur = p.b;

// 辺を追加.

if(vBef != -1){

G[vBef].pb(edge{vCur, cCur - cBef});

G[vCur].pb(edge{vBef, cCur - cBef});

}

// 前回分更新.

cBef = cCur;

vBef = vCur;

}

// 4. グラフ構築(エレベーター).

rep(i, M){

int u = m[a[i]];

int v = m[b[i]];

G[u].pb(edge{v, c[i]});

G[v].pb(edge{u, c[i]});

}

// 5. ダイクストラ法.

// https://ja.wikipedia.org/wiki/ダイクストラ法

auto dijkstra = [&](int s, LL* d, int* memo){

// 初期化.

priority_queue<edge> pq;

// 始点設定.

d[s] = 0;

pq.push({s, 0LL});

// キュー pq が空になるまで, 探索.

while(!pq.empty()){

// 探索を継続するために, 頂点を取得.

edge e = pq.top();

pq.pop();

int cn = e.n;

LL cc = e.c;

// 訪問済みフラグ設定.

if(memo[cn]) continue;

memo[cn]++;

// 各隣接する頂点について, 距離を確認し, 移動コストを更新.

for(auto &g : G[cn]){

// 移動コスト更新.

int nn = g.n;

LL nc = cc + g.c;

if(d[nn] > nc) d[nn] = nc, pq.push({nn, nc});

}

};

// 6. 各頂点までの, 最短コストを求める.

LL d[idx + 1]; // 頂点 0 からの距離.

int memo[idx + 1]; // 訪問済みフラグ.

rep(i, idx + 1) d[i] = INF, memo[i] = 0;

dijkstra(0, d, memo);

// 7. 出力.

printf("%lld\n", d[idx]);

return 0;

}

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

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

[入力例]
1000000000000000000 1
1 1000000000000000000 1000000000000000000

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

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

[出力例]
7

[入力例]
100 10
1 10 5
5 17 7
18 35 12
49 66 11
77 95 8
36 52 9
10 25 7
40 75 47
51 68 10
28 41 11

[出力例]
65

[入力例]
20220104 20
828865 4804632 12069969
6295187 13558375 1837197
3310273 11010080 7881068
5772550 14219264 18758563
4225815 8738497 6630771
6879164 10620764 10892637
4838718 8073754 14372199
6291069 10471126 70549
558133 1418658 9345163
8215556 18066689 18750539
8371221 8912288 13240335
6496981 12139308 15053771
7416355 12359442 7081448
116798 5578623 17894867
5948188 12066446 315682
932978 4289526 519795
3579073 9810527 15940312
8175707 15948535 19959019
4000956 6515736 2966577
8639132 11793341 15657568

[出力例]
11580774

[入力例]
202112111300 30
2836912071 8265759792 18349207920
6321404409 7117150178 5191319749
5133174124 6981490113 4115025861
8073790036 13562620650 576427819
2311345537 5346249323 15395778052
5232172781 6860771277 4967211588
9930875748 18298309556 1894862604
5493633256 9764925778 4529928865
2129123401 12177775551 771175460
6877686882 11695500319 16000522151
613446757 1219290120 8543162814
4425468693 6201308906 17815170784
760738956 10235609132 1569024502
5970087903 12676828451 5368533553
847837589 8203683049 654051583
3366379489 5918321181 16417033782
8019754324 14372671034 4782560986
10048397218 14291129034 14916272145
4180881599 8564813978 6154260194
8335300636 9618931292 7974820034
8247089832 17234489737 112903612
9226479498 12245429510 17492201072
584745120 5781270528 11323123105
1266934563 5758721472 12198029546
5226702368 8951155543 783723174
9715667921 18083960295 14479844635
5325151693 9867219235 787867457
4579272049 9781286327 1477152595
564092880 5096514264 17221220356
1621294237 11411345457 12861090392

[出力例]
186535821129

100

101

102

103

[入力例]

10 2

2 5 1

4 10 3

[出力例]

※AtCoderテストケースより

[入力例]

1000000000000000000 1

1 1000000000000000000 1000000000000000000

[出力例]

999999999999999999

※AtCoderテストケースより

[入力例]

11 3

2 4 1

5 7 1

8 10 1

[出力例]

[入力例]

100 10

1 10 5

5 17 7

18 35 12

49 66 11

77 95 8

36 52 9

10 25 7

40 75 47

51 68 10

28 41 11

[出力例]

[入力例]

20220104 20

828865 4804632 12069969

6295187 13558375 1837197

3310273 11010080 7881068

5772550 14219264 18758563

4225815 8738497 6630771

6879164 10620764 10892637

4838718 8073754 14372199

6291069 10471126 70549

558133 1418658 9345163

8215556 18066689 18750539

8371221 8912288 13240335

6496981 12139308 15053771

7416355 12359442 7081448

116798 5578623 17894867

5948188 12066446 315682

932978 4289526 519795

3579073 9810527 15940312

8175707 15948535 19959019

4000956 6515736 2966577

8639132 11793341 15657568

[出力例]

11580774

[入力例]

202112111300 30

2836912071 8265759792 18349207920

6321404409 7117150178 5191319749

5133174124 6981490113 4115025861

8073790036 13562620650 576427819

2311345537 5346249323 15395778052

5232172781 6860771277 4967211588

9930875748 18298309556 1894862604

5493633256 9764925778 4529928865

2129123401 12177775551 771175460

6877686882 11695500319 16000522151

613446757 1219290120 8543162814

4425468693 6201308906 17815170784

760738956 10235609132 1569024502

5970087903 12676828451 5368533553

847837589 8203683049 654051583

3366379489 5918321181 16417033782

8019754324 14372671034 4782560986

10048397218 14291129034 14916272145

4180881599 8564813978 6154260194

8335300636 9618931292 7974820034

8247089832 17234489737 112903612

9226479498 12245429510 17492201072

584745120 5781270528 11323123105

1266934563 5758721472 12198029546

5226702368 8951155543 783723174

9715667921 18083960295 14479844635

5325151693 9867219235 787867457

4579272049 9781286327 1477152595

564092880 5096514264 17221220356

1621294237 11411345457 12861090392

[出力例]

186535821129

■参照サイト
第九回アルゴリズム実技検定

2022年1月4日

C++ の動作確認をしてみた（６１０）

C++の練習を兼ねて, AtCoder Regular Contest 048 の問題C (足の多い高橋君) を解いてみた.

■感想.
1. 問題Cは, 方針が見えなかったので, 解説を参考に, AC版に到達できた.
2. 最大公約数を求めるロジックに落とし込む, 解法の考え方が, 非常に興味深く感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

本家のサイト AtCoder Regular Contest 048 解説をご覧下さい.

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

// 解き直し.
// https://www.slideshare.net/chokudai/arc048
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
const LL MOD = 1e9 + 7;
LL L[101010];

// Fermat's little theorem から, 大きな冪乗の計算を行う.
// @param a: べき乗したい正整数.
// @param b: 指数.
// @return:  べき乗した計算結果(mod版).
LL mPow(LL a, LL b){
    LL t = 1;
    while(b){
        if(b & 1) t = (t * a) % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return t;
}

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    LL D = 202020202020202020;
    rep(i, N){
        scanf("%lld", &L[i]);
        D = min(D, L[i]);
    }
    
    // 2. 最大公約数.
    LL g = 0;
    rep(i, N) g = __gcd(g, L[i] - D);
    
    // 3. 出力.
    printf("%lld\n", mPow(2LL, D + (g + 1) / 2));
    return 0;
    
}

// 解き直し.

// https://www.slideshare.net/chokudai/arc048

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

const LL MOD = 1e9 + 7;

LL L[101010];

// Fermat's little theorem から, 大きな冪乗の計算を行う.

// @param a: べき乗したい正整数.

// @param b: 指数.

// @return: べき乗した計算結果(mod版).

LL mPow(LL a, LL b){

LL t = 1;

while(b){

if(b & 1) t = (t * a) % MOD;

a = a * a % MOD;

b >>= 1;

}

return t;

}

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

LL D = 202020202020202020;

rep(i, N){

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

D = min(D, L[i]);

}

// 2. 最大公約数.

LL g = 0;

rep(i, N) g = __gcd(g, L[i] - D);

// 3. 出力.

printf("%lld\n", mPow(2LL, D + (g + 1) / 2));

return 0;

}

[入力例]
3
2
4
8

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

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

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

[入力例]
5
700000000
20000000
9000000
600000000
30000000

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

[入力例]
3
7
5
3

[出力例]
16

[入力例]
10
6066
2022
8088
2022
10110
18198
4044
12132
10110
6066

[出力例]
739772112

[入力例]
15
121021629
645189559
100861324
1693525419
1915288774
1108876574
625029254
1653204809
181502544
927433829
1592723894
60540714
806471999
947594134
1068555964

[出力例]
342555388

[入力例]

[出力例]

※AtCoderのテストケースより

[入力例]

[出力例]

※AtCoderのテストケースより

[入力例]

700000000

20000000

9000000

600000000

30000000

[出力例]

861838989

※AtCoderのテストケースより

[入力例]

[出力例]

[入力例]

6066

2022

8088

2022

10110

18198

4044

12132

10110

6066

[出力例]

739772112

[入力例]

121021629

645189559

100861324

1693525419

1915288774

1108876574

625029254

1653204809

181502544

927433829

1592723894

60540714

806471999

947594134

1068555964

[出力例]

342555388

■参照サイト
AtCoder Regular Contest 048

2022年1月3日

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

C++の練習を兼ねて, 第九回アルゴリズム実技検定の問題H (最長非共通部分列) を解いてみた.

■感想.
1. 問題Hは, 方針が見えなかったので, 解説を参考にしたところ, AC版に到達できた.
2. 苦手な動的計画法の訓練を積めたので, 非常に良かったと思う.
3. 最長非共通部分列(Longest Non-Common Subsequence)に関して, その概念を, 学習できたと思う.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

本家のサイト第九回アルゴリズム実技検定の各リンクをご覧下さい.

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

// 解き直し.
// https://atcoder.jp/contests/past202112-open/editorial/3129
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vs = vector<set<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 dp[5050][5050];

int main(){
    
    // 1. 入力情報.
    char s[5050], t[5050];
    scanf("%s %s", s, t);
    
    // 2. dp更新.
    int N = strlen(s);
    int M = strlen(t);
    rep(a, N){
        rep(b, M){
            // S[a] と T[b] を 両方使う.
            if(s[a] != t[b]) dp[a + 1][b + 1] = max(dp[a + 1][b + 1], dp[a][b] + 1);
            
            // S[a] と T[b] の 少なくとも一方を使わない場合.
            dp[a + 1][b + 0] = max(dp[a + 1][b + 0], dp[a][b]);
            dp[a + 0][b + 1] = max(dp[a + 0][b + 1], dp[a][b]);
            dp[a + 1][b + 1] = max({dp[a + 1][b + 1], dp[a + 1][b + 0], dp[a + 0][b + 1]});
        }
    }
    
    // 3. 出力.
    printf("%d\n", dp[N][M]);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/past202112-open/editorial/3129

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vs = vector<set<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 dp[5050][5050];

int main(){

// 1. 入力情報.

char s[5050], t[5050];

scanf("%s %s", s, t);

// 2. dp更新.

int N = strlen(s);

int M = strlen(t);

rep(a, N){

rep(b, M){

// S[a] と T[b] を両方使う.

if(s[a] != t[b]) dp[a + 1][b + 1] = max(dp[a + 1][b + 1], dp[a][b] + 1);

// S[a] と T[b] の少なくとも一方を使わない場合.

dp[a + 1][b + 0] = max(dp[a + 1][b + 0], dp[a][b]);

dp[a + 0][b + 1] = max(dp[a + 0][b + 1], dp[a][b]);

dp[a + 1][b + 1] = max({dp[a + 1][b + 1], dp[a + 1][b + 0], dp[a + 0][b + 1]});

}

// 3. 出力.

printf("%d\n", dp[N][M]);

return 0;

}

[入力例]
abc
aba

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

[入力例]
aaaaaa
a

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

[入力例]
abra
cadabra

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

[入力例]
oooopppqqrrrsss
oooppqrrssstttt

[出力例]
12

[入力例]
yfbtiphgpoierzzkhrnyawhgjqbnsciaiditqouwhtfxhamwryqtzguzrafvgifexvvmiktzepdwnvesuvmsgigxizbxrynyskypjrthvvicmifkyffqxkiouieoidjtsxwwjqaflytcmzvmpacmalcuucqtujpagpmtnpdtadlvosihreliuhfwssakqknyiqowqlww
zfdxmlcbgrubvnalctxasvihvjweishewyhvvziaoyyybklzhcomsgjncqcscfzdyknlbmdrxligotjlshferdfwqkoastrqcqfepovdxmpjobgujagplfbnrnbvdntpnkrvbkdjznjybqpcnbrxpkeolbrmyjvscroszlravwxsribentjjwcisvujyjlpvnwvtkrca

[出力例]
197

[入力例]
cuwllsesaoaanxfghjytmttwsmdrmgfisujygpusbxgwdsikzuyixsbtpnwuwuawarsesfmnhuijjhfetoovqwuezcxqhneuyjnfibobwgyjpgamvdpresibyqrpcyusskijajdalxyvqgldyqcukldztmuaxnfqmocvxjrlziivycyrgdfbqvbysdtydffvwnsivkicgdmtmcugfkhscbuuvbsqfaykqiiseztmebmzdksulvxsyqqyekwfgntubqqggtlegcophdaedonulmnvqyunwukrclpsezrwoplyxxqsmbvlykctngbcyhgfaydfbtdetknxibyessslaghwrqizaafjlxgrokbdexyyxelmgesdlegamceyobadkylenxntzogqmgohmwgzsilajuxohgxjxaloryjsbjsrutzcilgwrmfwlbtfptwkxyfjywihisvpaozszcpmwhjtpwelkmfjfjnfstyaukhscantysqiljidoikimpmngpsmijhklknshqhcubhfgdcfgkifayxdlvaakunebttqhhchkoyknrlwwpyqucipsvxntlkqrwrgflupqdetxinhzhaesriqtdngrxuxccoedyhoesdydenrutgfqkrvuecajgkdxfdufptcrxmsbgllzhniarmnivvdkadflexzfpooomhcydasfrcshfbyetninsxnutpiyqrbtzqcdsujcznnptplcrjiddnnurlervukhhqeweyiypqrznznfxwggrfqloloehthkrthnxqqceqdteyinpcvuwzrximynobuglgwvsczkvebtngsgvyocvnqjnaanelwaamkhwlmrwihlgfplojnvywwjcizwycnbyvgpulydcfyukfucdvlxxgzcvwlqchommydyrfukhqzlweqvcrpqawuabfclpjohsiidfrtbsdfzohkkjsvlvkwujbfrlorlqakoiwonpjmwgrkegiacbco
fwmskagltnakcfqnfwsqtelzinginpilrbjchyfbjkgqjhnrrzcmqbqvcompavodojucybjlkfhqsvvibqcrjtmsbzcmuzmzrpnngaouepcscmmohyojyhrdyijesqfocykarhfmxozhqeaawogsbethpydovwnipohocnratyaagqjgmudgwxigxyyvzaigkinpuabgzsrcqbcxmdcugpovtnlaiyxreifjjiifpwtvnlwemocuijllpxhdmvvliioqvqrfoaqebopripetkludfcucjbhqlrtipoxyrfwfclmhvbbrebwcezjzydrwnudfzaykbvieabjezocryfrbitlyapjcffbaqmgutydvoyzzallhnuqnflqyjlfdajgwajkdjawjxfixuycyhffsayfjjrwyvnawqdnpbionwgktolanaxzuclwltsngdqfcjdvwvuaelupmoxalmsgjfrrafmvoeiqbtdrpfowapyiwfegvsdvytijbzglpzxcvnddqiijthfngxwtcnqosoodogpbnvbzovdsbniyokqiqhkmhofzhgarxetezzchmhrkuwliwwrlcetgxhwddxrdunwjaqrpfyfoniuopcxhxwzkzvypkvykslkchudkxgrrjhqmfkclslsccedueymrsdiaejfjngvyvarongoewfmnfxkqtxcvnhujprdskjgmcqmezwmrtauhnenfojpwofvpvrqzoiuecnndpnnauzvpomtcdimjbgcpewpkcyyimzqunxthtzhcxuazuuhynzdtrvxevitgfmgpcjlhqetmkonmzairztyhghtqakkfcqbrpxzvgasrsunnlrhyomxnoihilfnkckaqvstlwuahbupufwzleplwjvyllhgndzcptjheuekrnimvaykhinxivupxpxuzbnggjubvaeemencunpzcosjvndsmfvyvfsstenakcdsgxwnmegaykmmdcsnzxblvt

[出力例]
985

[入力例]
tjgqvvdipknzaeedgpuwbtowamjeeszoeptnnwkjvetrkcrpbnykpvxvxkmafjmojswxvxzlulxlzkdcdgwprvulgdxjwadenwyagqhnyamttckhrugrybquhnddojizvotaowmoczmwvzmojasuyqvsiymzmirsoxqqzixlkfdrdanjzsnhhjksiszhejyjxjujhwaqaalbmjqwssiqcchsylvezfeviijzzobiyeyestlajsnlbwodlgwsufoqtupwnppcbwiryhwyhhkyciscfmmkqaubysmmrqwxgqprtutnbwyrzinpmkmtdtfchqpvqankqdlpehzrsbytdflyerlrbkwjwkrshbjijqvqfbgvmoocpuqephppczawzcfuiolvsdpcwidoewthgkwnsutdaazpnwygfkoxatecipqoaoglgrckdufenwhjuycxmybfdpjtoilmjxzjcdwvvqkynfevakjyasmqnbbwfybfcejhseuodowvlnznewqunixjktsqbuwkwsjupxszbjxogxgmxdwgmdzrbogvmsfyklxctnxopcviuoxjlrepdgydgxkjjxoqxxzqlhmaxdwayafcphklrupuuitvapphmkgwgxrquggkhnftqvgdwpibmlepvglfftsuczcqsbbwhkybefdjzdbpyxnlajpqrjtqdsdsrbvejlsfenpjogmspqmpbxnhcxxgsyafxjyulkcbauxzegzvndqwdfxtuuoxqbingaasqukhzhympmirgnhczytrfpdtezrstxtgssrolkgxixntfkfcysknbvtwjqxffljieuxahyylbcuhpywxjfvaiowjuuxwghfyvvrujctjqaynhlovucvdthektngptqcjbzwcidogjncihfnfpmosfkbmgoakyrxhqcwukdlrsqcsybhchmtbqkynswxqcaesnkgoaacddybwmxkhuxqqditkdrzneneeccllxuhzcsxfrnmffojtopguoxlvsiyzomfpoyoduiuhhxsiixpqbhsivyxkefaujmfevuhxbwynwqfjfhfobolnumvvoyydzoezldblgnnnwcscajuwicymyjdjdpyduycinojkmvamfxjdfiknuptpdkmwvhelssvsdjojtvrgocrwmftacorkqtsqyhjnpxnhbfjspingmjiaycqfmicfehtsutsfgvhkohqvwiebohencjgnwnnpwzvkumwwankrzhvfmfopqfddwvckhtgjcvjqvztvhzryprmocrsyvjrhghqekimygtaciqzcbvzujjptsvrouoqhveecbccssdzzxaxwfboyxaozplhdryqudahniwmgmxfapgsmwxnximgbucxbpcclyrexiqufafvjvphbbeziqryihbxrlllfltnwytmoarlxbwihiaosmbiqlwgeynfukwalhorqfpahlyzkeehfauulbekusyxdftdbqudczkdqtuujcjlfikjzxgobwzwakmueykehpovfhuhiiasbhucpotjddrwtnbfgijnfwylozwnclimdwnivhulmrprqbtesdkjiuqlchzagdaxxoiojfhewwwguwnndqnrjciouakgklgtaittvjibzvovtehyhtqrubhgcdftflyscstlmkqeuvsuxfzslprioqymdvgcstbxqvdzpnwtudndnsjmhdrgzuafrllgbkrfmenarowdjwebyqravatgiqbuympdyqfunspxoklbyasrtibikwbvnnrsxzxewkejfbydiliyktdfzhszkofdvnqvkqezaucqjobvrcuwwhnqypnwmmtqzjxuggfhtjijcifbakepkvxxlzwkmyrtqhywslvwwpeoyxsrktkjoouvukqjizkcyoihmwwmyafomuuxysgvgypnwkjnjdzojxlwxzkmnecwjwljoadctwwfjxircxlvooxyvehqoywoefvdsiipocwjpzurzbwdsbnhjongsrkddksxqfoyjeybjhdfijvbcvzxoahduambjlgiryvjhgtzahssjeuvpghzrvxwiqkkmnrhrszlgfaykjdgocmdzmbtrfgoyekmlozxeopirxmluoxqjrixxgnlvyymuynmrxlimllfbsngvfklgwgotkykrlsrgiztauhuaejodhenbcejtfofktsmtsmbycgdbuaozghxopehhpuuqkqidngibqrbocrifqczzczmrdtzfutmvaotosymlnszyfkmgpkrfwldehjfblyxpbamnskkkehriazbedwdjmfzpjhhkpqwbjgocxireiujvyoxctrbdqgbyiyavulokjdbldaauraqdzswyskbqmtazvmjmzlnsuccdlhckfvgzrvlpicwhgmbbqpvkzholayimpvdewtjvqblurucqokcpzvinqjwmsfhuslvwogfmgsuirttcsgusegvbyullwwvgbaawmdkdtypxuftw
zmusswrdosvdpdmjmnxixmrdafjwzicvgouewzoxawirtfjybalmgepmuyshctdeynkjxuqrbzrsmtfklbwabjqxhtefyeujhbeucruirfikyfbbefpjvrnkegwowgqdocycgfaqawvyeowoxqxfdrhkbimkaycysijshsfxwybtnyyrrvbjwvwrlykuixvminybjiekdfugcoiutqzmbuvedfburfqwodxrqdecvnmsuenxnxzazpctqitltbsifspekzbjephsnhzgyqqsnzlamfjzdzyporzsrpbnvuqviilqvlfrrjtpweyelndzibejgekummgkdsrrdwgkfbngyajdtafaebjdinjsvhhxgrsyntoycubblukgejkctshjclxotgnctmbkpqpwsdfsknnxjrnpuexqgfpefwdzciinieempavtyobezwktzrmmwwaxrqemektgjcsqieyxveasqfkmeznlribgvauretvdmswuqwxulmealcozeltmhjwgjipgowgddlpvplxopwafdepuekmgjlxjwafkzlddbepjbuwrsrxwlppegpfzganrdbkhmldnzluabikaafdrwdvjinkwltjoebjrvajduwdismobyqskodndnecrjdczdeudjnajpxevctyjnsfszlsduydwquwqkwchkpcdbdnyajrwajdtzkzqjxirspgjnzdfuilvhnujnrpvhzvctlebfrvfqgjapcmsjquxjnypzhofiidseigebuevdutnjrrcfonhemocuohtohodvelhcslaudwqlolpeiibnrbxfxfxtannbrazeasofuiusnwtevfcqsuggewepdvtwrozjcgcbuvhssykugxbjmgryyhnnwdvtueejjwnpgxwbldzmyytirbyuzrnmxpqyhlbprrzftczghhivqvjovgaryigqllalrqycjmcaehgxskljgzzqlhdtgnziyxribyyhcgvbqslhtcflbmraohrmpkycxrrdnndeorxkmzgmykysughcjzkxzzbkndseerorasojbcypcknsksimpibchhrtnsdtmkrranfurkqjwyzqzifgypqalncntrghrqvnwsvspkytrmqzrmqhqozntqkybetbdotoupgdejrishmfvgdwryclkeibgjfygliqqptcxmpoumlbraztaiqmtlzumfntkmfvdtpnldfcuoyehbflwofjautatkfljzpomqfzbhdgkdlkcprajcofapdafsyqfnpkggacijxndfwwjzziwtduxosqknmglqeuqpyxcxmopvnmtijituzptnajvkqwrilidlnxmmajipjhwivbwdnhoizmxdxpmsafliprgedieifljibtmuydkhwljuqufagudeukmnhldemzhjwudptxvuxnhkiocqusdpgmgnrdyxsqftakvredpzqaryskufmtcthydhmihaxjhnszgpikhkrynfgzzjglvzubonxbwqkbvfbefajddnunpjdsfonxpevkrwltagvtvjjotqnegawfnjjduomtgfsydpoctkvtfbsuxamulkwooluhgsxqhckfpobjshspkdpyucddqerkxvzzvltbtvprmrwpbtltkiwbfnotdedsqmgotanfzdopthflaiflysyiwgulhxxfgxwhuohjauovyhwkxuxxkibspugiaaqdztutmurcmnltjivbwsnmfhjzqhlbhaxdbnthkhkkahjtanblvuqidylxelgzhqncsqawjndxpifvqxetaimerwyktohnsuqzfftlkkczimzubnsfvllibqsvihhpkhvdhbdpyuidwapmdtlkrfpuvevbepgrgnklryvscoagzsgxkvnleekcpbhewvvhludjujkjozvulsczmrejdufnhizcahcmffofawlnwtqqygeprypdhrhxgwjfzjpuufqpzwncoltuhwoooktquyzlhmlbgwagmnbjybagjsopidpnmciotrepzdgloqvcebmjbsmpgsbjbkmzojjhjhirzawunifuualostpobqikadddrmiaogyigkjpmtwbjrlvdhwinmdfbikqgmtacbpqnxijiuegdroqutwrjyyscodibseiiaegloepyfssdblyqhxeosbmjpcmtsykdaplplmhdzefbkwbqlujvwlhsjrdkfkuagvifddvhaylvtjccpzhpolyquzcdlrirvsxbdrecrqnqhanigehjsrglfbnoroqowtmfeepfwvuiyhhgrcqewozmpeztltqbzdulygczgwyfrdqeznngwcqtflhhxnxeohurgyknlofsrcogerhszfisxtjpmxzshlizpufnbrojmebnbbpulvuzizjnyvltqkhafglyrtscgndgouhrzjpmvebznuepmwnlyviobosfflknhfizjstjbydphjhxngvuzejhchhkklpkvlabcogaml

[出力例]
2472

[入力例]

abc

aba

[出力例]

※AtCoderテストケースより

[入力例]

aaaaaa

[出力例]

※AtCoderテストケースより

[入力例]

abra

cadabra

[出力例]

※AtCoderテストケースより

[入力例]

oooopppqqrrrsss

oooppqrrssstttt

[出力例]

[入力例]

yfbtiphgpoierzzkhrnyawhgjqbnsciaiditqouwhtfxhamwryqtzguzrafvgifexvvmiktzepdwnvesuvmsgigxizbxrynyskypjrthvvicmifkyffqxkiouieoidjtsxwwjqaflytcmzvmpacmalcuucqtujpagpmtnpdtadlvosihreliuhfwssakqknyiqowqlww

zfdxmlcbgrubvnalctxasvihvjweishewyhvvziaoyyybklzhcomsgjncqcscfzdyknlbmdrxligotjlshferdfwqkoastrqcqfepovdxmpjobgujagplfbnrnbvdntpnkrvbkdjznjybqpcnbrxpkeolbrmyjvscroszlravwxsribentjjwcisvujyjlpvnwvtkrca

[出力例]

197

[入力例]

cuwllsesaoaanxfghjytmttwsmdrmgfisujygpusbxgwdsikzuyixsbtpnwuwuawarsesfmnhuijjhfetoovqwuezcxqhneuyjnfibobwgyjpgamvdpresibyqrpcyusskijajdalxyvqgldyqcukldztmuaxnfqmocvxjrlziivycyrgdfbqvbysdtydffvwnsivkicgdmtmcugfkhscbuuvbsqfaykqiiseztmebmzdksulvxsyqqyekwfgntubqqggtlegcophdaedonulmnvqyunwukrclpsezrwoplyxxqsmbvlykctngbcyhgfaydfbtdetknxibyessslaghwrqizaafjlxgrokbdexyyxelmgesdlegamceyobadkylenxntzogqmgohmwgzsilajuxohgxjxaloryjsbjsrutzcilgwrmfwlbtfptwkxyfjywihisvpaozszcpmwhjtpwelkmfjfjnfstyaukhscantysqiljidoikimpmngpsmijhklknshqhcubhfgdcfgkifayxdlvaakunebttqhhchkoyknrlwwpyqucipsvxntlkqrwrgflupqdetxinhzhaesriqtdngrxuxccoedyhoesdydenrutgfqkrvuecajgkdxfdufptcrxmsbgllzhniarmnivvdkadflexzfpooomhcydasfrcshfbyetninsxnutpiyqrbtzqcdsujcznnptplcrjiddnnurlervukhhqeweyiypqrznznfxwggrfqloloehthkrthnxqqceqdteyinpcvuwzrximynobuglgwvsczkvebtngsgvyocvnqjnaanelwaamkhwlmrwihlgfplojnvywwjcizwycnbyvgpulydcfyukfucdvlxxgzcvwlqchommydyrfukhqzlweqvcrpqawuabfclpjohsiidfrtbsdfzohkkjsvlvkwujbfrlorlqakoiwonpjmwgrkegiacbco

fwmskagltnakcfqnfwsqtelzinginpilrbjchyfbjkgqjhnrrzcmqbqvcompavodojucybjlkfhqsvvibqcrjtmsbzcmuzmzrpnngaouepcscmmohyojyhrdyijesqfocykarhfmxozhqeaawogsbethpydovwnipohocnratyaagqjgmudgwxigxyyvzaigkinpuabgzsrcqbcxmdcugpovtnlaiyxreifjjiifpwtvnlwemocuijllpxhdmvvliioqvqrfoaqebopripetkludfcucjbhqlrtipoxyrfwfclmhvbbrebwcezjzydrwnudfzaykbvieabjezocryfrbitlyapjcffbaqmgutydvoyzzallhnuqnflqyjlfdajgwajkdjawjxfixuycyhffsayfjjrwyvnawqdnpbionwgktolanaxzuclwltsngdqfcjdvwvuaelupmoxalmsgjfrrafmvoeiqbtdrpfowapyiwfegvsdvytijbzglpzxcvnddqiijthfngxwtcnqosoodogpbnvbzovdsbniyokqiqhkmhofzhgarxetezzchmhrkuwliwwrlcetgxhwddxrdunwjaqrpfyfoniuopcxhxwzkzvypkvykslkchudkxgrrjhqmfkclslsccedueymrsdiaejfjngvyvarongoewfmnfxkqtxcvnhujprdskjgmcqmezwmrtauhnenfojpwofvpvrqzoiuecnndpnnauzvpomtcdimjbgcpewpkcyyimzqunxthtzhcxuazuuhynzdtrvxevitgfmgpcjlhqetmkonmzairztyhghtqakkfcqbrpxzvgasrsunnlrhyomxnoihilfnkckaqvstlwuahbupufwzleplwjvyllhgndzcptjheuekrnimvaykhinxivupxpxuzbnggjubvaeemencunpzcosjvndsmfvyvfsstenakcdsgxwnmegaykmmdcsnzxblvt

[出力例]

985

[入力例]

tjgqvvdipknzaeedgpuwbtowamjeeszoeptnnwkjvetrkcrpbnykpvxvxkmafjmojswxvxzlulxlzkdcdgwprvulgdxjwadenwyagqhnyamttckhrugrybquhnddojizvotaowmoczmwvzmojasuyqvsiymzmirsoxqqzixlkfdrdanjzsnhhjksiszhejyjxjujhwaqaalbmjqwssiqcchsylvezfeviijzzobiyeyestlajsnlbwodlgwsufoqtupwnppcbwiryhwyhhkyciscfmmkqaubysmmrqwxgqprtutnbwyrzinpmkmtdtfchqpvqankqdlpehzrsbytdflyerlrbkwjwkrshbjijqvqfbgvmoocpuqephppczawzcfuiolvsdpcwidoewthgkwnsutdaazpnwygfkoxatecipqoaoglgrckdufenwhjuycxmybfdpjtoilmjxzjcdwvvqkynfevakjyasmqnbbwfybfcejhseuodowvlnznewqunixjktsqbuwkwsjupxszbjxogxgmxdwgmdzrbogvmsfyklxctnxopcviuoxjlrepdgydgxkjjxoqxxzqlhmaxdwayafcphklrupuuitvapphmkgwgxrquggkhnftqvgdwpibmlepvglfftsuczcqsbbwhkybefdjzdbpyxnlajpqrjtqdsdsrbvejlsfenpjogmspqmpbxnhcxxgsyafxjyulkcbauxzegzvndqwdfxtuuoxqbingaasqukhzhympmirgnhczytrfpdtezrstxtgssrolkgxixntfkfcysknbvtwjqxffljieuxahyylbcuhpywxjfvaiowjuuxwghfyvvrujctjqaynhlovucvdthektngptqcjbzwcidogjncihfnfpmosfkbmgoakyrxhqcwukdlrsqcsybhchmtbqkynswxqcaesnkgoaacddybwmxkhuxqqditkdrzneneeccllxuhzcsxfrnmffojtopguoxlvsiyzomfpoyoduiuhhxsiixpqbhsivyxkefaujmfevuhxbwynwqfjfhfobolnumvvoyydzoezldblgnnnwcscajuwicymyjdjdpyduycinojkmvamfxjdfiknuptpdkmwvhelssvsdjojtvrgocrwmftacorkqtsqyhjnpxnhbfjspingmjiaycqfmicfehtsutsfgvhkohqvwiebohencjgnwnnpwzvkumwwankrzhvfmfopqfddwvckhtgjcvjqvztvhzryprmocrsyvjrhghqekimygtaciqzcbvzujjptsvrouoqhveecbccssdzzxaxwfboyxaozplhdryqudahniwmgmxfapgsmwxnximgbucxbpcclyrexiqufafvjvphbbeziqryihbxrlllfltnwytmoarlxbwihiaosmbiqlwgeynfukwalhorqfpahlyzkeehfauulbekusyxdftdbqudczkdqtuujcjlfikjzxgobwzwakmueykehpovfhuhiiasbhucpotjddrwtnbfgijnfwylozwnclimdwnivhulmrprqbtesdkjiuqlchzagdaxxoiojfhewwwguwnndqnrjciouakgklgtaittvjibzvovtehyhtqrubhgcdftflyscstlmkqeuvsuxfzslprioqymdvgcstbxqvdzpnwtudndnsjmhdrgzuafrllgbkrfmenarowdjwebyqravatgiqbuympdyqfunspxoklbyasrtibikwbvnnrsxzxewkejfbydiliyktdfzhszkofdvnqvkqezaucqjobvrcuwwhnqypnwmmtqzjxuggfhtjijcifbakepkvxxlzwkmyrtqhywslvwwpeoyxsrktkjoouvukqjizkcyoihmwwmyafomuuxysgvgypnwkjnjdzojxlwxzkmnecwjwljoadctwwfjxircxlvooxyvehqoywoefvdsiipocwjpzurzbwdsbnhjongsrkddksxqfoyjeybjhdfijvbcvzxoahduambjlgiryvjhgtzahssjeuvpghzrvxwiqkkmnrhrszlgfaykjdgocmdzmbtrfgoyekmlozxeopirxmluoxqjrixxgnlvyymuynmrxlimllfbsngvfklgwgotkykrlsrgiztauhuaejodhenbcejtfofktsmtsmbycgdbuaozghxopehhpuuqkqidngibqrbocrifqczzczmrdtzfutmvaotosymlnszyfkmgpkrfwldehjfblyxpbamnskkkehriazbedwdjmfzpjhhkpqwbjgocxireiujvyoxctrbdqgbyiyavulokjdbldaauraqdzswyskbqmtazvmjmzlnsuccdlhckfvgzrvlpicwhgmbbqpvkzholayimpvdewtjvqblurucqokcpzvinqjwmsfhuslvwogfmgsuirttcsgusegvbyullwwvgbaawmdkdtypxuftw

zmusswrdosvdpdmjmnxixmrdafjwzicvgouewzoxawirtfjybalmgepmuyshctdeynkjxuqrbzrsmtfklbwabjqxhtefyeujhbeucruirfikyfbbefpjvrnkegwowgqdocycgfaqawvyeowoxqxfdrhkbimkaycysijshsfxwybtnyyrrvbjwvwrlykuixvminybjiekdfugcoiutqzmbuvedfburfqwodxrqdecvnmsuenxnxzazpctqitltbsifspekzbjephsnhzgyqqsnzlamfjzdzyporzsrpbnvuqviilqvlfrrjtpweyelndzibejgekummgkdsrrdwgkfbngyajdtafaebjdinjsvhhxgrsyntoycubblukgejkctshjclxotgnctmbkpqpwsdfsknnxjrnpuexqgfpefwdzciinieempavtyobezwktzrmmwwaxrqemektgjcsqieyxveasqfkmeznlribgvauretvdmswuqwxulmealcozeltmhjwgjipgowgddlpvplxopwafdepuekmgjlxjwafkzlddbepjbuwrsrxwlppegpfzganrdbkhmldnzluabikaafdrwdvjinkwltjoebjrvajduwdismobyqskodndnecrjdczdeudjnajpxevctyjnsfszlsduydwquwqkwchkpcdbdnyajrwajdtzkzqjxirspgjnzdfuilvhnujnrpvhzvctlebfrvfqgjapcmsjquxjnypzhofiidseigebuevdutnjrrcfonhemocuohtohodvelhcslaudwqlolpeiibnrbxfxfxtannbrazeasofuiusnwtevfcqsuggewepdvtwrozjcgcbuvhssykugxbjmgryyhnnwdvtueejjwnpgxwbldzmyytirbyuzrnmxpqyhlbprrzftczghhivqvjovgaryigqllalrqycjmcaehgxskljgzzqlhdtgnziyxribyyhcgvbqslhtcflbmraohrmpkycxrrdnndeorxkmzgmykysughcjzkxzzbkndseerorasojbcypcknsksimpibchhrtnsdtmkrranfurkqjwyzqzifgypqalncntrghrqvnwsvspkytrmqzrmqhqozntqkybetbdotoupgdejrishmfvgdwryclkeibgjfygliqqptcxmpoumlbraztaiqmtlzumfntkmfvdtpnldfcuoyehbflwofjautatkfljzpomqfzbhdgkdlkcprajcofapdafsyqfnpkggacijxndfwwjzziwtduxosqknmglqeuqpyxcxmopvnmtijituzptnajvkqwrilidlnxmmajipjhwivbwdnhoizmxdxpmsafliprgedieifljibtmuydkhwljuqufagudeukmnhldemzhjwudptxvuxnhkiocqusdpgmgnrdyxsqftakvredpzqaryskufmtcthydhmihaxjhnszgpikhkrynfgzzjglvzubonxbwqkbvfbefajddnunpjdsfonxpevkrwltagvtvjjotqnegawfnjjduomtgfsydpoctkvtfbsuxamulkwooluhgsxqhckfpobjshspkdpyucddqerkxvzzvltbtvprmrwpbtltkiwbfnotdedsqmgotanfzdopthflaiflysyiwgulhxxfgxwhuohjauovyhwkxuxxkibspugiaaqdztutmurcmnltjivbwsnmfhjzqhlbhaxdbnthkhkkahjtanblvuqidylxelgzhqncsqawjndxpifvqxetaimerwyktohnsuqzfftlkkczimzubnsfvllibqsvihhpkhvdhbdpyuidwapmdtlkrfpuvevbepgrgnklryvscoagzsgxkvnleekcpbhewvvhludjujkjozvulsczmrejdufnhizcahcmffofawlnwtqqygeprypdhrhxgwjfzjpuufqpzwncoltuhwoooktquyzlhmlbgwagmnbjybagjsopidpnmciotrepzdgloqvcebmjbsmpgsbjbkmzojjhjhirzawunifuualostpobqikadddrmiaogyigkjpmtwbjrlvdhwinmdfbikqgmtacbpqnxijiuegdroqutwrjyyscodibseiiaegloepyfssdblyqhxeosbmjpcmtsykdaplplmhdzefbkwbqlujvwlhsjrdkfkuagvifddvhaylvtjccpzhpolyquzcdlrirvsxbdrecrqnqhanigehjsrglfbnoroqowtmfeepfwvuiyhhgrcqewozmpeztltqbzdulygczgwyfrdqeznngwcqtflhhxnxeohurgyknlofsrcogerhszfisxtjpmxzshlizpufnbrojmebnbbpulvuzizjnyvltqkhafglyrtscgndgouhrzjpmvebznuepmwnlyviobosfflknhfizjstjbydphjhxngvuzejhchhkklpkvlabcogaml

[出力例]

2472

■参照サイト
第九回アルゴリズム実技検定

2022年1月2日

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

C++の練習を兼ねて, 第九回アルゴリズム実技検定の問題G (連結) を解いてみた.

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

本家のサイト第九回アルゴリズム実技検定の各リンクをご覧下さい.

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vs = vector<set<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 main(){
    
    // 1. 入力情報.
    int N, Q;
    scanf("%d %d", &N, &Q);
    vs G(N);
    
    // 2. bfs.
    // https://ja.wikipedia.org/wiki/幅優先探索
    auto bfs = [&](vs &G, int s, int* d){
        // 空のキュー.
        queue<int> q;
        
        // 探索地点 s をキュー q に追加.
        q.push(s);
        while(!q.empty()){
            // キューから取り出す.
            int u = q.front();
            q.pop();
            
            // 取り出した要素を処理.
            for(auto &e : G[u]){
                // 訪問済であれば, 処理をスキップ.
                if(!d[e] && e != s) d[e] = d[u] + 1, q.push(e);
            }
        }
    };
    
    // 3. クエリ回答.
    rep(i, Q){
        int t, u, v;
        scanf("%d %d %d", &t, &u, &v);
        u--, v--;
        
        if(t == 1){
            // 辺(u, v)があるか？
            if(G[u].count(v) && G[v].count(u)){
                G[u].erase(v);
                G[v].erase(u);
            }else{
                G[u].insert(v);
                G[v].insert(u);
            }
        }
        
        if(t == 2){
            // 頂点 u から 頂点 v へ 辿れるか？
            int d[N];
            rep(i, N) d[i] = 0;
            bfs(G, u, d);
            
            // 出力.
            printf("%s\n", d[v] ? "Yes" : "No");
        }
    }
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vs = vector<set<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 main(){

// 1. 入力情報.

int N, Q;

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

vs G(N);

// 2. bfs.

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

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

// 空のキュー.

queue<int> q;

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

q.push(s);

while(!q.empty()){

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

int u = q.front();

q.pop();

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

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

// 訪問済であれば, 処理をスキップ.

if(!d[e] && e != s) d[e] = d[u] + 1, q.push(e);

}

};

// 3. クエリ回答.

rep(i, Q){

int t, u, v;

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

u--, v--;

if(t == 1){

// 辺(u, v)があるか？

if(G[u].count(v) && G[v].count(u)){

G[u].erase(v);

G[v].erase(u);

}else{

G[u].insert(v);

G[v].insert(u);

}

if(t == 2){

// 頂点 u から頂点 v へ辿れるか？

int d[N];

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

bfs(G, u, d);

// 出力.

printf("%s\n", d[v] ? "Yes" : "No");

}

return 0;

}

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

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

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

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

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

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

[入力例]

3 5

1 1 2

1 3 2

2 1 3

1 2 1

2 1 3

[出力例]

Yes

※AtCoderテストケースより

[入力例]

5 17

1 1 2

1 5 2

2 1 5

2 4 5

1 5 2

1 5 3

1 2 3

2 1 3

2 2 4

1 4 3

2 1 4

1 2 3

2 1 3

1 5 3

1 5 2

2 2 3

2 1 5

[出力例]

Yes

[入力例]

10 23

1 3 10

1 8 3

2 8 10

1 10 6

1 6 4

1 2 4

1 1 9

1 7 9

1 7 2

2 8 1

2 6 5

2 10 9

1 5 6

1 6 4

1 7 10

1 3 10

2 8 2

2 1 5

2 2 10

1 7 2

2 2 10

1 7 6

2 7 5

[出力例]

Yes

■参照サイト
第九回アルゴリズム実技検定

2022年1月1日

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

C++の練習を兼ねて, 第九回アルゴリズム実技検定の問題F (将棋のように) を解いてみた.

■感想.
1. 問題Fは, 方針を絞り込めたので, AC版に到達できた.
2. 幅優先探索(応用版, 移動可能方向の構築)の復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

本家のサイト第九回アルゴリズム実技検定の各リンクをご覧下さい.

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vs = vector<string>;
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 main(){
    
    // 1. 入力情報.
    int A, B;
    scanf("%d %d", &A, &B);
    A--, B--;
    vs info;
    rep(i, 3){
        char c[11];
        scanf("%s", c);
        string s(c);
        info.pb(s);
    }
    
    // 2. 移動可能な方向は？
    vp dir;
    rep(i, 3) rep(j, 3) if(info[i][j] == '#') dir.pb({i - 1, j - 1});
    
    // 3. bfs.
    // https://ja.wikipedia.org/wiki/幅優先探索
    auto bfs = [&](int s, int H, int W, int* d) -> void{
        // 空のキュー.
        queue<int> q;
        
        // 訪問済みフラグ設定.
        d[s] = 1;
        
        // 探索地点 s をキュー q に追加.
        q.push(s);
        while(!q.empty()){
            // キューから取り出す.
            int v = q.front();
            q.pop();
            
            // 取り出した要素を処理.
            // x: 列方向, y: 行方向 で考える.
            int nx, ny, n;
            int cx = v % W , cy = v / W;
            for(auto &p : dir){
                // 移動先.
                nx = cx + p.b;
                ny = cy + p.a;
                n = nx + ny * W;
                
                // 訪問不可能なマス であれば, 処理をスキップ.
                if(nx < 0 || nx >= W || ny < 0 || ny >= H) continue;
                
                // 訪問先のマスで, 訪問可能 かつ 未訪問 であれば, 訪問済みフラグ設定.
                if(!d[n]) d[n] = 1, q.push(n);
            }
        }
        return;
    };
    int d[81];
    rep(i, 81) d[i] = 0;
    bfs(A * 9 + B, 9, 9, d);
    
    // 4. 集計.
    int ans = 0;
    rep(i, 81) if(d[i]) ans++;
    
    // 5. 出力.
    printf("%d\n", ans);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vs = vector<string>;

using P = pair<int, int>;

using vp = vector;

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

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

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

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

#define a first

#define b second

#define pb push_back

int main(){

// 1. 入力情報.

int A, B;

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

A--, B--;

vs info;

rep(i, 3){

char c[11];

scanf("%s", c);

string s(c);

info.pb(s);

}

// 2. 移動可能な方向は？

vp dir;

rep(i, 3) rep(j, 3) if(info[i][j] == '#') dir.pb({i - 1, j - 1});

// 3. bfs.

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

auto bfs = [&](int s, int H, int W, int* d) -> void{

// 空のキュー.

queue<int> q;

// 訪問済みフラグ設定.

d[s] = 1;

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

q.push(s);

while(!q.empty()){

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

int v = q.front();

q.pop();

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

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

int nx, ny, n;

int cx = v % W , cy = v / W;

for(auto &p : dir){

// 移動先.

nx = cx + p.b;

ny = cy + p.a;

n = nx + ny * W;

// 訪問不可能なマスであれば, 処理をスキップ.

if(nx < 0 || nx >= W || ny < 0 || ny >= H) continue;

// 訪問先のマスで, 訪問可能かつ未訪問であれば, 訪問済みフラグ設定.

if(!d[n]) d[n] = 1, q.push(n);

}

return;

};

int d[81];

rep(i, 81) d[i] = 0;

bfs(A * 9 + B, 9, 9, d);

// 4. 集計.

int ans = 0;

rep(i, 81) if(d[i]) ans++;

// 5. 出力.

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

return 0;

}

[入力例]
2 2
###
#..
...

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

[入力例]
5 4
###
#.#
###

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

[入力例]
9 9
...
...
..#

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

[入力例]
8 8
...
...
...

[出力例]
1

[入力例]
5 7
.#.
...
...

[出力例]
5

[入力例]
3 3
...
#.#
...

[出力例]
9

[入力例]
2 2
#.#
...
#.#

[出力例]
41

[入力例]
2 8
.#.
#.#
.#.

[出力例]
81

[入力例]

2 2

###

#..

...

[出力例]

※AtCoderのテストケースより

[入力例]

5 4

###

#.#

###

[出力例]

※AtCoderのテストケースより

[入力例]

9 9

...

..#

[出力例]

※AtCoderのテストケースより

[入力例]

8 8

...

[出力例]

[入力例]

5 7

.#.

...

[出力例]

[入力例]

3 3

...

#.#

...

[出力例]

[入力例]

2 2

#.#

...

#.#

[出力例]

[入力例]

2 8

.#.

#.#

.#.

[出力例]

■参照サイト
第九回アルゴリズム実技検定

C++の練習を兼ねて, 第九回 アルゴリズム実技検定 の 問題K (ガソリンスタンド) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 116 の 問題D (Various Sushi) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 100 の 問題D (Patisserie ABC) を解いてみた.

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

C++の練習を兼ねて, 第九回 アルゴリズム実技検定 の 問題J (回転と反転) を解いてみた.

C++の練習を兼ねて, 第九回 アルゴリズム実技検定 の 問題I (直通エレベーター) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 048 の 問題C (足の多い高橋君) を解いてみた.

C++の練習を兼ねて, 第九回 アルゴリズム実技検定 の 問題H (最長非共通部分列) を解いてみた.

C++の練習を兼ねて, 第九回 アルゴリズム実技検定 の 問題G (連結) を解いてみた.

C++の練習を兼ねて, 第九回 アルゴリズム実技検定 の 問題F (将棋のように) を解いてみた.

C++の練習を兼ねて, 第九回アルゴリズム実技検定の問題K (ガソリンスタンド) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 116 の問題D (Various Sushi) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 100 の問題D (Patisserie ABC) を解いてみた.

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

C++の練習を兼ねて, 第九回アルゴリズム実技検定の問題J (回転と反転) を解いてみた.

C++の練習を兼ねて, 第九回アルゴリズム実技検定の問題I (直通エレベーター) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 048 の問題C (足の多い高橋君) を解いてみた.

C++の練習を兼ねて, 第九回アルゴリズム実技検定の問題H (最長非共通部分列) を解いてみた.

C++の練習を兼ねて, 第九回アルゴリズム実技検定の問題G (連結) を解いてみた.

C++の練習を兼ねて, 第九回アルゴリズム実技検定の問題F (将棋のように) を解いてみた.