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

C++の練習を兼ねて, AtCoder Regular Contest 044 の問題C (ビーム) を解いてみた.

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

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

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

// 解き直し.
// https://www.slideshare.net/chokudai/arc044
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
#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
#define a first
#define b second
#define all(x) x.begin(), x.end()
const int INF = 1010101010;
int dpX[101010], dpY[101010];

int main(){
    
    // 1. 入力情報.
    int W, H, Q;
    scanf("%d %d %d", &W, &H, &Q);
    vvi vx(101010), vy(101010);
    rep(i, Q){
        int t, d, x;
        scanf("%d %d %d", &t, &d, &x);
        if(!d) vx[t].pb(x);
        else   vy[t].pb(x);
    }
    
    // 2. dp更新.
    // ex.
    // 7 10 19
    // 1 0 1
    // 1 0 2
    // 1 0 3
    // 1 0 4
    // 1 0 5
    // 1 0 7
    // 2 0 2
    // 2 0 3
    // 2 0 6
    // 3 0 1
    // 3 0 2
    // 3 0 4
    // 3 0 7
    // 4 0 2
    // 4 0 5
    // 4 0 6
    // 5 0 2
    // 5 0 4
    // 5 0 7
    // 
    // 解説にあるように, おおよそ, ビームの本数分が更新されるように調整.
    // 更新① => 前回ビームが通過した位置で, 今回ビームが通過しない場合は, 
    //           前回ビームが通過した区間の左右を比較して, dp更新.
    // 更新② => 今回ビーム自身 に INF を 割り当てる.
    // 
    //       [座標]   1    2    3    4    5    6    7
    // [時刻]
    //  0             0    0    0    0    0    0    0
    // 
    //  1  (更新①)   -    -    -    -    -    -    -  ※ - は 更新対象外(前回からの値を引き継ぐ, 以下略)
    //     (更新②)  INF  INF  INF  INF  INF   0   INF
    // 
    //  2  (更新①)   5    -    -    2    1    -    1
    //     (更新②)   5   INF  INF   2    1   INF   1
    // 
    //  3  (更新①)   -    -    3    -    -    2    -
    //     (更新②)  INF  INF   3   INF   1    2   INF
    // 
    //  4  (更新①)   5    -    -    2    -    -    3
    //     (更新②)   5   INF   3    2   INF  INF   3
    //  
    //  5  (更新①)   -    -    -    -    3    4    -
    //     (更新②)   5   INF   3   INF   3    4   INF
    //  
    //  -> 以上から, 最初(座標 6) => 時刻 1.5(座標 5) => 時刻 1.5(座標 4) => 時刻 2.5(座標 3)
    //     に 移動すると, 移動回数 3 が 最小と分かる.
    // 
    // 2-1. 縦.
    set<int> xBef, xCur;
    map<int, int> mx;
    vi xSections;
    rep(i, 101010){
        // 更新対象.
        if(!vx[i].size()) continue;
        for(auto &p : vx[i]) xCur.insert(p);
        for(auto &p : xBef){
            if(!xCur.count(p)){
                // 区間[l, r].
                int at = upper_bound(all(xSections), p) - xSections.begin();
                if(at) --at;
                int l = xSections[at];
                int r = mx[l];
                if(p >= l && p <= r){
                    if(l > 1) dpX[p] = min(dpX[p], dpX[l - 1] + p - (l - 1));
                    if(r < W) dpX[p] = min(dpX[p], dpX[r + 1] + (r + 1) - p);
                }
            }
        }
        
        // ビーム反映.
        for(auto &p : vx[i]) dpX[p] = INF;
        
        // 区間作成.
        vx[i].pb(INF); // 番兵.
        mx.clear();
        xSections.clear();
        int s = 0;
        for(auto &p : xCur){
            if(!mx.count(s) || p - mx[s] != 1){
                s = p;
                mx[s] = p;
                continue;
            }
            ++mx[s];
        }
        for(auto &p : mx) xSections.pb(p.a);
        
        // 前回分更新.
        xBef = xCur;
        xCur.clear();
    }
    
    // 2-2. 横.
    set<int> yBef, yCur;
    map<int, int> my;
    vi ySections;
    rep(i, 101010){
        // 更新対象.
        if(!vy[i].size()) continue;
        for(auto &p : vy[i]) yCur.insert(p);
        for(auto &p : yBef){
            if(!yCur.count(p)){
                // 区間[l, r].
                int at = upper_bound(all(ySections), p) - ySections.begin();
                if(at) --at;
                int l = ySections[at];
                int r = my[l];
                if(p >= l && p <= r){
                    if(l > 1) dpY[p] = min(dpY[p], dpY[l - 1] + p - (l - 1));
                    if(r < H) dpY[p] = min(dpY[p], dpY[r + 1] + (r + 1) - p);
                }
            }
        }
        
        // ビーム反映.
        for(auto &p : vy[i]) dpY[p] = INF;
        
        // 区間作成.
        vy[i].pb(INF); // 番兵.
        my.clear();
        ySections.clear();
        int s = 0;
        for(auto &p : yCur){
            if(!my.count(s) || p - my[s] != 1){
                s = p;
                my[s] = p;
                continue;
            }
            ++my[s];
        }
        for(auto &p : my) ySections.pb(p.a);
        
        // 前回分更新.
        yBef = yCur;
        yCur.clear();
    }
    
    // 3. 移動回数の最小値は？
    // 3-1. 縦.
    int xMin = INF;
    repx(i, 1, W + 1) xMin = min(xMin, dpX[i]);
    
    // 3-2. 横.
    int yMin = INF;
    repx(i, 1, H + 1) yMin = min(yMin, dpY[i]);
    
    // 4. 出力.
    int ans = xMin + yMin;
    printf("%d\n", (ans < INF) ? ans : -1);
    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

178

179

180

181

182

183

184

185

186

// 解き直し.

// https://www.slideshare.net/chokudai/arc044

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

using vvi = vector<vi>;

#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

#define a first

#define b second

#define all(x) x.begin(), x.end()

const int INF = 1010101010;

int dpX[101010], dpY[101010];

int main(){

// 1. 入力情報.

int W, H, Q;

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

vvi vx(101010), vy(101010);

rep(i, Q){

int t, d, x;

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

if(!d) vx[t].pb(x);

else vy[t].pb(x);

}

// 2. dp更新.

// ex.

// 7 10 19

// 1 0 1

// 1 0 2

// 1 0 3

// 1 0 4

// 1 0 5

// 1 0 7

// 2 0 2

// 2 0 3

// 2 0 6

// 3 0 1

// 3 0 2

// 3 0 4

// 3 0 7

// 4 0 2

// 4 0 5

// 4 0 6

// 5 0 2

// 5 0 4

// 5 0 7

// 解説にあるように, おおよそ, ビームの本数分が更新されるように調整.

// 更新① => 前回ビームが通過した位置で, 今回ビームが通過しない場合は,

// 前回ビームが通過した区間の左右を比較して, dp更新.

// 更新② => 今回ビーム自身に INF を割り当てる.

// [座標] 1 2 3 4 5 6 7

// [時刻]

// 0 0 0 0 0 0 0 0

// 1 (更新①) - - - - - - - ※ - は更新対象外(前回からの値を引き継ぐ, 以下略)

// (更新②) INF INF INF INF INF 0 INF

// 2 (更新①) 5 - - 2 1 - 1

// (更新②) 5 INF INF 2 1 INF 1

// 3 (更新①) - - 3 - - 2 -

// (更新②) INF INF 3 INF 1 2 INF

// 4 (更新①) 5 - - 2 - - 3

// (更新②) 5 INF 3 2 INF INF 3

// 5 (更新①) - - - - 3 4 -

// (更新②) 5 INF 3 INF 3 4 INF

// -> 以上から, 最初(座標 6) => 時刻 1.5(座標 5) => 時刻 1.5(座標 4) => 時刻 2.5(座標 3)

// に移動すると, 移動回数 3 が最小と分かる.

// 2-1. 縦.

set<int> xBef, xCur;

map<int, int> mx;

vi xSections;

rep(i, 101010){

// 更新対象.

if(!vx[i].size()) continue;

for(auto &p : vx[i]) xCur.insert(p);

for(auto &p : xBef){

if(!xCur.count(p)){

// 区間[l, r].

int at = upper_bound(all(xSections), p) - xSections.begin();

if(at) --at;

int l = xSections[at];

int r = mx[l];

if(p >= l && p <= r){

if(l > 1) dpX[p] = min(dpX[p], dpX[l - 1] + p - (l - 1));

if(r < W) dpX[p] = min(dpX[p], dpX[r + 1] + (r + 1) - p);

}

// ビーム反映.

for(auto &p : vx[i]) dpX[p] = INF;

// 区間作成.

vx[i].pb(INF); // 番兵.

mx.clear();

xSections.clear();

int s = 0;

for(auto &p : xCur){

if(!mx.count(s) || p - mx[s] != 1){

s = p;

mx[s] = p;

continue;

}

++mx[s];

}

for(auto &p : mx) xSections.pb(p.a);

// 前回分更新.

xBef = xCur;

xCur.clear();

}

// 2-2. 横.

set<int> yBef, yCur;

map<int, int> my;

vi ySections;

rep(i, 101010){

// 更新対象.

if(!vy[i].size()) continue;

for(auto &p : vy[i]) yCur.insert(p);

for(auto &p : yBef){

if(!yCur.count(p)){

// 区間[l, r].

int at = upper_bound(all(ySections), p) - ySections.begin();

if(at) --at;

int l = ySections[at];

int r = my[l];

if(p >= l && p <= r){

if(l > 1) dpY[p] = min(dpY[p], dpY[l - 1] + p - (l - 1));

if(r < H) dpY[p] = min(dpY[p], dpY[r + 1] + (r + 1) - p);

}

// ビーム反映.

for(auto &p : vy[i]) dpY[p] = INF;

// 区間作成.

vy[i].pb(INF); // 番兵.

my.clear();

ySections.clear();

int s = 0;

for(auto &p : yCur){

if(!my.count(s) || p - my[s] != 1){

s = p;

my[s] = p;

continue;

}

++my[s];

}

for(auto &p : my) ySections.pb(p.a);

// 前回分更新.

yBef = yCur;

yCur.clear();

}

// 3. 移動回数の最小値は？

// 3-1. 縦.

int xMin = INF;

repx(i, 1, W + 1) xMin = min(xMin, dpX[i]);

// 3-2. 横.

int yMin = INF;

repx(i, 1, H + 1) yMin = min(yMin, dpY[i]);

// 4. 出力.

int ans = xMin + yMin;

printf("%d\n", (ans < INF) ? ans : -1);

return 0;

}

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

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

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

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

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

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

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

[出力例]
3

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

[出力例]
7

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

[出力例]
2

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

[出力例]
7

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

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

[入力例]

3 2 8

1 0 2

3 0 2

4 1 2

2 1 2

4 0 3

2 0 3

1 1 1

2 0 1

[出力例]

※AtCoderのテストケースより

[入力例]

2 4 10

3 1 1

2 1 3

3 0 1

2 1 4

1 1 3

2 1 2

3 1 2

1 0 1

3 1 4

2 0 2

[出力例]

※AtCoderのテストケースより

[入力例]

3 3 5

1 0 3

1 0 2

1 1 3

1 1 2

1 0 1

[出力例]

-1

※AtCoderのテストケースより

[入力例]

7 10 19

1 0 1

1 0 2

1 0 3

1 0 4

1 0 5

1 0 7

2 0 2

2 0 3

2 0 6

3 0 1

3 0 2

3 0 4

3 0 7

4 0 2

4 0 5

4 0 6

5 0 2

5 0 4

5 0 7

[出力例]

[入力例]

3 5 21

1 0 1

1 0 2

2 0 2

2 0 3

3 0 3

3 0 1

1 1 1

1 1 2

1 1 3

2 1 2

2 1 3

2 1 4

3 1 3

3 1 4

3 1 5

4 1 4

4 1 5

4 1 1

5 1 5

5 1 1

5 1 2

[出力例]

[入力例]

7 10 30

3 0 4

6 0 6

2 1 6

3 1 9

6 1 1

6 1 3

2 1 5

5 1 1

5 0 6

5 1 10

4 1 5

1 0 4

4 1 6

3 0 7

2 0 5

1 0 2

4 1 8

1 1 4

4 0 3

2 1 3

4 0 7

1 0 7

6 0 5

2 0 1

6 0 2

6 0 3

5 0 7

1 1 10

6 1 7

2 1 2

[出力例]

[入力例]

12 17 150

1 1 4

5 0 10

11 0 11

7 1 4

11 1 14

5 0 8

14 1 11

12 1 10

2 1 13

5 0 9

11 0 1

1 1 1

5 0 4

15 0 2

8 1 1

4 0 11

6 0 1

12 0 5

12 0 2

12 0 12

11 1 3

3 1 5

3 0 8

5 1 8

13 1 3

4 0 4

2 1 14

13 1 11

14 1 5

11 0 5

14 0 1

9 0 3

15 0 10

10 0 3

10 0 6

11 0 2

14 0 5

3 0 6

8 0 11

1 0 7

15 1 8

7 1 6

5 1 5

1 0 12

14 0 7

3 1 15

1 0 1

10 0 1

14 0 9

11 0 4

5 0 3

1 0 3

14 1 10

8 1 16

15 0 1

7 0 10

11 0 6

2 0 11

10 1 14

6 1 1

5 0 12

5 0 7

14 0 11

11 0 7

4 1 5

9 0 10

10 0 2

12 1 12

3 0 4

2 0 1

1 1 9

1 0 10

11 1 15

13 0 4

2 0 4

12 1 13

15 0 5

10 0 5

6 0 12

8 1 5

15 0 8

14 1 3

13 1 13

11 1 11

3 0 7

11 0 10

5 0 11

2 0 9

6 0 5

5 0 5

12 1 16

2 0 8

14 0 8

5 1 11

9 0 11

11 0 8

13 0 3

2 0 10

11 1 10

3 1 3

1 1 14

15 1 15

15 0 9

6 1 15

14 1 2

12 0 4

4 0 2

1 1 5

15 1 12

10 1 17

2 1 4

15 1 1

10 1 11

6 0 7

9 0 7

11 1 4

7 0 6

10 0 12

10 1 16

3 1 14

9 1 2

2 1 3

15 0 4

14 0 6

7 0 2

7 0 5

2 1 2

12 0 9

9 1 4

6 0 6

4 0 1

4 0 7

1 0 2

12 0 10

13 1 12

4 0 8

11 1 1

13 0 5

10 1 12

3 0 3

10 1 7

6 1 14

1 1 6

1 0 11

1 1 3

5 0 2

6 1 6

3 1 12

6 0 3

6 1 16

[出力例]

■参照サイト
AtCoder Regular Contest 044

C++の練習を兼ねて, AtCoder Regular Contest 044 の 問題C (ビーム) を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 044 の問題C (ビーム) を解いてみた.

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