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

C++の練習を兼ねて, AtCoder Regular Contest 068 の問題E (Snuke Line) を解いてみた.

■感想.
1. 問題Eは, 方針が見えなかったので, 解説を参考に実装して, AC版に到達できたので, 良かったと思う.
2. 遅延評価セグメント木が必要なため, 下記のライブラリを拝借させて頂いた.
3. 遅延評価セグメント木が復習できたので, 非常に良かったと思う.
4. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/arc068/editorial.pdf
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;
using vi = vector<int>;
using vp = vector<P>;
using vvp = vector<vp>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define a first
#define b second
#define pb push_back
int l[303030], r[303030], iCum[101010];

// ※※※ 以下のライブラリを使用(一部改変) ※※※.
// 遅延評価セグメント木をソラで書きたいあなたに.
// http://tsutaj.hatenablog.com/entry/2017/03/30/224339
// http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2236726
struct LazySegmentTree{
private:
    int n;
    vi node, lazy;
public:
    LazySegmentTree(vi v){
        int sz = (int)v.size();
        n = 1; while(n < sz) n *= 2;
        node.resize(2 * n - 1);
        lazy.resize(2 * n - 1, 0);
        rep(i, sz) node[i + n - 1] = v[i];
        repr(i, n - 2, 0) node[i] = node[i * 2 + 1] + node[i * 2 + 2];
    }
    void eval(int k, int l, int r){
        if(lazy[k] != 0) {
            node[k] += lazy[k];
            if(r - l > 1) {
                lazy[2 * k + 1] += lazy[k] / 2;
                lazy[2 * k + 2] += lazy[k] / 2;
            }
            lazy[k] = 0;
        }
    }
    void update(int a, int b, int x, int k = 0, int l = 0, int r = -1){
        if(r < 0) r = n;
        eval(k, l, r);
        if(b <= l || r <= a) return;
        if(a <= l && r <= b){
            lazy[k] += (r - l) * x;
            eval(k, l, r);
        }else{
            update(a, b, x, 2 * k + 1,           l, (l + r) / 2);
            update(a, b, x, 2 * k + 2, (l + r) / 2,           r);
            node[k] = node[2 * k + 1] + node[2 * k + 2];
        }
    }
    int query(int a, int b, int k = 0, int l = 0, int r = -1){
        if(r < 0) r = n;
        eval(k, l, r);
        if(b <= l || r <= a) return 0;
        if(a <= l && r <= b) return node[k];
        int vl = query(a, b, 2 * k + 1,           l, (l + r) / 2);
        int vr = query(a, b, 2 * k + 2, (l + r) / 2,           r);
        return vl + vr;
    }

};

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    set<int> st;
    rep(i, N){
        scanf("%d %d", &l[i], &r[i]);
        int d = r[i] - l[i] + 1;
        st.insert(d); // 区間幅の種類を保存.
        iCum[d]++;    // 区間幅の個数を保存.
    }
    
    // 2. 区間幅に, indexを割り当て.
    int idx = -1;
    map<int, int> m;
    for(auto &p : st) m[p] = ++idx;
    
    // 3. 区間を長さごとに分類.
    vvp v(idx + 1);
    rep(i, N){
        int d = r[i] - l[i] + 1;
        v[m[d]].pb({l[i], r[i]});
    }
    
    // 4. 累積和.
    rep(i, M) iCum[i + 1] += iCum[i];
    
    // 5. 各間隔 d について, 購入可能な名産品の種類数を計算.
    // 解説上, Binary Indexed Tree (Fenwick Tree) を使う方針が示されていたが, 
    // 実装方法が見えなかったので, LazySegmentTree による実装で対応した.
    LazySegmentTree seg(vi(M + 1, 0));
    int k = 0;
    repx(d, 1, M + 1){
        // 5-1. 必ず, 1回以上訪問する区間.
        int ans = iCum[M] - iCum[d];
        
        // 5-2. 最大でも, 1回しか訪問できない区間.
        if(k <= idx && v[k][0].b - v[k][0].a + 1 <= d){
            // 区間への加算.
            rep(i, v[k].size()) seg.update(v[k][i].a, v[k][i].b + 1, 1);
            
            // インクリメント.
            k++;
        }
        
        // 5-3. 駅番号 が dの倍数 における 種類数 を カウント.
        repex(i, d, M + 1, d) ans += seg.query(i, i + 1);
        
        // 5-4. 出力.
        printf("%d\n", ans);
    }
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using P = pair<int, int>;

using vi = vector<int>;

using vp = vector<P>;

using vvp = vector<vp>;

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

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

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

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

#define a first

#define b second

#define pb push_back

int l[303030], r[303030], iCum[101010];

// ※※※ 以下のライブラリを使用(一部改変) ※※※.

// 遅延評価セグメント木をソラで書きたいあなたに.

// http://tsutaj.hatenablog.com/entry/2017/03/30/224339

// http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2236726

struct LazySegmentTree{

private:

int n;

vi node, lazy;

public:

LazySegmentTree(vi v){

int sz = (int)v.size();

n = 1; while(n < sz) n *= 2;

node.resize(2 * n - 1);

lazy.resize(2 * n - 1, 0);

rep(i, sz) node[i + n - 1] = v[i];

repr(i, n - 2, 0) node[i] = node[i * 2 + 1] + node[i * 2 + 2];

}

void eval(int k, int l, int r){

if(lazy[k] != 0) {

node[k] += lazy[k];

if(r - l > 1) {

lazy[2 * k + 1] += lazy[k] / 2;

lazy[2 * k + 2] += lazy[k] / 2;

}

lazy[k] = 0;

}

void update(int a, int b, int x, int k = 0, int l = 0, int r = -1){

if(r < 0) r = n;

eval(k, l, r);

if(b <= l || r <= a) return;

if(a <= l && r <= b){

lazy[k] += (r - l) * x;

eval(k, l, r);

}else{

update(a, b, x, 2 * k + 1, l, (l + r) / 2);

update(a, b, x, 2 * k + 2, (l + r) / 2, r);

node[k] = node[2 * k + 1] + node[2 * k + 2];

}

int query(int a, int b, int k = 0, int l = 0, int r = -1){

if(r < 0) r = n;

eval(k, l, r);

if(b <= l || r <= a) return 0;

if(a <= l && r <= b) return node[k];

int vl = query(a, b, 2 * k + 1, l, (l + r) / 2);

int vr = query(a, b, 2 * k + 2, (l + r) / 2, r);

return vl + vr;

}

};

int main(){

// 1. 入力情報.

int N, M;

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

set<int> st;

rep(i, N){

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

int d = r[i] - l[i] + 1;

st.insert(d); // 区間幅の種類を保存.

iCum[d]++; // 区間幅の個数を保存.

}

// 2. 区間幅に, indexを割り当て.

int idx = -1;

map<int, int> m;

for(auto &p : st) m[p] = ++idx;

// 3. 区間を長さごとに分類.

vvp v(idx + 1);

rep(i, N){

int d = r[i] - l[i] + 1;

v[m[d]].pb({l[i], r[i]});

}

// 4. 累積和.

rep(i, M) iCum[i + 1] += iCum[i];

// 5. 各間隔 d について, 購入可能な名産品の種類数を計算.

// 解説上, Binary Indexed Tree (Fenwick Tree) を使う方針が示されていたが,

// 実装方法が見えなかったので, LazySegmentTree による実装で対応した.

LazySegmentTree seg(vi(M + 1, 0));

int k = 0;

repx(d, 1, M + 1){

// 5-1. 必ず, 1回以上訪問する区間.

int ans = iCum[M] - iCum[d];

// 5-2. 最大でも, 1回しか訪問できない区間.

if(k <= idx && v[k][0].b - v[k][0].a + 1 <= d){

// 区間への加算.

rep(i, v[k].size()) seg.update(v[k][i].a, v[k][i].b + 1, 1);

// インクリメント.

k++;

}

// 5-3. 駅番号が dの倍数における種類数をカウント.

repex(i, d, M + 1, d) ans += seg.query(i, i + 1);

// 5-4. 出力.

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

}

return 0;

}

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

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

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

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

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

[出力例]
15
15
14
14
11
12
7
5
3
5
7
7
6
3
2

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

[出力例]
33
33
33
30
28
25
19
16
17
20
19
15
9
4
3
2
2
2
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

[入力例]

3 3

1 2

2 3

3 3

[出力例]

※AtCoderのテストケースより

[入力例]

7 9

1 7

5 9

5 7

5 9

1 1

6 8

3 4

[出力例]

※AtCoderのテストケースより

[入力例]

15 15

2 5

3 8

10 15

1 3

11 15

3 6

8 13

10 12

4 5

10 13

6 8

11 14

4 9

11 13

6 10

[出力例]

[入力例]

33 19

9 13

2 4

1 5

7 12

5 13

10 12

10 19

9 11

4 7

11 12

4 8

6 13

11 13

9 13

2 8

7 12

10 18

3 11

10 12

1 4

9 11

2 10

7 14

8 15

3 4

1 8

4 7

10 12

3 5

5 7

3 11

6 10

7 10

[出力例]

■参照サイト
AtCoder Regular Contest 068
遅延評価セグメント木をソラで書きたいあなたに

C++の練習を兼ねて, AtCoder Regular Contest 068 の 問題E (Snuke Line) を解いてみた.

コメントを残す コメントをキャンセル

C++の練習を兼ねて, AtCoder Regular Contest 068 の問題E (Snuke Line) を解いてみた.

コメントを残すコメントをキャンセル