個人用メモ帳

2022年1月5日

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

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

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

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

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

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

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

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

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

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

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

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

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

// 0: e

// 1: a

// 2: a * a

// 3: a * a * a

// 4: b

// 5: a * b

// 6: a * a * b

// 7: a * a * a * b

int t[8][8] = {

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

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

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

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

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

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

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

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

};

int main(){

// 1. 入力情報.

int N, Q;

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

// 2. マス目初期化.

int ans[N][N];

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

// 3. クエリ.

vector<T3> q;

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

rep(i, Q){

// パターン取得.

int f;

scanf("%d", &f);

// パターン①.

if(f == 1){

int x, y;

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

x--, y--;

q.emplace_back(f, x, y);

}

// パターン②.

if(f == 2){

char c[11];

scanf("%s", c);

// 時計回り(90度).

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

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

qs = t[qs][3];

}

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

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

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

qs = t[qs][1];

}

// パターン③.

if(f == 3){

char c[11];

scanf("%s", c);

// 上下反転.

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

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

qs = t[qs][4];

}

// 左右反転.

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

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

qs = t[qs][6];

}

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

for(auto &p : q){

// クエリ情報.

int f = get<0>(p);

int ca = get<1>(p);

int cb = get<2>(p);

// パターン①.

if(f == 1){

int na = N - 1 - ca;

int nb = N - 1 - cb;

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

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

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

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

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

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

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

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

}

// パターン② or ③.

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

}

// 5. 出力.

rep(i, N){

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

puts("");

}

return 0;

}

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

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

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

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

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

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

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

[出力例]
01000
00000
00000
00100
10010

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

[出力例]
000000
000000
000000
000000
000000
000000

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

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

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

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

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

[入力例]

3 2

1 1 1

2 A

[出力例]

001

000

※AtCoderテストケースより

[入力例]

3 3

1 1 1

3 A

3 B

[出力例]

000

001

※AtCoderテストケースより

[入力例]

4 8

2 A

1 4 2

2 A

1 2 2

3 B

3 A

1 3 1

[出力例]

0000

0100

0000

※AtCoderテストケースより

[入力例]

5 15

3 A

2 B

1 1 1

3 B

2 A

2 B

1 2 3

2 B

1 3 2

3 A

1 4 5

3 B

1 3 4

1 2 5

2 A

[出力例]

01000

00000

00100

10010

[入力例]

6 5

1 2 3

2 A

3 B

1 3 2

3 A

[出力例]

000000

[入力例]

10 20

1 2 3

2 A

3 B

1 1 9

3 A

1 7 6

3 B

1 3 7

3 A

1 8 3

2 A

3 B

1 3 5

3 A

3 B

1 3 7

3 A

2 B

2 A

1 10 1

[出力例]

0000000000

0000000001

0010010000

0000000000

0000001000

0000000000

0010000000

0000001000

0000000100

1000000000

[入力例]

20 50

1 3 18

2 B

3 A

1 17 1

2 B

1 12 10

2 A

1 7 18

3 A

1 2 13

2 B

1 5 5

2 A

3 B

1 13 18

3 A

3 B

3 A

1 15 10

2 B

2 A

1 5 7

1 10 1

3 B

2 B

3 A

1 6 17

3 A

3 B

1 15 10

2 A

1 3 20

3 A

1 8 9

3 B

1 13 6

3 A

1 18 17

2 A

1 17 5

2 B

3 A

3 B

1 4 13

3 A

2 B

1 6 15

[出力例]

00010000010000000100

00000000000000000000

00100000000000000000

00000000000000000000

00000001010000100000

00001000000000000100

00100000000000001000

00000000001000000000

00000000000000000000

00000000000010000000

00000000000000000000

00000000001000001000

00000000000000010000

00000000000000010100

00000000000000000000

00000000000010000000

00000000000000000000

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

2022年1月4日

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

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

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

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

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

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

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

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

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

100

101

102

103

104

105

106

107

108

109

110

111

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

#define a first

#define b second

#define pb push_back

const LL INF = 2e18 + 1;

struct edge{

int n; // 次の頂点.

LL c; // コスト.

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

};

vector<edge> G[202020];

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

int main(){

// 1. 入力情報.

LL N;

int M;

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

map<LL, int> m;

rep(i, M){

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

m[a[i]] = 1;

m[b[i]] = 1;

}

m[1] = 1;

m[N] = 1;

// 2. 座標圧縮.

int idx = -1;

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

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

LL cBef, cCur;

int vBef = -1, vCur;

for(auto &p : m){

// 今回分更新.

cCur = p.a;

vCur = p.b;

// 辺を追加.

if(vBef != -1){

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

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

}

// 前回分更新.

cBef = cCur;

vBef = vCur;

}

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

rep(i, M){

int u = m[a[i]];

int v = m[b[i]];

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

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

}

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

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

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

// 初期化.

priority_queue<edge> pq;

// 始点設定.

d[s] = 0;

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

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

while(!pq.empty()){

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

edge e = pq.top();

pq.pop();

int cn = e.n;

LL cc = e.c;

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

if(memo[cn]) continue;

memo[cn]++;

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

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

// 移動コスト更新.

int nn = g.n;

LL nc = cc + g.c;

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

}

};

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

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

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

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

dijkstra(0, d, memo);

// 7. 出力.

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

return 0;

}

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

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

[入力例]
1000000000000000000 1
1 1000000000000000000 1000000000000000000

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

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

[出力例]
7

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

[出力例]
65

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

[出力例]
11580774

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

[出力例]
186535821129

100

101

102

103

[入力例]

10 2

2 5 1

4 10 3

[出力例]

※AtCoderテストケースより

[入力例]

1000000000000000000 1

1 1000000000000000000 1000000000000000000

[出力例]

999999999999999999

※AtCoderテストケースより

[入力例]

11 3

2 4 1

5 7 1

8 10 1

[出力例]

[入力例]

100 10

1 10 5

5 17 7

18 35 12

49 66 11

77 95 8

36 52 9

10 25 7

40 75 47

51 68 10

28 41 11

[出力例]

[入力例]

20220104 20

828865 4804632 12069969

6295187 13558375 1837197

3310273 11010080 7881068

5772550 14219264 18758563

4225815 8738497 6630771

6879164 10620764 10892637

4838718 8073754 14372199

6291069 10471126 70549

558133 1418658 9345163

8215556 18066689 18750539

8371221 8912288 13240335

6496981 12139308 15053771

7416355 12359442 7081448

116798 5578623 17894867

5948188 12066446 315682

932978 4289526 519795

3579073 9810527 15940312

8175707 15948535 19959019

4000956 6515736 2966577

8639132 11793341 15657568

[出力例]

11580774

[入力例]

202112111300 30

2836912071 8265759792 18349207920

6321404409 7117150178 5191319749

5133174124 6981490113 4115025861

8073790036 13562620650 576427819

2311345537 5346249323 15395778052

5232172781 6860771277 4967211588

9930875748 18298309556 1894862604

5493633256 9764925778 4529928865

2129123401 12177775551 771175460

6877686882 11695500319 16000522151

613446757 1219290120 8543162814

4425468693 6201308906 17815170784

760738956 10235609132 1569024502

5970087903 12676828451 5368533553

847837589 8203683049 654051583

3366379489 5918321181 16417033782

8019754324 14372671034 4782560986

10048397218 14291129034 14916272145

4180881599 8564813978 6154260194

8335300636 9618931292 7974820034

8247089832 17234489737 112903612

9226479498 12245429510 17492201072

584745120 5781270528 11323123105

1266934563 5758721472 12198029546

5226702368 8951155543 783723174

9715667921 18083960295 14479844635

5325151693 9867219235 787867457

4579272049 9781286327 1477152595

564092880 5096514264 17221220356

1621294237 11411345457 12861090392

[出力例]

186535821129

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

2022年1月4日

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

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

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

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

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

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

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

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

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

const LL MOD = 1e9 + 7;

LL L[101010];

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

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

// @param b: 指数.

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

LL mPow(LL a, LL b){

LL t = 1;

while(b){

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

a = a * a % MOD;

b >>= 1;

}

return t;

}

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

LL D = 202020202020202020;

rep(i, N){

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

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

}

// 2. 最大公約数.

LL g = 0;

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

// 3. 出力.

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

return 0;

}

[入力例]
3
2
4
8

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

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

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

[入力例]
5
700000000
20000000
9000000
600000000
30000000

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

[入力例]
3
7
5
3

[出力例]
16

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

[出力例]
739772112

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

[出力例]
342555388

[入力例]

[出力例]

※AtCoderのテストケースより

[入力例]

[出力例]

※AtCoderのテストケースより

[入力例]

700000000

20000000

9000000

600000000

30000000

[出力例]

861838989

※AtCoderのテストケースより

[入力例]

[出力例]

[入力例]

6066

2022

8088

2022

10110

18198

4044

12132

10110

6066

[出力例]

739772112

[入力例]

121021629

645189559

100861324

1693525419

1915288774

1108876574

625029254

1653204809

181502544

927433829

1592723894

60540714

806471999

947594134

1068555964

[出力例]

342555388

■参照サイト
AtCoder Regular Contest 048

2022年1月3日

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

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

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

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

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

// 解き直し.
// https://atcoder.jp/contests/past202112-open/editorial/3129
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vs = vector<set<int>>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
int dp[5050][5050];

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

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vs = vector<set<int>>;

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

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

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

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

int dp[5050][5050];

int main(){

// 1. 入力情報.

char s[5050], t[5050];

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

// 2. dp更新.

int N = strlen(s);

int M = strlen(t);

rep(a, N){

rep(b, M){

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

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

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

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

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

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

}

// 3. 出力.

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

return 0;

}

[入力例]
abc
aba

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

[入力例]
aaaaaa
a

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

[入力例]
abra
cadabra

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

[入力例]
oooopppqqrrrsss
oooppqrrssstttt

[出力例]
12

[入力例]
yfbtiphgpoierzzkhrnyawhgjqbnsciaiditqouwhtfxhamwryqtzguzrafvgifexvvmiktzepdwnvesuvmsgigxizbxrynyskypjrthvvicmifkyffqxkiouieoidjtsxwwjqaflytcmzvmpacmalcuucqtujpagpmtnpdtadlvosihreliuhfwssakqknyiqowqlww
zfdxmlcbgrubvnalctxasvihvjweishewyhvvziaoyyybklzhcomsgjncqcscfzdyknlbmdrxligotjlshferdfwqkoastrqcqfepovdxmpjobgujagplfbnrnbvdntpnkrvbkdjznjybqpcnbrxpkeolbrmyjvscroszlravwxsribentjjwcisvujyjlpvnwvtkrca

[出力例]
197

[入力例]
cuwllsesaoaanxfghjytmttwsmdrmgfisujygpusbxgwdsikzuyixsbtpnwuwuawarsesfmnhuijjhfetoovqwuezcxqhneuyjnfibobwgyjpgamvdpresibyqrpcyusskijajdalxyvqgldyqcukldztmuaxnfqmocvxjrlziivycyrgdfbqvbysdtydffvwnsivkicgdmtmcugfkhscbuuvbsqfaykqiiseztmebmzdksulvxsyqqyekwfgntubqqggtlegcophdaedonulmnvqyunwukrclpsezrwoplyxxqsmbvlykctngbcyhgfaydfbtdetknxibyessslaghwrqizaafjlxgrokbdexyyxelmgesdlegamceyobadkylenxntzogqmgohmwgzsilajuxohgxjxaloryjsbjsrutzcilgwrmfwlbtfptwkxyfjywihisvpaozszcpmwhjtpwelkmfjfjnfstyaukhscantysqiljidoikimpmngpsmijhklknshqhcubhfgdcfgkifayxdlvaakunebttqhhchkoyknrlwwpyqucipsvxntlkqrwrgflupqdetxinhzhaesriqtdngrxuxccoedyhoesdydenrutgfqkrvuecajgkdxfdufptcrxmsbgllzhniarmnivvdkadflexzfpooomhcydasfrcshfbyetninsxnutpiyqrbtzqcdsujcznnptplcrjiddnnurlervukhhqeweyiypqrznznfxwggrfqloloehthkrthnxqqceqdteyinpcvuwzrximynobuglgwvsczkvebtngsgvyocvnqjnaanelwaamkhwlmrwihlgfplojnvywwjcizwycnbyvgpulydcfyukfucdvlxxgzcvwlqchommydyrfukhqzlweqvcrpqawuabfclpjohsiidfrtbsdfzohkkjsvlvkwujbfrlorlqakoiwonpjmwgrkegiacbco
fwmskagltnakcfqnfwsqtelzinginpilrbjchyfbjkgqjhnrrzcmqbqvcompavodojucybjlkfhqsvvibqcrjtmsbzcmuzmzrpnngaouepcscmmohyojyhrdyijesqfocykarhfmxozhqeaawogsbethpydovwnipohocnratyaagqjgmudgwxigxyyvzaigkinpuabgzsrcqbcxmdcugpovtnlaiyxreifjjiifpwtvnlwemocuijllpxhdmvvliioqvqrfoaqebopripetkludfcucjbhqlrtipoxyrfwfclmhvbbrebwcezjzydrwnudfzaykbvieabjezocryfrbitlyapjcffbaqmgutydvoyzzallhnuqnflqyjlfdajgwajkdjawjxfixuycyhffsayfjjrwyvnawqdnpbionwgktolanaxzuclwltsngdqfcjdvwvuaelupmoxalmsgjfrrafmvoeiqbtdrpfowapyiwfegvsdvytijbzglpzxcvnddqiijthfngxwtcnqosoodogpbnvbzovdsbniyokqiqhkmhofzhgarxetezzchmhrkuwliwwrlcetgxhwddxrdunwjaqrpfyfoniuopcxhxwzkzvypkvykslkchudkxgrrjhqmfkclslsccedueymrsdiaejfjngvyvarongoewfmnfxkqtxcvnhujprdskjgmcqmezwmrtauhnenfojpwofvpvrqzoiuecnndpnnauzvpomtcdimjbgcpewpkcyyimzqunxthtzhcxuazuuhynzdtrvxevitgfmgpcjlhqetmkonmzairztyhghtqakkfcqbrpxzvgasrsunnlrhyomxnoihilfnkckaqvstlwuahbupufwzleplwjvyllhgndzcptjheuekrnimvaykhinxivupxpxuzbnggjubvaeemencunpzcosjvndsmfvyvfsstenakcdsgxwnmegaykmmdcsnzxblvt

[出力例]
985

[入力例]
tjgqvvdipknzaeedgpuwbtowamjeeszoeptnnwkjvetrkcrpbnykpvxvxkmafjmojswxvxzlulxlzkdcdgwprvulgdxjwadenwyagqhnyamttckhrugrybquhnddojizvotaowmoczmwvzmojasuyqvsiymzmirsoxqqzixlkfdrdanjzsnhhjksiszhejyjxjujhwaqaalbmjqwssiqcchsylvezfeviijzzobiyeyestlajsnlbwodlgwsufoqtupwnppcbwiryhwyhhkyciscfmmkqaubysmmrqwxgqprtutnbwyrzinpmkmtdtfchqpvqankqdlpehzrsbytdflyerlrbkwjwkrshbjijqvqfbgvmoocpuqephppczawzcfuiolvsdpcwidoewthgkwnsutdaazpnwygfkoxatecipqoaoglgrckdufenwhjuycxmybfdpjtoilmjxzjcdwvvqkynfevakjyasmqnbbwfybfcejhseuodowvlnznewqunixjktsqbuwkwsjupxszbjxogxgmxdwgmdzrbogvmsfyklxctnxopcviuoxjlrepdgydgxkjjxoqxxzqlhmaxdwayafcphklrupuuitvapphmkgwgxrquggkhnftqvgdwpibmlepvglfftsuczcqsbbwhkybefdjzdbpyxnlajpqrjtqdsdsrbvejlsfenpjogmspqmpbxnhcxxgsyafxjyulkcbauxzegzvndqwdfxtuuoxqbingaasqukhzhympmirgnhczytrfpdtezrstxtgssrolkgxixntfkfcysknbvtwjqxffljieuxahyylbcuhpywxjfvaiowjuuxwghfyvvrujctjqaynhlovucvdthektngptqcjbzwcidogjncihfnfpmosfkbmgoakyrxhqcwukdlrsqcsybhchmtbqkynswxqcaesnkgoaacddybwmxkhuxqqditkdrzneneeccllxuhzcsxfrnmffojtopguoxlvsiyzomfpoyoduiuhhxsiixpqbhsivyxkefaujmfevuhxbwynwqfjfhfobolnumvvoyydzoezldblgnnnwcscajuwicymyjdjdpyduycinojkmvamfxjdfiknuptpdkmwvhelssvsdjojtvrgocrwmftacorkqtsqyhjnpxnhbfjspingmjiaycqfmicfehtsutsfgvhkohqvwiebohencjgnwnnpwzvkumwwankrzhvfmfopqfddwvckhtgjcvjqvztvhzryprmocrsyvjrhghqekimygtaciqzcbvzujjptsvrouoqhveecbccssdzzxaxwfboyxaozplhdryqudahniwmgmxfapgsmwxnximgbucxbpcclyrexiqufafvjvphbbeziqryihbxrlllfltnwytmoarlxbwihiaosmbiqlwgeynfukwalhorqfpahlyzkeehfauulbekusyxdftdbqudczkdqtuujcjlfikjzxgobwzwakmueykehpovfhuhiiasbhucpotjddrwtnbfgijnfwylozwnclimdwnivhulmrprqbtesdkjiuqlchzagdaxxoiojfhewwwguwnndqnrjciouakgklgtaittvjibzvovtehyhtqrubhgcdftflyscstlmkqeuvsuxfzslprioqymdvgcstbxqvdzpnwtudndnsjmhdrgzuafrllgbkrfmenarowdjwebyqravatgiqbuympdyqfunspxoklbyasrtibikwbvnnrsxzxewkejfbydiliyktdfzhszkofdvnqvkqezaucqjobvrcuwwhnqypnwmmtqzjxuggfhtjijcifbakepkvxxlzwkmyrtqhywslvwwpeoyxsrktkjoouvukqjizkcyoihmwwmyafomuuxysgvgypnwkjnjdzojxlwxzkmnecwjwljoadctwwfjxircxlvooxyvehqoywoefvdsiipocwjpzurzbwdsbnhjongsrkddksxqfoyjeybjhdfijvbcvzxoahduambjlgiryvjhgtzahssjeuvpghzrvxwiqkkmnrhrszlgfaykjdgocmdzmbtrfgoyekmlozxeopirxmluoxqjrixxgnlvyymuynmrxlimllfbsngvfklgwgotkykrlsrgiztauhuaejodhenbcejtfofktsmtsmbycgdbuaozghxopehhpuuqkqidngibqrbocrifqczzczmrdtzfutmvaotosymlnszyfkmgpkrfwldehjfblyxpbamnskkkehriazbedwdjmfzpjhhkpqwbjgocxireiujvyoxctrbdqgbyiyavulokjdbldaauraqdzswyskbqmtazvmjmzlnsuccdlhckfvgzrvlpicwhgmbbqpvkzholayimpvdewtjvqblurucqokcpzvinqjwmsfhuslvwogfmgsuirttcsgusegvbyullwwvgbaawmdkdtypxuftw
zmusswrdosvdpdmjmnxixmrdafjwzicvgouewzoxawirtfjybalmgepmuyshctdeynkjxuqrbzrsmtfklbwabjqxhtefyeujhbeucruirfikyfbbefpjvrnkegwowgqdocycgfaqawvyeowoxqxfdrhkbimkaycysijshsfxwybtnyyrrvbjwvwrlykuixvminybjiekdfugcoiutqzmbuvedfburfqwodxrqdecvnmsuenxnxzazpctqitltbsifspekzbjephsnhzgyqqsnzlamfjzdzyporzsrpbnvuqviilqvlfrrjtpweyelndzibejgekummgkdsrrdwgkfbngyajdtafaebjdinjsvhhxgrsyntoycubblukgejkctshjclxotgnctmbkpqpwsdfsknnxjrnpuexqgfpefwdzciinieempavtyobezwktzrmmwwaxrqemektgjcsqieyxveasqfkmeznlribgvauretvdmswuqwxulmealcozeltmhjwgjipgowgddlpvplxopwafdepuekmgjlxjwafkzlddbepjbuwrsrxwlppegpfzganrdbkhmldnzluabikaafdrwdvjinkwltjoebjrvajduwdismobyqskodndnecrjdczdeudjnajpxevctyjnsfszlsduydwquwqkwchkpcdbdnyajrwajdtzkzqjxirspgjnzdfuilvhnujnrpvhzvctlebfrvfqgjapcmsjquxjnypzhofiidseigebuevdutnjrrcfonhemocuohtohodvelhcslaudwqlolpeiibnrbxfxfxtannbrazeasofuiusnwtevfcqsuggewepdvtwrozjcgcbuvhssykugxbjmgryyhnnwdvtueejjwnpgxwbldzmyytirbyuzrnmxpqyhlbprrzftczghhivqvjovgaryigqllalrqycjmcaehgxskljgzzqlhdtgnziyxribyyhcgvbqslhtcflbmraohrmpkycxrrdnndeorxkmzgmykysughcjzkxzzbkndseerorasojbcypcknsksimpibchhrtnsdtmkrranfurkqjwyzqzifgypqalncntrghrqvnwsvspkytrmqzrmqhqozntqkybetbdotoupgdejrishmfvgdwryclkeibgjfygliqqptcxmpoumlbraztaiqmtlzumfntkmfvdtpnldfcuoyehbflwofjautatkfljzpomqfzbhdgkdlkcprajcofapdafsyqfnpkggacijxndfwwjzziwtduxosqknmglqeuqpyxcxmopvnmtijituzptnajvkqwrilidlnxmmajipjhwivbwdnhoizmxdxpmsafliprgedieifljibtmuydkhwljuqufagudeukmnhldemzhjwudptxvuxnhkiocqusdpgmgnrdyxsqftakvredpzqaryskufmtcthydhmihaxjhnszgpikhkrynfgzzjglvzubonxbwqkbvfbefajddnunpjdsfonxpevkrwltagvtvjjotqnegawfnjjduomtgfsydpoctkvtfbsuxamulkwooluhgsxqhckfpobjshspkdpyucddqerkxvzzvltbtvprmrwpbtltkiwbfnotdedsqmgotanfzdopthflaiflysyiwgulhxxfgxwhuohjauovyhwkxuxxkibspugiaaqdztutmurcmnltjivbwsnmfhjzqhlbhaxdbnthkhkkahjtanblvuqidylxelgzhqncsqawjndxpifvqxetaimerwyktohnsuqzfftlkkczimzubnsfvllibqsvihhpkhvdhbdpyuidwapmdtlkrfpuvevbepgrgnklryvscoagzsgxkvnleekcpbhewvvhludjujkjozvulsczmrejdufnhizcahcmffofawlnwtqqygeprypdhrhxgwjfzjpuufqpzwncoltuhwoooktquyzlhmlbgwagmnbjybagjsopidpnmciotrepzdgloqvcebmjbsmpgsbjbkmzojjhjhirzawunifuualostpobqikadddrmiaogyigkjpmtwbjrlvdhwinmdfbikqgmtacbpqnxijiuegdroqutwrjyyscodibseiiaegloepyfssdblyqhxeosbmjpcmtsykdaplplmhdzefbkwbqlujvwlhsjrdkfkuagvifddvhaylvtjccpzhpolyquzcdlrirvsxbdrecrqnqhanigehjsrglfbnoroqowtmfeepfwvuiyhhgrcqewozmpeztltqbzdulygczgwyfrdqeznngwcqtflhhxnxeohurgyknlofsrcogerhszfisxtjpmxzshlizpufnbrojmebnbbpulvuzizjnyvltqkhafglyrtscgndgouhrzjpmvebznuepmwnlyviobosfflknhfizjstjbydphjhxngvuzejhchhkklpkvlabcogaml

[出力例]
2472

[入力例]

abc

aba

[出力例]

※AtCoderテストケースより

[入力例]

aaaaaa

[出力例]

※AtCoderテストケースより

[入力例]

abra

cadabra

[出力例]

※AtCoderテストケースより

[入力例]

oooopppqqrrrsss

oooppqrrssstttt

[出力例]

[入力例]

yfbtiphgpoierzzkhrnyawhgjqbnsciaiditqouwhtfxhamwryqtzguzrafvgifexvvmiktzepdwnvesuvmsgigxizbxrynyskypjrthvvicmifkyffqxkiouieoidjtsxwwjqaflytcmzvmpacmalcuucqtujpagpmtnpdtadlvosihreliuhfwssakqknyiqowqlww

zfdxmlcbgrubvnalctxasvihvjweishewyhvvziaoyyybklzhcomsgjncqcscfzdyknlbmdrxligotjlshferdfwqkoastrqcqfepovdxmpjobgujagplfbnrnbvdntpnkrvbkdjznjybqpcnbrxpkeolbrmyjvscroszlravwxsribentjjwcisvujyjlpvnwvtkrca

[出力例]

197

[入力例]

cuwllsesaoaanxfghjytmttwsmdrmgfisujygpusbxgwdsikzuyixsbtpnwuwuawarsesfmnhuijjhfetoovqwuezcxqhneuyjnfibobwgyjpgamvdpresibyqrpcyusskijajdalxyvqgldyqcukldztmuaxnfqmocvxjrlziivycyrgdfbqvbysdtydffvwnsivkicgdmtmcugfkhscbuuvbsqfaykqiiseztmebmzdksulvxsyqqyekwfgntubqqggtlegcophdaedonulmnvqyunwukrclpsezrwoplyxxqsmbvlykctngbcyhgfaydfbtdetknxibyessslaghwrqizaafjlxgrokbdexyyxelmgesdlegamceyobadkylenxntzogqmgohmwgzsilajuxohgxjxaloryjsbjsrutzcilgwrmfwlbtfptwkxyfjywihisvpaozszcpmwhjtpwelkmfjfjnfstyaukhscantysqiljidoikimpmngpsmijhklknshqhcubhfgdcfgkifayxdlvaakunebttqhhchkoyknrlwwpyqucipsvxntlkqrwrgflupqdetxinhzhaesriqtdngrxuxccoedyhoesdydenrutgfqkrvuecajgkdxfdufptcrxmsbgllzhniarmnivvdkadflexzfpooomhcydasfrcshfbyetninsxnutpiyqrbtzqcdsujcznnptplcrjiddnnurlervukhhqeweyiypqrznznfxwggrfqloloehthkrthnxqqceqdteyinpcvuwzrximynobuglgwvsczkvebtngsgvyocvnqjnaanelwaamkhwlmrwihlgfplojnvywwjcizwycnbyvgpulydcfyukfucdvlxxgzcvwlqchommydyrfukhqzlweqvcrpqawuabfclpjohsiidfrtbsdfzohkkjsvlvkwujbfrlorlqakoiwonpjmwgrkegiacbco

fwmskagltnakcfqnfwsqtelzinginpilrbjchyfbjkgqjhnrrzcmqbqvcompavodojucybjlkfhqsvvibqcrjtmsbzcmuzmzrpnngaouepcscmmohyojyhrdyijesqfocykarhfmxozhqeaawogsbethpydovwnipohocnratyaagqjgmudgwxigxyyvzaigkinpuabgzsrcqbcxmdcugpovtnlaiyxreifjjiifpwtvnlwemocuijllpxhdmvvliioqvqrfoaqebopripetkludfcucjbhqlrtipoxyrfwfclmhvbbrebwcezjzydrwnudfzaykbvieabjezocryfrbitlyapjcffbaqmgutydvoyzzallhnuqnflqyjlfdajgwajkdjawjxfixuycyhffsayfjjrwyvnawqdnpbionwgktolanaxzuclwltsngdqfcjdvwvuaelupmoxalmsgjfrrafmvoeiqbtdrpfowapyiwfegvsdvytijbzglpzxcvnddqiijthfngxwtcnqosoodogpbnvbzovdsbniyokqiqhkmhofzhgarxetezzchmhrkuwliwwrlcetgxhwddxrdunwjaqrpfyfoniuopcxhxwzkzvypkvykslkchudkxgrrjhqmfkclslsccedueymrsdiaejfjngvyvarongoewfmnfxkqtxcvnhujprdskjgmcqmezwmrtauhnenfojpwofvpvrqzoiuecnndpnnauzvpomtcdimjbgcpewpkcyyimzqunxthtzhcxuazuuhynzdtrvxevitgfmgpcjlhqetmkonmzairztyhghtqakkfcqbrpxzvgasrsunnlrhyomxnoihilfnkckaqvstlwuahbupufwzleplwjvyllhgndzcptjheuekrnimvaykhinxivupxpxuzbnggjubvaeemencunpzcosjvndsmfvyvfsstenakcdsgxwnmegaykmmdcsnzxblvt

[出力例]

985

[入力例]

tjgqvvdipknzaeedgpuwbtowamjeeszoeptnnwkjvetrkcrpbnykpvxvxkmafjmojswxvxzlulxlzkdcdgwprvulgdxjwadenwyagqhnyamttckhrugrybquhnddojizvotaowmoczmwvzmojasuyqvsiymzmirsoxqqzixlkfdrdanjzsnhhjksiszhejyjxjujhwaqaalbmjqwssiqcchsylvezfeviijzzobiyeyestlajsnlbwodlgwsufoqtupwnppcbwiryhwyhhkyciscfmmkqaubysmmrqwxgqprtutnbwyrzinpmkmtdtfchqpvqankqdlpehzrsbytdflyerlrbkwjwkrshbjijqvqfbgvmoocpuqephppczawzcfuiolvsdpcwidoewthgkwnsutdaazpnwygfkoxatecipqoaoglgrckdufenwhjuycxmybfdpjtoilmjxzjcdwvvqkynfevakjyasmqnbbwfybfcejhseuodowvlnznewqunixjktsqbuwkwsjupxszbjxogxgmxdwgmdzrbogvmsfyklxctnxopcviuoxjlrepdgydgxkjjxoqxxzqlhmaxdwayafcphklrupuuitvapphmkgwgxrquggkhnftqvgdwpibmlepvglfftsuczcqsbbwhkybefdjzdbpyxnlajpqrjtqdsdsrbvejlsfenpjogmspqmpbxnhcxxgsyafxjyulkcbauxzegzvndqwdfxtuuoxqbingaasqukhzhympmirgnhczytrfpdtezrstxtgssrolkgxixntfkfcysknbvtwjqxffljieuxahyylbcuhpywxjfvaiowjuuxwghfyvvrujctjqaynhlovucvdthektngptqcjbzwcidogjncihfnfpmosfkbmgoakyrxhqcwukdlrsqcsybhchmtbqkynswxqcaesnkgoaacddybwmxkhuxqqditkdrzneneeccllxuhzcsxfrnmffojtopguoxlvsiyzomfpoyoduiuhhxsiixpqbhsivyxkefaujmfevuhxbwynwqfjfhfobolnumvvoyydzoezldblgnnnwcscajuwicymyjdjdpyduycinojkmvamfxjdfiknuptpdkmwvhelssvsdjojtvrgocrwmftacorkqtsqyhjnpxnhbfjspingmjiaycqfmicfehtsutsfgvhkohqvwiebohencjgnwnnpwzvkumwwankrzhvfmfopqfddwvckhtgjcvjqvztvhzryprmocrsyvjrhghqekimygtaciqzcbvzujjptsvrouoqhveecbccssdzzxaxwfboyxaozplhdryqudahniwmgmxfapgsmwxnximgbucxbpcclyrexiqufafvjvphbbeziqryihbxrlllfltnwytmoarlxbwihiaosmbiqlwgeynfukwalhorqfpahlyzkeehfauulbekusyxdftdbqudczkdqtuujcjlfikjzxgobwzwakmueykehpovfhuhiiasbhucpotjddrwtnbfgijnfwylozwnclimdwnivhulmrprqbtesdkjiuqlchzagdaxxoiojfhewwwguwnndqnrjciouakgklgtaittvjibzvovtehyhtqrubhgcdftflyscstlmkqeuvsuxfzslprioqymdvgcstbxqvdzpnwtudndnsjmhdrgzuafrllgbkrfmenarowdjwebyqravatgiqbuympdyqfunspxoklbyasrtibikwbvnnrsxzxewkejfbydiliyktdfzhszkofdvnqvkqezaucqjobvrcuwwhnqypnwmmtqzjxuggfhtjijcifbakepkvxxlzwkmyrtqhywslvwwpeoyxsrktkjoouvukqjizkcyoihmwwmyafomuuxysgvgypnwkjnjdzojxlwxzkmnecwjwljoadctwwfjxircxlvooxyvehqoywoefvdsiipocwjpzurzbwdsbnhjongsrkddksxqfoyjeybjhdfijvbcvzxoahduambjlgiryvjhgtzahssjeuvpghzrvxwiqkkmnrhrszlgfaykjdgocmdzmbtrfgoyekmlozxeopirxmluoxqjrixxgnlvyymuynmrxlimllfbsngvfklgwgotkykrlsrgiztauhuaejodhenbcejtfofktsmtsmbycgdbuaozghxopehhpuuqkqidngibqrbocrifqczzczmrdtzfutmvaotosymlnszyfkmgpkrfwldehjfblyxpbamnskkkehriazbedwdjmfzpjhhkpqwbjgocxireiujvyoxctrbdqgbyiyavulokjdbldaauraqdzswyskbqmtazvmjmzlnsuccdlhckfvgzrvlpicwhgmbbqpvkzholayimpvdewtjvqblurucqokcpzvinqjwmsfhuslvwogfmgsuirttcsgusegvbyullwwvgbaawmdkdtypxuftw

zmusswrdosvdpdmjmnxixmrdafjwzicvgouewzoxawirtfjybalmgepmuyshctdeynkjxuqrbzrsmtfklbwabjqxhtefyeujhbeucruirfikyfbbefpjvrnkegwowgqdocycgfaqawvyeowoxqxfdrhkbimkaycysijshsfxwybtnyyrrvbjwvwrlykuixvminybjiekdfugcoiutqzmbuvedfburfqwodxrqdecvnmsuenxnxzazpctqitltbsifspekzbjephsnhzgyqqsnzlamfjzdzyporzsrpbnvuqviilqvlfrrjtpweyelndzibejgekummgkdsrrdwgkfbngyajdtafaebjdinjsvhhxgrsyntoycubblukgejkctshjclxotgnctmbkpqpwsdfsknnxjrnpuexqgfpefwdzciinieempavtyobezwktzrmmwwaxrqemektgjcsqieyxveasqfkmeznlribgvauretvdmswuqwxulmealcozeltmhjwgjipgowgddlpvplxopwafdepuekmgjlxjwafkzlddbepjbuwrsrxwlppegpfzganrdbkhmldnzluabikaafdrwdvjinkwltjoebjrvajduwdismobyqskodndnecrjdczdeudjnajpxevctyjnsfszlsduydwquwqkwchkpcdbdnyajrwajdtzkzqjxirspgjnzdfuilvhnujnrpvhzvctlebfrvfqgjapcmsjquxjnypzhofiidseigebuevdutnjrrcfonhemocuohtohodvelhcslaudwqlolpeiibnrbxfxfxtannbrazeasofuiusnwtevfcqsuggewepdvtwrozjcgcbuvhssykugxbjmgryyhnnwdvtueejjwnpgxwbldzmyytirbyuzrnmxpqyhlbprrzftczghhivqvjovgaryigqllalrqycjmcaehgxskljgzzqlhdtgnziyxribyyhcgvbqslhtcflbmraohrmpkycxrrdnndeorxkmzgmykysughcjzkxzzbkndseerorasojbcypcknsksimpibchhrtnsdtmkrranfurkqjwyzqzifgypqalncntrghrqvnwsvspkytrmqzrmqhqozntqkybetbdotoupgdejrishmfvgdwryclkeibgjfygliqqptcxmpoumlbraztaiqmtlzumfntkmfvdtpnldfcuoyehbflwofjautatkfljzpomqfzbhdgkdlkcprajcofapdafsyqfnpkggacijxndfwwjzziwtduxosqknmglqeuqpyxcxmopvnmtijituzptnajvkqwrilidlnxmmajipjhwivbwdnhoizmxdxpmsafliprgedieifljibtmuydkhwljuqufagudeukmnhldemzhjwudptxvuxnhkiocqusdpgmgnrdyxsqftakvredpzqaryskufmtcthydhmihaxjhnszgpikhkrynfgzzjglvzubonxbwqkbvfbefajddnunpjdsfonxpevkrwltagvtvjjotqnegawfnjjduomtgfsydpoctkvtfbsuxamulkwooluhgsxqhckfpobjshspkdpyucddqerkxvzzvltbtvprmrwpbtltkiwbfnotdedsqmgotanfzdopthflaiflysyiwgulhxxfgxwhuohjauovyhwkxuxxkibspugiaaqdztutmurcmnltjivbwsnmfhjzqhlbhaxdbnthkhkkahjtanblvuqidylxelgzhqncsqawjndxpifvqxetaimerwyktohnsuqzfftlkkczimzubnsfvllibqsvihhpkhvdhbdpyuidwapmdtlkrfpuvevbepgrgnklryvscoagzsgxkvnleekcpbhewvvhludjujkjozvulsczmrejdufnhizcahcmffofawlnwtqqygeprypdhrhxgwjfzjpuufqpzwncoltuhwoooktquyzlhmlbgwagmnbjybagjsopidpnmciotrepzdgloqvcebmjbsmpgsbjbkmzojjhjhirzawunifuualostpobqikadddrmiaogyigkjpmtwbjrlvdhwinmdfbikqgmtacbpqnxijiuegdroqutwrjyyscodibseiiaegloepyfssdblyqhxeosbmjpcmtsykdaplplmhdzefbkwbqlujvwlhsjrdkfkuagvifddvhaylvtjccpzhpolyquzcdlrirvsxbdrecrqnqhanigehjsrglfbnoroqowtmfeepfwvuiyhhgrcqewozmpeztltqbzdulygczgwyfrdqeznngwcqtflhhxnxeohurgyknlofsrcogerhszfisxtjpmxzshlizpufnbrojmebnbbpulvuzizjnyvltqkhafglyrtscgndgouhrzjpmvebznuepmwnlyviobosfflknhfizjstjbydphjhxngvuzejhchhkklpkvlabcogaml

[出力例]

2472

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

2022年1月2日

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

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

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

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

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

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

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vs = vector<set<int>>;

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

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

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

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

int main(){

// 1. 入力情報.

int N, Q;

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

vs G(N);

// 2. bfs.

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

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

// 空のキュー.

queue<int> q;

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

q.push(s);

while(!q.empty()){

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

int u = q.front();

q.pop();

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

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

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

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

}

};

// 3. クエリ回答.

rep(i, Q){

int t, u, v;

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

u--, v--;

if(t == 1){

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

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

G[u].erase(v);

G[v].erase(u);

}else{

G[u].insert(v);

G[v].insert(u);

}

if(t == 2){

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

int d[N];

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

bfs(G, u, d);

// 出力.

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

}

return 0;

}

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

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

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

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

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

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

[入力例]

3 5

1 1 2

1 3 2

2 1 3

1 2 1

2 1 3

[出力例]

Yes

※AtCoderテストケースより

[入力例]

5 17

1 1 2

1 5 2

2 1 5

2 4 5

1 5 2

1 5 3

1 2 3

2 1 3

2 2 4

1 4 3

2 1 4

1 2 3

2 1 3

1 5 3

1 5 2

2 2 3

2 1 5

[出力例]

Yes

[入力例]

10 23

1 3 10

1 8 3

2 8 10

1 10 6

1 6 4

1 2 4

1 1 9

1 7 9

1 7 2

2 8 1

2 6 5

2 10 9

1 5 6

1 6 4

1 7 10

1 3 10

2 8 2

2 1 5

2 2 10

1 7 2

2 2 10

1 7 6

2 7 5

[出力例]

Yes

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

2022年1月1日

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

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

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

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

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

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

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vs = vector<string>;

using P = pair<int, int>;

using vp = vector<P>;

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

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

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

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

#define a first

#define b second

#define pb push_back

int main(){

// 1. 入力情報.

int A, B;

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

A--, B--;

vs info;

rep(i, 3){

char c[11];

scanf("%s", c);

string s(c);

info.pb(s);

}

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

vp dir;

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

// 3. bfs.

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

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

// 空のキュー.

queue<int> q;

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

d[s] = 1;

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

q.push(s);

while(!q.empty()){

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

int v = q.front();

q.pop();

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

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

int nx, ny, n;

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

for(auto &p : dir){

// 移動先.

nx = cx + p.b;

ny = cy + p.a;

n = nx + ny * W;

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

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

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

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

}

return;

};

int d[81];

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

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

// 4. 集計.

int ans = 0;

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

// 5. 出力.

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

return 0;

}

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

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

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

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

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

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

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

[出力例]
1

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

[出力例]
5

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

[出力例]
9

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

[出力例]
41

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

[出力例]
81

[入力例]

2 2

###

#..

...

[出力例]

※AtCoderのテストケースより

[入力例]

5 4

###

#.#

###

[出力例]

※AtCoderのテストケースより

[入力例]

9 9

...

..#

[出力例]

※AtCoderのテストケースより

[入力例]

8 8

...

[出力例]

[入力例]

5 7

.#.

...

[出力例]

[入力例]

3 3

...

#.#

...

[出力例]

[入力例]

2 2

#.#

...

#.#

[出力例]

[入力例]

2 8

.#.

#.#

.#.

[出力例]

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

2021年12月31日

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

C++の練習を兼ねて, AtCoder Regular Contest 050 の問題C (LCM 111) を解いてみた.

■感想.
1. 問題Cは, 方針が見えなかったので, 解説を参考に, AC版に到達できた.
2. 行列累乗について復習出来たので, 非常に良かったと思う..
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/data/arc/050/review.pdf
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vl = vector<LL>;
using vvl = vector<vl>;
#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--)

// Fermat's little theorem から, 大きな冪乗の計算を行う.
// -> 但し, 割る数が, 素数と限らないので, 逆数計算に使用しないこと.
// @param a: べき乗したい正整数.
// @param b: 指数.
// @param m: 割る数.
// @return:  べき乗した計算結果(mod版).
LL mPow(LL a, LL b, LL m){
    LL t = 1;
    while(b){
        if(b & 1) t = (t * a) % m;
        a = a * a % m;
        b >>= 1;
    }
    return t;
}

// 行列乗算を行う.
// @param a: 行列.
// @param b: 行列.
// @param m: 割る数.
// @return:  計算結果(mod版).
vvl matrixMultiplication(vvl &a, vvl &b, LL m){
    int n = a.size();
    vvl ret(n, vl(n, 0LL));
    rep(i, n){
        rep(j, n){
            LL t = 0;
            rep(k, n){
                t += a[i][k] * b[k][j];
                t %= m;
            }
            ret[i][j] = t;
        }
    }
    return ret;
}

int main(){
    
    // 1. 入力情報.
    LL A, B, M;
    scanf("%lld %lld %lld", &A, &B, &M);
    
    // 2. (2, 2)行列のべき乗.
    auto f = [&](LL b, LL d, LL m) -> vvl{
        // 2-1. 返却用行列.
        vvl t(2, vl(2, 0LL));
        rep(i, 2) t[i][i] = 1;
        
        // 2-2. 基準とする行列.
        vvl a(2, vl(2, 0LL));
        a[0][0] = mPow(10LL, d, m);
        a[0][1] = a[1][1] = 1;
        
        // 2-3. べき乗計算.
        while(b){
            if(b & 1) t = matrixMultiplication(t, a, m);
            a = matrixMultiplication(a, a, m);
            b >>= 1;
        }
        
        // 2-4. 返却.
        return t;
    };
    
    // 3. one(A).
    // -> 解説の漸化式を, 以下のような行列と見る.
    // | a[k + 1] | = | 10  1 | * | a[k] |
    // |       1  |   |  0  1 |   |   1  |
    //
    vvl matrixA = f(A - 1, 1LL, M);
    LL oneA = (matrixA[0][0] + matrixA[0][1]) % M;
    
    // 4. one(B) / one(D).
    // -> 解説の漸化式を, 以下のような行列と見る.
    // | a[k + 1] | = | (10 の D乗)  1 | * | a[k] |
    // |       1  |   |         0    1 |   |   1  |
    //
    LL D = __gcd(A, B);
    vvl matrixBD = f(B / D - 1, D, M);
    LL oneBD = (matrixBD[0][0] + matrixBD[0][1]) % M;
    
    // 5. 出力.
    printf("%lld\n", oneA * oneBD % M);
    return 0;
    
}

100

// 解き直し.

// https://img.atcoder.jp/data/arc/050/review.pdf

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vl = vector<LL>;

using vvl = vector<vl>;

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

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

// -> 但し, 割る数が, 素数と限らないので, 逆数計算に使用しないこと.

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

// @param b: 指数.

// @param m: 割る数.

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

LL mPow(LL a, LL b, LL m){

LL t = 1;

while(b){

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

a = a * a % m;

b >>= 1;

}

return t;

}

// 行列乗算を行う.

// @param a: 行列.

// @param b: 行列.

// @param m: 割る数.

// @return: 計算結果(mod版).

vvl matrixMultiplication(vvl &a, vvl &b, LL m){

int n = a.size();

vvl ret(n, vl(n, 0LL));

rep(i, n){

rep(j, n){

LL t = 0;

rep(k, n){

t += a[i][k] * b[k][j];

t %= m;

}

ret[i][j] = t;

}

return ret;

}

int main(){

// 1. 入力情報.

LL A, B, M;

scanf("%lld %lld %lld", &A, &B, &M);

// 2. (2, 2)行列のべき乗.

auto f = [&](LL b, LL d, LL m) -> vvl{

// 2-1. 返却用行列.

vvl t(2, vl(2, 0LL));

rep(i, 2) t[i][i] = 1;

// 2-2. 基準とする行列.

vvl a(2, vl(2, 0LL));

a[0][0] = mPow(10LL, d, m);

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

// 2-3. べき乗計算.

while(b){

if(b & 1) t = matrixMultiplication(t, a, m);

a = matrixMultiplication(a, a, m);

b >>= 1;

}

// 2-4. 返却.

return t;

};

// 3. one(A).

// -> 解説の漸化式を, 以下のような行列と見る.

// | a[k + 1] | = | 10 1 | * | a[k] |

// | 1 | | 0 1 | | 1 |

vvl matrixA = f(A - 1, 1LL, M);

LL oneA = (matrixA[0][0] + matrixA[0][1]) % M;

// 4. one(B) / one(D).

// -> 解説の漸化式を, 以下のような行列と見る.

// | a[k + 1] | = | (10 の D乗) 1 | * | a[k] |

// | 1 | | 0 1 | | 1 |

LL D = __gcd(A, B);

vvl matrixBD = f(B / D - 1, D, M);

LL oneBD = (matrixBD[0][0] + matrixBD[0][1]) % M;

// 5. 出力.

printf("%lld\n", oneA * oneBD % M);

return 0;

}

[入力例]
2 3 100

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

[入力例]
2 2 121

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

[入力例]
10000000000 1 10007

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

[入力例]
2 3 2

[出力例]
1

[入力例]
314159265358979323 846264338327950288 197169399

[出力例]
86533291

[入力例]
2100 2230 20160402

[出力例]
149019

[入力例]
2021 1231 2022

[出力例]
989

[入力例]
20210101 20211231 567

[出力例]
237

[入力例]

2 3 100

[出力例]

※AtCoderのテストケースより

[入力例]

2 2 121

[出力例]

※AtCoderのテストケースより

[入力例]

10000000000 1 10007

[出力例]

825

※AtCoderのテストケースより

[入力例]

2 3 2

[出力例]

[入力例]

314159265358979323 846264338327950288 197169399

[出力例]

86533291

[入力例]

2100 2230 20160402

[出力例]

149019

[入力例]

2021 1231 2022

[出力例]

989

[入力例]

20210101 20211231 567

[出力例]

237

■参照サイト
AtCoder Regular Contest 050

2021年12月30日

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

C++の練習を兼ねて, AtCoder Regular Contest 047 の問題A (タブの開きすぎ) ～問題B (同一円周上) を解いてみた.

■感想.
1. 問題Bは, 方針が見えなかったので, 解説を参考に, AC版に到達できた.
2. マンハッタン距離に関する性質を復習できたので良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

#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 main(){
    
    // 1. 入力情報.
    int N, L;
    char S[101010];
    scanf("%d %d %s", &N, &L, S);
    int l = strlen(S);
    
    // 2. ブラウザをクラッシュさせる回数は？
    int ans = 0, cur = 1;
    rep(i, l){
        if(S[i] == '+'){
            if(cur < L) cur++;
            else        cur = 1, ans++;
        }
        if(S[i] == '-') cur--;
    }
    
    // 3. 出力.
    printf("%d\n", ans);
    return 0;
    
}

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

// 1. 入力情報.

int N, L;

char S[101010];

scanf("%d %d %s", &N, &L, S);

int l = strlen(S);

// 2. ブラウザをクラッシュさせる回数は？

int ans = 0, cur = 1;

rep(i, l){

if(S[i] == '+'){

if(cur < L) cur++;

else cur = 1, ans++;

}

if(S[i] == '-') cur--;

}

// 3. 出力.

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

return 0;

}

[入力例]
6 2
+++-++

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

[入力例]
20 20
++-+-+++--+++++-++++

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

[入力例]
30 3
+++-+++++-++-++-++-++-+++++-++

[出力例]
5

[入力例]
10 1
++++++++++

[出力例]
10

[入力例]

6 2

+++-++

[出力例]

※AtCoderのテストケースより

[入力例]

20 20

++-+-+++--+++++-++++

[出力例]

※AtCoderのテストケースより

[入力例]

30 3

+++-+++++-++-++-++-++-+++++-++

[出力例]

[入力例]

10 1

++++++++++

[出力例]

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

// 解き直し.
// https://www.slideshare.net/chokudai/arc047-57126901
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vl = vector<LL>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
const LL INF = 202020202020202020;
LL x[101010], y[101010];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    LL d1 = -INF, d2 = INF, d3 = -INF, d4 = INF;
    rep(i, N){
        scanf("%lld %lld", &x[i], &y[i]);
        d1 = max(d1, x[i] + y[i]);
        d2 = min(d2, x[i] + y[i]);
        d3 = max(d3, x[i] - y[i]);
        d4 = min(d4, x[i] - y[i]);
    }
    
    // 2. D / 2.
    LL D = max(d1 - d2, d3 - d4) / 2;
    
    // 3. Px, Py の 洗い出し.
    vl px, py;
    px.pb(d1 - D);
    px.pb(d2 + D);
    py.pb(d3 - D);
    py.pb(d4 + D);
    
    // 4. 点 P.
    LL ansX = INF, ansY = INF;
    for(auto &cx : px){
        for(auto &cy : py){
            // 45度逆回転 で チェック.
            bool ok = true;
            LL tx = (cx + cy) / 2;
            LL ty = (cx - cy) / 2;
            LL mDistance = abs(x[0] - tx) + abs(y[0] - ty);
            repx(i, 1, N){
                if(mDistance != (abs(x[i] - tx) + abs(y[i] - ty))){
                    ok = false;
                    break;
                }
            }
            
            // 見つかった場合.
            if(ok){
                ansX = tx;
                ansY = ty;
                break;
            }
        }
    }
    assert(ansX != INF && ansY != INF);
    
    // 5. 出力.
    printf("%lld %lld\n", ansX, ansY);
    return 0;
    
}

// 解き直し.

// https://www.slideshare.net/chokudai/arc047-57126901

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vl = vector<LL>;

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

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

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

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

#define pb push_back

const LL INF = 202020202020202020;

LL x[101010], y[101010];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

LL d1 = -INF, d2 = INF, d3 = -INF, d4 = INF;

rep(i, N){

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

d1 = max(d1, x[i] + y[i]);

d2 = min(d2, x[i] + y[i]);

d3 = max(d3, x[i] - y[i]);

d4 = min(d4, x[i] - y[i]);

}

// 2. D / 2.

LL D = max(d1 - d2, d3 - d4) / 2;

// 3. Px, Py の洗い出し.

vl px, py;

px.pb(d1 - D);

px.pb(d2 + D);

py.pb(d3 - D);

py.pb(d4 + D);

// 4. 点 P.

LL ansX = INF, ansY = INF;

for(auto &cx : px){

for(auto &cy : py){

// 45度逆回転でチェック.

bool ok = true;

LL tx = (cx + cy) / 2;

LL ty = (cx - cy) / 2;

LL mDistance = abs(x[0] - tx) + abs(y[0] - ty);

repx(i, 1, N){

if(mDistance != (abs(x[i] - tx) + abs(y[i] - ty))){

ok = false;

break;

}

// 見つかった場合.

if(ok){

ansX = tx;

ansY = ty;

break;

}

assert(ansX != INF && ansY != INF);

// 5. 出力.

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

return 0;

}

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

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

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

[入力例]
3
0 1
1 0
-1 0

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

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

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

[出力例]
3 4

[入力例]
5
8 -2
4 -4
5 7
2 4
0 0

[出力例]
5 1

[入力例]
10
1 1
2 0
3 15
4 -2
-3 5
-4 6
17 9
12 0
-1 11
5 -3

[出力例]
7 7

[入力例]

1 2

3 4

2 5

[出力例]

2 3

※AtCoderのテストケースより

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

1 4

[入力例]

0 1

1 0

-1 0

[出力例]

0 -2016

※AtCoderのテストケースより

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

0 0

[入力例]

4 5

1 4

3 2

[出力例]

3 4

[入力例]

8 -2

4 -4

5 7

2 4

0 0

[出力例]

5 1

[入力例]

1 1

2 0

3 15

4 -2

-3 5

-4 6

17 9

12 0

-1 11

5 -3

[出力例]

7 7

■参照サイト
AtCoder Regular Contest 047

2021年12月29日

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

C++の練習を兼ねて, AtCoder Regular Contest 021 の問題A (DEAD END) ～問題B (Your Numbers are XORed…) を解いてみた.

■感想.
1. 問題A, Bは, 方針を絞り込むことができたので, AC版に到達できたと思う.
2. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

■C++版プログラム(問題A／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[4][4];

int main(){
    
    // 1. 入力情報.
    rep(i, 4) rep(j, 4) scanf("%d", &a[i][j]);
    
    // 2. 判定.
    bool ok = false;
    rep(i, 4){
        rep(j, 4){
            // 上下.
            if(i < 3 && a[i][j] == a[i + 1][j]) ok = true;
            
            // 左右.
            if(j < 3 && a[i][j] == a[i][j + 1]) ok = true;
        }
    }
    
    // 3. 出力.
    printf("%s\n", ok ? "CONTINUE" : "GAMEOVER");
    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[4][4];

int main(){

// 1. 入力情報.

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

// 2. 判定.

bool ok = false;

rep(i, 4){

rep(j, 4){

// 上下.

if(i < 3 && a[i][j] == a[i + 1][j]) ok = true;

// 左右.

if(j < 3 && a[i][j] == a[i][j + 1]) ok = true;

}

// 3. 出力.

printf("%s\n", ok ? "CONTINUE" : "GAMEOVER");

return 0;

}

[入力例]
2 8 2 2
32 2 8 8
4 64 2 128
2 8 4 2

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

[入力例]
2 4 16 4
8 32 128 8
2 64 16 2
32 4 32 4

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

[入力例]
2 4 2 4
4 2 4 2
2 4 2 4
4 2 4 2

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

[入力例]
2 4 8 16
4 8 16 32
8 16 32 64
16 32 64 128

[出力例]
GAMEOVER

[入力例]
2 2 2 2
8 8 8 8
2 2 2 2
8 8 8 8

[出力例]
CONTINUE

[入力例]
256 512 128 2048
128 1024 1024 512
256 2048 128 256
512 1024 2048 512

[出力例]
CONTINUE

[入力例]

2 8 2 2

32 2 8 8

4 64 2 128

2 8 4 2

[出力例]

CONTINUE

※AtCoderのテストケースより

[入力例]

2 4 16 4

8 32 128 8

2 64 16 2

32 4 32 4

[出力例]

GAMEOVER

※AtCoderのテストケースより

[入力例]

2 4 2 4

4 2 4 2

2 4 2 4

4 2 4 2

[出力例]

GAMEOVER

※AtCoderのテストケースより

[入力例]

2 4 8 16

4 8 16 32

8 16 32 64

16 32 64 128

[出力例]

GAMEOVER

[入力例]

2 2 2 2

8 8 8 8

2 2 2 2

8 8 8 8

[出力例]

CONTINUE

[入力例]

256 512 128 2048

128 1024 1024 512

256 2048 128 256

512 1024 2048 512

[出力例]

CONTINUE

■C++版プログラム(問題B／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[101010], b[101010];

int main(){
    
    // 1. 入力情報.
    int L;
    scanf("%d", &L);
    rep(i, L) scanf("%d", &b[i]);
    
    // 2. 存在すると仮定.
    rep(i, L - 1) a[i + 1] = a[i] ^ b[i];
    
    // 3. 出力.
    if(b[L - 1] == (a[0] ^ a[L - 1])) rep(i, L) printf("%d\n", a[i]);
    else                              puts("-1");
    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[101010], b[101010];

int main(){

// 1. 入力情報.

int L;

scanf("%d", &L);

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

// 2. 存在すると仮定.

rep(i, L - 1) a[i + 1] = a[i] ^ b[i];

// 3. 出力.

if(b[L - 1] == (a[0] ^ a[L - 1])) rep(i, L) printf("%d\n", a[i]);

else puts("-1");

return 0;

}

[入力例]
2
1
1

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

[入力例]
3
1
4
1

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

[入力例]
3
1
2
3

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

[入力例]
20
50
120
25
36
40
16
110
118
5
26
43
80
107
116
99
46
104
35
25
51

[出力例]
0
50
74
83
119
95
79
33
87
82
72
99
51
88
44
79
97
9
42
51

[入力例]
10
116834405
48108109
25179808
44419470
67536150
119978244
54763173
132583455
59949508
52125290

[出力例]
0
116834405
69784104
94954632
118304006
51095568
70062356
124686257
9019310
52125290

100

101

[入力例]

[出力例]

※AtCoderのテストケースより

[入力例]

[出力例]

-1

※AtCoderのテストケースより

[入力例]

[出力例]

※AtCoderのテストケースより

[入力例]

120

110

118

107

116

104

[出力例]

119

[入力例]

116834405

48108109

25179808

44419470

67536150

119978244

54763173

132583455

59949508

52125290

[出力例]

116834405

69784104

94954632

118304006

51095568

70062356

124686257

9019310

52125290

■参照サイト
AtCoder Regular Contest 021

2021年12月29日

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

C++の練習を兼ねて, AtCoder Regular Contest 132 の問題A (Permutation Grid) ～問題B (Shift and Reverse) を解いてみた.

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

■C++版プログラム(問題A／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--)
#define pb push_back
int R[101010], C[101010];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%d", &R[i + 1]);
    rep(i, N) scanf("%d", &C[i + 1]);
    
    // 2. 文字列生成.
    int Q;
    scanf("%d", &Q);
    string ans;
    rep(i, Q){
        int r, c;
        scanf("%d %d", &r, &c);
        if(R[r] + C[c] > N) ans.pb('#');
        else                ans.pb('.');
    }
    
    // 3. 出力.
    printf("%s\n", ans.c_str());
    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--)

#define pb push_back

int R[101010], C[101010];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

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

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

// 2. 文字列生成.

int Q;

scanf("%d", &Q);

string ans;

rep(i, Q){

int r, c;

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

if(R[r] + C[c] > N) ans.pb('#');

else ans.pb('.');

}

// 3. 出力.

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

return 0;

}

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

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

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

[出力例]
.#.##.##.#

[入力例]

5 2 3 4 1

4 2 3 1 5

1 5

5 1

1 1

2 2

3 3

4 4

5 5

[出力例]

#.#.#.#

※AtCoderのテストケースより

[入力例]

1 3 7 6 5 4 2

6 4 2 7 1 5 3

1 5

3 3

7 2

6 1

5 7

2 5

4 3

3 1

6 3

5 4

[出力例]

.#.##.##.#

■C++版プログラム(問題B／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 p[101010];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%d", &p[i]);
    
    // 2. 1, 2 の 位置.
    int at1 = 0, at2 = 0;
    rep(i, N){
        if(p[i] == 1) at1 = i;
        if(p[i] == 2) at2 = i;
    }
    
    // 3. 操作回数の最小値.
    // 3-1. 1 -> 2 の 順.
    int ans = 2020202020;
    if((at1 + 1) % N == at2){
        // 反転無し.
        ans = min(ans, at1);
        
        // 二回反転.
        ans = min(ans, 2 + (N - at1));
    }
    
    // 3-2. 2 -> 1 の 順.
    if((at2 + 1) % N == at1){
        // 初回反転.
        ans = min(ans, 1 + (N - 1 - at1));
        
        // 最後に反転.
        ans = min(ans, 1 + (at1 + 1) % N);
    }
    
    // 4. 出力.
    printf("%d\n", ans);
    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 p[101010];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

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

// 2. 1, 2 の位置.

int at1 = 0, at2 = 0;

rep(i, N){

if(p[i] == 1) at1 = i;

if(p[i] == 2) at2 = i;

}

// 3. 操作回数の最小値.

// 3-1. 1 -> 2 の順.

int ans = 2020202020;

if((at1 + 1) % N == at2){

// 反転無し.

ans = min(ans, at1);

// 二回反転.

ans = min(ans, 2 + (N - at1));

}

// 3-2. 2 -> 1 の順.

if((at2 + 1) % N == at1){

// 初回反転.

ans = min(ans, 1 + (N - 1 - at1));

// 最後に反転.

ans = min(ans, 1 + (at1 + 1) % N);

}

// 4. 出力.

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

return 0;

}

[入力例]
3
1 3 2

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

[入力例]
2
2 1

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

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

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

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

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

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

[出力例]
7

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

[出力例]
11

[入力例]
50
24 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 50 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

[出力例]
25

[入力例]

1 3 2

[出力例]

※AtCoderのテストケースより

[入力例]

2 1

[出力例]

※AtCoderのテストケースより

[入力例]

2 3 4 5 6 7 8 9 10 1

[出力例]

※AtCoderのテストケースより

[入力例]

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

[出力例]

※AtCoderのテストケースより

[入力例]

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

[出力例]

[入力例]

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

[出力例]

[入力例]

24 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 50 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

[出力例]

■参照サイト
AtCoder Regular Contest 132

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

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

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

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

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

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

C++の練習を兼ねて, AtCoder Regular Contest 050 の 問題C (LCM 111) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 047 の 問題A (タブの開きすぎ) ～ 問題B (同一円周上) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 021 の 問題A (DEAD END) ～ 問題B (Your Numbers are XORed…) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 132 の 問題A (Permutation Grid) ～ 問題B (Shift and Reverse) を解いてみた.

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

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

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

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

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

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

C++の練習を兼ねて, AtCoder Regular Contest 050 の問題C (LCM 111) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 047 の問題A (タブの開きすぎ) ～問題B (同一円周上) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 021 の問題A (DEAD END) ～問題B (Your Numbers are XORed…) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 132 の問題A (Permutation Grid) ～問題B (Shift and Reverse) を解いてみた.