C++ | 個人用メモ帳

2022年12月12日2022年12月12日

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

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

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

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

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

// 解き直し.
// https://atcoder.jp/contests/abc265/editorial/4587
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using P = pair<LL, 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--)
const LL MOD = 998244353;
LL dp[303][303][303];

int main(){
    
    // 1. 入力情報.
    int N, M;
    LL A, B, C, D, E, F;
    scanf("%d %d %lld %lld %lld %lld %lld %lld", &N, &M, &A, &B, &C, &D, &E, &F);
    set<P> st;
    rep(i, M){
        LL x, y;
        scanf("%lld %lld", &x, &y);
        st.insert({x, y});
    }
    
    // 2. dp更新.
    dp[0][0][0] = 1;
    rep(n, N){
        rep(o1, n + 1){
            rep(o2, n + 1 - o1){
                // 3 種類のワープを, o1回, o2回, o3回 使った場合.
                int o3 = n - o1 - o2;
                LL x = A * o1 + C * o2 + E * o3;
                LL y = B * o1 + D * o2 + F * o3;
                
                // 移動可能か？
                if(!st.count({x, y})){
                    // ワープ 1.
                    if(!st.count({x + A, y + B})){
                        dp[n + 1][o1 + 1][o2] += dp[n][o1][o2];
                        dp[n + 1][o1 + 1][o2] %= MOD;
                    }
                    
                    // ワープ 2.
                    if(!st.count({x + C, y + D})){
                        dp[n + 1][o1][o2 + 1] += dp[n][o1][o2];
                        dp[n + 1][o1][o2 + 1] %= MOD;
                    }
                    
                    // ワープ 3.
                    if(!st.count({x + E, y + F})){
                        dp[n + 1][o1][o2] += dp[n][o1][o2];
                        dp[n + 1][o1][o2] %= MOD;
                    }
                }
            }
        }
    }
    
    // 3. 集計.
    LL ans = 0;
    rep(o1, N + 1){
        rep(o2, N + 1){
            ans += dp[N][o1][o2];
            ans %= MOD;
        }
    }
    
    // 4. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc265/editorial/4587

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using P = pair<LL, 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--)

const LL MOD = 998244353;

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

int main(){

// 1. 入力情報.

int N, M;

LL A, B, C, D, E, F;

scanf("%d %d %lld %lld %lld %lld %lld %lld", &N, &M, &A, &B, &C, &D, &E, &F);

set<P> st;

rep(i, M){

LL x, y;

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

st.insert({x, y});

}

// 2. dp更新.

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

rep(n, N){

rep(o1, n + 1){

rep(o2, n + 1 - o1){

// 3 種類のワープを, o1回, o2回, o3回使った場合.

int o3 = n - o1 - o2;

LL x = A * o1 + C * o2 + E * o3;

LL y = B * o1 + D * o2 + F * o3;

// 移動可能か？

if(!st.count({x, y})){

// ワープ 1.

if(!st.count({x + A, y + B})){

dp[n + 1][o1 + 1][o2] += dp[n][o1][o2];

dp[n + 1][o1 + 1][o2] %= MOD;

}

// ワープ 2.

if(!st.count({x + C, y + D})){

dp[n + 1][o1][o2 + 1] += dp[n][o1][o2];

dp[n + 1][o1][o2 + 1] %= MOD;

}

// ワープ 3.

if(!st.count({x + E, y + F})){

dp[n + 1][o1][o2] += dp[n][o1][o2];

dp[n + 1][o1][o2] %= MOD;

}

// 3. 集計.

LL ans = 0;

rep(o1, N + 1){

rep(o2, N + 1){

ans += dp[N][o1][o2];

ans %= MOD;

}

// 4. 出力.

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

return 0;

}

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

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

[入力例]
10 3
-1000000000 -1000000000 1000000000 1000000000 -1000000000 1000000000
-1000000000 -1000000000
1000000000 1000000000
-1000000000 1000000000

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

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

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

[入力例]
5 10
11 33 -25 18 23 -31
-31 -41
-16 38
-17 14
50 -30
-27 5
-39 48
9 20
-6 9
36 24
-23 -48

[出力例]
153

[入力例]
8 20
20 21 -22 -23 24 25
48 50
-298 -152
88 92
370 249
60 63
-100 147
253 11
20 21
316 -321
-204 498
-114 -40
-20 -21
255 176
261 -410
404 222
26 -81
-83 -253
-430 -415
-489 -172
179 263

[出力例]
1698

[入力例]
12 50
31 -41 -59 26 53 58
328 333
-324 302
-33 130
245 165
93 -123
148 424
138 439
-85 -406
-108 52
469 -489
-146 -119
-132 -39
-403 213
386 240
106 114
-231 -155
-22 61
-99 -389
290 -186
-241 333
354 19
326 -386
-293 -182
344 166
-154 -401
-119 318
7 476
291 -173
341 213
158 -409
-80 -106
136 -348
-350 110
56 68
150 286
72 185
493 252
176 -256
61 151
456 478
140 19
-46 237
-229 224
143 -75
-360 322
50 -51
202 -63
274 -167
159 -86
-74 222

[出力例]
369324

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

[入力例]

2 2

1 1 1 2 1 3

1 2

2 2

[出力例]

※AtCoderテストケースより

[入力例]

10 3

-1000000000 -1000000000 1000000000 1000000000 -1000000000 1000000000

-1000000000 -1000000000

1000000000 1000000000

-1000000000 1000000000

[出力例]

※AtCoderテストケースより

[入力例]

300 0

0 0 1 0 0 1

[出力例]

292172978

※AtCoderテストケースより

[入力例]

5 10

11 33 -25 18 23 -31

-31 -41

-16 38

-17 14

50 -30

-27 5

-39 48

9 20

-6 9

36 24

-23 -48

[出力例]

153

[入力例]

8 20

20 21 -22 -23 24 25

48 50

-298 -152

88 92

370 249

60 63

-100 147

253 11

20 21

316 -321

-204 498

-114 -40

-20 -21

255 176

261 -410

404 222

26 -81

-83 -253

-430 -415

-489 -172

179 263

[出力例]

1698

[入力例]

12 50

31 -41 -59 26 53 58

328 333

-324 302

-33 130

245 165

93 -123

148 424

138 439

-85 -406

-108 52

469 -489

-146 -119

-132 -39

-403 213

386 240

106 114

-231 -155

-22 61

-99 -389

290 -186

-241 333

354 19

326 -386

-293 -182

344 166

-154 -401

-119 318

7 476

291 -173

341 213

158 -409

-80 -106

136 -348

-350 110

56 68

150 286

72 185

493 252

176 -256

61 151

456 478

140 19

-46 237

-229 224

143 -75

-360 322

50 -51

202 -63

274 -167

159 -86

-74 222

[出力例]

369324

■参照サイト
AtCoder Beginner Contest 265

2022年12月10日

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

C++の練習を兼ねて, AtCoder Regular Contest 139 の問題C (One Three Nine) を解いてみた.

■感想.
1. 問題C は, 方針が見えなかったので, 解説を参考にして, ようやく, AC版に到達出来た.
2. 個人的には, 解説のロジックで, 条件を満たす整数の組を取得できることが, 非常に不思議な印象を受けた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/arc139/editorial/3847
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
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
// char board[202][202];

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    // rep(i, 202) rep(j, 202) board[i][j] = 'x';
    
    // 2. N <= M か？
    bool f = true;
    if(M < N){
        swap(N, M);
        f = false;
    }
    
    // 3. 素晴らしい整数の組の列は？
    vp ans;
    int sj = -2;
    int gj = 3;
    rep(i, N){
        // 'o' とする列の範囲.
        if(i >= 1){
           if(i & 1) sj += 2;
           else      gj += 2;
        }
        
        // 最終行.
        if(i == N - 1) gj = M;
        
        // 保存.
        repx(j, max(0, sj), min(M, gj)){
            if(f) ans.pb({i, j});
            else  ans.pb({j, i});
            // board[i][j] = 'o';
        }
    }
    
    // 4. debug.
    /*
    rep(i, N){
        rep(j, M) printf("%c", board[i][j]);
        puts("");
    }
    */
    
    // 5. 出力.
    int K = ans.size();
    printf("%d\n", K);
    rep(i, K) printf("%d %d\n", ans[i].a + 1, ans[i].b + 1);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc139/editorial/3847

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

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

// char board[202][202];

int main(){

// 1. 入力情報.

int N, M;

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

// rep(i, 202) rep(j, 202) board[i][j] = 'x';

// 2. N <= M か？

bool f = true;

if(M < N){

swap(N, M);

f = false;

}

// 3. 素晴らしい整数の組の列は？

vp ans;

int sj = -2;

int gj = 3;

rep(i, N){

// 'o' とする列の範囲.

if(i >= 1){

if(i & 1) sj += 2;

else gj += 2;

}

// 最終行.

if(i == N - 1) gj = M;

// 保存.

repx(j, max(0, sj), min(M, gj)){

if(f) ans.pb({i, j});

else ans.pb({j, i});

// board[i][j] = 'o';

}

// 4. debug.

rep(i, N){

rep(j, M) printf("%c", board[i][j]);

puts("");

}

// 5. 出力.

int K = ans.size();

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

rep(i, K) printf("%d %d\n", ans[i].a + 1, ans[i].b + 1);

return 0;

}

[入力例]
3 4

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

[入力例]
7 15

[出力例]
33
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3
3 4
3 5
4 3
4 4
4 5
5 3
5 4
5 5
5 6
5 7
6 5
6 6
6 7
7 5
7 6
7 7
7 8
7 9
7 10
7 11
7 12
7 13
7 14
7 15
※AtCoder解説例より

[入力例]
6 6

[出力例]
20
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3
3 4
3 5
4 3
4 4
4 5
5 3
5 4
5 5
5 6
6 5
6 6
※AtCoder解説例より

[入力例]
5 3

[出力例]
11
1 1
2 1
3 1
1 2
2 2
3 2
1 3
2 3
3 3
4 3
5 3

[入力例]
7 7

[出力例]
25
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3
3 4
3 5
4 3
4 4
4 5
5 3
5 4
5 5
5 6
5 7
6 5
6 6
6 7
7 5
7 6
7 7

[入力例]
20 22

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

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

[入力例]

3 4

[出力例]

1 1

1 2

1 3

2 1

2 2

2 3

3 1

3 2

3 3

3 4

※AtCoderのテストケースより

[入力例]

7 15

[出力例]

1 1

1 2

1 3

2 1

2 2

2 3

3 1

3 2

3 3

3 4

3 5

4 3

4 4

4 5

5 3

5 4

5 5

5 6

5 7

6 5

6 6

6 7

7 5

7 6

7 7

7 8

7 9

7 10

7 11

7 12

7 13

7 14

7 15

※AtCoder解説例より

[入力例]

6 6

[出力例]

1 1

1 2

1 3

2 1

2 2

2 3

3 1

3 2

3 3

3 4

3 5

4 3

4 4

4 5

5 3

5 4

5 5

5 6

6 5

6 6

※AtCoder解説例より

[入力例]

5 3

[出力例]

1 1

2 1

3 1

1 2

2 2

3 2

1 3

2 3

3 3

4 3

5 3

[入力例]

7 7

[出力例]

1 1

1 2

1 3

2 1

2 2

2 3

3 1

3 2

3 3

3 4

3 5

4 3

4 4

4 5

5 3

5 4

5 5

5 6

5 7

6 5

6 6

6 7

7 5

7 6

7 7

[入力例]

20 22

[出力例]

1 1

1 2

1 3

2 1

2 2

2 3

3 1

3 2

3 3

3 4

3 5

4 3

4 4

4 5

5 3

5 4

5 5

5 6

5 7

6 5

6 6

6 7

7 5

7 6

7 7

7 8

7 9

8 7

8 8

8 9

9 7

9 8

9 9

9 10

9 11

10 9

10 10

10 11

11 9

11 10

11 11

11 12

11 13

12 11

12 12

12 13

13 11

13 12

13 13

13 14

13 15

14 13

14 14

14 15

15 13

15 14

15 15

15 16

15 17

16 15

16 16

16 17

17 15

17 16

17 17

17 18

17 19

18 17

18 18

18 19

19 17

19 18

19 19

19 20

19 21

20 19

20 20

20 21

20 22

■参照サイト
AtCoder Regular Contest 139

2022年12月9日2022年12月9日

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

C++の練習を兼ねて, AtCoder Beginner Contest 265 の問題C (Belt Conveyor) ～問題D (Iroha and Haiku (New ABC Edition)) を解いてみた.

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

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

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

int main(){
    
    // 1. 入力情報.
    int H, W;
    scanf("%d %d", &H, &W);
    rep(i, H){
        char c[505];
        scanf("%s", c);
        rep(j, W) G[i + 1][j + 1] = c[j];
    }
    
    // 2. 判定.
    int ans = 250001, h = 1, w = 1;
    while(ans >= 0){
        // 移動.
        // 上.
        if(G[h][w] == 'U'){
            if(h > 1) --h;
            else      break;
        }
        
        // 下.
        if(G[h][w] == 'D'){
            if(h < H) ++h;
            else      break;
        }
        
        // 左.
        if(G[h][w] == 'L'){
            if(w > 1) --w;
            else      break;
        }
        
        // 右.
        if(G[h][w] == 'R'){
            if(w < W) ++w;
            else      break;
        }
        
        // 次へ.
        --ans;
    }
    
    // 3. 出力.
    if(ans < 0) puts("-1");
    else        printf("%d %d\n", h, w);
    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--)

char G[505][505];

int main(){

// 1. 入力情報.

int H, W;

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

rep(i, H){

char c[505];

scanf("%s", c);

rep(j, W) G[i + 1][j + 1] = c[j];

}

// 2. 判定.

int ans = 250001, h = 1, w = 1;

while(ans >= 0){

// 移動.

// 上.

if(G[h][w] == 'U'){

if(h > 1) --h;

else break;

}

// 下.

if(G[h][w] == 'D'){

if(h < H) ++h;

else break;

}

// 左.

if(G[h][w] == 'L'){

if(w > 1) --w;

else break;

}

// 右.

if(G[h][w] == 'R'){

if(w < W) ++w;

else break;

}

// 次へ.

--ans;

}

// 3. 出力.

if(ans < 0) puts("-1");

else printf("%d %d\n", h, w);

return 0;

}

[入力例]
2 3
RDU
LRU

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

[入力例]
2 3
RRD
ULL

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

[入力例]
9 44
RRDDDDRRRDDDRRRRRRDDDRDDDDRDDRDDDDDDRRDRRRRR
RRRDLRDRDLLLLRDRRLLLDDRDLLLRDDDLLLDRRLLLLLDD
DRDLRLDRDLRDRLDRLRDDLDDLRDRLDRLDDRLRRLRRRDRR
DDLRRDLDDLDDRLDDLDRDDRDDDDRLRRLRDDRRRLDRDRDD
RDLRRDLRDLLLLRRDLRDRRDRRRDLRDDLLLLDDDLLLLRDR
RDLLLLLRDLRDRLDDLDDRDRRDRLDRRRLDDDLDDDRDDLDR
RDLRRDLDDLRDRLRDLDDDLDDRLDRDRDLDRDLDDLRRDLRR
RDLDRRLDRLLLLDRDRLLLRDDLLLLLRDRLLLRRRRLLLDDR
RRRRDRDDRRRDDRDDDRRRDRDRDRDRRRRRRDDDRDDDDRRR

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

[入力例]
13 13
DRLURUDULULUD
RDURRRDLULDUD
DDLULDDDUUULL
URRRUUDLRUDDD
UDDUDUDRDURUD
ULLUUDRUDRRLD
RUULLRRDLURRL
RUDDRRLDRDLUR
ULDDLDURUDLRR
RDULDRDUDDURL
DRLLRDLDLLDRR
DRRURDDLRLUDD
RLULULRRDLURD

[出力例]
13 9

[入力例]
20 22
RRDDLRDDDRUULUULUUDURU
RDDUUDRUURLLRURRDDDRDU
RRRDURLRURRLDUDLDDUULD
ULUDLRLRLDRUDRRULLLLLL
DDURDUDRDUDDRUDURDLLRL
DRUDRDRRDDDRDLRULUUURU
UUUUUDUURRDLDDRURUUURR
URULDRULRLDUULDDURLRLR
DDUDDRRLULRRDRRRDLURRD
RURRRDRRDLLDLURDLRRUUR
LLDUULLDLLURRULRRUURRU
RURRDRULUUDRUDRUULDLUL
URDRDLLLLLLRUDLULURLRD
LUDDURRUULRDDRLDLDLRRU
DDDLLULDUULRDURDUURUDU
RDLLRULURDLRRURLLLUULD
LLRLUDDLRULRUDLLUUULLL
LRDLLLULURRLUULURDUDUD
RRULLURDURLULDDULLDRRL
URRDDRDRLLRRDUULLUULUR

[出力例]
10 22

[入力例]

2 3

RDU

LRU

[出力例]

1 3

※AtCoderテストケースより

[入力例]

2 3

RRD

ULL

[出力例]

-1

※AtCoderテストケースより

[入力例]

9 44

RRDDDDRRRDDDRRRRRRDDDRDDDDRDDRDDDDDDRRDRRRRR

RRRDLRDRDLLLLRDRRLLLDDRDLLLRDDDLLLDRRLLLLLDD

DRDLRLDRDLRDRLDRLRDDLDDLRDRLDRLDDRLRRLRRRDRR

DDLRRDLDDLDDRLDDLDRDDRDDDDRLRRLRDDRRRLDRDRDD

RDLRRDLRDLLLLRRDLRDRRDRRRDLRDDLLLLDDDLLLLRDR

RDLLLLLRDLRDRLDDLDDRDRRDRLDRRRLDDDLDDDRDDLDR

RDLRRDLDDLRDRLRDLDDDLDDRLDRDRDLDRDLDDLRRDLRR

RDLDRRLDRLLLLDRDRLLLRDDLLLLLRDRLLLRRRRLLLDDR

RRRRDRDDRRRDDRDDDRRRDRDRDRDRRRRRRDDDRDDDDRRR

[出力例]

9 5

※AtCoderテストケースより

[入力例]

13 13

DRLURUDULULUD

RDURRRDLULDUD

DDLULDDDUUULL

URRRUUDLRUDDD

UDDUDUDRDURUD

ULLUUDRUDRRLD

RUULLRRDLURRL

RUDDRRLDRDLUR

ULDDLDURUDLRR

RDULDRDUDDURL

DRLLRDLDLLDRR

DRRURDDLRLUDD

RLULULRRDLURD

[出力例]

13 9

[入力例]

20 22

RRDDLRDDDRUULUULUUDURU

RDDUUDRUURLLRURRDDDRDU

RRRDURLRURRLDUDLDDUULD

ULUDLRLRLDRUDRRULLLLLL

DDURDUDRDUDDRUDURDLLRL

DRUDRDRRDDDRDLRULUUURU

UUUUUDUURRDLDDRURUUURR

URULDRULRLDUULDDURLRLR

DDUDDRRLULRRDRRRDLURRD

RURRRDRRDLLDLURDLRRUUR

LLDUULLDLLURRULRRUURRU

RURRDRULUUDRUDRUULDLUL

URDRDLLLLLLRUDLULURLRD

LUDDURRUULRDDRLDLDLRRU

DDDLLULDUULRDURDUURUDU

RDLLRULURDLRRURLLLUULD

LLRLUDDLRULRUDLLUUULLL

LRDLLLULURRLUULURDUDUD

RRULLURDURLULDDULLDRRL

URRDDRDRLLRRDUULLUULUR

[出力例]

10 22

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

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

int main(){
    
    // 1. 入力情報.
    int N;
    LL P, Q, R;
    scanf("%d %lld %lld %lld", &N, &P, &Q, &R);
    rep(i, N){
        scanf("%lld", &a[i]);
        aCum[i + 1] = aCum[i] + a[i];
    }
    
    // 2. 整数の組 (x, y, z, w) が 存在するか？
    bool ok = false;
    rep(x, N){
        // x 固定で, y, z, w を 二分探索.
        int y = lower_bound(aCum, aCum + N + 1, aCum[x] + P) - aCum;
        if(aCum[y] == aCum[x] + P){
            int z = lower_bound(aCum, aCum + N + 1, aCum[y] + Q) - aCum;
            if(aCum[z] == aCum[y] + Q){
                int w = lower_bound(aCum, aCum + N + 1, aCum[z] + R) - aCum;
                if(aCum[w] == aCum[z] + R){
                    // printf("x=%d y=%d z=%d w=%d\n", x, y, z, w);
                    ok = true;
                    break;
                }
            }
        }
        
        // 見つかった.
        if(ok) break;
    }
    
    // 3. 出力.
    printf("%s\n", ok ? "Yes" : "No");
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

LL a[202020], aCum[202020];

int main(){

// 1. 入力情報.

int N;

LL P, Q, R;

scanf("%d %lld %lld %lld", &N, &P, &Q, &R);

rep(i, N){

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

aCum[i + 1] = aCum[i] + a[i];

}

// 2. 整数の組 (x, y, z, w) が存在するか？

bool ok = false;

rep(x, N){

// x 固定で, y, z, w を二分探索.

int y = lower_bound(aCum, aCum + N + 1, aCum[x] + P) - aCum;

if(aCum[y] == aCum[x] + P){

int z = lower_bound(aCum, aCum + N + 1, aCum[y] + Q) - aCum;

if(aCum[z] == aCum[y] + Q){

int w = lower_bound(aCum, aCum + N + 1, aCum[z] + R) - aCum;

if(aCum[w] == aCum[z] + R){

// printf("x=%d y=%d z=%d w=%d\n", x, y, z, w);

ok = true;

break;

}

// 見つかった.

if(ok) break;

}

// 3. 出力.

printf("%s\n", ok ? "Yes" : "No");

return 0;

}

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

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

[入力例]
9 100 101 100
31 41 59 26 53 58 97 93 23

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

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

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

[入力例]
30 54 34 115
2 20 18 6 10 7 13 19 5 2 2 1 4 1 7 12 11 9 10 19 14 2 1 19 11 8 15 13 8 16

[出力例]
Yes

[入力例]
50 643 1717 1465
85 36 103 63 57 91 43 73 92 39 90 120 70 101 57 43 112 81 110 56 35 47 81 109 32 58 42 32 61 53 39 129 120 73 105 58 110 118 117 39 35 124 118 89 81 112 56 105 69 56

[出力例]
Yes

[入力例]
100 113055 197583 92859
3000 5859 9713 4986 6390 3165 4257 406 3566 5806 7091 2479 1420 4926 5234 5853 640 1858 9214 5205 7140 8221 2341 2796 5028 7979 3501 4634 1465 1449 3154 5477 6106 5230 5150 3551 4105 1378 3680 6632 1846 6255 1391 8893 289 8644 5954 5458 7679 5956 8817 3139 7496 9426 8674 9610 9255 5522 4624 2792 267 1206 4782 6502 6373 1490 2723 8221 9605 455 5009 2388 4393 8570 3567 8716 1291 6662 399 915 6098 4766 9056 1549 7950 732 2770 7088 8544 2649 4141 3824 7346 746 2590 5027 5559 9925 1990 9955

[出力例]
Yes

[入力例]

10 5 7 5

1 3 2 2 2 3 1 4 3 2

[出力例]

Yes

※AtCoderテストケースより

[入力例]

9 100 101 100

31 41 59 26 53 58 97 93 23

[出力例]

※AtCoderテストケースより

[入力例]

7 1 1 1

1 1 1 1 1 1 1

[出力例]

Yes

※AtCoderテストケースより

[入力例]

30 54 34 115

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

[出力例]

Yes

[入力例]

50 643 1717 1465

85 36 103 63 57 91 43 73 92 39 90 120 70 101 57 43 112 81 110 56 35 47 81 109 32 58 42 32 61 53 39 129 120 73 105 58 110 118 117 39 35 124 118 89 81 112 56 105 69 56

[出力例]

Yes

[入力例]

100 113055 197583 92859

3000 5859 9713 4986 6390 3165 4257 406 3566 5806 7091 2479 1420 4926 5234 5853 640 1858 9214 5205 7140 8221 2341 2796 5028 7979 3501 4634 1465 1449 3154 5477 6106 5230 5150 3551 4105 1378 3680 6632 1846 6255 1391 8893 289 8644 5954 5458 7679 5956 8817 3139 7496 9426 8674 9610 9255 5522 4624 2792 267 1206 4782 6502 6373 1490 2723 8221 9605 455 5009 2388 4393 8570 3567 8716 1291 6662 399 915 6098 4766 9056 1549 7950 732 2770 7088 8544 2649 4141 3824 7346 746 2590 5027 5559 9925 1990 9955

[出力例]

Yes

■参照サイト
AtCoder Beginner Contest 265

2022年12月8日2022年12月8日

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

C++の練習を兼ねて, AtCoder Beginner Contest 280 の問題C (Extra Character), 問題E (Critical Hit) を解いてみた.

■感想.
1. 問題C, E は, 方針を絞り込めたので, AC版に到達できたと思う.
2. 問題D は, 初見で提出したもの, 解説確認後にしたものが, いずれも, AC版とならなかったため, 割愛した(理解不足と見做して, 解答不能のステータスとした).
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

■C++版プログラム(問題C／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 main(){
    
    // 1. 入力情報.
    char s[505050], t[505050];
    scanf("%s %s", s, t);
    string S(s), T(t);
    
    // 2. 対象の英文字は？
    int ans = T.size();
    rep(i, S.size()){
        if(S[i] != T[i]){
            ans = i + 1;
            break;
        }
    }
    
    // 3. 出力.
    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 main(){

// 1. 入力情報.

char s[505050], t[505050];

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

string S(s), T(t);

// 2. 対象の英文字は？

int ans = T.size();

rep(i, S.size()){

if(S[i] != T[i]){

ans = i + 1;

break;

}

// 3. 出力.

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

return 0;

}

[入力例]
atcoder
atcorder

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

[入力例]
million
milllion

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

[入力例]
vvwvw
vvvwvw

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

[入力例]
pppqqr
pppqqrs

[出力例]
7

[入力例]
aaaaaaaaaa
aaaaaaaaaaa

[出力例]
11

[入力例]
abracadabra
aabracadabra

[出力例]
2

[入力例]

atcoder

atcorder

[出力例]

※AtCoderテストケースより

[入力例]

million

milllion

[出力例]

※AtCoderテストケースより

[入力例]

vvwvw

vvvwvw

[出力例]

※AtCoderテストケースより

[入力例]

pppqqr

pppqqrs

[出力例]

[入力例]

aaaaaaaaaa

aaaaaaaaaaa

[出力例]

[入力例]

abracadabra

aabracadabra

[出力例]

■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--)
const LL MOD = 998244353;
const LL I100 = 828542813;
LL e[202020];

int main(){
    
    // 1. 入力情報.
    int N, P;
    scanf("%d %d", &N, &P);
    
    // 2. 漸化式.
    // E[n] = (1 - P / 100) * (E[n - 1] + 1) + (P / 100) * (E[n - 2] + 1) で 計算.
    e[1] = 1;
    e[2] = (2 + MOD - (P * I100 % MOD)) % MOD;
    repx(i, 3, N + 1){
        e[i] += (1 + MOD - (P * I100 % MOD)) % MOD * (e[i - 1] + 1) % MOD;
        e[i] %= MOD;
        e[i] += (P * I100 % MOD) * (e[i - 2] + 1) % MOD;
        e[i] %= MOD;
    }
    
    // 3. 出力.
    printf("%lld\n", e[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--)

const LL MOD = 998244353;

const LL I100 = 828542813;

LL e[202020];

int main(){

// 1. 入力情報.

int N, P;

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

// 2. 漸化式.

// E[n] = (1 - P / 100) * (E[n - 1] + 1) + (P / 100) * (E[n - 2] + 1) で計算.

e[1] = 1;

e[2] = (2 + MOD - (P * I100 % MOD)) % MOD;

repx(i, 3, N + 1){

e[i] += (1 + MOD - (P * I100 % MOD)) % MOD * (e[i - 1] + 1) % MOD;

e[i] %= MOD;

e[i] += (P * I100 % MOD) * (e[i - 2] + 1) % MOD;

e[i] %= MOD;

}

// 3. 出力.

printf("%lld\n", e[N]);

return 0;

}

[入力例]
3 10

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

[入力例]
5 100

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

[入力例]
280 59

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

[入力例]
1 50

[出力例]
1

[入力例]
2 50

[出力例]
499122178

[入力例]
3 20

[出力例]
119789325

[入力例]
5 15

[出力例]
520228810

[入力例]
20 22

[出力例]
89557086

[入力例]
2022 12

[出力例]
23091804

[入力例]

3 10

[出力例]

229596204

※AtCoderテストケースより

[入力例]

5 100

[出力例]

※AtCoderテストケースより

[入力例]

280 59

[出力例]

567484387

※AtCoderテストケースより

[入力例]

1 50

[出力例]

[入力例]

2 50

[出力例]

499122178

[入力例]

3 20

[出力例]

119789325

[入力例]

5 15

[出力例]

520228810

[入力例]

20 22

[出力例]

89557086

[入力例]

2022 12

[出力例]

23091804

■参照サイト
デンソークリエイトプログラミングコンテスト2022 Winter(AtCoder Beginner Contest 280)

2022年12月4日

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

C++の練習を兼ねて, AtCoder Beginner Contest 276 の問題C (Previous Permutation) ～問題D (Divide by 2 or 3) を解いてみた.

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

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

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

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

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    vi p(N);
    rep(i, N) scanf("%d", &p[i]);
    
    // 2. (K - 1)番目の順列は？
    vi ans = p, r;
    r.pub(p[N - 1]);
    ans.pob();
    repr(i, N - 2, 0){
        if(p[i] > r.back()) break;
        r.pub(p[i]);
        ans.pob();
    }
    int x = ans.back();
    ans.pob();
    set<int> st;
    for(auto &u : r) st.insert(u);
    int y = 0;
    for(auto &u : st) if(u < x) y = max(y, u);
    ans.pub(y);
    st.erase(y);
    st.insert(x);
    reverse_iterator it = st.rbegin();
    while(it != st.rend()) ans.pub(*it++);
    
    // 3. 出力.
    rep(i, N) printf("%d%s", ans[i], (i < N - 1) ? " " : "\n");
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

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

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

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

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

#define pob pop_back

#define pub push_back

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

vi p(N);

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

// 2. (K - 1)番目の順列は？

vi ans = p, r;

r.pub(p[N - 1]);

ans.pob();

repr(i, N - 2, 0){

if(p[i] > r.back()) break;

r.pub(p[i]);

ans.pob();

}

int x = ans.back();

ans.pob();

set<int> st;

for(auto &u : r) st.insert(u);

int y = 0;

for(auto &u : st) if(u < x) y = max(y, u);

ans.pub(y);

st.erase(y);

st.insert(x);

reverse_iterator it = st.rbegin();

while(it != st.rend()) ans.pub(*it++);

// 3. 出力.

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

return 0;

}

[入力例]
3
3 1 2

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

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

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

[入力例]
5
1 2 3 5 4

[出力例]
1 2 3 4 5

[入力例]
5
5 4 3 2 1

[出力例]
5 4 3 1 2

[入力例]
5
5 1 2 3 4

[出力例]
4 5 3 2 1

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

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

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

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

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

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

[入力例]
200
18 183 80 180 22 112 34 111 114 197 109 176 45 185 25 75 52 70 143 189 148 17 56 184 132 118 103 102 65 177 191 135 28 63 152 174 7 142 46 138 171 85 119 50 31 162 107 178 72 61 1 2 3 4 5 6 8 9 10 11 12 13 14 15 16 19 20 21 23 24 26 27 29 30 32 33 35 36 37 38 39 40 41 42 43 44 47 48 49 51 53 54 55 57 58 59 60 62 64 66 67 68 69 71 73 74 76 77 78 79 81 82 83 84 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 104 105 106 108 110 113 115 116 117 120 121 122 123 124 125 126 127 128 129 130 131 133 134 136 137 139 140 141 144 145 146 147 149 150 151 153 154 155 156 157 158 159 160 161 163 164 165 166 167 168 169 170 172 173 175 179 181 182 186 187 188 190 192 193 194 195 196 198 199 200

[出力例]
18 183 80 180 22 112 34 111 114 197 109 176 45 185 25 75 52 70 143 189 148 17 56 184 132 118 103 102 65 177 191 135 28 63 152 174 7 142 46 138 171 85 119 50 31 162 107 178 72 60 200 199 198 196 195 194 193 192 190 188 187 186 182 181 179 175 173 172 170 169 168 167 166 165 164 163 161 160 159 158 157 156 155 154 153 151 150 149 147 146 145 144 141 140 139 137 136 134 133 131 130 129 128 127 126 125 124 123 122 121 120 117 116 115 113 110 108 106 105 104 101 100 99 98 97 96 95 94 93 92 91 90 89 88 87 86 84 83 82 81 79 78 77 76 74 73 71 69 68 67 66 64 62 61 59 58 57 55 54 53 51 49 48 47 44 43 42 41 40 39 38 37 36 35 33 32 30 29 27 26 24 23 21 20 19 16 15 14 13 12 11 10 9 8 6 5 4 3 2 1
※整数 N が, 問題文の制約条件から範囲外であるケース.

[入力例]

3 1 2

[出力例]

2 3 1

※AtCoderテストケースより

[入力例]

9 8 6 5 10 3 1 2 4 7

[出力例]

9 8 6 5 10 2 7 4 3 1

※AtCoderテストケースより

[入力例]

1 2 3 5 4

[出力例]

1 2 3 4 5

[入力例]

5 4 3 2 1

[出力例]

5 4 3 1 2

[入力例]

5 1 2 3 4

[出力例]

4 5 3 2 1

[入力例]

7 6 4 2 3 5 1

[出力例]

7 6 4 2 3 1 5

[入力例]

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

[出力例]

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

[入力例]

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

[出力例]

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

[入力例]

200

18 183 80 180 22 112 34 111 114 197 109 176 45 185 25 75 52 70 143 189 148 17 56 184 132 118 103 102 65 177 191 135 28 63 152 174 7 142 46 138 171 85 119 50 31 162 107 178 72 61 1 2 3 4 5 6 8 9 10 11 12 13 14 15 16 19 20 21 23 24 26 27 29 30 32 33 35 36 37 38 39 40 41 42 43 44 47 48 49 51 53 54 55 57 58 59 60 62 64 66 67 68 69 71 73 74 76 77 78 79 81 82 83 84 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 104 105 106 108 110 113 115 116 117 120 121 122 123 124 125 126 127 128 129 130 131 133 134 136 137 139 140 141 144 145 146 147 149 150 151 153 154 155 156 157 158 159 160 161 163 164 165 166 167 168 169 170 172 173 175 179 181 182 186 187 188 190 192 193 194 195 196 198 199 200

[出力例]

18 183 80 180 22 112 34 111 114 197 109 176 45 185 25 75 52 70 143 189 148 17 56 184 132 118 103 102 65 177 191 135 28 63 152 174 7 142 46 138 171 85 119 50 31 162 107 178 72 60 200 199 198 196 195 194 193 192 190 188 187 186 182 181 179 175 173 172 170 169 168 167 166 165 164 163 161 160 159 158 157 156 155 154 153 151 150 149 147 146 145 144 141 140 139 137 136 134 133 131 130 129 128 127 126 125 124 123 122 121 120 117 116 115 113 110 108 106 105 104 101 100 99 98 97 96 95 94 93 92 91 90 89 88 87 86 84 83 82 81 79 78 77 76 74 73 71 69 68 67 66 64 62 61 59 58 57 55 54 53 51 49 48 47 44 43 42 41 40 39 38 37 36 35 33 32 30 29 27 26 24 23 21 20 19 16 15 14 13 12 11 10 9 8 6 5 4 3 2 1

※整数 N が, 問題文の制約条件から範囲外であるケース.

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

// 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
LL a[1010], b[1010], cPow[33][33];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    LL aMin = 202020202020202020;
    rep(i, N){
        scanf("%lld", &a[i]);
        b[i] = a[i];
        aMin = min(aMin, a[i]);
    }
    
    // 2. 2, 3 で 割る.
    int c2 = 0, c3 = 0;
    rep(i, N){
        int c = 0;
        while(b[i] % 2 == 0){
            b[i] /= 2;
            ++c;
        }
        c2 = max(c2, c);
        
        c = 0;
        while(b[i] % 3 == 0){
            b[i] /= 3;
            ++c;
        }
        c3 = max(c3, c);
    }
    
    // 3. 例外.
    bool ok = true;
    rep(i, N) if(b[0] != b[i]) ok = false;
    if(!ok){
        puts("-1");
        return 0;
    }
    
    // 4. 事前計算.
    // 4-1. べき乗の組み合わせ.
    cPow[0][0] = 1;
    rep(i, c2 + 1){
        if(i) cPow[i][0] = cPow[i - 1][0] * 2;
        rep(j, c3 + 1) if(j) cPow[i][j] = cPow[i][j - 1] * 3;
    }
    
    // 4-2. 約数.
    vl divisors;
    rep(i, c2 + 1) rep(j, c3 + 1) if(aMin % cPow[i][j] == 0) divisors.pb(aMin / cPow[i][j]);
    
    // 4-3. 操作回数.
    map<LL, int> o;
    rep(i, c2 + 1) rep(j, c3 + 1) o[cPow[i][j]] = i + j;
    
    // 5. 最小回数は？
    int ans = 2020202020;
    for(auto &d : divisors){
        // 最小値に揃えるために, 必要な操作回数は？
        int c = 0;
        bool ok = true;
        rep(i, N){
          if(a[i] % d != 0) ok = false;
          c += o[a[i] / d];
        }
        
        // 更新.
        if(ok) ans = min(ans, c);
    }
    
    // 6. 出力.
    printf("%d\n", ans);
    return 0;
    
}

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

LL a[1010], b[1010], cPow[33][33];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

LL aMin = 202020202020202020;

rep(i, N){

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

b[i] = a[i];

aMin = min(aMin, a[i]);

}

// 2. 2, 3 で割る.

int c2 = 0, c3 = 0;

rep(i, N){

int c = 0;

while(b[i] % 2 == 0){

b[i] /= 2;

++c;

}

c2 = max(c2, c);

c = 0;

while(b[i] % 3 == 0){

b[i] /= 3;

++c;

}

c3 = max(c3, c);

}

// 3. 例外.

bool ok = true;

rep(i, N) if(b[0] != b[i]) ok = false;

if(!ok){

puts("-1");

return 0;

}

// 4. 事前計算.

// 4-1. べき乗の組み合わせ.

cPow[0][0] = 1;

rep(i, c2 + 1){

if(i) cPow[i][0] = cPow[i - 1][0] * 2;

rep(j, c3 + 1) if(j) cPow[i][j] = cPow[i][j - 1] * 3;

}

// 4-2. 約数.

vl divisors;

rep(i, c2 + 1) rep(j, c3 + 1) if(aMin % cPow[i][j] == 0) divisors.pb(aMin / cPow[i][j]);

// 4-3. 操作回数.

map<LL, int> o;

rep(i, c2 + 1) rep(j, c3 + 1) o[cPow[i][j]] = i + j;

// 5. 最小回数は？

int ans = 2020202020;

for(auto &d : divisors){

// 最小値に揃えるために, 必要な操作回数は？

int c = 0;

bool ok = true;

rep(i, N){

if(a[i] % d != 0) ok = false;

c += o[a[i] / d];

}

// 更新.

if(ok) ans = min(ans, c);

}

// 6. 出力.

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

return 0;

}

[入力例]
3
1 4 3

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

[入力例]
3
2 7 6

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

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

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

[入力例]
10
79626240 122880 12960 1399680 1574640 540 6635520 1658880 69120 4320

[出力例]
100

[入力例]
25
10450944 8064 35271936 367416 258048 12096 7838208 18144 12096 244944 1469664 326592 6048 5225472 896 125411328 81648 13608 47029248 2939328 752467968 979776 9289728 108864 193536

[出力例]
250

[入力例]
50
279936 36864 34992 839808 2304 24 20736 209952 1327104 972 1152 107495424 5832 768 7776 26244 49152 17496 8748 279936 419904 53747712 2239488 1327104 3456 26244 1327104 648 6912 331776 1327104 20736 8748 72 497664 53747712 839808 41472 648 419904 53747712 139968 373248 12 34992 15552 8957952 17915904 1679616 24576

[出力例]
500

[入力例]

1 4 3

[出力例]

※AtCoderテストケースより

[入力例]

2 7 6

[出力例]

-1

※AtCoderテストケースより

[入力例]

1 1 1 1 1 1

[出力例]

※AtCoderテストケースより

[入力例]

79626240 122880 12960 1399680 1574640 540 6635520 1658880 69120 4320

[出力例]

100

[入力例]

10450944 8064 35271936 367416 258048 12096 7838208 18144 12096 244944 1469664 326592 6048 5225472 896 125411328 81648 13608 47029248 2939328 752467968 979776 9289728 108864 193536

[出力例]

250

[入力例]

279936 36864 34992 839808 2304 24 20736 209952 1327104 972 1152 107495424 5832 768 7776 26244 49152 17496 8748 279936 419904 53747712 2239488 1327104 3456 26244 1327104 648 6912 331776 1327104 20736 8748 72 497664 53747712 839808 41472 648 419904 53747712 139968 373248 12 34992 15552 8957952 17915904 1679616 24576

[出力例]

500

■参照サイト
AtCoder Beginner Contest 276

2022年12月2日

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

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

■感想.
1. 問題F は, 方針を絞り込めたので, AC版に到達できたと思う.
2. Union-Find木の復習が出来たので, 非常に良かったと思う.
※ 公式のライブラリを拝借させて頂いてます.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
int ball[606060]; // ボール の (保存先)箱番号
int box[606060];  // 箱に入っている 最小 の ボール番号.

// https://github.com/atcoder/live_library/blob/master/uf.cpp
// UnionFind
// coding: https://youtu.be/TdR816rqc3s?t=726
// comment: https://youtu.be/TdR816rqc3s?t=6822
// -> 一部改変.
struct UnionFind{
    vi d;
    UnionFind(int n = 0): d(n, -1) {}
    int find(int x){
        return (d[x] < 0) ? x : (d[x] = find(d[x]));
    }
    bool unite(int x, int y){
        x = find(x);
        y = find(y);
        if(x == y) return false;
        if(d[x] > d[y]) swap(x, y);
        d[x] += d[y];
        d[y] = x;
        return true;
    }
    bool same(int x, int y){
        return find(x) == find(y);
    }
    int size(int x){
        return -d[find(x)];
    }
};

int main(){
    
    // 1. 入力情報.
    int N, Q;
    scanf("%d %d", &N, &Q);
    
    // 2. 初期化.
    UnionFind uf(N + Q + 2);
    rep(i, N + Q + 2){
        uf.unite(i + 1, i + 1);
        ball[i + 1] = box[i + 1] = i + 1;
    }
    
    // 3. クエリ回答.
    int k = N;
    rep(i, Q){
        // 3-1. クエリ入力情報.
        int t;
        scanf("%d", &t);
        
        // 3-2. クエリ 1.
        if(t == 1){
            int x, y;
            scanf("%d %d", &x, &y);
            
            // 箱 Y が 空である.
            if(!box[y]) continue;
            
            // 箱 X, Y が 空でない.
            if(box[x]){
                // 箱 X, Y の ボール番号(最小値)をマージ.
                uf.unite(box[x], box[y]);
                
                // 箱 X に保存したボール番号(最小値) を 保存.
                box[x] = uf.find(box[x]);
                
                // 上記ボール の (保存先)箱番号 を 保存.
                ball[box[x]] = x;
                ball[box[y]] = x;
                
                // 箱 Y を 空にする.
                box[y] = 0;
                
                // 次へ.
                continue;
            }
            
            // 箱 X が 空, 箱 Y が 空でない.
            // 箱 X に保存したボール番号(最小値) を 保存.
            box[x] = box[y];
            
            // 上記ボール の (保存先)箱番号 を 保存.
            ball[box[y]] = x;
            
            // 箱 Y を 空にする.
            box[y] = 0;
        }
        
        // 3-3. クエリ 2.
        if(t == 2){
            int x;
            scanf("%d", &x);
            
            // ボール数 を インクリメント.
            ++k;
            
            // ボール (k + 1) の (保存先)箱番号 を 保存.
            ball[k] = x;
            
            // 箱 X が 空でない.
            if(box[x]){
                // 箱 X に, ボール (k + 1) を 保存.
                // -> マージと解釈する.
                uf.unite(box[x], k);
                
                // 次へ.
                continue;
            }
            
            // 箱 X が 空である.
            box[x] = k;
        }
        
        // 3-4. クエリ 3.
        if(t == 3){
            int x;
            scanf("%d", &x);
            
            // ボール X を 保存している箱で, ボール番号の最小値は？
            int xMin = uf.find(x);
            
            // 出力.
            printf("%d\n", ball[xMin]);
        }
    }
    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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

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

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

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

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

int ball[606060]; // ボールの (保存先)箱番号

int box[606060]; // 箱に入っている最小のボール番号.

// https://github.com/atcoder/live_library/blob/master/uf.cpp

// UnionFind

// coding: https://youtu.be/TdR816rqc3s?t=726

// comment: https://youtu.be/TdR816rqc3s?t=6822

// -> 一部改変.

struct UnionFind{

vi d;

UnionFind(int n = 0): d(n, -1) {}

int find(int x){

return (d[x] < 0) ? x : (d[x] = find(d[x]));

}

bool unite(int x, int y){

x = find(x);

y = find(y);

if(x == y) return false;

if(d[x] > d[y]) swap(x, y);

d[x] += d[y];

d[y] = x;

return true;

}

bool same(int x, int y){

return find(x) == find(y);

}

int size(int x){

return -d[find(x)];

}

};

int main(){

// 1. 入力情報.

int N, Q;

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

// 2. 初期化.

UnionFind uf(N + Q + 2);

rep(i, N + Q + 2){

uf.unite(i + 1, i + 1);

ball[i + 1] = box[i + 1] = i + 1;

}

// 3. クエリ回答.

int k = N;

rep(i, Q){

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

int t;

scanf("%d", &t);

// 3-2. クエリ 1.

if(t == 1){

int x, y;

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

// 箱 Y が空である.

if(!box[y]) continue;

// 箱 X, Y が空でない.

if(box[x]){

// 箱 X, Y のボール番号(最小値)をマージ.

uf.unite(box[x], box[y]);

// 箱 X に保存したボール番号(最小値) を保存.

box[x] = uf.find(box[x]);

// 上記ボールの (保存先)箱番号を保存.

ball[box[x]] = x;

ball[box[y]] = x;

// 箱 Y を空にする.

box[y] = 0;

// 次へ.

continue;

}

// 箱 X が空, 箱 Y が空でない.

// 箱 X に保存したボール番号(最小値) を保存.

box[x] = box[y];

// 上記ボールの (保存先)箱番号を保存.

ball[box[y]] = x;

// 箱 Y を空にする.

box[y] = 0;

}

// 3-3. クエリ 2.

if(t == 2){

int x;

scanf("%d", &x);

// ボール数をインクリメント.

++k;

// ボール (k + 1) の (保存先)箱番号を保存.

ball[k] = x;

// 箱 X が空でない.

if(box[x]){

// 箱 X に, ボール (k + 1) を保存.

// -> マージと解釈する.

uf.unite(box[x], k);

// 次へ.

continue;

}

// 箱 X が空である.

box[x] = k;

}

// 3-4. クエリ 3.

if(t == 3){

int x;

scanf("%d", &x);

// ボール X を保存している箱で, ボール番号の最小値は？

int xMin = uf.find(x);

// 出力.

printf("%d\n", ball[xMin]);

}

return 0;

}

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

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

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

[出力例]
2
4
7
6

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

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

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

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

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

[入力例]

5 10

3 5

1 1 4

2 1

2 4

3 7

1 3 1

3 4

1 1 4

3 7

3 6

[出力例]

※AtCoderテストケースより

[入力例]

7 10

1 5 1

1 2 5

3 5

2 1

2 4

3 9

1 7 4

3 9

2 6

3 10

[出力例]

[入力例]

10 25

2 5

2 9

1 5 8

2 10

1 5 7

2 6

3 11

1 3 5

2 10

3 13

2 6

3 2

2 7

1 2 5

2 1

1 5 10

3 15

3 7

2 7

1 2 3

1 7 2

3 3

1 1 3

1 5 7

3 10

[出力例]

[入力例]

20 70

3 1

2 14

1 8 11

1 15 3

1 2 14

3 21

2 11

2 2

1 3 2

2 1

2 14

2 16

3 23

2 12

3 4

1 5 12

1 12 15

1 5 14

3 25

1 16 18

3 6

1 8 9

1 7 16

3 26

2 7

3 9

2 9

2 12

3 30

3 10

2 16

3 22

2 10

1 14 17

1 13 7

3 31

2 12

1 14 16

1 15 16

3 16

2 7

2 4

3 17

1 15 5

2 2

2 9

3 25

1 16 3

1 17 12

3 21

1 17 19

3 19

2 18

1 18 13

3 7

1 19 8

2 19

2 20

2 2

3 41

1 20 4

1 20 17

2 16

2 15

3 3

1 8 11

2 17

2 4

[出力例]

■参照サイト
トヨタシステムズプログラミングコンテスト2022(AtCoder Beginner Contest 279)
Union-Find木

2022年11月30日2022年11月30日

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

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

■感想.
1. 問題E は, 方針を絞り込めたので, AC版に到達できたと思う.
2. 個人的には, 問題E は, 操作を, なるべくコンパクトに捉えることに着目する点が, 非常に面白いと思った.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

■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[202020], ib[202020], ob[202020], cur[202020];

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    rep(i, M) scanf("%d", &a[i]);
    
    // 2. すべて操作.
    rep(i, N) ib[i + 1] = ob[i + 1] = cur[i + 1] = i + 1;
    rep(i, M){
        int s = ib[a[i]];
        int e = ib[a[i] + 1];
        swap(ib[a[i]], ib[a[i] + 1]);
        swap(ob[s], ob[e]);
    }
    
    // 3. 出力.
    rep(i, M){
        // 操作対象に, 1 が 含まれるか否かで, 分岐.
        // 1 を 含まない.
        if(cur[a[i]] != 1 && cur[a[i] + 1] != 1) printf("%d\n", ob[1]);
        
        // 1 を 含む(その①).
        if(cur[a[i]] == 1) printf("%d\n", ob[cur[a[i] + 1]]);
        
        // 1 を 含む(その②).
        if(cur[a[i] + 1] == 1) printf("%d\n", ob[cur[a[i]]]);
        
        // 操作.
        swap(cur[a[i]], cur[a[i] + 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[202020], ib[202020], ob[202020], cur[202020];

int main(){

// 1. 入力情報.

int N, M;

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

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

// 2. すべて操作.

rep(i, N) ib[i + 1] = ob[i + 1] = cur[i + 1] = i + 1;

rep(i, M){

int s = ib[a[i]];

int e = ib[a[i] + 1];

swap(ib[a[i]], ib[a[i] + 1]);

swap(ob[s], ob[e]);

}

// 3. 出力.

rep(i, M){

// 操作対象に, 1 が含まれるか否かで, 分岐.

// 1 を含まない.

if(cur[a[i]] != 1 && cur[a[i] + 1] != 1) printf("%d\n", ob[1]);

// 1 を含む(その①).

if(cur[a[i]] == 1) printf("%d\n", ob[cur[a[i] + 1]]);

// 1 を含む(その②).

if(cur[a[i] + 1] == 1) printf("%d\n", ob[cur[a[i]]]);

// 操作.

swap(cur[a[i]], cur[a[i] + 1]);

}

return 0;

}

[入力例]
5 4
1 2 3 2

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

[入力例]
3 3
2 2 2

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

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

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

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

[出力例]
4
2
2
1
2
4
2

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

[出力例]
3
2
3
2
3
3
1
2
3
3
3
3

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

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

[入力例]

5 4

1 2 3 2

[出力例]

※AtCoderテストケースより

[入力例]

3 3

2 2 2

[出力例]

※AtCoderテストケースより

[入力例]

10 10

1 1 1 9 4 4 2 1 3 3

[出力例]

※AtCoderテストケースより

[入力例]

5 7

1 3 4 2 1 2 3

[出力例]

[入力例]

8 12

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

[出力例]

[入力例]

10 25

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

[出力例]

■参照サイト
トヨタシステムズプログラミングコンテスト2022(AtCoder Beginner Contest 279)

2022年11月30日

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

C++の練習を兼ねて, AtCoder Beginner Contest 279 の問題C (RANDOM) ～問題D (Freefall) を解いてみた.

■感想.
1. 問題C, D は, 方針を絞り込めたので, AC版に到達できたと思う.
2. 個人的には, 問題D は, 桁数オーバーフローを回避する訓練が積めたので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

■C++版プログラム(問題C／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 main(){
    
    // 1. 入力情報.
    int H, W;
    scanf("%d %d", &H, &W);
    vector<string> S, T;
    rep(i, H){
        char c[W + 1];
        scanf("%s", c);
        string s(c);
        S.pb(s);
    }
    rep(i, H){
        char c[W + 1];
        scanf("%s", c);
        string t(c);
        T.pb(t);
    }
    
    // 2. 列情報保存.
    map<string, int> ms, mt;
    rep(j, W){
        string sCur, tCur;
        rep(i, H){
            sCur.pb(S[i][j]);
            tCur.pb(T[i][j]);
        }
        ++ms[sCur];
        ++mt[tCur];
    }
    
    // 3. 出力.
    printf("%s\n", (ms == mt) ? "Yes" : "No");
    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 main(){

// 1. 入力情報.

int H, W;

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

vector<string> S, T;

rep(i, H){

char c[W + 1];

scanf("%s", c);

string s(c);

S.pb(s);

}

rep(i, H){

char c[W + 1];

scanf("%s", c);

string t(c);

T.pb(t);

}

// 2. 列情報保存.

map<string, int> ms, mt;

rep(j, W){

string sCur, tCur;

rep(i, H){

sCur.pb(S[i][j]);

tCur.pb(T[i][j]);

}

++ms[sCur];

++mt[tCur];

}

// 3. 出力.

printf("%s\n", (ms == mt) ? "Yes" : "No");

return 0;

}

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

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

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

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

[入力例]
2 1
#
.
#
.

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

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

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

[入力例]

3 4

##.#

##..

#...

.###

..##

...#

[出力例]

Yes

※AtCoderテストケースより

[入力例]

3 3

#.#

.#.

#.#

##.

.#.

[出力例]

※AtCoderテストケースより

[入力例]

2 1

[出力例]

Yes

※AtCoderテストケースより

[入力例]

8 7

#..#..#

.##.##.

#..#..#

.##.##.

#..#..#

.##.##.

#..#..#

.##.##.

....###

####...

....###

####...

....###

####...

....###

####...

[出力例]

Yes

※AtCoderテストケースより

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

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

int main(){
    
    // 1. 入力情報.
    LL A, B;
    scanf("%lld %lld", &A, &B);
    
    // 2. g を t 増やすと仮定.
    // -> t は A / (2 * B) の (2 / 3)乗 - 1 と思われる.
    LL x = 0;
    rep(i, 1010101){
        if((LL)i * (LL)i * (LL)i > A / (2 * B)){
            x = i;
            break;
        }
    }
    
    // 3. 最小値は？
    // 区間[(x - 1) * (x - 1), x * x] で 考えてみる.
    double ans = 2020202020202020202.0;
    rep(i, 2 * (int)x + 2){
        LL t = (x - 1) * (x - 1) + i - 1;
        ans = min(ans, (double)A / sqrt(t + 1) + (double)(B * t));
    }
    
    // 4. 出力.
    printf("%.10lf\n", ans);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

int main(){

// 1. 入力情報.

LL A, B;

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

// 2. g を t 増やすと仮定.

// -> t は A / (2 * B) の (2 / 3)乗 - 1 と思われる.

LL x = 0;

rep(i, 1010101){

if((LL)i * (LL)i * (LL)i > A / (2 * B)){

x = i;

break;

}

// 3. 最小値は？

// 区間[(x - 1) * (x - 1), x * x] で考えてみる.

double ans = 2020202020202020202.0;

rep(i, 2 * (int)x + 2){

LL t = (x - 1) * (x - 1) + i - 1;

ans = min(ans, (double)A / sqrt(t + 1) + (double)(B * t));

}

// 4. 出力.

printf("%.10lf\n", ans);

return 0;

}

[入力例]
10 1

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

[入力例]
5 10

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

[入力例]
1000000000000000000 100

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

[入力例]
2022 5

[出力例]
511.7701391582

[入力例]
20221130 11

[出力例]
311951.5299304323

[入力例]
123456789012345678 55

[出力例]
1781963505917.5668945312

[入力例]

10 1

[出力例]

7.7735026919

※AtCoderテストケースより

[入力例]

5 10

[出力例]

5.0000000000

※AtCoderテストケースより

[入力例]

1000000000000000000 100

[出力例]

8772053214538.5976562500

※AtCoderテストケースより

[入力例]

2022 5

[出力例]

511.7701391582

[入力例]

20221130 11

[出力例]

311951.5299304323

[入力例]

123456789012345678 55

[出力例]

1781963505917.5668945312

■参照サイト
トヨタシステムズプログラミングコンテスト2022(AtCoder Beginner Contest 279)

2022年11月26日

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

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

■感想.
1. 問題D は, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 解説のロジックで, 操作後のグラフが, 木となるようなものを構成できる点が, 非常に面白く感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

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

int main(){
    
    // 1. 入力情報.
    LL N, K;
    scanf("%lld %lld", &N, &K);
    
    // 2. 例外.
    if(!(N & 1)){
        puts("-1");
        return 0;
    }
    
    // 3. 事前計算.
    LL g = __gcd(N, K);
    LL n = N / g;
    
    // 4. 追加する辺は？
    // 4-1. 縦線.
    vp ans;
    repex(i, 0, (int)n - 1, 2) repex(j, 0, (int)g, 2) ans.pb({(i * K + j) % N, ((i + 1) * K + j) % N});
    
    // 4-2. 横線(奇数列目).
    repex(i, 0, (int)n - 1, 2) repex(j, 0, (int)g - 1, 2) ans.pb({(i * K + j) % N, (i * K + j + 1) % N});
    
    // 4-3. 横線(偶数列目).
    repex(j, 1, (int)g, 2) ans.pb({((n - 2) * K + j) % N, ((n - 2) * K + j + 1) % N});
    
    // 5. 出力.
    printf("%lld\n", (N - 1) / 2);
    rep(i, (N - 1) / 2) printf("%lld %lld\n", ans[i].a, ans[i].b);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc152/editorial/5119

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using P = pair<LL, LL>;

using vp = vector<P>;

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

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

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

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

#define pb push_back

#define a first

#define b second

int main(){

// 1. 入力情報.

LL N, K;

scanf("%lld %lld", &N, &K);

// 2. 例外.

if(!(N & 1)){

puts("-1");

return 0;

}

// 3. 事前計算.

LL g = __gcd(N, K);

LL n = N / g;

// 4. 追加する辺は？

// 4-1. 縦線.

vp ans;

repex(i, 0, (int)n - 1, 2) repex(j, 0, (int)g, 2) ans.pb({(i * K + j) % N, ((i + 1) * K + j) % N});

// 4-2. 横線(奇数列目).

repex(i, 0, (int)n - 1, 2) repex(j, 0, (int)g - 1, 2) ans.pb({(i * K + j) % N, (i * K + j + 1) % N});

// 4-3. 横線(偶数列目).

repex(j, 1, (int)g, 2) ans.pb({((n - 2) * K + j) % N, ((n - 2) * K + j + 1) % N});

// 5. 出力.

printf("%lld\n", (N - 1) / 2);

rep(i, (N - 1) / 2) printf("%lld %lld\n", ans[i].a, ans[i].b);

return 0;

}

[入力例]
5 2

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

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

[入力例]
2 1

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

[入力例]
7 1

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

[入力例]
25 10

[出力例]
12
0 10
2 12
4 14
20 5
22 7
24 9
0 1
2 3
20 21
22 23
6 7
8 9
※AtCoder解説例より

[入力例]
3 2

[出力例]
1
0 2

[入力例]
9 6

[出力例]
4
0 6
2 8
0 1
7 8

[入力例]
15 3

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

[入力例]
51 34

[出力例]
25
0 34
2 36
4 38
6 40
8 42
10 44
12 46
14 48
16 50
0 1
2 3
4 5
6 7
8 9
10 11
12 13
14 15
35 36
37 38
39 40
41 42
43 44
45 46
47 48
49 50

100

101

102

103

104

105

106

107

108

109

110

[入力例]

5 2

[出力例]

2 3

2 4

※AtCoderテストケースより

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

0 2

4 1

[入力例]

2 1

[出力例]

-1

※AtCoderテストケースより

[入力例]

7 1

[出力例]

0 1

2 3

4 5

※AtCoderテストケースより

[入力例]

25 10

[出力例]

0 10

2 12

4 14

20 5

22 7

24 9

0 1

2 3

20 21

22 23

6 7

8 9

※AtCoder解説例より

[入力例]

3 2

[出力例]

0 2

[入力例]

9 6

[出力例]

0 6

2 8

0 1

7 8

[入力例]

15 3

[出力例]

0 3

2 5

6 9

8 11

0 1

6 7

10 11

[入力例]

51 34

[出力例]

0 34

2 36

4 38

6 40

8 42

10 44

12 46

14 48

16 50

0 1

2 3

4 5

6 7

8 9

10 11

12 13

14 15

35 36

37 38

39 40

41 42

43 44

45 46

47 48

49 50

■参照サイト
AtCoder Regular Contest 152

2022年11月26日2022年11月26日

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

C++の練習を兼ねて, AtCoder Beginner Contest 272 の問題C (Max Even) ～問題E (Add and Mex) を解いてみた.

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

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

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

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%d", &a[i]);
    
    // 2. sort.
    sort(a, a + N);
    
    // 3. 大きな二つの奇数, 偶数.
    int o1 = -1, o2 = -1, e1 = -1, e2 = -1;
    repr(i, N - 1, 0){
        // 奇数.
        if(a[i] & 1){
            if(o1 == -1){
                o1 = a[i];
                continue;
            }
            if(o1 != -1 && o2 == -1) o2 = a[i];
        }
        
        // 偶数.
        if(!(a[i] & 1)){
            if(e1 == -1){
                e1 = a[i];
                continue;
            }
            if(e1 != -1 && e2 == -1) e2 = a[i];
        }
    }
    
    // 4. 最大値は？
    int ans = -1;
    if(o1 != -1 && o2 != -1) ans = max(ans, o1 + o2);
    if(e1 != -1 && e2 != -1) ans = max(ans, e1 + e2);
    
    // 5. 出力.
    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 a[202020];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

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

// 2. sort.

sort(a, a + N);

// 3. 大きな二つの奇数, 偶数.

int o1 = -1, o2 = -1, e1 = -1, e2 = -1;

repr(i, N - 1, 0){

// 奇数.

if(a[i] & 1){

if(o1 == -1){

o1 = a[i];

continue;

}

if(o1 != -1 && o2 == -1) o2 = a[i];

}

// 偶数.

if(!(a[i] & 1)){

if(e1 == -1){

e1 = a[i];

continue;

}

if(e1 != -1 && e2 == -1) e2 = a[i];

}

// 4. 最大値は？

int ans = -1;

if(o1 != -1 && o2 != -1) ans = max(ans, o1 + o2);

if(e1 != -1 && e2 != -1) ans = max(ans, e1 + e2);

// 5. 出力.

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

return 0;

}

[入力例]
3
2 3 4

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

[入力例]
2
1 0

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

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

[出力例]
24

[入力例]
25
70 77 52 10 56 11 95 86 93 7 66 74 114 8 4 1 66 2 34 35 8 42 55 74 60

[出力例]
200

[入力例]
100
89 161 141 234 1 38 245 4 22 15 12 16 123 33 65 201 114 174 155 150 121 245 161 146 23 7 13 191 178 193 53 7 221 122 244 86 174 150 116 98 24 8 14 112 185 9 168 10 96 58 176 201 179 8 17 210 155 72 208 151 217 240 96 22 215 18 190 178 123 50 73 233 117 20 111 88 6 208 126 2 210 11 178 19 35 3 215 224 171 223 5 108 12 85 168 21 239 51 256 216

[出力例]
500

[入力例]

2 3 4

[出力例]

※AtCoderテストケースより

[入力例]

1 0

[出力例]

-1

※AtCoderテストケースより

[入力例]

9 3 0 10 8 7 3 15 8 1

[出力例]

[入力例]

70 77 52 10 56 11 95 86 93 7 66 74 114 8 4 1 66 2 34 35 8 42 55 74 60

[出力例]

200

[入力例]

100

89 161 141 234 1 38 245 4 22 15 12 16 123 33 65 201 114 174 155 150 121 245 161 146 23 7 13 191 178 193 53 7 221 122 244 86 174 150 116 98 24 8 14 112 185 9 168 10 96 58 176 201 179 8 17 210 155 72 208 151 217 240 96 22 215 18 190 178 123 50 73 233 117 20 111 88 6 208 126 2 210 11 178 19 35 3 215 224 171 223 5 108 12 85 168 21 239 51 256 216

[出力例]

500

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;
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--)
#define a first
#define b second

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    
    // 2. 距離の二乗が M のベクトルは？
    // -> すべての頂点に対して, 二点間の距離を計算すると, 計算量が, N の 4乗くらいになりそうなので, 
    //    原点から, 距離の二乗が M のベクトルだけ, 保存する方針とした.
    set<P> st;
    rep(i, N){
        rep(j, N){
            if(i * i + j * j == M){
                st.insert({-i, -j});
                st.insert({-i, +j});
                st.insert({+i, -j});
                st.insert({+i, +j});
            }
        }
    }
    
    // 3. グラフ作成.
    // -> 距離の二乗が, M となるマス間に, 辺を張る.
    int n = N * N;
    vs G(n);
    rep(i, N){
        rep(j, N){
            int p1 = i * N + j;
            for(auto &v : st){
                int r = i + v.a;
                int c = j + v.b;
                if(r >= 0 && r <= N - 1 && c >= 0 && c <= N - 1){
                    int p2 = r * N + c;
                    G[p1].insert(p2);
                    G[p2].insert(p1);
                }
            }
        }
    }
    
    // 4. bfs.
    // https://ja.wikipedia.org/wiki/幅優先探索
    auto bfs = [&](vs &G, int s, int* d){
        // 空のキュー.
        queue<int> q;
        
        // スタート地点は, 距離ゼロ.
        d[s] = 0;
        
        // 探索地点 s をキュー q に追加.
        q.push(s);
        while(!q.empty()){
            // キューから取り出す.
            int u = q.front();
            q.pop();
            
            // 隣接頂点をチェック.
            for(auto &v : G[u]) if(d[v] == -1 && v != s) d[v] = d[u] + 1, q.push(v);
        }
    };
    int d[n];
    rep(i, n) d[i] = -1;
    bfs(G, 0, d);
    
    // 5. 出力.
    rep(i, N) rep(j, N) printf("%d%s", d[i * N + j], (j < N - 1) ? " " : "\n");
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using P = pair<int, int>;

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

#define a first

#define b second

int main(){

// 1. 入力情報.

int N, M;

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

// 2. 距離の二乗が M のベクトルは？

// -> すべての頂点に対して, 二点間の距離を計算すると, 計算量が, N の 4乗くらいになりそうなので,

// 原点から, 距離の二乗が M のベクトルだけ, 保存する方針とした.

set<P> st;

rep(i, N){

rep(j, N){

if(i * i + j * j == M){

st.insert({-i, -j});

st.insert({-i, +j});

st.insert({+i, -j});

st.insert({+i, +j});

}

// 3. グラフ作成.

// -> 距離の二乗が, M となるマス間に, 辺を張る.

int n = N * N;

vs G(n);

rep(i, N){

rep(j, N){

int p1 = i * N + j;

for(auto &v : st){

int r = i + v.a;

int c = j + v.b;

if(r >= 0 && r <= N - 1 && c >= 0 && c <= N - 1){

int p2 = r * N + c;

G[p1].insert(p2);

G[p2].insert(p1);

}

// 4. bfs.

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

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

// 空のキュー.

queue<int> q;

// スタート地点は, 距離ゼロ.

d[s] = 0;

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

q.push(s);

while(!q.empty()){

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

int u = q.front();

q.pop();

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

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

}

};

int d[n];

rep(i, n) d[i] = -1;

bfs(G, 0, d);

// 5. 出力.

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

return 0;

}

[入力例]
3 1

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

[入力例]
10 5

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

[入力例]
5 5

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

[入力例]
7 2

[出力例]
0 -1 2 -1 4 -1 6
-1 1 -1 3 -1 5 -1
2 -1 2 -1 4 -1 6
-1 3 -1 3 -1 5 -1
4 -1 4 -1 4 -1 6
-1 5 -1 5 -1 5 -1
6 -1 6 -1 6 -1 6

[入力例]
25 34

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

[入力例]

3 1

[出力例]

0 1 2

1 2 3

2 3 4

※AtCoderテストケースより

[入力例]

10 5

[出力例]

0 3 2 3 2 3 4 5 4 5

3 4 1 2 3 4 3 4 5 6

2 1 4 3 2 3 4 5 4 5

3 2 3 2 3 4 3 4 5 6

2 3 2 3 4 3 4 5 4 5

3 4 3 4 3 4 5 4 5 6

4 3 4 3 4 5 4 5 6 5

5 4 5 4 5 4 5 6 5 6

4 5 4 5 4 5 6 5 6 7

5 6 5 6 5 6 5 6 7 6

※AtCoderテストケースより

[入力例]

5 5

[出力例]

0 3 2 3 2

3 4 1 2 3

2 1 4 3 2

3 2 3 2 3

2 3 2 3 4

[入力例]

7 2

[出力例]

0 -1 2 -1 4 -1 6

-1 1 -1 3 -1 5 -1

2 -1 2 -1 4 -1 6

-1 3 -1 3 -1 5 -1

4 -1 4 -1 4 -1 6

-1 5 -1 5 -1 5 -1

6 -1 6 -1 6 -1 6

[入力例]

25 34

[出力例]

0 -1 6 -1 4 -1 2 -1 8 -1 2 -1 4 -1 6 -1 4 -1 6 -1 4 -1 6 -1 8

-1 5 -1 3 -1 5 -1 3 -1 5 -1 5 -1 3 -1 5 -1 5 -1 5 -1 5 -1 5 -1

6 -1 4 -1 4 -1 6 -1 2 -1 6 -1 4 -1 4 -1 6 -1 4 -1 6 -1 6 -1 6

-1 3 -1 7 -1 1 -1 5 -1 5 -1 3 -1 7 -1 3 -1 5 -1 7 -1 5 -1 7 -1

4 -1 4 -1 6 -1 4 -1 4 -1 4 -1 4 -1 6 -1 4 -1 4 -1 6 -1 6 -1 6

-1 5 -1 1 -1 7 -1 3 -1 3 -1 7 -1 3 -1 5 -1 5 -1 5 -1 7 -1 5 -1

2 -1 6 -1 4 -1 4 -1 6 -1 2 -1 6 -1 6 -1 4 -1 6 -1 4 -1 6 -1 6

-1 3 -1 5 -1 3 -1 5 -1 5 -1 3 -1 5 -1 5 -1 5 -1 7 -1 5 -1 5 -1

8 -1 2 -1 4 -1 6 -1 2 -1 6 -1 4 -1 4 -1 8 -1 4 -1 6 -1 6 -1 6

-1 5 -1 5 -1 3 -1 5 -1 5 -1 5 -1 5 -1 3 -1 7 -1 5 -1 5 -1 7 -1

2 -1 6 -1 4 -1 2 -1 6 -1 4 -1 4 -1 6 -1 4 -1 6 -1 6 -1 6 -1 8

-1 5 -1 3 -1 7 -1 3 -1 5 -1 7 -1 3 -1 7 -1 5 -1 5 -1 7 -1 5 -1

4 -1 4 -1 4 -1 6 -1 4 -1 4 -1 6 -1 4 -1 6 -1 6 -1 4 -1 8 -1 6

-1 3 -1 7 -1 3 -1 5 -1 5 -1 3 -1 7 -1 5 -1 5 -1 7 -1 5 -1 7 -1

6 -1 4 -1 6 -1 6 -1 4 -1 6 -1 4 -1 6 -1 6 -1 4 -1 8 -1 6 -1 6

-1 5 -1 3 -1 5 -1 5 -1 3 -1 7 -1 5 -1 5 -1 7 -1 5 -1 7 -1 7 -1

4 -1 6 -1 4 -1 4 -1 8 -1 4 -1 6 -1 6 -1 4 -1 8 -1 6 -1 6 -1 8

-1 5 -1 5 -1 5 -1 5 -1 7 -1 5 -1 5 -1 7 -1 5 -1 7 -1 7 -1 5 -1

6 -1 4 -1 4 -1 6 -1 4 -1 6 -1 6 -1 4 -1 8 -1 6 -1 6 -1 8 -1 6

-1 5 -1 7 -1 5 -1 7 -1 5 -1 5 -1 7 -1 5 -1 7 -1 7 -1 5 -1 9 -1

4 -1 6 -1 6 -1 4 -1 6 -1 6 -1 4 -1 8 -1 6 -1 6 -1 8 -1 6 -1 8

-1 5 -1 5 -1 7 -1 5 -1 5 -1 7 -1 5 -1 7 -1 7 -1 5 -1 9 -1 7 -1

6 -1 6 -1 6 -1 6 -1 6 -1 6 -1 8 -1 6 -1 6 -1 8 -1 6 -1 8 -1 8

-1 5 -1 7 -1 5 -1 5 -1 7 -1 5 -1 7 -1 7 -1 5 -1 9 -1 7 -1 7 -1

8 -1 6 -1 6 -1 6 -1 6 -1 8 -1 6 -1 6 -1 8 -1 6 -1 8 -1 8 -1 6

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

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

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    rep(i, N) scanf("%lld", &a[i]);
    
    // 2. 各A[i]の操作で得られる値.
    set<LL> op[M + 1];
    LL q = 0, r = 0;
    repx(i, 1, N + 1){
        // 負.
        if(a[i - 1] < 0){
            // 下限.
            LL l = abs(a[i - 1]) / i + ((abs(a[i - 1]) % i) > 0);
            l = min(l, (LL)M);
            
            // 上限.
            LL r = (N - a[i - 1]) / i + (((N - a[i - 1]) % i) > 0);
            r = min(r, (LL)M);
            
            // 保存.
            repx(j, (int)l, (int)(r + 1)) op[j].insert(j * i + a[i - 1]);
            
            // 次へ.
            continue;
        }
        
        // 上記以外.
        // 次へ.
        if(a[i - 1] > N) continue;
        
        // 下限(ゼロ).
        
        // 上限.
        LL r = (N - a[i - 1]) / i + (((N - a[i - 1]) % i) > 0);
        r = min(r, (LL)M);
        
        // 保存.
        rep(j, (int)(r + 1)) op[j].insert(j * i + a[i - 1]);
    }
    
    // 3. 出力.
    repx(i, 1, M + 1){
        if(op[i].empty()){
            puts("0");
            continue;
        }
        int ans = -1;
        while(op[i].count(++ans)){}
        printf("%d\n", ans);
    }
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc272/editorial/4982

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

LL a[202020];

int main(){

// 1. 入力情報.

int N, M;

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

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

// 2. 各A[i]の操作で得られる値.

set<LL> op[M + 1];

LL q = 0, r = 0;

repx(i, 1, N + 1){

// 負.

if(a[i - 1] < 0){

// 下限.

LL l = abs(a[i - 1]) / i + ((abs(a[i - 1]) % i) > 0);

l = min(l, (LL)M);

// 上限.

LL r = (N - a[i - 1]) / i + (((N - a[i - 1]) % i) > 0);

r = min(r, (LL)M);

// 保存.

repx(j, (int)l, (int)(r + 1)) op[j].insert(j * i + a[i - 1]);

// 次へ.

continue;

}

// 上記以外.

// 次へ.

if(a[i - 1] > N) continue;

// 下限(ゼロ).

// 上限.

LL r = (N - a[i - 1]) / i + (((N - a[i - 1]) % i) > 0);

r = min(r, (LL)M);

// 保存.

rep(j, (int)(r + 1)) op[j].insert(j * i + a[i - 1]);

}

// 3. 出力.

repx(i, 1, M + 1){

if(op[i].empty()){

puts("0");

continue;

}

int ans = -1;

while(op[i].count(++ans)){}

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

}

return 0;

}

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

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

[入力例]
5 6
-2 -2 -5 -7 -15

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

[入力例]
7 8
-5 -10 -14 -8 -17 -20 -25

[出力例]
0
1
0
0
2
0
0
0

[入力例]
15 10
-2 -2 -5 -12 -20 -30 -42 -56 -60 -70 -100 -101 -102 -150 -225

[出力例]
1
3
2
1
1
1
1
0
0
0

[入力例]
30 20
-20 -38 -56 -72 -89 -106 -98 -104 -108 -10 -11 -11 -13 -27 -28 -64 -85 -90 -190 -20 -21 -43 -45 -44 -220 -256 -267 -278 -289 -300

[出力例]
2
0
0
1
1
0
0
0
0
5
0
1
1
1
0
0
0
3
2
1

[入力例]

3 3

-1 -1 -6

[出力例]

※AtCoderテストケースより

[入力例]

5 6

-2 -2 -5 -7 -15

[出力例]

※AtCoderテストケースより

[入力例]

7 8

-5 -10 -14 -8 -17 -20 -25

[出力例]

[入力例]

15 10

-2 -2 -5 -12 -20 -30 -42 -56 -60 -70 -100 -101 -102 -150 -225

[出力例]

[入力例]

30 20

-20 -38 -56 -72 -89 -106 -98 -104 -108 -10 -11 -11 -13 -27 -28 -64 -85 -90 -190 -20 -21 -43 -45 -44 -220 -256 -267 -278 -289 -300

[出力例]

■参照サイト
AtCoder Beginner Contest 272

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

C++の練習を兼ねて, AtCoder Regular Contest 139 の 問題C (One Three Nine) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 265 の 問題C (Belt Conveyor) ～ 問題D (Iroha and Haiku (New ABC Edition)) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 280 の 問題C (Extra Character), 問題E (Critical Hit) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 276 の 問題C (Previous Permutation) ～ 問題D (Divide by 2 or 3) を解いてみた.

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

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

C++の練習を兼ねて, AtCoder Beginner Contest 279 の 問題C (RANDOM) ～ 問題D (Freefall) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 272 の 問題C (Max Even) ～ 問題E (Add and Mex) を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 139 の問題C (One Three Nine) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 265 の問題C (Belt Conveyor) ～問題D (Iroha and Haiku (New ABC Edition)) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 280 の問題C (Extra Character), 問題E (Critical Hit) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 276 の問題C (Previous Permutation) ～問題D (Divide by 2 or 3) を解いてみた.

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

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

C++の練習を兼ねて, AtCoder Beginner Contest 279 の問題C (RANDOM) ～問題D (Freefall) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 272 の問題C (Max Even) ～問題E (Add and Mex) を解いてみた.