7月, 2019 | 個人用メモ帳

2019年7月6日

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

C++の練習を兼ねて, AtCoder Beginner Contest 131 の問題D (D – Megalomania) を解いてみた.

■感想.
1. いくつかのテストケース(sub1_07.txt, sub1_09.txt, sub1_27.txt, sub1_28.txt) で, WA となったが, 簡単なテストケースで確認して, WA を解決出来たので良かったと思う.
2. 解答を見る前に, 解けたので, 及第点は取れたと思う.

本家のサイトABC 131解説をご覧下さい.

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

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main() {

    // 1. 入力情報取得.
    int N;
    scanf("%d", &N);
    vector<pair<LL, LL>> v;
    for(int i = 0; i < N; i++){
        LL a, b;
        scanf("%lld %lld", &a, &b);
        v.push_back(make_pair(b, a));
    }
    
    // 2. 〆切の時刻で, 昇順sort.
    sort(v.begin(), v.end());
    
    // 3. 区間をマージしていく.
    // [入力例]
    // ※〆切の時刻で, 昇順sort済.
    // 5
    // 2 4
    // 1 8
    // 1 9
    // 4 9
    // 3 12
    // -> 具体的には, 以下のような処理を想定.
    // 仕事1 => [2, 4]  … 開始時刻: 2, 終了時刻: 4
    // 仕事2 => [1, 4]  … 開始時刻: 1, 終了時刻: 4
    // 仕事3 => [0, 4]  … 開始時刻: 0, 終了時刻: 4
    // 仕事4 => [0, 8]  … 開始時刻: 0, 終了時刻: 8
    // 仕事5 => [0, 11] … 開始時刻: 0, 終了時刻: 11
    bool ans = true;
    LL l = v[0].first - v[0].second, r = v[0].first;
    // printf("[%lld, %lld]\n", l, r);
    // sub1_07.txt, sub1_09.txt, sub1_27.txt, sub1_28.txt で, 
    // WA版となった理由 と 推定し, ロジック追加.
    if(l < 0) ans = false; 

    for(int i = 1; i < N; i++){
        // 以下の条件で, 区間更新.
        LL a = v[i].second, b = v[i].first;
        
        // 3-1. 最小時刻が, ゼロの場合.
        if(l == 0) r += a;
        
        // 3-2. 最小時刻 が 0より大きく, かつ, 仕事にかかる時間が, 最小時刻 より 大きい場合.
        if(l > 0 && l < a) r += (a - l), l = 0;
        
        // 3-3. 最小時刻 が, 仕事にかかる時間以上に大きい場合.
        if(l >= a) l -= a;
        
        // 3-4. 仕事が〆切までに終了しているかチェック.
        // printf("[%lld, %lld]\n", l, r);
        if(r > b){
            ans = false;
            break;
        }
    }
    
    // 4. 後処理.
    if(ans) printf("%s\n", "Yes");
    else    printf("%s\n",  "No");
    return 0;

}

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

int main() {

// 1. 入力情報取得.

int N;

scanf("%d", &N);

vector<pair<LL, LL>> v;

for(int i = 0; i < N; i++){

LL a, b;

scanf("%lld %lld", &a, &b);

v.push_back(make_pair(b, a));

}

// 2. 〆切の時刻で, 昇順sort.

sort(v.begin(), v.end());

// 3. 区間をマージしていく.

// [入力例]

// ※〆切の時刻で, 昇順sort済.

// 5

// 2 4

// 1 8

// 1 9

// 4 9

// 3 12

// -> 具体的には, 以下のような処理を想定.

// 仕事1 => [2, 4] … 開始時刻: 2, 終了時刻: 4

// 仕事2 => [1, 4] … 開始時刻: 1, 終了時刻: 4

// 仕事3 => [0, 4] … 開始時刻: 0, 終了時刻: 4

// 仕事4 => [0, 8] … 開始時刻: 0, 終了時刻: 8

// 仕事5 => [0, 11] … 開始時刻: 0, 終了時刻: 11

bool ans = true;

LL l = v[0].first - v[0].second, r = v[0].first;

// printf("[%lld, %lld]\n", l, r);

// sub1_07.txt, sub1_09.txt, sub1_27.txt, sub1_28.txt で,

// WA版となった理由と推定し, ロジック追加.

if(l < 0) ans = false;

for(int i = 1; i < N; i++){

// 以下の条件で, 区間更新.

LL a = v[i].second, b = v[i].first;

// 3-1. 最小時刻が, ゼロの場合.

if(l == 0) r += a;

// 3-2. 最小時刻が 0より大きく, かつ, 仕事にかかる時間が, 最小時刻より大きい場合.

if(l > 0 && l < a) r += (a - l), l = 0;

// 3-3. 最小時刻が, 仕事にかかる時間以上に大きい場合.

if(l >= a) l -= a;

// 3-4. 仕事が〆切までに終了しているかチェック.

// printf("[%lld, %lld]\n", l, r);

if(r > b){

ans = false;

break;

}

// 4. 後処理.

if(ans) printf("%s\n", "Yes");

else printf("%s\n", "No");

return 0;

}

[入力例]
1
2 1

[出力例(debug版)]
[-1, 1]
No

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

[出力例(debug版)]
[3, 4]
[2, 4]
[0, 4]
Yes

[入力例]
5
2 4
1 9
1 8
4 9
3 12

[出力例(debug版)]
[2, 4]
[1, 4]
[0, 4]
[0, 8]
[0, 11]
Yes
※AtCoderテストケースより

[入力例]
3
334 1000
334 1000
334 1000

[出力例(debug版)]
[666, 1000]
[332, 1000]
[0, 1002]
No
※AtCoderテストケースより

[入力例]
30
384 8895
1725 9791
170 1024
4 11105
2 6
578 1815
702 3352
143 5141
1420 6980
24 1602
849 999
76 7586
85 5570
444 4991
719 11090
470 10708
1137 4547
455 9003
110 9901
15 8578
368 3692
104 1286
3 4
366 12143
7 6649
610 2374
152 7324
4 7042
292 11386
334 5720

[出力例(debug版)]
[1, 4]
[0, 5]
[0, 854]
[0, 1024]
[0, 1128]
[0, 1152]
[0, 1730]
[0, 2340]
[0, 3042]
[0, 3410]
[0, 4547]
[0, 4991]
[0, 5134]
[0, 5219]
[0, 5553]
[0, 5560]
[0, 6980]
[0, 6984]
[0, 7136]
[0, 7212]
[0, 7227]
[0, 7611]
[0, 8066]
[0, 9791]
[0, 9901]
[0, 10371]
[0, 11090]
[0, 11094]
[0, 11386]
[0, 11752]
Yes
※AtCoderテストケースより

[入力例]
50 
25 150
24 160
23 170
22 180
21 190
20 200
19 210
18 220
17 230
16 240
15 250
14 260
13 270
12 280
11 290
10 300
9 310
8 320
7 330
6 340
5 350
4 360
3 370
2 380
1 390
1 400
2 410
3 420
4 430
5 440
6 450
7 460
8 470
9 480
10 490
11 500
12 510
13 520
14 530
15 540
16 550
17 560
18 570
19 580
20 590
21 600
22 610
23 620
24 630
25 640

[出力例(debug版)]
[125, 150]
[101, 150]
[78, 150]
[56, 150]
[35, 150]
[15, 150]
[0, 154]
[0, 172]
[0, 189]
[0, 205]
[0, 220]
[0, 234]
[0, 247]
[0, 259]
[0, 270]
[0, 280]
[0, 289]
[0, 297]
[0, 304]
[0, 310]
[0, 315]
[0, 319]
[0, 322]
[0, 324]
[0, 325]
[0, 326]
[0, 328]
[0, 331]
[0, 335]
[0, 340]
[0, 346]
[0, 353]
[0, 361]
[0, 370]
[0, 380]
[0, 391]
[0, 403]
[0, 416]
[0, 430]
[0, 445]
[0, 461]
[0, 478]
[0, 496]
[0, 515]
[0, 535]
[0, 556]
[0, 578]
[0, 601]
[0, 625]
[0, 650]
No

[入力例]
50 
25 200
24 220
23 240
22 260
21 280
20 300
19 320
18 340
17 360
16 380
15 400
14 420
13 440
12 460
11 480
10 500
9 520
8 540
7 560
6 580
5 600
4 620
3 640
2 660
1 680
1 700
2 720
3 740
4 760
5 780
6 800
7 820
8 840
9 860
10 880
11 900
12 920
13 940
14 960
15 980
16 1000
17 1020
18 1040
19 1060
20 1080
21 1100
22 1120
23 1140
24 1160
25 1180

[出力例(debug版)]
[175, 200]
[151, 200]
[128, 200]
[106, 200]
[85, 200]
[65, 200]
[46, 200]
[28, 200]
[11, 200]
[0, 205]
[0, 220]
[0, 234]
[0, 247]
[0, 259]
[0, 270]
[0, 280]
[0, 289]
[0, 297]
[0, 304]
[0, 310]
[0, 315]
[0, 319]
[0, 322]
[0, 324]
[0, 325]
[0, 326]
[0, 328]
[0, 331]
[0, 335]
[0, 340]
[0, 346]
[0, 353]
[0, 361]
[0, 370]
[0, 380]
[0, 391]
[0, 403]
[0, 416]
[0, 430]
[0, 445]
[0, 461]
[0, 478]
[0, 496]
[0, 515]
[0, 535]
[0, 556]
[0, 578]
[0, 601]
[0, 625]
[0, 650]
Yes

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

288

289

290

291

292

293

294

295

296

297

298

299

300

301

302

303

304

305

306

307

308

309

310

311

312

313

314

315

316

317

318

319

320

321

322

323

324

325

326

327

328

[入力例]

2 1

[出力例(debug版)]

[-1, 1]

[入力例]

1 4

2 4

1 4

[出力例(debug版)]

[3, 4]

[2, 4]

[0, 4]

Yes

[入力例]

2 4

1 9

1 8

4 9

3 12

[出力例(debug版)]

[2, 4]

[1, 4]

[0, 4]

[0, 8]

[0, 11]

Yes

※AtCoderテストケースより

[入力例]

334 1000

[出力例(debug版)]

[666, 1000]

[332, 1000]

[0, 1002]

※AtCoderテストケースより

[入力例]

384 8895

1725 9791

170 1024

4 11105

2 6

578 1815

702 3352

143 5141

1420 6980

24 1602

849 999

76 7586

85 5570

444 4991

719 11090

470 10708

1137 4547

455 9003

110 9901

15 8578

368 3692

104 1286

3 4

366 12143

7 6649

610 2374

152 7324

4 7042

292 11386

334 5720

[出力例(debug版)]

[1, 4]

[0, 5]

[0, 854]

[0, 1024]

[0, 1128]

[0, 1152]

[0, 1730]

[0, 2340]

[0, 3042]

[0, 3410]

[0, 4547]

[0, 4991]

[0, 5134]

[0, 5219]

[0, 5553]

[0, 5560]

[0, 6980]

[0, 6984]

[0, 7136]

[0, 7212]

[0, 7227]

[0, 7611]

[0, 8066]

[0, 9791]

[0, 9901]

[0, 10371]

[0, 11090]

[0, 11094]

[0, 11386]

[0, 11752]

Yes

※AtCoderテストケースより

[入力例]

25 150

24 160

23 170

22 180

21 190

20 200

19 210

18 220

17 230

16 240

15 250

14 260

13 270

12 280

11 290

10 300

9 310

8 320

7 330

6 340

5 350

4 360

3 370

2 380

1 390

1 400

2 410

3 420

4 430

5 440

6 450

7 460

8 470

9 480

10 490

11 500

12 510

13 520

14 530

15 540

16 550

17 560

18 570

19 580

20 590

21 600

22 610

23 620

24 630

25 640

[出力例(debug版)]

[125, 150]

[101, 150]

[78, 150]

[56, 150]

[35, 150]

[15, 150]

[0, 154]

[0, 172]

[0, 189]

[0, 205]

[0, 220]

[0, 234]

[0, 247]

[0, 259]

[0, 270]

[0, 280]

[0, 289]

[0, 297]

[0, 304]

[0, 310]

[0, 315]

[0, 319]

[0, 322]

[0, 324]

[0, 325]

[0, 326]

[0, 328]

[0, 331]

[0, 335]

[0, 340]

[0, 346]

[0, 353]

[0, 361]

[0, 370]

[0, 380]

[0, 391]

[0, 403]

[0, 416]

[0, 430]

[0, 445]

[0, 461]

[0, 478]

[0, 496]

[0, 515]

[0, 535]

[0, 556]

[0, 578]

[0, 601]

[0, 625]

[0, 650]

[入力例]

25 200

24 220

23 240

22 260

21 280

20 300

19 320

18 340

17 360

16 380

15 400

14 420

13 440

12 460

11 480

10 500

9 520

8 540

7 560

6 580

5 600

4 620

3 640

2 660

1 680

1 700

2 720

3 740

4 760

5 780

6 800

7 820

8 840

9 860

10 880

11 900

12 920

13 940

14 960

15 980

16 1000

17 1020

18 1040

19 1060

20 1080

21 1100

22 1120

23 1140

24 1160

25 1180

[出力例(debug版)]

[175, 200]

[151, 200]

[128, 200]

[106, 200]

[85, 200]

[65, 200]

[46, 200]

[28, 200]

[11, 200]

[0, 205]

[0, 220]

[0, 234]

[0, 247]

[0, 259]

[0, 270]

[0, 280]

[0, 289]

[0, 297]

[0, 304]

[0, 310]

[0, 315]

[0, 319]

[0, 322]

[0, 324]

[0, 325]

[0, 326]

[0, 328]

[0, 331]

[0, 335]

[0, 340]

[0, 346]

[0, 353]

[0, 361]

[0, 370]

[0, 380]

[0, 391]

[0, 403]

[0, 416]

[0, 430]

[0, 445]

[0, 461]

[0, 478]

[0, 496]

[0, 515]

[0, 535]

[0, 556]

[0, 578]

[0, 601]

[0, 625]

[0, 650]

Yes

■参照サイト
AtCoder Beginner Contest 131

2019年7月6日

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

C++の練習を兼ねて, AtCoder Beginner Contest 129 の問題D (D – Lamp) を解いてみた.

■感想.
1. 解答を見る前に, 解けたので, 及第点は取れたと思う.
2. 復習したい問題が, たくさん残っているので, 時間取って進めていきたいと思う.

本家のサイトABC 129解説をご覧下さい.

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

#include <bits/stdc++.h>
using namespace std;
const int MAX = 2002;
char grid[MAX][MAX];
int r[MAX][MAX], c[MAX][MAX];
int rGrid[MAX][MAX], cGrid[MAX][MAX];

int main() {
    
    // 1. 入力情報取得.
    int H, W;
    scanf("%d %d", &H, &W);
    for(int i = 0; i < MAX; i++) for(int j = 0; j < MAX; j++) grid[i][j] = '#';
    for(int i = 0; i < H; i++) scanf("%s", grid + i), grid[i][W] = '#'; // delete null character `\0`.
    
    // for(int i = 0; i < H + 1; i++){
    //     for(int j = 0; j < W + 1; j++) printf("%c", grid[i][j]);
    //     printf("\n");
    // }
    
    // 2. 行方向で照らされるマスの個数をカウント.
    for(int i = 0; i < H; i++){
        int rIndex = 1;
        for(int j = 0; j < W; j++){
            // '.' が 連続出現している場合は, カウントアップ.
            if(grid[i][j] == '.') r[i][rIndex]++, rGrid[i][j] = rIndex;
            // '.' の 連続出現が終わったら, rIndex を インクリメントして, 次のカウントアップに備える.
            if(grid[i][j] == '#' && j > 0 && grid[i][j - 1] == '.') rIndex++;
        }
    }

    // 3. 列方向で照らされるマスの個数をカウント.
    for(int j = 0; j < W; j++){
        int cIndex = 1;
        for(int i = 0; i < H; i++){
            // '.' が 連続出現している場合は, カウントアップ.
            if(grid[i][j] == '.') c[j][cIndex]++, cGrid[i][j] = cIndex;
            // '.' の 連続出現が終わったら, cIndex を インクリメントして, 次のカウントアップに備える.
            if(grid[i][j] == '#' && i > 0 && grid[i - 1][j] == '.') cIndex++;
        }
    }
    
    // for(int i = 0; i < H + 1; i++){
    //     for(int j = 0; j < W + 1; j++) printf("%d ", rGrid[i][j]);
    //     printf("\n");
    // }
    // printf("\n");
    // for(int i = 0; i < H + 1; i++){
    //     for(int j = 0; j < W + 1; j++) printf("%d ", r[i][j]);
    //     printf("\n");
    // }
    // printf("\n");
    // for(int i = 0; i < H + 1; i++){
    //     for(int j = 0; j < W + 1; j++) printf("%d ", cGrid[i][j]);
    //     printf("\n");
    // }
    // printf("\n");
    // for(int i = 0; i < H + 1; i++){
    //     for(int j = 0; j < W + 1; j++) printf("%d ", c[i][j]);
    //     printf("\n");
    // }
    
    // 4. 照らされるマスの個数の最大値を計算.
    int ans = 0;
    for(int i = 0; i < H; i++){
        for(int j = 0; j < W; j++){
            int rIndex = rGrid[i][j], cIndex = cGrid[i][j];
            int count = r[i][rIndex] + c[j][cIndex] - 1;
            ans = max(ans, count);
        }
    }

    // 5. 出力 ～ 後処理.
    printf("%d\n", ans);
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

const int MAX = 2002;

char grid[MAX][MAX];

int r[MAX][MAX], c[MAX][MAX];

int rGrid[MAX][MAX], cGrid[MAX][MAX];

int main() {

// 1. 入力情報取得.

int H, W;

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

for(int i = 0; i < MAX; i++) for(int j = 0; j < MAX; j++) grid[i][j] = '#';

for(int i = 0; i < H; i++) scanf("%s", grid + i), grid[i][W] = '#'; // delete null character `\0`.

// for(int i = 0; i < H + 1; i++){

// for(int j = 0; j < W + 1; j++) printf("%c", grid[i][j]);

// printf("\n");

// }

// 2. 行方向で照らされるマスの個数をカウント.

for(int i = 0; i < H; i++){

int rIndex = 1;

for(int j = 0; j < W; j++){

// '.' が連続出現している場合は, カウントアップ.

if(grid[i][j] == '.') r[i][rIndex]++, rGrid[i][j] = rIndex;

// '.' の連続出現が終わったら, rIndex をインクリメントして, 次のカウントアップに備える.

if(grid[i][j] == '#' && j > 0 && grid[i][j - 1] == '.') rIndex++;

}

// 3. 列方向で照らされるマスの個数をカウント.

for(int j = 0; j < W; j++){

int cIndex = 1;

for(int i = 0; i < H; i++){

// '.' が連続出現している場合は, カウントアップ.

if(grid[i][j] == '.') c[j][cIndex]++, cGrid[i][j] = cIndex;

// '.' の連続出現が終わったら, cIndex をインクリメントして, 次のカウントアップに備える.

if(grid[i][j] == '#' && i > 0 && grid[i - 1][j] == '.') cIndex++;

}

// for(int i = 0; i < H + 1; i++){

// for(int j = 0; j < W + 1; j++) printf("%d ", rGrid[i][j]);

// printf("\n");

// }

// printf("\n");

// for(int i = 0; i < H + 1; i++){

// for(int j = 0; j < W + 1; j++) printf("%d ", r[i][j]);

// printf("\n");

// }

// printf("\n");

// for(int i = 0; i < H + 1; i++){

// for(int j = 0; j < W + 1; j++) printf("%d ", cGrid[i][j]);

// printf("\n");

// }

// printf("\n");

// for(int i = 0; i < H + 1; i++){

// for(int j = 0; j < W + 1; j++) printf("%d ", c[i][j]);

// printf("\n");

// }

// 4. 照らされるマスの個数の最大値を計算.

int ans = 0;

for(int i = 0; i < H; i++){

for(int j = 0; j < W; j++){

int rIndex = rGrid[i][j], cIndex = cGrid[i][j];

int count = r[i][rIndex] + c[j][cIndex] - 1;

ans = max(ans, count);

}

// 5. 出力～後処理.

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

return 0;

}

[入力例]
4 6
#..#..
.....#
....#.
#.#...

[出力例(debug版)]
0 1 1 0 2 2 0 
1 1 1 1 1 0 0 
1 1 1 1 0 2 0 
0 1 0 2 2 2 0 
0 0 0 0 0 0 0 

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

0 1 1 0 1 1 0 
1 1 1 1 1 0 0 
1 1 1 1 0 2 0 
0 1 0 1 2 2 0 
0 0 0 0 0 0 0 

0 2 0 0 0 0 0 
0 4 0 0 0 0 0 
0 3 0 0 0 0 0 
0 3 0 0 0 0 0 
0 2 1 0 0 0 0 
8
※AtCoderテストケースより

[入力例]
8 8
..#...#.
....#...
##......
..###..#
...#..#.
##....#.
#...#...
###.#..#

[出力例(debug版)]
1 1 0 2 2 2 0 3 0 
1 1 1 1 0 2 2 2 0 
0 0 1 1 1 1 1 1 0 
1 1 0 0 0 2 2 0 0 
1 1 1 0 2 2 0 3 0 
0 0 1 1 1 1 0 2 0 
0 1 1 1 0 2 2 2 0 
0 0 0 1 0 2 2 0 0 
0 0 0 0 0 0 0 0 0 

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

1 1 0 1 1 1 0 1 0 
1 1 1 1 0 1 1 1 0 
0 0 1 1 2 1 1 1 0 
2 2 0 0 0 1 1 0 0 
2 2 2 0 3 1 0 2 0 
0 0 2 2 3 1 0 2 0 
0 3 2 2 0 1 2 2 0 
0 0 0 2 0 1 2 0 0 
0 0 0 0 0 0 0 0 0 

0 2 2 0 0 0 0 0 0 
0 2 2 1 0 0 0 0 0 
0 2 3 0 0 0 0 0 0 
0 3 3 0 0 0 0 0 0 
0 1 1 2 0 0 0 0 0 
0 8 0 0 0 0 0 0 0 
0 3 2 0 0 0 0 0 0 
0 3 3 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 
13
※AtCoderテストケースより

[入力例]
100 100
........#.........##..#.#.##..#.#..#..#...##...#...#....#........##.....#..#.##.##..#..#....#...###.
#...#..#...#....##..#....#...#.#.....#...#..#.#..#...#.....#..##...#......#.....##....###....#..#.#.
............#.......##.##.....##....#.#.#.......#....##.#......#.#....#...###....#...#....#.#....#..
.#...#.#...#..##.#...#.#...###..............#..##........#......#....#.#.#.....#.........#.##.###...
.........##...##..#.....#.#.###..#....#.#..##...#..#...#.....###.##........#..#......##.#.#....#.#..
.....##......#.......##...#.#....#...............#.....##..#..#...#.....##..#..#.##...........#.##..
....#.........##.##.#.#.##.#####..#...#........####.##...##....#...#.....#...#.#.#..........#.....#.
.#.#.....#..#....#........#.#.###.....#...#.#.........#......#....#.#........##.##..#.##.#...#....##
.##.#..#...##...#######....#.##.###..........##....##..#..##.##.##...#....#...####...#.#.#...###.#..
....#....#....#.##.#.....#...#...#.....#..#.####........#.#..##...#....#..##....#.#...#........#....
##...###.#...#.#.#.....#.......##.##....#..#..#.#.#..#..#.###...#.#.....#..#.##.##..#.#..#.#......#.
#.#.##.....#......#......#..#.##......###.##.....#.#..##....#...#.#..#........###.#...###......#.#..
#...##.#....#....#....#.....#...##.##.#....#.....#....#.....#....#....#..#....####.........#....#...
..#..##.#....#.#######..#...#.......#.#.##.#.....#...#....##.###..........#..#.#....#....#..##.##...
......#.#.#.........#.....#..#..##.....##.......#.#.#....#####.#..#...##.......#...###...#..#..##.##
#.#.#..........#......#...#...#.#.........#......##..###...........##...####..##.#..#.......#.....##
........#.#..............#.#.#.##....#.....##....#.....#.....#...#........#....######.#..###........
......#.......#...#..#.#...#.....##...#.#..####.........##..##.......#...##...#..####.#..#.#....#..#
.......#....#.#.#...##.##...##........#...#........#..#.#..#.##...#......####......#......#.........
###..#....##...#..#..#..#......#..#.#......#..####.##.....####.#...#..##...#...##...##...#...#....#.
.##......#....######.#.....#......##.#...#.##.##..##............####..###........#.#...#..#..#.##...
#..##....#.#.......###..#.......#.#..#.#.#.##.....#.....#....#...##........#.#......#.#.....#....##.
#.....#....#.#..#...##.#....#..#.....#.##.......#....##..#.##....#..##..#........#.........#.....###
..##.##...##......#.##...#.#.#.#...#..#...###......##.#...###.......##..........#......#..#..#...##.
#...#..#....#....###.#.......#..##..##.....#......#...........##.....#..###..##..#.#.....#..###..#..
..#..#..#.##....##...#....#......##.#...##..#....#.##....###.#....#......##.....#..#...#...##.......
...#...#..#..#..#...###..#..##............#...##...#.#.....##.#.....#.......#.##..#......#.....##...
..#....#........#.#...#....#..#.......#..#.....#.#....#.........#...###.....##.##.##.....##.#.....#.
.#.#..##...#.##..#..#.##.#..#...##........#.#.#....#..#.#..#....#..#..#..##.#.......##....###....##.
...#..##..#.##..#...#..##.#.#........#.....#.#.....#.##.###......#..###....##....#....#.##....#..###
.......#....####...#.....#..##...#...#..#....#.##.#.#....#..#...#.........##.#..##.......#.....##...
###..#...#.#..##...##..##.##.#.#.....#....#......#........#......#.....#........#..#..........#.#.#.
#...#....#...####....#..#..#...#.#...#.#.##....#...#...#...#...#.#.#..#...#.#..#....#.#.....##.#....
...#..##..##.....#.#..#..#.##.##.#..#....#..#......#.##.....#.....#.........#...###.##.....#...###..
..#.####...#.#....#.##...#.......#.....###......#..##......###.##...##...#...##......#.#..#.#..#....
##.##.#.##.#......#..#.......#....#........#.#.##.....##...##.#.....#..#....#..#.##.#...#..###..#.#.
....####.....#.....#.##.#.#..##...##.##.#.#...##.#..#..#....#...#.#..#....##...###...#..##.#..#...##
.#..#..#.#..#..##.....#.##.......#.#...##..........#..#.##.#.....#....#..#...#.......###..#.#..#.#..
......#.#....#..#.#.......#...#.....#.##..#.#..#.#.#.#.#..##.#...#...#..#...#....##..#.#.#.#....###.
#.#..#.##.#.......#............##.#.#..#.....#...#....##.............#..#.....#.....#.#....#....#...
#.....#.#.........#....##.###.....#..#...##...#.....#...#....#.#...###...####.#...#.#...#...........
.#....#....#.#....##.#..#...##.#...###....#.....##.##..###...#.#.#....#...#...#.....#.#####.#.#.....
##.###....#........#..#....#....##....##.#.#..##..###....#..##....#.#...##....#..#.#.#.#...#.##....#
...#..##.##..........#....#...#....#.##.###.#....#.##....#............#.#..#.##...##...#.#.....#.#.#
#....#....#.#...##......#.#.#....#...##....###...#..#...#...#.###...#....##..#....#..##...#......#..
......#..#......###..###....#....#.#............#.##..##.....#.#...#........#...#...####.....##...#.
.#.#..#...#.......#......#.................#.###.###..#.##...#.#.#......#..#..#.....#..#..####......
#.......#.#...#..#..#..#.#...##.#.#.###.##........#.......#......##...###....#...##...#.....###.....
...#.....#...#..##...#.....###......#....#....#.....##.#........###.....#....#.....###...#.#....##..
........###.........#.....#.#..#.#.###..###.......#.###.....#.#..##..##.......#.#.#..##.#..#.#..#.#.
.#..#.....#.##.####.........#......####...##..#.......#..#...##.#............#.#......##....##.##..#
..#..#.#...#......##.....###...#....#.#.##....#..##.#.#..#..#..#........#....#...#..#....#...##...#.
#..#.#..#......#.#..#..#.###....#....#...#.#..#.....##..#...#.#.#.#....#...#.........#...####.#..##.
..#....##.#..#.#.....#..#........#....#.#.#.#...#####.......#.##....#.#.#..##...#...##.....#.#.#..#.
#..#.###......##..........#..........####..##.#..#.#..#.......#..#....#.##..#.#....#..#.....#...####
#.#.#..........#####.#....##...#........##.##.#.#..#.#..#.#.##............#.##.#....#.#..#...#.#....
.....##..#.#..##....#...##...........#.#..#........###.#........#..###.#......##.##..####..##.....#.
#....#....##................#.....###....#...#####............#...##....#...#.#.#......##..#..#.....
.................#.........##..##..............#.#...#....#.##.#.#..#...#...#.##...........#...##...
#....#.#......#.#..#.#...##........##.###....#...#.#....#.#....#......#.#.#.#.#.....#.............##
.##.##...#.....#..#.....#.#..##....#..#.....#..#.....##.......#.##..#.....##.#.#..#...##.........###
###..#..............#.##....#..#.#..###...#.###..##......#..##.##...#...#.#..#..#.##...###.#...#....
.......#....#.#..#.#.....###.......#.#..##..#..#......##.#..#.#....##..#......#........#......#..##.
.#.#....#..#....#....#.#.#...#..#...#.#..#....##...##....#.#####.#..##......#..##...##.#....#..#....
.#......#....#..#.....##..#..##...#....#...#..##.#..#..##.............####.##.#.........#.##.#....#.
#..##.......#..##...#..#.###..#..#....##..###.###..###..#....................##.....#.#..#..#.#.....
#.###.#.#..#.....###.#.##...#.#....#...#.#..#.###.##.##.#.##..#..#......................##.##....#..
.......#................#....#....#...#.........#.#.#..###.#...###.....#............#..#............
............##..##...#.......#..#..##.....#..#.....###..#.####..#.....##.....##.#.#..#..#.##.#.....#
......#..###.......#...#..#..#.....#....#..........#....................#.#..#..#.##....#....###....
..#..#.......#....#..##..#.#..####.#..#.#......###...##...#..#........#.....##.#.#.#............##.#
..##.#.#......##.....#.#.#...##..#........#.##....#......#.....#.#.#..##..#..#......#...#.......##..
...##..##.#...#...#........#.#..##......##.#....#...#..#..##....#....#.##..#....#..#..#.....##.##..#
.........#..........#..#....#.#......#.##....#..##...##...#.##...##..#.##.........#...#.#...#...#...
##.......##.#.#.#.#....##..#......##..##....#.....##.##.###...##.#..#...##..##.#.....#..#.#..#..##..
#.#.....##.....#.....##..##..#.#...#.....#.#..##.......#......##.#...#.#.......##.##.....#....#.####
.........##...##..................##...#...##...##..#.#..#..#..........#.#.........#.....###..#..#..
....###.##.........##.##..............##.#...#.#..#.#...#...#..#.##........#...#.#.............#....
..#..##..#.#.......#.###...#...#.#...##.#........#.....#.##.#.........#..#.....#...##...#....##...#.
#....####.##...#.###.....##.#.####.#.#...#....#............#..#...#.........#.....#...#...........##
.#......#....#.......#..#...##....#.#.##.#..#.#........##.#..#.#......#...#.#..##........#...#....#.
....#....#.....#..##...##..#..#..#....#.#..#...#......###.......#.......###.........##.#...###.###..
..##...#...##.#...#.#...##....#....#..........#.##.....#.#...#.....#..#...##.####...##..#.##.#...##.
.......#.##......#..#.#.......##....#..##..#....#.###.#...#.#.#...#.#..#.##..#..##.#.....#...###.#..
#.........#.#....###.......##..........#..#...#####......#....#...#.#.#.###.#.#.####..#...#.........
####..#.###..#.#....#..#...#..#...##..##..#....#.#....##.....##.......##....#.#....#.##.......#.....
##.........#......#....#.....#.##...#....#.....###...##..##.#.#........####.....#..#.#####...#...##.
...#....#......#.#.......#....#.....#.#.........#.#...##...##....##.#.#.....#....###....###...#..#..
#.#........#..#.##...#..#.....#..#...#..##.##....#.#.####.#.......#....##..#.#....#..#..............
............#.##...#....###...#.#...........#.#..#.......#....#........###..#..#...###..###..#.###..
.#..####..#..#......#...##..#....#..#....#....#......#.......##......#...##..#....#.#..#..#..#...##.
#..#...##.##.##.#.#....#......#.....#.........##....#..........####.....#..#.###..#....###..#.#.#.#.
##..##..##.....#.####......##....#...#.....#..##..##......#.#.#.#...........#.....#..#.#.#.........#
.##....##...........##........#.........##......#..#.#...#........#.#.##.##..#........#...#........#
.#..#......#..........###.#..##.#.#......#...###.....##...#..##....####......#......................
...#...#..#.#..#..#...#....###.##.#.........#...#.##....#.#..##.#.....#....#.....##....#.##.##......
.##........#.......##...#....##.#.###.#.#.....#..#.....##..#.#.....###......#..#...#...#........#..#
.........#....................#..##....#.#...#..#..#...#.........#.....#..##.....#.#.##..#...#...#..
#.....##....#.....#..#...#....##..#...##........#.##.#....#.##..#...........##..##.#.#...#..###....#
....#.##..#.#...#..##..............#..#..##..........##....#..##..#....#####..###..##...#.##.##..#..

[出力例]
37

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

[入力例]

4 6

#..#..

.....#

....#.

#.#...

[出力例(debug版)]

0 1 1 0 2 2 0

1 1 1 1 1 0 0

1 1 1 1 0 2 0

0 1 0 2 2 2 0

0 0 0 0 0 0 0

0 2 2 0 0 0 0

0 5 0 0 0 0 0

0 4 1 0 0 0 0

0 1 3 0 0 0 0

0 0 0 0 0 0 0

0 1 1 0 1 1 0

1 1 1 1 1 0 0

1 1 1 1 0 2 0

0 1 0 1 2 2 0

0 0 0 0 0 0 0

0 2 0 0 0 0 0

0 4 0 0 0 0 0

0 3 0 0 0 0 0

0 2 1 0 0 0 0

※AtCoderテストケースより

[入力例]

8 8

..#...#.

....#...

##......

..###..#

...#..#.

##....#.

#...#...

###.#..#

[出力例(debug版)]

1 1 0 2 2 2 0 3 0

1 1 1 1 0 2 2 2 0

0 0 1 1 1 1 1 1 0

1 1 0 0 0 2 2 0 0

1 1 1 0 2 2 0 3 0

0 0 1 1 1 1 0 2 0

0 1 1 1 0 2 2 2 0

0 0 0 1 0 2 2 0 0

0 0 0 0 0 0 0 0 0

0 2 3 1 0 0 0 0 0

0 4 3 0 0 0 0 0 0

0 6 0 0 0 0 0 0 0

0 2 2 0 0 0 0 0 0

0 3 2 1 0 0 0 0 0

0 4 1 0 0 0 0 0 0

0 3 3 0 0 0 0 0 0

0 1 2 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0

1 1 0 1 1 1 0 1 0

1 1 1 1 0 1 1 1 0

0 0 1 1 2 1 1 1 0

2 2 0 0 0 1 1 0 0

2 2 2 0 3 1 0 2 0

0 0 2 2 3 1 0 2 0

0 3 2 2 0 1 2 2 0

0 0 0 2 0 1 2 0 0

0 0 0 0 0 0 0 0 0

0 2 2 0 0 0 0 0 0

0 2 2 1 0 0 0 0 0

0 2 3 0 0 0 0 0 0

0 3 3 0 0 0 0 0 0

0 1 1 2 0 0 0 0 0

0 8 0 0 0 0 0 0 0

0 3 2 0 0 0 0 0 0

0 3 3 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0

※AtCoderテストケースより

[入力例]

100 100

........#.........##..#.#.##..#.#..#..#...##...#...#....#........##.....#..#.##.##..#..#....#...###.

#...#..#...#....##..#....#...#.#.....#...#..#.#..#...#.....#..##...#......#.....##....###....#..#.#.

............#.......##.##.....##....#.#.#.......#....##.#......#.#....#...###....#...#....#.#....#..

.#...#.#...#..##.#...#.#...###..............#..##........#......#....#.#.#.....#.........#.##.###...

.........##...##..#.....#.#.###..#....#.#..##...#..#...#.....###.##........#..#......##.#.#....#.#..

.....##......#.......##...#.#....#...............#.....##..#..#...#.....##..#..#.##...........#.##..

....#.........##.##.#.#.##.#####..#...#........####.##...##....#...#.....#...#.#.#..........#.....#.

.#.#.....#..#....#........#.#.###.....#...#.#.........#......#....#.#........##.##..#.##.#...#....##

.##.#..#...##...#######....#.##.###..........##....##..#..##.##.##...#....#...####...#.#.#...###.#..

....#....#....#.##.#.....#...#...#.....#..#.####........#.#..##...#....#..##....#.#...#........#....

##...###.#...#.#.#.....#.......##.##....#..#..#.#.#..#..#.###...#.#.....#..#.##.##..#.#..#.#......#.

#.#.##.....#......#......#..#.##......###.##.....#.#..##....#...#.#..#........###.#...###......#.#..

#...##.#....#....#....#.....#...##.##.#....#.....#....#.....#....#....#..#....####.........#....#...

..#..##.#....#.#######..#...#.......#.#.##.#.....#...#....##.###..........#..#.#....#....#..##.##...

......#.#.#.........#.....#..#..##.....##.......#.#.#....#####.#..#...##.......#...###...#..#..##.##

#.#.#..........#......#...#...#.#.........#......##..###...........##...####..##.#..#.......#.....##

........#.#..............#.#.#.##....#.....##....#.....#.....#...#........#....######.#..###........

......#.......#...#..#.#...#.....##...#.#..####.........##..##.......#...##...#..####.#..#.#....#..#

.......#....#.#.#...##.##...##........#...#........#..#.#..#.##...#......####......#......#.........

###..#....##...#..#..#..#......#..#.#......#..####.##.....####.#...#..##...#...##...##...#...#....#.

.##......#....######.#.....#......##.#...#.##.##..##............####..###........#.#...#..#..#.##...

#..##....#.#.......###..#.......#.#..#.#.#.##.....#.....#....#...##........#.#......#.#.....#....##.

#.....#....#.#..#...##.#....#..#.....#.##.......#....##..#.##....#..##..#........#.........#.....###

..##.##...##......#.##...#.#.#.#...#..#...###......##.#...###.......##..........#......#..#..#...##.

#...#..#....#....###.#.......#..##..##.....#......#...........##.....#..###..##..#.#.....#..###..#..

..#..#..#.##....##...#....#......##.#...##..#....#.##....###.#....#......##.....#..#...#...##.......

...#...#..#..#..#...###..#..##............#...##...#.#.....##.#.....#.......#.##..#......#.....##...

..#....#........#.#...#....#..#.......#..#.....#.#....#.........#...###.....##.##.##.....##.#.....#.

.#.#..##...#.##..#..#.##.#..#...##........#.#.#....#..#.#..#....#..#..#..##.#.......##....###....##.

...#..##..#.##..#...#..##.#.#........#.....#.#.....#.##.###......#..###....##....#....#.##....#..###

.......#....####...#.....#..##...#...#..#....#.##.#.#....#..#...#.........##.#..##.......#.....##...

###..#...#.#..##...##..##.##.#.#.....#....#......#........#......#.....#........#..#..........#.#.#.

#...#....#...####....#..#..#...#.#...#.#.##....#...#...#...#...#.#.#..#...#.#..#....#.#.....##.#....

...#..##..##.....#.#..#..#.##.##.#..#....#..#......#.##.....#.....#.........#...###.##.....#...###..

..#.####...#.#....#.##...#.......#.....###......#..##......###.##...##...#...##......#.#..#.#..#....

##.##.#.##.#......#..#.......#....#........#.#.##.....##...##.#.....#..#....#..#.##.#...#..###..#.#.

....####.....#.....#.##.#.#..##...##.##.#.#...##.#..#..#....#...#.#..#....##...###...#..##.#..#...##

.#..#..#.#..#..##.....#.##.......#.#...##..........#..#.##.#.....#....#..#...#.......###..#.#..#.#..

......#.#....#..#.#.......#...#.....#.##..#.#..#.#.#.#.#..##.#...#...#..#...#....##..#.#.#.#....###.

#.#..#.##.#.......#............##.#.#..#.....#...#....##.............#..#.....#.....#.#....#....#...

#.....#.#.........#....##.###.....#..#...##...#.....#...#....#.#...###...####.#...#.#...#...........

.#....#....#.#....##.#..#...##.#...###....#.....##.##..###...#.#.#....#...#...#.....#.#####.#.#.....

##.###....#........#..#....#....##....##.#.#..##..###....#..##....#.#...##....#..#.#.#.#...#.##....#

...#..##.##..........#....#...#....#.##.###.#....#.##....#............#.#..#.##...##...#.#.....#.#.#

#....#....#.#...##......#.#.#....#...##....###...#..#...#...#.###...#....##..#....#..##...#......#..

......#..#......###..###....#....#.#............#.##..##.....#.#...#........#...#...####.....##...#.

.#.#..#...#.......#......#.................#.###.###..#.##...#.#.#......#..#..#.....#..#..####......

#.......#.#...#..#..#..#.#...##.#.#.###.##........#.......#......##...###....#...##...#.....###.....

...#.....#...#..##...#.....###......#....#....#.....##.#........###.....#....#.....###...#.#....##..

........###.........#.....#.#..#.#.###..###.......#.###.....#.#..##..##.......#.#.#..##.#..#.#..#.#.

.#..#.....#.##.####.........#......####...##..#.......#..#...##.#............#.#......##....##.##..#

..#..#.#...#......##.....###...#....#.#.##....#..##.#.#..#..#..#........#....#...#..#....#...##...#.

#..#.#..#......#.#..#..#.###....#....#...#.#..#.....##..#...#.#.#.#....#...#.........#...####.#..##.

..#....##.#..#.#.....#..#........#....#.#.#.#...#####.......#.##....#.#.#..##...#...##.....#.#.#..#.

#..#.###......##..........#..........####..##.#..#.#..#.......#..#....#.##..#.#....#..#.....#...####

#.#.#..........#####.#....##...#........##.##.#.#..#.#..#.#.##............#.##.#....#.#..#...#.#....

.....##..#.#..##....#...##...........#.#..#........###.#........#..###.#......##.##..####..##.....#.

#....#....##................#.....###....#...#####............#...##....#...#.#.#......##..#..#.....

.................#.........##..##..............#.#...#....#.##.#.#..#...#...#.##...........#...##...

#....#.#......#.#..#.#...##........##.###....#...#.#....#.#....#......#.#.#.#.#.....#.............##

.##.##...#.....#..#.....#.#..##....#..#.....#..#.....##.......#.##..#.....##.#.#..#...##.........###

###..#..............#.##....#..#.#..###...#.###..##......#..##.##...#...#.#..#..#.##...###.#...#....

.......#....#.#..#.#.....###.......#.#..##..#..#......##.#..#.#....##..#......#........#......#..##.

.#.#....#..#....#....#.#.#...#..#...#.#..#....##...##....#.#####.#..##......#..##...##.#....#..#....

.#......#....#..#.....##..#..##...#....#...#..##.#..#..##.............####.##.#.........#.##.#....#.

#..##.......#..##...#..#.###..#..#....##..###.###..###..#....................##.....#.#..#..#.#.....

#.###.#.#..#.....###.#.##...#.#....#...#.#..#.###.##.##.#.##..#..#......................##.##....#..

.......#................#....#....#...#.........#.#.#..###.#...###.....#............#..#............

............##..##...#.......#..#..##.....#..#.....###..#.####..#.....##.....##.#.#..#..#.##.#.....#

......#..###.......#...#..#..#.....#....#..........#....................#.#..#..#.##....#....###....

..#..#.......#....#..##..#.#..####.#..#.#......###...##...#..#........#.....##.#.#.#............##.#

..##.#.#......##.....#.#.#...##..#........#.##....#......#.....#.#.#..##..#..#......#...#.......##..

...##..##.#...#...#........#.#..##......##.#....#...#..#..##....#....#.##..#....#..#..#.....##.##..#

.........#..........#..#....#.#......#.##....#..##...##...#.##...##..#.##.........#...#.#...#...#...

##.......##.#.#.#.#....##..#......##..##....#.....##.##.###...##.#..#...##..##.#.....#..#.#..#..##..

#.#.....##.....#.....##..##..#.#...#.....#.#..##.......#......##.#...#.#.......##.##.....#....#.####

.........##...##..................##...#...##...##..#.#..#..#..........#.#.........#.....###..#..#..

....###.##.........##.##..............##.#...#.#..#.#...#...#..#.##........#...#.#.............#....

..#..##..#.#.......#.###...#...#.#...##.#........#.....#.##.#.........#..#.....#...##...#....##...#.

#....####.##...#.###.....##.#.####.#.#...#....#............#..#...#.........#.....#...#...........##

.#......#....#.......#..#...##....#.#.##.#..#.#........##.#..#.#......#...#.#..##........#...#....#.

....#....#.....#..##...##..#..#..#....#.#..#...#......###.......#.......###.........##.#...###.###..

..##...#...##.#...#.#...##....#....#..........#.##.....#.#...#.....#..#...##.####...##..#.##.#...##.

.......#.##......#..#.#.......##....#..##..#....#.###.#...#.#.#...#.#..#.##..#..##.#.....#...###.#..

#.........#.#....###.......##..........#..#...#####......#....#...#.#.#.###.#.#.####..#...#.........

####..#.###..#.#....#..#...#..#...##..##..#....#.#....##.....##.......##....#.#....#.##.......#.....

##.........#......#....#.....#.##...#....#.....###...##..##.#.#........####.....#..#.#####...#...##.

...#....#......#.#.......#....#.....#.#.........#.#...##...##....##.#.#.....#....###....###...#..#..

#.#........#..#.##...#..#.....#..#...#..##.##....#.#.####.#.......#....##..#.#....#..#..............

............#.##...#....###...#.#...........#.#..#.......#....#........###..#..#...###..###..#.###..

.#..####..#..#......#...##..#....#..#....#....#......#.......##......#...##..#....#.#..#..#..#...##.

#..#...##.##.##.#.#....#......#.....#.........##....#..........####.....#..#.###..#....###..#.#.#.#.

##..##..##.....#.####......##....#...#.....#..##..##......#.#.#.#...........#.....#..#.#.#.........#

.##....##...........##........#.........##......#..#.#...#........#.#.##.##..#........#...#........#

.#..#......#..........###.#..##.#.#......#...###.....##...#..##....####......#......................

...#...#..#.#..#..#...#....###.##.#.........#...#.##....#.#..##.#.....#....#.....##....#.##.##......

.##........#.......##...#....##.#.###.#.#.....#..#.....##..#.#.....###......#..#...#...#........#..#

.........#....................#..##....#.#...#..#..#...#.........#.....#..##.....#.#.##..#...#...#..

#.....##....#.....#..#...#....##..#...##........#.##.#....#.##..#...........##..##.#.#...#..###....#

....#.##..#.#...#..##..............#..#..##..........##....#..##..#....#####..###..##...#.##.##..#..

[出力例]

■参照サイト
AtCoder Beginner Contest 129

2019年7月5日

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

C++の練習を兼ねて, AtCoder Beginner Contest 130 の問題D (D – Enough Array) を解いてみた.

■感想.
1. 苦手な DP の訓練となったと思う.
2. 解答を見る前に, 解けたので, 及第点は取れたと思う.

本家のサイトABC 130解説をご覧下さい.

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

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const LL MAX = 1e5 + 1;
LL dp[MAX], a[MAX], c[MAX];

int main() {
    
    // 1. 入力情報取得.
    LL N, K;
    scanf("%lld %lld", &N, &K);
    for(int i = 1; i <= N; i++) scanf("%lld", a + i), c[i] += c[i - 1] + a[i];
    
    // 2. 連続部分列に含まれる全ての要素の値の和が, K以上のものを数える.
    // dp[i]: 位置 i までで, 条件を満たす部分列の個数.
    LL buf = 0;
    for(LL i = 1; i <= N; i++){
        // 2-1. K以上 となったので, K以上 の 範囲を探索.
        if(c[i] >= K){
            for(LL j = buf; j <= i; j++){
                if(c[i] - c[j] >= K) continue;
                if(c[i] - c[j] < K){
                    // 前回分 dp[i - 1] に j個 を 加算.
                    dp[i] = dp[i - 1] + j;
                    buf = j - 1;
                    break;
                }
            }
        
        }
    }
    
    // 3. 出力 ～ 後処理.
    // for(int i = 0; i <= N; i++) cout << dp[i] << " ";
    printf("%lld\n", dp[N]);
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

const LL MAX = 1e5 + 1;

LL dp[MAX], a[MAX], c[MAX];

int main() {

// 1. 入力情報取得.

LL N, K;

scanf("%lld %lld", &N, &K);

for(int i = 1; i <= N; i++) scanf("%lld", a + i), c[i] += c[i - 1] + a[i];

// 2. 連続部分列に含まれる全ての要素の値の和が, K以上のものを数える.

// dp[i]: 位置 i までで, 条件を満たす部分列の個数.

LL buf = 0;

for(LL i = 1; i <= N; i++){

// 2-1. K以上となったので, K以上の範囲を探索.

if(c[i] >= K){

for(LL j = buf; j <= i; j++){

if(c[i] - c[j] >= K) continue;

if(c[i] - c[j] < K){

// 前回分 dp[i - 1] に j個を加算.

dp[i] = dp[i - 1] + j;

buf = j - 1;

break;

}

// 3. 出力～後処理.

// for(int i = 0; i <= N; i++) cout << dp[i] << " ";

printf("%lld\n", dp[N]);

return 0;

}

[入力例]
4 10
6 1 2 7

[出力例(debug版)]
0 0 0 0 2 2
※AtCoderテストケースより

[入力例]
3 5
3 3 3

[出力例(debug版)]
0 0 1 3 3
※AtCoderテストケースより

[入力例]
10 53462
103 35322 232 342 21099 90000 18843 9010 35221 19352

[出力例(debug版)]
0 0 0 0 0 2 8 14 20 27 36 36
※AtCoderテストケースより

[入力例]
27 12345
1111 2222 3333 4444 5555 6666 7777 8888 9999 111 222 333 444 555 666 777 888 999 11111 22222 33333 44444 55555 66666 77777 88888 99999

[出力例(debug版)]
0 0 0 0 0 3 7 13 20 28 36 44 52 60 68 76 85 94 103 120 140 161 183 206 230 255 281 308 308

[入力例]
20000 1234567890
99999	99998	99997	99996	99995	99994	99993	99992	99991	99990	99989	99988	99987	99986	99985	99984	99983	99982	99981	99980	99979	99978	99977	99976	99975	99974	99973	99972	99971	99970	～(略, 99999 から 80000 までの数字 20000個)～
80019	80018	80017	80016	80015	80014	80013	80012	80011	80010	80009	80008	80007	80006	80005	80004	80003	80002	80001	80000

[出力例]
19820696

[入力例]

4 10

6 1 2 7

[出力例(debug版)]

0 0 0 0 2 2

※AtCoderテストケースより

[入力例]

3 5

3 3 3

[出力例(debug版)]

0 0 1 3 3

※AtCoderテストケースより

[入力例]

10 53462

103 35322 232 342 21099 90000 18843 9010 35221 19352

[出力例(debug版)]

0 0 0 0 0 2 8 14 20 27 36 36

※AtCoderテストケースより

[入力例]

27 12345

1111 2222 3333 4444 5555 6666 7777 8888 9999 111 222 333 444 555 666 777 888 999 11111 22222 33333 44444 55555 66666 77777 88888 99999

[出力例(debug版)]

0 0 0 0 0 3 7 13 20 28 36 44 52 60 68 76 85 94 103 120 140 161 183 206 230 255 281 308 308

[入力例]

20000 1234567890

99999 99998 99997 99996 99995 99994 99993 99992 99991 99990 99989 99988 99987 99986 99985 99984 99983 99982 99981 99980 99979 99978 99977 99976 99975 99974 99973 99972 99971 99970 ～(略, 99999 から 80000 までの数字 20000個)～

80019 80018 80017 80016 80015 80014 80013 80012 80011 80010 80009 80008 80007 80006 80005 80004 80003 80002 80001 80000

[出力例]

19820696

■参照サイト
AtCoder Beginner Contest 130

2019年7月4日

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

C++の練習を兼ねて, AtCoder Beginner Contest 132 の問題F (F – Small Products) を解いてみた.

■感想.
1. 方針も見えず, 解けそうに無かったので, 解答を参考に実装した.
2. 解説上, N の平方数を考えて, DP高速化を図る必要があると指摘があり実装したが, DPの組み立て方で, 非常に苦労した.
3. 実装終わったものの, AC版とならなかった(※必ず, テストケース 03.txt, 12.txt で, WA版となる).
4. 考えても分からなかったので, 正解者のソースを, 色々眺めていたところ, “N の平方数に 1 を加算する必要がある” ことが判明したので, 修正後, 再提出して, AC版となった.
5. AC版となったものの, “N の平方数に 1 を加算する必要がある” ことの理由が分からないため, とりあえず, 解法パターンの一つとして暗記しておくことにした.

本家のサイトABC 132解説をご覧下さい.

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

// 解き直し.
// ABC 132解説.
// https://img.atcoder.jp/abc132/editorial.pdf
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const LL MOD = 1e9 + 7;
const LL MAX_K = 101;
const LL MAX_N = 1e5;
LL dp[MAX_K][MAX_N];

int main() {

    // 1. 入力情報取得.
    LL N, K;
    scanf("%lld %lld", &N, &K);

    // 2. 解説通り.
    // dp[i][x]: 最後の整数が, x であるような i個 の 整数を並べて条件を満たせる場合の数.
    // ex.
    // [入力例]
    // 10 3
    // ※下記, dp[3][XX] については, 計算方法を ()内 に, 記載した.
    // dp[1][1]  = 1, dp[2][1]  = 10, dp[3][1]  = 27 (= dp[2][1] + ... + dp[2][10])
    // dp[1][2]  = 1, dp[2][2]  = 5,  dp[3][2]  = 22 (= dp[2][1] + dp[2][2] + dp[2][3] + dp[2][4] + dp[2][5])
    // dp[1][3]  = 1, dp[2][3]  = 3,  dp[3][3]  = 18 (= dp[2][1] + dp[2][2] + dp[2][3])
    // dp[1][4]  = 1, dp[2][4]  = 2,  dp[3][4]  = 15 (= dp[2][1] + dp[2][2])
    // dp[1][5]  = 1, dp[2][5]  = 2,  dp[3][5]  = 15 (= dp[2][1] + dp[2][2])
    // dp[1][6]  = 1, dp[2][6]  = 1,  dp[3][6]  = 10 (= dp[2][1])
    // dp[1][7]  = 1, dp[2][7]  = 1,  dp[3][7]  = 10 (= dp[2][1])
    // dp[1][8]  = 1, dp[2][8]  = 1,  dp[3][8]  = 10 (= dp[2][1])
    // dp[1][9]  = 1, dp[2][9]  = 1,  dp[3][9]  = 10 (= dp[2][1])
    // dp[1][10] = 1, dp[2][10] = 1,  dp[3][10] = 10 (= dp[2][1])
    // -> dp[3][1] + dp[3][2] + ... + dp[3][9] + dp[3][10] = 147通り と 計算するようである.
    
    // 正解者のソースを確認したところ, "N の 平方数 に 1 を 加算する必要がある" ことが判明.
    // LL nr = sqrt(N + 0.0); // 03.txt, 12.txt で, WA版 となるので, 注意.
    LL nr = sqrt(N + 0.0) + 1;
    LL ir = N / nr;
    for(LL x = 1; x < nr + ir; x++) dp[1][x] = 1;
    
    for(LL k = 2; k <= K; k++){
         
         // 2-1. N ～ r + 1 まで集計.
         // ex.
         // x = 5 に 6 ～ 10, x = 4 に 4 ～ 5 を 集約.
         for(LL x = nr + ir - 1; x >= nr; x--){
             dp[k][x] = dp[k - 1][nr + ir - x] + dp[k][x + 1];
             dp[k][x] %= MOD;
         }
         
         // 2-2. r ～ 1 まで集計.
         // ex.
         // x = 3 ～ 1 までを集計.
         for(LL x = nr - 1; x > 0; x--){
             dp[k][x] = dp[k][x + 1] + dp[k - 1][nr + ir - x] * (N / x - N / (x + 1));
             dp[k][x] %= MOD;
         }
    }
    // for(LL x = 1; x < nr + ir; x++) cout << dp[K][x] << " ";
    // cout << endl;
    
    // 3. 後処理.
    LL ans = 0;
    for(LL x = 1; x < nr; x++)       ans += dp[K][x], ans %= MOD;
    for(LL x = nr; x < nr + ir; x++) ans += dp[K][x] * (N / (nr + ir - x) - N / (nr + ir - x + 1)), ans %= MOD;
    printf("%lld\n", ans);
    return 0;

}

// 解き直し.

// ABC 132解説.

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

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

const LL MOD = 1e9 + 7;

const LL MAX_K = 101;

const LL MAX_N = 1e5;

LL dp[MAX_K][MAX_N];

int main() {

// 1. 入力情報取得.

LL N, K;

scanf("%lld %lld", &N, &K);

// 2. 解説通り.

// dp[i][x]: 最後の整数が, x であるような i個の整数を並べて条件を満たせる場合の数.

// ex.

// [入力例]

// 10 3

// ※下記, dp[3][XX] については, 計算方法を ()内に, 記載した.

// dp[1][1] = 1, dp[2][1] = 10, dp[3][1] = 27 (= dp[2][1] + ... + dp[2][10])

// dp[1][2] = 1, dp[2][2] = 5, dp[3][2] = 22 (= dp[2][1] + dp[2][2] + dp[2][3] + dp[2][4] + dp[2][5])

// dp[1][3] = 1, dp[2][3] = 3, dp[3][3] = 18 (= dp[2][1] + dp[2][2] + dp[2][3])

// dp[1][4] = 1, dp[2][4] = 2, dp[3][4] = 15 (= dp[2][1] + dp[2][2])

// dp[1][5] = 1, dp[2][5] = 2, dp[3][5] = 15 (= dp[2][1] + dp[2][2])

// dp[1][6] = 1, dp[2][6] = 1, dp[3][6] = 10 (= dp[2][1])

// dp[1][7] = 1, dp[2][7] = 1, dp[3][7] = 10 (= dp[2][1])

// dp[1][8] = 1, dp[2][8] = 1, dp[3][8] = 10 (= dp[2][1])

// dp[1][9] = 1, dp[2][9] = 1, dp[3][9] = 10 (= dp[2][1])

// dp[1][10] = 1, dp[2][10] = 1, dp[3][10] = 10 (= dp[2][1])

// -> dp[3][1] + dp[3][2] + ... + dp[3][9] + dp[3][10] = 147通りと計算するようである.

// 正解者のソースを確認したところ, "N の平方数に 1 を加算する必要がある" ことが判明.

// LL nr = sqrt(N + 0.0); // 03.txt, 12.txt で, WA版となるので, 注意.

LL nr = sqrt(N + 0.0) + 1;

LL ir = N / nr;

for(LL x = 1; x < nr + ir; x++) dp[1][x] = 1;

for(LL k = 2; k <= K; k++){

// 2-1. N ～ r + 1 まで集計.

// ex.

// x = 5 に 6 ～ 10, x = 4 に 4 ～ 5 を集約.

for(LL x = nr + ir - 1; x >= nr; x--){

dp[k][x] = dp[k - 1][nr + ir - x] + dp[k][x + 1];

dp[k][x] %= MOD;

}

// 2-2. r ～ 1 まで集計.

// ex.

// x = 3 ～ 1 までを集計.

for(LL x = nr - 1; x > 0; x--){

dp[k][x] = dp[k][x + 1] + dp[k - 1][nr + ir - x] * (N / x - N / (x + 1));

dp[k][x] %= MOD;

}

// for(LL x = 1; x < nr + ir; x++) cout << dp[K][x] << " ";

// cout << endl;

// 3. 後処理.

LL ans = 0;

for(LL x = 1; x < nr; x++) ans += dp[K][x], ans %= MOD;

for(LL x = nr; x < nr + ir; x++) ans += dp[K][x] * (N / (nr + ir - x) - N / (nr + ir - x + 1)), ans %= MOD;

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

return 0;

}

[入力例]
10 3

[出力例(debug版)]
27 22 18 15 10 
147
※AtCoderテストケースより

[入力例]
3 2

[出力例(debug版)]
3 1 
5
※AtCoderテストケースより

[入力例]
2 5

[出力例(debug版)]
8 5 
13

[入力例]
5 7

[出力例(debug版)]
589 352 224 
1613

[入力例]
314159265 35

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

[入力例]
987654321 100

[出力例]
573601723

[入力例]

10 3

[出力例(debug版)]

27 22 18 15 10

147

※AtCoderテストケースより

[入力例]

3 2

[出力例(debug版)]

3 1

※AtCoderテストケースより

[入力例]

2 5

[出力例(debug版)]

8 5

[入力例]

5 7

[出力例(debug版)]

589 352 224

1613

[入力例]

314159265 35

[出力例]

457397712

※AtCoderテストケースより

[入力例]

987654321 100

[出力例]

573601723

■参照サイト
AtCoder Beginner Contest 132

2019年7月2日2019年7月2日

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

C++の練習を兼ねて, AtCoder Beginner Contest 132 の問題E (E – Hopscotch Addict) を解いてみた.

■感想.
1. 方針も見えず, 解けそうに無かったので, 解答を参考に実装した.
2. 解説上, グラフを “3倍化” するというのが, 何のことか理解出来なかったが, 多分こうだろうという実装で, AC版まで行ったので, 大きなズレは無かったと思う.
3. TLE版と AC版を掲載した.
※1. TLE版を AC版に修正する訓練を積めたので, 貴重な経験となったと思う.
※2. AC版は, 50 ～ 51ms で通過したので, 十分高速化出来たと思う.

本家のサイトABC 132解説をご覧下さい.

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

// 解き直し.
// ABC 132解説.
// https://img.atcoder.jp/abc132/editorial.pdf
#include <bits/stdc++.h>
using namespace std;
const int MAX_V = 1e5;
int memo[321123];

struct Edge{ int f, t, w; };
struct Graph{
    int V, E;
    struct Edge* edge;
};
struct Graph* build(int V, int E){
    struct Graph* graph = new Graph;
    graph->V = V;
    graph->E = E;
    graph->edge = new Edge[E];
    return graph;
}

// 幅優先探索.
// https://ja.wikipedia.org/wiki/幅優先探索
// グラフを幅優先探索する.
// ※bfsの動作確認用.
// @param graph: グラフ.
// @param s: 探索開始の頂点番号.
// @param g: 探索終了の頂点番号.
// @param M: 辺数.
// @return: 特に無し.
void bfs(struct Graph* graph, int s, int g, int M){

    // 1. 空のキュー.
    queue<int> q;

    // 2. 訪問済みフラグ設定.
    // ※スタート地点は, 距離ゼロを指定.
    memo[s] = 0;

    // 3. 探索地点 s をキュー q に追加.
    q.push(s);
    
    // 4. キュー q が 空になるまで, 探索.
    while(!q.empty()) {
        
        // 5. 頂点 u を キュー q から取り出す.
        int u = q.front();
        q.pop();
        
        // 6. 頂点 u が ゴールだったら終了.
        // -> TLE対策.
        if(u == g) break;
        
        // 7. 取り出した要素を処理.
        for(int i = 0; i < M; i++){
            int a = graph->edge[i].f;
            int b = graph->edge[i].t;
            int w = graph->edge[i].w;
            // 7-1. 頂点u の 隣接する頂点b が, 未訪問だったら, キュー q に追加.
            if(u == a && memo[b] == 0 && b != s){
                q.push(b);      // 頂点b を キュー q に追加.
                // 頂点b に 距離memo[a] プラス 1 を 加算.
                memo[b] += memo[a];
                memo[b]++;
            }
            // ※※※ 本問は, 有向グラフを考えているので, コメントアウト ※※※.
            // 7-2. 頂点u の 隣接する頂点a が, 未訪問だったら, キュー q に追加.
            // if(u == b && memo[a] == 0 && a != s){
            //     q.push(a);      // 頂点a を キュー q に追加.
            //     // 頂点a に 距離memo[b] プラス 1 を 加算.
            //     memo[a] += memo[b];
            //     memo[a]++;
            // }
            
        }
    }
}

int main() {

    // 1. 入力情報取得.
    int N, M;
    scanf("%d %d", &N, &M);

    // 2. グラフ作成.
    // 解説通り, グラフを3倍化？してみる.
    // 3辺 u0 -> v1, u1 -> v2, u2 -> v0 を 張る.
    // 具体的には, 
    // u0 = u + i * 3, u1 = u + 1, u2 = u + MAX_V * 2
    // v0 = v, v1 = v + MAX_V, v2 = v + MAX_V * 2
    struct Graph* graph = build(N * 3, M * 3);
    for(int i = 0; i < M * 3; i += 3){
        int u, v;
        scanf("%d %d", &u, &v);
        u--, v--;
        // u0 -> v1
        graph->edge[i + 0].f = u;
        graph->edge[i + 0].t = v + MAX_V * 1;
        graph->edge[i + 0].w = 1;
        // u1 -> v2
        graph->edge[i + 1].f = u + MAX_V * 1;
        graph->edge[i + 1].t = v + MAX_V * 2;
        graph->edge[i + 1].w = 1;
        // u2 -> v0
        graph->edge[i + 2].f = u + MAX_V * 2;
        graph->edge[i + 2].t = v;
        graph->edge[i + 2].w = 1;
    }
    // for(int i = 0; i < M * 3; i++){
    //     int f = graph->edge[i].f;
    //     int t = graph->edge[i].t;
    //     int w = graph->edge[i].w;
    //     cout << "i=" << i << " f=" << f << " t=" << t << " w=" << w << endl;
    // }
    
    // 3. スタート地点, ゴール地点.
    int S, T;
    scanf("%d %d", &S, &T);
    S--, T--;
    
    // 4. S0 -> T0 の 最短距離 を 計算.
    bfs(graph, S, T, M * 3);
    // for(int i = 0; i < N * 3; i++) cout << memo[i] << " ";
    // cout << endl;
    
    // 5. 後処理.
    int ans = memo[T] / 3;
    if(ans == 0) printf("%d\n", -1);
    else         printf("%d\n", ans);
    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

// 解き直し.

// ABC 132解説.

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

#include <bits/stdc++.h>

using namespace std;

const int MAX_V = 1e5;

int memo[321123];

struct Edge{ int f, t, w; };

struct Graph{

int V, E;

struct Edge* edge;

};

struct Graph* build(int V, int E){

struct Graph* graph = new Graph;

graph->V = V;

graph->E = E;

graph->edge = new Edge[E];

return graph;

}

// 幅優先探索.

// https://ja.wikipedia.org/wiki/幅優先探索

// グラフを幅優先探索する.

// ※bfsの動作確認用.

// @param graph: グラフ.

// @param s: 探索開始の頂点番号.

// @param g: 探索終了の頂点番号.

// @param M: 辺数.

// @return: 特に無し.

void bfs(struct Graph* graph, int s, int g, int M){

// 1. 空のキュー.

queue<int> q;

// 2. 訪問済みフラグ設定.

// ※スタート地点は, 距離ゼロを指定.

memo[s] = 0;

// 3. 探索地点 s をキュー q に追加.

q.push(s);

// 4. キュー q が空になるまで, 探索.

while(!q.empty()) {

// 5. 頂点 u をキュー q から取り出す.

int u = q.front();

q.pop();

// 6. 頂点 u がゴールだったら終了.

// -> TLE対策.

if(u == g) break;

// 7. 取り出した要素を処理.

for(int i = 0; i < M; i++){

int a = graph->edge[i].f;

int b = graph->edge[i].t;

int w = graph->edge[i].w;

// 7-1. 頂点u の隣接する頂点b が, 未訪問だったら, キュー q に追加.

if(u == a && memo[b] == 0 && b != s){

q.push(b); // 頂点b をキュー q に追加.

// 頂点b に距離memo[a] プラス 1 を加算.

memo[b] += memo[a];

memo[b]++;

}

// ※※※ 本問は, 有向グラフを考えているので, コメントアウト ※※※.

// 7-2. 頂点u の隣接する頂点a が, 未訪問だったら, キュー q に追加.

// if(u == b && memo[a] == 0 && a != s){

// q.push(a); // 頂点a をキュー q に追加.

// // 頂点a に距離memo[b] プラス 1 を加算.

// memo[a] += memo[b];

// memo[a]++;

// }

}

int main() {

// 1. 入力情報取得.

int N, M;

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

// 2. グラフ作成.

// 解説通り, グラフを3倍化？してみる.

// 3辺 u0 -> v1, u1 -> v2, u2 -> v0 を張る.

// 具体的には,

// u0 = u + i * 3, u1 = u + 1, u2 = u + MAX_V * 2

// v0 = v, v1 = v + MAX_V, v2 = v + MAX_V * 2

struct Graph* graph = build(N * 3, M * 3);

for(int i = 0; i < M * 3; i += 3){

int u, v;

scanf("%d %d", &u, &v);

u--, v--;

// u0 -> v1

graph->edge[i + 0].f = u;

graph->edge[i + 0].t = v + MAX_V * 1;

graph->edge[i + 0].w = 1;

// u1 -> v2

graph->edge[i + 1].f = u + MAX_V * 1;

graph->edge[i + 1].t = v + MAX_V * 2;

graph->edge[i + 1].w = 1;

// u2 -> v0

graph->edge[i + 2].f = u + MAX_V * 2;

graph->edge[i + 2].t = v;

graph->edge[i + 2].w = 1;

}

// for(int i = 0; i < M * 3; i++){

// int f = graph->edge[i].f;

// int t = graph->edge[i].t;

// int w = graph->edge[i].w;

// cout << "i=" << i << " f=" << f << " t=" << t << " w=" << w << endl;

// }

// 3. スタート地点, ゴール地点.

int S, T;

scanf("%d %d", &S, &T);

S--, T--;

// 4. S0 -> T0 の最短距離を計算.

bfs(graph, S, T, M * 3);

// for(int i = 0; i < N * 3; i++) cout << memo[i] << " ";

// cout << endl;

// 5. 後処理.

int ans = memo[T] / 3;

if(ans == 0) printf("%d\n", -1);

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

return 0;

}

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

[出力例(debug版)]
i=0 f=0 t=100001 w=1
i=1 f=100000 t=200001 w=1
i=2 f=200000 t=1 w=1
i=3 f=1 t=100002 w=1
i=4 f=100001 t=200002 w=1
i=5 f=200001 t=2 w=1
i=6 f=2 t=100003 w=1
i=7 f=100002 t=200003 w=1
i=8 f=200002 t=3 w=1
i=9 f=3 t=100000 w=1
i=10 f=100003 t=200000 w=1
i=11 f=200003 t=0 w=1
0 9 6 3 0 0 0 0 0 0 0 0 
2

※経路確認
始点: 0 終点: 2
けんけんぱの経路: 0 -> 100001 -> 200002 -> 3 -> 100000 -> 200001 -> 2
=> OK
※AtCoderテストケースより

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

[出力例(debug版)]
i=0 f=0 t=100001 w=1
i=1 f=100000 t=200001 w=1
i=2 f=200000 t=1 w=1
i=3 f=1 t=100002 w=1
i=4 f=100001 t=200002 w=1
i=5 f=200001 t=2 w=1
i=6 f=2 t=100003 w=1
i=7 f=100002 t=200003 w=1
i=8 f=200002 t=3 w=1
i=9 f=3 t=100004 w=1
i=10 f=100003 t=200004 w=1
i=11 f=200003 t=4 w=1
i=12 f=4 t=100000 w=1
i=13 f=100004 t=200000 w=1
i=14 f=200004 t=0 w=1
i=15 f=0 t=100003 w=1
i=16 f=100000 t=200003 w=1
i=17 f=200000 t=3 w=1
i=18 f=0 t=100004 w=1
i=19 f=100000 t=200004 w=1
i=20 f=200000 t=4 w=1
i=21 f=3 t=100005 w=1
i=22 f=100003 t=200005 w=1
i=23 f=200003 t=5 w=1
0 3 6 3 3 6 0 0 0 0 0 0 0 0 0 0 0 0 
2

※経路確認
始点: 0 終点: 5
けんけんぱの経路: 0 -> 100004 -> 200000 -> 4 -> 100000 -> 200003 -> 5
=> OK
※AtCoderテストケースより

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

[出力例(debug版)]
i=0 f=0 t=100001 w=1
i=1 f=100000 t=200001 w=1
i=2 f=200000 t=1 w=1
i=3 f=1 t=100002 w=1
i=4 f=100001 t=200002 w=1
i=5 f=200001 t=2 w=1
i=6 f=2 t=100003 w=1
i=7 f=100002 t=200003 w=1
i=8 f=200002 t=3 w=1
i=9 f=3 t=100004 w=1
i=10 f=100003 t=200004 w=1
i=11 f=200003 t=4 w=1
i=12 f=4 t=100000 w=1
i=13 f=100004 t=200000 w=1
i=14 f=200004 t=0 w=1
i=15 f=0 t=100003 w=1
i=16 f=100000 t=200003 w=1
i=17 f=200000 t=3 w=1
i=18 f=4 t=100001 w=1
i=19 f=100004 t=200001 w=1
i=20 f=200004 t=1 w=1
i=21 f=0 t=100004 w=1
i=22 f=100000 t=200004 w=1
i=23 f=200000 t=4 w=1
i=24 f=3 t=100005 w=1
i=25 f=100003 t=200005 w=1
i=26 f=200003 t=5 w=1
6 0 6 6 3 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
1

※経路確認
始点: 1 終点: 4
けんけんぱの経路: 1 -> 100002 -> 200003 -> 4
=> OK

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

[出力例(debug版)]
i=0 f=0 t=100001 w=1
i=1 f=100000 t=200001 w=1
i=2 f=200000 t=1 w=1
i=3 f=0 t=100002 w=1
i=4 f=100000 t=200002 w=1
i=5 f=200000 t=2 w=1
i=6 f=3 t=100000 w=1
i=7 f=100003 t=200000 w=1
i=8 f=200003 t=0 w=1
i=9 f=1 t=100002 w=1
i=10 f=100001 t=200002 w=1
i=11 f=200001 t=2 w=1
i=12 f=2 t=100003 w=1
i=13 f=100002 t=200003 w=1
i=14 f=200002 t=3 w=1
i=15 f=5 t=100006 w=1
i=16 f=100005 t=200006 w=1
i=17 f=200005 t=6 w=1
i=18 f=6 t=100004 w=1
i=19 f=100006 t=200004 w=1
i=20 f=200006 t=4 w=1
i=21 f=4 t=100005 w=1
i=22 f=100004 t=200005 w=1
i=23 f=200004 t=5 w=1
i=24 f=3 t=100004 w=1
i=25 f=100003 t=200004 w=1
i=26 f=200003 t=4 w=1
6 3 0 9 6 3 12 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
2

※経路確認
始点: 2 終点: 4
けんけんぱの経路: 2 -> 100003 -> 200000 -> 1 -> 100002 -> 200003 -> 4
=> OK

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

[入力例]

4 4

1 2

2 3

3 4

4 1

1 3

[出力例(debug版)]

i=0 f=0 t=100001 w=1

i=1 f=100000 t=200001 w=1

i=2 f=200000 t=1 w=1

i=3 f=1 t=100002 w=1

i=4 f=100001 t=200002 w=1

i=5 f=200001 t=2 w=1

i=6 f=2 t=100003 w=1

i=7 f=100002 t=200003 w=1

i=8 f=200002 t=3 w=1

i=9 f=3 t=100000 w=1

i=10 f=100003 t=200000 w=1

i=11 f=200003 t=0 w=1

0 9 6 3 0 0 0 0 0 0 0 0

※経路確認

始点: 0 終点: 2

けんけんぱの経路: 0 -> 100001 -> 200002 -> 3 -> 100000 -> 200001 -> 2

=> OK

※AtCoderテストケースより

[入力例]

6 8

1 2

2 3

3 4

4 5

5 1

1 4

1 5

4 6

1 6

[出力例(debug版)]

i=0 f=0 t=100001 w=1

i=1 f=100000 t=200001 w=1

i=2 f=200000 t=1 w=1

i=3 f=1 t=100002 w=1

i=4 f=100001 t=200002 w=1

i=5 f=200001 t=2 w=1

i=6 f=2 t=100003 w=1

i=7 f=100002 t=200003 w=1

i=8 f=200002 t=3 w=1

i=9 f=3 t=100004 w=1

i=10 f=100003 t=200004 w=1

i=11 f=200003 t=4 w=1

i=12 f=4 t=100000 w=1

i=13 f=100004 t=200000 w=1

i=14 f=200004 t=0 w=1

i=15 f=0 t=100003 w=1

i=16 f=100000 t=200003 w=1

i=17 f=200000 t=3 w=1

i=18 f=0 t=100004 w=1

i=19 f=100000 t=200004 w=1

i=20 f=200000 t=4 w=1

i=21 f=3 t=100005 w=1

i=22 f=100003 t=200005 w=1

i=23 f=200003 t=5 w=1

0 3 6 3 3 6 0 0 0 0 0 0 0 0 0 0 0 0

※経路確認

始点: 0 終点: 5

けんけんぱの経路: 0 -> 100004 -> 200000 -> 4 -> 100000 -> 200003 -> 5

=> OK

※AtCoderテストケースより

[入力例]

7 9

1 2

2 3

3 4

4 5

5 1

1 4

5 2

1 5

4 6

2 5

[出力例(debug版)]

i=0 f=0 t=100001 w=1

i=1 f=100000 t=200001 w=1

i=2 f=200000 t=1 w=1

i=3 f=1 t=100002 w=1

i=4 f=100001 t=200002 w=1

i=5 f=200001 t=2 w=1

i=6 f=2 t=100003 w=1

i=7 f=100002 t=200003 w=1

i=8 f=200002 t=3 w=1

i=9 f=3 t=100004 w=1

i=10 f=100003 t=200004 w=1

i=11 f=200003 t=4 w=1

i=12 f=4 t=100000 w=1

i=13 f=100004 t=200000 w=1

i=14 f=200004 t=0 w=1

i=15 f=0 t=100003 w=1

i=16 f=100000 t=200003 w=1

i=17 f=200000 t=3 w=1

i=18 f=4 t=100001 w=1

i=19 f=100004 t=200001 w=1

i=20 f=200004 t=1 w=1

i=21 f=0 t=100004 w=1

i=22 f=100000 t=200004 w=1

i=23 f=200000 t=4 w=1

i=24 f=3 t=100005 w=1

i=25 f=100003 t=200005 w=1

i=26 f=200003 t=5 w=1

6 0 6 6 3 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

※経路確認

始点: 1 終点: 4

けんけんぱの経路: 1 -> 100002 -> 200003 -> 4

=> OK

[入力例]

7 9

1 2

1 3

4 1

2 3

3 4

6 7

7 5

5 6

4 5

3 5

[出力例(debug版)]

i=0 f=0 t=100001 w=1

i=1 f=100000 t=200001 w=1

i=2 f=200000 t=1 w=1

i=3 f=0 t=100002 w=1

i=4 f=100000 t=200002 w=1

i=5 f=200000 t=2 w=1

i=6 f=3 t=100000 w=1

i=7 f=100003 t=200000 w=1

i=8 f=200003 t=0 w=1

i=9 f=1 t=100002 w=1

i=10 f=100001 t=200002 w=1

i=11 f=200001 t=2 w=1

i=12 f=2 t=100003 w=1

i=13 f=100002 t=200003 w=1

i=14 f=200002 t=3 w=1

i=15 f=5 t=100006 w=1

i=16 f=100005 t=200006 w=1

i=17 f=200005 t=6 w=1

i=18 f=6 t=100004 w=1

i=19 f=100006 t=200004 w=1

i=20 f=200006 t=4 w=1

i=21 f=4 t=100005 w=1

i=22 f=100004 t=200005 w=1

i=23 f=200004 t=5 w=1

i=24 f=3 t=100004 w=1

i=25 f=100003 t=200004 w=1

i=26 f=200003 t=4 w=1

6 3 0 9 6 3 12 0 0 0 0 0 0 0 0 0 0 0 0 0 0

※経路確認

始点: 2 終点: 4

けんけんぱの経路: 2 -> 100003 -> 200000 -> 1 -> 100002 -> 200003 -> 4

=> OK

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

// 解き直し.
// ABC 132解説.
// https://img.atcoder.jp/abc132/editorial.pdf
#include <bits/stdc++.h>
using namespace std;
const int MAX_V = 1e5;
int memo[321123];
vector<int> graph[321123];

// 幅優先探索.
// https://ja.wikipedia.org/wiki/幅優先探索
// グラフを幅優先探索する.
// ※bfsの動作確認用.
// @param s: 探索開始の頂点番号.
// @param g: 探索終了の頂点番号.
// @return: 特に無し.
void bfs(int s, int g){

    // 1. 空のキュー.
    queue<int> q;

    // 2. 訪問済みフラグ設定.
    // ※スタート地点は, 距離ゼロを指定.
    memo[s] = 0;

    // 3. 探索地点 s をキュー q に追加.
    q.push(s);
    
    // 4. キュー q が 空になるまで, 探索.
    while(!q.empty()) {
        
        // 5. 頂点 u を キュー q から取り出す.
        int u = q.front();
        q.pop();
        
        // 6. 頂点 u が ゴールだったら終了.
        if(u == g) break;
        
        // 7. 取り出した要素を処理.
        for(auto &e : graph[u]){
            // 7-1. 頂点u の 隣接する頂点e が, 未訪問だったら, キュー q に追加.
            if(memo[e] == 0 && e != s){
                // 頂点e を キュー q に追加.
                q.push(e);
                // 頂点e に 距離memo[u] プラス 1 を 加算.
                memo[e] += memo[u];
                memo[e]++;
            }
        }
    }
}

int main() {

    // 1. 入力情報取得.
    int N, M;
    scanf("%d %d", &N, &M);

    // 2. グラフ作成.
    // 解説通り, グラフを3倍化？してみる.
    // 3辺 u0 -> v1, u1 -> v2, u2 -> v0 を 張る.
    // 具体的には, 
    // u0 = u, u1 = u + MAX_V, u2 = u + MAX_V * 2
    // v0 = v, v1 = v + MAX_V, v2 = v + MAX_V * 2
    for(int i = 0; i < M * 3; i += 3){
        int u, v;
        scanf("%d %d", &u, &v);
        u--, v--;
        // u0 -> v1
        graph[u].push_back(v + MAX_V);
        // u1 -> v2
        graph[u + MAX_V].push_back(v + MAX_V * 2);
        // u2 -> v0
        graph[u + MAX_V * 2].push_back(v);
    }
    
    // 3. スタート地点, ゴール地点.
    int S, T;
    scanf("%d %d", &S, &T);
    S--, T--;
    
    // 4. S0 -> T0 の 最短距離 を 計算.
    bfs(S, T);
    // for(int i = 0; i < N * 3; i++) cout << memo[i] << " ";
    // cout << endl;
    
    // 5. 後処理.
    int ans = memo[T] / 3;
    if(ans == 0) printf("%d\n", -1);
    else         printf("%d\n", ans);
    return 0;

}

// 解き直し.

// ABC 132解説.

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

#include <bits/stdc++.h>

using namespace std;

const int MAX_V = 1e5;

int memo[321123];

vector<int> graph[321123];

// 幅優先探索.

// https://ja.wikipedia.org/wiki/幅優先探索

// グラフを幅優先探索する.

// ※bfsの動作確認用.

// @param s: 探索開始の頂点番号.

// @param g: 探索終了の頂点番号.

// @return: 特に無し.

void bfs(int s, int g){

// 1. 空のキュー.

queue<int> q;

// 2. 訪問済みフラグ設定.

// ※スタート地点は, 距離ゼロを指定.

memo[s] = 0;

// 3. 探索地点 s をキュー q に追加.

q.push(s);

// 4. キュー q が空になるまで, 探索.

while(!q.empty()) {

// 5. 頂点 u をキュー q から取り出す.

int u = q.front();

q.pop();

// 6. 頂点 u がゴールだったら終了.

if(u == g) break;

// 7. 取り出した要素を処理.

for(auto &e : graph[u]){

// 7-1. 頂点u の隣接する頂点e が, 未訪問だったら, キュー q に追加.

if(memo[e] == 0 && e != s){

// 頂点e をキュー q に追加.

q.push(e);

// 頂点e に距離memo[u] プラス 1 を加算.

memo[e] += memo[u];

memo[e]++;

}

int main() {

// 1. 入力情報取得.

int N, M;

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

// 2. グラフ作成.

// 解説通り, グラフを3倍化？してみる.

// 3辺 u0 -> v1, u1 -> v2, u2 -> v0 を張る.

// 具体的には,

// u0 = u, u1 = u + MAX_V, u2 = u + MAX_V * 2

// v0 = v, v1 = v + MAX_V, v2 = v + MAX_V * 2

for(int i = 0; i < M * 3; i += 3){

int u, v;

scanf("%d %d", &u, &v);

u--, v--;

// u0 -> v1

graph[u].push_back(v + MAX_V);

// u1 -> v2

graph[u + MAX_V].push_back(v + MAX_V * 2);

// u2 -> v0

graph[u + MAX_V * 2].push_back(v);

}

// 3. スタート地点, ゴール地点.

int S, T;

scanf("%d %d", &S, &T);

S--, T--;

// 4. S0 -> T0 の最短距離を計算.

bfs(S, T);

// for(int i = 0; i < N * 3; i++) cout << memo[i] << " ";

// cout << endl;

// 5. 後処理.

int ans = memo[T] / 3;

if(ans == 0) printf("%d\n", -1);

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

return 0;

}

■参照サイト
AtCoder Beginner Contest 132

C++の練習を兼ねて, AtCoder Beginner Contest 131 の 問題D (D – Megalomania) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 129 の 問題D (D – Lamp) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 130 の 問題D (D – Enough Array) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 132 の 問題F (F – Small Products) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 132 の 問題E (E – Hopscotch Addict) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 131 の問題D (D – Megalomania) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 129 の問題D (D – Lamp) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 130 の問題D (D – Enough Array) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 132 の問題F (F – Small Products) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 132 の問題E (E – Hopscotch Addict) を解いてみた.