C++ | 個人用メモ帳

2021年9月5日

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

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

■感想.
1. 問題081は, 方針が見えなかったので, (問題081 (Friendly Group) 解説) を参考に実装したところ, AC版に到達出来た.
2. 二次元累積和の復習が出来たので良かったと思う.
3. 手強い問題が非常に多い気もするけど, 時間を見つけて, 引き続き, 取り組んでいきたいと思う.

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

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

// 解き直し.
// https://github.com/E869120/kyopro_educational_90/blob/main/editorial/081.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 a[202020], b[202020], c[5050][5050];

int main(){
    
    // 1. 入力情報.
    int N, K;
    scanf("%d %d", &N, &K);
    rep(i, N) scanf("%d %d", &a[i], &b[i]);
    rep(i, N) c[a[i]][b[i]]++;
    
    // 2. 二次元累積和(解説通り).
    int ans = 0;
    repx(i, 1, 5001) repx(j, 1, 5001) c[i][j] += c[i][j - 1]; // 横方向.
    repx(j, 1, 5001) repx(i, 1, 5001) c[i][j] += c[i - 1][j]; // 縦方向.
    repx(lx, 1, 5001 - K){
        repx(ly, 1, 5001 - K){
            int rx = lx + K;
            int ry = ly + K;
            ans = max(ans, c[rx][ry] - c[lx - 1][ry] - c[rx][ly - 1] + c[lx - 1][ly - 1]);
        }
    }
    
    // 3. 出力.
    printf("%d\n", ans);
    return 0;
    
}

// 解き直し.

// https://github.com/E869120/kyopro_educational_90/blob/main/editorial/081.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 a[202020], b[202020], c[5050][5050];

int main(){

// 1. 入力情報.

int N, K;

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

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

rep(i, N) c[a[i]][b[i]]++;

// 2. 二次元累積和(解説通り).

int ans = 0;

repx(i, 1, 5001) repx(j, 1, 5001) c[i][j] += c[i][j - 1]; // 横方向.

repx(j, 1, 5001) repx(i, 1, 5001) c[i][j] += c[i - 1][j]; // 縦方向.

repx(lx, 1, 5001 - K){

repx(ly, 1, 5001 - K){

int rx = lx + K;

int ry = ly + K;

ans = max(ans, c[rx][ry] - c[lx - 1][ry] - c[rx][ly - 1] + c[lx - 1][ly - 1]);

}

// 3. 出力.

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

return 0;

}

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

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

[入力例]
2 123
4 5
678 901

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

[入力例]
7 10
20 20
20 20
20 30
20 40
30 20
30 30
40 20

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

[入力例]
20 48
168 72
182 79
193 59
176 53
145 55
158 72
129 56
148 66
206 79
150 59
172 72
200 76
197 57
136 41
157 67
127 59
199 70
157 50
157 67
141 42

[出力例]
13

[入力例]

3 4

1 1

2 5

7 4

[出力例]

※AtCoderテストケースより

[入力例]

2 123

4 5

678 901

[出力例]

※AtCoderテストケースより

[入力例]

7 10

20 20

20 30

20 40

30 20

30 30

40 20

[出力例]

※AtCoderテストケースより

[入力例]

20 48

168 72

182 79

193 59

176 53

145 55

158 72

129 56

148 66

206 79

150 59

172 72

200 76

197 57

136 41

157 67

127 59

199 70

157 50

157 67

141 42

[出力例]

■参照サイト
081 – Friendly Group
問題081 (Friendly Group) 解説

2021年9月4日

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

C++の練習を兼ねて, 競プロ典型 90 問の問題073 (We Need Both a and b) を解いてみた.

■感想.
1. 問題073は, 方針が見えなかったので, (問題073 (We Need Both a and b) 解説) を参考に実装したところ, AC版に到達出来た.
2. 苦手な動的計画法(木dp)の訓練を積めたこと, 幅優先探索の復習が出来たので, 非常に良かったと思う.
3. 手強い問題が非常に多い気もするけど, 時間を見つけて, 引き続き, 取り組んでいきたいと思う.

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

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

// 解き直し.
// https://github.com/E869120/kyopro_educational_90/blob/main/editorial/073.jpg
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vvi = vector<vector<int>>;
using P = pair<int, int>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
#define a first
#define b second
const LL MOD = 1e9 + 7;
int c[101010];    // 文字 'a', 'b'.
LL dp[101010][3]; // 木dp.

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N){
        char x[11];
        scanf("%s", x);
        c[i] = (x[0] == 'b') ? 1 : 0;
    }
    vvi G(N);
    rep(i, N - 1){
        int a, b;
        scanf("%d %d", &a, &b);
        a--, b--;
        G[a].pb(b);
        G[b].pb(a);
    }
    
    // 2. 根(頂点 1) から 各頂点までの距離を計算.
    // https://ja.wikipedia.org/wiki/幅優先探索
    auto bfs = [&](vvi &G, int s, int* d){
        // 3-1. 空のキュー.
        queue<int> q;
        
        // 3-2. 探索地点 s をキュー q に追加.
        q.push(s);
        while(!q.empty()){
            // 3-3. キューから取り出す.
            int u = q.front();
            q.pop();
            
            // 3-4. 取り出した要素を処理.
            for(auto &e : G[u]) if(!d[e] && e != s) d[e] = d[u] + 1, q.push(e);
        }
        return;
    };
    int d[N];
    rep(i, N) d[i] = 0;
    bfs(G, 0, d);
    // rep(i, N) printf("%d ", d[i]);
    // puts("");
    
    // 3. 事前計算.
    // 3-1. 頂点 1 から 遠い順 に並び替え.
    priority_queue<P> pq;
    rep(i, N) pq.push({d[i], i}); // {距離, 頂点番号}
    
    // 4. 木dp.
    while(!pq.empty()){
        // 4-1. 頂点 v を一つ取り出す.
        P p = pq.top();
        pq.pop();
        
        // 4-2. 頂点 v の 頂点番号は？
        int v = p.b;
        
        // 4-3. 頂点 v が, 'a' の 場合.
        if(!c[v]){
            // 頂点 v 自身について, 更新.
            dp[v][0]++;
            dp[v][2]++;
            LL dpSum1 = 1, dpSum2 = 1;
            
            // 頂点 v の 子供 に相当する 頂点について, 更新.
            for(auto &u : G[v]){
                // 頂点 v の 子供 に 相当する頂点 u を 選択.
                if(d[u] > d[v]){
                    // 頂点 v の 周囲 の 頂点 u の 情報 を 反映.
                    // dp[v][0] への 反映用.
                    dpSum1 *= (dp[u][0] + dp[u][2]);
                    dpSum1 %= MOD;
                    
                    // dp[v][2] への 反映用.
                    dpSum2 *= (dp[u][0] + dp[u][1] + 2 * dp[u][2]);
                    dpSum2 %= MOD;
                }
            }
            
            // dp[v][0] へ 反映.
            dp[v][0] *= dpSum1;
            dp[v][0] %= MOD;
            
            // dp[v][2] へ 反映.
            dp[v][2] *= (dpSum2 + MOD - dpSum1);
            dp[v][2] %= MOD;
        }
        
        // 4-4. 頂点 v が, 'b' の 場合.
        if(c[v]){
            // 頂点 v 自身について, 更新.
            dp[v][1]++;
            dp[v][2]++;
            LL dpSum1 = 1, dpSum2 = 1;
            
            // 頂点 v の 子供 に相当する 頂点について, 更新.
            for(auto &u : G[v]){
                // 頂点 v の 子供 に 相当する頂点 u を 選択.
                if(d[u] > d[v]){
                    // 頂点 v の 周囲 の 頂点 u の 情報 を 反映.
                    // dp[v][1] への 反映用.
                    dpSum1 *= (dp[u][1] + dp[u][2]);
                    dpSum1 %= MOD;
                    
                    // dp[v][2] への 反映用.
                    dpSum2 *= (dp[u][0] + dp[u][1] + 2 * dp[u][2]);
                    dpSum2 %= MOD;
                }
            }
            
            // dp[v][1] へ 反映.
            dp[v][1] *= dpSum1;
            dp[v][1] %= MOD;
            
            // dp[v][2] へ 反映.
            dp[v][2] *= (dpSum2 + MOD - dpSum1);
            dp[v][2] %= MOD;
        }
    }
    
    // 5. 出力.
    printf("%lld\n", dp[0][2]);
    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

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vvi = vector<vector<int>>;

using P = pair<int, int>;

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

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

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

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

#define pb push_back

#define a first

#define b second

const LL MOD = 1e9 + 7;

int c[101010]; // 文字 'a', 'b'.

LL dp[101010][3]; // 木dp.

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

rep(i, N){

char x[11];

scanf("%s", x);

c[i] = (x[0] == 'b') ? 1 : 0;

}

vvi G(N);

rep(i, N - 1){

int a, b;

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

a--, b--;

G[a].pb(b);

G[b].pb(a);

}

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

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

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

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

queue<int> q;

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

q.push(s);

while(!q.empty()){

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

int u = q.front();

q.pop();

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

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

}

return;

};

int d[N];

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

bfs(G, 0, d);

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

// puts("");

// 3. 事前計算.

// 3-1. 頂点 1 から遠い順に並び替え.

priority_queue<P> pq;

rep(i, N) pq.push({d[i], i}); // {距離, 頂点番号}

// 4. 木dp.

while(!pq.empty()){

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

P p = pq.top();

pq.pop();

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

int v = p.b;

// 4-3. 頂点 v が, 'a' の場合.

if(!c[v]){

// 頂点 v 自身について, 更新.

dp[v][0]++;

dp[v][2]++;

LL dpSum1 = 1, dpSum2 = 1;

// 頂点 v の子供に相当する頂点について, 更新.

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

// 頂点 v の子供に相当する頂点 u を選択.

if(d[u] > d[v]){

// 頂点 v の周囲の頂点 u の情報を反映.

// dp[v][0] への反映用.

dpSum1 *= (dp[u][0] + dp[u][2]);

dpSum1 %= MOD;

// dp[v][2] への反映用.

dpSum2 *= (dp[u][0] + dp[u][1] + 2 * dp[u][2]);

dpSum2 %= MOD;

}

// dp[v][0] へ反映.

dp[v][0] *= dpSum1;

dp[v][0] %= MOD;

// dp[v][2] へ反映.

dp[v][2] *= (dpSum2 + MOD - dpSum1);

dp[v][2] %= MOD;

}

// 4-4. 頂点 v が, 'b' の場合.

if(c[v]){

// 頂点 v 自身について, 更新.

dp[v][1]++;

dp[v][2]++;

LL dpSum1 = 1, dpSum2 = 1;

// 頂点 v の子供に相当する頂点について, 更新.

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

// 頂点 v の子供に相当する頂点 u を選択.

if(d[u] > d[v]){

// 頂点 v の周囲の頂点 u の情報を反映.

// dp[v][1] への反映用.

dpSum1 *= (dp[u][1] + dp[u][2]);

dpSum1 %= MOD;

// dp[v][2] への反映用.

dpSum2 *= (dp[u][0] + dp[u][1] + 2 * dp[u][2]);

dpSum2 %= MOD;

}

// dp[v][1] へ反映.

dp[v][1] *= dpSum1;

dp[v][1] %= MOD;

// dp[v][2] へ反映.

dp[v][2] *= (dpSum2 + MOD - dpSum1);

dp[v][2] %= MOD;

}

// 5. 出力.

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

return 0;

}

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

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

[入力例]
2
a b
1 2

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

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

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

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

[出力例]
0

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

[出力例]
6

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

[出力例]
6

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

[出力例]
5

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

[出力例]
1464

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

[出力例]
222480

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

[入力例]

b a b a b b a

2 1

3 7

3 2

3 4

5 4

4 6

[出力例]

※AtCoderテストケースより

[入力例]

a b

1 2

[出力例]

※AtCoderテストケースより

[入力例]

b a b b a b b b a b a a a a b b a b b a a a

1 7

4 14

12 22

2 4

21 17

3 20

7 8

20 14

15 11

8 14

9 12

17 8

6 20

11 20

18 19

10 8

22 20

13 21

5 14

19 20

16 14

[出力例]

※AtCoderテストケースより

[入力例]

a a a

1 2

1 3

[出力例]

[入力例]

a a b a b b a

1 3

1 4

3 2

4 5

4 6

6 7

[出力例]

[入力例]

a a a a b b b b b a

1 3

1 4

7 3

3 2

2 8

2 9

2 10

6 4

5 4

[出力例]

[入力例]

b b a a a a b a a a a b

1 12

4 1

1 5

5 2

5 3

8 2

9 2

4 7

6 4

6 10

6 11

[出力例]

[入力例]

a a b a b a a a a b a b a b b b a b b a b a b b b b b a a b a

1 3

1 5

1 7

7 23

7 6

5 2

2 15

2 16

3 4

3 8

4 24

4 25

8 9

9 10

9 11

9 12

9 13

9 14

14 20

14 21

14 22

10 17

10 18

11 19

13 26

26 27

26 28

26 29

26 30

26 31

[出力例]

1464

[入力例]

b b a b b b a b b a b a b b a b a b a b a b a a b b a a a b b a b a a a a b b b a a b b b b b a a b a a b a a

1 3

1 8

1 17

1 13

1 16

16 43

16 41

16 42

13 14

13 15

14 31

14 30

30 32

30 33

32 34

32 35

3 12

3 4

4 5

4 7

7 6

7 9

7 22

12 28

12 29

9 2

2 23

2 10

2 11

11 27

11 26

26 39

26 40

6 24

6 25

24 36

36 37

36 38

17 18

17 19

19 20

19 21

8 44

44 45

44 46

44 47

45 49

47 48

48 50

48 51

48 52

46 55

46 54

46 53

[出力例]

222480

■参照サイト
073 – We Need Both a and b
問題073 (We Need Both a and b) 解説

2021年9月4日2021年9月4日

■感想.
1. 問題068は, 方針が見えなかったので, (問題068 (Paired Information) 解説) を参考に実装したところ, AC版に到達出来た.
2. 実装に非常に苦労したものの, 個人的には, Ambiguous であるか否かの判定に, グラフの連結状況(Union-Find木)を考える部分が, 非常に面白いと感じた.
3. Union-Find木, 幅優先探索の復習が出来たので, 非常に良かったと思う.
※ 公式のライブラリを拝借させて頂いてます.
4. 手強い問題が非常に多い気もするけど, 時間を見つけて, 引き続き, 取り組んでいきたいと思う.

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

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

// 解き直し.
// https://github.com/E869120/kyopro_educational_90/blob/main/editorial/068.jpg
// 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 int MAX = 101010;
int t[MAX], x[MAX], y[MAX];
LL v0[MAX], v1[MAX];

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

int main(){
    
    // 1. 入力情報.
    int N, Q;
    scanf("%d %d", &N, &Q);
    vvi G(N);
    rep(i, Q){
        LL u;
        scanf("%d %d %d %lld", &t[i], &x[i], &y[i], &u);
        x[i]--;
        y[i]--;
        if(t[i]) v1[i] = u;
        else     v0[x[i]] = u;
        
        // グラフ作成.
        if(!t[i]){
            G[x[i]].pb(y[i]);
            G[y[i]].pb(x[i]);
        }
    }
    
    // 2. グラフを連結成分に分解.
    // https://ja.wikipedia.org/wiki/幅優先探索
    auto bfs = [&](vvi &G, int s, int* c, int l){
        // 2-1. 空のキュー.
        queue<int> q;
        
        // 2-2. 連結成分番号を設定.
        c[s] = l;
        
        // 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]) if(e != s && !c[e]) c[e] = l, q.push(e);
        }
        return;
    };
    int b[N], c[N], idx = 0;
    rep(i, N) b[i] = c[i] = 0;
    rep(i, N) if(!c[i]) bfs(G, i, c, ++idx);
    
    // 3. 二つのパターン作成.
    // 3-1. 0 を ベース に考える場合.
    LL a0[N];
    a0[0] = 0;
    rep(i, N - 1){
        if(c[i] == c[i + 1]) a0[i + 1] = v0[i] - a0[i];
        else                 a0[i + 1] = 0;
    }
    
    // 3-2. 1 を ベース に考える場合.
    LL a1[N];
    a1[0] = 1;
    rep(i, N - 1){
        if(c[i] == c[i + 1]) a1[i + 1] = v0[i] - a1[i];
        else                 a1[i + 1] = 1;
    }
    
    // 4. クエリ回答.
    UnionFind uf(N + 1);
    rep(i, Q){
        // 4-1. T が 0 の 場合.
        if(!t[i]) uf.unite(x[i], y[i]);
        
        // 4-2. T が 1 の 場合.
        if(t[i]){
            // 確定しない場合.
            if(!uf.same(x[i], y[i])) puts("Ambiguous");
            
            // 確定する場合.
            if(uf.same(x[i], y[i])){
                // 基準値 + 符号(対象) × 符号(基準) × 差分
                LL ans = a0[y[i]] + (a1[y[i]] - a0[y[i]]) * (a1[x[i]] - a0[x[i]]) * (v1[i] - a0[x[i]]);
                
                // 出力.
                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

// 解き直し.

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

// 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 int MAX = 101010;

int t[MAX], x[MAX], y[MAX];

LL v0[MAX], v1[MAX];

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

// UnionFind

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

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

// -> 一部改変.

struct UnionFind{

vi d;

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

int find(int x){

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

}

bool unite(int x, int y){

x = find(x);

y = find(y);

if(x == y) return false;

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

d[x] += d[y];

d[y] = x;

return true;

}

bool same(int x, int y){

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

}

int size(int x){

return -d[find(x)];

}

};

int main(){

// 1. 入力情報.

int N, Q;

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

vvi G(N);

rep(i, Q){

LL u;

scanf("%d %d %d %lld", &t[i], &x[i], &y[i], &u);

x[i]--;

y[i]--;

if(t[i]) v1[i] = u;

else v0[x[i]] = u;

// グラフ作成.

if(!t[i]){

G[x[i]].pb(y[i]);

G[y[i]].pb(x[i]);

}

// 2. グラフを連結成分に分解.

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

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

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

queue<int> q;

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

c[s] = l;

// 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]) if(e != s && !c[e]) c[e] = l, q.push(e);

}

return;

};

int b[N], c[N], idx = 0;

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

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

// 3. 二つのパターン作成.

// 3-1. 0 をベースに考える場合.

LL a0[N];

a0[0] = 0;

rep(i, N - 1){

if(c[i] == c[i + 1]) a0[i + 1] = v0[i] - a0[i];

else a0[i + 1] = 0;

}

// 3-2. 1 をベースに考える場合.

LL a1[N];

a1[0] = 1;

rep(i, N - 1){

if(c[i] == c[i + 1]) a1[i + 1] = v0[i] - a1[i];

else a1[i + 1] = 1;

}

// 4. クエリ回答.

UnionFind uf(N + 1);

rep(i, Q){

// 4-1. T が 0 の場合.

if(!t[i]) uf.unite(x[i], y[i]);

// 4-2. T が 1 の場合.

if(t[i]){

// 確定しない場合.

if(!uf.same(x[i], y[i])) puts("Ambiguous");

// 確定する場合.

if(uf.same(x[i], y[i])){

// 基準値 + 符号(対象) × 符号(基準) × 差分

LL ans = a0[y[i]] + (a1[y[i]] - a0[y[i]]) * (a1[x[i]] - a0[x[i]]) * (v1[i] - a0[x[i]]);

// 出力.

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

}

return 0;

}

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

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

[入力例]
15
25
0 11 12 41
0 1 2 159
0 14 15 121
0 4 5 245
0 12 13 157
0 9 10 176
0 6 7 170
0 2 3 123
0 7 8 167
0 3 4 159
1 12 11 33
0 10 11 116
0 8 9 161
1 9 12 68
1 12 12 33
1 7 12 74
0 5 6 290
1 8 9 93
0 13 14 127
1 10 12 108
1 14 1 3
1 13 8 124
1 12 11 33
1 12 10 33
1 5 15 194

[出力例]
8
33
33
33
68
33
144
93
8
108
118
※AtCoderテストケースより

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

[出力例]
5
Ambiguous
Ambiguous
-2
11
-1
1
Ambiguous

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

[出力例]
-3
Ambiguous
0
Ambiguous
3
11
3
2
Ambiguous
7
-2
7
7
Ambiguous
Ambiguous
15

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

[入力例]

0 1 2 3

1 1 2 1

1 3 4 5

0 3 4 6

1 3 4 5

0 2 3 6

1 3 1 5

[出力例]

Ambiguous

※AtCoderテストケースより

[入力例]

0 11 12 41

0 1 2 159

0 14 15 121

0 4 5 245

0 12 13 157

0 9 10 176

0 6 7 170

0 2 3 123

0 7 8 167

0 3 4 159

1 12 11 33

0 10 11 116

0 8 9 161

1 9 12 68

1 12 12 33

1 7 12 74

0 5 6 290

1 8 9 93

0 13 14 127

1 10 12 108

1 14 1 3

1 13 8 124

1 12 11 33

1 12 10 33

1 5 15 194

[出力例]

144

108

118

※AtCoderテストケースより

[入力例]

0 1 2 5

1 1 2 0

1 3 2 7

0 3 4 5

1 3 5 8

1 4 3 7

0 4 5 6

1 5 3 12

1 4 3 6

0 6 7 9

1 6 7 8

1 7 5 3

[出力例]

Ambiguous

-2

-1

Ambiguous

[入力例]

0 1 2 2

1 1 2 5

1 1 3 7

0 2 3 7

1 3 1 5

1 5 3 2

0 4 5 6

1 4 5 3

0 6 7 4

0 7 8 8

1 6 8 7

1 7 8 5

1 7 6 2

0 9 10 10

1 9 6 5

1 10 9 3

0 11 12 3

0 12 13 12

1 12 11 5

1 12 13 5

1 13 11 16

0 14 15 11

1 15 10 8

1 14 4 15

1 1 3 10

[出力例]

-3

Ambiguous

-2

Ambiguous

■参照サイト
068 – Paired Information
問題068 (Paired Information) 解説
 Union-Find木

2021年9月2日2021年9月2日

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

C++の練習を兼ねて, 競プロ典型 90 問の問題072 (Loop Railway Plan) を解いてみた.

■感想.
1. 問題072は, 実装方針が見えなかったので, (問題072 (Loop Railway Plan) 解説プログラム) を参考に実装したところ, AC版に到達出来た.
2. 深さ優先探索(応用版, Backtracking) の復習が出来たので, 非常に, 良かったと思う.
但し, Backtracking について, 本質的な部分が, 理解できてないため, 引き続き, 今後の課題になると思う.
3. 手強い問題が非常に多い気もするけど, 時間を見つけて, 引き続き, 取り組んでいきたいと思う.

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

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

// 解答不能.
// https://github.com/E869120/kyopro_educational_90/blob/main/sol/072.cpp
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vs = vector<string>;
#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
constexpr int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

int main(){
    
    // 1. 入力情報.
    int H, W;
    scanf("%d %d", &H, &W);
    vs board;
    rep(i, H){
        char c[22];
        scanf("%s", c);
        string s(c);
        board.pb(s);
    }
    
    // 2. dfs(Backtracking).
    // https://ja.wikipedia.org/wiki/深さ優先探索
    int ans = -1;
    bool memo[20][20];
    rep(i, 20) rep(j, 20) memo[i][j] = false;
    auto dfs = [&](auto&& self, int sx, int sy, int px, int py) -> int{
        // 2-1. 終了条件.
        if(sx == px && sy == py && memo[px][py]) return 0;
        
        // 2-2. 訪問したことを記録.
        memo[px][py] = true;
        
        // 2-3. dfs.
        // -> ret の 初期値は, どのくらい小さくするかは, よく理解出来てない.
        int ret = -111;
        rep(i, 4){
            // 隣接マスを用意.
            int nx = px + dx[i];
            int ny = py + dy[i];
            
            // 隣接マスが, 到達不可能な場合(山とか).
            if(nx < 0 || ny < 0 || nx >= H || ny >= W || board[nx][ny] == '#') continue;
            
            // 隣接マスが, 開始頂点でないが, 訪問済みの場合.
            if((sx != nx || sy != ny) && memo[nx][ny]) continue;
            
            // 移動したマス数を取得.
            int v = self(self, sx, sy, nx, ny);
            
            // 最大値更新.
            ret = max(ret, v + 1);
        }
        
        // 2-4. 訪問してない状態に戻す.
        memo[px][py] = false;
        
        // 2-5. 処理終了.
        return ret;
    };
    
    // 3. 全探索.
    rep(x, H) rep(y, W) ans = max(ans, dfs(dfs, x, y, x, y));
    
    // 4. 鉄道路線が通るマスの数が, 3マス以下の場合(鉄道路線が無い場合).
    if(ans <= 3) ans = -1;
    
    // 5. 出力.
    printf("%d\n", ans);
    return 0;
    
}

// 解答不能.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vs = vector<string>;

#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

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

int main(){

// 1. 入力情報.

int H, W;

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

vs board;

rep(i, H){

char c[22];

scanf("%s", c);

string s(c);

board.pb(s);

}

// 2. dfs(Backtracking).

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

int ans = -1;

bool memo[20][20];

rep(i, 20) rep(j, 20) memo[i][j] = false;

auto dfs = [&](auto&& self, int sx, int sy, int px, int py) -> int{

// 2-1. 終了条件.

if(sx == px && sy == py && memo[px][py]) return 0;

// 2-2. 訪問したことを記録.

memo[px][py] = true;

// 2-3. dfs.

// -> ret の初期値は, どのくらい小さくするかは, よく理解出来てない.

int ret = -111;

rep(i, 4){

// 隣接マスを用意.

int nx = px + dx[i];

int ny = py + dy[i];

// 隣接マスが, 到達不可能な場合(山とか).

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

// 隣接マスが, 開始頂点でないが, 訪問済みの場合.

if((sx != nx || sy != ny) && memo[nx][ny]) continue;

// 移動したマス数を取得.

int v = self(self, sx, sy, nx, ny);

// 最大値更新.

ret = max(ret, v + 1);

}

// 2-4. 訪問してない状態に戻す.

memo[px][py] = false;

// 2-5. 処理終了.

return ret;

};

// 3. 全探索.

rep(x, H) rep(y, W) ans = max(ans, dfs(dfs, x, y, x, y));

// 4. 鉄道路線が通るマスの数が, 3マス以下の場合(鉄道路線が無い場合).

if(ans <= 3) ans = -1;

// 5. 出力.

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

return 0;

}

[入力例]
3 3
...
.#.
...

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

[入力例]
1 6
......

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

[入力例]
4 4
....
#...
....
...#

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

[入力例]
5 5
.....
.#...
.....
...#.
.#...

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

-> 以下のような経路で, 20 と 分かる.
@@@@@
@#@@@
@.@@@
@@@#@
.#@@@

[入力例]
6 6
.....#
.#....
......
...#.#
.#....
......

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

-> 以下のような経路で, 30 と 分かる.
@@@@@#
@#@@@@
@@@.@@
@@@#@#
@#@@@@
@@@@@@

[入力例]

3 3

...

.#.

...

[出力例]

※AtCoderテストケースより

[入力例]

1 6

......

[出力例]

-1

※AtCoderテストケースより

[入力例]

4 4

....

#...

....

...#

[出力例]

※AtCoderテストケースより

[入力例]

5 5

.....

.#...

.....

...#.

.#...

[出力例]

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

-> 以下のような経路で, 20 と分かる.

@@@@@

@#@@@

@.@@@

@@@#@

.#@@@

[入力例]

6 6

.....#

.#....

......

...#.#

.#....

......

[出力例]

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

-> 以下のような経路で, 30 と分かる.

@@@@@#

@#@@@@

@@@.@@

@@@#@#

@#@@@@

@@@@@@

■参照サイト
072 – Loop Railway Plan
問題072 (Loop Railway Plan) 解説
 問題072 (Loop Railway Plan) 解説プログラム

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) 解説

カテゴリー: C++

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

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

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

C++の練習を兼ねて, 競プロ典型 90 問の問題073 (We Need Both a and b) を解いてみた.

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

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

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

C++の練習を兼ねて, 競プロ典型 90 問の問題072 (Loop Railway Plan) を解いてみた.

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

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

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

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

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

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

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

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

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

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

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

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

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

C++の練習を兼ねて, 競プロ典型 90 問 の 問題073 (We Need Both a and b) を解いてみた.

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

C++の練習を兼ねて, 競プロ典型 90 問 の 問題072 (Loop Railway Plan) を解いてみた.

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 問の問題081 (Friendly Group) を解いてみた.

C++の練習を兼ねて, 競プロ典型 90 問の問題073 (We Need Both a and b) を解いてみた.

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

C++の練習を兼ねて, 競プロ典型 90 問の問題072 (Loop Railway Plan) を解いてみた.

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) を解いてみた.