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

C++の練習を兼ねて, AtCoder Grand Contest 017 の問題C (Snuke and Spells) を解いてみた.

■感想.
1. 問題Cは, 解答方針が見えなかったので, 解説を参考に実装して, ようやく, AC版に到達できた.
2. 解答に至るまでの実装方針が, 個人的には, 非常に不思議な印象を受ける面白い問題に感じた.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/agc017/editorial.pdf
// 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 a[202020];
int cover[202020]; // 被覆[x - 1, x]
P section[202020]; // ボール i (q個) の 区間[i - q, i]

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    rep(i, N) scanf("%d", &a[i]);
    
    // 2. 初期化.
    int ans = 0;
    rep(i, 202020) section[i] = {i, i};
    rep(i, N){
        int v = a[i];
        section[v].a--;
    }
    repx(i, 1, N + 1){
        int s = section[i].a + 1;
        int e = section[i].b + 1;
        repx(j, s, e) cover[j]++;
    }
    repx(i, 1, N + 1) if(!cover[i]) ans++;
    
    // 3. クエリ回答.
    rep(i, M){
        // 3-1．ボール情報を取得.
        int x, y;
        scanf("%d %d", &x, &y);
        x--;
        
        // 3-2．区間[p - N[p], p] を 縮める.
        int p = a[x];
        int lp = ++section[p].a;
        if(lp > 0){
            cover[lp]--;
            if(cover[lp] == 0) ans++;
        }
        
        // 3-3．x番目 の ボールを, y に 変更.
        a[x] = y;
        
        // 3-4. 区間[q - N[q], q] を 伸ばす.
        int q = a[x];
        int lq = section[q].a--;
        if(lq > 0){
            cover[lq]++;
            if(cover[lq] == 1) ans--;
        }
        
        // 3-5. 出力.
        printf("%d\n", ans);
    }
    return 0;
    
}

// 解き直し.

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

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

int cover[202020]; // 被覆[x - 1, x]

P section[202020]; // ボール i (q個) の区間[i - q, i]

int main(){

// 1. 入力情報.

int N, M;

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

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

// 2. 初期化.

int ans = 0;

rep(i, 202020) section[i] = {i, i};

rep(i, N){

int v = a[i];

section[v].a--;

}

repx(i, 1, N + 1){

int s = section[i].a + 1;

int e = section[i].b + 1;

repx(j, s, e) cover[j]++;

}

repx(i, 1, N + 1) if(!cover[i]) ans++;

// 3. クエリ回答.

rep(i, M){

// 3-1．ボール情報を取得.

int x, y;

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

x--;

// 3-2．区間[p - N[p], p] を縮める.

int p = a[x];

int lp = ++section[p].a;

if(lp > 0){

cover[lp]--;

if(cover[lp] == 0) ans++;

}

// 3-3．x番目のボールを, y に変更.

a[x] = y;

// 3-4. 区間[q - N[q], q] を伸ばす.

int q = a[x];

int lq = section[q].a--;

if(lq > 0){

cover[lq]++;

if(cover[lq] == 1) ans--;

}

// 3-5. 出力.

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

}

return 0;

}

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

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

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

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

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

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

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

[出力例]
1
2
3
2
2
1
1
2
1
1

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

[出力例]
7
7
8
8
7
6
6
7
6
5
5
5
5
5
5
6
5
4
5
6
6
7
7
6
5
5
5
6
6
6

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

[入力例]

5 3

1 1 3 4 5

1 2

2 5

5 4

[出力例]

※AtCoderテストケースより

[入力例]

4 4

4 4 4 4

4 1

3 1

1 1

2 1

[出力例]

※AtCoderテストケースより

[入力例]

10 10

8 7 2 9 10 6 6 5 5 4

8 1

6 3

6 2

7 10

9 7

9 9

2 4

8 1

1 8

7 7

[出力例]

※AtCoderテストケースより

[入力例]

7 10

7 1 4 2 5 6 7

1 1

3 6

7 1

5 3

2 3

2 7

5 3

3 7

1 7

6 3

[出力例]

[入力例]

20 30

1 2 14 16 12 6 13 7 14 15 9 18 11 14 8 1 3 15 16 12

17 1

14 16

6 15

15 20

4 6

17 4

12 17

15 16

19 11

16 3

9 2

11 9

6 3

9 14

20 13

13 12

19 9

7 19

5 17

1 17

2 17

7 8

11 2

6 12

1 5

6 10

8 20

19 16

7 9

5 4

[出力例]

■参照サイト
AtCoder Grand Contest 017

C++の練習を兼ねて, AtCoder Grand Contest 017 の 問題C (Snuke and Spells) を解いてみた.

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

C++の練習を兼ねて, AtCoder Grand Contest 017 の問題C (Snuke and Spells) を解いてみた.

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