C++ | 個人用メモ帳

2021年9月14日

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

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

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

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

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

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

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

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    LL cTotal = 0;
    rep(i, M){
        scanf("%d %d %lld", &a[i], &b[i], &c[i]);
        a[i]--;
        b[i]--;
        cTotal += c[i]; // コスト合計.
    }
    
    // 2. sort.
    vector<T3> t;
    rep(i, M) t.emplace_back(c[i], a[i], b[i]);
    sort(all(t));
    
    // 3. 最小全域木(Kruskal's Algorithm)を計算.
    // 競プロ典型 90 問 (049 - Flip Digits 2)
    // https://github.com/E869120/kyopro_educational_90/blob/main/sol/049.cpp
    LL cSum = 0;
    UnionFind uf(N + 2);
    rep(i, t.size()){
        // 3-1. グラフ情報.
        int u = get<1>(t[i]);
        int v = get<2>(t[i]);
        LL cost = get<0>(t[i]);
        
        // 3-2. コストが負.
        // -> 必ず, 辺を追加.
        if(cost < 0){
            uf.unite(u, v);
            cSum += cost;
        }
        
        // 3-3. コストがゼロ以上.
        // -> 最小全域木に必要な場合に, 追加.
        if(cost >= 0){
            if(!uf.same(u, v)){
                uf.unite(u, v);
                cSum += cost;
            }
        }
    }
    
    // 4. 出力.
    printf("%lld\n", cTotal - cSum);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc218/editorial/2580

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vi = vector<int>;

using vl = vector<LL>;

using T3 = tuple<LL, int, int>;

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

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

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

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

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

LL c[202020];

int a[202020], b[202020];

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

// UnionFind

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

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

// -> 一部改変.

struct UnionFind{

vi d;

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

int find(int x){

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

}

bool unite(int x, int y){

x = find(x);

y = find(y);

if(x == y) return false;

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

d[x] += d[y];

d[y] = x;

return true;

}

bool same(int x, int y){

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

}

int size(int x){

return -d[find(x)];

}

};

int main(){

// 1. 入力情報.

int N, M;

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

LL cTotal = 0;

rep(i, M){

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

a[i]--;

b[i]--;

cTotal += c[i]; // コスト合計.

}

// 2. sort.

vector<T3> t;

rep(i, M) t.emplace_back(c[i], a[i], b[i]);

sort(all(t));

// 3. 最小全域木(Kruskal's Algorithm)を計算.

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

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

LL cSum = 0;

UnionFind uf(N + 2);

rep(i, t.size()){

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

int u = get<1>(t[i]);

int v = get<2>(t[i]);

LL cost = get<0>(t[i]);

// 3-2. コストが負.

// -> 必ず, 辺を追加.

if(cost < 0){

uf.unite(u, v);

cSum += cost;

}

// 3-3. コストがゼロ以上.

// -> 最小全域木に必要な場合に, 追加.

if(cost >= 0){

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

uf.unite(u, v);

cSum += cost;

}

// 4. 出力.

printf("%lld\n", cTotal - cSum);

return 0;

}

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

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

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

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

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

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

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

[出力例]
13

※実際, 辺 1, 4, 5 を 取り除いて, 合計 4 + 3 + 6 = 13 の 報酬となる.

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

[出力例]
49

※実際, 辺 5, 7, 8, 10, 13, 15, 16 を 取り除いて, 合計 3 + 6 + 7 + 11 + 6 + 7 + 9 = 49 の 報酬となる.

[入力例]

4 5

1 2 1

1 3 1

1 4 1

3 2 2

4 2 2

[出力例]

※AtCoderテストケースより

[入力例]

3 3

1 2 1

2 3 0

3 1 -1

[出力例]

※AtCoderテストケースより

[入力例]

2 3

1 2 -1

1 2 2

1 1 3

[出力例]

※AtCoderテストケースより

[入力例]

5 7

1 3 4

3 4 3

1 2 -1

2 5 3

2 5 6

2 4 2

5 4 -2

[出力例]

※実際, 辺 1, 4, 5 を取り除いて, 合計 4 + 3 + 6 = 13 の報酬となる.

[入力例]

10 16

1 3 -4

7 1 3

5 3 2

3 6 -1

5 6 3

5 2 7

5 7 6

7 9 7

4 9 -3

8 9 11

4 8 4

4 2 5

2 8 6

2 10 2

6 10 7

8 10 9

[出力例]

※実際, 辺 5, 7, 8, 10, 13, 15, 16 を取り除いて, 合計 3 + 6 + 7 + 11 + 6 + 7 + 9 = 49 の報酬となる.

■参照サイト
AtCoder Beginner Contest 218
Union-Find木
 競プロ典型 90 問の問題049

2021年9月13日

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

C++の練習を兼ねて, AtCoder Beginner Contest 218 の問題C (Shapes) ～問題D (Rectangles) を解いてみた.

■感想.
1. 問題D は, 方針が見えなかったので, 解説を参考に実装したところ, AC版に到達出来た.
2. 問題D の解説で, 全探索で数え上げていく方針が, なるほどと感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vs = vector<string>;
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

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    vs S, T000;
    rep(i, N){
        char c[202];
        scanf("%s", c);
        string s(c);
        S.pb(s);
    }
    rep(i, N){
        char c[202];
        scanf("%s", c);
        string s(c);
        T000.pb(s);
    }
    
    // 2. T を 90度, 180度, 270度回転させる.
    vs T090, T180, T270;
    string x(N, '.');
    rep(i, N){
        T090.pb(x);
        T180.pb(x);
        T270.pb(x);
    }
    rep(i, N) rep(j, N) T090[N - 1 - j][i] = T000[i][j];
    rep(i, N) rep(j, N) T180[N - 1 - j][i] = T090[i][j];
    rep(i, N) rep(j, N) T270[N - 1 - j][i] = T180[i][j];
    
    // 3. 図形 について, # の 位置関係を取得.
    auto f = [&](vs &s) -> set<P> {
        // 3-1. 基準となる場所を取得.
        set<P> ret;
        int sx = -1, sy = -1;
        rep(i, N){
            bool ok = false;
            rep(j, N){
                if(s[i][j] == '#'){
                    sx = i;
                    sy = j;
                    ok = true;
                    break;
                }
            }
            if(ok) break;
        }
        
        // 3-2. 位置関係を取得.
        rep(i, N) rep(j, N) if(s[i][j] == '#') ret.insert({i - sx, j - sy});
        
        // 3-3. 返却.
        return ret;
    };
    
    // 4. 各図形 について, # の 位置関係を保存.
    set<P> q0 = f(S);
    set<P> q1 = f(T000);
    set<P> q2 = f(T090);
    set<P> q3 = f(T180);
    set<P> q4 = f(T270);
    
    // 5. 出力.
    bool ans = false;
    if(q0 == q1 || q0 == q2 || q0 == q3 || q0 == q4) ans = true;
    printf("%s\n", ans ? "Yes" : "No");
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vs = vector<string>;

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

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

vs S, T000;

rep(i, N){

char c[202];

scanf("%s", c);

string s(c);

S.pb(s);

}

rep(i, N){

char c[202];

scanf("%s", c);

string s(c);

T000.pb(s);

}

// 2. T を 90度, 180度, 270度回転させる.

vs T090, T180, T270;

string x(N, '.');

rep(i, N){

T090.pb(x);

T180.pb(x);

T270.pb(x);

}

rep(i, N) rep(j, N) T090[N - 1 - j][i] = T000[i][j];

rep(i, N) rep(j, N) T180[N - 1 - j][i] = T090[i][j];

rep(i, N) rep(j, N) T270[N - 1 - j][i] = T180[i][j];

// 3. 図形について, # の位置関係を取得.

auto f = [&](vs &s) -> set {

// 3-1. 基準となる場所を取得.

set ret;

int sx = -1, sy = -1;

rep(i, N){

bool ok = false;

rep(j, N){

if(s[i][j] == '#'){

sx = i;

sy = j;

ok = true;

break;

}

if(ok) break;

}

// 3-2. 位置関係を取得.

rep(i, N) rep(j, N) if(s[i][j] == '#') ret.insert({i - sx, j - sy});

// 3-3. 返却.

return ret;

};

// 4. 各図形について, # の位置関係を保存.

set q0 = f(S);

set q1 = f(T000);

set q2 = f(T090);

set q3 = f(T180);

set q4 = f(T270);

// 5. 出力.

bool ans = false;

if(q0 == q1 || q0 == q2 || q0 == q3 || q0 == q4) ans = true;

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

return 0;

}

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

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

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

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

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

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

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

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

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

[出力例]
Yes

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

[出力例]
Yes

[入力例]
17
.................
...#...###...###.
..#.#..#..#.#....
..#.#..#..#.#....
..###..####.#....
.#...#.#..#.#....
.#...#.#..#.#....
.#...#.###...###.
.................
.####..##..#####.
....#...#..#...#.
....#...#..#...#.
.####...#..#####.
.#......#..#...#.
.#......#..#...#.
.####..###.#####.
.................
.................
.................
####..#.###......
#..#..#....###...
#..#..#....#..#..
#..####....###...
........###......
.................
#.....#.#######..
#######.#..#..#..
#.......#..#..#..
.........#####...
#######..........
#..#..#..#####...
#..#..#.#.....#..
#..#..#.#.....#..
#######.#.....#..

[出力例]
Yes

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

[入力例]

.....

..#..

.###.

.....

....#

...##

....#

[出力例]

Yes

※AtCoderテストケースより

[入力例]

#####

##..#

#..##

#####

.....

#####

#..##

##..#

#####

.....

[出力例]

※AtCoderテストケースより

[入力例]

#...

..#.

....

#...

..#.

....

[出力例]

Yes

※AtCoderテストケースより

[入力例]

#...

.##.

..#.

....

##..

#...

..#.

....

[出力例]

※AtCoderテストケースより

[入力例]

#..

.#.

...

..#

.#.

...

[出力例]

Yes

[入力例]

..#..

.#.#.

.###.

#...#

...##

.##..

#.#..

.##..

...##

[出力例]

Yes

[入力例]

.................

...#...###...###.

..#.#..#..#.#....

..###..####.#....

.#...#.#..#.#....

.#...#.###...###.

.................

.####..##..#####.

....#...#..#...#.

.####...#..#####.

.#......#..#...#.

.####..###.#####.

.................

####..#.###......

#..#..#....###...

#..#..#....#..#..

#..####....###...

........###......

.................

#.....#.#######..

#######.#..#..#..

#.......#..#..#..

.........#####...

#######..........

#..#..#..#####...

#..#..#.#.....#..

#######.#.....#..

[出力例]

Yes

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

// 解き直し.
// https://atcoder.jp/contests/abc218/editorial/2605
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define a first
#define b second

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    set<P> st;
    rep(i, N){
        int x, y;
        scanf("%d %d", &x, &y);
        st.insert({x, y});
    }
    
    // 2. 全探索.
    int ans = 0;
    for(auto &p : st){
        // 左下.
        int ldX = p.a;
        int ldY = p.b;
        for(auto &q : st){
            // 右上.
            int ruX = q.a;
            int ruY = q.b;
            
            // 条件を満たすかチェック.
            if(ruX <= ldX || ruY <= ldY) continue;
            
            // 左上 を 含むか？
            bool ok = true;
            if(st.count({ldX, ruY}) == 0) ok = false;
            
            // 右下 を 含むか？
            if(st.count({ruX, ldY}) == 0) ok = false;
            
            // カウント.
            if(ok) ans++;
        }
    }
    
    // 3. 出力.
    printf("%d\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc218/editorial/2605

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using P = pair<int, int>;

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

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

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

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

#define a first

#define b second

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

set st;

rep(i, N){

int x, y;

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

st.insert({x, y});

}

// 2. 全探索.

int ans = 0;

for(auto &p : st){

// 左下.

int ldX = p.a;

int ldY = p.b;

for(auto &q : st){

// 右上.

int ruX = q.a;

int ruY = q.b;

// 条件を満たすかチェック.

if(ruX <= ldX || ruY <= ldY) continue;

// 左上を含むか？

bool ok = true;

if(st.count({ldX, ruY}) == 0) ok = false;

// 右下を含むか？

if(st.count({ruX, ldY}) == 0) ok = false;

// カウント.

if(ok) ans++;

}

// 3. 出力.

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

return 0;

}

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

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

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

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

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

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

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

[出力例]
10

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

[出力例]
22

[入力例]

0 0

0 1

1 0

1 1

2 0

2 1

[出力例]

※AtCoderテストケースより

[入力例]

0 1

1 2

2 3

3 4

[出力例]

※AtCoderテストケースより

[入力例]

0 1

1 0

2 0

2 1

2 2

3 0

3 2

[出力例]

※AtCoderテストケースより

[入力例]

3 2

3 7

3 11

5 4

5 7

5 11

7 2

7 4

7 7

7 11

9 7

9 11

[出力例]

[入力例]

1 0

1 5

1 8

0 5

0 9

0 12

3 0

3 2

3 5

3 8

2 3

2 9

10 8

10 9

10 11

2 7

5 8

5 11

5 2

5 3

2 12

9 8

9 11

4 3

4 9

6 0

6 5

7 0

7 2

7 3

7 5

7 7

7 9

[出力例]

■参照サイト
AtCoder Beginner Contest 218

2021年9月12日

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

C++の練習を兼ねて, AtCoder Beginner Contest 216 の問題G (01Sequence) を解いてみた.

■感想.
1. 問題G は, 方針が見えなかったので, 解説を参考に実装したところ, AC版に到達出来た.
2. ダイクストラ法の復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/abc216/editorial/2474
// 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 pb push_back
const LL INF = 202020202020202020;

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

vector<edge> G[202020];

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    rep(i, M){
        int l, r, x;
        scanf("%d %d %d", &l, &r, &x);
        edge e;
        e.n = r;
        e.c = (LL)(r - l + 1 - x);
        G[l - 1].pb(e);
    }
    
    // 2. グラフに辺を追加.
    rep(i, N){
        edge e1;
        e1.n = i + 1;
        e1.c = 1LL;
        G[i].pb(e1);
        
        edge e2;
        e2.n = i;
        e2.c = 0LL;
        G[i + 1].pb(e2);
    }
    
    // 3. ダイクストラ法.
    // https://ja.wikipedia.org/wiki/ダイクストラ法
    auto dijkstra = [&](int s, LL* d, int* memo){
        // 3-1. 初期化.
        priority_queue<edge> pq;
        
        // 3-2. 始点設定.
        d[s] = 0;
        pq.push({s, 0LL});
        
        // 3-3. キュー pq が 空になるまで, 探索.
        while(!pq.empty()){
            // 3-4. 探索を継続するために, 頂点を取得.
            edge e = pq.top();
            pq.pop();
            int cn = e.n;
            LL cc = e.c;
            
            // 3-5. 訪問済みフラグ設定.
            if(memo[cn]) continue;
            memo[cn]++;
            
            // 3-6. 各隣接する頂点について, 距離を確認し, 移動コストを更新.
            for(auto &g : G[cn]){
                // 移動コスト更新.
                int nn = g.n;
                LL nc = cc + g.c;
                if(d[nn] > nc) d[nn] = nc, pq.push({nn, nc});
            }
        }
        return;
    };
    
    // 4. 各頂点までの, 最短コストを求める.
    LL d[N + 1];     // 頂点 0 からの距離.
    int memo[N + 1]; // 訪問済みフラグ.
    rep(i, N + 1) d[i] = INF, memo[i] = 0;
    dijkstra(0, d, memo);
    
    // 5. 数列 A に含まれる 1 の 個数.
    LL a[N];
    rep(i, N) a[i] = 1LL - (d[i + 1] - d[i]);
    
    // 6. 出力.
    rep(i, N){
        printf("%lld", a[i]);
        printf("%s", (i < N - 1) ? " " : "\n");
    }
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc216/editorial/2474

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

const LL INF = 202020202020202020;

struct edge{

int n; // 次の頂点.

LL c; // コスト.

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

};

vector<edge> G[202020];

int main(){

// 1. 入力情報.

int N, M;

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

rep(i, M){

int l, r, x;

scanf("%d %d %d", &l, &r, &x);

edge e;

e.n = r;

e.c = (LL)(r - l + 1 - x);

G[l - 1].pb(e);

}

// 2. グラフに辺を追加.

rep(i, N){

edge e1;

e1.n = i + 1;

e1.c = 1LL;

G[i].pb(e1);

edge e2;

e2.n = i;

e2.c = 0LL;

G[i + 1].pb(e2);

}

// 3. ダイクストラ法.

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

auto dijkstra = [&](int s, LL* d, int* memo){

// 3-1. 初期化.

priority_queue<edge> pq;

// 3-2. 始点設定.

d[s] = 0;

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

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

while(!pq.empty()){

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

edge e = pq.top();

pq.pop();

int cn = e.n;

LL cc = e.c;

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

if(memo[cn]) continue;

memo[cn]++;

// 3-6. 各隣接する頂点について, 距離を確認し, 移動コストを更新.

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

// 移動コスト更新.

int nn = g.n;

LL nc = cc + g.c;

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

}

return;

};

// 4. 各頂点までの, 最短コストを求める.

LL d[N + 1]; // 頂点 0 からの距離.

int memo[N + 1]; // 訪問済みフラグ.

rep(i, N + 1) d[i] = INF, memo[i] = 0;

dijkstra(0, d, memo);

// 5. 数列 A に含まれる 1 の個数.

LL a[N];

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

// 6. 出力.

rep(i, N){

printf("%lld", a[i]);

printf("%s", (i < N - 1) ? " " : "\n");

}

return 0;

}

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

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

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

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

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

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

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

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

[入力例]

6 3

1 4 3

2 2 1

4 6 2

[出力例]

0 1 1 1 0 1

※AtCoderテストケースより

[入力例]

8 2

2 6 1

3 5 3

[出力例]

0 0 1 1 1 0 0 0

※AtCoderテストケースより

[入力例]

10 5

3 7 3

1 6 4

5 5 1

6 8 2

8 10 1

[出力例]

0 0 1 1 1 1 0 1 0 0

[入力例]

25 12

9 13 2

3 5 1

6 18 6

1 6 3

10 22 6

5 18 7

9 11 1

8 15 4

7 25 9

4 5 1

3 17 7

2 11 5

[出力例]

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

■参照サイト
AtCoder Beginner Contest 216

2021年9月11日

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

C++の練習を兼ねて, AtCoder Beginner Contest 216 の問題F (Max Sum Counting) を解いてみた.

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

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

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

// 解き直し.
// https://atcoder.jp/contests/abc216/editorial/2560
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
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 all(x) x.begin(), x.end()
#define a first
#define b second
const LL MOD = 998244353;
LL dp[5050][5050], a[5050], b[5050];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%d", &a[i]);
    rep(i, N) scanf("%d", &b[i]);
    
    // 2. sort.
    vp v;
    rep(i, N) v.pb({a[i], b[i]});
    sort(all(v));
    
    // 3. dp更新.
    // Typical DP Contest (A - コンテスト) を ベース に 実装.
    // https://atcoder.jp/contests/tdpc/tasks/tdpc_contest
    dp[0][0] = 1;
    repx(i, 1, N + 1){
        // 前回分反映.
        rep(j, 5000) dp[i][j] += dp[i - 1][j];
        
        // 今回分反映.
        repr(j, 5000, 0){
            if(j + v[i - 1].b <= 5000){
                dp[i][j + v[i - 1].b] += dp[i][j];
                dp[i][j + v[i - 1].b] %= MOD;
            }
        }
    }
    
    // 4. 集計.
    LL ans = 0;
    // 並び替え前の情報を使っていたので, index も含めて, ロジック修正(000.txt などで, WA版となった).
    // repx(i, 1, N + 1){
    //     rep(j, a[i - 1] - b[i - 1] + 1){
    rep(i, N){
        rep(j, v[i].a - v[i].b + 1){
            ans += dp[i][j];
            ans %= MOD;
        }
    }
    
    // 5. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc216/editorial/2560

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using P = pair<int, int>;

using vp = vector;

#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()

#define a first

#define b second

const LL MOD = 998244353;

LL dp[5050][5050], a[5050], b[5050];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

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

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

// 2. sort.

vp v;

rep(i, N) v.pb({a[i], b[i]});

sort(all(v));

// 3. dp更新.

// Typical DP Contest (A - コンテスト) をベースに実装.

// https://atcoder.jp/contests/tdpc/tasks/tdpc_contest

dp[0][0] = 1;

repx(i, 1, N + 1){

// 前回分反映.

rep(j, 5000) dp[i][j] += dp[i - 1][j];

// 今回分反映.

repr(j, 5000, 0){

if(j + v[i - 1].b <= 5000){

dp[i][j + v[i - 1].b] += dp[i][j];

dp[i][j + v[i - 1].b] %= MOD;

}

// 4. 集計.

LL ans = 0;

// 並び替え前の情報を使っていたので, index も含めて, ロジック修正(000.txt などで, WA版となった).

// repx(i, 1, N + 1){

// rep(j, a[i - 1] - b[i - 1] + 1){

rep(i, N){

rep(j, v[i].a - v[i].b + 1){

ans += dp[i][j];

ans %= MOD;

}

// 5. 出力.

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

return 0;

}

[入力例]
2
3 1
1 2

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

[入力例]
2
1 1
2 2

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

[入力例]
20
1937 3980 2689 1208 3640 1979 581 2271 4229 3948 3708 1522 4161 4661 3797 96 3388 3395 2920 2247
4485 2580 174 1156 3770 3396 3558 3500 3494 479 269 3383 1230 1711 3545 3919 134 475 3796 1017

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

[入力例]
5
11 7 8 10 1
8 8 5 4 1

[出力例]
9

[入力例]
31
41 59 26 53 58 97 93 23 84 62 64 33 83 27 9 50 28 84 19 71 69 39 93 75 10 58 20 97 49 44 59
2 30 78 16 40 62 86 20 89 98 62 80 34 82 53 42 11 70 67 98 21 4 80 86 51 32 82 30 66 4 70

[出力例]
858

[入力例]
50
24 65 106 21 21 8 21 93 35 83 20 21 18 104 82 13 74 53 26 84 94 97 120 44 117 115 109 26 123 11 18 54 106 53 53 79 57 111 29 92 26 25 65 28 55 86 11 76 19 74
14 8 115 35 57 118 76 48 7 41 63 49 41 29 10 51 95 47 95 4 36 106 108 115 70 116 48 62 58 39 81 66 101 53 17 68 73 35 90 9 111 91 20 64 4 96 39 101 30 123

[出力例]
11620

[入力例]
100
1540 1174 910 995 418 1478 131 730 2216 1677 1056 704 648 1114 794 276 1839 297 2082 83 566 913 458 1788 1528 287 281 1475 1998 570 1319 1719 1752 1008 88 953 599 235 1229 2067 1064 1590 306 1747 756 1277 146 1367 539 725 2139 1061 617 395 1947 194 703 100 441 1979 631 1717 1619 463 275 1283 1433 1788 1309 48 867 1758 997 37 1951 54 106 71 1621 1051 1502 1783 593 1097 900 249 511 934 944 1099 1826 1080 1430 1175 486 1056 2202 700 569 1914
1445 1448 56 875 681 807 1791 707 397 1056 1073 866 2079 598 722 1514 490 788 196 93 607 769 685 851 475 703 1924 1606 1414 1291 96 1641 1717 1500 852 1995 1198 469 122 619 2123 1417 277 1321 658 1783 855 1653 1938 752 1011 223 1134 1616 2032 2009 75 1369 114 1775 2126 549 1691 778 412 1636 1404 1822 822 1997 821 168 315 263 529 65 142 393 2090 1871 1385 1702 963 1838 1513 619 1996 1788 1750 180 35 1231 846 24 1355 1463 1354 885 582 674

[出力例]
10146452

[入力例]

3 1

1 2

[出力例]

※AtCoderテストケースより

[入力例]

1 1

2 2

[出力例]

※AtCoderテストケースより

[入力例]

1937 3980 2689 1208 3640 1979 581 2271 4229 3948 3708 1522 4161 4661 3797 96 3388 3395 2920 2247

4485 2580 174 1156 3770 3396 3558 3500 3494 479 269 3383 1230 1711 3545 3919 134 475 3796 1017

[出力例]

476

※AtCoderテストケースより

[入力例]

11 7 8 10 1

8 8 5 4 1

[出力例]

[入力例]

41 59 26 53 58 97 93 23 84 62 64 33 83 27 9 50 28 84 19 71 69 39 93 75 10 58 20 97 49 44 59

2 30 78 16 40 62 86 20 89 98 62 80 34 82 53 42 11 70 67 98 21 4 80 86 51 32 82 30 66 4 70

[出力例]

858

[入力例]

24 65 106 21 21 8 21 93 35 83 20 21 18 104 82 13 74 53 26 84 94 97 120 44 117 115 109 26 123 11 18 54 106 53 53 79 57 111 29 92 26 25 65 28 55 86 11 76 19 74

14 8 115 35 57 118 76 48 7 41 63 49 41 29 10 51 95 47 95 4 36 106 108 115 70 116 48 62 58 39 81 66 101 53 17 68 73 35 90 9 111 91 20 64 4 96 39 101 30 123

[出力例]

11620

[入力例]

100

1540 1174 910 995 418 1478 131 730 2216 1677 1056 704 648 1114 794 276 1839 297 2082 83 566 913 458 1788 1528 287 281 1475 1998 570 1319 1719 1752 1008 88 953 599 235 1229 2067 1064 1590 306 1747 756 1277 146 1367 539 725 2139 1061 617 395 1947 194 703 100 441 1979 631 1717 1619 463 275 1283 1433 1788 1309 48 867 1758 997 37 1951 54 106 71 1621 1051 1502 1783 593 1097 900 249 511 934 944 1099 1826 1080 1430 1175 486 1056 2202 700 569 1914

1445 1448 56 875 681 807 1791 707 397 1056 1073 866 2079 598 722 1514 490 788 196 93 607 769 685 851 475 703 1924 1606 1414 1291 96 1641 1717 1500 852 1995 1198 469 122 619 2123 1417 277 1321 658 1783 855 1653 1938 752 1011 223 1134 1616 2032 2009 75 1369 114 1775 2126 549 1691 778 412 1636 1404 1822 822 1997 821 168 315 263 529 65 142 393 2090 1871 1385 1702 963 1838 1513 619 1996 1788 1750 180 35 1231 846 24 1355 1463 1354 885 582 674

[出力例]

10146452

■参照サイト
AtCoder Beginner Contest 216

2021年9月10日

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

C++の練習を兼ねて, AtCoder Beginner Contest 216 の問題E (Amusement Park) を解いてみた.

■感想.
1. 問題E は, 方針が見えなかったので, 解説を参考に実装したところ, AC版に到達出来た.
2. 二分探索の復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/abc216/editorial/2469
// 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[101010];

int main(){
    
    // 1. 入力情報.
    int N;
    LL K, b = 0, bSum = 0;
    scanf("%d %lld", &N, &K);
    rep(i, N){
        scanf("%lld", &a[i]);
        b += a[i];
        bSum += (a[i] + 1) * a[i] / 2;
    }
    
    // 2. 数列B の 項数が, K以下.
    if(b <= K){
        printf("%lld\n", bSum);
        return 0;
    }
    
    // 3. 評価関数.
    auto f = [&](LL m) -> bool {
        // 3-1. 数列B で, m以上となる個数.
        LL ret = 0;
        rep(i, N) ret += max(a[i] - m + 1, 0LL);
        
        // 3-2. 判定結果.
        return (ret <= K);
    };
    
    // 4. 二分探索で確認してみる.
    LL l = 1, h = 2e9 + 1, m;
    while(l + 1 < h){
        LL m = (h + l) >> 1;
        if(f(m)) h = m;
        else     l = m;
        // printf("h=%d l=%d m=%d\n", h, l, m);
    }
    
    // 5. 集計.
    LL t = 0, ans = 0;
    rep(i, N){
        if(a[i] >= h){
            ans += (h + a[i]) * (a[i] - h + 1) / 2; // 合計.
            t += (a[i] - h + 1);                    // 項数.
        }
    }
    
    // 6. 残り.
    if(t < K) ans += (h - 1) * (K - t);
    
    // 7. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc216/editorial/2469

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

int main(){

// 1. 入力情報.

int N;

LL K, b = 0, bSum = 0;

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

rep(i, N){

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

b += a[i];

bSum += (a[i] + 1) * a[i] / 2;

}

// 2. 数列B の項数が, K以下.

if(b <= K){

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

return 0;

}

// 3. 評価関数.

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

// 3-1. 数列B で, m以上となる個数.

LL ret = 0;

rep(i, N) ret += max(a[i] - m + 1, 0LL);

// 3-2. 判定結果.

return (ret <= K);

};

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

LL l = 1, h = 2e9 + 1, m;

while(l + 1 < h){

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

if(f(m)) h = m;

else l = m;

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

}

// 5. 集計.

LL t = 0, ans = 0;

rep(i, N){

if(a[i] >= h){

ans += (h + a[i]) * (a[i] - h + 1) / 2; // 合計.

t += (a[i] - h + 1); // 項数.

}

// 6. 残り.

if(t < K) ans += (h - 1) * (K - t);

// 7. 出力.

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

return 0;

}

[入力例]
3 5
100 50 102

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

[入力例]
2 2021
2 3

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

[入力例]
1 5
7

[出力例]
25

[入力例]
3 5
7 5 3

[出力例]
27

[入力例]
10 314
5 75 74 87 48 102 35 18 41 21

[出力例]
15734

[入力例]
20 2021
113 23 11 120 50 116 38 168 140 169 205 190 144 81 154 169 149 210 142 180

[出力例]
192343

[入力例]
50 20210910
5511573 1823734 1537335 3718321 5263474 1794118 2046166 3165523 1869164 1553963 1194575 1642020 5484771 2214363 692014 1043993 909762 3261784 4060954 4078088 3464262 2525049 3121061 2078598 3962003 332254 1136135 4933593 4628158 4264588 3350207 4356224 3950236 2563276 4359650 4760678 2248995 1177972 2608249 389230 3856211 1569739 1668055 1712937 2083808 4737499 5340644 4022180 466263 3292659

[出力例]
82888537486520

[入力例]

3 5

100 50 102

[出力例]

502

※AtCoderテストケースより

[入力例]

2 2021

2 3

[出力例]

※AtCoderテストケースより

[入力例]

1 5

[出力例]

[入力例]

3 5

7 5 3

[出力例]

[入力例]

10 314

5 75 74 87 48 102 35 18 41 21

[出力例]

15734

[入力例]

20 2021

113 23 11 120 50 116 38 168 140 169 205 190 144 81 154 169 149 210 142 180

[出力例]

192343

[入力例]

50 20210910

5511573 1823734 1537335 3718321 5263474 1794118 2046166 3165523 1869164 1553963 1194575 1642020 5484771 2214363 692014 1043993 909762 3261784 4060954 4078088 3464262 2525049 3121061 2078598 3962003 332254 1136135 4933593 4628158 4264588 3350207 4356224 3950236 2563276 4359650 4760678 2248995 1177972 2608249 389230 3856211 1569739 1668055 1712937 2083808 4737499 5340644 4022180 466263 3292659

[出力例]

82888537486520

■参照サイト
AtCoder Beginner Contest 216

2021年9月9日

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

C++の練習を兼ねて, AtCoder Beginner Contest 216 の問題C (Many Balls) ～問題D (Pair of Balls) を解いてみた.

■感想.
1. 問題D は, 方針が見えなかったので, 解説を参考に実装したところ, AC版に到達出来た.
2. 問題D で, 計算量を減らすための, キューの利用方法が, 大変勉強になったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

■C++版プログラム(問題C／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--)

int main(){
    
    // 1. 入力情報.
    LL N;
    scanf("%lld", &N);
    
    // 2. 魔法を使ってみる.
    string ans = "";
    while(N){
        ans = ((N % 2 > 0) ? "A" : "B") + ans;
        if(N % 2 > 0) N--;
        else          N >>= 1;
    }
    
    // 3. 出力.
    printf("%s\n", ans.c_str());
    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--)

int main(){

// 1. 入力情報.

LL N;

scanf("%lld", &N);

// 2. 魔法を使ってみる.

string ans = "";

while(N){

ans = ((N % 2 > 0) ? "A" : "B") + ans;

if(N % 2 > 0) N--;

else N >>= 1;

}

// 3. 出力.

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

return 0;

}

[入力例]
5

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

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

[入力例]
14

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

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

[入力例]
2021

[出力例]
ABABABABABABBBABBA

[入力例]
20210909

[出力例]
ABBBABABBABBBBABABBBABBBABABBABABABBA

[入力例]
999999999999999999

[出力例]
ABABBABABABABBBBBBABBABABBABABBABBABABBBABABABBABBBABABABBABABBBBABABABABABABABABABABABABABABABABABA

[入力例]
1000000000000000000

[出力例]
ABABBABABABABBBBBBABBABABBABABBABBABABBBABABABBABBBABABABBABABBBABBBBBBBBBBBBBBBBBB

[入力例]

[出力例]

AABA

※AtCoderテストケースより

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

ABBA

[入力例]

[出力例]

BBABBAAAB

※AtCoderテストケースより

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

ABABAB

[入力例]

2021

[出力例]

ABABABABABABBBABBA

[入力例]

20210909

[出力例]

ABBBABABBABBBBABABBBABBBABABBABABABBA

[入力例]

999999999999999999

[出力例]

ABABBABABABABBBBBBABBABABBABABBABBABABBBABABABBABBBABABABBABABBBBABABABABABABABABABABABABABABABABABA

[入力例]

1000000000000000000

[出力例]

ABABBABABABABBBBBBABBABABBABABBABBABABBBABABABBABBBABABABBABABBBABBBBBBBBBBBBBBBBBB

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

// 解き直し.
// https://atcoder.jp/contests/abc216/editorial/2559
// 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 pof pop_front
#define pub push_back
int c[202020];

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    vector<deque<int>> v(M), b(N);
    rep(i, M){
        int k;
        scanf("%d", &k);
        rep(j, k){
            int a;
            scanf("%d", &a);
            a--;
            v[i].pub(a); // i番目の筒に保存.
            b[a].pub(i); // 色 a のボールに, 筒の番号 i を保存.
        }
    }
    
    // 2. 筒を順番に見ていく.
    deque<int> dq;
    rep(i, M){
        // 2-1. ボールを取得.
        int t = v[i].front();
        c[t]++;
        
        // 2-2. キューに追加.
        if(c[t] == 2) dq.pub(t);
        
        // 2-3. キューが空になるまで, 筒からボールを取り除く.
        while(!dq.empty()){
            // ボールを取得.
            int u = dq.front();
            dq.pof();
            
            // 筒番号を取得.
            int p1 = b[u].front();
            b[u].pof();
            int p2 = b[u].front();
            b[u].pof();
            
            // 筒から除去.
            v[p1].pof();
            v[p2].pof();
            
            // 筒から, 一番上のボールを取得.
            int b1 = -1;
            int b2 = -1;
            if(!v[p1].empty()) b1 = v[p1].front();
            if(!v[p2].empty()) b2 = v[p2].front();
            
            // 取得したボールの出現回数を確認し, 二回であれば, キューに追加.
            if(b1 != -1){
                c[b1]++;
                if(c[b1] == 2) dq.pub(b1);
            }
            if(b2 != -1){
                c[b2]++;
                if(c[b2] == 2) dq.pub(b2);
            }
        }
    }
    
    // 3. 判定.
    bool ok = true;
    rep(i, N) if(c[i] != 2) ok = false;
    
    // 4. 出力.
    printf("%s\n", ok ? "Yes" : "No");
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc216/editorial/2559

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

#define pub push_back

int c[202020];

int main(){

// 1. 入力情報.

int N, M;

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

vector<deque<int>> v(M), b(N);

rep(i, M){

int k;

scanf("%d", &k);

rep(j, k){

int a;

scanf("%d", &a);

a--;

v[i].pub(a); // i番目の筒に保存.

b[a].pub(i); // 色 a のボールに, 筒の番号 i を保存.

}

// 2. 筒を順番に見ていく.

deque<int> dq;

rep(i, M){

// 2-1. ボールを取得.

int t = v[i].front();

c[t]++;

// 2-2. キューに追加.

if(c[t] == 2) dq.pub(t);

// 2-3. キューが空になるまで, 筒からボールを取り除く.

while(!dq.empty()){

// ボールを取得.

int u = dq.front();

dq.pof();

// 筒番号を取得.

int p1 = b[u].front();

b[u].pof();

int p2 = b[u].front();

b[u].pof();

// 筒から除去.

v[p1].pof();

v[p2].pof();

// 筒から, 一番上のボールを取得.

int b1 = -1;

int b2 = -1;

if(!v[p1].empty()) b1 = v[p1].front();

if(!v[p2].empty()) b2 = v[p2].front();

// 取得したボールの出現回数を確認し, 二回であれば, キューに追加.

if(b1 != -1){

c[b1]++;

if(c[b1] == 2) dq.pub(b1);

}

if(b2 != -1){

c[b2]++;

if(c[b2] == 2) dq.pub(b2);

}

// 3. 判定.

bool ok = true;

rep(i, N) if(c[i] != 2) ok = false;

// 4. 出力.

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

return 0;

}

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

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

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

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

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

[出力例]
Yes

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

[出力例]
No

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

[出力例]
Yes

[入力例]

2 2

1 2

[出力例]

Yes

※AtCoderテストケースより

[入力例]

2 2

1 2

2 1

[出力例]

※AtCoderテストケースより

[入力例]

10 6

9 4 2 1

10 9 8 4 2

5 3 1

8 6 5 3

7 6

10 7

[出力例]

Yes

[入力例]

3 3

2 1

3 2

1 3

[出力例]

[入力例]

25 10

17 9 1

22 9 6 2

25 23 17 16 14 10 5 1

24 20 16 8 2

18 14 11 6 3

19 18 15 10 8 3 4

24 22 19 15 13 12 11 7 4

23 20 12 5

21 13 7

25 21

[出力例]

Yes

■参照サイト
AtCoder Beginner Contest 216

2021年9月7日

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

C++の練習を兼ねて, AtCoder Beginner Contest 217 の問題F (Make Pair) を解いてみた.

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

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

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

// 解き直し.
// https://atcoder.jp/contests/abc217/editorial/2584
// 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 LIMIT = 1010;
LL FAC[LIMIT], INV[LIMIT];
int f[808][808];
LL dp[808][808];

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

// 組み合わせ(nCk)計算用(mod版).
// ※配列FAC, INV は, 事前に計算済のものを使う.
// @param n: 対象となる要素の個数.
// @param k: 選択する要素の個数.
// @return: 組み合わせ(nCk)の計算結果(mod版).
LL combination(LL n, LL k){
    if(n < 0 || k < 0 || k > n) return 0LL;
    // k = 0 で, 256423756 (※挙動がおかしい) が 出力されたため, ロジック修正.
    if(n == k || k == 0LL) return 1LL;
    LL ret = FAC[n] * INV[k] % MOD * INV[n - k] % MOD;
    return ret;
}

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    rep(i, M){
        int a, b;
        scanf("%d %d", &a, &b);
        f[a][b] = 1;
        f[b][a] = 1;
    }
    
    // 2. 事前計算.
    FAC[0] = 1;
    repx(i, 1, LIMIT) FAC[i] = (LL)i * FAC[i - 1] % MOD;
    rep(i, LIMIT)     INV[i] = mPow(FAC[i], MOD - 2);
    
    // 3. dp更新.
    rep(i, N * 2 + 1) dp[i][0] = 1;
    repx(j, 1, N * 2 + 1){
        rep(i, N * 2 + 1){
            repx(k, 1, j + 1){
                LL a1 = dp[i + 1][k - 1];
                LL a2 = dp[i + k * 2][j - k];
                LL a3 = combination((LL)j, (LL)k);
                LL a4 = f[i + 1][i + k * 2];
                dp[i][j] += a1 * a2 % MOD * a3 % MOD * a4;
                dp[i][j] %= MOD;
            }
        }
    }
    
    // 4. 出力.
    printf("%lld\n", dp[0][N]);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc217/editorial/2584

// 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 LIMIT = 1010;

LL FAC[LIMIT], INV[LIMIT];

int f[808][808];

LL dp[808][808];

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

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

// @param b: 指数.

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

LL mPow(LL a, LL b){

LL t = 1;

while(b){

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

a = a * a % MOD;

b >>= 1;

}

return t % MOD;

}

// 組み合わせ(nCk)計算用(mod版).

// ※配列FAC, INV は, 事前に計算済のものを使う.

// @param n: 対象となる要素の個数.

// @param k: 選択する要素の個数.

// @return: 組み合わせ(nCk)の計算結果(mod版).

LL combination(LL n, LL k){

if(n < 0 || k < 0 || k > n) return 0LL;

// k = 0 で, 256423756 (※挙動がおかしい) が出力されたため, ロジック修正.

if(n == k || k == 0LL) return 1LL;

LL ret = FAC[n] * INV[k] % MOD * INV[n - k] % MOD;

return ret;

}

int main(){

// 1. 入力情報.

int N, M;

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

rep(i, M){

int a, b;

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

f[a][b] = 1;

f[b][a] = 1;

}

// 2. 事前計算.

FAC[0] = 1;

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

rep(i, LIMIT) INV[i] = mPow(FAC[i], MOD - 2);

// 3. dp更新.

rep(i, N * 2 + 1) dp[i][0] = 1;

repx(j, 1, N * 2 + 1){

rep(i, N * 2 + 1){

repx(k, 1, j + 1){

LL a1 = dp[i + 1][k - 1];

LL a2 = dp[i + k * 2][j - k];

LL a3 = combination((LL)j, (LL)k);

LL a4 = f[i + 1][i + k * 2];

dp[i][j] += a1 * a2 % MOD * a3 % MOD * a4;

dp[i][j] %= MOD;

}

// 4. 出力.

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

return 0;

}

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

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

[入力例]
2 2
1 2
3 4

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

[入力例]
2 2
1 3
2 4

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

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

[出力例]
30

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

[出力例]
604800

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

[出力例]
883463798

100

[入力例]

2 3

1 2

1 4

2 3

[出力例]

※AtCoderテストケースより

[入力例]

2 2

1 2

3 4

[出力例]

※AtCoderテストケースより

[入力例]

2 2

1 3

2 4

[出力例]

※AtCoderテストケースより

[入力例]

5 5

1 2

3 6

4 5

7 10

8 9

[出力例]

[入力例]

10 15

1 6

2 3

4 5

7 10

8 9

11 12

13 14

15 16

17 20

18 19

11 14

12 13

15 20

16 19

17 18

[出力例]

604800

[入力例]

20 35

1 2

3 4

5 6

7 8

9 10

11 12

13 14

15 16

17 18

19 20

21 22

23 24

25 26

27 28

29 30

31 32

33 34

35 36

37 38

39 40

1 10

8 9

2 7

3 6

4 5

11 30

12 29

13 28

14 27

15 26

16 25

17 24

18 23

19 22

20 21

[出力例]

883463798

■参照サイト
AtCoder Beginner Contest 217

2021年9月6日

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

C++の練習を兼ねて, AtCoder Beginner Contest 217 の問題E (Sorting Queries) を解いてみた.

■感想.
1. 問題E は, 方針を絞り込めたので, AC版に到達出来たと思う.
2. 優先順位付きキューの復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

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

int main(){
    
    // 1. 入力情報.
    int Q;
    scanf("%d", &Q);
    
    // 2. クエリ回答.
    priority_queue<int, vector<int>, greater<int>> pq;
    deque<int> dq;
    rep(i, Q){
        // 2-1. クエリ入力情報.
        int c;
        scanf("%d", &c);
        
        // 2-2. c = 1 の 場合(末尾に追加).
        if(c == 1){
            int x;
            scanf("%d", &x);
            dq.pub(x);
        }
        
        // 2-3. c = 2 の 場合(先頭要素を出力).
        if(c == 2){
            int ans = 0;
            if(!pq.empty()){
                ans = pq.top();
                pq.pop();
            }else{
                ans = dq.front();
                dq.pof();
            }
            printf("%d\n", ans);
        }
        
        // 2-4. c = 3 の 場合(昇順sort).
        if(c == 3){
            while(!dq.empty()){
                pq.push(dq.front());
                dq.pop_front();
            }
        }
    }
    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 pof pop_front

#define pub push_back

int main(){

// 1. 入力情報.

int Q;

scanf("%d", &Q);

// 2. クエリ回答.

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

deque<int> dq;

rep(i, Q){

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

int c;

scanf("%d", &c);

// 2-2. c = 1 の場合(末尾に追加).

if(c == 1){

int x;

scanf("%d", &x);

dq.pub(x);

}

// 2-3. c = 2 の場合(先頭要素を出力).

if(c == 2){

int ans = 0;

if(!pq.empty()){

ans = pq.top();

pq.pop();

}else{

ans = dq.front();

dq.pof();

}

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

}

// 2-4. c = 3 の場合(昇順sort).

if(c == 3){

while(!dq.empty()){

pq.push(dq.front());

dq.pop_front();

}

return 0;

}

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

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

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

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

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

[出力例]
11
1
0
2
3
5
0

[入力例]

1 4

1 3

1 2

1 1

1 0

[出力例]

※AtCoderテストケースより

[入力例]

1 5

1 3

1 6

[出力例]

※AtCoderテストケースより

[入力例]

1 11

1 9

1 5

1 2

1 1

1 3

1 0

1 7

1 11

1 5

1 6

1 3

1 10

1 0

1 5

[出力例]

■参照サイト
AtCoder Beginner Contest 217

2021年9月6日2021年9月6日

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

C++の練習を兼ねて, AtCoder Beginner Contest 217 の問題C (Inverse of Permutation) ～問題D (Cutting Woods) を解いてみた.

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

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

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

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

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N){
        int p;
        scanf("%d", &p);
        q[p - 1] = i + 1;
    }
    
    // 2. 出力.
    rep(i, N){
        printf("%d", q[i]);
        printf("%s", (i < N - 1) ? " " : "\n");
    }
    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 q[202020];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

rep(i, N){

int p;

scanf("%d", &p);

q[p - 1] = i + 1;

}

// 2. 出力.

rep(i, N){

printf("%d", q[i]);

printf("%s", (i < N - 1) ? " " : "\n");

}

return 0;

}

[入力例]
3
2 3 1

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

[入力例]
3
1 2 3

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

[入力例]
5
5 3 2 4 1

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

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

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

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

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

[入力例]

2 3 1

[出力例]

3 1 2

※AtCoderテストケースより

[入力例]

1 2 3

[出力例]

1 2 3

※AtCoderテストケースより

[入力例]

5 3 2 4 1

[出力例]

5 3 2 4 1

※AtCoderテストケースより

[入力例]

2 1 4 3 6 5 7

[出力例]

2 1 4 3 6 5 7

[入力例]

3 12 8 9 5 7 10 11 1 4 6 2

[出力例]

9 12 1 10 5 11 6 3 4 7 8 2

■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 main(){
    
    // 1. 入力情報.
    int L, Q;
    scanf("%d %d", &L, &Q);
    set<int> st;
    st.insert(0);
    st.insert(L);
    
    // 2. クエリ回答.
    rep(i, Q){
        // 2-1. クエリ入力情報.
        int c, x;
        scanf("%d %d", &c, &x);
        
        // 2-2. c = 1 の 場合.
        if(c == 1) st.insert(x);
        
        // 2-3. c = 2 の 場合.
        if(c == 2){
            decltype(st)::iterator itr = st.lower_bound(x);
            int r = *itr;
            int l = *(--itr);
            printf("%d\n", r - l);
        }
    }
    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 main(){

// 1. 入力情報.

int L, Q;

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

set<int> st;

st.insert(0);

st.insert(L);

// 2. クエリ回答.

rep(i, Q){

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

int c, x;

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

// 2-2. c = 1 の場合.

if(c == 1) st.insert(x);

// 2-3. c = 2 の場合.

if(c == 2){

decltype(st)::iterator itr = st.lower_bound(x);

int r = *itr;

int l = *(--itr);

printf("%d\n", r - l);

}

return 0;

}

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

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

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

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

[入力例]
100 10
1 31
2 41
1 59
2 26
1 53
2 58
1 97
2 93
1 23
2 84

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

[入力例]
200 20
1 172
2 99
1 54
2 121
2 169
1 3
2 178
1 65
2 128
1 165
2 187
1 44
2 199
1 117
1 88
1 196
1 77
2 1
2 123
2 85

[出力例]
172
118
118
28
107
28
28
3
48
11

[入力例]

5 3

2 2

1 3

2 2

[出力例]

※AtCoderテストケースより

[入力例]

5 3

1 2

1 4

2 3

[出力例]

※AtCoderテストケースより

[入力例]

100 10

1 31

2 41

1 59

2 26

1 53

2 58

1 97

2 93

1 23

2 84

[出力例]

※AtCoderテストケースより

[入力例]

200 20

1 172

2 99

1 54

2 121

2 169

1 3

2 178

1 65

2 128

1 165

2 187

1 44

2 199

1 117

1 88

1 196

1 77

2 1

2 123

2 85

[出力例]

172

118

107

■参照サイト
AtCoder Beginner Contest 217

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

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

C++の練習を兼ねて, AtCoder Beginner Contest 218 の 問題C (Shapes) ～ 問題D (Rectangles) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 216 の 問題G (01Sequence) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 216 の 問題F (Max Sum Counting) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 216 の 問題E (Amusement Park) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 216 の 問題C (Many Balls) ～ 問題D (Pair of Balls) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 217 の 問題F (Make Pair) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 217 の 問題E (Sorting Queries) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 217 の 問題C (Inverse of Permutation) ～ 問題D (Cutting Woods) を解いてみた.

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

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

C++の練習を兼ねて, AtCoder Beginner Contest 218 の問題C (Shapes) ～問題D (Rectangles) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 216 の問題G (01Sequence) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 216 の問題F (Max Sum Counting) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 216 の問題E (Amusement Park) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 216 の問題C (Many Balls) ～問題D (Pair of Balls) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 217 の問題F (Make Pair) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 217 の問題E (Sorting Queries) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 217 の問題C (Inverse of Permutation) ～問題D (Cutting Woods) を解いてみた.

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