C++ | 個人用メモ帳

2022年8月27日

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

C++の練習を兼ねて, AtCoder Regular Contest 046 の問題C (合コン大作戦) を解いてみた.

■感想.
1. 問題Cは, 方針が見えなかったので, 解説を参考にして, AC版に到達できたと思う.
2. 実装に苦労したものの, 個人的には, 尺取り法と std::multiset の復習が出来たので, 非常に良かったと思う.
3. B[i] は, 降順ソートが必要に見えたため, 実装に反映している(※).
※男性の年収情報 A[i] を固定した場合に, 女性の希望年収情報 D[i] 以上となる女性の年収情報 C[i] を, すべて, 多重集合に保存し, 男性の希望年収情報 B[i] を大きい順に, チェックしていくイメージの実装としている.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://www.slideshare.net/chokudai/arc046
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;
using vp = vector<P>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define a first
#define b second
#define all(x) x.begin(), x.end()

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    vp mv(N), fv(M);
    rep(i, N){
        scanf("%d %d", &mv[i].a, &mv[i].b);
        mv[i].b *= -1; // B[i] は, 降順sort するため.
    }
    rep(i, M) scanf("%d %d", &fv[i].b, &fv[i].a);
    
    // 2. sort.
    sort(all(mv));
    sort(all(fv));
    
    // 3. 尺取り法(解説通り).
    multiset<int> mst;
    int ans = 0, j = 0;
    rep(i, N){
        // 年収が, D[j]以上 の 場合.
        while(j < M && fv[j].a <= mv[i].a){
            // 女性を追加.
            mst.insert(fv[j].b);
            
            // 次へ.
            ++j;
        }
            
        // 多重集合に, B[i]以上があるか？
        auto b = mst.lower_bound(-mv[i].b);
        
        // 存在した場合.
        if(b != mst.end()){
            // カップル誕生.
            auto itr = mst.find(*b);
            mst.erase(itr);
            
            // カップル数 を インクリメント.
            ++ans;
        }
    }
    
    // 4. 出力.
    printf("%d\n", ans);
    return 0;
    
}

// 解き直し.

// https://www.slideshare.net/chokudai/arc046

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using P = pair<int, int>;

using vp = vector<P>;

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

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

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

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

#define a first

#define b second

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

int main(){

// 1. 入力情報.

int N, M;

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

vp mv(N), fv(M);

rep(i, N){

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

mv[i].b *= -1; // B[i] は, 降順sort するため.

}

rep(i, M) scanf("%d %d", &fv[i].b, &fv[i].a);

// 2. sort.

sort(all(mv));

sort(all(fv));

// 3. 尺取り法(解説通り).

multiset<int> mst;

int ans = 0, j = 0;

rep(i, N){

// 年収が, D[j]以上の場合.

while(j < M && fv[j].a <= mv[i].a){

// 女性を追加.

mst.insert(fv[j].b);

// 次へ.

++j;

}

// 多重集合に, B[i]以上があるか？

auto b = mst.lower_bound(-mv[i].b);

// 存在した場合.

if(b != mst.end()){

// カップル誕生.

auto itr = mst.find(*b);

mst.erase(itr);

// カップル数をインクリメント.

++ans;

}

// 4. 出力.

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

return 0;

}

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

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

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

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

[入力例]
5 1
1 1
1 1
1 1
1 1
1 1
1 1

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

[入力例]
1 1
1 1
1 2

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

[入力例]
5 7
73 8
118 101
61 121
104 17
105 17
26 97
7 45
57 69
113 61
84 10
72 62
8 5

[出力例]
4

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

[出力例]
4

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

[出力例]
5

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

[出力例]
21

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

[出力例]
50

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

[入力例]

3 3

3 5

2 4

4 5

3 1

6 2

5 3

[出力例]

※AtCoderのテストケースより

[入力例]

3 4

4 1

2 1

7 1

5 3

12 1

1 10

8 5

[出力例]

※AtCoderのテストケースより

[入力例]

5 1

1 1

[出力例]

※AtCoderのテストケースより

[入力例]

1 1

1 2

[出力例]

※AtCoderのテストケースより

[入力例]

5 7

73 8

118 101

61 121

104 17

105 17

26 97

7 45

57 69

113 61

84 10

72 62

8 5

[出力例]

[入力例]

7 6

5 3

6 4

2 3

7 6

4 3

5 2

6 7

2 6

1 3

3 4

4 2

5 3

2 5

[出力例]

[入力例]

10 8

6 3

10 11

12 5

4 13

3 3

7 10

5 13

9 2

9 12

1 9

4 2

7 1

11 9

4 6

2 13

3 2

6 5

9 11

[出力例]

[入力例]

30 25

14 17

12 15

9 12

5 10

4 2

2 2

17 7

15 6

13 12

8 11

16 13

13 17

13 8

8 5

12 2

1 12

14 16

9 16

11 9

10 9

14 1

7 15

17 8

1 6

17 16

15 14

6 11

4 15

17 11

1 3

17 15

14 10

5 16

13 6

3 2

17 1

5 9

12 7

15 10

9 9

2 3

12 11

11 4

4 5

15 15

11 9

3 6

6 16

10 8

12 5

7 2

11 9

4 6

8 8

12 11

[出力例]

[入力例]

55 65

32 26

11 18

9 28

42 37

16 3

10 33

10 6

32 16

42 3

26 2

8 21

24 9

48 13

35 5

38 39

49 34

37 18

32 22

25 8

5 14

1 10

24 25

33 45

32 13

21 20

24 44

23 17

46 24

3 47

23 27

6 21

2 7

24 12

37 14

17 1

27 33

25 35

5 9

1 12

38 44

9 33

28 30

12 39

49 29

31 25

42 5

41 45

42 29

39 45

15 38

45 33

45 20

46 43

28 44

43 17

44 23

32 5

41 41

24 4

15 42

46 10

11 50

12 27

8 6

40 18

49 13

25 48

6 44

25 22

37 48

6 3

12 43

50 31

43 16

39 9

19 50

50 15

15 13

25 29

32 9

21 28

14 34

16 46

5 9

46 36

40 50

5 11

5 6

31 6

34 29

3 6

45 47

30 5

36 2

32 12

23 36

1 24

7 6

28 19

37 5

40 16

50 7

2 24

13 8

43 28

22 44

50 6

29 11

29 27

6 5

32 20

1 18

44 18

10 37

47 18

19 50

5 30

27 32

23 5

6 49

[出力例]

■参照サイト
AtCoder Regular Contest 046

2022年8月25日

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

C++の練習を兼ねて, AtCoder Regular Contest 146 の問題C (Even XOR) を解いてみた.

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

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

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

// 解き直し.
// https://atcoder.jp/contests/arc146/editorial/4635
// 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;
const int MAX = 202020;
LL FAC[MAX], INV[MAX], dp[MAX], mPow2[MAX];

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

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    
    // 2. 事前計算.
    FAC[0] = mPow2[0] = 1;
    rep(i, MAX){
        FAC[i + 1] = (LL)(i + 1) * FAC[i] % MOD;
        INV[i + 1] = mPow(i + 1, MOD - 2);
        mPow2[i + 1] = (mPow2[i] << 1) % MOD; 
    }
    
    // 3. 初期化.
    dp[0] = 1;
    dp[1] = dp[0] * mPow2[N];
    
    // 4. dp更新.
    repx(i, 2, N + 2){
        dp[i] = dp[i - 1] * ((mPow2[N] + MOD - mPow2[i - 2]) % MOD);
        dp[i] %= MOD;
        dp[i] *= INV[i];
        dp[i] %= MOD;
    }
    
    // 5. 集計.
    LL ans = 0;
    rep(i, N + 2) ans = (ans + dp[i]) % MOD;
    
    // 6. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc146/editorial/4635

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

const int MAX = 202020;

LL FAC[MAX], INV[MAX], dp[MAX], mPow2[MAX];

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

}

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

// 2. 事前計算.

FAC[0] = mPow2[0] = 1;

rep(i, MAX){

FAC[i + 1] = (LL)(i + 1) * FAC[i] % MOD;

INV[i + 1] = mPow(i + 1, MOD - 2);

mPow2[i + 1] = (mPow2[i] << 1) % MOD;

}

// 3. 初期化.

dp[0] = 1;

dp[1] = dp[0] * mPow2[N];

// 4. dp更新.

repx(i, 2, N + 2){

dp[i] = dp[i - 1] * ((mPow2[N] + MOD - mPow2[i - 2]) % MOD);

dp[i] %= MOD;

dp[i] *= INV[i];

dp[i] %= MOD;

}

// 5. 集計.

LL ans = 0;

rep(i, N + 2) ans = (ans + dp[i]) % MOD;

// 6. 出力.

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

return 0;

}

[入力例]
2

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

[入力例]
146

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

[入力例]
1

[出力例]
4

[入力例]
3

[出力例]
149

[入力例]
4

[出力例]
5065

[入力例]
5

[出力例]
651281

[入力例]
6

[出力例]
319648289

[入力例]
2022

[出力例]
789447177

[入力例]
200000

[出力例]
583209323

[入力例]

[出力例]

※AtCoderのテストケースより

[入力例]

146

[出力例]

743874490

※AtCoderのテストケースより

[入力例]

[出力例]

[入力例]

[出力例]

149

[入力例]

[出力例]

5065

[入力例]

[出力例]

651281

[入力例]

[出力例]

319648289

[入力例]

2022

[出力例]

789447177

[入力例]

200000

[出力例]

583209323

■参照サイト
AtCoder Regular Contest 146

2022年8月23日

C++ の動作確認をしてみた（７９４）

C++の練習を兼ねて, AtCoder Regular Contest 146 の問題A (Three Cards) ～問題B (Plus and AND) を解いてみた.

■感想.
1. 問題Bは, 方針が見えなかったので, 解説を参考にして, AC版に到達できたと思う.
2. 個人的には, 問題B で, 二分探索(応用版, 集合を考慮) の復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

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

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    vvl v(6);
    rep(i, N){
        int a;
        scanf("%d", &a);
        if(a < 10)          v[0].pb(a);
        else if(a < 100)    v[1].pb(a);
        else if(a < 1000)   v[2].pb(a);
        else if(a < 10000)  v[3].pb(a);
        else if(a < 100000) v[4].pb(a);
        else                v[5].pb(a);
    }
    
    // 2. sort.
    rep(i, 6){
        sort(all(v[i]));
        reverse(all(v[i]));
    }
    
    // 3. 整数を, 最大 18個 選ぶ.
    vl t;
    rep(i, 6) rep(j, min(3, (int)v[i].size())) t.pb(v[i][j]);
    
    // 4. 整数(3個)から作成した整数の最大値は？
    LL ans = 0;
    int n = t.size();
    rep(i, n){
        rep(j, n){
            rep(k, n){
                if(i != j && j != k && k != i){
                    string s = to_string(t[i]);
                    s += to_string(t[j]);
                    s += to_string(t[k]);
                    ans = max(ans, stoll(s));
                }
            }
        }
    }
    
    // 5. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vl = vector<LL>;

using vvl = vector<vl>;

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

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

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

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

#define pb push_back

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

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

vvl v(6);

rep(i, N){

int a;

scanf("%d", &a);

if(a < 10) v[0].pb(a);

else if(a < 100) v[1].pb(a);

else if(a < 1000) v[2].pb(a);

else if(a < 10000) v[3].pb(a);

else if(a < 100000) v[4].pb(a);

else v[5].pb(a);

}

// 2. sort.

rep(i, 6){

sort(all(v[i]));

reverse(all(v[i]));

}

// 3. 整数を, 最大 18個選ぶ.

vl t;

rep(i, 6) rep(j, min(3, (int)v[i].size())) t.pb(v[i][j]);

// 4. 整数(3個)から作成した整数の最大値は？

LL ans = 0;

int n = t.size();

rep(i, n){

rep(j, n){

rep(k, n){

if(i != j && j != k && k != i){

string s = to_string(t[i]);

s += to_string(t[j]);

s += to_string(t[k]);

ans = max(ans, stoll(s));

}

// 5. 出力.

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

return 0;

}

[入力例]
5
1 4 3 5 8

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

[入力例]
8
813 921 481 282 120 900 555 409

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

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

[出力例]
977711


[入力例]
20
12345 487 8080 123 7070 220 3763 1665 5164 1638 4271 1302 3184 241 630 12 1861 3565 987 999

[出力例]
8080707012345

[入力例]

1 4 3 5 8

[出力例]

854

※AtCoderのテストケースより

[入力例]

813 921 481 282 120 900 555 409

[出力例]

921900813

※AtCoderのテストケースより

[入力例]

11 8 9 5 6 7 8 777 2 3

[出力例]

977711

[入力例]

12345 487 8080 123 7070 220 3763 1665 5164 1638 4271 1302 3184 241 630 12 1861 3565 987 999

[出力例]

8080707012345

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

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

int main(){
    
    // 1. 入力情報.
    int N, M, K;
    scanf("%d %d %d", &N, &M, &K);
    rep(i, N) scanf("%lld", &a[i]);
    
    // 2. 評価関数.
    auto f = [&](LL X) -> bool {
        // 2-1. X の 上位集合に含まれる最小の整数 b[i].
        vl v;
        rep(i, N){
            LL b = X;
            repr(j, 31, 0){
                // X の jbit目 が 1.
                LL bit = 1LL << j;
                if(b & bit) continue;
                
                // X の jbit目 が 0.
                LL t = b | (bit - 1);
                if(t < a[i]) b |= bit;
            }
            
            // 差分.
            v.pb(b - a[i]);
        }
        
        // 2-2. sort.
        sort(all(v));
        
        // 2-3. (K要素)操作回数.
        LL d = 0;
        rep(i, K) d += v[i];
        
        // 2-5. 判定結果.
        return (d > (LL)M);
    };
    
    // 3. 二分探索で確認してみる.
    LL l = 0, h = (1LL << 32) + 1LL;
    while(l + 1 < h){
        LL m = (h + l) >> 1;
        if(f(m)) h = m;
        else     l = m;
    }
    
    // 4. 出力.
    printf("%lld\n", l);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc146/editorial/4634

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vl = vector<LL>;

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

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

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

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

#define pb push_back

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

LL a[202020];

int main(){

// 1. 入力情報.

int N, M, K;

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

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

// 2. 評価関数.

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

// 2-1. X の上位集合に含まれる最小の整数 b[i].

vl v;

rep(i, N){

LL b = X;

repr(j, 31, 0){

// X の jbit目が 1.

LL bit = 1LL << j;

if(b & bit) continue;

// X の jbit目が 0.

LL t = b | (bit - 1);

if(t < a[i]) b |= bit;

}

// 差分.

v.pb(b - a[i]);

}

// 2-2. sort.

sort(all(v));

// 2-3. (K要素)操作回数.

LL d = 0;

rep(i, K) d += v[i];

// 2-5. 判定結果.

return (d > (LL)M);

};

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

LL l = 0, h = (1LL << 32) + 1LL;

while(l + 1 < h){

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

if(f(m)) h = m;

else l = m;

}

// 4. 出力.

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

return 0;

}

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

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

[入力例]
5 345 3
111 192 421 390 229

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

[入力例]
7 18 5
3 4 8 11 12 17 23

[出力例]
16

[入力例]
10 50 7
80 100 92 34 115 59 103 107 112 101

[出力例]
106

[入力例]
50 20220823 17
106255686 84374702 102511172 86199041 20471611 20311296 25895741 120233844 66769765 116404889 86089818 109694206 50780701 58043255 91938819 51432612 80712996 95142878 41522855 34035448 59244373 58566447 45185189 47990981 116692991 68140874 82529468 98511521 50416527 75089014 57540828 37157784 75212891 64977902 31486499 10838381 13836513 35242992 48366115 12313711 35495113 92933260 52126220 32483328 99177008 55365265 108962428 69874519 16053102 55722329

[出力例]
72576026

[入力例]
500 123456789 111
680 832 391 2592 749 3698 5432 649 2973 2499 4400 3107 378 1875 2858 3135 3233 3088 1539 4483 292 2256 43 3530 4733 1043 2671 2946 2906 831 5167 4084 3297 2991 2092 5247 3232 566 2818 4460 3748 1728 2182 3735 175 49 384 330 3731 5155 2727 2740 4824 2638 4893 2006 759 3428 4417 28 837 712 698 52 1032 4380 778 2632 1284 4571 119 5415 2338 671 4897 3129 3819 988 171 5457 3724 1806 2536 212 4444 3564 5124 2434 3372 699 1557 2015 1893 1329 2473 2123 1051 211 3316 4260 4507 2841 2131 1701 2042 2903 1865 3026 2537 2366 4223 4718 2520 5479 3421 2271 2797 5087 2515 1364 1208 3269 1571 2583 2378 1379 2196 5247 3440 3115 3986 2084 3964 2054 3843 639 4010 4303 4769 4615 2755 4114 2330 2901 1816 5554 875 5121 654 3069 2624 1121 3296 1622 3882 2166 3230 3666 4968 4488 900 103 998 4527 5020 3320 5087 5284 880 4634 3351 2915 3460 2519 506 1383 1037 1074 108 5279 1575 4675 2074 1704 731 3293 2269 5169 5253 3887 4754 3919 5225 1019 3616 4083 393 4651 31 1364 3206 2343 5474 4904 4538 3121 3732 5200 700 57 4168 533 2286 615 4986 4238 1983 956 3266 5314 3133 1060 2150 1783 780 1206 1122 4424 2431 3900 2456 621 1449 1293 4326 3316 1267 2879 2375 3294 5064 3148 844 2211 5042 2959 1514 480 3418 2831 3601 948 4114 4042 3076 4022 159 3060 1570 697 3182 1746 4473 3548 1599 4910 300 14 1537 3014 95 4629 4240 1027 4785 3510 1461 4875 2042 4740 3801 3127 1581 4747 3386 2181 2985 1322 1378 4341 4516 218 442 3795 2946 1967 1536 513 1415 475 5509 2023 968 162 2344 1061 710 2823 4978 3573 2838 1485 2429 2169 5549 2598 3511 3115 319 874 3594 2284 991 3339 5186 2285 3321 2021 2933 3121 3143 2873 4050 1613 2136 3085 2051 3736 5195 2081 4454 1644 1837 616 2332 1141 374 597 2865 4596 1971 2263 2823 1430 4658 3672 1565 1845 908 3970 1871 5115 1718 497 4440 88 4024 5136 3260 2716 4313 1285 4984 1385 4443 5164 1958 4575 2518 5431 1445 1536 4560 495 636 5002 302 3208 4775 2729 535 4576 121 662 97 696 4157 1167 4022 4796 4541 4236 2431 2102 2901 2763 5474 5211 1508 4290 1667 4460 4659 3899 3880 2462 2895 577 4882 1859 3844 2211 837 1696 4273 5210 4562 1716 29 2078 105 1349 3943 4370 1787 4968 260 1423 1197 2524 1027 5343 5226 132 1731 4900 4942 3422 4667 1625 3437 2107 5438 2513 904 486 2420 4224 1537 3514 1541 925 2920 736 5406 1952 3007 3333 290 4163 3085 2850 4015 4045 5209 5050 1652 340 2459 3461 1745 909 4630 868 3815 4233 2138 5494 3326 4160 1784 2108 3693 447 976 2192 1535 1657 184 5388

[出力例]
1117090

[入力例]

4 8 2

1 2 4 8

[出力例]

※AtCoderテストケースより

[入力例]

5 345 3

111 192 421 390 229

[出力例]

461

※AtCoderテストケースより

[入力例]

7 18 5

3 4 8 11 12 17 23

[出力例]

[入力例]

10 50 7

80 100 92 34 115 59 103 107 112 101

[出力例]

106

[入力例]

50 20220823 17

106255686 84374702 102511172 86199041 20471611 20311296 25895741 120233844 66769765 116404889 86089818 109694206 50780701 58043255 91938819 51432612 80712996 95142878 41522855 34035448 59244373 58566447 45185189 47990981 116692991 68140874 82529468 98511521 50416527 75089014 57540828 37157784 75212891 64977902 31486499 10838381 13836513 35242992 48366115 12313711 35495113 92933260 52126220 32483328 99177008 55365265 108962428 69874519 16053102 55722329

[出力例]

72576026

[入力例]

500 123456789 111

680 832 391 2592 749 3698 5432 649 2973 2499 4400 3107 378 1875 2858 3135 3233 3088 1539 4483 292 2256 43 3530 4733 1043 2671 2946 2906 831 5167 4084 3297 2991 2092 5247 3232 566 2818 4460 3748 1728 2182 3735 175 49 384 330 3731 5155 2727 2740 4824 2638 4893 2006 759 3428 4417 28 837 712 698 52 1032 4380 778 2632 1284 4571 119 5415 2338 671 4897 3129 3819 988 171 5457 3724 1806 2536 212 4444 3564 5124 2434 3372 699 1557 2015 1893 1329 2473 2123 1051 211 3316 4260 4507 2841 2131 1701 2042 2903 1865 3026 2537 2366 4223 4718 2520 5479 3421 2271 2797 5087 2515 1364 1208 3269 1571 2583 2378 1379 2196 5247 3440 3115 3986 2084 3964 2054 3843 639 4010 4303 4769 4615 2755 4114 2330 2901 1816 5554 875 5121 654 3069 2624 1121 3296 1622 3882 2166 3230 3666 4968 4488 900 103 998 4527 5020 3320 5087 5284 880 4634 3351 2915 3460 2519 506 1383 1037 1074 108 5279 1575 4675 2074 1704 731 3293 2269 5169 5253 3887 4754 3919 5225 1019 3616 4083 393 4651 31 1364 3206 2343 5474 4904 4538 3121 3732 5200 700 57 4168 533 2286 615 4986 4238 1983 956 3266 5314 3133 1060 2150 1783 780 1206 1122 4424 2431 3900 2456 621 1449 1293 4326 3316 1267 2879 2375 3294 5064 3148 844 2211 5042 2959 1514 480 3418 2831 3601 948 4114 4042 3076 4022 159 3060 1570 697 3182 1746 4473 3548 1599 4910 300 14 1537 3014 95 4629 4240 1027 4785 3510 1461 4875 2042 4740 3801 3127 1581 4747 3386 2181 2985 1322 1378 4341 4516 218 442 3795 2946 1967 1536 513 1415 475 5509 2023 968 162 2344 1061 710 2823 4978 3573 2838 1485 2429 2169 5549 2598 3511 3115 319 874 3594 2284 991 3339 5186 2285 3321 2021 2933 3121 3143 2873 4050 1613 2136 3085 2051 3736 5195 2081 4454 1644 1837 616 2332 1141 374 597 2865 4596 1971 2263 2823 1430 4658 3672 1565 1845 908 3970 1871 5115 1718 497 4440 88 4024 5136 3260 2716 4313 1285 4984 1385 4443 5164 1958 4575 2518 5431 1445 1536 4560 495 636 5002 302 3208 4775 2729 535 4576 121 662 97 696 4157 1167 4022 4796 4541 4236 2431 2102 2901 2763 5474 5211 1508 4290 1667 4460 4659 3899 3880 2462 2895 577 4882 1859 3844 2211 837 1696 4273 5210 4562 1716 29 2078 105 1349 3943 4370 1787 4968 260 1423 1197 2524 1027 5343 5226 132 1731 4900 4942 3422 4667 1625 3437 2107 5438 2513 904 486 2420 4224 1537 3514 1541 925 2920 736 5406 1952 3007 3333 290 4163 3085 2850 4015 4045 5209 5050 1652 340 2459 3461 1745 909 4630 868 3815 4233 2138 5494 3326 4160 1784 2108 3693 447 976 2192 1535 1657 184 5388

[出力例]

1117090

■参照サイト
AtCoder Regular Contest 146

2022年8月21日

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

C++の練習を兼ねて, AtCoder Beginner Contest 253 の問題E (Distance Sequence) を解いてみた.

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

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

■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--)
const LL MOD = 998244353;
LL dp[1010][5050], dpCum[5050];

int main(){
    
    // 1. 入力情報.
    int N, M, K;
    scanf("%d %d %d", &N, &M, &K);
    
    // 2. 初期化.
    repx(j, 1, M + 1) dp[1][j] = 1;
    
    // 3. dp更新.
    repx(i, 2, N + 1){
        // 前回分更新(累積和).
        repx(j, 1, M + 1){
            dpCum[j] = dpCum[j - 1] + dp[i - 1][j];
            dpCum[j] %= MOD;
        }
        dpCum[M + 1] = dpCum[M];
        
        // 今回分更新.
        repx(j, 1, M + 1){
            // 下限(区間 [1, j - K]), 上限(区間 [j + K, M]).
            int l = max(0, j - K);
            int r = min(M + 1, j + K);
            
            // 累積和から設定.
            dp[i][j] += dpCum[l];
            dp[i][j] %= MOD;
            dp[i][j] += dpCum[M + 1] + MOD - dpCum[r - 1];
            dp[i][j] %= MOD;
            
            // l, r が 等しい場合(K == 0 の パターン).
            // -> 重複分を除外.
            if(l == r){
                dp[i][j] += MOD;
                dp[i][j] -= dpCum[j];
                dp[i][j] += dpCum[j - 1];
                dp[i][j] %= MOD;
            }
        }
    }
    
    // 4. 集計.
    LL ans = 0;
    repx(j, 1, M + 1){
        ans += dp[N][j];
        ans %= MOD;
    }
    
    // 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--)

const LL MOD = 998244353;

LL dp[1010][5050], dpCum[5050];

int main(){

// 1. 入力情報.

int N, M, K;

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

// 2. 初期化.

repx(j, 1, M + 1) dp[1][j] = 1;

// 3. dp更新.

repx(i, 2, N + 1){

// 前回分更新(累積和).

repx(j, 1, M + 1){

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

dpCum[j] %= MOD;

}

dpCum[M + 1] = dpCum[M];

// 今回分更新.

repx(j, 1, M + 1){

// 下限(区間 [1, j - K]), 上限(区間 [j + K, M]).

int l = max(0, j - K);

int r = min(M + 1, j + K);

// 累積和から設定.

dp[i][j] += dpCum[l];

dp[i][j] %= MOD;

dp[i][j] += dpCum[M + 1] + MOD - dpCum[r - 1];

dp[i][j] %= MOD;

// l, r が等しい場合(K == 0 のパターン).

// -> 重複分を除外.

if(l == r){

dp[i][j] += MOD;

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

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

dp[i][j] %= MOD;

}

// 4. 集計.

LL ans = 0;

repx(j, 1, M + 1){

ans += dp[N][j];

ans %= MOD;

}

// 5. 出力.

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

return 0;

}

[入力例]
2 3 1

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

[入力例]
3 3 2

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

[入力例]
100 1000 500

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

[入力例]
2 1 0

[出力例]
1

[入力例]
5 2 0

[出力例]
32

[入力例]
3 5 2

[出力例]
30

[入力例]
6 5 2

[出力例]
456

[入力例]
7 5 3

[出力例]
68

[入力例]
20 22 5

[出力例]
709598492

[入力例]
1000 2022 821

[出力例]
486966154

[入力例]
1000 5000 3210

[出力例]
393738463

[入力例]

2 3 1

[出力例]

※AtCoderテストケースより

[入力例]

3 3 2

[出力例]

※AtCoderテストケースより

[入力例]

100 1000 500

[出力例]

657064711

※AtCoderテストケースより

[入力例]

2 1 0

[出力例]

[入力例]

5 2 0

[出力例]

[入力例]

3 5 2

[出力例]

[入力例]

6 5 2

[出力例]

456

[入力例]

7 5 3

[出力例]

[入力例]

20 22 5

[出力例]

709598492

[入力例]

1000 2022 821

[出力例]

486966154

[入力例]

1000 5000 3210

[出力例]

393738463

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

2022年8月20日

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

C++の練習を兼ねて, AtCoder Beginner Contest 264 の問題E (Blackout 2) を解いてみた.

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

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

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using P = pair<int, int>;
using vp = vector<P>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
#define a first
#define b second
int memo[505050], ans[505050];

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

int main(){
    
    // 1. 入力情報.
    int N, M, E;
    scanf("%d %d %d", &N, &M, &E);
    vp es;
    rep(i, E){
        int u, v;
        scanf("%d %d", &u, &v);
        es.pb({u, v});
    }
    int Q;
    scanf("%d", &Q);
    vi xs;
    rep(i, Q){
        int x;
        scanf("%d", &x);
        --x;
        xs.pb(x);
        ++memo[x];
    }
    
    // 2. 最終状態.
    // 都市:   頂点 1 ～ N.
    // 発電所: 頂点 N + 1 ～ N + M.
    // -> 頂点 0 に 発電所 を 集約.
    UnionFind uf(N + 2);
    rep(i, E){
        // 電線番号 i が, 最後まで, 残っているか？
        if(!memo[i]){
            // 都市 or 発電所.
            int a = es[i].a;
            int b = es[i].b;
            
            // 都市 - 都市.
            if(a <= N && b <= N) uf.unite(a, b);
            
            // 都市 - 発電所.
            if(a <= N && b > N) uf.unite(a, 0);
            
            // 発電所 - 発電所(何もしない).
        }
    }
    
    // 3. 初期化.
    // -> 最終状態のみ.
    ans[Q] = uf.size(0);
    
    // 4. 逆算.
    repr(i, Q - 1, 0){
        // 電線番号 j.
        int j = xs[i];
        
        // 都市 or 発電所.
        int a = es[j].a;
        int b = es[j].b;
        
        // 都市 - 都市.
        if(a <= N && b <= N){
            uf.unite(a, b);
            ans[i] = uf.size(0);
        }
        
        // 都市 - 発電所.
        if(a <= N && b > N){
            uf.unite(a, 0);
            ans[i] = uf.size(0);
        }
        
        // 発電所 - 発電所(変化なし).
        if(a > N) ans[i] = uf.size(0);
    }
    
    // 5. 出力.
    repx(i, 1, Q + 1) printf("%d\n", ans[i] - 1);
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

using P = pair<int, int>;

using vp = vector<P>;

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

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

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

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

#define pb push_back

#define a first

#define b second

int memo[505050], ans[505050];

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

// UnionFind

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

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

// -> 一部改変.

struct UnionFind{

vi d;

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

int find(int x){

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

}

bool unite(int x, int y){

x = find(x);

y = find(y);

if(x == y) return false;

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

d[x] += d[y];

d[y] = x;

return true;

}

bool same(int x, int y){

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

}

int size(int x){

return -d[find(x)];

}

};

int main(){

// 1. 入力情報.

int N, M, E;

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

vp es;

rep(i, E){

int u, v;

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

es.pb({u, v});

}

int Q;

scanf("%d", &Q);

vi xs;

rep(i, Q){

int x;

scanf("%d", &x);

--x;

xs.pb(x);

++memo[x];

}

// 2. 最終状態.

// 都市: 頂点 1 ～ N.

// 発電所: 頂点 N + 1 ～ N + M.

// -> 頂点 0 に発電所を集約.

UnionFind uf(N + 2);

rep(i, E){

// 電線番号 i が, 最後まで, 残っているか？

if(!memo[i]){

// 都市 or 発電所.

int a = es[i].a;

int b = es[i].b;

// 都市 - 都市.

if(a <= N && b <= N) uf.unite(a, b);

// 都市 - 発電所.

if(a <= N && b > N) uf.unite(a, 0);

// 発電所 - 発電所(何もしない).

}

// 3. 初期化.

// -> 最終状態のみ.

ans[Q] = uf.size(0);

// 4. 逆算.

repr(i, Q - 1, 0){

// 電線番号 j.

int j = xs[i];

// 都市 or 発電所.

int a = es[j].a;

int b = es[j].b;

// 都市 - 都市.

if(a <= N && b <= N){

uf.unite(a, b);

ans[i] = uf.size(0);

}

// 都市 - 発電所.

if(a <= N && b > N){

uf.unite(a, 0);

ans[i] = uf.size(0);

}

// 発電所 - 発電所(変化なし).

if(a > N) ans[i] = uf.size(0);

}

// 5. 出力.

repx(i, 1, Q + 1) printf("%d\n", ans[i] - 1);

return 0;

}

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

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

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

[出力例]
3
3
3
2
0

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

[出力例]
5
5
5
5
4
4
2
1

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

[出力例]
7
7
7
6
5
5
5
3
3
0

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

[入力例]

5 5 10

2 3

4 10

5 10

6 9

2 9

4 8

1 7

3 6

8 10

1 8

[出力例]

※AtCoderテストケースより

[入力例]

3 2 7

1 2

1 3

2 3

1 4

2 5

3 5

4 5

[出力例]

[入力例]

5 3 10

1 2

3 4

1 5

1 6

1 7

6 7

5 8

2 3

2 5

3 8

[出力例]

[入力例]

7 5 13

1 2

3 4

5 6

1 7

3 7

5 7

9 10

11 12

1 8

1 10

4 11

6 11

7 12

[出力例]

■参照サイト
freee プログラミングコンテスト2022（AtCoder Beginner Contest 264）
Union-Find木

2022年8月20日

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

C++の練習を兼ねて, AtCoder Beginner Contest 253 の問題C (Max – Min Query) ～問題D (FizzBuzz Sum Hard) を解いてみた.

■感想.
1. 問題Dは, 方針を間違えていた(A, B の積を考えていたが, 誤り)ので, 解説を参考に, ようやく, AC版に到達出来た.
2. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

■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--)
#define a first
#define b second

int main(){
    
    // 1. 入力情報.
    int Q;
    scanf("%d", &Q);
    
    // 2. クエリ回答.
    map<int, int> m;
    rep(i, Q){
        // 2-1. クエリ情報.
        int t;
        scanf("%d", &t);
        
        // 2-2. パターン 1.
        if(t == 1){
            int x;
            scanf("%d", &x);
            ++m[x];
        }
        
        // 2-3. パターン 2.
        if(t == 2){
            int x, c;
            scanf("%d %d", &x, &c);
            m[x] -= min(c, m[x]);
            if(!m[x]) m.erase(x);
        }
        
        // 2-4. パターン 3.
        if(t == 3){
            auto s = m.begin();
            auto e = m.end();
            --e;
            printf("%d\n", e->a - s->a);
        }
    }
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

#define a first

#define b second

int main(){

// 1. 入力情報.

int Q;

scanf("%d", &Q);

// 2. クエリ回答.

map<int, int> m;

rep(i, Q){

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

int t;

scanf("%d", &t);

// 2-2. パターン 1.

if(t == 1){

int x;

scanf("%d", &x);

++m[x];

}

// 2-3. パターン 2.

if(t == 2){

int x, c;

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

m[x] -= min(c, m[x]);

if(!m[x]) m.erase(x);

}

// 2-4. パターン 3.

if(t == 3){

auto s = m.begin();

auto e = m.end();

--e;

printf("%d\n", e->a - s->a);

}

return 0;

}

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

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

[入力例]
4
1 10000
1 1000
2 100 3
1 10

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

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

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

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

[出力例]
5
5
11
11
12
12
12
11
11
11
6
6
6
6
7
7
10
7
7
7
7
7
7
13
13
13
11
10

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

[入力例]

1 3

1 2

1 7

2 2 3

[出力例]

※AtCoderテストケースより

[入力例]

1 10000

1 1000

2 100 3

1 10

[出力例]

※AtCoderテストケースより

[入力例]

1 4

2 4 1

2 5 2

1 4

2 2 3

2 3 3

1 3

2 5 2

1 6

1 3

1 4

2 0 1

2 1 1

2 4 2

2 1 2

1 5

1 3

1 5

1 4

1 2

2 1 3

1 3

1 5

2 4 3

1 3

1 0

1 4

2 6 1

2 3 3

1 6

2 5 1

2 0 1

2 2 2

1 6

2 6 3

1 0

[出力例]

[入力例]

100

1 6

1 1

1 0

2 6 3

1 5

2 1 2

1 4

1 11

2 2 3

1 2

1 0

1 12

2 3 2

2 6 1

1 0

2 2 1

1 1

1 2

2 12 3

1 5

1 6

1 4

2 2 3

1 6

2 6 1

1 2

2 11 2

2 5 2

1 6

2 3 1

1 0

1 5

1 0

1 2

1 1

1 4

1 7

1 3

2 6 3

1 2

1 1

1 3

1 5

1 10

2 2 3

2 0 3

1 5

1 3

2 10 3

1 6

1 0

1 3

1 2

1 1

1 2

2 3 2

2 3 3

1 13

1 3

1 11

2 0 2

2 5 2

1 1

2 2 1

2 13 1

2 6 1

2 7 1

2 0 3

[出力例]

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

// 解き直し.
// https://atcoder.jp/contests/abc253/editorial/4017
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(){
    
    // 1. 入力情報.
    LL N, A, B;
    scanf("%lld %lld %lld", &N, &A, &B);
    
    // 2. A, B の 倍数ではないものの総和は？
    // 2-1. 総和.
    LL ans = N * (N + 1) / 2;
    
    // 2-2. 総和(A の 倍数).
    LL qa = N / A;
    ans -= qa * (qa + 1) / 2 * A;
    
    // 2-3. 総和(B の 倍数).
    LL qb = N / B;
    ans -= qb * (qb + 1) / 2 * B;
    
    // 2-4. 総和(A, B の 最小公倍数).
    LL lcm = A * B / __gcd(A, B);
    LL qab = N / lcm;
    ans += qab * (qab + 1) / 2 * lcm;
    
    // 3. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc253/editorial/4017

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

int main(){

// 1. 入力情報.

LL N, A, B;

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

// 2. A, B の倍数ではないものの総和は？

// 2-1. 総和.

LL ans = N * (N + 1) / 2;

// 2-2. 総和(A の倍数).

LL qa = N / A;

ans -= qa * (qa + 1) / 2 * A;

// 2-3. 総和(B の倍数).

LL qb = N / B;

ans -= qb * (qb + 1) / 2 * B;

// 2-4. 総和(A, B の最小公倍数).

LL lcm = A * B / __gcd(A, B);

LL qab = N / lcm;

ans += qab * (qab + 1) / 2 * lcm;

// 3. 出力.

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

return 0;

}

[入力例]
10 3 5

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

[入力例]
1000000000 314 159

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

[入力例]
6 2 3

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

[入力例]
12 1 2

[出力例]
0

[入力例]
2022 8 20

[出力例]
1738209

[入力例]
20220528 27 18

[出力例]
189291570102870

[入力例]

10 3 5

[出力例]

※AtCoderテストケースより

[入力例]

1000000000 314 159

[出力例]

495273003954006262

※AtCoderテストケースより

[入力例]

6 2 3

[出力例]

※AtCoderテストケースより

[入力例]

12 1 2

[出力例]

[入力例]

2022 8 20

[出力例]

1738209

[入力例]

20220528 27 18

[出力例]

189291570102870

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

2022年8月17日

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

C++の練習を兼ねて, AtCoder Regular Contest 049 の問題B (高橋ノルム君) を解いてみた.

■感想.
1. 問題Bは, 方針が見えなかったので, 解説を参考に提出して, ようやく, AC版に到達出来た.
2. 個人的には, 二分探索(応用版, 小数点含む) の復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://www.slideshare.net/chokudai/arc049
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
#define all(x) x.begin(), x.end()
const double EPS = 1e-7;
const double INF = 202020202020.0;
double xy[1010][2], c[1010];

struct info{
    double p, c, t, k; // XY座標, 正整数定数, コスト, 符号.
    bool operator < (const info& rhs) const{
        return c * rhs.c * (p - rhs.p) < t * (rhs.c - c) * k;
    }
};

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%lf %lf %lf", &xy[i][0], &xy[i][1], &c[i]);
    
    // 2. 評価関数.
    auto f = [&](double m, int k) -> bool {
        // 2-1. m以下にできるか？
        vector<info> vl, vr;
        rep(i, N){
            vl.pb(info{xy[i][k], c[i], m, +1.0});
            vr.pb(info{xy[i][k], c[i], m, -1.0});
        }
        
        // 2-2. sort.
        sort(all(vl));
        sort(all(vr));
        
        // 2-3. 判定結果.
        info l = vl.back(), r = vr.front();
        return (r.p - l.p) * l.c * r.c >= -m * (l.c + r.c);
    };
    
    // 3. 二分探索で確認してみる.
    // 3-1. x方向.
    double l = 0.0, h = INF, ans = 0.0;
    while(EPS < abs(h - l)){
        double m = (h + l) / 2.0;
        if(f(m, 0)) h = m;
        else        l = m;
    }
    ans = max(ans, l);
    
    // 3-2. y方向.
    l = 0.0, h = INF;
    while(EPS < abs(h - l)){
        double m = (h + l) / 2.0;
        if(f(m, 1)) h = m;
        else        l = m;
    }
    ans = max(ans, l);
    
    // 4. 出力.
    printf("%.15lf\n", ans);
    return 0;
    
}

// 解き直し.

// https://www.slideshare.net/chokudai/arc049

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

#define pb push_back

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

const double EPS = 1e-7;

const double INF = 202020202020.0;

double xy[1010][2], c[1010];

struct info{

double p, c, t, k; // XY座標, 正整数定数, コスト, 符号.

bool operator < (const info& rhs) const{

return c * rhs.c * (p - rhs.p) < t * (rhs.c - c) * k;

}

};

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

rep(i, N) scanf("%lf %lf %lf", &xy[i][0], &xy[i][1], &c[i]);

// 2. 評価関数.

auto f = [&](double m, int k) -> bool {

// 2-1. m以下にできるか？

vector<info> vl, vr;

rep(i, N){

vl.pb(info{xy[i][k], c[i], m, +1.0});

vr.pb(info{xy[i][k], c[i], m, -1.0});

}

// 2-2. sort.

sort(all(vl));

sort(all(vr));

// 2-3. 判定結果.

info l = vl.back(), r = vr.front();

return (r.p - l.p) * l.c * r.c >= -m * (l.c + r.c);

};

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

// 3-1. x方向.

double l = 0.0, h = INF, ans = 0.0;

while(EPS < abs(h - l)){

double m = (h + l) / 2.0;

if(f(m, 0)) h = m;

else l = m;

}

ans = max(ans, l);

// 3-2. y方向.

l = 0.0, h = INF;

while(EPS < abs(h - l)){

double m = (h + l) / 2.0;

if(f(m, 1)) h = m;

else l = m;

}

ans = max(ans, l);

// 4. 出力.

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

return 0;

}

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

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

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

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

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

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

[入力例]
10
-27 -67 10
59 13 10
14 -15 9
-29 -84 7
-75 -2 2
-12 -74 5
77 31 9
40 64 8
-81 32 1
81 26 5

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

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

[入力例]
8
-81739 73917 446
42230 30484 911
79354 -50126 200
33440 -47087 651
-73 84114 905
79222 -53608 713
65194 -46284 685
81145 40933 47

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

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

[入力例]
3
-3 9 2
9 -5 3
10 8 5

[出力例]
24.374999949121964

[入力例]
7
85 -12 74
-18 -32 40
48 -89 20
-84 34 99
83 -112 14
100 98 51
-63 56 73

[出力例]
7156.612716680579979

[入力例]
30
52533 54305 67
64773 -45829 40
59127 76494 619
41062 -82488 824
77614 96992 999
-22277 96233 456
89003 97098 25
26503 -57323 324
93542 -26982 234
5253 21979 439
58210 -49169 954
-21460 15639 839
-38082 89568 717
45084 93608 832
-3098 93928 150
15494 61094 768
74469 -66666 874
10849 26147 341
98502 -2885 908
14469 4472 769
-93093 97848 430
60102 97930 297
-5297 12067 488
65474 -30187 130
42204 81887 40
27180 -86563 744
-26071 28252 940
-5227 57176 381
23081 95395 329
-17577 24330 731

[出力例]
81044228.458584725856781

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

[入力例]

0 0 1

10 10 1

[出力例]

5.000000000000000

※AtCoderのテストケースより

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

4.999999958112911

[入力例]

0 0 1

10 10 2

[出力例]

6.666666666666667

※AtCoderのテストケースより

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

6.666666640021313

[入力例]

-27 -67 10

59 13 10

14 -15 9

-29 -84 7

-75 -2 2

-12 -74 5

77 31 9

40 64 8

-81 32 1

81 26 5

[出力例]

582.222222222222222

※AtCoderのテストケースより

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

582.222222173114460

[入力例]

-81739 73917 446

42230 30484 911

79354 -50126 200

33440 -47087 651

-73 84114 905

79222 -53608 713

65194 -46284 685

81145 40933 47

[出力例]

54924095.383189122374461

※AtCoderのテストケースより

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

54924095.383189037442207

[入力例]

-3 9 2

9 -5 3

10 8 5

[出力例]

24.374999949121964

[入力例]

85 -12 74

-18 -32 40

48 -89 20

-84 34 99

83 -112 14

100 98 51

-63 56 73

[出力例]

7156.612716680579979

[入力例]

52533 54305 67

64773 -45829 40

59127 76494 619

41062 -82488 824

77614 96992 999

-22277 96233 456

89003 97098 25

26503 -57323 324

93542 -26982 234

5253 21979 439

58210 -49169 954

-21460 15639 839

-38082 89568 717

45084 93608 832

-3098 93928 150

15494 61094 768

74469 -66666 874

10849 26147 341

98502 -2885 908

14469 4472 769

-93093 97848 430

60102 97930 297

-5297 12067 488

65474 -30187 130

42204 81887 40

27180 -86563 744

-26071 28252 940

-5227 57176 381

23081 95395 329

-17577 24330 731

[出力例]

81044228.458584725856781

■参照サイト
AtCoder Regular Contest 049

2022年8月16日

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

C++の練習を兼ねて, AtCoder Grand Contest 058 の問題A (Make it Zigzag) を解いてみた.

■感想.
1. 問題Aは, 方針が見えなかったので, 解説を参考に提出して, ようやく, AC版に到達出来た.
2. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/agc058/editorial/4574
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
int p[202020];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, 2 * N) scanf("%d", &p[i]);
    
    // 2. 操作列.
    vi ans;
    rep(i, 2 * N - 1){
        // 奇数.
        if(i & 1){
            if(p[i] < p[i + 1]){
                if(i == 2 * N - 2 || p[i] < p[i + 2]){
                    ans.pb(i + 1);
                    swap(p[i], p[i + 1]);
                }else{
                    ans.pb(i + 2);
                    swap(p[i + 1], p[i + 2]);
                }
            }
        }
        
        // 偶数.
        if(!(i & 1)){
            if(p[i] > p[i + 1]){
                if(i == 2 * N - 2 || p[i] > p[i + 2]){
                    ans.pb(i + 1);
                    swap(p[i], p[i + 1]);
                }else{
                    ans.pb(i + 2);
                    swap(p[i + 1], p[i + 2]);
                }
            }
        }
    }
    
    // 3. 出力.
    int n = ans.size();
    printf("%d\n", n);
    rep(i, n) printf("%d%s", ans[i], (i < n - 1) ? " " : "\n");
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/agc058/editorial/4574

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

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

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

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

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

#define pb push_back

int p[202020];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

rep(i, 2 * N) scanf("%d", &p[i]);

// 2. 操作列.

vi ans;

rep(i, 2 * N - 1){

// 奇数.

if(i & 1){

if(p[i] < p[i + 1]){

if(i == 2 * N - 2 || p[i] < p[i + 2]){

ans.pb(i + 1);

swap(p[i], p[i + 1]);

}else{

ans.pb(i + 2);

swap(p[i + 1], p[i + 2]);

}

// 偶数.

if(!(i & 1)){

if(p[i] > p[i + 1]){

if(i == 2 * N - 2 || p[i] > p[i + 2]){

ans.pb(i + 1);

swap(p[i], p[i + 1]);

}else{

ans.pb(i + 2);

swap(p[i + 1], p[i + 2]);

}

// 3. 出力.

int n = ans.size();

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

rep(i, n) printf("%d%s", ans[i], (i < n - 1) ? " " : "\n");

return 0;

}

[入力例]
2
4 3 2 1

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

[入力例]
1
1 2

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

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

[出力例]
2
1 4

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

[出力例]
2
1 4

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

[出力例]
8
2 8 12 13 18 24 26 29

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

[出力例]
10
15 18 22 26 29 36 39 42 44 48

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

[出力例]
16
1 7 9 14 15 18 22 28 29 32 34 36 39 41 47 49

[入力例]

4 3 2 1

[出力例]

1 3

※AtCoderテストケースより

[入力例]

1 2

[出力例]

※AtCoderテストケースより

[入力例]

5 1 2 3 6 4

[出力例]

1 4

[入力例]

5 4 2 1 3 8 6 7

[出力例]

1 4

[入力例]

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

[出力例]

2 8 12 13 18 24 26 29

[入力例]

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

[出力例]

15 18 22 26 29 36 39 42 44 48

[入力例]

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

[出力例]

1 7 9 14 15 18 22 28 29 32 34 36 39 41 47 49

■参照サイト
AtCoder Grand Contest 058

2022年8月14日

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

C++の練習を兼ねて, AtCoder Regular Contest 047 の問題C (N!÷K番目の単語) を解いてみた.

■感想.
1. 問題Cは, 方針が見えなかったので, 解説を参考に提出して, ようやく, AC版に到達出来た.
2. Binary Indexed Tree の復習が出来たので, 非常に良かったと思う.
※ 公式のライブラリを拝借させて頂いてます.
3. 合わせて, 二分探索の復習も出来たので, 非常に良かったと思う.
4. Binary Indexed Tree と二分探索を組み合わせて, 歯抜けになった状態から, i文字目を確定するロジックが, 非常に面白いと感じた.
5. 余りが 0 となった場合, 別途, 処理を考慮する必要がある点に, 注意が必要と理解した.
6. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://www.slideshare.net/chokudai/arc047-57126901
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vi = vector<int>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back

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

int main(){
    
    // 1. 入力情報.
    int N, K;
    scanf("%d %d", &N, &K);
    
    // 2. 事前準備.
    BIT<int> ft(N + 1);
    repx(i, 1, N + 1) ft.add(i, 1);
    
    // 3. 評価関数.
    auto f = [&](int m, int q) -> bool {
        // 3-1. 区間[1, m] の 合計は？
        int t = ft.sum(1, m + 1);
        
        // 3-2. 判定結果.
        return (t < q);
    };
    
    // 4. 単語を検索.
    vi ans;
    int q = 0, r = 1;
    rep(i, N){
        // 4-1. 商, 余り.
        LL cur = (LL)r * (LL)(N - i);
        q = (int)(cur / K);
        r = (int)(cur % K);
        
        // 4-2. 二分探索で確認してみる.
        int l = 0, h = 2 * N + 1, m;
        while(l + 1 < h){
            int m = (h + l) >> 1;
            if(f(m, q + (r > 0))) l = m;
            else                  h = m;
            // printf("h=%d l=%d m=%d\n", h, l, m);
        }
        
        // 4-3. 位置 h に, 1 を 減算.
        ft.add(h, -1);
        
        // 4-4. 保存.
        ans.pb(h);
        
        // 4-5. 例外(余り 0).
        if(!r){
            // 保存(残り).
            repr(j, N, 1) if(ft.sum(j, j + 1)) ans.pb(j);
            
            // 終了.
            break;
        }
    }
    
    // 5. 出力.
    for(auto &p : ans) printf("%d\n", p);
    return 0;
    
}

// 解き直し.

// https://www.slideshare.net/chokudai/arc047-57126901

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vi = vector<int>;

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

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

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

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

#define pb push_back

// Binary Indexed Tree (Fenwick Tree)

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

template<typename T>

struct BIT{

int n;

vector<T> d;

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

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

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

}

T sum(int i){

T x = 0;

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

return x;

}

T sum(int l, int r){

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

}

};

int main(){

// 1. 入力情報.

int N, K;

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

// 2. 事前準備.

BIT<int> ft(N + 1);

repx(i, 1, N + 1) ft.add(i, 1);

// 3. 評価関数.

auto f = [&](int m, int q) -> bool {

// 3-1. 区間[1, m] の合計は？

int t = ft.sum(1, m + 1);

// 3-2. 判定結果.

return (t < q);

};

// 4. 単語を検索.

vi ans;

int q = 0, r = 1;

rep(i, N){

// 4-1. 商, 余り.

LL cur = (LL)r * (LL)(N - i);

q = (int)(cur / K);

r = (int)(cur % K);

// 4-2. 二分探索で確認してみる.

int l = 0, h = 2 * N + 1, m;

while(l + 1 < h){

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

if(f(m, q + (r > 0))) l = m;

else h = m;

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

}

// 4-3. 位置 h に, 1 を減算.

ft.add(h, -1);

// 4-4. 保存.

ans.pb(h);

// 4-5. 例外(余り 0).

if(!r){

// 保存(残り).

repr(j, N, 1) if(ft.sum(j, j + 1)) ans.pb(j);

// 終了.

break;

}

// 5. 出力.

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

return 0;

}

[入力例]
4 3

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

[入力例]
11 7

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

[入力例]
3 2

[出力例]
2
1
3

[入力例]
4 4

[出力例]
1
4
3
2

[入力例]
5 3

[出力例]
2
4
3
5
1

[入力例]
6 5

[出力例]
2
1
6
5
4
3

[入力例]
10 8

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

[入力例]
23 15

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

[入力例]
27 18

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

[入力例]
100 77

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

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

[入力例]

4 3

[出力例]

※AtCoderテストケースより

[入力例]

11 7

[出力例]

※AtCoderテストケースより

[入力例]

3 2

[出力例]

[入力例]

4 4

[出力例]

[入力例]

5 3

[出力例]

[入力例]

6 5

[出力例]

[入力例]

10 8

[出力例]

[入力例]

23 15

[出力例]

[入力例]

27 18

[出力例]

[入力例]

100 77

[出力例]

100

■参照サイト
AtCoder Regular Contest 047

2022年8月14日

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

C++の練習を兼ねて, AtCoder Beginner Contest 264 の問題C (Matrix Reducing) ～問題D (“redocta”.swap(i,i+1)) を解いてみた.

■感想.
1. 問題C, Dは, 方針が絞り込めたので, AC版に到達出来た.
2. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

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

int main(){
    
    // 1. 入力情報.
    int h1, w1;
    scanf("%d %d", &h1, &w1);
    rep(i, h1) rep(j, w1) scanf("%d", &a[i][j]);
    int h2, w2;
    scanf("%d %d", &h2, &w2);
    rep(i, h2) rep(j, w2) scanf("%d", &b[i][j]);
    
    // 2. 判定.
    bool ok = false;
    rep(i, 1 << h1){
        rep(j, 1 << w1){
            if(__builtin_popcount(i) == h2 && __builtin_popcount(j) == w2){
                vi r, c;
                rep(k, h1) if(i & (1 << (h1 - 1 - k))) r.pb(k);
                rep(k, w1) if(j & (1 << (w1 - 1 - k))) c.pb(k);
                int m = 0;
                rep(k, h2) rep(l, w2) if(a[r[k]][c[l]] == b[k][l]) ++m;
                if(m == h2 * w2) ok = true;
            }
            if(ok) break;
        }
        if(ok) break;
    }
    
    // 3. 出力.
    printf("%s\n", ok ? "Yes" : "No");
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

#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 a[22][22], b[22][22];

int main(){

// 1. 入力情報.

int h1, w1;

scanf("%d %d", &h1, &w1);

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

int h2, w2;

scanf("%d %d", &h2, &w2);

rep(i, h2) rep(j, w2) scanf("%d", &b[i][j]);

// 2. 判定.

bool ok = false;

rep(i, 1 << h1){

rep(j, 1 << w1){

if(__builtin_popcount(i) == h2 && __builtin_popcount(j) == w2){

vi r, c;

rep(k, h1) if(i & (1 << (h1 - 1 - k))) r.pb(k);

rep(k, w1) if(j & (1 << (w1 - 1 - k))) c.pb(k);

int m = 0;

rep(k, h2) rep(l, w2) if(a[r[k]][c[l]] == b[k][l]) ++m;

if(m == h2 * w2) ok = true;

}

if(ok) break;

}

if(ok) break;

}

// 3. 出力.

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

return 0;

}

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

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

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

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

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

[出力例]
No

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

[出力例]
Yes

[入力例]
15 13
14112 6703 7454 16669 7504 15174 10947 5600 16299 9455 8775 14843 15446
10004 15105 7182 12983 7848 16470 10802 7418 11339 14214 10209 10642 11947
7872 7590 10518 6332 15478 7121 15346 13572 12418 9757 16916 15100 15001
6754 16819 8481 6762 9875 11093 11354 11475 9663 17822 6608 6654 12567
14542 6957 6254 11540 10730 7004 12983 10200 10338 6225 16679 14253 13898
9651 12852 10111 13123 12501 17677 14465 12935 6714 5636 5867 8039 12899
9268 6793 8535 16434 12347 14547 17801 16118 6708 6989 7556 12148 13991
12462 10999 13742 11830 12261 12256 8219 9739 13284 13676 10999 6516 6809
12489 11964 13749 5888 6891 16004 17815 8654 13771 11399 15752 16153 8000
12995 13348 6191 13298 11707 17111 10732 11997 13590 6752 12167 8851 10078
13631 10939 7729 14238 11173 10749 14903 7076 7150 6899 10203 13855 13507
12197 14511 11419 14041 17497 6261 10789 12046 17145 8358 16503 6293 15987
7459 15819 15843 15591 12920 15026 6222 15588 17770 7812 11065 10296 16756
11297 16984 7284 16838 8746 5622 9769 13472 15395 14944 16958 15049 15310
16923 13275 10278 17897 7761 16148 15743 10395 17356 8316 10620 15096 13629
11 10
14112 6703 16669 7504 15174 5600 16299 9455 8775 15446
10004 15105 12983 7848 16470 7418 11339 14214 10209 11947
6754 16819 6762 9875 11093 11475 9663 17822 6608 12567
14542 6957 11540 10730 7004 10200 10338 6225 16679 13898
12462 10999 11830 12261 12256 9739 13284 13676 10999 6809
12489 11964 5888 6891 16004 8654 13771 11399 15752 8000
12995 13348 13298 11707 17111 11997 13590 6752 12167 10078
12197 14511 14041 17497 6261 12046 17145 8358 16503 15987
7459 15819 15591 12920 15026 15588 17770 7812 11065 16756
11297 16984 16838 8746 5622 13472 15395 14944 16958 15310
16923 13275 17897 7761 16148 10395 17356 8316 10620 13629

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

[入力例]

4 5

1 2 3 4 5

6 7 8 9 10

11 12 13 14 15

16 17 18 19 20

2 3

6 8 9

16 18 19

[出力例]

Yes

※AtCoderテストケースより

[入力例]

3 3

1 1 1

1 1

[出力例]

※AtCoderテストケースより

[入力例]

2 3

1 2 3

3 2 1

1 2

1 1

[出力例]

[入力例]

10 10

18 4 12 12 9 7 14 15 4 9

17 19 16 17 17 15 20 5 17 12

13 20 19 18 16 2 1 20 18 5

11 2 16 10 1 16 18 18 5 16

14 6 13 7 11 16 20 6 8 16

16 8 14 3 16 11 20 11 6 10

12 4 19 1 8 3 13 9 19 1

15 3 11 6 12 10 8 19 9 20

6 9 9 9 4 11 8 6 1 17

16 11 7 7 6 7 17 12 13 6

6 6

18 12 9 7 14 9

11 10 1 16 18 16

14 7 11 16 20 16

15 6 12 10 8 20

6 9 4 11 8 17

16 7 6 7 17 6

[出力例]

Yes

[入力例]

15 13

14112 6703 7454 16669 7504 15174 10947 5600 16299 9455 8775 14843 15446

10004 15105 7182 12983 7848 16470 10802 7418 11339 14214 10209 10642 11947

7872 7590 10518 6332 15478 7121 15346 13572 12418 9757 16916 15100 15001

6754 16819 8481 6762 9875 11093 11354 11475 9663 17822 6608 6654 12567

14542 6957 6254 11540 10730 7004 12983 10200 10338 6225 16679 14253 13898

9651 12852 10111 13123 12501 17677 14465 12935 6714 5636 5867 8039 12899

9268 6793 8535 16434 12347 14547 17801 16118 6708 6989 7556 12148 13991

12462 10999 13742 11830 12261 12256 8219 9739 13284 13676 10999 6516 6809

12489 11964 13749 5888 6891 16004 17815 8654 13771 11399 15752 16153 8000

12995 13348 6191 13298 11707 17111 10732 11997 13590 6752 12167 8851 10078

13631 10939 7729 14238 11173 10749 14903 7076 7150 6899 10203 13855 13507

12197 14511 11419 14041 17497 6261 10789 12046 17145 8358 16503 6293 15987

7459 15819 15843 15591 12920 15026 6222 15588 17770 7812 11065 10296 16756

11297 16984 7284 16838 8746 5622 9769 13472 15395 14944 16958 15049 15310

16923 13275 10278 17897 7761 16148 15743 10395 17356 8316 10620 15096 13629

11 10

14112 6703 16669 7504 15174 5600 16299 9455 8775 15446

10004 15105 12983 7848 16470 7418 11339 14214 10209 11947

6754 16819 6762 9875 11093 11475 9663 17822 6608 12567

14542 6957 11540 10730 7004 10200 10338 6225 16679 13898

12462 10999 11830 12261 12256 9739 13284 13676 10999 6809

12489 11964 5888 6891 16004 8654 13771 11399 15752 8000

12995 13348 13298 11707 17111 11997 13590 6752 12167 10078

12197 14511 14041 17497 6261 12046 17145 8358 16503 15987

7459 15819 15591 12920 15026 15588 17770 7812 11065 16756

11297 16984 16838 8746 5622 13472 15395 14944 16958 15310

16923 13275 17897 7761 16148 10395 17356 8316 10620 13629

[出力例]

Yes

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

■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 a[33], p[11];

int main(){
    
    // 1. 入力情報.
    char c[11];
    scanf("%s", c);
    string s(c);
    
    // 2. 転倒数.
    int ans = 0;
    string atcoder = "atcoder";
    rep(i, 7) a[atcoder[i] - 'a'] = i + 1;
    rep(i, 7) p[i] = a[s[i] - 'a'];
    rep(i, 7) repx(j, i + 1, 7) if(p[i] > p[j]) ++ans;
    
    // 3. 出力.
    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 a[33], p[11];

int main(){

// 1. 入力情報.

char c[11];

scanf("%s", c);

string s(c);

// 2. 転倒数.

int ans = 0;

string atcoder = "atcoder";

rep(i, 7) a[atcoder[i] - 'a'] = i + 1;

rep(i, 7) p[i] = a[s[i] - 'a'];

rep(i, 7) repx(j, i + 1, 7) if(p[i] > p[j]) ++ans;

// 3. 出力.

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

return 0;

}

[入力例]
catredo

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

[入力例]
atcoder

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

[入力例]
redocta

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

[入力例]
deratco

[出力例]
12

[入力例]
ercatdo

[出力例]
13

[入力例]

catredo

[出力例]

※AtCoderテストケースより

[入力例]

atcoder

[出力例]

※AtCoderテストケースより

[入力例]

redocta

[出力例]

※AtCoderテストケースより

[入力例]

deratco

[出力例]

[入力例]

ercatdo

[出力例]

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

C++の練習を兼ねて, AtCoder Regular Contest 046 の 問題C (合コン大作戦) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 146 の 問題C (Even XOR) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 146 の 問題A (Three Cards) ～ 問題B (Plus and AND) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 253 の 問題E (Distance Sequence) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 264 の 問題E (Blackout 2) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 253 の 問題C (Max – Min Query) ～ 問題D (FizzBuzz Sum Hard) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 049 の 問題B (高橋ノルム君) を解いてみた.

C++の練習を兼ねて, AtCoder Grand Contest 058 の 問題A (Make it Zigzag) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 047 の 問題C (N!÷K番目の単語) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 264 の 問題C (Matrix Reducing) ～ 問題D (“redocta”.swap(i,i+1)) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 046 の問題C (合コン大作戦) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 146 の問題C (Even XOR) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 146 の問題A (Three Cards) ～問題B (Plus and AND) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 253 の問題E (Distance Sequence) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 264 の問題E (Blackout 2) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 253 の問題C (Max – Min Query) ～問題D (FizzBuzz Sum Hard) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 049 の問題B (高橋ノルム君) を解いてみた.

C++の練習を兼ねて, AtCoder Grand Contest 058 の問題A (Make it Zigzag) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 047 の問題C (N!÷K番目の単語) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 264 の問題C (Matrix Reducing) ～問題D (“redocta”.swap(i,i+1)) を解いてみた.