個人用メモ帳

2022年2月16日

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

C++の練習を兼ねて, JOI 2021/2022 本選過去問の問題A (インターカステラー (Intercastellar)) を解いてみた.

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

本家のサイト JOI 2021/2022 本選過去問解説の各リンクをご覧下さい.

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vl = vector<LL>;
#define repx(i, a, b) for(int i = a; i < b; i++)
#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()

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    vl p, q;
    p.pb(0);
    rep(i, N){
        LL a, c = 0;
        scanf("%lld", &a);
        
        // ピースの細分化.
        while(a % 2 == 0){
            ++c;
            a >>= 1;
        }
        
        // 細分化したカステラ情報(位置, 長さ)を保存.
        p.pb(p.back() + (1LL << c));
        q.pb(a);
    }
    
    // 2. クエリ回答.
    int Q;
    scanf("%d", &Q);
    rep(i, Q){
        // 2-1. 質問.
        LL x;
        scanf("%lld", &x);
        
        // 2-2. カステラの場所.
        int at = lower_bound(all(p), x) - p.begin();
        --at;
        
        // 2-3. 出力.
        printf("%lld\n", q[at]);
    }
    return 0;
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vl = vector<LL>;

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

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

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

vl p, q;

p.pb(0);

rep(i, N){

LL a, c = 0;

scanf("%lld", &a);

// ピースの細分化.

while(a % 2 == 0){

++c;

a >>= 1;

}

// 細分化したカステラ情報(位置, 長さ)を保存.

p.pb(p.back() + (1LL << c));

q.pb(a);

}

// 2. クエリ回答.

int Q;

scanf("%d", &Q);

rep(i, Q){

// 2-1. 質問.

LL x;

scanf("%lld", &x);

// 2-2. カステラの場所.

int at = lower_bound(all(p), x) - p.begin();

--at;

// 2-3. 出力.

printf("%lld\n", q[at]);

}

return 0;

}

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

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

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

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

[入力例]
16
536870912
402653184
536870912
536870912
134217728
536870912
671088640
536870912
536870912
536870912
939524096
805306368
536870912
956301312
536870912
536870912
5
2500000000
3355443201
4294967296
5111111111
6190792704

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

[入力例]
15
2592
7680
576
92160
57600
450
33177600
2
675
225
48000
3072000
20736
147456
45
11
233
377
610
987
1597
2584
4181
6765
10946
17711
28657

[出力例]
15
15
45
45
45
45
2025
2025
2025
2025
9

[入力例]
25
37158912
2646
840
216
73728
196
3641573376
3430
98784
1555848
1032192
260112384
47185920
1209655
1032192
12042248
236027904
110100480
393216
28800000
5529600
63221765
132765696
72576
131072
15
274
504
927
1705
3136
5768
10609
19513
35890
66012
121415
223317
410744
755476
1389537

[出力例]
567
567
567
567
567
567
567
567
567
9
27783
3969
45
45
105

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

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

536870912

402653184

536870912

134217728

536870912

671088640

536870912

939524096

805306368

536870912

956301312

536870912

2500000000

3355443201

4294967296

5111111111

6190792704

[出力例]

※AtCoderテストケースより

[入力例]

2592

7680

576

92160

57600

450

33177600

675

225

48000

3072000

20736

147456

233

377

610

987

1597

2584

4181

6765

10946

17711

28657

[出力例]

2025

[入力例]

37158912

2646

840

216

73728

196

3641573376

3430

98784

1555848

1032192

260112384

47185920

1209655

1032192

12042248

236027904

110100480

393216

28800000

5529600

63221765

132765696

72576

131072

274

504

927

1705

3136

5768

10609

19513

35890

66012

121415

223317

410744

755476

1389537

[出力例]

567

27783

3969

105

■参照サイト
JOI 2021/2022 本選過去問

2022年2月15日

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

C++の練習を兼ねて, AtCoder Beginner Contest 225 の問題C (Calendar Validator) ～問題D (Play Train) を解いてみた.

■感想.
1. 問題C, Dは, 方針を絞り込めたので, AC版に到達できたと思う.
2. 問題D で, 標準ライブラリ std::deque を利用するロジックが, 非常に面白いと感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

■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 b[10101][7], m[7];

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    rep(i, N) rep(j, M) scanf("%d", &b[i][j]);
    
    // 2. 余り.
    // -> 006.txt などで, WA版となったので, ロジック修正.
    repx(i, 1, 8) m[i % 7] = i;
    
    // 3. 判定.
    // 3-1. 横方向.
    // -> 1ずつ増加しているか？
    //    余りも考慮.
    bool ok = true;
    rep(i, N){
        rep(j, M - 1){
            if(b[i][j + 1] != b[i][j] + 1)          ok = false;
            if(m[b[i][j + 1] % 7] < m[b[i][j] % 7]) ok = false;
        }
    }
    
    // 3-2. 縦方向.
    // -> 7ずつ増加しているか？
    rep(j, M) rep(i, N - 1) if(b[i + 1][j] != b[i][j] + 7) ok = false;
    
    // 4. 出力.
    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 b[10101][7], m[7];

int main(){

// 1. 入力情報.

int N, M;

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

rep(i, N) rep(j, M) scanf("%d", &b[i][j]);

// 2. 余り.

// -> 006.txt などで, WA版となったので, ロジック修正.

repx(i, 1, 8) m[i % 7] = i;

// 3. 判定.

// 3-1. 横方向.

// -> 1ずつ増加しているか？

// 余りも考慮.

bool ok = true;

rep(i, N){

rep(j, M - 1){

if(b[i][j + 1] != b[i][j] + 1) ok = false;

if(m[b[i][j + 1] % 7] < m[b[i][j] % 7]) ok = false;

}

// 3-2. 縦方向.

// -> 7ずつ増加しているか？

rep(j, M) rep(i, N - 1) if(b[i + 1][j] != b[i][j] + 7) ok = false;

// 4. 出力.

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

return 0;

}

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

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

[入力例]
2 1
1
2

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

[入力例]
10 4
1346 1347 1348 1349
1353 1354 1355 1356
1360 1361 1362 1363
1367 1368 1369 1370
1374 1375 1376 1377
1381 1382 1383 1384
1388 1389 1390 1391
1395 1396 1397 1398
1402 1403 1404 1405
1409 1410 1411 1412

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

[入力例]
7 5
990 991 992 993 994
997 998 999 1000 1001
1004 1005 1006 1007 1008
1011 1012 1013 1014 1015
1018 1019 1020 1021 1022
1025 1026 1027 1028 1029
1032 1033 1034 1035 1036

[出力例]
Yes

[入力例]
10 5
3296 3297 3298 3299 3300
3303 3304 3305 3306 3307
3310 3311 3312 3313 3314
3317 3318 3319 3320 3321
3324 3325 3326 3327 3328
3331 3332 3333 3334 3335
3338 3339 3340 3341 3342
3345 3346 3347 3348 3349
3352 3353 3354 3355 3356
3359 3360 3361 3362 3363

[出力例]
No

[入力例]
20 3
5168 5169 5170
5175 5176 5177
5182 5183 5184
5189 5190 5191
5196 5197 5198
5203 5204 5205
5210 5211 5212
5217 5218 5219
5224 5225 5226
5231 5232 5233
5238 5239 5240
5245 5246 5247
5252 5253 5254
5259 5260 5261
5266 5267 5268
5273 5274 5275
5280 5281 5282
5287 5288 5289
5294 5295 5296
5301 5302 5303

[出力例]
Yes

[入力例]

2 3

1 2 3

8 9 10

[出力例]

Yes

※AtCoderテストケースより

[入力例]

2 1

[出力例]

※AtCoderテストケースより

[入力例]

10 4

1346 1347 1348 1349

1353 1354 1355 1356

1360 1361 1362 1363

1367 1368 1369 1370

1374 1375 1376 1377

1381 1382 1383 1384

1388 1389 1390 1391

1395 1396 1397 1398

1402 1403 1404 1405

1409 1410 1411 1412

[出力例]

Yes

※AtCoderテストケースより

[入力例]

7 5

990 991 992 993 994

997 998 999 1000 1001

1004 1005 1006 1007 1008

1011 1012 1013 1014 1015

1018 1019 1020 1021 1022

1025 1026 1027 1028 1029

1032 1033 1034 1035 1036

[出力例]

Yes

[入力例]

10 5

3296 3297 3298 3299 3300

3303 3304 3305 3306 3307

3310 3311 3312 3313 3314

3317 3318 3319 3320 3321

3324 3325 3326 3327 3328

3331 3332 3333 3334 3335

3338 3339 3340 3341 3342

3345 3346 3347 3348 3349

3352 3353 3354 3355 3356

3359 3360 3361 3362 3363

[出力例]

[入力例]

20 3

5168 5169 5170

5175 5176 5177

5182 5183 5184

5189 5190 5191

5196 5197 5198

5203 5204 5205

5210 5211 5212

5217 5218 5219

5224 5225 5226

5231 5232 5233

5238 5239 5240

5245 5246 5247

5252 5253 5254

5259 5260 5261

5266 5267 5268

5273 5274 5275

5280 5281 5282

5287 5288 5289

5294 5295 5296

5301 5302 5303

[出力例]

Yes

■C++版プログラム(問題D／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 pof pop_front
#define pob pop_back
#define puf push_front
#define pub push_back
int p[101010], q[101010];

int main(){
    
    // 1. 入力情報.
    int N, Q;
    scanf("%d %d", &N, &Q);
    
    // 2. 初期化.
    rep(i, N) p[i] = q[i] = -1;
    
    // 3. クエリ回答.
    rep(i, Q){
        // 3-1. クエリ入力情報.
        int c;
        scanf("%d ", &c);
        
        // 3-2. クエリ 1.
        if(c == 1){
            int x, y;
            scanf("%d %d", &x, &y);
            --x;
            --y;
            
            // 電車 y の 親 を 電車 x と 設定.
            p[y] = x;
            q[x] = y;
        }
        
        // 3-3. クエリ 2.
        if(c == 2){
            int x, y;
            scanf("%d %d", &x, &y);
            --x;
            --y;
            
            // 電車 x, y の 親子関係 を 廃止.
            p[y] = -1;
            q[x] = -1;
        }
        
        // 3-4. クエリ 3.
        if(c == 3){
            int x;
            scanf("%d", &x);
            --x;
            
            // 電車 x の 親.
            int cur = x;
            deque<int> dq;
            while(cur != -1){
                dq.puf(cur);
                cur = p[cur];
            }
            
            // 電車 x の 子.
            cur = x;
            dq.pob();
            while(cur != -1){
                dq.pub(cur);
                cur = q[cur];
            }
            
            // 出力.
            int M = dq.size();
            printf("%d ", M);
            rep(i, M) printf("%d%s", dq[i] + 1, (i < M - 1) ? " " : "\n");
        }
    }
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

#define pof pop_front

#define pob pop_back

#define puf push_front

#define pub push_back

int p[101010], q[101010];

int main(){

// 1. 入力情報.

int N, Q;

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

// 2. 初期化.

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

// 3. クエリ回答.

rep(i, Q){

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

int c;

scanf("%d ", &c);

// 3-2. クエリ 1.

if(c == 1){

int x, y;

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

--x;

--y;

// 電車 y の親を電車 x と設定.

p[y] = x;

q[x] = y;

}

// 3-3. クエリ 2.

if(c == 2){

int x, y;

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

--x;

--y;

// 電車 x, y の親子関係を廃止.

p[y] = -1;

q[x] = -1;

}

// 3-4. クエリ 3.

if(c == 3){

int x;

scanf("%d", &x);

--x;

// 電車 x の親.

int cur = x;

deque<int> dq;

while(cur != -1){

dq.puf(cur);

cur = p[cur];

}

// 電車 x の子.

cur = x;

dq.pob();

while(cur != -1){

dq.pub(cur);

cur = q[cur];

}

// 出力.

int M = dq.size();

printf("%d ", M);

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

}

return 0;

}

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

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

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

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

[入力例]

7 14

1 6 3

1 4 1

1 5 2

1 2 7

1 3 5

3 2

3 4

3 6

2 3 5

2 4 1

1 1 5

3 2

3 4

3 6

[出力例]

5 6 3 5 2 7

2 4 1

5 6 3 5 2 7

4 1 5 2 7

1 4

2 6 3

※AtCoderテストケースより

[入力例]

12 25

1 1 2

3 1

1 2 3

1 5 7

1 8 9

1 11 12

2 8 9

1 10 8

1 3 10

3 3

1 6 4

2 2 3

1 2 6

1 4 5

3 5

1 7 3

3 10

2 4 5

3 7

1 12 5

2 3 10

3 5

1 4 9

1 9 11

3 12

[出力例]

2 1 2

5 1 2 3 10 8

6 1 2 6 4 5 7

9 1 2 6 4 5 7 3 10 8

5 5 7 3 10 8

5 11 12 5 7 3

10 1 2 6 4 9 11 12 5 7 3

■参照サイト
UNICORNプログラミングコンテスト2021(AtCoder Beginner Contest 225)

2022年2月15日

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

C++の練習を兼ねて, AtCoder Regular Contest 135 の問題C (XOR to All) を解いてみた.

■感想.
1. 問題Cは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 一括して数え上げるロジックが, 非常に面白いと感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/arc135/editorial/3356
// 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 x[303030], d[33][2];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N){
        scanf("%lld", &x[i + 1]);
        rep(j, 30){
            if(x[i + 1] & (1 << j)) d[j][1]++; // 1 を カウント.
            else                    d[j][0]++; // 0 を カウント.
        }
    }
    
    // 2. 操作後の数列 B.
    LL ans = 0;
    rep(i, N + 1){
        // 2-1. 各 x で 計算.
        LL cur = 0;
        rep(j, 30){
            if(x[i] & (1 << j)) cur += (1LL << j) * d[j][0];
            else                cur += (1LL << j) * d[j][1];
        }
        
        // 2-2. 最大値更新.
        ans = max(ans, cur);
    }
    
    // 3. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc135/editorial/3356

// 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 x[303030], d[33][2];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

rep(i, N){

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

rep(j, 30){

if(x[i + 1] & (1 << j)) d[j][1]++; // 1 をカウント.

else d[j][0]++; // 0 をカウント.

}

// 2. 操作後の数列 B.

LL ans = 0;

rep(i, N + 1){

// 2-1. 各 x で計算.

LL cur = 0;

rep(j, 30){

if(x[i] & (1 << j)) cur += (1LL << j) * d[j][0];

else cur += (1LL << j) * d[j][1];

}

// 2-2. 最大値更新.

ans = max(ans, cur);

}

// 3. 出力.

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

return 0;

}

[入力例]
5
1 2 3 4 5

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

[入力例]
5
10 10 10 10 10

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

[入力例]
5
3 1 4 1 5

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

[入力例]
10
58 53 36 53 71 45 79 56 91 64

[出力例]
736

[入力例]
50
11359 6089 6053 5356 4815 2314 5214 1971 11222 11632 1480 5775 9135 6597 4431 1028 10270 4920 1892 538 4805 6507 3228 5494 7929 7504 9109 5981 7001 11330 10230 4253 8590 4103 7524 7037 4356 9942 8591 7956 2185 8932 6956 12166 3423 10070 11659 3761 8262 10990

[出力例]
475341

[入力例]

1 2 3 4 5

[出力例]

※AtCoderのテストケースより

[入力例]

10 10 10 10 10

[出力例]

※AtCoderのテストケースより

[入力例]

3 1 4 1 5

[出力例]

※AtCoderのテストケースより

[入力例]

58 53 36 53 71 45 79 56 91 64

[出力例]

736

[入力例]

11359 6089 6053 5356 4815 2314 5214 1971 11222 11632 1480 5775 9135 6597 4431 1028 10270 4920 1892 538 4805 6507 3228 5494 7929 7504 9109 5981 7001 11330 10230 4253 8590 4103 7524 7037 4356 9942 8591 7956 2185 8932 6956 12166 3423 10070 11659 3761 8262 10990

[出力例]

475341

■参照サイト
AtCoder Regular Contest 135

2022年2月13日

Python（Qiskit）について（２０）

概要

Qiskit について, 学習サイトのサンプルプログラムを動かしてみた.
動作環境は, 学習サイト上で行った
実行プログラム, 解説は, 下記の参照サイトをご覧ください

感想

ベルンシュタイン・ヴァジラニアルゴリズムの演算方法で, 量子オラクルについて確認してみた.
5 ～ 6量子ビットで確認したが出力結果が改行されなかったので, wbrタグを手動埋め込みし改行させて確認している.
下記の (参考)シミュレーターでの実験の通り, ベルンシュタイン・ヴァジラニアルゴリズムのプログラム内に, 秘密の文字列を反転する操作が実装されており, 個人的には, 手計算前に, 秘密の文字列を反転させる操作と符合すると予想する.
演習問題では, 10量子ビット(“1110110101”)での記述もあったが, 実行後に, エラー(Too large to display)となったため, 詳細は確認できなかったが, 5 ～ 6量子ビットで確認出来たので, 十分だと思う.

ベルンシュタイン・ヴァジラニアルゴリズム(演習問題改題ほか)

量子オラクル(5量子ビット “10011”)

[手計算]

※ 秘密の文字列 "10011" を 反転し, "11001" と読み替えて, 計算する必要があるように見える.

1 / √32 * {
  (-1)(00000･11001)|00000> + 
  (-1)(00001･11001)|00001> + 
  (-1)(00010･11001)|00010> + 
  (-1)(00011･11001)|00011> + 
  (-1)(00100･11001)|00100> + 
  (-1)(00101･11001)|00101> + 
  (-1)(00110･11001)|00110> + 
  (-1)(00111･11001)|00111> + 
  (-1)(01000･11001)|01000> + 
  (-1)(01001･11001)|01001> + 
  (-1)(01010･11001)|01010> + 
  (-1)(01011･11001)|01011> + 
  (-1)(01100･11001)|01100> + 
  (-1)(01101･11001)|01101> + 
  (-1)(01110･11001)|01110> + 
  (-1)(01111･11001)|01111> + 
  (-1)(10000･11001)|10000> + 
  (-1)(10001･11001)|10001> + 
  (-1)(10010･11001)|10010> + 
  (-1)(10011･11001)|10011> + 
  (-1)(10100･11001)|10100> + 
  (-1)(10101･11001)|10101> + 
  (-1)(10110･11001)|10110> + 
  (-1)(10111･11001)|10111> + 
  (-1)(11000･11001)|11000> + 
  (-1)(11001･11001)|11001> + 
  (-1)(11010･11001)|11010> + 
  (-1)(11011･11001)|11011> + 
  (-1)(11100･11001)|11100> + 
  (-1)(11101･11001)|11101> + 
  (-1)(11110･11001)|11110> + 
  (-1)(11111･11001)|11111>
}

↓↓↓

1 / √32 * {
  (+ |00000>) + 
  (- |00001>) + 
  (+ |00010>) + 
  (- |00011>) + 
  (+ |00100>) + 
  (- |00101>) + 
  (+ |00110>) + 
  (- |00111>) + 
  (- |01000>) + 
  (+ |01001>) + 
  (- |01010>) + 
  (+ |01011>) + 
  (- |01100>) + 
  (+ |01101>) + 
  (- |01110>) + 
  (+ |01111>) + 
  (- |10000>) + 
  (+ |10001>) + 
  (- |10010>) + 
  (+ |10011>) + 
  (- |10100>) + 
  (+ |10101>) + 
  (- |10110>) + 
  (+ |10111>) + 
  (+ |11000>) + 
  (- |11001>) + 
  (+ |11010>) + 
  (- |11011>) + 
  (+ |11100>) + 
  (- |11101>) + 
  (+ |11110>) + 
  (- |11111>)
}

↓↓↓

1 / √32 * (+ |00000> - |00001> + |00010> - |00011> + |00100> - |00101> + |00110> - |00111> - |01000> + |01001> - |01010> + |01011> - |01100> + |01101> - |01110> + |01111> - |10000> + |10001> - |10010> + |10011> - |10100> + |10101> - |10110> + |10111> + |11000> - |11001> + |11010> - |11011> + |11100> - |11101> + |11110> - |11111>)

例)
11011･11001
= (左から, 1bit目どうしの積) + ... + (左から, 5bit目どうしの積) (modulo 2)
= 1 * 1 + 1 * 1 + 0 * 0 + 1 * 0 + 1 * 1 (modulo 2)
= 1 + 1 + 0 + 0 + 1 (modulo 2)
= 3 (modulo 2)
= 1 (modulo 2)
→ (-1) が 1個なので, -1 と 解釈.

01001･11001
= (左から, 1bit目どうしの積) + ... + (左から, 5bit目どうしの積) (modulo 2)
= 0 * 1 + 1 * 1 + 0 * 0 + 0 * 0 + 1 * 1 (modulo 2)
= 0 + 1 + 0 + 0 + 1 (modulo 2)
= 2 (modulo 2)
= 0 (modulo 2)
→ (-1) が 0個なので, +1 と 解釈.

※ 秘密の文字列 "10011" を反転し, "11001" と読み替えて, 計算する必要があるように見える.

1 / √32 * {

(-1)(00000･11001)|00000> +

(-1)(00001･11001)|00001> +

(-1)(00010･11001)|00010> +

(-1)(00011･11001)|00011> +

(-1)(00100･11001)|00100> +

(-1)(00101･11001)|00101> +

(-1)(00110･11001)|00110> +

(-1)(00111･11001)|00111> +

(-1)(01000･11001)|01000> +

(-1)(01001･11001)|01001> +

(-1)(01010･11001)|01010> +

(-1)(01011･11001)|01011> +

(-1)(01100･11001)|01100> +

(-1)(01101･11001)|01101> +

(-1)(01110･11001)|01110> +

(-1)(01111･11001)|01111> +

(-1)(10000･11001)|10000> +

(-1)(10001･11001)|10001> +

(-1)(10010･11001)|10010> +

(-1)(10011･11001)|10011> +

(-1)(10100･11001)|10100> +

(-1)(10101･11001)|10101> +

(-1)(10110･11001)|10110> +

(-1)(10111･11001)|10111> +

(-1)(11000･11001)|11000> +

(-1)(11001･11001)|11001> +

(-1)(11010･11001)|11010> +

(-1)(11011･11001)|11011> +

(-1)(11100･11001)|11100> +

(-1)(11101･11001)|11101> +

(-1)(11110･11001)|11110> +

(-1)(11111･11001)|11111>

}

↓↓↓

1 / √32 * {

(+ |00000>) +

(- |00001>) +

(+ |00010>) +

(- |00011>) +

(+ |00100>) +

(- |00101>) +

(+ |00110>) +

(- |00111>) +

(- |01000>) +

(+ |01001>) +

(- |01010>) +

(+ |01011>) +

(- |01100>) +

(+ |01101>) +

(- |01110>) +

(+ |01111>) +

(- |10000>) +

(+ |10001>) +

(- |10010>) +

(+ |10011>) +

(- |10100>) +

(+ |10101>) +

(- |10110>) +

(+ |10111>) +

(+ |11000>) +

(- |11001>) +

(+ |11010>) +

(- |11011>) +

(+ |11100>) +

(- |11101>) +

(+ |11110>) +

(- |11111>)

}

↓↓↓

1 / √32 * (+ |00000> - |00001> + |00010> - |00011> + |00100> - |00101> + |00110> - |00111> - |01000> + |01001> - |01010> + |01011> - |01100> + |01101> - |01110> + |01111> - |10000> + |10001> - |10010> + |10011> - |10100> + |10101> - |10110> + |10111> + |11000> - |11001> + |11010> - |11011> + |11100> - |11101> + |11110> - |11111>)

例)

11011･11001

= (左から, 1bit目どうしの積) + ... + (左から, 5bit目どうしの積) (modulo 2)

= 1 * 1 + 1 * 1 + 0 * 0 + 1 * 0 + 1 * 1 (modulo 2)

= 1 + 1 + 0 + 0 + 1 (modulo 2)

= 3 (modulo 2)

= 1 (modulo 2)

→ (-1) が 1個なので, -1 と解釈.

01001･11001

= (左から, 1bit目どうしの積) + ... + (左から, 5bit目どうしの積) (modulo 2)

= 0 * 1 + 1 * 1 + 0 * 0 + 0 * 0 + 1 * 1 (modulo 2)

= 0 + 1 + 0 + 0 + 1 (modulo 2)

= 2 (modulo 2)

= 0 (modulo 2)

→ (-1) が 0個なので, +1 と解釈.

[結果]
手計算との一致を確認できた.

量子オラクル(6量子ビット “010110”)

[手計算]

※ 秘密の文字列 "010110" を 反転し, "011010" と読み替えて, 計算する必要があるように見える.

1 / √64 * {
  (-1)(000000･011010)|000000> + 
  (-1)(000001･011010)|000001> + 
  (-1)(000010･011010)|000010> + 
  (-1)(000011･011010)|000011> + 
  (-1)(000100･011010)|000100> + 
  (-1)(000101･011010)|000101> + 
  (-1)(000110･011010)|000110> + 
  (-1)(000111･011010)|000111> + 
  (-1)(001000･011010)|001000> + 
  (-1)(001001･011010)|001001> + 
  (-1)(001010･011010)|001010> + 
  (-1)(001011･011010)|001011> + 
  (-1)(001100･011010)|001100> + 
  (-1)(001101･011010)|001101> + 
  (-1)(001110･011010)|001110> + 
  (-1)(001111･011010)|001111> + 
  (-1)(010000･011010)|010000> + 
  (-1)(010001･011010)|010001> + 
  (-1)(010010･011010)|010010> + 
  (-1)(010011･011010)|010011> + 
  (-1)(010100･011010)|010100> + 
  (-1)(010101･011010)|010101> + 
  (-1)(010110･011010)|010110> + 
  (-1)(010111･011010)|010111> + 
  (-1)(011000･011010)|011000> + 
  (-1)(011001･011010)|011001> + 
  (-1)(011010･011010)|011010> + 
  (-1)(011011･011010)|011011> + 
  (-1)(011100･011010)|011100> + 
  (-1)(011101･011010)|011101> + 
  (-1)(011110･011010)|011110> + 
  (-1)(011111･011010)|011111> + 
  (-1)(100000･011010)|100000> + 
  (-1)(100001･011010)|100001> + 
  (-1)(100010･011010)|100010> + 
  (-1)(100011･011010)|100011> + 
  (-1)(100100･011010)|100100> + 
  (-1)(100101･011010)|100101> + 
  (-1)(100110･011010)|100110> + 
  (-1)(100111･011010)|100111> + 
  (-1)(101000･011010)|101000> + 
  (-1)(101001･011010)|101001> + 
  (-1)(101010･011010)|101010> + 
  (-1)(101011･011010)|101011> + 
  (-1)(101100･011010)|101100> + 
  (-1)(101101･011010)|101101> + 
  (-1)(101110･011010)|101110> + 
  (-1)(101111･011010)|101111> + 
  (-1)(110000･011010)|110000> + 
  (-1)(110001･011010)|110001> + 
  (-1)(110010･011010)|110010> + 
  (-1)(110011･011010)|110011> + 
  (-1)(110100･011010)|110100> + 
  (-1)(110101･011010)|110101> + 
  (-1)(110110･011010)|110110> + 
  (-1)(110111･011010)|110111> + 
  (-1)(111000･011010)|111000> + 
  (-1)(111001･011010)|111001> + 
  (-1)(111010･011010)|111010> + 
  (-1)(111011･011010)|111011> + 
  (-1)(111100･011010)|111100> + 
  (-1)(111101･011010)|111101> + 
  (-1)(111110･011010)|111110> + 
  (-1)(111111･011010)|111111>
}

↓↓↓

1 / √64 * {
  (+ |000000>) + 
  (+ |000001>) + 
  (- |000010>) + 
  (- |000011>) + 
  (+ |000100>) + 
  (+ |000101>) + 
  (- |000110>) + 
  (- |000111>) + 
  (- |001000>) + 
  (- |001001>) + 
  (+ |001010>) + 
  (+ |001011>) + 
  (- |001100>) + 
  (- |001101>) + 
  (+ |001110>) + 
  (+ |001111>) + 
  (- |010000>) + 
  (- |010001>) + 
  (+ |010010>) + 
  (+ |010011>) + 
  (- |010100>) + 
  (- |010101>) + 
  (+ |010110>) + 
  (+ |010111>) + 
  (+ |011000>) + 
  (+ |011001>) + 
  (- |011010>) + 
  (- |011011>) + 
  (+ |011100>) + 
  (+ |011101>) + 
  (- |011110>) + 
  (- |011111>) + 
  (+ |100000>) + 
  (+ |100001>) + 
  (- |100010>) + 
  (- |100011>) + 
  (+ |100100>) + 
  (+ |100101>) + 
  (- |100110>) + 
  (- |100111>) + 
  (- |101000>) + 
  (- |101001>) + 
  (+ |101010>) + 
  (+ |101011>) + 
  (- |101100>) + 
  (- |101101>) + 
  (+ |101110>) + 
  (+ |101111>) + 
  (- |110000>) + 
  (- |110001>) + 
  (+ |110010>) + 
  (+ |110011>) + 
  (- |110100>) + 
  (- |110101>) + 
  (+ |110110>) + 
  (+ |110111>) + 
  (+ |111000>) + 
  (+ |111001>) + 
  (- |111010>) + 
  (- |111011>) + 
  (+ |111100>) + 
  (+ |111101>) + 
  (- |111110>) + 
  (- |111111>)
}

↓↓↓

1 / √64 * (+ |000000> + |000001> - |000010> - |000011> + |000100> + |000101> - |000110> - |000111> - |001000> - |001001> + |001010> + |001011> - |001100> - |001101> + |001110> + |001111> - |010000> - |010001> + |010010> + |010011> - |010100> - |010101> + |010110> + |010111> + |011000> + |011001> - |011010> - |011011> + |011100> + |011101> - |011110> - |011111> + |100000> + |100001> - |100010> - |100011> + |100100> + |100101> - |100110> - |100111> - |101000> - |101001> + |101010> + |101011> - |101100> - |101101> + |101110> + |101111> - |110000> - |110001> + |110010> + |110011> - |110100> - |110101> + |110110> + |110111> + |111000> + |111001> - |111010> - |111011> + |111100> + |111101> - |111110> - |111111>)

例)
011011･011010
= (左から, 1bit目どうしの積) + ... + (左から, 6bit目どうしの積) (modulo 2)
= 0 * 0 + 1 * 1 + 1 * 1 + 0 * 0 + 1 * 1 + 1 * 0 (modulo 2)
= 0 + 1 + 1 + 0 + 1 + 0 (modulo 2)
= 3 (modulo 2)
= 1 (modulo 2)
→ (-1) が 1個なので, -1 と 解釈.

011100･011010
= (左から, 1bit目どうしの積) + ... + (左から, 6bit目どうしの積) (modulo 2)
= 0 * 0 + 1 * 1 + 1 * 1 + 1 * 0 + 0 * 1 + 0 * 0 (modulo 2)
= 0 + 1 + 1 + 0 + 0 + 0 (modulo 2)
= 2 (modulo 2)
= 0 (modulo 2)
→ (-1) が 0個なので, +1 と 解釈.

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

※ 秘密の文字列 "010110" を反転し, "011010" と読み替えて, 計算する必要があるように見える.

1 / √64 * {

(-1)(000000･011010)|000000> +

(-1)(000001･011010)|000001> +

(-1)(000010･011010)|000010> +

(-1)(000011･011010)|000011> +

(-1)(000100･011010)|000100> +

(-1)(000101･011010)|000101> +

(-1)(000110･011010)|000110> +

(-1)(000111･011010)|000111> +

(-1)(001000･011010)|001000> +

(-1)(001001･011010)|001001> +

(-1)(001010･011010)|001010> +

(-1)(001011･011010)|001011> +

(-1)(001100･011010)|001100> +

(-1)(001101･011010)|001101> +

(-1)(001110･011010)|001110> +

(-1)(001111･011010)|001111> +

(-1)(010000･011010)|010000> +

(-1)(010001･011010)|010001> +

(-1)(010010･011010)|010010> +

(-1)(010011･011010)|010011> +

(-1)(010100･011010)|010100> +

(-1)(010101･011010)|010101> +

(-1)(010110･011010)|010110> +

(-1)(010111･011010)|010111> +

(-1)(011000･011010)|011000> +

(-1)(011001･011010)|011001> +

(-1)(011010･011010)|011010> +

(-1)(011011･011010)|011011> +

(-1)(011100･011010)|011100> +

(-1)(011101･011010)|011101> +

(-1)(011110･011010)|011110> +

(-1)(011111･011010)|011111> +

(-1)(100000･011010)|100000> +

(-1)(100001･011010)|100001> +

(-1)(100010･011010)|100010> +

(-1)(100011･011010)|100011> +

(-1)(100100･011010)|100100> +

(-1)(100101･011010)|100101> +

(-1)(100110･011010)|100110> +

(-1)(100111･011010)|100111> +

(-1)(101000･011010)|101000> +

(-1)(101001･011010)|101001> +

(-1)(101010･011010)|101010> +

(-1)(101011･011010)|101011> +

(-1)(101100･011010)|101100> +

(-1)(101101･011010)|101101> +

(-1)(101110･011010)|101110> +

(-1)(101111･011010)|101111> +

(-1)(110000･011010)|110000> +

(-1)(110001･011010)|110001> +

(-1)(110010･011010)|110010> +

(-1)(110011･011010)|110011> +

(-1)(110100･011010)|110100> +

(-1)(110101･011010)|110101> +

(-1)(110110･011010)|110110> +

(-1)(110111･011010)|110111> +

(-1)(111000･011010)|111000> +

(-1)(111001･011010)|111001> +

(-1)(111010･011010)|111010> +

(-1)(111011･011010)|111011> +

(-1)(111100･011010)|111100> +

(-1)(111101･011010)|111101> +

(-1)(111110･011010)|111110> +

(-1)(111111･011010)|111111>

}

↓↓↓

1 / √64 * {

(+ |000000>) +

(+ |000001>) +

(- |000010>) +

(- |000011>) +

(+ |000100>) +

(+ |000101>) +

(- |000110>) +

(- |000111>) +

(- |001000>) +

(- |001001>) +

(+ |001010>) +

(+ |001011>) +

(- |001100>) +

(- |001101>) +

(+ |001110>) +

(+ |001111>) +

(- |010000>) +

(- |010001>) +

(+ |010010>) +

(+ |010011>) +

(- |010100>) +

(- |010101>) +

(+ |010110>) +

(+ |010111>) +

(+ |011000>) +

(+ |011001>) +

(- |011010>) +

(- |011011>) +

(+ |011100>) +

(+ |011101>) +

(- |011110>) +

(- |011111>) +

(+ |100000>) +

(+ |100001>) +

(- |100010>) +

(- |100011>) +

(+ |100100>) +

(+ |100101>) +

(- |100110>) +

(- |100111>) +

(- |101000>) +

(- |101001>) +

(+ |101010>) +

(+ |101011>) +

(- |101100>) +

(- |101101>) +

(+ |101110>) +

(+ |101111>) +

(- |110000>) +

(- |110001>) +

(+ |110010>) +

(+ |110011>) +

(- |110100>) +

(- |110101>) +

(+ |110110>) +

(+ |110111>) +

(+ |111000>) +

(+ |111001>) +

(- |111010>) +

(- |111011>) +

(+ |111100>) +

(+ |111101>) +

(- |111110>) +

(- |111111>)

}

↓↓↓

1 / √64 * (+ |000000> + |000001> - |000010> - |000011> + |000100> + |000101> - |000110> - |000111> - |001000> - |001001> + |001010> + |001011> - |001100> - |001101> + |001110> + |001111> - |010000> - |010001> + |010010> + |010011> - |010100> - |010101> + |010110> + |010111> + |011000> + |011001> - |011010> - |011011> + |011100> + |011101> - |011110> - |011111> + |100000> + |100001> - |100010> - |100011> + |100100> + |100101> - |100110> - |100111> - |101000> - |101001> + |101010> + |101011> - |101100> - |101101> + |101110> + |101111> - |110000> - |110001> + |110010> + |110011> - |110100> - |110101> + |110110> + |110111> + |111000> + |111001> - |111010> - |111011> + |111100> + |111101> - |111110> - |111111>)

例)

011011･011010

= (左から, 1bit目どうしの積) + ... + (左から, 6bit目どうしの積) (modulo 2)

= 0 * 0 + 1 * 1 + 1 * 1 + 0 * 0 + 1 * 1 + 1 * 0 (modulo 2)

= 0 + 1 + 1 + 0 + 1 + 0 (modulo 2)

= 3 (modulo 2)

= 1 (modulo 2)

→ (-1) が 1個なので, -1 と解釈.

011100･011010

= (左から, 1bit目どうしの積) + ... + (左から, 6bit目どうしの積) (modulo 2)

= 0 * 0 + 1 * 1 + 1 * 1 + 1 * 0 + 0 * 1 + 0 * 0 (modulo 2)

= 0 + 1 + 1 + 0 + 0 + 0 (modulo 2)

= 2 (modulo 2)

= 0 (modulo 2)

→ (-1) が 0個なので, +1 と解釈.

[結果]
手計算との一致を確認できた.

(参考)量子オラクル(10量子ビット “1110110101”)

[結果]
エラー出力された.

(参考)シミュレーターでの実験

公式サイトでは, 秘密の文字列 “011” で, シミュレーターによる実験を見ることが出来る.
⇒ プログラム中に, 以下の実装箇所があるが, これをコメントアウト(秘密の文字列の反転を行わない)して, 結果を確認してみる.

～ (略) ～
s = s[::-1] # reverse s to fit qiskit's qubit ordering
～ (略) ～

～ (略) ～

s = s[::-1] # reverse s to fit qiskit's qubit ordering

～ (略) ～

[結果]
シミュレーターの結果が, 秘密の文字列 “110” で, 出力されることを確認できた.

参照サイト

ベルンシュタイン・ヴァジラニアルゴリズム

2022年2月13日2022年2月13日

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

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

■感想.
1. 問題Eは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 解説にある通り, X, Y方向で, 独立に数え上げできるという部分が, 面白く感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/abc127/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;
const int LIMIT = 202020;
LL FAC[LIMIT], INV[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 0LL;
    if(n == k || k == 0LL) return 1LL;
    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);
    
    // 2. 事前計算.
    FAC[0] = 1;
    repx(i, 1, LIMIT) FAC[i] = (LL)i * FAC[i - 1] % MOD;
    rep(i, LIMIT)     INV[i] = mPow(FAC[i], MOD - 2);
    
    // 3. 各座標ごとの差の絶対値の和.
    // -> 2マスを, 固定で選んだ場合の数, 差の絶対値 d を 乗ずることを忘れないこと!
    // 3-1. X方向.
    LL x = 0;
    repx(d, 1, N){
        x += (LL)(N - d) * (LL)M % MOD * (LL)M % MOD * (LL)d % MOD;
        x %= MOD;
    }
    
    // 3-2. Y方向.
    LL y = 0;
    repx(d, 1, M){
        y += (LL)(M - d) * (LL)N % MOD * (LL)N % MOD * (LL)d % MOD;
        y %= MOD;
    }
    
    // 4. (K - 2)マス選ぶ場合の数.
    // -> 固定で選んだ 2マス以外のマスの選び方(解説より).
    LL k2 = combination((LL)(N * M - 2), (LL)(K - 2));
    
    // 5. 集計.
    // -> X, Y方向は, 独立と考えて良いとのこと(解説より).
    LL ans = (x + y) % MOD * k2 % MOD;
    
    // 6. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://img.atcoder.jp/abc127/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;

const int LIMIT = 202020;

LL FAC[LIMIT], INV[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 0LL;

if(n == k || k == 0LL) return 1LL;

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

// 2. 事前計算.

FAC[0] = 1;

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

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

// 3. 各座標ごとの差の絶対値の和.

// -> 2マスを, 固定で選んだ場合の数, 差の絶対値 d を乗ずることを忘れないこと!

// 3-1. X方向.

LL x = 0;

repx(d, 1, N){

x += (LL)(N - d) * (LL)M % MOD * (LL)M % MOD * (LL)d % MOD;

x %= MOD;

}

// 3-2. Y方向.

LL y = 0;

repx(d, 1, M){

y += (LL)(M - d) * (LL)N % MOD * (LL)N % MOD * (LL)d % MOD;

y %= MOD;

}

// 4. (K - 2)マス選ぶ場合の数.

// -> 固定で選んだ 2マス以外のマスの選び方(解説より).

LL k2 = combination((LL)(N * M - 2), (LL)(K - 2));

// 5. 集計.

// -> X, Y方向は, 独立と考えて良いとのこと(解説より).

LL ans = (x + y) % MOD * k2 % MOD;

// 6. 出力.

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

return 0;

}

[入力例]
2 2 2

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

[入力例]
4 5 4

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

[入力例]
100 100 5000

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

[入力例]
3 4 5

[出力例]
18480

[入力例]
7 8 3

[出力例]
415800

[入力例]
202 203 12345

[出力例]
906503729

[入力例]

2 2 2

[出力例]

※AtCoderテストケースより

[入力例]

4 5 4

[出力例]

87210

※AtCoderテストケースより

[入力例]

100 100 5000

[出力例]

817260251

※AtCoderテストケースより

[入力例]

3 4 5

[出力例]

18480

[入力例]

7 8 3

[出力例]

415800

[入力例]

202 203 12345

[出力例]

906503729

■参照サイト
AtCoder Beginner Contest 127

2022年2月12日2022年2月13日

Python（Qiskit）について（１９）

概要

Qiskit について, 学習サイトのサンプルプログラムを動かしてみた.
動作環境は, 学習サイト上で行った
実行プログラム, 解説は, 下記の参照サイトをご覧ください

感想

ベルンシュタイン・ヴァジラニアルゴリズムの演算方法で, 量子オラクルについて確認してみた.
既に, 学習環境が用意されており, 数値を書き換えるなどして試行錯誤もできるので, 個人的には, 非常に面白く感じた.

ベルンシュタイン・ヴァジラニアルゴリズム

量子オラクル(1量子ビット “1”)

[手計算]

1 / √2 * {
  (-1)(0･1)|0> + 
  (-1)(1･1)|1> + 

↓↓↓

1 / √2 * {
  (+ |0>) + 
  (- |1>)
}

↓↓↓

1 / √2 * (+ |0> - |1>)

例)
0･1 
= (左から, 1bit目どうしの積)
= 0 * 1
= 0 (modulo 2)
→ (-1) が 0個なので, +1 と 解釈.

1 / √2 * {

(-1)(0･1)|0> +

(-1)(1･1)|1> +

↓↓↓

1 / √2 * {

(+ |0>) +

(- |1>)

}

↓↓↓

1 / √2 * (+ |0> - |1>)

例)

0･1

= (左から, 1bit目どうしの積)

= 0 * 1

= 0 (modulo 2)

→ (-1) が 0個なので, +1 と解釈.

[結果]
手計算との一致を確認できた.

量子オラクル(2量子ビット “01”)

[手計算]

※ 秘密の文字列 "01" を 反転し, "10" と読み替えて, 計算する必要があるように見える.

1 / √4 * {
  (-1)(00･10)|00> + 
  (-1)(01･10)|01> + 
  (-1)(10･10)|10> + 
  (-1)(11･10)|11> + 
}

↓↓↓

1 / √4 * {
  (+ |00>) + 
  (+ |01>) + 
  (- |10>) + 
  (- |11>) + 
}

↓↓↓

1 / √4 * (+ |00> + |01> - |10> - |11>)

例)
01･10 
= (左から, 1bit目どうしの積) + (左から, 2bit目どうしの積) (modulo 2)
= 0 * 1 + 1 * 0 (modulo 2)
= 0 + 0 (modulo 2)
= 0 (modulo 2)
→ (-1) が 0個なので, +1 と 解釈.

11･10
= (左から, 1bit目どうしの積) + (左から, 2bit目どうしの積) (modulo 2)
= 1 * 1 + 1 * 0 (modulo 2)
= 1 + 0 (modulo 2)
= 1 (modulo 2)
→ (-1) が 1個なので, -1 と 解釈.

※ 秘密の文字列 "01" を反転し, "10" と読み替えて, 計算する必要があるように見える.

1 / √4 * {

(-1)(00･10)|00> +

(-1)(01･10)|01> +

(-1)(10･10)|10> +

(-1)(11･10)|11> +

}

↓↓↓

1 / √4 * {

(+ |00>) +

(+ |01>) +

(- |10>) +

(- |11>) +

}

↓↓↓

1 / √4 * (+ |00> + |01> - |10> - |11>)

例)

01･10

= (左から, 1bit目どうしの積) + (左から, 2bit目どうしの積) (modulo 2)

= 0 * 1 + 1 * 0 (modulo 2)

= 0 + 0 (modulo 2)

= 0 (modulo 2)

→ (-1) が 0個なので, +1 と解釈.

11･10

= (左から, 1bit目どうしの積) + (左から, 2bit目どうしの積) (modulo 2)

= 1 * 1 + 1 * 0 (modulo 2)

= 1 + 0 (modulo 2)

= 1 (modulo 2)

→ (-1) が 1個なので, -1 と解釈.

[結果]
手計算との一致を確認できた.

量子オラクル(3量子ビット “110”)

[手計算]

※ 秘密の文字列 "110" を 反転し, "011" と読み替えて, 計算する必要があるように見える.

1 / √8 * {
  (-1)(000･011)|000> + 
  (-1)(001･011)|001> + 
  (-1)(010･011)|010> + 
  (-1)(011･011)|011> + 
  (-1)(100･011)|100> + 
  (-1)(101･011)|101> + 
  (-1)(110･011)|110> + 
  (-1)(111･011)|111>
}

↓↓↓

1 / √8 * {
  (+ |000>) + 
  (- |001>) + 
  (- |010>) + 
  (+ |011>) + 
  (+ |100>) + 
  (- |101>) + 
  (- |110>) + 
  (+ |111>)
}

↓↓↓

1 / √8 * (+ |000> - |001> - |010> + |011> + |100> - |101> - |110> + |111>)

例)
010･011 
= (左から, 1bit目どうしの積) + (左から, 2bit目どうしの積) + (左から, 3bit目どうしの積) (modulo 2)
= 0 * 0 + 1 * 1 + 0 * 1 (modulo 2)
= 0 + 1 + 0 (modulo 2)
= 1 (modulo 2)
→ (-1) が 1個なので, -1 と 解釈.

100･011
= (左から, 1bit目どうしの積) + (左から, 2bit目どうしの積) + (左から, 3bit目どうしの積) (modulo 2)
= 1 * 0 + 0 * 1 + 0 * 1 (modulo 2)
= 0 + 0 + 0 (modulo 2)
= 0 (modulo 2)
→ (-1) が 0個なので, +1 と 解釈.

※ 秘密の文字列 "110" を反転し, "011" と読み替えて, 計算する必要があるように見える.

1 / √8 * {

(-1)(000･011)|000> +

(-1)(001･011)|001> +

(-1)(010･011)|010> +

(-1)(011･011)|011> +

(-1)(100･011)|100> +

(-1)(101･011)|101> +

(-1)(110･011)|110> +

(-1)(111･011)|111>

}

↓↓↓

1 / √8 * {

(+ |000>) +

(- |001>) +

(- |010>) +

(+ |011>) +

(+ |100>) +

(- |101>) +

(- |110>) +

(+ |111>)

}

↓↓↓

1 / √8 * (+ |000> - |001> - |010> + |011> + |100> - |101> - |110> + |111>)

例)

010･011

= (左から, 1bit目どうしの積) + (左から, 2bit目どうしの積) + (左から, 3bit目どうしの積) (modulo 2)

= 0 * 0 + 1 * 1 + 0 * 1 (modulo 2)

= 0 + 1 + 0 (modulo 2)

= 1 (modulo 2)

→ (-1) が 1個なので, -1 と解釈.

100･011

= (左から, 1bit目どうしの積) + (左から, 2bit目どうしの積) + (左から, 3bit目どうしの積) (modulo 2)

= 1 * 0 + 0 * 1 + 0 * 1 (modulo 2)

= 0 + 0 + 0 (modulo 2)

= 0 (modulo 2)

→ (-1) が 0個なので, +1 と解釈.

[結果]
手計算との一致を確認できた.

量子オラクル(4量子ビット “1011”)

[手計算]

※ 秘密の文字列 "1011" を 反転し, "1101" と読み替えて, 計算する必要があるように見える.

1 / √16 * {
  (-1)(0000･1101)|0000> + 
  (-1)(0001･1101)|0001> + 
  (-1)(0010･1101)|0010> + 
  (-1)(0011･1101)|0011> + 
  (-1)(0100･1101)|0100> + 
  (-1)(0101･1101)|0101> + 
  (-1)(0110･1101)|0110> + 
  (-1)(0111･1101)|0111> + 
  (-1)(1000･1101)|1000> + 
  (-1)(1001･1101)|1001> + 
  (-1)(1010･1101)|1010> + 
  (-1)(1011･1101)|1011> + 
  (-1)(1100･1101)|1100> + 
  (-1)(1101･1101)|1101> + 
  (-1)(1110･1101)|1110> + 
  (-1)(1111･1101)|1111>
}

↓↓↓

1 / √16 * {
  (+ |0000>) + 
  (- |0001>) + 
  (+ |0010>) + 
  (- |0011>) + 
  (- |0100>) + 
  (+ |0101>) + 
  (- |0110>) + 
  (+ |0111>) + 
  (- |1000>) + 
  (+ |1001>) + 
  (- |1010>) + 
  (+ |1011>) + 
  (+ |1100>) + 
  (- |1101>) + 
  (+ |1110>) + 
  (- |1111>)
}

↓↓↓

1 / √16 * (+ |0000> - |0001> + |0010> - |0011> - |0100> + |0101> - |0110> + |0111> - |1000> + |1001> - |1010> + |1011> + |1100> - |1101> + |1110> - |1111>)

例)
0111･1101 
= (左から, 1bit目どうしの積) + (左から, 2bit目どうしの積) + (左から, 3bit目どうしの積) + (左から, 4bit目どうしの積) (modulo 2)
= 0 * 1 + 1 * 1 + 1 * 0 + 1 * 1 (modulo 2)
= 0 + 1 + 0 + 1 (modulo 2)
= 2 (modulo 2)
= 0 (modulo 2)
→ (-1) が 0個なので, +1 と 解釈.

1101･1101
= (左から, 1bit目どうしの積) + (左から, 2bit目どうしの積) + (左から, 3bit目どうしの積) + (左から, 4bit目どうしの積) (modulo 2)
= 1 * 1 + 1 * 1 + 0 * 0 + 1 * 1 (modulo 2)
= 1 + 1 + 0 + 1 (modulo 2)
= 3 (modulo 2)
= 1 (modulo 2)
→ (-1) が 1個なので, -1 と 解釈.

※ 秘密の文字列 "1011" を反転し, "1101" と読み替えて, 計算する必要があるように見える.

1 / √16 * {

(-1)(0000･1101)|0000> +

(-1)(0001･1101)|0001> +

(-1)(0010･1101)|0010> +

(-1)(0011･1101)|0011> +

(-1)(0100･1101)|0100> +

(-1)(0101･1101)|0101> +

(-1)(0110･1101)|0110> +

(-1)(0111･1101)|0111> +

(-1)(1000･1101)|1000> +

(-1)(1001･1101)|1001> +

(-1)(1010･1101)|1010> +

(-1)(1011･1101)|1011> +

(-1)(1100･1101)|1100> +

(-1)(1101･1101)|1101> +

(-1)(1110･1101)|1110> +

(-1)(1111･1101)|1111>

}

↓↓↓

1 / √16 * {

(+ |0000>) +

(- |0001>) +

(+ |0010>) +

(- |0011>) +

(- |0100>) +

(+ |0101>) +

(- |0110>) +

(+ |0111>) +

(- |1000>) +

(+ |1001>) +

(- |1010>) +

(+ |1011>) +

(+ |1100>) +

(- |1101>) +

(+ |1110>) +

(- |1111>)

}

↓↓↓

1 / √16 * (+ |0000> - |0001> + |0010> - |0011> - |0100> + |0101> - |0110> + |0111> - |1000> + |1001> - |1010> + |1011> + |1100> - |1101> + |1110> - |1111>)

例)

0111･1101

= (左から, 1bit目どうしの積) + (左から, 2bit目どうしの積) + (左から, 3bit目どうしの積) + (左から, 4bit目どうしの積) (modulo 2)

= 0 * 1 + 1 * 1 + 1 * 0 + 1 * 1 (modulo 2)

= 0 + 1 + 0 + 1 (modulo 2)

= 2 (modulo 2)

= 0 (modulo 2)

→ (-1) が 0個なので, +1 と解釈.

1101･1101

= (左から, 1bit目どうしの積) + (左から, 2bit目どうしの積) + (左から, 3bit目どうしの積) + (左から, 4bit目どうしの積) (modulo 2)

= 1 * 1 + 1 * 1 + 0 * 0 + 1 * 1 (modulo 2)

= 1 + 1 + 0 + 1 (modulo 2)

= 3 (modulo 2)

= 1 (modulo 2)

→ (-1) が 1個なので, -1 と解釈.

[結果]
手計算との一致を確認できた.

参照サイト

ベルンシュタイン・ヴァジラニアルゴリズム

2022年2月11日

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

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

■感想.
1. 問題Fは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 苦手な動的計画法の訓練を積めたので, 非常に良かったと思う.
3. 個人的には, 数え上げする種類数が, アルファベットの出現数にのみ依存するという部分が, 不思議な印象を受けた.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/abc234/editorial/3223
// 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;
LL C[5050][5050], dp[27][5050];
int freq[26];

int main(){
    
    // 1. 入力情報.
    char s[5050];
    scanf("%s", s);
    string S(s);
    int N = S.size();
    
    // 2. 出現数('a' ～ 'z').
    rep(i, N) rep(j, 26) freq[j] = freq[j] + (S[i] == ('a' + j));
    
    // 3. パスカルの三角形.
    C[0][0] = 1;
    repx(i, 1, 5050){
        rep(j, 5050){
            C[i][j] = (!j || j == i) ? 1LL : C[i - 1][j - 1] + C[i - 1][j];
            C[i][j] %= MOD;
        }
    }
    
    // 4. dp更新(index注意, j は 0 ～ N までの範囲を動くとのこと).
    dp[0][0] = 1;
    rep(i, 26){
        rep(j, N + 1){
            rep(k, min(j, freq[i]) + 1){
                dp[i + 1][j] += dp[i][j - k] * C[j][k];
                dp[i + 1][j] %= MOD;
            }
        }
    }
    
    // 5. 集計.
    LL ans = 0;
    repx(j, 1, N + 1) ans += dp[26][j], ans %= MOD;
    
    // 6. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc234/editorial/3223

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

LL C[5050][5050], dp[27][5050];

int freq[26];

int main(){

// 1. 入力情報.

char s[5050];

scanf("%s", s);

string S(s);

int N = S.size();

// 2. 出現数('a' ～ 'z').

rep(i, N) rep(j, 26) freq[j] = freq[j] + (S[i] == ('a' + j));

// 3. パスカルの三角形.

C[0][0] = 1;

repx(i, 1, 5050){

rep(j, 5050){

C[i][j] = (!j || j == i) ? 1LL : C[i - 1][j - 1] + C[i - 1][j];

C[i][j] %= MOD;

}

// 4. dp更新(index注意, j は 0 ～ N までの範囲を動くとのこと).

dp[0][0] = 1;

rep(i, 26){

rep(j, N + 1){

rep(k, min(j, freq[i]) + 1){

dp[i + 1][j] += dp[i][j - k] * C[j][k];

dp[i + 1][j] %= MOD;

}

// 5. 集計.

LL ans = 0;

repx(j, 1, N + 1) ans += dp[26][j], ans %= MOD;

// 6. 出力.

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

return 0;

}

[入力例]
aab

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

[入力例]
aaa

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

[入力例]
abcdefghijklmnopqrstuvwxyz

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

[入力例]
abc

[出力例]
15

[入力例]
abracadabra

[出力例]
257589

[入力例]
jugemujugemugokonosurikirekaijarisuigyonosuigyomatsuunraimatsufuraimatsukunerutokoronisumutokoroyaburakojinoburakojipaipopaipopaiponoshuringanshuringannogurindaigurindainopompokopinopompokonanochokyumeinochosukezyugemuzyugemugokonosurikirekaizyarisuigyonosuigyomatuunraimatuhuraimatukuunerutokoronisumutokorol
magicalspell

[出力例]
985106188

[入力例]

aab

[出力例]

※AtCoderテストケースより

[入力例]

aaa

[出力例]

※AtCoderテストケースより

[入力例]

abcdefghijklmnopqrstuvwxyz

[出力例]

149621752

※AtCoderテストケースより

[入力例]

abc

[出力例]

[入力例]

abracadabra

[出力例]

257589

[入力例]

jugemujugemugokonosurikirekaijarisuigyonosuigyomatsuunraimatsufuraimatsukunerutokoronisumutokoroyaburakojinoburakojipaipopaipopaiponoshuringanshuringannogurindaigurindainopompokopinopompokonanochokyumeinochosukezyugemuzyugemugokonosurikirekaizyarisuigyonosuigyomatuunraimatuhuraimatukuunerutokoronisumutokorol

magicalspell

[出力例]

985106188

■参照サイト
AtCoder Beginner Contest 234

2022年2月11日

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

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

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

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

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

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

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

vector<edge> G[202020];
LL h[202020];

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    rep(i, N) scanf("%lld", &h[i]);
    rep(i, M){
        int u, v;
        scanf("%d %d", &u, &v);
        u--;
        v--;
        
        // 辺のコストは, 広場間の標高差の絶対値(解説通り).
        G[u].pb(edge{v, abs(h[v] - h[u])});
        G[v].pb(edge{u, abs(h[v] - h[u])});
    }
    
    // 2. ダイクストラ法.
    // https://ja.wikipedia.org/wiki/ダイクストラ法
    auto dijkstra = [&](int s, LL* d, int* memo){
        // 2-1. 初期化.
        priority_queue<edge> pq;
        
        // 2-2. 始点設定.
        d[s] = 0;
        pq.push({s, 0LL});
        
        // 2-3. キュー pq が 空になるまで, 探索.
        while(!pq.empty()){
            // 2-4. 探索を継続するために, 頂点を取得.
            edge e = pq.top();
            pq.pop();
            int cn = e.n;
            LL cc = e.c;
            
            // 2-5. 訪問済みフラグ設定.
            if(memo[cn]) continue;
            memo[cn]++;
            
            // 2-6. 各隣接する頂点について, 距離を確認し, 移動コストを更新.
            for(auto &g : G[cn]){
                // 移動コスト更新.
                int nn = g.n;
                LL nc = cc + g.c;
                if(d[nn] > nc) d[nn] = nc, pq.push({nn, nc});
            }
        }
    };
    
    // 3. 各広場までの, 最小コスト.
    LL d[N];
    int memo[N];
    rep(i, N) d[i] = INF, memo[i] = 0;
    dijkstra(0, d, memo);
    
    // 4. 楽しさの最大値は？
    // -> 数式計算で取得した値と比較(解説通り).
    //    解説上 の d[i], H[i] - H[1] は, 偶奇が一致するので, 展開した式は, 2 で 割り切れるはず.
    LL ans = 0;
    rep(i, N) ans = max(ans, (- d[i] - 3 * h[i] + 3 * h[0])/ 2);
    
    // 5. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc237/editorial/3346

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

#define pb push_back

const LL INF = 202020202020202020;

struct edge{

int n; // 次の頂点.

LL c; // コスト.

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

};

vector<edge> G[202020];

LL h[202020];

int main(){

// 1. 入力情報.

int N, M;

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

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

rep(i, M){

int u, v;

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

u--;

v--;

// 辺のコストは, 広場間の標高差の絶対値(解説通り).

G[u].pb(edge{v, abs(h[v] - h[u])});

G[v].pb(edge{u, abs(h[v] - h[u])});

}

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

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

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

// 2-1. 初期化.

priority_queue<edge> pq;

// 2-2. 始点設定.

d[s] = 0;

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

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

while(!pq.empty()){

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

edge e = pq.top();

pq.pop();

int cn = e.n;

LL cc = e.c;

// 2-5. 訪問済みフラグ設定.

if(memo[cn]) continue;

memo[cn]++;

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

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

// 移動コスト更新.

int nn = g.n;

LL nc = cc + g.c;

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

}

};

// 3. 各広場までの, 最小コスト.

LL d[N];

int memo[N];

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

dijkstra(0, d, memo);

// 4. 楽しさの最大値は？

// -> 数式計算で取得した値と比較(解説通り).

// 解説上の d[i], H[i] - H[1] は, 偶奇が一致するので, 展開した式は, 2 で割り切れるはず.

LL ans = 0;

rep(i, N) ans = max(ans, (- d[i] - 3 * h[i] + 3 * h[0])/ 2);

// 5. 出力.

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

return 0;

}

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

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

[入力例]
2 1
0 10
1 2

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

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

[出力例]
5

[入力例]
10 16
314 159 265 358 979 323 846 264 338 327
1 2
1 3
2 4
2 5
3 5
3 6
4 8
4 9
5 7
5 8
6 7
6 10
7 8
7 10
8 9
9 10

[出力例]
155

[入力例]

4 4

10 8 12 5

1 2

1 3

2 3

3 4

[出力例]

※AtCoderテストケースより

[入力例]

2 1

0 10

1 2

[出力例]

※AtCoderテストケースより

[入力例]

5 7

12 7 13 10 8

1 2

1 4

1 5

2 3

2 4

2 5

3 5

[出力例]

[入力例]

10 16

314 159 265 358 979 323 846 264 338 327

1 2

1 3

2 4

2 5

3 5

3 6

4 8

4 9

5 7

5 8

6 7

6 10

7 8

7 10

8 9

9 10

[出力例]

155

■参照サイト
AtCoder Beginner Contest 237

2022年2月10日

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

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

■感想.
1. 問題Dは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 解説にあるロジック(投げ刀, 強い投げ刀, 振り刀に分けて考える)が, 非常に面白く感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

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

int main(){
    
    // 1. 入力情報.
    int N, H;
    scanf("%d %d", &N, &H);
    vp v;
    int a, b, maxA = 0;
    rep(i, N){
        scanf("%d %d", &a, &b);
        v.pb({a, 0}); // 振り刀.
        v.pb({b, 1}); // 投げ刀.
        maxA = max(maxA, a); // 攻撃力最大の振り刀.
    }
    
    // 2. sort.
    sort(all(v));
    reverse(all(v));
    
    // 3. 攻撃パターン 1.
    // 強い投げ刀を投げる.
    int ans = 0;
    rep(i, N * 2){
        if(H > 0 && v[i].b && v[i].a >= maxA){
            H -= v[i].a;
            ans++;
        }
    }
    
    // 4. 攻撃パターン 2.
    // 攻撃力最大の振り刀を振り続ける.
    if(H > 0) ans += (H + maxA - 1) / maxA;
    
    // 5. 出力.
    printf("%d\n", ans);
    return 0;
    
}

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using P = pair<int, int>;

using vp = vector<P>;

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

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

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

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

#define a first

#define b second

#define pb push_back

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

int main(){

// 1. 入力情報.

int N, H;

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

vp v;

int a, b, maxA = 0;

rep(i, N){

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

v.pb({a, 0}); // 振り刀.

v.pb({b, 1}); // 投げ刀.

maxA = max(maxA, a); // 攻撃力最大の振り刀.

}

// 2. sort.

sort(all(v));

reverse(all(v));

// 3. 攻撃パターン 1.

// 強い投げ刀を投げる.

int ans = 0;

rep(i, N * 2){

if(H > 0 && v[i].b && v[i].a >= maxA){

H -= v[i].a;

ans++;

}

// 4. 攻撃パターン 2.

// 攻撃力最大の振り刀を振り続ける.

if(H > 0) ans += (H + maxA - 1) / maxA;

// 5. 出力.

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

return 0;

}

[入力例]
1 10
3 5

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

[入力例]
2 10
3 5
2 6

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

[入力例]
4 1000000000
1 1
1 10000000
1 30000000
1 99999999

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

[入力例]
5 500
35 44
28 83
46 62
31 79
40 43

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

[入力例]
10 12345
100 222
72 194
108 211
76 172
85 144
28 51
40 126
8 50
19 120
26 84

[出力例]
111

[入力例]
30 20220210
941 9675
723 8610
873 9340
133 8728
286 9696
343 9739
369 9549
715 8992
665 9378
127 7592
313 9120
141 9167
69 8934
999 9174
985 9922
862 8752
455 9665
969 8218
705 7940
519 9332
859 9772
47 8968
333 9603
427 8878
710 7646
272 9973
145 8972
375 7253
45 9815
930 8493

[出力例]
20000

[入力例]

1 10

3 5

[出力例]

※AtCoderテストケースより

[入力例]

2 10

3 5

2 6

[出力例]

※AtCoderテストケースより

[入力例]

4 1000000000

1 1

1 10000000

1 30000000

1 99999999

[出力例]

860000004

※AtCoderテストケースより

[入力例]

5 500

35 44

28 83

46 62

31 79

40 43

[出力例]

※AtCoderテストケースより

[入力例]

10 12345

100 222

72 194

108 211

76 172

85 144

28 51

40 126

8 50

19 120

26 84

[出力例]

111

[入力例]

30 20220210

941 9675

723 8610

873 9340

133 8728

286 9696

343 9739

369 9549

715 8992

665 9378

127 7592

313 9120

141 9167

69 8934

999 9174

985 9922

862 8752

455 9665

969 8218

705 7940

519 9332

859 9772

47 8968

333 9603

427 8878

710 7646

272 9973

145 8972

375 7253

45 9815

930 8493

[出力例]

20000

■参照サイト
AtCoder Beginner Contest 085

2022年2月9日

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

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

■感想.
1. 問題Eは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 苦手な動的計画法の訓練を積めたので, 非常に良かったと思う.
3. 最初, TLE版で実装したが, 計算量の削減方法が分からず, dp更新式に渡す鍵情報を, AtCoder Beginner Contest 142 (解説プログラム)を参考に修正している.
4. 個人的には, 動的計画法に関する理解を, 深めることが出来たように感じた.
現状, TLE版と AC版との違いは, 本質的には, 鍵情報の捉え方の違いにあると理解している.
→ 具体的には, 鍵情報が, {宝箱1, 宝箱2, 宝箱3} だった場合に, TLE版では, {宝箱1}, {宝箱2}, {宝箱3}, {宝箱1, 宝箱2}, {宝箱1, 宝箱3}, {宝箱2, 宝箱3}, {宝箱1, 宝箱2, 宝箱3} の 7通りの鍵情報で, dp更新を行っているが, AC版では, {宝箱1, 宝箱2, 宝箱3} の 1通りの鍵情報で, dp計算を行っているため, 計算量に違いが現れたと理解している.
→ さらに, TLE版と AC版は, dp配列の途中部分は, 差分が生じるものの, 最終的に必要な情報は, すべての宝箱を, 開けることが出来るかどうか(および, 最小費用)であるため, 各鍵毎に, 常に, 1通りの鍵情報(ここでは, {宝箱1, 宝箱2, 宝箱3})を見れば十分という点について, なるほどと, 改めて感じた.
5. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/abc142/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 dp[1010][1 << 12];

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    
    // 2. 初期化.
    rep(i, 1010) rep(j, 1 << N) dp[i][j] = 2020202020;
    dp[0][0] = 0;
    
    // 3. dp更新.
    rep(i, M){
        // i個目の鍵情報.
        // ex.
        // 鍵 1, 3, 7 が 手に入った場合, 
        // 集合 {1}, {3}, {7}, {1, 3}, {1, 7}, {3, 7}, {1, 3, 7} の 組み合わせで, 見る必要があることに注意.
        int t[1 << N];
        rep(j, 1 << N) t[j] = 0;
        t[0] = 1;
        int a, b, c;
        scanf("%d %d", &a, &b);
        rep(j, b){
            scanf("%d", &c);
            repr(j, (1 << N) - 1, 0) if(t[j]) t[j + (1 << (N - c))] = 1;
        }
        
        // 鍵情報の組み合わせ保存.
        vi key;
        repx(j, 1, 1 << N) if(t[j]) key.pb(j);
        // for(auto &k : key) printf("%d ", k);
        // puts("\n----------");
        
        // 前回分反映.
        rep(j, 1 << N) dp[i + 1][j] = dp[i][j];
        
        // 宝箱を開けるための最小コスト.
        // -> 状態 j は, 開いている宝箱情報と見る.
        // ex. 
        // N = 12 で, j = 100010100011 は, 宝箱 = {1, 2, 6, 8, 12} が 開いていると見る.
        rep(j, 1 << N) for(auto &k : key) dp[i + 1][j | k] = min({dp[i + 1][j | k], dp[i][j | k], dp[i][j] + a});
        // rep(j, 1 << N) printf("%d ", dp[i + 1][j]);
        // puts("\n----------");
    }
    
    // 4. 集計.
    int ans = dp[M][(1 << N) - 1];
    if(ans == 2020202020) ans = -1;
    
    // 5. 出力.
    printf("%d\n", ans);
    return 0;
    
}

// 解き直し.

// https://img.atcoder.jp/abc142/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 dp[1010][1 << 12];

int main(){

// 1. 入力情報.

int N, M;

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

// 2. 初期化.

rep(i, 1010) rep(j, 1 << N) dp[i][j] = 2020202020;

dp[0][0] = 0;

// 3. dp更新.

rep(i, M){

// i個目の鍵情報.

// ex.

// 鍵 1, 3, 7 が手に入った場合,

// 集合 {1}, {3}, {7}, {1, 3}, {1, 7}, {3, 7}, {1, 3, 7} の組み合わせで, 見る必要があることに注意.

int t[1 << N];

rep(j, 1 << N) t[j] = 0;

t[0] = 1;

int a, b, c;

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

rep(j, b){

scanf("%d", &c);

repr(j, (1 << N) - 1, 0) if(t[j]) t[j + (1 << (N - c))] = 1;

}

// 鍵情報の組み合わせ保存.

vi key;

repx(j, 1, 1 << N) if(t[j]) key.pb(j);

// for(auto &k : key) printf("%d ", k);

// puts("\n----------");

// 前回分反映.

rep(j, 1 << N) dp[i + 1][j] = dp[i][j];

// 宝箱を開けるための最小コスト.

// -> 状態 j は, 開いている宝箱情報と見る.

// ex.

// N = 12 で, j = 100010100011 は, 宝箱 = {1, 2, 6, 8, 12} が開いていると見る.

rep(j, 1 << N) for(auto &k : key) dp[i + 1][j | k] = min({dp[i + 1][j | k], dp[i][j | k], dp[i][j] + a});

// rep(j, 1 << N) printf("%d ", dp[i + 1][j]);

// puts("\n----------");

}

// 4. 集計.

int ans = dp[M][(1 << N) - 1];

if(ans == 2020202020) ans = -1;

// 5. 出力.

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

return 0;

}

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

// 解き直し.
// https://img.atcoder.jp/abc142/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 dp[1010][1 << 12];

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    
    // 2. 初期化.
    rep(i, 1010) rep(j, 1 << N) dp[i][j] = 2020202020;
    dp[0][0] = 0;
    
    // 3. dp更新(01-handmade-07 で, TLE版だったため, ロジック修正).
    rep(i, M){
        // i個目の鍵情報.
        // -> 状態 j は, 開いている宝箱情報と見る.
        // ex. 
        // N = 12 で, j = 100010100011 は, 宝箱 = {1, 2, 6, 8, 12} が 開いていると見る.
        int a, b, c, key = 0;
        scanf("%d %d", &a, &b);
        rep(j, b){
            scanf("%d", &c);
            key |= (1 << (N - c));
        }
        
        // 前回分反映.
        rep(j, 1 << N) dp[i + 1][j] = dp[i][j];
        
        // 宝箱を開けるための最小コスト.
        rep(j, 1 << N) dp[i + 1][j | key] = min({dp[i + 1][j | key], dp[i][j | key], dp[i][j] + a});
    }
    
    // 4. 集計.
    int ans = dp[M][(1 << N) - 1];
    if(ans == 2020202020) ans = -1;
    
    // 5. 出力.
    printf("%d\n", ans);
    return 0;
    
}

// 解き直し.

// https://img.atcoder.jp/abc142/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 dp[1010][1 << 12];

int main(){

// 1. 入力情報.

int N, M;

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

// 2. 初期化.

rep(i, 1010) rep(j, 1 << N) dp[i][j] = 2020202020;

dp[0][0] = 0;

// 3. dp更新(01-handmade-07 で, TLE版だったため, ロジック修正).

rep(i, M){

// i個目の鍵情報.

// -> 状態 j は, 開いている宝箱情報と見る.

// ex.

// N = 12 で, j = 100010100011 は, 宝箱 = {1, 2, 6, 8, 12} が開いていると見る.

int a, b, c, key = 0;

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

rep(j, b){

scanf("%d", &c);

key |= (1 << (N - c));

}

// 前回分反映.

rep(j, 1 << N) dp[i + 1][j] = dp[i][j];

// 宝箱を開けるための最小コスト.

rep(j, 1 << N) dp[i + 1][j | key] = min({dp[i + 1][j | key], dp[i][j | key], dp[i][j] + a});

}

// 4. 集計.

int ans = dp[M][(1 << N) - 1];

if(ans == 2020202020) ans = -1;

// 5. 出力.

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

return 0;

}

[入力例]
2 3
10 1
1
15 1
2
30 2
1 2

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

[入力例]
12 1
100000 1
2

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

[入力例]
4 6
67786 3
1 3 4
3497 1
2
44908 3
2 3 4
2156 3
2 3 4
26230 1
2
86918 1
3

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

[入力例]
5 7
83 3
1 2 3
93 1
4
10 1
1
114 2
2 5
119 1
3
84 2
4 5
17 2
2 5

[出力例]
167

[入力例]
12 15
13483 2
1 5
5458 1
6
10474 6
2 3 7 8 10 11
3974 3
9 11 12
11592 3
1 2 3
12856 3
4 5 6
3538 4
7 8 9 10
2999 1
11
3780 3
1 11 12
9159 2
5 6
2890 3
7 9 10
11778 4
3 5 8 9
11169 5
1 2 5 7 11
12798 5
3 4 7 8 9
9578 1
2

[出力例]
30000

[入力例]

2 3

10 1

15 1

30 2

1 2

[出力例]

※AtCoderテストケースより

[入力例]

12 1

100000 1

[出力例]

-1

※AtCoderテストケースより

[入力例]

4 6

67786 3

1 3 4

3497 1

44908 3

2 3 4

2156 3

2 3 4

26230 1

86918 1

[出力例]

69942

※AtCoderテストケースより

[入力例]

5 7

83 3

1 2 3

93 1

10 1

114 2

2 5

119 1

84 2

4 5

17 2

2 5

[出力例]

167

[入力例]

12 15

13483 2

1 5

5458 1

10474 6

2 3 7 8 10 11

3974 3

9 11 12

11592 3

1 2 3

12856 3

4 5 6

3538 4

7 8 9 10

2999 1

3780 3

1 11 12

9159 2

5 6

2890 3

7 9 10

11778 4

3 5 8 9

11169 5

1 2 5 7 11

12798 5

3 4 7 8 9

9578 1

[出力例]

30000

■参照サイト
AtCoder Beginner Contest 142
AtCoder Beginner Contest 142 (解説プログラム)

C++の練習を兼ねて, JOI 2021/2022 本選 過去問 の 問題A (インターカステラー (Intercastellar)) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 225 の 問題C (Calendar Validator) ～ 問題D (Play Train) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 135 の 問題C (XOR to All) を解いてみた.

概要

感想

ベルンシュタイン・ヴァジラニ アルゴリズム(演習問題改題ほか)

参照サイト

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

概要

感想

ベルンシュタイン・ヴァジラニ アルゴリズム

参照サイト

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

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

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

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

C++の練習を兼ねて, JOI 2021/2022 本選過去問の問題A (インターカステラー (Intercastellar)) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 225 の問題C (Calendar Validator) ～問題D (Play Train) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 135 の問題C (XOR to All) を解いてみた.

ベルンシュタイン・ヴァジラニアルゴリズム(演習問題改題ほか)

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

ベルンシュタイン・ヴァジラニアルゴリズム

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

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

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

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