C++ | 個人用メモ帳

2023年4月19日

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

C++の練習を兼ねて, AtCoder Beginner Contest 197 の問題F (Construct a Palindrome) を解いてみた.

■感想.
1. 問題F は, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 幅優先探索の復習が出来たので, 非常に良かったと思う.
3. 個人的には, 解説のロジックで, 計算できる点が, 非常に不思議な印象を受けた.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/abc197/editorial/994
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
using T3 = tuple<int, int, int>;
using vt = vector<T3>;
#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 int INF = 1010101010;

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    vt e;
    rep(i, M){
        char c[11];
        int a, b;
        scanf("%d %d %s", &a, &b, c);
        --a;
        --b;
        e.emplace_back(a, b, c[0] - 'a');
        e.emplace_back(b, a, c[0] - 'a');
    }
    
    // 2. 拡張グラフ作成.
    int n = N * N;
    vvi G(n);
    for(auto &p : e){
        for(auto &q : e){
            // 頂点を設定.
            int a = get<0>(p);
            int b = get<0>(q);
            int c = get<1>(p);
            int d = get<1>(q);
            int vac = get<2>(p);
            int vbd = get<2>(q);
            
            // 二辺の書かれた文字が異なる場合は, Skip.
            if(vac != vbd) continue;
            
            // 辺を張る.
            G[a * N + b].pb(c * N + d);
            G[c * N + d].pb(a * N + b);
        }
    }
    
    // 3. bfs.
    // https://ja.wikipedia.org/wiki/幅優先探索
    auto bfs = [&](vvi &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 &e : G[u]) if(d[e] == INF && e != s) d[e] = d[u] + 1, q.push(e);
        }
    };
    
    // 4. 頂点の組 (1, N) に対応する頂点 からの 最短距離.
    int d[n];
    rep(i, n) d[i] = INF;
    bfs(G, 0 * N + (N - 1), d);
    
    // 5. 最短距離は？
    int ans = INF;
    rep(i, N){
        rep(j, N){
            // 5-1. 回文長(候補).
            int cur = d[i * N + j] + d[j * N + i];
            
            // 5-2. 偶数長.
            if(i == j) if(!(cur & 1)) ans = min(ans, cur);
            
            // 5-3. 奇数長.
            if(i != j) if(cur & 1) ans = min(ans, cur);
        }
    }
    
    // 6. 出力.
    printf("%d\n", (ans == INF) ? -1 : ans);
    return 0;
    
}

100

// 解き直し.

// https://atcoder.jp/contests/abc197/editorial/994

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

using vvi = vector<vi>;

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

using vt = vector<T3>;

#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 int INF = 1010101010;

int main(){

// 1. 入力情報.

int N, M;

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

vt e;

rep(i, M){

char c[11];

int a, b;

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

--a;

--b;

e.emplace_back(a, b, c[0] - 'a');

e.emplace_back(b, a, c[0] - 'a');

}

// 2. 拡張グラフ作成.

int n = N * N;

vvi G(n);

for(auto &p : e){

for(auto &q : e){

// 頂点を設定.

int a = get<0>(p);

int b = get<0>(q);

int c = get<1>(p);

int d = get<1>(q);

int vac = get<2>(p);

int vbd = get<2>(q);

// 二辺の書かれた文字が異なる場合は, Skip.

if(vac != vbd) continue;

// 辺を張る.

G[a * N + b].pb(c * N + d);

G[c * N + d].pb(a * N + b);

}

// 3. bfs.

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

auto bfs = [&](vvi &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 &e : G[u]) if(d[e] == INF && e != s) d[e] = d[u] + 1, q.push(e);

}

};

// 4. 頂点の組 (1, N) に対応する頂点からの最短距離.

int d[n];

rep(i, n) d[i] = INF;

bfs(G, 0 * N + (N - 1), d);

// 5. 最短距離は？

int ans = INF;

rep(i, N){

rep(j, N){

// 5-1. 回文長(候補).

int cur = d[i * N + j] + d[j * N + i];

// 5-2. 偶数長.

if(i == j) if(!(cur & 1)) ans = min(ans, cur);

// 5-3. 奇数長.

if(i != j) if(cur & 1) ans = min(ans, cur);

}

// 6. 出力.

printf("%d\n", (ans == INF) ? -1 : ans);

return 0;

}

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

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

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

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

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

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

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

[出力例]
3

[入力例]
8 13
1 2 c
1 2 b
3 1 a
4 3 b
5 4 a
5 4 c
5 6 c
2 5 c
5 8 a
8 2 a
8 7 a
7 6 b
7 6 c

[出力例]
6

[入力例]
20 50
14 10 c
11 14 m
5 20 t
17 17 t
12 14 f
15 17 m
12 17 r
8 20 q
16 11 z
13 8 g
8 5 g
9 10 c
17 15 k
16 19 i
5 11 b
5 16 h
17 14 c
2 9 u
16 4 t
16 18 k
1 16 p
18 19 r
14 6 z
20 3 x
1 17 x
4 7 w
17 9 a
5 1 d
4 8 f
5 12 o
1 5 h
10 3 e
5 18 h
9 7 r
13 18 d
5 18 s
2 18 j
12 8 l
20 19 h
15 16 k
4 13 p
20 7 b
3 10 x
6 19 j
13 8 e
6 10 i
16 15 j
19 19 t
10 14 e
11 18 t

[出力例]
5

[入力例]
30 150
27 13 i
2 14 r
25 26 k
25 14 s
2 4 y
14 16 l
7 11 a
1 12 c
27 14 w
17 1 z
17 22 l
4 22 u
26 9 w
15 25 w
21 3 e
23 21 x
28 14 y
8 4 b
1 19 h
28 14 a
12 9 r
4 21 i
3 26 p
9 3 o
19 11 j
17 11 k
13 29 i
14 7 t
25 7 t
7 14 z
7 7 p
21 4 l
24 13 t
19 5 b
17 25 s
19 29 q
26 13 c
28 19 j
20 29 k
18 19 h
13 18 b
10 26 q
8 21 i
15 10 t
4 4 p
19 3 c
9 20 w
22 3 i
3 26 f
10 17 r
19 24 f
4 11 j
17 29 k
9 1 h
1 1 a
25 22 e
22 23 h
28 29 b
4 22 t
18 17 p
3 28 w
21 18 c
11 1 m
9 26 m
11 28 l
23 17 o
23 2 a
13 3 u
12 22 c
13 26 x
9 9 j
18 25 w
18 22 u
5 28 h
21 4 t
30 11 q
2 24 c
27 19 u
14 16 e
4 5 r
8 15 d
8 30 l
14 10 u
6 2 j
29 15 z
17 12 j
20 27 l
24 14 o
29 2 f
8 7 j
14 8 u
5 30 d
26 4 o
7 30 e
22 25 c
29 15 z
12 11 h
24 17 q
11 8 n
24 2 f
8 30 u
30 6 a
24 5 q
10 9 h
19 30 f
30 8 s
3 16 c
29 24 a
29 28 l
6 21 k
20 17 x
2 24 n
12 8 t
20 21 q
30 3 a
13 18 z
14 17 t
11 10 a
27 9 p
29 14 z
3 26 p
26 20 m
25 15 z
6 24 h
4 19 h
3 11 z
6 20 t
16 28 v
6 15 z
19 4 l
3 20 o
5 3 u
21 13 h
7 30 a
17 16 o
24 11 m
8 13 x
30 8 k
5 18 y
12 7 m
20 14 i
6 25 v
21 14 f
30 25 m
17 3 j
24 12 a
5 28 i
24 17 q
22 6 o
23 17 h

[出力例]
5

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

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

[入力例]

8 8

1 2 a

2 3 b

1 3 c

3 4 b

4 5 a

5 6 c

6 7 b

7 8 a

[出力例]

※AtCoderのテストケースより

[入力例]

4 5

1 1 a

1 2 a

2 3 a

3 4 b

4 4 a

[出力例]

※AtCoderのテストケースより

[入力例]

3 4

1 1 a

1 2 a

2 3 b

3 3 b

[出力例]

-1

※AtCoderのテストケースより

[入力例]

4 3

1 2 a

2 3 b

3 4 a

[出力例]

[入力例]

8 13

1 2 c

1 2 b

3 1 a

4 3 b

5 4 a

5 4 c

5 6 c

2 5 c

5 8 a

8 2 a

8 7 a

7 6 b

7 6 c

[出力例]

[入力例]

20 50

14 10 c

11 14 m

5 20 t

17 17 t

12 14 f

15 17 m

12 17 r

8 20 q

16 11 z

13 8 g

8 5 g

9 10 c

17 15 k

16 19 i

5 11 b

5 16 h

17 14 c

2 9 u

16 4 t

16 18 k

1 16 p

18 19 r

14 6 z

20 3 x

1 17 x

4 7 w

17 9 a

5 1 d

4 8 f

5 12 o

1 5 h

10 3 e

5 18 h

9 7 r

13 18 d

5 18 s

2 18 j

12 8 l

20 19 h

15 16 k

4 13 p

20 7 b

3 10 x

6 19 j

13 8 e

6 10 i

16 15 j

19 19 t

10 14 e

11 18 t

[出力例]

[入力例]

30 150

27 13 i

2 14 r

25 26 k

25 14 s

2 4 y

14 16 l

7 11 a

1 12 c

27 14 w

17 1 z

17 22 l

4 22 u

26 9 w

15 25 w

21 3 e

23 21 x

28 14 y

8 4 b

1 19 h

28 14 a

12 9 r

4 21 i

3 26 p

9 3 o

19 11 j

17 11 k

13 29 i

14 7 t

25 7 t

7 14 z

7 7 p

21 4 l

24 13 t

19 5 b

17 25 s

19 29 q

26 13 c

28 19 j

20 29 k

18 19 h

13 18 b

10 26 q

8 21 i

15 10 t

4 4 p

19 3 c

9 20 w

22 3 i

3 26 f

10 17 r

19 24 f

4 11 j

17 29 k

9 1 h

1 1 a

25 22 e

22 23 h

28 29 b

4 22 t

18 17 p

3 28 w

21 18 c

11 1 m

9 26 m

11 28 l

23 17 o

23 2 a

13 3 u

12 22 c

13 26 x

9 9 j

18 25 w

18 22 u

5 28 h

21 4 t

30 11 q

2 24 c

27 19 u

14 16 e

4 5 r

8 15 d

8 30 l

14 10 u

6 2 j

29 15 z

17 12 j

20 27 l

24 14 o

29 2 f

8 7 j

14 8 u

5 30 d

26 4 o

7 30 e

22 25 c

29 15 z

12 11 h

24 17 q

11 8 n

24 2 f

8 30 u

30 6 a

24 5 q

10 9 h

19 30 f

30 8 s

3 16 c

29 24 a

29 28 l

6 21 k

20 17 x

2 24 n

12 8 t

20 21 q

30 3 a

13 18 z

14 17 t

11 10 a

27 9 p

29 14 z

3 26 p

26 20 m

25 15 z

6 24 h

4 19 h

3 11 z

6 20 t

16 28 v

6 15 z

19 4 l

3 20 o

5 3 u

21 13 h

7 30 a

17 16 o

24 11 m

8 13 x

30 8 k

5 18 y

12 7 m

20 14 i

6 25 v

21 14 f

30 25 m

17 3 j

24 12 a

5 28 i

24 17 q

22 6 o

23 17 h

[出力例]

■参照サイト
AtCoder Beginner Contest 197（Sponsored by Panasonic）

2023年4月16日2023年4月16日

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

C++の練習を兼ねて, AtCoder Beginner Contest 295 の問題C (Socks) ～問題E (Kth Number) を解いてみた.

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

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

■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 a first
#define b second

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    map<int, int> m;
    rep(i, N){
        int a;
        scanf("%d", &a);
        ++m[a];
    }
    
    // 2. 数え上げ.
    int ans = 0;
    for(auto &p : m) ans += p.b / 2;
    
    // 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--)

#define a first

#define b second

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

map<int, int> m;

rep(i, N){

int a;

scanf("%d", &a);

++m[a];

}

// 2. 数え上げ.

int ans = 0;

for(auto &p : m) ans += p.b / 2;

// 3. 出力.

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

return 0;

}

[入力例]
6
4 1 7 4 1 4

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

[入力例]
1
158260522

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

[入力例]
10
295 2 29 295 29 2 29 295 2 29

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

[入力例]
50
106 19 10 90 72 101 22 82 119 87 3 2 79 31 6 51 54 33 40 29 6 46 74 30 11 117 53 96 75 16 104 30 76 111 32 51 2 52 116 72 101 1 75 41 10 48 51 46 13 87

[出力例]
10

[出力例]
100
96 6 61 23 95 56 76 88 55 35 88 89 65 59 76 95 5 55 33 2 18 61 76 77 99 55 69 69 96 70 63 92 79 6 95 57 97 91 10 26 55 52 53 85 5 38 59 76 90 72 56 83 80 87 96 20 62 25 5 55 72 17 31 66 79 57 1 16 20 25 57 72 81 62 32 59 70 2 31 20 39 15 88 3 63 85 52 50 66 96 60 25 18 55 53 5 87 39 80 18

[出力例]
34

[入力例]

4 1 7 4 1 4

[出力例]

※AtCoderテストケースより

[入力例]

158260522

[出力例]

※AtCoderテストケースより

[入力例]

295 2 29 295 29 2 29 295 2 29

[出力例]

※AtCoderテストケースより

[入力例]

106 19 10 90 72 101 22 82 119 87 3 2 79 31 6 51 54 33 40 29 6 46 74 30 11 117 53 96 75 16 104 30 76 111 32 51 2 52 116 72 101 1 75 41 10 48 51 46 13 87

[出力例]

100

96 6 61 23 95 56 76 88 55 35 88 89 65 59 76 95 5 55 33 2 18 61 76 77 99 55 69 69 96 70 63 92 79 6 95 57 97 91 10 26 55 52 53 85 5 38 59 76 90 72 56 83 80 87 96 20 62 25 5 55 72 17 31 66 79 57 1 16 20 25 57 72 81 62 32 59 70 2 31 20 39 15 88 3 63 85 52 50 66 96 60 25 18 55 53 5 87 39 80 18

[出力例]

■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 sCum[505050][10], p[1 << 10];

int main(){
    
    // 1. 入力情報.
    char c[505050];
    scanf("%s", c);
    string s(c);
    int n = s.size();
    
    // 2. 累積和.
    rep(i, n){
        rep(j, 10) sCum[i + 1][j] = sCum[i][j];
        ++sCum[i + 1][s[i] - '0'];
        sCum[i + 1][s[i] - '0'] %= 2;
    }
    
    // 3. 0 ～ 9 の 出現状況.
    rep(i, n + 1){
        int x = 0;
        rep(j, 10) if(sCum[i][j]) x += (1 << j);
        ++p[x];
    }
    
    // 4. 集計.
    LL ans = 0;
    rep(i, 1 << 10) ans += p[i] * (p[i] - 1) / 2;
    
    // 5. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

LL sCum[505050][10], p[1 << 10];

int main(){

// 1. 入力情報.

char c[505050];

scanf("%s", c);

string s(c);

int n = s.size();

// 2. 累積和.

rep(i, n){

rep(j, 10) sCum[i + 1][j] = sCum[i][j];

++sCum[i + 1][s[i] - '0'];

sCum[i + 1][s[i] - '0'] %= 2;

}

// 3. 0 ～ 9 の出現状況.

rep(i, n + 1){

int x = 0;

rep(j, 10) if(sCum[i][j]) x += (1 << j);

++p[x];

}

// 4. 集計.

LL ans = 0;

rep(i, 1 << 10) ans += p[i] * (p[i] - 1) / 2;

// 5. 出力.

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

return 0;

}

[入力例]
20230322

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

[入力例]
0112223333444445555556666666777777778888888889999999999

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

[入力例]
3141592653589793238462643383279502884197169399375105820974944

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

[入力例]
0672399474713525344309392013100562405141933097426713800408602692352473255409543673131038281718215293

[出力例]
20

[入力例]
43822528221649586967940200326919217981214617997174645566916246429027035301160142726935216220663659002429777446705798098514754637046664769823895464470447839113645140314579441295003133693442118292076023029585905176686160152927670069097377211608662693688552989472022870695274946047128163632607233361118307126215978369445322356782736681676583947149227261084417279392373265251895002425146460442210632034427766477119809205298411207570678353852846722362757233262697098795068765642393454991793416984734622695

[出力例]
212

[入力例]
11805307412898056014811861952584801110638821485390195055179698385152688502845075255306732699755927047525484702021750019923218888888869807053392030277385707339025387971725950124571770122201914594405997876873167792867848680897398725786333899448556145640604856530998625779607965004719975275348094137930472084379538806599118885844496558015235792644856563252104424209154517968812102488169581318407277269237942006023595456804238446133378632081703362309940891767935389059893317188382651547788928398428024266161995658403840303194697969862443297485515454983593810569853098261801874588234556192061599590413849779313332937511503355421398259761508113373746391384029328819113695945586824934988795545015810184556828255096618452959664691321554707850917730348510551075906552244363632802266519115641184396436228716310950894609371745203598252791168435669502765588962692686091072679624998705512051491113304959605912354143123356348091902689563125445970395707077135026907428534457236694868484162027898219774573352737543482924313467617215632485601085057318243234590848320785308678093572812048259874230798802816025599049544548479708396320113421744137430427393930461399709491227106210168723749968668315657341934473686994033732147729260511833229733659482695350430911033244448852680751587103196509888920205150522453839742726222261371836165286423613851788531342658395087412284404493673271490348249160998127967763889956783578314168834629262587700264290708163173154830964079641201306714485249095153169243107422018002659316012623296652943544442544199065959481908810106490695540182227664180961331081163058688792761053447965226881684335219018006668104304476657522280708087471699103401808482313981181494229521752113511948035713754859385286834381670025628689225207317336626606999123542735012621120412152204064967838095637342851234056103688631774338813197765195732721366511235469631787506700865177243414518243788946309677856224589264305081227174286364192203858179517269954682973002820880310854943798900624247909762804411239473507521039175333697224608311744252312583266454424290517447401487576279400633184546072382054223242032445125709634042371832473687464057346549248346778634401954853525962293257794172383292239164303514276293495304464679646737790462960954830641029456521171295806745883271735787078772126646050466004624445914055095476184197375263162317362706655644045546596278657696865832837871336826594909944934135567388470036528519284692115980087028660007311280871975672176753031463618573182285565441922665565794572764402548245877155079827511515586755426356702738088830662049931708687541194530207725218207733921166416068810870103155990088178850162428475429167573764115138262005117041766733976016393197787028812060655593205744766905531128992854192938842958156671046169810581579937860282917065469238176537898498412564673585432363684506217785999646583119843196289395557832586462346090479848168152643113022195424648845992369139379447571288529241246737609645784566191676552420536030552431780638862283190079514691554026454659767149301195583540587307895107543469924113221255917010549062520435065371327452503456688468805743168723907665737043847277268088605087928934832071757157272826832793695980425322168918373496766430792924254727042047201389271006828219179911447853987373869494522260226860368105402254629086571949082455850025539064912725734347360707870226183383375629744253727927654470630302617135442973371896672745600917303745515334883455314882694428789677247992666117573648880947470515113716048144716527771138295278845094282730334284226373197288668226483181135499626734053912318887844449127055908277986623814435955878538373024356052678142727158374970717133606525957541929617160859472271411764672671249887514384546102059562477919369065957351711368227567648783197802897208592360611834278291341314420850042838567139936314791880337886430860584308942368809019370364321822818136667766656010075325425707713013563650328547445129209747049099864388191935232241079852720378201478395869034987683332238102922066325999143676107318586659699799168748795794092956062598379611972071344340291882097385718859597067634819077579298822594828706495365465189221731714594884283028093194237045662481144553602547493026579181015964494697455666093435445577344880065612460189484274889416651847773812107060380540908954494527833955503414456929914085795442447715824826673643188068688499404673709745288273756338588177048248224823618942413059694647337444469983111699421982856935862902096438779554482623451274339968637590503489408905774967602932644117055570851480603951728434286521222632007484559812448187861165542983465572612697958030561725736385172818426367060710702388840239965334073619556266008781829065074995020372154874770358348622301062860291310309901262302113786791157743621313987256404212616764512335501713755330860864678220497286677616294376383345670894445172879045334008190508927621270729241076553825982953567533372177227782392437928034813701396575178378906469637435757443107915790336255565209737147062647887920291690092209735451261147758438576523554190622187875

[出力例]
12678

[入力例]

20230322

[出力例]

※AtCoderテストケースより

[入力例]

0112223333444445555556666666777777778888888889999999999

[出力例]

185

※AtCoderテストケースより

[入力例]

3141592653589793238462643383279502884197169399375105820974944

[出力例]

※AtCoderテストケースより

[入力例]

0672399474713525344309392013100562405141933097426713800408602692352473255409543673131038281718215293

[出力例]

[入力例]

43822528221649586967940200326919217981214617997174645566916246429027035301160142726935216220663659002429777446705798098514754637046664769823895464470447839113645140314579441295003133693442118292076023029585905176686160152927670069097377211608662693688552989472022870695274946047128163632607233361118307126215978369445322356782736681676583947149227261084417279392373265251895002425146460442210632034427766477119809205298411207570678353852846722362757233262697098795068765642393454991793416984734622695

[出力例]

212

[入力例]

11805307412898056014811861952584801110638821485390195055179698385152688502845075255306732699755927047525484702021750019923218888888869807053392030277385707339025387971725950124571770122201914594405997876873167792867848680897398725786333899448556145640604856530998625779607965004719975275348094137930472084379538806599118885844496558015235792644856563252104424209154517968812102488169581318407277269237942006023595456804238446133378632081703362309940891767935389059893317188382651547788928398428024266161995658403840303194697969862443297485515454983593810569853098261801874588234556192061599590413849779313332937511503355421398259761508113373746391384029328819113695945586824934988795545015810184556828255096618452959664691321554707850917730348510551075906552244363632802266519115641184396436228716310950894609371745203598252791168435669502765588962692686091072679624998705512051491113304959605912354143123356348091902689563125445970395707077135026907428534457236694868484162027898219774573352737543482924313467617215632485601085057318243234590848320785308678093572812048259874230798802816025599049544548479708396320113421744137430427393930461399709491227106210168723749968668315657341934473686994033732147729260511833229733659482695350430911033244448852680751587103196509888920205150522453839742726222261371836165286423613851788531342658395087412284404493673271490348249160998127967763889956783578314168834629262587700264290708163173154830964079641201306714485249095153169243107422018002659316012623296652943544442544199065959481908810106490695540182227664180961331081163058688792761053447965226881684335219018006668104304476657522280708087471699103401808482313981181494229521752113511948035713754859385286834381670025628689225207317336626606999123542735012621120412152204064967838095637342851234056103688631774338813197765195732721366511235469631787506700865177243414518243788946309677856224589264305081227174286364192203858179517269954682973002820880310854943798900624247909762804411239473507521039175333697224608311744252312583266454424290517447401487576279400633184546072382054223242032445125709634042371832473687464057346549248346778634401954853525962293257794172383292239164303514276293495304464679646737790462960954830641029456521171295806745883271735787078772126646050466004624445914055095476184197375263162317362706655644045546596278657696865832837871336826594909944934135567388470036528519284692115980087028660007311280871975672176753031463618573182285565441922665565794572764402548245877155079827511515586755426356702738088830662049931708687541194530207725218207733921166416068810870103155990088178850162428475429167573764115138262005117041766733976016393197787028812060655593205744766905531128992854192938842958156671046169810581579937860282917065469238176537898498412564673585432363684506217785999646583119843196289395557832586462346090479848168152643113022195424648845992369139379447571288529241246737609645784566191676552420536030552431780638862283190079514691554026454659767149301195583540587307895107543469924113221255917010549062520435065371327452503456688468805743168723907665737043847277268088605087928934832071757157272826832793695980425322168918373496766430792924254727042047201389271006828219179911447853987373869494522260226860368105402254629086571949082455850025539064912725734347360707870226183383375629744253727927654470630302617135442973371896672745600917303745515334883455314882694428789677247992666117573648880947470515113716048144716527771138295278845094282730334284226373197288668226483181135499626734053912318887844449127055908277986623814435955878538373024356052678142727158374970717133606525957541929617160859472271411764672671249887514384546102059562477919369065957351711368227567648783197802897208592360611834278291341314420850042838567139936314791880337886430860584308942368809019370364321822818136667766656010075325425707713013563650328547445129209747049099864388191935232241079852720378201478395869034987683332238102922066325999143676107318586659699799168748795794092956062598379611972071344340291882097385718859597067634819077579298822594828706495365465189221731714594884283028093194237045662481144553602547493026579181015964494697455666093435445577344880065612460189484274889416651847773812107060380540908954494527833955503414456929914085795442447715824826673643188068688499404673709745288273756338588177048248224823618942413059694647337444469983111699421982856935862902096438779554482623451274339968637590503489408905774967602932644117055570851480603951728434286521222632007484559812448187861165542983465572612697958030561725736385172818426367060710702388840239965334073619556266008781829065074995020372154874770358348622301062860291310309901262302113786791157743621313987256404212616764512335501713755330860864678220497286677616294376383345670894445172879045334008190508927621270729241076553825982953567533372177227782392437928034813701396575178378906469637435757443107915790336255565209737147062647887920291690092209735451261147758438576523554190622187875

[出力例]

12678

■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 int LIMIT = 2020;
LL FAC[LIMIT], INV[LIMIT];
int a[LIMIT], aCum[LIMIT];

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

// 組み合わせ(nCk)計算用(mod版).
// ※配列FAC, INV は, 事前に計算済のものを使う.
// @param n: 対象となる要素の個数.
// @param k: 選択する要素の個数.
// @return: 組み合わせ(nCk)の計算結果(mod版).
LL combination(LL n, LL k){
    if(n < 0 || k < 0 || k > n) return 0;
    LL ret = FAC[n] * INV[k] % MOD * INV[n - k] % MOD;
    return ret;
}

int main(){
    
    // 1. 入力情報.
    int N, M, K;
    scanf("%d %d %d", &N, &M, &K);
    rep(i, N){
        int x;
        scanf("%d", &x);
        ++a[x];
    }
    
    // 2. 事前準備.
    FAC[0] = INV[0] = 1;
    repx(i, 1, LIMIT){
        FAC[i] = (LL)i * FAC[i - 1] % MOD;
        INV[i] = mPow(FAC[i], MOD - 2);
    }
    
    // 3. 累積和.
    repx(i, 1, M + 1) aCum[i] = aCum[i - 1] + a[i];
    
    // 4. 数え上げ(分子).
    LL ans = 0, bef = 0;
    repx(i, 1, M + 1){
        LL cur = 0;
        repr(j, a[0], 0){
            // 0 ～ i までが, K個未満だったら, Skip.
            if(j + aCum[i] < K) continue;
            
            // 0 を 書き換える場合の数.
            // j個:               1  ～ i に 設定.
            // (a[0] - j)個: (i + 1) ～ M に 設定.
            cur += combination(a[0], j) * mPow(i, j) % MOD * mPow(M - i, a[0] - j) % MOD;
            cur %= MOD;
        }
        
        // 今回分反映.
        ans += i * (cur - bef + MOD) % MOD;
        ans %= MOD;
        
        // 前回分更新.
        bef = cur;
    }
    
    // 5. 数え上げ(分母).
    // -> 0 を 1 ～ M に 書き換えるので, (0 の 個数) の M乗 を 分母 とする.
    ans *= mPow(mPow(M, a[0]), MOD - 2);
    ans %= MOD;
    
    // 6. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

const LL MOD = 998244353;

const int LIMIT = 2020;

LL FAC[LIMIT], INV[LIMIT];

int a[LIMIT], aCum[LIMIT];

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

}

// 組み合わせ(nCk)計算用(mod版).

// ※配列FAC, INV は, 事前に計算済のものを使う.

// @param n: 対象となる要素の個数.

// @param k: 選択する要素の個数.

// @return: 組み合わせ(nCk)の計算結果(mod版).

LL combination(LL n, LL k){

if(n < 0 || k < 0 || k > n) return 0;

LL ret = FAC[n] * INV[k] % MOD * INV[n - k] % MOD;

return ret;

}

int main(){

// 1. 入力情報.

int N, M, K;

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

rep(i, N){

int x;

scanf("%d", &x);

++a[x];

}

// 2. 事前準備.

FAC[0] = INV[0] = 1;

repx(i, 1, LIMIT){

FAC[i] = (LL)i * FAC[i - 1] % MOD;

INV[i] = mPow(FAC[i], MOD - 2);

}

// 3. 累積和.

repx(i, 1, M + 1) aCum[i] = aCum[i - 1] + a[i];

// 4. 数え上げ(分子).

LL ans = 0, bef = 0;

repx(i, 1, M + 1){

LL cur = 0;

repr(j, a[0], 0){

// 0 ～ i までが, K個未満だったら, Skip.

if(j + aCum[i] < K) continue;

// 0 を書き換える場合の数.

// j個: 1 ～ i に設定.

// (a[0] - j)個: (i + 1) ～ M に設定.

cur += combination(a[0], j) * mPow(i, j) % MOD * mPow(M - i, a[0] - j) % MOD;

cur %= MOD;

}

// 今回分反映.

ans += i * (cur - bef + MOD) % MOD;

ans %= MOD;

// 前回分更新.

bef = cur;

}

// 5. 数え上げ(分母).

// -> 0 を 1 ～ M に書き換えるので, (0 の個数) の M乗を分母とする.

ans *= mPow(mPow(M, a[0]), MOD - 2);

ans %= MOD;

// 6. 出力.

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

return 0;

}

[入力例]
3 5 2
2 0 4

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

[入力例]
2 3 1
0 0

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

[入力例]
10 20 7
6 5 0 2 0 0 0 15 0 0

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

[入力例]
5 6 3
2 0 3 0 4

[出力例]
305019111

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

[出力例]
358744067

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

[出力例]
6

[入力例]
20 15 12
9 13 1 0 7 0 1 3 11 8 7 10 8 5 0 2 9 20 8 9

[出力例]
569960562

[入力例]
50 77 30
31 66 28 70 49 30 51 40 58 0 20 43 50 9 4 26 49 0 70 22 61 31 25 26 3 69 11 24 63 0 5 3 77 23 68 63 27 50 53 0 32 58 5 24 34 24 0 23 10 5

[出力例]
352265950

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

[出力例]
160902217

[入力例]

3 5 2

2 0 4

[出力例]

※AtCoderテストケースより

[入力例]

2 3 1

0 0

[出力例]

221832080

※AtCoderテストケースより

[入力例]

10 20 7

6 5 0 2 0 0 0 15 0 0

[出力例]

617586310

※AtCoderテストケースより

[入力例]

5 6 3

2 0 3 0 4

[出力例]

305019111

[入力例]

7 4 5

1 0 1 0 2 4 0

[出力例]

358744067

[入力例]

12 10 7

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

[出力例]

[入力例]

20 15 12

9 13 1 0 7 0 1 3 11 8 7 10 8 5 0 2 9 20 8 9

[出力例]

569960562

[入力例]

50 77 30

31 66 28 70 49 30 51 40 58 0 20 43 50 9 4 26 49 0 70 22 61 31 25 26 3 69 11 24 63 0 5 3 77 23 68 63 27 50 53 0 32 58 5 24 34 24 0 23 10 5

[出力例]

352265950

[入力例]

100 30 55

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

[出力例]

160902217

■参照サイト
AtCoder Beginner Contest 295

2023年4月12日2023年4月12日

C++ の動作確認をしてみた（９２４）

C++の練習を兼ねて, AtCoder Beginner Contest 199 の問題D (RGB Coloring 2) を解いてみた.

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

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

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

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

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    vvi G(N);
    vp E;
    rep(i, M){
        int a, b;
        scanf("%d %d", &a, &b);
        --a, --b;
        G[a].pb(b);
        G[b].pb(a);
        E.pb({a, b});
    }
    
    // 2. bfs.
    // https://ja.wikipedia.org/wiki/幅優先探索
    auto bfs = [&](vvi &G, int s, int* c, int* d, int l){
        // 空のキュー.
        queue<int> q;
        
        // 連結成分番号 を 設定.
        c[s] = l;
        
        // 距離 を 設定.
        d[s] = 1;
        
        // 探索地点 s をキュー q に追加.
        q.push(s);
        while(!q.empty()){
            // キューから取り出す.
            int u = q.front();
            q.pop();
            
            // 取り出した要素を処理.
            for(auto &e : G[u]){
                if(!c[e] && e != s){
                    c[e] = l;
                    d[e] = d[u] ^ 1;
                    q.push(e);
                }
            }
        }
    };
    
    // 3. 数え上げ.
    LL ans = 0;
    rep(i, 1 << N){
        // 3-1. 赤頂点設定.
        int red[N];
        rep(j, N) red[j] = ((1 << j) & i) ? 1 : 0;
        
        // 3-2. 赤頂点 に 矛盾がないか？
        bool ok = true;
        for(auto &p : E){
            // 赤頂点同士 を 結ぶ辺 が 見つかったら, NG.
            if(red[p.a] && red[p.b]){
                ok = false;
                break;
            }
        }
        
        // 3-3. Skip.
        if(!ok) continue;
        
        // 3-4. グラフ構築.
        vvi H(N);
        for(auto &p : E){
            // 赤頂点Skip.
            if(red[p.a] || red[p.b]) continue;
            
            // 辺追加.
            H[p.a].pb(p.b);
            H[p.b].pb(p.a);
        }
        
        // 3-5. 各連結成分に分解, かつ, 距離(0 or 1) を 保存.
        int c[N], d[N], idx = 0;
        rep(j, N) c[j] = d[j] = 0;
        rep(j, N) if(!c[j] && !red[j]) bfs(H, j, c, d, ++idx);
        
        // 3-6. 緑頂点, 青頂点 に 矛盾がないか？
        for(auto &p : E){
            // 赤頂点Skip.
            if(red[p.a] || red[p.b]) continue;
            
            // 緑頂点同士, 青頂点同士 を 結ぶ辺 が 見つかったら, NG.
            if(!(d[p.a] ^ d[p.b])){
                ok = false;
                break;
            }
        }
        
        // 3-7. 加算.
        if(ok) ans += (1LL << idx);
    }
    
    // 4. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

// 解き直し.

// https://atcoder.jp/contests/abc199/editorial/1163

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vi = vector<int>;

using vvi = vector<vi>;

using P = pair<int, int>;

using vp = vector<P>;

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

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

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

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

#define pb push_back

#define a first

#define b second

int main(){

// 1. 入力情報.

int N, M;

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

vvi G(N);

vp E;

rep(i, M){

int a, b;

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

--a, --b;

G[a].pb(b);

G[b].pb(a);

E.pb({a, b});

}

// 2. bfs.

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

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

// 空のキュー.

queue<int> q;

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

c[s] = l;

// 距離を設定.

d[s] = 1;

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

q.push(s);

while(!q.empty()){

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

int u = q.front();

q.pop();

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

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

if(!c[e] && e != s){

c[e] = l;

d[e] = d[u] ^ 1;

q.push(e);

}

};

// 3. 数え上げ.

LL ans = 0;

rep(i, 1 << N){

// 3-1. 赤頂点設定.

int red[N];

rep(j, N) red[j] = ((1 << j) & i) ? 1 : 0;

// 3-2. 赤頂点に矛盾がないか？

bool ok = true;

for(auto &p : E){

// 赤頂点同士を結ぶ辺が見つかったら, NG.

if(red[p.a] && red[p.b]){

ok = false;

break;

}

// 3-3. Skip.

if(!ok) continue;

// 3-4. グラフ構築.

vvi H(N);

for(auto &p : E){

// 赤頂点Skip.

if(red[p.a] || red[p.b]) continue;

// 辺追加.

H[p.a].pb(p.b);

H[p.b].pb(p.a);

}

// 3-5. 各連結成分に分解, かつ, 距離(0 or 1) を保存.

int c[N], d[N], idx = 0;

rep(j, N) c[j] = d[j] = 0;

rep(j, N) if(!c[j] && !red[j]) bfs(H, j, c, d, ++idx);

// 3-6. 緑頂点, 青頂点に矛盾がないか？

for(auto &p : E){

// 赤頂点Skip.

if(red[p.a] || red[p.b]) continue;

// 緑頂点同士, 青頂点同士を結ぶ辺が見つかったら, NG.

if(!(d[p.a] ^ d[p.b])){

ok = false;

break;

}

// 3-7. 加算.

if(ok) ans += (1LL << idx);

}

// 4. 出力.

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

return 0;

}

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

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

[入力例]
3 0

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

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

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

[入力例]
20 0

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

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

[出力例]
288

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

[出力例]
7290

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

[出力例]
21600

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

[出力例]
77760

100

101

102

103

104

105

106

107

[入力例]

3 3

1 2

2 3

3 1

[出力例]

※AtCoderテストケースより

[入力例]

3 0

[出力例]

※AtCoderテストケースより

[入力例]

4 6

1 2

2 3

3 4

2 4

1 3

1 4

[出力例]

※AtCoderテストケースより

[入力例]

20 0

[出力例]

3486784401

※AtCoderテストケースより

[入力例]

10 12

1 2

1 3

2 3

2 4

3 4

4 5

5 6

5 7

9 6

10 7

8 6

8 7

[出力例]

288

[入力例]

10 5

1 2

2 3

3 4

4 5

5 1

[出力例]

7290

[入力例]

15 15

1 2

2 3

3 4

4 5

5 1

3 6

6 7

7 8

8 9

9 10

10 6

11 12

13 14

14 15

15 13

[出力例]

21600

[入力例]

16 15

1 2

3 2

4 3

5 6

6 7

7 5

8 9

9 10

11 10

11 8

12 13

13 14

14 15

15 16

16 12

[出力例]

77760

■参照サイト
AtCoder Beginner Contest 199（Sponsored by Panasonic）

2023年4月9日

C++ の動作確認をしてみた（９２３）

C++の練習を兼ねて, AtCoder Beginner Contest 296 の問題C (Gap Existence) ～問題E (Transition Game) を解いてみた.

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

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

■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, X;
    scanf("%d %d", &N, &X);
    set<int> st;
    rep(i, N){
        scanf("%d", &a[i]);
        st.insert(a[i]);
    }
    
    // 2. 存在するか？
    bool ok = false;
    rep(i, N) if(st.count(a[i] + X))  ok = true;
    
    // 3. 出力.
    printf("%s\n", ok ? "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--)

int a[202020];

int main(){

// 1. 入力情報.

int N, X;

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

set<int> st;

rep(i, N){

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

st.insert(a[i]);

}

// 2. 存在するか？

bool ok = false;

rep(i, N) if(st.count(a[i] + X)) ok = true;

// 3. 出力.

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

return 0;

}

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

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

[入力例]
6 -4
-2 -7 -1 -8 -2 -8

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

[入力例]
2 0
141421356 17320508

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

[入力例]
30 7
35 5 -40 -57 4 -35 81 -18 76 93 -88 -54 -28 49 -5 -40 -6 -30 75 -48 -21 -58 99 72 -99 55 91 67 -48 -96

[出力例]
Yes

[入力例]

6 5

3 1 4 1 5 9

[出力例]

Yes

※AtCoderテストケースより

[入力例]

6 -4

-2 -7 -1 -8 -2 -8

[出力例]

※AtCoderテストケースより

[入力例]

2 0

141421356 17320508

[出力例]

Yes

※AtCoderテストケースより

[入力例]

30 7

35 5 -40 -57 4 -35 81 -18 76 93 -88 -54 -28 49 -5 -40 -6 -30 75 -48 -21 -58 99 72 -99 55 91 67 -48 -96

[出力例]

Yes

■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--)
const LL INF = 202020202020202020;

int main(){
    
    // 1. 入力情報.
    LL N, M;
    scanf("%lld %lld", &N, &M);
    
    // 2. 全探索.
    LL ans = INF;
    int u = (int)sqrt(M) + 1;
    repx(a, 1, u + 1){
        LL b = M / a;
        if(M % a) ++b;
        if(a > N || b > N) continue;
        ans = min(ans, a * b);
    }
    
    // 3. 出力.
    printf("%lld\n", (ans == INF) ? -1 : ans);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

const LL INF = 202020202020202020;

int main(){

// 1. 入力情報.

LL N, M;

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

// 2. 全探索.

LL ans = INF;

int u = (int)sqrt(M) + 1;

repx(a, 1, u + 1){

LL b = M / a;

if(M % a) ++b;

if(a > N || b > N) continue;

ans = min(ans, a * b);

}

// 3. 出力.

printf("%lld\n", (ans == INF) ? -1 : ans);

return 0;

}

[入力例]
5 7

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

[入力例]
2 5

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

[入力例]
100000 10000000000

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

[入力例]
31 415

[出力例]
416

[入力例]
2023 2023401

[出力例]
2023405

[入力例]
2023409 9754525225

[出力例]
9754525225

[入力例]

5 7

[出力例]

※AtCoderテストケースより

[入力例]

2 5

[出力例]

-1

※AtCoderテストケースより

[入力例]

100000 10000000000

[出力例]

10000000000

※AtCoderテストケースより

[入力例]

31 415

[出力例]

416

[入力例]

2023 2023401

[出力例]

2023405

[入力例]

2023409 9754525225

[出力例]

9754525225

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

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

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    vvi G(N);
    rep(i, N){
        int a;
        scanf("%d", &a);
        --a;
        
        // 有向グラフ.
        G[i].pb(a);
        
        // 頂点次数.
        ++oDegree[i];
        ++iDegree[a];
    }
    
    // 2. 初期化(入次数 0, 出次数 1 の頂点).
    queue<int> q;
    rep(i, N) if(iDegree[i] == 0 && oDegree[i] == 1) q.push(i);
    
    // 3. 辺削除(出次数 1 の 頂点 を 除く).
    while(!q.empty()){
        // キューから取り出す.
        int u = q.front();
        q.pop();
        
        // 隣接頂点.
        for(auto &v : G[u]){
            // 辺(u, v) を 削除.
            --iDegree[v];
            --oDegree[u];
            
            // 入次数 0, 出次数 1 の 頂点.
            if(iDegree[v] == 0 && oDegree[v] == 1) q.push(v);
        }
    }
    
    // 4. 集計.
    int ans = 0;
    rep(i, N) if(iDegree[i] && oDegree[i]) ++ans;
    
    // 5. 出力.
    printf("%d\n", ans);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

using vvi = vector<vi>;

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

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

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

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

#define pb push_back

int iDegree[202020], oDegree[202020];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

vvi G(N);

rep(i, N){

int a;

scanf("%d", &a);

--a;

// 有向グラフ.

G[i].pb(a);

// 頂点次数.

++oDegree[i];

++iDegree[a];

}

// 2. 初期化(入次数 0, 出次数 1 の頂点).

queue<int> q;

rep(i, N) if(iDegree[i] == 0 && oDegree[i] == 1) q.push(i);

// 3. 辺削除(出次数 1 の頂点を除く).

while(!q.empty()){

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

int u = q.front();

q.pop();

// 隣接頂点.

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

// 辺(u, v) を削除.

--iDegree[v];

--oDegree[u];

// 入次数 0, 出次数 1 の頂点.

if(iDegree[v] == 0 && oDegree[v] == 1) q.push(v);

}

// 4. 集計.

int ans = 0;

rep(i, N) if(iDegree[i] && oDegree[i]) ++ans;

// 5. 出力.

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

return 0;

}

[入力例]
3
2 2 3

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

[入力例]
2
2 1

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

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

[出力例]
4

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

[出力例]
6

[入力例]
17
13 4 9 9 13 11 2 4 7 10 11 6 17 5 17 5 5

[出力例]
9

[入力例]
50
5 4 3 2 1 30 25 20 20 49 15 14 13 12 11 8 23 49 36 19 25 24 23 22 21 30 21 1 30 30 50 1 25 50 50 50 14 23 3 22 32 50 23 37 33 22 22 39 50 35

[出力例]
18

[入力例]

2 2 3

[出力例]

※AtCoderテストケースより

[入力例]

2 1

[出力例]

※AtCoderテストケースより

[入力例]

3 1 4 1 5 9 2 6 5

[出力例]

[入力例]

10 1 5 3 1 7 3 2 9 4 5

[出力例]

[入力例]

13 4 9 9 13 11 2 4 7 10 11 6 17 5 17 5 5

[出力例]

[入力例]

5 4 3 2 1 30 25 20 20 49 15 14 13 12 11 8 23 49 36 19 25 24 23 22 21 30 21 1 30 30 50 1 25 50 50 50 14 23 3 22 32 50 23 37 33 22 22 39 50 35

[出力例]

■参照サイト
AtCoder Beginner Contest 296

2023年4月8日

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

C++の練習を兼ねて, AtCoder Regular Contest 158 の問題A (+3 +5 +7) ～問題C (All Pair Digit Sums) を解いてみた.

■感想.
1. 問題A ～ C は, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 問題C で, 尺取り法の復習ができたので非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/arc158/editorial/5902
// 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. 入力情報.
    int T;
    scanf("%d", &T);
    
    // 2. テストケース.
    rep(i, T){
        // 2-1. 各テストケース.
        LL x1, x2, x3;
        scanf("%lld %lld %lld", &x1, &x2, &x3);
        
        // 2-2. 例外(その①).
        LL a = x1 + x2 + x3;
        if(a % 3 != 0){
            puts("-1");
            continue;
        }
        
        // 2-3. 例外(その②).
        a /= 3;
        if(!((a % 2 == x1 % 2) && (a % 2 == x2 % 2) && (a % 2 == x3 % 2))){
            puts("-1");
            continue;
        }
        
        // 2-4. 最小の操作回数は？
        printf("%lld\n", (abs(x1 - a) + abs(x2 - a) + abs(x3 - a)) / 4);
    }
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc158/editorial/5902

// 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. 入力情報.

int T;

scanf("%d", &T);

// 2. テストケース.

rep(i, T){

// 2-1. 各テストケース.

LL x1, x2, x3;

scanf("%lld %lld %lld", &x1, &x2, &x3);

// 2-2. 例外(その①).

LL a = x1 + x2 + x3;

if(a % 3 != 0){

puts("-1");

continue;

}

// 2-3. 例外(その②).

a /= 3;

if(!((a % 2 == x1 % 2) && (a % 2 == x2 % 2) && (a % 2 == x3 % 2))){

puts("-1");

continue;

}

// 2-4. 最小の操作回数は？

printf("%lld\n", (abs(x1 - a) + abs(x2 - a) + abs(x3 - a)) / 4);

}

return 0;

}

[入力例]
4
2 8 8
1 1 1
5 5 10
10 100 1000

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

[入力例]
10
57 27 87
31 41 51
92 18 46
101 131 191
333 555 777
300 600 900
27 106 56
88 148 208
78 76 121
20 4 84

[出力例]
15
5
20
25
111
150
-1
30
-1
24

[入力例]

2 8 8

1 1 1

5 5 10

10 100 1000

[出力例]

-1

315

※AtCoderのテストケースより

[入力例]

57 27 87

31 41 51

92 18 46

101 131 191

333 555 777

300 600 900

27 106 56

88 148 208

78 76 121

20 4 84

[出力例]

111

150

-1

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

// 解き直し.
// https://atcoder.jp/contests/arc158/editorial/5903
// 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 pb push_back
int a[2020202];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    vi X;
    rep(i, N){
        int x;
        scanf("%d", &x);
        if(N < 6) X.pb(x);
        x += 1e6;
        ++a[x];
    }
    
    // 2. 小さい方から三つ.
    vi vMin;
    repr(i, 1e6 - 1, 0) rep(j, a[i])   if(vMin.size() < 3) vMin.pb(i - 1e6);
    repr(i, 2e6, 1e6 + 1) rep(j, a[i]) if(vMin.size() < 3) vMin.pb(i - 1e6);
    // for(auto &p : vMin) printf("%d\n", p);
    
    // 3. 大きい方から三つ.
    vi vMax;
    repx(i, 1e6 + 1, 2e6 + 1) rep(j, a[i]) if(vMax.size() < 3) vMax.pb(i - 1e6);
    rep(i, 1e6) rep(j, a[i])               if(vMax.size() < 3) vMax.pb(i - 1e6);
    // for(auto &p : vMax) printf("%d\n", p);
    
    // 4. 多重集合 X.
    if(!X.size()){
        for(auto &p : vMin) X.pb(p);
        for(auto &p : vMax) X.pb(p);
    }
    
    // 5. 最小値, 最大値は？
    int n = X.size();
    double aMin = +2020202020202020202.0;
    double aMax = -2020202020202020202.0;
    rep(i, n){
        rep(j, n){
            rep(k, n){
                if(i != j && j != k && k != i){
                    double cur = (double)(X[i] + X[j] + X[k]);
                    cur /= (double)(X[i]);
                    cur /= (double)(X[j]);
                    cur /= (double)(X[k]);
                    aMin = min(aMin, cur);
                    aMax = max(aMax, cur);
                }
            }
        }
    }
    
    // 6. 出力.
    printf("%.15lf\n%.15lf\n", aMin, aMax);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc158/editorial/5903

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

int a[2020202];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

vi X;

rep(i, N){

int x;

scanf("%d", &x);

if(N < 6) X.pb(x);

x += 1e6;

++a[x];

}

// 2. 小さい方から三つ.

vi vMin;

repr(i, 1e6 - 1, 0) rep(j, a[i]) if(vMin.size() < 3) vMin.pb(i - 1e6);

repr(i, 2e6, 1e6 + 1) rep(j, a[i]) if(vMin.size() < 3) vMin.pb(i - 1e6);

// for(auto &p : vMin) printf("%d\n", p);

// 3. 大きい方から三つ.

vi vMax;

repx(i, 1e6 + 1, 2e6 + 1) rep(j, a[i]) if(vMax.size() < 3) vMax.pb(i - 1e6);

rep(i, 1e6) rep(j, a[i]) if(vMax.size() < 3) vMax.pb(i - 1e6);

// for(auto &p : vMax) printf("%d\n", p);

// 4. 多重集合 X.

if(!X.size()){

for(auto &p : vMin) X.pb(p);

for(auto &p : vMax) X.pb(p);

}

// 5. 最小値, 最大値は？

int n = X.size();

double aMin = +2020202020202020202.0;

double aMax = -2020202020202020202.0;

rep(i, n){

rep(j, n){

rep(k, n){

if(i != j && j != k && k != i){

double cur = (double)(X[i] + X[j] + X[k]);

cur /= (double)(X[i]);

cur /= (double)(X[j]);

cur /= (double)(X[k]);

aMin = min(aMin, cur);

aMax = max(aMax, cur);

}

// 6. 出力.

printf("%.15lf\n%.15lf\n", aMin, aMax);

return 0;

}

[入力例]
4
-2 -4 4 5

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

[入力例]
4
1 1 1 1

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

[入力例]
5
1 2 3 4 5

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

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

[出力例]
0.074074074074074
2.000000000000000

[入力例]
25
-62654 38060 -40395 73411 32287 -31964 -6069 -59569 -18953 18276 -81815 84325 23611 65481 19093 -68288 76696 84093 66270 91521 -64748 -14904 -17338 58638 95110

[出力例]
-0.000000014779913
0.000000024428934

[入力例]
100
69916 -958462 175350 663506 174976 381343 837499 -218757 486796 -109940 -387930 116682 869009 215328 -85009 -817691 581748 711432 -170442 707919 14179 -463495 -476948 -673290 -913092 11249 -189868 -746976 505087 -622496 849045 838323 716835 784815 -185511 -4073 -951883 -370116 -911945 74817 -767359 769381 104268 -176164 -571565 605559 -678942 -324080 133562 -79780 94243 852129 -250020 578113 -197780 613104 714339 320649 323447 743163 420709 299303 -793398 258040 -46584 -164749 656078 859105 355055 126428 410186 988732 -504969 200275 770031 -63896 -147531 418090 274663 -796636 36168 217126 -254489 709912 44747 281016 -499495 709992 212867 -218466 349600 -60391 -466757 -743023 259071 24453 -888436 -138187 246464 788471

[出力例]
-0.000000032871964
0.000000012789203

[入力例]

-2 -4 4 5

[出力例]

-0.175000000000000

-0.025000000000000

※AtCoderのテストケースより

[入力例]

1 1 1 1

[出力例]

3.000000000000000

※AtCoderのテストケースより

[入力例]

1 2 3 4 5

[出力例]

0.200000000000000

1.000000000000000

※AtCoderのテストケースより

[入力例]

3 1 4 1 5 9 2 6 5 3

[出力例]

0.074074074074074

2.000000000000000

[入力例]

-62654 38060 -40395 73411 32287 -31964 -6069 -59569 -18953 18276 -81815 84325 23611 65481 19093 -68288 76696 84093 66270 91521 -64748 -14904 -17338 58638 95110

[出力例]

-0.000000014779913

0.000000024428934

[入力例]

100

69916 -958462 175350 663506 174976 381343 837499 -218757 486796 -109940 -387930 116682 869009 215328 -85009 -817691 581748 711432 -170442 707919 14179 -463495 -476948 -673290 -913092 11249 -189868 -746976 505087 -622496 849045 838323 716835 784815 -185511 -4073 -951883 -370116 -911945 74817 -767359 769381 104268 -176164 -571565 605559 -678942 -324080 133562 -79780 94243 852129 -250020 578113 -197780 613104 714339 320649 323447 743163 420709 299303 -793398 258040 -46584 -164749 656078 859105 355055 126428 410186 988732 -504969 200275 770031 -63896 -147531 418090 274663 -796636 36168 217126 -254489 709912 44747 281016 -499495 709992 212867 -218466 349600 -60391 -466757 -743023 259071 24453 -888436 -138187 246464 788471

[出力例]

-0.000000032871964

0.000000012789203

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

// 解き直し.
// https://atcoder.jp/contests/arc158/editorial/5904
// 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
#define all(x) x.begin(), x.end()
LL a[202020];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    LL aMax = 0;
    rep(i, N){
        scanf("%lld", &a[i]);
        aMax = max(aMax, a[i]);
    }
    
    // 2. f.
    auto f = [&](LL n) -> LL {
        LL ret = 0;
        assert(n >= 0);
        while(n){
            ret += n % 10;
            n /= 10;
        }
        return ret;
    };
    
    // 3. 合計.
    LL ans = 0;
    rep(i, N) ans += f(a[i]) * 2 * N;
    
    // 4. 最大桁数 K.
    int K = 0;
    while(aMax){
        ++K;
        aMax /= 10;
    }
    
    // 5. 桁上がり分 を 集計.
    LL carry = 0, d = 1;
    rep(k, K){
        // 10 の (k + 1)乗.
        d *= 10;
        
        // 余り x[i].
        vl x;
        rep(i, N) x.pb(a[i] % d);
        
        // sort.
        sort(all(x));
        
        // 尺取り法.
        int cur = N - 1;
        rep(l, N){
            // 右側.
            int s = cur;
            repr(r, s, l){
                // 更新.
                cur = r;
                
                // 桁上がりが見つかった.
                if(x[l] + x[r] >= d) continue;
                
                // 次へ.
                break;
            }
            
            // 桁上がり分を加算.
            if(l < cur) carry += 2 * (N - 1 - cur);
            
            // 終了条件.
            if(l >= cur){
                // 桁上がり分を加算.
                carry += (LL)(N - cur) * (LL)(N - cur);
                if(x[l] + x[cur] < d) --carry;
                
                // 終了.
                break;
            }
        }
    }
    
    // 6. 桁上がり分 を 減算.
    ans -= carry * 9;
    
    // 7. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

100

// 解き直し.

// https://atcoder.jp/contests/arc158/editorial/5904

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

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

LL a[202020];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

LL aMax = 0;

rep(i, N){

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

aMax = max(aMax, a[i]);

}

// 2. f.

auto f = [&](LL n) -> LL {

LL ret = 0;

assert(n >= 0);

while(n){

ret += n % 10;

n /= 10;

}

return ret;

};

// 3. 合計.

LL ans = 0;

rep(i, N) ans += f(a[i]) * 2 * N;

// 4. 最大桁数 K.

int K = 0;

while(aMax){

++K;

aMax /= 10;

}

// 5. 桁上がり分を集計.

LL carry = 0, d = 1;

rep(k, K){

// 10 の (k + 1)乗.

d *= 10;

// 余り x[i].

vl x;

rep(i, N) x.pb(a[i] % d);

// sort.

sort(all(x));

// 尺取り法.

int cur = N - 1;

rep(l, N){

// 右側.

int s = cur;

repr(r, s, l){

// 更新.

cur = r;

// 桁上がりが見つかった.

if(x[l] + x[r] >= d) continue;

// 次へ.

break;

}

// 桁上がり分を加算.

if(l < cur) carry += 2 * (N - 1 - cur);

// 終了条件.

if(l >= cur){

// 桁上がり分を加算.

carry += (LL)(N - cur) * (LL)(N - cur);

if(x[l] + x[cur] < d) --carry;

// 終了.

break;

}

// 6. 桁上がり分を減算.

ans -= carry * 9;

// 7. 出力.

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

return 0;

}

[入力例]
2
53 28

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

[入力例]
1
999999999999999

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

[入力例]
5
123 456 789 101 112

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

[入力例]
10
877 2585 7531 11636 5407 10490 2919 4532 11968 6571

[出力例]
1826

[入力例]
20
2393459 2597592 9505071 7781639 3941269 11574647 10141029 7729956 5040599 7776400 4374539 4798162 1267669 959174 1602926 892360 3494352 8402891 4887639 9792278

[出力例]
13238

[入力例]
100
106830287 96297137 99507332 120542676 12480615 7988160 102303598 43518574 49587435 94374908 7640495 88460951 118398168 61221541 113945917 105266591 88283842 99682740 75784384 27248820 46611683 63624340 3243101 74574568 60575314 42966526 119849902 110794016 114392684 110470545 96730113 119821124 123444633 109708206 83442219 49800640 87862787 21189091 91254742 52378699 118374037 77594928 63008973 13058689 79673135 14169600 43908552 71245022 101211144 31151792 101626330 50762445 32103874 117480389 68620838 44935862 40259456 104169855 84453646 80701603 67655779 2143857 116506450 60053024 7312992 94662630 57846804 89395004 16571557 98434911 74528701 23929873 66957073 41170766 75800861 100453435 51092328 6798915 46133408 84964698 50926294 70015591 91551909 105928166 63985408 93857936 31874447 62932675 67370594 7590564 67516487 69931336 18257230 63202372 37661017 32950199 53732043 60295509 62016818 93710886

[出力例]
367109

[入力例]
300
103 105 82 73 36 50 55 73 15 104 40 115 41 50 57 94 77 48 37 33 47 123 9 54 102 90 42 79 18 95 88 60 40 52 116 75 122 120 101 61 33 60 55 113 117 76 38 61 91 40 100 109 102 84 25 74 80 87 15 91 22 80 33 32 23 86 47 7 116 60 93 112 103 89 102 108 81 2 106 103 39 119 19 6 66 69 107 36 37 34 108 119 93 36 62 78 34 98 106 64 52 102 56 60 55 88 100 17 14 38 103 87 84 73 61 24 20 56 104 74 184 36 47 50 30 54 91 58 63 104 18 99 61 41 53 55 34 3 19 115 96 98 3 114 60 97 51 43 78 27 61 116 88 18 73 12 75 75 78 37 42 64 92 73 84 32 56 77 6 79 90 122 7 12 122 108 57 33 71 105 11 21 109 63 2 79 114 29 51 102 115 110 109 33 106 61 122 24 25 53 8 96 86 49 15 90 81 120 22 52 40 39 71 107 34 9 64 20 100 115 27 6 42 56 98 77 23 74 28 98 71 50 15 70 75 221 16 74 39 117 111 91 100 64 99 18 43 76 121 17 38 105 91 92 52 117 69 96 72 61 77 121 84 7 6 112 97 115 63 112 98 2 86 195 118 47 52 121 75 99 18 79 25 127 10 35 121 89 108 101 11 40 74 5 62 81 65 104 111 121

[出力例]
884175

[入力例]
500
16285 13619 21183 21387 5008 17859 1156 3979 11678 20593 13590 10077 9381 21353 21672 9870 7211 896 12621 17778 15867 15297 21792 12378 118 9215 17872 12318 18773 17838 3565 8979 10067 18578 8079 13778 17207 7897 17187 15553 7630 13517 7931 1917 11753 12577 1152 17281 2188 3508 7666 15183 9121 367 10872 7191 11916 18617 21869 8653 3127 17019 20172 11297 2058 968 20723 16899 21370 12676 7137 7296 21557 20577 11276 17760 7777 17375 12367 1652 15593 18375 1680 7358 17785 17915 10036 18997 9789 7902 17965 19732 8920 7915 2029 21157 6783 11259 287 13737 11959 18892 15762 11273 19806 1076 13560 3959 8391 13301 10809 6897 6370 18215 7550 18523 20537 17659 1230 7210 9167 2573 9177 6278 7775 325 19779 16977 12077 8887 17965 3799 2976 20725 8737 18595 5983 20551 13107 9323 195 5038 20036 16508 6562 5767 10786 1298 18673 2610 7935 1975 7096 19635 13370 6358 6591 15879 15623 3318 12717 19289 7770 3357 9917 18706 1836 8532 13667 117 3077 6863 12358 17560 9755 5569 13995 20167 3660 9608 20772 22026 5301 9797 9912 17551 12372 7830 19150 6151 8655 18257 3523 8027 16531 8129 511 17517 7332 3967 18399 3000 673 595 7363 7662 17963 22155 21253 22052 13573 16723 7509 6630 13359 21376 20277 5658 17892 11766 18570 20877 13271 7858 6238 19327 7251 7570 2218 17780 3978 16857 9021 17317 19685 7387 5735 760 15507 230 19107 10939 17297 217 10079 15991 17500 7099 10292 6121 9376 5715 7688 3868 582 12671 11307 21157 5579 13317 5852 7857 17395 3008 17600 19790 20957 17869 17731 17678 16770 18259 20973 19185 5581 9577 8365 6782 2560 13785 10600 3687 3100 17756 10291 7328 15886 18703 11500 652 21839 17200 7016 7850 20179 13593 7983 36 11973 327 6099 17693 17572 6965 17173 12799 19212 12997 20768 775 8215 7531 9799 12973 3380 11732 6761 17099 6213 12970 17865 16291 20099 587 15802 11672 5171 12068 8871 3605 7860 17517 11606 850 15832 6060 18112 16997 1873 8571 5171 13957 5957 11656 13217 18768 16056 7173 17233 6502 20786 6320 11533 20197 17360 11877 12818 19906 10371 11500 17168 11777 3171 1787 13995 21803 10078 771 9860 10296 763 2702 8101 11817 18377 7168 16806 17813 17017 16717 17518 7851 13857 6659 726 7582 19919 8886 7087 19380 12071 19502 1178 15618 1986 16831 20566 15178 8387 3133 16867 10860 3832 17655 3999 16711 17970 21659 2265 979 19372 6067 695 12291 13502 17831 17602 8505 2763 18920 7789 20161 5027 17710 18785 11275 1326 16270 3067 6773 18812 6112 22127 2917 6897 20236 11867 7332 8572 18193 7059 11921 7050 6772 7913 13931 7839 19566 17177 17722 12167 19880 7998 9188 17171 21258 17778 16291 20831 21779 17817 5556 15612 8762 1838 12591 10375 17697 17627 8057 7900 20991 6778 9910 2038 8162 15851 5632 7067 10623 11977 7580 3016 18097 3535 2283 11093 16807 21797 19750 1161 525 8788 11278 1679 10878 20818 12762 12032 17105

[出力例]
5062588

[入力例]

53 28

[出力例]

※AtCoderのテストケースより

[入力例]

999999999999999

[出力例]

135

※AtCoderのテストケースより

[入力例]

123 456 789 101 112

[出力例]

321

※AtCoderのテストケースより

[入力例]

877 2585 7531 11636 5407 10490 2919 4532 11968 6571

[出力例]

1826

[入力例]

2393459 2597592 9505071 7781639 3941269 11574647 10141029 7729956 5040599 7776400 4374539 4798162 1267669 959174 1602926 892360 3494352 8402891 4887639 9792278

[出力例]

13238

[入力例]

100

106830287 96297137 99507332 120542676 12480615 7988160 102303598 43518574 49587435 94374908 7640495 88460951 118398168 61221541 113945917 105266591 88283842 99682740 75784384 27248820 46611683 63624340 3243101 74574568 60575314 42966526 119849902 110794016 114392684 110470545 96730113 119821124 123444633 109708206 83442219 49800640 87862787 21189091 91254742 52378699 118374037 77594928 63008973 13058689 79673135 14169600 43908552 71245022 101211144 31151792 101626330 50762445 32103874 117480389 68620838 44935862 40259456 104169855 84453646 80701603 67655779 2143857 116506450 60053024 7312992 94662630 57846804 89395004 16571557 98434911 74528701 23929873 66957073 41170766 75800861 100453435 51092328 6798915 46133408 84964698 50926294 70015591 91551909 105928166 63985408 93857936 31874447 62932675 67370594 7590564 67516487 69931336 18257230 63202372 37661017 32950199 53732043 60295509 62016818 93710886

[出力例]

367109

[入力例]

300

103 105 82 73 36 50 55 73 15 104 40 115 41 50 57 94 77 48 37 33 47 123 9 54 102 90 42 79 18 95 88 60 40 52 116 75 122 120 101 61 33 60 55 113 117 76 38 61 91 40 100 109 102 84 25 74 80 87 15 91 22 80 33 32 23 86 47 7 116 60 93 112 103 89 102 108 81 2 106 103 39 119 19 6 66 69 107 36 37 34 108 119 93 36 62 78 34 98 106 64 52 102 56 60 55 88 100 17 14 38 103 87 84 73 61 24 20 56 104 74 184 36 47 50 30 54 91 58 63 104 18 99 61 41 53 55 34 3 19 115 96 98 3 114 60 97 51 43 78 27 61 116 88 18 73 12 75 75 78 37 42 64 92 73 84 32 56 77 6 79 90 122 7 12 122 108 57 33 71 105 11 21 109 63 2 79 114 29 51 102 115 110 109 33 106 61 122 24 25 53 8 96 86 49 15 90 81 120 22 52 40 39 71 107 34 9 64 20 100 115 27 6 42 56 98 77 23 74 28 98 71 50 15 70 75 221 16 74 39 117 111 91 100 64 99 18 43 76 121 17 38 105 91 92 52 117 69 96 72 61 77 121 84 7 6 112 97 115 63 112 98 2 86 195 118 47 52 121 75 99 18 79 25 127 10 35 121 89 108 101 11 40 74 5 62 81 65 104 111 121

[出力例]

884175

[入力例]

500

16285 13619 21183 21387 5008 17859 1156 3979 11678 20593 13590 10077 9381 21353 21672 9870 7211 896 12621 17778 15867 15297 21792 12378 118 9215 17872 12318 18773 17838 3565 8979 10067 18578 8079 13778 17207 7897 17187 15553 7630 13517 7931 1917 11753 12577 1152 17281 2188 3508 7666 15183 9121 367 10872 7191 11916 18617 21869 8653 3127 17019 20172 11297 2058 968 20723 16899 21370 12676 7137 7296 21557 20577 11276 17760 7777 17375 12367 1652 15593 18375 1680 7358 17785 17915 10036 18997 9789 7902 17965 19732 8920 7915 2029 21157 6783 11259 287 13737 11959 18892 15762 11273 19806 1076 13560 3959 8391 13301 10809 6897 6370 18215 7550 18523 20537 17659 1230 7210 9167 2573 9177 6278 7775 325 19779 16977 12077 8887 17965 3799 2976 20725 8737 18595 5983 20551 13107 9323 195 5038 20036 16508 6562 5767 10786 1298 18673 2610 7935 1975 7096 19635 13370 6358 6591 15879 15623 3318 12717 19289 7770 3357 9917 18706 1836 8532 13667 117 3077 6863 12358 17560 9755 5569 13995 20167 3660 9608 20772 22026 5301 9797 9912 17551 12372 7830 19150 6151 8655 18257 3523 8027 16531 8129 511 17517 7332 3967 18399 3000 673 595 7363 7662 17963 22155 21253 22052 13573 16723 7509 6630 13359 21376 20277 5658 17892 11766 18570 20877 13271 7858 6238 19327 7251 7570 2218 17780 3978 16857 9021 17317 19685 7387 5735 760 15507 230 19107 10939 17297 217 10079 15991 17500 7099 10292 6121 9376 5715 7688 3868 582 12671 11307 21157 5579 13317 5852 7857 17395 3008 17600 19790 20957 17869 17731 17678 16770 18259 20973 19185 5581 9577 8365 6782 2560 13785 10600 3687 3100 17756 10291 7328 15886 18703 11500 652 21839 17200 7016 7850 20179 13593 7983 36 11973 327 6099 17693 17572 6965 17173 12799 19212 12997 20768 775 8215 7531 9799 12973 3380 11732 6761 17099 6213 12970 17865 16291 20099 587 15802 11672 5171 12068 8871 3605 7860 17517 11606 850 15832 6060 18112 16997 1873 8571 5171 13957 5957 11656 13217 18768 16056 7173 17233 6502 20786 6320 11533 20197 17360 11877 12818 19906 10371 11500 17168 11777 3171 1787 13995 21803 10078 771 9860 10296 763 2702 8101 11817 18377 7168 16806 17813 17017 16717 17518 7851 13857 6659 726 7582 19919 8886 7087 19380 12071 19502 1178 15618 1986 16831 20566 15178 8387 3133 16867 10860 3832 17655 3999 16711 17970 21659 2265 979 19372 6067 695 12291 13502 17831 17602 8505 2763 18920 7789 20161 5027 17710 18785 11275 1326 16270 3067 6773 18812 6112 22127 2917 6897 20236 11867 7332 8572 18193 7059 11921 7050 6772 7913 13931 7839 19566 17177 17722 12167 19880 7998 9188 17171 21258 17778 16291 20831 21779 17817 5556 15612 8762 1838 12591 10375 17697 17627 8057 7900 20991 6778 9910 2038 8162 15851 5632 7067 10623 11977 7580 3016 18097 3535 2283 11093 16807 21797 19750 1161 525 8788 11278 1679 10878 20818 12762 12032 17105

[出力例]

5062588

■参照サイト
AtCoder Regular Contest 158

2023年4月3日

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

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

■感想.
1. 問題F は, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. TLEをギリギリ回避している実装(1793[ms])なので, 高速化について, 将来的な課題として残っている.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/abc137/editorial.pdf
// 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 int LIMIT = 3030;
LL FAC[LIMIT], INV[LIMIT], a[LIMIT], b[LIMIT], t[LIMIT];

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

// 組み合わせ(nCk)計算用(mod版).
// ※配列FAC, INV は, 事前に計算済のものを使う.
// @param n: 対象となる要素の個数.
// @param k: 選択する要素の個数.
// @return: 組み合わせ(nCk)の計算結果(mod版).
LL combination(LL n, LL k, LL MOD){
    if(n < 0 || k < 0 || k > n) return 0;
    LL ret = FAC[n] * INV[k] % MOD * INV[n - k] % MOD;
    return ret;
}

int main(){
    
    // 1. 入力情報.
    int p;
    scanf("%d", &p);
    rep(i, p) scanf("%lld", &a[i]);
    
    // 2. 事前準備.
    FAC[0] = INV[0] = 1;
    repx(i, 1, LIMIT){
        FAC[i] = (LL)i * FAC[i - 1] % p;
        INV[i] = mPow(FAC[i], p - 2, p);
    }
    
    // 3. 集計.
    rep(j, p){
        // Skip.
        if(!a[j]) continue;
        
        // 初期化.
        rep(i, LIMIT) t[i] = 0;
        
        // 1 - {(x - j) の (p - 1)乗} を 展開.
        bool sign = false;
        repr(i, p - 1, 0){
            t[i] = sign ? combination(p - 1, i, p) : (p - combination(p - 1, i, p));
            t[i] = t[i] * mPow(j, p - 1 - i, p) % p;
            sign = !sign;
        }
        
        // 定数項補正.
        t[0] = (t[0] + 1) % p;
        
        // 加算.
        rep(i, p) b[i] = (b[i] + t[i]) % p;
    }
    
    // 4. 出力.
    rep(i, p) printf("%lld%s", b[i], (i < p - 1) ? " " : "\n");
    return 0;
    
}

// 解き直し.

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

// 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 int LIMIT = 3030;

LL FAC[LIMIT], INV[LIMIT], a[LIMIT], b[LIMIT], t[LIMIT];

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

// -> 引数 MOD は, 素数と限らないので, 逆元の計算に使用する場合は, 注意する.

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

// @param b: 指数.

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

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

LL t = 1;

while(b){

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

a = a * a % MOD;

b >>= 1;

}

return t;

}

// 組み合わせ(nCk)計算用(mod版).

// ※配列FAC, INV は, 事前に計算済のものを使う.

// @param n: 対象となる要素の個数.

// @param k: 選択する要素の個数.

// @return: 組み合わせ(nCk)の計算結果(mod版).

LL combination(LL n, LL k, LL MOD){

if(n < 0 || k < 0 || k > n) return 0;

LL ret = FAC[n] * INV[k] % MOD * INV[n - k] % MOD;

return ret;

}

int main(){

// 1. 入力情報.

int p;

scanf("%d", &p);

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

// 2. 事前準備.

FAC[0] = INV[0] = 1;

repx(i, 1, LIMIT){

FAC[i] = (LL)i * FAC[i - 1] % p;

INV[i] = mPow(FAC[i], p - 2, p);

}

// 3. 集計.

rep(j, p){

// Skip.

if(!a[j]) continue;

// 初期化.

rep(i, LIMIT) t[i] = 0;

// 1 - {(x - j) の (p - 1)乗} を展開.

bool sign = false;

repr(i, p - 1, 0){

t[i] = sign ? combination(p - 1, i, p) : (p - combination(p - 1, i, p));

t[i] = t[i] * mPow(j, p - 1 - i, p) % p;

sign = !sign;

}

// 定数項補正.

t[0] = (t[0] + 1) % p;

// 加算.

rep(i, p) b[i] = (b[i] + t[i]) % p;

}

// 4. 出力.

rep(i, p) printf("%lld%s", b[i], (i < p - 1) ? " " : "\n");

return 0;

}

[入力例]
2
1 0

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

[入力例]
3
0 0 0

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

[入力例]
5
0 1 0 1 0

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

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

[出力例]
0 5 0 1 0 5 4

[入力例]
11
0 0 1 0 0 0 1 0 1 0 0

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

[入力例]
17
0 0 1 0 0 0 1 0 1 0 0 1 1 1 0 0 1

[出力例]
0 14 1 1 4 15 12 7 16 0 16 12 13 10 5 0 10 

[入力例]
331
0 0 1 0 1 1 1 0 1 1 0 0 0 1 0 0 0 0 0 1 1 0 1 0 1 0 1 0 1 1 0 1 1 0 1 0 1 1 0 1 1 1 0 1 1 1 1 1 0 1 0 1 0 0 0 0 0 1 0 0 1 1 1 0 0 1 1 0 1 1 0 0 1 1 1 0 0 0 0 1 1 1 1 1 0 1 0 1 1 0 1 1 1 0 1 0 1 1 1 1 0 1 0 1 0 0 1 0 1 1 1 0 1 1 1 1 0 0 0 1 0 0 0 0 0 0 1 1 0 0 1 0 1 1 1 1 1 1 1 1 0 0 0 1 0 1 0 1 0 0 0 1 1 1 0 0 0 0 0 0 1 0 0 1 0 0 1 1 1 1 1 0 0 1 0 1 0 0 1 1 0 1 1 1 0 1 0 0 0 1 0 0 0 0 1 0 1 1 1 0 1 0 0 0 1 0 1 1 1 1 1 1 1 1 0 1 0 1 1 1 0 1 0 0 1 1 0 1 1 1 0 0 1 0 1 0 0 1 1 1 1 0 0 0 0 1 1 0 0 0 1 1 0 1 1 0 1 0 1 0 1 1 1 0 1 0 0 0 1 0 1 0 1 0 1 1 1 1 0 1 0 1 0 1 1 1 1 0 0 0 0 0 0 1 0 1 1 0 1 1 1 0 0 0 0 0 1 1 0 0 0 0 1 1 0 1 1 1 1 1 1 0 1 1 1 0 0 0 0 1 0

[出力例]
0 270 29 28 211 326 92 161 309 74 132 135 28 242 187 243 185 253 58 165 253 31 0 297 289 236 323 67 2 207 156 248 113 174 12 12 176 254 118 107 176 253 6 283 218 8 261 79 115 48 156 165 23 185 294 122 45 217 32 237 135 110 224 299 104 246 99 243 153 53 202 322 54 201 123 282 125 68 308 248 73 263 16 274 261 102 67 57 21 1 5 104 46 117 74 11 324 59 95 248 100 110 203 304 170 276 252 317 184 213 312 213 163 138 21 289 167 316 119 145 275 191 206 63 12 200 204 204 294 242 224 23 308 208 30 195 42 192 232 293 162 96 8 15 173 291 232 36 125 110 239 115 126 230 18 1 177 23 185 23 219 71 207 98 254 3 184 306 324 45 290 137 81 174 8 135 183 237 179 81 32 202 115 204 304 271 252 188 135 158 239 303 123 100 69 326 63 75 188 43 109 132 233 77 43 66 86 153 121 63 85 77 66 143 180 197 145 51 261 308 44 236 202 87 173 292 254 43 168 21 165 320 196 122 91 258 212 104 6 280 210 23 150 176 127 6 31 137 189 140 113 97 325 57 100 212 271 308 80 7 107 318 164 25 42 200 2 210 19 170 213 258 270 10 58 200 88 268 205 83 164 261 50 55 262 29 61 68 16 316 276 260 237 48 13 208 158 248 18 187 304 265 307 234 109 207 259 46 322 91 64 119 185 128 159 142 273 171 255 270 105 92 285 221 206 101 232 52 156 62 156

[入力例]
2027
0 1 1 1 0 1 0 0 1 0 1 1 0 0 1 0 0 1 0 0 1 1 1 1 1 0 0 0 1 1 1 1 1 1 0 0 0 1 1 0 1 0 1 1 1 1 1 1 1 1 0 1 0 1 1 1 1 0 1 1 1 1 1 0 0 0 1 0 0 1 0 0 1 0 1 1 0 0 1 0 1 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 1 0 1 0 0 1 0 1 0 0 0 1 0 1 1 1 0 0 0 0 1 1 0 1 1 1 0 1 1 0 0 1 0 1 1 0 0 1 1 1 0 1 0 1 1 1 1 1 0 1 0 0 0 1 1 1 1 0 0 1 0 1 1 1 0 0 0 1 0 0 1 1 0 0 0 0 0 1 1 1 0 1 0 1 0 1 0 1 0 0 1 0 0 0 0 0 0 1 1 0 1 0 1 1 1 1 0 1 1 1 1 0 0 0 1 0 0 0 0 1 1 1 1 1 0 0 1 1 0 0 0 1 1 0 0 1 1 0 1 0 0 1 1 1 1 0 0 0 1 1 0 0 1 1 0 1 1 1 0 1 0 1 0 0 1 1 0 1 1 0 1 0 0 0 0 0 0 1 0 0 1 0 1 0 1 1 1 1 0 1 1 0 1 1 0 1 0 1 1 0 1 1 0 1 0 1 1 0 1 0 0 0 0 1 0 1 0 0 0 1 0 1 0 0 1 0 1 0 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 0 1 0 0 0 1 1 1 0 0 0 1 1 0 1 1 0 0 0 1 1 0 0 0 0 0 0 1 0 1 0 1 0 1 1 0 1 1 0 1 1 0 1 1 1 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 1 1 1 0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 1 1 1 0 1 0 1 1 0 0 1 0 1 1 1 1 0 1 1 1 1 1 0 1 0 0 1 1 0 0 0 1 0 0 1 1 1 1 1 1 0 0 0 1 0 1 0 0 1 0 1 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 1 1 0 1 1 0 0 1 1 1 1 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 1 0 0 0 1 0 1 0 1 1 0 1 1 1 1 0 0 0 0 0 1 0 0 0 1 1 0 0 0 0 0 0 1 1 1 0 0 1 1 0 1 1 1 1 0 0 1 0 1 1 1 1 0 1 0 1 0 1 1 0 0 1 0 1 0 0 1 0 0 0 1 0 1 1 0 0 0 0 1 0 1 0 1 0 1 0 1 1 0 1 1 0 0 1 1 0 0 1 1 1 1 1 1 1 0 1 1 0 0 1 0 1 1 1 0 1 0 1 1 1 0 0 1 1 1 0 1 1 1 0 0 0 1 1 0 1 1 1 0 1 0 0 0 0 1 0 0 0 0 1 1 1 0 0 0 0 1 1 0 1 0 1 1 0 0 0 0 0 1 0 1 0 0 0 0 1 1 1 1 1 0 1 0 1 1 1 0 1 1 1 1 1 1 1 0 0 1 1 0 1 1 0 0 1 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 0 1 1 0 1 0 0 1 0 0 0 0 0 1 1 1 1 0 0 1 0 0 0 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 0 0 0 1 1 1 1 1 0 0 1 0 1 0 0 0 1 1 0 0 0 1 0 0 0 0 0 1 1 1 0 0 1 0 0 0 1 0 0 0 0 1 0 1 0 1 1 1 1 0 1 1 1 0 1 0 0 0 1 0 0 0 1 1 0 0 0 1 1 0 0 0 1 0 1 1 1 0 1 1 0 0 0 1 1 1 0 1 0 0 0 0 1 0 1 0 1 1 0 0 0 1 1 0 0 1 1 1 0 0 0 1 0 0 0 0 0 1 1 0 1 1 0 1 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 1 0 0 1 1 0 0 1 1 0 0 0 1 1 0 0 1 0 0 0 1 0 0 1 1 1 1 1 0 0 0 1 1 0 1 0 1 0 1 0 1 1 1 0 1 1 1 0 1 1 1 1 1 0 0 1 1 0 1 0 0 1 0 0 1 1 0 0 0 1 0 0 1 1 0 0 1 1 1 1 0 1 1 0 1 0 1 0 1 0 1 0 0 1 0 1 0 0 0 1 0 1 0 0 1 1 0 0 0 0 0 1 0 0 0 1 1 1 0 1 0 0 0 0 0 1 1 0 0 1 1 0 0 0 0 1 0 1 1 1 0 0 1 1 1 0 1 1 0 1 0 1 0 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 1 0 1 1 1 0 1 1 0 1 0 1 0 1 1 0 0 1 0 0 1 1 0 1 1 0 1 0 1 0 0 1 1 1 0 0 0 0 0 0 1 0 0 1 0 0 1 0 1 1 1 0 0 0 1 1 0 1 1 0 1 0 0 0 0 1 1 1 0 0 1 1 0 1 0 1 0 0 0 1 0 1 0 1 1 1 0 0 0 1 1 1 0 1 0 1 1 1 0 1 1 0 0 0 1 0 0 1 0 0 1 1 0 1 1 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 1 0 1 0 0 1 0 0 1 1 1 0 1 0 0 1 0 1 1 0 1 1 1 1 0 0 0 1 1 0 0 0 1 1 0 1 0 0 0 1 1 1 0 0 1 1 1 0 1 0 1 0 1 1 0 0 0 0 1 1 0 1 1 0 1 1 1 1 0 1 1 0 0 0 1 0 0 1 1 1 0 1 1 0 0 0 0 1 1 1 0 1 0 0 0 1 1 0 0 0 0 0 1 0 1 1 1 0 1 0 1 1 0 1 1 1 1 0 1 0 1 0 0 1 1 0 1 0 0 0 1 1 0 0 1 1 1 1 1 1 0 1 1 0 1 0 1 0 1 0 1 1 1 0 0 0 1 1 0 1 1 1 0 1 1 0 0 0 0 0 1 0 1 1 1 0 1 0 1 0 1 0 1 1 0 1 0 1 0 0 0 1 0 0 0 0 1 0 0 1 0 1 0 1 1 0 1 1 1 1 1 0 0 0 0 0 1 0 1 1 1 0 0 1 1 1 1 1 0 1 0 1 1 1 1 0 0 1 0 0 1 0 1 0 1 1 0 0 1 1 0 0 1 1 1 1 0 1 1 1 1 0 0 1 0 0 0 1 1 0 0 1 0 1 1 0 1 1 1 0 1 1 1 0 0 1 1 1 0 0 0 0 0 0 1 1 0 0 0 0 1 1 1 0 0 0 1 1 0 1 1 0 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 1 0 0 0 1 1 1 1 0 0 1 0 1 0 0 0 1 1 0 1 1 0 0 0 0 1 0 1 1 1 1 0 0 1 1 0 0 1 0 0 1 0 1 0 0 1 0 0 1 0 0 1 0 1 1 1 0 0 1 1 0 1 1 0 1 0 0 1 1 0 0 0 1 1 0 1 1 0 0 1 1 0 0 0 1 0 1 1 1 0 1 0 1 1 1 1 1 0 0 0 1 0 1 1 1 1 0 0 1 0 0 1 1 0 0 1 0 0 0 0 1 1 1 0 1 0 1 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 1 0 1 1 1 1 1 0 0 1 1 1 0 0 1 1 0 0 1 1 0 0 1 0 0 0 1 1 0 1 0 0 1 1 1 1 1 1 0 0 1 1 0 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1 0 1 1 0 1 0 0 1 0 0 0 0 0 1 1 1 0 0 1 0 1 1 0 0 1 0 1 1 0 0 1 1 0 0 0 0 0 0 1 0 0 1 0 0 1 0 1 1 0 1 0 0 1 1 1 1 1 1 1 0 0 1 0 0 1 1 0 0 0 0 0 1 1 0 1 1 1 1 0 1 1 0 1 1 1 0 1 1 0 1 0 1 1 0 1 0 1 1 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 1 1 0 0 1 0 0 0 1 1 0 1 1 0 1 1 1 0 1 1 1 0 1 0 0 0 1 1 1 0 0 1 0 0 0 1 0 1 1 0 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1 0 0 1 0 0 1 0 1 0 1 0 1 0 1 1 1 1 0 0 1 0 0 0 0 0 1 0 1 0 0 1 0 1 1 0 0 0 0

[出力例]
0 601 1616 1772 2023 1856 752 1059 1602 1265 1361 1383 1006 1934 149 1935 1792 1675 1540 611 1508 47 587 787 1528 1616 1145 908 1096 1641 1056 109 1764 236 517 1129 1334 144 178 1566 131 1763 1702 1394 564 451 496 1873 1630 892 64 811 989 1986 402 202 1514 545 830 1373 1132 1817 260 693 971 1255 1516 860 655 1351 1193 1652 1912 307 1671 1957 651 424 512 497 215 1197 341 1942 420 372 1167 337 1385 656 483 1795 1069 1104 1242 579 990 434 824 1176 1153 1115 258 607 1482 792 47 1812 1800 1575 1713 609 203 1389 1698 1016 1502 1224 1101 68 59 255 1984 307 72 390 631 1926 605 1273 882 1282 294 1885 1653 605 179 21 1839 1820 845 458 1332 583 575 537 37 601 28 56 1179 640 1483 1937 1994 1818 343 1513 1497 247 320 1953 707 1832 1822 874 390 1676 861 1469 853 730 422 756 180 0 382 1615 173 76 236 1868 281 988 1818 1180 583 471 1536 1283 1641 1668 715 1874 647 1119 1054 1781 1649 1150 1401 1991 168 1784 403 1110 1919 1312 1216 554 1513 1537 362 961 216 773 1828 1505 1604 1869 2005 1955 1381 1188 1465 1328 944 1760 1435 1558 1730 1778 320 1821 1869 275 984 1899 987 605 1533 677 1208 667 224 1420 1453 1519 441 814 968 996 925 1301 2001 1169 682 460 1039 1798 1358 1572 231 114 440 652 454 138 393 220 1140 1009 1435 1980 1723 775 1408 1954 233 416 1919 1001 1802 176 1144 1151 290 534 1523 1717 315 338 916 410 835 1095 120 922 460 1141 437 1951 274 1639 873 1772 179 1320 1916 703 356 1761 1465 339 1795 1464 1263 252 766 1853 841 536 2002 1099 1924 95 1966 1742 424 1404 476 144 1861 1340 667 2018 1554 1998 983 557 1160 828 200 1697 1833 291 876 1743 994 1406 230 1151 1351 1360 473 799 324 1473 190 1772 921 1345 499 7 174 246 301 1164 1594 575 1167 1998 1302 1561 814 202 1082 1895 21 1827 216 258 122 437 1914 1334 1534 236 137 1594 1814 306 414 628 846 1603 608 191 921 687 700 1002 858 1547 1174 1476 1936 1807 1139 1416 738 618 941 653 1751 1573 1033 541 1774 341 1658 1137 1312 476 1164 612 1262 49 1347 1825 1864 1002 804 1167 1067 639 660 701 1408 1011 1137 1451 1766 1704 926 725 1987 97 143 405 408 977 1431 1526 1668 1506 1732 1549 39 1621 1586 1694 1177 1485 1806 519 721 1086 644 1726 1529 1666 1029 1952 138 124 438 1397 755 1942 1805 1642 369 905 1487 1786 1635 71 1523 1160 1125 1690 768 1774 1711 1549 1079 761 777 2020 1944 1873 158 661 1907 787 291 687 1644 817 1188 329 607 1998 377 849 890 109 661 614 1914 1052 1806 1300 1361 1198 641 359 653 516 57 1819 1017 330 80 1420 709 466 28 1140 1327 621 955 1924 152 79 859 703 1222 1611 905 654 1686 408 541 1163 1638 1749 676 980 994 686 1615 551 1036 1761 1048 292 778 638 492 772 1127 376 1727 585 847 413 1854 1682 252 1106 763 738 646 291 1700 2024 159 1330 671 1055 1472 241 1877 1127 809 1407 945 1628 1882 1022 802 738 1597 735 1620 1287 867 462 1367 1909 732 704 406 711 530 407 172 605 405 1641 1175 366 1722 1272 905 1094 1218 1452 1275 1333 1323 1932 1926 1294 1166 823 1942 408 1186 1328 1134 842 465 939 1420 957 1356 1417 313 712 720 1954 994 81 53 132 659 507 1440 1735 1666 1396 84 886 1512 441 314 1954 1734 1812 1660 1580 782 722 671 1810 1311 392 269 428 1587 263 1162 788 861 252 1121 618 1082 827 923 1783 97 319 1167 292 1861 1993 1344 386 1812 1430 608 223 1883 1767 768 1612 297 1439 1852 426 1231 1056 994 1227 140 1874 921 1953 361 1004 597 649 523 472 188 906 1516 1581 282 1727 1998 276 1204 943 810 1845 894 981 1223 63 1524 1222 827 1321 366 1137 425 1268 1484 307 1004 1123 693 837 564 740 891 1773 1350 685 825 368 1811 1338 1866 1013 217 303 1357 1421 851 626 372 517 189 49 1153 279 1532 1431 1652 1910 1574 1224 1739 1815 68 1845 1722 226 1248 1571 53 801 1484 348 1155 905 667 157 884 563 1438 1819 1672 1011 261 136 27 1300 1974 1807 317 380 1271 1328 2026 1680 1545 1448 462 1431 542 1794 1465 1293 573 1080 41 1298 1236 365 2011 1910 525 509 1604 818 28 1417 1756 1714 1858 22 1946 1096 573 58 1957 607 670 74 1749 1207 232 1171 483 1685 128 1302 36 1614 1639 685 263 1845 1651 1904 523 855 452 694 365 654 1475 1893 945 1710 1108 1225 21 1411 1703 827 1540 317 1203 318 1690 1631 473 494 1237 850 565 186 831 122 1968 1220 706 1757 1136 656 301 1510 2022 1534 610 1439 399 1137 974 825 1001 941 1337 494 509 230 1868 1345 663 164 392 501 676 1077 1144 1034 1383 442 69 382 868 42 1789 1656 1825 649 824 1096 244 1371 838 1 972 770 777 84 398 1375 1267 834 273 618 40 1538 1411 1214 398 1148 1489 1777 945 587 447 82 1201 60 1538 210 374 1480 124 376 1194 281 1523 1995 322 142 485 1819 994 334 1198 200 1534 267 333 569 1348 162 472 812 454 478 722 627 1355 186 1143 518 23 1371 497 1403 1136 2025 1550 917 1736 1489 131 803 690 422 404 1043 848 770 168 369 1814 1606 1509 130 782 1776 1808 467 1316 1141 1081 1574 1245 905 1573 1504 178 866 1547 869 1084 1900 1975 111 575 1418 313 1359 43 1792 233 8 1325 1055 1942 1327 2004 431 952 1989 1793 361 935 647 1016 1718 1348 1791 867 1291 1747 1362 271 1957 439 174 1318 1202 1169 779 2025 156 921 201 722 825 416 395 484 138 708 471 315 1606 896 1309 184 1794 426 293 221 1087 643 1558 819 1577 1170 555 567 1997 1137 870 959 1050 931 1149 1699 1425 1999 399 244 1896 340 1793 1689 466 96 316 961 257 894 1879 1566 1727 595 356 1887 1702 1180 984 1939 1770 1244 825 1059 1189 1350 618 1901 1522 510 407 320 776 1226 1 1608 1542 826 1651 512 464 1628 49 759 703 815 1261 697 42 748 1654 1266 1869 776 655 182 696 1756 1187 1726 813 6 1995 1892 908 1496 18 315 1712 1322 1893 243 185 415 364 76 916 105 1862 390 1416 854 1553 1748 319 1696 1760 1960 1380 1365 1078 841 1300 1816 1142 448 1216 1779 305 183 295 946 224 1226 1011 1852 1326 371 814 1529 1256 1380 186 482 1877 1622 1560 815 1280 1708 1375 1805 1273 1675 153 1736 408 333 611 1083 733 96 865 1164 912 604 1002 1282 514 1939 1239 723 1067 1553 159 1147 2006 1650 1382 1312 1617 710 1029 1367 1877 1462 1067 583 495 605 925 435 1730 1263 1005 982 1862 1422 1861 732 1593 1514 1520 1496 808 192 973 681 335 610 1206 631 1770 243 1255 1434 966 1257 845 1042 892 781 1521 1347 1324 1369 758 1435 556 842 1804 715 358 445 1543 909 219 88 1125 66 1518 737 1623 1038 1036 891 716 1916 813 22 894 754 1504 989 759 58 1579 1778 1844 923 53 1097 1833 1892 1282 1342 1503 1105 1807 1019 689 1118 870 560 1170 1811 1548 1282 1007 1282 845 1734 2004 1072 1954 982 1650 788 1224 594 210 1971 1400 1487 119 1685 734 282 1948 404 456 299 382 1888 687 147 1616 1398 346 1444 1206 1968 637 960 717 1522 1655 1456 1817 982 1325 1325 362 526 1985 1384 1218 446 538 1767 406 1730 667 911 286 1472 319 240 957 709 767 1838 38 242 1516 323 1198 701 1484 799 1249 87 1431 1523 1439 1435 1556 1830 335 1222 130 1084 35 443 1737 479 1678 481 1545 194 318 1034 463 1458 1132 1562 867 1111 1793 1271 207 199 1466 657 529 180 239 825 818 668 1242 1264 1597 1306 1776 1319 969 125 23 483 1426 1628 1592 1777 881 807 434 44 619 1364 1810 312 662 271 1507 418 247 1023 1862 314 289 1668 1278 634 1012 247 98 2007 669 1037 1418 540 767 444 1170 874 1503 1291 749 1460 1016 1995 1128 21 1304 1445 692 1528 2013 710 1423 13 1287 1857 116 566 349 1029 861 130 170 656 1724 1666 1461 1326 488 354 1210 1876 326 976 1514 1116 1593 841 456 974 1864 1414 497 737 1234 52 1788 994 1301 1955 687 310 1695 1879 1127 1570 520 1915 768 641 1959 1908 260 1971 500 792 1250 1784 1192 1172 662 296 654 836 1356 206 20 18 1411 1225 954 827 810 1931 963 443 989 939 920 631 1664 958 1524 316 1477 97 45 468 1770 431 272 659 170 171 1061 1196 1188 1098 84 1582 1387 471 1962 73 1111 697 763 1644 1109 322 240 1079 970 1639 1423 1961 1487 1440 498 1897 580 1711 1308 1081 779 1762 456 864 748 268 1767 387 1269 152 1608 958 1697 890 1228 1108 1070 1192 347 1557 579 1044 1563 1517 852 1523 1345 423 1624 1748 1418 1822 170 1194 1995 921 1522 957 1660 635 1084 116 1914 809 1499 1387 1237 1500 1270 248 1770 1815 352 1108 904 1031 1242 947 471 761 666 1660 513 1311 419 258 1457 1969 1287 1098 1017 419 99 1078 1782 1424 1999 629 284 1832 182 735 413 1412 1166 599 44 1328 997 1025 1411 593 290 28 25 1247 801 1050 1661 1387 1549 1720 1857 1858 178 1829 1040 1981 909 762 798 1062 27 879 445 676 20 831 1950 801 234 450 870 623 1747 309 619 118 1485 1744 1417 1525 1309 649 1171 1992 413 178 1120 831 1792 193 184 1548 1151 1786 1315 469 1615 1530 514 1243 794 624 876 1357 654 559 1160 834 497 1033 1880 1771 687 1907 1088 1211 1992 1801 1290 1382 1787 1703 199 832 120 999 330 982 1910 765 741 1495 1393 856 954 1472 472 437 1266 849 1062 267 13 402 1264 1041 969 1346 1050 1141 186 1221 371 1774 1925 1244 1214 1478 572 1473 790 1518 1840 489 388 1163 409 1441 1858 952 459 1830 1897 1972 636 793 1919 1092 266 1216 360 69 1700 227 350 1342 343 1823 301 1562 1329 650 1778 436 430 1905 401 1688 1186 924 1171 650 973 1258 872 41 1330 1872 1275 1569 1703 1985 357 132 18 1612 1933 1150 1196 459 501 109 1575 1283 1319 1044 433 275 1487 632 100 253 2011 1321 1696 720 1407 324 46 848 1794 1274 715 1807 851 745 711 1196 744 381 1124 1462 239 385 1617 1082 660 703 982 82 1383 1097 1537 587 699 1682 1374 1624 878 1548 378 1981 1325 740 426 692 314 894 1932 1108 1501 2006 913 1384 1298 13 1695 1186 393 1343 907 1106 1895 5 1321 920 210 1125 1956 966 1991 411 1685 1017

[入力例]

1 0

[出力例]

1 1

※AtCoderテストケースより

[入力例]

0 0 0

[出力例]

0 0 0

※AtCoderテストケースより

[入力例]

0 1 0 1 0

[出力例]

0 2 0 1 3

※AtCoderテストケースより

[入力例]

0 1 0 1 0 1 0

[出力例]

0 5 0 1 0 5 4

[入力例]

0 0 1 0 0 0 1 0 1 0 0

[出力例]

0 7 10 5 5 3 4 1 6 6 8

[入力例]

0 0 1 0 0 0 1 0 1 0 0 1 1 1 0 0 1

[出力例]

0 14 1 1 4 15 12 7 16 0 16 12 13 10 5 0 10

[入力例]

331

0 0 1 0 1 1 1 0 1 1 0 0 0 1 0 0 0 0 0 1 1 0 1 0 1 0 1 0 1 1 0 1 1 0 1 0 1 1 0 1 1 1 0 1 1 1 1 1 0 1 0 1 0 0 0 0 0 1 0 0 1 1 1 0 0 1 1 0 1 1 0 0 1 1 1 0 0 0 0 1 1 1 1 1 0 1 0 1 1 0 1 1 1 0 1 0 1 1 1 1 0 1 0 1 0 0 1 0 1 1 1 0 1 1 1 1 0 0 0 1 0 0 0 0 0 0 1 1 0 0 1 0 1 1 1 1 1 1 1 1 0 0 0 1 0 1 0 1 0 0 0 1 1 1 0 0 0 0 0 0 1 0 0 1 0 0 1 1 1 1 1 0 0 1 0 1 0 0 1 1 0 1 1 1 0 1 0 0 0 1 0 0 0 0 1 0 1 1 1 0 1 0 0 0 1 0 1 1 1 1 1 1 1 1 0 1 0 1 1 1 0 1 0 0 1 1 0 1 1 1 0 0 1 0 1 0 0 1 1 1 1 0 0 0 0 1 1 0 0 0 1 1 0 1 1 0 1 0 1 0 1 1 1 0 1 0 0 0 1 0 1 0 1 0 1 1 1 1 0 1 0 1 0 1 1 1 1 0 0 0 0 0 0 1 0 1 1 0 1 1 1 0 0 0 0 0 1 1 0 0 0 0 1 1 0 1 1 1 1 1 1 0 1 1 1 0 0 0 0 1 0

[出力例]

0 270 29 28 211 326 92 161 309 74 132 135 28 242 187 243 185 253 58 165 253 31 0 297 289 236 323 67 2 207 156 248 113 174 12 12 176 254 118 107 176 253 6 283 218 8 261 79 115 48 156 165 23 185 294 122 45 217 32 237 135 110 224 299 104 246 99 243 153 53 202 322 54 201 123 282 125 68 308 248 73 263 16 274 261 102 67 57 21 1 5 104 46 117 74 11 324 59 95 248 100 110 203 304 170 276 252 317 184 213 312 213 163 138 21 289 167 316 119 145 275 191 206 63 12 200 204 204 294 242 224 23 308 208 30 195 42 192 232 293 162 96 8 15 173 291 232 36 125 110 239 115 126 230 18 1 177 23 185 23 219 71 207 98 254 3 184 306 324 45 290 137 81 174 8 135 183 237 179 81 32 202 115 204 304 271 252 188 135 158 239 303 123 100 69 326 63 75 188 43 109 132 233 77 43 66 86 153 121 63 85 77 66 143 180 197 145 51 261 308 44 236 202 87 173 292 254 43 168 21 165 320 196 122 91 258 212 104 6 280 210 23 150 176 127 6 31 137 189 140 113 97 325 57 100 212 271 308 80 7 107 318 164 25 42 200 2 210 19 170 213 258 270 10 58 200 88 268 205 83 164 261 50 55 262 29 61 68 16 316 276 260 237 48 13 208 158 248 18 187 304 265 307 234 109 207 259 46 322 91 64 119 185 128 159 142 273 171 255 270 105 92 285 221 206 101 232 52 156 62 156

[入力例]

2027

0 1 1 1 0 1 0 0 1 0 1 1 0 0 1 0 0 1 0 0 1 1 1 1 1 0 0 0 1 1 1 1 1 1 0 0 0 1 1 0 1 0 1 1 1 1 1 1 1 1 0 1 0 1 1 1 1 0 1 1 1 1 1 0 0 0 1 0 0 1 0 0 1 0 1 1 0 0 1 0 1 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 1 0 1 0 0 1 0 1 0 0 0 1 0 1 1 1 0 0 0 0 1 1 0 1 1 1 0 1 1 0 0 1 0 1 1 0 0 1 1 1 0 1 0 1 1 1 1 1 0 1 0 0 0 1 1 1 1 0 0 1 0 1 1 1 0 0 0 1 0 0 1 1 0 0 0 0 0 1 1 1 0 1 0 1 0 1 0 1 0 0 1 0 0 0 0 0 0 1 1 0 1 0 1 1 1 1 0 1 1 1 1 0 0 0 1 0 0 0 0 1 1 1 1 1 0 0 1 1 0 0 0 1 1 0 0 1 1 0 1 0 0 1 1 1 1 0 0 0 1 1 0 0 1 1 0 1 1 1 0 1 0 1 0 0 1 1 0 1 1 0 1 0 0 0 0 0 0 1 0 0 1 0 1 0 1 1 1 1 0 1 1 0 1 1 0 1 0 1 1 0 1 1 0 1 0 1 1 0 1 0 0 0 0 1 0 1 0 0 0 1 0 1 0 0 1 0 1 0 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 0 1 0 0 0 1 1 1 0 0 0 1 1 0 1 1 0 0 0 1 1 0 0 0 0 0 0 1 0 1 0 1 0 1 1 0 1 1 0 1 1 0 1 1 1 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 1 1 1 0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 1 1 1 0 1 0 1 1 0 0 1 0 1 1 1 1 0 1 1 1 1 1 0 1 0 0 1 1 0 0 0 1 0 0 1 1 1 1 1 1 0 0 0 1 0 1 0 0 1 0 1 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 1 1 0 1 1 0 0 1 1 1 1 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 1 0 0 0 1 0 1 0 1 1 0 1 1 1 1 0 0 0 0 0 1 0 0 0 1 1 0 0 0 0 0 0 1 1 1 0 0 1 1 0 1 1 1 1 0 0 1 0 1 1 1 1 0 1 0 1 0 1 1 0 0 1 0 1 0 0 1 0 0 0 1 0 1 1 0 0 0 0 1 0 1 0 1 0 1 0 1 1 0 1 1 0 0 1 1 0 0 1 1 1 1 1 1 1 0 1 1 0 0 1 0 1 1 1 0 1 0 1 1 1 0 0 1 1 1 0 1 1 1 0 0 0 1 1 0 1 1 1 0 1 0 0 0 0 1 0 0 0 0 1 1 1 0 0 0 0 1 1 0 1 0 1 1 0 0 0 0 0 1 0 1 0 0 0 0 1 1 1 1 1 0 1 0 1 1 1 0 1 1 1 1 1 1 1 0 0 1 1 0 1 1 0 0 1 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 0 1 1 0 1 0 0 1 0 0 0 0 0 1 1 1 1 0 0 1 0 0 0 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 0 0 0 1 1 1 1 1 0 0 1 0 1 0 0 0 1 1 0 0 0 1 0 0 0 0 0 1 1 1 0 0 1 0 0 0 1 0 0 0 0 1 0 1 0 1 1 1 1 0 1 1 1 0 1 0 0 0 1 0 0 0 1 1 0 0 0 1 1 0 0 0 1 0 1 1 1 0 1 1 0 0 0 1 1 1 0 1 0 0 0 0 1 0 1 0 1 1 0 0 0 1 1 0 0 1 1 1 0 0 0 1 0 0 0 0 0 1 1 0 1 1 0 1 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 1 0 0 1 1 0 0 1 1 0 0 0 1 1 0 0 1 0 0 0 1 0 0 1 1 1 1 1 0 0 0 1 1 0 1 0 1 0 1 0 1 1 1 0 1 1 1 0 1 1 1 1 1 0 0 1 1 0 1 0 0 1 0 0 1 1 0 0 0 1 0 0 1 1 0 0 1 1 1 1 0 1 1 0 1 0 1 0 1 0 1 0 0 1 0 1 0 0 0 1 0 1 0 0 1 1 0 0 0 0 0 1 0 0 0 1 1 1 0 1 0 0 0 0 0 1 1 0 0 1 1 0 0 0 0 1 0 1 1 1 0 0 1 1 1 0 1 1 0 1 0 1 0 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 1 0 1 1 1 0 1 1 0 1 0 1 0 1 1 0 0 1 0 0 1 1 0 1 1 0 1 0 1 0 0 1 1 1 0 0 0 0 0 0 1 0 0 1 0 0 1 0 1 1 1 0 0 0 1 1 0 1 1 0 1 0 0 0 0 1 1 1 0 0 1 1 0 1 0 1 0 0 0 1 0 1 0 1 1 1 0 0 0 1 1 1 0 1 0 1 1 1 0 1 1 0 0 0 1 0 0 1 0 0 1 1 0 1 1 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 1 0 1 0 0 1 0 0 1 1 1 0 1 0 0 1 0 1 1 0 1 1 1 1 0 0 0 1 1 0 0 0 1 1 0 1 0 0 0 1 1 1 0 0 1 1 1 0 1 0 1 0 1 1 0 0 0 0 1 1 0 1 1 0 1 1 1 1 0 1 1 0 0 0 1 0 0 1 1 1 0 1 1 0 0 0 0 1 1 1 0 1 0 0 0 1 1 0 0 0 0 0 1 0 1 1 1 0 1 0 1 1 0 1 1 1 1 0 1 0 1 0 0 1 1 0 1 0 0 0 1 1 0 0 1 1 1 1 1 1 0 1 1 0 1 0 1 0 1 0 1 1 1 0 0 0 1 1 0 1 1 1 0 1 1 0 0 0 0 0 1 0 1 1 1 0 1 0 1 0 1 0 1 1 0 1 0 1 0 0 0 1 0 0 0 0 1 0 0 1 0 1 0 1 1 0 1 1 1 1 1 0 0 0 0 0 1 0 1 1 1 0 0 1 1 1 1 1 0 1 0 1 1 1 1 0 0 1 0 0 1 0 1 0 1 1 0 0 1 1 0 0 1 1 1 1 0 1 1 1 1 0 0 1 0 0 0 1 1 0 0 1 0 1 1 0 1 1 1 0 1 1 1 0 0 1 1 1 0 0 0 0 0 0 1 1 0 0 0 0 1 1 1 0 0 0 1 1 0 1 1 0 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 1 0 0 0 1 1 1 1 0 0 1 0 1 0 0 0 1 1 0 1 1 0 0 0 0 1 0 1 1 1 1 0 0 1 1 0 0 1 0 0 1 0 1 0 0 1 0 0 1 0 0 1 0 1 1 1 0 0 1 1 0 1 1 0 1 0 0 1 1 0 0 0 1 1 0 1 1 0 0 1 1 0 0 0 1 0 1 1 1 0 1 0 1 1 1 1 1 0 0 0 1 0 1 1 1 1 0 0 1 0 0 1 1 0 0 1 0 0 0 0 1 1 1 0 1 0 1 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 1 0 1 1 1 1 1 0 0 1 1 1 0 0 1 1 0 0 1 1 0 0 1 0 0 0 1 1 0 1 0 0 1 1 1 1 1 1 0 0 1 1 0 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1 0 1 1 0 1 0 0 1 0 0 0 0 0 1 1 1 0 0 1 0 1 1 0 0 1 0 1 1 0 0 1 1 0 0 0 0 0 0 1 0 0 1 0 0 1 0 1 1 0 1 0 0 1 1 1 1 1 1 1 0 0 1 0 0 1 1 0 0 0 0 0 1 1 0 1 1 1 1 0 1 1 0 1 1 1 0 1 1 0 1 0 1 1 0 1 0 1 1 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 1 1 0 0 1 0 0 0 1 1 0 1 1 0 1 1 1 0 1 1 1 0 1 0 0 0 1 1 1 0 0 1 0 0 0 1 0 1 1 0 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1 0 0 1 0 0 1 0 1 0 1 0 1 0 1 1 1 1 0 0 1 0 0 0 0 0 1 0 1 0 0 1 0 1 1 0 0 0 0

[出力例]

0 601 1616 1772 2023 1856 752 1059 1602 1265 1361 1383 1006 1934 149 1935 1792 1675 1540 611 1508 47 587 787 1528 1616 1145 908 1096 1641 1056 109 1764 236 517 1129 1334 144 178 1566 131 1763 1702 1394 564 451 496 1873 1630 892 64 811 989 1986 402 202 1514 545 830 1373 1132 1817 260 693 971 1255 1516 860 655 1351 1193 1652 1912 307 1671 1957 651 424 512 497 215 1197 341 1942 420 372 1167 337 1385 656 483 1795 1069 1104 1242 579 990 434 824 1176 1153 1115 258 607 1482 792 47 1812 1800 1575 1713 609 203 1389 1698 1016 1502 1224 1101 68 59 255 1984 307 72 390 631 1926 605 1273 882 1282 294 1885 1653 605 179 21 1839 1820 845 458 1332 583 575 537 37 601 28 56 1179 640 1483 1937 1994 1818 343 1513 1497 247 320 1953 707 1832 1822 874 390 1676 861 1469 853 730 422 756 180 0 382 1615 173 76 236 1868 281 988 1818 1180 583 471 1536 1283 1641 1668 715 1874 647 1119 1054 1781 1649 1150 1401 1991 168 1784 403 1110 1919 1312 1216 554 1513 1537 362 961 216 773 1828 1505 1604 1869 2005 1955 1381 1188 1465 1328 944 1760 1435 1558 1730 1778 320 1821 1869 275 984 1899 987 605 1533 677 1208 667 224 1420 1453 1519 441 814 968 996 925 1301 2001 1169 682 460 1039 1798 1358 1572 231 114 440 652 454 138 393 220 1140 1009 1435 1980 1723 775 1408 1954 233 416 1919 1001 1802 176 1144 1151 290 534 1523 1717 315 338 916 410 835 1095 120 922 460 1141 437 1951 274 1639 873 1772 179 1320 1916 703 356 1761 1465 339 1795 1464 1263 252 766 1853 841 536 2002 1099 1924 95 1966 1742 424 1404 476 144 1861 1340 667 2018 1554 1998 983 557 1160 828 200 1697 1833 291 876 1743 994 1406 230 1151 1351 1360 473 799 324 1473 190 1772 921 1345 499 7 174 246 301 1164 1594 575 1167 1998 1302 1561 814 202 1082 1895 21 1827 216 258 122 437 1914 1334 1534 236 137 1594 1814 306 414 628 846 1603 608 191 921 687 700 1002 858 1547 1174 1476 1936 1807 1139 1416 738 618 941 653 1751 1573 1033 541 1774 341 1658 1137 1312 476 1164 612 1262 49 1347 1825 1864 1002 804 1167 1067 639 660 701 1408 1011 1137 1451 1766 1704 926 725 1987 97 143 405 408 977 1431 1526 1668 1506 1732 1549 39 1621 1586 1694 1177 1485 1806 519 721 1086 644 1726 1529 1666 1029 1952 138 124 438 1397 755 1942 1805 1642 369 905 1487 1786 1635 71 1523 1160 1125 1690 768 1774 1711 1549 1079 761 777 2020 1944 1873 158 661 1907 787 291 687 1644 817 1188 329 607 1998 377 849 890 109 661 614 1914 1052 1806 1300 1361 1198 641 359 653 516 57 1819 1017 330 80 1420 709 466 28 1140 1327 621 955 1924 152 79 859 703 1222 1611 905 654 1686 408 541 1163 1638 1749 676 980 994 686 1615 551 1036 1761 1048 292 778 638 492 772 1127 376 1727 585 847 413 1854 1682 252 1106 763 738 646 291 1700 2024 159 1330 671 1055 1472 241 1877 1127 809 1407 945 1628 1882 1022 802 738 1597 735 1620 1287 867 462 1367 1909 732 704 406 711 530 407 172 605 405 1641 1175 366 1722 1272 905 1094 1218 1452 1275 1333 1323 1932 1926 1294 1166 823 1942 408 1186 1328 1134 842 465 939 1420 957 1356 1417 313 712 720 1954 994 81 53 132 659 507 1440 1735 1666 1396 84 886 1512 441 314 1954 1734 1812 1660 1580 782 722 671 1810 1311 392 269 428 1587 263 1162 788 861 252 1121 618 1082 827 923 1783 97 319 1167 292 1861 1993 1344 386 1812 1430 608 223 1883 1767 768 1612 297 1439 1852 426 1231 1056 994 1227 140 1874 921 1953 361 1004 597 649 523 472 188 906 1516 1581 282 1727 1998 276 1204 943 810 1845 894 981 1223 63 1524 1222 827 1321 366 1137 425 1268 1484 307 1004 1123 693 837 564 740 891 1773 1350 685 825 368 1811 1338 1866 1013 217 303 1357 1421 851 626 372 517 189 49 1153 279 1532 1431 1652 1910 1574 1224 1739 1815 68 1845 1722 226 1248 1571 53 801 1484 348 1155 905 667 157 884 563 1438 1819 1672 1011 261 136 27 1300 1974 1807 317 380 1271 1328 2026 1680 1545 1448 462 1431 542 1794 1465 1293 573 1080 41 1298 1236 365 2011 1910 525 509 1604 818 28 1417 1756 1714 1858 22 1946 1096 573 58 1957 607 670 74 1749 1207 232 1171 483 1685 128 1302 36 1614 1639 685 263 1845 1651 1904 523 855 452 694 365 654 1475 1893 945 1710 1108 1225 21 1411 1703 827 1540 317 1203 318 1690 1631 473 494 1237 850 565 186 831 122 1968 1220 706 1757 1136 656 301 1510 2022 1534 610 1439 399 1137 974 825 1001 941 1337 494 509 230 1868 1345 663 164 392 501 676 1077 1144 1034 1383 442 69 382 868 42 1789 1656 1825 649 824 1096 244 1371 838 1 972 770 777 84 398 1375 1267 834 273 618 40 1538 1411 1214 398 1148 1489 1777 945 587 447 82 1201 60 1538 210 374 1480 124 376 1194 281 1523 1995 322 142 485 1819 994 334 1198 200 1534 267 333 569 1348 162 472 812 454 478 722 627 1355 186 1143 518 23 1371 497 1403 1136 2025 1550 917 1736 1489 131 803 690 422 404 1043 848 770 168 369 1814 1606 1509 130 782 1776 1808 467 1316 1141 1081 1574 1245 905 1573 1504 178 866 1547 869 1084 1900 1975 111 575 1418 313 1359 43 1792 233 8 1325 1055 1942 1327 2004 431 952 1989 1793 361 935 647 1016 1718 1348 1791 867 1291 1747 1362 271 1957 439 174 1318 1202 1169 779 2025 156 921 201 722 825 416 395 484 138 708 471 315 1606 896 1309 184 1794 426 293 221 1087 643 1558 819 1577 1170 555 567 1997 1137 870 959 1050 931 1149 1699 1425 1999 399 244 1896 340 1793 1689 466 96 316 961 257 894 1879 1566 1727 595 356 1887 1702 1180 984 1939 1770 1244 825 1059 1189 1350 618 1901 1522 510 407 320 776 1226 1 1608 1542 826 1651 512 464 1628 49 759 703 815 1261 697 42 748 1654 1266 1869 776 655 182 696 1756 1187 1726 813 6 1995 1892 908 1496 18 315 1712 1322 1893 243 185 415 364 76 916 105 1862 390 1416 854 1553 1748 319 1696 1760 1960 1380 1365 1078 841 1300 1816 1142 448 1216 1779 305 183 295 946 224 1226 1011 1852 1326 371 814 1529 1256 1380 186 482 1877 1622 1560 815 1280 1708 1375 1805 1273 1675 153 1736 408 333 611 1083 733 96 865 1164 912 604 1002 1282 514 1939 1239 723 1067 1553 159 1147 2006 1650 1382 1312 1617 710 1029 1367 1877 1462 1067 583 495 605 925 435 1730 1263 1005 982 1862 1422 1861 732 1593 1514 1520 1496 808 192 973 681 335 610 1206 631 1770 243 1255 1434 966 1257 845 1042 892 781 1521 1347 1324 1369 758 1435 556 842 1804 715 358 445 1543 909 219 88 1125 66 1518 737 1623 1038 1036 891 716 1916 813 22 894 754 1504 989 759 58 1579 1778 1844 923 53 1097 1833 1892 1282 1342 1503 1105 1807 1019 689 1118 870 560 1170 1811 1548 1282 1007 1282 845 1734 2004 1072 1954 982 1650 788 1224 594 210 1971 1400 1487 119 1685 734 282 1948 404 456 299 382 1888 687 147 1616 1398 346 1444 1206 1968 637 960 717 1522 1655 1456 1817 982 1325 1325 362 526 1985 1384 1218 446 538 1767 406 1730 667 911 286 1472 319 240 957 709 767 1838 38 242 1516 323 1198 701 1484 799 1249 87 1431 1523 1439 1435 1556 1830 335 1222 130 1084 35 443 1737 479 1678 481 1545 194 318 1034 463 1458 1132 1562 867 1111 1793 1271 207 199 1466 657 529 180 239 825 818 668 1242 1264 1597 1306 1776 1319 969 125 23 483 1426 1628 1592 1777 881 807 434 44 619 1364 1810 312 662 271 1507 418 247 1023 1862 314 289 1668 1278 634 1012 247 98 2007 669 1037 1418 540 767 444 1170 874 1503 1291 749 1460 1016 1995 1128 21 1304 1445 692 1528 2013 710 1423 13 1287 1857 116 566 349 1029 861 130 170 656 1724 1666 1461 1326 488 354 1210 1876 326 976 1514 1116 1593 841 456 974 1864 1414 497 737 1234 52 1788 994 1301 1955 687 310 1695 1879 1127 1570 520 1915 768 641 1959 1908 260 1971 500 792 1250 1784 1192 1172 662 296 654 836 1356 206 20 18 1411 1225 954 827 810 1931 963 443 989 939 920 631 1664 958 1524 316 1477 97 45 468 1770 431 272 659 170 171 1061 1196 1188 1098 84 1582 1387 471 1962 73 1111 697 763 1644 1109 322 240 1079 970 1639 1423 1961 1487 1440 498 1897 580 1711 1308 1081 779 1762 456 864 748 268 1767 387 1269 152 1608 958 1697 890 1228 1108 1070 1192 347 1557 579 1044 1563 1517 852 1523 1345 423 1624 1748 1418 1822 170 1194 1995 921 1522 957 1660 635 1084 116 1914 809 1499 1387 1237 1500 1270 248 1770 1815 352 1108 904 1031 1242 947 471 761 666 1660 513 1311 419 258 1457 1969 1287 1098 1017 419 99 1078 1782 1424 1999 629 284 1832 182 735 413 1412 1166 599 44 1328 997 1025 1411 593 290 28 25 1247 801 1050 1661 1387 1549 1720 1857 1858 178 1829 1040 1981 909 762 798 1062 27 879 445 676 20 831 1950 801 234 450 870 623 1747 309 619 118 1485 1744 1417 1525 1309 649 1171 1992 413 178 1120 831 1792 193 184 1548 1151 1786 1315 469 1615 1530 514 1243 794 624 876 1357 654 559 1160 834 497 1033 1880 1771 687 1907 1088 1211 1992 1801 1290 1382 1787 1703 199 832 120 999 330 982 1910 765 741 1495 1393 856 954 1472 472 437 1266 849 1062 267 13 402 1264 1041 969 1346 1050 1141 186 1221 371 1774 1925 1244 1214 1478 572 1473 790 1518 1840 489 388 1163 409 1441 1858 952 459 1830 1897 1972 636 793 1919 1092 266 1216 360 69 1700 227 350 1342 343 1823 301 1562 1329 650 1778 436 430 1905 401 1688 1186 924 1171 650 973 1258 872 41 1330 1872 1275 1569 1703 1985 357 132 18 1612 1933 1150 1196 459 501 109 1575 1283 1319 1044 433 275 1487 632 100 253 2011 1321 1696 720 1407 324 46 848 1794 1274 715 1807 851 745 711 1196 744 381 1124 1462 239 385 1617 1082 660 703 982 82 1383 1097 1537 587 699 1682 1374 1624 878 1548 378 1981 1325 740 426 692 314 894 1932 1108 1501 2006 913 1384 1298 13 1695 1186 393 1343 907 1106 1895 5 1321 920 210 1125 1956 966 1991 411 1685 1017

■参照サイト
AtCoder Beginner Contest 137

2023年4月1日

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

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

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

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

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

// 解き直し.
// https://img.atcoder.jp/abc134/editorial.pdf
// 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 dp[55][55][3025];

int main(){
    
    // 1. 入力情報.
    int N, K;
    scanf("%d %d", &N, &K);
    
    // 2. dp更新.
    dp[0][0][0] = 1;
    repx(i, 1, N + 1){
        rep(j, i + 1){
            rep(k, N * N + 1){
                // 2-1. 奇妙さ.
                int nk =  k - 2 * j;
                if(nk < 0) continue;
                
                // 2-2. うさぎ i, かめ i を ペア.
                //          | うさぎ 1 ～ (i - 1) | かめ 1 ～ (i - 1) |
                // ペア保留 |                j匹  |               j匹 |
                // 
                // => うさぎ i, かめ i を ペアにするので, ペア保留 の 動物数は, j匹 で 変わらない.
                //          | うさぎ 1 ～ i | かめ 1 ～ i |
                // ペア保留 |          j匹  |         j匹 |
                // 
                // => 遷移は, (i - 1, j) => (i, j) で, 1通りと分かる.
                dp[i][j][k] += dp[i - 1][j][nk];
                
                // 2-3. うさぎ i, かめ i の いずれかを保留にしておいた動物 と ペア.
                //          | うさぎ 1 ～ (i - 1) | かめ 1 ～ (i - 1) |
                // ペア保留 |                j匹  |               j匹 |
                // 
                // => a1. うさぎ i, (ペア保留)かめ を ペアにする.
                //          | うさぎ 1 ～ i | かめ 1 ～ (i - 1) |
                // ペア保留 |          j匹  |         (j - 1)匹 |
                // 
                // => a2. かめ i は ペア保留にする.
                //          | うさぎ 1 ～ i | かめ 1 ～ i   |
                // ペア保留 |           j匹 | (j - 1 + 1)匹 |
                // 
                // => b1. (ペア保留)うさぎ, かめ i を ペアにする.
                //          | うさぎ 1 ～ (i - 1) | かめ 1 ～ i |
                // ペア保留 |          (j - 1)匹  |         j匹 |
                // 
                // => b2. うさぎ i は ペア保留にする.
                //          | うさぎ 1 ～ i | かめ 1 ～ i |
                // ペア保留 | (j - 1 + 1)匹 |         j匹 |
                // 
                // => a2, b2 から, 遷移は, (i - 1, j) => (i, j) で, j通りずつと分かる.
                dp[i][j][k] += (2 * j) * dp[i - 1][j][nk];
                
                // 2-4. うさぎ i, かめ i の 両方を保留にしておいた動物 と ペア.
                //          | うさぎ 1 ～ (i - 1) | かめ 1 ～ (i - 1) |
                // ペア保留 |           (j + 1)匹 |         (j + 1)匹 |
                // 
                // => c1. うさぎ i, (ペア保留)かめ を ペアにする.
                //          | うさぎ 1 ～ i      | かめ 1 ～ (i - 1) |
                // ペア保留 |          (j + 1)匹 |     (j + 1 - 1)匹 |
                // 
                // => c2. (ペア保留)うさぎ, かめ i を ペアにする.
                //          | うさぎ 1 ～ i      | かめ 1 ～ i   |
                // ペア保留 |      (j + 1 - 1)匹 | (j + 1 - 1)匹 |
                // 
                // => c2 から, 遷移は, (i - 1, j + 1) => (i, j) で, (j + 1) * (j + 1)通りと分かる.
                dp[i][j][k] += (j + 1) * (j + 1) * dp[i - 1][j + 1][nk];
                
                // 2-5. うさぎ i, かめ i の 両方をペア保留.
                //          | うさぎ 1 ～ (i - 1) | かめ 1 ～ (i - 1) |
                // ペア保留 |           (j - 1)匹 |         (j - 1)匹 |
                // 
                // => うさぎ i, かめ i の 両方をペア保留にするので, ペア保留 の 動物数は, j匹 に 変わる.
                //          | うさぎ 1 ～ i  | かめ 1 ～ i   |
                // ペア保留 |  (j - 1 + 1)匹 | (j - 1 + 1)匹 |
                // 
                // => 遷移は, (i - 1, j - 1) => (i, j) で, 1通りと分かる.
                if(j) dp[i][j][k] += dp[i - 1][j - 1][nk];
                
                // 2-6. MOD.
                dp[i][j][k] %= MOD;
            }
        }
    }
    
    // 3. 出力.
    printf("%lld\n", dp[N][0][K]);
    return 0;
    
}

// 解き直し.

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

// 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 dp[55][55][3025];

int main(){

// 1. 入力情報.

int N, K;

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

// 2. dp更新.

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

repx(i, 1, N + 1){

rep(j, i + 1){

rep(k, N * N + 1){

// 2-1. 奇妙さ.

int nk = k - 2 * j;

if(nk < 0) continue;

// 2-2. うさぎ i, かめ i をペア.

// | うさぎ 1 ～ (i - 1) | かめ 1 ～ (i - 1) |

// ペア保留 | j匹 | j匹 |

// => うさぎ i, かめ i をペアにするので, ペア保留の動物数は, j匹で変わらない.

// | うさぎ 1 ～ i | かめ 1 ～ i |

// ペア保留 | j匹 | j匹 |

// => 遷移は, (i - 1, j) => (i, j) で, 1通りと分かる.

dp[i][j][k] += dp[i - 1][j][nk];

// 2-3. うさぎ i, かめ i のいずれかを保留にしておいた動物とペア.

// | うさぎ 1 ～ (i - 1) | かめ 1 ～ (i - 1) |

// ペア保留 | j匹 | j匹 |

// => a1. うさぎ i, (ペア保留)かめをペアにする.

// | うさぎ 1 ～ i | かめ 1 ～ (i - 1) |

// ペア保留 | j匹 | (j - 1)匹 |

// => a2. かめ i はペア保留にする.

// | うさぎ 1 ～ i | かめ 1 ～ i |

// ペア保留 | j匹 | (j - 1 + 1)匹 |

// => b1. (ペア保留)うさぎ, かめ i をペアにする.

// | うさぎ 1 ～ (i - 1) | かめ 1 ～ i |

// ペア保留 | (j - 1)匹 | j匹 |

// => b2. うさぎ i はペア保留にする.

// | うさぎ 1 ～ i | かめ 1 ～ i |

// ペア保留 | (j - 1 + 1)匹 | j匹 |

// => a2, b2 から, 遷移は, (i - 1, j) => (i, j) で, j通りずつと分かる.

dp[i][j][k] += (2 * j) * dp[i - 1][j][nk];

// 2-4. うさぎ i, かめ i の両方を保留にしておいた動物とペア.

// | うさぎ 1 ～ (i - 1) | かめ 1 ～ (i - 1) |

// ペア保留 | (j + 1)匹 | (j + 1)匹 |

// => c1. うさぎ i, (ペア保留)かめをペアにする.

// | うさぎ 1 ～ i | かめ 1 ～ (i - 1) |

// ペア保留 | (j + 1)匹 | (j + 1 - 1)匹 |

// => c2. (ペア保留)うさぎ, かめ i をペアにする.

// | うさぎ 1 ～ i | かめ 1 ～ i |

// ペア保留 | (j + 1 - 1)匹 | (j + 1 - 1)匹 |

// => c2 から, 遷移は, (i - 1, j + 1) => (i, j) で, (j + 1) * (j + 1)通りと分かる.

dp[i][j][k] += (j + 1) * (j + 1) * dp[i - 1][j + 1][nk];

// 2-5. うさぎ i, かめ i の両方をペア保留.

// | うさぎ 1 ～ (i - 1) | かめ 1 ～ (i - 1) |

// ペア保留 | (j - 1)匹 | (j - 1)匹 |

// => うさぎ i, かめ i の両方をペア保留にするので, ペア保留の動物数は, j匹に変わる.

// | うさぎ 1 ～ i | かめ 1 ～ i |

// ペア保留 | (j - 1 + 1)匹 | (j - 1 + 1)匹 |

// => 遷移は, (i - 1, j - 1) => (i, j) で, 1通りと分かる.

if(j) dp[i][j][k] += dp[i - 1][j - 1][nk];

// 2-6. MOD.

dp[i][j][k] %= MOD;

}

// 3. 出力.

printf("%lld\n", dp[N][0][K]);

return 0;

}

[入力例]
3 2

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

[入力例]
39 14

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

[入力例]
5 6

[出力例]
24

[入力例]
7 10

[出力例]
366

[入力例]
10 18

[出力例]
50461

[入力例]
20 22

[出力例]
166643130

[入力例]
50 1234

[出力例]
202448366

[入力例]

3 2

[出力例]

※AtCoderテストケースより

[入力例]

39 14

[出力例]

74764168

※AtCoderテストケースより

[入力例]

5 6

[出力例]

[入力例]

7 10

[出力例]

366

[入力例]

10 18

[出力例]

50461

[入力例]

20 22

[出力例]

166643130

[入力例]

50 1234

[出力例]

202448366

■参照サイト
AtCoder Beginner Contest 134

2023年3月31日2023年3月31日

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

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

■感想.
1. 問題D は, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 解説のロジックで, ロボットアームのモードを計算できることに非常に興味深く思った.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/arc103/editorial.pdf
// 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 pb push_back
int ox[1010], oy[1010], x[1010], y[1010];

int main(){
    
    // 1. 入力情報.
    int N, o = 0;
    scanf("%d", &N);
    rep(i, N){
        scanf("%d %d", &ox[i], &oy[i]);
        x[i] = ox[i];
        y[i] = oy[i];
        o += ((x[i] + y[i]) & 1);
        
        // (x[i] + y[i]) mod 2 が 0.
        // -> モード R で 長さ 1 の 腕 を 追加予定.
        if(!((x[i] + y[i]) & 1)) --x[i];
    }
    
    // 2. (x[i] + y[i]) mod 2 が 一定でない.
    if(o % N != 0){
        puts("-1");
        return 0;
    }
    
    // 3. モード定数.
    char MODE[2][2];
    MODE[0][0] = 'L';
    MODE[0][1] = 'D';
    MODE[1][0] = 'U';
    MODE[1][1] = 'R';
    
    // 4. モード作成.
    auto f = [&](int cx, int cy) -> string {
        // 変換.
        int u = cx + cy;
        int v = cx - cy;
        
        // ex.
        // m = 5
        // (x, y) = (7, 10) => (u, v) = (17, -3) で, 
        //  17 =  16 + 8 - 4 - 2 - 1
        //  -3 = -16 + 8 + 4 + 2 - 1
        //  d =  1 => (-1, -1)   => L
        //  d =  2 => (-2, +2)   => D
        //  d =  4 => (-4, +4)   => D
        //  d =  8 => (+8, +8)   => R
        //  d = 16 => (+16, -16) => U
        //  => モード指定は, LDDRU と分かる.
        //  解説では, (17 + 31) / 2 = 24 = 11000, (-3 + 31) / 2 = 14 = 01110 から, 
        //  各桁の 0, 1 を 見て, LDDRU を 取得する方法なので, これを踏襲する.
        // 
        // (x, y) = (2, -8) => (u, v) = (-6, 10) で, 
        //  -6 = -16 + 8 + 4 - 2 - 1 + 1
        //  10 =  16 - 8 + 4 - 2 - 1 + 1
        //  d =  1 => (+1, +1)   => R
        //  d =  1 => (-1, -1)   => L
        //  d =  2 => (-2, -2)   => L
        //  d =  4 => (+4, +4)   => R
        //  d =  8 => (+8, -8)   => U
        //  d = 16 => (-16, +16) => D
        //  => モードの指定は, RLLRUD と分かる(x, y の合計が, 偶数なので, 長さ 1 の腕を追加).
        //  解説では, (-6 + 31 - 1) / 2 = 12 = 01100, (10 + 31 - 1) / 2 = 20 = 10100 から, 
        //  各桁の 0, 1 を 見て, RLLRUD を 取得する方法なので, これを踏襲する.
        //  
        // 各桁の 0, 1 を 見て, モードを構築.
        string ret;
        if(!o) ret.pb('R');
        u = (u + (1 << 31) - 1) / 2;
        v = (v + (1 << 31) - 1) / 2;
        rep(i, 31){
            int mu = ((1 << i) & u) > 0;
            int mv = ((1 << i) & v) > 0;
            ret.pb(MODE[mu][mv]);
        }
        
        // 返却.
        return ret;
    };
    
    // 5. 検算.
    auto g = [&](vi& v, string s, int xRef, int yRef) -> bool {
        // ロボットアームを, モードに従って, 動かす.
        int xCur = 0;
        int yCur = 0;
        rep(i, s.size()){
            if(s[i] == 'L') xCur -= v[i];
            if(s[i] == 'R') xCur += v[i];
            if(s[i] == 'D') yCur -= v[i];
            if(s[i] == 'U') yCur += v[i];
        }
        
        // 返却.
        return (xCur == xRef && yCur == yRef);
    };
    
    // 6. 2 の 冪乗.
    vi pow2;
    if(!o) pow2.pb(1);
    rep(i, 31) pow2.pb(1 << i);
    
    // 7. 出力.
    int m = pow2.size();
    printf("%d\n", m);
    rep(i, m) printf("%d%s", pow2[i], (i < m - 1) ? " " : "\n");
    rep(i, N){
        string ans = f(x[i], y[i]);
        assert(g(pow2, ans, ox[i], oy[i]));
        printf("%s\n", ans.c_str());
    }
    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

// 解き直し.

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

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

int ox[1010], oy[1010], x[1010], y[1010];

int main(){

// 1. 入力情報.

int N, o = 0;

scanf("%d", &N);

rep(i, N){

scanf("%d %d", &ox[i], &oy[i]);

x[i] = ox[i];

y[i] = oy[i];

o += ((x[i] + y[i]) & 1);

// (x[i] + y[i]) mod 2 が 0.

// -> モード R で長さ 1 の腕を追加予定.

if(!((x[i] + y[i]) & 1)) --x[i];

}

// 2. (x[i] + y[i]) mod 2 が一定でない.

if(o % N != 0){

puts("-1");

return 0;

}

// 3. モード定数.

char MODE[2][2];

MODE[0][0] = 'L';

MODE[0][1] = 'D';

MODE[1][0] = 'U';

MODE[1][1] = 'R';

// 4. モード作成.

auto f = [&](int cx, int cy) -> string {

// 変換.

int u = cx + cy;

int v = cx - cy;

// ex.

// m = 5

// (x, y) = (7, 10) => (u, v) = (17, -3) で,

// 17 = 16 + 8 - 4 - 2 - 1

// -3 = -16 + 8 + 4 + 2 - 1

// d = 1 => (-1, -1) => L

// d = 2 => (-2, +2) => D

// d = 4 => (-4, +4) => D

// d = 8 => (+8, +8) => R

// d = 16 => (+16, -16) => U

// => モード指定は, LDDRU と分かる.

// 解説では, (17 + 31) / 2 = 24 = 11000, (-3 + 31) / 2 = 14 = 01110 から,

// 各桁の 0, 1 を見て, LDDRU を取得する方法なので, これを踏襲する.

// (x, y) = (2, -8) => (u, v) = (-6, 10) で,

// -6 = -16 + 8 + 4 - 2 - 1 + 1

// 10 = 16 - 8 + 4 - 2 - 1 + 1

// d = 1 => (+1, +1) => R

// d = 1 => (-1, -1) => L

// d = 2 => (-2, -2) => L

// d = 4 => (+4, +4) => R

// d = 8 => (+8, -8) => U

// d = 16 => (-16, +16) => D

// => モードの指定は, RLLRUD と分かる(x, y の合計が, 偶数なので, 長さ 1 の腕を追加).

// 解説では, (-6 + 31 - 1) / 2 = 12 = 01100, (10 + 31 - 1) / 2 = 20 = 10100 から,

// 各桁の 0, 1 を見て, RLLRUD を取得する方法なので, これを踏襲する.

// 各桁の 0, 1 を見て, モードを構築.

string ret;

if(!o) ret.pb('R');

u = (u + (1 << 31) - 1) / 2;

v = (v + (1 << 31) - 1) / 2;

rep(i, 31){

int mu = ((1 << i) & u) > 0;

int mv = ((1 << i) & v) > 0;

ret.pb(MODE[mu][mv]);

}

// 返却.

return ret;

};

// 5. 検算.

auto g = [&](vi& v, string s, int xRef, int yRef) -> bool {

// ロボットアームを, モードに従って, 動かす.

int xCur = 0;

int yCur = 0;

rep(i, s.size()){

if(s[i] == 'L') xCur -= v[i];

if(s[i] == 'R') xCur += v[i];

if(s[i] == 'D') yCur -= v[i];

if(s[i] == 'U') yCur += v[i];

}

// 返却.

return (xCur == xRef && yCur == yRef);

};

// 6. 2 の冪乗.

vi pow2;

if(!o) pow2.pb(1);

rep(i, 31) pow2.pb(1 << i);

// 7. 出力.

int m = pow2.size();

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

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

rep(i, N){

string ans = f(x[i], y[i]);

assert(g(pow2, ans, ox[i], oy[i]));

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

}

return 0;

}

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

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

※但し, 上記のプログラムでは, 以下の内容が出力される.
31
1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 1048576 2097152 4194304 8388608 16777216 33554432 67108864 134217728 268435456 536870912 1073741824
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRL
UDDDDDDDDDDDDDDDDDDDDDDDDDDDDDU
DLLLLLLLLLLLLLLLLLLLLLLLLLLLLLR

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

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

[入力例]
2
1 1
1 1

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

※但し, 上記のプログラムでは, 以下の内容が出力される.
32
1 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 1048576 2097152 4194304 8388608 16777216 33554432 67108864 134217728 268435456 536870912 1073741824
RDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDU
RDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDU

[入力例]
3
-7 -3
7 3
-3 -7

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

※但し, 上記のプログラムでは, 以下の内容が出力される.
32
1 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 1048576 2097152 4194304 8388608 16777216 33554432 67108864 134217728 268435456 536870912 1073741824
RDUDRRRRRRRRRRRRRRRRRRRRRRRRRRRL
RDLULLLLLLLLLLLLLLLLLLLLLLLLLLLR
RDULUUUUUUUUUUUUUUUUUUUUUUUUUUUD

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

[出力例]
31
1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 1048576 2097152 4194304 8388608 16777216 33554432 67108864 134217728 268435456 536870912 1073741824
LDULLLLLLLLLLLLLLLLLLLLLLLLLLLR
RLDDDDDDDDDDDDDDDDDDDDDDDDDDDDU
RLRRRRRRRRRRRRRRRRRRRRRRRRRRRRL
LDRDDDDDDDDDDDDDDDDDDDDDDDDDDDU
UDULLLLLLLLLLLLLLLLLLLLLLLLLLLR

[入力例]
5
6 2
10 -4
10 6
-8 6
-11 13

[出力例]
32
1 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 1048576 2097152 4194304 8388608 16777216 33554432 67108864 134217728 268435456 536870912 1073741824
RRULLLLLLLLLLLLLLLLLLLLLLLLLLLLR
RLRDLLLLLLLLLLLLLLLLLLLLLLLLLLLR
RRUULLLLLLLLLLLLLLLLLLLLLLLLLLLR
RLUURRRRRRRRRRRRRRRRRRRRRRRRRRRL
RDDLLDDDDDDDDDDDDDDDDDDDDDDDDDDU

[入力例]
10
460 -6745
7020 1681
-2023 -6484
-6981 -8798
-1904 -8343
8931 2724
9350 -323
-5531 9192
-5986 -7491
-7388 4169

[出力例]
31
1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 1048576 2097152 4194304 8388608 16777216 33554432 67108864 134217728 268435456 536870912 1073741824
UDLURULUURDDUUUUUUUUUUUUUUUUUUD
DURRURRULDLDULLLLLLLLLLLLLLLLLR
LRDLDRUDUUURLUUUUUUUUUUUUUUUUUD
LURRLULDRDLLLUUUUUUUUUUUUUUUUUD
DDUURUURUUDRLUUUUUUUUUUUUUUUUUD
RRDDDLUULURDULLLLLLLLLLLLLLLLLR
ULDLLRDRUDLLRLLLLLLLLLLLLLLLLLR
LRRDDRLLRRULLDDDDDDDDDDDDDDDDDU
ULUUDRDRUDULLUUUUUUUUUUUUUUUUUD
DURDURDURLLRURRRRRRRRRRRRRRRRRL

[入力例]
25
-5953226 -2290492
5071301 -8503277
8944868 1245104
5395438 -7316964
6504388 -4105998
8012638 696802
8327105 2067117
-9453041 -9109887
-4509170 5221108
-5279356 2333670
-6479223 -7587591
4871060 -583664
5320575 -5570533
-5244415 9345609
-959587 1001313
8201127 -9098561
-7746306 -6836854
-2120747 1971013
4810527 9962529
2022565 9362577
6669237 -9851025
5118892 8323422
-7064351 -7326801
-3499880 -6185050
1137123 -592531

[出力例]
32
1 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 1048576 2097152 4194304 8388608 16777216 33554432 67108864 134217728 268435456 536870912 1073741824
RLLURRRUULRDRULLLULDLLDRRRRRRRRL
RUULRDURRLLLLRLURRDRLLRRUUUUUUUD
RRLLRDLUDLRRRRRLRUDURDDULLLLLLLR
RLLUDLDDDUURDRDRDULLLURRUUUUUUUD
RLULRUDRLDDUUDDRDLULLRLDLLLLLLLR
RRURRRDLRLULLRURDDRDLDDULLLLLLLR
RDUUDUULDUDUULLRDRRRRLDULLLLLLLR
RURRLLLRDDLLLLRRLDUDDRRRDRRRRRRL
RLLDDLLLRDRUULURDRLRLDDLDDDDDDDU
RLDRDUUDRLRUDLDDRRLDULURRRRRRRRL
RDDDLLLRRULRUDRDULLUDULLUUUUUUUD
RRLLLULRRRLRDRULRDLLDLRLLLLLLLLR
RDLUUDDURRRRLRLLLDRUURURUUUUUUUD
RDDUDDUDDDRDRLDUDUUUURLLDDDDDDDU
RDURRRUULUDLDULULDLLLDDDDDDDDDDU
RDRLLRRDLUURDDRDDRDLUUUURUUUUUUD
RRULDDDUDRDRRUULUDLLDRDDRRRRRRRL
RDDRULLDUUULRULRRLUUUURRRRRRRRRL
RURRRRDDURLULRRLRLLLDRURDDDDDDDU
RDULRULLULLUUULUULUUDULRDDDDDDDU
RUDLLUDLUUDLRUULUURRDDRRUUUUUUUD
RLDRLLDLUDURRLLLRDRRLLRRDDDDDDDU
RUUUDDLUDLLULUULLLRLLULLUUUUUUUD
RLUURRDDLLLRRRDDLLURLRULUUUUUUUD
RURUDDRLUURULDRLLDLRDLLLLLLLLLLR

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

[入力例]

-1 0

0 3

2 -1

[出力例]

1 2

※AtCoderテストケースより

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

1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 1048576 2097152 4194304 8388608 16777216 33554432 67108864 134217728 268435456 536870912 1073741824

RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRL

UDDDDDDDDDDDDDDDDDDDDDDDDDDDDDU

DLLLLLLLLLLLLLLLLLLLLLLLLLLLLLR

[入力例]

0 0

1 0

2 0

3 0

4 0

[出力例]

-1

※AtCoderテストケースより

[入力例]

1 1

[出力例]

1 1

※AtCoderテストケースより

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

1 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 1048576 2097152 4194304 8388608 16777216 33554432 67108864 134217728 268435456 536870912 1073741824

RDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDU

[入力例]

-7 -3

7 3

-3 -7

[出力例]

3 1 4 1 5

LRDUL

RDULR

DULRD

※AtCoderテストケースより

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

1 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 1048576 2097152 4194304 8388608 16777216 33554432 67108864 134217728 268435456 536870912 1073741824

RDUDRRRRRRRRRRRRRRRRRRRRRRRRRRRL

RDLULLLLLLLLLLLLLLLLLLLLLLLLLLLR

RDULUUUUUUUUUUUUUUUUUUUUUUUUUUUD

[入力例]

7 2

-1 4

-5 0

3 6

8 3

[出力例]

1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 1048576 2097152 4194304 8388608 16777216 33554432 67108864 134217728 268435456 536870912 1073741824

LDULLLLLLLLLLLLLLLLLLLLLLLLLLLR

RLDDDDDDDDDDDDDDDDDDDDDDDDDDDDU

RLRRRRRRRRRRRRRRRRRRRRRRRRRRRRL

LDRDDDDDDDDDDDDDDDDDDDDDDDDDDDU

UDULLLLLLLLLLLLLLLLLLLLLLLLLLLR

[入力例]

6 2

10 -4

10 6

-8 6

-11 13

[出力例]

1 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 1048576 2097152 4194304 8388608 16777216 33554432 67108864 134217728 268435456 536870912 1073741824

RRULLLLLLLLLLLLLLLLLLLLLLLLLLLLR

RLRDLLLLLLLLLLLLLLLLLLLLLLLLLLLR

RRUULLLLLLLLLLLLLLLLLLLLLLLLLLLR

RLUURRRRRRRRRRRRRRRRRRRRRRRRRRRL

RDDLLDDDDDDDDDDDDDDDDDDDDDDDDDDU

[入力例]

460 -6745

7020 1681

-2023 -6484

-6981 -8798

-1904 -8343

8931 2724

9350 -323

-5531 9192

-5986 -7491

-7388 4169

[出力例]

1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 1048576 2097152 4194304 8388608 16777216 33554432 67108864 134217728 268435456 536870912 1073741824

UDLURULUURDDUUUUUUUUUUUUUUUUUUD

DURRURRULDLDULLLLLLLLLLLLLLLLLR

LRDLDRUDUUURLUUUUUUUUUUUUUUUUUD

LURRLULDRDLLLUUUUUUUUUUUUUUUUUD

DDUURUURUUDRLUUUUUUUUUUUUUUUUUD

RRDDDLUULURDULLLLLLLLLLLLLLLLLR

ULDLLRDRUDLLRLLLLLLLLLLLLLLLLLR

LRRDDRLLRRULLDDDDDDDDDDDDDDDDDU

ULUUDRDRUDULLUUUUUUUUUUUUUUUUUD

DURDURDURLLRURRRRRRRRRRRRRRRRRL

[入力例]

-5953226 -2290492

5071301 -8503277

8944868 1245104

5395438 -7316964

6504388 -4105998

8012638 696802

8327105 2067117

-9453041 -9109887

-4509170 5221108

-5279356 2333670

-6479223 -7587591

4871060 -583664

5320575 -5570533

-5244415 9345609

-959587 1001313

8201127 -9098561

-7746306 -6836854

-2120747 1971013

4810527 9962529

2022565 9362577

6669237 -9851025

5118892 8323422

-7064351 -7326801

-3499880 -6185050

1137123 -592531

[出力例]

1 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 1048576 2097152 4194304 8388608 16777216 33554432 67108864 134217728 268435456 536870912 1073741824

RLLURRRUULRDRULLLULDLLDRRRRRRRRL

RUULRDURRLLLLRLURRDRLLRRUUUUUUUD

RRLLRDLUDLRRRRRLRUDURDDULLLLLLLR

RLLUDLDDDUURDRDRDULLLURRUUUUUUUD

RLULRUDRLDDUUDDRDLULLRLDLLLLLLLR

RRURRRDLRLULLRURDDRDLDDULLLLLLLR

RDUUDUULDUDUULLRDRRRRLDULLLLLLLR

RURRLLLRDDLLLLRRLDUDDRRRDRRRRRRL

RLLDDLLLRDRUULURDRLRLDDLDDDDDDDU

RLDRDUUDRLRUDLDDRRLDULURRRRRRRRL

RDDDLLLRRULRUDRDULLUDULLUUUUUUUD

RRLLLULRRRLRDRULRDLLDLRLLLLLLLLR

RDLUUDDURRRRLRLLLDRUURURUUUUUUUD

RDDUDDUDDDRDRLDUDUUUURLLDDDDDDDU

RDURRRUULUDLDULULDLLLDDDDDDDDDDU

RDRLLRRDLUURDDRDDRDLUUUURUUUUUUD

RRULDDDUDRDRRUULUDLLDRDDRRRRRRRL

RDDRULLDUUULRULRRLUUUURRRRRRRRRL

RURRRRDDURLULRRLRLLLDRURDDDDDDDU

RDULRULLULLUUULUULUUDULRDDDDDDDU

RUDLLUDLUUDLRUULUURRDDRRUUUUUUUD

RLDRLLDLUDURRLLLRDRRLLRRDDDDDDDU

RUUUDDLUDLLULUULLLRLLULLUUUUUUUD

RLUURRDDLLLRRRDDLLURLRULUUUUUUUD

RURUDDRLUURULDRLLDLRDLLLLLLLLLLR

■参照サイト
AtCoder Regular Contest 103

2023年3月29日

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

C++の練習を兼ねて, AtCoder Beginner Contest 076 の問題D (AtCoder Express) を解いてみた.

■感想.
1. 問題D は, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 解説のロジックで, 走れる最大の距離を計算できることに非常に興味深く思った.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

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

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%d", &t[i + 1]);
    rep(i, N) scanf("%d", &v[i + 1]);
    
    // 2. 累積和.
    rep(i, N + 2) tCum[i + 1] = tCum[i] + t[i];
    
    // 3. 最小速度(0.5秒刻み).
    rep(i, 40404) f[i] = 2020202020.0;
    rep(i, N + 2){
        // 区間 の l, r.
        int l = 2 * tCum[i + 0];
        int r = 2 * tCum[i + 1];
        
        // 区間[0, l].
        repr(x, l, 0) f[x] = min(f[x], (double)v[i] + 0.5 * (l - x));
        
        // 区間[l, r].
        repx(x, l, r + 1) f[x] = min(f[x], (double)v[i]);
        
        // 区間[r, 40404).
        repx(x, r, 40404) f[x] = min(f[x], (double)v[i] + 0.5 * (x - r));
    }
    
    // 4. 集計.
    double ans = 0.0;
    rep(x, 2 * tCum[N + 1]) ans += f[x];
    
    // 5. 出力.
    printf("%.15lf\n", ans / 2);
    return 0;
    
}

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

int t[202], v[202], tCum[202];

double f[40404];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

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

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

// 2. 累積和.

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

// 3. 最小速度(0.5秒刻み).

rep(i, 40404) f[i] = 2020202020.0;

rep(i, N + 2){

// 区間の l, r.

int l = 2 * tCum[i + 0];

int r = 2 * tCum[i + 1];

// 区間[0, l].

repr(x, l, 0) f[x] = min(f[x], (double)v[i] + 0.5 * (l - x));

// 区間[l, r].

repx(x, l, r + 1) f[x] = min(f[x], (double)v[i]);

// 区間[r, 40404).

repx(x, r, 40404) f[x] = min(f[x], (double)v[i] + 0.5 * (x - r));

}

// 4. 集計.

double ans = 0.0;

rep(x, 2 * tCum[N + 1]) ans += f[x];

// 5. 出力.

printf("%.15lf\n", ans / 2);

return 0;

}

[入力例]
1
100
30

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

[入力例]
2
60 50
34 38

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

[入力例]
3
12 14 2
6 2 7

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

[入力例]
1
9
10

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

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

[入力例]
10
64 55 27 35 76 119 7 18 49 100
29 19 31 39 27 48 41 87 55 70

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

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

[入力例]
5
13 152 63 71 93
36 30 22 5 23

[出力例]
7777.000000000000000

[入力例]
30
151 100 66 148 150 40 132 172 164 76 160 121 51 67 39 136 170 133 78 135 125 197 117 151 186 136 111 123 101 92
62 80 50 51 60 77 38 78 86 81 68 77 99 80 79 50 72 52 81 56 87 55 30 33 81 60 62 87 50 64

[出力例]
222222.000000000000000

[入力例]
100
8 121 6 60 172 83 136 108 1 51 165 36 98 164 50 92 66 174 22 175 106 190 110 107 108 38 70 5 93 199 133 119 166 167 68 128 77 66 133 177 87 184 194 34 175 98 153 71 72 119 172 71 51 13 168 156 165 155 31 189 134 127 103 22 67 110 47 25 115 111 49 12 6 39 79 55 128 176 156 184 67 123 167 78 161 184 155 88 76 109 132 59 50 160 122 29 132 110 61 180
5 53 25 54 18 99 19 87 25 8 8 73 26 83 8 26 64 66 59 63 64 33 89 64 57 62 69 50 62 51 60 82 70 33 73 55 99 55 33 62 88 27 87 11 60 86 1 86 96 97 72 63 99 33 11 50 95 60 67 86 55 88 77 64 69 77 79 55 99 7 71 30 94 67 81 23 5 84 31 96 22 55 57 60 70 40 36 51 77 37 57 7 11 58 10 11 89 11 93 58

[出力例]
500000.000000000000000

[入力例]

100

[出力例]

2100.000000000000000

※AtCoderテストケースより

[入力例]

60 50

34 38

[出力例]

2632.000000000000000

※AtCoderテストケースより

[入力例]

12 14 2

6 2 7

[出力例]

76.000000000000000

※AtCoderテストケースより

[入力例]

[出力例]

20.250000000000000000

※AtCoderテストケースより

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

20.250000000000000

[入力例]

64 55 27 35 76 119 7 18 49 100

29 19 31 39 27 48 41 87 55 70

[出力例]

20291.000000000000

※AtCoderテストケースより

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

20291.000000000000000

[入力例]

13 152 63 71 93

36 30 22 5 23

[出力例]

7777.000000000000000

[入力例]

151 100 66 148 150 40 132 172 164 76 160 121 51 67 39 136 170 133 78 135 125 197 117 151 186 136 111 123 101 92

62 80 50 51 60 77 38 78 86 81 68 77 99 80 79 50 72 52 81 56 87 55 30 33 81 60 62 87 50 64

[出力例]

222222.000000000000000

[入力例]

100

8 121 6 60 172 83 136 108 1 51 165 36 98 164 50 92 66 174 22 175 106 190 110 107 108 38 70 5 93 199 133 119 166 167 68 128 77 66 133 177 87 184 194 34 175 98 153 71 72 119 172 71 51 13 168 156 165 155 31 189 134 127 103 22 67 110 47 25 115 111 49 12 6 39 79 55 128 176 156 184 67 123 167 78 161 184 155 88 76 109 132 59 50 160 122 29 132 110 61 180

5 53 25 54 18 99 19 87 25 8 8 73 26 83 8 26 64 66 59 63 64 33 89 64 57 62 69 50 62 51 60 82 70 33 73 55 99 55 33 62 88 27 87 11 60 86 1 86 96 97 72 63 99 33 11 50 95 60 67 86 55 88 77 64 69 77 79 55 99 7 71 30 94 67 81 23 5 84 31 96 22 55 57 60 70 40 36 51 77 37 57 7 11 58 10 11 89 11 93 58

[出力例]

500000.000000000000000

■参照サイト
AtCoder Beginner Contest 076

2023年3月26日2023年3月26日

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

C++の練習を兼ねて, AtCoder Beginner Contest 133 の問題E (Virus Tree 2) を解いてみた.

■感想.
1. 問題E は, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 苦手な動的計画法(木dp)の訓練を積めたので, 非常に良かったと思う.
3. メモ化再帰の復習もできたので, 非常に良かったと思う.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/abc133/editorial.pdf
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vi = vector<int>;
using vvi = vector<vi>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
const LL MOD = 1e9 + 7;
const int LIMIT = 101010;
LL FAC[LIMIT], INV[LIMIT], dp[LIMIT];

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

// 順列(nPk)計算用(mod版).
// ※配列FAC, INV は, 事前に計算済のものを使う.
// @param n: 対象となる要素の個数.
// @param k: 選択する要素の個数.
// @return: 順列(nPk)の計算結果(mod版).
LL permutation(LL n, LL k){
    if(n < 0 || k < 0 || k > n) return 0LL;
    LL ret = FAC[n] * INV[n - k] % MOD;
    return ret;
}

int main(){
    
    // 1. 入力情報.
    int N, K;
    scanf("%d %d", &N, &K);
    vvi G(N);
    rep(i, N - 1){
        int a, b;
        scanf("%d %d", &a, &b);
        --a, --b;
        G[a].pb(b);
        G[b].pb(a);
    }
    
    // 2. 事前準備.
    FAC[0] = INV[0] = 1;
    repx(i, 1, LIMIT){
        FAC[i] = (LL)i * FAC[i - 1] % MOD;
        INV[i] = mPow(FAC[i], MOD - 2);
    }
    rep(i, N) dp[i] = -1;
     
    // 3. dfs.
    // https://ja.wikipedia.org/wiki/深さ優先探索
    auto dfs = [&](auto&& self, int cur, int bef) -> LL {
        // 終了条件.
        if(dp[cur] != -1) return dp[cur];
        
        // 葉っぱ(根以外).
        if(cur != 0 && G[cur].size() == 1) return (dp[cur] = permutation(K - 2, 0));
        
        // 隣接頂点.
        LL ret = 1, cx = 0;
        for(auto &nex : G[cur]){
            if(nex == bef) continue;
            ret *= (dp[nex] != -1) ? dp[nex] : self(self, nex, cur);
            ret %= MOD;
            ++cx;
        }
        
        // 根.
        if(cur == 0){
            ret *= K;
            ret %= MOD;
            ret *= permutation(K - 1, cx);
            ret %= MOD;
        }
        
        // 根以外.
        if(cur != 0){
            ret *= permutation(K - 2, cx);
            ret %= MOD;
        }
        
        // メモ化して返却.
        return (dp[cur] = ret);
    };
    
    // 4. 出力.
    printf("%lld\n", dfs(dfs, 0, -1));
    return 0;
    
}

100

101

102

103

104

105

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vi = vector<int>;

using vvi = vector<vi>;

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

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

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

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

#define pb push_back

const LL MOD = 1e9 + 7;

const int LIMIT = 101010;

LL FAC[LIMIT], INV[LIMIT], dp[LIMIT];

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

}

// 順列(nPk)計算用(mod版).

// ※配列FAC, INV は, 事前に計算済のものを使う.

// @param n: 対象となる要素の個数.

// @param k: 選択する要素の個数.

// @return: 順列(nPk)の計算結果(mod版).

LL permutation(LL n, LL k){

if(n < 0 || k < 0 || k > n) return 0LL;

LL ret = FAC[n] * INV[n - k] % MOD;

return ret;

}

int main(){

// 1. 入力情報.

int N, K;

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

vvi G(N);

rep(i, N - 1){

int a, b;

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

--a, --b;

G[a].pb(b);

G[b].pb(a);

}

// 2. 事前準備.

FAC[0] = INV[0] = 1;

repx(i, 1, LIMIT){

FAC[i] = (LL)i * FAC[i - 1] % MOD;

INV[i] = mPow(FAC[i], MOD - 2);

}

rep(i, N) dp[i] = -1;

// 3. dfs.

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

auto dfs = [&](auto&& self, int cur, int bef) -> LL {

// 終了条件.

if(dp[cur] != -1) return dp[cur];

// 葉っぱ(根以外).

if(cur != 0 && G[cur].size() == 1) return (dp[cur] = permutation(K - 2, 0));

// 隣接頂点.

LL ret = 1, cx = 0;

for(auto &nex : G[cur]){

if(nex == bef) continue;

ret *= (dp[nex] != -1) ? dp[nex] : self(self, nex, cur);

ret %= MOD;

++cx;

}

// 根.

if(cur == 0){

ret *= K;

ret %= MOD;

ret *= permutation(K - 1, cx);

ret %= MOD;

}

// 根以外.

if(cur != 0){

ret *= permutation(K - 2, cx);

ret %= MOD;

}

// メモ化して返却.

return (dp[cur] = ret);

};

// 4. 出力.

printf("%lld\n", dfs(dfs, 0, -1));

return 0;

}

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

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

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

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

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

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

[入力例]
1 5

[出力例]
5

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

[出力例]
4320

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

[出力例]
585418077

[入力例]

4 3

1 2

2 3

3 4

[出力例]

※AtCoderテストケースより

[入力例]

5 4

1 2

1 3

1 4

4 5

[出力例]

※AtCoderテストケースより

[入力例]

16 22

12 1

3 1

4 16

7 12

6 2

2 15

5 16

14 16

10 11

3 10

3 13

8 6

16 8

9 12

4 3

[出力例]

271414432

※AtCoderテストケースより

[入力例]

1 5

[出力例]

[入力例]

9 5

1 2

3 1

1 4

5 2

6 2

7 3

3 8

9 3

[出力例]

4320

[入力例]

20 11

1 2

5 1

6 1

3 2

4 2

3 20

4 11

4 12

5 15

16 5

7 6

6 8

8 9

8 10

13 9

14 9

13 17

13 18

13 19

[出力例]

585418077

■参照サイト
AtCoder Beginner Contest 133

C++の練習を兼ねて, AtCoder Beginner Contest 197 の 問題F (Construct a Palindrome) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 295 の 問題C (Socks) ～ 問題E (Kth Number) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 199 の 問題D (RGB Coloring 2) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 296 の 問題C (Gap Existence) ～ 問題E (Transition Game) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 158 の 問題A (+3 +5 +7) ～ 問題C (All Pair Digit Sums) を解いてみた.

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

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

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

C++の練習を兼ねて, AtCoder Beginner Contest 076 の 問題D (AtCoder Express) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 133 の 問題E (Virus Tree 2) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 197 の問題F (Construct a Palindrome) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 295 の問題C (Socks) ～問題E (Kth Number) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 199 の問題D (RGB Coloring 2) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 296 の問題C (Gap Existence) ～問題E (Transition Game) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 158 の問題A (+3 +5 +7) ～問題C (All Pair Digit Sums) を解いてみた.

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

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

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

C++の練習を兼ねて, AtCoder Beginner Contest 076 の問題D (AtCoder Express) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 133 の問題E (Virus Tree 2) を解いてみた.