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

C++の練習を兼ねて, AtCoder Beginner Contest 224 の問題E (Integers on Grid) を解いてみた.

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

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

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

// 解き直し.
// https://atcoder.jp/contests/abc224/editorial/2814
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using T3 = tuple<int, int, int>;
using T4 = tuple<int, int, 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()
#define a first
#define b second
int dp[202020], rMax[202020], cMax[202020];

int main(){
    
    // 1. 入力情報.
    int H, W, N;
    scanf("%d %d %d", &H, &W, &N);
    vector<T4> t;
    map<int, int> m;
    rep(i, N){
        int r, c, a;
        scanf("%d %d %d", &r, &c, &a);
        t.emplace_back(a, r, c, i);
        m[a] = 0;
    }
    
    // 2. sort.
    sort(all(t));
    
    // 3. マスに記載された整数 X の並び替え.
    int idx = -1;
    for(auto &p : m) p.b = ++idx;
    
    // 4. 整数 X ごとに分類.
    vector<vector<T3>> u(idx + 1);
    for(auto &p : t){
        int a = get<0>(p);
        int r = get<1>(p);
        int c = get<2>(p);
        int j = get<3>(p);
        u[m[a]].emplace_back(r, c, j);
    }
    
    // 5. dp更新.
    repr(i, idx, 0){
        // dp更新.
        for(auto &p : u[i]){
            int r = get<0>(p);
            int c = get<1>(p);
            int j = get<2>(p);
            dp[j] = max(rMax[r], cMax[c]);
        }
        
        // rMax, cMax更新.
        for(auto &p : u[i]){
            int r = get<0>(p);
            int c = get<1>(p);
            int j = get<2>(p);
            rMax[r] = max(rMax[r], dp[j] + 1);
            cMax[c] = max(cMax[c], dp[j] + 1);
        }
    }
    
    // 6. 出力.
    rep(i, N) printf("%d\n", dp[i]);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc224/editorial/2814

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

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

using T4 = tuple<int, int, 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()

#define a first

#define b second

int dp[202020], rMax[202020], cMax[202020];

int main(){

// 1. 入力情報.

int H, W, N;

scanf("%d %d %d", &H, &W, &N);

vector<T4> t;

map<int, int> m;

rep(i, N){

int r, c, a;

scanf("%d %d %d", &r, &c, &a);

t.emplace_back(a, r, c, i);

m[a] = 0;

}

// 2. sort.

sort(all(t));

// 3. マスに記載された整数 X の並び替え.

int idx = -1;

for(auto &p : m) p.b = ++idx;

// 4. 整数 X ごとに分類.

vector<vector<T3>> u(idx + 1);

for(auto &p : t){

int a = get<0>(p);

int r = get<1>(p);

int c = get<2>(p);

int j = get<3>(p);

u[m[a]].emplace_back(r, c, j);

}

// 5. dp更新.

repr(i, idx, 0){

// dp更新.

for(auto &p : u[i]){

int r = get<0>(p);

int c = get<1>(p);

int j = get<2>(p);

dp[j] = max(rMax[r], cMax[c]);

}

// rMax, cMax更新.

for(auto &p : u[i]){

int r = get<0>(p);

int c = get<1>(p);

int j = get<2>(p);

rMax[r] = max(rMax[r], dp[j] + 1);

cMax[c] = max(cMax[c], dp[j] + 1);

}

// 6. 出力.

rep(i, N) printf("%d\n", dp[i]);

return 0;

}

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

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

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

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

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

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

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

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

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

[入力例]

3 3 7

1 1 4

1 2 7

2 1 3

2 3 5

3 1 2

3 2 5

3 3 5

[出力例]

※AtCoderテストケースより

[入力例]

5 7 20

2 7 8

2 6 4

4 1 9

1 5 4

2 2 7

5 5 2

1 7 2

4 6 6

1 4 1

2 1 10

5 6 9

5 3 3

3 7 9

3 6 3

4 3 4

3 3 10

4 2 1

3 5 4

1 2 6

4 7 9

[出力例]

※AtCoderテストケースより

[入力例]

5 6 18

1 1 3

1 5 7

2 1 1

2 2 4

2 4 6

2 5 6

2 6 8

3 1 2

3 2 3

3 3 5

3 4 5

3 5 5

3 6 7

4 2 2

4 3 4

4 4 4

4 6 6

5 3 3

[出力例]

[入力例]

10 8 30

2 1 9

3 1 10

4 1 9

5 1 6

6 1 5

7 1 2

8 1 1

3 2 9

4 2 8

5 2 7

6 2 4

7 2 3

3 3 8

4 3 7

6 3 5

3 4 9

4 4 11

3 5 10

3 6 8

4 6 9

5 6 10

6 6 11

7 6 12

3 7 7

4 7 6

5 7 5

5 8 4

6 8 3

7 8 2

8 8 1

[出力例]

■参照サイト
AtCoder Beginner Contest 224

C++の練習を兼ねて, AtCoder Beginner Contest 224 の 問題E (Integers on Grid) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 224 の問題E (Integers on Grid) を解いてみた.

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