C++ | 個人用メモ帳

2022年1月26日

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

C++の練習を兼ねて, JOIG 2021/2022 本選過去問の問題D (いちご 2 (Strawberry 2)) を解いてみた.

■感想.
1. 問題Dは, 方針を絞り込めたので, AC版に到達できたので十分だと思う.
2. 個人的には, 数え上げの方法に, std::map を使う方針が, 面白く感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

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

int main(){
    
    // 1. 入力情報.
    int H, W, N;
    scanf("%d %d %d", &H, &W, &N);
    map<P, int> m;
    rep(i, N){
        scanf("%d %d", &a[i], &b[i]);
        m[{a[i], b[i]}]++;
    }
    
    // 2. 取得可能ないちごの最大数は？
    int ans = 0;
    rep(i, N){
        // i番目のいちごを基準に, 81通りチェック.
        for(auto dh : {-2, -1, 0}){
            for(auto dw : {-2, -1, 0}){
                // (基準とする)左上の位置.
                int hBase = a[i] + dh;
                int wBase = b[i] + dw;
                
                // 縦3行, 横3行 の いちごを集計.
                int t = 0;
                rep(h, 3){
                    rep(w, 3){
                        int hCur = hBase + h;
                        int wCur = wBase + w;
                        if(hCur >= 1 && wCur >= 1 && hCur <= H && wCur <= W) t += m[{hCur, wCur}];
                    }
                }
                
                // 最大値更新.
                ans = max(ans, t);
            }
        }
    }
    
    // 3. 出力.
    printf("%d\n", ans);
    return 0;

}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

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

int a[60606], b[60606];

int main(){

// 1. 入力情報.

int H, W, N;

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

map<P, int> m;

rep(i, N){

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

m[{a[i], b[i]}]++;

}

// 2. 取得可能ないちごの最大数は？

int ans = 0;

rep(i, N){

// i番目のいちごを基準に, 81通りチェック.

for(auto dh : {-2, -1, 0}){

for(auto dw : {-2, -1, 0}){

// (基準とする)左上の位置.

int hBase = a[i] + dh;

int wBase = b[i] + dw;

// 縦3行, 横3行のいちごを集計.

int t = 0;

rep(h, 3){

rep(w, 3){

int hCur = hBase + h;

int wCur = wBase + w;

if(hCur >= 1 && wCur >= 1 && hCur <= H && wCur <= W) t += m[{hCur, wCur}];

}

// 最大値更新.

ans = max(ans, t);

}

// 3. 出力.

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

return 0;

}

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

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

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

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

[入力例]
3 99999
9
1 77813
2 77813
3 77813
1 77814
2 77814
3 77814
1 77815
2 77815
3 77815

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

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

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

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

[出力例]
18

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

[入力例]

4 5

1 1

1 5

2 2

2 4

3 3

4 2

4 4

[出力例]

※AtCoderテストケースより

[入力例]

3 5

1 1

1 2

2 1

2 4

3 4

[出力例]

※AtCoderテストケースより

[入力例]

3 99999

1 77813

2 77813

3 77813

1 77814

2 77814

3 77814

1 77815

2 77815

3 77815

[出力例]

※AtCoderテストケースより

[入力例]

11 11

7 7

6 11

5 7

8 8

9 9

5 5

8 4

4 4

4 8

2 6

1 6

6 2

3 3

9 3

7 5

6 1

10 6

6 10

11 6

3 9

[出力例]

※AtCoderテストケースより

[入力例]

6 7

6 3

4 5

3 3

3 2

1 7

5 7

2 5

4 4

6 5

1 2

2 1

5 7

4 3

6 5

1 2

4 5

5 4

6 5

2 6

2 5

5 2

4 3

2 1

6 6

2 1

6 7

5 2

4 1

4 5

4 3

1 2

3 2

5 2

2 5

4 7

4 3

5 2

2 1

2 6

2 1

4 3

5 2

2 5

1 7

2 5

1 7

2 5

3 4

4 1

4 3

[出力例]

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

2022年1月25日2022年1月25日

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

C++の練習を兼ねて, AtCoder Regular Contest 133 の問題A (Erase by Value) ～問題B (Dividing Subsequence) を解いてみた.

■感想.
1. 問題Bは, 方針が見えなかったので, 解説を参考に, AC版に到達できた.
2. LIS(Longest increase subsequence) の応用版(追加条件) を, 確認することができたので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

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

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    vi a(N);
    rep(i, N) scanf("%d", &a[i]);
    
    // 2. x を 求める.
    int x = a[0];
    rep(i, N){
        // 減少.
        if(x > a[i]) break;
        
        // 増加.
        if(x < a[i]) x = a[i];
    }
    
    // 3. 出力.
    rep(i, N){
        if(a[i] == x) continue;
        else          printf("%d ", a[i]);
    }
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

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

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

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

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

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

vi a(N);

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

// 2. x を求める.

int x = a[0];

rep(i, N){

// 減少.

if(x > a[i]) break;

// 増加.

if(x < a[i]) x = a[i];

}

// 3. 出力.

rep(i, N){

if(a[i] == x) continue;

else printf("%d ", a[i]);

}

return 0;

}

[入力例]
5
2 4 4 1 2

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

[入力例]
3
1 1 1

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

[入力例]
5
1 1 2 3 3

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

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

[出力例]
1 4 1 5 9 2 

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

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

[入力例]

2 4 4 1 2

[出力例]

2 1 2

※AtCoderのテストケースより

[入力例]

1 1 1

[出力例]

※AtCoderのテストケースより

[入力例]

1 1 2 3 3

[出力例]

1 1 2

※AtCoderのテストケースより

[入力例]

3 1 4 1 5 9 2

[出力例]

1 4 1 5 9 2

[入力例]

1 1 2 2 3 3 5 5 7 7 7 7 11 11 11 10 5 3 2 1

[出力例]

1 1 2 2 3 3 5 5 7 7 7 7 10 5 3 2 1

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

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

int main(){
    
    // 1. 入力情報.
    int N, x;
    scanf("%d", &N);
    rep(i, N){
        scanf("%d", &x);
        p[x] = i + 1;
    }
    rep(i, N){
        scanf("%d", &x);
        q[x] = i + 1;
    }
    
    // 2. Q[j] が P[i] の 倍数になっているペアは？
    vp v;
    repx(i, 1, N + 1) repex(j, i, N + 1, i) v.pb({p[i], -q[j]});
    
    // 3. sort.
    sort(all(v));
    
    // 4. 狭義単調増加な数列の長さの最大値は？
    // 以下の問題を参照.
    // https://atcoder.jp/contests/typical90/tasks/typical90_bh
    // -> LIS(Longest increase subsequence) を 利用.
    vi dp;
    for(auto &p : v){
        // 数列を保存.
        // -> 但し, 符号を反転したもので, 保存等を行うこと.
        if(dp.size() == 0 || dp.back() < -p.b){
            dp.pb(-p.b);
        }else{
            int at = lower_bound(all(dp), -p.b) - dp.begin();
            dp[at] = -p.b;
        }
    }
    
    // 5. 出力.
    printf("%d\n", dp.size());
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc133/editorial/3283

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

using P = pair<int, int>;

using vp = vector<P>;

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

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

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

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

#define pb push_back

#define a first

#define b second

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

int p[202020], q[202020];

int main(){

// 1. 入力情報.

int N, x;

scanf("%d", &N);

rep(i, N){

scanf("%d", &x);

p[x] = i + 1;

}

rep(i, N){

scanf("%d", &x);

q[x] = i + 1;

}

// 2. Q[j] が P[i] の倍数になっているペアは？

vp v;

repx(i, 1, N + 1) repex(j, i, N + 1, i) v.pb({p[i], -q[j]});

// 3. sort.

sort(all(v));

// 4. 狭義単調増加な数列の長さの最大値は？

// 以下の問題を参照.

// https://atcoder.jp/contests/typical90/tasks/typical90_bh

// -> LIS(Longest increase subsequence) を利用.

vi dp;

for(auto &p : v){

// 数列を保存.

// -> 但し, 符号を反転したもので, 保存等を行うこと.

if(dp.size() == 0 || dp.back() < -p.b){

dp.pb(-p.b);

}else{

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

dp[at] = -p.b;

}

// 5. 出力.

printf("%d\n", dp.size());

return 0;

}

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

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

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

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

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

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

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

[出力例]
10

[入力例]
100
68 49 78 16 97 82 47 41 69 44 38 45 36 32 92 66 33 10 57 94 52 100 30 75 59 89 37 83 11 55 17 60 50 71 28 2 20 12 81 53 3 96 19 42 14 1 67 70 58 72 23 98 51 56 84 95 6 26 79 73 8 13 48 5 80 63 29 85 76 31 34 90 25 65 86 99 54 77 62 74 91 7 87 35 22 4 9 40 43 64 27 24 15 93 46 61 18 21 39 88
78 11 52 79 82 46 90 8 83 80 39 58 35 54 3 6 75 51 76 27 13 96 33 25 65 2 43 20 92 21 60 84 9 74 30 63 32 19 22 14 86 55 15 85 100 61 37 34 81 23 1 40 26 59 94 47 70 88 89 71 62 69 87 7 68 66 4 44 48 36 95 67 10 38 12 64 45 72 24 16 28 93 99 17 53 42 18 29 97 41 56 49 91 73 77 5 50 98 31 57

[出力例]
27

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

[出力例]
45

[入力例]

3 1 4 2

4 2 1 3

[出力例]

※AtCoderのテストケースより

[入力例]

1 2 3 4 5

5 4 3 2 1

[出力例]

※AtCoderのテストケースより

[入力例]

4 3 1 10 9 2 8 6 5 7

9 6 5 4 2 3 8 10 1 7

[出力例]

※AtCoderのテストケースより

[入力例]

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

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

[出力例]

[入力例]

100

68 49 78 16 97 82 47 41 69 44 38 45 36 32 92 66 33 10 57 94 52 100 30 75 59 89 37 83 11 55 17 60 50 71 28 2 20 12 81 53 3 96 19 42 14 1 67 70 58 72 23 98 51 56 84 95 6 26 79 73 8 13 48 5 80 63 29 85 76 31 34 90 25 65 86 99 54 77 62 74 91 7 87 35 22 4 9 40 43 64 27 24 15 93 46 61 18 21 39 88

78 11 52 79 82 46 90 8 83 80 39 58 35 54 3 6 75 51 76 27 13 96 33 25 65 2 43 20 92 21 60 84 9 74 30 63 32 19 22 14 86 55 15 85 100 61 37 34 81 23 1 40 26 59 94 47 70 88 89 71 62 69 87 7 68 66 4 44 48 36 95 67 10 38 12 64 45 72 24 16 28 93 99 17 53 42 18 29 97 41 56 49 91 73 77 5 50 98 31 57

[出力例]

[入力例]

250

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

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

[出力例]

■参照サイト
AtCoder Regular Contest 133
060 – Chimera

2022年1月25日2022年1月25日

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

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

■感想.
1. 問題Dは, 方針が見えなかったので, 解説を参考に, AC版に到達できた.
2. 本問は, メモ化再帰の例題として, 学習した内容である.
相変わらず, メモ化再帰の本質が見えてないため, 理解が進むまでは, 本問を, 典型的な例題として, いったん丸暗記の方針とした.
とはいえ, メモ化再帰は, 以下の構成要素(ロジック)が含まれていると, とりあえず理解した.
① 第一段階 … メモ化が終わっているか確認する作業, 再帰処理の終了条件として使用する.
② 第二段階 … 再帰処理の実装, 本問では, “経路数” を知りたいので, 経路数を集計する実装が必要.
③ 第三段階 … メモ化が終わってないため, メモ化の作業を追加, なお, 本問では, メモ化の対象は, “経路数” と理解.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/data/abc/037/editorial.pdf
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vl = vector<LL>;
using vvl = vector<vl>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
constexpr int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};
const LL MOD = 1e9 + 7;

int main(){
    
    // 1. 入力情報.
    int H, W;
    scanf("%d %d", &H, &W);
    vvl a(H, vl(W));
    rep(i, H) rep(j, W) scanf("%lld", &a[i][j]);
    
    // 2. dfs.
    // https://ja.wikipedia.org/wiki/深さ優先探索
    vvl dp(H, vl(W));
    auto dfs = [&](auto self, int hCur, int wCur) -> LL{
        // 2-1. 終了条件.
        // -> 前回以前に, メモ化が完了しているため終了.
        if(dp[hCur][wCur]) return dp[hCur][wCur];
        
        // 2-2. 経路数 f(i, j) の 計算.
        LL ret = 1;
        rep(i, 4){
            // 移動先候補.
            int hNex = hCur + dy[i];
            int wNex = wCur + dx[i];
            
            // 移動不可能.
            if(wNex < 0 || wNex >= W || hNex < 0 || hNex >= H) continue;
            
            // 移動可能.
            if(a[hCur][wCur] < a[hNex][wNex]) ret = (ret + self(self, hNex, wNex)) % MOD;
        }
        
        // 2-3. メモ化.
        // -> まだ, メモ化していないマスに対して, メモ化する.
        //    ここで, 本問でのメモ化対象は, 解説にある f(i, j) を dp[i][j] に保存(メモ化)すると理解.
        return dp[hCur][wCur] = ret;
    };
    
    // 3. 集計.
    LL ans = 0;
    rep(i, H) rep(j, W) ans = (ans + dfs(dfs, i, j)) % MOD;
    
    // 4. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://img.atcoder.jp/data/abc/037/editorial.pdf

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vl = vector<LL>;

using vvl = vector<vl>;

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

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

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

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

constexpr int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};

const LL MOD = 1e9 + 7;

int main(){

// 1. 入力情報.

int H, W;

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

vvl a(H, vl(W));

rep(i, H) rep(j, W) scanf("%lld", &a[i][j]);

// 2. dfs.

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

vvl dp(H, vl(W));

auto dfs = [&](auto self, int hCur, int wCur) -> LL{

// 2-1. 終了条件.

// -> 前回以前に, メモ化が完了しているため終了.

if(dp[hCur][wCur]) return dp[hCur][wCur];

// 2-2. 経路数 f(i, j) の計算.

LL ret = 1;

rep(i, 4){

// 移動先候補.

int hNex = hCur + dy[i];

int wNex = wCur + dx[i];

// 移動不可能.

if(wNex < 0 || wNex >= W || hNex < 0 || hNex >= H) continue;

// 移動可能.

if(a[hCur][wCur] < a[hNex][wNex]) ret = (ret + self(self, hNex, wNex)) % MOD;

}

// 2-3. メモ化.

// -> まだ, メモ化していないマスに対して, メモ化する.

// ここで, 本問でのメモ化対象は, 解説にある f(i, j) を dp[i][j] に保存(メモ化)すると理解.

return dp[hCur][wCur] = ret;

};

// 3. 集計.

LL ans = 0;

rep(i, H) rep(j, W) ans = (ans + dfs(dfs, i, j)) % MOD;

// 4. 出力.

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

return 0;

}

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

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

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

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


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

[出力例]
77

[入力例]
20 10
6 44 80 52 78 83 4 44 83 71
62 78 40 65 94 29 59 74 23 116
75 14 103 67 18 7 15 73 116 12
44 14 64 103 9 3 122 40 91 12
96 48 71 14 87 13 41 57 29 88
112 39 39 53 108 69 18 8 113 22
85 37 9 48 4 34 101 119 28 12
51 35 30 28 76 51 107 106 20 121
49 118 9 67 89 92 54 97 123 32
68 83 37 102 119 54 67 60 2 64
105 72 81 107 50 92 51 30 30 78
122 32 20 3 33 42 112 45 14 118
108 13 64 33 49 82 104 63 115 115
36 96 83 57 120 58 23 54 77 41
120 47 113 34 100 99 84 79 70 12
4 114 98 118 104 116 78 14 5 121
46 8 97 64 68 117 115 90 57 120
13 117 23 106 27 23 11 74 57 73
86 75 80 6 115 75 79 36 45 59
13 66 103 28 89 92 54 114 114 9

[出力例]
1335

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

[出力例]
5185

[入力例]

2 3

1 4 5

2 4 9

[出力例]

※AtCoderテストケースより

[入力例]

6 6

1 3 4 6 7 5

1 2 4 8 8 7

2 7 9 2 7 2

9 4 2 7 6 5

2 8 4 6 7 6

3 7 9 1 2 7

[出力例]

170

※AtCoderテストケースより

[入力例]

3 3

1 2 3

6 5 4

7 8 9

[出力例]

[入力例]

20 10

6 44 80 52 78 83 4 44 83 71

62 78 40 65 94 29 59 74 23 116

75 14 103 67 18 7 15 73 116 12

44 14 64 103 9 3 122 40 91 12

96 48 71 14 87 13 41 57 29 88

112 39 39 53 108 69 18 8 113 22

85 37 9 48 4 34 101 119 28 12

51 35 30 28 76 51 107 106 20 121

49 118 9 67 89 92 54 97 123 32

68 83 37 102 119 54 67 60 2 64

105 72 81 107 50 92 51 30 30 78

122 32 20 3 33 42 112 45 14 118

108 13 64 33 49 82 104 63 115 115

36 96 83 57 120 58 23 54 77 41

120 47 113 34 100 99 84 79 70 12

4 114 98 118 104 116 78 14 5 121

46 8 97 64 68 117 115 90 57 120

13 117 23 106 27 23 11 74 57 73

86 75 80 6 115 75 79 36 45 59

13 66 103 28 89 92 54 114 114 9

[出力例]

1335

[入力例]

25 30

111 59 96 84 98 107 13 25 75 36 8 14 13 115 29 24 37 5 75 100 2 100 101 81 24 9 4 90 120 26

35 21 47 111 103 69 95 40 34 17 8 82 34 75 34 90 30 103 16 22 84 71 49 13 30 26 47 9 60 34

43 4 36 64 60 114 37 121 77 102 38 123 77 121 86 22 43 80 76 30 89 57 60 7 40 11 7 96 66 55

2 73 105 40 45 90 89 37 8 113 10 102 47 109 82 114 19 52 55 72 39 57 53 70 122 83 4 23 38 46

72 66 110 28 39 101 63 59 68 82 110 65 9 106 118 115 122 102 42 3 71 43 114 20 81 97 71 113 51 39

62 62 104 45 1 23 23 36 66 63 76 3 24 109 68 70 66 38 85 68 21 98 74 118 107 60 117 11 40 117

84 52 61 30 122 92 50 87 94 114 108 52 91 48 97 31 120 67 67 93 55 33 17 70 22 15 30 95 36 93

43 66 117 31 8 11 53 47 69 13 110 51 118 117 92 2 84 119 18 34 18 34 16 86 55 103 52 51 47 92

41 36 106 70 93 108 41 117 119 120 89 85 37 7 123 55 69 44 112 30 77 76 67 25 63 40 89 107 111 22

18 6 25 9 55 69 120 24 14 92 58 64 109 84 113 68 46 103 56 105 13 108 8 29 36 31 58 115 30 5

119 54 98 77 96 46 39 59 65 77 77 105 20 20 79 13 83 78 66 5 31 27 43 60 102 5 23 119 55 23

52 46 84 105 15 105 92 81 32 70 25 17 58 70 17 102 115 85 65 37 59 92 66 80 90 22 5 15 45 89

22 65 43 58 105 40 33 29 113 37 59 53 81 113 116 88 51 20 42 82 32 5 91 3 99 98 11 97 99 72

106 2 87 16 38 55 118 63 30 68 9 57 114 36 102 40 110 46 42 3 72 116 104 98 51 59 95 3 10 25

110 117 103 18 32 78 2 42 49 111 51 40 121 18 34 5 32 87 1 64 81 43 45 106 69 36 100 68 77 38

27 37 121 44 93 89 79 62 120 64 56 70 47 101 96 102 50 119 117 112 108 95 109 85 110 104 91 121 9 2

93 83 30 98 92 36 92 90 88 25 5 23 27 116 72 76 71 17 20 67 94 83 100 56 77 26 66 23 90 58

46 51 5 115 11 21 52 38 28 4 113 27 44 72 32 39 19 11 38 38 99 3 46 52 14 22 47 68 31 13

46 118 103 11 14 79 77 113 90 99 33 87 54 96 90 92 35 1 89 16 36 109 38 65 81 25 34 8 50 24

34 45 10 44 23 103 57 96 86 122 37 84 33 64 85 41 59 38 105 55 45 10 32 87 107 106 10 2 84 42

53 8 23 34 73 77 24 39 10 91 18 58 85 88 112 44 38 64 58 69 72 57 101 39 51 86 32 85 40 91

17 11 6 88 26 31 79 91 106 4 23 64 5 78 48 108 89 95 59 64 33 80 33 73 12 30 52 78 96 109

72 10 120 18 42 4 36 48 16 45 40 58 52 28 74 49 85 15 123 33 114 12 52 65 6 105 86 62 38 49

5 86 76 106 22 28 111 78 8 33 73 14 116 84 85 113 54 99 80 37 4 91 123 85 120 3 114 79 66 98

52 76 26 102 32 28 54 37 60 104 9 104 47 20 90 25 29 53 84 22 3 122 121 109 72 3 5 76 31 58

[出力例]

5185

■参照サイト
AtCoder Beginner Contest 037

2022年1月23日

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

C++の練習を兼ねて, AtCoder Regular Contest 103 の問題E (Tr/ee) を解いてみた.

■感想.
1. 問題Eは, 方針が見えなかったので, 解説を参考に, AC版に到達できた.
2. 個人的には, 特殊な性質を持つグラフを抽出するロジックが, 面白いと感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/arc103/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

int main(){
    
    // 1. 入力情報.
    char x[101010];
    scanf("%s", x);
    string s(x);
    int N = s.size();
    
    // 2. 条件を満たすか？
    bool ok = true;
    if(s[0] != '1' || s[N - 1] != '0') ok = false;
    repx(i, 1, N - 1) if(s[i] != s[N - 2 - i]) ok = false;
    
    // 3. 例外.
    if(!ok){
        puts("-1");
        return 0;
    }
    
    // 4. グラフ構築.
    // 4-1. 根 を 設定.
    s[N - 1] = '1';
    
    // 4-2. 文字 '1'.
    vp ans(N - 1);
    int c = 0;
    repx(i, 1, N){
        if(s[i] == '1'){
            // {子頂点, 親頂点} を 設定.
            ans[c] = {c + 1, i + 1};
            
            // 子頂点更新.
            c = i;
        }
    }
    
    // 4-3. 文字 '0'.
    rep(i, N){
        // 子頂点 を 設定.
        if(s[i] == '1') c = ans[i].b;
        
        // {子頂点, 親頂点} を 設定.
        if(s[i] == '0') ans[i] = {c, i + 1};
    }
    
    // 5. 出力.
    for(auto &p : ans) printf("%d %d\n", p.a, p.b);
    return 0;
    
}

// 解き直し.

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

int main(){

// 1. 入力情報.

char x[101010];

scanf("%s", x);

string s(x);

int N = s.size();

// 2. 条件を満たすか？

bool ok = true;

if(s[0] != '1' || s[N - 1] != '0') ok = false;

repx(i, 1, N - 1) if(s[i] != s[N - 2 - i]) ok = false;

// 3. 例外.

if(!ok){

puts("-1");

return 0;

}

// 4. グラフ構築.

// 4-1. 根を設定.

s[N - 1] = '1';

// 4-2. 文字 '1'.

vp ans(N - 1);

int c = 0;

repx(i, 1, N){

if(s[i] == '1'){

// {子頂点, 親頂点} を設定.

ans[c] = {c + 1, i + 1};

// 子頂点更新.

c = i;

}

// 4-3. 文字 '0'.

rep(i, N){

// 子頂点を設定.

if(s[i] == '1') c = ans[i].b;

// {子頂点, 親頂点} を設定.

if(s[i] == '0') ans[i] = {c, i + 1};

}

// 5. 出力.

for(auto &p : ans) printf("%d %d\n", p.a, p.b);

return 0;

}

[入力例]
1111

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

[入力例]
1110

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

[入力例]
1010

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

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

[入力例]
1001110010

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

[入力例]
11000010101010000110

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

[入力例]

1111

[出力例]

-1

※AtCoderテストケースより

[入力例]

1110

[出力例]

1 2

2 3

3 4

※AtCoderテストケースより

[入力例]

1010

[出力例]

1 2

1 3

1 4

※AtCoderテストケースより

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

1 3

3 2

3 4

[入力例]

1001110010

[出力例]

1 4

4 2

4 3

4 5

5 6

6 9

9 7

9 8

9 10

[入力例]

11000010101010000110

[出力例]

1 2

2 7

7 3

7 4

7 5

7 6

7 9

9 8

9 11

11 10

11 13

13 12

13 18

18 14

18 15

18 16

18 17

18 19

19 20

■参照サイト
AtCoder Regular Contest 103

2022年1月22日

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

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

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

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

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vi = vector<int>;
using P = pair<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 a first
#define b second
#define pb push_back
#define all(x) x.begin(), x.end()

// Binary Indexed Tree (Fenwick Tree)
// https://youtu.be/lyHk98daDJo?t=7960
template<typename T>
struct BIT{
    int n;
    vector<T> d;
    BIT(int n = 0) : n(n), d(n + 1) {}
    void add(int i, T x = 1){
        for(i++; i <= n; i += i & -i) d[i] += x;
    }
    T sum(int i){
        T x = 0;
        for(i++; i; i -= i & -i) x += d[i];
        return x;
    }
    T sum(int l, int r){
        return sum(r - 1) - sum(l - 1);
    }
};

struct joy{
   int a, b;
   bool operator < (const joy &J) const{ 
       return (a > J.a) || (a == J.a && b < J.b); 
   }
};

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    vi A(N), B(N);
    map<int, int> m;
    rep(i, N) scanf("%d", &A[i]);
    rep(i, N){
        scanf("%d", &B[i]);
        m[B[i]] = 1;
    }
    
    // 2. 同一要素の出現を考慮する必要がある？
    map<P, int> mo;
    rep(i, N) mo[{A[i], B[i]}]++;
    LL ans = 0;
    for(auto &p : mo) ans += (LL)(p.b - 1) * (LL)p.b / 2;
    
    // 3. 座標圧縮(青木君の嬉しさ).
    int idx = 0;
    for(auto &p : m) p.b = ++idx;
    
    // 4. 累積和.
    vi bCum(idx + 1);
    rep(i, N) bCum[m[B[i]]]++;
    rep(i, idx) bCum[i + 1] += bCum[i];
    
    // 5. sort;
    vector<joy> v;
    rep(i, N) v.emplace_back(joy{A[i], B[i]});
    sort(all(v));
    
    // 6. 集計(i番目以降の青木君の嬉しさが, i番目の青木君の嬉しさ以上のものをカウントしたい).
    BIT<int> ft(idx + 1);
    rep(i, N){
        // 青木君 の 嬉しさ(BIT の 加算位置).
        int j = m[v[i].b];
        
        // 今回までで, 嬉しさ j以上 が, 何回出現したか？
        // -> 区間[j, idx + 1) の 合計は？
        int bCount = ft.sum(j, idx + 1);
        
        // 嬉しさ j以上 の 出現回数合計.
        int cCount = bCum[idx] - bCum[j - 1];
        
        // 次回以降で, j以上の嬉しさが, 何回出現できるか？
        ans += (LL)(cCount - bCount);
        
        // 出現回数 として 加算.
        ft.add(j, 1);
    }
    
    // 7. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

100

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vi = vector<int>;

using P = pair<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 a first

#define b second

#define pb push_back

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

// Binary Indexed Tree (Fenwick Tree)

// https://youtu.be/lyHk98daDJo?t=7960

template<typename T>

struct BIT{

int n;

vector<T> d;

BIT(int n = 0) : n(n), d(n + 1) {}

void add(int i, T x = 1){

for(i++; i <= n; i += i & -i) d[i] += x;

}

T sum(int i){

T x = 0;

for(i++; i; i -= i & -i) x += d[i];

return x;

}

T sum(int l, int r){

return sum(r - 1) - sum(l - 1);

}

};

struct joy{

int a, b;

bool operator < (const joy &J) const{

return (a > J.a) || (a == J.a && b < J.b);

}

};

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

vi A(N), B(N);

map<int, int> m;

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

rep(i, N){

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

m[B[i]] = 1;

}

// 2. 同一要素の出現を考慮する必要がある？

map<P, int> mo;

rep(i, N) mo[{A[i], B[i]}]++;

LL ans = 0;

for(auto &p : mo) ans += (LL)(p.b - 1) * (LL)p.b / 2;

// 3. 座標圧縮(青木君の嬉しさ).

int idx = 0;

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

// 4. 累積和.

vi bCum(idx + 1);

rep(i, N) bCum[m[B[i]]]++;

rep(i, idx) bCum[i + 1] += bCum[i];

// 5. sort;

vector<joy> v;

rep(i, N) v.emplace_back(joy{A[i], B[i]});

sort(all(v));

// 6. 集計(i番目以降の青木君の嬉しさが, i番目の青木君の嬉しさ以上のものをカウントしたい).

BIT<int> ft(idx + 1);

rep(i, N){

// 青木君の嬉しさ(BIT の加算位置).

int j = m[v[i].b];

// 今回までで, 嬉しさ j以上が, 何回出現したか？

// -> 区間[j, idx + 1) の合計は？

int bCount = ft.sum(j, idx + 1);

// 嬉しさ j以上の出現回数合計.

int cCount = bCum[idx] - bCum[j - 1];

// 次回以降で, j以上の嬉しさが, 何回出現できるか？

ans += (LL)(cCount - bCount);

// 出現回数として加算.

ft.add(j, 1);

}

// 7. 出力.

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

return 0;

}

[入力例]
3
50 100 150
1 3 2

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

[入力例]
3
123456789 123456 123
987 987654 987654321

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

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

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

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

[出力例]
10

[入力例]
25
1 83 57 35 11 80 87 64 91 89 2 7 56 64 7 10 83 11 2 7 64 45 64 83 55
8 97 61 39 11 85 34 21 72 88 2 7 34 21 7 15 50 11 2 7 16 61 21 97 65

[出力例]
99

[入力例]
100
54 15 84 28 42 95 87 62 81 6 44 70 58 65 92 11 10 92 40 20 33 62 64 18 64 3 15 93 52 93 71 72 27 23 79 25 9 15 55 94 0 97 46 56 20 51 24 77 4 37 55 57 90 48 53 25 74 7 76 45 60 90 30 42 84 87 25 23 0 48 62 5 88 34 77 81 17 60 88 5 15 65 13 71 45 0 15 71 63 79 2 38 76 53 91 94 18 22 36 89
56 34 20 1 66 99 72 87 78 39 83 97 26 48 88 41 49 56 24 11 87 26 63 62 65 99 19 13 99 12 34 13 37 24 53 91 3 18 15 18 62 73 56 63 46 97 62 97 66 77 90 24 19 62 25 50 24 12 49 14 33 94 79 47 78 86 3 95 16 3 99 77 18 62 22 16 60 92 49 63 53 37 19 88 28 36 26 92 54 4 12 19 30 52 19 76 98 96 27 71

[出力例]
2500

[入力例]

50 100 150

1 3 2

[出力例]

※AtCoderテストケースより

[入力例]

123456789 123456 123

987 987654 987654321

[出力例]

※AtCoderテストケースより

[入力例]

3 1 4 1 5 9 2 6 5 3

2 7 1 8 2 8 1 8 2 8

[出力例]

※AtCoderテストケースより

[入力例]

5 9 7 3 7

0 6 1 2 1

[出力例]

[入力例]

1 83 57 35 11 80 87 64 91 89 2 7 56 64 7 10 83 11 2 7 64 45 64 83 55

8 97 61 39 11 85 34 21 72 88 2 7 34 21 7 15 50 11 2 7 16 61 21 97 65

[出力例]

[入力例]

100

54 15 84 28 42 95 87 62 81 6 44 70 58 65 92 11 10 92 40 20 33 62 64 18 64 3 15 93 52 93 71 72 27 23 79 25 9 15 55 94 0 97 46 56 20 51 24 77 4 37 55 57 90 48 53 25 74 7 76 45 60 90 30 42 84 87 25 23 0 48 62 5 88 34 77 81 17 60 88 5 15 65 13 71 45 0 15 71 63 79 2 38 76 53 91 94 18 22 36 89

56 34 20 1 66 99 72 87 78 39 83 97 26 48 88 41 49 56 24 11 87 26 63 62 65 99 19 13 99 12 34 13 37 24 53 91 3 18 15 18 62 73 56 63 46 97 62 97 66 77 90 24 19 62 25 50 24 12 49 14 33 94 79 47 78 86 3 95 16 3 99 77 18 62 22 16 60 92 49 63 53 37 19 88 28 36 26 92 54 4 12 19 30 52 19 76 98 96 27 71

[出力例]

2500

■参照サイト
パナソニックプログラミングコンテスト2021(AtCoder Beginner Contest 231)
Binary Indexed Tree (Fenwick Tree)

2022年1月22日

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

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

■感想.
1. 問題Eは, 解説を参考に, 実装を試行錯誤してみたものの, 実装方針が確定できず, 解説プログラムベースで, AC版としている.
2. メモ化再帰の復習が出来たので, 非常に良かったと思う.
但し, メモ化再帰の本質が理解出来てないので, 今後の課題だと思われる.
3. 方針が見えなかった原因として, 現在見ている硬貨だけでなく, 次回分の硬貨も見る必要がある部分, および, 現在見ている硬貨で割った余りがゼロの場合は, 再帰処理が, 一本化される部分が, 該当すると思われる.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解答不能.
// https://atcoder.jp/contests/abc231/submissions/27854173
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vl = vector<LL>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)

int main(){
    
    // 1. 入力情報.
    int N;
    LL X;
    scanf("%d %lld", &N, &X);
    vl a(N);
    rep(i, N) scanf("%lld", &a[i]);
    
    // 2. dfs(解説通り).
    // https://ja.wikipedia.org/wiki/深さ優先探索
    // -> 正しく動作しないので, 解説プログラムを参考に, 以下のロジックに修正.
    map<LL, LL> m;
    auto dfs = [&](auto self, LL curX, int d) -> LL{
        // 2-1. 終了条件.
        if(m.count(curX)) return m[curX];
        if(d == N - 1)    return curX / a[N - 1];
        
        // 2-2. 端数処理.
        // -> 現在分, 次回分 の 数列 A の要素を考える必要があるらしい.
        LL curA = a[d];
        LL nexA = a[d + 1];
        LL rL = curX % nexA / curA;
        LL rR = nexA / curA - rL;
        
        // 2-3. 次回の支払い対象金額.
        LL nexXL = curX / nexA * nexA;
        LL nexXR = nexXL;
        if(curX % nexA) nexXR += nexA;
        
        // 2-4. 次へ.
        LL ret = rL + self(self, nexXL, d + 1);
        if(rL) ret = min(ret, rR + self(self, nexXR, d + 1));
        
        // 2-5. 返却.
        return m[curX] = ret;
    };
    
    // 3. 出力.
    printf("%lld\n", dfs(dfs, X, 0));
    return 0;
    
}

// 解答不能.

// https://atcoder.jp/contests/abc231/submissions/27854173

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vl = vector<LL>;

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

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

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

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

int main(){

// 1. 入力情報.

int N;

LL X;

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

vl a(N);

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

// 2. dfs(解説通り).

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

// -> 正しく動作しないので, 解説プログラムを参考に, 以下のロジックに修正.

map<LL, LL> m;

auto dfs = [&](auto self, LL curX, int d) -> LL{

// 2-1. 終了条件.

if(m.count(curX)) return m[curX];

if(d == N - 1) return curX / a[N - 1];

// 2-2. 端数処理.

// -> 現在分, 次回分の数列 A の要素を考える必要があるらしい.

LL curA = a[d];

LL nexA = a[d + 1];

LL rL = curX % nexA / curA;

LL rR = nexA / curA - rL;

// 2-3. 次回の支払い対象金額.

LL nexXL = curX / nexA * nexA;

LL nexXR = nexXL;

if(curX % nexA) nexXR += nexA;

// 2-4. 次へ.

LL ret = rL + self(self, nexXL, d + 1);

if(rL) ret = min(ret, rR + self(self, nexXR, d + 1));

// 2-5. 返却.

return m[curX] = ret;

};

// 3. 出力.

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

return 0;

}

[入力例]
3 87
1 10 100

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

[入力例]
2 49
1 7

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

[入力例]
10 123456789012345678
1 100 10000 1000000 100000000 10000000000 1000000000000 100000000000000 10000000000000000 1000000000000000000

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

[入力例]
4 234
1 5 50 250

[出力例]
5

[入力例]
11 3141592653
1 3 27 405 1215 8505 144585 1012095 17205615 326906685 3595973535

[出力例]
29

[入力例]
16 202112112100
1 3 15 45 225 1575 7875 23625 259875 5197500 36382500 254677500 2801452500 47624692500 142874077500 1571614852500

[出力例]
30

[入力例]

3 87

1 10 100

[出力例]

※AtCoderテストケースより

[入力例]

2 49

1 7

[出力例]

※AtCoderテストケースより

[入力例]

10 123456789012345678

1 100 10000 1000000 100000000 10000000000 1000000000000 100000000000000 10000000000000000 1000000000000000000

[出力例]

233

※AtCoderテストケースより

[入力例]

4 234

1 5 50 250

[出力例]

[入力例]

11 3141592653

1 3 27 405 1215 8505 144585 1012095 17205615 326906685 3595973535

[出力例]

[入力例]

16 202112112100

1 3 15 45 225 1575 7875 23625 259875 5197500 36382500 254677500 2801452500 47624692500 142874077500 1571614852500

[出力例]

■参照サイト
パナソニックプログラミングコンテスト2021(AtCoder Beginner Contest 231)

2022年1月21日

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

C++の練習を兼ねて, 第三回アルゴリズム実技検定の問題G (グリッド金移動) を解いてみた.

■感想.
1. 問題Gは, 方針を絞り込むことが出来たので, AC版に到達できたと思う.
2. 過去問(第九回アルゴリズム実技検定 F – 将棋のように) に似ている問題に見えたため, 実装を一部流用している.
3. 幅優先探索(応用版, 移動可能方向の構築)の復習が出来たので, 非常に良かったと思う.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 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
const int D1 = 505;
const int D2 = 250;
int board[(D1 + 1) * (D1 + 1)];

int main(){
    
    // 1. 入力情報.
    int N, X, Y;
    scanf("%d %d %d", &N, &X, &Y);
    X += D2;
    Y += D2;
    rep(i, N){
        int x, y;
        scanf("%d %d", &x, &y);
        x += D2;
        y += D2;
        board[D1 * x + y] = 1;
    }
    
    // 2. 移動可能な方向は？
    // 過去問参照(第九回 アルゴリズム実技検定 F - 将棋のように)
    // https://atcoder.jp/contests/past202112-open/tasks/past202112_f
    vp dir;
    dir.pb({1, 1});
    dir.pb({0, 1});
    dir.pb({-1, 1});
    dir.pb({1, 0});
    dir.pb({-1, 0});
    dir.pb({0, -1});
    
    // 3. bfs.
    // https://ja.wikipedia.org/wiki/幅優先探索
    auto bfs = [&](int s, int H, int W, int* d) -> void{
        // 空のキュー.
        queue<int> q;
        
        // 訪問済みフラグ設定.
        d[s] = 0;
        
        // 探索地点 s をキュー q に追加.
        q.push(s);
        while(!q.empty()){
            // キューから取り出す.
            int v = q.front();
            q.pop();
            
            // 取り出した要素を処理.
            // x: 列方向, y: 行方向 で考える.
            int nx, ny, n;
            int cx = v % W , cy = v / W;
            for(auto &p : dir){
                // 移動先.
                nx = cx + p.b;
                ny = cy + p.a;
                n = nx + ny * W;
                
                // 訪問不可能なマス であれば, 処理をスキップ.
                if(nx < 0 || nx >= W || ny < 0 || ny >= H || board[n]) continue;
                
                // 移動先のマスで, 訪問可能 かつ 未訪問 であれば, 最短距離を設定.
                if(d[n] == -1) d[n] = d[v] + 1, q.push(n);
            }
        }
    };
    int d[D1 * D1];
    rep(i, D1 * D1) d[i] = -1;
    bfs(D1 * D2 + D2, D1, D1, d);
    
    // 4. 出力.
    printf("%d\n", d[D1 * X + Y]);
    return 0;
    
}

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

const int D1 = 505;

const int D2 = 250;

int board[(D1 + 1) * (D1 + 1)];

int main(){

// 1. 入力情報.

int N, X, Y;

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

X += D2;

Y += D2;

rep(i, N){

int x, y;

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

x += D2;

y += D2;

board[D1 * x + y] = 1;

}

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

// 過去問参照(第九回アルゴリズム実技検定 F - 将棋のように)

// https://atcoder.jp/contests/past202112-open/tasks/past202112_f

vp dir;

dir.pb({1, 1});

dir.pb({0, 1});

dir.pb({-1, 1});

dir.pb({1, 0});

dir.pb({-1, 0});

dir.pb({0, -1});

// 3. bfs.

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

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

// 空のキュー.

queue<int> q;

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

d[s] = 0;

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

q.push(s);

while(!q.empty()){

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

int v = q.front();

q.pop();

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

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

int nx, ny, n;

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

for(auto &p : dir){

// 移動先.

nx = cx + p.b;

ny = cy + p.a;

n = nx + ny * W;

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

if(nx < 0 || nx >= W || ny < 0 || ny >= H || board[n]) continue;

// 移動先のマスで, 訪問可能かつ未訪問であれば, 最短距離を設定.

if(d[n] == -1) d[n] = d[v] + 1, q.push(n);

}

};

int d[D1 * D1];

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

bfs(D1 * D2 + D2, D1, D1, d);

// 4. 出力.

printf("%d\n", d[D1 * X + Y]);

return 0;

}

[入力例]
1 2 2
1 1

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

[入力例]
1 2 2
2 1

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

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

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

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

[出力例]
5

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

[出力例]
11

[入力例]

1 2 2

1 1

[出力例]

※AtCoderテストケースより

[入力例]

1 2 2

2 1

[出力例]

※AtCoderテストケースより

[入力例]

5 -2 3

1 1

-1 1

0 1

-2 1

-3 1

[出力例]

※AtCoderテストケースより

[入力例]

7 4 4

4 1

4 3

1 1

1 5

2 1

2 2

3 3

[出力例]

[入力例]

22 10 3

3 1

6 1

8 1

2 2

3 2

7 2

9 2

2 3

5 3

6 3

7 3

9 3

4 4

7 4

9 4

1 5

3 5

7 5

10 5

6 6

8 6

6 7

[出力例]

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

2022年1月19日

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

C++の練習を兼ねて, AtCoder Beginner Contest 235 の問題C (Counting 2) ～問題D (Neighbors) を解いてみた.

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

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

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

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

int main(){
    
    // 1. 入力情報.
    int N, Q;
    scanf("%d %d", &N, &Q);
    vi a(N);
    rep(i, N) scanf("%d", &a[i]);
    
    // 2. sort.
    sort(all(a));
    
    // 3. クエリ回答.
    rep(i, Q){
        int x;
        scanf("%d", &x);
        int ans = N - (lower_bound(all(a), x) - a.begin());
        printf("%d\n", ans);
    }
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

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

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

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

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

#define pb push_back

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

int main(){

// 1. 入力情報.

int N, Q;

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

vi a(N);

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

// 2. sort.

sort(all(a));

// 3. クエリ回答.

rep(i, Q){

int x;

scanf("%d", &x);

int ans = N - (lower_bound(all(a), x) - a.begin());

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

}

return 0;

}

[入力例]
3 1
100 160 130
120

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

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

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

[入力例]
5 5
804289384 846930887 681692778 714636916 957747794
424238336
719885387
649760493
596516650
189641422

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

[入力例]
10 5
112 20 72 91 60 54 58 5 66 39
97
20
113
80
3

[出力例]
1
9
0
2
10

[入力例]

3 1

100 160 130

120

[出力例]

※AtCoderテストケースより

[入力例]

5 5

1 2 3 4 5

[出力例]

※AtCoderテストケースより

[入力例]

5 5

804289384 846930887 681692778 714636916 957747794

424238336

719885387

649760493

596516650

189641422

[出力例]

※AtCoderテストケースより

[入力例]

10 5

112 20 72 91 60 54 58 5 66 39

113

[出力例]

■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

// 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);
    
    // 2. 人 A, B が 隣り合うように出来るか？
    // -> 一列に並べる必要があることに注意.
    vvi G(N);
    UnionFind uf(N + 2);
    bool ok = true;
    rep(i, M){
        int a, b;
        scanf("%d %d", &a, &b);
        a--;
        b--;
        G[a].pb(b);
        G[b].pb(a);
        
        // 次数チェック.
        if(G[a].size() > 2 || G[b].size() > 2) ok = false;
        
        // 閉路チェック.
        // -> 閉路があると, 横一列に並べることが出来なくなる.
        if(!uf.same(a, b)) uf.unite(a, b);
        else               ok = false;
    }
    
    // 3. 出力.
    printf("%s\n", ok ? "Yes" : "No");
    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

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

// 2. 人 A, B が隣り合うように出来るか？

// -> 一列に並べる必要があることに注意.

vvi G(N);

UnionFind uf(N + 2);

bool ok = true;

rep(i, M){

int a, b;

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

a--;

b--;

G[a].pb(b);

G[b].pb(a);

// 次数チェック.

if(G[a].size() > 2 || G[b].size() > 2) ok = false;

// 閉路チェック.

// -> 閉路があると, 横一列に並べることが出来なくなる.

if(!uf.same(a, b)) uf.unite(a, b);

else ok = false;

}

// 3. 出力.

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

return 0;

}

[入力例]
4 2
1 3
2 3

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

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

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

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

[出力例]
Yes

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

[出力例]
No

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

[出力例]
No

[入力例]

4 2

1 3

2 3

[出力例]

Yes

※AtCoderテストケースより

[入力例]

4 3

1 4

2 4

3 4

[出力例]

※AtCoderテストケースより

[入力例]

10 5

6 7

1 2

1 10

2 6

3 5

[出力例]

Yes

[入力例]

10 7

5 8

4 5

1 4

1 7

7 9

1 6

2 3

[出力例]

[入力例]

10 10

1 10

1 2

2 3

3 4

4 5

5 6

6 7

7 8

8 9

9 10

[出力例]

■参照サイト
パナソニックプログラミングコンテスト2021(AtCoder Beginner Contest 231)
Union-Find木

2022年1月18日

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

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

■感想.
1. 問題Eは, 方針を絞ることが出来たので, AC版に到達できたと思う.
2. 最小全域木(Kruskal’s Algorithm) の復習が出来たので, 非常に良かったと思う.
※ 公式のライブラリを拝借させて頂いてます.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using T4 = tuple<int, int, int, int>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#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, Q;
    scanf("%d %d %d", &N, &M, &Q);
    vector<T4> t;
    rep(i, M + Q){
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        a--, b--;
        t.emplace_back(c, a, b, (i < M) ? 0 : (i - M + 1));
    }
    
    // 2. sort.
    sort(all(t));
    
    // 3. 最小全域木(Kruskal's Algorithm) の 構築.
    // 競プロ典型 90 問 (049 - Flip Digits 2)
    // https://github.com/E869120/kyopro_educational_90/blob/main/sol/049.cpp
    int ans[Q];
    rep(i, Q) ans[i] = 0;
    UnionFind uf(N + 2);
    rep(i, t.size()){
        // 3-1. グラフ情報.
        int u = get<1>(t[i]); // 頂点.
        int v = get<2>(t[i]); // 頂点.
        int q = get<3>(t[i]); // グラフG(0) or クエリ番号(1, 2, ...).
        
        // 3-2. 最小全域木を構成する辺の追加.
        // -> 但し, クエリ情報の場合は, 辺は追加しない.
        if(!uf.same(u, v)){
            if(q) ans[q - 1] = 1;
            else  uf.unite(u, v);
        }
    }
    
    // 4. 出力.
    rep(i, Q) printf("%s\n", ans[i] ? "Yes" : "No");
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

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

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

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

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

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

#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, Q;

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

vector<T4> t;

rep(i, M + Q){

int a, b, c;

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

a--, b--;

t.emplace_back(c, a, b, (i < M) ? 0 : (i - M + 1));

}

// 2. sort.

sort(all(t));

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

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

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

int ans[Q];

rep(i, Q) ans[i] = 0;

UnionFind uf(N + 2);

rep(i, t.size()){

// 3-1. グラフ情報.

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

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

int q = get<3>(t[i]); // グラフG(0) or クエリ番号(1, 2, ...).

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

// -> 但し, クエリ情報の場合は, 辺は追加しない.

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

if(q) ans[q - 1] = 1;

else uf.unite(u, v);

}

// 4. 出力.

rep(i, Q) printf("%s\n", ans[i] ? "Yes" : "No");

return 0;

}

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

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

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

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

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

[出力例]
Yes
No
No
No
Yes
Yes

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

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

[入力例]

5 6 3

1 2 2

2 3 3

1 3 6

2 4 5

4 5 9

3 5 8

1 3 1

3 4 7

3 5 7

[出力例]

Yes

※AtCoderテストケースより

[入力例]

2 3 2

1 2 100

1 2 1000000000

1 1 1

1 2 2

1 1 5

[出力例]

Yes

※AtCoderテストケースより

[入力例]

6 12 6

1 2 7

1 4 3

6 1 5

6 1 2

1 1 8

2 5 12

2 3 5

6 5 10

5 4 6

5 4 11

4 3 13

3 2 5

1 3 5

2 4 20

3 5 7

4 6 18

5 1 3

1 2 3

[出力例]

Yes

[入力例]

10 15 10

1 2 8

9 1 2

9 6 6

2 6 1

1 5 5

2 3 2

5 3 3

5 7 11

5 10 12

7 10 8

7 4 7

3 4 1

4 8 4

3 8 10

8 10 5

1 3 5

5 4 2

7 8 17

9 6 12

3 5 6

5 9 4

6 8 7

9 8 3

1 7 10

7 2 6

[出力例]

Yes

■参照サイト
HHKB プログラミングコンテスト 2022（AtCoder Beginner Contest 235）
Union-Find木
 競プロ典型 90 問の問題049

2022年1月18日

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

C++の練習を兼ねて, AtCoder Beginner Contest 235 の問題D (Multiply and Rotate) を解いてみた.

■感想.
1. 問題Dは, とりあえず実装したものの, AC版に到達できず, 解説プログラムを参考に, 修正版で, AC版に到達できたと思う.
2. 幅優先探索(応用版, グラフの頂点数削減)の復習が出来たので, 非常に良かったと思う.
3. 実装に苦労した箇所は, プログラム上に記載した T1 ～ T4 になるが, 個人的には, 落とし穴が, たくさんある印象を受けた.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/abc235/editorial/3255
// 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 pob pop_back
#define pub push_back
#define all(x) x.begin(), x.end()

int main(){
    
    // 1. 入力情報.
    int a, N;
    scanf("%d %d", &a, &N);
    
    // 2. 10 の 冪乗.
    int M = 1;
    while(M <= N) M *= 10;
    
    // 3. bfs.
    // https://ja.wikipedia.org/wiki/幅優先探索
    auto bfs = [&](int s, int* d){
        // 空のキュー.
        queue<int> q;
        
        // 距離を設定.
        d[s] = 0;
        
        // 探索地点 s をキュー q に追加.
        q.push(s);
        while(!q.empty()){
            // キューから取り出す.
            LL cx = (LL)q.front();
            q.pop();
            
            // Nの桁数 プラス 1 以上になった場合, Skip.
            if(cx >= M) continue;
            
            // x を 消して, x * a を 書き込む.
            LL nx1 = cx * a;
            if(nx1 < M && d[(int)nx1] == -1){
                d[(int)nx1] = d[cx] + 1;
                q.push((int)nx1);
            }
            
            // x を 文字列と見做して, 末尾を先頭に移動.
            if(cx >= 10 && cx % 10 != 0){
                string sx = to_string(cx), snx;
                snx.pub(sx.back());
                sx.pob();
                reverse(all(sx));
                while(!sx.empty()){
                    snx.pub(sx.back());
                    sx.pob();
                }
                if(!snx.empty()){
                    LL nx2 = stoll(snx);
                    if(nx2 < M && d[(int)nx2] == -1){
                        d[(int)nx2] = d[cx] + 1;
                        q.push((int)nx2);
                    }
                }
            }
        }
    };
    // [課題]
    // T1. 01_a_eq_2_00.txt などで, TLE版 となったため, ロジック修正が必要.
    // -> 解説プログラムを参考に, map<LL, int> を 廃止し, 配列を使用する形に修正(OK).
    // T2. Runtime Error となる件に対応するため, 配列サイズを, かなり大きめに設定(OK).
    // T3. 03_random_00.txt などの Runtime Error を 防止するため, long long型 を 部分的 に 廃止(OK).
    // -> ex. d[(int)nx1] == -1 の ような実装に修正.
    // T4. bfs の 判定を, nx1 <= M, nx2 <= M から nx1 < M, nx2 < M に 修正(OK).
    int d[M * 10 + 1];
    rep(i, M * 10 + 1) d[i] = -1;
    bfs(1, d);
    
    // 4. 出力.
    printf("%d\n", d[N]);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc235/editorial/3255

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

#define pub push_back

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

int main(){

// 1. 入力情報.

int a, N;

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

// 2. 10 の冪乗.

int M = 1;

while(M <= N) M *= 10;

// 3. bfs.

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

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

// 空のキュー.

queue<int> q;

// 距離を設定.

d[s] = 0;

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

q.push(s);

while(!q.empty()){

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

LL cx = (LL)q.front();

q.pop();

// Nの桁数プラス 1 以上になった場合, Skip.

if(cx >= M) continue;

// x を消して, x * a を書き込む.

LL nx1 = cx * a;

if(nx1 < M && d[(int)nx1] == -1){

d[(int)nx1] = d[cx] + 1;

q.push((int)nx1);

}

// x を文字列と見做して, 末尾を先頭に移動.

if(cx >= 10 && cx % 10 != 0){

string sx = to_string(cx), snx;

snx.pub(sx.back());

sx.pob();

reverse(all(sx));

while(!sx.empty()){

snx.pub(sx.back());

sx.pob();

}

if(!snx.empty()){

LL nx2 = stoll(snx);

if(nx2 < M && d[(int)nx2] == -1){

d[(int)nx2] = d[cx] + 1;

q.push((int)nx2);

}

};

// [課題]

// T1. 01_a_eq_2_00.txt などで, TLE版となったため, ロジック修正が必要.

// -> 解説プログラムを参考に, map<LL, int> を廃止し, 配列を使用する形に修正(OK).

// T2. Runtime Error となる件に対応するため, 配列サイズを, かなり大きめに設定(OK).

// T3. 03_random_00.txt などの Runtime Error を防止するため, long long型を部分的に廃止(OK).

// -> ex. d[(int)nx1] == -1 のような実装に修正.

// T4. bfs の判定を, nx1 <= M, nx2 <= M から nx1 < M, nx2 < M に修正(OK).

int d[M * 10 + 1];

rep(i, M * 10 + 1) d[i] = -1;

bfs(1, d);

// 4. 出力.

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

return 0;

}

[入力例]
3 72

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

[入力例]
2 5

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

[入力例]
2 611

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

[入力例]
2 767090

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

[入力例]
10 1000000

[出力例]
6

[入力例]
7 826630

[出力例]
11

[入力例]
5 320000

[出力例]
8

[入力例]
2 162578

[出力例]
17

[入力例]
3 768690

[出力例]
19

[入力例]
2 522086

[出力例]
19

[入力例]

3 72

[出力例]

※AtCoderテストケースより

[入力例]

2 5

[出力例]

-1

※AtCoderテストケースより

[入力例]

2 611

[出力例]

※AtCoderテストケースより

[入力例]

2 767090

[出力例]

111

※AtCoderテストケースより

[入力例]

10 1000000

[出力例]

[入力例]

7 826630

[出力例]

[入力例]

5 320000

[出力例]

[入力例]

2 162578

[出力例]

[入力例]

3 768690

[出力例]

[入力例]

2 522086

[出力例]

■参照サイト
HHKB プログラミングコンテスト 2022（AtCoder Beginner Contest 235）

C++の練習を兼ねて, JOIG 2021/2022 本選 過去問 の 問題D (いちご 2 (Strawberry 2)) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 133 の 問題A (Erase by Value) ～ 問題B (Dividing Subsequence) を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 103 の 問題E (Tr/ee) を解いてみた.

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

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

C++の練習を兼ねて, 第三回 アルゴリズム実技検定 の 問題G (グリッド金移動) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 235 の 問題C (Counting 2) ～ 問題D (Neighbors) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 235 の 問題D (Multiply and Rotate) を解いてみた.

C++の練習を兼ねて, JOIG 2021/2022 本選過去問の問題D (いちご 2 (Strawberry 2)) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 133 の問題A (Erase by Value) ～問題B (Dividing Subsequence) を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 103 の問題E (Tr/ee) を解いてみた.

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

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

C++の練習を兼ねて, 第三回アルゴリズム実技検定の問題G (グリッド金移動) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 235 の問題C (Counting 2) ～問題D (Neighbors) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 235 の問題D (Multiply and Rotate) を解いてみた.