個人用メモ帳

2022年7月23日2022年7月23日

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

2022年7月19日2022年7月19日

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

C++の練習を兼ねて, AtCoder Regular Contest 060 の問題F (最良表現) を解いてみた.

■感想.
1. 問題Fは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, Z-Algorithm を, 復習できたので, 非常に良かったと思う.
3. 解説のロジックで, 答えを見つけることが出来ることに, 非常に不思議な印象を受けた.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/data/arc/060/editorial.pdf
// 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--)
#define all(x) x.begin(), x.end()

int main(){
    
    // 1. 入力情報.
    char c[505050];
    scanf("%s", c);
    string w(c), rw(c);
    int ws = w.size();
    
    // 2. (b) per(w) = 1.
    bool ok = true;
    rep(i, ws) if(w[0] != w[i]) ok = false;
    if(ok){
        printf("%d\n%d\n", ws, 1);
        return 0;
    }
    
    // 3. 逆文字列.
    reverse(all(rw));
    
    // 4. Z-Algorithm.
    // https://atcoder.jp/contests/abc257/editorial/4185
    // -> 解説プログラム一部変更.
    // ex.
    // S = abracadabra の 場合, 
    // f[i] = 11 0 0 1 0 1 0 4 0 0 1 
    // 
    // S = abcabc の 場合, 
    // f[i] = 6 0 0 3 0 0 
    auto z = [](string s, int ss, int* f){
        int l = 0, r = 1;
        f[0] = ss;
        repx(i, 1, ss){
            if(i > 1 && f[i - l] < r - i){
                f[i] = f[i - l];
                continue;
            }
            r = max(i, r);
            while(r < ss){
                if(s[r] == s[r - i]) ++r;
                else                 break;
            }
            f[i] = r - i;
            l = i;
        }
    };
    int zf[505050], zb[505050];
    rep(i, 505050) zf[i] = zb[i] = 0;
    z(w, ws, zf);
    z(rw, ws, zb);
    
    // 5. 配列 G.
    bool gf[505050], gb[505050];
    rep(i, 505050) gf[i] = gb[i] = true;
    repx(p, 1, ws){
        if(!gf[p]) continue;
        for(int k = 2; (k - 1) * p <= zf[p]; ++k) gf[k * p] = false;
    }
    repx(p, 1, ws){
        if(!gb[p]) continue;
        for(int k = 2; (k - 1) * p <= zb[p]; ++k) gb[k * p] = false;
    }
    
    // 6. (a) w が 良い文字列.
    if(gf[ws]){
        puts("1\n1");
        return 0;
    }
    
    // 7. (c) それ以外.
    int ans = 0;
    repx(i, 1, ws) if(gf[i] && gb[ws - i]) ++ans;
    
    // 8. 出力.
    printf("%d\n%d\n", 2, ans);
    return 0;
    
}

// 解き直し.

// https://img.atcoder.jp/data/arc/060/editorial.pdf

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

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

int main(){

// 1. 入力情報.

char c[505050];

scanf("%s", c);

string w(c), rw(c);

int ws = w.size();

// 2. (b) per(w) = 1.

bool ok = true;

rep(i, ws) if(w[0] != w[i]) ok = false;

if(ok){

printf("%d\n%d\n", ws, 1);

return 0;

}

// 3. 逆文字列.

reverse(all(rw));

// 4. Z-Algorithm.

// https://atcoder.jp/contests/abc257/editorial/4185

// -> 解説プログラム一部変更.

// ex.

// S = abracadabra の場合,

// f[i] = 11 0 0 1 0 1 0 4 0 0 1

// S = abcabc の場合,

// f[i] = 6 0 0 3 0 0

auto z = [](string s, int ss, int* f){

int l = 0, r = 1;

f[0] = ss;

repx(i, 1, ss){

if(i > 1 && f[i - l] < r - i){

f[i] = f[i - l];

continue;

}

r = max(i, r);

while(r < ss){

if(s[r] == s[r - i]) ++r;

else break;

}

f[i] = r - i;

l = i;

}

};

int zf[505050], zb[505050];

rep(i, 505050) zf[i] = zb[i] = 0;

z(w, ws, zf);

z(rw, ws, zb);

// 5. 配列 G.

bool gf[505050], gb[505050];

rep(i, 505050) gf[i] = gb[i] = true;

repx(p, 1, ws){

if(!gf[p]) continue;

for(int k = 2; (k - 1) * p <= zf[p]; ++k) gf[k * p] = false;

}

repx(p, 1, ws){

if(!gb[p]) continue;

for(int k = 2; (k - 1) * p <= zb[p]; ++k) gb[k * p] = false;

}

// 6. (a) w が良い文字列.

if(gf[ws]){

puts("1\n1");

return 0;

}

// 7. (c) それ以外.

int ans = 0;

repx(i, 1, ws) if(gf[i] && gb[ws - i]) ++ans;

// 8. 出力.

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

return 0;

}

[入力例]
aab

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

[入力例]
bcbc

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

[入力例]
ddd

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

[入力例]
abbaabba

[出力例]
2
7

[入力例]
abracadabra

[出力例]
1
1

[入力例]
appleelppaappleelppaappleelppaappleelppaappleelppaappleelppaappleelppaappleelppaappleelppaappleelppa

[出力例]
2
90

[入力例]
palindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilap

[出力例]
2
950

[入力例]
abcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacra

[出力例]
2
1960

[入力例]

aab

[出力例]

※AtCoderのテストケースより

[入力例]

bcbc

[出力例]

※AtCoderのテストケースより

[入力例]

ddd

[出力例]

※AtCoderのテストケースより

[入力例]

abbaabba

[出力例]

[入力例]

abracadabra

[出力例]

[入力例]

appleelppaappleelppaappleelppaappleelppaappleelppaappleelppaappleelppaappleelppaappleelppaappleelppa

[出力例]

[入力例]

palindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilappalindromeemordnilap

[出力例]

950

[入力例]

abcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacraabcarcagcahcochacgacracbaarcabcahcagcocgachacbacra

[出力例]

1960

■参照サイト
AtCoder Regular Contest 060

2022年7月16日2022年7月19日

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

C++の練習を兼ねて, AtCoder Regular Contest 055 の問題C (ABCAC) を解いてみた.

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

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

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

// 解き直し.
// https://img.atcoder.jp/data/arc/055/editorial.pdf
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#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()

int main(){
    
    // 1. 入力情報.
    char c[202020];
    scanf("%s", c);
    string S(c), R(c);
    int ss = S.size();
    
    // 2. 反転.
    reverse(all(R));
    
    // 3. Z-Algorithm.
    // https://atcoder.jp/contests/abc257/editorial/4185
    // -> 解説プログラム一部変更.
    // ex.
    // S = abracadabra の 場合, 
    // f[i] = 11 0 0 1 0 1 0 4 0 0 1 
    // 
    // S = abcabc の 場合, 
    // f[i] = 6 0 0 3 0 0 
    auto z = [](string s, int ss, int* f){
        int l = 0, r = 1;
        f[0] = ss;
        repx(i, 1, ss){
            if(i > 1 && f[i - l] < r - i){
                f[i] = f[i - l];
                continue;
            }
            r = max(i, r);
            while(r < ss){
                if(s[r] == s[r - i]) ++r;
                else                 break;
            }
            f[i] = r - i;
            l = i;
        }
    };
    int p[202020], s[202020];
    rep(i, 202020) p[i] = s[i] = 0;
    z(S, ss, p);
    z(R, ss, s);
    
    // 4. 全探索(ABC/AC).
    // ex.
    // x = aaaaababaab, y = aaaab
    // y の 分割 => x の 分割 を, それぞれ確認.
    // a/aaab => a/aaaaba/baab で, NG.
    // aa/aab => aa/aaabab/aab で, OK.
    // aaa/ab => aaa/aababa/ab で, OK.
    // aaaa/b => aaaa/ababaa/b で, OK.
    // -> OK は, 3個取れたので, 3通り.
    // -> この例では, prefix 4文字, suffix 3文字 まで 一致するので,
    //    4 + 3 - 5 (文字列 y のサイズ) + 1 = 3通り と 計算される.
    LL ans = 0;
    repx(i, ss / 2, ss - 2){
        // 文字列 を 区間[0, i], [i + 1, ss - 1] に 分割し, 正当なものがいくつあるか？
        int x = i + 1;
        int y = ss - i - 1;
        int a = p[x];
        int c = s[y];
        
        // 分割なし.
        if(a + c < y) continue;
        
        // 非空チェック.
        if(!a || !c) continue;
        
        // 分割あり.
        // ① 文字列 x の 分割(文字列 A (a文字), 文字列 B (1文字以上), 文字列 C (c文字)) は, 文字列 x の サイズ以下.
        // ② 文字列 y の 分割(文字列 A (a文字), 文字列 C (c文字)) は, 文字列 y の サイズ未満.
        // LL cur = (LL)min({x, a + c - y + 1, y - 1});
        
        // 1_009.txt などで, WA版となったため, ロジック修正.
        // -> (a, c) の 組み合わせは, (1, y - 1), (2, y - 2), ..., (y - 1, 1) の 高々 (y - 1)個.
        //    x > y の 範囲で考えているので, x については, 特に考慮する必要は無さそうに見える.
        // ③ (m, y - m) が, m <= a かつ y - m <= c となる 最大の m は？
        // ④ (y - n, n) が, y - n <= a かつ n <= c となる 最大の n は？
        LL m = (LL)max(min(a, y - 1), y - c);
        LL n = (LL)max(min(c, y - 1), y - a);
        LL cur = max(0LL, min(m + n - y + 1, (LL)(y - 1)));
        
        // 加算.
        ans += cur;
    }
    
    // 5. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

100

101

102

// 解き直し.

// https://img.atcoder.jp/data/arc/055/editorial.pdf

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

#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()

int main(){

// 1. 入力情報.

char c[202020];

scanf("%s", c);

string S(c), R(c);

int ss = S.size();

// 2. 反転.

reverse(all(R));

// 3. Z-Algorithm.

// https://atcoder.jp/contests/abc257/editorial/4185

// -> 解説プログラム一部変更.

// ex.

// S = abracadabra の場合,

// f[i] = 11 0 0 1 0 1 0 4 0 0 1

// S = abcabc の場合,

// f[i] = 6 0 0 3 0 0

auto z = [](string s, int ss, int* f){

int l = 0, r = 1;

f[0] = ss;

repx(i, 1, ss){

if(i > 1 && f[i - l] < r - i){

f[i] = f[i - l];

continue;

}

r = max(i, r);

while(r < ss){

if(s[r] == s[r - i]) ++r;

else break;

}

f[i] = r - i;

l = i;

}

};

int p[202020], s[202020];

rep(i, 202020) p[i] = s[i] = 0;

z(S, ss, p);

z(R, ss, s);

// 4. 全探索(ABC/AC).

// ex.

// x = aaaaababaab, y = aaaab

// y の分割 => x の分割を, それぞれ確認.

// a/aaab => a/aaaaba/baab で, NG.

// aa/aab => aa/aaabab/aab で, OK.

// aaa/ab => aaa/aababa/ab で, OK.

// aaaa/b => aaaa/ababaa/b で, OK.

// -> OK は, 3個取れたので, 3通り.

// -> この例では, prefix 4文字, suffix 3文字まで一致するので,

// 4 + 3 - 5 (文字列 y のサイズ) + 1 = 3通りと計算される.

LL ans = 0;

repx(i, ss / 2, ss - 2){

// 文字列を区間[0, i], [i + 1, ss - 1] に分割し, 正当なものがいくつあるか？

int x = i + 1;

int y = ss - i - 1;

int a = p[x];

int c = s[y];

// 分割なし.

if(a + c < y) continue;

// 非空チェック.

if(!a || !c) continue;

// 分割あり.

// ① 文字列 x の分割(文字列 A (a文字), 文字列 B (1文字以上), 文字列 C (c文字)) は, 文字列 x のサイズ以下.

// ② 文字列 y の分割(文字列 A (a文字), 文字列 C (c文字)) は, 文字列 y のサイズ未満.

// LL cur = (LL)min({x, a + c - y + 1, y - 1});

// 1_009.txt などで, WA版となったため, ロジック修正.

// -> (a, c) の組み合わせは, (1, y - 1), (2, y - 2), ..., (y - 1, 1) の高々 (y - 1)個.

// x > y の範囲で考えているので, x については, 特に考慮する必要は無さそうに見える.

// ③ (m, y - m) が, m <= a かつ y - m <= c となる最大の m は？

// ④ (y - n, n) が, y - n <= a かつ n <= c となる最大の n は？

LL m = (LL)max(min(a, y - 1), y - c);

LL n = (LL)max(min(c, y - 1), y - a);

LL cur = max(0LL, min(m + n - y + 1, (LL)(y - 1)));

// 加算.

ans += cur;

}

// 5. 出力.

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

return 0;

}

[入力例]
takaitai

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

[入力例]
aaaaaaaaaa

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

[入力例]
abcabc

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

[入力例]
aaaaa

[出力例]
1

[入力例]
abracadabra

[出力例]
0

[入力例]
aaaaabbbccccaaaccc

[出力例]
1

[入力例]
xyzxyzxyzxyzxyzxyzxyzxyzxyzxyz

[出力例]
26

[入力例]
aaaaabbbbcccaaaaabbbbcccaaaaabbbbcccdddaaaaabbbbcccddddaaaaabbbbcccdddddaaaaabbbbcccaaaaabbbbccc

[出力例]
11

[入力例]
aaabbbcccaaabbbcccaaabbbcccaaabbbcccaaabbbcccaaabbbcccaaabbbcccaaabbbcccaaabbbcccaaabbbccc

[出力例]
86

[入力例]
aabbbccccaabbbccccaabbbccccaabbbccccaabbbccccaabbbccccaabbbccccaabbbccccaabbbccccaabbbccccaabbbccccaabbbccccaabbbccccaabbbccccaabbbccccaabbbccccaabbbcccc

[出力例]
316

[入力例]

takaitai

[出力例]

※AtCoderのテストケースより

[入力例]

aaaaaaaaaa

[出力例]

※AtCoderのテストケースより

[入力例]

abcabc

[出力例]

※AtCoderのテストケースより

[入力例]

aaaaa

[出力例]

[入力例]

abracadabra

[出力例]

[入力例]

aaaaabbbccccaaaccc

[出力例]

[入力例]

xyzxyzxyzxyzxyzxyzxyzxyzxyzxyz

[出力例]

[入力例]

aaaaabbbbcccaaaaabbbbcccaaaaabbbbcccdddaaaaabbbbcccddddaaaaabbbbcccdddddaaaaabbbbcccaaaaabbbbccc

[出力例]

[入力例]

aaabbbcccaaabbbcccaaabbbcccaaabbbcccaaabbbcccaaabbbcccaaabbbcccaaabbbcccaaabbbcccaaabbbccc

[出力例]

[入力例]

aabbbccccaabbbccccaabbbccccaabbbccccaabbbccccaabbbccccaabbbccccaabbbccccaabbbccccaabbbccccaabbbccccaabbbccccaabbbccccaabbbccccaabbbccccaabbbccccaabbbcccc

[出力例]

316

■参照サイト
AtCoder Regular Contest 055

2022年7月14日2022年7月15日

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

C++の練習を兼ねて, AtCoder Beginner Contest 257 の問題G (Prefix Concatenation) を解いてみた.

■感想.
1. 問題Gは, 方針が見えなかったので, 解説プログラムを参考に, AC版に到達できたと思う.
2. 新しい知識として, Z-Algorithm を, 学習できたので, 非常に良かったと思う.
3. 苦手な動的計画法の訓練も積めたので, 非常に良かったと思う.
4. S = abcabc の場合, f[i] = 6 0 0 3 2 1 に変えて, f[i] = 6 0 0 3 0 0 が正しい結果に見えるため, Z-Algorithm の実装箇所から, 以下の部分を削除し, 再提出した.

if(r == ss){
    f[i] = ss - i;
    continue;
}

if(r == ss){

f[i] = ss - i;

continue;

}

5. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解答不能.
// https://atcoder.jp/contests/abc257/editorial/4185
// 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--)

int main(){
    
    // 1. 入力情報.
    char s[505050], t[505050];
    scanf("%s %s", s, t);
    string S(s), T(t);
    int ss = S.size();
    int ts = T.size();
    
    // 2. Z-Algorithm.
    // https://atcoder.jp/contests/abc257/editorial/4185
    // -> 解説プログラム一部変更.
    // ex.
    // S = aaabbcddaaabbaaaeaaabbcaaabbcddaaabbaefgaaabbcdaaa の 場合, 
    // f[i] = 50 2 1 0 0 0 0 0 5 2 1 0 0 3 2 1 0 6 2 1 0 0 0 14 2 1 0 0 0 0 0 5 2 1 0 0 1 0 0 0 7 2 1 0 0 0 0 3 2 1 
    // 
    // S = abcabc の 場合, 
    // f[i] = 6 0 0 3 0 0 
    auto z = [](string s, int ss, int* f){
        int l = 0, r = 1;
        f[0] = ss;
        repx(i, 1, ss){
            if(i > 1 && f[i - l] < r - i){
                f[i] = f[i - l];
                continue;
            }
            r = max(i, r);
            while(r < ss){
                if(s[r] == s[r - i]) ++r;
                else                 break;
            }
            f[i] = r - i;
            l = i;
        }
    };
    int f[505050];
    rep(i, 505050) f[i] = 0;
    z(s, ss, f);
    
    // 3. dp更新.
    // -> 解説の文章で説明されている添え字の対応関係が, 不明だったため, 解説プログラムを一部修正して提出.
    int dp[505050];
    rep(i, 505050) dp[i] = -1;
    int l = 0, r = 0;
    rep(i, ts){
        if(r == ts) break;
        if(!i){
            rep(j, min(ss, ts)){
                if(S[j] != T[j]) break;
                dp[j] = 1;
                r = j + 1;
            }
            continue;
        }
        if(dp[i - 1] == -1) break;
        if(f[i - l] >= r - i){
            while(r < ts && (r - i) < ss){
                if(T[r] != S[r - i]) break;
                dp[r] = dp[i - 1] + 1;
                ++r;
            }
            l = i;
        }
    }
    
    // 4. 出力.
    printf("%d\n", dp[ts - 1]);
    return 0;
    
}

// 解答不能.

// https://atcoder.jp/contests/abc257/editorial/4185

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

int main(){

// 1. 入力情報.

char s[505050], t[505050];

scanf("%s %s", s, t);

string S(s), T(t);

int ss = S.size();

int ts = T.size();

// 2. Z-Algorithm.

// https://atcoder.jp/contests/abc257/editorial/4185

// -> 解説プログラム一部変更.

// ex.

// S = aaabbcddaaabbaaaeaaabbcaaabbcddaaabbaefgaaabbcdaaa の場合,

// f[i] = 50 2 1 0 0 0 0 0 5 2 1 0 0 3 2 1 0 6 2 1 0 0 0 14 2 1 0 0 0 0 0 5 2 1 0 0 1 0 0 0 7 2 1 0 0 0 0 3 2 1

// S = abcabc の場合,

// f[i] = 6 0 0 3 0 0

auto z = [](string s, int ss, int* f){

int l = 0, r = 1;

f[0] = ss;

repx(i, 1, ss){

if(i > 1 && f[i - l] < r - i){

f[i] = f[i - l];

continue;

}

r = max(i, r);

while(r < ss){

if(s[r] == s[r - i]) ++r;

else break;

}

f[i] = r - i;

l = i;

}

};

int f[505050];

rep(i, 505050) f[i] = 0;

z(s, ss, f);

// 3. dp更新.

// -> 解説の文章で説明されている添え字の対応関係が, 不明だったため, 解説プログラムを一部修正して提出.

int dp[505050];

rep(i, 505050) dp[i] = -1;

int l = 0, r = 0;

rep(i, ts){

if(r == ts) break;

if(!i){

rep(j, min(ss, ts)){

if(S[j] != T[j]) break;

dp[j] = 1;

r = j + 1;

}

continue;

}

if(dp[i - 1] == -1) break;

if(f[i - l] >= r - i){

while(r < ts && (r - i) < ss){

if(T[r] != S[r - i]) break;

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

++r;

}

l = i;

}

// 4. 出力.

printf("%d\n", dp[ts - 1]);

return 0;

}

[入力例]
aba
ababaab

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

[入力例]
atcoder
ac

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

[入力例]
abcab
aaabb

[出力例]
-1

[入力例]
abcab
aabaaababcababc

[出力例]
7

[入力例]
aaabbcddaaabbaaaeaaabbcaaabbcddaaabbaefgaaabbcdaaa
aaaaaaaaaaaaaaaaaaaabbcddaaabbaaaeaaabbcaaabbcddaaabbaaaeaaabbcaaaaaabbcddaaabbaaaeaaabbcaaabbcddaaabbaef

[出力例]
9

[入力例]
abcopq
abcopqaabcopqaaabcopqaaaabcopqaaaaabcopqaaaaaabcopqaaaaaaabcopqaaaaaaaabcopqaaaaaaaaabcopqaaaaaaaaaabcopq

[出力例]
55

[入力例]

aba

ababaab

[出力例]

※AtCoderテストケースより

[入力例]

atcoder

[出力例]

-1

※AtCoderテストケースより

[入力例]

abcab

aaabb

[出力例]

-1

[入力例]

abcab

aabaaababcababc

[出力例]

[入力例]

aaabbcddaaabbaaaeaaabbcaaabbcddaaabbaefgaaabbcdaaa

aaaaaaaaaaaaaaaaaaaabbcddaaabbaaaeaaabbcaaabbcddaaabbaaaeaaabbcaaaaaabbcddaaabbaaaeaaabbcaaabbcddaaabbaef

[出力例]

[入力例]

abcopq

abcopqaabcopqaaabcopqaaaabcopqaaaaabcopqaaaaaabcopqaaaaaaabcopqaaaaaaaabcopqaaaaaaaaabcopqaaaaaaaaaabcopq

[出力例]

■参照サイト
日鉄ソリューションズプログラミングコンテスト2022（AtCoder Beginner Contest 257）

2022年7月11日

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

C++の練習を兼ねて, AtCoder Regular Contest 143 の問題A (Three Integers) ～問題B (Counting Grids) を解いてみた.

■感想.
1. 問題A, Bは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/arc143/editorial/4182
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(){
    
    // 1. 入力情報.
    LL a[3];
    scanf("%lld %lld %lld", &a[0], &a[1], &a[2]);
    
    // 2. sort.
    sort(a, a + 3);
    
    // 3. 出力.
    printf("%lld\n", (a[2] >= (a[2] - a[0]) + (a[2] - a[1])) ? a[2] : -1);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc143/editorial/4182

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

int main(){

// 1. 入力情報.

LL a[3];

scanf("%lld %lld %lld", &a[0], &a[1], &a[2]);

// 2. sort.

sort(a, a + 3);

// 3. 出力.

printf("%lld\n", (a[2] >= (a[2] - a[0]) + (a[2] - a[1])) ? a[2] : -1);

return 0;

}

[入力例]
2 2 3

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

[入力例]
0 0 1

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

[入力例]
0 0 0

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

[入力例]
314 159 265

[出力例]
314

[入力例]
2020 2021 2022

[出力例]
2022

[入力例]

2 2 3

[出力例]

※AtCoderのテストケースより

[入力例]

0 0 1

[出力例]

-1

※AtCoderのテストケースより

[入力例]

0 0 0

[出力例]

※AtCoderのテストケースより

[入力例]

314 159 265

[出力例]

314

[入力例]

2020 2021 2022

[出力例]

2022

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

// 解き直し.
// https://atcoder.jp/contests/arc143/editorial/4193
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#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 LL MOD = 998244353;
LL FAC[252525], INV[252525];

// Fermat's little theorem から, 大きな冪乗の計算を行う.
// @param a: べき乗したい正整数.
// @param b: 指数.
// @return:  べき乗した計算結果(mod版).
LL mPow(LL a, LL b){
    LL t = 1;
    while(b){
        if(b & 1) t = (t * a) % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return t;
}

// 組み合わせ(nCk)計算用(mod版).
// ※配列FAC, INV は, 事前に計算済のものを使う.
// @param n: 対象となる要素の個数.
// @param k: 選択する要素の個数.
// @return: 組み合わせ(nCk)の計算結果(mod版).
LL combination(LL n, LL k){
    if(n < 0 || k < 0 || k > n) return 0LL;
    if(n == k || k == 0LL) return 1LL;
    LL ret = FAC[n] * INV[k] % MOD * INV[n - k] % MOD;
    return ret;
}

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    
    // 2. 事前計算.
    FAC[0] = 1;
    repx(i, 1, 252525) FAC[i] = (LL)i * FAC[i - 1] % MOD;
    rep(i, 252525)     INV[i] = mPow(FAC[i], MOD - 2);
    
    // 3. 全体.
    LL a = FAC[N * N];
    
    // 4. 条件を満たさないもの.
    LL b = N * N;
    b *= combination(N * N, 2 * N - 1);
    b %= MOD;
    b *= FAC[N - 1];
    b %= MOD;
    b *= FAC[N - 1];
    b %= MOD;
    b *= FAC[(N - 1) * (N - 1)];
    b %= MOD;
    
    // 5. 出力.
    printf("%lld\n", (a + MOD - b) % MOD);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc143/editorial/4193

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

#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 LL MOD = 998244353;

LL FAC[252525], INV[252525];

// Fermat's little theorem から, 大きな冪乗の計算を行う.

// @param a: べき乗したい正整数.

// @param b: 指数.

// @return: べき乗した計算結果(mod版).

LL mPow(LL a, LL b){

LL t = 1;

while(b){

if(b & 1) t = (t * a) % MOD;

a = a * a % MOD;

b >>= 1;

}

return t;

}

// 組み合わせ(nCk)計算用(mod版).

// ※配列FAC, INV は, 事前に計算済のものを使う.

// @param n: 対象となる要素の個数.

// @param k: 選択する要素の個数.

// @return: 組み合わせ(nCk)の計算結果(mod版).

LL combination(LL n, LL k){

if(n < 0 || k < 0 || k > n) return 0LL;

if(n == k || k == 0LL) return 1LL;

LL ret = FAC[n] * INV[k] % MOD * INV[n - k] % MOD;

return ret;

}

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

// 2. 事前計算.

FAC[0] = 1;

repx(i, 1, 252525) FAC[i] = (LL)i * FAC[i - 1] % MOD;

rep(i, 252525) INV[i] = mPow(FAC[i], MOD - 2);

// 3. 全体.

LL a = FAC[N * N];

// 4. 条件を満たさないもの.

LL b = N * N;

b *= combination(N * N, 2 * N - 1);

b %= MOD;

b *= FAC[N - 1];

b %= MOD;

b *= FAC[N - 1];

b %= MOD;

b *= FAC[(N - 1) * (N - 1)];

b %= MOD;

// 5. 出力.

printf("%lld\n", (a + MOD - b) % MOD);

return 0;

}

[入力例]
2

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

[入力例]
5

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

[入力例]
100

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

[入力例]
3

[出力例]
254016

[入力例]
314

[出力例]
550897280

[入力例]

[出力例]

※AtCoderのテストケースより

[入力例]

[出力例]

704332752

※AtCoderのテストケースより

[入力例]

100

[出力例]

927703658

※AtCoderのテストケースより

[入力例]

[出力例]

254016

[入力例]

314

[出力例]

550897280

■参照サイト
AtCoder Regular Contest 143

2022年7月10日

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

C++の練習を兼ねて, AtCoder Beginner Contest 259 の問題C (XX to XXX) ～問題D (Circumferences) を解いてみた.

■感想.
1. 問題C, Dは, 方針を絞り込めたので, AC版に到達できたと思う.
2. 個人的には, 問題Dで, 幅優先探索の復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using P = pair<char, int>;
using vp = vector<P>;
#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

int main(){
    
    // 1. 入力情報.
    char s[202020], t[202020];
    scanf("%s %s", s, t);
    string S(s), T(t);
    
    // 2. 番兵.
    S.pb('#');
    T.pb('#');
    
    // 3. 各文字の連続出現数.
    // 3-1. 文字列 S.
    vp vs;
    int c = 1;
    rep(i, S.size() - 1){
        // 今回, 次回が同じ.
        if(S[i] == S[i + 1]){
            ++c;
            continue;
        }
        
        // 今回, 次回が異なる.
        vs.pb({S[i], c});
        c = 1;
    }
    
    // 3-2. 文字列 T.
    vp vt;
    c = 1;
    rep(i, T.size() - 1){
        // 今回, 次回が同じ.
        if(T[i] == T[i + 1]){
            ++c;
            continue;
        }
        
        // 今回, 次回が異なる.
        vt.pb({T[i], c});
        c = 1;
    }
    
    // 4. 例外.
    if(vs.size() != vt.size()){
        puts("No");
        return 0;
    }
    
    // 5. 判定.
    bool ok = true;
    rep(i, vs.size()){
        P sCur = vs[i];
        P tCur = vt[i];
        
        // 評価対象の文字.
        if(sCur.a != tCur.a){
            ok = false;
            continue;
        }
        
        // 出現回数の評価(その①).
        if((sCur.b == 1) && (tCur.b > 1)){
            ok = false;
            continue;
        }
        
        // 出現回数の評価(その②).
        if(sCur.b > tCur.b) ok = false;
    }
    
    // 6. 出力.
    printf("%s\n", ok ? "Yes" : "No");
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using P = pair<char, int>;

using vp = vector<P>;

#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

int main(){

// 1. 入力情報.

char s[202020], t[202020];

scanf("%s %s", s, t);

string S(s), T(t);

// 2. 番兵.

S.pb('#');

T.pb('#');

// 3. 各文字の連続出現数.

// 3-1. 文字列 S.

vp vs;

int c = 1;

rep(i, S.size() - 1){

// 今回, 次回が同じ.

if(S[i] == S[i + 1]){

++c;

continue;

}

// 今回, 次回が異なる.

vs.pb({S[i], c});

c = 1;

}

// 3-2. 文字列 T.

vp vt;

c = 1;

rep(i, T.size() - 1){

// 今回, 次回が同じ.

if(T[i] == T[i + 1]){

++c;

continue;

}

// 今回, 次回が異なる.

vt.pb({T[i], c});

c = 1;

}

// 4. 例外.

if(vs.size() != vt.size()){

puts("No");

return 0;

}

// 5. 判定.

bool ok = true;

rep(i, vs.size()){

P sCur = vs[i];

P tCur = vt[i];

// 評価対象の文字.

if(sCur.a != tCur.a){

ok = false;

continue;

}

// 出現回数の評価(その①).

if((sCur.b == 1) && (tCur.b > 1)){

ok = false;

continue;

}

// 出現回数の評価(その②).

if(sCur.b > tCur.b) ok = false;

}

// 6. 出力.

printf("%s\n", ok ? "Yes" : "No");

return 0;

}

[入力例]
abbaac
abbbbaaac

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

[入力例]
xyzz
xyyzz

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

[入力例]
mwqyvmhoful
mwqyvmhoful

[出力例]
Yes

[入力例]
aabbbcccc
bbbaacccc

[出力例]
No

[入力例]
aabbbccccdeefff
aaabbbbcccccdeeeeefffffff

[出力例]
Yes

[入力例]

abbaac

abbbbaaac

[出力例]

Yes

※AtCoderテストケースより

[入力例]

xyzz

xyyzz

[出力例]

※AtCoderテストケースより

[入力例]

mwqyvmhoful

[出力例]

Yes

[入力例]

aabbbcccc

bbbaacccc

[出力例]

[入力例]

aabbbccccdeefff

aaabbbbcccccdeeeeefffffff

[出力例]

Yes

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using T3 = tuple<LL, LL, LL>;
using vt = vector<T3>;
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
const LL INF = 2e18 + 1;

int main(){
    
    // 1. 入力情報.
    int N;
    LL sx, sy, tx, ty;
    scanf("%d %lld %lld %lld %lld", &N, &sx, &sy, &tx, &ty);
    vt v;
    int s = -1, t = -1;
    rep(i, N){
        LL x, y, r;
        scanf("%lld %lld %lld", &x, &y, &r);
        v.emplace_back(x, y, r);
        if(s == -1 && (sx - x) * (sx - x) + (sy - y) * (sy - y) == r * r) s = i;
        if(t == -1 && (tx - x) * (tx - x) + (ty - y) * (ty - y) == r * r) t = i;
    }
    assert(s != -1 && t != -1);
    
    // 2. グラフ作成.
    vvi G(N);
    rep(i, N){
        repx(j, i + 1, N){
            // 円 i.
            LL xi = get<0>(v[i]);
            LL yi = get<1>(v[i]);
            LL ri = get<2>(v[i]);
            
            // 円 j.
            LL xj = get<0>(v[j]);
            LL yj = get<1>(v[j]);
            LL rj = get<2>(v[j]);
            
            // 円 i と 円 j が 交点を持つか？
            LL dij = (xi - xj) * (xi - xj) + (yi - yj) * (yi - yj);
            if(dij >= (ri - rj) * (ri - rj) && dij <= (ri + rj) * (ri + rj)){
                G[i].pb(j);
                G[j].pb(i);
            }
        }
    }
    
    // 3. bfs.
    // https://ja.wikipedia.org/wiki/幅優先探索
    auto bfs = [&](vvi &G, int s, LL* d) {
        // 空のキュー.
        queue<int> q;
        
        // 開始地点は, 距離ゼロ.
        d[s] = 0;
        
        // 探索地点 s をキュー q に追加.
        q.push(s);
        while(!q.empty()){
            // キューから取り出す.
            int u = q.front();
            q.pop();
            
            // 隣接頂点をチェック.
            for(auto &e : G[u]) if(d[e] == INF && e != s) d[e] = d[u] + 1, q.push(e);
        }
    };
    LL d[N];
    rep(i, N) d[i] = INF;
    bfs(G, s, d);
    
    // 4. 出力.
    printf("%s\n", (d[t] == INF) ? "No" : "Yes");
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

using vt = vector<T3>;

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

const LL INF = 2e18 + 1;

int main(){

// 1. 入力情報.

int N;

LL sx, sy, tx, ty;

scanf("%d %lld %lld %lld %lld", &N, &sx, &sy, &tx, &ty);

vt v;

int s = -1, t = -1;

rep(i, N){

LL x, y, r;

scanf("%lld %lld %lld", &x, &y, &r);

v.emplace_back(x, y, r);

if(s == -1 && (sx - x) * (sx - x) + (sy - y) * (sy - y) == r * r) s = i;

if(t == -1 && (tx - x) * (tx - x) + (ty - y) * (ty - y) == r * r) t = i;

}

assert(s != -1 && t != -1);

// 2. グラフ作成.

vvi G(N);

rep(i, N){

repx(j, i + 1, N){

// 円 i.

LL xi = get<0>(v[i]);

LL yi = get<1>(v[i]);

LL ri = get<2>(v[i]);

// 円 j.

LL xj = get<0>(v[j]);

LL yj = get<1>(v[j]);

LL rj = get<2>(v[j]);

// 円 i と円 j が交点を持つか？

LL dij = (xi - xj) * (xi - xj) + (yi - yj) * (yi - yj);

if(dij >= (ri - rj) * (ri - rj) && dij <= (ri + rj) * (ri + rj)){

G[i].pb(j);

G[j].pb(i);

}

// 3. bfs.

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

auto bfs = [&](vvi &G, int s, LL* d) {

// 空のキュー.

queue<int> q;

// 開始地点は, 距離ゼロ.

d[s] = 0;

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

q.push(s);

while(!q.empty()){

// キューから取り出す.

int u = q.front();

q.pop();

// 隣接頂点をチェック.

for(auto &e : G[u]) if(d[e] == INF && e != s) d[e] = d[u] + 1, q.push(e);

}

};

LL d[N];

rep(i, N) d[i] = INF;

bfs(G, s, d);

// 4. 出力.

printf("%s\n", (d[t] == INF) ? "No" : "Yes");

return 0;

}

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

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

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

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

[入力例]
5
0 -6 9 3
0 -3 3
-3 0 3
-6 3 3
3 0 3
6 3 3

[出力例]
Yes

[入力例]
10
5 0 6 8
0 0 5
0 6 3
0 -6 3
6 0 3
-6 0 3
0 9 1
0 -9 1
9 0 1
-9 0 1
0 0 10

[出力例]
Yes

[入力例]

0 -2 3 3

0 0 2

2 0 2

2 3 1

-3 3 3

[出力例]

Yes

※AtCoderテストケースより

[入力例]

0 1 0 3

0 0 1

0 0 2

0 0 3

[出力例]

※AtCoderテストケースより

[入力例]

0 -6 9 3

0 -3 3

-3 0 3

-6 3 3

3 0 3

6 3 3

[出力例]

Yes

[入力例]

5 0 6 8

0 0 5

0 6 3

0 -6 3

6 0 3

-6 0 3

0 9 1

0 -9 1

9 0 1

-9 0 1

0 0 10

[出力例]

Yes

■参照サイト
AtCoder Beginner Contest 259

2022年7月9日2022年7月9日

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

C++の練習を兼ねて, AtCoder Beginner Contest 258 の問題E (Packing Potatoes) を解いてみた.

■感想.
1. 問題Eは, 方針を絞り込めたので, AC版に到達できたと思う.
2. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vl = vector<LL>;
#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 pob pop_back
#define pub push_back
LL w[202020], wCum[202020], p[202020];
int s[202020];

int main(){
    
    // 1. 入力情報.
    int N, Q;
    LL X, wSum = 0;
    scanf("%d %d %lld", &N, &Q, &X);
    rep(i, N){
        scanf("%lld", &w[i]);
        wCum[i + 1] = wCum[i] + w[i];
    }
    
    // 2. 初期化.
    int g = 0;
    rep(i, 202020) s[i] = -1;
    wCum[N + 1] = wCum[N];
    
    // 3. 事前準備.
    rep(i, N){
        // 3-1. 開始番号.
        s[i] = g;
        
        // 3-2. 重さの総和が, X以上となるには？
        g = lower_bound(wCum, wCum + N + 1, wCum[s[i]] + X) - wCum;
        LL d = wCum[g] - wCum[s[i]];
        if(d >= X) p[i] = g - s[i];
        if(d < X){
            LL q = (X - d) / wCum[N];
            LL r = (X - d) % wCum[N];
            g = lower_bound(wCum, wCum + N + 1, r) - wCum;
            p[i] = q * N + (N - s[i]) + g;
        }
        
        // 3-3. 次へ.
        g = g % N;
    }
    
    // 4. 周期は？
    // 4-1. 周期を区切る値.
    set<int> st;
    int at = 0, wi = 0;
    rep(i, N){
        if(st.count(s[i])){
            at = s[i];
            break;
        }
        st.insert(s[i]);
    }
    
    // 4-2. 周期を区切る位置.
    rep(i, N){
        if(s[i] == at){
            wi = i;
            break;
        }
    }
    
    // 5. あり得る箱に入っているじゃがいもの個数.
    vl b1, b2;
    st.clear();
    rep(i, N){
        // 5-1. 終了条件.
        if(st.count(s[i])) break;
        
        // 5-2. 要素を保存.
        if(i < wi) b1.pub(p[i]);
        else       b2.pub(p[i]);
        
        // 5-3. 訪問済設定.
        st.insert(s[i]);
    }
    
    // 6. クエリ回答.
    int n1 = b1.size(), n2 = b2.size();
    rep(i, Q){
        // 6-1. クエリ入力情報.
        LL K;
        scanf("%lld", &K);
        --K;
        
        // 6-2. 出力.
        if(K < n1) printf("%lld\n", b1[(int)K]);
        else       printf("%lld\n", b2[(int)((K - n1) % n2)]);
    }
    return 0;
    
}

100

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vl = vector<LL>;

#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 pob pop_back

#define pub push_back

LL w[202020], wCum[202020], p[202020];

int s[202020];

int main(){

// 1. 入力情報.

int N, Q;

LL X, wSum = 0;

scanf("%d %d %lld", &N, &Q, &X);

rep(i, N){

scanf("%lld", &w[i]);

wCum[i + 1] = wCum[i] + w[i];

}

// 2. 初期化.

int g = 0;

rep(i, 202020) s[i] = -1;

wCum[N + 1] = wCum[N];

// 3. 事前準備.

rep(i, N){

// 3-1. 開始番号.

s[i] = g;

// 3-2. 重さの総和が, X以上となるには？

g = lower_bound(wCum, wCum + N + 1, wCum[s[i]] + X) - wCum;

LL d = wCum[g] - wCum[s[i]];

if(d >= X) p[i] = g - s[i];

if(d < X){

LL q = (X - d) / wCum[N];

LL r = (X - d) % wCum[N];

g = lower_bound(wCum, wCum + N + 1, r) - wCum;

p[i] = q * N + (N - s[i]) + g;

}

// 3-3. 次へ.

g = g % N;

}

// 4. 周期は？

// 4-1. 周期を区切る値.

set<int> st;

int at = 0, wi = 0;

rep(i, N){

if(st.count(s[i])){

at = s[i];

break;

}

st.insert(s[i]);

}

// 4-2. 周期を区切る位置.

rep(i, N){

if(s[i] == at){

wi = i;

break;

}

// 5. あり得る箱に入っているじゃがいもの個数.

vl b1, b2;

st.clear();

rep(i, N){

// 5-1. 終了条件.

if(st.count(s[i])) break;

// 5-2. 要素を保存.

if(i < wi) b1.pub(p[i]);

else b2.pub(p[i]);

// 5-3. 訪問済設定.

st.insert(s[i]);

}

// 6. クエリ回答.

int n1 = b1.size(), n2 = b2.size();

rep(i, Q){

// 6-1. クエリ入力情報.

LL K;

scanf("%lld", &K);

--K;

// 6-2. 出力.

if(K < n1) printf("%lld\n", b1[(int)K]);

else printf("%lld\n", b2[(int)((K - n1) % n2)]);

}

return 0;

}

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

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

[入力例]
10 5 20
5 8 5 9 8 7 4 4 8 2
1
1000
1000000
1000000000
1000000000000

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

[入力例]
10 7 2022
3 1 4 1 5 9 2 6 5 3
1
10
100
1000
10000
100000
1000000

[出力例]
519
520
520
520
520
520
520

[入力例]
30 12 20220709
88 46 82 116 23 77 65 118 6 3 16 102 1 43 72 28 15 60 72 76 49 9 18 76 9 78 56 111 94 39
438
559
734
684
109
3
979
797
282
131
770
308

[出力例]
368097
368094
368097
368097
368094
368097
368094
368094
368094
368095
368095
368097

[入力例]
50 22 123456789
13178 8332 16796 11184 6448 5530 6253 12134 13871 7743 7125 15067 15683 5310 12459 7199 6583 12051 13587 10439 7885 12445 12332 16369 7532 13214 8929 16801 14022 7133 9432 6451 10296 5878 12159 14788 8248 8127 11524 16830 8634 10144 7504 15596 4863 6343 15314 10192 12669 4917
4845673
3914668
6455736
5749472
9885018
7910987
996876
522416
7795112
3065943
7521842
3614894
8313320
2959256
1093096
1059995
2430186
6134091
6469304
1608536
6457470
4683723

[出力例]
11790
11791
11791
11791
11790
11791
11791
11791
11791
11791
11792
11790
11791
11791
11791
11791
11790
11791
11791
11791
11790
11790

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

[入力例]

3 2 5

3 4 1

[出力例]

※AtCoderテストケースより

[入力例]

10 5 20

5 8 5 9 8 7 4 4 8 2

1000

1000000

1000000000

1000000000000

[出力例]

※AtCoderテストケースより

[入力例]

10 7 2022

3 1 4 1 5 9 2 6 5 3

100

1000

10000

100000

1000000

[出力例]

519

520

[入力例]

30 12 20220709

88 46 82 116 23 77 65 118 6 3 16 102 1 43 72 28 15 60 72 76 49 9 18 76 9 78 56 111 94 39

438

559

734

684

109

979

797

282

131

770

308

[出力例]

368097

368094

368097

368094

368097

368094

368095

368097

[入力例]

50 22 123456789

13178 8332 16796 11184 6448 5530 6253 12134 13871 7743 7125 15067 15683 5310 12459 7199 6583 12051 13587 10439 7885 12445 12332 16369 7532 13214 8929 16801 14022 7133 9432 6451 10296 5878 12159 14788 8248 8127 11524 16830 8634 10144 7504 15596 4863 6343 15314 10192 12669 4917

4845673

3914668

6455736

5749472

9885018

7910987

996876

522416

7795112

3065943

7521842

3614894

8313320

2959256

1093096

1059995

2430186

6134091

6469304

1608536

6457470

4683723

[出力例]

11790

11791

11790

11791

11792

11790

11791

11790

11791

11790

■参照サイト
AtCoder Beginner Contest 258

2022年7月8日2022年7月8日

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

C++の練習を兼ねて, AtCoder Regular Contest 142 の問題C (Tree Queries) を解いてみた.

■感想.
1. 問題Cは, 方針を絞り込めなかったので, 解説を参考に, AC版に到達できたと思う.
2. 解説上の D[i] が 3 となるパターンについて, 細かい分岐を, すべて考慮する必要があり, 自力で, これを取り纏めることが出来なかったので, 正答まで到達出来なかったと理解した.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/arc142/editorial/4101
// 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--)
int d1[111], d2[111], d[222];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    
    // 2. 質問(頂点 1 との 距離).
    repx(v, 3, N + 1){
        printf("? %d %d\n", 1, v);
        fflush(stdout);
        scanf("%d", &d1[v]);
    }
    
    // 3. 質問(頂点 2 との 距離).
    repx(v, 3, N + 1){
        printf("? %d %d\n", 2, v);
        fflush(stdout);
        scanf("%d", &d2[v]);
    }
    
    // 4. 頂点 1, 2 の 距離は？
    // -> 距離の和の最小値(d とする)が, 頂点 1, 2 間 の 頂点数である(d - 1)回出現するはず.
    // ※ 解説にある通り, この考え方は, 最小値が, 3 と異なる場合に限定されることに注意.
    int ans = 1;
    repx(v, 3, N + 1) ++d[d1[v] + d2[v]];
    rep(i, 222){
        if(d[i]){
            // if(d[i] + 1 == i) ans = i;
            ans = i;
            break;
        }
    }
    
    // 5. d != 3.
    if(ans != 3){
        printf("! %d\n", ans);
        return 0;
    }
    
    // 6. d = 3 かつ 出現は, 2回でない.
    if(d[3] != 2){
        printf("! %d\n", 1);
        return 0;
    }
    
    // 7. それ以外.
    // 7-1. 頂点 x, y は？
    int x = 0, y = 0;
    repx(v, 3, N + 1){
        if(d1[v] + d2[v] == 3){
            if(!x){
                x = v;
                continue;
            }
            if(!y){
                y = v;
                break;
            }
        }
    }
    assert(x && y);
    
    // 7-2. 頂点 x, y の距離は？
    int dxy = 0;
    printf("? %d %d\n", x, y);
    fflush(stdout);
    scanf("%d", &dxy);
    
    // 7-3. 出力.
    printf("! %d\n", (dxy == 1) ? 3 : 1);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc142/editorial/4101

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

int d1[111], d2[111], d[222];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

// 2. 質問(頂点 1 との距離).

repx(v, 3, N + 1){

printf("? %d %d\n", 1, v);

fflush(stdout);

scanf("%d", &d1[v]);

}

// 3. 質問(頂点 2 との距離).

repx(v, 3, N + 1){

printf("? %d %d\n", 2, v);

fflush(stdout);

scanf("%d", &d2[v]);

}

// 4. 頂点 1, 2 の距離は？

// -> 距離の和の最小値(d とする)が, 頂点 1, 2 間の頂点数である(d - 1)回出現するはず.

// ※ 解説にある通り, この考え方は, 最小値が, 3 と異なる場合に限定されることに注意.

int ans = 1;

repx(v, 3, N + 1) ++d[d1[v] + d2[v]];

rep(i, 222){

if(d[i]){

// if(d[i] + 1 == i) ans = i;

ans = i;

break;

}

// 5. d != 3.

if(ans != 3){

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

return 0;

}

// 6. d = 3 かつ出現は, 2回でない.

if(d[3] != 2){

printf("! %d\n", 1);

return 0;

}

// 7. それ以外.

// 7-1. 頂点 x, y は？

int x = 0, y = 0;

repx(v, 3, N + 1){

if(d1[v] + d2[v] == 3){

if(!x){

x = v;

continue;

}

if(!y){

y = v;

break;

}

assert(x && y);

// 7-2. 頂点 x, y の距離は？

int dxy = 0;

printf("? %d %d\n", x, y);

fflush(stdout);

scanf("%d", &dxy);

// 7-3. 出力.

printf("! %d\n", (dxy == 1) ? 3 : 1);

return 0;

}

※インタラクティブな問題のため, 入出力は, デバッグ時に使用したものを記載している.

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

[出力例]
? 1 3
? 1 4
? 1 5
? 2 3
? 2 4
? 2 5
? 3 4
! 1

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

[出力例]
? 1 3
? 1 4
? 1 5
? 1 6
? 1 7
? 2 3
? 2 4
? 2 5
? 2 6
? 2 7
! 1

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

[出力例]
? 1 3
? 1 4
? 1 5
? 1 6
? 1 7
? 2 3
? 2 4
? 2 5
? 2 6
? 2 7
? 3 4
! 3

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

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

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

[出力例]
? 1 3
? 1 4
? 1 5
? 1 6
? 1 7
? 1 8
? 1 9
? 1 10
? 1 11
? 1 12
? 2 3
? 2 4
? 2 5
? 2 6
? 2 7
? 2 8
? 2 9
? 2 10
? 2 11
? 2 12
! 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

※インタラクティブな問題のため, 入出力は, デバッグ時に使用したものを記載している.

[入力例]

[出力例]

? 1 3

? 1 4

? 1 5

? 2 3

? 2 4

? 2 5

? 3 4

! 1

[入力例]

[出力例]

? 1 3

? 1 4

? 1 5

? 1 6

? 1 7

? 2 3

? 2 4

? 2 5

? 2 6

? 2 7

! 1

[入力例]

[出力例]

? 1 3

? 1 4

? 1 5

? 1 6

? 1 7

? 2 3

? 2 4

? 2 5

? 2 6

? 2 7

? 3 4

! 3

[入力例]

[出力例]

? 1 3

? 1 4

? 1 5

? 1 6

? 1 7

? 1 8

? 1 9

? 1 10

? 1 11

? 1 12

? 2 3

? 2 4

? 2 5

? 2 6

? 2 7

? 2 8

? 2 9

? 2 10

? 2 11

? 2 12

! 1

[入力例]

[出力例]

? 1 3

? 1 4

? 1 5

? 1 6

? 1 7

? 1 8

? 1 9

? 1 10

? 1 11

? 1 12

? 2 3

? 2 4

? 2 5

? 2 6

? 2 7

? 2 8

? 2 9

? 2 10

? 2 11

? 2 12

! 7

■参照サイト
AtCoder Regular Contest 142

2022年7月7日

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

C++の練習を兼ねて, AtCoder Regular Contest 142 の問題A (Reverse and Minimize) ～問題B (Unbalanced Squares) を解いてみた.

■感想.
1. 問題Bは, 方針が見えなかったため, 解説を参考に, AC版に到達できたと思う.
2. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define all(x) x.begin(), x.end()

int main(){
    
    // 1. 入力情報.
    LL N, K;
    scanf("%lld %lld", &N, &K);
    
    // 2. 例外.
    // -> 04_big_01.txt の WA を 回避するため, ロジック修正.
    string o = to_string(K);
    string r = to_string(K);
    reverse(all(r));
    if(r < o){
        puts("0");
        return 0;
    }
    
    // 3. f[x] = K.
    // 3-1. そのまま.
    set<LL> st;
    LL x = K;
    while(x <= N){
        st.insert(x);
        x *= 10;
    }
    
    // 3-2. 反転.
    x = stoll(r);
    while(x <= N){
        st.insert(x);
        x *= 10;
    }
    
    // 4. 出力.
    printf("%d\n", st.size());
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

int main(){

// 1. 入力情報.

LL N, K;

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

// 2. 例外.

// -> 04_big_01.txt の WA を回避するため, ロジック修正.

string o = to_string(K);

string r = to_string(K);

reverse(all(r));

if(r < o){

puts("0");

return 0;

}

// 3. f[x] = K.

// 3-1. そのまま.

set<LL> st;

LL x = K;

while(x <= N){

st.insert(x);

x *= 10;

}

// 3-2. 反転.

x = stoll(r);

while(x <= N){

st.insert(x);

x *= 10;

}

// 4. 出力.

printf("%d\n", st.size());

return 0;

}

[入力例]
1420 142

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

[入力例]
1419 142

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

[入力例]
6 19

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

[入力例]
314159 265

[出力例]
7

[入力例]
1234567890 2022

[出力例]
12

[入力例]
1234567890 2102

[出力例]
0

[入力例]
202020202020 707

[出力例]
9

[入力例]

1420 142

[出力例]

※AtCoderのテストケースより

[入力例]

1419 142

[出力例]

※AtCoderのテストケースより

[入力例]

6 19

[出力例]

※AtCoderのテストケースより

[入力例]

314159 265

[出力例]

[入力例]

1234567890 2022

[出力例]

[入力例]

1234567890 2102

[出力例]

[入力例]

202020202020 707

[出力例]

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

// 解き直し.
// https://atcoder.jp/contests/arc142/editorial/4100
// 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--)
int board[505][505];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    
    // 2. 書き込み(奇数行).
    int cur = 0;
    rep(i, N) if(!(i & 1)) rep(j, N) board[i][j] = ++cur;
    
    // 3. 書き込み(偶数行).
    rep(i, N) if(i & 1) rep(j, N) board[i][j] = ++cur;
    
    // 4. チェック.
    rep(i, N){
        rep(j, N){
            // 隣接マス.
            int a = 0, b = 0, v = board[i][j];
            for(auto &p : {-1, 0, 1}){
                for(auto &q : {-1, 0, 1}){
                    if(p == 0 && q == 0) continue;
                    int ni = i + p, nj = j + q;
                    if(ni < 0 || nj < 0 || ni >= N || nj >= N) continue;
                    int nv = board[ni][nj];
                    if(v < nv) ++a;
                    if(v > nv) ++b;
                }
            }
            
            // a != b か？
            assert(a != b);
        }
    }
    
    // 5. 出力.
    rep(i, N) rep(j, N) printf("%d%s", board[i][j], (j < N - 1) ? " " : "\n");
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc142/editorial/4100

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

int board[505][505];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

// 2. 書き込み(奇数行).

int cur = 0;

rep(i, N) if(!(i & 1)) rep(j, N) board[i][j] = ++cur;

// 3. 書き込み(偶数行).

rep(i, N) if(i & 1) rep(j, N) board[i][j] = ++cur;

// 4. チェック.

rep(i, N){

rep(j, N){

// 隣接マス.

int a = 0, b = 0, v = board[i][j];

for(auto &p : {-1, 0, 1}){

for(auto &q : {-1, 0, 1}){

if(p == 0 && q == 0) continue;

int ni = i + p, nj = j + q;

if(ni < 0 || nj < 0 || ni >= N || nj >= N) continue;

int nv = board[ni][nj];

if(v < nv) ++a;

if(v > nv) ++b;

}

// a != b か？

assert(a != b);

}

// 5. 出力.

rep(i, N) rep(j, N) printf("%d%s", board[i][j], (j < N - 1) ? " " : "\n");

return 0;

}

[入力例]
2

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

[入力例]
3

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

※ 但し, 上記のプログラムでは, 以下の内容が出力される.
1 2 3
7 8 9
4 5 6

[入力例]
4

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

[入力例]
5

[出力例]
1 2 3 4 5
16 17 18 19 20
6 7 8 9 10
21 22 23 24 25
11 12 13 14 15

[入力例]
10

[出力例]
1 2 3 4 5 6 7 8 9 10
51 52 53 54 55 56 57 58 59 60
11 12 13 14 15 16 17 18 19 20
61 62 63 64 65 66 67 68 69 70
21 22 23 24 25 26 27 28 29 30
71 72 73 74 75 76 77 78 79 80
31 32 33 34 35 36 37 38 39 40
81 82 83 84 85 86 87 88 89 90
41 42 43 44 45 46 47 48 49 50
91 92 93 94 95 96 97 98 99 100

[入力例]
18

[出力例]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180
19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198
37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54
199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216
55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72
217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234
73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90
235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252
91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108
253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270
109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126
271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288
127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144
289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306
145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162
307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324

[入力例]

[出力例]

1 2

3 4

※AtCoderのテストケースより

[入力例]

[出力例]

1 2 3

5 4 6

7 8 9

※AtCoderのテストケースより

※ 但し, 上記のプログラムでは, 以下の内容が出力される.

1 2 3

7 8 9

4 5 6

[入力例]

[出力例]

1 2 3 4

9 10 11 12

5 6 7 8

13 14 15 16

[入力例]

[出力例]

1 2 3 4 5

16 17 18 19 20

6 7 8 9 10

21 22 23 24 25

11 12 13 14 15

[入力例]

[出力例]

1 2 3 4 5 6 7 8 9 10

51 52 53 54 55 56 57 58 59 60

11 12 13 14 15 16 17 18 19 20

61 62 63 64 65 66 67 68 69 70

21 22 23 24 25 26 27 28 29 30

71 72 73 74 75 76 77 78 79 80

31 32 33 34 35 36 37 38 39 40

81 82 83 84 85 86 87 88 89 90

41 42 43 44 45 46 47 48 49 50

91 92 93 94 95 96 97 98 99 100

[入力例]

[出力例]

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180

19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198

37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54

199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216

55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72

217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234

73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90

235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252

91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108

253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270

109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126

271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288

127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144

289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306

145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162

307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324

■参照サイト
AtCoder Regular Contest 142

2022年7月6日

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

C++の練習を兼ねて, AtCoder Regular Contest 123 の問題E (Training) を解いてみた.

■感想.
1. 問題Eは, 方針が見えなかったため, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 場合分けが多く, 実装に苦労したものの, 解説のロジックで, 個数を高速に数え上げることが出来る点に, 興味深く感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/arc123/editorial/2291
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#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--)

int main(){
    
    // 1. 入力情報.
    int T;
    scanf("%d", &T);
    
    // 2. Σ[A + x / B].
    auto o = [&](LL N, LL a, LL b) -> LL {
        // ex.
        // N = 16, B = 3 の 時, Σ[x / B] の 値は？
        // 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15
        // 0, 0, 0, 1, 1, 1, 2, 2, 2, 3,  3,  3,  4,  4,  4,  5
        // -> 0 ～ 5 は, B個(3個)ずつあるので, (初項 0 + 最終項 5) * 6個 / 2 * B個 = 45
        //    5 は, 2個余分なので, 5 * (B - N % B) = 5 * 2 = 10
        //    計算結果は, 45 - 10 = 35 となる.
        // 
        // 2-1. 区間[0, N) での総和.
        LL q = N / b;
        LL r = N % b;
        LL ret = 0;
        
        // A は N項.
        ret += a * N;
        
        // B個ずつ出現.
        ret += q * (q + 1) / 2 * b;
        
        // 超過分.
        ret -= q * (b - r);
        
        // 2-2. 計算結果.
        return ret;
    };
    
    // 3. テストケース.
    rep(i, T){
        // 3-1. 各テストケース.
        LL N, ax, bx, ay, by;
        scanf("%lld %lld %lld %lld %lld", &N, &ax, &bx, &ay, &by);
        
        // 3-2. 例外(bx = by).
        if(bx == by){
            printf("%lld\n", (ax != ay) ? 0LL : N);
            continue;
        }
        
        // 3-3. 例外.
        if((ax > ay && by >= bx) || (ax < ay && by <= bx)){
            puts("0");
            continue;
        }
        
        // 3-4. 例外(ax = ay).
        // -> m / bx <= m / by + 1 となる最大の m は？
        if(ax == ay){
            if(bx > by) swap(bx, by);
            LL n = min(by * bx / (by - bx), N + 1);
            LL f = o(n, ax, bx);
            LL g = o(n, ay, by);
            printf("%lld\n", n - 1 - abs(f - g));
            continue;
        }
        
        // 3-5. swap.
        if(ax < ay){
            swap(ax, ay);
            swap(bx, by);
        }
        
        // 3-6. 大小が入れ替わる地点.
        // パターン① (ax + m / bx = ay + m / by).
        LL m = (ax - ay) * bx * by / (bx - by);
        m = min(max(0LL, m), N);
        
        // パターン② (ax + m / bx <= ay + m / by + 1).
        LL l = (ax - ay - 1) * bx * by / (bx - by);
        l = min({max(0LL, l), m, N});
        
        // パターン③ (ax + m / bx + 1 >= ay + m / by).
        LL r = (ax - ay + 1) * bx * by / (bx - by);
        r = min(max({0LL, m, r}), N);
        
        // 3-7. 区間[l, m).
        LL fl = o(m, ax, bx) - o(l, ax, bx);
        LL gl = o(m, ay, by) - o(l, ay, by);
        
        // 3-8. 区間[m, r + 1).
        LL fr = o(r + 1, ax, bx) - o(m, ax, bx);
        LL gr = o(r + 1, ay, by) - o(m, ay, by);
        
        // 3-9. 出力.
        if(l >= N) puts("0");
        else       printf("%lld\n", r - l + 1 - abs(fl - gl) - abs(fr - gr));
    }
    return 0;
    
}

100

101

102

103

104

105

106

107

108

// 解き直し.

// https://atcoder.jp/contests/arc123/editorial/2291

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

int main(){

// 1. 入力情報.

int T;

scanf("%d", &T);

// 2. Σ[A + x / B].

auto o = [&](LL N, LL a, LL b) -> LL {

// ex.

// N = 16, B = 3 の時, Σ[x / B] の値は？

// 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15

// 0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5

// -> 0 ～ 5 は, B個(3個)ずつあるので, (初項 0 + 最終項 5) * 6個 / 2 * B個 = 45

// 5 は, 2個余分なので, 5 * (B - N % B) = 5 * 2 = 10

// 計算結果は, 45 - 10 = 35 となる.

// 2-1. 区間[0, N) での総和.

LL q = N / b;

LL r = N % b;

LL ret = 0;

// A は N項.

ret += a * N;

// B個ずつ出現.

ret += q * (q + 1) / 2 * b;

// 超過分.

ret -= q * (b - r);

// 2-2. 計算結果.

return ret;

};

// 3. テストケース.

rep(i, T){

// 3-1. 各テストケース.

LL N, ax, bx, ay, by;

scanf("%lld %lld %lld %lld %lld", &N, &ax, &bx, &ay, &by);

// 3-2. 例外(bx = by).

if(bx == by){

printf("%lld\n", (ax != ay) ? 0LL : N);

continue;

}

// 3-3. 例外.

if((ax > ay && by >= bx) || (ax < ay && by <= bx)){

puts("0");

continue;

}

// 3-4. 例外(ax = ay).

// -> m / bx <= m / by + 1 となる最大の m は？

if(ax == ay){

if(bx > by) swap(bx, by);

LL n = min(by * bx / (by - bx), N + 1);

LL f = o(n, ax, bx);

LL g = o(n, ay, by);

printf("%lld\n", n - 1 - abs(f - g));

continue;

}

// 3-5. swap.

if(ax < ay){

swap(ax, ay);

swap(bx, by);

}

// 3-6. 大小が入れ替わる地点.

// パターン① (ax + m / bx = ay + m / by).

LL m = (ax - ay) * bx * by / (bx - by);

m = min(max(0LL, m), N);

// パターン② (ax + m / bx <= ay + m / by + 1).

LL l = (ax - ay - 1) * bx * by / (bx - by);

l = min({max(0LL, l), m, N});

// パターン③ (ax + m / bx + 1 >= ay + m / by).

LL r = (ax - ay + 1) * bx * by / (bx - by);

r = min(max({0LL, m, r}), N);

// 3-7. 区間[l, m).

LL fl = o(m, ax, bx) - o(l, ax, bx);

LL gl = o(m, ay, by) - o(l, ay, by);

// 3-8. 区間[m, r + 1).

LL fr = o(r + 1, ax, bx) - o(m, ax, bx);

LL gr = o(r + 1, ay, by) - o(m, ay, by);

// 3-9. 出力.

if(l >= N) puts("0");

else printf("%lld\n", r - l + 1 - abs(fl - gl) - abs(fr - gr));

}

return 0;

}

[入力例]
5
10 5 3 4 2
5 5 3 4 2
100 5 3 4 2
10 5 3 4 3
10 5 10 5 9

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

[入力例]
10
1060 17 1 69 8
644 76 7 59 5
330 122 8 117 5
542 31 3 61 6
753 48 3 82 10
262 50 11 49 10
561 103 9 112 11
1045 106 7 109 12
861 50 8 49 7
889 77 12 80 15

[出力例]
1
17
13
6
3
110
49
17
56
60

[入力例]
15
354 101 25 110 120
545 110 17 112 23
292 35 83 33 78
576 53 10 48 7
945 99 96 97 90
291 111 79 110 77
337 77 86 78 88
270 115 32 116 36
326 26 93 59 2
242 4 27 91 78
315 55 23 59 97
244 110 5 111 7
512 34 35 36 40
302 68 9 70 13
324 46 117 44 2

[出力例]
25
65
0
23
0
12
12
127
0
0
28
17
98
29
2

[入力例]

10 5 3 4 2

5 5 3 4 2

100 5 3 4 2

10 5 3 4 3

10 5 10 5 9

[出力例]

※AtCoderテストケースより

[入力例]

1060 17 1 69 8

644 76 7 59 5

330 122 8 117 5

542 31 3 61 6

753 48 3 82 10

262 50 11 49 10

561 103 9 112 11

1045 106 7 109 12

861 50 8 49 7

889 77 12 80 15

[出力例]

110

[入力例]

354 101 25 110 120

545 110 17 112 23

292 35 83 33 78

576 53 10 48 7

945 99 96 97 90

291 111 79 110 77

337 77 86 78 88

270 115 32 116 36

326 26 93 59 2

242 4 27 91 78

315 55 23 59 97

244 110 5 111 7

512 34 35 36 40

302 68 9 70 13

324 46 117 44 2

[出力例]

127

■参照サイト
AtCoder Regular Contest 123

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

C++の練習を兼ねて, AtCoder Regular Contest 060 の 問題F (最良表現) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 055 の 問題C (ABCAC) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 257 の 問題G (Prefix Concatenation) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 143 の 問題A (Three Integers) ～ 問題B (Counting Grids) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 259 の 問題C (XX to XXX) ～ 問題D (Circumferences) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 258 の 問題E (Packing Potatoes) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 142 の 問題C (Tree Queries) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 142 の 問題A (Reverse and Minimize) ～ 問題B (Unbalanced Squares) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 123 の 問題E (Training) を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 060 の問題F (最良表現) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 055 の問題C (ABCAC) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 257 の問題G (Prefix Concatenation) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 143 の問題A (Three Integers) ～問題B (Counting Grids) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 259 の問題C (XX to XXX) ～問題D (Circumferences) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 258 の問題E (Packing Potatoes) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 142 の問題C (Tree Queries) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 142 の問題A (Reverse and Minimize) ～問題B (Unbalanced Squares) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 123 の問題E (Training) を解いてみた.