個人用メモ帳

2020年11月12日

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

C++の練習を兼ねて, AtCoder Beginner Contest 180 の問題E (Traveling Salesman among Aerial Cities) を解いてみた.

■感想.
1. 問題Eは, 方針が見えず, 解説を参照して実装し, ようやく, AC版となった.
2. 苦手なdpの訓練(本問では, bitDP)を積めたので, 非常に良かったと思う.
3. 個人的には, 非常に面白い問題に感じた.
4. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/abc180/editorial/154
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
int x[22], y[22], z[22]; // 各都市 の 座標.
int cost[22][22];        // 都市 i -> 都市 j の 移動コスト.

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%d %d %d", &x[i], &y[i], &z[i]);
    
    // 2. 都市 i -> 都市 j の 移動コスト.
    rep(i, N) rep(j, N) cost[i][j] = abs(x[j] - x[i]) + abs(y[j] - y[i]) + max(0, z[j] - z[i]);
    
    // 3. dp更新.
    // ex.
    // N = 6
    // s が 101001 -> 111001 に変化する場合は, 都市 3 から 都市 2 へ 移動と解釈.
    int dp[N][1 << N];
    rep(i, N) rep(j, 1 << N) dp[i][j] = 1010101010;
    dp[0][1 << (N - 1)] = 0;
    repx(p, 1, N){
        // 3-1. (p + 1)個目 の 街 を 訪問する場合は？
        repx(s, 1 << (N - 1), 1 << N){
            // 3-2. 訪問済 の 街の集合が, p個である場合.
            if(__builtin_popcount(s) == p){
                // 3-3. 移動元 を 都市 i とする.
                rep(i, N){
                    int bef = 1 << (N - 1 - i);
                    if(s & bef){
                        // 3-4. 移動先 を 都市 j とし, dp更新.
                        repx(j, 1, N){
                            int cur = 1 << (N - 1 - j);
                            if(!(s & cur)) dp[j][s + cur] = min(dp[j][s + cur], dp[i][s] + cost[i][j]);
                        }
                    }
                }
            }
        }
    }
    
    // 4. 都市 1 に 戻る.
    int ans = 1010101010;
    repx(i, 1, N) ans = min(ans, dp[i][(1 << N) - 1] + cost[i][0]);
    
    // 5. 出力.
    printf("%d\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc180/editorial/154

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

#define pb push_back

int x[22], y[22], z[22]; // 各都市の座標.

int cost[22][22]; // 都市 i -> 都市 j の移動コスト.

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

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

// 2. 都市 i -> 都市 j の移動コスト.

rep(i, N) rep(j, N) cost[i][j] = abs(x[j] - x[i]) + abs(y[j] - y[i]) + max(0, z[j] - z[i]);

// 3. dp更新.

// ex.

// N = 6

// s が 101001 -> 111001 に変化する場合は, 都市 3 から都市 2 へ移動と解釈.

int dp[N][1 << N];

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

dp[0][1 << (N - 1)] = 0;

repx(p, 1, N){

// 3-1. (p + 1)個目の街を訪問する場合は？

repx(s, 1 << (N - 1), 1 << N){

// 3-2. 訪問済の街の集合が, p個である場合.

if(__builtin_popcount(s) == p){

// 3-3. 移動元を都市 i とする.

rep(i, N){

int bef = 1 << (N - 1 - i);

if(s & bef){

// 3-4. 移動先を都市 j とし, dp更新.

repx(j, 1, N){

int cur = 1 << (N - 1 - j);

if(!(s & cur)) dp[j][s + cur] = min(dp[j][s + cur], dp[i][s] + cost[i][j]);

}

// 4. 都市 1 に戻る.

int ans = 1010101010;

repx(i, 1, N) ans = min(ans, dp[i][(1 << N) - 1] + cost[i][0]);

// 5. 出力.

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

return 0;

}

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

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

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

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

[入力例]
17
14142 13562 373095
-17320 508075 68877
223606 -79774 9979
-24494 -89742 783178
26457 513110 -64591
-282842 7124 -74619
31622 -77660 -168379
-33166 -24790 -3554
346410 16151 37755
-36055 51275 463989
37416 -573867 73941
-3872 -983346 207417
412310 56256 -17661
-42426 40687 -119285
43588 -989435 -40674
-447213 -59549 -99579
45825 7569 45584

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

[入力例]
5
161 560 -133
307 -274 246
21 450 -547
-25 561 444
160 -553 82

[出力例]
4105

[入力例]
13
816401 -335930 196982
516442 540869 757047
762652 -360494 858741
62175 -164846 282668
807559 272001 -72863
929055 824663 -153815
-438363 100290 981822
-256837 502105 100612
144931 716832 809205
-300099 -374150 679054
42820 76514 -739391
691879 260849 -507805
250553 -45231 143330

[出力例]
10100563

[入力例]

0 0 0

1 2 3

[出力例]

※AtCoderテストケースより

[入力例]

0 0 0

1 1 1

-1 -1 -1

[出力例]

※AtCoderテストケースより

[入力例]

14142 13562 373095

-17320 508075 68877

223606 -79774 9979

-24494 -89742 783178

26457 513110 -64591

-282842 7124 -74619

31622 -77660 -168379

-33166 -24790 -3554

346410 16151 37755

-36055 51275 463989

37416 -573867 73941

-3872 -983346 207417

412310 56256 -17661

-42426 40687 -119285

43588 -989435 -40674

-447213 -59549 -99579

45825 7569 45584

[出力例]

6519344

※AtCoderテストケースより

[入力例]

161 560 -133

307 -274 246

21 450 -547

-25 561 444

160 -553 82

[出力例]

4105

[入力例]

816401 -335930 196982

516442 540869 757047

762652 -360494 858741

62175 -164846 282668

807559 272001 -72863

929055 824663 -153815

-438363 100290 981822

-256837 502105 100612

144931 716832 809205

-300099 -374150 679054

42820 76514 -739391

691879 260849 -507805

250553 -45231 143330

[出力例]

10100563

■参照サイト
AtCoder Beginner Contest 180

2020年11月10日2020年11月10日

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

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

■感想.
1. 問題Fは, 方針が見えなかったので, 解説を参照して実装して, ようやく, AC版となった.
2. Union-Find木の復習が出来たので, 非常に良かったと思う.
※ 公式のライブラリを拝借させて頂いてます.
3. 個人的には, 非常に面白い問題に感じた.
4. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/abc181/editorial/267
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using P = pair<double, 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
double x[111], y[111];

// 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{
    vector<int> 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;
    scanf("%d", &N);
    rep(i, N) scanf("%lf %lf", &x[i], &y[i]);
    
    // 2. 2点間の距離, 頂点のペア を 保存.
    // -> 頂点 1 … 直線 y = -100, 頂点 N + 2 … 直線 y = 100 とする.
    priority_queue<P, vector<P>, greater<P>> pq;
    rep(i, N){
        P p0, p1;
        // 頂点 1 と 他の頂点との辺 を 追加.
        p0.a = abs(-100.0 - y[i]);
        p0.b.a = 0;
        p0.b.b = i + 1;
        pq.push(p0);
        
        // 頂点 N + 2 と 他の頂点との辺 を 追加.
        p1.a = abs(100.0 - y[i]);
        p1.b.a = N + 1;
        p1.b.b = i + 1;
        pq.push(p1);
    }
    rep(i, N){
        repx(j, i + 1, N){
            double d = hypot(x[i] - x[j], y[i] - y[j]);
            P p;
            p.a = d;
            p.b.a = i + 1;
            p.b.b = j + 1;
            pq.push(p);
        }
    }
    
    // 3. 距離の短い方から順に, 辺を追加.
    double ans = 0.0;
    UnionFind uf(N + 2);
    while(!pq.empty()){
        // 3-1. 辺を取り出す.
        P p = pq.top();
        pq.pop();
        
        // 3-2. 円の直径を更新.
        ans = p.a;
        
        // 3-3. グラフに辺を追加.
        uf.unite(p.b.a, p.b.b);
        
        // 3-4. 辺を追加した結果, 二直線が, 同じ連結成分に含まれてしまう場合は終了.
        if(uf.same(0, N + 1)) break;
    }
    
    // 4. 出力.
    printf("%.12lf\n", ans / 2.0);
    return 0;
    
}

100

// 解き直し.

// https://atcoder.jp/contests/abc181/editorial/267

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

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

double x[111], y[111];

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

vector<int> 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;

scanf("%d", &N);

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

// 2. 2点間の距離, 頂点のペアを保存.

// -> 頂点 1 … 直線 y = -100, 頂点 N + 2 … 直線 y = 100 とする.

priority_queue<P, vector<P>, greater<P>> pq;

rep(i, N){

P p0, p1;

// 頂点 1 と他の頂点との辺を追加.

p0.a = abs(-100.0 - y[i]);

p0.b.a = 0;

p0.b.b = i + 1;

pq.push(p0);

// 頂点 N + 2 と他の頂点との辺を追加.

p1.a = abs(100.0 - y[i]);

p1.b.a = N + 1;

p1.b.b = i + 1;

pq.push(p1);

}

rep(i, N){

repx(j, i + 1, N){

double d = hypot(x[i] - x[j], y[i] - y[j]);

P p;

p.a = d;

p.b.a = i + 1;

p.b.b = j + 1;

pq.push(p);

}

// 3. 距離の短い方から順に, 辺を追加.

double ans = 0.0;

UnionFind uf(N + 2);

while(!pq.empty()){

// 3-1. 辺を取り出す.

P p = pq.top();

pq.pop();

// 3-2. 円の直径を更新.

ans = p.a;

// 3-3. グラフに辺を追加.

uf.unite(p.b.a, p.b.b);

// 3-4. 辺を追加した結果, 二直線が, 同じ連結成分に含まれてしまう場合は終了.

if(uf.same(0, N + 1)) break;

}

// 4. 出力.

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

return 0;

}

[入力例]
2
0 -40
0 40

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

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

[入力例]
4
0 -10
99 10
0 91
99 -91

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

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

[入力例]
10
-90 40
20 -30
0 -90
10 -70
80 70
-90 30
-20 -80
10 90
50 30
60 -70

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

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

[入力例]
10
65 -90
-34 -2
62 99
42 -13
47 -84
84 87
16 -78
56 35
90 8
90 19

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

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

[入力例]
30
-85 42
12 69
17 -3
22 -51
-86 21
74 -58
78 -41
43 64
21 3
30 -58
4 32
14 22
28 42
71 -69
78 57
60 -4
87 17
-75 13
-86 32
28 95
-34 -32
70 -67
27 94
38 -80
21 -4
-54 87
89 81
-12 -13
87 -55
-42 81

[出力例]
20.573040611441

[入力例]
50
7 72
65 -52
46 33
59 30
30 -53
31 42
5 52
-7 56
40 41
34 99
50 -35
98 44
52 -69
7 97
28 -85
-96 41
46 -31
8 95
19 37
9 32
17 32
61 -94
10 33
89 19
38 -64
31 88
-7 25
86 61
3 56
10 79
-55 32
44 27
-55 74
18 44
50 -75
19 58
17 43
-36 60
68 43
24 79
45 41
19 74
46 34
30 48
-48 27
79 28
20 34
59 -44
72 68
23 72

[出力例]
29.017236257094

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

[入力例]

0 -40

0 40

[出力例]

※AtCoderテストケースより

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

40.000000000000

[入力例]

0 -10

99 10

0 91

99 -91

[出力例]

50.5

※AtCoderテストケースより

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

50.500000000000

[入力例]

-90 40

20 -30

0 -90

10 -70

80 70

-90 30

-20 -80

10 90

50 30

60 -70

[出力例]

33.541019662496845446

※AtCoderテストケースより

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

33.541019662497

[入力例]

65 -90

-34 -2

62 99

42 -13

47 -84

84 87

16 -78

56 35

90 8

90 19

[出力例]

35.003571246374276203

※AtCoderテストケースより

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

35.003571246374

[入力例]

-85 42

12 69

17 -3

22 -51

-86 21

74 -58

78 -41

43 64

21 3

30 -58

4 32

14 22

28 42

71 -69

78 57

60 -4

87 17

-75 13

-86 32

28 95

-34 -32

70 -67

27 94

38 -80

21 -4

-54 87

89 81

-12 -13

87 -55

-42 81

[出力例]

20.573040611441

[入力例]

7 72

65 -52

46 33

59 30

30 -53

31 42

5 52

-7 56

40 41

34 99

50 -35

98 44

52 -69

7 97

28 -85

-96 41

46 -31

8 95

19 37

9 32

17 32

61 -94

10 33

89 19

38 -64

31 88

-7 25

86 61

3 56

10 79

-55 32

44 27

-55 74

18 44

50 -75

19 58

17 43

-36 60

68 43

24 79

45 41

19 74

46 34

30 48

-48 27

79 28

20 34

59 -44

72 68

23 72

[出力例]

29.017236257094

■参照サイト
AtCoder Beginner Contest 181
Union-Find木

2020年11月9日2020年11月9日

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

C++の練習を兼ねて, AtCoder Beginner Contest 182 の問題C (To 3) ～問題E (Akari) を解いてみた.

■感想.
1. 問題E は, 数え上げる方法が, 首尾よく見つかったので, AC版に到達できたと思う.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

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

int main(){
    
    // 1. 入力情報.
    char n[33];
    scanf("%s", n);
    string N(n);
    
    // 2. 各桁を3で割った場合の余り.
    rep(i, N.size()) r[(N[i] - '0') % 3]++;
    
    // 3. 3の倍数が作成できない場合.
    if(r[0] == 0){
        if(r[1] + r[2] == 1){
            puts("-1");
            return 0;
        }
        if(r[1] == 0 && r[2] == 2){
            puts("-1");
            return 0;
        }
        if(r[1] == 2 && r[2] == 0){
            puts("-1");
            return 0;
        }
    }
    
    // 4. 最小の桁数は？
    // -> 余り 0 は残す.
    // -> 余り 0 でない場合は, (1, 1, 1), (1, 2), (2, 2, 2) のような形で, 組み合わせる.
    int ans = 0;
    if(r[1] == 0) ans = r[2] % 3;
    if(r[2] == 0) ans = r[1] % 3;
    if(r[1] && r[2]){
        if(r[1] % 3 == r[2] % 3) ans = 0;
        if(r[1] % 3 != r[2] % 3) ans = 1;
    }
    
    // 5. 出力.
    printf("%d\n", ans);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

int r[3];

int main(){

// 1. 入力情報.

char n[33];

scanf("%s", n);

string N(n);

// 2. 各桁を3で割った場合の余り.

rep(i, N.size()) r[(N[i] - '0') % 3]++;

// 3. 3の倍数が作成できない場合.

if(r[0] == 0){

if(r[1] + r[2] == 1){

puts("-1");

return 0;

}

if(r[1] == 0 && r[2] == 2){

puts("-1");

return 0;

}

if(r[1] == 2 && r[2] == 0){

puts("-1");

return 0;

}

// 4. 最小の桁数は？

// -> 余り 0 は残す.

// -> 余り 0 でない場合は, (1, 1, 1), (1, 2), (2, 2, 2) のような形で, 組み合わせる.

int ans = 0;

if(r[1] == 0) ans = r[2] % 3;

if(r[2] == 0) ans = r[1] % 3;

if(r[1] && r[2]){

if(r[1] % 3 == r[2] % 3) ans = 0;

if(r[1] % 3 != r[2] % 3) ans = 1;

}

// 5. 出力.

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

return 0;

}

[入力例]
35

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

[入力例]
369

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

[入力例]
6227384

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

[入力例]
11

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

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

369

[出力例]

※AtCoderテストケースより

[入力例]

6227384

[出力例]

※AtCoderテストケースより

[入力例]

[出力例]

-1

※AtCoderテストケースより

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

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

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    LL ans = 0, cur = 0, aMax = 0;
    rep(i, N){
        scanf("%lld", &aCum[i + 1]);
        // 累積和.
        aCum[i + 1] += aCum[i];
        
        // 正方向の最大距離.
        aMax = max(aMax, aCum[i + 1]);
        
        // 更新.
        ans = max(ans, aMax + cur);
        
        // 現在位置.
        cur += aCum[i + 1];
    }
    
    // 2. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

LL aCum[202020];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

LL ans = 0, cur = 0, aMax = 0;

rep(i, N){

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

// 累積和.

aCum[i + 1] += aCum[i];

// 正方向の最大距離.

aMax = max(aMax, aCum[i + 1]);

// 更新.

ans = max(ans, aMax + cur);

// 現在位置.

cur += aCum[i + 1];

}

// 2. 出力.

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

return 0;

}

[入力例]
3
2 -1 -2

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

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

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

[入力例]
5
-1000 -1000 -1000 -1000 -1000

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

[入力例]
100
20022790 77312906 28502596 77179992 -76725463 21610710 25468798 -26917148 -69713598 -77687592 25158646 -47146999 82704774 61586512 19106570 63689620 -69024373 -66256411 1435505 -75172039 -80563839 37011095 68399099 -74796903 26525550 20414678 75195711 11845141 31908840 20765536 85858038 60077731 -81722174 -20753582 -14868082 70877005 -3169908 -7768198 60490382 1095223 48023286 -58861880 -24380265 42564919 26692705 -20007039 -3950337 -83339131 -83431162 77176199 51523492 31022813 230520 3974693 -7335799 -22624273 25760540 51004423 40920099 -72328969 -32148022 -17325796 -52872898 -81250143 57239096 61873344 37619949 -32512570 -56594056 20880843 24048391 18018645 -9478729 3819552 56463618 -66897726 -8255775 -52153846 55488291 49406848 -57371873 -27963618 53725101 46831927 -82985155 79609370 -37615012 -76230735 -61418017 -31474127 68616442 30205375 55514018 -87196634 -64488338 78424941 56321591 -73903849 79753422 74820465

[出力例]
18573336169

[入力例]

2 -1 -2

[出力例]

※AtCoderテストケースより

[入力例]

-2 1 3 -1 -1

[出力例]

※AtCoderテストケースより

[入力例]

-1000 -1000 -1000 -1000 -1000

[出力例]

※AtCoderテストケースより

[入力例]

100

20022790 77312906 28502596 77179992 -76725463 21610710 25468798 -26917148 -69713598 -77687592 25158646 -47146999 82704774 61586512 19106570 63689620 -69024373 -66256411 1435505 -75172039 -80563839 37011095 68399099 -74796903 26525550 20414678 75195711 11845141 31908840 20765536 85858038 60077731 -81722174 -20753582 -14868082 70877005 -3169908 -7768198 60490382 1095223 48023286 -58861880 -24380265 42564919 26692705 -20007039 -3950337 -83339131 -83431162 77176199 51523492 31022813 230520 3974693 -7335799 -22624273 25760540 51004423 40920099 -72328969 -32148022 -17325796 -52872898 -81250143 57239096 61873344 37619949 -32512570 -56594056 20880843 24048391 18018645 -9478729 3819552 56463618 -66897726 -8255775 -52153846 55488291 49406848 -57371873 -27963618 53725101 46831927 -82985155 79609370 -37615012 -76230735 -61418017 -31474127 68616442 30205375 55514018 -87196634 -64488338 78424941 56321591 -73903849 79753422 74820465

[出力例]

18573336169

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

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

int main(){
    
    // 1. 入力情報.
    int H, W, N, M;
    scanf("%d %d %d %d", &H, &W, &N, &M);
    rep(i, N){
        int a, b;
        scanf("%d %d", &a, &b);
        a--, b--;
        o[a][b] = 1; // 電球.
    }
    rep(i, M){
        int c, d;
        scanf("%d %d", &c, &d);
        c--, d--;
        o[c][d] = -1; // ブロック.
    }
    
    // 2. 左右上下について, 電球の光が届いているか見る.
    // 2-1. 左 → 右.
    rep(i, H){
        rep(j, W){
            if(j) lr[i][j] += lr[i][j - 1];
            if(o[i][j] == 1)  lr[i][j] = 1;
            if(o[i][j] == -1) lr[i][j] = 0;
        }
    }
    // 2-2. 右 → 左.
    rep(i, H){
        repr(j, W - 1, 0){
            if(j < W - 1) rl[i][j] += rl[i][j + 1];
            if(o[i][j] == 1)  rl[i][j] = 1;
            if(o[i][j] == -1) rl[i][j] = 0;
        }
    }
    // 2-3. 上 → 下.
    rep(j, W){
        rep(i, H){
            if(i) ud[i][j] += ud[i - 1][j];
            if(o[i][j] == 1)  ud[i][j] = 1;
            if(o[i][j] == -1) ud[i][j] = 0;
        }
    }
    // 2-4. 下 → 上.
    rep(j, W){
        repr(i, H - 1, 0){
            if(i < H - 1) du[i][j] += du[i + 1][j];
            if(o[i][j] == 1)  du[i][j] = 1;
            if(o[i][j] == -1) du[i][j] = 0;
        }
    }
    
    // 3. カウント.
    int ans = 0;
    rep(i, H) rep(j, W) if(lr[i][j] + rl[i][j] + ud[i][j] + du[i][j]) ans++;
    
    // 4. 出力.
    printf("%d\n", ans);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

int o[1515][1515], lr[1515][1515], rl[1515][1515], ud[1515][1515], du[1515][1515];

int main(){

// 1. 入力情報.

int H, W, N, M;

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

rep(i, N){

int a, b;

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

a--, b--;

o[a][b] = 1; // 電球.

}

rep(i, M){

int c, d;

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

c--, d--;

o[c][d] = -1; // ブロック.

}

// 2. 左右上下について, 電球の光が届いているか見る.

// 2-1. 左 → 右.

rep(i, H){

rep(j, W){

if(j) lr[i][j] += lr[i][j - 1];

if(o[i][j] == 1) lr[i][j] = 1;

if(o[i][j] == -1) lr[i][j] = 0;

}

// 2-2. 右 → 左.

rep(i, H){

repr(j, W - 1, 0){

if(j < W - 1) rl[i][j] += rl[i][j + 1];

if(o[i][j] == 1) rl[i][j] = 1;

if(o[i][j] == -1) rl[i][j] = 0;

}

// 2-3. 上 → 下.

rep(j, W){

rep(i, H){

if(i) ud[i][j] += ud[i - 1][j];

if(o[i][j] == 1) ud[i][j] = 1;

if(o[i][j] == -1) ud[i][j] = 0;

}

// 2-4. 下 → 上.

rep(j, W){

repr(i, H - 1, 0){

if(i < H - 1) du[i][j] += du[i + 1][j];

if(o[i][j] == 1) du[i][j] = 1;

if(o[i][j] == -1) du[i][j] = 0;

}

// 3. カウント.

int ans = 0;

rep(i, H) rep(j, W) if(lr[i][j] + rl[i][j] + ud[i][j] + du[i][j]) ans++;

// 4. 出力.

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

return 0;

}

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

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

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

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

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

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

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

[出力例]
39

[入力例]
150 150 20 15
134 39
121 4
15 117
69 122
99 118
34 23
27 125
41 144
110 33
35 43
28 3
111 71
136 93
17 57
94 143
100 14
47 6
129 5
81 146
117 20
51 6
125 17
48 75
49 20
142 146
34 90
19 43
116 132
35 114
86 120
98 97
93 90
31 137
75 26
10 123

[出力例]
5362

[入力例]
200 200 100 60
11 130
128 17
117 49
75 69
53 28
150 30
73 4
64 47
14 10
127 140
84 112
143 110
118 61
107 73
85 113
144 65
111 23
82 10
14 145
47 101
128 33
51 117
13 89
111 62
101 20
41 88
15 95
115 78
5 141
6 133
106 76
23 83
144 50
130 92
141 81
124 79
31 17
58 63
130 53
38 62
63 92
57 13
8 109
90 82
144 85
144 90
1 27
48 55
105 92
45 111
143 97
31 123
74 131
136 86
88 95
44 112
99 147
148 61
109 12
2 119
84 57
81 123
104 48
90 63
120 50
130 25
111 149
112 137
119 19
134 100
105 8
78 84
143 126
30 51
115 74
52 55
137 56
97 127
130 29
64 42
21 141
132 70
58 21
30 101
85 63
25 38
62 16
86 31
1 65
150 9
135 134
74 18
47 127
57 50
46 102
28 138
125 31
39 115
6 148
16 99
104 13
17 104
44 57
123 110
82 134
117 4
115 117
8 100
74 111
76 118
90 45
22 40
109 63
129 96
44 25
80 116
144 66
74 28
16 9
25 7
109 125
51 103
81 141
4 138
121 39
100 34
53 42
84 65
136 139
89 5
97 90
42 112
132 132
80 62
85 84
10 89
7 119
128 129
12 43
12 91
6 23
120 49
121 63
36 29
50 95
139 1
98 77
15 8
40 86
71 73
60 88
129 63
75 48
24 110
141 150
22 150
22 25
81 4
94 75
132 95

[出力例]
22513

[入力例]
500 500 189 111
443 34
139 424
222 301
368 353
451 352
132 271
191 232
456 338
446 443
210 105
145 318
259 270
284 51
350 354
468 353
137 208
441 270
218 28
146 203
116 197
372 288
47 417
462 191
132 45
344 154
178 322
32 286
295 449
203 351
380 287
445 455
67 298
281 54
492 477
162 74
256 451
171 397
367 167
258 375
42 339
256 418
43 401
79 404
485 194
5 175
269 342
90 206
288 238
481 383
379 365
19 17
255 420
182 255
227 357
82 138
163 170
118 121
3 108
498 370
297 143
196 455
3 481
227 309
209 309
171 311
128 210
309 213
20 361
477 303
357 110
166 461
383 254
53 459
58 416
157 108
52 133
288 482
414 271
207 126
86 140
134 336
103 50
155 273
38 303
65 217
4 232
191 21
164 433
276 172
465 374
255 449
179 84
156 375
123 50
158 236
335 383
477 403
314 46
440 71
198 249
493 77
210 158
146 449
232 360
108 38
101 119
104 225
299 199
346 300
422 221
45 209
294 334
242 137
137 325
389 208
196 453
42 340
414 25
493 148
40 166
438 485
233 470
136 430
168 280
298 76
19 491
261 309
381 410
475 327
272 97
431 420
370 29
34 27
264 211
163 53
434 260
454 555
103 73
422 401
69 218
492 236
29 379
380 294
364 166
227 296
379 8
209 85
254 407
79 312
307 394
125 76
467 174
146 342
319 178
465 442
112 286
486 236
110 224
396 269
4 177
329 45
157 354
472 93
16 302
241 45
144 219
26 55
236 78
178 253
161 295
257 114
13 338
257 210
417 15
145 233
205 13
227 425
215 354
127 151
344 268
362 267
187 388
272 445
238 488
38 289
335 151
192 494
134 348
271 174
374 373
399 157
190 427
231 18
33 357
419 347
279 29
126 491
272 53
36 202
465 294
100 198
20 482
78 201
481 262
321 244
46 316
382 357
290 137
275 398
25 389
32 14
75 26
138 238
486 352
210 168
118 272
271 106
369 394
346 52
193 383
135 356
264 91
498 426
460 433
382 373
72 475
477 44
456 254
30 390
122 430
17 500
121 127
258 240
64 16
59 311
408 428
450 470
447 305
71 343
468 377
140 276
338 282
133 348
332 342
471 359
250 22
243 59
236 34
404 202
330 351
119 14
307 233
164 488
206 95
45 56
275 265
98 420
127 398
319 453
47 65
230 490
467 128
95 28
387 261
298 59
430 378
378 115
299 191
353 59
145 39
79 15
16 184
458 235
421 138
10 211
377 420
424 79
384 91
300 405
172 253
189 215
177 441
48 341
131 395
198 11
264 245
67 94
2 1
496 166
204 447
471 412
327 157
219 140
484 81
365 364
121 462
455 254
117 50
494 210
52 473

[出力例]
123613

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

290

291

292

293

294

295

296

297

298

299

300

301

302

303

304

305

306

307

308

309

310

311

312

313

314

315

316

317

318

319

320

321

322

323

324

325

326

327

328

329

330

331

332

333

334

335

336

337

338

339

340

341

342

343

344

345

346

347

348

349

350

351

352

353

354

355

356

357

358

359

360

361

362

363

364

365

366

367

368

369

370

371

372

373

374

375

376

377

378

379

380

381

382

383

384

385

386

387

388

389

390

391

392

393

394

395

396

397

398

399

400

401

402

403

404

405

406

407

408

409

410

411

412

413

414

415

416

417

418

419

420

421

422

423

424

425

426

427

428

429

430

431

432

433

434

435

436

437

438

439

440

441

442

443

444

445

446

447

448

449

450

451

452

453

454

455

456

457

458

459

460

461

462

463

464

465

466

467

468

469

470

471

472

473

474

475

476

477

478

479

480

481

482

483

484

485

486

487

488

489

490

491

492

493

494

495

496

497

498

499

500

501

502

503

504

505

506

507

508

509

510

511

512

513

514

515

516

517

518

519

520

521

522

523

524

525

526

527

528

529

530

531

532

533

534

535

536

537

538

539

540

541

542

543

544

545

546

547

548

549

550

551

552

553

554

555

556

557

558

559

560

561

562

563

564

565

566

567

568

569

570

[入力例]

3 3 2 1

1 1

2 3

2 2

[出力例]

※AtCoderテストケースより

[入力例]

4 4 3 3

1 2

1 3

3 4

2 3

2 4

3 2

[出力例]

※AtCoderテストケースより

[入力例]

5 5 5 1

1 1

2 2

3 3

4 4

5 5

4 2

[出力例]

※AtCoderテストケースより

[入力例]

8 8 8 8

2 2

4 3

5 3

3 4

1 5

4 6

3 8

1 7

3 3

4 2

7 3

3 5

3 6

3 7

6 6

1 8

[出力例]

[入力例]

150 150 20 15

134 39

121 4

15 117

69 122

99 118

34 23

27 125

41 144

110 33

35 43

28 3

111 71

136 93

17 57

94 143

100 14

47 6

129 5

81 146

117 20

51 6

125 17

48 75

49 20

142 146

34 90

19 43

116 132

35 114

86 120

98 97

93 90

31 137

75 26

10 123

[出力例]

5362

[入力例]

200 200 100 60

11 130

128 17

117 49

75 69

53 28

150 30

73 4

64 47

14 10

127 140

84 112

143 110

118 61

107 73

85 113

144 65

111 23

82 10

14 145

47 101

128 33

51 117

13 89

111 62

101 20

41 88

15 95

115 78

5 141

6 133

106 76

23 83

144 50

130 92

141 81

124 79

31 17

58 63

130 53

38 62

63 92

57 13

8 109

90 82

144 85

144 90

1 27

48 55

105 92

45 111

143 97

31 123

74 131

136 86

88 95

44 112

99 147

148 61

109 12

2 119

84 57

81 123

104 48

90 63

120 50

130 25

111 149

112 137

119 19

134 100

105 8

78 84

143 126

30 51

115 74

52 55

137 56

97 127

130 29

64 42

21 141

132 70

58 21

30 101

85 63

25 38

62 16

86 31

1 65

150 9

135 134

74 18

47 127

57 50

46 102

28 138

125 31

39 115

6 148

16 99

104 13

17 104

44 57

123 110

82 134

117 4

115 117

8 100

74 111

76 118

90 45

22 40

109 63

129 96

44 25

80 116

144 66

74 28

16 9

25 7

109 125

51 103

81 141

4 138

121 39

100 34

53 42

84 65

136 139

89 5

97 90

42 112

132 132

80 62

85 84

10 89

7 119

128 129

12 43

12 91

6 23

120 49

121 63

36 29

50 95

139 1

98 77

15 8

40 86

71 73

60 88

129 63

75 48

24 110

141 150

22 150

22 25

81 4

94 75

132 95

[出力例]

22513

[入力例]

500 500 189 111

443 34

139 424

222 301

368 353

451 352

132 271

191 232

456 338

446 443

210 105

145 318

259 270

284 51

350 354

468 353

137 208

441 270

218 28

146 203

116 197

372 288

47 417

462 191

132 45

344 154

178 322

32 286

295 449

203 351

380 287

445 455

67 298

281 54

492 477

162 74

256 451

171 397

367 167

258 375

42 339

256 418

43 401

79 404

485 194

5 175

269 342

90 206

288 238

481 383

379 365

19 17

255 420

182 255

227 357

82 138

163 170

118 121

3 108

498 370

297 143

196 455

3 481

227 309

209 309

171 311

128 210

309 213

20 361

477 303

357 110

166 461

383 254

53 459

58 416

157 108

52 133

288 482

414 271

207 126

86 140

134 336

103 50

155 273

38 303

65 217

4 232

191 21

164 433

276 172

465 374

255 449

179 84

156 375

123 50

158 236

335 383

477 403

314 46

440 71

198 249

493 77

210 158

146 449

232 360

108 38

101 119

104 225

299 199

346 300

422 221

45 209

294 334

242 137

137 325

389 208

196 453

42 340

414 25

493 148

40 166

438 485

233 470

136 430

168 280

298 76

19 491

261 309

381 410

475 327

272 97

431 420

370 29

34 27

264 211

163 53

434 260

454 555

103 73

422 401

69 218

492 236

29 379

380 294

364 166

227 296

379 8

209 85

254 407

79 312

307 394

125 76

467 174

146 342

319 178

465 442

112 286

486 236

110 224

396 269

4 177

329 45

157 354

472 93

16 302

241 45

144 219

26 55

236 78

178 253

161 295

257 114

13 338

257 210

417 15

145 233

205 13

227 425

215 354

127 151

344 268

362 267

187 388

272 445

238 488

38 289

335 151

192 494

134 348

271 174

374 373

399 157

190 427

231 18

33 357

419 347

279 29

126 491

272 53

36 202

465 294

100 198

20 482

78 201

481 262

321 244

46 316

382 357

290 137

275 398

25 389

32 14

75 26

138 238

486 352

210 168

118 272

271 106

369 394

346 52

193 383

135 356

264 91

498 426

460 433

382 373

72 475

477 44

456 254

30 390

122 430

17 500

121 127

258 240

64 16

59 311

408 428

450 470

447 305

71 343

468 377

140 276

338 282

133 348

332 342

471 359

250 22

243 59

236 34

404 202

330 351

119 14

307 233

164 488

206 95

45 56

275 265

98 420

127 398

319 453

47 65

230 490

467 128

95 28

387 261

298 59

430 378

378 115

299 191

353 59

145 39

79 15

16 184

458 235

421 138

10 211

377 420

424 79

384 91

300 405

172 253

189 215

177 441

48 341

131 395

198 11

264 245

67 94

2 1

496 166

204 447

471 412

327 157

219 140

484 81

365 364

121 462

455 254

117 50

494 210

52 473

[出力例]

123613

■参照サイト
AtCoder Beginner Contest 182

2020年11月7日2020年11月7日

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

C++の練習を兼ねて, AtCoder Regular Contest 107 の問題E (Mex Mat) を解いてみた.

■感想.
1. E問題は, 方針が見えなかったので, 解説を参照して実装して, ようやく, AC版となった.
2. 個人的には, (規則性が埋め込まれているため)非常に面白い問題に感じた.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/arc107/editorial/265
// 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 r[505050][5], c[5][505050], mex[3][3];
LL ans[3];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%d", &c[0][i]);
    rep(i, N - 1) scanf("%d", &r[i + 1][0]);
    
    // 2. 入力情報を加工.
    r[0][0] = c[0][0];
    r[0][1] = c[0][1];
    r[0][2] = c[0][2];
    r[0][3] = c[0][3];
    c[1][0] = r[1][0];
    c[2][0] = r[2][0];
    c[3][0] = r[3][0];
    
    // 3. mex設定.
    mex[0][0] = 1;
    mex[0][1] = 2;
    mex[0][2] = 1;
    mex[1][0] = 2;
    mex[1][1] = 0;
    mex[1][2] = 0;
    mex[2][0] = 1;
    mex[2][1] = 0;
    mex[2][2] = 0;
    
    // 4. 4行 × N列 を 計算.
    repx(i, 1, 4){
        repx(j, 1, N){
            int x = c[i - 1][j];
            int y = c[i][j - 1];
            c[i][j] = mex[x][y];
        }
    }
    
    // 5. N行 × 4列 を 計算.
    repx(i, 1, N){
        repx(j, 1, 4){
            int x = r[i - 1][j];
            int y = r[i][j - 1];
            r[i][j] = mex[x][y];
        }
    }
    
    // 6. 集計.
    // 6-1. 4行 × N列(加算).
    int u = min(N, 4);
    rep(i, u) rep(j, N) ans[c[i][j]]++;
    
    // 6-2. N行 × 4列(加算).
    rep(i, N) rep(j, u) ans[r[i][j]]++;
    
    // 6-3. 4行 × 4列(減算).
    rep(i, u) rep(j, u) ans[r[i][j]]--;
    
    // 7. N が 4 より 大きい場合.
    if(N > 4){
        // 7-1. 5行 × (5 ～ N)列(加算).
        repx(j, 3, N - 1) ans[c[3][j]] += (LL)(N - 1 - j);
        
        // 7-2. (5 ～ N)行 × 5列(加算).
        repx(i, 3, N - 1) ans[r[i][3]] += (LL)(N - 1 - i);
        
        // 7-3. 5行 × 5列(減算).
        ans[r[3][3]] -= (LL)(N - 1 - 3);
    }
    
    // 8. 出力.
    printf("%lld %lld %lld\n", ans[0], ans[1], ans[2]);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc107/editorial/265

// 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 r[505050][5], c[5][505050], mex[3][3];

LL ans[3];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

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

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

// 2. 入力情報を加工.

r[0][0] = c[0][0];

r[0][1] = c[0][1];

r[0][2] = c[0][2];

r[0][3] = c[0][3];

c[1][0] = r[1][0];

c[2][0] = r[2][0];

c[3][0] = r[3][0];

// 3. mex設定.

mex[0][0] = 1;

mex[0][1] = 2;

mex[0][2] = 1;

mex[1][0] = 2;

mex[1][1] = 0;

mex[1][2] = 0;

mex[2][0] = 1;

mex[2][1] = 0;

mex[2][2] = 0;

// 4. 4行 × N列を計算.

repx(i, 1, 4){

repx(j, 1, N){

int x = c[i - 1][j];

int y = c[i][j - 1];

c[i][j] = mex[x][y];

}

// 5. N行 × 4列を計算.

repx(i, 1, N){

repx(j, 1, 4){

int x = r[i - 1][j];

int y = r[i][j - 1];

r[i][j] = mex[x][y];

}

// 6. 集計.

// 6-1. 4行 × N列(加算).

int u = min(N, 4);

rep(i, u) rep(j, N) ans[c[i][j]]++;

// 6-2. N行 × 4列(加算).

rep(i, N) rep(j, u) ans[r[i][j]]++;

// 6-3. 4行 × 4列(減算).

rep(i, u) rep(j, u) ans[r[i][j]]--;

// 7. N が 4 より大きい場合.

if(N > 4){

// 7-1. 5行 × (5 ～ N)列(加算).

repx(j, 3, N - 1) ans[c[3][j]] += (LL)(N - 1 - j);

// 7-2. (5 ～ N)行 × 5列(加算).

repx(i, 3, N - 1) ans[r[i][3]] += (LL)(N - 1 - i);

// 7-3. 5行 × 5列(減算).

ans[r[3][3]] -= (LL)(N - 1 - 3);

}

// 8. 出力.

printf("%lld %lld %lld\n", ans[0], ans[1], ans[2]);

return 0;

}

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

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

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

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

[入力例]
1
1

[出力例]
0 1 0

[入力例]
3
1 2 0
0
1

[出力例]
3 4 2

[入力例]
2
1 2
0

[出力例]
1 2 1

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

[出力例]
4334 4338 1328

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

[出力例]
40475 40442 9083

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

290

291

292

293

294

295

296

297

298

299

300

301

302

303

304

305

306

307

308

309

310

311

312

313

314

315

316

317

318

319

320

321

322

323

324

325

326

327

328

329

330

331

332

333

334

335

336

337

338

339

340

341

342

343

344

345

346

347

348

349

350

351

352

353

354

355

356

357

358

359

360

361

362

363

364

365

366

367

368

369

370

371

372

373

374

375

376

377

378

379

380

381

382

383

384

385

386

387

388

389

390

391

392

393

394

395

396

397

398

399

400

401

402

403

404

405

406

407

408

409

410

411

412

413

414

415

416

417

418

419

420

421

422

423

424

425

426

427

428

429

430

431

432

433

434

435

436

437

438

439

440

441

442

443

444

445

446

447

448

449

450

451

452

453

454

455

456

457

458

459

460

461

462

463

464

465

466

467

468

469

470

471

472

473

[入力例]

1 2 0 2

[出力例]

7 4 5

※AtCoderのテストケースより

[入力例]

1 1 2 2 1 2 0 2 2 1 0 2 0 2 0 2 1 1 1 1

[出力例]

176 175 49

※AtCoderのテストケースより

[入力例]

[出力例]

0 1 0

[入力例]

1 2 0

[出力例]

3 4 2

[入力例]

1 2

[出力例]

1 2 1

[入力例]

100

2 1 0 0 1 1 2 2 0 1 2 1 0 1 1 0 1 2 0 1 2 1 2 1 2 0 1 0 2 2 0 2 1 1 0 1 1 1 1 2 0 1 1 1 2 1 1 0 1 0 2 1 0 1 1 0 2 1 2 2 0 2 1 1 1 2 1 0 0 2 2 2 0 2 2 1 2 2 1 1 0 0 2 0 2 2 1 0 2 2 2 1 2 1 2 0 2 2 1 2

[出力例]

4334 4338 1328

[入力例]

300

1 0 1 2 2 2 2 1 0 0 2 1 0 1 0 1 1 2 2 2 2 2 2 2 2 0 2 0 0 1 2 0 0 0 0 0 2 0 2 1 2 0 0 1 1 0 1 2 0 1 1 2 2 2 2 1 2 2 2 0 2 2 1 0 1 1 1 0 1 1 1 1 0 0 0 0 1 2 1 2 2 2 0 2 1 0 1 1 2 0 2 2 2 0 1 0 2 1 0 1 2 1 1 2 2 1 0 2 2 1 2 0 1 1 2 0 2 0 2 2 2 1 0 1 1 2 1 2 2 2 2 2 2 0 1 0 0 2 0 0 0 1 2 2 0 1 0 0 0 1 2 0 2 0 0 1 1 1 1 0 0 1 2 2 0 1 1 0 1 2 1 1 1 2 0 2 2 1 2 2 2 2 1 1 2 2 1 1 1 0 0 2 2 1 0 1 2 2 2 0 1 0 1 0 1 1 0 1 0 1 2 0 0 1 2 1 2 1 1 2 2 1 0 1 1 0 2 1 2 1 0 0 2 1 0 2 1 1 0 0 1 1 1 0 0 0 1 1 2 1 0 1 1 1 0 0 1 1 0 1 1 0 0 1 0 0 1 1 2 0 1 0 0 2 2 0 0 2 2 1 2 1 1 1 0 2 2 1 0 0 1 2 0 2 0 1 2 2 0 0

[出力例]

40475 40442 9083

■参照サイト
AtCoder Regular Contest 107

2020年11月5日

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

C++の練習を兼ねて, AtCoder Regular Contest 107 の問題D (Number of Multisets) を解いてみた.

■感想.
1. D問題は, 方針が見えなかったので, 解説を参照して実装して, ようやく, AC版となった.
2. 苦手なdpの訓練を積めたので良かったと思う.
3. 個人的には, 摩訶不思議な問題に見えて, 非常に印象に残ったと思う.
4. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

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

int main(){
    
    // 1. 入力情報.
    int N, K;
    scanf("%d %d", &N, &K);
    
    // 2. dp更新.
    // -> 漸化式: dp[N][K] = dp[N - 1][K - 1] + dp[N][2 * K].
    rep(i, N) dp[i][i] = 1;
    repx(i, 1, N + 1){
        repr(j, 2 * N, 1){
            if(i < j * 2) dp[i][j] = dp[i - 1][j - 1];
            else          dp[i][j] = dp[i - 1][j - 1] + dp[i][2 * j];
            dp[i][j] %= MOD;
        }
    }
    
    // 3. 出力.
    printf("%lld\n", dp[N][K]);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc107/editorial/264

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

const LL MOD = 998244353;

LL dp[3030][3030];

int main(){

// 1. 入力情報.

int N, K;

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

// 2. dp更新.

// -> 漸化式: dp[N][K] = dp[N - 1][K - 1] + dp[N][2 * K].

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

repx(i, 1, N + 1){

repr(j, 2 * N, 1){

if(i < j * 2) dp[i][j] = dp[i - 1][j - 1];

else dp[i][j] = dp[i - 1][j - 1] + dp[i][2 * j];

dp[i][j] %= MOD;

}

// 3. 出力.

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

return 0;

}

[入力例]
4 2

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

[入力例]
2525 425

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

[入力例]
2 1

[出力例]
1

[入力例]
8 1

[出力例]
16

[入力例]
314 159

[出力例]
584242605

[入力例]
1234 567

[出力例]
730928588

[入力例]

4 2

[出力例]

※AtCoderのテストケースより

[入力例]

2525 425

[出力例]

687232272

※AtCoderのテストケースより

[入力例]

2 1

[出力例]

[入力例]

8 1

[出力例]

[入力例]

314 159

[出力例]

584242605

[入力例]

1234 567

[出力例]

730928588

■参照サイト
AtCoder Regular Contest 107

2020年11月3日

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

C++の練習を兼ねて, AtCoder Regular Contest 107 の問題C (Shuffle Permutation) を解いてみた.

■感想.
1. C問題は, 方針が見えなかったので, 解説を参照して実装して, ようやく, AC版となった.
2. 幅優先探索の復習が出来たので, 非常に良かったと思う.
3. 個人的には, 非常に面白い問題に感じた.
4. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/arc107/editorial/266
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vi = vector<int>;
using vvi = vector<vi>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
const LL MOD = 998244353;
int a[55][55];
LL FAC[55];
int rConnection[55], cConnection[55]; // 連結成分番号を保存.
LL rAppearance[55], cAppearance[55];  // 連結成分番号の出現回数.

// https://ja.wikipedia.org/wiki/幅優先探索
// ※bfsの動作確認用.
// @param G: グラフ.
// @param s: グラフの探索開始頂点.
// @param c: 連結成分番号の保存領域.
// @param l: 連結成分番号(※1以上).
// @return: 特に無し.
void bfs(vvi &G, int s, int* c, int l){
    // 1. 空のキュー.
    queue<int> q;
    
    // 2. 連結成分番号を設定.
    c[s] = l;
    
    // 3. 探索地点 s をキュー q に追加.
    q.push(s);
    while(!q.empty()){
        // 4. キューから取り出す.
        int u = q.front();
        q.pop();
        
        // 5. 取り出した要素を処理.
        for(auto &e : G[u]){
            // 6. 訪問済であれば, 処理をスキップ.
            if(c[e])            continue;
            if(!c[e] && e != s) c[e] = l, q.push(e);
        }
    }
    return;
}

int main(){
    
    // 1. 入力情報.
    int N, K;
    scanf("%d %d", &N, &K);
    rep(i, N) rep(j, N) scanf("%d", &a[i][j]);
    
    // 2. 階乗計算.
    FAC[0] = 1;
    repx(i, 1, 55) FAC[i] = FAC[i - 1] * (LL)i, FAC[i] %= MOD;
    
    // 3. グラフ作成.
    vvi rG(N), cG(N);
    rep(i, N){
        repx(j, i + 1, N){
            // 行方向.
            bool rOk = true;
            rep(k, N) if(a[i][k] + a[j][k] > K) rOk = false;
            if(rOk) rG[i].pb(j), rG[j].pb(i);
            
            // 列方向.
            bool cOk = true;
            rep(k, N) if(a[k][i] + a[k][j] > K) cOk = false;
            if(cOk) cG[i].pb(j), cG[j].pb(i);
        }
    }
    
    // 4. 探索を行い, 連結成分に分割.
    int rIdx = 0, cIdx = 0;
    rep(i, N){
        if(!rConnection[i]) bfs(rG, i, rConnection, ++rIdx);
        if(!cConnection[i]) bfs(cG, i, cConnection, ++cIdx);
    }
    
    // 5. 各連結成分番号の出現回数を計算.
    rep(i, N) rAppearance[rConnection[i]]++, cAppearance[cConnection[i]]++;
    
    // 6. 集計.
    LL ans = 1;
    repx(i, 1, rIdx + 1) ans *= FAC[rAppearance[i]], ans %= MOD;
    repx(i, 1, cIdx + 1) ans *= FAC[cAppearance[i]], ans %= MOD;
    
    // 7. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc107/editorial/266

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vi = vector<int>;

using vvi = vector<vi>;

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

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

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

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

#define pb push_back

const LL MOD = 998244353;

int a[55][55];

LL FAC[55];

int rConnection[55], cConnection[55]; // 連結成分番号を保存.

LL rAppearance[55], cAppearance[55]; // 連結成分番号の出現回数.

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

// ※bfsの動作確認用.

// @param G: グラフ.

// @param s: グラフの探索開始頂点.

// @param c: 連結成分番号の保存領域.

// @param l: 連結成分番号(※1以上).

// @return: 特に無し.

void bfs(vvi &G, int s, int* c, int l){

// 1. 空のキュー.

queue<int> q;

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

c[s] = l;

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

q.push(s);

while(!q.empty()){

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

int u = q.front();

q.pop();

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

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

// 6. 訪問済であれば, 処理をスキップ.

if(c[e]) continue;

if(!c[e] && e != s) c[e] = l, q.push(e);

}

return;

}

int main(){

// 1. 入力情報.

int N, K;

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

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

// 2. 階乗計算.

FAC[0] = 1;

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

// 3. グラフ作成.

vvi rG(N), cG(N);

rep(i, N){

repx(j, i + 1, N){

// 行方向.

bool rOk = true;

rep(k, N) if(a[i][k] + a[j][k] > K) rOk = false;

if(rOk) rG[i].pb(j), rG[j].pb(i);

// 列方向.

bool cOk = true;

rep(k, N) if(a[k][i] + a[k][j] > K) cOk = false;

if(cOk) cG[i].pb(j), cG[j].pb(i);

}

// 4. 探索を行い, 連結成分に分割.

int rIdx = 0, cIdx = 0;

rep(i, N){

if(!rConnection[i]) bfs(rG, i, rConnection, ++rIdx);

if(!cConnection[i]) bfs(cG, i, cConnection, ++cIdx);

}

// 5. 各連結成分番号の出現回数を計算.

rep(i, N) rAppearance[rConnection[i]]++, cAppearance[cConnection[i]]++;

// 6. 集計.

LL ans = 1;

repx(i, 1, rIdx + 1) ans *= FAC[rAppearance[i]], ans %= MOD;

repx(i, 1, cIdx + 1) ans *= FAC[cAppearance[i]], ans %= MOD;

// 7. 出力.

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

return 0;

}

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

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

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

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

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

[出力例]
1

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

[出力例]
144

[入力例]
7 88
35 15 21 49 23 7 37
36 3 5 47 8 12 42
18 4 14 22 28 30 16
26 29 20 31 10 17 48
45 38 27 43 24 19 6
13 2 40 11 1 46 33
44 25 32 41 34 9 39

[出力例]
25401600

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

[出力例]
350016467

[入力例]

3 13

3 2 7

4 8 9

1 6 5

[出力例]

※AtCoderのテストケースより

[入力例]

10 165

82 94 21 65 28 22 61 80 81 79

93 35 59 85 96 1 78 72 43 5

12 15 97 49 69 53 18 73 6 58

60 14 23 19 44 99 64 17 29 67

24 39 56 92 88 7 48 75 36 91

74 16 26 10 40 63 45 76 86 3

9 66 42 84 38 51 25 2 33 41

87 54 57 62 47 31 68 11 83 8

46 27 55 70 52 98 20 77 89 34

32 71 30 50 90 4 37 95 13 100

[出力例]

348179577

※AtCoderのテストケースより

[入力例]

3 3

1 5 6

2 3 7

4 9 8

[出力例]

[入力例]

5 35

22 21 8 16 23

9 3 13 2 24

4 11 5 20 10

25 14 6 12 18

7 15 17 19 1

[出力例]

144

[入力例]

7 88

35 15 21 49 23 7 37

36 3 5 47 8 12 42

18 4 14 22 28 30 16

26 29 20 31 10 17 48

45 38 27 43 24 19 6

13 2 40 11 1 46 33

44 25 32 41 34 9 39

[出力例]

25401600

[入力例]

12 256

100 91 25 129 49 61 73 85 97 109 121 8

115 14 103 38 18 62 74 32 98 110 22 134

139 118 27 39 51 63 11 87 99 44 123 135

89 16 114 40 112 64 76 88 1 52 124 136

82 17 29 144 53 92 77 4 101 113 48 137

119 50 90 127 54 66 69 30 71 28 126 138

7 19 31 43 105 67 24 13 26 2 42 3

133 107 86 111 56 59 80 65 104 116 128 140

9 21 33 45 57 78 81 93 55 117 37 46

132 122 34 141 58 70 5 94 106 15 130 142

75 23 35 47 68 102 83 95 20 6 131 36

12 79 143 125 60 72 84 96 108 120 10 41

[出力例]

350016467

■参照サイト
AtCoder Regular Contest 107

2020年11月2日

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

C++の練習を兼ねて, AtCoder Beginner Contest 181 の問題D (Hachi) ～問題E (Transformable Teacher) を解いてみた.

■感想.
1. 久しぶりに, 解説見る前に, AC版に到達できたと思う.
2. 個人的には, D問題, E問題ともに, 非常に面白いと感じた.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
int cs[10];   // 数字列 S に 含まれる 各文字 の 個数.

int main(){
    
    // 1. 入力情報.
    char c[202020];
    scanf("%s", c);
    string S(c);
    int l = S.size();
    
    // 2. S が 1桁の場合.
    if(l == 1){
        printf("%s\n", (S[0] == '8') ? "Yes" : "No");
        return 0;
    }
    
    // 3. S が 2桁の場合.
    if(l == 2){
        // 2桁 の 数字で, 8 の 倍数となるもの.
        bool ok = false;
        repx(i, 10, 100){
            string s = to_string(i);
            if(s[0] != '0' && s[1] != '0' && i % 8 == 0){
                if((S[0] == s[0] && S[1] == s[1]) || (S[0] == s[1] && S[1] == s[0])){
                    ok = true;
                    break;
                }
            }
        }
        printf("%s\n", ok ? "Yes" : "No");
        return 0;
    }
    
    // 4. S が 3桁以上 の 場合.
    if(l >= 3){
        // 4桁以上が, どのような組み合わせであっても,
        // 3桁部分が, 8 の 倍数ならば, 全体としても 8 の 倍数 に注意.
        // -> 理由としては, 1000 は, 8 の 倍数であるから.
        rep(i, l) cs[S[i] - '0']++;
        
        // 3桁 の 数字で, 8 の 倍数となるもの.
        bool ok = false;
        repx(i, 100, 1000){
            string s = to_string(i);
            if(s[0] != '0' && s[1] != '0' && s[2] != '0' && i % 8 == 0){
                ok = true;
                int cn[10];
                memset(cn, 0 ,sizeof(cn));
                rep(j, 3) cn[s[j] - '0']++;
                
                // 3桁 の 数字 が, 数字列 S の 文字 で 構成可能か？
                rep(j, 10){
                    // 数字列 S の 文字 では, 構成できない場合は, false.
                    if(cn[j] && cn[j] > cs[j]){
                        ok = false;
                        break;
                    }
                }
            }
            if(ok) break;
        }
        printf("%s\n", ok ? "Yes" : "No");
    }
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

int cs[10]; // 数字列 S に含まれる各文字の個数.

int main(){

// 1. 入力情報.

char c[202020];

scanf("%s", c);

string S(c);

int l = S.size();

// 2. S が 1桁の場合.

if(l == 1){

printf("%s\n", (S[0] == '8') ? "Yes" : "No");

return 0;

}

// 3. S が 2桁の場合.

if(l == 2){

// 2桁の数字で, 8 の倍数となるもの.

bool ok = false;

repx(i, 10, 100){

string s = to_string(i);

if(s[0] != '0' && s[1] != '0' && i % 8 == 0){

if((S[0] == s[0] && S[1] == s[1]) || (S[0] == s[1] && S[1] == s[0])){

ok = true;

break;

}

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

return 0;

}

// 4. S が 3桁以上の場合.

if(l >= 3){

// 4桁以上が, どのような組み合わせであっても,

// 3桁部分が, 8 の倍数ならば, 全体としても 8 の倍数に注意.

// -> 理由としては, 1000 は, 8 の倍数であるから.

rep(i, l) cs[S[i] - '0']++;

// 3桁の数字で, 8 の倍数となるもの.

bool ok = false;

repx(i, 100, 1000){

string s = to_string(i);

if(s[0] != '0' && s[1] != '0' && s[2] != '0' && i % 8 == 0){

ok = true;

int cn[10];

memset(cn, 0 ,sizeof(cn));

rep(j, 3) cn[s[j] - '0']++;

// 3桁の数字が, 数字列 S の文字で構成可能か？

rep(j, 10){

// 数字列 S の文字では, 構成できない場合は, false.

if(cn[j] && cn[j] > cs[j]){

ok = false;

break;

}

if(ok) break;

}

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

}

return 0;

}

[入力例]
1234

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

[入力例]
1333

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

[入力例]
8

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

[入力例]
1233321

[出力例]
Yes

[入力例]
111111111133333333335555555555

[出力例]
No

[入力例]
2333333333333333333333333333333555555555555555555555555555555777777777777777777777777777777999999999

[出力例]
Yes

[入力例]
69999999999777777777755555555553333333333111111111199999999997777777777555555555533333333331111111111999999999977777777775555555555333333333311111111119999999999777777777755555555553333333333111111111199999999997777777777555555555533333333331111111111

[出力例]
Yes

[入力例]

1234

[出力例]

Yes

※AtCoderテストケースより

[入力例]

1333

[出力例]

※AtCoderテストケースより

[入力例]

[出力例]

Yes

※AtCoderテストケースより

[入力例]

1233321

[出力例]

Yes

[入力例]

111111111133333333335555555555

[出力例]

[入力例]

2333333333333333333333333333333555555555555555555555555555555777777777777777777777777777777999999999

[出力例]

Yes

[入力例]

69999999999777777777755555555553333333333111111111199999999997777777777555555555533333333331111111111999999999977777777775555555555333333333311111111119999999999777777777755555555553333333333111111111199999999997777777777555555555533333333331111111111

[出力例]

Yes

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

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

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    rep(i, N) scanf("%lld", &h[i]);
    rep(i, M) scanf("%lld", &w[i]);
    int N2 = N / 2;
    
    // 2. sort.
    sort(h, h + N);
    
    // 3. 累積和.
    rep(i, N2){
        // h[1] - h[0], h[3] - h[2], h[5] - h[4], ... を 保存(※ h[N - 1] が 余る).
        lCum[i + 1] = lCum[i] + abs(h[2 * i + 1] - h[2 * i]);
        
        // h[2] - h[1], h[4] - h[3], h[6] - h[5], ... を 保存(※ h[0] が 余る).
        rCum[i + 1] = rCum[i] + abs(h[2 * i + 2] - h[2 * i + 1]);
    }
    
    // 4. 最小化するには？
    LL ans = 202020202020202020;
    rep(i, M){
        // ex.
        // h[0], h[1], h[2], h[3], h[4] の 場合.
        // at = 0, 1, ... , 5 の パターンがある.
        // at = 0 の場合: h[0] - w[i], h[2] - h[1], h[4] - h[3] の 合計 を 評価.
        // at = 1 の場合: w[i] - h[0], h[2] - h[1], h[4] - h[3] の 合計 を 評価.
        // at = 2 の場合: h[1] - h[0], h[2] - w[i], h[4] - h[3] の 合計 を 評価.
        // at = 3 の場合: h[1] - h[0], w[i] - h[2], h[4] - h[3] の 合計 を 評価.
        // at = 4 の場合: h[1] - h[0], h[3] - h[2], h[4] - w[i] の 合計 を 評価.
        // at = 5 の場合: h[1] - h[0], h[2] - h[1], w[i] - h[4] の 合計 を 評価.
        int at = lower_bound(h, h + N, w[i]) - h;
        int at2 = at / 2;
        
        // 左.
        LL l = lCum[at2];
        
        // 右.
        LL r = rCum[N2] - rCum[at2];
        
        // 中央.
        LL m = abs(w[i] - h[at2 * 2]);
        
        // 最小値更新.
        ans = min(ans, l + m + r);
    }
    
    // 5. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

LL h[202020], w[202020], lCum[101010], rCum[101010];

int main(){

// 1. 入力情報.

int N, M;

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

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

rep(i, M) scanf("%lld", &w[i]);

int N2 = N / 2;

// 2. sort.

sort(h, h + N);

// 3. 累積和.

rep(i, N2){

// h[1] - h[0], h[3] - h[2], h[5] - h[4], ... を保存(※ h[N - 1] が余る).

lCum[i + 1] = lCum[i] + abs(h[2 * i + 1] - h[2 * i]);

// h[2] - h[1], h[4] - h[3], h[6] - h[5], ... を保存(※ h[0] が余る).

rCum[i + 1] = rCum[i] + abs(h[2 * i + 2] - h[2 * i + 1]);

}

// 4. 最小化するには？

LL ans = 202020202020202020;

rep(i, M){

// ex.

// h[0], h[1], h[2], h[3], h[4] の場合.

// at = 0, 1, ... , 5 のパターンがある.

// at = 0 の場合: h[0] - w[i], h[2] - h[1], h[4] - h[3] の合計を評価.

// at = 1 の場合: w[i] - h[0], h[2] - h[1], h[4] - h[3] の合計を評価.

// at = 2 の場合: h[1] - h[0], h[2] - w[i], h[4] - h[3] の合計を評価.

// at = 3 の場合: h[1] - h[0], w[i] - h[2], h[4] - h[3] の合計を評価.

// at = 4 の場合: h[1] - h[0], h[3] - h[2], h[4] - w[i] の合計を評価.

// at = 5 の場合: h[1] - h[0], h[2] - h[1], w[i] - h[4] の合計を評価.

int at = lower_bound(h, h + N, w[i]) - h;

int at2 = at / 2;

// 左.

LL l = lCum[at2];

// 右.

LL r = rCum[N2] - rCum[at2];

// 中央.

LL m = abs(w[i] - h[at2 * 2]);

// 最小値更新.

ans = min(ans, l + m + r);

}

// 5. 出力.

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

return 0;

}

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

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

[入力例]
7 7
31 60 84 23 16 13 32
96 80 73 76 87 57 29

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

[入力例]
15 10
554 525 541 814 661 279 668 360 382 175 833 783 688 793 736
496 732 455 306 189 207 976 73 567 759

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

[入力例]
50 25
6112220 9783018 2479422 2269829 7714144 9539484 6992540 10270860 11097942 8714607 9539098 8475395 9171642 9678191 3494236 4387544 7279578 8352819 4799010 301560 12034975 5647824 5831236 8908282 8301643 7428094 5442233 6313757 3689481 10886952 4957765 7476024 2491214 5604047 11797342 8202939 980344 5711285 4345840 10815056 1638509 7281838 1052127 5696706 11851239 6912861 7386159 578827 4393448 1045889
10894829 11523747 10330013 9016970 1140391 11336743 1169651 2932069 517012 12205331 10771065 3655248 9531446 2609964 2438078 10058915 3136281 4517832 11412406 7395623 10271658 6532730 4207747 8825708 9499227

[出力例]
17375903

[入力例]

5 3

1 2 3 4 7

1 3 8

[出力例]

※AtCoderテストケースより

[入力例]

7 7

31 60 84 23 16 13 32

96 80 73 76 87 57 29

[出力例]

※AtCoderテストケースより

[入力例]

15 10

554 525 541 814 661 279 668 360 382 175 833 783 688 793 736

496 732 455 306 189 207 976 73 567 759

[出力例]

239

※AtCoderテストケースより

[入力例]

50 25

6112220 9783018 2479422 2269829 7714144 9539484 6992540 10270860 11097942 8714607 9539098 8475395 9171642 9678191 3494236 4387544 7279578 8352819 4799010 301560 12034975 5647824 5831236 8908282 8301643 7428094 5442233 6313757 3689481 10886952 4957765 7476024 2491214 5604047 11797342 8202939 980344 5711285 4345840 10815056 1638509 7281838 1052127 5696706 11851239 6912861 7386159 578827 4393448 1045889

10894829 11523747 10330013 9016970 1140391 11336743 1169651 2932069 517012 12205331 10771065 3655248 9531446 2609964 2438078 10058915 3136281 4517832 11412406 7395623 10271658 6532730 4207747 8825708 9499227

[出力例]

17375903

■参照サイト
AtCoder Beginner Contest 181

2020年11月2日

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

C++の練習を兼ねて, AtCoder Regular Contest 090 の問題F (Number of Digits) を解いてみた.

■感想.
1. F問題は, 方針が見えなかったので, 解説を参照して実装して, ようやく, AC版となった.
2. 但し, 正しく数え上げできるまでに, 実装に, 非常に苦労した(※).
※ おそらく, このような内容だろうと推測して, 解説を, 若干読み替えている箇所を含む.
3. AC版となったものの, TLEをギリギリ回避している実装(1985[ms])なので, 高速化について, 将来的な課題として残っている.
4. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/arc090/editorial.pdf
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define all(x) x.begin(), x.end()
#define pb push_back
const LL MOD = 1e9 + 7;
const LL pow10[] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000, 10000000000};

// Fermat's little theorem から, 大きな冪乗の計算を行う.
// @param a: べき乗したい正整数.
// @param b: 指数.
// @return:  べき乗した計算結果(mod版).
LL mPow(LL a, LL b){
    LL t = 1;
    while(b){
        if(b & 1) t = (t * a) % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return t % MOD;
}


// 与えられた正の整数のすべての約数を抽出.
// @param X: 約数を抽出したい正の整数.
// @return ret: すべての約数(※1以上).
set<LL> div(LL X){
    set<LL> ret;
    for(LL d = 1; d * d <= X; d++){
        if(!(X % d)){
            ret.insert(d);
            if(d * d != X) ret.insert(X / d);
        }
    }
    return ret;
}

int main(){
    
    // 1. 入力情報.
    LL S;
    scanf("%lld", &S);
    
    // 2. S の 約数.
    set<LL> s = div(S);
    // for(auto &p : s) printf("%lld ", p);
    // puts("");
    
    // 3. 場合分け.
    // 3-1. f[l] = f[r].
    // ex.
    // S = 50 の 場合.
    //  1桁:         0個
    //  2桁:        66個
    //  5桁:     89991個
    // 10桁: 999999940個 (MOD版)
    // 25桁: 440999999個 (MOD版)
    // 50桁: 487370014個 (MOD版)
    // -> 928460003(MOD版) と 推測される.
    LL ans = 0;
    for(auto &d : s){
        if(d < 11){
            LL nd = pow10[d] - pow10[d - 1];
            ans += max(0LL, nd - (S / d) + 1LL) % MOD;
        }else{
            LL nd = (mPow(10LL, d) + MOD - mPow(10LL, d - 1)) % MOD;
            ans += (nd + MOD - (S / d) + 1LL) % MOD;
        }
        ans %= MOD;
    }
    
    // 3-2. f[r] <= 9 かつ f[r] >= f[l] + 1.
    // l は, 1 ～ 99999999 を取り得るはず(※解説の範囲を拡大する方向に変更).
    function<bool(int, int, LL, LL)> f = [&](int od, int cd, LL sum, LL S){
        // 終了条件.
        if(sum >= S) return false;
        
        // r を確定させるための 残差分を 計算.
        LL ds = S - sum;
        LL dr = pow10[cd] - pow10[cd - 1];
        
        // 残差分を更新.
        if(ds > dr * (LL)cd) sum += dr * (LL)cd;
        else                 return (ds % cd == 0);
        
        // r を 再帰的に, 探索.
        // ※ return を 指定しないと, 正しく動作しないので要注意.
        return f(od, cd + 1, sum, S);
    };
    // ex.
    // S = 50 の 場合.
    // 1桁:  8個, 2桁: 21個
    // 1桁:  6個, 2桁: 22個
    // 1桁:  4個, 2桁: 23個
    // 1桁:  2個, 2桁: 24個
    // 2桁: 22個, 3桁:  2個
    // 2桁: 19個, 3桁:  4個
    // 2桁: 16個, 3桁:  6個
    // 2桁: 13個, 3桁:  8個
    // 2桁: 10個, 3桁: 10個
    // 2桁:  7個, 3桁: 12個
    // 2桁:  4個, 3桁: 14個
    // 2桁:  1個, 3桁: 16個
    // 3桁: 14個, 4桁:  2個
    // 3桁: 10個, 4桁:  5個
    // 3桁:  6個, 4桁:  8個
    // 3桁:  2個, 4桁: 11個
    // 4桁: 10個, 5桁:  2個
    // 4桁:  5個, 5桁:  6個
    // 5桁:  4個, 6桁:  5個
    // 6桁:  6個, 7桁:  2個
    // 7桁:  6個, 8桁:  1個
    // 8桁:  4個, 9桁:  2個 <- 上限を, 10000000 とした場合, 探索から漏れるパターン(※探索方法を要検討)
    // の 22通りが考えられる.
    // 但し, repx の 上限 に 100000000 を 指定すると, 7458[ms] かかるので, TLE版 となってしまう.
    // repx(l, 1, 100000000){
    // -> while文 に 書き換え.
    int l = 0;
    // S = 100 の 場合に, 9桁: 10個, 10桁: 1個 が, 探索から漏れてしまうため, 
    // 探索上限を, 100000000 -> 1000000000 に 変更.
    // while(++l < 100000000){
    // -> 06.txt などのテストケースで, TLE版となるため, 却下.
    // while(++l < 1000000000){
    while(++l < 100000000){
        // l の 桁数.
        string sl = to_string(l);
        int dl = sl.size();
        
        // l の 桁数 と 同じものの総和.
        LL lSum = pow10[dl] - (LL)l;
        lSum *= dl;
        
        // l を Skip.
        if(lSum > S){
            l = pow10[dl] - S / dl;
            if(S % dl == 0) l++;
            lSum = pow10[dl] - (LL)l;
            lSum *= dl;
        }
        
        // r の 存在チェック.
        if(f(dl, dl + 1, lSum, S)) ans++;
    }
    
    // 3-3. f[r] >= 10 かつ f[r] = f[l] + 1.
    // ex.
    // S = 50 の 場合.
    // f[l] = 12, f[r] = 13
    // f[l] = 16, f[r] = 17
    // の 2通りが考えられる.
    // -> 実際, 50 = 12 + 12 + 13 + 13, 16 + 17 + 17 となるからである.
    // int u = (int)(S / 10);
    // if(S % 10 != 0) u++;
    // -> TLE回避のため, 評価する数字を, 10 => 9 に 変更.
    int u = (int)(S / 9);
    if(S % 9 != 0) u++;
    repx(i, 1, u) if(!s.count((LL)i)) ans++, ans %= MOD;
    
    // 5. 出力.
    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

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

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

#define pb push_back

const LL MOD = 1e9 + 7;

const LL pow10[] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000, 10000000000};

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

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

// @param b: 指数.

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

LL mPow(LL a, LL b){

LL t = 1;

while(b){

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

a = a * a % MOD;

b >>= 1;

}

return t % MOD;

}

// 与えられた正の整数のすべての約数を抽出.

// @param X: 約数を抽出したい正の整数.

// @return ret: すべての約数(※1以上).

set<LL> div(LL X){

set<LL> ret;

for(LL d = 1; d * d <= X; d++){

if(!(X % d)){

ret.insert(d);

if(d * d != X) ret.insert(X / d);

}

return ret;

}

int main(){

// 1. 入力情報.

LL S;

scanf("%lld", &S);

// 2. S の約数.

set<LL> s = div(S);

// for(auto &p : s) printf("%lld ", p);

// puts("");

// 3. 場合分け.

// 3-1. f[l] = f[r].

// ex.

// S = 50 の場合.

// 1桁: 0個

// 2桁: 66個

// 5桁: 89991個

// 10桁: 999999940個 (MOD版)

// 25桁: 440999999個 (MOD版)

// 50桁: 487370014個 (MOD版)

// -> 928460003(MOD版) と推測される.

LL ans = 0;

for(auto &d : s){

if(d < 11){

LL nd = pow10[d] - pow10[d - 1];

ans += max(0LL, nd - (S / d) + 1LL) % MOD;

}else{

LL nd = (mPow(10LL, d) + MOD - mPow(10LL, d - 1)) % MOD;

ans += (nd + MOD - (S / d) + 1LL) % MOD;

}

ans %= MOD;

}

// 3-2. f[r] <= 9 かつ f[r] >= f[l] + 1.

// l は, 1 ～ 99999999 を取り得るはず(※解説の範囲を拡大する方向に変更).

function<bool(int, int, LL, LL)> f = [&](int od, int cd, LL sum, LL S){

// 終了条件.

if(sum >= S) return false;

// r を確定させるための残差分を計算.

LL ds = S - sum;

LL dr = pow10[cd] - pow10[cd - 1];

// 残差分を更新.

if(ds > dr * (LL)cd) sum += dr * (LL)cd;

else return (ds % cd == 0);

// r を再帰的に, 探索.

// ※ return を指定しないと, 正しく動作しないので要注意.

return f(od, cd + 1, sum, S);

};

// ex.

// S = 50 の場合.

// 1桁: 8個, 2桁: 21個

// 1桁: 6個, 2桁: 22個

// 1桁: 4個, 2桁: 23個

// 1桁: 2個, 2桁: 24個

// 2桁: 22個, 3桁: 2個

// 2桁: 19個, 3桁: 4個

// 2桁: 16個, 3桁: 6個

// 2桁: 13個, 3桁: 8個

// 2桁: 10個, 3桁: 10個

// 2桁: 7個, 3桁: 12個

// 2桁: 4個, 3桁: 14個

// 2桁: 1個, 3桁: 16個

// 3桁: 14個, 4桁: 2個

// 3桁: 10個, 4桁: 5個

// 3桁: 6個, 4桁: 8個

// 3桁: 2個, 4桁: 11個

// 4桁: 10個, 5桁: 2個

// 4桁: 5個, 5桁: 6個

// 5桁: 4個, 6桁: 5個

// 6桁: 6個, 7桁: 2個

// 7桁: 6個, 8桁: 1個

// 8桁: 4個, 9桁: 2個 <- 上限を, 10000000 とした場合, 探索から漏れるパターン(※探索方法を要検討)

// の 22通りが考えられる.

// 但し, repx の上限に 100000000 を指定すると, 7458[ms] かかるので, TLE版となってしまう.

// repx(l, 1, 100000000){

// -> while文に書き換え.

int l = 0;

// S = 100 の場合に, 9桁: 10個, 10桁: 1個が, 探索から漏れてしまうため,

// 探索上限を, 100000000 -> 1000000000 に変更.

// while(++l < 100000000){

// -> 06.txt などのテストケースで, TLE版となるため, 却下.

// while(++l < 1000000000){

while(++l < 100000000){

// l の桁数.

string sl = to_string(l);

int dl = sl.size();

// l の桁数と同じものの総和.

LL lSum = pow10[dl] - (LL)l;

lSum *= dl;

// l を Skip.

if(lSum > S){

l = pow10[dl] - S / dl;

if(S % dl == 0) l++;

lSum = pow10[dl] - (LL)l;

lSum *= dl;

}

// r の存在チェック.

if(f(dl, dl + 1, lSum, S)) ans++;

}

// 3-3. f[r] >= 10 かつ f[r] = f[l] + 1.

// ex.

// S = 50 の場合.

// f[l] = 12, f[r] = 13

// f[l] = 16, f[r] = 17

// の 2通りが考えられる.

// -> 実際, 50 = 12 + 12 + 13 + 13, 16 + 17 + 17 となるからである.

// int u = (int)(S / 10);

// if(S % 10 != 0) u++;

// -> TLE回避のため, 評価する数字を, 10 => 9 に変更.

int u = (int)(S / 9);

if(S % 9 != 0) u++;

repx(i, 1, u) if(!s.count((LL)i)) ans++, ans %= MOD;

// 5. 出力.

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

return 0;

}

[入力例]
1

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

[入力例]
2

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

[入力例]
123

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

[入力例]
36018

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

[入力例]
1000

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

[入力例]
50

[出力例]
928460027

[入力例]
100

[出力例]
132532820

[入力例]
1234

[出力例]
127428960

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

123

[出力例]

460191684

※AtCoderテストケースより

[入力例]

36018

[出力例]

966522825

※AtCoderテストケースより

[入力例]

1000

[出力例]

184984484

※AtCoderテストケースより

[入力例]

[出力例]

928460027

[入力例]

100

[出力例]

132532820

[入力例]

1234

[出力例]

127428960

■参照サイト
AtCoder Regular Contest 090

2020年11月1日

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

C++の練習を兼ねて, AtCoder Regular Contest 107 の問題A (Simple Math) ～問題B (Quadruple) を解いてみた.

■感想.
1. B問題は, 正しく集計できるまでに, 時間かかったものの, AC版に到達できたので, 良かったと思う.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const LL MOD = 998244353;

int main(){
    
    // 1. 入力情報.
    LL A, B, C;
    scanf("%lld %lld %lld", &A, &B, &C);
    
    // 2. 数式を計算.
    // 2-1. Σa.
    LL ans = 1;
    ans *= (1 + A);
    ans %= MOD;
    ans *= A;
    ans %= MOD;
    ans *= 499122177;
    ans %= MOD;
    
    // 2-2. Σb.
    ans *= (1 + B);
    ans %= MOD;
    ans *= B;
    ans %= MOD;
    ans *= 499122177;
    ans %= MOD;
    
    // 2-3. Σc.
    ans *= (1 + C);
    ans %= MOD;
    ans *= C;
    ans %= MOD;
    ans *= 499122177;
    ans %= MOD;
    
    // 3. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

const LL MOD = 998244353;

int main(){

// 1. 入力情報.

LL A, B, C;

scanf("%lld %lld %lld", &A, &B, &C);

// 2. 数式を計算.

// 2-1. Σa.

LL ans = 1;

ans *= (1 + A);

ans %= MOD;

ans *= A;

ans %= MOD;

ans *= 499122177;

ans %= MOD;

// 2-2. Σb.

ans *= (1 + B);

ans %= MOD;

ans *= B;

ans %= MOD;

ans *= 499122177;

ans %= MOD;

// 2-3. Σc.

ans *= (1 + C);

ans %= MOD;

ans *= C;

ans %= MOD;

ans *= 499122177;

ans %= MOD;

// 3. 出力.

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

return 0;

}

[入力例]
1 2 3

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

[入力例]
1000000000 987654321 123456789

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

[入力例]
314159265 358979323 846264338

[出力例]
72400245

[入力例]

1 2 3

[出力例]

※AtCoderのテストケースより

[入力例]

1000000000 987654321 123456789

[出力例]

951633476

※AtCoderのテストケースより

[入力例]

314159265 358979323 846264338

[出力例]

72400245

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

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

int main(){
    
    // 1. 入力情報.
    int N, K;
    scanf("%d %d", &N, &K);
    
    // 2. (a + b) = K + (c + d) となる組み合わせを集計.
    // 2-1. a + b の 組み合わせ.
    int sab = 2;
    int gab = min(K + 2 * N, 2 * N);
    repx(i, sab, gab + 1){
        // ex.
        // i = N     => (N - 1)通り.
        // i = N + 1 => N通り.
        // i = N + 2 => (N - 1)通り.
        ab[i] = (i > N) ? 2 * N + 1 - i : i - 1;
        ab[i] = max(0LL, ab[i]);
    }
    
    // 2-2. c + d の 組み合わせ.
    int scd = 2;
    int gcd = min(2 * N - K, 2 * N);
    repx(i, scd, gcd + 1){
        cd[i] = (i > N) ? 2 * N + 1 - i : i - 1;
        cd[i] = max(0LL, cd[i]);
    }
    
    // 3. 集計.
    // ※ c + d は, インデックス を K ずらしたものを取得.
    LL ans = 0;
    rep(i, 303030){
        int j = i - K;
        if(j >= 0 && j < 303030) ans += ab[i] * cd[j];
    }
    
    // 4. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

LL ab[303030], cd[303030];

int main(){

// 1. 入力情報.

int N, K;

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

// 2. (a + b) = K + (c + d) となる組み合わせを集計.

// 2-1. a + b の組み合わせ.

int sab = 2;

int gab = min(K + 2 * N, 2 * N);

repx(i, sab, gab + 1){

// ex.

// i = N => (N - 1)通り.

// i = N + 1 => N通り.

// i = N + 2 => (N - 1)通り.

ab[i] = (i > N) ? 2 * N + 1 - i : i - 1;

ab[i] = max(0LL, ab[i]);

}

// 2-2. c + d の組み合わせ.

int scd = 2;

int gcd = min(2 * N - K, 2 * N);

repx(i, scd, gcd + 1){

cd[i] = (i > N) ? 2 * N + 1 - i : i - 1;

cd[i] = max(0LL, cd[i]);

}

// 3. 集計.

// ※ c + d は, インデックスを K ずらしたものを取得.

LL ans = 0;

rep(i, 303030){

int j = i - K;

if(j >= 0 && j < 303030) ans += ab[i] * cd[j];

}

// 4. 出力.

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

return 0;

}

[入力例]
2 1

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

[入力例]
2525 -425

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

[入力例]
2 0

[出力例]
6

[入力例]
3 0

[出力例]
19

[入力例]
3 1

[出力例]
16

[入力例]
3 2

[出力例]
10

[入力例]
3 3

[出力例]
4

[入力例]
3 4

[出力例]
1

[入力例]
31415 9265

[出力例]
18370006445360

[入力例]
31415 -9265

[出力例]
18370006445360

[入力例]
98765 43210

[出力例]
498204703553400

[入力例]

2 1

[出力例]

※AtCoderのテストケースより

[入力例]

2525 -425

[出力例]

10314607400

※AtCoderのテストケースより

[入力例]

2 0

[出力例]

[入力例]

3 0

[出力例]

[入力例]

3 1

[出力例]

[入力例]

3 2

[出力例]

[入力例]

3 3

[出力例]

[入力例]

3 4

[出力例]

[入力例]

31415 9265

[出力例]

18370006445360

[入力例]

31415 -9265

[出力例]

18370006445360

[入力例]

98765 43210

[出力例]

498204703553400

■参照サイト
AtCoder Regular Contest 107

2020年10月31日

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

C++の練習を兼ねて, AtCoder Regular Contest 090 の問題E (Avoiding Collision) を解いてみた.

■感想.
1. E問題は, 方針が全く見えず, 解説を確認して, AC版に到達できたので, 良かったと思う.
2. ダイクストラ法の復習が出来たので, 非常に良かったと思う.
3. 苦手なdpの訓練を積めたので, 非常に良かったと思う.
4. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/arc090/editorial.pdf
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using PII = pair<int, int>;
using PLI = pair<LL, 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
const LL INF = 202020202020202020;
const LL MOD = 1e9 + 7;
LL dp1[202020]; // 頂点 S から 頂点 v への 最短路 の 個数.
LL dp2[202020]; // 頂点 v から 頂点 T への 最短路 の 個数.

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

LL d[101010]; // 頂点 S から 各頂点への 最短距離 を 保存.
vector<edge> G[101010];

// https://ja.wikipedia.org/wiki/ダイクストラ法
// グラフを最良優先探索する.
// ※dijkstraの動作確認用.
// @param s: 今回探索する頂点番号.
// @return: 特に無し.
void dijkstra(int s){
    
    // 1. 初期化.
    priority_queue<edge> pq;
    
    // 2. 始点設定.
    d[s] = 0;
    pq.push({s, 0LL});
    
    // 3. キュー pq が 空になるまで, 探索.
    while(!pq.empty()){
        // 4. 探索を継続するために, 頂点を取得.
        edge e = pq.top();
        pq.pop();
        int cn = e.n;
        LL cc = e.c;
        
        // 5. より小さい距離が設定済みなら, Skip.
        if(d[cn] < cc) continue;
        
        // 6. 各隣接する頂点について, 距離を確認し, 最短経路を更新.
        for(auto &g : G[cn]){
            int nn = g.n;
            LL nc = cc + g.c;
            
            // 最短経路更新.
            if(d[nn] > nc) d[nn] = nc, pq.push({nn, nc});
        }
    }
}

int main(){
    
    // 1. 入力情報.
    int N, M, S, T;
    scanf("%d %d %d %d", &N, &M, &S, &T);
    S--, T--;
    map<PII, LL> m;
    rep(i, M){
        int u, v;
        LL d;
        scanf("%d %d %lld", &u, &v, &d);
        u--, v--;
        G[u].pb({v, d});
        G[v].pb({u, d});
        m[{u, v}] = d;
        m[{v, u}] = d;
    }
    
    // 2. 頂点 S から 各頂点への最短経路を求める(ダイクストラ法).
    rep(i, N) d[i] = INF;
    dijkstra(S);
    // rep(i, N) printf("%lld ", d[i]);
    // puts("");
    
    // 3. 頂点 S から 遠い順, 近い順 に並び替え.
    priority_queue<PLI> fPq;
    priority_queue<PLI, vector<PLI>, greater<PLI>> nPq;
    rep(i, N){
        // {距離, 頂点番号}
        fPq.push({d[i], i});
        nPq.push({d[i], i});
    }
    
    // 4. dp1更新.
    // -> 頂点 S から 頂点 v への 最短路 の 個数 を 計算.
    dp1[S] = 1;
    while(!nPq.empty()){
        // 4-1. 頂点 u を一つ取り出す.
        PLI p = nPq.top();
        nPq.pop();
        
        // 4-2. 頂点 u の 頂点番号は？
        int u = p.b;
        
        // 4-3. 頂点 u から 頂点 v に向かって, dp1更新.
        for(auto &e : G[u]){
            // d[u] + c = d[v] が 成立するか？
            int v = e.n;
            LL cUV = m[{u, v}];
            if(d[u] + cUV == d[v]) dp1[v] += dp1[u], dp1[v] %= MOD;
        }
    }
    // rep(i, N) printf("%lld ", dp1[i]);
    // puts("");
    
    // 5. dp2更新.
    // -> 頂点 v から 頂点 T への 最短路 の 個数 を 計算.
    dp2[T] = 1;
    while(!fPq.empty()){
        // 4-1. 頂点 u を一つ取り出す.
        PLI p = fPq.top();
        fPq.pop();
        
        // 4-2. 頂点 u の 頂点番号は？
        int u = p.b;
        
        // 4-3. 頂点 u から 頂点 v に向かって, dp2更新.
        for(auto &e : G[u]){
            // d[v] + c = d[u] が 成立するか？
            int v = e.n;
            LL cUV = m[{u, v}];
            if(d[v] + cUV == d[u]) dp2[v] += dp2[u], dp2[v] %= MOD;
        }
    }
    // rep(i, N) printf("%lld ", dp2[i]);
    // puts("");
    
    // 6. 最短路の組の個数は？
    // 6-1. 途中で出会うものも含めた最短路の選び方の組.
    LL p1 = dp1[T] * dp1[T] % MOD;
    
    // 6-2. 途中(頂点上)で出会う最短路の選び方の組.
    LL p2 = 0;
    rep(i, N){
        // 2 * d[v] = d[T] となる 各頂点 v で集計.
        if(2 * d[i] == d[T]){
            LL s1 = dp1[i] * dp1[i] % MOD;
            LL s2 = dp2[i] * dp2[i] % MOD;
            p2 += s1 * s2 % MOD;
            p2 %= MOD;
        }
    }
    
    // 6-3. 途中(辺上)で出会う最短路の選び方の組.
    LL p3 = 0;
    for(auto &e : m){
        int u = e.a.a, v = e.a.b;
        LL c = e.b;
        // 2 * d[u] < d[T] かつ 2 * d[v] > d[T] かつ d[u] + c = d[v] となる 各辺(u, v) で集計.
        if(2 * d[u] < d[T] && 2 * d[v] > d[T] && d[u] + c == d[v]){
            LL s1 = dp1[u] * dp1[u] % MOD;
            LL s2 = dp2[v] * dp2[v] % MOD;
            p3 += s1 * s2 % MOD;
            p3 %= MOD;
        }
    }
    
    // 7. 出力.
    LL ans = (p1 + (MOD - p2) + (MOD - p3)) % MOD;
    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

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using PII = pair<int, int>;

using PLI = pair<LL, 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

const LL INF = 202020202020202020;

const LL MOD = 1e9 + 7;

LL dp1[202020]; // 頂点 S から頂点 v への最短路の個数.

LL dp2[202020]; // 頂点 v から頂点 T への最短路の個数.

struct edge{

int n; // 次の頂点.

LL c; // コスト.

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

};

LL d[101010]; // 頂点 S から各頂点への最短距離を保存.

vector<edge> G[101010];

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

// グラフを最良優先探索する.

// ※dijkstraの動作確認用.

// @param s: 今回探索する頂点番号.

// @return: 特に無し.

void dijkstra(int s){

// 1. 初期化.

priority_queue<edge> pq;

// 2. 始点設定.

d[s] = 0;

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

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

while(!pq.empty()){

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

edge e = pq.top();

pq.pop();

int cn = e.n;

LL cc = e.c;

// 5. より小さい距離が設定済みなら, Skip.

if(d[cn] < cc) continue;

// 6. 各隣接する頂点について, 距離を確認し, 最短経路を更新.

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

int nn = g.n;

LL nc = cc + g.c;

// 最短経路更新.

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

}

int main(){

// 1. 入力情報.

int N, M, S, T;

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

S--, T--;

map<PII, LL> m;

rep(i, M){

int u, v;

LL d;

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

u--, v--;

G[u].pb({v, d});

G[v].pb({u, d});

m[{u, v}] = d;

m[{v, u}] = d;

}

// 2. 頂点 S から各頂点への最短経路を求める(ダイクストラ法).

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

dijkstra(S);

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

// puts("");

// 3. 頂点 S から遠い順, 近い順に並び替え.

priority_queue<PLI> fPq;

priority_queue<PLI, vector<PLI>, greater<PLI>> nPq;

rep(i, N){

// {距離, 頂点番号}

fPq.push({d[i], i});

nPq.push({d[i], i});

}

// 4. dp1更新.

// -> 頂点 S から頂点 v への最短路の個数を計算.

dp1[S] = 1;

while(!nPq.empty()){

// 4-1. 頂点 u を一つ取り出す.

PLI p = nPq.top();

nPq.pop();

// 4-2. 頂点 u の頂点番号は？

int u = p.b;

// 4-3. 頂点 u から頂点 v に向かって, dp1更新.

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

// d[u] + c = d[v] が成立するか？

int v = e.n;

LL cUV = m[{u, v}];

if(d[u] + cUV == d[v]) dp1[v] += dp1[u], dp1[v] %= MOD;

}

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

// puts("");

// 5. dp2更新.

// -> 頂点 v から頂点 T への最短路の個数を計算.

dp2[T] = 1;

while(!fPq.empty()){

// 4-1. 頂点 u を一つ取り出す.

PLI p = fPq.top();

fPq.pop();

// 4-2. 頂点 u の頂点番号は？

int u = p.b;

// 4-3. 頂点 u から頂点 v に向かって, dp2更新.

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

// d[v] + c = d[u] が成立するか？

int v = e.n;

LL cUV = m[{u, v}];

if(d[v] + cUV == d[u]) dp2[v] += dp2[u], dp2[v] %= MOD;

}

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

// puts("");

// 6. 最短路の組の個数は？

// 6-1. 途中で出会うものも含めた最短路の選び方の組.

LL p1 = dp1[T] * dp1[T] % MOD;

// 6-2. 途中(頂点上)で出会う最短路の選び方の組.

LL p2 = 0;

rep(i, N){

// 2 * d[v] = d[T] となる各頂点 v で集計.

if(2 * d[i] == d[T]){

LL s1 = dp1[i] * dp1[i] % MOD;

LL s2 = dp2[i] * dp2[i] % MOD;

p2 += s1 * s2 % MOD;

p2 %= MOD;

}

// 6-3. 途中(辺上)で出会う最短路の選び方の組.

LL p3 = 0;

for(auto &e : m){

int u = e.a.a, v = e.a.b;

LL c = e.b;

// 2 * d[u] < d[T] かつ 2 * d[v] > d[T] かつ d[u] + c = d[v] となる各辺(u, v) で集計.

if(2 * d[u] < d[T] && 2 * d[v] > d[T] && d[u] + c == d[v]){

LL s1 = dp1[u] * dp1[u] % MOD;

LL s2 = dp2[v] * dp2[v] % MOD;

p3 += s1 * s2 % MOD;

p3 %= MOD;

}

// 7. 出力.

LL ans = (p1 + (MOD - p2) + (MOD - p3)) % MOD;

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

return 0;

}

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

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

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

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

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

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

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

[出力例]
8

[入力例]

4 4

1 3

1 2 1

2 3 1

3 4 1

4 1 1

[出力例]

※AtCoderテストケースより

[入力例]

3 3

1 3

1 2 1

2 3 1

3 1 2

[出力例]

※AtCoderテストケースより

[入力例]

8 13

4 2

7 3 9

6 2 3

1 6 4

7 6 9

3 8 9

1 2 2

2 8 12

8 6 9

2 5 5

4 2 18

5 3 7

5 1 515371567

4 8 6

[出力例]

※AtCoderテストケースより

[入力例]

10 12

5 10

1 3 1

1 2 2

2 6 3

6 5 2

3 5 8

3 10 10

3 4 4

4 10 6

10 7 12

8 7 7

9 8 2

10 9 3

[出力例]

■参照サイト
AtCoder Regular Contest 090

C++の練習を兼ねて, AtCoder Beginner Contest 180 の 問題E (Traveling Salesman among Aerial Cities) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 182 の 問題C (To 3) ～ 問題E (Akari) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 107 の 問題E (Mex Mat) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 107 の 問題D (Number of Multisets) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 107 の 問題C (Shuffle Permutation) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 181 の 問題D (Hachi) ～ 問題E (Transformable Teacher) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 090 の 問題F (Number of Digits) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 107 の 問題A (Simple Math) ～ 問題B (Quadruple) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 090 の 問題E (Avoiding Collision) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 180 の問題E (Traveling Salesman among Aerial Cities) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 182 の問題C (To 3) ～問題E (Akari) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 107 の問題E (Mex Mat) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 107 の問題D (Number of Multisets) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 107 の問題C (Shuffle Permutation) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 181 の問題D (Hachi) ～問題E (Transformable Teacher) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 090 の問題F (Number of Digits) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 107 の問題A (Simple Math) ～問題B (Quadruple) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 090 の問題E (Avoiding Collision) を解いてみた.