C++ | 個人用メモ帳

2023年1月1日

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

C++の練習を兼ねて, AtCoder Regular Contest 117 の問題D (Miracle Tree) を解いてみた.

■感想.
1. 問題D は, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 幅優先探索および, 深さ優先探索(応用版, 行きがけ順および特定の頂点に対する探索順序変更) を学習が出来たので, 非常に, 良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

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

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    vvi G(N);
    rep(i, N - 1){
        int a, b;
        scanf("%d %d", &a, &b);
        --a;
        --b;
        G[a].pb(b);
        G[b].pb(a);
    }
    
    // 2. bfs.
    // https://ja.wikipedia.org/wiki/幅優先探索
    auto bfs = [&](vvi &G, int s, int* d) {
        // 空のキュー.
        queue<int> q;
        
        // 探索地点 s をキュー q に追加.
        q.push(s);
        while(!q.empty()){
            // キューから取り出す.
            int u = q.front();
            q.pop();
            
            // 隣接頂点をチェック.
            for(auto &e : G[u]) if(!d[e] && e != s) d[e] = d[u] + 1, q.push(e);
        }
    };
    
    // 3. 直径となる 頂点 (u, v) は？
    // 3-1. 頂点 1 から 各頂点までの距離.
    int d[N], du[N], dv[N];
    rep(i, N) d[i] = du[i] = dv[i] = 0;
    bfs(G, 0, d);
    
    // 3-2. 頂点 1 から 最も遠い 頂点 u.
    int u = -1, D = 0;
    rep(i, N){
        if(D < d[i]){
            D = max(D, d[i]);
            u = i;
        }
    }
    assert(u != -1);
    
    // 3-3. 頂点 u から 各頂点までの距離.
    bfs(G, u, du);
    
    // 3-4. 頂点 u から 最も遠い 頂点 v.
    int v = -1;
    D = 0;
    rep(i, N){
        if(D < du[i]){
            D = max(D, du[i]);
            v = i;
        }
    }
    assert(v != -1);
    
    // 4. 頂点 u から 頂点 v までの 経路.
    // -> 頂点 v から, 頂点 u に 向かって, 経路上 の 頂点 を 保存.
    auto f = [&](vvi &G, int g, int* d){
        // 空のキュー.
        queue<int> q;
        
        // 探索開始地点.
        ++route[g];
        
        // 探索地点 g をキュー q に追加.
        q.push(g);
        while(!q.empty()){
            // キューから取り出す.
            int u = q.front();
            q.pop();
            
            // 隣接頂点をチェック.
            for(auto &e : G[u]){
                if(d[e] == d[u] - 1){
                    // 距離が 1 小さい頂点を追加.
                    q.push(e);
                    
                    // 最短経路を構成する頂点とみて, カウントアップ.
                    ++route[e];
                }
            }
        }
    };
    f(G, v, du);
    
    // 5. dfs.
    // https://ja.wikipedia.org/wiki/深さ優先探索
    int idx = 0;
    auto dfs = [&](auto&& self, int c) -> void {
        // 訪問済フラグ設定.
        ans[c] = ++idx;
        
        // 隣接頂点.
        vp ns;
        for(auto &n : G[c]) if(!ans[n]) ns.pb({route[n], n});
        
        // sort.
        // -> 頂点 v を, 最後に探索するように調整.
        sort(all(ns));
        
        // 次へ.
        for(auto &n : ns) self(self, n.b);
        
        // 訪問順更新.
        ++idx;
    };
    dfs(dfs, u);
    
    // 6. 出力.
    rep(i, N) printf("%d%s", ans[i], (i < N - 1) ? " " : "\n");
    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

// 解き直し.

// https://atcoder.jp/contests/arc117/editorial/1129

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

using vvi = vector<vi>;

using P = pair<int, int>;

using vp = vector<P>;

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

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

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

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

#define pb push_back

#define a first

#define b second

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

int route[202020], ans[202020];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

vvi G(N);

rep(i, N - 1){

int a, b;

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

--a;

--b;

G[a].pb(b);

G[b].pb(a);

}

// 2. bfs.

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

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

// 空のキュー.

queue<int> q;

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

q.push(s);

while(!q.empty()){

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

int u = q.front();

q.pop();

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

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

}

};

// 3. 直径となる頂点 (u, v) は？

// 3-1. 頂点 1 から各頂点までの距離.

int d[N], du[N], dv[N];

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

bfs(G, 0, d);

// 3-2. 頂点 1 から最も遠い頂点 u.

int u = -1, D = 0;

rep(i, N){

if(D < d[i]){

D = max(D, d[i]);

u = i;

}

assert(u != -1);

// 3-3. 頂点 u から各頂点までの距離.

bfs(G, u, du);

// 3-4. 頂点 u から最も遠い頂点 v.

int v = -1;

D = 0;

rep(i, N){

if(D < du[i]){

D = max(D, du[i]);

v = i;

}

assert(v != -1);

// 4. 頂点 u から頂点 v までの経路.

// -> 頂点 v から, 頂点 u に向かって, 経路上の頂点を保存.

auto f = [&](vvi &G, int g, int* d){

// 空のキュー.

queue<int> q;

// 探索開始地点.

++route[g];

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

q.push(g);

while(!q.empty()){

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

int u = q.front();

q.pop();

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

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

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

// 距離が 1 小さい頂点を追加.

q.push(e);

// 最短経路を構成する頂点とみて, カウントアップ.

++route[e];

}

};

f(G, v, du);

// 5. dfs.

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

int idx = 0;

auto dfs = [&](auto&& self, int c) -> void {

// 訪問済フラグ設定.

ans[c] = ++idx;

// 隣接頂点.

vp ns;

for(auto &n : G[c]) if(!ans[n]) ns.pb({route[n], n});

// sort.

// -> 頂点 v を, 最後に探索するように調整.

sort(all(ns));

// 次へ.

for(auto &n : ns) self(self, n.b);

// 訪問順更新.

++idx;

};

dfs(dfs, u);

// 6. 出力.

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

return 0;

}

[入力例]
2
1 2

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

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

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

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

[出力例]
13 12 11 19 8 7 2 9 22 20 14 16 1 3 5

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

[出力例]
25 9 5 2 1 3 28 26 16 8 6 31 29 10 11 13 17 18 20 32 34 35 38 36 21

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

[出力例]
43 34 23 2 7 1 49 46 35 37 38 40 16 17 18 20 8 10 25 15 24 27 28 30 3 5 12 13 47 44

100

101

102

[入力例]

1 2

[出力例]

2 1

※AtCoderのテストケースより

[入力例]

1 2

1 4

2 3

[出力例]

3 2 1 4

※AtCoderのテストケースより

[入力例]

1 2

1 11

1 12

2 3

2 4

3 5

4 9

4 10

5 6

5 8

6 7

7 13

7 14

7 15

[出力例]

13 12 11 19 8 7 2 9 22 20 14 16 1 3 5

[入力例]

1 7

1 8

1 9

2 9

2 10

2 14

3 4

3 10

3 11

4 5

4 6

7 12

7 13

9 17

12 20

12 21

14 15

14 16

17 18

17 19

19 25

21 22

22 23

22 24

[出力例]

25 9 5 2 1 3 28 26 16 8 6 31 29 10 11 13 17 18 20 32 34 35 38 36 21

[入力例]

1 2

1 8

1 30

2 3

2 9

2 10

3 13

3 21

4 5

4 6

4 25

4 26

5 17

5 18

5 27

7 8

8 29

10 11

10 12

13 14

13 20

14 15

14 16

19 21

20 27

21 22

22 23

22 24

27 28

[出力例]

43 34 23 2 7 1 49 46 35 37 38 40 16 17 18 20 8 10 25 15 24 27 28 30 3 5 12 13 47 44

■参照サイト
AtCoder Regular Contest 117

2022年12月30日

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

C++の練習を兼ねて, 第１１回アルゴリズム実技検定過去問の問題H (2つのナップサック) を解いてみた.

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

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

■C++版プログラム(問題H／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 INF = 202020202020202020;
int w[101], v[101];
LL dp[2][303][303];

int main(){
    
    // 1. 入力情報.
    int N, A, B;
    scanf("%d %d %d", &N, &A, &B);
    rep(i, N) scanf("%d %d", &w[i + 1], &v[i + 1]);
    
    // 2. 初期化.
    rep(i, 2) rep(j, 303) rep(k, 303) dp[i][j][k] = -INF;
    dp[0][0][0] = 0;
    
    // 3. dp更新.
    repx(i, 1, N + 1){
        // 今回分(初期化).
        rep(j, 303) rep(k, 303) dp[1][j][k] = dp[0][j][k];
        
        // 今回分更新.
        repr(j, A, 0){
            repr(k, B, 0){
                if(dp[0][j][k] >= 0){
                    // 一つ目のナップサック.
                    if(w[i] + j <= A){
                        dp[1][w[i] + j][k] = max(dp[1][w[i] + j][k], dp[0][j][k] + (LL)v[i]);
                    }
                    
                    // 二つ目のナップサック.
                    if(w[i] + k <= B){
                        dp[1][j][w[i] + k] = max(dp[1][j][w[i] + k], dp[0][j][k] + (LL)v[i]);
                    }
                }
            }
        }
        
        // 前回分(保存).
        rep(j, 303) rep(k, 303) dp[0][j][k] = dp[1][j][k];
    }
    
    // 4. お菓子の美味しさの合計としてありうる最大値は？
    LL ans = 0;
    rep(j, A + 1) rep(k, B + 1) ans = max(ans, dp[1][j][k]);
    
    // 5. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

const LL INF = 202020202020202020;

int w[101], v[101];

LL dp[2][303][303];

int main(){

// 1. 入力情報.

int N, A, B;

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

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

// 2. 初期化.

rep(i, 2) rep(j, 303) rep(k, 303) dp[i][j][k] = -INF;

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

// 3. dp更新.

repx(i, 1, N + 1){

// 今回分(初期化).

rep(j, 303) rep(k, 303) dp[1][j][k] = dp[0][j][k];

// 今回分更新.

repr(j, A, 0){

repr(k, B, 0){

if(dp[0][j][k] >= 0){

// 一つ目のナップサック.

if(w[i] + j <= A){

dp[1][w[i] + j][k] = max(dp[1][w[i] + j][k], dp[0][j][k] + (LL)v[i]);

}

// 二つ目のナップサック.

if(w[i] + k <= B){

dp[1][j][w[i] + k] = max(dp[1][j][w[i] + k], dp[0][j][k] + (LL)v[i]);

}

// 前回分(保存).

rep(j, 303) rep(k, 303) dp[0][j][k] = dp[1][j][k];

}

// 4. お菓子の美味しさの合計としてありうる最大値は？

LL ans = 0;

rep(j, A + 1) rep(k, B + 1) ans = max(ans, dp[1][j][k]);

// 5. 出力.

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

return 0;

}

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

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

[入力例]
20 70 60
7 94
18 33
14 26
10 1
9 57
2 80
19 74
16 10
15 18
10 38
13 90
12 23
3 3
8 11
18 10
3 42
3 66
3 90
10 2
5 45

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

[入力例]
7 8 10
3 7
8 1
9 15
10 15
2 7
7 1
3 15

[出力例]
44

[入力例]
15 20 22
7 7
9 1
8 15
1 15
7 50
9 37
6 23
8 21
2 11
5 19
8 11
2 13
10 20
8 32
1 22

[出力例]
222

[入力例]
30 256 234
76 53
70 169
77 330
42 23
42 263
14 155
38 198
58 203
13 50
43 153
10 103
13 103
80 110
59 277
67 150
21 59
27 123
22 131
56 203
58 260
16 211
12 199
33 274
45 268
44 287
1 80
11 9
64 185
13 248
73 76

[出力例]
3333

[入力例]
50 300 300
15 20022
38 18592
4 5470
1 2926
19 2156
13 2548
42 30859
34 31505
50 1414
38 32713
9 16687
15 23146
19 24343
6 19052
9 30208
10 33332
7 2013
27 28004
8 13704
10 2819
48 10548
43 20648
19 11678
47 23502
6 25309
31 29272
35 30446
2 2392
19 28872
47 3897
29 30287
24 667
37 2891
34 21064
25 15530
5 11073
5 22751
2 8789
27 2078
46 18138
43 16273
25 3429
13 16627
15 31875
34 31875
6 29727
4 37547
6 633
21 23994
10 33196

[出力例]
777777

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

[入力例]

6 8 9

2 6

4 1

5 9

3 1

5 3

5 8

[出力例]

※AtCoderテストケースより

[入力例]

20 70 60

7 94

18 33

14 26

10 1

9 57

2 80

19 74

16 10

15 18

10 38

13 90

12 23

3 3

8 11

18 10

3 42

3 66

3 90

10 2

5 45

[出力例]

772

※AtCoderテストケースより

[入力例]

7 8 10

3 7

8 1

9 15

10 15

2 7

7 1

3 15

[出力例]

[入力例]

15 20 22

7 7

9 1

8 15

1 15

7 50

9 37

6 23

8 21

2 11

5 19

8 11

2 13

10 20

8 32

1 22

[出力例]

222

[入力例]

30 256 234

76 53

70 169

77 330

42 23

42 263

14 155

38 198

58 203

13 50

43 153

10 103

13 103

80 110

59 277

67 150

21 59

27 123

22 131

56 203

58 260

16 211

12 199

33 274

45 268

44 287

1 80

11 9

64 185

13 248

73 76

[出力例]

3333

[入力例]

50 300 300

15 20022

38 18592

4 5470

1 2926

19 2156

13 2548

42 30859

34 31505

50 1414

38 32713

9 16687

15 23146

19 24343

6 19052

9 30208

10 33332

7 2013

27 28004

8 13704

10 2819

48 10548

43 20648

19 11678

47 23502

6 25309

31 29272

35 30446

2 2392

19 28872

47 3897

29 30287

24 667

37 2891

34 21064

25 15530

5 11073

5 22751

2 8789

27 2078

46 18138

43 16273

25 3429

13 16627

15 31875

34 31875

6 29727

4 37547

6 633

21 23994

10 33196

[出力例]

777777

■参照サイト
第１１回アルゴリズム実技検定過去問

2022年12月30日

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

C++の練習を兼ねて, 第１１回アルゴリズム実技検定過去問の問題F (シューティングゲーム) ～問題G (木の判定) を解いてみた.

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

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

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

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

int main(){
    
    // 1. 入力情報.
    int H, W;
    scanf("%d %d", &H, &W);
    rep(i, H) rep(j, W) scanf("%d", &s[i][j]);
    
    // 2. 操作.
    int N;
    scanf("%d", &N);
    rep(i, N){
        // 2-1. シューティング対象のマス.
        int r, c;
        scanf("%d %d", &r, &c);
        --r;
        --c;
        
        // 2-2. 空の場合.
        if(!s[r][c]) continue;
        
        // 2-3. 空でない場合.
        repr(i, r, 1) s[i][c] = s[i - 1][c];
        s[0][c] = 0;
    }
    
    // 3. 出力.
    rep(i, H) rep(j, W) printf("%d%s", s[i][j], (j < W - 1) ? " " : "\n");
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

int s[101][101];

int main(){

// 1. 入力情報.

int H, W;

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

rep(i, H) rep(j, W) scanf("%d", &s[i][j]);

// 2. 操作.

int N;

scanf("%d", &N);

rep(i, N){

// 2-1. シューティング対象のマス.

int r, c;

scanf("%d %d", &r, &c);

--r;

--c;

// 2-2. 空の場合.

if(!s[r][c]) continue;

// 2-3. 空でない場合.

repr(i, r, 1) s[i][c] = s[i - 1][c];

s[0][c] = 0;

}

// 3. 出力.

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

return 0;

}

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

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

[入力例]
1 1
1
1
1 1

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

[入力例]
2 3
18459 0 35959
150312 573935 612940
3
2 3
1 2
1 1

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

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

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

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

[出力例]
0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 9 0 0 99 0 0 0 0 0 0 0
0 98 33 0 49 69 0 17 0 52 0 2 0
0 80 57 62 68 4 0 28 80 36 77 9 0
0 21 40 70 88 73 76 68 31 98 97 21 0
0 33 34 30 34 28 48 87 93 100 61 9 0
71 40 79 26 3 89 22 57 86 36 56 55 0
23 67 24 54 9 14 69 75 41 28 72 15 0
62 51 87 29 2 26 45 23 99 67 72 57 3
1 2 8 59 53 93 74 48 65 4 45 86 83

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

[入力例]

3 3

0 1 0

1 2 0

3 4 4

3 2

[出力例]

0 0 0

1 1 0

3 2 4

※AtCoderテストケースより

[入力例]

1 1

[出力例]

※AtCoderテストケースより

[入力例]

2 3

18459 0 35959

150312 573935 612940

2 3

1 2

1 1

[出力例]

0 0 0

150312 573935 35959

※AtCoderテストケースより

[入力例]

7 5

0 1 0 2 0

3 10 4 1 9

7 4 9 5 8

9 5 9 4 3

8 9 7 9 5

2 10 1 10 4

5 5 10 1 6

1 3

7 3

2 1

1 3

3 4

5 5

7 4

5 1

4 4

6 1

4 1

6 1

4 5

5 2

4 3

[出力例]

0 0 0 0 0

0 1 0 0 0

0 10 0 0 0

0 4 4 2 9

0 5 9 4 3

7 10 7 9 4

5 5 1 10 6

[入力例]

11 13

71 0 9 0 0 99 0 94 0 52 23 0 0

40 3 33 0 98 69 0 17 0 36 93 0 31

23 98 15 62 49 4 0 41 80 98 77 31 80

35 84 57 70 68 73 76 28 58 2 97 2 42

15 80 40 30 88 28 8 68 31 100 61 9 29

62 21 34 79 34 89 48 87 93 36 56 21 18

1 33 79 26 60 32 22 57 86 28 72 9 24

19 40 24 54 3 14 69 75 41 71 31 55 95

23 67 71 1 9 26 45 23 56 66 72 15 67

84 51 87 29 2 93 74 27 99 67 45 57 3

40 2 8 59 53 62 47 48 65 4 100 86 83

3 8

2 13

8 1

10 8

6 1

2 11

1 1

3 13

7 13

4 2

2 11

11 7

6 7

9 9

11 6

9 10

2 5

3 2

7 13

11 11

3 12

3 3

4 1

3 12

7 13

10 1

7 1

9 10

3 8

7 13

8 13

7 5

1 4

9 11

2 7

1 9

2 11

6 10

7 13

2 5

1 11

9 3

11 1

9 4

3 12

5 9

9 13

11 1

7 4

8 6

[出力例]

0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 9 0 0 99 0 0 0 0 0 0 0

0 98 33 0 49 69 0 17 0 52 0 2 0

0 80 57 62 68 4 0 28 80 36 77 9 0

0 21 40 70 88 73 76 68 31 98 97 21 0

0 33 34 30 34 28 48 87 93 100 61 9 0

71 40 79 26 3 89 22 57 86 36 56 55 0

23 67 24 54 9 14 69 75 41 28 72 15 0

62 51 87 29 2 26 45 23 99 67 72 57 3

1 2 8 59 53 93 74 48 65 4 45 86 83

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

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

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    vvi G(N);
    rep(i, N - 1){
        int a, b;
        scanf("%d %d", &a, &b);
        --a;
        --b;
        G[a].pb(b);
        G[b].pb(a);
    }    
    
    // 2. bfs.
    // https://ja.wikipedia.org/wiki/幅優先探索
    auto bfs = [&](vvi &G, int s, int* c, int l){
        // 空のキュー.
        queue<int> q;
        
        // 連結成分番号を設定.
        c[s] = l;
        
        // 探索地点 s をキュー q に追加.
        q.push(s);
        while(!q.empty()){
            // キューから取り出す.
            int u = q.front();
            q.pop();
            
            // 取り出した要素を処理.
            for(auto &e : G[u]) if(!c[e] && e != s) c[e] = l, q.push(e);
        }
    };
    int c[N], idx = 0;
    rep(i, N) c[i] = 0;
    rep(i, N) if(!c[i]) bfs(G, i, c, ++idx);
    
    // 3. 出力.
    printf("%s\n", (idx == 1) ? "Yes" : "No");
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

using vvi = vector<vi>;

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

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

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

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

#define pb push_back

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

vvi G(N);

rep(i, N - 1){

int a, b;

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

--a;

--b;

G[a].pb(b);

G[b].pb(a);

}

// 2. bfs.

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

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

// 空のキュー.

queue<int> q;

// 連結成分番号を設定.

c[s] = l;

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

q.push(s);

while(!q.empty()){

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

int u = q.front();

q.pop();

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

for(auto &e : G[u]) if(!c[e] && e != s) c[e] = l, q.push(e);

}

};

int c[N], idx = 0;

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

rep(i, N) if(!c[i]) bfs(G, i, c, ++idx);

// 3. 出力.

printf("%s\n", (idx == 1) ? "Yes" : "No");

return 0;

}

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

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

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

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

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

[出力例]
Yes

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

[出力例]
No

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

[出力例]
No

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

[出力例]
Yes

[入力例]

1 3

3 4

2 3

[出力例]

Yes

※AtCoderテストケースより

[入力例]

1 2

2 3

1 3

[出力例]

※AtCoderテストケースより

[入力例]

1 2

2 3

3 4

4 5

[出力例]

Yes

[入力例]

1 2

1 3

2 3

4 5

5 6

6 7

[出力例]

[入力例]

1 2

3 4

3 5

4 5

6 7

6 8

7 9

8 9

10 11

10 12

11 12

[出力例]

[入力例]

1 2

1 4

2 3

2 5

2 9

3 6

3 7

4 8

5 10

5 11

6 14

6 15

11 12

11 13

[出力例]

Yes

■参照サイト
第１１回アルゴリズム実技検定過去問

2022年12月29日

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

C++の練習を兼ねて, 第１１回アルゴリズム実技検定過去問の問題E (変わった数列) を解いてみた.

■感想.
1. 問題Eは, 方針を絞り込むことが出来たので, AC版に到達できたと思う.
2. 個人的には, 問題E で, sqrt関数を使うと, 期待した結果が得られないパターンを確認出来たので, 勉強になった.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

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

int main(){
    
    // 1. 入力情報.
    LL N;
    scanf("%lld", &N);
    
    // 2. 例外.
    if(N <= 3){
        int ans[3] = {1, 2, 1};
        printf("%d\n", ans[(int)N - 1]);
        return 0;
    }
    
    // 3. 二乗して, N に近い整数は？
    // ex,
    // N = 999999999999999999
    // -> (LL)sqrt(N) は, 999999999 が期待される値であるが, 1000000003 が 出力され, 
    //    正しく計算できなかったため, 廃止.
    LL n = 0;
    rep(i, 1000000001){
        if((LL)i * (LL)i <= N) n = (LL)i;
        else                   break;
    }
    
    // 4. 例外.
    if(n * n == N){
        printf("%lld\n", n);
        return 0;
    }
    
    // 5. 出力.
    printf("%lld\n", max((n + 1) + 1 - (N - n * n), (N - n * n) - n));
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

int main(){

// 1. 入力情報.

LL N;

scanf("%lld", &N);

// 2. 例外.

if(N <= 3){

int ans[3] = {1, 2, 1};

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

return 0;

}

// 3. 二乗して, N に近い整数は？

// ex,

// N = 999999999999999999

// -> (LL)sqrt(N) は, 999999999 が期待される値であるが, 1000000003 が出力され,

// 正しく計算できなかったため, 廃止.

LL n = 0;

rep(i, 1000000001){

if((LL)i * (LL)i <= N) n = (LL)i;

else break;

}

// 4. 例外.

if(n * n == N){

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

return 0;

}

// 5. 出力.

printf("%lld\n", max((n + 1) + 1 - (N - n * n), (N - n * n) - n));

return 0;

}

[入力例]
10

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

[入力例]
1

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

[入力例]
123456789012345678

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

[入力例]
30

[出力例]
2

[入力例]
55

[出力例]
3

[入力例]
20220604

[出力例]
2092

[入力例]
202212301230

[出力例]
250852

[入力例]
999999999999999999

[出力例]
999999999

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

123456789012345678

[出力例]

268452372

※AtCoderテストケースより

[入力例]

[出力例]

[入力例]

[出力例]

[入力例]

20220604

[出力例]

2092

[入力例]

202212301230

[出力例]

250852

[入力例]

999999999999999999

[出力例]

999999999

■参照サイト
第１１回アルゴリズム実技検定過去問

2022年12月29日

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

C++の練習を兼ねて, 第１１回アルゴリズム実技検定過去問の問題D (似ている文字列) を解いてみた.

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

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

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

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

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    vvi G(26);
    rep(i, N){
        char a[11], b[11];
        scanf("%s %s", a, b);
        G[a[0] - 'a'].pb(b[0] - 'a');
        G[b[0] - 'a'].pb(a[0] - 'a');
    }
    char s[222], t[222];
    scanf("%s %s", s, t);
    string S(s), T(t);
    
    // 2. bfs.
    // https://ja.wikipedia.org/wiki/幅優先探索
    auto bfs = [&](vvi &G, int s, int* c, int l){
        // 空のキュー.
        queue<int> q;
        
        // 連結成分番号を設定.
        c[s] = l;
        
        // 探索地点 s をキュー q に追加.
        q.push(s);
        while(!q.empty()){
            // キューから取り出す.
            int u = q.front();
            q.pop();
            
            // 取り出した要素を処理.
            for(auto &e : G[u]) if(!c[e] && e != s) c[e] = l, q.push(e);
        }
    };
    int c[26], n = 0;
    rep(i, 26) c[i] = 0;
    rep(i, 26) if(!c[i]) bfs(G, i, c, ++n);
    
    // 3. 文字列 S, T を 操作.
    vi vs, vt;
    rep(i, S.size()) vs.pb(c[S[i] - 'a']);
    rep(i, T.size()) vt.pb(c[T[i] - 'a']);
    
    // 4. 出力.
    printf("%s\n", (vs == vt) ? "Yes" : "No");
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

using vvi = vector<vi>;

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

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

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

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

#define pb push_back

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

vvi G(26);

rep(i, N){

char a[11], b[11];

scanf("%s %s", a, b);

G[a[0] - 'a'].pb(b[0] - 'a');

G[b[0] - 'a'].pb(a[0] - 'a');

}

char s[222], t[222];

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

string S(s), T(t);

// 2. bfs.

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

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

// 空のキュー.

queue<int> q;

// 連結成分番号を設定.

c[s] = l;

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

q.push(s);

while(!q.empty()){

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

int u = q.front();

q.pop();

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

for(auto &e : G[u]) if(!c[e] && e != s) c[e] = l, q.push(e);

}

};

int c[26], n = 0;

rep(i, 26) c[i] = 0;

rep(i, 26) if(!c[i]) bfs(G, i, c, ++n);

// 3. 文字列 S, T を操作.

vi vs, vt;

rep(i, S.size()) vs.pb(c[S[i] - 'a']);

rep(i, T.size()) vt.pb(c[T[i] - 'a']);

// 4. 出力.

printf("%s\n", (vs == vt) ? "Yes" : "No");

return 0;

}

[入力例]
1
m n
man
nan

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

[入力例]
1
m n
man
men

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

[入力例]
3
a b
a e
d e
abc
edc

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

[入力例]
1
a b
xyz
xyz

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

[入力例]
15
t z
o y
k n
f i
n w
p r
c m
q w
c q
h r
d y
o p
j w
j p
a k
pqrst
vwxyz

[出力例]
No

[入力例]
10
b e
i l
b p
f q
a b
u n
e y
p r
i p
a q
blueberry
pineapple

[出力例]
Yes

[入力例]

m n

man

nan

[出力例]

Yes

※AtCoderテストケースより

[入力例]

m n

man

men

[出力例]

※AtCoderテストケースより

[入力例]

a b

a e

d e

abc

edc

[出力例]

Yes

※AtCoderテストケースより

[入力例]

a b

xyz

[出力例]

Yes

※AtCoderテストケースより

[入力例]

t z

o y

k n

f i

n w

p r

c m

q w

c q

h r

d y

o p

j w

j p

a k

pqrst

vwxyz

[出力例]

[入力例]

b e

i l

b p

f q

a b

u n

e y

p r

i p

a q

blueberry

pineapple

[出力例]

Yes

■参照サイト
第１１回アルゴリズム実技検定過去問

2022年12月28日

■感想.
1. 問題D は, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 過去問 AtCoder Beginner Contest 187 (F – Close Group) をベースにして, 部分集合を考える方針で実装してみたものの, 実行時間(3304[ms])が, かなり大きかったため, 改善の余地があると思われる(今後の課題として持っておく).
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/arc137/editorial/3589
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
int a[1010101], ans[2020202];

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    rep(i, N) scanf("%d", &a[i]);
    
    // 2. S を 計算.
    int S = 1;
    while(S < max(N, M)) S <<= 1;
    
    // 3. 操作(k = 1).
    rep(i, N) ans[1] ^= a[i];
    
    // 4. 操作(k >= 2).
    // 過去問参照(AtCoder Beginner Contest 187 F - Close Group).
    // https://atcoder.jp/contests/abc187/editorial/488
    // https://atcoder.jp/contests/abc187/submissions/19205798
    // -> 部分集合 s と k が 同じケースを含めるため, 一部改変(for(int j = i; --j &= i; ) の 部分).
    repx(s, S - N, S){
        for(int k = s; k &= s; k--) ans[k + 1] ^= a[s - (S - N)];
    }
    
    // 5. 出力.
    rep(i, M) printf("%d%s", ans[i + 1], (i < M - 1) ? " " : "\n");
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc137/editorial/3589

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

int a[1010101], ans[2020202];

int main(){

// 1. 入力情報.

int N, M;

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

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

// 2. S を計算.

int S = 1;

while(S < max(N, M)) S <<= 1;

// 3. 操作(k = 1).

rep(i, N) ans[1] ^= a[i];

// 4. 操作(k >= 2).

// 過去問参照(AtCoder Beginner Contest 187 F - Close Group).

// https://atcoder.jp/contests/abc187/editorial/488

// https://atcoder.jp/contests/abc187/submissions/19205798

// -> 部分集合 s と k が同じケースを含めるため, 一部改変(for(int j = i; --j &= i; ) の部分).

repx(s, S - N, S){

for(int k = s; k &= s; k--) ans[k + 1] ^= a[s - (S - N)];

}

// 5. 出力.

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

return 0;

}

[入力例]
3 2
2 1 3

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

[入力例]
10 12
721939838 337089195 171851101 1069204754 348295925 77134863 839878205 89360649 838712948 918594427

[出力例]
716176219 480674244 678890528 642764255 259091950 663009497 942498522 584528336 364872846 145822575 392655861 844652404
※AtCoderテストケースより

[入力例]
7 5
11 3 7 10 15 6 5

[出力例]
9 6 7 2 6

[入力例]
20 22
99 77 53 11 69 32 89 54 69 63 98 50 20 77 78 85 55 50 27 108

[出力例]
0 27 109 54 72 21 25 85 32 0 82 50 98 24 73 103 16 93 83 61 88 83

[入力例]
60 15
8777 9093 6326 6315 11000 255 2012 12073 8918 4632 6473 10990 6424 1056 7516 3298 3304 8068 11679 7925 3283 5221 11619 5543 2495 3726 2788 5819 12143 11972 2515 3206 3016 3480 7015 1289 11426 10165 6215 1691 6383 10122 11476 5358 9620 10670 7549 10238 10676 9753 10523 9550 5489 7369 4537 10089 5133 3226 6237 5026

[出力例]
195 11596 11044 8678 13857 15622 15729 7424 1043 14341 9216 8293 3120 3231 7229

[入力例]
200 33
11275 3642 4137 11368 2555 6684 9178 5024 3453 8405 9759 893 3978 5689 6340 6472 358 2841 8551 7063 4786 9449 6631 10328 6624 273 9829 10956 9124 9064 6961 4113 9959 6084 5672 4986 1535 1557 4477 2472 2829 1069 1785 2994 5626 1269 10313 9093 2077 1920 1743 8134 4278 11743 44 3622 7969 5541 12001 3507 8900 8644 12046 7774 4401 11788 12334 2465 7548 9325 7018 2929 10072 12324 8951 6873 3615 6420 2095 12269 2317 8060 2221 3367 1053 10228 10520 7489 6759 10237 7068 8301 9107 8057 7787 3485 7383 4084 10232 8473 12268 11485 3388 8087 1562 5746 8761 6006 9694 3563 6239 8170 7130 4453 5255 4538 7258 3946 4257 3951 11504 6351 4354 11100 1859 7657 5689 267 7933 8164 9685 6320 1543 3106 10000 5092 6330 10876 5083 9462 10786 10788 2512 8052 1636 865 4514 4658 3488 3662 6774 5402 11287 9231 10839 6295 6784 3847 9367 7625 9803 9939 8432 11193 11355 1480 5652 9301 2495 7218 12037 5290 7081 10560 222 8168 9109 7467 1156 10585 9951 2881 11846 11258 3622 2545 10211 11481 2943 7926 10715 8692 952 12264 11338 4168 6061 10759 4154 10647

[出力例]
16230 4952 6305 5306 9936 10659 10133 11978 6981 11476 2725 3380 10847 2443 3061 6776 5710 3327 319 711 2929 2229 6850 11820 16312 15790 6484 9251 8502 10140 5383 4296 417

[入力例]
1000 50
55230 13276 46032 90047 13897 93439 74663 51465 50284 121720 4960 87962 86688 81870 18237 12987 27161 55886 119063 101794 58878 22308 15083 10960 29886 41605 102721 76465 40366 64909 85182 4004 50717 111852 24292 73664 61001 15764 120557 12217 39672 6271 61819 113317 99235 67173 93274 83927 110029 114336 79652 83801 49034 3108 64819 121707 121878 40847 6089 37291 75364 77190 44808 64749 107878 44943 770 67832 35430 27583 59755 14387 76213 111313 81978 97649 11164 106543 97124 38124 3704 2173 39434 41935 39772 49544 118011 119396 112357 98769 29115 60794 1268 33166 78227 119947 73991 62279 38345 90904 46791 121889 98075 25787 121230 37518 95331 113032 122032 119945 123207 92614 7198 53342 95432 58666 15310 13090 42628 32006 114910 94534 60133 91137 5069 89628 10784 65808 42456 47341 77848 39112 55692 17007 14011 77391 53025 27611 43868 7781 100490 108816 21436 34199 73246 119125 115789 103830 19414 74638 65002 72147 32070 109048 43311 113909 88264 111918 62991 3086 55919 45484 100482 41887 74786 94663 10579 38233 20666 1844 77617 54457 752 49319 81871 57756 102943 91203 24768 105112 46862 116126 23389 4973 49793 114850 18522 58906 12048 5322 41531 3238 91453 66378 64237 45620 36435 1434 84890 12672 75365 17041 92542 21726 46258 26135 48950 110386 1974 121510 54984 12598 76692 108524 18002 113388 47603 76038 51450 21297 48722 14904 68287 81904 90787 88948 119474 90486 77949 85185 28844 43881 6263 122757 36287 120585 87454 70347 33461 43690 23994 114243 99525 79610 97266 45630 37347 53120 46950 106562 99495 18814 74672 27075 92025 120467 86390 90532 74717 22229 43248 95265 115538 121820 53200 97787 27316 105618 99360 78975 56769 70728 12721 89023 54539 39439 99930 35948 118375 70849 17399 88361 39231 39417 11994 15358 56215 17054 41478 73741 28509 54838 122170 64236 93508 59436 47486 31026 87234 76397 41387 34839 6478 50975 8441 104293 60008 32442 116938 116848 63963 111891 14148 120976 20090 18359 73385 104263 94357 123203 52651 11625 73203 17211 54949 16388 20724 10240 36847 80662 52280 81499 25972 61506 71412 58619 99620 118497 101090 67400 8492 116093 55877 94759 90034 74087 68413 104858 80351 112365 37608 108222 31659 108565 97277 105193 28246 102121 86350 76431 122874 91022 60969 2769 37464 101365 36132 66287 56594 109686 45188 66177 104170 24464 72130 51866 90949 58456 53369 87518 32744 104467 119667 99161 97953 9637 66413 36634 47292 53501 64507 85629 3822 55772 88440 58698 10554 76649 12627 24525 76642 42802 68956 99620 77473 99915 56065 13809 90950 49883 122237 80934 98801 96700 50570 20266 122316 4456 67485 95826 58875 110374 87081 66853 10228 74810 45083 99151 91358 68624 8881 3633 14325 72583 10436 46301 120906 12949 56985 45160 83578 29290 43639 52201 25153 44997 1146 47375 88350 121043 121187 114859 28809 120968 89741 34127 70513 121609 116379 103573 810 44388 112478 77474 59295 72210 74796 29945 98425 81407 62211 48615 95377 93553 31033 46651 6767 89153 77153 87001 118586 17855 5957 37487 105611 93568 59063 98970 97812 59094 85032 40334 51031 32704 72170 116174 100652 112974 22642 90312 116321 51783 57382 76533 108385 15062 74938 35976 61410 112076 61394 56579 118528 107430 2370 59506 32964 73202 103170 18728 19183 70210 88507 63351 26654 113552 50472 80305 115830 117994 57785 121155 50612 32402 7769 34250 81225 81798 101087 2312 36404 113083 117864 116259 643 51514 24929 7846 50656 26031 76839 47249 803 101040 36352 113145 29329 117880 29009 109966 32912 32674 115241 58283 76089 100252 11381 62057 52990 3215 16205 109495 21961 78521 48863 111804 34810 67763 68285 95660 56277 76912 123223 90594 108313 31293 17543 8029 30282 95617 65031 111856 104409 21312 17601 21489 100019 53191 48703 116935 106278 98433 69964 20229 90236 24428 99054 103329 12261 116940 6761 113718 19247 109979 54226 89019 14884 22619 103722 48233 73711 77563 94686 72025 10342 98099 52371 117061 4129 7985 73460 81943 103420 47250 101642 6932 2042 33488 100240 19156 27216 9709 122144 5975 34857 102695 28901 3601 117061 33537 7070 55226 74066 13445 112403 27611 102548 18639 122391 122863 73563 12612 90594 23016 108557 84604 7677 70402 93575 83122 728 43317 52245 76281 92933 32504 91230 53008 92273 43506 94871 1079 45164 68207 88237 29051 73904 60650 1113 53636 50481 73656 58213 73194 40603 107251 60320 5077 26311 100531 19871 58534 83802 85734 85111 117991 110421 30233 75345 8554 53214 122302 56791 84263 630 68693 80762 79914 27835 119452 54090 28823 83874 57864 25847 59107 26427 9857 98429 17393 90428 80630 41618 90517 99327 104180 15876 111025 117581 67765 6104 57077 63244 47903 55333 46117 2066 330 5379 102335 116799 108856 4554 120139 67497 56907 66840 71919 66995 58224 117166 9650 15966 4650 7022 36912 54870 8945 107769 119364 60038 85506 50151 82186 27747 12707 11295 91993 1329 43524 113610 104673 57824 50334 34834 75771 18546 20895 16718 62618 78240 117819 17097 16296 91302 27671 106945 14587 69188 111506 14441 55678 32393 85453 25336 110320 114169 8894 11180 101401 16094 883 66838 56983 26315 98162 53632 70624 7784 96354 23359 108869 112522 27090 110873 80499 29891 57131 71751 81134 15973 59410 55808 87934 98851 89052 84685 117037 9590 116286 44925 56772 11691 87458 30478 115290 24506 114395 103677 61140 18293 69620 17344 71902 105406 76924 104706 14571 83037 60610 66495 122983 116724 30912 84458 64836 46856 57323 106199 14686 113827 97989 97886 89002 59148 77949 29573 77962 40922 17266 119143 91390 46917 95011 108257 27635 2692 84262 39056 98676 25987 77727 102772 93450 82189 109880 259 59790 7411 21291 77277 105572 74494 13893 77854 119111 69207 55792 95130 35347 17375 50680 63577 77030 67888 37473 14608 99735 64333 120937 46159 34484 106522 94483 21217 57192 36854 108744 67106 97781 69252 96911 63661 93595 82799 46701 97627 121471 26219 98274 3898 4124 74020 32804 90007 28317 40846 9488 55182 88294 101123 13382 103345 94504 77427 114379 37526 24866 101333 89792 101252 12690 87626 63272 62972 99204 77903 120407 3752 101203 80967 52532 96654 5972 30495 73025 70111 17008 101273 81030 73818 93859 56094 14293 72325 47045 67473 92592 72121 101161 116343 85189 118391 98095 51389 4635 109371 21412 94579 61747

[出力例]
49977 9590 45131 125255 45990 131059 99465 86154 114579 120650 86627 98538 103047 115002 42967 69634 66420 64502 57170 94464 84848 38644 7311 7528 98230 99585 66688 111144 34795 102528 121497 57405 4815 11998 93556 15311 31631 1049 29860 40162 13035 94132 91340 117530 88484 117137 8705 21032 60749 54786

[入力例]

3 2

2 1 3

[出力例]

0 1

※AtCoderテストケースより

[入力例]

10 12

721939838 337089195 171851101 1069204754 348295925 77134863 839878205 89360649 838712948 918594427

[出力例]

716176219 480674244 678890528 642764255 259091950 663009497 942498522 584528336 364872846 145822575 392655861 844652404

※AtCoderテストケースより

[入力例]

7 5

11 3 7 10 15 6 5

[出力例]

9 6 7 2 6

[入力例]

20 22

99 77 53 11 69 32 89 54 69 63 98 50 20 77 78 85 55 50 27 108

[出力例]

0 27 109 54 72 21 25 85 32 0 82 50 98 24 73 103 16 93 83 61 88 83

[入力例]

60 15

8777 9093 6326 6315 11000 255 2012 12073 8918 4632 6473 10990 6424 1056 7516 3298 3304 8068 11679 7925 3283 5221 11619 5543 2495 3726 2788 5819 12143 11972 2515 3206 3016 3480 7015 1289 11426 10165 6215 1691 6383 10122 11476 5358 9620 10670 7549 10238 10676 9753 10523 9550 5489 7369 4537 10089 5133 3226 6237 5026

[出力例]

195 11596 11044 8678 13857 15622 15729 7424 1043 14341 9216 8293 3120 3231 7229

[入力例]

200 33

11275 3642 4137 11368 2555 6684 9178 5024 3453 8405 9759 893 3978 5689 6340 6472 358 2841 8551 7063 4786 9449 6631 10328 6624 273 9829 10956 9124 9064 6961 4113 9959 6084 5672 4986 1535 1557 4477 2472 2829 1069 1785 2994 5626 1269 10313 9093 2077 1920 1743 8134 4278 11743 44 3622 7969 5541 12001 3507 8900 8644 12046 7774 4401 11788 12334 2465 7548 9325 7018 2929 10072 12324 8951 6873 3615 6420 2095 12269 2317 8060 2221 3367 1053 10228 10520 7489 6759 10237 7068 8301 9107 8057 7787 3485 7383 4084 10232 8473 12268 11485 3388 8087 1562 5746 8761 6006 9694 3563 6239 8170 7130 4453 5255 4538 7258 3946 4257 3951 11504 6351 4354 11100 1859 7657 5689 267 7933 8164 9685 6320 1543 3106 10000 5092 6330 10876 5083 9462 10786 10788 2512 8052 1636 865 4514 4658 3488 3662 6774 5402 11287 9231 10839 6295 6784 3847 9367 7625 9803 9939 8432 11193 11355 1480 5652 9301 2495 7218 12037 5290 7081 10560 222 8168 9109 7467 1156 10585 9951 2881 11846 11258 3622 2545 10211 11481 2943 7926 10715 8692 952 12264 11338 4168 6061 10759 4154 10647

[出力例]

16230 4952 6305 5306 9936 10659 10133 11978 6981 11476 2725 3380 10847 2443 3061 6776 5710 3327 319 711 2929 2229 6850 11820 16312 15790 6484 9251 8502 10140 5383 4296 417

[入力例]

1000 50

55230 13276 46032 90047 13897 93439 74663 51465 50284 121720 4960 87962 86688 81870 18237 12987 27161 55886 119063 101794 58878 22308 15083 10960 29886 41605 102721 76465 40366 64909 85182 4004 50717 111852 24292 73664 61001 15764 120557 12217 39672 6271 61819 113317 99235 67173 93274 83927 110029 114336 79652 83801 49034 3108 64819 121707 121878 40847 6089 37291 75364 77190 44808 64749 107878 44943 770 67832 35430 27583 59755 14387 76213 111313 81978 97649 11164 106543 97124 38124 3704 2173 39434 41935 39772 49544 118011 119396 112357 98769 29115 60794 1268 33166 78227 119947 73991 62279 38345 90904 46791 121889 98075 25787 121230 37518 95331 113032 122032 119945 123207 92614 7198 53342 95432 58666 15310 13090 42628 32006 114910 94534 60133 91137 5069 89628 10784 65808 42456 47341 77848 39112 55692 17007 14011 77391 53025 27611 43868 7781 100490 108816 21436 34199 73246 119125 115789 103830 19414 74638 65002 72147 32070 109048 43311 113909 88264 111918 62991 3086 55919 45484 100482 41887 74786 94663 10579 38233 20666 1844 77617 54457 752 49319 81871 57756 102943 91203 24768 105112 46862 116126 23389 4973 49793 114850 18522 58906 12048 5322 41531 3238 91453 66378 64237 45620 36435 1434 84890 12672 75365 17041 92542 21726 46258 26135 48950 110386 1974 121510 54984 12598 76692 108524 18002 113388 47603 76038 51450 21297 48722 14904 68287 81904 90787 88948 119474 90486 77949 85185 28844 43881 6263 122757 36287 120585 87454 70347 33461 43690 23994 114243 99525 79610 97266 45630 37347 53120 46950 106562 99495 18814 74672 27075 92025 120467 86390 90532 74717 22229 43248 95265 115538 121820 53200 97787 27316 105618 99360 78975 56769 70728 12721 89023 54539 39439 99930 35948 118375 70849 17399 88361 39231 39417 11994 15358 56215 17054 41478 73741 28509 54838 122170 64236 93508 59436 47486 31026 87234 76397 41387 34839 6478 50975 8441 104293 60008 32442 116938 116848 63963 111891 14148 120976 20090 18359 73385 104263 94357 123203 52651 11625 73203 17211 54949 16388 20724 10240 36847 80662 52280 81499 25972 61506 71412 58619 99620 118497 101090 67400 8492 116093 55877 94759 90034 74087 68413 104858 80351 112365 37608 108222 31659 108565 97277 105193 28246 102121 86350 76431 122874 91022 60969 2769 37464 101365 36132 66287 56594 109686 45188 66177 104170 24464 72130 51866 90949 58456 53369 87518 32744 104467 119667 99161 97953 9637 66413 36634 47292 53501 64507 85629 3822 55772 88440 58698 10554 76649 12627 24525 76642 42802 68956 99620 77473 99915 56065 13809 90950 49883 122237 80934 98801 96700 50570 20266 122316 4456 67485 95826 58875 110374 87081 66853 10228 74810 45083 99151 91358 68624 8881 3633 14325 72583 10436 46301 120906 12949 56985 45160 83578 29290 43639 52201 25153 44997 1146 47375 88350 121043 121187 114859 28809 120968 89741 34127 70513 121609 116379 103573 810 44388 112478 77474 59295 72210 74796 29945 98425 81407 62211 48615 95377 93553 31033 46651 6767 89153 77153 87001 118586 17855 5957 37487 105611 93568 59063 98970 97812 59094 85032 40334 51031 32704 72170 116174 100652 112974 22642 90312 116321 51783 57382 76533 108385 15062 74938 35976 61410 112076 61394 56579 118528 107430 2370 59506 32964 73202 103170 18728 19183 70210 88507 63351 26654 113552 50472 80305 115830 117994 57785 121155 50612 32402 7769 34250 81225 81798 101087 2312 36404 113083 117864 116259 643 51514 24929 7846 50656 26031 76839 47249 803 101040 36352 113145 29329 117880 29009 109966 32912 32674 115241 58283 76089 100252 11381 62057 52990 3215 16205 109495 21961 78521 48863 111804 34810 67763 68285 95660 56277 76912 123223 90594 108313 31293 17543 8029 30282 95617 65031 111856 104409 21312 17601 21489 100019 53191 48703 116935 106278 98433 69964 20229 90236 24428 99054 103329 12261 116940 6761 113718 19247 109979 54226 89019 14884 22619 103722 48233 73711 77563 94686 72025 10342 98099 52371 117061 4129 7985 73460 81943 103420 47250 101642 6932 2042 33488 100240 19156 27216 9709 122144 5975 34857 102695 28901 3601 117061 33537 7070 55226 74066 13445 112403 27611 102548 18639 122391 122863 73563 12612 90594 23016 108557 84604 7677 70402 93575 83122 728 43317 52245 76281 92933 32504 91230 53008 92273 43506 94871 1079 45164 68207 88237 29051 73904 60650 1113 53636 50481 73656 58213 73194 40603 107251 60320 5077 26311 100531 19871 58534 83802 85734 85111 117991 110421 30233 75345 8554 53214 122302 56791 84263 630 68693 80762 79914 27835 119452 54090 28823 83874 57864 25847 59107 26427 9857 98429 17393 90428 80630 41618 90517 99327 104180 15876 111025 117581 67765 6104 57077 63244 47903 55333 46117 2066 330 5379 102335 116799 108856 4554 120139 67497 56907 66840 71919 66995 58224 117166 9650 15966 4650 7022 36912 54870 8945 107769 119364 60038 85506 50151 82186 27747 12707 11295 91993 1329 43524 113610 104673 57824 50334 34834 75771 18546 20895 16718 62618 78240 117819 17097 16296 91302 27671 106945 14587 69188 111506 14441 55678 32393 85453 25336 110320 114169 8894 11180 101401 16094 883 66838 56983 26315 98162 53632 70624 7784 96354 23359 108869 112522 27090 110873 80499 29891 57131 71751 81134 15973 59410 55808 87934 98851 89052 84685 117037 9590 116286 44925 56772 11691 87458 30478 115290 24506 114395 103677 61140 18293 69620 17344 71902 105406 76924 104706 14571 83037 60610 66495 122983 116724 30912 84458 64836 46856 57323 106199 14686 113827 97989 97886 89002 59148 77949 29573 77962 40922 17266 119143 91390 46917 95011 108257 27635 2692 84262 39056 98676 25987 77727 102772 93450 82189 109880 259 59790 7411 21291 77277 105572 74494 13893 77854 119111 69207 55792 95130 35347 17375 50680 63577 77030 67888 37473 14608 99735 64333 120937 46159 34484 106522 94483 21217 57192 36854 108744 67106 97781 69252 96911 63661 93595 82799 46701 97627 121471 26219 98274 3898 4124 74020 32804 90007 28317 40846 9488 55182 88294 101123 13382 103345 94504 77427 114379 37526 24866 101333 89792 101252 12690 87626 63272 62972 99204 77903 120407 3752 101203 80967 52532 96654 5972 30495 73025 70111 17008 101273 81030 73818 93859 56094 14293 72325 47045 67473 92592 72121 101161 116343 85189 118391 98095 51389 4635 109371 21412 94579 61747

[出力例]

49977 9590 45131 125255 45990 131059 99465 86154 114579 120650 86627 98538 103047 115002 42967 69634 66420 64502 57170 94464 84848 38644 7311 7528 98230 99585 66688 111144 34795 102528 121497 57405 4815 11998 93556 15311 31631 1049 29860 40162 13035 94132 91340 117530 88484 117137 8705 21032 60749 54786

■参照サイト
AtCoder Regular Contest 137

2022年12月26日

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

C++の練習を兼ねて, AtCoder Grand Contest 030 の問題C (Coloring Torus) を解いてみた.

■感想.
1. 問題C は, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 解説のロジックで, K色でのよい塗り方を構成ことが, 非常に不思議な印象を受け, 面白く感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/agc030/editorial.pdf
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
int ans[505][505];

int main(){
    
    // 1. 入力情報.
    int K;
    scanf("%d", &K);
    
    // 2. 例外.
    if(K == 1){
        puts("1\n1");
        return 0;
    }
    
    // 3. K色でのよい塗り方(解説通り).
    int n = 2 * ((K + 3) / 4);
    int d = 2 * n - K;
    rep(r, n){
        rep(c, n){
            int b = (r + c) % n;
            ans[r][c] = b;
            if(r & 1) ans[r][c] += (b < n - d) ? n : 0;
        }
    }
    
    // 4. 出力.
    printf("%d\n", n);
    rep(r, n) rep(c, n) printf("%d%s", ans[r][c] + 1, (c < n - 1) ? " " : "\n");
    return 0;
    
}

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

int ans[505][505];

int main(){

// 1. 入力情報.

int K;

scanf("%d", &K);

// 2. 例外.

if(K == 1){

puts("1\n1");

return 0;

}

// 3. K色でのよい塗り方(解説通り).

int n = 2 * ((K + 3) / 4);

int d = 2 * n - K;

rep(r, n){

rep(c, n){

int b = (r + c) % n;

ans[r][c] = b;

if(r & 1) ans[r][c] += (b < n - d) ? n : 0;

}

// 4. 出力.

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

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

return 0;

}

[入力例]
2

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

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

[入力例]
9

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

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

[入力例]
1

[出力例]
1
1

[入力例]
3

[出力例]
2
1 2
2 3

[入力例]
4

[出力例]
2
1 2
4 3

[入力例]
13

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

[入力例]
22

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

[入力例]
50

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

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

[入力例]

[出力例]

1 1 1

2 2 2

※AtCoderテストケースより

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

1 2

2 1

[入力例]

[出力例]

1 2 3

4 5 6

7 8 9

※AtCoderテストケースより

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

1 2 3 4 5 6

8 9 4 5 6 7

3 4 5 6 1 2

4 5 6 7 8 9

5 6 1 2 3 4

6 7 8 9 4 5

[入力例]

[出力例]

[入力例]

[出力例]

1 2

2 3

[入力例]

[出力例]

1 2

4 3

[入力例]

[出力例]

1 2 3 4 5 6 7 8

10 11 12 13 6 7 8 9

3 4 5 6 7 8 1 2

12 13 6 7 8 9 10 11

5 6 7 8 1 2 3 4

6 7 8 9 10 11 12 13

7 8 1 2 3 4 5 6

8 9 10 11 12 13 6 7

[入力例]

[出力例]

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

14 15 16 17 18 19 20 21 22 11 12 13

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

16 17 18 19 20 21 22 11 12 13 14 15

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

18 19 20 21 22 11 12 13 14 15 16 17

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

20 21 22 11 12 13 14 15 16 17 18 19

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

22 11 12 13 14 15 16 17 18 19 20 21

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

12 13 14 15 16 17 18 19 20 21 22 11

[入力例]

[出力例]

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

28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 25 26 27

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

30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 25 26 27 28 29

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

32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 25 26 27 28 29 30 31

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

34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 25 26 27 28 29 30 31 32 33

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

36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 25 26 27 28 29 30 31 32 33 34 35

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

38 39 40 41 42 43 44 45 46 47 48 49 50 25 26 27 28 29 30 31 32 33 34 35 36 37

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

40 41 42 43 44 45 46 47 48 49 50 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

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

42 43 44 45 46 47 48 49 50 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41

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

44 45 46 47 48 49 50 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43

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

46 47 48 49 50 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45

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

48 49 50 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47

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

50 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49

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

26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 25

■参照サイト
AtCoder Grand Contest 030

2022年12月23日

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

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

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

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

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

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

int main(){
    
    // 1. 入力情報.
    int H, W, N, h, w;
    scanf("%d %d %d %d %d", &H, &W, &N, &h, &w);
    rep(i, H){
        rep(j, W){
            scanf("%d", &a[i][j]);
            --a[i][j];
        }
    }
    
    // 2. 二次元累積和.
    repx(i, 1, H + 1){
        repx(j, 1, W + 1){
            rep(k, N) b[i][j][k] = b[i - 1][j][k] + b[i][j - 1][k] - b[i - 1][j - 1][k];
            ++b[i][j][a[i - 1][j - 1]];
        }
    }
    
    // 3. マスに書かれた整数の種類を集計.
    rep(k, N) t[k] = b[H][W][k];
    
    // 4. 各塗りつぶしを確認.
    repx(i, 1, H - h + 2){
        repx(j, 1, W - w + 2){
            // 初期化.
            int c[N];
            rep(k, N) c[k] = t[k];
            
            // 左上マス(i, j) ～ 右下マス(i + h - 1, j + w - 1) までを塗りつぶした場合.
            // 減算: 右下マス(i + h - 1, j + w - 1)
            rep(k, N) c[k] -= b[i + h - 1][j + w - 1][k];
            
            // 加算: 左下マス(i + h - 1, j) よりも左側.
            if(j > 1) rep(k, N) c[k] += b[i + h - 1][j - 1][k];
            
            // 加算: 右上マス(i, j + w - 1) よりも上側.
            if(i > 1) rep(k, N) c[k] += b[i - 1][j + w - 1][k];
            
            // 減算: 左上マス(i, j) よりも左上側.
            if(i > 1 && j > 1) rep(k, N) c[k] -= b[i - 1][j - 1][k];
            
            // 集計.
            int ans = 0;
            rep(k, N) ans += (c[k] > 0);
            
            // 出力.
            printf("%d%s", ans, (j < W - w + 1) ? " " : "\n");
        }
    }
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

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

int main(){

// 1. 入力情報.

int H, W, N, h, w;

scanf("%d %d %d %d %d", &H, &W, &N, &h, &w);

rep(i, H){

rep(j, W){

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

--a[i][j];

}

// 2. 二次元累積和.

repx(i, 1, H + 1){

repx(j, 1, W + 1){

rep(k, N) b[i][j][k] = b[i - 1][j][k] + b[i][j - 1][k] - b[i - 1][j - 1][k];

++b[i][j][a[i - 1][j - 1]];

}

// 3. マスに書かれた整数の種類を集計.

rep(k, N) t[k] = b[H][W][k];

// 4. 各塗りつぶしを確認.

repx(i, 1, H - h + 2){

repx(j, 1, W - w + 2){

// 初期化.

int c[N];

rep(k, N) c[k] = t[k];

// 左上マス(i, j) ～右下マス(i + h - 1, j + w - 1) までを塗りつぶした場合.

// 減算: 右下マス(i + h - 1, j + w - 1)

rep(k, N) c[k] -= b[i + h - 1][j + w - 1][k];

// 加算: 左下マス(i + h - 1, j) よりも左側.

if(j > 1) rep(k, N) c[k] += b[i + h - 1][j - 1][k];

// 加算: 右上マス(i, j + w - 1) よりも上側.

if(i > 1) rep(k, N) c[k] += b[i - 1][j + w - 1][k];

// 減算: 左上マス(i, j) よりも左上側.

if(i > 1 && j > 1) rep(k, N) c[k] -= b[i - 1][j - 1][k];

// 集計.

int ans = 0;

rep(k, N) ans += (c[k] > 0);

// 出力.

printf("%d%s", ans, (j < W - w + 1) ? " " : "\n");

}

return 0;

}

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

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

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

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

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

[出力例]
21 20 19 20 18 17
20 19 18 19 17 15
21 19 20 19 18 16
21 19 19 18 19 18
20 18 18 18 19 18
18 16 17 18 19 17
※AtCoderテストケースより

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

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

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

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

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

[入力例]

3 4 5 2 2

2 2 1 1

3 2 5 3

3 4 4 3

[出力例]

4 4 3

5 3 4

※AtCoderテストケースより

[入力例]

5 6 9 3 4

7 1 5 3 9 5

4 5 4 5 1 2

6 1 6 2 9 7

4 7 1 5 8 8

3 4 3 3 5 3

[出力例]

8 8 7

8 9 7

8 9 8

※AtCoderテストケースより

[入力例]

9 12 30 4 7

2 2 2 2 2 2 2 2 2 2 2 2

2 2 20 20 2 2 5 9 10 9 9 23

2 29 29 29 29 29 28 28 26 26 26 15

2 29 29 29 29 29 25 25 26 26 26 15

2 29 29 29 29 29 25 25 8 25 15 15

2 18 18 18 18 1 27 27 25 25 16 16

2 19 22 1 1 1 7 3 7 7 7 7

2 19 22 22 6 6 21 21 21 7 7 7

2 19 22 22 22 22 21 21 21 24 24 24

[出力例]

21 20 19 20 18 17

20 19 18 19 17 15

21 19 20 19 18 16

21 19 19 18 19 18

20 18 18 18 19 18

18 16 17 18 19 17

※AtCoderテストケースより

[入力例]

13 15 7 7 7

1 2 1 2 1 2 1 2 1 2 1 2 1 2 1

2 1 2 1 2 1 2 1 2 1 2 1 2 1 2

1 2 1 2 1 2 1 2 1 2 1 2 1 2 1

2 1 2 1 2 1 2 1 2 1 2 1 2 1 2

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

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

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

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

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

2 1 2 1 2 1 2 1 2 1 2 1 2 1 2

1 2 1 2 1 2 1 2 1 2 1 2 1 2 1

2 1 2 1 2 1 2 1 2 1 2 1 2 1 2

1 2 1 2 1 2 1 2 1 2 1 2 1 2 1

[出力例]

7 7 7 7 7 7 7 7 7

5 4 3 2 2 2 3 4 5

7 7 7 7 7 7 7 7 7

[入力例]

30 30 19 21 21

1 2 3 2 1 1 2 3 2 1 1 2 3 2 1 1 2 3 2 1 1 2 3 2 1 1 2 3 2 1

2 3 2 1 1 2 3 2 1 1 2 3 2 1 1 2 3 2 1 1 2 3 2 1 1 2 3 2 1 1

3 2 1 1 2 3 2 1 1 2 3 2 1 1 2 3 2 1 1 2 3 2 1 1 2 3 2 1 1 2

2 1 1 2 3 2 1 1 2 3 2 1 1 2 3 2 1 1 2 3 2 1 1 2 3 2 1 1 2 3

1 1 2 3 2 1 1 2 3 2 1 1 2 3 2 1 1 2 3 2 1 1 2 3 2 1 1 2 3 2

1 2 3 2 1 1 2 3 2 1 1 2 3 2 1 1 2 3 2 1 1 2 3 2 1 1 2 3 2 1

2 3 2 1 1 2 3 2 1 1 2 3 2 1 1 2 3 2 1 1 2 3 2 1 1 2 3 2 1 1

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

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

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

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

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