C++ | 個人用メモ帳

2021年9月27日

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

C++の練習を兼ねて, AtCoder Beginner Contest 220 の問題C (Long Sequence) ～問題D (FG operation) を解いてみた.

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

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

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
LL a[101010], aCum[101010];

int main(){
    
    // 1. 入力情報.
    int N;
    LL X;
    scanf("%d", &N);
    rep(i, N) scanf("%lld", &a[i]);
    scanf("%lld", &X);
    
    // 2. 累積和.
    rep(i, N) aCum[i + 1] = aCum[i] + a[i];
    
    // 3. 商, 余りは？
    LL q = X / aCum[N];
    LL r = X % aCum[N];
    
    // 4. 余りを超える位置は？
    int at = -1;
    rep(i, N + 1){
        if(aCum[i] > r){
            at = i;
            break;
        }
    }
    
    // 5. 出力.
    printf("%lld\n", q * N + (LL)at);
    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[101010], aCum[101010];

int main(){

// 1. 入力情報.

int N;

LL X;

scanf("%d", &N);

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

scanf("%lld", &X);

// 2. 累積和.

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

// 3. 商, 余りは？

LL q = X / aCum[N];

LL r = X % aCum[N];

// 4. 余りを超える位置は？

int at = -1;

rep(i, N + 1){

if(aCum[i] > r){

at = i;

break;

}

// 5. 出力.

printf("%lld\n", q * N + (LL)at);

return 0;

}

[入力例]
3
3 5 2
26

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

[入力例]
4
12 34 56 78
1000

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

[入力例]
10
5 1 9 11 6 5 1 2 12 7
2021

[出力例]
344

[入力例]
20
34 121 72 71 95 78 78 32 86 109 73 39 81 23 68 78 54 98 76 33
20210927

[出力例]
288934

[入力例]
50
554 261 807 477 51 847 575 1186 901 415 520 381 622 1115 438 1010 625 1234 732 415 814 1193 1033 112 1125 1028 984 1113 928 535 656 12 287 874 1196 94 1089 986 177 988 812 246 414 1097 134 152 19 942 1096 1165
1000000000000000000

[出力例]
1450662952969509

[入力例]

3 5 2

[出力例]

※AtCoderテストケースより

[入力例]

12 34 56 78

1000

[出力例]

※AtCoderテストケースより

[入力例]

5 1 9 11 6 5 1 2 12 7

2021

[出力例]

344

[入力例]

34 121 72 71 95 78 78 32 86 109 73 39 81 23 68 78 54 98 76 33

20210927

[出力例]

288934

[入力例]

554 261 807 477 51 847 575 1186 901 415 520 381 622 1115 438 1010 625 1234 732 415 814 1193 1033 112 1125 1028 984 1113 928 535 656 12 287 874 1196 94 1089 986 177 988 812 246 414 1097 134 152 19 942 1096 1165

1000000000000000000

[出力例]

1450662952969509

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
const LL MOD = 998244353;
LL dp[101010][10];
int a[101010];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%d", &a[i]);
    
    // 2. dp更新.
    dp[0][a[0]] = 1;
    rep(i, N - 1){
        rep(j, 10){
            // 操作 F.
            int f = (j + a[i + 1]) % 10;
            dp[i + 1][f] += dp[i][j];
            dp[i + 1][f] %= MOD;
            
            // 操作 G.
            int g = (j * a[i + 1]) % 10;
            dp[i + 1][g] += dp[i][j];
            dp[i + 1][g] %= MOD;
        }
    }
    
    // 3. 出力.
    rep(i, 10) printf("%lld\n", dp[N - 1][i]);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

const LL MOD = 998244353;

LL dp[101010][10];

int a[101010];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

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

// 2. dp更新.

dp[0][a[0]] = 1;

rep(i, N - 1){

rep(j, 10){

// 操作 F.

int f = (j + a[i + 1]) % 10;

dp[i + 1][f] += dp[i][j];

dp[i + 1][f] %= MOD;

// 操作 G.

int g = (j * a[i + 1]) % 10;

dp[i + 1][g] += dp[i][j];

dp[i + 1][g] %= MOD;

}

// 3. 出力.

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

return 0;

}

[入力例]
3
2 7 6

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

[入力例]
5
0 1 2 3 4

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

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

[出力例]
108
2
174
38
38
4
46
10
82
10

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

[出力例]
795218227
107345812
107305502
107505240
107361985
644232897
107505240
107305502
107345812
107352373

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

[出力例]
905413840
17605008
307786178
847871598
26241917
17716361
76727260
463602346
95789053
727441864

[入力例]

2 7 6

[出力例]

※AtCoderテストケースより

[入力例]

0 1 2 3 4

[出力例]

※AtCoderテストケースより

[入力例]

1 4 1 4 2 1 3 5 6 2

[出力例]

108

174

[入力例]

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

[出力例]

795218227

107345812

107305502

107505240

107361985

644232897

107505240

107305502

107345812

107352373

[入力例]

200

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

[出力例]

905413840

17605008

307786178

847871598

26241917

17716361

76727260

463602346

95789053

727441864

■参照サイト
AtCoder Beginner Contest 220

2021年9月26日2021年9月26日

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

C++の練習を兼ねて, AtCoder Beginner Contest 219 の問題G (Propagation) を解いてみた.

■感想.
1. 問題G は, 方針が見えなかったので, 解説を参考に実装したところ AC版に到達できた.
2. (競プロ典型 90 問の問題083 (Colorful Graph))に, 類似している印象を受けたものの, AC版となるための実装までに, 苦労したように思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/abc219/editorial/2653
// https://atcoder.jp/contests/typical90/tasks/typical90_ce
// -> 003.txt などのテストケースで, WA版となったため, ロジック修正.
// 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
#define a first
#define b second
P n[202020]; // {頂点番号, {クエリ番号, 整数}}.
P q[202020]; // {頂点番号, {クエリ番号, 整数}}(※看板).

int main(){
    
    // 1. 入力情報.
    int N, M, Q;
    scanf("%d %d %d", &N, &M, &Q);
    vvi G(N), F(N);
    rep(i, M){
        int a, b;
        scanf("%d %d", &a, &b);
        a--, b--;
        G[a].pb(b);
        G[b].pb(a);
    }
    
    // 2. 部分グラフ作成(次数が大きい頂点に向かう頂点のみ辺を追加).
    int B = (int)sqrt(M);
    rep(i, N) if(G[i].size() >= B) for(auto &p : G[i]) F[p].pb(i);
    
    // 3. クエリ実行.
    rep(i, N) n[i].a = -1, n[i].b = i + 1;
    rep(i, N) q[i].a = -1, q[i].b = 0;
    rep(i, Q){
        // 3-1. クエリ入力情報.
        int x;
        scanf("%d", &x);
        x--;
        
        // 3-2. (手順 1) 頂点 x の整数を正しい値に書き換え.
        // -> 一番直近のクエリ番号(値が最も大きいもの)で更新された内容を反映.
        for(auto &u : F[x]){
            if(q[u].a > n[x].a){
                n[x].a = q[u].a;
                n[x].b = q[u].b;
            }
        }
        
        // 3-3. (手順 2) 頂点 xの正しい整数を X とおく.
        int X = n[x].b;
        
        // 3-4. (手順 3) 頂点 xの次数が B 以上か否か応じて, 処理を分岐.
        int gSize = G[x].size();
        
        // (a) 隣接する頂点数が小さい場合.
        if(gSize < B){
            for(auto &u : G[x]){
                n[u].a = i;
                n[u].b = X;
            }
        }
        
        // (b) 隣接する頂点数が大きい場合.
        if(gSize >= B){
            q[x].a = i;
            q[x].b = X;
        }
    }
    
    // 4. 復元.
    rep(i, N){
        // 隣接する頂点数が大きい頂点を基準に, 各頂点 の 整数を正しい値に書き換え.
        // -> グラフ F は, 構成上, 利用できないことに注意.
        int gSize = G[i].size();
        if(gSize >= B){
            for(auto &u : G[i]){
                if(q[i].a > n[u].a){
                    n[u].a = q[i].a;
                    n[u].b = q[i].b;
                }
            }
        }
    }
    
    // 5. 出力.
    rep(i, N){
        printf("%d", n[i].b);
        printf("%s", (i < N - 1) ? " " :"\n");
    }
    return 0;
    
}

100

// 解き直し.

// https://atcoder.jp/contests/abc219/editorial/2653

// https://atcoder.jp/contests/typical90/tasks/typical90_ce

// -> 003.txt などのテストケースで, WA版となったため, ロジック修正.

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

#define a first

#define b second

P n[202020]; // {頂点番号, {クエリ番号, 整数}}.

P q[202020]; // {頂点番号, {クエリ番号, 整数}}(※看板).

int main(){

// 1. 入力情報.

int N, M, Q;

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

vvi G(N), F(N);

rep(i, M){

int a, b;

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

a--, b--;

G[a].pb(b);

G[b].pb(a);

}

// 2. 部分グラフ作成(次数が大きい頂点に向かう頂点のみ辺を追加).

int B = (int)sqrt(M);

rep(i, N) if(G[i].size() >= B) for(auto &p : G[i]) F[p].pb(i);

// 3. クエリ実行.

rep(i, N) n[i].a = -1, n[i].b = i + 1;

rep(i, N) q[i].a = -1, q[i].b = 0;

rep(i, Q){

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

int x;

scanf("%d", &x);

x--;

// 3-2. (手順 1) 頂点 x の整数を正しい値に書き換え.

// -> 一番直近のクエリ番号(値が最も大きいもの)で更新された内容を反映.

for(auto &u : F[x]){

if(q[u].a > n[x].a){

n[x].a = q[u].a;

n[x].b = q[u].b;

}

// 3-3. (手順 2) 頂点 xの正しい整数を X とおく.

int X = n[x].b;

// 3-4. (手順 3) 頂点 xの次数が B 以上か否か応じて, 処理を分岐.

int gSize = G[x].size();

// (a) 隣接する頂点数が小さい場合.

if(gSize < B){

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

n[u].a = i;

n[u].b = X;

}

// (b) 隣接する頂点数が大きい場合.

if(gSize >= B){

q[x].a = i;

q[x].b = X;

}

// 4. 復元.

rep(i, N){

// 隣接する頂点数が大きい頂点を基準に, 各頂点の整数を正しい値に書き換え.

// -> グラフ F は, 構成上, 利用できないことに注意.

int gSize = G[i].size();

if(gSize >= B){

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

if(q[i].a > n[u].a){

n[u].a = q[i].a;

n[u].b = q[i].b;

}

// 5. 出力.

rep(i, N){

printf("%d", n[i].b);

printf("%s", (i < N - 1) ? " " :"\n");

}

return 0;

}

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

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

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

[出力例]
1 6 1 1 6 6 1 9 9 10 11 12 10 14
※AtCoderテストケースより

[入力例]
1 0 1
1

[出力例]
1

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

[出力例]
1 1 1

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

[出力例]
1 1 7 1 7 7 7 11 1 1 11

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

[出力例]
12 3 3 3 5 5 7 7 9 10 7 12 15 15 15 15 18 18 18 3 21 22

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

[出力例]
1 1 1 1 1 1 1 8 8 8 8 8 8

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

[出力例]
1 5 5 5 5 7 7 7 7 11 11 11 11 1 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

[入力例]

5 6 3

4 2

4 3

1 2

2 3

4 5

1 5

1 3 4

[出力例]

1 3 3 3 3

※AtCoderテストケースより

[入力例]

14 14 8

7 4

13 9

9 8

4 3

7 2

13 8

12 8

11 3

6 3

7 14

6 5

1 4

10 13

5 2

2 6 12 9 1 10 5 4

[出力例]

1 6 1 1 6 6 1 9 9 10 11 12 10 14

※AtCoderテストケースより

[入力例]

1 0 1

[出力例]

[入力例]

3 2 3

2 1

3 2

3 1 2

[出力例]

1 1 1

[入力例]

11 13 5

2 1

2 10

2 9

10 9

2 4

4 5

4 3

3 5

3 7

3 6

7 8

8 7

8 11

7 3 1 2 11

[出力例]

1 1 7 1 7 7 7 11 1 1 11

[入力例]

22 27 8

1 17

1 5

1 6

6 5

17 18

18 19

19 17

12 1

12 13

13 14

14 12

15 13

15 14

15 16

16 13

2 3

3 4

4 2

4 20

21 20

20 22

21 22

7 8

9 8

10 9

10 11

11 7

5 18 17 12 15 3 4 7

[出力例]

12 3 3 3 5 5 7 7 9 10 7 12 15 15 15 15 18 18 18 3 21 22

[入力例]

13 12 5

1 2

1 3

1 4

1 5

1 6

1 7

8 7

8 9

8 10

8 11

8 12

8 13

1 8 1 8 1

[出力例]

1 1 1 1 1 1 1 8 8 8 8 8 8

[入力例]

15 14 10

1 10

1 3

1 6

1 14

14 15

10 11

10 12

10 13

3 2

3 4

3 5

6 7

6 8

6 9

1 14 15 7 6 5 3 11 10 14

[出力例]

1 5 5 5 5 7 7 7 7 11 11 11 11 1 1

■参照サイト
サイシードプログラミングコンテスト2021（AtCoder Beginner Contest 219）
083 – Colorful Graph

2021年9月24日

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

C++の練習を兼ねて, AtCoder Beginner Contest 217 の問題G (Groups) を解いてみた.

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

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

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

// 解き直し.
// https://atcoder.jp/contests/abc217/editorial/2390
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
const LL MOD = 998244353;
LL dp[5050][5050];

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    
    // 2. dp更新.
    dp[0][0] = 1;
    repx(j, 1, N + 1){
        repx(i, 1, N + 1){
            dp[i][j] += dp[i - 1][j - 1] + (LL)(j - (i - 1) / M) * dp[i - 1][j];
            dp[i][j] %= MOD;
        }
    }
    
    // 3. 出力.
    repx(i, 1, N + 1) printf("%lld\n", dp[N][i]);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc217/editorial/2390

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

const LL MOD = 998244353;

LL dp[5050][5050];

int main(){

// 1. 入力情報.

int N, M;

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

// 2. dp更新.

dp[0][0] = 1;

repx(j, 1, N + 1){

repx(i, 1, N + 1){

dp[i][j] += dp[i - 1][j - 1] + (LL)(j - (i - 1) / M) * dp[i - 1][j];

dp[i][j] %= MOD;

}

// 3. 出力.

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

return 0;

}

[入力例]
4 2

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

[入力例]
6 6

[出力例]
1
31
90
65
15
1
※AtCoderテストケースより

[入力例]
20 5

[出力例]
0
0
0
331776
207028224
204931064
814022582
544352515
755619435
401403040
323173195
538468102
309259764
722947327
162115584
10228144
423360
10960
160
1
※AtCoderテストケースより

[入力例]
3 2

[出力例]
0
2
1

[入力例]
5 3

[出力例]
0
4
14
8
1

[入力例]
10 5

[出力例]
0
16
1280
9080
16944
12052
3840
580
40
1

[入力例]
27 18

[出力例]
0
131072
117687007
561668248
333765796
944219615
413145914
25234252
844291551
147820601
415647094
502074964
742578391
643588001
224531504
645569485
719396402
321847628
67809364
337380247
323011383
410215
298122147
4848666
52686
342
1

100

101

102

103

104

105

106

107

108

109

110

111

112

[入力例]

4 2

[出力例]

※AtCoderテストケースより

[入力例]

6 6

[出力例]

※AtCoderテストケースより

[入力例]

20 5

[出力例]

331776

207028224

204931064

814022582

544352515

755619435

401403040

323173195

538468102

309259764

722947327

162115584

10228144

423360

10960

160

※AtCoderテストケースより

[入力例]

3 2

[出力例]

[入力例]

5 3

[出力例]

[入力例]

10 5

[出力例]

1280

9080

16944

12052

3840

580

[入力例]

27 18

[出力例]

131072

117687007

561668248

333765796

944219615

413145914

25234252

844291551

147820601

415647094

502074964

742578391

643588001

224531504

645569485

719396402

321847628

67809364

337380247

323011383

410215

298122147

4848666

52686

342

■参照サイト
AtCoder Beginner Contest 217

2021年9月23日2021年9月23日

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

C++の練習を兼ねて, AtCoder Regular Contest 126 の問題A (Make 10) ～問題B (Cross-free Matching) を解いてみた.

■感想.
1. 問題B は, 方針が見えなかったので, 解説を参考に実装したところ AC版に到達できた.
2. 問題B で, LIS(Longest increase subsequence) の復習ができたので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)

int main(){
    
    // 1. 入力情報.
    int T;
    scanf("%d", &T);
    
    // 2. クエリ回答.
    rep(i, T){
        LL N2, N3, N4;
        scanf("%lld %lld %lld", &N2, &N3, &N4);
        
        // 長さ 10 の 棒 を 作成.
        // 長さ 3 の 棒が, 1本余る可能性あるが, 無視.
        LL ans= 0;
        LL n3 = N3 / 2;
        if(n3 <= N4){
            // (3, 3, 4)
            ans += n3;
            N4 -= n3;
            
            // (2, 4, 4)
            LL n4 = N4 / 2;
            LL n24 = min(N2, n4);
            ans += n24;
            N2 -= n24;
            
            // (2, 2, 2, 4)
            if(N4 != n4 * 2){
                if(N2 >= 3){
                    ans++;
                    N2 -= 3;
                }
            }
            
            // (2, 2, 2, 2, 2)
            LL n2 = N2 / 5;
            ans += n2;
        }else{
            // (3, 3, 4)
            ans += N4;
            N3 -= N4 * 2;
            
            // (3, 3, 2, 2)
            LL n23 = min(N2, N3) / 2;
            ans += n23;
            N2 -= n23 * 2;
            N3 -= n23 * 2;
            
            // (2, 2, 2, 2, 2)
            LL n2 = N2 / 5;
            ans += n2;
        }
        
        // 出力.
        printf("%lld\n", ans);
    }
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

int main(){

// 1. 入力情報.

int T;

scanf("%d", &T);

// 2. クエリ回答.

rep(i, T){

LL N2, N3, N4;

scanf("%lld %lld %lld", &N2, &N3, &N4);

// 長さ 10 の棒を作成.

// 長さ 3 の棒が, 1本余る可能性あるが, 無視.

LL ans= 0;

LL n3 = N3 / 2;

if(n3 <= N4){

// (3, 3, 4)

ans += n3;

N4 -= n3;

// (2, 4, 4)

LL n4 = N4 / 2;

LL n24 = min(N2, n4);

ans += n24;

N2 -= n24;

// (2, 2, 2, 4)

if(N4 != n4 * 2){

if(N2 >= 3){

ans++;

N2 -= 3;

}

// (2, 2, 2, 2, 2)

LL n2 = N2 / 5;

ans += n2;

}else{

// (3, 3, 4)

ans += N4;

N3 -= N4 * 2;

// (3, 3, 2, 2)

LL n23 = min(N2, N3) / 2;

ans += n23;

N2 -= n23 * 2;

N3 -= n23 * 2;

// (2, 2, 2, 2, 2)

LL n2 = N2 / 5;

ans += n2;

}

// 出力.

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

}

return 0;

}

[入力例]
5
3 4 1
7 0 0
0 0 7
0 0 0
1000000000000000 1000000000000000 1000000000000000

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

[入力例]
20
36 112 72
92 61 67
59 59 72
63 4 103
103 63 4
119 96 74
30 112 96
98 61 1
33 3 82
34 77 20
71 109 14
40 52 15
89 0 15
3 84 98
95 41 6
3 24 4
62 113 3
117 23 62
67 27 97
23 102 113

[出力例]
69
63
58
55
40
82
78
38
34
37
49
29
23
45
33
5
34
54
60
74

[入力例]
30
5321 7661 6793
4132 7399 8201
6164 11064 2291
11945 7434 3588
11106 797 12089
1298 7596 9460
11423 11121 4504
8614 7146 11395
6482 7458 7156
5325 5719 285
9070 2202 8960
12194 3869 8798
4770 8479 7498
12099 2499 8485
2690 10112 9743
2595 11087 1936
599 3992 1408
3370 6874 5128
10216 11395 1709
8586 7213 11453
3617 1863 11294
9373 6187 6843
2626 11253 9954
6650 1357 10072
7673 9727 3941
3705 1164 194
70 5032 4508
8848 6466 2153
4381 4286 4640
3875 3967 6781

[出力例]
6079
6326
5373
6054
7295
5096
7422
8424
6396
2894
6058
7118
6496
6563
7468
3233
1707
4787
6145
8462
4548
6467
7882
5765
6028
1167
2586
4570
4018
4677

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

[入力例]

3 4 1

7 0 0

0 0 7

0 0 0

1000000000000000 1000000000000000 1000000000000000

[出力例]

900000000000000

※AtCoderのテストケースより

[入力例]

36 112 72

92 61 67

59 59 72

63 4 103

103 63 4

119 96 74

30 112 96

98 61 1

33 3 82

34 77 20

71 109 14

40 52 15

89 0 15

3 84 98

95 41 6

3 24 4

62 113 3

117 23 62

67 27 97

23 102 113

[出力例]

[入力例]

5321 7661 6793

4132 7399 8201

6164 11064 2291

11945 7434 3588

11106 797 12089

1298 7596 9460

11423 11121 4504

8614 7146 11395

6482 7458 7156

5325 5719 285

9070 2202 8960

12194 3869 8798

4770 8479 7498

12099 2499 8485

2690 10112 9743

2595 11087 1936

599 3992 1408

3370 6874 5128

10216 11395 1709

8586 7213 11453

3617 1863 11294

9373 6187 6843

2626 11253 9954

6650 1357 10072

7673 9727 3941

3705 1164 194

70 5032 4508

8848 6466 2153

4381 4286 4640

3875 3967 6781

[出力例]

6079

6326

5373

6054

7295

5096

7422

8424

6396

2894

6058

7118

6496

6563

7468

3233

1707

4787

6145

8462

4548

6467

7882

5765

6028

1167

2586

4570

4018

4677

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

// 解き直し.
// https://atcoder.jp/contests/arc126/editorial/2626
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
#define all(x) x.begin(), x.end()

struct line{
    int a, b; // 座標 a, b.
    bool operator < (const line& rhs) const{
        return (a == rhs.a) ? (b > rhs.b) : (a < rhs.a);
    }
};

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    vector<line> v;
    rep(i, M){
        int a, b;
        scanf("%d %d", &a, &b);
        line l;
        l.a = a;
        l.b = b;
        v.pb(l);
    }
    
    // 2. sort.
    sort(all(v));
    
    // 3. 狭義単調増加な数列の長さの最大値は？
    // 以下の問題を参照.
    // https://atcoder.jp/contests/typical90/tasks/typical90_bh
    // -> LIS(Longest increase subsequence) を 利用.
    vi dp;
    rep(i, M){
        // 数列を保存.
        line l = v[i];
        if(dp.size() == 0 || dp.back() < l.b){
            dp.pb(l.b);
        }else{
            int at = lower_bound(all(dp), l.b) - dp.begin();
            dp[at] = l.b;
        }
    }
    // rep(i, dp.size()) printf("%d\n", dp[i]);
    
    // 4. 出力.
    printf("%d\n", dp.size());
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc126/editorial/2626

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

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

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

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

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

#define pb push_back

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

struct line{

int a, b; // 座標 a, b.

bool operator < (const line& rhs) const{

return (a == rhs.a) ? (b > rhs.b) : (a < rhs.a);

}

};

int main(){

// 1. 入力情報.

int N, M;

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

vector<line> v;

rep(i, M){

int a, b;

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

line l;

l.a = a;

l.b = b;

v.pb(l);

}

// 2. sort.

sort(all(v));

// 3. 狭義単調増加な数列の長さの最大値は？

// 以下の問題を参照.

// https://atcoder.jp/contests/typical90/tasks/typical90_bh

// -> LIS(Longest increase subsequence) を利用.

vi dp;

rep(i, M){

// 数列を保存.

line l = v[i];

if(dp.size() == 0 || dp.back() < l.b){

dp.pb(l.b);

}else{

int at = lower_bound(all(dp), l.b) - dp.begin();

dp[at] = l.b;

}

// rep(i, dp.size()) printf("%d\n", dp[i]);

// 4. 出力.

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

return 0;

}

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

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

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

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

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

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

[入力例]
1 1
1 1

[出力例]
1

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

[出力例]
3

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

[出力例]
6

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

[出力例]
6

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

[出力例]
10

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

[入力例]

3 3

1 2

2 3

3 1

[出力例]

※AtCoderのテストケースより

[入力例]

3 5

1 1

2 1

2 2

3 2

3 3

[出力例]

※AtCoderのテストケースより

[入力例]

7 5

1 7

7 1

3 4

2 6

5 2

[出力例]

※AtCoderのテストケースより

[入力例]

1 1

[出力例]

[入力例]

5 6

1 3

4 1

4 5

5 3

3 2

3 4

[出力例]

[入力例]

8 15

2 1

2 3

3 4

3 2

1 1

4 4

4 5

5 7

5 4

5 8

6 5

6 6

7 6

7 8

8 8

[出力例]

[入力例]

15 20

9 8

1 3

5 4

10 1

10 11

7 7

9 7

4 2

8 14

7 14

5 12

8 11

10 13

15 14

2 10

13 8

4 11

12 4

2 12

5 3

[出力例]

[入力例]

25 50

25 16

6 19

22 14

10 21

6 20

7 20

12 3

8 13

19 23

13 21

8 16

1 22

4 1

14 18

11 9

23 2

13 19

4 10

5 7

1 15

24 1

5 11

3 10

5 4

15 20

17 22

24 16

25 11

10 15

7 6

14 16

8 11

11 13

6 7

15 8

6 9

6 18

8 25

15 12

14 7

16 2

22 6

3 13

10 10

20 4

16 23

9 10

16 20

5 12

12 14

[出力例]

■参照サイト
AtCoder Regular Contest 126
060 – Chimera

2021年9月22日2021年9月22日

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

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

■感想.
1. 問題F は, 方針が見えなかったので, 解説を参考に実装したところ AC版に到達できた.
2. 実装に, 非常に苦労したものの, いろいろ参考になった知識が多く, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/abc219/editorial/2654
// 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 vvp = vector<vp>;
#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()
const LL INF = 202020202020202020;

int main(){
    
    // 1. 入力情報.
    char c[202020];
    LL K;
    scanf("%s %lld", c, &K);
    string s(c);
    
    // 2. ロボットの位置(文字列 S を 1回分).
    set<P> v;
    P cur, bef = {0, 0};
    v.insert({0, 0});
    rep(i, s.size()){
        // 今回分更新.
        // 下.
        if(s[i] == 'L'){
            cur.a = bef.a - 1;
            cur.b = bef.b;
        }
        
        // 右.
        if(s[i] == 'R'){
            cur.a = bef.a + 1;
            cur.b = bef.b;
        }
        
        // 上.
        if(s[i] == 'U'){
            cur.a = bef.a;
            cur.b = bef.b - 1;
        }
        
        // 下.
        if(s[i] == 'D'){
            cur.a = bef.a;
            cur.b = bef.b + 1;
        }
        
        // 保存.
        v.insert(cur);
        
        // 前回分更新.
        bef = cur;
    }
    LL a = cur.a, b = cur.b;
    
    // 3. d を 計算(※解説通り).
    // a が 0 で無い場合は, q = x / a を ベースに考える.
    // b が 0 で無い場合は, q = y / b を ベースに考える.
    auto f = [](set<P> &v, int N, LL a, LL b, LL* d) -> void{
        map<P, int> m;
        vvp qs(N);
        int i = -1;
        for(auto &p : v){
            // q, s, t を 計算
            LL x = p.a, y = p.b;
            LL q = INF, r = INF;
            
            // テストケース 046.txt, 047.txt で, WA版となったので修正.
            // -> 符号に応じて, 計算式が変動するかをチェック.
            // -> 余りが, 常に, 0 以上になるように寄せる必要がありそう.
            // ex.
            // (-11) % (-3) = -2, (-11) / (-3) =  3 -> 余りを, 1 として, 商を, 4 とする.
            // (+11) % (-3) = +2, (+11) / (-3) = -3
            // (-11) % (+3) = -2, (-11) / (+3) = -3 -> 余りを, 1 として, 商を, -4 とする.
            // (+11) % (+3) = +2, (+11) / (+3) =  3
            if(a != 0){
                r = x % a;
                q = x / a;
                if(r < 0 && x < 0){
                    r += abs(a);
                    q = (x - r) / a;
                }
            }else{
                r = y % b;
                q = y / b;
                if(r < 0 && y < 0){
                    r += abs(b);
                    q = (y - r) / b;
                }
            }
            LL s = x - q * a;
            LL t = y - q * b;
            ++i;
            
            // (s, t)ごとに保存.
            P g = {s, t};
            P h = {q, i};
            
            // 前回以前で, 出現済の場合.
            if(m.count(g) > 0){
                int j = m[g];
                qs[j].pb(h);
                continue;
            }
            
            // 初回出現した場合.
            if(m.count(g) == 0){
                m[g] = m.size();
                int j = m[g];
                qs[j].pb(h);
            }
        }
        
        // sort.
        rep(j, m.size()) sort(all(qs[j]));
        
        // d を 保存.
        rep(j, m.size()){
            rep(k, qs[j].size() - 1){
                LL qDiff = qs[j][k + 1].a - qs[j][k].a;
                int at = qs[j][k].b;
                d[at] = qDiff;
            }
        }
        
        // 終了.
        return;
    };
    
    // 4. 場合分け.
    int N = v.size();
    LL d[N];
    rep(i, N) d[i] = INF;
    if(a == 0 && b == 0) rep(i, N) d[i] = 1;
    else                 f(v, N, a, b, d);
    
    // 5. 集計.
    LL ans = 0;
    rep(i, N) ans += min(K, d[i]);
    
    // 6. 出力.
    printf("%lld\n", ans);
    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

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

// 解き直し.

// https://atcoder.jp/contests/abc219/editorial/2654

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using P = pair<LL, LL>;

using vp = vector;

using vvp = vector<vp>;

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

const LL INF = 202020202020202020;

int main(){

// 1. 入力情報.

char c[202020];

LL K;

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

string s(c);

// 2. ロボットの位置(文字列 S を 1回分).

set v;

P cur, bef = {0, 0};

v.insert({0, 0});

rep(i, s.size()){

// 今回分更新.

// 下.

if(s[i] == 'L'){

cur.a = bef.a - 1;

cur.b = bef.b;

}

// 右.

if(s[i] == 'R'){

cur.a = bef.a + 1;

cur.b = bef.b;

}

// 上.

if(s[i] == 'U'){

cur.a = bef.a;

cur.b = bef.b - 1;

}

// 下.

if(s[i] == 'D'){

cur.a = bef.a;

cur.b = bef.b + 1;

}

// 保存.

v.insert(cur);

// 前回分更新.

bef = cur;

}

LL a = cur.a, b = cur.b;

// 3. d を計算(※解説通り).

// a が 0 で無い場合は, q = x / a をベースに考える.

// b が 0 で無い場合は, q = y / b をベースに考える.

auto f = [](set &v, int N, LL a, LL b, LL* d) -> void{

map<P, int> m;

vvp qs(N);

int i = -1;

for(auto &p : v){

// q, s, t を計算

LL x = p.a, y = p.b;

LL q = INF, r = INF;

// テストケース 046.txt, 047.txt で, WA版となったので修正.

// -> 符号に応じて, 計算式が変動するかをチェック.

// -> 余りが, 常に, 0 以上になるように寄せる必要がありそう.

// ex.

// (-11) % (-3) = -2, (-11) / (-3) = 3 -> 余りを, 1 として, 商を, 4 とする.

// (+11) % (-3) = +2, (+11) / (-3) = -3

// (-11) % (+3) = -2, (-11) / (+3) = -3 -> 余りを, 1 として, 商を, -4 とする.

// (+11) % (+3) = +2, (+11) / (+3) = 3

if(a != 0){

r = x % a;

q = x / a;

if(r < 0 && x < 0){

r += abs(a);

q = (x - r) / a;

}

}else{

r = y % b;

q = y / b;

if(r < 0 && y < 0){

r += abs(b);

q = (y - r) / b;

}

LL s = x - q * a;

LL t = y - q * b;

++i;

// (s, t)ごとに保存.

P g = {s, t};

P h = {q, i};

// 前回以前で, 出現済の場合.

if(m.count(g) > 0){

int j = m[g];

qs[j].pb(h);

continue;

}

// 初回出現した場合.

if(m.count(g) == 0){

m[g] = m.size();

int j = m[g];

qs[j].pb(h);

}

// sort.

rep(j, m.size()) sort(all(qs[j]));

// d を保存.

rep(j, m.size()){

rep(k, qs[j].size() - 1){

LL qDiff = qs[j][k + 1].a - qs[j][k].a;

int at = qs[j][k].b;

d[at] = qDiff;

}

// 終了.

return;

};

// 4. 場合分け.

int N = v.size();

LL d[N];

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

if(a == 0 && b == 0) rep(i, N) d[i] = 1;

else f(v, N, a, b, d);

// 5. 集計.

LL ans = 0;

rep(i, N) ans += min(K, d[i]);

// 6. 出力.

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

return 0;

}

[入力例]
RDRUL
2

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

[入力例]
LR
1000000000000

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

[入力例]
UUURRDDDRRRUUUURDLLUURRRDDDDDDLLLLLLU
31415926535

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

[入力例]
R
1

[出力例]
2

[入力例]
RU
2

[出力例]
5

[入力例]
LDURU
3

[出力例]
8

[入力例]
LULRDRRLDULURRLRLRRUDRDLRULDDDDLDRUDDDLRDDLDDUDRLD
1732050807

[出力例]
45033320985

[入力例]
DLUDDLULLURRDRUULRLUDRDULURDDDUULLDLLDUUDUDUUURRRUUDRRURLRDLLDLLRULULLLUURLRDLLDULRLLDRDDLUDDURURLUL
223606797749

[出力例]
11627553482950

[入力例]
LUULLLDLDRRUDDDUDLRDRLDRURUULULRRDURLRDLURULLULLDDDLRLLDRDRRRLDRUDRRLRDLUUDLULUDRLUULLLRRLDDRRULRDLLULULDURULUDUDRUDLDDRDLLRUULRLLLDUUUDDUDLDDLRDDLUDDURUDRUDDUUDRULDLLDUDUDLURRUURURDRRURUURRRURRDRLRUURDDRLRUDLDRDULDLRDRRLRLRDDDDLUDDDLULURRULUDLDUDRRLURDDRLLLDRUURULURLLLRUULLLRURRRURLLDULLDDLDLUURRUULDRLRDRURRRDRDUURLDLURDURLLUDLDDRRRLUDRDDLURRLULUDRLLLDLRURUDDDLRRUUULRRLDLRDDURRLLRDUDRDLLLRDLRDLUUURRLLURDURDDLRULUULDRLRDLRLRRDDRULLLLLDURLUDDRUUUUDLRLUDLRLRLDRRLDDULDLLUUUDRLLLDDLRRLDLDUUULLDLLLRRUURDULDLULUUDRLDLDUUDRLLDLUURUUDDLULUURRLDUDLLDRRULRULRDRULLLUUURRRURULULDUDUDRUDDDDDDLRRLDDRLRDLDRRLLRDDRUUDDLLUDLLURDDLDUDDRDULDDURLDLLRDDRLDDDLLLRULLULRURUULULRDRDURUDULRDDUDLDRLRUUULRLUDDULRURRRLDLULLURUDRRLDDRURLDLRDLDULLRUDRLLRLRRRRLLRDLRLLRDURURLDLDDRLRUDRRRLLRDLLLLDLURUDULURURLDRDDURRUDDRDLDLDDULLRLLDURLRLDRUDLUUDLUDULURDLUDURRULDDULRLDLDDLDRLRRURURDRDRUURDRLLDULLLUULUDDLRDRLURDULUDRUURRUDDDRURLURLUDRDURDUDLURUUUULULRRUUDULLLULLUUUULDLUURDRDUDUDRULDLRRUDURDLRDULULDDRRRDURDRRUULRDULRLRLLR
120205690315

[出力例]
28488748604720

[入力例]
URLRDRDDLDLLRDUUUURDULLLRUUUULRLULULLLRDDLDDLDDLRRRDLULDDDUDRDULDDDUURLDUUDDRURRLLLDDUUDRRLULLDLRUUULRDDUDDUULDLDLDLDURUULUULDRLUDLLRDRRURRULRLDURLRRRRDLDLRRRLDLDRURLDUDLLDDURUDLUULDLULRRDDDLRRRUDRRRDRLRULRDLURLLRUULRDLDURUURLUUULDUDDDULURLLRRRRRDRLDRRDULDDDDDUULDDURLUDLURDURDDURRLDLDRLUDDUURRDURRRRLURURRDURDDLRDLRLLRDLULURLDUDLLURDDRRRULRLRURDLRURUURDUUULLRURDLLUDDLULLUURLLRURULRRURDLLRULLURRRRDUUDULULDLLRUURDRLRRRDLURURUUDRURDRURDRULRLLRUDURULDRRRUURUDLUULRRDLDLULRRRRLRDRULRULLUDRULLLDDULRUDUUDDRURRURDDDDDUDUUUURLRLLRDDLULDDRDLRRDLURDULDLRDRUULULRULURDRUDLLLURULLUUUUDLLDDLDURRLURLRLLDLDDRLDLRRDULLRDUUDUUDDURRRDUUULLRRDLLDDRRDUURUUDUUURDLULLRURULULRRLLLRLDLLDRUURUURLRRUDLDURRDRLUDDRULRLLDUDRLUDDURDUDDDLUDLLDDDRUDRRDULDUUURLRRLDRRRLURLUUDLURDDULRDRLLDLUDRLDULDLDDLRDLRULDDRUDUUDULRUUDRRLLDLDLURRRDURLRRDRULRRRRURLUUULLDULRDUDLRLDLRLLDLLUULUURDDRRLRULRLLUULRDURUDUUUDDDUDDLLRUDUDDLLLURDDURLURUUDLLRUURRUUUUULLLLRRDLLRRLURRLDDDRRRRUULLDRLULUDDLDRDLUUULLUDLLDLRLLULRRLRLURRULUUDDUUDDRLURLULURDLRLRLLDRURRURUUDLRLDDRURLDRLDRRDRDUUULULLUURRRRLLUDRDRDUURRLLURRRURUUDUDUUDRLDDLRLUURLLRLUURRUDDULDLDDUUULDUDRLURRDDRLDLRURRULURULRRRLDURULDUDRUDDRRLLRUURLRURLRUDLRRDUDUDULDUDDDDDLUDUUUDLRLRLUUUULLDLRRUDRRDDLDUDRDUULDULDDURURLDLDDRRUDRULRRULRDUDDLRLULDDULDRLULUDLDRRDLRRRUUDLRUDDLULDDRRLLUDDLDURRUUDURULLLLUDRRLDLLUDDURDLDLDURDDRLULRLLDLLRDDDURDUURRULDDUUDLRLDLRLRRDLRULLUULLDDUURULRDUDRURDRULLLDRRRLDRUUUURDDDDDLUULUDURDDRDDRUDLDRUULULLRRDLRRRRUDDRRRLUUDDUUDDLDLRUUURDLULULLDURRLLDDUUDRDLRDRLDRULDRUDLRURDRLUUDRLLLRULUURLUDLLUDULLRRUUDRLLRLLDLLRRUUUULLRRRDUUDUUUULRRRDDRUULLUDLLRUDDLRRDLLLURLRRUURRRUDULDDRRRUDRRDLURRLULRRLDUDLULUDURRLDDURDLDDDLRUUDDDDDUUUDULUUDRLURLDUDRLRRRDRLLRDLDRLLUURRRUURDRDULDLDLLRUULLUDLLURRRLRLDRRLDDURURDLRLRUUULLDDRUUDULRDLRRURLUDDRRDRDLUDDRULLUURLDLDUDDRUUURUULRRRRRRUDDRUURLURDLDRULDDLDRLLUULLRRDRLUUDURLDRLDDRRLDDRRLUDLLDUURLRUUDRRDDDULUURLDDLLURRDDRRRUULDRLDULLULDRULUUDLLLDLULLURLDUDLDUULULRLDLULURLRDRDDRLULLLURDLULDDUULLDDLURLDLRDLDRRDDRRRRLLDRRDDRRUUDLULRUDUDLRUD
670499185382

[出力例]
342625083730316

[入力例]

RDRUL

[出力例]

※AtCoderテストケースより

[入力例]

1000000000000

[出力例]

※AtCoderテストケースより

[入力例]

UUURRDDDRRRUUUURDLLUURRRDDDDDDLLLLLLU

31415926535

[出力例]

219911485785

※AtCoderテストケースより

[入力例]

[出力例]

[入力例]

[出力例]

[入力例]

LDURU

[出力例]

[入力例]

LULRDRRLDULURRLRLRRUDRDLRULDDDDLDRUDDDLRDDLDDUDRLD

1732050807

[出力例]

45033320985

[入力例]

DLUDDLULLURRDRUULRLUDRDULURDDDUULLDLLDUUDUDUUURRRUUDRRURLRDLLDLLRULULLLUURLRDLLDULRLLDRDDLUDDURURLUL

223606797749

[出力例]

11627553482950

[入力例]

LUULLLDLDRRUDDDUDLRDRLDRURUULULRRDURLRDLURULLULLDDDLRLLDRDRRRLDRUDRRLRDLUUDLULUDRLUULLLRRLDDRRULRDLLULULDURULUDUDRUDLDDRDLLRUULRLLLDUUUDDUDLDDLRDDLUDDURUDRUDDUUDRULDLLDUDUDLURRUURURDRRURUURRRURRDRLRUURDDRLRUDLDRDULDLRDRRLRLRDDDDLUDDDLULURRULUDLDUDRRLURDDRLLLDRUURULURLLLRUULLLRURRRURLLDULLDDLDLUURRUULDRLRDRURRRDRDUURLDLURDURLLUDLDDRRRLUDRDDLURRLULUDRLLLDLRURUDDDLRRUUULRRLDLRDDURRLLRDUDRDLLLRDLRDLUUURRLLURDURDDLRULUULDRLRDLRLRRDDRULLLLLDURLUDDRUUUUDLRLUDLRLRLDRRLDDULDLLUUUDRLLLDDLRRLDLDUUULLDLLLRRUURDULDLULUUDRLDLDUUDRLLDLUURUUDDLULUURRLDUDLLDRRULRULRDRULLLUUURRRURULULDUDUDRUDDDDDDLRRLDDRLRDLDRRLLRDDRUUDDLLUDLLURDDLDUDDRDULDDURLDLLRDDRLDDDLLLRULLULRURUULULRDRDURUDULRDDUDLDRLRUUULRLUDDULRURRRLDLULLURUDRRLDDRURLDLRDLDULLRUDRLLRLRRRRLLRDLRLLRDURURLDLDDRLRUDRRRLLRDLLLLDLURUDULURURLDRDDURRUDDRDLDLDDULLRLLDURLRLDRUDLUUDLUDULURDLUDURRULDDULRLDLDDLDRLRRURURDRDRUURDRLLDULLLUULUDDLRDRLURDULUDRUURRUDDDRURLURLUDRDURDUDLURUUUULULRRUUDULLLULLUUUULDLUURDRDUDUDRULDLRRUDURDLRDULULDDRRRDURDRRUULRDULRLRLLR

120205690315

[出力例]

28488748604720

[入力例]

URLRDRDDLDLLRDUUUURDULLLRUUUULRLULULLLRDDLDDLDDLRRRDLULDDDUDRDULDDDUURLDUUDDRURRLLLDDUUDRRLULLDLRUUULRDDUDDUULDLDLDLDURUULUULDRLUDLLRDRRURRULRLDURLRRRRDLDLRRRLDLDRURLDUDLLDDURUDLUULDLULRRDDDLRRRUDRRRDRLRULRDLURLLRUULRDLDURUURLUUULDUDDDULURLLRRRRRDRLDRRDULDDDDDUULDDURLUDLURDURDDURRLDLDRLUDDUURRDURRRRLURURRDURDDLRDLRLLRDLULURLDUDLLURDDRRRULRLRURDLRURUURDUUULLRURDLLUDDLULLUURLLRURULRRURDLLRULLURRRRDUUDULULDLLRUURDRLRRRDLURURUUDRURDRURDRULRLLRUDURULDRRRUURUDLUULRRDLDLULRRRRLRDRULRULLUDRULLLDDULRUDUUDDRURRURDDDDDUDUUUURLRLLRDDLULDDRDLRRDLURDULDLRDRUULULRULURDRUDLLLURULLUUUUDLLDDLDURRLURLRLLDLDDRLDLRRDULLRDUUDUUDDURRRDUUULLRRDLLDDRRDUURUUDUUURDLULLRURULULRRLLLRLDLLDRUURUURLRRUDLDURRDRLUDDRULRLLDUDRLUDDURDUDDDLUDLLDDDRUDRRDULDUUURLRRLDRRRLURLUUDLURDDULRDRLLDLUDRLDULDLDDLRDLRULDDRUDUUDULRUUDRRLLDLDLURRRDURLRRDRULRRRRURLUUULLDULRDUDLRLDLRLLDLLUULUURDDRRLRULRLLUULRDURUDUUUDDDUDDLLRUDUDDLLLURDDURLURUUDLLRUURRUUUUULLLLRRDLLRRLURRLDDDRRRRUULLDRLULUDDLDRDLUUULLUDLLDLRLLULRRLRLURRULUUDDUUDDRLURLULURDLRLRLLDRURRURUUDLRLDDRURLDRLDRRDRDUUULULLUURRRRLLUDRDRDUURRLLURRRURUUDUDUUDRLDDLRLUURLLRLUURRUDDULDLDDUUULDUDRLURRDDRLDLRURRULURULRRRLDURULDUDRUDDRRLLRUURLRURLRUDLRRDUDUDULDUDDDDDLUDUUUDLRLRLUUUULLDLRRUDRRDDLDUDRDUULDULDDURURLDLDDRRUDRULRRULRDUDDLRLULDDULDRLULUDLDRRDLRRRUUDLRUDDLULDDRRLLUDDLDURRUUDURULLLLUDRRLDLLUDDURDLDLDURDDRLULRLLDLLRDDDURDUURRULDDUUDLRLDLRLRRDLRULLUULLDDUURULRDUDRURDRULLLDRRRLDRUUUURDDDDDLUULUDURDDRDDRUDLDRUULULLRRDLRRRRUDDRRRLUUDDUUDDLDLRUUURDLULULLDURRLLDDUUDRDLRDRLDRULDRUDLRURDRLUUDRLLLRULUURLUDLLUDULLRRUUDRLLRLLDLLRRUUUULLRRRDUUDUUUULRRRDDRUULLUDLLRUDDLRRDLLLURLRRUURRRUDULDDRRRUDRRDLURRLULRRLDUDLULUDURRLDDURDLDDDLRUUDDDDDUUUDULUUDRLURLDUDRLRRRDRLLRDLDRLLUURRRUURDRDULDLDLLRUULLUDLLURRRLRLDRRLDDURURDLRLRUUULLDDRUUDULRDLRRURLUDDRRDRDLUDDRULLUURLDLDUDDRUUURUULRRRRRRUDDRUURLURDLDRULDDLDRLLUULLRRDRLUUDURLDRLDDRRLDDRRLUDLLDUURLRUUDRRDDDULUURLDDLLURRDDRRRUULDRLDULLULDRULUUDLLLDLULLURLDUDLDUULULRLDLULURLRDRDDRLULLLURDLULDDUULLDDLURLDLRDLDRRDDRRRRLLDRRDDRRUUDLULRUDUDLRUD

670499185382

[出力例]

342625083730316

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

2021年9月20日

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

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

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

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

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

// 解き直し.
// https://atcoder.jp/contests/abc219/editorial/2666
// 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
constexpr int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};

int main(){
    
    // 1. 入力情報.
    string board = "";
    rep(i, 4){
        string s = "";
        rep(j, 4){
            int c;
            scanf("%d", &c);
            s.pb(c + '0');
        }
        // 村情報.
        board += s;
    }
    
    // 2. bfs.
    // https://ja.wikipedia.org/wiki/幅優先探索
    auto bfs = [&](string &G, int s, int H, int W, int* c, int l, char f) -> void{
        // 空のキュー.
        queue<int> q;
        
        // 訪問済みフラグ設定.
        c[s] = l;
        
        // 探索地点 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;
            rep(i, 4){
                nx = cx + dx[i];
                ny = cy + dy[i];
                n = nx + ny * W;
                
                // 訪問不可能なマス であれば, 処理をスキップ.
                if(nx < 0 || nx >= W || ny < 0 || ny >= H) continue;
                
                // 訪問先のマスで, 訪問可能 かつ 未訪問 であれば, 連結成分を設定.
                if(G[n] == f && !c[n]) c[n] = l, q.push(n);
            }
        }
        return;
    };
    
    // 3. 全探索.
    int ans = 0;
    repx(i, 1, 1 << 16){
        // 2進数値(16桁)で, '1' を 村, '0' を 平野 と見做して, お堀を作成.
        string g = "";
        rep(j, 16){
            if(i & (1 << (15 - j))) g.pb('1');
            else                    g.pb('0');
        }
        
        // 連結成分チェック(村を含む側).
        int cIn[16], idx = 0;
        rep(j, 16) cIn[j] = 0;
        rep(j, 16) if(!cIn[j] && g[j] == '1') bfs(g, j, 4, 4, cIn, ++idx, '1');
        
        // 連結成分(村を含む側)の個数が, 1 より大きい場合.
        if(idx > 1) continue;
        
        // 例外パターン.
        // 村を含まない側について, お堀に, 四方を囲まれた領域があるか？
        // -> 以下のロジックは, 正しく動作しない.
        // ex.
        // i = 60223 が, 反例の一つ.
        // 1110
        // 1011
        // 0011
        // 1111
        // -> r = 1, c = 1 で, one = 4 となるが, 入力例 1 では, 除外してはならないパターン.
        /*
        bool ok = true;
        vs a;
        a.pb(g.substr(0, 4));
        a.pb(g.substr(4, 4));
        a.pb(g.substr(8, 4));
        a.pb(g.substr(12, 4));
        rep(r, 4){
            rep(c, 4){
                // 基準とする領域.
                if(a[r][c] == '0'){
                    int one = 0;
                    
                    // 左方向.
                    repr(p, c - 1, 0){
                        if(a[r][p] == '1'){
                            one++;
                            break;
                        }
                    }
                    
                    // 右方向.
                    repx(p, c + 1, 4){
                        if(a[r][p] == '1'){
                            one++;
                            break;
                        }
                    }
                    
                    // 上方向.
                    repr(p, r - 1, 0){
                        if(a[p][c] == '1'){
                            one++;
                            break;
                        }
                    }
                    
                    // 下方向.
                    repx(p, r + 1, 4){
                        if(a[p][c] == '1'){
                            one++;
                            break;
                        }
                    }
                    
                    // 判定.
                    if(one == 4) ok = false;
                    
                    // ex.
                    // i = 59863
                    // 1110
                    // 1001
                    // 1101
                    // 0111
                    // -> r = 1, c = 1 で, one = 4 となるはず.
                    // if(i == 59863) printf("r=%d c=%d one=%d\n", r, c, one);
                }
                if(!ok) break;
            }
            if(!ok) break;
        }
        
        // お堀に, 四方を囲まれた領域があった場合.
        if(!ok) continue;
        */
        
        // 作成したお堀が, 条件を満たすか？
        // 自己交差を含むか.
        // -> (r, c) = '1' について, 常に, 右下, 左下 を チェック(※以下の二パターン).
        // 10
        // 01
        // 
        // 01
        // 10
        bool ok = true;
        vs a;
        a.pb(g.substr(0, 4));
        a.pb(g.substr(4, 4));
        a.pb(g.substr(8, 4));
        a.pb(g.substr(12, 4));
        rep(r, 3){
            rep(c, 3){
                if(a[r][c] == '1'){
                    // 右下.
                    if(a[r][c + 1] == '0' && a[r + 1][c] == '0' && a[r + 1][c + 1] == '1') ok = false;
                    
                    // 左下.
                    if(c > 0 && a[r][c - 1] == '0' && a[r + 1][c] == '0' && a[r + 1][c - 1] == '1') ok = false;
                }
            }
        }
        
        // 内部に, 空洞があるか.
        // -> 以下のロジックは, 正しく動作しない(入力例 1 で, 1307 となり, 1272 にならない).
        /*
        // 空洞のパターン(その1).
        // 1110
        // 1010
        // 1110
        // 0000
        // -> 1110101011100000, 0111010101110000, 0000111010101110, 0000011101010111 と照合.
        bitset<16> bsg(g);
        bitset<16> bs01("1110101011100000");
        bitset<16> bs02("0111010101110000");
        bitset<16> bs03("0000111010101110");
        bitset<16> bs04("0000011101010111");
        if((bsg & bs01).count() == 8 && g[5] == '0')  ok = false;
        if((bsg & bs02).count() == 8 && g[6] == '0')  ok = false;
        if((bsg & bs03).count() == 8 && g[9] == '0')  ok = false;
        if((bsg & bs04).count() == 8 && g[10] == '0') ok = false;
        
        // 空洞のパターン(その2).
        // 1111
        // 1001
        // 1111
        // 0000
        // -> 1111100111110000, 0000111110011111 と照合.
        bitset<16> bs11("1111100111110000");
        bitset<16> bs12("0000111110011111");
        if((bsg & bs11).count() == 10 && (g[5] == '0' || g[6] == '0'))  ok = false;
        if((bsg & bs12).count() == 10 && (g[9] == '0' || g[10] == '0')) ok = false;
        
        // 空洞のパターン(その3).
        // 1110
        // 1010
        // 1010
        // 1110
        // -> 1110101010101110, 0111010101010111 と 照合.
        bitset<16> bs21("1110101010101110");
        bitset<16> bs22("0111010101010111");
        if((bsg & bs21).count() == 10 && (g[5] == '0' || g[9] == '0'))  ok = false;
        if((bsg & bs22).count() == 10 && (g[6] == '0' || g[10] == '0')) ok = false;
        
        // 空洞のパターン(その4).
        // 1111
        // 1001
        // 1001
        // 1111
        // -> 1111100110011111 と 照合.
        bitset<16> bs31("1111100110011111");
        if((bsg & bs31).count() == 12){
            if(g[5] == '0' || g[6] == '0' || g[9] == '0' || g[10] == '0') ok = false;
        }
        */
        
        // 内部に, 空洞があるか(※実装をやり直す).
        // -> 6 × 6 のエリアで確認する方法(解説通り).
        // 2進数値(36桁)で, '1' を 村, '0' を 平野 と見做して, (拡張した)お堀を作成.
        string h = "000000";
        rep(j, 16){
            if(j % 4 == 0) h.pb('0');
            if(i & (1 << (15 - j))) h.pb('1');
            else                    h.pb('0');
            if(j % 4 == 3) h.pb('0');
        }
        h += "000000";
        
        // 連結成分チェック(村を含まない側).
        idx = 0;
        int cOut[36];
        rep(j, 36) cOut[j] = 0;
        rep(j, 36) if(!cOut[j] && h[j] == '0') bfs(h, j, 6, 6, cOut, ++idx, '0');
        // if(i == 59863) printf("%s\n%s\n", g.c_str(), h.c_str());
        
        // 連結成分(村を含まない側)の個数が, 1 より大きい場合.
        if(idx > 1) continue;
        
        // 村を全て含むか.
        rep(j, 16){
            if(board[j] == '1' && g[j] == '0'){
                ok = false;
                break;
            }
        }
        
        // カウントアップ.
        if(ok) ans++;
    }
    
    // 4. 出力.
    printf("%d\n", ans);
    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

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

// 解き直し.

// https://atcoder.jp/contests/abc219/editorial/2666

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

constexpr int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};

int main(){

// 1. 入力情報.

string board = "";

rep(i, 4){

string s = "";

rep(j, 4){

int c;

scanf("%d", &c);

s.pb(c + '0');

}

// 村情報.

board += s;

}

// 2. bfs.

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

auto bfs = [&](string &G, int s, int H, int W, int* c, int l, char f) -> void{

// 空のキュー.

queue<int> q;

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

c[s] = l;

// 探索地点 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;

rep(i, 4){

nx = cx + dx[i];

ny = cy + dy[i];

n = nx + ny * W;

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

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

// 訪問先のマスで, 訪問可能かつ未訪問であれば, 連結成分を設定.

if(G[n] == f && !c[n]) c[n] = l, q.push(n);

}

return;

};

// 3. 全探索.

int ans = 0;

repx(i, 1, 1 << 16){

// 2進数値(16桁)で, '1' を村, '0' を平野と見做して, お堀を作成.

string g = "";

rep(j, 16){

if(i & (1 << (15 - j))) g.pb('1');

else g.pb('0');

}

// 連結成分チェック(村を含む側).

int cIn[16], idx = 0;

rep(j, 16) cIn[j] = 0;

rep(j, 16) if(!cIn[j] && g[j] == '1') bfs(g, j, 4, 4, cIn, ++idx, '1');

// 連結成分(村を含む側)の個数が, 1 より大きい場合.

if(idx > 1) continue;

// 例外パターン.

// 村を含まない側について, お堀に, 四方を囲まれた領域があるか？

// -> 以下のロジックは, 正しく動作しない.

// ex.

// i = 60223 が, 反例の一つ.

// 1110

// 1011

// 0011

// 1111

// -> r = 1, c = 1 で, one = 4 となるが, 入力例 1 では, 除外してはならないパターン.

bool ok = true;

vs a;

a.pb(g.substr(0, 4));

a.pb(g.substr(4, 4));

a.pb(g.substr(8, 4));

a.pb(g.substr(12, 4));

rep(r, 4){

rep(c, 4){

// 基準とする領域.

if(a[r][c] == '0'){

int one = 0;

// 左方向.

repr(p, c - 1, 0){

if(a[r][p] == '1'){

one++;

break;

}

// 右方向.

repx(p, c + 1, 4){

if(a[r][p] == '1'){

one++;

break;

}

// 上方向.

repr(p, r - 1, 0){

if(a[p][c] == '1'){

one++;

break;

}

// 下方向.

repx(p, r + 1, 4){

if(a[p][c] == '1'){

one++;

break;

}

// 判定.

if(one == 4) ok = false;

// ex.

// i = 59863

// 1110

// 1001

// 1101

// 0111

// -> r = 1, c = 1 で, one = 4 となるはず.

// if(i == 59863) printf("r=%d c=%d one=%d\n", r, c, one);

}

if(!ok) break;

}

if(!ok) break;

}

// お堀に, 四方を囲まれた領域があった場合.

if(!ok) continue;

// 作成したお堀が, 条件を満たすか？

// 自己交差を含むか.

// -> (r, c) = '1' について, 常に, 右下, 左下をチェック(※以下の二パターン).

// 10

// 01

// 10

bool ok = true;

vs a;

a.pb(g.substr(0, 4));

a.pb(g.substr(4, 4));

a.pb(g.substr(8, 4));

a.pb(g.substr(12, 4));

rep(r, 3){

rep(c, 3){

if(a[r][c] == '1'){

// 右下.

if(a[r][c + 1] == '0' && a[r + 1][c] == '0' && a[r + 1][c + 1] == '1') ok = false;

// 左下.

if(c > 0 && a[r][c - 1] == '0' && a[r + 1][c] == '0' && a[r + 1][c - 1] == '1') ok = false;

}

// 内部に, 空洞があるか.

// -> 以下のロジックは, 正しく動作しない(入力例 1 で, 1307 となり, 1272 にならない).

// 空洞のパターン(その1).

// 1110

// 1010

// 1110

// 0000

// -> 1110101011100000, 0111010101110000, 0000111010101110, 0000011101010111 と照合.

bitset<16> bsg(g);

bitset<16> bs01("1110101011100000");

bitset<16> bs02("0111010101110000");

bitset<16> bs03("0000111010101110");

bitset<16> bs04("0000011101010111");

if((bsg & bs01).count() == 8 && g[5] == '0') ok = false;

if((bsg & bs02).count() == 8 && g[6] == '0') ok = false;

if((bsg & bs03).count() == 8 && g[9] == '0') ok = false;

if((bsg & bs04).count() == 8 && g[10] == '0') ok = false;

// 空洞のパターン(その2).

// 1111

// 1001

// 1111

// 0000

// -> 1111100111110000, 0000111110011111 と照合.

bitset<16> bs11("1111100111110000");

bitset<16> bs12("0000111110011111");

if((bsg & bs11).count() == 10 && (g[5] == '0' || g[6] == '0')) ok = false;

if((bsg & bs12).count() == 10 && (g[9] == '0' || g[10] == '0')) ok = false;

// 空洞のパターン(その3).

// 1110

// 1010

// 1110

// -> 1110101010101110, 0111010101010111 と照合.

bitset<16> bs21("1110101010101110");

bitset<16> bs22("0111010101010111");

if((bsg & bs21).count() == 10 && (g[5] == '0' || g[9] == '0')) ok = false;

if((bsg & bs22).count() == 10 && (g[6] == '0' || g[10] == '0')) ok = false;

// 空洞のパターン(その4).

// 1111

// 1001

// 1111

// -> 1111100110011111 と照合.

bitset<16> bs31("1111100110011111");

if((bsg & bs31).count() == 12){

if(g[5] == '0' || g[6] == '0' || g[9] == '0' || g[10] == '0') ok = false;

}

// 内部に, 空洞があるか(※実装をやり直す).

// -> 6 × 6 のエリアで確認する方法(解説通り).

// 2進数値(36桁)で, '1' を村, '0' を平野と見做して, (拡張した)お堀を作成.

string h = "000000";

rep(j, 16){

if(j % 4 == 0) h.pb('0');

if(i & (1 << (15 - j))) h.pb('1');

else h.pb('0');

if(j % 4 == 3) h.pb('0');

}

h += "000000";

// 連結成分チェック(村を含まない側).

idx = 0;

int cOut[36];

rep(j, 36) cOut[j] = 0;

rep(j, 36) if(!cOut[j] && h[j] == '0') bfs(h, j, 6, 6, cOut, ++idx, '0');

// if(i == 59863) printf("%s\n%s\n", g.c_str(), h.c_str());

// 連結成分(村を含まない側)の個数が, 1 より大きい場合.

if(idx > 1) continue;

// 村を全て含むか.

rep(j, 16){

if(board[j] == '1' && g[j] == '0'){

ok = false;

break;

}

// カウントアップ.

if(ok) ans++;

}

// 4. 出力.

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

return 0;

}

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

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

[入力例]
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1

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

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

[出力例]
153

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

[出力例]
373

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

[出力例]
696

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

[出力例]
2401

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

[出力例]
4111

[入力例]

1 0 0 0

0 0 1 0

0 0 0 0

1 0 0 0

[出力例]

1272

※AtCoderテストケースより

[入力例]

1 1 1 1

[出力例]

※AtCoderテストケースより

[入力例]

1 0 0 1

0 0 1 0

0 1 0 0

1 0 0 1

[出力例]

153

[入力例]

1 0 0 1

0 0 0 0

1 0 0 1

[出力例]

373

[入力例]

0 1 0 0

0 0 0 1

1 0 0 0

0 0 1 0

[出力例]

696

[入力例]

0 0 0 0

0 1 1 0

0 0 0 0

[出力例]

2401

[入力例]

1 0 0 0

0 0 0 0

[出力例]

4111

■参照サイト
AtCoder Beginner Contest 219

2021年9月20日

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

C++の練習を兼ねて, AtCoder Beginner Contest 219 の問題C (Neo-lexicographic Ordering) ～問題D (Strange Lunchbox) を解いてみた.

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

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

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

int main(){
    
    // 1. 入力情報.
    char x[33];
    scanf("%s", x);
    
    // 2. 対応表作成.
    string X(x);
    map<char, char> ix, ox;
    rep(i, X.size()){
        ix['a' + i] = X[i];
        ox[X[i]]    = 'a' + i;
    }
    
    // 3. 並べ替え対象の文字列情報.
    int N;
    scanf("%d", &N);
    vs v;
    rep(i, N){
        char c[22];
        scanf("%s", c);
        string s(c);
        rep(j, s.size()) s[j] = ox[s[j]];
        v.pb(s);
    }
    
    // 4. sort.
    sort(all(v));
    
    // 5. 出力.
    for(auto &p : v){
        string ans = p;
        rep(i, ans.size()) ans[i] = ix[ans[i]];
        printf("%s\n", ans.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

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

int main(){

// 1. 入力情報.

char x[33];

scanf("%s", x);

// 2. 対応表作成.

string X(x);

map<char, char> ix, ox;

rep(i, X.size()){

ix['a' + i] = X[i];

ox[X[i]] = 'a' + i;

}

// 3. 並べ替え対象の文字列情報.

int N;

scanf("%d", &N);

vs v;

rep(i, N){

char c[22];

scanf("%s", c);

string s(c);

rep(j, s.size()) s[j] = ox[s[j]];

v.pb(s);

}

// 4. sort.

sort(all(v));

// 5. 出力.

for(auto &p : v){

string ans = p;

rep(i, ans.size()) ans[i] = ix[ans[i]];

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

}

return 0;

}

[入力例]
bacdefghijklmnopqrstuvwxzy
4
abx
bzz
bzy
caa

[出力例]
bzz
bzy
abx
caa
※AtCoderテストケースより

[入力例]
zyxwvutsrqponmlkjihgfedcba
5
a
ab
abc
ac
b

[出力例]
b
a
ac
ab
abc
※AtCoderテストケースより

[入力例]
rqpoihgfnmlwvutzyedcbaxskj
10
nvtyqh
coqnne
lgvixt
erswhk
dnfzdv
zjsxzq
sjcveg
orxzqy
ougfli
doronj

[出力例]
orxzqy
ougfli
nvtyqh
lgvixt
zjsxzq
erswhk
doronj
dnfzdv
coqnne
sjcveg

[入力例]
dcpxskjhgfnoiwvutzybamlrqe
15
sndgxatct
owgwzag
qdduk
xtajce
oajsn
ysllcgo
mzaqdh
llobul
fahfo
had
ompyn
ssmiwhgz
iazoaqa
dykdyhe
sbmrqnze

[出力例]
dykdyhe
xtajce
ssmiwhgz
sndgxatct
sbmrqnze
had
fahfo
owgwzag
oajsn
ompyn
iazoaqa
ysllcgo
mzaqdh
llobul
qdduk

[入力例]

bacdefghijklmnopqrstuvwxzy

abx

bzz

bzy

caa

[出力例]

bzz

bzy

abx

caa

※AtCoderテストケースより

[入力例]

zyxwvutsrqponmlkjihgfedcba

abc

[出力例]

abc

※AtCoderテストケースより

[入力例]

rqpoihgfnmlwvutzyedcbaxskj

nvtyqh

coqnne

lgvixt

erswhk

dnfzdv

zjsxzq

sjcveg

orxzqy

ougfli

doronj

[出力例]

orxzqy

ougfli

nvtyqh

lgvixt

zjsxzq

erswhk

doronj

dnfzdv

coqnne

sjcveg

[入力例]

dcpxskjhgfnoiwvutzybamlrqe

sndgxatct

owgwzag

qdduk

xtajce

oajsn

ysllcgo

mzaqdh

llobul

fahfo

had

ompyn

ssmiwhgz

iazoaqa

dykdyhe

sbmrqnze

[出力例]

dykdyhe

xtajce

ssmiwhgz

sndgxatct

sbmrqnze

had

fahfo

owgwzag

oajsn

ompyn

iazoaqa

ysllcgo

mzaqdh

llobul

qdduk

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

// 解き直し.
// https://atcoder.jp/contests/abc219/editorial/2651
// 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--)
const int INF = 2020202020;
int a[303], b[303], dp[303][303][303];

int main(){
    
    // 1. 入力情報.
    int N, X, Y;
    scanf("%d %d %d", &N, &X, &Y);
    rep(i, N) scanf("%d %d", &a[i], &b[i]);
    
    // 2. dp更新.
    rep(i, N + 1) rep(j, X + 1) rep(k, Y + 1) dp[i][j][k] = INF;
    dp[0][0][0] = 0;
    repx(i, 1, N + 1){
        rep(j, X + 1){
            int p = min(j + a[i - 1], X);
            rep(k, Y + 1){
                // 弁当を購入する.
                int q = min(k + b[i - 1], Y);
                dp[i][p][q] = min(dp[i][p][q], dp[i - 1][j][k] + 1);
                
                // 弁当を購入しない.
                dp[i][j][k] = min(dp[i][j][k], dp[i - 1][j][k]);
            }
        }
    }
    
    // 3. 出力.
    printf("%d\n", (dp[N][X][Y] == INF) ? -1 : dp[N][X][Y]);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc219/editorial/2651

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

const int INF = 2020202020;

int a[303], b[303], dp[303][303][303];

int main(){

// 1. 入力情報.

int N, X, Y;

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

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

// 2. dp更新.

rep(i, N + 1) rep(j, X + 1) rep(k, Y + 1) dp[i][j][k] = INF;

dp[0][0][0] = 0;

repx(i, 1, N + 1){

rep(j, X + 1){

int p = min(j + a[i - 1], X);

rep(k, Y + 1){

// 弁当を購入する.

int q = min(k + b[i - 1], Y);

dp[i][p][q] = min(dp[i][p][q], dp[i - 1][j][k] + 1);

// 弁当を購入しない.

dp[i][j][k] = min(dp[i][j][k], dp[i - 1][j][k]);

}

// 3. 出力.

printf("%d\n", (dp[N][X][Y] == INF) ? -1 : dp[N][X][Y]);

return 0;

}

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

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

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

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

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

[出力例]
5

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

[出力例]
10

[入力例]

5 6

2 1

3 4

2 3

[出力例]

※AtCoderテストケースより

[入力例]

8 8

3 4

2 3

2 1

[出力例]

-1

※AtCoderテストケースより

[入力例]

13 18

1 3

2 1

3 2

5 4

3 8

5 2

3 1

[出力例]

[入力例]

77 88

2 2

5 9

10 6

3 1

12 5

2 9

3 6

4 7

11 5

1 10

9 5

5 7

11 3

8 11

4 9

9 2

4 9

6 5

6 11

7 2

5 4

5 12

10 8

2 2

12 2

12 8

5 8

5 9

2 6

6 2

[出力例]

■参照サイト
AtCoder Beginner Contest 219

2021年9月19日

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

C++の練習を兼ねて, AtCoder Beginner Contest 218 の問題G (Game on Tree 2) を解いてみた.

■感想.
1. 問題G は, 方針が見えなかったので, 解説(プログラム)を参考に実装して, AC版に持って行く方針を取った.
2. 苦手な動的計画法(木dp)の訓練を積めたので, 非常に良かったと思う.
3. いったん自力で実装してみたものの, AC版に到達できなかった.
-> 原因としては, 二つの multiset の個数調整で, 実装が正しくなかったこと, dpへの中央値設定(のタイミング, 更新条件)などがあげられると推測する.
いずれにしても, dfsの実装を正しく行うことは, 相変わらず, 直観的に分かりづらく, 難しく感じる(※)ため, 継続して, 今後の課題になっていくと思う.
※dfsの終了条件, dp更新(条件, タイミング)などが, 難しく感じる原因の一つと推測する.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解答不能.
// https://atcoder.jp/contests/abc218/editorial/2607
// -> dfs の 実装パターン を 暗記すること(特に, 終了条件, multiset の 利用方法など).
// 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 a[101010], dp[101010];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%d", &a[i]);
    vvi G(N);
    rep(i, N - 1){
        int u, v;
        scanf("%d %d", &u, &v);
        u--, v--;
        G[u].pb(v);
        G[v].pb(u);
    }
    
    // 2. 中央値.
    auto f = [&](multiset<int> &l, multiset<int> &r) -> int{
        int m = -1;
        if(l.size() == r.size() + 1){
            auto it = l.end();
            m = *(--it);
        }else{
            auto it1 = l.end();
            auto it2 = r.begin();
            m = (*(--it1) + *it2) / 2;
        }
        return m;
    };
    
    // 3. 個数調整.
    auto g = [&](multiset<int> &l, multiset<int> &r) -> void{
        // 左側の最大値を, 右側に移動.
        if(l.size()){
            auto itr = l.end();
            --itr;
            r.insert(*itr);
            l.erase(itr);
        }
        
        // 左側, 右側のサイズを調整.
        while(l.size() < r.size()){
            l.insert(*r.begin());
            r.erase(r.begin());
        }
        return;
    };
    
    // 4. 削除.
    auto h = [&](multiset<int> &l, multiset<int> &r, int x) -> void{
        auto itr = l.end();
        --itr;
        if(*itr < x) r.erase(r.lower_bound(x));
        else         l.erase(l.lower_bound(x));
        return;
    };
    
    // 5. dfs.
    multiset<int> l, r;
    auto dfs = [&](auto self, int cur, int bef, int d) -> void{
        // 多重集合に, 要素を追加.
        l.insert(a[cur]);
        g(l, r);
        
        // dp更新.
        int mMin = 2020202020;
        int mMax = 0;
        for(int nex : G[cur]){
            if(nex != bef){
                self(self, nex, cur, d + 1);
                mMin = min(mMin, dp[nex]);
                mMax = max(mMax, dp[nex]);
            }
        }
        
        // 中央値設定など.
        if(mMax == 0)  dp[cur] = f(l, r);
        else if(d & 1) dp[cur] = mMin;
        else           dp[cur] = mMax;
        
        // 多重集合から, 要素を削除.
        h(l, r, a[cur]);
        g(l, r);
        
        // 終了.
        return;
    };
    
    // 6. 木dp.
    dfs(dfs, 0, -1, 0);
    
    // 7. 出力.
    printf("%d\n", dp[0]);
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

110

// 解答不能.

// https://atcoder.jp/contests/abc218/editorial/2607

// -> dfs の実装パターンを暗記すること(特に, 終了条件, multiset の利用方法など).

// 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 a[101010], dp[101010];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

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

vvi G(N);

rep(i, N - 1){

int u, v;

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

u--, v--;

G[u].pb(v);

G[v].pb(u);

}

// 2. 中央値.

auto f = [&](multiset<int> &l, multiset<int> &r) -> int{

int m = -1;

if(l.size() == r.size() + 1){

auto it = l.end();

m = *(--it);

}else{

auto it1 = l.end();

auto it2 = r.begin();

m = (*(--it1) + *it2) / 2;

}

return m;

};

// 3. 個数調整.

auto g = [&](multiset<int> &l, multiset<int> &r) -> void{

// 左側の最大値を, 右側に移動.

if(l.size()){

auto itr = l.end();

--itr;

r.insert(*itr);

l.erase(itr);

}

// 左側, 右側のサイズを調整.

while(l.size() < r.size()){

l.insert(*r.begin());

r.erase(r.begin());

}

return;

};

// 4. 削除.

auto h = [&](multiset<int> &l, multiset<int> &r, int x) -> void{

auto itr = l.end();

--itr;

if(*itr < x) r.erase(r.lower_bound(x));

else l.erase(l.lower_bound(x));

return;

};

// 5. dfs.

multiset<int> l, r;

auto dfs = [&](auto self, int cur, int bef, int d) -> void{

// 多重集合に, 要素を追加.

l.insert(a[cur]);

g(l, r);

// dp更新.

int mMin = 2020202020;

int mMax = 0;

for(int nex : G[cur]){

if(nex != bef){

self(self, nex, cur, d + 1);

mMin = min(mMin, dp[nex]);

mMax = max(mMax, dp[nex]);

}

// 中央値設定など.

if(mMax == 0) dp[cur] = f(l, r);

else if(d & 1) dp[cur] = mMin;

else dp[cur] = mMax;

// 多重集合から, 要素を削除.

h(l, r, a[cur]);

g(l, r);

// 終了.

return;

};

// 6. 木dp.

dfs(dfs, 0, -1, 0);

// 7. 出力.

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

return 0;

}

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

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

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

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

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

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

[入力例]
2
6 18
1 2

[出力例]
12

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

[出力例]
6

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

[出力例]
5

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

[出力例]
10

[入力例]
9
18 2 4 18 24 12 8 14 12
1 2
1 3
2 4
2 5
5 6
5 7
7 8
7 9

[出力例]
15

100

101

102

[入力例]

2 4 6 8 10

4 5

3 4

1 5

2 4

[出力例]

※AtCoderテストケースより

[入力例]

6 4 6 10 8

1 4

1 2

1 5

1 3

[出力例]

※AtCoderテストケースより

[入力例]

2 2 6 4 6 6

1 2

2 3

4 6

2 5

2 6

[出力例]

※AtCoderテストケースより

[入力例]

6 18

1 2

[出力例]

[入力例]

6 8 2

1 2

2 3

[出力例]

[入力例]

6 2 8 12 4 2

1 2

1 6

6 3

6 4

4 5

[出力例]

[入力例]

8 2 10 12 16 2 4 20 18 14 12 6 4 8 10 6

1 2

1 3

2 4

2 5

4 8

4 9

5 10

5 11

3 6

3 7

6 12

6 13

7 14

7 15

7 16

[出力例]

[入力例]

18 2 4 18 24 12 8 14 12

1 2

1 3

2 4

2 5

5 6

5 7

7 8

7 9

[出力例]

■参照サイト
AtCoder Beginner Contest 218

2021年9月17日2021年9月17日

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

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

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

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

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

// 解き直し.
// https://atcoder.jp/contests/abc218/editorial/2606
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;
using vs = vector<set<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 pb push_back
#define a first
#define b second
int info[404][404]; // 最短経路を構成する辺情報.
int memo[404][404]; // 最短経路上の辺情報.

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    vs OG(N), RG(N);
    vp edges;
    rep(i, M){
        int s, t;
        scanf("%d %d", &s, &t);
        s--, t--;
        OG[s].insert(t);  // 有向グラフ.
        RG[t].insert(s);  // 有向グラフ(逆向き).
        edges.pb({s, t}); // 有向辺.
    }
    
    // 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);
            }
        }
        return;
    };
    
    // 3. 最短距離(グラフの有向辺が, 全てそろっている場合).
    int d[N];
    rep(i, N) d[i] = 0;
    bfs(OG, 0, d);
    
    // 4. 最短経路を取得.
    // -> 到達可能な場合に, 最短経路を取得(ゴールから逆算).
    auto f = [&](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]){
                // 距離 が 1 小さい場合に, 最短経路として保存.
                if(d[e] == d[u] - 1){
                    info[e][u]++;
                    q.push(e);
                    break;
                }
            }
        }
        return;
    };
    int D = d[N - 1];
    if(D) f(RG, N - 1, d);
    
    // 5. クエリ回答.
    for(auto &e : edges){
        // 辺情報.
        int u = e.a; // 始点.
        int v = e.b; // 終点.
        
        // 到達不可能な場合.
        if(!D) puts("-1");
        
        // 到達可能な場合.
        if(D){
            // 辺(u, v) が, 最短経路上に無い場合.
            if(!info[u][v]) printf("%d\n", D);
            
            // 辺(u, v) が, 最短経路上に有る場合.
            if(info[u][v]){
                // 探索済みの場合.
                if(memo[u][v] != 0) printf("%d\n", memo[u][v]);
                
                // 探索済みでない場合.
                if(memo[u][v] == 0){
                    // グラフから, 辺を削除.
                    OG[u].erase(v);
                    
                    // bfs.
                    int duv[N];
                    rep(i, N) duv[i] = 0;
                    bfs(OG, 0, duv);
                    
                    // 探索結果を保存.
                    memo[u][v] = duv[N - 1] ? duv[N - 1] : -1;
                    
                    // グラフに, 辺を戻す.
                    OG[u].insert(v);
                    
                    // 出力.
                    printf("%d\n", memo[u][v]);
                }
            }
        }
    }
    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

128

129

130

131

132

133

// 解き直し.

// https://atcoder.jp/contests/abc218/editorial/2606

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using P = pair<int, int>;

using vs = vector<set<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 pb push_back

#define a first

#define b second

int info[404][404]; // 最短経路を構成する辺情報.

int memo[404][404]; // 最短経路上の辺情報.

int main(){

// 1. 入力情報.

int N, M;

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

vs OG(N), RG(N);

vp edges;

rep(i, M){

int s, t;

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

s--, t--;

OG[s].insert(t); // 有向グラフ.

RG[t].insert(s); // 有向グラフ(逆向き).

edges.pb({s, t}); // 有向辺.

}

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

}

return;

};

// 3. 最短距離(グラフの有向辺が, 全てそろっている場合).

int d[N];

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

bfs(OG, 0, d);

// 4. 最短経路を取得.

// -> 到達可能な場合に, 最短経路を取得(ゴールから逆算).

auto f = [&](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]){

// 距離が 1 小さい場合に, 最短経路として保存.

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

info[e][u]++;

q.push(e);

break;

}

return;

};

int D = d[N - 1];

if(D) f(RG, N - 1, d);

// 5. クエリ回答.

for(auto &e : edges){

// 辺情報.

int u = e.a; // 始点.

int v = e.b; // 終点.

// 到達不可能な場合.

if(!D) puts("-1");

// 到達可能な場合.

if(D){

// 辺(u, v) が, 最短経路上に無い場合.

if(!info[u][v]) printf("%d\n", D);

// 辺(u, v) が, 最短経路上に有る場合.

if(info[u][v]){

// 探索済みの場合.

if(memo[u][v] != 0) printf("%d\n", memo[u][v]);

// 探索済みでない場合.

if(memo[u][v] == 0){

// グラフから, 辺を削除.

OG[u].erase(v);

// bfs.

int duv[N];

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

bfs(OG, 0, duv);

// 探索結果を保存.

memo[u][v] = duv[N - 1] ? duv[N - 1] : -1;

// グラフに, 辺を戻す.

OG[u].insert(v);

// 出力.

printf("%d\n", memo[u][v]);

}

return 0;

}

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

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

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

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

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

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

[入力例]
4 1
1 2

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

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

[出力例]
-1
-1
-1

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

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

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

[出力例]
7
5
5
8
5
5
5
5
-1
5
5
6
5
5
5
7
5
5
5
5
5
5
5
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

[入力例]

3 3

1 2

1 3

2 3

[出力例]

※AtCoderテストケースより

[入力例]

4 4

1 2

2 3

2 4

3 4

[出力例]

-1

※AtCoderテストケースより

[入力例]

5 10

1 2

1 4

1 5

2 1

2 3

3 1

3 2

3 5

4 2

4 3

[出力例]

※AtCoderテストケースより

[入力例]

4 1

1 2

[出力例]

-1

※AtCoderテストケースより

[入力例]

5 3

1 2

3 4

3 5

[出力例]

-1

[入力例]

7 9

1 3

3 4

1 4

4 2

7 4

2 5

5 6

6 7

2 7

[出力例]

-1

[入力例]

18 24

1 2

1 3

3 6

2 5

6 2

6 7

7 4

4 5

5 8

8 4

8 9

8 10

9 10

10 11

10 17

10 18

10 12

12 15

12 13

12 14

13 14

14 16

13 18

18 14

[出力例]

-1

■参照サイト
AtCoder Beginner Contest 218

2021年9月16日

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

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

■感想.
1. 問題E は, 方針が見えなかったので, 解説を参考に実装したところ, AC版に到達出来た.
2. 個人的には, 解説にあるように, 最小全域木(Kruskal’s Algorithm) の性質を使って, 最終的に, 数式まで落とし込んでいくロジックが, 非常に面白いと感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/abc210/editorial/2299
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using P = pair<LL, LL>;
using vp = vector<P>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
#define all(x) x.begin(), x.end()
#define a first
#define b second

int main(){
    
    // 1. 入力情報.
    int M;
    LL N;
    scanf("%lld %d", &N, &M);
    vp v;
    rep(i, M){
        LL a, c;
        scanf("%lld %lld", &a, &c);
        v.pb({c, a});
    }
    
    // 2. sort.
    // -> 解説にある通り, 最小全域木(Kruskal's Algorithm) を ベースに考えるため必要.
    sort(all(v));
    
    // 3. コストの最小値は？
    LL ans = 0, bef = N, cur;
    for(auto &p : v){
        // 今回分更新.
        cur = __gcd(bef, p.b);
        
        // 集計.
        ans += p.a * (bef - cur);
        
        // 前回分更新.
        bef = cur;
    }
    
    // 4. 全域木が無い場合.
    if(cur > 1) ans = -1;
    
    // 5. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc210/editorial/2299

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using P = pair<LL, LL>;

using vp = vector;

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

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

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

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

#define pb push_back

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

#define a first

#define b second

int main(){

// 1. 入力情報.

int M;

LL N;

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

vp v;

rep(i, M){

LL a, c;

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

v.pb({c, a});

}

// 2. sort.

// -> 解説にある通り, 最小全域木(Kruskal's Algorithm) をベースに考えるため必要.

sort(all(v));

// 3. コストの最小値は？

LL ans = 0, bef = N, cur;

for(auto &p : v){

// 今回分更新.

cur = __gcd(bef, p.b);

// 集計.

ans += p.a * (bef - cur);

// 前回分更新.

bef = cur;

}

// 4. 全域木が無い場合.

if(cur > 1) ans = -1;

// 5. 出力.

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

return 0;

}

[入力例]
4 2
2 3
3 5

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

[入力例]
6 1
3 4

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

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

[出力例]
-1

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

[出力例]
9

[入力例]
32 10
12 5
16 1
22 13
31 10
1 7
19 3
21 8
3 17
17 5
26 10

[出力例]
61

[入力例]
33333 22
19002 32181
25701 58593
18097 46854
383 94737
14074 64088
5079 170351
17624 152448
21230 18133
1601 73981
31329 28493
22453 10214
3365 132535
9035 127417
28030 170783
14237 68665
13917 179105
21643 104707
6672 65054
30083 196465
31715 98708
19864 154275
25748 53992

[出力例]
340453048

[入力例]

4 2

2 3

3 5

[出力例]

※AtCoderテストケースより

[入力例]

6 1

3 4

[出力例]

-1

※AtCoderテストケースより

[入力例]

8 3

2 1

4 2

6 3

[出力例]

-1

[入力例]

10 9

1 9

2 8

3 7

4 6

5 5

6 4

7 3

8 2

9 1

[出力例]

[入力例]

32 10

12 5

16 1

22 13

31 10

1 7

19 3

21 8

3 17

17 5

26 10

[出力例]

[入力例]

33333 22

19002 32181

25701 58593

18097 46854

383 94737

14074 64088

5079 170351

17624 152448

21230 18133

1601 73981

31329 28493

22453 10214

3365 132535

9035 127417

28030 170783

14237 68665

13917 179105

21643 104707

6672 65054

30083 196465

31715 98708

19864 154275

25748 53992

[出力例]

340453048

■参照サイト
AtCoder Beginner Contest 210

C++の練習を兼ねて, AtCoder Beginner Contest 220 の 問題C (Long Sequence) ～ 問題D (FG operation) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 219 の 問題G (Propagation) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 217 の 問題G (Groups) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 126 の 問題A (Make 10) ～ 問題B (Cross-free Matching) を解いてみた.

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

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

C++の練習を兼ねて, AtCoder Beginner Contest 219 の 問題C (Neo-lexicographic Ordering) ～ 問題D (Strange Lunchbox) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 218 の 問題G (Game on Tree 2) を解いてみた.

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

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

C++の練習を兼ねて, AtCoder Beginner Contest 220 の問題C (Long Sequence) ～問題D (FG operation) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 219 の問題G (Propagation) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 217 の問題G (Groups) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 126 の問題A (Make 10) ～問題B (Cross-free Matching) を解いてみた.

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

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

C++の練習を兼ねて, AtCoder Beginner Contest 219 の問題C (Neo-lexicographic Ordering) ～問題D (Strange Lunchbox) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 218 の問題G (Game on Tree 2) を解いてみた.

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

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