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