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

C++の練習を兼ねて, AtCoder Regular Contest 080 の問題E (Young Maids)を解いてみた.

■感想.
1. 問題Eは, 方針が見えなかったので, 解説を参考に実装して, AC版に到達できたので, 良かったと思う.
2. 実装に苦労したものの, 個人的には, 非常に面白い問題に感じた.
※ 公式のライブラリを拝借させて頂いてます.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/arc080/editorial.pdf
// 参考資料.
// https://atcoder.jp/contests/pakencamp-2020-day1/editorial/527
// 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
const int INF = 2020202020;
int p[202020], pos[202020];

struct section{
    int l, r, a; // 半開区間[l, r) と, 区間内 の 偶数番目の最小値 を 保存.
    bool operator < (const section& rhs) const{
        return a > rhs.a;
    }
};

// AtCoder Library(https://github.com/atcoder/ac-library/blob/master/atcoder/segtree.hpp)
// -> 一部改変(2021/02/05).
template<class S, S (*op)(S, S), S (*e)()> struct SegmentTree{
public:
    SegmentTree() : SegmentTree(0){}
    explicit SegmentTree(int n) : SegmentTree(vector<S>(n, e())){}
    explicit SegmentTree(const vector<S>& v) : _n(int(v.size())){
        log = 0;
        while((1 << log) < _n) log++;
        size = 1 << log;
        d = vector<S>(2 * size, e());
        rep(i, _n) d[size + i] = v[i];
        repr(i, size - 1, 1) update(i);
    }
    void set(int p, S x){
        assert(0 <= p && p < _n);
        p += size;
        d[p] = x;
        repx(i, 1, log + 1) update(p >> i);
    }
    S get(int p){
        assert(0 <= p && p < _n);
        return d[p + size];
    }
    S prod(int l, int r){
        assert(0 <= l && l <= r && r <= _n);
        S sml = e(), smr = e();
        l += size;
        r += size;
        while(l < r){
            if(l & 1) sml = op(sml, d[l++]);
            if(r & 1) smr = op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }
        return op(sml, smr);
    }
    S all_prod(){
        return d[1];
    }
private:
    int _n, size, log;
    vector<S> d;
    void update(int k){
        d[k] = op(d[2 * k], d[2 * k + 1]);
    }
};

static int RMiQ_nodef(int l, int r){
    return min(l, r);
}
static int RMiQ_ef(){
    return INF;
}
using RMiQ = SegmentTree<int, RMiQ_nodef, RMiQ_ef>;

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N){
        scanf("%d", &p[i]);
        pos[p[i]] = i; // p[i] の 出現位置.
    }
    
    // 2. 前処理.
    RMiQ eSeg(N + 2); // 偶数番目だけ保存.
    RMiQ oSeg(N + 2); // 奇数番目だけ保存.
    rep(i, N){
        if(i & 1) oSeg.set(i, p[i]);
        else      eSeg.set(i, p[i]);
    }
    
    // 3. 操作を繰り返す.
    vector<int> q;
    priority_queue<section> pq;
    
    // 3-1. 全区間を保存.
    int qe = 0, posQe = 0, qo = 0, posQo = 0;
    section s;
    s.l = 0, s.r = N, s.a = eSeg.prod(s.l, s.r);
    pq.push(s);
    while(!pq.empty() && q.size() < N){
        // 3-2. 区間を一つ取り出す.
        s = pq.top();
        pq.pop();
        
        // 偶数番目を見る.
        if(s.r > s.l){
            // 3-3. 最小の要素は？
            if(s.l & 1) qe = oSeg.prod(s.l, s.r);
            else        qe = eSeg.prod(s.l, s.r);
            
            // 3-4. 最小の要素の出現場所は？
            posQe = pos[qe];
            
            // 3-5. 数列 q に追加.
            q.pb(qe);
        }
        
        // 奇数番目を見る.
        if(s.r > posQe + 1){
            // 3-6. 最小の要素は？
            if(s.l & 1) qo = eSeg.prod(posQe + 1, s.r);
            else        qo = oSeg.prod(posQe + 1, s.r);
            
            // 3-7. 最小の要素の出現場所は？
            posQo = pos[qo];
            
            // 3-8. 数列 q に追加.
            q.pb(qo);
        }
        // printf("qe=%d posQe=%d qo=%d posQo=%d\n", qe, posQe, qo, posQo);
        
        // 3-9. 区間分割／保存.
        section sl, sm, sr;
        // 左.
        if(posQe > s.l + 1){
            sl.l = s.l;
            sl.r = posQe;
            if(sl.l & 1) sl.a = oSeg.prod(sl.l, sl.r);
            else         sl.a = eSeg.prod(sl.l, sl.r);
            pq.push(sl);
        }
        // 中央.
        if(posQo > posQe + 1){
            sm.l = posQe + 1;
            sm.r = posQo;
            if(sm.l & 1) sm.a = oSeg.prod(sm.l, sm.r);
            else         sm.a = eSeg.prod(sm.l, sm.r);
            pq.push(sm);
        }
        // 右.
        if(s.r > posQo + 1){
            sr.l = posQo + 1;
            sr.r = s.r;
            if(sr.l & 1) sr.a = oSeg.prod(sr.l, sr.r);
            else         sr.a = eSeg.prod(sr.l, sr.r);
            pq.push(sr);
        }
        // if(posQe > s.l + 1)   printf("sl.l=%d sl.r=%d sl.a=%d\n", sl.l, sl.r, sl.a);
        // if(posQo > posQe + 1) printf("sm.l=%d sm.r=%d sm.a=%d\n", sm.l, sm.r, sm.a);
        // if(s.r > posQo + 1)   printf("sr.l=%d sr.r=%d sr.a=%d\n", sr.l, sr.r, sr.a);
    }
    
    // 4. 出力.
    int ql = q.size();
    rep(i, ql){
        printf("%d", q[i]);
        printf("%s", (i < ql - 1) ? " " : "\n");
    }
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

// 解き直し.

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

// 参考資料.

// https://atcoder.jp/contests/pakencamp-2020-day1/editorial/527

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

const int INF = 2020202020;

int p[202020], pos[202020];

struct section{

int l, r, a; // 半開区間[l, r) と, 区間内の偶数番目の最小値を保存.

bool operator < (const section& rhs) const{

return a > rhs.a;

}

};

// AtCoder Library(https://github.com/atcoder/ac-library/blob/master/atcoder/segtree.hpp)

// -> 一部改変(2021/02/05).

template<class S, S (*op)(S, S), S (*e)()> struct SegmentTree{

public:

SegmentTree() : SegmentTree(0){}

explicit SegmentTree(int n) : SegmentTree(vector<S>(n, e())){}

explicit SegmentTree(const vector<S>& v) : _n(int(v.size())){

log = 0;

while((1 << log) < _n) log++;

size = 1 << log;

d = vector<S>(2 * size, e());

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

repr(i, size - 1, 1) update(i);

}

void set(int p, S x){

assert(0 <= p && p < _n);

p += size;

d[p] = x;

repx(i, 1, log + 1) update(p >> i);

}

S get(int p){

assert(0 <= p && p < _n);

return d[p + size];

}

S prod(int l, int r){

assert(0 <= l && l <= r && r <= _n);

S sml = e(), smr = e();

l += size;

r += size;

while(l < r){

if(l & 1) sml = op(sml, d[l++]);

if(r & 1) smr = op(d[--r], smr);

l >>= 1;

r >>= 1;

}

return op(sml, smr);

}

S all_prod(){

return d[1];

}

private:

int _n, size, log;

vector<S> d;

void update(int k){

d[k] = op(d[2 * k], d[2 * k + 1]);

}

};

static int RMiQ_nodef(int l, int r){

return min(l, r);

}

static int RMiQ_ef(){

return INF;

}

using RMiQ = SegmentTree<int, RMiQ_nodef, RMiQ_ef>;

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

rep(i, N){

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

pos[p[i]] = i; // p[i] の出現位置.

}

// 2. 前処理.

RMiQ eSeg(N + 2); // 偶数番目だけ保存.

RMiQ oSeg(N + 2); // 奇数番目だけ保存.

rep(i, N){

if(i & 1) oSeg.set(i, p[i]);

else eSeg.set(i, p[i]);

}

// 3. 操作を繰り返す.

vector<int> q;

priority_queue<section> pq;

// 3-1. 全区間を保存.

int qe = 0, posQe = 0, qo = 0, posQo = 0;

section s;

s.l = 0, s.r = N, s.a = eSeg.prod(s.l, s.r);

pq.push(s);

while(!pq.empty() && q.size() < N){

// 3-2. 区間を一つ取り出す.

s = pq.top();

pq.pop();

// 偶数番目を見る.

if(s.r > s.l){

// 3-3. 最小の要素は？

if(s.l & 1) qe = oSeg.prod(s.l, s.r);

else qe = eSeg.prod(s.l, s.r);

// 3-4. 最小の要素の出現場所は？

posQe = pos[qe];

// 3-5. 数列 q に追加.

q.pb(qe);

}

// 奇数番目を見る.

if(s.r > posQe + 1){

// 3-6. 最小の要素は？

if(s.l & 1) qo = eSeg.prod(posQe + 1, s.r);

else qo = oSeg.prod(posQe + 1, s.r);

// 3-7. 最小の要素の出現場所は？

posQo = pos[qo];

// 3-8. 数列 q に追加.

q.pb(qo);

}

// printf("qe=%d posQe=%d qo=%d posQo=%d\n", qe, posQe, qo, posQo);

// 3-9. 区間分割／保存.

section sl, sm, sr;

// 左.

if(posQe > s.l + 1){

sl.l = s.l;

sl.r = posQe;

if(sl.l & 1) sl.a = oSeg.prod(sl.l, sl.r);

else sl.a = eSeg.prod(sl.l, sl.r);

pq.push(sl);

}

// 中央.

if(posQo > posQe + 1){

sm.l = posQe + 1;

sm.r = posQo;

if(sm.l & 1) sm.a = oSeg.prod(sm.l, sm.r);

else sm.a = eSeg.prod(sm.l, sm.r);

pq.push(sm);

}

// 右.

if(s.r > posQo + 1){

sr.l = posQo + 1;

sr.r = s.r;

if(sr.l & 1) sr.a = oSeg.prod(sr.l, sr.r);

else sr.a = eSeg.prod(sr.l, sr.r);

pq.push(sr);

}

// if(posQe > s.l + 1) printf("sl.l=%d sl.r=%d sl.a=%d\n", sl.l, sl.r, sl.a);

// if(posQo > posQe + 1) printf("sm.l=%d sm.r=%d sm.a=%d\n", sm.l, sm.r, sm.a);

// if(s.r > posQo + 1) printf("sr.l=%d sr.r=%d sr.a=%d\n", sr.l, sr.r, sr.a);

}

// 4. 出力.

int ql = q.size();

rep(i, ql){

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

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

}

return 0;

}

[入力例]
4
3 2 4 1

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

[入力例]
2
1 2

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

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

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

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

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

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

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

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

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

[入力例]

3 2 4 1

[出力例]

3 1 2 4

※AtCoderのテストケースより

[入力例]

1 2

[出力例]

1 2

※AtCoderのテストケースより

[入力例]

4 6 3 2 8 5 7 1

[出力例]

3 1 2 7 4 6 8 5

※AtCoderのテストケースより

[入力例]

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

[出力例]

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

[入力例]

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

[出力例]

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

[入力例]

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

[出力例]

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

■参照サイト
AtCoder Regular Contest 080
パ研合宿2020 第1日「SpeedRun」／N – 背の順解説／セグメント木（Range Minimum Query）の使い方を参考にしました

C++の練習を兼ねて, AtCoder Regular Contest 080 の 問題E (Young Maids)を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 080 の問題E (Young Maids)を解いてみた.

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