個人用メモ帳

2021年8月3日2021年8月3日

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

C++の練習を兼ねて, 競プロ典型 90 問の問題011 (Gravy Jobs) を解いてみた.

■感想.
1. 問題011は, 解答の方針が見えなかったので, (問題011 (Gravy Jobs) 解説) を参考に実装したところ, AC版に到達出来た.
2. 苦手な動的計画法の訓練を積めたので, 非常に良かったと思う.
3. 手強い問題が非常に多い気もするけど, 時間を見つけて, 引き続き, 取り組んでいきたいと思う.

詳細は, 本家のサイト(GitHub) 競プロ典型 90 問の問題011 をご覧下さい.

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

// 解き直し.
// https://github.com/E869120/kyopro_educational_90/blob/main/editorial/011-02.jpg
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using T3 = tuple<int, int, 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 all(x) x.begin(), x.end()
LL dp[5050][5050];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    vector<T3> v;
    rep(i, N){
        int d, c;
        LL s;
        scanf("%d %d %d", &d, &c, &s);
        v.emplace_back(d, c, s);
    }
    
    // 2. sort.
    sort(all(v));
    
    // 3. dp更新.
    repx(i, 1, N + 1){
        int d = get<0>(v[i - 1]);
        int c = get<1>(v[i - 1]);
        LL s = get<2>(v[i - 1]);
        repx(j, 1, 5050){
            dp[i][j] = dp[i - 1][j];
            if(j >= c && j <= d) dp[i][j] = max(dp[i][j], dp[i - 1][j - c] + s);
        }
    }
    
    // 4. 集計.
    LL ans = 0;
    rep(i, 5050) ans = max(ans, dp[N][i]);
    
    // 5. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://github.com/E869120/kyopro_educational_90/blob/main/editorial/011-02.jpg

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using T3 = tuple<int, int, 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 all(x) x.begin(), x.end()

LL dp[5050][5050];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

vector<T3> v;

rep(i, N){

int d, c;

LL s;

scanf("%d %d %d", &d, &c, &s);

v.emplace_back(d, c, s);

}

// 2. sort.

sort(all(v));

// 3. dp更新.

repx(i, 1, N + 1){

int d = get<0>(v[i - 1]);

int c = get<1>(v[i - 1]);

LL s = get<2>(v[i - 1]);

repx(j, 1, 5050){

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

if(j >= c && j <= d) dp[i][j] = max(dp[i][j], dp[i - 1][j - c] + s);

}

// 4. 集計.

LL ans = 0;

rep(i, 5050) ans = max(ans, dp[N][i]);

// 5. 出力.

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

return 0;

}

[入力例]
1
12 3 69853

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

[入力例]
3
7 3 200000
3 2 100000
5 3 150000

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

[入力例]
8
376 640 602876667
4015 1868 533609371
3330 152 408704870
1874 798 30417810
2 1450 40706045
3344 1840 801881841
2853 1229 5235900
458 1277 997429858

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

[入力例]
20
376 640 602876667
4015 868 533609371
3330 152 408704870
1874 798 30417810
2 450 40706045
3344 840 801881841
2853 229 5235900
458 277 997429858
1689 948 981897272
4774 393 997361572
4237 750 294800444
4663 293 277667068
2249 808 444906878
3341 137 845317003
3625 765 739689211
911 510 326127348
1343 193 235655766
842 323 406413067
1425 303 68833418
212 808 745744264

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

[入力例]
30
376 140 602876667
4015 368 533609371
3330 152 408704870
1874 298 30417810
2 450 40706045
3344 340 801881841
2853 229 5235900
458 277 997429858
1689 448 981897272
4774 393 997361572
4237 250 294800444
4663 293 277667068
2249 308 444906878
3341 137 845317003
3625 265 739689211
911 10 326127348
1343 193 235655766
842 323 406413067
1425 303 68833418
212 308 745744264
3563 376 196296968
4186 323 275217640
332 361 337078801
4466 245 694789156
3763 250 432518459
2937 124 581390864
2255 227 642944345
2851 480 688009163
1957 295 5532462
3277 445 15791361

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

[入力例]
5
16 5 14
9 5 8
3 3 3
7 6 12
12 8 13

[出力例]
30

※ 実際, 以下のスケジュールで, 報酬 30円 になる.
1  ～  3日目 =  3
4  ～ 11日目 = 13
12 ～ 16日目 = 14

[入力例]
10
25 16 58
7 3 73
10 6 80
19 8 67
13 10 19
30 13 105
17 9 90
24 20 88
17 15 120
23 12 111

[出力例]
325

※ 実際, 以下のスケジュールで, 報酬 325円 になる.
1  ～  3日目 =  73
4  ～  9日目 =  80
10 ～ 17日目 =  67
18 ～ 30日目 = 105

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

[入力例]

12 3 69853

[出力例]

69853

※AtCoderテストケースより

[入力例]

7 3 200000

3 2 100000

5 3 150000

[出力例]

350000

※AtCoderテストケースより

[入力例]

376 640 602876667

4015 1868 533609371

3330 152 408704870

1874 798 30417810

2 1450 40706045

3344 1840 801881841

2853 1229 5235900

458 1277 997429858

[出力例]

1744196082

※AtCoderテストケースより

[入力例]

376 640 602876667

4015 868 533609371

3330 152 408704870

1874 798 30417810

2 450 40706045

3344 840 801881841

2853 229 5235900

458 277 997429858

1689 948 981897272

4774 393 997361572

4237 750 294800444

4663 293 277667068

2249 808 444906878

3341 137 845317003

3625 765 739689211

911 510 326127348

1343 193 235655766

842 323 406413067

1425 303 68833418

212 808 745744264

[出力例]

6583558066

※AtCoderテストケースより

[入力例]

376 140 602876667

4015 368 533609371

3330 152 408704870

1874 298 30417810

2 450 40706045

3344 340 801881841

2853 229 5235900

458 277 997429858

1689 448 981897272

4774 393 997361572

4237 250 294800444

4663 293 277667068

2249 308 444906878

3341 137 845317003

3625 265 739689211

911 10 326127348

1343 193 235655766

842 323 406413067

1425 303 68833418

212 308 745744264

3563 376 196296968

4186 323 275217640

332 361 337078801

4466 245 694789156

3763 250 432518459

2937 124 581390864

2255 227 642944345

2851 480 688009163

1957 295 5532462

3277 445 15791361

[出力例]

11420667389

※AtCoderテストケースより

[入力例]

16 5 14

9 5 8

3 3 3

7 6 12

12 8 13

[出力例]

※ 実際, 以下のスケジュールで, 報酬 30円になる.

1 ～ 3日目 = 3

4 ～ 11日目 = 13

12 ～ 16日目 = 14

[入力例]

25 16 58

7 3 73

10 6 80

19 8 67

13 10 19

30 13 105

17 9 90

24 20 88

17 15 120

23 12 111

[出力例]

325

※ 実際, 以下のスケジュールで, 報酬 325円になる.

1 ～ 3日目 = 73

4 ～ 9日目 = 80

10 ～ 17日目 = 67

18 ～ 30日目 = 105

■参照サイト
011 – Gravy Jobs
問題011 (Gravy Jobs) 解説

2021年8月2日2021年8月2日

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

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

■感想.
1. 問題F は, 方針が見えなかったので, 解説を参考にして, ようやく, AC版に到達出来た.
2. 実装に苦労したものの, 個人的には, 非常に面白いと感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/arc110/editorial/384
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
#define all(x) x.begin(), x.end()

int main(){

    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    vi p, q(N);
    rep(i, N){
        int n;
        scanf("%d", &n);
        p.pb(n);  // 値を保存.
        q[n] = i; // 出現位置.
    }
    
    // 2. 並び替えを行う.
    vi z(N), ans;
    iota(all(z), 0);
    bool ok = false;
    int debug = 0;
    while(!ok && debug < 200000){
        // 2-1. P の 昇順チェック.
        if(z == p) ok = true;
        
        // 2-2. 終了チェック.
        if(ok) break;
        
        // 2-3. P内 の 1, ..., k を 取得(※ N でなくて, N - 1 が 正しい, testcase_20.txt で, WA となった理由).
        vi np;
        rep(i, N - 1){
            // 1 ～ k を 設定.
            int cur = i + 1;
            
            // 1 ～ k の 出現位置.
            int curPos = (i + q[1]) % N;
            
            // 1 ～ k の 出現位置が, もともとの場所と一致したら, 保存.
            if(curPos == q[cur]) np.pb(cur);
            else                 break;
        }
        
        // 2-4. 並び替え.
        for(auto &n : np){
            // 移動元情報.
            int op = n;     // 値.
            int oq = q[op]; // 出現位置.
            
            // 宣言 を 保存.
            ans.pb(oq);
            
            // 移動先情報.
            int tq = (oq + p[oq]) % N; // 出現位置.
            int tp = p[tq];            // 値.
            
            // 交換処理.
            swap(p[oq], p[tq]); // 値.
            swap(q[op], q[tp]); // 出現位置.
        }
        
        // printf("np.size()=%d\n", np.size());
        // puts("----- p start -----");
        // for(auto &n : p) printf("%d ", n);
        // puts("\n----- p end -------");
        // puts("----- q start -----");
        // for(auto &n : q) printf("%d ", n);
        // puts("\n----- q end -------");
        
        // 2-5. 無限ループ回避.
        ++debug;
    }
    
    // 3. 出力.
    printf("%d\n", ans.size());
    for(auto &n : ans) printf("%d\n", n);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc110/editorial/384

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

#define repex(i, a, b, c) for(int i = a; i < b; i += c)

#define repx(i, a, b) repex(i, a, b, 1)

#define rep(i, n) repx(i, 0, n)

#define repr(i, a, b) for(int i = a; i >= b; i--)

#define pb push_back

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

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

vi p, q(N);

rep(i, N){

int n;

scanf("%d", &n);

p.pb(n); // 値を保存.

q[n] = i; // 出現位置.

}

// 2. 並び替えを行う.

vi z(N), ans;

iota(all(z), 0);

bool ok = false;

int debug = 0;

while(!ok && debug < 200000){

// 2-1. P の昇順チェック.

if(z == p) ok = true;

// 2-2. 終了チェック.

if(ok) break;

// 2-3. P内の 1, ..., k を取得(※ N でなくて, N - 1 が正しい, testcase_20.txt で, WA となった理由).

vi np;

rep(i, N - 1){

// 1 ～ k を設定.

int cur = i + 1;

// 1 ～ k の出現位置.

int curPos = (i + q[1]) % N;

// 1 ～ k の出現位置が, もともとの場所と一致したら, 保存.

if(curPos == q[cur]) np.pb(cur);

else break;

}

// 2-4. 並び替え.

for(auto &n : np){

// 移動元情報.

int op = n; // 値.

int oq = q[op]; // 出現位置.

// 宣言を保存.

ans.pb(oq);

// 移動先情報.

int tq = (oq + p[oq]) % N; // 出現位置.

int tp = p[tq]; // 値.

// 交換処理.

swap(p[oq], p[tq]); // 値.

swap(q[op], q[tp]); // 出現位置.

}

// printf("np.size()=%d\n", np.size());

// puts("----- p start -----");

// for(auto &n : p) printf("%d ", n);

// puts("\n----- p end -------");

// puts("----- q start -----");

// for(auto &n : q) printf("%d ", n);

// puts("\n----- q end -------");

// 2-5. 無限ループ回避.

++debug;

}

// 3. 出力.

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

for(auto &n : ans) printf("%d\n", n);

return 0;

}

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

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

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

[入力例]
3
0 1 2

[出力例]
0

[入力例]
3
2 1 0

[出力例]
5
1
2
2
0
0

[入力例]
5
3 4 1 0 2

[出力例]
13
2
3
3
3
3
4
4
4
4
0
0
0
0

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

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

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

[出力例]
116
1
2
3
4
4
5
5
6
6
7
7
8
8
8
8
8
9
9
9
9
9
9
0
0
0
0
0
0
0
1
1
1
1
1
1
1
2
2
2
2
2
2
2
2
3
3
3
3
3
3
3
3
3
4
4
4
4
4
4
4
4
4
5
5
5
5
5
5
5
5
5
6
6
6
6
6
6
6
6
6
7
7
7
7
7
7
7
7
7
8
8
8
8
8
8
8
8
8
9
9
9
9
9
9
9
9
9
0
0
0
0
0
0
0
0
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

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

[入力例]

7 1 2 6 4 0 5 3

[出力例]

※AtCoderのテストケースより

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

[入力例]

0 1 2

[出力例]

[入力例]

2 1 0

[出力例]

[入力例]

3 4 1 0 2

[出力例]

[入力例]

1 2 4 5 0 3

[出力例]

[入力例]

3 1 4 5 9 2 6 8 7 0

[出力例]

116

■参照サイト
鹿島建設プログラミングコンテスト2020（AtCoder Regular Contest 110）

2021年7月26日

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

C++の練習を兼ねて, AtCoder Beginner Contest 211 の問題C (chokudai) ～問題D (Number of Shortest paths) を解いてみた.

■感想.
1. 問題D は, 実装してみたもののAC版到達できなかったので, 解説を参考にして, ようやく, AC版に到達出来た.
2. 問題C は, 過去問 008 – AtCounter に似ていると感じた.
3. 幅優先探索(応用版, 経路数カウント)の復習が出来たので, 非常に良かったと思う.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 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 = 1e9 + 7;
LL dp[101010][9];

int main(){
    
    // 1. 入力情報.
    char c[101010];
    scanf("%s", c);
    string S(c);
    int l = S.size();
    
    // 2. dp更新.
    dp[0][0] = 1;
    rep(i, l){
        rep(j, 9){
            dp[i + 1][j] += dp[i][j];
            if(S[i] == 'c' && j == 0) dp[i + 1][j + 1] += dp[i][j];
            if(S[i] == 'h' && j == 1) dp[i + 1][j + 1] += dp[i][j];
            if(S[i] == 'o' && j == 2) dp[i + 1][j + 1] += dp[i][j];
            if(S[i] == 'k' && j == 3) dp[i + 1][j + 1] += dp[i][j];
            if(S[i] == 'u' && j == 4) dp[i + 1][j + 1] += dp[i][j];
            if(S[i] == 'd' && j == 5) dp[i + 1][j + 1] += dp[i][j];
            if(S[i] == 'a' && j == 6) dp[i + 1][j + 1] += dp[i][j];
            if(S[i] == 'i' && j == 7) dp[i + 1][j + 1] += dp[i][j];
        }
        rep(j, 9) dp[i + 1][j] %= MOD;
    }
    
    // 3. 出力.
    printf("%lld\n", dp[l][8]);
    return 0;
    
}

// 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 = 1e9 + 7;

LL dp[101010][9];

int main(){

// 1. 入力情報.

char c[101010];

scanf("%s", c);

string S(c);

int l = S.size();

// 2. dp更新.

dp[0][0] = 1;

rep(i, l){

rep(j, 9){

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

if(S[i] == 'c' && j == 0) dp[i + 1][j + 1] += dp[i][j];

if(S[i] == 'h' && j == 1) dp[i + 1][j + 1] += dp[i][j];

if(S[i] == 'o' && j == 2) dp[i + 1][j + 1] += dp[i][j];

if(S[i] == 'k' && j == 3) dp[i + 1][j + 1] += dp[i][j];

if(S[i] == 'u' && j == 4) dp[i + 1][j + 1] += dp[i][j];

if(S[i] == 'd' && j == 5) dp[i + 1][j + 1] += dp[i][j];

if(S[i] == 'a' && j == 6) dp[i + 1][j + 1] += dp[i][j];

if(S[i] == 'i' && j == 7) dp[i + 1][j + 1] += dp[i][j];

}

rep(j, 9) dp[i + 1][j] %= MOD;

}

// 3. 出力.

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

return 0;

}

[入力例]
chchokudai

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

[入力例]
atcoderrr

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

[入力例]
chokudaichokudaichokudai

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

[入力例]
uciaoyatofazncmepcaptpoewbuhwqifkrssjbdfgrqoboelqpkvnchcxuxvpmzgcbydwfzvgxwjliqfzxdcqzggssmoeimllvhexhmqddjqrwabrmwteklwkghmocgescxinyflxsgauoivrmhjsrutmxurdchrvrpilxyaoadodirwgshoifajbacqechyyjwrqobj

[出力例]
720

[入力例]
tqrsvhwwyftvwfuuaswulzjypjxdrvjcjqgjpkeowqqrelmsxohutlovxvvkfrvduzxryffnxrufdoruiilpzlqrblgydotbgtjuwuftdaknaadmvwnovabhtbcxyggjsjpjpnuoxgqgafpkjhxorlmcbedmcbdjvpbwdpygeuqzfdcosezhvlanunivnmhdyccxanlghtxaptrmpusjrcqrwoolysekniigqdidndhgqkmzvnmudbfignecqfputmskyotcsfufxdykdphmsuwajyjexnhmdgzypxpkdtrjqaaeguxmmwymaryqtadzbcjeassymyjqcgnpgreseanutdgytwwrjgreswzaeetoymribmwijiqxjgzugzyfgqcbrkceutzmixinerlhgkataypocxkbmxolewvvxfeyhehrzwzifqyuxbqnsvbpwndasarjbjdknefazrxvdcojfmzejesyrzthndnlryyhdoujtijq

[出力例]
227938

[入力例]

chchokudai

[出力例]

※AtCoderテストケースより

[入力例]

atcoderrr

[出力例]

※AtCoderテストケースより

[入力例]

chokudaichokudaichokudai

[出力例]

※AtCoderテストケースより

[入力例]

uciaoyatofazncmepcaptpoewbuhwqifkrssjbdfgrqoboelqpkvnchcxuxvpmzgcbydwfzvgxwjliqfzxdcqzggssmoeimllvhexhmqddjqrwabrmwteklwkghmocgescxinyflxsgauoivrmhjsrutmxurdchrvrpilxyaoadodirwgshoifajbacqechyyjwrqobj

[出力例]

720

[入力例]

tqrsvhwwyftvwfuuaswulzjypjxdrvjcjqgjpkeowqqrelmsxohutlovxvvkfrvduzxryffnxrufdoruiilpzlqrblgydotbgtjuwuftdaknaadmvwnovabhtbcxyggjsjpjpnuoxgqgafpkjhxorlmcbedmcbdjvpbwdpygeuqzfdcosezhvlanunivnmhdyccxanlghtxaptrmpusjrcqrwoolysekniigqdidndhgqkmzvnmudbfignecqfputmskyotcsfufxdykdphmsuwajyjexnhmdgzypxpkdtrjqaaeguxmmwymaryqtadzbcjeassymyjqcgnpgreseanutdgytwwrjgreswzaeetoymribmwijiqxjgzugzyfgqcbrkceutzmixinerlhgkataypocxkbmxolewvvxfeyhehrzwzifqyuxbqnsvbpwndasarjbjdknefazrxvdcojfmzejesyrzthndnlryyhdoujtijq

[出力例]

227938

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

// 解き直し.
// https://atcoder.jp/contests/abc211/editorial/2003.
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
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 MOD = 1e9 + 7;
LL ans[202020];

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    vvi G(N);
    rep(i, M){
        int a, b;
        scanf("%d %d", &a, &b);
        a--, b--;
        G[a].pb(b);
        G[b].pb(a);
    }
    
    // 2. 都市 1 を スタート地点として探索.
    // https://ja.wikipedia.org/wiki/幅優先探索
    auto bfs = [&](vvi &G, int s, int *d){
        // 2-1. 空のキュー.
        queue<int> q;
        
        // 2-2. 探索地点 s をキュー q に追加.
        q.push(s);
        while(!q.empty()){
            // 2-3. キューから取り出す.
            int u = q.front();
            q.pop();
            
            // 2-4. 取り出した要素を処理(※解説通り).
            for(auto &e : G[u]){
                // 到達済み.
                if(d[e]){
                    if(d[e] == d[u] + 1){
                        ans[e] += ans[u];
                        ans[e] %= MOD;
                    }
                }
                // 未到達.
                if(!d[e] && e != s){
                    d[e] = d[u] + 1;
                    q.push(e);
                    ans[e] = ans[u];
                }
            }
        }
    };
    int d[202020];
    rep(i, 202020) d[i] = 0;
    ans[0] = 1;
    bfs(G, 0, d);
    
    // 3. 移動できない場合.
    if(!d[N - 1]){
        puts("0");
        return 0;
    }
    
    // 4. 出力.
    printf("%lld\n", ans[N - 1]);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc211/editorial/2003.

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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 MOD = 1e9 + 7;

LL ans[202020];

int main(){

// 1. 入力情報.

int N, M;

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

vvi G(N);

rep(i, M){

int a, b;

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

a--, b--;

G[a].pb(b);

G[b].pb(a);

}

// 2. 都市 1 をスタート地点として探索.

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

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

// 2-1. 空のキュー.

queue<int> q;

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

q.push(s);

while(!q.empty()){

// 2-3. キューから取り出す.

int u = q.front();

q.pop();

// 2-4. 取り出した要素を処理(※解説通り).

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

// 到達済み.

if(d[e]){

if(d[e] == d[u] + 1){

ans[e] += ans[u];

ans[e] %= MOD;

}

// 未到達.

if(!d[e] && e != s){

d[e] = d[u] + 1;

q.push(e);

ans[e] = ans[u];

}

};

int d[202020];

rep(i, 202020) d[i] = 0;

ans[0] = 1;

bfs(G, 0, d);

// 3. 移動できない場合.

if(!d[N - 1]){

puts("0");

return 0;

}

// 4. 出力.

printf("%lld\n", ans[N - 1]);

return 0;

}

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

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

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

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

[入力例]
2 0

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

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

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

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

[出力例]
1

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

[出力例]
2

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

[出力例]
5

100

101

[入力例]

4 5

2 4

1 2

2 3

1 3

3 4

[出力例]

※AtCoderテストケースより

[入力例]

4 3

1 3

2 3

2 4

[出力例]

※AtCoderテストケースより

[入力例]

2 0

[出力例]

※AtCoderテストケースより

[入力例]

7 8

1 3

1 4

2 3

2 4

2 5

2 6

5 7

6 7

[出力例]

※AtCoderテストケースより

[入力例]

15 20

1 3

1 2

2 3

2 4

2 5

4 9

4 10

5 7

5 6

7 10

10 11

7 11

6 8

8 11

11 12

8 12

8 13

13 15

12 14

14 15

[出力例]

[入力例]

7 7

1 3

1 4

2 3

2 4

2 5

5 6

2 7

[出力例]

[入力例]

10 13

1 5

2 5

1 6

2 6

2 4

3 6

3 4

3 7

4 8

7 8

7 9

8 10

9 10

[出力例]

■参照サイト
AtCoder Beginner Contest 211

2021年7月24日2021年7月24日

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

C++の練習を兼ねて, AtCoder Regular Contest 123 の問題A (Deforestation) ～問題B (Increasing Triples) を解いてみた.

■感想.
1. 問題A, B は, 規則性を抽出できたので, AC版に到達出来たと思う.
2. 問題B で, 標準ライブラリ std::deque を使う練習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(){
    
    // 1. 入力情報.
    LL A, B, C;
    scanf("%lld %lld %lld", &A, &B, &C);
    
    // 2. 入れ替え.
    if(A > C) swap(A, C);
    
    // 3. 等差数列になるように調整.
    // ex.
    // 1 1000000000000000 2
    // -> 1999999999999997 が 正解のはず.
    LL ans = 202020202020202020, D = A + C;
    if(D & 1){
        if(C - B > B - A) ans = min(ans, (D + 1) / 2 - B + 1);
        // else              ans = min(ans, B + B - D - 1); // 02_rand_03.txt などの WA対応.
        else              ans = min(ans, B + B - D);
    }else{
        if(C - B > B - A) ans = min(ans, D / 2 - B);
        else              ans = min(ans, B + B - D);
    }
    
    // 4. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

int main(){

// 1. 入力情報.

LL A, B, C;

scanf("%lld %lld %lld", &A, &B, &C);

// 2. 入れ替え.

if(A > C) swap(A, C);

// 3. 等差数列になるように調整.

// ex.

// 1 1000000000000000 2

// -> 1999999999999997 が正解のはず.

LL ans = 202020202020202020, D = A + C;

if(D & 1){

if(C - B > B - A) ans = min(ans, (D + 1) / 2 - B + 1);

// else ans = min(ans, B + B - D - 1); // 02_rand_03.txt などの WA対応.

else ans = min(ans, B + B - D);

}else{

if(C - B > B - A) ans = min(ans, D / 2 - B);

else ans = min(ans, B + B - D);

}

// 4. 出力.

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

return 0;

}

[入力例]
4 8 10

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

[入力例]
10 3 4

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

[入力例]
1 2 3

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

[入力例]
1000000000000000 1 1000000000000000

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

[入力例]
1 1000000000000000 2

[出力例]
1999999999999997

[入力例]
31415 92653 58979

[出力例]
94912

[入力例]
14 14 21

[出力例]
5

[入力例]
173 20 50

[出力例]
93

[入力例]

4 8 10

[出力例]

※AtCoderのテストケースより

[入力例]

10 3 4

[出力例]

※AtCoderのテストケースより

[入力例]

1 2 3

[出力例]

※AtCoderのテストケースより

[入力例]

1000000000000000 1 1000000000000000

[出力例]

999999999999999

※AtCoderのテストケースより

[入力例]

1 1000000000000000 2

[出力例]

1999999999999997

[入力例]

31415 92653 58979

[出力例]

94912

[入力例]

14 14 21

[出力例]

[入力例]

173 20 50

[出力例]

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

// 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 pof pop_front
#define pob pop_back
#define pub push_back
#define puf push_front
int a[101010], b[101010], c[101010];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%d", &a[i]);
    rep(i, N) scanf("%d", &b[i]);
    rep(i, N) scanf("%d", &c[i]);
    
    // 2. sort.
    sort(a, a + N);
    sort(b, b + N);
    sort(c, c + N);
    
    // 3. dequeに保存.
    deque<int> dqA, dqB, dqC;
    rep(i, N) dqA.pub(a[i]);
    rep(i, N) dqB.pub(b[i]);
    rep(i, N) dqC.pub(c[i]);
    
    // 4. a[i] < b[i] < c[i] を カウント.
    int ans = 0;
    while(!dqA.empty()){
        // 4-1. 初期化.
        int sa = 0, sb = 0, sc = 0;
        
        // 4-2. 整数列 A から取得.
        sa = dqA.front();
        dqA.pof();
        
        // 4-3. 整数列 B から 取得.
        while(!dqB.empty()){
            sb = dqB.front();
            dqB.pof();
            if(sb > sa) break;
        }
        
        // 4-4. 整数列 C から取得.
        while(!dqC.empty()){
            sc = dqC.front();
            dqC.pof();
            if(sc > sb) break;
        }
        
        // 4-5. チェック.
        if(sa < sb && sb < sc) ans++;
        
        // 4-6. 継続するか？
        if(dqB.empty() || dqC.empty()) break;
    }
    
    // 5. 出力.
    printf("%d\n", ans);
    return 0;
    
}

// 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 pof pop_front

#define pob pop_back

#define pub push_back

#define puf push_front

int a[101010], b[101010], c[101010];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

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

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

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

// 2. sort.

sort(a, a + N);

sort(b, b + N);

sort(c, c + N);

// 3. dequeに保存.

deque<int> dqA, dqB, dqC;

rep(i, N) dqA.pub(a[i]);

rep(i, N) dqB.pub(b[i]);

rep(i, N) dqC.pub(c[i]);

// 4. a[i] < b[i] < c[i] をカウント.

int ans = 0;

while(!dqA.empty()){

// 4-1. 初期化.

int sa = 0, sb = 0, sc = 0;

// 4-2. 整数列 A から取得.

sa = dqA.front();

dqA.pof();

// 4-3. 整数列 B から取得.

while(!dqB.empty()){

sb = dqB.front();

dqB.pof();

if(sb > sa) break;

}

// 4-4. 整数列 C から取得.

while(!dqC.empty()){

sc = dqC.front();

dqC.pof();

if(sc > sb) break;

}

// 4-5. チェック.

if(sa < sb && sb < sc) ans++;

// 4-6. 継続するか？

if(dqB.empty() || dqC.empty()) break;

}

// 5. 出力.

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

return 0;

}

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

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

[入力例]
1
10
20
30

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

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

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

[入力例]
10
85 106 100 9 110 34 57 114 11 110
86 16 39 5 64 43 122 106 29 67
38 68 98 110 88 37 111 5 60 112

[出力例]
6

[入力例]
20
82 71 54 91 7 98 26 35 35 13 50 1 70 108 37 69 94 95 12 68
22 89 68 76 3 16 11 100 86 73 123 101 59 123 97 1 39 59 61 109
51 28 48 45 26 119 98 68 20 84 11 74 59 95 65 74 69 117 47 49

[出力例]
15

[入力例]
100
9 14 21 39 50 35 20 42 27 50 17 20 8 9 19 48 46 38 38 47 39 19 14 19 5 34 5 27 39 6 35 47 30 2 30 2 31 43 16 36 18 40 20 22 7 13 5 22 20 16 8 44 38 16 10 2 8 27 49 5 42 4 40 25 31 41 38 5 25 35 29 9 31 48 16 29 29 25 22 36 11 45 30 34 38 28 2 47 13 1 49 3 34 7 22 15 16 18 49 26
38 31 48 7 32 46 15 46 40 6 24 19 39 39 38 46 3 29 45 11 25 20 35 36 30 3 19 41 44 17 26 43 36 10 16 19 22 10 13 9 30 50 20 41 6 41 10 43 41 20 6 18 1 18 4 17 45 16 36 48 50 50 24 36 22 18 11 9 14 34 18 2 38 20 1 17 13 8 10 4 31 47 36 32 16 7 40 22 49 38 32 15 35 8 12 46 37 6 35 27
23 20 31 5 28 2 19 22 22 41 44 19 34 38 3 8 9 13 7 21 17 33 27 26 3 11 21 39 34 31 8 12 41 12 4 3 23 37 43 30 5 43 9 37 43 50 5 42 33 8 19 12 29 12 46 39 5 35 23 49 45 10 39 3 40 32 9 3 31 33 6 44 31 10 9 28 39 17 18 19 24 22 23 16 13 2 7 2 17 26 47 15 30 37 9 26 23 23 23 28

[出力例]
78

[入力例]

9 6 14 1 8

2 10 3 12 11

15 13 5 7 4

[出力例]

※AtCoderのテストケースより

[入力例]

[出力例]

※AtCoderのテストケースより

[入力例]

1 1 1

1 1 2

2 2 2

[出力例]

※AtCoderのテストケースより

[入力例]

85 106 100 9 110 34 57 114 11 110

86 16 39 5 64 43 122 106 29 67

38 68 98 110 88 37 111 5 60 112

[出力例]

[入力例]

82 71 54 91 7 98 26 35 35 13 50 1 70 108 37 69 94 95 12 68

22 89 68 76 3 16 11 100 86 73 123 101 59 123 97 1 39 59 61 109

51 28 48 45 26 119 98 68 20 84 11 74 59 95 65 74 69 117 47 49

[出力例]

[入力例]

100

9 14 21 39 50 35 20 42 27 50 17 20 8 9 19 48 46 38 38 47 39 19 14 19 5 34 5 27 39 6 35 47 30 2 30 2 31 43 16 36 18 40 20 22 7 13 5 22 20 16 8 44 38 16 10 2 8 27 49 5 42 4 40 25 31 41 38 5 25 35 29 9 31 48 16 29 29 25 22 36 11 45 30 34 38 28 2 47 13 1 49 3 34 7 22 15 16 18 49 26

38 31 48 7 32 46 15 46 40 6 24 19 39 39 38 46 3 29 45 11 25 20 35 36 30 3 19 41 44 17 26 43 36 10 16 19 22 10 13 9 30 50 20 41 6 41 10 43 41 20 6 18 1 18 4 17 45 16 36 48 50 50 24 36 22 18 11 9 14 34 18 2 38 20 1 17 13 8 10 4 31 47 36 32 16 7 40 22 49 38 32 15 35 8 12 46 37 6 35 27

23 20 31 5 28 2 19 22 22 41 44 19 34 38 3 8 9 13 7 21 17 33 27 26 3 11 21 39 34 31 8 12 41 12 4 3 23 37 43 30 5 43 9 37 43 50 5 42 33 8 19 12 29 12 46 39 5 35 23 49 45 10 39 3 40 32 9 3 31 33 6 44 31 10 9 28 39 17 18 19 24 22 23 16 13 2 7 2 17 26 47 15 30 37 9 26 23 23 23 28

[出力例]

■参照サイト
AtCoder Regular Contest 123

2021年7月21日

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

C++の練習を兼ねて, AtCoder Beginner Contest 209 の問題F (Deforestation) を解いてみた.

■感想.
1. 問題Fは, 方針が見えなかったので, 解説を参考にして, ようやく, AC版に到達出来た.
2. 苦手な動的計画法の訓練を積めたので, 非常に良かったと思う.
3. 個人的には, 計算量を削減するために, 累積和を求めながら, dpを更新していく処理が, 面白いと感じた.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/abc209/editorial/2233
// 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 = 1e9 + 7;
LL h[4040], dp[4040][4040], dpCum[4040][4040];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%lld", &h[i]);
    
    // 2. 木を伐採する順番の総数を計算(N の 3乗版).
    // dp[0][0] = 1;
    // rep(i, N - 1){
    //     // 2-1. dp更新.
    //     rep(j, N){
    //         // h[i] = h[i + 1] の 場合.
    //         if(h[i] == h[i + 1]) rep(k, i + 1) dp[i + 1][j] += dp[i][k], dp[i + 1][j] %= MOD;
    //         
    //         // h[i] < h[i + 1] の 場合.
    //         if(h[i] < h[i + 1]) repx(k, j, i + 1) dp[i + 1][j] += dp[i][k], dp[i + 1][j] %= MOD;
    //         
    //         // h[i] > h[i + 1] の 場合.
    //         if(h[i] > h[i + 1]) rep(k, j) dp[i + 1][j] += dp[i][k], dp[i + 1][j] %= MOD;
    //     }
    // }
    
    // 3. 木を伐採する順番の総数を計算(N の 2乗版).
    dp[0][0] = 1;
    rep(i, N - 1){
        // 3-1. dp累積和.
        rep(j, N){
            dpCum[i][j + 1] = dpCum[i][j] + dp[i][j];
            dpCum[i][j + 1] %= MOD;
        }
        
        // 3-2. dp更新.
        rep(j, N){
            // h[i] = h[i + 1] の 場合.
            if(h[i] == h[i + 1]){
                dp[i + 1][j] += dpCum[i][i + 1];
                dp[i + 1][j] %= MOD;
            }
            
            // h[i] < h[i + 1] の 場合.
            if(h[i] < h[i + 1]){
                dp[i + 1][j] += dpCum[i][i + 1];
                dp[i + 1][j] += MOD;
                dp[i + 1][j] -= dpCum[i][j];
                dp[i + 1][j] %= MOD;
            }
            
            // h[i] > h[i + 1] の 場合.
            if(h[i] > h[i + 1]){
                dp[i + 1][j] += dpCum[i][j];
                dp[i + 1][j] %= MOD;
            }
        }
    }
    
    // 4. 集計.
    LL ans = 0;
    rep(i, N){
        ans += dp[N - 1][i];
        ans %= MOD;
    }
    
    // 5. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc209/editorial/2233

// 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 = 1e9 + 7;

LL h[4040], dp[4040][4040], dpCum[4040][4040];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

rep(i, N) scanf("%lld", &h[i]);

// 2. 木を伐採する順番の総数を計算(N の 3乗版).

// dp[0][0] = 1;

// rep(i, N - 1){

// // 2-1. dp更新.

// rep(j, N){

// // h[i] = h[i + 1] の場合.

// if(h[i] == h[i + 1]) rep(k, i + 1) dp[i + 1][j] += dp[i][k], dp[i + 1][j] %= MOD;

// // h[i] < h[i + 1] の場合.

// if(h[i] < h[i + 1]) repx(k, j, i + 1) dp[i + 1][j] += dp[i][k], dp[i + 1][j] %= MOD;

// // h[i] > h[i + 1] の場合.

// if(h[i] > h[i + 1]) rep(k, j) dp[i + 1][j] += dp[i][k], dp[i + 1][j] %= MOD;

// }

// 3. 木を伐採する順番の総数を計算(N の 2乗版).

dp[0][0] = 1;

rep(i, N - 1){

// 3-1. dp累積和.

rep(j, N){

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

dpCum[i][j + 1] %= MOD;

}

// 3-2. dp更新.

rep(j, N){

// h[i] = h[i + 1] の場合.

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

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

dp[i + 1][j] %= MOD;

}

// h[i] < h[i + 1] の場合.

if(h[i] < h[i + 1]){

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

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

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

dp[i + 1][j] %= MOD;

}

// h[i] > h[i + 1] の場合.

if(h[i] > h[i + 1]){

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

dp[i + 1][j] %= MOD;

}

// 4. 集計.

LL ans = 0;

rep(i, N){

ans += dp[N - 1][i];

ans %= MOD;

}

// 5. 出力.

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

return 0;

}

[入力例]
3
4 2 4

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

[入力例]
3
100 100 100

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

[入力例]
15
804289384 846930887 681692778 714636916 957747794 424238336 719885387 649760493 596516650 189641422 25202363 350490028 783368691 102520060 44897764

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

[入力例]
1
10

[出力例]
1

[入力例]
5
3 1 4 1 5

[出力例]
16

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

[出力例]
72359

[入力例]
20
60 70 117 54 33 74 89 64 102 52 43 27 13 53 101 37 34 17 26 70

[出力例]
364927511

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

[出力例]
840511117

[入力例]

4 2 4

[出力例]

※AtCoderテストケースより

[入力例]

100 100 100

[出力例]

※AtCoderテストケースより

[入力例]

804289384 846930887 681692778 714636916 957747794 424238336 719885387 649760493 596516650 189641422 25202363 350490028 783368691 102520060 44897764

[出力例]

54537651

※AtCoderテストケースより

[入力例]

[出力例]

[入力例]

3 1 4 1 5

[出力例]

[入力例]

1 4 1 4 2 1 3 5 6 2 3

[出力例]

72359

[入力例]

60 70 117 54 33 74 89 64 102 52 43 27 13 53 101 37 34 17 26 70

[出力例]

364927511

[入力例]

100

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

[出力例]

840511117

■参照サイト
AtCoder Beginner Contest 209

2021年7月16日2021年7月16日

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

C++の練習を兼ねて, 競プロ典型 90 問の問題009 (Three Point Angle) を解いてみた.

■感想.
1. 問題009は, 何となく過去問の解説 (D – 三角形の分類) の方針が利用できるように見えたので, AC版に到達出来たと思う.
2. 尺取り法の復習ができたので非常に良かったと思う.
3. 手強い問題が非常に多い気もするけど, 時間を見つけて, 引き続き, 取り組んでいきたいと思う.

詳細は, 本家のサイト(GitHub) 競プロ典型 90 問の問題009 をご覧下さい.

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

// 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 pb push_back
#define all(x) x.begin(), x.end()
const double PI = acos(-1);
int x[2020], y[2020];

struct rotation{
    int x, y;
    double a;
    bool operator < (const rotation& rhs) const{
        return a < rhs.a;
    }
};

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N){
        int a, b;
        scanf("%d %d", &a, &b);
        x[i] = a;
        y[i] = b;
    }
    
    // 2. ベクトルの角度を計算.
    double ans = 0.0;
    rep(i, N){
        // 2-1. 点P[j] を 固定.
        vector<int> bx, by;
        rep(j, N){
            if(j == i) continue;
            bx.pb(x[j] - x[i]);
            by.pb(y[j] - y[i]);
        }
        
        // 2-2. 角度(1周分) を 保存.
        vector<rotation> angle;
        rep(j, bx.size()){
            // atan2 は, [-PI, PI] で 返却されることに注意.
            double a = atan2(by[j], bx[j]);
            if(a < 0.0) a += PI * 2.0;
            rotation r;
            r.x = bx[j];
            r.y = by[j];
            r.a = a;
            angle.pb(r);
        }
        
        // 2-3. 角度 を sort.
        sort(all(angle));
        
        // 2-4. 角度(2周分) に 水増し.
        int n = angle.size();
        rep(j, n){
            rotation r;
            r.x = angle[j].x;
            r.y = angle[j].y;
            r.a = angle[j].a + PI * 2.0;
            angle.pb(r);
        }
        // for(auto &p : angle) printf("%d %d %lf\n", p.x, p.y, p.a);
        
        // 2-5. 角度の最大値は？
        int l = 0, r = 1;
        double cur = 0.0;
        while(l < n){
            double diff = 0.0;
            while(r < l + n){
                // 角度を取得.
                diff = angle[r].a - angle[l].a;
                
                // 180度を超えた場合は, 一つ前の r を使って, 探索終了.
                if(diff > PI){
                    r--;
                    diff = angle[r].a - angle[l].a;
                    break;
                }
                
                // 180度の場合は, 探索終了.
                if(diff == PI) break;
                
                // r を increment.
                r++;
            }
            
            // l を increment.
            l++;
            
            // 最大値更新.
            cur = max(cur, diff);
        }
        
        // 2-6. 最大値更新.
        ans = max(ans, cur);
    }
    
    // 3. 出力.
    printf("%.12lf\n", ans / PI * 180.0);
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

// 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 pb push_back

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

const double PI = acos(-1);

int x[2020], y[2020];

struct rotation{

int x, y;

double a;

bool operator < (const rotation& rhs) const{

return a < rhs.a;

}

};

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

rep(i, N){

int a, b;

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

x[i] = a;

y[i] = b;

}

// 2. ベクトルの角度を計算.

double ans = 0.0;

rep(i, N){

// 2-1. 点P[j] を固定.

vector<int> bx, by;

rep(j, N){

if(j == i) continue;

bx.pb(x[j] - x[i]);

by.pb(y[j] - y[i]);

}

// 2-2. 角度(1周分) を保存.

vector<rotation> angle;

rep(j, bx.size()){

// atan2 は, [-PI, PI] で返却されることに注意.

double a = atan2(by[j], bx[j]);

if(a < 0.0) a += PI * 2.0;

rotation r;

r.x = bx[j];

r.y = by[j];

r.a = a;

angle.pb(r);

}

// 2-3. 角度を sort.

sort(all(angle));

// 2-4. 角度(2周分) に水増し.

int n = angle.size();

rep(j, n){

rotation r;

r.x = angle[j].x;

r.y = angle[j].y;

r.a = angle[j].a + PI * 2.0;

angle.pb(r);

}

// for(auto &p : angle) printf("%d %d %lf\n", p.x, p.y, p.a);

// 2-5. 角度の最大値は？

int l = 0, r = 1;

double cur = 0.0;

while(l < n){

double diff = 0.0;

while(r < l + n){

// 角度を取得.

diff = angle[r].a - angle[l].a;

// 180度を超えた場合は, 一つ前の r を使って, 探索終了.

if(diff > PI){

r--;

diff = angle[r].a - angle[l].a;

break;

}

// 180度の場合は, 探索終了.

if(diff == PI) break;

// r を increment.

r++;

}

// l を increment.

l++;

// 最大値更新.

cur = max(cur, diff);

}

// 2-6. 最大値更新.

ans = max(ans, cur);

}

// 3. 出力.

printf("%.12lf\n", ans / PI * 180.0);

return 0;

}

[入力例]
3
0 0
0 10
10 10

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

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

[入力例]
5
8 6
9 1
2 0
1 0
0 1

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

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

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

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

[入力例]
40
298750376 229032640
602876667 944779015
909539868 533609371
231368330 445484152
408704870 850216874
349286798 30417810
807260002 554049450
40706045 380488344
749325840 801881841
459457853 66691229
5235900 8100458
46697277 997429858
827651689 790051948
981897272 271364774
536232393 997361572
449659237 602191750
294800444 346669663
792837293 277667068
997282249 468293808
444906878 702693341
894286137 845317003
27053625 926547765
739689211 447395911
902031510 326127348
582956343 842918193
235655766 844300842
438389323 406413067
862896425 464876303
68833418 76340212
911399808 745744264
551223563 854507876
196296968 52144186
431165823 275217640
424495332 847375861
337078801 83054466
648322745 694789156
301518763 319851750
432518459 772897937
630628124 581390864
313132255 350770227

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

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

[入力例]
10
24 9
77 72
0 4
13 73
51 105
100 104
72 23
0 26
62 16
120 49

[出力例]
178.669186419098

[入力例]
20
1635 10426
7389 8009
10003 10431
7740 1110
5013 6171
4086 8267
209 1918
304 10739
3845 270
2296 260
11754 4025
3574 11342
11595 3431
4631 2738
4790 5436
1230 68
9420 9848
3010 9007
5451 6745
9511 10460

[出力例]
179.896865785287

[入力例]
30
7158389 10413815
6070867 151525
4958107 5169148
4360871 9883042
8892018 2127037
3220360 7466394
6867253 7301852
11921852 4646440
5647521 11730630
4478503 2578017
3427913 11428302
7441405 2060342
4200045 555865
3115916 12322024
3952701 490350
4650035 632956
9619727 2197121
10424915 6817438
7780200 8796458
5659878 10310152
8771320 7675027
11080686 12322081
315038 4030589
736617 8845875
848867 10840290
7079095 7947504
3373068 6395890
5469078 5321751
8258439 9651831
8611025 4864387

[出力例]
179.976838213525

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

[入力例]

0 0

0 10

10 10

[出力例]

※AtCoderテストケースより

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

90.000000000000

[入力例]

8 6

9 1

2 0

1 0

0 1

[出力例]

171.869897645844

※AtCoderテストケースより

[入力例]

0 0

1 7

2 6

2 8

3 5

5 5

6 7

7 1

7 9

8 8

[出力例]

180

※AtCoderテストケースより

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

180.000000000000

[入力例]

298750376 229032640

602876667 944779015

909539868 533609371

231368330 445484152

408704870 850216874

349286798 30417810

807260002 554049450

40706045 380488344

749325840 801881841

459457853 66691229

5235900 8100458

46697277 997429858

827651689 790051948

981897272 271364774

536232393 997361572

449659237 602191750

294800444 346669663

792837293 277667068

997282249 468293808

444906878 702693341

894286137 845317003

27053625 926547765

739689211 447395911

902031510 326127348

582956343 842918193

235655766 844300842

438389323 406413067

862896425 464876303

68833418 76340212

911399808 745744264

551223563 854507876

196296968 52144186

431165823 275217640

424495332 847375861

337078801 83054466

648322745 694789156

301518763 319851750

432518459 772897937

630628124 581390864

313132255 350770227

[出力例]

179.9834340684232

※AtCoderテストケースより

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

179.983434068423

[入力例]

24 9

77 72

0 4

13 73

51 105

100 104

72 23

0 26

62 16

120 49

[出力例]

178.669186419098

[入力例]

1635 10426

7389 8009

10003 10431

7740 1110

5013 6171

4086 8267

209 1918

304 10739

3845 270

2296 260

11754 4025

3574 11342

11595 3431

4631 2738

4790 5436

1230 68

9420 9848

3010 9007

5451 6745

9511 10460

[出力例]

179.896865785287

[入力例]

7158389 10413815

6070867 151525

4958107 5169148

4360871 9883042

8892018 2127037

3220360 7466394

6867253 7301852

11921852 4646440

5647521 11730630

4478503 2578017

3427913 11428302

7441405 2060342

4200045 555865

3115916 12322024

3952701 490350

4650035 632956

9619727 2197121

10424915 6817438

7780200 8796458

5659878 10310152

8771320 7675027

11080686 12322081

315038 4030589

736617 8845875

848867 10840290

7079095 7947504

3373068 6395890

5469078 5321751

8258439 9651831

8611025 4864387

[出力例]

179.976838213525

■参照サイト
009 – Three Point Angle
AtCoder Beginner Contest 033 (D – 三角形の分類)

2021年7月13日

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

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

■感想.
1. 問題Eは, 方針が見えなかったので, 解説を参考にして, ようやく, AC版に到達出来た.
2. 実装に非常に苦労したものの, 個人的には, 非常に面白い問題に感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/arc095/editorial.pdf
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vs = vector<string>;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
#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

int main(){
    
    // 1. 入力情報.
    int H, W;
    scanf("%d %d", &H, &W);
    vs board;
    rep(i, H){
        char c[22];
        scanf("%s", c);
        string s(c);
        board.pb(s);
    }
    
    // 2. H が 奇数の場合, 偶数化する.
    // -> 列をチェックする場合に, 最大行は, Skipさせる方針.
    bool odd = false;
    if(H & 1){
        odd = true;
        H++;
    }
    
    // 3. 行ペア作成.
    vvvi rp;
    vvi r;
    auto dfs = [&](auto&& self, int* m, vvi& bef) -> void{
        // 2-1. 訪問済フラグチェック.
        int f = 0;
        rep(i, H) if(m[i]) f++;
        
        // 2-2. 未訪問の行を探索.
        int row = 0;
        rep(i, H){
            if(!m[i]){
                row = i;
                break;
            }
        }
        
        // 2-3. 最終の場合(Hは偶数のはず).
        if(f == H - 2){
            repx(i, row + 1, H){
                if(!m[i]){
                    vvi cur = bef;
                    cur.pb({row, i});
                    rp.pb(cur);
                    return;
                }
            }
        }
        
        // 2-4. ペアを作成しつつ, 次処理へ.
        repx(i, row + 1, H){
            if(!m[i]){
                vvi cur = bef;
                cur.pb({row, i});
                int d[H];
                rep(i, H) d[i] = m[i];
                d[row] = 1;
                d[i]   = 1;
                self(self, d, cur);
            }
        }
    };
    int row[H];
    rep(i, H) row[i] = 0;
    dfs(dfs, row, r);
    // for(auto &p : rp){
    //     int x = p.size();
    //     rep(i, x){
    //         printf("%s", "{");
    //         int y = p[i].size();
    //         rep(j, y){
    //             printf("%d", p[i][j]);
    //             if(j < y - 1) printf("%s", ", ");
    //         }
    //         printf("%s", "}");
    //         if(i < x - 1) printf("%s", ", ");
    //     }
    //     puts("");
    // }
    // 
    // ex.
    // H = 2 の 場合.
    // -> 1通り.
    // {0, 1}
    // 
    // H = 3 の 場合(3 を 除外して考えることに注意).
    // H = 4 の 場合.
    // -> 3通り.
    // {0, 1}, {2, 3}
    // {0, 2}, {1, 3}
    // {0, 3}, {1, 2}
    // 
    // H = 5 の 場合(5 を 除外して考えることに注意).
    // H = 6 の 場合.
    // -> 15通り.
    // {0, 1}, {2, 3}, {4, 5}
    // {0, 1}, {2, 4}, {3, 5}
    // {0, 1}, {2, 5}, {3, 4}
    // {0, 2}, {1, 3}, {4, 5}
    // {0, 2}, {1, 4}, {3, 5}
    // {0, 2}, {1, 5}, {3, 4}
    // {0, 3}, {1, 2}, {4, 5}
    // {0, 3}, {1, 4}, {2, 5}
    // {0, 3}, {1, 5}, {2, 4}
    // {0, 4}, {1, 2}, {3, 5}
    // {0, 4}, {1, 3}, {2, 5}
    // {0, 4}, {1, 5}, {2, 3}
    // {0, 5}, {1, 2}, {3, 4}
    // {0, 5}, {1, 3}, {2, 4}
    // {0, 5}, {1, 4}, {2, 3}
    // 
    // H = 7 の 場合(7 を 除外して考えることに注意).
    // H = 8 の 場合.
    // -> 105通り.
    // {0, 1}, {2, 3}, {4, 5}, {6, 7}
    // {0, 1}, {2, 3}, {4, 6}, {5, 7}
    // {0, 1}, {2, 3}, {4, 7}, {5, 6}
    // {0, 1}, {2, 4}, {3, 5}, {6, 7}
    // {0, 1}, {2, 4}, {3, 6}, {5, 7}
    // {0, 1}, {2, 4}, {3, 7}, {5, 6}
    // {0, 1}, {2, 5}, {3, 4}, {6, 7}
    // {0, 1}, {2, 5}, {3, 6}, {4, 7}
    // {0, 1}, {2, 5}, {3, 7}, {4, 6}
    // {0, 1}, {2, 6}, {3, 4}, {5, 7}
    // {0, 1}, {2, 6}, {3, 5}, {4, 7}
    // {0, 1}, {2, 6}, {3, 7}, {4, 5}
    // {0, 1}, {2, 7}, {3, 4}, {5, 6}
    // {0, 1}, {2, 7}, {3, 5}, {4, 6}
    // {0, 1}, {2, 7}, {3, 6}, {4, 5}
    // {0, 2}, {1, 3}, {4, 5}, {6, 7}
    // {0, 2}, {1, 3}, {4, 6}, {5, 7}
    // {0, 2}, {1, 3}, {4, 7}, {5, 6}
    // {0, 2}, {1, 4}, {3, 5}, {6, 7}
    // {0, 2}, {1, 4}, {3, 6}, {5, 7}
    // {0, 2}, {1, 4}, {3, 7}, {5, 6}
    // {0, 2}, {1, 5}, {3, 4}, {6, 7}
    // {0, 2}, {1, 5}, {3, 6}, {4, 7}
    // {0, 2}, {1, 5}, {3, 7}, {4, 6}
    // {0, 2}, {1, 6}, {3, 4}, {5, 7}
    // {0, 2}, {1, 6}, {3, 5}, {4, 7}
    // {0, 2}, {1, 6}, {3, 7}, {4, 5}
    // {0, 2}, {1, 7}, {3, 4}, {5, 6}
    // {0, 2}, {1, 7}, {3, 5}, {4, 6}
    // {0, 2}, {1, 7}, {3, 6}, {4, 5}
    // {0, 3}, {1, 2}, {4, 5}, {6, 7}
    // {0, 3}, {1, 2}, {4, 6}, {5, 7}
    // {0, 3}, {1, 2}, {4, 7}, {5, 6}
    // {0, 3}, {1, 4}, {2, 5}, {6, 7}
    // {0, 3}, {1, 4}, {2, 6}, {5, 7}
    // {0, 3}, {1, 4}, {2, 7}, {5, 6}
    // {0, 3}, {1, 5}, {2, 4}, {6, 7}
    // {0, 3}, {1, 5}, {2, 6}, {4, 7}
    // {0, 3}, {1, 5}, {2, 7}, {4, 6}
    // {0, 3}, {1, 6}, {2, 4}, {5, 7}
    // {0, 3}, {1, 6}, {2, 5}, {4, 7}
    // {0, 3}, {1, 6}, {2, 7}, {4, 5}
    // {0, 3}, {1, 7}, {2, 4}, {5, 6}
    // {0, 3}, {1, 7}, {2, 5}, {4, 6}
    // {0, 3}, {1, 7}, {2, 6}, {4, 5}
    // {0, 4}, {1, 2}, {3, 5}, {6, 7}
    // {0, 4}, {1, 2}, {3, 6}, {5, 7}
    // {0, 4}, {1, 2}, {3, 7}, {5, 6}
    // {0, 4}, {1, 3}, {2, 5}, {6, 7}
    // {0, 4}, {1, 3}, {2, 6}, {5, 7}
    // {0, 4}, {1, 3}, {2, 7}, {5, 6}
    // {0, 4}, {1, 5}, {2, 3}, {6, 7}
    // {0, 4}, {1, 5}, {2, 6}, {3, 7}
    // {0, 4}, {1, 5}, {2, 7}, {3, 6}
    // {0, 4}, {1, 6}, {2, 3}, {5, 7}
    // {0, 4}, {1, 6}, {2, 5}, {3, 7}
    // {0, 4}, {1, 6}, {2, 7}, {3, 5}
    // {0, 4}, {1, 7}, {2, 3}, {5, 6}
    // {0, 4}, {1, 7}, {2, 5}, {3, 6}
    // {0, 4}, {1, 7}, {2, 6}, {3, 5}
    // {0, 5}, {1, 2}, {3, 4}, {6, 7}
    // {0, 5}, {1, 2}, {3, 6}, {4, 7}
    // {0, 5}, {1, 2}, {3, 7}, {4, 6}
    // {0, 5}, {1, 3}, {2, 4}, {6, 7}
    // {0, 5}, {1, 3}, {2, 6}, {4, 7}
    // {0, 5}, {1, 3}, {2, 7}, {4, 6}
    // {0, 5}, {1, 4}, {2, 3}, {6, 7}
    // {0, 5}, {1, 4}, {2, 6}, {3, 7}
    // {0, 5}, {1, 4}, {2, 7}, {3, 6}
    // {0, 5}, {1, 6}, {2, 3}, {4, 7}
    // {0, 5}, {1, 6}, {2, 4}, {3, 7}
    // {0, 5}, {1, 6}, {2, 7}, {3, 4}
    // {0, 5}, {1, 7}, {2, 3}, {4, 6}
    // {0, 5}, {1, 7}, {2, 4}, {3, 6}
    // {0, 5}, {1, 7}, {2, 6}, {3, 4}
    // {0, 6}, {1, 2}, {3, 4}, {5, 7}
    // {0, 6}, {1, 2}, {3, 5}, {4, 7}
    // {0, 6}, {1, 2}, {3, 7}, {4, 5}
    // {0, 6}, {1, 3}, {2, 4}, {5, 7}
    // {0, 6}, {1, 3}, {2, 5}, {4, 7}
    // {0, 6}, {1, 3}, {2, 7}, {4, 5}
    // {0, 6}, {1, 4}, {2, 3}, {5, 7}
    // {0, 6}, {1, 4}, {2, 5}, {3, 7}
    // {0, 6}, {1, 4}, {2, 7}, {3, 5}
    // {0, 6}, {1, 5}, {2, 3}, {4, 7}
    // {0, 6}, {1, 5}, {2, 4}, {3, 7}
    // {0, 6}, {1, 5}, {2, 7}, {3, 4}
    // {0, 6}, {1, 7}, {2, 3}, {4, 5}
    // {0, 6}, {1, 7}, {2, 4}, {3, 5}
    // {0, 6}, {1, 7}, {2, 5}, {3, 4}
    // {0, 7}, {1, 2}, {3, 4}, {5, 6}
    // {0, 7}, {1, 2}, {3, 5}, {4, 6}
    // {0, 7}, {1, 2}, {3, 6}, {4, 5}
    // {0, 7}, {1, 3}, {2, 4}, {5, 6}
    // {0, 7}, {1, 3}, {2, 5}, {4, 6}
    // {0, 7}, {1, 3}, {2, 6}, {4, 5}
    // {0, 7}, {1, 4}, {2, 3}, {5, 6}
    // {0, 7}, {1, 4}, {2, 5}, {3, 6}
    // {0, 7}, {1, 4}, {2, 6}, {3, 5}
    // {0, 7}, {1, 5}, {2, 3}, {4, 6}
    // {0, 7}, {1, 5}, {2, 4}, {3, 6}
    // {0, 7}, {1, 5}, {2, 6}, {3, 4}
    // {0, 7}, {1, 6}, {2, 3}, {4, 5}
    // {0, 7}, {1, 6}, {2, 4}, {3, 5}
    // {0, 7}, {1, 6}, {2, 5}, {3, 4}
    
    // 4. 各ペアごとに, 列をチェック.
    // -> もともと, H が 奇数だった場合は, 最終行 を 除外して考えることに注意.
    if(odd) H--;
    bool symmetric = false;
    for(auto &p : rp){
        // 4-1. ペアに対応するマス目を作成.
        char t[H][W];
        int idx = 0;
        rep(i, p.size()){
            int r1 = p[i][0];
            int r2 = p[i][1];
            if(r1 >= H){
                rep(k, W) t[H / 2][k] = board[r2][k];
                continue;
            }
            if(r2 >= H){
                rep(k, W) t[H / 2][k] = board[r1][k];
                continue;
            }
            rep(k, W){
                t[idx][k]         = board[r1][k];
                t[H - 1 - idx][k] = board[r2][k];
            }
            idx++;
        }
        
        // 4-2. 点対称となる列の組み合わせが存在するか？
        int column[W], deploy[W];
        rep(i, W) column[i] = deploy[i] = 0;
        idx = 0;
        rep(i, W){
            if(column[i]) continue;
            bool ok = false;
            repx(j, i + 1, W){
                if(column[j]) continue;
                ok = true;
                rep(k, H) if(t[k][i] != t[H - 1 - k][j]) ok = false;
                if(ok){
                    column[i]           = 1; // i列目 を 使用済み に 変更.
                    column[j]           = 1; // j列目 を 使用済み に 変更.
                    deploy[idx]         = 1; // 最も左側の列を, 配置済み に 変更.
                    deploy[W - 1 - idx] = 1; // 最も右側の列を, 配置済み に 変更.
                    idx++;
                    break;
                }
            }
            if(W & 1){
                if(!ok){
                    if(!deploy[W / 2]){
                        bool g = true;
                        rep(k, (H + 1) / 2) if(t[k][i] != t[H - 1 - k][i]) g = false;
                        if(g){
                            ok = true;
                            column[i]     = 1; // i列目 を 使用済み に 変更.
                            deploy[W / 2] = 1; // 中央の列を, 配置済み に 変更.
                        }
                    }
                }
            }
            if(!ok) break;
        }
        
        // 4-3. 存在した場合(※配置が正常に行われた場合).
        int used = 0;
        rep(i, W) if(deploy[i]) used++;
        if(used == W){
            symmetric = true;
            break;
        }
    }
    
    // 5. 出力.
    printf("%s\n", symmetric ? "YES" : "NO");
    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

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

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vs = vector<string>;

using vi = vector<int>;

using vvi = vector<vi>;

using vvvi = vector<vvi>;

#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

int main(){

// 1. 入力情報.

int H, W;

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

vs board;

rep(i, H){

char c[22];

scanf("%s", c);

string s(c);

board.pb(s);

}

// 2. H が奇数の場合, 偶数化する.

// -> 列をチェックする場合に, 最大行は, Skipさせる方針.

bool odd = false;

if(H & 1){

odd = true;

H++;

}

// 3. 行ペア作成.

vvvi rp;

vvi r;

auto dfs = [&](auto&& self, int* m, vvi& bef) -> void{

// 2-1. 訪問済フラグチェック.

int f = 0;

rep(i, H) if(m[i]) f++;

// 2-2. 未訪問の行を探索.

int row = 0;

rep(i, H){

if(!m[i]){

row = i;

break;

}

// 2-3. 最終の場合(Hは偶数のはず).

if(f == H - 2){

repx(i, row + 1, H){

if(!m[i]){

vvi cur = bef;

cur.pb({row, i});

rp.pb(cur);

return;

}

// 2-4. ペアを作成しつつ, 次処理へ.

repx(i, row + 1, H){

if(!m[i]){

vvi cur = bef;

cur.pb({row, i});

int d[H];

rep(i, H) d[i] = m[i];

d[row] = 1;

d[i] = 1;

self(self, d, cur);

}

};

int row[H];

rep(i, H) row[i] = 0;

dfs(dfs, row, r);

// for(auto &p : rp){

// int x = p.size();

// rep(i, x){

// printf("%s", "{");

// int y = p[i].size();

// rep(j, y){

// printf("%d", p[i][j]);

// if(j < y - 1) printf("%s", ", ");

// }

// printf("%s", "}");

// if(i < x - 1) printf("%s", ", ");

// }

// puts("");

// }

// ex.

// H = 2 の場合.

// -> 1通り.

// {0, 1}

// H = 3 の場合(3 を除外して考えることに注意).

// H = 4 の場合.

// -> 3通り.

// {0, 1}, {2, 3}

// {0, 2}, {1, 3}

// {0, 3}, {1, 2}

// H = 5 の場合(5 を除外して考えることに注意).

// H = 6 の場合.

// -> 15通り.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

// H = 7 の場合(7 を除外して考えることに注意).

// H = 8 の場合.

// -> 105通り.

// {0, 1}, {2, 3}, {4, 5}, {6, 7}

// {0, 1}, {2, 3}, {4, 6}, {5, 7}

// {0, 1}, {2, 3}, {4, 7}, {5, 6}

// {0, 1}, {2, 4}, {3, 5}, {6, 7}

// {0, 1}, {2, 4}, {3, 6}, {5, 7}

// {0, 1}, {2, 4}, {3, 7}, {5, 6}

// {0, 1}, {2, 5}, {3, 4}, {6, 7}

// {0, 1}, {2, 5}, {3, 6}, {4, 7}

// {0, 1}, {2, 5}, {3, 7}, {4, 6}

// {0, 1}, {2, 6}, {3, 4}, {5, 7}

// {0, 1}, {2, 6}, {3, 5}, {4, 7}

// {0, 1}, {2, 6}, {3, 7}, {4, 5}

// {0, 1}, {2, 7}, {3, 4}, {5, 6}

// {0, 1}, {2, 7}, {3, 5}, {4, 6}

// {0, 1}, {2, 7}, {3, 6}, {4, 5}

// {0, 2}, {1, 3}, {4, 5}, {6, 7}

// {0, 2}, {1, 3}, {4, 6}, {5, 7}

// {0, 2}, {1, 3}, {4, 7}, {5, 6}

// {0, 2}, {1, 4}, {3, 5}, {6, 7}

// {0, 2}, {1, 4}, {3, 6}, {5, 7}

// {0, 2}, {1, 4}, {3, 7}, {5, 6}

// {0, 2}, {1, 5}, {3, 4}, {6, 7}

// {0, 2}, {1, 5}, {3, 6}, {4, 7}

// {0, 2}, {1, 5}, {3, 7}, {4, 6}

// {0, 2}, {1, 6}, {3, 4}, {5, 7}

// {0, 2}, {1, 6}, {3, 5}, {4, 7}

// {0, 2}, {1, 6}, {3, 7}, {4, 5}

// {0, 2}, {1, 7}, {3, 4}, {5, 6}

// {0, 2}, {1, 7}, {3, 5}, {4, 6}

// {0, 2}, {1, 7}, {3, 6}, {4, 5}

// {0, 3}, {1, 2}, {4, 5}, {6, 7}

// {0, 3}, {1, 2}, {4, 6}, {5, 7}

// {0, 3}, {1, 2}, {4, 7}, {5, 6}

// {0, 3}, {1, 4}, {2, 5}, {6, 7}

// {0, 3}, {1, 4}, {2, 6}, {5, 7}

// {0, 3}, {1, 4}, {2, 7}, {5, 6}

// {0, 3}, {1, 5}, {2, 4}, {6, 7}

// {0, 3}, {1, 5}, {2, 6}, {4, 7}

// {0, 3}, {1, 5}, {2, 7}, {4, 6}

// {0, 3}, {1, 6}, {2, 4}, {5, 7}

// {0, 3}, {1, 6}, {2, 5}, {4, 7}

// {0, 3}, {1, 6}, {2, 7}, {4, 5}

// {0, 3}, {1, 7}, {2, 4}, {5, 6}

// {0, 3}, {1, 7}, {2, 5}, {4, 6}

// {0, 3}, {1, 7}, {2, 6}, {4, 5}

// {0, 4}, {1, 2}, {3, 5}, {6, 7}

// {0, 4}, {1, 2}, {3, 6}, {5, 7}

// {0, 4}, {1, 2}, {3, 7}, {5, 6}

// {0, 4}, {1, 3}, {2, 5}, {6, 7}

// {0, 4}, {1, 3}, {2, 6}, {5, 7}

// {0, 4}, {1, 3}, {2, 7}, {5, 6}

// {0, 4}, {1, 5}, {2, 3}, {6, 7}

// {0, 4}, {1, 5}, {2, 6}, {3, 7}

// {0, 4}, {1, 5}, {2, 7}, {3, 6}

// {0, 4}, {1, 6}, {2, 3}, {5, 7}

// {0, 4}, {1, 6}, {2, 5}, {3, 7}

// {0, 4}, {1, 6}, {2, 7}, {3, 5}

// {0, 4}, {1, 7}, {2, 3}, {5, 6}

// {0, 4}, {1, 7}, {2, 5}, {3, 6}

// {0, 4}, {1, 7}, {2, 6}, {3, 5}

// {0, 5}, {1, 2}, {3, 4}, {6, 7}

// {0, 5}, {1, 2}, {3, 6}, {4, 7}

// {0, 5}, {1, 2}, {3, 7}, {4, 6}

// {0, 5}, {1, 3}, {2, 4}, {6, 7}

// {0, 5}, {1, 3}, {2, 6}, {4, 7}

// {0, 5}, {1, 3}, {2, 7}, {4, 6}

// {0, 5}, {1, 4}, {2, 3}, {6, 7}

// {0, 5}, {1, 4}, {2, 6}, {3, 7}

// {0, 5}, {1, 4}, {2, 7}, {3, 6}

// {0, 5}, {1, 6}, {2, 3}, {4, 7}

// {0, 5}, {1, 6}, {2, 4}, {3, 7}

// {0, 5}, {1, 6}, {2, 7}, {3, 4}

// {0, 5}, {1, 7}, {2, 3}, {4, 6}

// {0, 5}, {1, 7}, {2, 4}, {3, 6}

// {0, 5}, {1, 7}, {2, 6}, {3, 4}

// {0, 6}, {1, 2}, {3, 4}, {5, 7}

// {0, 6}, {1, 2}, {3, 5}, {4, 7}

// {0, 6}, {1, 2}, {3, 7}, {4, 5}

// {0, 6}, {1, 3}, {2, 4}, {5, 7}

// {0, 6}, {1, 3}, {2, 5}, {4, 7}

// {0, 6}, {1, 3}, {2, 7}, {4, 5}

// {0, 6}, {1, 4}, {2, 3}, {5, 7}

// {0, 6}, {1, 4}, {2, 5}, {3, 7}

// {0, 6}, {1, 4}, {2, 7}, {3, 5}

// {0, 6}, {1, 5}, {2, 3}, {4, 7}

// {0, 6}, {1, 5}, {2, 4}, {3, 7}

// {0, 6}, {1, 5}, {2, 7}, {3, 4}

// {0, 6}, {1, 7}, {2, 3}, {4, 5}

// {0, 6}, {1, 7}, {2, 4}, {3, 5}

// {0, 6}, {1, 7}, {2, 5}, {3, 4}

// {0, 7}, {1, 2}, {3, 4}, {5, 6}

// {0, 7}, {1, 2}, {3, 5}, {4, 6}

// {0, 7}, {1, 2}, {3, 6}, {4, 5}

// {0, 7}, {1, 3}, {2, 4}, {5, 6}

// {0, 7}, {1, 3}, {2, 5}, {4, 6}

// {0, 7}, {1, 3}, {2, 6}, {4, 5}

// {0, 7}, {1, 4}, {2, 3}, {5, 6}

// {0, 7}, {1, 4}, {2, 5}, {3, 6}

// {0, 7}, {1, 4}, {2, 6}, {3, 5}

// {0, 7}, {1, 5}, {2, 3}, {4, 6}

// {0, 7}, {1, 5}, {2, 4}, {3, 6}

// {0, 7}, {1, 5}, {2, 6}, {3, 4}

// {0, 7}, {1, 6}, {2, 3}, {4, 5}

// {0, 7}, {1, 6}, {2, 4}, {3, 5}

// {0, 7}, {1, 6}, {2, 5}, {3, 4}

// 4. 各ペアごとに, 列をチェック.

// -> もともと, H が奇数だった場合は, 最終行を除外して考えることに注意.

if(odd) H--;

bool symmetric = false;

for(auto &p : rp){

// 4-1. ペアに対応するマス目を作成.

char t[H][W];

int idx = 0;

rep(i, p.size()){

int r1 = p[i][0];

int r2 = p[i][1];

if(r1 >= H){

rep(k, W) t[H / 2][k] = board[r2][k];

continue;

}

if(r2 >= H){

rep(k, W) t[H / 2][k] = board[r1][k];

continue;

}

rep(k, W){

t[idx][k] = board[r1][k];

t[H - 1 - idx][k] = board[r2][k];

}

idx++;

}

// 4-2. 点対称となる列の組み合わせが存在するか？

int column[W], deploy[W];

rep(i, W) column[i] = deploy[i] = 0;

idx = 0;

rep(i, W){

if(column[i]) continue;

bool ok = false;

repx(j, i + 1, W){

if(column[j]) continue;

ok = true;

rep(k, H) if(t[k][i] != t[H - 1 - k][j]) ok = false;

if(ok){

column[i] = 1; // i列目を使用済みに変更.

column[j] = 1; // j列目を使用済みに変更.

deploy[idx] = 1; // 最も左側の列を, 配置済みに変更.

deploy[W - 1 - idx] = 1; // 最も右側の列を, 配置済みに変更.

idx++;

break;

}

if(W & 1){

if(!ok){

if(!deploy[W / 2]){

bool g = true;

rep(k, (H + 1) / 2) if(t[k][i] != t[H - 1 - k][i]) g = false;

if(g){

ok = true;

column[i] = 1; // i列目を使用済みに変更.

deploy[W / 2] = 1; // 中央の列を, 配置済みに変更.

}

if(!ok) break;

}

// 4-3. 存在した場合(※配置が正常に行われた場合).

int used = 0;

rep(i, W) if(deploy[i]) used++;

if(used == W){

symmetric = true;

break;

}

// 5. 出力.

printf("%s\n", symmetric ? "YES" : "NO");

return 0;

}

[入力例]
2 3
arc
rac

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

[入力例]
3 7
atcoder
regular
contest

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

[入力例]
12 12
bimonigaloaf
faurwlkbleht
dexwimqxzxbb
lxdgyoifcxid
ydxiliocfdgx
nfoabgilamoi
ibxbdqmzxxwe
pqirylfrcrnf
wtehfkllbura
yfrnpflcrirq
wvcclwgiubrk
lkbrwgwuiccv

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

[入力例]
4 5
pqrqp
qrqpp
rqppq
qppqr

[出力例]
YES

[入力例]
5 6
acbabc
acbabc
dagfej
oxtotx
fjedga

[出力例]
YES

[入力例]
8 11
mhrgarqnlsf
elsncyfgpih
gfejiaosmjy
hifgycsnple
fsqnrarglhm
yjosaiejmfg
eynvranhubi
ibnharnvuye

[出力例]
YES

[入力例]

2 3

arc

rac

[出力例]

YES

※AtCoderテストケースより

[入力例]

3 7

atcoder

regular

contest

[出力例]

※AtCoderテストケースより

[入力例]

12 12

bimonigaloaf

faurwlkbleht

dexwimqxzxbb

lxdgyoifcxid

ydxiliocfdgx

nfoabgilamoi

ibxbdqmzxxwe

pqirylfrcrnf

wtehfkllbura

yfrnpflcrirq

wvcclwgiubrk

lkbrwgwuiccv

[出力例]

YES

※AtCoderテストケースより

[入力例]

4 5

pqrqp

qrqpp

rqppq

qppqr

[出力例]

YES

[入力例]

5 6

acbabc

dagfej

oxtotx

fjedga

[出力例]

YES

[入力例]

8 11

mhrgarqnlsf

elsncyfgpih

gfejiaosmjy

hifgycsnple

fsqnrarglhm

yjosaiejmfg

eynvranhubi

ibnharnvuye

[出力例]

YES

■参照サイト
AtCoder Regular Contest 095

2021年7月11日

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

C++の練習を兼ねて, AtCoder Beginner Contest 209 の問題C (Not Equal) ～問題D (Collision) を解いてみた.

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

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

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

// 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 = 1e9 + 7;
LL c[202020];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%lld", &c[i]);
    
    // 2. sort.
    sort(c, c + N);
    
    // 3. 集計.
    LL ans = 1;
    rep(i, N){
        ans *= max(0LL, c[i] - i);
        ans %= MOD;
    }
    
    // 4. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 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 = 1e9 + 7;

LL c[202020];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

rep(i, N) scanf("%lld", &c[i]);

// 2. sort.

sort(c, c + N);

// 3. 集計.

LL ans = 1;

rep(i, N){

ans *= max(0LL, c[i] - i);

ans %= MOD;

}

// 4. 出力.

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

return 0;

}

[入力例]
2
1 3

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

[入力例]
4
3 3 4 4

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

[入力例]
2
1 1

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

[入力例]
10
999999917 999999914 999999923 999999985 999999907 999999965 999999914 999999908 999999951 999999979

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

[入力例]
15
31415 92653 58979 32384 62643 38327 95028 84197 16939 9375 105820 97494 4592 30781 64062

[出力例]
791280696

[入力例]

1 3

[出力例]

※AtCoderテストケースより

[入力例]

3 3 4 4

[出力例]

※AtCoderテストケースより

[入力例]

1 1

[出力例]

※AtCoderテストケースより

[入力例]

999999917 999999914 999999923 999999985 999999907 999999965 999999914 999999908 999999951 999999979

[出力例]

405924645

※AtCoderテストケースより

[入力例]

31415 92653 58979 32384 62643 38327 95028 84197 16939 9375 105820 97494 4592 30781 64062

[出力例]

791280696

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

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

int main(){
    
    // 1. 入力情報.
    int N, Q;
    scanf("%d %d", &N, &Q);
    vvi G(N);
    rep(i, N - 1){
        int a, b;
        scanf("%d %d", &a, &b);
        a--, b--;
        G[a].pb(b);
        G[b].pb(a);
    }
    
    // 2. 街 1 を スタート地点として探索.
    // https://ja.wikipedia.org/wiki/幅優先探索
    auto bfs = [&](vvi &G, int s, int *d){
        // 2-1. 空のキュー.
        queue<int> q;
        
        // 2-2. 探索地点 s をキュー q に追加.
        q.push(s);
        while(!q.empty()){
            // 2-3. キューから取り出す.
            int u = q.front();
            q.pop();
            
            // 2-4. 取り出した要素を処理.
            for(auto &e : G[u]){
                // 3-5. 訪問済であれば, 処理をスキップ.
                if(d[e])            continue;
                if(!d[e] && e != s) d[e] = d[u] + 1, q.push(e);
            }
        }
        return;
    };
    int d[101010];
    rep(i, 101010) d[i] = 0;
    bfs(G, 0, d);
    
    // 3. クエリ回答.
    rep(i, Q){
        // 3-1. 街情報.
        int x, y;
        scanf("%d %d", &x, &y);
        x--, y--;
        
        // 3-2. 街 x -> y に移動する場合の偶奇.
        bool ok = (abs(d[x] - d[y]) & 1);
        
        // 3-3. 出力.
        printf("%s\n", ok ? "Road" : "Town");
    }
    return 0;
    
}

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

int main(){

// 1. 入力情報.

int N, Q;

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

vvi G(N);

rep(i, N - 1){

int a, b;

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

a--, b--;

G[a].pb(b);

G[b].pb(a);

}

// 2. 街 1 をスタート地点として探索.

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

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

// 2-1. 空のキュー.

queue<int> q;

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

q.push(s);

while(!q.empty()){

// 2-3. キューから取り出す.

int u = q.front();

q.pop();

// 2-4. 取り出した要素を処理.

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

// 3-5. 訪問済であれば, 処理をスキップ.

if(d[e]) continue;

if(!d[e] && e != s) d[e] = d[u] + 1, q.push(e);

}

return;

};

int d[101010];

rep(i, 101010) d[i] = 0;

bfs(G, 0, d);

// 3. クエリ回答.

rep(i, Q){

// 3-1. 街情報.

int x, y;

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

x--, y--;

// 3-2. 街 x -> y に移動する場合の偶奇.

bool ok = (abs(d[x] - d[y]) & 1);

// 3-3. 出力.

printf("%s\n", ok ? "Road" : "Town");

}

return 0;

}

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

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

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

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

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

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

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

[出力例]
Road
Road
Town
Road
Road
Town
Town
Road
Road
Town
Town
Road
Town
Road
Road

100

101

102

103

104

105

106

107

108

109

110

[入力例]

4 1

1 2

2 3

2 4

1 2

[出力例]

Road

※AtCoderテストケースより

[入力例]

5 2

1 2

2 3

3 4

4 5

1 3

1 5

[出力例]

Town

※AtCoderテストケースより

[入力例]

9 9

2 3

5 6

4 8

8 9

4 5

3 4

1 9

3 7

7 9

2 5

2 6

4 6

2 4

5 8

7 8

3 6

5 6

[出力例]

Town

Road

Town

Road

※AtCoderテストケースより

[入力例]

20 15

1 17

1 2

1 5

1 8

2 19

2 9

9 18

9 10

10 20

8 16

3 5

5 6

6 11

3 13

3 4

4 12

13 14

14 15

7 20

4 19

8 14

5 15

11 12

1 8

17 18

8 18

3 17

12 18

2 11

7 18

16 18

5 13

3 11

7 20

[出力例]

Road

Town

Road

Town

Road

Town

Road

Town

Road

■参照サイト
AtCoder Beginner Contest 209

2021年7月9日

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

C++の練習を兼ねて, 競プロ典型 90 問の問題016 (Minimum Coins) を解いてみた.

■感想.
1. 実装方針を決めることができたので, AC版に到達出来たと思う.
2. 手強い問題が非常に多い気もするけど, 時間を見つけて, 引き続き, 取り組んでいきたいと思う.

詳細は, 本家のサイト(GitHub) 競プロ典型 90 問の問題016 をご覧下さい.

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

// 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. 入力情報.
    LL N, coin[3];
    scanf("%lld %lld %lld %lld", &N, &coin[0], &coin[1], &coin[2]);
    
    // 2. sort.
    sort(coin, coin + 3);
    
    // 3. 硬貨枚数を計算.
    int ans = 10000;
    // ex.
    // 15円 を 1, 5, 8円で支払う場合, 
    // 1, 1, 5, 8 とすると, 4枚.
    // 5, 5, 5    とすると, 3枚.
    // のように, 硬貨枚数が変化することに注意.
    repr(c, 9999, 0){
        // 金額がオーバーする場合.
        LL mc = coin[2] * c;
        if(mc > N) continue;
        
        // ぴったりの場合.
        if(mc == N) ans = min(ans, c);
        
        // 不足する場合.
        if(mc < N){
            LL mab = N - mc;
            if(mab / coin[1] > 9999) continue;
            int bMax = (int)(mab / coin[1]);
            repr(b, bMax, 0){
                LL ma = mab - coin[1] * b;
                int a = (int)(ma / coin[0]);
                if(ma % coin[0] == 0){
                    ans = min(ans, a + b + c);
                    break;
                }
            }
        }
    }
    
    // 4. 出力.
    assert(ans != 10000);
    printf("%d\n", ans);
    return 0;
    
}

// 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. 入力情報.

LL N, coin[3];

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

// 2. sort.

sort(coin, coin + 3);

// 3. 硬貨枚数を計算.

int ans = 10000;

// ex.

// 15円を 1, 5, 8円で支払う場合,

// 1, 1, 5, 8 とすると, 4枚.

// 5, 5, 5 とすると, 3枚.

// のように, 硬貨枚数が変化することに注意.

repr(c, 9999, 0){

// 金額がオーバーする場合.

LL mc = coin[2] * c;

if(mc > N) continue;

// ぴったりの場合.

if(mc == N) ans = min(ans, c);

// 不足する場合.

if(mc < N){

LL mab = N - mc;

if(mab / coin[1] > 9999) continue;

int bMax = (int)(mab / coin[1]);

repr(b, bMax, 0){

LL ma = mab - coin[1] * b;

int a = (int)(ma / coin[0]);

if(ma % coin[0] == 0){

ans = min(ans, a + b + c);

break;

}

// 4. 出力.

assert(ans != 10000);

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

return 0;

}

[入力例]
227
21 47 56

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

[入力例]
9999
1 5 10

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

[入力例]
998244353
314159 265358 97932

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

[入力例]
100000000
10001 10002 10003

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

[入力例]
1000000000
314159 265358 97932

[出力例]
3527

[入力例]
987654321
14142 135623 73095

[出力例]
7405

[入力例]

227

21 47 56

[出力例]

※AtCoderテストケースより

[入力例]

9999

1 5 10

[出力例]

1004

※AtCoderテストケースより

[入力例]

998244353

314159 265358 97932

[出力例]

3333

※AtCoderテストケースより

[入力例]

100000000

10001 10002 10003

[出力例]

9998

※AtCoderテストケースより

[入力例]

1000000000

314159 265358 97932

[出力例]

3527

[入力例]

987654321

14142 135623 73095

[出力例]

7405

■参照サイト
016 – Minimum Coins

2021年7月7日

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

C++の練習を兼ねて, 競プロ典型 90 問の問題030 (K Factors) を解いてみた.

詳細は, 本家のサイト(GitHub) 競プロ典型 90 問の問題030 をご覧下さい.

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

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

int main(){
    
    // 1. 入力情報.
    int N, K;
    scanf("%d %d", &N, &K);
    
    // 2. 倍数を保存.
    repx(i, 2, N + 1){
        if(a[i]) continue;
        repex(j, i, N + 1, i) a[j]++;
    }
    
    // 3. K種類以上をカウント.
    int ans = 0;
    rep(i, N + 1) if(a[i] >= K) ans++;
    
    // 4. 出力.
    printf("%d\n", ans);
    return 0;
    
}

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

int main(){

// 1. 入力情報.

int N, K;

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

// 2. 倍数を保存.

repx(i, 2, N + 1){

if(a[i]) continue;

repex(j, i, N + 1, i) a[j]++;

}

// 3. K種類以上をカウント.

int ans = 0;

rep(i, N + 1) if(a[i] >= K) ans++;

// 4. 出力.

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

return 0;

}

[入力例]
15 2

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

[入力例]
30 2

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

[入力例]
200 4

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

[入力例]
869120 1

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

[入力例]
10000000 3

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

[入力例]
2021 4

[出力例]
83

[入力例]
20210707 3

[出力例]
13978430
※整数 N が, 問題文の制約条件から範囲外であるケース.

[入力例]
20210711 8

[出力例]
11
※整数 N が, 問題文の制約条件から範囲外であるケース.

[入力例]

15 2

[出力例]

※AtCoderテストケースより

[入力例]

30 2

[出力例]

※AtCoderテストケースより

[入力例]

200 4

[出力例]

※AtCoderテストケースより

[入力例]

869120 1

[出力例]

869119

※AtCoderテストケースより

[入力例]

10000000 3

[出力例]

6798027

※AtCoderテストケースより

[入力例]

2021 4

[出力例]

[入力例]

20210707 3

[出力例]

13978430

※整数 N が, 問題文の制約条件から範囲外であるケース.

[入力例]

20210711 8

[出力例]

※整数 N が, 問題文の制約条件から範囲外であるケース.

■参照サイト
030 – K Factors

C++の練習を兼ねて, 競プロ典型 90 問 の 問題011 (Gravy Jobs) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 211 の 問題C (chokudai) ～ 問題D (Number of Shortest paths) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 123 の 問題A (Deforestation) ～ 問題B (Increasing Triples) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 209 の 問題F (Deforestation) を解いてみた.

C++の練習を兼ねて, 競プロ典型 90 問 の 問題009 (Three Point Angle) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 209 の 問題C (Not Equal) ～ 問題D (Collision) を解いてみた.

C++の練習を兼ねて, 競プロ典型 90 問 の 問題016 (Minimum Coins) を解いてみた.

C++の練習を兼ねて, 競プロ典型 90 問 の 問題030 (K Factors) を解いてみた.

C++の練習を兼ねて, 競プロ典型 90 問の問題011 (Gravy Jobs) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 211 の問題C (chokudai) ～問題D (Number of Shortest paths) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 123 の問題A (Deforestation) ～問題B (Increasing Triples) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 209 の問題F (Deforestation) を解いてみた.

C++の練習を兼ねて, 競プロ典型 90 問の問題009 (Three Point Angle) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 209 の問題C (Not Equal) ～問題D (Collision) を解いてみた.

C++の練習を兼ねて, 競プロ典型 90 問の問題016 (Minimum Coins) を解いてみた.

C++の練習を兼ねて, 競プロ典型 90 問の問題030 (K Factors) を解いてみた.