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

C++の練習を兼ねて, AtCoder Regular Contest 038 の問題C (茶碗と豆)を解いてみた.

■感想.
1. 問題Cは, 方針が見えなかったので, 解説を参考に実装して, AC版に到達できたので, 良かったと思う.
2. ただし, セグメント木（Range Minimum Query）を, 二本使うことに気付くのに, 非常に時間がかかってしまったと思う.
3. 個人的には, 非常に面白い問題と感じたとともに, Grundy数という新しい知識が増えたので, 非常に良かったと思う.
※ 公式のライブラリを拝借させて頂いてます.
4. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// 解き直し.
// https://www.slideshare.net/chokudai/arc038
// 参考資料.
// 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--)
const int INF = 2020202020;
int a[101010], c[101010], k[101010], grundy[101010];

// 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 - 1) scanf("%d %d", &c[i], &a[i]);
    
    // 2. Grundy数 を 計算.
    // ex.
    // 18
    // 1 1
    // 1 0
    // 2 2
    // 3 5
    // 1 17
    // 2 3
    // 1 12
    // 5 13
    // 4 5
    // 1 7
    // 6 11
    // 3 9
    // 7 0
    // 2 15
    // 5 8
    // 8 7
    // 5 6
    // 
    // index          | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
    // c[i]           | 0 1 1 2 3 1 2 1 5 4  1  6  3  7  2  5  8  5
    // grundy[i]      | 0 1 0 2 3 0 1 0 4 2  0  3  1  5  0  2  6  3 
    // k[i]           | 0 0 1 1 1 1 3 3 3 4  4  6  8  8  8  8  8  8 
    // l(= 0)         | 0 0 0 0 0 0 0 0 0 0  0  0  0  0  0  0  0  0
    // r(= maxGrundy) | 0 0 1 2 3 3 3 3 4 4  4  4  4  5  5  5  6  6
    // -> 例えば, index = 12 に対する grundy[12] を 計算する場合, 
    //    区間[i - C[i], i - 1] = [12 - 3, 12 - 1] = [9, 11] に 出現している Grundy数{2, 0, 3}
    //    からは, 選択できない.
    //    区間[k[i - 1], i - C[i] - 1] = [6, 12 - 3 - 1] = [6, 8] に着目して,
    //    この中のGrundy数{1, 4} から 最小のものを選択して, grundy[12] に 設定すれば良いはず.
    // -> 区間[6, 8] に Grundy数{0} を 含まない理由は, 区間[9, 11]側 に 含まれているからである.
    // -> 前行のデータ管理をするため, 二本目のセグメント木(pgSeg)が, 必要となると理解する.
    // -> 補足として, 一本目のセグメント木(gpSeg)は, 過去に出現した各Grundy数の一番直近に出現した
    //    位置を保存しているので, 解説上 の k を 算出するために必要.
    RMiQ gpSeg(N + 2); // 各Grundy数に対し, 一番直近に出現した位置(position)だけ保存.
    RMiQ pgSeg(N + 2); // 各位置(position)に対し, 一番直近に出現したGrundy数だけ保存.
    int maxGrundy = 0;
    gpSeg.set(0, 0);
    pgSeg.set(0, 0);
    repx(i, 1, N){
        // 2-1. 区間[i - C[i], i - 1] の 左端 が 前回 の k 以下の場合.
        int befPos = 0, curPos = i, l = i - c[i - 1];
        if(l <= k[i - 1]){
            // Grundy数 を 最大値 に 設定.
            grundy[i] = maxGrundy + 1;
            
            // Grundy数 の 最大値 を 更新.
            maxGrundy = max(maxGrundy, grundy[i]);
            
            // 今回確定した Grundy数 の 前回出現位置 を 取得.
            befPos = gpSeg.get(grundy[i]);
            
            // 今回確定した Grundy数 の 今回出現位置 を 更新.
            gpSeg.set(grundy[i], i);
        }
        
        // 2-2. 区間[i - C[i], i - 1] の 左端 が 前回 の k より大きい場合.
        if(l > k[i - 1]){
            // 区間[前回 の k, i - C[i] - 1] の Grundy数 の 最小値 を 取得.
            int minGrundy = pgSeg.prod(k[i - 1], l);
            
            // Grundy数を更新.
            grundy[i] = minGrundy;
            
            // Grundy数 の 最大値 を 更新.
            maxGrundy = max(maxGrundy, grundy[i]);
            
            // 今回確定した Grundy数 の 前回出現位置 を 取得.
            befPos = gpSeg.get(grundy[i]);
            
            // 今回確定した Grundy数 の 今回出現位置 を 更新.
            gpSeg.set(grundy[i], i);
        }
        
        // 2-3. セグメント木更新(※今回確定した Grundy数 の 前回出現位置).
        if(befPos != INF) pgSeg.set(befPos, INF);
        
        // 2-4. セグメント木更新(※今回確定した Grundy数 の 今回出現位置).
        pgSeg.set(curPos, grundy[i]);
        
        // 2-5. 区間[0, maxGrundy] を 参照して, 今回 の k を 更新.
        k[i] = gpSeg.prod(0, maxGrundy + 1);
    }
    // puts("--- k ---");
    // rep(i, N) printf("%d ", k[i]);
    // puts("\n--- grundy ---");
    // rep(i, N) printf("%d ", grundy[i]);
    // puts("");
    
    // 3. Grundy数 の XOR を 計算.
    int ans = 0;
    repx(i, 1, N) if(a[i - 1] & 1) ans ^= grundy[i];
    
    // 4. 出力.
    printf("%s\n", (ans == 0) ? "Second" : "First");
    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://www.slideshare.net/chokudai/arc038

// 参考資料.

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

const int INF = 2020202020;

int a[101010], c[101010], k[101010], grundy[101010];

// 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 - 1) scanf("%d %d", &c[i], &a[i]);

// 2. Grundy数を計算.

// ex.

// 18

// 1 1

// 1 0

// 2 2

// 3 5

// 1 17

// 2 3

// 1 12

// 5 13

// 4 5

// 1 7

// 6 11

// 3 9

// 7 0

// 2 15

// 5 8

// 8 7

// 5 6

// index | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

// c[i] | 0 1 1 2 3 1 2 1 5 4 1 6 3 7 2 5 8 5

// grundy[i] | 0 1 0 2 3 0 1 0 4 2 0 3 1 5 0 2 6 3

// k[i] | 0 0 1 1 1 1 3 3 3 4 4 6 8 8 8 8 8 8

// l(= 0) | 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

// r(= maxGrundy) | 0 0 1 2 3 3 3 3 4 4 4 4 4 5 5 5 6 6

// -> 例えば, index = 12 に対する grundy[12] を計算する場合,

// 区間[i - C[i], i - 1] = [12 - 3, 12 - 1] = [9, 11] に出現している Grundy数{2, 0, 3}

// からは, 選択できない.

// 区間[k[i - 1], i - C[i] - 1] = [6, 12 - 3 - 1] = [6, 8] に着目して,

// この中のGrundy数{1, 4} から最小のものを選択して, grundy[12] に設定すれば良いはず.

// -> 区間[6, 8] に Grundy数{0} を含まない理由は, 区間[9, 11]側に含まれているからである.

// -> 前行のデータ管理をするため, 二本目のセグメント木(pgSeg)が, 必要となると理解する.

// -> 補足として, 一本目のセグメント木(gpSeg)は, 過去に出現した各Grundy数の一番直近に出現した

// 位置を保存しているので, 解説上の k を算出するために必要.

RMiQ gpSeg(N + 2); // 各Grundy数に対し, 一番直近に出現した位置(position)だけ保存.

RMiQ pgSeg(N + 2); // 各位置(position)に対し, 一番直近に出現したGrundy数だけ保存.

int maxGrundy = 0;

gpSeg.set(0, 0);

pgSeg.set(0, 0);

repx(i, 1, N){

// 2-1. 区間[i - C[i], i - 1] の左端が前回の k 以下の場合.

int befPos = 0, curPos = i, l = i - c[i - 1];

if(l <= k[i - 1]){

// Grundy数を最大値に設定.

grundy[i] = maxGrundy + 1;

// Grundy数の最大値を更新.

maxGrundy = max(maxGrundy, grundy[i]);

// 今回確定した Grundy数の前回出現位置を取得.

befPos = gpSeg.get(grundy[i]);

// 今回確定した Grundy数の今回出現位置を更新.

gpSeg.set(grundy[i], i);

}

// 2-2. 区間[i - C[i], i - 1] の左端が前回の k より大きい場合.

if(l > k[i - 1]){

// 区間[前回の k, i - C[i] - 1] の Grundy数の最小値を取得.

int minGrundy = pgSeg.prod(k[i - 1], l);

// Grundy数を更新.

grundy[i] = minGrundy;

// Grundy数の最大値を更新.

maxGrundy = max(maxGrundy, grundy[i]);

// 今回確定した Grundy数の前回出現位置を取得.

befPos = gpSeg.get(grundy[i]);

// 今回確定した Grundy数の今回出現位置を更新.

gpSeg.set(grundy[i], i);

}

// 2-3. セグメント木更新(※今回確定した Grundy数の前回出現位置).

if(befPos != INF) pgSeg.set(befPos, INF);

// 2-4. セグメント木更新(※今回確定した Grundy数の今回出現位置).

pgSeg.set(curPos, grundy[i]);

// 2-5. 区間[0, maxGrundy] を参照して, 今回の k を更新.

k[i] = gpSeg.prod(0, maxGrundy + 1);

}

// puts("--- k ---");

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

// puts("\n--- grundy ---");

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

// puts("");

// 3. Grundy数の XOR を計算.

int ans = 0;

repx(i, 1, N) if(a[i - 1] & 1) ans ^= grundy[i];

// 4. 出力.

printf("%s\n", (ans == 0) ? "Second" : "First");

return 0;

}

[入力例]
3
1 0
1 1

[出力例(debug版)]
--- k ---
0 0 1 
--- grundy ---
0 1 0 
Second
※AtCoderのテストケースより

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

[出力例(debug版)]
--- k ---
0 0 0 1 2 2 3 
--- grundy ---
0 1 2 0 1 3 2 
First
※AtCoderのテストケースより

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

[出力例(debug版)]
--- k ---
0 0 0 1 2 2 3 
--- grundy ---
0 1 2 0 1 3 2 
Second
※AtCoderのテストケースより

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

[出力例(debug版)]
--- k ---
0 0 1 1 1 1 3 3 3 4 4 6 8 8 8 8 8 8 
--- grundy ---
0 1 0 2 3 0 1 0 4 2 0 3 1 5 0 2 6 3 
First

[入力例]
30
1 1
1 0
2 2
3 5
1 17
2 3
3 6
1 12
5 13
2 7
1 7
6 6
3 11
7 9
1 0
2 15
5 8
8 7
3 6
2 11
9 18
3 10
5 4
3 19
7 17
10 9
5 8
7 15
3 23

[出力例(debug版)]
--- k ---
0 0 1 1 1 1 3 4 4 4 4 4 7 9 9 9 9 12 12 12 12 12 12 14 14 14 18 18 21 21 
--- grundy ---
0 1 0 2 3 0 1 2 0 4 1 0 3 2 5 0 1 4 6 0 1 7 2 3 0 4 5 1 6 0 
Second

[入力例]
50
5 69379463
14 121410993
5 65591092
5 45598468
13 13351854
7 11461527
6 26186966
10 71634680
11 66189154
1 53830114
3 15427275
12 6929923
12 18649567
12 88587971
1 82196776
10 39901772
3 61263173
3 79275060
3 86684502
14 37382396
15 62256931
12 86356755
16 22474298
8 101539891
2 30730994
10 69045198
14 75729438
15 112107055
7 112056635
8 1428515
2 45261247
3 121601466
17 94295137
9 68729985
17 12705325
1 32519109
11 5437491
5 78777121
6 36839199
13 44773739
15 80027184
1 72941422
17 12218068
15 21893608
10 47917352
14 73871275
17 119485015
14 109054715
7 24072763

[出力例(debug版)]
--- k ---
0 0 0 0 0 0 0 1 1 1 1 2 2 2 2 2 3 3 4 4 5 6 8 8 9 9 12 13 13 13 13 13 13 14 14 21 21 22 22 22 23 23 23 26 27 27 28 33 34 34 
--- grundy ---
0 1 2 3 4 5 6 0 7 8 0 1 9 10 11 0 2 1 3 0 4 5 6 12 7 0 8 9 13 1 2 0 3 10 4 11 0 5 1 2 6 7 0 12 8 3 9 13 10 1 
First

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

[入力例]

1 0

1 1

[出力例(debug版)]

--- k ---

0 0 1

--- grundy ---

0 1 0

Second

※AtCoderのテストケースより

[入力例]

1 1

2 0

1 0

2 0

4 1

3 0

[出力例(debug版)]

--- k ---

0 0 0 1 2 2 3

--- grundy ---

0 1 2 0 1 3 2

First

※AtCoderのテストケースより

[入力例]

1 1

2 0

1 9

2 10

4 3

3 5

[出力例(debug版)]

--- k ---

0 0 0 1 2 2 3

--- grundy ---

0 1 2 0 1 3 2

Second

※AtCoderのテストケースより

[入力例]

1 1

1 0

2 2

3 5

1 17

2 3

1 12

5 13

4 5

1 7

6 11

3 9

7 0

2 15

5 8

8 7

5 6

[出力例(debug版)]

--- k ---

0 0 1 1 1 1 3 3 3 4 4 6 8 8 8 8 8 8

--- grundy ---

0 1 0 2 3 0 1 0 4 2 0 3 1 5 0 2 6 3

First

[入力例]

1 1

1 0

2 2

3 5

1 17

2 3

3 6

1 12

5 13

2 7

1 7

6 6

3 11

7 9

1 0

2 15

5 8

8 7

3 6

2 11

9 18

3 10

5 4

3 19

7 17

10 9

5 8

7 15

3 23

[出力例(debug版)]

--- k ---

0 0 1 1 1 1 3 4 4 4 4 4 7 9 9 9 9 12 12 12 12 12 12 14 14 14 18 18 21 21

--- grundy ---

0 1 0 2 3 0 1 2 0 4 1 0 3 2 5 0 1 4 6 0 1 7 2 3 0 4 5 1 6 0

Second

[入力例]

5 69379463

14 121410993

5 65591092

5 45598468

13 13351854

7 11461527

6 26186966

10 71634680

11 66189154

1 53830114

3 15427275

12 6929923

12 18649567

12 88587971

1 82196776

10 39901772

3 61263173

3 79275060

3 86684502

14 37382396

15 62256931

12 86356755

16 22474298

8 101539891

2 30730994

10 69045198

14 75729438

15 112107055

7 112056635

8 1428515

2 45261247

3 121601466

17 94295137

9 68729985

17 12705325

1 32519109

11 5437491

5 78777121

6 36839199

13 44773739

15 80027184

1 72941422

17 12218068

15 21893608

10 47917352

14 73871275

17 119485015

14 109054715

7 24072763

[出力例(debug版)]

--- k ---

0 0 0 0 0 0 0 1 1 1 1 2 2 2 2 2 3 3 4 4 5 6 8 8 9 9 12 13 13 13 13 13 13 14 14 21 21 22 22 22 23 23 23 26 27 27 28 33 34 34

--- grundy ---

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

First

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

C++の練習を兼ねて, AtCoder Regular Contest 038 の 問題C (茶碗と豆)を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 038 の問題C (茶碗と豆)を解いてみた.

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