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

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

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

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

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

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

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

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

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

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

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

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

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

// 0: e

// 1: a

// 2: a * a

// 3: a * a * a

// 4: b

// 5: a * b

// 6: a * a * b

// 7: a * a * a * b

int t[8][8] = {

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

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

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

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

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

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

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

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

};

int main(){

// 1. 入力情報.

int N, Q;

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

// 2. マス目初期化.

int ans[N][N];

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

// 3. クエリ.

vector<T3> q;

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

rep(i, Q){

// パターン取得.

int f;

scanf("%d", &f);

// パターン①.

if(f == 1){

int x, y;

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

x--, y--;

q.emplace_back(f, x, y);

}

// パターン②.

if(f == 2){

char c[11];

scanf("%s", c);

// 時計回り(90度).

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

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

qs = t[qs][3];

}

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

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

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

qs = t[qs][1];

}

// パターン③.

if(f == 3){

char c[11];

scanf("%s", c);

// 上下反転.

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

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

qs = t[qs][4];

}

// 左右反転.

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

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

qs = t[qs][6];

}

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

for(auto &p : q){

// クエリ情報.

int f = get<0>(p);

int ca = get<1>(p);

int cb = get<2>(p);

// パターン①.

if(f == 1){

int na = N - 1 - ca;

int nb = N - 1 - cb;

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

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

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

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

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

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

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

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

}

// パターン② or ③.

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

}

// 5. 出力.

rep(i, N){

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

puts("");

}

return 0;

}

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

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

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

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

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

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

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

[出力例]
01000
00000
00000
00100
10010

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

[出力例]
000000
000000
000000
000000
000000
000000

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

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

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

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

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

[入力例]

3 2

1 1 1

2 A

[出力例]

001

000

※AtCoderテストケースより

[入力例]

3 3

1 1 1

3 A

3 B

[出力例]

000

001

※AtCoderテストケースより

[入力例]

4 8

2 A

1 4 2

2 A

1 2 2

3 B

3 A

1 3 1

[出力例]

0000

0100

0000

※AtCoderテストケースより

[入力例]

5 15

3 A

2 B

1 1 1

3 B

2 A

2 B

1 2 3

2 B

1 3 2

3 A

1 4 5

3 B

1 3 4

1 2 5

2 A

[出力例]

01000

00000

00100

10010

[入力例]

6 5

1 2 3

2 A

3 B

1 3 2

3 A

[出力例]

000000

[入力例]

10 20

1 2 3

2 A

3 B

1 1 9

3 A

1 7 6

3 B

1 3 7

3 A

1 8 3

2 A

3 B

1 3 5

3 A

3 B

1 3 7

3 A

2 B

2 A

1 10 1

[出力例]

0000000000

0000000001

0010010000

0000000000

0000001000

0000000000

0010000000

0000001000

0000000100

1000000000

[入力例]

20 50

1 3 18

2 B

3 A

1 17 1

2 B

1 12 10

2 A

1 7 18

3 A

1 2 13

2 B

1 5 5

2 A

3 B

1 13 18

3 A

3 B

3 A

1 15 10

2 B

2 A

1 5 7

1 10 1

3 B

2 B

3 A

1 6 17

3 A

3 B

1 15 10

2 A

1 3 20

3 A

1 8 9

3 B

1 13 6

3 A

1 18 17

2 A

1 17 5

2 B

3 A

3 B

1 4 13

3 A

2 B

1 6 15

[出力例]

00010000010000000100

00000000000000000000

00100000000000000000

00000000000000000000

00000001010000100000

00001000000000000100

00100000000000001000

00000000001000000000

00000000000000000000

00000000000010000000

00000000000000000000

00000000001000001000

00000000000000010000

00000000000000010100

00000000000000000000

00000000000010000000

00000000000000000000

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

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

コメントを残す コメントをキャンセル

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

コメントを残すコメントをキャンセル