C++ | 個人用メモ帳

2022年10月5日

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

C++の練習を兼ねて, AtCoder Beginner Contest 271 の問題F (XOR on Grid Path) を解いてみた.

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

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

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

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

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) rep(j, N) scanf("%d", &a[i][j]);
    
    // 2. 半分全列挙.
    // 2-1. マス(1, 1) ～ 対角線上のマス(x, y).
    // → 二進数の各桁を, 以下の移動とみなす.
    //    1: マス(i, j) → マス(i + 1, j)
    //    0: マス(i, j) → マス(i, j + 1)
    map<int, int> pXor[N];
    rep(i, 1 << (N - 1)){
        int x = 0, y = 0;
        int p = a[x][y];
        rep(j, N - 1){
            if(i & (1 << j)) ++x;
            else             ++y;
            p ^= a[x][y];
        }
        ++pXor[__builtin_popcount(i)][p];
    }
    
    // 2-2. 対角線上のマス(N, N) ～ マス(x, y).
    // → 二進数の各桁を, 以下の移動とみなす.
    //    1: マス(i, j) → マス(i - 1, j)
    //    0: マス(i, j) → マス(i, j - 1)
    map<int, int> qXor[N];
    rep(i, 1 << (N - 1)){
        int x = N - 1, y = N - 1;
        int q = a[x][y];
        rep(j, N - 1){
            if(i & (1 << j)) --x;
            else             --y;
            q ^= a[x][y];
        }
        ++qXor[N - 1 - __builtin_popcount(i)][q];
    }
    
    // 3. 集計.
    LL ans = 0;
    rep(i, N){
        // マス(x, y) を 固定して, 全探索.
        for(auto &p : pXor[i]){
            int cur = a[i][N - 1 - i] ^ p.a;
            if(qXor[i].count(cur)) ans += (LL)p.b * (LL)qXor[i][cur];
        }
    }
    
    // 4. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc271/editorial/4925

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

#define a first

#define b second

int a[22][22];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

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

// 2. 半分全列挙.

// 2-1. マス(1, 1) ～対角線上のマス(x, y).

// → 二進数の各桁を, 以下の移動とみなす.

// 1: マス(i, j) → マス(i + 1, j)

// 0: マス(i, j) → マス(i, j + 1)

map<int, int> pXor[N];

rep(i, 1 << (N - 1)){

int x = 0, y = 0;

int p = a[x][y];

rep(j, N - 1){

if(i & (1 << j)) ++x;

else ++y;

p ^= a[x][y];

}

++pXor[__builtin_popcount(i)][p];

}

// 2-2. 対角線上のマス(N, N) ～マス(x, y).

// → 二進数の各桁を, 以下の移動とみなす.

// 1: マス(i, j) → マス(i - 1, j)

// 0: マス(i, j) → マス(i, j - 1)

map<int, int> qXor[N];

rep(i, 1 << (N - 1)){

int x = N - 1, y = N - 1;

int q = a[x][y];

rep(j, N - 1){

if(i & (1 << j)) --x;

else --y;

q ^= a[x][y];

}

++qXor[N - 1 - __builtin_popcount(i)][q];

}

// 3. 集計.

LL ans = 0;

rep(i, N){

// マス(x, y) を固定して, 全探索.

for(auto &p : pXor[i]){

int cur = a[i][N - 1 - i] ^ p.a;

if(qXor[i].count(cur)) ans += (LL)p.b * (LL)qXor[i][cur];

}

// 4. 出力.

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

return 0;

}

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

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

[入力例]
2
1 2
2 1

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

[入力例]
10
1 0 1 0 0 1 0 0 0 1
0 0 0 1 0 1 0 1 1 0
1 0 0 0 1 0 1 0 0 0
0 1 0 0 0 1 1 0 0 1
0 0 1 1 0 1 1 0 1 0
1 0 0 0 1 0 0 1 1 0
1 1 1 0 0 0 1 1 0 0
0 1 1 0 0 1 1 0 1 0
1 0 1 1 0 0 0 0 0 0
1 0 1 1 0 0 1 1 1 0

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

[入力例]
2
3 1
1 2

[出力例]
2

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

[出力例]
2

[入力例]
7
87 47 83 83 33 76 95
32 114 38 7 46 90 118
116 14 1 55 29 40 76
25 41 115 13 66 79 43
71 67 73 94 43 111 83
57 121 98 97 57 67 91
24 110 47 28 22 64 37

[出力例]
5

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

[出力例]
3107

[入力例]
20
261 92 16 184 99 232 142 1 23 173 135 112 45 50 115 171 224 132 109 49
293 108 122 163 124 276 97 200 70 183 301 166 64 65 38 298 182 298 9 53
290 274 207 298 45 227 220 198 132 137 176 144 12 182 112 265 316 133 225 312
114 191 76 164 227 184 254 98 137 114 265 8 177 121 234 4 177 137 21 88
272 331 11 330 288 1 165 274 234 99 137 201 331 105 184 132 301 90 139 103
44 299 33 135 67 142 113 196 226 279 107 144 296 46 181 43 33 51 11 10
214 123 67 65 313 183 266 98 3 203 197 292 262 55 22 323 108 63 330 103
314 295 295 273 172 73 85 320 150 38 20 11 276 301 10 226 125 233 225 116
2 166 10 116 249 258 84 142 191 54 39 327 137 90 27 262 313 39 153 40
7 170 272 72 121 332 105 327 76 61 188 144 208 258 313 154 76 223 123 196
256 263 272 201 13 296 200 171 195 176 48 239 111 225 173 235 268 159 154 201
287 112 10 276 46 316 168 199 220 144 208 290 56 194 53 305 229 192 43 168
159 297 328 51 48 75 292 181 193 33 17 21 19 219 167 160 94 104 46 240
58 318 199 20 178 150 213 97 242 278 187 312 213 41 108 52 41 165 98 292
6 181 148 51 290 9 128 230 12 266 136 225 6 319 26 115 274 256 164 129
309 210 276 294 202 68 37 53 98 184 112 49 20 259 286 105 86 325 134 158
4 321 125 150 197 190 13 286 44 314 33 152 189 201 80 80 222 239 70 155
263 134 327 70 108 161 207 124 225 144 58 70 69 308 104 239 309 232 142 222
212 162 301 261 286 246 163 296 285 9 117 6 9 22 273 235 317 55 326 90
97 264 249 115 309 249 242 7 49 1 254 215 43 145 267 48 18 65 65 168

[出力例]
69041220

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

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

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

[入力例]

1 5 2

7 0 5

4 2 3

[出力例]

※AtCoderテストケースより

[入力例]

1 2

2 1

[出力例]

※AtCoderテストケースより

[入力例]

1 0 1 0 0 1 0 0 0 1

0 0 0 1 0 1 0 1 1 0

1 0 0 0 1 0 1 0 0 0

0 1 0 0 0 1 1 0 0 1

0 0 1 1 0 1 1 0 1 0

1 0 0 0 1 0 0 1 1 0

1 1 1 0 0 0 1 1 0 0

0 1 1 0 0 1 1 0 1 0

1 0 1 1 0 0 0 0 0 0

1 0 1 1 0 0 1 1 1 0

[出力例]

24307

※AtCoderテストケースより

[入力例]

3 1

1 2

[出力例]

[入力例]

3 2 0

1 2 3

0 1 3

[出力例]

[入力例]

87 47 83 83 33 76 95

32 114 38 7 46 90 118

116 14 1 55 29 40 76

25 41 115 13 66 79 43

71 67 73 94 43 111 83

57 121 98 97 57 67 91

24 110 47 28 22 64 37

[出力例]

[入力例]

2 0 1 10 3 1 0 4 6 0

3 5 6 11 1 4 2 7 7 9

5 8 4 2 0 11 2 4 5 8

0 8 3 11 4 11 0 11 8 11

2 10 1 6 10 1 0 3 0 6

10 3 2 8 4 2 10 2 8 9

11 11 4 10 10 7 9 8 8 4

11 0 7 6 5 3 5 5 3 11

11 4 1 11 1 7 9 10 1 3

2 7 6 4 5 0 8 10 11 3

[出力例]

3107

[入力例]

261 92 16 184 99 232 142 1 23 173 135 112 45 50 115 171 224 132 109 49

293 108 122 163 124 276 97 200 70 183 301 166 64 65 38 298 182 298 9 53

290 274 207 298 45 227 220 198 132 137 176 144 12 182 112 265 316 133 225 312

114 191 76 164 227 184 254 98 137 114 265 8 177 121 234 4 177 137 21 88

272 331 11 330 288 1 165 274 234 99 137 201 331 105 184 132 301 90 139 103

44 299 33 135 67 142 113 196 226 279 107 144 296 46 181 43 33 51 11 10

214 123 67 65 313 183 266 98 3 203 197 292 262 55 22 323 108 63 330 103

314 295 295 273 172 73 85 320 150 38 20 11 276 301 10 226 125 233 225 116

2 166 10 116 249 258 84 142 191 54 39 327 137 90 27 262 313 39 153 40

7 170 272 72 121 332 105 327 76 61 188 144 208 258 313 154 76 223 123 196

256 263 272 201 13 296 200 171 195 176 48 239 111 225 173 235 268 159 154 201

287 112 10 276 46 316 168 199 220 144 208 290 56 194 53 305 229 192 43 168

159 297 328 51 48 75 292 181 193 33 17 21 19 219 167 160 94 104 46 240

58 318 199 20 178 150 213 97 242 278 187 312 213 41 108 52 41 165 98 292

6 181 148 51 290 9 128 230 12 266 136 225 6 319 26 115 274 256 164 129

309 210 276 294 202 68 37 53 98 184 112 49 20 259 286 105 86 325 134 158

4 321 125 150 197 190 13 286 44 314 33 152 189 201 80 80 222 239 70 155

263 134 327 70 108 161 207 124 225 144 58 70 69 308 104 239 309 232 142 222

212 162 301 261 286 246 163 296 285 9 117 6 9 22 273 235 317 55 326 90

97 264 249 115 309 249 242 7 49 1 254 215 43 145 267 48 18 65 65 168

[出力例]

69041220

[入力例]

27 19 16 13 25 25 12 26 26 6 13 13 29 5 7 10 17 11 6 20 8 14 25

24 0 31 5 27 27 21 29 0 7 13 28 6 2 3 23 2 26 21 17 16 29 9

32 15 20 32 22 2 15 23 19 20 18 19 1 9 29 15 3 13 5 32 4 19 31

29 8 12 9 32 25 26 6 31 17 14 10 26 14 11 19 11 29 17 0 7 16 18

23 6 18 30 18 32 16 8 16 15 6 24 18 3 5 1 0 9 29 10 14 9 11

22 23 29 2 28 5 10 1 21 27 20 22 15 21 12 13 15 30 1 13 9 10 22

16 18 19 8 29 20 18 29 1 6 21 22 7 15 13 0 20 26 22 12 32 7 28

6 1 28 7 23 11 24 7 9 4 32 11 21 4 29 8 30 25 16 27 7 17 10

18 5 26 3 21 11 8 6 3 8 3 12 25 19 28 26 20 11 20 5 27 25 4

12 7 18 12 7 3 4 9 0 20 22 7 4 19 27 22 16 22 16 8 19 24 27

26 27 8 6 4 12 12 25 14 12 22 25 18 20 27 15 32 18 8 23 15 17 11

12 22 4 14 24 30 28 5 16 6 9 25 18 4 10 11 29 28 21 17 15 5 9

22 5 15 17 16 23 28 10 5 19 13 31 24 0 28 1 15 24 25 1 2 27 29

9 5 14 20 26 16 14 14 27 30 15 12 14 2 4 14 2 32 14 19 10 4 12

22 11 12 16 19 11 11 19 16 0 2 10 15 24 32 12 25 15 31 10 28 29 19

5 32 6 20 3 9 17 27 20 18 2 30 0 6 10 25 30 14 0 2 2 5 3

28 1 11 26 5 27 32 26 16 16 14 19 29 23 3 24 0 9 3 13 6 29 14

25 17 23 21 21 12 29 23 30 18 5 2 23 12 3 16 17 10 1 26 24 0 20

12 19 26 29 12 26 24 30 15 0 28 13 6 9 4 31 3 32 3 10 3 20 23

32 0 22 26 21 0 30 26 5 27 32 11 29 23 21 24 3 10 17 7 32 9 21

4 4 3 17 17 6 11 17 32 27 8 5 7 17 10 5 12 12 5 24 15 23 2

7 32 32 5 9 14 12 25 22 26 27 31 32 2 10 1 25 17 19 6 21 13 0

13 22 3 13 21 24 25 3 27 3 32 6 28 32 4 10 8 9 15 7 31 17 28

[出力例]

32767609364

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

■参照サイト
京セラプログラミングコンテスト2022(AtCoder Beginner Contest 271)

2022年10月4日2022年10月4日

■感想.
1. 問題Eは, 方針が見えなかったため, 解説を参考に, AC版に到達できた.
2. 実装に苦労したものの, 問題Eで, 苦手な動的計画法の訓練を積めたので, 非常に良かったと思う.
3. dp更新式は, 解説プログラムを見ると, 非常にシンプルに実装されていたので, 実装のシンプル化は, 引き続き, 今後の課題にしたいと思う.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

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

int main(){
    
    // 1. 入力情報.
    int N, M, K;
    scanf("%d %d %d", &N, &M, &K);
    vt t;
    set<int> Idx[N];
    rep(i, M){
        int a, b;
        LL c;
        scanf("%d %d %lld", &a, &b, &c);
        --a;
        --b;
        
        // 辺(a, b) の 情報.
        t.emplace_back(a, b, c);
        
        // 辺(a, b) を, 頂点 a を 基準 に 保存.
        Idx[a].insert(b);
    }
    vi E(K);
    rep(i, K){
        scanf("%d", &E[i]);
        --E[i];
    }
    
    // 2. dp更新.
    LL dp[N];
    rep(i, N) dp[i] = INF;
    dp[0] = 0;
    rep(i, K){
        // 辺情報(番号: E[i]).
        int ca = get<0>(t[E[i]]);
        int cb = get<1>(t[E[i]]);
        LL cc = get<2>(t[E[i]]);
        
        // 最小値更新.
        dp[cb] = min(dp[cb], dp[ca] + cc);
        
        // ループ(i) の 範囲は, [0, K - 1] に ロジック修正.
        // -> テストケース(test_01.txt)で, WA だったことに対応.
        if(i == K - 1) break;
        
        // 辺情報(番号: E[i + 1]).
        int na = get<0>(t[E[i + 1]]);
        int nb = get<1>(t[E[i + 1]]);
        LL nc = get<2>(t[E[i + 1]]);
        
        // 最小値更新.
        // -> 頂点 na を 終端とするものを考える.
        if(Idx[na].count(nb)) dp[nb] = min(dp[nb], dp[na] + nc);
    }
    
    // 3. 出力.
    printf("%lld\n", (dp[N - 1] >= INF) ? -1 : dp[N - 1]);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc271/editorial/4924

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vi = vector<int>;

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

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 LL INF = 101010101010101010;

int main(){

// 1. 入力情報.

int N, M, K;

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

vt t;

set<int> Idx[N];

rep(i, M){

int a, b;

LL c;

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

--a;

--b;

// 辺(a, b) の情報.

t.emplace_back(a, b, c);

// 辺(a, b) を, 頂点 a を基準に保存.

Idx[a].insert(b);

}

vi E(K);

rep(i, K){

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

--E[i];

}

// 2. dp更新.

LL dp[N];

rep(i, N) dp[i] = INF;

dp[0] = 0;

rep(i, K){

// 辺情報(番号: E[i]).

int ca = get<0>(t[E[i]]);

int cb = get<1>(t[E[i]]);

LL cc = get<2>(t[E[i]]);

// 最小値更新.

dp[cb] = min(dp[cb], dp[ca] + cc);

// ループ(i) の範囲は, [0, K - 1] にロジック修正.

// -> テストケース(test_01.txt)で, WA だったことに対応.

if(i == K - 1) break;

// 辺情報(番号: E[i + 1]).

int na = get<0>(t[E[i + 1]]);

int nb = get<1>(t[E[i + 1]]);

LL nc = get<2>(t[E[i + 1]]);

// 最小値更新.

// -> 頂点 na を終端とするものを考える.

if(Idx[na].count(nb)) dp[nb] = min(dp[nb], dp[na] + nc);

}

// 3. 出力.

printf("%lld\n", (dp[N - 1] >= INF) ? -1 : dp[N - 1]);

return 0;

}

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

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

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

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

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

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

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

[出力例]
3

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

[出力例]
5

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

[出力例]
10

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

[出力例]
21

[入力例]

3 4 4

1 2 2

2 3 2

1 3 3

1 3 5

4 2 1 2

[出力例]

※AtCoderテストケースより

[入力例]

3 2 3

1 2 1

2 3 1

2 1 1

[出力例]

-1

※AtCoderテストケースより

[入力例]

4 4 5

3 2 2

1 3 5

2 4 7

3 4 10

2 4 1 4 3

[出力例]

※AtCoderテストケースより

[入力例]

2 3 1

1 2 3

1 2 2

1 2 1

[出力例]

[入力例]

3 4 5

1 2 2

1 3 7

2 3 4

2 3 3

2 1 3 2 4

[出力例]

[入力例]

7 9 10

1 2 3

2 5 4

6 7 1

3 7 5

5 6 2

3 6 1

2 4 2

2 3 1

4 7 6

3 1 4 1 5 9 2 6 5 3

[出力例]

[入力例]

15 21 18

1 5 2

1 3 7

1 8 5

8 9 1

3 2 6

5 7 8

2 4 5

9 4 9

9 10 6

4 6 2

4 7 1

7 6 2

7 13 3

6 10 15

6 11 1

10 11 7

13 11 7

13 14 6

11 12 8

12 14 1

14 15 2

8 9 10 1 2 3 12 7 4 6 5 7 11 13 20 18 19 21

[出力例]

■参照サイト
京セラプログラミングコンテスト2022(AtCoder Beginner Contest 271)

2022年10月2日2022年10月2日

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

C++の練習を兼ねて, AtCoder Beginner Contest 271 の問題C (Manga) ～問題D (Flip and Adjust) を解いてみた.

■感想.
1. 問題Cは, 実装したもののロジック誤りが修正出来なかったため, 解説を参考に, AC版に到達できた.
2. 問題Dで, 苦手な動的計画法の訓練を積めたので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

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

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    multiset<int> mst;
    rep(i, N){
        int a;
        scanf("%d", &a);
        
        // 1-1. N より大きな巻.
        if(a > N){
            mst.insert(N + 1);
            continue;
        }
        
        // 1-2. 二冊以上ある.
        if(mst.count(a)){
            mst.insert(N + 1);
            continue;
        }
        
        // 1-3. それ以外.
        mst.insert(a);
    }
    
    // 2. 単行本売買.
    int ans = 0;
    repx(i, 1, N + 1){
        // 2-1. 単行本を持っている.
        auto s = mst.begin();
        if(i == *s){
            ++ans;
            mst.erase(mst.find(*s));
            continue;
        }
        
        // 2-2. 単行本を持ってない.
        if(mst.size() < 2) break;
        mst.erase(mst.find(*(--mst.end())));
        mst.erase(mst.find(*(--mst.end())));
        ++ans;
    }
    
    // 3. 出力.
    printf("%d\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc271/editorial/4930

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

multiset<int> mst;

rep(i, N){

int a;

scanf("%d", &a);

// 1-1. N より大きな巻.

if(a > N){

mst.insert(N + 1);

continue;

}

// 1-2. 二冊以上ある.

if(mst.count(a)){

mst.insert(N + 1);

continue;

}

// 1-3. それ以外.

mst.insert(a);

}

// 2. 単行本売買.

int ans = 0;

repx(i, 1, N + 1){

// 2-1. 単行本を持っている.

auto s = mst.begin();

if(i == *s){

++ans;

mst.erase(mst.find(*s));

continue;

}

// 2-2. 単行本を持ってない.

if(mst.size() < 2) break;

mst.erase(mst.find(*(--mst.end())));

++ans;

}

// 3. 出力.

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

return 0;

}

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

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

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

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

[入力例]
1
5

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

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

[出力例]
10

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

[出力例]
10

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

[出力例]
16

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

[出力例]
66

[入力例]

1 2 4 6 7 271

[出力例]

※AtCoderテストケースより

[入力例]

1 1 1 1 1 1 1 1 1 1

[出力例]

※AtCoderテストケースより

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

1 2 3 4 5 6 7 8 9 10

[出力例]

[入力例]

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

[出力例]

[入力例]

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

[出力例]

[入力例]

100

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

[出力例]

■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 pb push_back
#define all(x) x.begin(), x.end()
bool dp[101][10101][2];
int a[101], b[101];

int main(){
    
    // 1. 入力情報.
    int N, S;
    scanf("%d %d", &N, &S);
    rep(i, N) scanf("%d %d", &a[i], &b[i]);
    
    // 2. dp更新.
    dp[0][0][0] = dp[0][0][1] = 1;
    rep(i, N){
        repr(j, S, 0){
            // 表.
            int h = a[i] + j;
            if(h <= S){
                if(dp[i][j][0] || dp[i][j][1]) dp[i + 1][h][0] = true;
            }
            
            // 裏.
            int t = b[i] + j;
            if(t <= S){
                if(dp[i][j][0] || dp[i][j][1]) dp[i + 1][t][1] = true;
            }
        }
    }
    
    // 3. 例外.
    if(!dp[N][S][0] && !dp[N][S][1]){
        puts("No");
        return 0;
    }
    
    // 4. カードの置き方は？
    string ans = "";
    int s = S;
    ans.pb(dp[N][S][0] ? 'H' : 'T');
    s -= dp[N][S][0] ? a[N - 1] : b[N - 1];
    repr(i, N - 2, 0){
        // 表.
        if(s >= 0 && dp[i + 1][s][0]){
            ans.pb('H');
            s -= a[i];
            continue;
        }
        
        // 裏.
        if(s >= 0 && dp[i + 1][s][1]){
            ans.pb('T');
            s -= b[i];
        }
    }
    
    // 5. 反転.
    reverse(all(ans));
    
    // 6. 出力.
    printf("%s\n%s\n", "Yes", ans.c_str());
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

#define pb push_back

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

bool dp[101][10101][2];

int a[101], b[101];

int main(){

// 1. 入力情報.

int N, S;

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

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

// 2. dp更新.

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

rep(i, N){

repr(j, S, 0){

// 表.

int h = a[i] + j;

if(h <= S){

if(dp[i][j][0] || dp[i][j][1]) dp[i + 1][h][0] = true;

}

// 裏.

int t = b[i] + j;

if(t <= S){

if(dp[i][j][0] || dp[i][j][1]) dp[i + 1][t][1] = true;

}

// 3. 例外.

if(!dp[N][S][0] && !dp[N][S][1]){

puts("No");

return 0;

}

// 4. カードの置き方は？

string ans = "";

int s = S;

ans.pb(dp[N][S][0] ? 'H' : 'T');

s -= dp[N][S][0] ? a[N - 1] : b[N - 1];

repr(i, N - 2, 0){

// 表.

if(s >= 0 && dp[i + 1][s][0]){

ans.pb('H');

s -= a[i];

continue;

}

// 裏.

if(s >= 0 && dp[i + 1][s][1]){

ans.pb('T');

s -= b[i];

}

// 5. 反転.

reverse(all(ans));

// 6. 出力.

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

return 0;

}

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

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

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

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

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

[出力例]
Yes
HHHHTHH

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

[出力例]
Yes
HTHHHHH

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

[出力例]
Yes
THTHT

[入力例]
12 210
18 5
12 12
15 12
7 18
7 15
24 12
8 25
18 13
8 22
12 1
23 21
8 2

[出力例]
Yes
HHHTTHTHTHHH

[入力例]
50 2022
40 93
24 85
78 30
54 5
25 40
92 65
36 29
23 77
83 84
82 73
57 2
1 31
98 28
35 17
66 93
54 70
72 1
28 79
72 83
68 74
81 62
32 26
59 75
5 87
13 27
68 77
47 11
40 80
27 41
95 51
21 21
93 90
17 32
95 25
31 87
80 25
47 45
14 60
89 96
90 56
59 26
5 47
83 99
32 18
79 85
1 11
87 20
79 1
14 85
57 91

[出力例]
Yes
HHTTHTTHHTTHTTHHTHHTTHHHHHTHHTHHHTHTHHHTHHHHHHHHHH

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

[入力例]

3 11

1 4

2 3

5 7

[出力例]

Yes

THH

※AtCoderテストケースより

[入力例]

5 25

2 8

9 3

4 11

5 1

12 6

[出力例]

※AtCoderテストケースより

[入力例]

7 18

2 3

2 4

2 3

3 2

9 5

1 2

3 1

[出力例]

Yes

HHHHTHH

[入力例]

7 18

3 2

4 2

3 2

2 3

5 9

2 1

1 3

[出力例]

Yes

HTHHHHH

[入力例]

5 15

1 3

3 1

1 3

3 1

1 3

[出力例]

Yes

THTHT

[入力例]

12 210

18 5

12 12

15 12

7 18

7 15

24 12

8 25

18 13

8 22

12 1

23 21

8 2

[出力例]

Yes

HHHTTHTHTHHH

[入力例]

50 2022

40 93

24 85

78 30

54 5

25 40

92 65

36 29

23 77

83 84

82 73

57 2

1 31

98 28

35 17

66 93

54 70

72 1

28 79

72 83

68 74

81 62

32 26

59 75

5 87

13 27

68 77

47 11

40 80

27 41

95 51

21 21

93 90

17 32

95 25

31 87

80 25

47 45

14 60

89 96

90 56

59 26

5 47

83 99

32 18

79 85

1 11

87 20

79 1

14 85

57 91

[出力例]

Yes

HHTTHTTHHTTHTTHHTHHTTHHHHHTHHTHHHTHTHHHTHHHHHHHHHH

■参照サイト
京セラプログラミングコンテスト2022(AtCoder Beginner Contest 271)

2022年9月30日

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

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

■感想.
1. 問題Fは, 方針が見えなかったので, 解説を参考に, AC版に到達できた.
2. 最小全域木(Kruskal’s Algorithm) の復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/abc270/editorial/4879
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vi = vector<int>;
using T3 = tuple<LL, int, int>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define all(x) x.begin(), x.end()

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

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    // 1-1. 空港.
    vector<T3> tx;
    rep(i, N){
        LL x;
        scanf("%lld", &x);
        tx.emplace_back(x, i, N);
    }
    
    // 1-2. 港.
    vector<T3> ty;
    rep(i, N){
        LL y;
        scanf("%lld", &y);
        ty.emplace_back(y, i, N + 1);
    }
    
    // 1-3. 道路.
    vector<T3> tz;
    rep(i, M){
        int a, b;
        LL z;
        scanf("%d %d %lld", &a, &b, &z);
        --a, --b;
        tz.emplace_back(z, a, b);
    }
    
    // 2. 最小全域木(Kruskal's Algorithm) の 構築.
    // 競プロ典型 90 問 (049 - Flip Digits 2)
    // https://github.com/E869120/kyopro_educational_90/blob/main/sol/049.cpp
    // -> 空港, 港 を 含む, 含まないで, 4 通り を 確認.
    LL ans = 202020202020202020;
    rep(i, 2){
        rep(j, 2){
            // 候補となる辺.
            vector<T3> t = tz;
            
            // 空港あり.
            if(i) t.insert(t.end(), all(tx));
            
            // 港あり.
            if(j) t.insert(t.end(), all(ty));
            
            // sort.
            sort(all(t));
            
            // グラフ構築.
            UnionFind uf(N + 3);
            LL cost = 0;
            rep(k, t.size()){
                // グラフ情報.
                int u = get<1>(t[k]); // 頂点.
                int v = get<2>(t[k]); // 頂点.
                LL c = get<0>(t[k]); // コスト.
                
                // 最小全域木を構成する辺の追加.
                if(!uf.same(u, v)){
                    uf.unite(u, v);
                    cost += c;
                }
            }
            
            // 頂点 1 ～ 頂点 N が, 同じ連結成分に含まれるか？
            bool ok = true;
            int g = uf.find(0);
            repx(k, 1, N) if(g != uf.find(k)) ok = false;
            
            // 最小値更新.
            if(ok) ans = min(ans, cost);
        }
    }
    
    // 3. 出力.
    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

122

123

// 解き直し.

// https://atcoder.jp/contests/abc270/editorial/4879

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vi = vector<int>;

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

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

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

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

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

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

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

// UnionFind

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

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

// -> 一部改変.

struct UnionFind{

vi d;

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

int find(int x){

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

}

bool unite(int x, int y){

x = find(x);

y = find(y);

if(x == y) return false;

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

d[x] += d[y];

d[y] = x;

return true;

}

bool same(int x, int y){

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

}

int size(int x){

return -d[find(x)];

}

};

int main(){

// 1. 入力情報.

int N, M;

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

// 1-1. 空港.

vector<T3> tx;

rep(i, N){

LL x;

scanf("%lld", &x);

tx.emplace_back(x, i, N);

}

// 1-2. 港.

vector<T3> ty;

rep(i, N){

LL y;

scanf("%lld", &y);

ty.emplace_back(y, i, N + 1);

}

// 1-3. 道路.

vector<T3> tz;

rep(i, M){

int a, b;

LL z;

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

--a, --b;

tz.emplace_back(z, a, b);

}

// 2. 最小全域木(Kruskal's Algorithm) の構築.

// 競プロ典型 90 問 (049 - Flip Digits 2)

// https://github.com/E869120/kyopro_educational_90/blob/main/sol/049.cpp

// -> 空港, 港を含む, 含まないで, 4 通りを確認.

LL ans = 202020202020202020;

rep(i, 2){

rep(j, 2){

// 候補となる辺.

vector<T3> t = tz;

// 空港あり.

if(i) t.insert(t.end(), all(tx));

// 港あり.

if(j) t.insert(t.end(), all(ty));

// sort.

sort(all(t));

// グラフ構築.

UnionFind uf(N + 3);

LL cost = 0;

rep(k, t.size()){

// グラフ情報.

int u = get<1>(t[k]); // 頂点.

int v = get<2>(t[k]); // 頂点.

LL c = get<0>(t[k]); // コスト.

// 最小全域木を構成する辺の追加.

if(!uf.same(u, v)){

uf.unite(u, v);

cost += c;

}

// 頂点 1 ～頂点 N が, 同じ連結成分に含まれるか？

bool ok = true;

int g = uf.find(0);

repx(k, 1, N) if(g != uf.find(k)) ok = false;

// 最小値更新.

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

}

// 3. 出力.

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

return 0;

}

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

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

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

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

[入力例]
7 8
35 29 36 88 58 15 25
99 7 49 61 67 4 57
2 3 3
2 5 36
2 6 89
1 6 24
5 7 55
1 3 71
3 4 94
5 6 21

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

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

[出力例]
15

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

[出力例]
19

[入力例]
20 25
1020 606 1053 255 1031 592 887 450 875 791 851 1086 655 108 393 650 379 517 111 404
1046 462 208 281 1007 308 856 156 291 864 559 941 1028 128 994 979 1055 989 811 645
1 20 1010
1 16 1347
1 17 1550
2 18 1597
2 19 870
2 20 792
2 3 1639
2 4 1609
3 4 1178
1 3 1537
5 6 1504
7 8 1336
8 11 1160
4 5 1537
9 11 1018
12 13 1244
14 15 1335
16 17 1632
17 18 973
13 18 1296
18 19 1056
10 11 1160
10 12 752
18 19 1492
17 18 1463

[出力例]
10000

[入力例]

4 2

1 20 4 7

20 2 20 3

1 3 5

1 4 6

[出力例]

※AtCoderテストケースより

[入力例]

3 1

1 1 1

10 10 10

1 2 100

[出力例]

※AtCoderテストケースより

[入力例]

7 8

35 29 36 88 58 15 25

99 7 49 61 67 4 57

2 3 3

2 5 36

2 6 89

1 6 24

5 7 55

1 3 71

3 4 94

5 6 21

[出力例]

160

※AtCoderテストケースより

[入力例]

5 5

5 7 8 10 12

7 1 13 11 6

1 2 5

2 3 7

1 3 2

3 4 9

4 5 1

[出力例]

[入力例]

7 6

5 6 2 3 8 5 10

8 7 2 1 6 6 6

1 2 3

2 3 1

3 4 7

3 5 9

3 6 2

1 7 4

[出力例]

[入力例]

20 25

1020 606 1053 255 1031 592 887 450 875 791 851 1086 655 108 393 650 379 517 111 404

1046 462 208 281 1007 308 856 156 291 864 559 941 1028 128 994 979 1055 989 811 645

1 20 1010

1 16 1347

1 17 1550

2 18 1597

2 19 870

2 20 792

2 3 1639

2 4 1609

3 4 1178

1 3 1537

5 6 1504

7 8 1336

8 11 1160

4 5 1537

9 11 1018

12 13 1244

14 15 1335

16 17 1632

17 18 973

13 18 1296

18 19 1056

10 11 1160

10 12 752

18 19 1492

17 18 1463

[出力例]

10000

■参照サイト
トヨタ自動車プログラミングコンテスト2022(AtCoder Beginner Contest 270)

2022年9月29日

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

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

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

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

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

int main(){
    
    // 1. 入力情報.
    LL N, M;
    int Q;
    scanf("%lld %lld %d", &N, &M, &Q);
    
    // 2. 整数和(マス(0, 0) ～ マス(x, y)).
    auto f = [&](LL x, LL y) -> LL {
        // 2-1. y が 偶数.
        // x * (y / 2) * (y / 2) + M * x * (x - 1) / 2 * (y / 2) + (x / 2) * (y / 2).
        LL x2 = x / 2;
        LL x3 = (x - 1) / 2;
        LL y2 = y / 2;
        LL ret = x * y2 % MOD * y2 % MOD;
        ret += M * x % MOD * (x + MOD - 1) % MOD * 499122177 % MOD * y2 % MOD;
        ret %= MOD;
        ret += x2 * y2 % MOD;
        ret %= MOD;
        
        // 2-2. y が 奇数.
        // 2 * x * (y / 2) + x - y * (x / 2) + M * (1 + (x - 1) / 2) * (x - 1) / 2.
        if(y & 1){
            ret += 2 * x % MOD * y2 % MOD;
            ret %= MOD;
            ret += x;
            ret %= MOD;
            ret += MOD;
            ret -= y * x2 % MOD;
            ret %= MOD;
            ret += M * (1 + x3) % MOD * x3 % MOD;
            ret %= MOD;
        }
        
        // 2-3. 計算結果.
        return ret;
    };
    
    // 3. クエリ回答.
    rep(i, Q){
        // 3-1. クエリ入力情報.
        LL a, b, c, d;
        scanf("%lld %lld %lld %lld", &a, &b, &c, &d);
        
        // 3-2. 二次元累積和.
        LL ans = f(b, d);
        ans += MOD;
        ans -= f(a - 1, d);
        ans %= MOD;
        ans += MOD;
        ans -= f(b, c - 1);
        ans %= MOD;
        ans += f(a - 1, c - 1);
        ans %= MOD;
        
        // 3-3. 出力.
        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;

int main(){

// 1. 入力情報.

LL N, M;

int Q;

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

// 2. 整数和(マス(0, 0) ～マス(x, y)).

auto f = [&](LL x, LL y) -> LL {

// 2-1. y が偶数.

// x * (y / 2) * (y / 2) + M * x * (x - 1) / 2 * (y / 2) + (x / 2) * (y / 2).

LL x2 = x / 2;

LL x3 = (x - 1) / 2;

LL y2 = y / 2;

LL ret = x * y2 % MOD * y2 % MOD;

ret += M * x % MOD * (x + MOD - 1) % MOD * 499122177 % MOD * y2 % MOD;

ret %= MOD;

ret += x2 * y2 % MOD;

ret %= MOD;

// 2-2. y が奇数.

// 2 * x * (y / 2) + x - y * (x / 2) + M * (1 + (x - 1) / 2) * (x - 1) / 2.

if(y & 1){

ret += 2 * x % MOD * y2 % MOD;

ret %= MOD;

ret += x;

ret %= MOD;

ret += MOD;

ret -= y * x2 % MOD;

ret %= MOD;

ret += M * (1 + x3) % MOD * x3 % MOD;

ret %= MOD;

}

// 2-3. 計算結果.

return ret;

};

// 3. クエリ回答.

rep(i, Q){

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

LL a, b, c, d;

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

// 3-2. 二次元累積和.

LL ans = f(b, d);

ans += MOD;

ans -= f(a - 1, d);

ans %= MOD;

ans += MOD;

ans -= f(b, c - 1);

ans %= MOD;

ans += f(a - 1, c - 1);

ans %= MOD;

// 3-3. 出力.

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

}

return 0;

}

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

[出力例]
28
27
36
14
0
104
※AtCoderテストケースより

[入力例]
1000000000 1000000000
3
1000000000 1000000000 1000000000 1000000000
165997482 306594988 719483261 992306147
1 1000000000 1 1000000000

[出力例]
716070898
240994972
536839100
※AtCoderテストケースより

[入力例]
999999999 999999999
3
999999999 999999999 999999999 999999999
216499784 840031647 84657913 415448790
1 999999999 1 999999999

[出力例]
712559605
648737448
540261130
※AtCoderテストケースより

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

[出力例]
325
316
256
248
792
1896
1311

[入力例]
20 22
12
1 1 1 1
1 1 2 2
2 2 10 10
1 4 5 7
3 5 4 14
3 5 3 19
5 12 4 14
1 13 1 22
2 17 5 11
5 17 17 21
1 20 9 18
1 20 1 22

[出力例]
1
0
32
212
1200
2002
7700
20515
11008
7887
22250
48510

[入力例]

5 4

1 3 2 4

1 5 1 1

5 5 1 4

4 4 2 2

5 5 4 4

1 5 1 4

[出力例]

104

※AtCoderテストケースより

[入力例]

1000000000 1000000000

1000000000 1000000000 1000000000 1000000000

165997482 306594988 719483261 992306147

1 1000000000 1 1000000000

[出力例]

716070898

240994972

536839100

※AtCoderテストケースより

[入力例]

999999999 999999999

999999999 999999999 999999999 999999999

216499784 840031647 84657913 415448790

1 999999999 1 999999999

[出力例]

712559605

648737448

540261130

※AtCoderテストケースより

[入力例]

10 11

1 5 1 5

2 5 1 5

1 5 2 5

2 5 2 5

2 7 3 8

3 10 5 11

3 9 5 10

[出力例]

325

316

256

248

792

1896

1311

[入力例]

20 22

1 1 1 1

1 1 2 2

2 2 10 10

1 4 5 7

3 5 4 14

3 5 3 19

5 12 4 14

1 13 1 22

2 17 5 11

5 17 17 21

1 20 9 18

1 20 1 22

[出力例]

212

1200

2002

7700

20515

11008

7887

22250

48510

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

2022年9月27日

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

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

■感想.
1. 問題Eは, 方針を絞り込めたので, AC版に到達できたと思う.
2. 個人的には, 問題Eで, 二分探索(応用版, 評価関数のインタラクティブ対応) の復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

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

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    
    // 2. 評価関数.
    auto f = [&](int a, int b, int c, int d, int e) -> bool {
        // 2-1. 質問.
        printf("? %d %d %d %d\n", a, b, c, d);
        fflush(stdout);
        
        // 2-2. 応答.
        int T;
        scanf("%d", &T);
        
        // 2-3. 判定結果.
        return e ? (T == d - c + 1) : (T == b - a + 1);
    };
    
    // 3. 二分探索で確認してみる(行).
    int l = 1, h = N, X = -1;
    while(l + 1 <= h){
        int m = (h + l) >> 1;
        if(f(l, m, 1, N, 0)){
            l = m + 1;
            X = h;
        }else{
            h = m;
            X = l;
        }
    }
    
    // 4. 二分探索で確認してみる(列).
    l = 1, h = N;
    int Y = -1;
    while(l + 1 <= h){
        int m = (h + l) >> 1;
        if(f(1, N, l, m, 1)){
            l = m + 1;
            Y = h;
        }else{
            h = m;
            Y = l;
        }
    }
    
    // 5. 出力.
    assert(X != -1 && Y != -1);
    printf("! %d %d\n", X, Y);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

// 2. 評価関数.

auto f = [&](int a, int b, int c, int d, int e) -> bool {

// 2-1. 質問.

printf("? %d %d %d %d\n", a, b, c, d);

fflush(stdout);

// 2-2. 応答.

int T;

scanf("%d", &T);

// 2-3. 判定結果.

return e ? (T == d - c + 1) : (T == b - a + 1);

};

// 3. 二分探索で確認してみる(行).

int l = 1, h = N, X = -1;

while(l + 1 <= h){

int m = (h + l) >> 1;

if(f(l, m, 1, N, 0)){

l = m + 1;

X = h;

}else{

h = m;

X = l;

}

// 4. 二分探索で確認してみる(列).

l = 1, h = N;

int Y = -1;

while(l + 1 <= h){

int m = (h + l) >> 1;

if(f(1, N, l, m, 1)){

l = m + 1;

Y = h;

}else{

h = m;

Y = l;

}

// 5. 出力.

assert(X != -1 && Y != -1);

printf("! %d %d\n", X, Y);

return 0;

}

※インタラクティブな問題のため, 入出力は, デバッグ時に使用したものを記載している.

[入力例]
2
1
1

[出力例]
? 1 1 1 2
? 1 2 1 1
! 2 2

[入力例]
2
0
1

[出力例]
? 1 1 1 2
? 1 2 1 1
! 1 2

[入力例]
2
1
0

[出力例]
? 1 1 1 2
? 1 2 1 1
! 2 1

[入力例]
2
0
0

[出力例]
? 1 1 1 2
? 1 2 1 1
! 1 1

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

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

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

[出力例]
? 1 5 1 10
? 1 3 1 10
? 4 4 1 10
? 1 10 1 5
? 1 10 1 3
? 1 10 4 4
! 5 5

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

[出力例]
? 1 6 1 12
? 7 9 1 12
? 7 8 1 12
? 7 7 1 12
? 1 12 1 6
? 1 12 7 9
? 1 12 10 11
? 1 12 10 10
! 8 11

※インタラクティブな問題のため, 入出力は, デバッグ時に使用したものを記載している.

[入力例]

[出力例]

? 1 1 1 2

? 1 2 1 1

! 2 2

[入力例]

[出力例]

? 1 1 1 2

? 1 2 1 1

! 1 2

[入力例]

[出力例]

? 1 1 1 2

? 1 2 1 1

! 2 1

[入力例]

[出力例]

? 1 1 1 2

? 1 2 1 1

! 1 1

[入力例]

[出力例]

? 1 4 1 7

? 1 2 1 7

? 3 3 1 7

? 1 7 1 4

? 1 7 5 6

? 1 7 5 5

! 4 6

[入力例]

[出力例]

? 1 5 1 10

? 1 3 1 10

? 4 4 1 10

? 1 10 1 5

? 1 10 1 3

? 1 10 4 4

! 5 5

[入力例]

[出力例]

? 1 6 1 12

? 7 9 1 12

? 7 8 1 12

? 7 7 1 12

? 1 12 1 6

? 1 12 7 9

? 1 12 10 11

? 1 12 10 10

! 8 11

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

2022年9月27日

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

C++の練習を兼ねて, AtCoder Beginner Contest 269 の問題C (Submask) ～問題D (Do use hexagon grid) を解いてみた.

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

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

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vl = vector<LL>;
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 main(){
    
    // 1. 入力情報.
    LL N;
    scanf("%lld", &N);
    
    // 2. 2 の 冪乗.
    vl cPow;
    cPow.pb(1LL);
    rep(i, 60) cPow.pb(cPow.back() << 1LL);
    // for(auto &p : cPow) printf("%lld\n", p);
    
    // 3. 1 の 位置.
    vi at;
    rep(i, 60) if((1LL << i) & N) at.pb(i);
    
    // 4. 出力.
    int n = at.size();
    rep(i, 1 << n){
        LL ans = 0;
        rep(j, n) if((1 << j) & i) ans += cPow[at[j]];
        printf("%lld\n", ans);
    }
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vl = vector<LL>;

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

// 1. 入力情報.

LL N;

scanf("%lld", &N);

// 2. 2 の冪乗.

vl cPow;

cPow.pb(1LL);

rep(i, 60) cPow.pb(cPow.back() << 1LL);

// for(auto &p : cPow) printf("%lld\n", p);

// 3. 1 の位置.

vi at;

rep(i, 60) if((1LL << i) & N) at.pb(i);

// 4. 出力.

int n = at.size();

rep(i, 1 << n){

LL ans = 0;

rep(j, n) if((1 << j) & i) ans += cPow[at[j]];

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

}

return 0;

}

[入力例]
11

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

[入力例]
0

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

[入力例]
576461302059761664

[出力例]
0
524288
549755813888
549756338176
576460752303423488
576460752303947776
576461302059237376
576461302059761664
※AtCoderテストケースより

[入力例]
25

[出力例]
0
1
8
9
16
17
24
25

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

576461302059761664

[出力例]

524288

549755813888

549756338176

576460752303423488

576460752303947776

576461302059237376

576461302059761664

※AtCoderテストケースより

[入力例]

[出力例]

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

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%d %d", &x[i], &y[i]);
    
    // 2. グラフ構築.
    vvi G(N);
    rep(i, N){
        repx(j, i + 1, N){
            // マス(X[i], Y[i]), マス(X[j], Y[j]) が 隣接するか？
            bool ok = false;
            
            // 左下.
            if(x[j] == x[i] - 1 && y[j] == y[i] - 1) ok = true;
            
            // 左.
            if(x[j] == x[i] - 1 && y[j] == y[i] + 0) ok = true;
            
            // 右下.
            if(x[j] == x[i] + 0 && y[j] == y[i] - 1) ok = true;
            
            // 左上.
            if(x[j] == x[i] + 0 && y[j] == y[i] + 1) ok = true;
            
            // 右.
            if(x[j] == x[i] + 1 && y[j] == y[i] + 0) ok = true;
            
            // 右上.
            if(x[j] == x[i] + 1 && y[j] == y[i] + 1) ok = true;
            
            // 隣接する場合は, 辺を追加.
            if(ok){
                G[i].pb(j);
                G[j].pb(i);
            }
        }
    }
    
    // 3. bfs.
    // https://ja.wikipedia.org/wiki/幅優先探索
    auto bfs = [&](vvi &G, int s, int* c, int l){
        // 空のキュー.
        queue<int> q;
        
        // 連結成分番号を設定.
        c[s] = l;
        
        // 探索地点 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, q.push(e);
        }
    };
    int c[N], idx = 0;
    rep(i, N) c[i] = 0;
    rep(i, N) if(!c[i]) bfs(G, i, c, ++idx);
    
    // 4. 出力.
    printf("%d\n", idx);
    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 x[1010], y[1010];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

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

// 2. グラフ構築.

vvi G(N);

rep(i, N){

repx(j, i + 1, N){

// マス(X[i], Y[i]), マス(X[j], Y[j]) が隣接するか？

bool ok = false;

// 左下.

if(x[j] == x[i] - 1 && y[j] == y[i] - 1) ok = true;

// 左.

if(x[j] == x[i] - 1 && y[j] == y[i] + 0) ok = true;

// 右下.

if(x[j] == x[i] + 0 && y[j] == y[i] - 1) ok = true;

// 左上.

if(x[j] == x[i] + 0 && y[j] == y[i] + 1) ok = true;

// 右.

if(x[j] == x[i] + 1 && y[j] == y[i] + 0) ok = true;

// 右上.

if(x[j] == x[i] + 1 && y[j] == y[i] + 1) ok = true;

// 隣接する場合は, 辺を追加.

if(ok){

G[i].pb(j);

G[j].pb(i);

}

// 3. bfs.

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

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

// 空のキュー.

queue<int> q;

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

c[s] = l;

// 探索地点 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, q.push(e);

}

};

int c[N], idx = 0;

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

rep(i, N) if(!c[i]) bfs(G, i, c, ++idx);

// 4. 出力.

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

return 0;

}

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

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

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

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

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

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

[入力例]
15
1 0
5 0
3 1
3 0
3 -1
-2 1
-2 0
-1 0
2 3
1 2
0 -2
-1 -3
6 3
5 2
6 2

[出力例]
7

[入力例]

-1 -1

0 1

0 2

1 0

1 2

2 0

[出力例]

※AtCoderテストケースより

[入力例]

5 0

4 1

-3 -4

-2 -5

[出力例]

※AtCoderテストケースより

[入力例]

2 1

2 -1

1 0

3 1

1 -1

[出力例]

※AtCoderテストケースより

[入力例]

1 0

5 0

3 1

3 0

3 -1

-2 1

-2 0

-1 0

2 3

1 2

0 -2

-1 -3

6 3

5 2

6 2

[出力例]

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

2022年9月25日

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

C++の練習を兼ねて, AtCoder Beginner Contest 270 の問題C (Simple path) ～問題E (Apple Baskets on Circle) を解いてみた.

■感想.
1. 問題Dは, 想定誤解法から抜け出せなかったので, 解説を参考に, AC版に到達できたと思う.
2. 問題Dで, 苦手な動的計画法の訓練を積めたので, 非常に良かったと思う.
3. 個人的には, 問題C で, 幅優先探索, 問題E で, 二分探索の復習が出来たので, 非常に良かったと思う.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

■C++版プログラム(問題C／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 main(){
    
    // 1. 入力情報.
    int N, X, Y;
    scanf("%d %d %d", &N, &X, &Y);
    --X, --Y;
    vvi G(N);
    rep(i, N - 1){
        int u, v;
        scanf("%d %d", &u, &v);
        --u, --v;
        G[u].pb(v);
        G[v].pb(u);
    }
    
    // 2. bfs.
    // https://ja.wikipedia.org/wiki/幅優先探索
    auto bfs = [&](vvi &G, int s, int* d){
        // 空のキュー.
        queue<int> q;
        
        // 探索地点 s をキュー q に追加.
        q.push(s);
        while(!q.empty()){
            // キューから取り出す.
            int u = q.front();
            q.pop();
            
            // 隣接頂点をチェック.
            for(auto &v : G[u]) if(!d[v] && v != s) d[v] = d[u] + 1, q.push(v);
        }
    };
    int d[N];
    rep(i, N) d[i] = 0;
    bfs(G, X, d);
    
    // 3. 最短経路.
    auto f = [&](vvi &G, int s, int* d, vi& r){
        // 空のキュー.
        queue<int> q;
        
        // 探索地点 s をキュー q に追加.
        q.push(s);
        r.pb(s);
        while(!q.empty()){
            // キューから取り出す.
            int u = q.front();
            q.pop();
            
            // 取り出した要素を処理.
            for(auto &v : G[u]){
                // 距離 が 1 小さい場合に, 保存.
                if(d[v] == d[u] - 1){
                    r.pb(v);
                    q.push(v);
                    break;
                }
            }
        }
    };
    vi ans;
    f(G, Y, d, ans);
    
    // 4. 出力.
    int n = ans.size();
    repr(i, n - 1, 0) printf("%d%s", ans[i] + 1, i ? " " : "\n");
    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 main(){

// 1. 入力情報.

int N, X, Y;

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

--X, --Y;

vvi G(N);

rep(i, N - 1){

int u, v;

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

--u, --v;

G[u].pb(v);

G[v].pb(u);

}

// 2. bfs.

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

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

// 空のキュー.

queue<int> q;

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

q.push(s);

while(!q.empty()){

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

int u = q.front();

q.pop();

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

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

}

};

int d[N];

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

bfs(G, X, d);

// 3. 最短経路.

auto f = [&](vvi &G, int s, int* d, vi& r){

// 空のキュー.

queue<int> q;

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

q.push(s);

r.pb(s);

while(!q.empty()){

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

int u = q.front();

q.pop();

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

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

// 距離が 1 小さい場合に, 保存.

if(d[v] == d[u] - 1){

r.pb(v);

q.push(v);

break;

}

};

vi ans;

f(G, Y, d, ans);

// 4. 出力.

int n = ans.size();

repr(i, n - 1, 0) printf("%d%s", ans[i] + 1, i ? " " : "\n");

return 0;

}

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

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

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

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

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

[出力例]
5 7 6 3

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

[出力例]
12 14 10 11 8 6 5

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

[出力例]
10 1 19 8 20 13 18

[入力例]

5 2 5

1 2

1 3

3 4

3 5

[出力例]

2 1 3 5

※AtCoderテストケースより

[入力例]

6 1 2

3 1

2 5

1 2

4 1

2 6

[出力例]

1 2

※AtCoderテストケースより

[入力例]

7 5 3

1 2

7 2

7 6

7 5

3 6

6 4

[出力例]

5 7 6 3

[入力例]

15 12 5

11 10

11 8

10 13

14 10

15 14

12 14

8 7

8 6

6 1

6 5

1 2

1 9

9 3

9 4

[出力例]

12 14 10 11 8 6 5

[入力例]

20 10 18

5 4

6 4

4 7

7 8

8 9

8 19

8 20

19 1

19 2

19 3

1 10

20 11

20 13

20 14

13 12

13 15

13 16

13 17

13 18

[出力例]

10 1 19 8 20 13 18

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

// 解き直し.
// https://atcoder.jp/contests/abc270/editorial/4850
// 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[101], dp[10101];

int main(){
    
    // 1. 入力情報.
    int N, K;
    scanf("%d %d", &N, &K);
    rep(i, K) scanf("%d", &a[i]);
    
    // 2. ゲーム.
    rep(i, N + 1) rep(j, K + 1) if(i - a[j] >= 0) dp[i] = max(dp[i], a[j] + (i - a[j]) - dp[i - a[j]]);
    
    // 3. 出力.
    printf("%d\n", dp[N]);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc270/editorial/4850

// 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[101], dp[10101];

int main(){

// 1. 入力情報.

int N, K;

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

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

// 2. ゲーム.

rep(i, N + 1) rep(j, K + 1) if(i - a[j] >= 0) dp[i] = max(dp[i], a[j] + (i - a[j]) - dp[i - a[j]]);

// 3. 出力.

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

return 0;

}

[入力例]
10 2
1 4

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

[入力例]
11 4
1 2 3 6

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

[入力例]
10000 10
1 2 4 8 16 32 64 128 256 512

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

[入力例]
2022 15
1 3 10 11 16 18 20 21 24 27 30 33 39 43 51

[出力例]
1020

[入力例]
10000 25
1 4 6 11 17 25 30 36 39 41 50 53 55 60 63 70 76 81 87 88 91 93 98 103 111

[出力例]
5005

[入力例]

10 2

1 4

[出力例]

※AtCoderテストケースより

[入力例]

11 4

1 2 3 6

[出力例]

※AtCoderテストケースより

[入力例]

10000 10

1 2 4 8 16 32 64 128 256 512

[出力例]

5136

※AtCoderテストケースより

[入力例]

2022 15

1 3 10 11 16 18 20 21 24 27 30 33 39 43 51

[出力例]

1020

[入力例]

10000 25

1 4 6 11 17 25 30 36 39 41 50 53 55 60 63 70 76 81 87 88 91 93 98 103 111

[出力例]

5005

■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--)
LL a[202020];

int main(){
    
    // 1. 入力情報.
    int N;
    LL K;
    scanf("%d %lld", &N, &K);
    rep(i, N) scanf("%lld", &a[i]);
    
    // 2. 評価関数.
    auto f = [&](LL m) -> bool {
        // 2-1. りんごを, 最大 m 個ずつ食べた.
        LL cur = 0;
        rep(i, N) cur += min(a[i], m);
        
        // 2-2. 判定結果.
        return (cur <= K);
    };
    
    // 3. 二分探索で確認してみる.
    LL l = -1, h = 2e12 + 1, m;
    while(l + 1 < h){
        LL m = (h + l) >> 1;
        if(f(m)) l = m;
        else     h = m;
    }
    
    // 4. l 周後は？
    rep(i, N){
        K -= min(a[i], l);
        a[i] -= min(a[i], l);
    }
    
    // 5. まだりんごが食べられる場合.
    rep(i, N){
        if(K == 0) break;
        K -= min(a[i], 1LL);
        a[i] -= min(a[i], 1LL);
    }
    
    // 6. 出力.
    rep(i, N) printf("%lld%s", a[i], (i < N - 1) ? " " : "\n");
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

LL a[202020];

int main(){

// 1. 入力情報.

int N;

LL K;

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

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

// 2. 評価関数.

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

// 2-1. りんごを, 最大 m 個ずつ食べた.

LL cur = 0;

rep(i, N) cur += min(a[i], m);

// 2-2. 判定結果.

return (cur <= K);

};

// 3. 二分探索で確認してみる.

LL l = -1, h = 2e12 + 1, m;

while(l + 1 < h){

LL m = (h + l) >> 1;

if(f(m)) l = m;

else h = m;

}

// 4. l 周後は？

rep(i, N){

K -= min(a[i], l);

a[i] -= min(a[i], l);

}

// 5. まだりんごが食べられる場合.

rep(i, N){

if(K == 0) break;

K -= min(a[i], 1LL);

a[i] -= min(a[i], 1LL);

}

// 6. 出力.

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

return 0;

}

[入力例]
3 3
1 3 0

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

[入力例]
2 1000000000000
1000000000000 1000000000000

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

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

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

[入力例]
30 2022
92 128 58 79 83 54 88 66 98 84 116 53 103 70 53 72 82 121 97 61 107 51 115 56 71 87 90 105 12 92

[出力例]
17 53 0 4 8 0 13 0 23 9 41 0 28 0 0 0 7 46 22 0 32 0 41 0 0 13 16 31 0 18

[入力例]
300 20220925
84179 62870 97544 31943 77523 34777 100072 33029 79036 95524 104597 50581 69487 97904 68416 93643 49670 54396 94721 82777 78561 108339 94265 88431 49009 84955 60155 53688 36556 109031 44070 32236 76699 49332 101983 33841 36540 42339 69883 45574 54482 109013 33569 62492 32785 70787 56746 97920 94729 56586 65349 68738 35679 37124 53041 108899 37692 70719 34887 34074 32904 100389 47716 95627 52623 103358 99094 80182 103888 105515 54187 79559 65358 82494 32233 42767 65003 64016 42905 86831 87898 103926 75099 36521 42039 32751 47762 101831 79229 61616 94328 69907 96916 69666 35182 51593 107696 56703 42137 95111 60545 51030 86882 65570 51921 95783 39520 105441 67277 49068 38458 96961 41332 106481 102715 68835 108373 51080 94093 30166 90688 104360 67362 77686 102744 75310 74611 43536 93262 73873 34016 36757 40946 66899 89744 53575 39890 98110 99970 52393 69725 44696 92764 84847 67233 75814 93908 48517 100135 40835 77002 48630 42000 45642 68531 85979 68151 34428 57676 95055 67407 33687 72138 65996 60389 59174 106243 87415 72825 78073 63304 95889 99888 64730 59475 53716 73804 76717 30441 102873 69961 63113 92081 88353 45839 86385 72020 88993 64178 103156 49831 79480 105906 32582 38832 39724 77070 81396 61516 94600 86791 61350 50591 87229 37942 83047 34594 109389 71897 107547 71122 49263 107606 53922 42278 50771 35411 64597 31771 108308 35561 56434 41777 59937 104314 87334 84610 41387 72072 63971 53982 53348 83283 95228 102347 69586 67197 107944 91309 70085 69264 76873 100509 74832 79701 78740 72639 70859 75665 36443 103241 106616 55615 48652 75884 96568 35732 43139 65420 107881 33255 101503 83393 45436 48280 80391 79787 94859 94050 48323 33802 52520 32577 74861 51716 107031 94177 60988 35108 30149 34713 58798 56565 82377 42850 33105 76773 60219 73108 35524 65150 48358 37679 97556 60253 43450 64260 52765 70123 58630

[出力例]
0 0 192 0 0 0 2720 0 0 0 7245 0 0 552 0 0 0 0 0 0 0 10987 0 0 0 0 0 0 0 11679 0 0 0 0 4631 0 0 0 0 0 0 11661 0 0 0 0 0 568 0 0 0 0 0 0 0 11547 0 0 0 0 0 3037 0 0 0 6006 1742 0 6536 8163 0 0 0 0 0 0 0 0 0 0 0 6574 0 0 0 0 0 4479 0 0 0 0 0 0 0 0 10344 0 0 0 0 0 0 0 0 0 0 8089 0 0 0 0 0 9129 5364 0 11022 0 0 0 0 7009 0 0 5393 0 0 0 0 0 0 0 0 0 0 0 0 759 2619 0 0 0 0 0 0 0 0 0 2784 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 8892 0 0 0 0 0 2537 0 0 0 0 0 0 5522 0 0 0 0 0 0 0 0 0 5805 0 0 8555 0 0 0 0 0 0 0 0 0 0 0 0 0 0 12038 0 10196 0 0 10255 0 0 0 0 0 0 10957 0 0 0 0 6963 0 0 0 0 0 0 0 0 0 4996 0 0 10593 0 0 0 0 3158 0 0 0 0 0 0 0 5890 9265 0 0 0 0 0 0 0 10530 0 4152 0 0 0 0 0 0 0 0 0 0 0 0 0 9680 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 205 0 0 0 0 0 0

[入力例]

3 3

1 3 0

[出力例]

0 1 0

※AtCoderテストケースより

[入力例]

2 1000000000000

1000000000000 1000000000000

[出力例]

500000000000 500000000000

※AtCoderテストケースより

[入力例]

10 21

3 1 4 1 5 9 2 6 5 3

[出力例]

0 0 1 0 2 7 0 4 3 1

[入力例]

30 2022

92 128 58 79 83 54 88 66 98 84 116 53 103 70 53 72 82 121 97 61 107 51 115 56 71 87 90 105 12 92

[出力例]

17 53 0 4 8 0 13 0 23 9 41 0 28 0 0 0 7 46 22 0 32 0 41 0 0 13 16 31 0 18

[入力例]

300 20220925

84179 62870 97544 31943 77523 34777 100072 33029 79036 95524 104597 50581 69487 97904 68416 93643 49670 54396 94721 82777 78561 108339 94265 88431 49009 84955 60155 53688 36556 109031 44070 32236 76699 49332 101983 33841 36540 42339 69883 45574 54482 109013 33569 62492 32785 70787 56746 97920 94729 56586 65349 68738 35679 37124 53041 108899 37692 70719 34887 34074 32904 100389 47716 95627 52623 103358 99094 80182 103888 105515 54187 79559 65358 82494 32233 42767 65003 64016 42905 86831 87898 103926 75099 36521 42039 32751 47762 101831 79229 61616 94328 69907 96916 69666 35182 51593 107696 56703 42137 95111 60545 51030 86882 65570 51921 95783 39520 105441 67277 49068 38458 96961 41332 106481 102715 68835 108373 51080 94093 30166 90688 104360 67362 77686 102744 75310 74611 43536 93262 73873 34016 36757 40946 66899 89744 53575 39890 98110 99970 52393 69725 44696 92764 84847 67233 75814 93908 48517 100135 40835 77002 48630 42000 45642 68531 85979 68151 34428 57676 95055 67407 33687 72138 65996 60389 59174 106243 87415 72825 78073 63304 95889 99888 64730 59475 53716 73804 76717 30441 102873 69961 63113 92081 88353 45839 86385 72020 88993 64178 103156 49831 79480 105906 32582 38832 39724 77070 81396 61516 94600 86791 61350 50591 87229 37942 83047 34594 109389 71897 107547 71122 49263 107606 53922 42278 50771 35411 64597 31771 108308 35561 56434 41777 59937 104314 87334 84610 41387 72072 63971 53982 53348 83283 95228 102347 69586 67197 107944 91309 70085 69264 76873 100509 74832 79701 78740 72639 70859 75665 36443 103241 106616 55615 48652 75884 96568 35732 43139 65420 107881 33255 101503 83393 45436 48280 80391 79787 94859 94050 48323 33802 52520 32577 74861 51716 107031 94177 60988 35108 30149 34713 58798 56565 82377 42850 33105 76773 60219 73108 35524 65150 48358 37679 97556 60253 43450 64260 52765 70123 58630

[出力例]

0 0 192 0 0 0 2720 0 0 0 7245 0 0 552 0 0 0 0 0 0 0 10987 0 0 0 0 0 0 0 11679 0 0 0 0 4631 0 0 0 0 0 0 11661 0 0 0 0 0 568 0 0 0 0 0 0 0 11547 0 0 0 0 0 3037 0 0 0 6006 1742 0 6536 8163 0 0 0 0 0 0 0 0 0 0 0 6574 0 0 0 0 0 4479 0 0 0 0 0 0 0 0 10344 0 0 0 0 0 0 0 0 0 0 8089 0 0 0 0 0 9129 5364 0 11022 0 0 0 0 7009 0 0 5393 0 0 0 0 0 0 0 0 0 0 0 0 759 2619 0 0 0 0 0 0 0 0 0 2784 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 8892 0 0 0 0 0 2537 0 0 0 0 0 0 5522 0 0 0 0 0 0 0 0 0 5805 0 0 8555 0 0 0 0 0 0 0 0 0 0 0 0 0 0 12038 0 10196 0 0 10255 0 0 0 0 0 0 10957 0 0 0 0 6963 0 0 0 0 0 0 0 0 0 4996 0 0 10593 0 0 0 0 3158 0 0 0 0 0 0 0 5890 9265 0 0 0 0 0 0 0 10530 0 4152 0 0 0 0 0 0 0 0 0 0 0 0 0 9680 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 205 0 0 0 0 0 0

■参照サイト
トヨタ自動車プログラミングコンテスト2022(AtCoder Beginner Contest 270)

2022年9月24日

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

C++の練習を兼ねて, AtCoder Beginner Contest 266 の問題F (Well-defined Path Queries on a Namori) を解いてみた.

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

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

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

// 解き直し.
// https://atcoder.jp/contests/abc266/editorial/4698
// 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
set<int> C[202020];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    vvi G(N);
    rep(i, N){
        int u, v;
        scanf("%d %d", &u, &v);
        --u;
        --v;
        
        // 通常のグラフ.
        G[u].pb(v);
        G[v].pb(u);
        
        // 閉路検出用.
        C[u].insert(v);
        C[v].insert(u);
    }
    
    // 2. 閉路検出.
    queue<int> q;
    rep(i, N) if(C[i].size() == 1) q.push(i);
    while(!q.empty()){
        // キューから取り出す.
        int u = q.front();
        q.pop();
        
        // 取り出した要素を処理.
        for(auto &v : C[u]){
            // 辺(v, u) を 削除.
            C[v].erase(u);
            
            // 保存.
            if(C[v].size() == 1) q.push(v);
        }
        
        // 辺(u, v) を 削除.
        C[u].clear();
    }
    
    // 3. 閉路を構成する頂点.
    set<int> st;
    rep(i, N) if(C[i].size()) st.insert(i);
    
    // 4. bfs.
    // https://ja.wikipedia.org/wiki/幅優先探索
    auto bfs = [&](vvi &G, int s, int* c, int l){
        // 空のキュー.
        queue<int> q;
        
        // 連結成分番号を設定.
        c[s] = l;
        
        // 探索地点 s をキュー q に追加.
        q.push(s);
        while(!q.empty()){
            // キューから取り出す.
            int u = q.front();
            q.pop();
            
            // 取り出した要素を処理.
            for(auto &e : G[u]) if(!c[e] && e != s && !st.count(e)) c[e] = l, q.push(e);
        }
    };
    
    // 5. グループ分け.
    int c[N], idx = 0;
    rep(i, N) c[i] = 0;
    rep(i, N) if(st.count(i) && !c[i]) bfs(G, i, c, ++idx);
    
    // 6. クエリ回答.
    int Q;
    scanf("%d", &Q);
    rep(i, Q){
        // 6-1. クエリ入力情報.
        int x, y;
        scanf("%d %d", &x, &y);
        --x;
        --y;
        
        // 6-2. 頂点 x, y が, ともに閉路上にある.
        if(st.count(x) && st.count(y)){
            puts("No");
            continue;
        }
        
        // 6-3. 上記以外.
        printf("%s\n", (c[x] == c[y]) ? "Yes" : "No");
    }
    return 0;
    
}

100

101

102

103

104

105

106

107

108

// 解き直し.

// https://atcoder.jp/contests/abc266/editorial/4698

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

set<int> C[202020];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

vvi G(N);

rep(i, N){

int u, v;

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

--u;

--v;

// 通常のグラフ.

G[u].pb(v);

G[v].pb(u);

// 閉路検出用.

C[u].insert(v);

C[v].insert(u);

}

// 2. 閉路検出.

queue<int> q;

rep(i, N) if(C[i].size() == 1) q.push(i);

while(!q.empty()){

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

int u = q.front();

q.pop();

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

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

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

C[v].erase(u);

// 保存.

if(C[v].size() == 1) q.push(v);

}

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

C[u].clear();

}

// 3. 閉路を構成する頂点.

set<int> st;

rep(i, N) if(C[i].size()) st.insert(i);

// 4. bfs.

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

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

// 空のキュー.

queue<int> q;

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

c[s] = l;

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

q.push(s);

while(!q.empty()){

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

int u = q.front();

q.pop();

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

for(auto &e : G[u]) if(!c[e] && e != s && !st.count(e)) c[e] = l, q.push(e);

}

};

// 5. グループ分け.

int c[N], idx = 0;

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

rep(i, N) if(st.count(i) && !c[i]) bfs(G, i, c, ++idx);

// 6. クエリ回答.

int Q;

scanf("%d", &Q);

rep(i, Q){

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

int x, y;

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

--x;

--y;

// 6-2. 頂点 x, y が, ともに閉路上にある.

if(st.count(x) && st.count(y)){

puts("No");

continue;

}

// 6-3. 上記以外.

printf("%s\n", (c[x] == c[y]) ? "Yes" : "No");

}

return 0;

}

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

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

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

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

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

[出力例]
No
No
No

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

[出力例]
No
No
Yes

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

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

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

[入力例]

1 2

2 3

1 3

1 4

2 5

1 2

1 4

1 5

[出力例]

Yes

※AtCoderテストケースより

[入力例]

3 5

5 7

4 8

2 9

1 2

7 9

1 6

4 10

2 5

2 10

1 8

6 9

8 10

6 8

3 10

3 9

1 10

5 8

1 10

7 8

[出力例]

Yes

※AtCoderテストケースより

[入力例]

1 2

1 3

2 3

1 2

1 3

2 3

[出力例]

[入力例]

1 2

1 3

2 3

3 4

1 2

2 4

3 4

[出力例]

Yes

[入力例]

1 5

1 6

1 13

2 3

2 4

2 20

5 7

5 20

6 10

6 17

7 8

7 16

9 10

9 11

9 12

10 20

13 14

13 15

17 18

17 19

1 5

1 15

1 14

6 17

6 10

3 20

5 10

7 11

6 18

1 20

[出力例]

Yes

■参照サイト
AtCoder Beginner Contest 266

2022年9月23日

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

C++の練習を兼ねて, AtCoder Beginner Contest 266 の問題C (Convex Quadrilateral) ～問題E (Throwing the Die) を解いてみた.

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

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

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

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

int main(){
    
    // 1. 入力情報.
    int ax, ay, bx, by, cx, cy, dx, dy;
    scanf("%d %d %d %d %d %d %d %d", &ax, &ay, &bx, &by, &cx, &cy, &dx, &dy);
    
    // 2. 判定.
    // 対角線 AC, BD の 交点 X として考える.
    // p * (abx - adx) + adx = k * acx
    // p * (aby - ady) + ady = k * acy
    // -> (aby - ady) * adx - (abx - adx) * ady = k * (acx * (aby - ady) - acy * (abx - adx))
    // 
    // 2-1. AX = k * AC (0 < k < 1) が 存在するか？
    P ab = {bx - ax, by - ay};
    P ac = {cx - ax, cy - ay};
    P ad = {dx - ax, dy - ay};
    int kacMol = (ab.b - ad.b) * ad.a - (ab.a - ad.a) * ad.b;
    int kacDen = ac.a * (ab.b - ad.b) - ac.b * (ab.a - ad.a);
    bool ng = (kacMol == 0);
    ng |= (kacDen == 0);
    ng |= (kacMol < 0 && kacDen > 0);
    ng |= (kacMol > 0 && kacDen < 0);
    ng |= (abs(kacDen) <= abs(kacMol));
    if(ng){
        puts("No");
        return 0;
    }
    
    // 2-2. BX = k * BD (0 < k < 1) が 存在するか？
    P ba = {ax - bx, ay - by};
    P bc = {cx - bx, cy - by};
    P bd = {dx - bx, dy - by};
    int kbdMol = (ba.b - bc.b) * bc.a - (ba.a - bc.a) * bc.b;
    int kbdDen = bd.a * (ba.b - bc.b) - bd.b * (ba.a - bc.a);
    ng = (kbdMol == 0);
    ng |= (kbdDen == 0);
    ng |= (kbdMol < 0 && kbdDen > 0);
    ng |= (kbdMol > 0 && kbdDen < 0);
    ng |= (abs(kbdDen) <= abs(kbdMol));
    if(ng){
        puts("No");
        return 0;
    }
    
    // 2-3. 上記以外.
    puts("Yes");
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using P = pair<int, int>;

#define a first

#define b second

int main(){

// 1. 入力情報.

int ax, ay, bx, by, cx, cy, dx, dy;

scanf("%d %d %d %d %d %d %d %d", &ax, &ay, &bx, &by, &cx, &cy, &dx, &dy);

// 2. 判定.

// 対角線 AC, BD の交点 X として考える.

// p * (abx - adx) + adx = k * acx

// p * (aby - ady) + ady = k * acy

// -> (aby - ady) * adx - (abx - adx) * ady = k * (acx * (aby - ady) - acy * (abx - adx))

// 2-1. AX = k * AC (0 < k < 1) が存在するか？

P ab = {bx - ax, by - ay};

P ac = {cx - ax, cy - ay};

P ad = {dx - ax, dy - ay};

int kacMol = (ab.b - ad.b) * ad.a - (ab.a - ad.a) * ad.b;

int kacDen = ac.a * (ab.b - ad.b) - ac.b * (ab.a - ad.a);

bool ng = (kacMol == 0);

ng |= (kacDen == 0);

ng |= (kacMol < 0 && kacDen > 0);

ng |= (kacMol > 0 && kacDen < 0);

ng |= (abs(kacDen) <= abs(kacMol));

if(ng){

puts("No");

return 0;

}

// 2-2. BX = k * BD (0 < k < 1) が存在するか？

P ba = {ax - bx, ay - by};

P bc = {cx - bx, cy - by};

P bd = {dx - bx, dy - by};

int kbdMol = (ba.b - bc.b) * bc.a - (ba.a - bc.a) * bc.b;

int kbdDen = bd.a * (ba.b - bc.b) - bd.b * (ba.a - bc.a);

ng = (kbdMol == 0);

ng |= (kbdDen == 0);

ng |= (kbdMol < 0 && kbdDen > 0);

ng |= (kbdMol > 0 && kbdDen < 0);

ng |= (abs(kbdDen) <= abs(kbdMol));

if(ng){

puts("No");

return 0;

}

// 2-3. 上記以外.

puts("Yes");

return 0;

}

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

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

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

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

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

[出力例]
Yes

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

[出力例]
No

[入力例]
51 31
25 32
-7 18
67 -23

[出力例]
Yes

[入力例]

0 0

1 0

1 1

0 1

[出力例]

Yes

※AtCoderテストケースより

[入力例]

0 0

1 1

-1 0

1 -1

[出力例]

※AtCoderテストケースより

[入力例]

3 1

2 2

-1 0

1 -2

[出力例]

Yes

[入力例]

1 3

1 -1

4 0

2 2

[出力例]

[入力例]

51 31

25 32

-7 18

67 -23

[出力例]

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 int MAX = 101010;
LL b[MAX][5], dp[MAX][5];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N){
        int t, x;
        LL a;
        scanf("%d %d %lld", &t, &x, &a);
        b[t][x] = a;
    }
    
    // 2. 初期化.
    rep(i, 101010) rep(j, 5) dp[i][j] = -1;
    dp[0][0] = 0;
    
    // 3. dp更新.
    rep(i, 101010){
        rep(j, 5){
            // 前回以前が, 有り得る行動だった場合.
            if(dp[i][j] >= 0){
                dp[i + 1][j - (j > 0)] = max(dp[i + 1][j - (j > 0)], dp[i][j] + b[i][j]);
                dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + b[i][j]);
                dp[i + 1][j + (j < 4)] = max(dp[i + 1][j + (j < 4)], dp[i][j] + b[i][j]);
            }
            
        }
    }
    
    // 4. 出力.
    printf("%lld\n", max({dp[MAX][0], dp[MAX][1], dp[MAX][2], dp[MAX][3], dp[MAX][4]}));
    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 int MAX = 101010;

LL b[MAX][5], dp[MAX][5];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

rep(i, N){

int t, x;

LL a;

scanf("%d %d %lld", &t, &x, &a);

b[t][x] = a;

}

// 2. 初期化.

rep(i, 101010) rep(j, 5) dp[i][j] = -1;

dp[0][0] = 0;

// 3. dp更新.

rep(i, 101010){

rep(j, 5){

// 前回以前が, 有り得る行動だった場合.

if(dp[i][j] >= 0){

dp[i + 1][j - (j > 0)] = max(dp[i + 1][j - (j > 0)], dp[i][j] + b[i][j]);

dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + b[i][j]);

dp[i + 1][j + (j < 4)] = max(dp[i + 1][j + (j < 4)], dp[i][j] + b[i][j]);

}

// 4. 出力.

printf("%lld\n", max({dp[MAX][0], dp[MAX][1], dp[MAX][2], dp[MAX][3], dp[MAX][4]}));

return 0;

}

[入力例]
3
1 0 100
3 3 10
5 4 1

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

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

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

[入力例]
10
1 4 602436426
2 1 623690081
3 3 262703497
4 4 628894325
5 3 450968417
6 1 161735902
7 1 707723857
8 2 802329211
9 0 317063340
10 2 125660016

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

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

[出力例]
13

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

[出力例]
55

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

[出力例]
222

[入力例]

1 0 100

3 3 10

5 4 1

[出力例]

101

※AtCoderテストケースより

[入力例]

1 4 1

2 4 1

3 4 1

[出力例]

※AtCoderテストケースより

[入力例]

1 4 602436426

2 1 623690081

3 3 262703497

4 4 628894325

5 3 450968417

6 1 161735902

7 1 707723857

8 2 802329211

9 0 317063340

10 2 125660016

[出力例]

2978279323

※AtCoderテストケースより

[入力例]

1 0 3

3 1 1

4 2 4

7 1 1

8 3 5

[出力例]

[入力例]

1 0 3

3 4 6

4 1 5

5 3 9

7 3 14

10 2 3

12 1 5

15 4 8

16 4 13

17 1 12

[出力例]

[入力例]

1 0 7

2 2 9

3 4 12

4 2 9

5 2 11

6 1 15

7 4 16

8 0 11

9 1 12

10 4 7

11 3 12

12 0 10

13 3 8

14 0 17

15 1 10

16 4 9

17 2 12

18 2 20

19 0 10

20 2 13

21 0 13

22 4 10

23 1 12

24 3 19

25 2 3

26 0 11

27 4 7

28 3 19

29 2 5

30 4 13

[出力例]

222

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

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

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    
    // 2. ゲーム.
    double bef = 0.0, cur;
    rep(i, N){
        // 今回分更新.
        cur = 0;
        cur += max(bef, 1.0) / 6.0;
        cur += max(bef, 2.0) / 6.0;
        cur += max(bef, 3.0) / 6.0;
        cur += max(bef, 4.0) / 6.0;
        cur += max(bef, 5.0) / 6.0;
        cur += max(bef, 6.0) / 6.0;
        
        // 前回分更新.
        bef = cur;
    }
    
    // 3. 出力.
    printf("%.10lf\n", cur);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc266/editorial/4662

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

// 2. ゲーム.

double bef = 0.0, cur;

rep(i, N){

// 今回分更新.

cur = 0;

cur += max(bef, 1.0) / 6.0;

cur += max(bef, 2.0) / 6.0;

cur += max(bef, 3.0) / 6.0;

cur += max(bef, 4.0) / 6.0;

cur += max(bef, 5.0) / 6.0;

cur += max(bef, 6.0) / 6.0;

// 前回分更新.

bef = cur;

}

// 3. 出力.

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

return 0;

}

[入力例]
1

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

[入力例]
2

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

[入力例]
10

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

[入力例]
3

[出力例]
4.6666666667

[入力例]
5

[出力例]
5.1296296296

[入力例]
20

[出力例]
5.9435082007

[入力例]
100

[出力例]
5.9999999738

[入力例]

[出力例]

3.5000000000

※AtCoderテストケースより

[入力例]

[出力例]

4.2500000000

※AtCoderテストケースより

[入力例]

[出力例]

5.6502176688

※AtCoderテストケースより

[入力例]

[出力例]

4.6666666667

[入力例]

[出力例]

5.1296296296

[入力例]

[出力例]

5.9435082007

[入力例]

100

[出力例]

5.9999999738

■参照サイト
AtCoder Beginner Contest 266

カテゴリー: C++

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

C++の練習を兼ねて, AtCoder Beginner Contest 271 の問題F (XOR on Grid Path) を解いてみた.

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

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

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

C++の練習を兼ねて, AtCoder Beginner Contest 271 の問題C (Manga) ～問題D (Flip and Adjust) を解いてみた.

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

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

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

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

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

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

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

C++の練習を兼ねて, AtCoder Beginner Contest 269 の問題C (Submask) ～問題D (Do use hexagon grid) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 270 の問題C (Simple path) ～問題E (Apple Baskets on Circle) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 266 の問題F (Well-defined Path Queries on a Namori) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 266 の問題C (Convex Quadrilateral) ～問題E (Throwing the Die) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 271 の 問題F (XOR on Grid Path) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 271 の 問題C (Manga) ～ 問題D (Flip and Adjust) を解いてみた.

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

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

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

C++の練習を兼ねて, AtCoder Beginner Contest 269 の 問題C (Submask) ～ 問題D (Do use hexagon grid) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 270 の 問題C (Simple path) ～ 問題E (Apple Baskets on Circle) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 266 の 問題F (Well-defined Path Queries on a Namori) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 266 の 問題C (Convex Quadrilateral) ～ 問題E (Throwing the Die) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 271 の問題F (XOR on Grid Path) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 271 の問題C (Manga) ～問題D (Flip and Adjust) を解いてみた.

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

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

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

C++の練習を兼ねて, AtCoder Beginner Contest 269 の問題C (Submask) ～問題D (Do use hexagon grid) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 270 の問題C (Simple path) ～問題E (Apple Baskets on Circle) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 266 の問題F (Well-defined Path Queries on a Namori) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 266 の問題C (Convex Quadrilateral) ～問題E (Throwing the Die) を解いてみた.