個人用メモ帳

2021年8月31日

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

C++の練習を兼ねて, 競プロ典型 90 問の問題066 (Various Arrays) を解いてみた.

■感想.
1. 問題066は, 方針が見えなかったので, (問題066 (Various Arrays) 解説) などを参考に実装したところ, AC版に到達出来た.
2. 期待値の性質について, 確認できたので, 非常に良かったと思う.
3. 手強い問題が非常に多い気もするけど, 時間を見つけて, 引き続き, 取り組んでいきたいと思う.

詳細は, 本家のサイト(GitHub) 競プロ典型 90 問の問題066 をご覧下さい.

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

// 解き直し.
// https://github.com/E869120/kyopro_educational_90/blob/main/editorial/066.jpg
// 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 l[111], r[111];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%d %d", &l[i], &r[i]);
    
    // 2. 期待値(解説通り).
    double ans = 0.0;
    rep(i, N){
        repx(j, i + 1, N){
            // 全パターン.
            int a = (r[i] - l[i] + 1) * (r[j] - l[j] + 1);
            
            // 転倒数(a[i] > a[j]).
            int b = 0;
            if(r[i] > l[j]){
                if(l[i] > r[j]) b = a;
                if(l[i] <= r[j]){
                    // r[j] ～ r[i] の 部分.
                    b += max(0, r[i] - r[j]) * (r[j] - l[j] + 1);
                    
                    // max(l[i], l[j]) ～ min(r[i], r[j]) の 部分.
                    int x = min(r[i], r[j]);
                    int y = max(l[i], l[j]);
                    b += ((x - l[j]) + (y - l[j])) * (x - y + 1) / 2;
                }
            }
            
            // 期待値更新.
            ans += (double)b / (double)a;
        }
    }
    
    // 3. 出力.
    printf("%.12lf\n", ans);
    return 0;
    
}

// 解き直し.

// https://github.com/E869120/kyopro_educational_90/blob/main/editorial/066.jpg

// 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 l[111], r[111];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

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

// 2. 期待値(解説通り).

double ans = 0.0;

rep(i, N){

repx(j, i + 1, N){

// 全パターン.

int a = (r[i] - l[i] + 1) * (r[j] - l[j] + 1);

// 転倒数(a[i] > a[j]).

int b = 0;

if(r[i] > l[j]){

if(l[i] > r[j]) b = a;

if(l[i] <= r[j]){

// r[j] ～ r[i] の部分.

b += max(0, r[i] - r[j]) * (r[j] - l[j] + 1);

// max(l[i], l[j]) ～ min(r[i], r[j]) の部分.

int x = min(r[i], r[j]);

int y = max(l[i], l[j]);

b += ((x - l[j]) + (y - l[j])) * (x - y + 1) / 2;

}

// 期待値更新.

ans += (double)b / (double)a;

}

// 3. 出力.

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

return 0;

}

[入力例]
2
1 2
1 2

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

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

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

[入力例]
10
1 10
38 40
8 87
2 9
75 100
45 50
89 92
27 77
23 88
62 81

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

[入力例]
7
38 48
16 34
33 78
29 56
38 60
23 47
46 89

[出力例]
7.511059338519

[入力例]
20
11 30
25 65
7 38
25 37
10 17
46 69
19 21
34 34
38 58
30 77
28 36
9 43
39 52
22 66
23 68
18 57
40 79
14 44
15 52
35 66

[出力例]
71.321298694677

[入力例]
30
28 47
14 42
24 26
21 49
16 54
3 24
22 26
29 65
18 26
10 68
28 62
19 78
22 54
20 66
6 56
14 33
28 49
9 65
4 29
24 38
18 37
28 56
16 18
30 64
9 45
17 17
15 44
20 58
25 55
13 29

[出力例]
222.216725416714

100

101

102

103

104

105

106

107

108

109

110

[入力例]

1 2

[出力例]

0.250000000000

※AtCoderテストケースより

[入力例]

3 3

1 1

4 4

[出力例]

1.000000000000

※AtCoderテストケースより

[入力例]

1 10

38 40

8 87

2 9

75 100

45 50

89 92

27 77

23 88

62 81

[出力例]

13.696758921226

※AtCoderテストケースより

[入力例]

38 48

16 34

33 78

29 56

38 60

23 47

46 89

[出力例]

7.511059338519

[入力例]

11 30

25 65

7 38

25 37

10 17

46 69

19 21

34 34

38 58

30 77

28 36

9 43

39 52

22 66

23 68

18 57

40 79

14 44

15 52

35 66

[出力例]

71.321298694677

[入力例]

28 47

14 42

24 26

21 49

16 54

3 24

22 26

29 65

18 26

10 68

28 62

19 78

22 54

20 66

6 56

14 33

28 49

9 65

4 29

24 38

18 37

28 56

16 18

30 64

9 45

17 17

15 44

20 58

25 55

13 29

[出力例]

222.216725416714

■参照サイト
066 – Various Arrays
問題066 (Various Arrays) 解説

2021年8月29日2021年8月29日

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

C++の練習を兼ねて, 競プロ典型 90 問の問題037 (Don’t Leave the Spice) を解いてみた.

■感想.
1. 問題037は, 方針が見えなかったので, (問題037 (Don’t Leave the Spice) 解説) などを参考に実装したところ, AC版に到達出来た.
2. 新しい知識として, スライド最小値を, 確認できたので, 非常に良かったと思う.
3. 手強い問題が非常に多い気もするけど, 時間を見つけて, 引き続き, 取り組んでいきたいと思う.

詳細は, 本家のサイト(GitHub) 競プロ典型 90 問の問題037 をご覧下さい.

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

// 解き直し.
// https://github.com/E869120/kyopro_educational_90/blob/main/editorial/037.jpg
// 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 pof pop_front
#define pob pop_back
#define pub push_back
#define puf push_front
int l[505], r[505];
LL v[505], dp[505][10101];

int main(){
    
    // 1. 入力情報.
    int W, N;
    scanf("%d %d", &W, &N);
    rep(i, N) scanf("%d %d %lld", &l[i + 1], &r[i + 1], &v[i + 1]);
    
    // 2. dp更新(解説通り).
    rep(i, 505) rep(j, 10101) dp[i][j] = -1;
    dp[0][0] = 0;
    repx(i, 1, N + 1){
        deque<int> dq;
        int k = r[i] - l[i] + 1; // 有効な区間幅.
        rep(j, W + 1){
            // 選ばない場合.
            dp[i][j] = dp[i - 1][j];
            
            // インデックスが有効か？
            if(j < l[i]) continue;
            
            // スライド最小値.
            // https://phwinx.hatenablog.com/entry/2018/11/17/042646
            // -> 先頭要素に, 最大値が保存されている状態を目指す.
            int cur = j - l[i];
            while(!dq.empty()){
                int e = dq.back();
                if(dp[i - 1][e] <= dp[i - 1][cur]) dq.pob();
                else                               break;
            }
            dq.pub(cur);
            int s = dq.front();
            if(s + l[i] == j - k) dq.pof();
            
            // deque が 空 になってないか？
            if(dq.empty()) continue;
            
            // dp更新可能か？
            s = dq.front();
            if(dp[i - 1][s] == -1) continue;
            
            // 選ぶ場合.
            dp[i][j] = max(dp[i][j], dp[i - 1][s] + v[i]);
        }
    }
    
    // 3. 出力.
    printf("%lld\n", dp[N][W]);
    return 0;
    
}

// 解き直し.

// https://github.com/E869120/kyopro_educational_90/blob/main/editorial/037.jpg

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

#define pob pop_back

#define pub push_back

#define puf push_front

int l[505], r[505];

LL v[505], dp[505][10101];

int main(){

// 1. 入力情報.

int W, N;

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

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

// 2. dp更新(解説通り).

rep(i, 505) rep(j, 10101) dp[i][j] = -1;

dp[0][0] = 0;

repx(i, 1, N + 1){

deque<int> dq;

int k = r[i] - l[i] + 1; // 有効な区間幅.

rep(j, W + 1){

// 選ばない場合.

dp[i][j] = dp[i - 1][j];

// インデックスが有効か？

if(j < l[i]) continue;

// スライド最小値.

// https://phwinx.hatenablog.com/entry/2018/11/17/042646

// -> 先頭要素に, 最大値が保存されている状態を目指す.

int cur = j - l[i];

while(!dq.empty()){

int e = dq.back();

if(dp[i - 1][e] <= dp[i - 1][cur]) dq.pob();

else break;

}

dq.pub(cur);

int s = dq.front();

if(s + l[i] == j - k) dq.pof();

// deque が空になってないか？

if(dq.empty()) continue;

// dp更新可能か？

s = dq.front();

if(dp[i - 1][s] == -1) continue;

// 選ぶ場合.

dp[i][j] = max(dp[i][j], dp[i - 1][s] + v[i]);

}

// 3. 出力.

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

return 0;

}

[入力例]
100 4
30 40 120
30 40 30
30 40 1500
30 40 40

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

[入力例]
100 4
13 15 31415
12 13 92653
29 33 58979
95 98 32384

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

[入力例]
5000 5
1000 1000 1000000000
1000 1000 1000000000
1000 1000 1000000000
1000 1000 1000000000
1000 1000 1000000000

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

[入力例]
10000 20
4539 6002 485976
1819 5162 457795
1854 2246 487643
1023 4733 393530
1052 6274 289577
1874 2436 167747
1457 4248 452660
2103 4189 174955
3057 5061 319316
4898 4953 394627
1313 2880 154687
1274 1364 259598
3866 5844 233027
1163 5036 386223
1234 4630 155972
2845 4978 442858
3168 5368 171601
3708 4407 394899
3924 4122 428313
2112 4169 441976

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

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

[出力例]
-1

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

[出力例]
13

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

[出力例]
15

[入力例]
300 10 
18 87 15
117 206 14
40 140 7
41 76 3
119 123 11
61 157 13
10 17 3
74 193 18
106 193 10
48 81 3

[出力例]
63

[入力例]
2021 20 
183 189 155689
130 137 1206900
153 156 525365
89 99 717566
208 216 888757
95 100 804792
34 43 189160
22 29 984929
87 94 970880
7 12 234533
109 118 1208356
80 86 337394
45 54 279909
84 87 1115989
15 20 443194
14 16 416494
22 31 1076301
93 97 1083443
30 34 58830
115 118 234045

[出力例]
-1

[入力例]
2022 30 
15 20 294055
15 24 671762
46 53 724087
95 102 498068
16 18 208208
18 25 313671
55 58 824721
108 112 206751
50 52 389291
108 110 384652
124 130 279184
85 87 24088
64 71 1182134
62 65 755468
114 119 1078425
23 32 410211
109 111 949466
88 97 497373
98 108 797655
68 74 876269
40 47 817773
34 40 901397
84 85 898356
123 124 253600
75 81 773194
107 109 281478
53 61 980821
21 29 629501
25 31 370663
112 120 125819

[出力例]
17374053

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

[入力例]

100 4

30 40 120

30 40 30

30 40 1500

30 40 40

[出力例]

1660

※AtCoderのテストケースより

[入力例]

100 4

13 15 31415

12 13 92653

29 33 58979

95 98 32384

[出力例]

-1

※AtCoderのテストケースより

[入力例]

5000 5

1000 1000 1000000000

[出力例]

5000000000

※AtCoderのテストケースより

[入力例]

10000 20

4539 6002 485976

1819 5162 457795

1854 2246 487643

1023 4733 393530

1052 6274 289577

1874 2436 167747

1457 4248 452660

2103 4189 174955

3057 5061 319316

4898 4953 394627

1313 2880 154687

1274 1364 259598

3866 5844 233027

1163 5036 386223

1234 4630 155972

2845 4978 442858

3168 5368 171601

3708 4407 394899

3924 4122 428313

2112 4169 441976

[出力例]

2727026

※AtCoderのテストケースより

[入力例]

10 2

1 1 3

3 3 5

[出力例]

-1

[入力例]

10 3

1 1 3

3 3 5

6 6 5

[出力例]

[入力例]

17 5

1 1 3

3 3 5

5 5 2

7 7 4

9 9 8

[出力例]

[入力例]

300 10

18 87 15

117 206 14

40 140 7

41 76 3

119 123 11

61 157 13

10 17 3

74 193 18

106 193 10

48 81 3

[出力例]

[入力例]

2021 20

183 189 155689

130 137 1206900

153 156 525365

89 99 717566

208 216 888757

95 100 804792

34 43 189160

22 29 984929

87 94 970880

7 12 234533

109 118 1208356

80 86 337394

45 54 279909

84 87 1115989

15 20 443194

14 16 416494

22 31 1076301

93 97 1083443

30 34 58830

115 118 234045

[出力例]

-1

[入力例]

2022 30

15 20 294055

15 24 671762

46 53 724087

95 102 498068

16 18 208208

18 25 313671

55 58 824721

108 112 206751

50 52 389291

108 110 384652

124 130 279184

85 87 24088

64 71 1182134

62 65 755468

114 119 1078425

23 32 410211

109 111 949466

88 97 497373

98 108 797655

68 74 876269

40 47 817773

34 40 901397

84 85 898356

123 124 253600

75 81 773194

107 109 281478

53 61 980821

21 29 629501

25 31 370663

112 120 125819

[出力例]

17374053

■参照サイト
037 – Don’t Leave the Spice
問題037 (Don’t Leave the Spice) 解説
 スライド最小値

2021年8月26日

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

C++の練習を兼ねて, 競プロ典型 90 問の問題087 (Chokudai’s Demand) を解いてみた.

■感想.
1. 問題087は, 方針が見えなかったので, (問題087 (Chokudai’s Demand) 解説) などを参考に実装したところ, AC版に到達出来た.
2. 二分探索, ワーシャル–フロイド法の復習が出来たので, 非常に良かったと思う.
3. 手強い問題が非常に多い気もするけど, 時間を見つけて, 引き続き, 取り組んでいきたいと思う.

詳細は, 本家のサイト(GitHub) 競プロ典型 90 問の問題087 をご覧下さい.

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

// 解き直し.
// https://github.com/E869120/kyopro_educational_90/blob/main/editorial/087-01.jpg
// https://github.com/E869120/kyopro_educational_90/blob/main/editorial/087-02.jpg
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
const LL INF = 202020202020202020;
LL o[44][44]; // 交通費(入力情報).

int main(){
    
    // 1. 入力情報.
    int N, K;
    LL P;
    scanf("%d %lld %d", &N, &P, &K);
    rep(i, N) rep(j, N) scanf("%lld", &o[i][j]);
    
    // 2. 判定関数.
    auto f = [&](LL X, char c) -> bool{
        // 2-1. 初期化.
        LL a[N][N];
        int cnt = 0;
        rep(i, N) rep(j, N) a[i][j] = (o[i][j] == -1) ? X : o[i][j];
        
        // 2-2. Warshall–Floyd法(※各頂点間の最短距離を保存).
        rep(k, N) rep(i, N) rep(j, N) a[i][j] = min(a[i][j], a[i][k] + a[k][j]);
        
        // 2-3. Pヌーク以下の個数をカウント.
        rep(i, N) repx(j, i + 1, N) if(a[i][j] <= P) cnt++;
        
        // 2-4. 判定結果.
        return (c == 'L') ? (cnt <= K) : (cnt < K);
    };
    
    // 3. 左端を, 二分探索で確認してみる.
    LL l = 0, h = INF, m, L = 0, R = 0;
    while(l + 1 < h){
        m = (h + l) >> 1;
        if(f(m, 'L')) h = m;
        else          l = m;
        // printf("h=%lld l=%lld m=%lld\n", h, l, m);
    }
    L = h;
    
    // 4. 右端を, 二分探索で確認してみる.
    l = 0, h = INF;
    while(l + 1 < h){
        m = (h + l) >> 1;
        if(f(m, 'R')) h = m;
        else          l = m;
        // printf("h=%lld l=%lld m=%lld\n", h, l, m);
    }
    R = h;
    
    // 5. 出力.
    // -> R のみ INF の 場合は, Infinity と見る.
    if(L != INF && R == INF) puts("Infinity");
    else                     printf("%lld\n", R - L);
    return 0;
    
}

// 解き直し.

// https://github.com/E869120/kyopro_educational_90/blob/main/editorial/087-01.jpg

// https://github.com/E869120/kyopro_educational_90/blob/main/editorial/087-02.jpg

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

const LL INF = 202020202020202020;

LL o[44][44]; // 交通費(入力情報).

int main(){

// 1. 入力情報.

int N, K;

LL P;

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

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

// 2. 判定関数.

auto f = [&](LL X, char c) -> bool{

// 2-1. 初期化.

LL a[N][N];

int cnt = 0;

rep(i, N) rep(j, N) a[i][j] = (o[i][j] == -1) ? X : o[i][j];

// 2-2. Warshall–Floyd法(※各頂点間の最短距離を保存).

rep(k, N) rep(i, N) rep(j, N) a[i][j] = min(a[i][j], a[i][k] + a[k][j]);

// 2-3. Pヌーク以下の個数をカウント.

rep(i, N) repx(j, i + 1, N) if(a[i][j] <= P) cnt++;

// 2-4. 判定結果.

return (c == 'L') ? (cnt <= K) : (cnt < K);

};

// 3. 左端を, 二分探索で確認してみる.

LL l = 0, h = INF, m, L = 0, R = 0;

while(l + 1 < h){

m = (h + l) >> 1;

if(f(m, 'L')) h = m;

else l = m;

// printf("h=%lld l=%lld m=%lld\n", h, l, m);

}

L = h;

// 4. 右端を, 二分探索で確認してみる.

l = 0, h = INF;

while(l + 1 < h){

m = (h + l) >> 1;

if(f(m, 'R')) h = m;

else l = m;

// printf("h=%lld l=%lld m=%lld\n", h, l, m);

}

R = h;

// 5. 出力.

// -> R のみ INF の場合は, Infinity と見る.

if(L != INF && R == INF) puts("Infinity");

else printf("%lld\n", R - L);

return 0;

}

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

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

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

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

[入力例]
13 777 77
0 425 886 764 736 -1 692 660 -1 316 424 490 423
425 0 -1 473 -1 311 -1 -1 903 941 386 521 486
886 -1 0 605 519 473 775 467 677 769 690 483 501
764 473 605 0 424 454 474 408 421 530 756 568 685
736 -1 519 424 0 -1 804 598 911 731 837 459 610
-1 311 473 454 -1 0 479 613 880 -1 393 875 334
692 -1 775 474 804 479 0 579 -1 -1 575 985 603
660 -1 467 408 598 613 579 0 456 378 887 -1 372
-1 903 677 421 911 880 -1 456 0 859 701 476 370
316 941 769 530 731 -1 -1 378 859 0 800 870 740
424 386 690 756 837 393 575 887 701 800 0 -1 304
490 521 483 568 459 875 985 -1 476 870 -1 0 716
423 486 501 685 610 334 603 372 370 740 304 716 0

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

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

[出力例]
3

[入力例]
10 666 43
0 540 1208 443 -1 1062 221 926 824 572
540 0 348 614 997 557 -1 738 637 8
1208 348 0 -1 1188 -1 1076 672 208 325
443 614 -1 0 226 443 -1 1049 -1 847
-1 997 1188 226 0 777 307 -1 816 802
1062 557 -1 443 777 0 718 130 676 341
221 -1 1076 -1 307 718 0 76 552 645
926 738 672 1049 -1 130 76 0 469 615
824 637 208 -1 816 676 552 469 0 780
572 8 325 847 802 341 645 615 780 0

[出力例]
112

[入力例]

3 4 2

0 3 -1

3 0 5

-1 5 0

[出力例]

※AtCoderテストケースより

[入力例]

3 10 2

0 -1 10

-1 0 1

10 1 0

[出力例]

Infinity

※AtCoderテストケースより

[入力例]

13 777 77

0 425 886 764 736 -1 692 660 -1 316 424 490 423

425 0 -1 473 -1 311 -1 -1 903 941 386 521 486

886 -1 0 605 519 473 775 467 677 769 690 483 501

764 473 605 0 424 454 474 408 421 530 756 568 685

736 -1 519 424 0 -1 804 598 911 731 837 459 610

-1 311 473 454 -1 0 479 613 880 -1 393 875 334

692 -1 775 474 804 479 0 579 -1 -1 575 985 603

660 -1 467 408 598 613 579 0 456 378 887 -1 372

-1 903 677 421 911 880 -1 456 0 859 701 476 370

316 941 769 530 731 -1 -1 378 859 0 800 870 740

424 386 690 756 837 393 575 887 701 800 0 -1 304

490 521 483 568 459 875 985 -1 476 870 -1 0 716

423 486 501 685 610 334 603 372 370 740 304 716 0

[出力例]

※AtCoderテストケースより

[入力例]

4 5 4

0 5 -1 7

5 0 6 -1

-1 6 0 3

7 -1 3 0

[出力例]

[入力例]

10 666 43

0 540 1208 443 -1 1062 221 926 824 572

540 0 348 614 997 557 -1 738 637 8

1208 348 0 -1 1188 -1 1076 672 208 325

443 614 -1 0 226 443 -1 1049 -1 847

-1 997 1188 226 0 777 307 -1 816 802

1062 557 -1 443 777 0 718 130 676 341

221 -1 1076 -1 307 718 0 76 552 645

926 738 672 1049 -1 130 76 0 469 615

824 637 208 -1 816 676 552 469 0 780

572 8 325 847 802 341 645 615 780 0

[出力例]

112

■参照サイト
087 – Chokudai’s Demand
問題087 (Chokudai’s Demand) 解説(その１)
問題087 (Chokudai’s Demand) 解説(その２)

2021年8月25日

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

C++の練習を兼ねて, 競プロ典型 90 問の問題086 (Snuke’s Favorite Arrays) を解いてみた.

■感想.
1. 問題086は, 方針が見えなかったので, (問題086 (Snuke’s Favorite Arrays) 解説) などを参考に実装したところ, AC版に到達出来た.
2. 個人的には, 各桁(bit)ごとに, 独立して計算できるロジックが, 非常に面白い問題に感じた.
3. 手強い問題が非常に多い気もするけど, 時間を見つけて, 引き続き, 取り組んでいきたいと思う.

詳細は, 本家のサイト(GitHub) 競プロ典型 90 問の問題086 をご覧下さい.

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

// 解き直し.
// https://github.com/E869120/kyopro_educational_90/blob/main/editorial/086-01.jpg
// https://github.com/E869120/kyopro_educational_90/blob/main/editorial/086-02.jpg
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
const LL MOD = 1e9 + 7;
int x[55], y[55], z[55];
LL w[55];

int main(){
    
    // 1. 入力情報.
    int N, Q;
    scanf("%d %d", &N, &Q);
    rep(i, Q){
        scanf("%d %d %d %lld", &x[i], &y[i], &z[i], &w[i]);
        x[i]--;
        y[i]--;
        z[i]--;
    }
    
    // 2. 数列 A の 個数をカウント.
    LL ans = 1;
    rep(i, 60){
        // 数列 A(i桁目) の パターン を 全探索.
        // ex.
        // 10110
        // -> 以下のように解釈.
        // A[0] の i桁目 … 0
        // A[1] の i桁目 … 1
        // A[2] の i桁目 … 1
        // A[3] の i桁目 … 0
        // A[4] の i桁目 … 1
        LL a = 0;
        rep(j, 1 << N){
            // Q個の条件を満たすか？
            bool ok = true;
            rep(k, Q){
                int xBit = (j >> x[k]) & 1;
                int yBit = (j >> y[k]) & 1;
                int zBit = (j >> z[k]) & 1;
                LL wBit = (w[k] >> i) & 1LL;
                if((LL)(xBit | yBit | zBit) != wBit){
                    ok = false;
                    break;
                }
            }
            
            // カウント.
            if(ok) a++;
        }
        
        // 集計.
        ans *= a;
        ans %= MOD;
    }
    
    // 3. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://github.com/E869120/kyopro_educational_90/blob/main/editorial/086-01.jpg

// https://github.com/E869120/kyopro_educational_90/blob/main/editorial/086-02.jpg

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

const LL MOD = 1e9 + 7;

int x[55], y[55], z[55];

LL w[55];

int main(){

// 1. 入力情報.

int N, Q;

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

rep(i, Q){

scanf("%d %d %d %lld", &x[i], &y[i], &z[i], &w[i]);

x[i]--;

y[i]--;

z[i]--;

}

// 2. 数列 A の個数をカウント.

LL ans = 1;

rep(i, 60){

// 数列 A(i桁目) のパターンを全探索.

// ex.

// 10110

// -> 以下のように解釈.

// A[0] の i桁目 … 0

// A[1] の i桁目 … 1

// A[2] の i桁目 … 1

// A[3] の i桁目 … 0

// A[4] の i桁目 … 1

LL a = 0;

rep(j, 1 << N){

// Q個の条件を満たすか？

bool ok = true;

rep(k, Q){

int xBit = (j >> x[k]) & 1;

int yBit = (j >> y[k]) & 1;

int zBit = (j >> z[k]) & 1;

LL wBit = (w[k] >> i) & 1LL;

if((LL)(xBit | yBit | zBit) != wBit){

ok = false;

break;

}

// カウント.

if(ok) a++;

}

// 集計.

ans *= a;

ans %= MOD;

}

// 3. 出力.

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

return 0;

}

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

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

[入力例]
8 2
2 3 6 1152886174205865983
1 2 8 1116611213275394047

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

[入力例]
5 3
1 2 5 29
2 3 4 13
3 4 5 12

[出力例]
1058

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

[出力例]
1125

[入力例]
7 5
1 2 5 119
1 3 4 29
1 3 7 31
2 4 5 127
2 5 6 123

[出力例]
17428608

[入力例]

4 2

1 2 3 50

2 3 4 45

[出力例]

※AtCoderテストケースより

[入力例]

8 2

2 3 6 1152886174205865983

1 2 8 1116611213275394047

[出力例]

395781543

※AtCoderテストケースより

[入力例]

5 3

1 2 5 29

2 3 4 13

3 4 5 12

[出力例]

1058

[入力例]

6 3

1 2 5 41

2 3 4 40

1 3 6 9

[出力例]

1125

[入力例]

7 5

1 2 5 119

1 3 4 29

1 3 7 31

2 4 5 127

2 5 6 123

[出力例]

17428608

■参照サイト
086 – Snuke’s Favorite Arrays
問題086 (Snuke’s Favorite Arrays) 解説(その１)
問題086 (Snuke’s Favorite Arrays) 解説(その２)

2021年8月24日2021年8月24日

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

C++の練習を兼ねて, 競プロ典型 90 問の問題083 (Colorful Graph) を解いてみた.

■感想.
1. 問題083は, 方針が見えなかったので, (問題083 (Colorful Graph) 解説) などを参考に実装したところ, AC版に到達出来た.
2. 個人的には, 計算量削減のために, グラフを二つ作成するロジックが, 非常に面白い問題に感じた.
3. 手強い問題が非常に多い気もするけど, 時間を見つけて, 引き続き, 取り組んでいきたいと思う.

詳細は, 本家のサイト(GitHub) 競プロ典型 90 問の問題083 をご覧下さい.

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

// 解き直し.
// https://github.com/E869120/kyopro_educational_90/blob/main/editorial/083-01.jpg
// https://github.com/E869120/kyopro_educational_90/blob/main/editorial/083-02.jpg
// https://github.com/E869120/kyopro_educational_90/blob/main/editorial/083-03.jpg
// 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 e[202020]; // {各頂点番号, 最後に, クエリによる処理が行われたクエリ番号}.
int q[202020]; // {クエリ番号, 色}.
int c[202020]; // {頂点番号, 色}.

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    vvi G(N), F(N);
    rep(i, M){
        int a, b;
        scanf("%d %d", &a, &b);
        a--, b--;
        G[a].pb(b);
        G[b].pb(a);
    }
    
    // 2. 部分グラフ作成(次数が大きい頂点に向かう頂点のみ辺を追加).
    int B = (int)sqrt(2 * M);
    rep(i, N) if(G[i].size() >= B) for(auto &p : G[i]) F[p].pb(i);
    
    // 3. クエリ回答.
    int Q;
    q[0] = 1;
    rep(i, N) c[i] = 1;
    scanf("%d", &Q);
    rep(i, Q){
        // 3-1. クエリ情報.
        int x, y;
        scanf("%d %d", &x, &y);
        x--;
        
        // 3-2. 隣接する頂点数が大きい場合.
        int n = G[x].size();
        if(n > B){
            // 出力.
            printf("%d\n", c[x]);
            
            // 更新(隣接頂点).
            for(auto &u : F[x]) c[u] = y;
        }
        
        // 3-3. 隣接する頂点数が小さい場合.
        if(n <= B){
            // 最大値.
            int eMax = e[x];
            for(auto &u : G[x]) eMax = max(eMax, e[u]);
            
            // 出力.
            printf("%d\n", q[eMax]);
            
            // 更新(隣接頂点).
            for(auto &u : G[x]) c[u] = y;
        }
        
        // 3-4. 更新(自分自身).
        e[x] = i + 1;
        c[x] = y;
        
        // 3-5. クエリ保存.
        q[i + 1] = y;
    }
    return 0;
    
}

// 解き直し.

// https://github.com/E869120/kyopro_educational_90/blob/main/editorial/083-01.jpg

// https://github.com/E869120/kyopro_educational_90/blob/main/editorial/083-02.jpg

// https://github.com/E869120/kyopro_educational_90/blob/main/editorial/083-03.jpg

// 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 e[202020]; // {各頂点番号, 最後に, クエリによる処理が行われたクエリ番号}.

int q[202020]; // {クエリ番号, 色}.

int c[202020]; // {頂点番号, 色}.

int main(){

// 1. 入力情報.

int N, M;

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

vvi G(N), F(N);

rep(i, M){

int a, b;

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

a--, b--;

G[a].pb(b);

G[b].pb(a);

}

// 2. 部分グラフ作成(次数が大きい頂点に向かう頂点のみ辺を追加).

int B = (int)sqrt(2 * M);

rep(i, N) if(G[i].size() >= B) for(auto &p : G[i]) F[p].pb(i);

// 3. クエリ回答.

int Q;

q[0] = 1;

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

scanf("%d", &Q);

rep(i, Q){

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

int x, y;

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

x--;

// 3-2. 隣接する頂点数が大きい場合.

int n = G[x].size();

if(n > B){

// 出力.

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

// 更新(隣接頂点).

for(auto &u : F[x]) c[u] = y;

}

// 3-3. 隣接する頂点数が小さい場合.

if(n <= B){

// 最大値.

int eMax = e[x];

for(auto &u : G[x]) eMax = max(eMax, e[u]);

// 出力.

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

// 更新(隣接頂点).

for(auto &u : G[x]) c[u] = y;

}

// 3-4. 更新(自分自身).

e[x] = i + 1;

c[x] = y;

// 3-5. クエリ保存.

q[i + 1] = y;

}

return 0;

}

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

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

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

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

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

[出力例]
1
3
5
2
7

[入力例]
12 16
1 10
6 1
3 1
4 1
3 5
3 9
9 10
11 10
11 12
12 6
6 4
6 7
4 2
2 7
2 8
8 7
20
7 103
3 29
10 7
12 115
7 64
1 25
10 26
7 16
12 122
9 42
4 75
11 112
7 26
1 104
4 66
12 55
5 19
11 39
6 45
12 61

[出力例]
1
1
1
1
103
7
25
64
115
26
25
122
16
75
104
112
29
55
55
45

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

[入力例]

4 4

1 2

1 3

1 4

2 3

4 2

3 3

2 4

4 5

1 6

[出力例]

※AtCoderテストケースより

[入力例]

10 20

1 3

7 8

5 8

2 3

7 10

6 7

4 7

9 5

6 5

2 9

4 2

5 7

3 10

4 8

1 8

10 8

5 3

9 1

7 3

2 1

3 5

2 2

8 9

5 3

8 2

3 9

7 1

8 4

6 8

[出力例]

※AtCoderテストケースより

[入力例]

5 4

1 2

1 3

3 5

3 4

1 3

3 5

5 2

3 7

1 6

[出力例]

[入力例]

12 16

1 10

6 1

3 1

4 1

3 5

3 9

9 10

11 10

11 12

12 6

6 4

6 7

4 2

2 7

2 8

8 7

7 103

3 29

10 7

12 115

7 64

1 25

10 26

7 16

12 122

9 42

4 75

11 112

7 26

1 104

4 66

12 55

5 19

11 39

6 45

12 61

[出力例]

103

115

122

104

112

■参照サイト
083 – Colorful Graph
問題083 (Colorful Graph) 解説(その１)
問題083 (Colorful Graph) 解説(その２)
問題083 (Colorful Graph) 解説(その３)
問題083 (Colorful Graph) 解説(その４)

2021年8月22日2021年8月22日

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

C++の練習を兼ねて, 競プロ典型 90 問の問題080 (Let’s Share Bit) を解いてみた.

■感想.
1. 問題080は, 方針が見えなかったので, (問題080 (Let’s Share Bit) 解説) を参考に実装したところ, AC版に到達出来た.
2. 包除原理に関する訓練が出来たので, 非常に良かったと思う.
3. 手強い問題が非常に多い気もするけど, 時間を見つけて, 引き続き, 取り組んでいきたいと思う.

詳細は, 本家のサイト(GitHub) 競プロ典型 90 問の問題080 をご覧下さい.

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

// 解き直し.
// https://github.com/E869120/kyopro_educational_90/blob/main/editorial/080.jpg
// 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[22];

int main(){
    
    // 1. 入力情報.
    int N, D;
    scanf("%d %d", &N, &D);
    rep(i, N) scanf("%lld", &a[i]);
    
    // 2. 条件を満たすものをカウント(解説通り).
    LL ans = 1LL << D;
    repx(bit, 1, 1 << N){
        LL x = 0;
        repr(i, N - 1, 0) if(bit & (1 << i)) x |= a[i];
        LL f = 1LL << (D - __builtin_popcountll(x));
        ans += (1 & __builtin_popcount(bit)) ? -f : f;
    }
    
    // 3. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://github.com/E869120/kyopro_educational_90/blob/main/editorial/080.jpg

// 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[22];

int main(){

// 1. 入力情報.

int N, D;

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

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

// 2. 条件を満たすものをカウント(解説通り).

LL ans = 1LL << D;

repx(bit, 1, 1 << N){

LL x = 0;

repr(i, N - 1, 0) if(bit & (1 << i)) x |= a[i];

LL f = 1LL << (D - __builtin_popcountll(x));

ans += (1 & __builtin_popcount(bit)) ? -f : f;

}

// 3. 出力.

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

return 0;

}

[入力例]
4 3
1 3 4 5

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

[入力例]
5 21
1050624 32772 493952 144 869120

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

[入力例]
20 60
216181578206878016 81348488767472704 26388280246272 281543729742896 72127981178847488 2199108462600 585610888171487234 22027813536776 567459673280576 146648462866649600 144484898860704776 576471786208755714 4398621196432 144141576657960976 81069330992726040 360851057582278674 17859112 11570646360064 144115206396936193 1702052723957760

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

[入力例]
3 5
2 17 23

[出力例]
12

[入力例]
18 10
314 159 265 358 979 323 846 264 338 327 950 288 419 716 939 937 510 582

[出力例]
568

[入力例]
10 30
22275554 98136531 84288905 53485744 99268102 84582267 122830211 99671610 58981632 96084779

[出力例]
1068048752

[入力例]

4 3

1 3 4 5

[出力例]

※AtCoderテストケースより

[入力例]

5 21

1050624 32772 493952 144 869120

[出力例]

869120

※AtCoderテストケースより

[入力例]

20 60

216181578206878016 81348488767472704 26388280246272 281543729742896 72127981178847488 2199108462600 585610888171487234 22027813536776 567459673280576 146648462866649600 144484898860704776 576471786208755714 4398621196432 144141576657960976 81069330992726040 360851057582278674 17859112 11570646360064 144115206396936193 1702052723957760

[出力例]

977902973481140224

※AtCoderテストケースより

[入力例]

3 5

2 17 23

[出力例]

[入力例]

18 10

314 159 265 358 979 323 846 264 338 327 950 288 419 716 939 937 510 582

[出力例]

568

[入力例]

10 30

22275554 98136531 84288905 53485744 99268102 84582267 122830211 99671610 58981632 96084779

[出力例]

1068048752

■参照サイト
080 – Let’s Share Bit
問題080 (Let’s Share Bit) 解説

2021年8月21日

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

C++の練習を兼ねて, 競プロ典型 90 問の問題074 (ABC String 2) を解いてみた.

■感想.
1. 問題074は, 方針が見えなかったので, (問題074 (ABC String 2) 解説) を参考に実装したところ, AC版に到達出来た.
2. 個人的には, 数式で計算できてしまう点が, 非常に面白い問題に感じた.
3. 手強い問題が非常に多い気もするけど, 時間を見つけて, 引き続き, 取り組んでいきたいと思う.

詳細は, 本家のサイト(GitHub) 競プロ典型 90 問の問題074 をご覧下さい.

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

// 解き直し.
// https://github.com/E869120/kyopro_educational_90/blob/main/editorial/074.jpg
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)

int main(){
    
    // 1. 入力情報.
    int N;
    char c[66];
    scanf("%d %s", &N, c);
    
    // 2. 操作回数の最大値(解説通り).
    LL ans = 0;
    rep(i, N) ans += (1LL << i) * (LL)(c[i] - 'a');
    
    // 3. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://github.com/E869120/kyopro_educational_90/blob/main/editorial/074.jpg

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

int main(){

// 1. 入力情報.

int N;

char c[66];

scanf("%d %s", &N, c);

// 2. 操作回数の最大値(解説通り).

LL ans = 0;

rep(i, N) ans += (1LL << i) * (LL)(c[i] - 'a');

// 3. 出力.

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

return 0;

}

[入力例]
3
aba

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

[入力例]
10
aaaaaaaaaa

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

[入力例]
5
baaca

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

[入力例]
24
babaacbaaabaabbaaababbac

[出力例]
20210821

[入力例]
45
cbabbabbbaaaaacaccbcbcabbbbaabbbcbaabbbaaaaaa

[出力例]
502107111900

[入力例]

aba

[出力例]

※AtCoderテストケースより

[入力例]

aaaaaaaaaa

[出力例]

※AtCoderテストケースより

[入力例]

baaca

[出力例]

※AtCoderテストケースより

[入力例]

babaacbaaabaabbaaababbac

[出力例]

20210821

[入力例]

cbabbabbbaaaaacaccbcbcabbbbaabbbcbaabbbaaaaaa

[出力例]

502107111900

■参照サイト
074 – ABC String 2
問題074 (ABC String 2) 解説

2021年8月21日2021年8月21日

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

C++の練習を兼ねて, 競プロ典型 90 問の問題062 (Paint All) を解いてみた.

■感想.
1. 問題062は, 方針が見えなかったので, (問題062 (Paint All) 解説) を参考に実装したところ, AC版に到達出来た.
2. 個人的には, 逆順から考えるという視点が, 非常に面白い問題に感じた.
3. 手強い問題が非常に多い気もするけど, 時間を見つけて, 引き続き, 取り組んでいきたいと思う.

詳細は, 本家のサイト(GitHub) 競プロ典型 90 問の問題062 をご覧下さい.

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

// 解き直し.
// https://github.com/E869120/kyopro_educational_90/blob/main/editorial/062.jpg
// 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;
    vi x;
    scanf("%d", &N);
    vvi G(N);
    rep(i, N){
        int a, b;
        scanf("%d %d", &a, &b);
        a--, b--;
        G[a].pb(i);
        G[b].pb(i);
        if((a == i) || (b == i)) x.pb(i);
    }
    
    // 2. 不可能な場合.
    if(x.size() == 0){
        puts("-1");
        return 0;
    }
    
    // 3. 指定した頂点から操作を進めていく.
    // https://ja.wikipedia.org/wiki/幅優先探索
    // -> 本問は, bfs に, 類似した実装で, 対応可能と見る.
    vi ans;
    auto bfs = [&](vvi &G, int s, int* d){
        // 3-1. 空のキュー.
        queue<int> q;
        
        // 3-2. 訪問済みフラグ設定.
        d[s] = 1;
        
        // 3-3. 探索地点 s をキュー q に追加.
        q.push(s);
        
        // 3-4. キューが空になるまで処理.
        while(!q.empty()){
            // 3-5. 頂点を取り出す.
            int u = q.front();
            q.pop();
            
            // 3-6. 操作の保存.
            ans.pb(u);
            
            // 3-7. 取り出した要素を処理.
            for(auto &e : G[u]){
                // 3-8. 未訪問の頂点を処理.
                if(!d[e]) d[e] = 1, q.push(e);
            }
        }
        return;
    };
    int d[N];
    rep(i, N) d[i] = 0;
    for(auto &s : x) if(!d[s]) bfs(G, s, d);
    // rep(i, N) printf("%d ", d[i]);
    // puts("");
    
    // 4. 不可能な場合.
    if(ans.size() != N){
        puts("-1");
        return 0;
    }
    
    // 5. 出力.
    repr(i, N - 1, 0) printf("%d\n", ans[i] + 1);
    return 0;
    
}

// 解き直し.

// https://github.com/E869120/kyopro_educational_90/blob/main/editorial/062.jpg

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

vi x;

scanf("%d", &N);

vvi G(N);

rep(i, N){

int a, b;

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

a--, b--;

G[a].pb(i);

G[b].pb(i);

if((a == i) || (b == i)) x.pb(i);

}

// 2. 不可能な場合.

if(x.size() == 0){

puts("-1");

return 0;

}

// 3. 指定した頂点から操作を進めていく.

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

// -> 本問は, bfs に, 類似した実装で, 対応可能と見る.

vi ans;

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

// 3-1. 空のキュー.

queue<int> q;

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

d[s] = 1;

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

q.push(s);

// 3-4. キューが空になるまで処理.

while(!q.empty()){

// 3-5. 頂点を取り出す.

int u = q.front();

q.pop();

// 3-6. 操作の保存.

ans.pb(u);

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

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

// 3-8. 未訪問の頂点を処理.

if(!d[e]) d[e] = 1, q.push(e);

}

return;

};

int d[N];

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

for(auto &s : x) if(!d[s]) bfs(G, s, d);

// rep(i, N) printf("%d ", d[i]);

// puts("");

// 4. 不可能な場合.

if(ans.size() != N){

puts("-1");

return 0;

}

// 5. 出力.

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

return 0;

}

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

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

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

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

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

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

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

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

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

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

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

[出力例]
5
4
2
1
3

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

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

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

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

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

[入力例]

3 4

1 3

2 3

2 1

[出力例]

※AtCoderテストケースより

[入力例]

1 1

2 2

3 3

[出力例]

※AtCoderテストケースより

[入力例]

3 4

4 5

1 1

5 1

3 2

[出力例]

-1

※AtCoderテストケースより

[入力例]

5 5

2 4

6 6

5 2

1 3

4 1

[出力例]

※AtCoderテストケースより

[入力例]

5 1

3 9

7 8

9 3

3 7

10 10

3 5

4 7

1 1

6 6

[出力例]

-1

※AtCoderテストケースより

[入力例]

2 3

4 3

3 4

3 5

2 1

[出力例]

[入力例]

3 11

9 4

2 5

7 11

11 5

9 6

5 1

4 3

7 4

6 1

4 3

7 7

[出力例]

[入力例]

10 13

16 8

13 4

9 8

8 1

4 9

15 17

9 13

1 12

2 7

10 16

13 11

14 9

7 1

5 13

14 16

2 10

[出力例]

■参照サイト
062 – Paint All
問題062 (Paint All) 解説

2021年8月19日2021年8月19日

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

C++の練習を兼ねて, 競プロ典型 90 問の問題057 (Flip Flap) を解いてみた.

■感想.
1. 問題057は, 方針が見えなかったので, (問題057 (Flip Flap) 解説) を参考に実装したところ, AC版に到達出来た.
2. 行列の掃き出し法について学習出来たので, 非常に良かったと思う..
3. 手強い問題が非常に多い気もするけど, 時間を見つけて, 引き続き, 取り組んでいきたいと思う.

詳細は, 本家のサイト(GitHub) 競プロ典型 90 問の問題057 をご覧下さい.

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

// 解き直し.
// https://github.com/E869120/kyopro_educational_90/blob/main/editorial/057.jpg
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vs = vector<string>;
using LL = long long;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
#define all(x) x.begin(), x.end()
const LL MOD = 998244353;

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    string z(M, '0');
    vs matrix;
    rep(i, N){
        matrix.pb(z);
        int t;
        scanf("%d", &t);
        rep(j, t){
            int a;
            scanf("%d", &a);
            a--;
            matrix[i][a] = '1';
        }
    }
    string S;
    rep(i, M){
        int c;
        scanf("%d", &c);
        S.pb(c + '0');
    }
    // puts("--- Matrix before update ---");
    // rep(i, N) printf("%s\n", matrix[i].c_str());
    // puts("--- Target string ---");
    // printf("%s\n", S.c_str());
    
    // 2. 掃き出し法(mod2版).
    // https://ja.wikipedia.org/wiki/ガウスの消去法
    // ex.
    // [変更前行列]
    // 011001
    // 001001
    // 101011
    // 010110
    // 001100
    // 
    // [変更後行列]
    // 100001
    // 010000
    // 001001
    // 000101
    // 000011
    auto gauss = [&](vs &m, int N, int M) -> vs {
        // 2-1. 戻り値設定.
        vs ret = m;
        
        // 2-2. 各行を順次確認.
        rep(i, N){
            // 降順sort.
            sort(all(ret));
            reverse(all(ret));
            
            // 最初に, '1' となる位置.
            int at = 0;
            rep(j, M){
                if(ret[i][j] == '1'){
                    at = j;
                    break;
                }
            }
            
            // i行目以外(j行目)と比較して, 前項で求めた位置(列)に, '1' が 有れば, 掃き出す.
            rep(j, N){
                if(i != j && ret[j][at] == '1'){
                    // 操作対象を設定.
                    string o = ret[i]; // i行目.
                    string n = ret[j]; // j行目.
                    
                    // j行目の掃き出し.
                    rep(k, M) n[k] = '0' + ((n[k] - '0') ^ (o[k] - '0'));
                    
                    // j行目更新.
                    ret[j] = n;
                }
            }
        }
        
        // 2-3. 返却.
        return ret;
    };
    vs gMatrix = gauss(matrix, N, M);
    // puts("--- Matrix after update ---");
    // rep(i, N) printf("%s\n", gMatrix[i].c_str());
    
    // 3. 1行目のスイッチから, 希望通りのパネルのパターンになるかチェック.
    int index = 0;
    while(index < N){
        // 文字列 S で, 最初に, '1' となる位置.
        int at = -1;
        rep(j, M){
            if(S[j] == '1'){
                at = j;
                break;
            }
        }
        
        // 文字列 S に, '1' が 含まれなかった場合.
        if(at == -1) break;
        
        // 更新後の行列で, 前項で求めた位置に, '1' が 来るものがあるか？
        while(gMatrix[index][at] != '1'){
            index++;
            if(index >= N) break;
        }
        
        // 見つからなかった場合は, 終了.
        if(index >= N) break;
        
        // 見つかった場合, 文字列 S を 更新.
        rep(k, M) S[k] = '0' + ((S[k] - '0') ^ (gMatrix[index][k] - '0'));
        
        // 次行へ.
        index++;
    }
    
    // 4. 希望通りのパネルのパターンを実現出来なかったら終了.
    if(S != z){
        puts("0");
        return 0;
    }
    
    // 5. 希望通りのパネルのパターンを実現できる場合.
    int zCount = 0;
    rep(i, N) if(gMatrix[i] == z) zCount++;
    
    // 6. ボタンの押し方の場合の数を計算.
    LL ans = 1;
    rep(i, zCount) ans <<= 1, ans %= MOD;
    
    // 7. 出力.
    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

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

// 解き直し.

// https://github.com/E869120/kyopro_educational_90/blob/main/editorial/057.jpg

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vs = vector<string>;

using LL = long long;

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

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

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

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

#define pb push_back

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

const LL MOD = 998244353;

int main(){

// 1. 入力情報.

int N, M;

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

string z(M, '0');

vs matrix;

rep(i, N){

matrix.pb(z);

int t;

scanf("%d", &t);

rep(j, t){

int a;

scanf("%d", &a);

a--;

matrix[i][a] = '1';

}

string S;

rep(i, M){

int c;

scanf("%d", &c);

S.pb(c + '0');

}

// puts("--- Matrix before update ---");

// rep(i, N) printf("%s\n", matrix[i].c_str());

// puts("--- Target string ---");

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

// 2. 掃き出し法(mod2版).

// https://ja.wikipedia.org/wiki/ガウスの消去法

// ex.

// [変更前行列]

// 011001

// 001001

// 101011

// 010110

// 001100

// [変更後行列]

// 100001

// 010000

// 001001

// 000101

// 000011

auto gauss = [&](vs &m, int N, int M) -> vs {

// 2-1. 戻り値設定.

vs ret = m;

// 2-2. 各行を順次確認.

rep(i, N){

// 降順sort.

sort(all(ret));

reverse(all(ret));

// 最初に, '1' となる位置.

int at = 0;

rep(j, M){

if(ret[i][j] == '1'){

at = j;

break;

}

// i行目以外(j行目)と比較して, 前項で求めた位置(列)に, '1' が有れば, 掃き出す.

rep(j, N){

if(i != j && ret[j][at] == '1'){

// 操作対象を設定.

string o = ret[i]; // i行目.

string n = ret[j]; // j行目.

// j行目の掃き出し.

rep(k, M) n[k] = '0' + ((n[k] - '0') ^ (o[k] - '0'));

// j行目更新.

ret[j] = n;

}

// 2-3. 返却.

return ret;

};

vs gMatrix = gauss(matrix, N, M);

// puts("--- Matrix after update ---");

// rep(i, N) printf("%s\n", gMatrix[i].c_str());

// 3. 1行目のスイッチから, 希望通りのパネルのパターンになるかチェック.

int index = 0;

while(index < N){

// 文字列 S で, 最初に, '1' となる位置.

int at = -1;

rep(j, M){

if(S[j] == '1'){

at = j;

break;

}

// 文字列 S に, '1' が含まれなかった場合.

if(at == -1) break;

// 更新後の行列で, 前項で求めた位置に, '1' が来るものがあるか？

while(gMatrix[index][at] != '1'){

index++;

if(index >= N) break;

}

// 見つからなかった場合は, 終了.

if(index >= N) break;

// 見つかった場合, 文字列 S を更新.

rep(k, M) S[k] = '0' + ((S[k] - '0') ^ (gMatrix[index][k] - '0'));

// 次行へ.

index++;

}

// 4. 希望通りのパネルのパターンを実現出来なかったら終了.

if(S != z){

puts("0");

return 0;

}

// 5. 希望通りのパネルのパターンを実現できる場合.

int zCount = 0;

rep(i, N) if(gMatrix[i] == z) zCount++;

// 6. ボタンの押し方の場合の数を計算.

LL ans = 1;

rep(i, zCount) ans <<= 1, ans %= MOD;

// 7. 出力.

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

return 0;

}

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

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

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

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

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

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

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

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

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

[出力例]
1

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

[出力例]
1

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

[出力例]
16

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

[入力例]

2 3

1 2

2 3

1 0 1

[出力例]

※AtCoderテストケースより

[入力例]

2 3

0 1 1

[出力例]

※AtCoderテストケースより

[入力例]

3 2

1 0

[出力例]

※AtCoderテストケースより

[入力例]

13 6

1 3 5

1 4 5

3 4 5 6

2 5

1 2 3 5

3 4 6

4 5 6

1 2 3 4 5 6

1 3 5 6

1 2 4

1 5 6

1 2 3 4

1 0 0 1 0 0

[出力例]

128

※AtCoderテストケースより

[入力例]

5 6

2 3 6

3 6

1 3 5 6

2 4 5

3 4

1 0 1 1 0 1

[出力例]

[入力例]

7 10

2 3 5 6 8 9

2 4 6 7 8

3 4 5 6 7 8

1 2 3 5 8

4 5 6

1 3 4 5 6 7 8 9

5 7 8 9 10

1 0 1 0 1 1 0 0 0 1

[出力例]

[入力例]

10 15

4 6 12

9 13

4 6 13

3 9 11 12 13

4 6 13

9 13

1 2 4

3 7 8

4 6 12

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

[出力例]

■参照サイト
057 – Flip Flap
問題057 (Flip Flap) 解説

2021年8月18日

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

C++の練習を兼ねて, 競プロ典型 90 問の問題054 (Takahashi Number) を解いてみた.

■感想.
1. 問題054は, 方針が見えなかったので, (問題054 (Takahashi Number) 解説) を参考に実装したところ, AC版に到達出来た.
2. 幅優先探索(応用版, グラフの辺数削減)の復習が出来たので, 非常に良かったと思う..
3. 手強い問題が非常に多い気もするけど, 時間を見つけて, 引き続き, 取り組んでいきたいと思う.

詳細は, 本家のサイト(GitHub) 競プロ典型 90 問の問題054 をご覧下さい.

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

// 解き直し.
// https://github.com/E869120/kyopro_educational_90/blob/main/editorial/054.jpg
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vvi = vector<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. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    vvi G(N + M);
    rep(i, M){
        int k;
        scanf("%d", &k);
        
        // 新たに追加する頂点.
        int u = N + i;
        
        // グラフ作成.
        rep(j, k){
            int v;
            scanf("%d", &v);
            v--;
            G[u].pb(v);
            G[v].pb(u);
        }
    }
    
    // 2. 頂点 1 から 各頂点までの距離を計算.
    // https://ja.wikipedia.org/wiki/幅優先探索
    auto bfs = [&](vvi &G, int s, int* d){
        // 2-1. 空のキュー.
        queue<int> q;
        
        // 2-2. スタート地点(距離 0)を設定.
        d[s] = 0;
        
        // 2-3. 探索地点 s をキュー q に追加.
        q.push(s);
        while(!q.empty()){
            // 2-4. キューから取り出す.
            int u = q.front();
            q.pop();
            
            // 2-5. 取り出した要素を処理.
            for(auto &e : G[u]){
                // 2-5. 未訪問の頂点を処理.
                if((d[e] == -1) && e != s) d[e] = d[u] + 1, q.push(e);
            }
        }
        return;
    };
    int d[N + M];
    rep(i, N + M) d[i] = -1;
    bfs(G, 0, d);
    // rep(i, N + M) printf("%d ", d[i]);
    // puts("");
    
    // 3. 出力.
    rep(i, N) printf("%d\n", (d[i] != -1) ? (d[i] / 2) : -1);
    return 0;
    
}

// 解き直し.

// https://github.com/E869120/kyopro_educational_90/blob/main/editorial/054.jpg

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vvi = vector<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. 入力情報.

int N, M;

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

vvi G(N + M);

rep(i, M){

int k;

scanf("%d", &k);

// 新たに追加する頂点.

int u = N + i;

// グラフ作成.

rep(j, k){

int v;

scanf("%d", &v);

v--;

G[u].pb(v);

G[v].pb(u);

}

// 2. 頂点 1 から各頂点までの距離を計算.

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

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

// 2-1. 空のキュー.

queue<int> q;

// 2-2. スタート地点(距離 0)を設定.

d[s] = 0;

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

q.push(s);

while(!q.empty()){

// 2-4. キューから取り出す.

int u = q.front();

q.pop();

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

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

// 2-5. 未訪問の頂点を処理.

if((d[e] == -1) && e != s) d[e] = d[u] + 1, q.push(e);

}

return;

};

int d[N + M];

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

bfs(G, 0, d);

// rep(i, N + M) printf("%d ", d[i]);

// puts("");

// 3. 出力.

rep(i, N) printf("%d\n", (d[i] != -1) ? (d[i] / 2) : -1);

return 0;

}

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

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

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

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

[入力例]
4 1
3
2 3 4

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

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

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

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

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

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

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

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

[入力例]

6 3

1 2 3

3 4

5 6

[出力例]

-1

※AtCoderテストケースより

[入力例]

4 3

1 2

2 3

3 4

[出力例]

※AtCoderテストケースより

[入力例]

4 1

2 3 4

[出力例]

-1

※AtCoderテストケースより

[入力例]

11 5

2 6 9 10

1 3 8

2 4 6 8 10

6 7

5 6 7 8

[出力例]

-1

※AtCoderテストケースより

[入力例]

7 3

1 2 3 4

1 5

5 6 7

[出力例]

[入力例]

25 13

1 2 3 4 5

2 17

17 18 19 20

3 6

6 10

6 7

7 8 9

5 11

11 12

11 13

13 14 15 16

8 21

21 22 23 24 25

[出力例]

■参照サイト
054 – Takahashi Number
問題054 (Takahashi Number) 解説

C++の練習を兼ねて, 競プロ典型 90 問 の 問題066 (Various Arrays) を解いてみた.

C++の練習を兼ねて, 競プロ典型 90 問 の 問題037 (Don’t Leave the Spice) を解いてみた.

C++の練習を兼ねて, 競プロ典型 90 問 の 問題087 (Chokudai’s Demand) を解いてみた.

C++の練習を兼ねて, 競プロ典型 90 問 の 問題086 (Snuke’s Favorite Arrays) を解いてみた.

C++の練習を兼ねて, 競プロ典型 90 問 の 問題083 (Colorful Graph) を解いてみた.

C++の練習を兼ねて, 競プロ典型 90 問 の 問題080 (Let’s Share Bit) を解いてみた.

C++の練習を兼ねて, 競プロ典型 90 問 の 問題074 (ABC String 2) を解いてみた.

C++の練習を兼ねて, 競プロ典型 90 問 の 問題062 (Paint All) を解いてみた.

C++の練習を兼ねて, 競プロ典型 90 問 の 問題057 (Flip Flap) を解いてみた.

C++の練習を兼ねて, 競プロ典型 90 問 の 問題054 (Takahashi Number) を解いてみた.

C++の練習を兼ねて, 競プロ典型 90 問の問題066 (Various Arrays) を解いてみた.

C++の練習を兼ねて, 競プロ典型 90 問の問題037 (Don’t Leave the Spice) を解いてみた.

C++の練習を兼ねて, 競プロ典型 90 問の問題087 (Chokudai’s Demand) を解いてみた.

C++の練習を兼ねて, 競プロ典型 90 問の問題086 (Snuke’s Favorite Arrays) を解いてみた.

C++の練習を兼ねて, 競プロ典型 90 問の問題083 (Colorful Graph) を解いてみた.

C++の練習を兼ねて, 競プロ典型 90 問の問題080 (Let’s Share Bit) を解いてみた.

C++の練習を兼ねて, 競プロ典型 90 問の問題074 (ABC String 2) を解いてみた.

C++の練習を兼ねて, 競プロ典型 90 問の問題062 (Paint All) を解いてみた.

C++の練習を兼ねて, 競プロ典型 90 問の問題057 (Flip Flap) を解いてみた.

C++の練習を兼ねて, 競プロ典型 90 問の問題054 (Takahashi Number) を解いてみた.