C++ | 個人用メモ帳

2021年8月5日2021年8月5日

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

C++の練習を兼ねて, AtCoder Regular Contest 124 の問題C (C – LCM of GCDs) を解いてみた.

■感想.
1. 問題C は, 方針が見えなかったので, 解説を参考にして, ようやく, AC版に到達出来た.
2. 個人的には, 全探索を使用するロジックが, 非常に面白い問題に感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/arc124/editorial/2328
// 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 a[55], b[55];

// 与えられた正の整数のすべての約数を抽出.
// @param X: 約数を抽出したい正の整数.
// @return ret: すべての約数(※1以上).
set<int> div(int X){
    set<int> ret;
    repx(d, 1, (int)sqrt(X) + 1){
        if(!(X % d)){
            ret.insert(d);
            if(d * d != X) ret.insert(X / d);
        }
    }
    return ret;
}

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%d %d", &a[i], &b[i]);
    
    // 2. a[0], b[0] の 約数.
    set<int> aDiv = div(a[0]);
    set<int> bDiv = div(b[0]);
    
    // 3. 全探索.
    LL ans = 0;
    for(auto &p : aDiv){
        for(auto &q : bDiv){
            int c = 0;
            rep(i, N){
                // 以下の二通りのいずれか成立すれば良いはず.
                // a[i] が p の 倍数 かつ b が q の 倍数である場合.
                // a[i] が q の 倍数 かつ b が p の 倍数である場合.
                bool ok = false;
                if(a[i] % p == 0 && b[i] % q == 0) ok = true;
                if(a[i] % q == 0 && b[i] % p == 0) ok = true;
                if(ok) c++;
            }
            
            // 最大値更新.
            if(c == N){
                LL pCur = (LL)p;
                LL qCur = (LL)q;
                LL gCur = __gcd(pCur, qCur);
                ans = max(ans, pCur / gCur * qCur);
            }
        }
    }
    
    // 4. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc124/editorial/2328

// 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 a[55], b[55];

// 与えられた正の整数のすべての約数を抽出.

// @param X: 約数を抽出したい正の整数.

// @return ret: すべての約数(※1以上).

set<int> div(int X){

set<int> ret;

repx(d, 1, (int)sqrt(X) + 1){

if(!(X % d)){

ret.insert(d);

if(d * d != X) ret.insert(X / d);

}

return ret;

}

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

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

// 2. a[0], b[0] の約数.

set<int> aDiv = div(a[0]);

set<int> bDiv = div(b[0]);

// 3. 全探索.

LL ans = 0;

for(auto &p : aDiv){

for(auto &q : bDiv){

int c = 0;

rep(i, N){

// 以下の二通りのいずれか成立すれば良いはず.

// a[i] が p の倍数かつ b が q の倍数である場合.

// a[i] が q の倍数かつ b が p の倍数である場合.

bool ok = false;

if(a[i] % p == 0 && b[i] % q == 0) ok = true;

if(a[i] % q == 0 && b[i] % p == 0) ok = true;

if(ok) c++;

}

// 最大値更新.

if(c == N){

LL pCur = (LL)p;

LL qCur = (LL)q;

LL gCur = __gcd(pCur, qCur);

ans = max(ans, pCur / gCur * qCur);

}

// 4. 出力.

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

return 0;

}

[入力例]
2
2 15
10 6

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

[入力例]
5
148834018 644854700
947642099 255192490
35137537 134714230
944287156 528403260
68656286 200621680

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

[入力例]
20
557057460 31783488
843507940 794587200
640711140 620259584
1901220 499867584
190122000 41414848
349507610 620259584
890404700 609665088
392918800 211889920
507308870 722352000
156850650 498904448
806117280 862969856
193607570 992030080
660673950 422816704
622015810 563434560
207866720 316871744
63057130 117502592
482593010 366954816
605221700 705015552
702500790 900532160
171743540 353470912

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

[入力例]
5
21021 84344
50297 63294
54516 141752
94900 57596
36344 52689

[出力例]
1001

[入力例]
25
3143903 52425315
45033975 5838677
46260287 44381925
30221640 18863418
26498611 46791405
54981945 2245645
22456450 52922655
29491470 1347387
4940419 47997810
3497805 40421610
26049482 5033700
6698475 26498611
5838677 37795860
22076010 51649835
2694774 37952550
10155780 21558192
25151224 51394275
45175725 26498611
52098964 43921485
33622740 23803837
44014642 11862090
3111750 898258
52098964 9761085
50289075 14821257
21558192 50525010

[出力例]
20210805

[入力例]

2 15

10 6

[出力例]

※AtCoderのテストケースより

[入力例]

148834018 644854700

947642099 255192490

35137537 134714230

944287156 528403260

68656286 200621680

[出力例]

238630

※AtCoderのテストケースより

[入力例]

557057460 31783488

843507940 794587200

640711140 620259584

1901220 499867584

190122000 41414848

349507610 620259584

890404700 609665088

392918800 211889920

507308870 722352000

156850650 498904448

806117280 862969856

193607570 992030080

660673950 422816704

622015810 563434560

207866720 316871744

63057130 117502592

482593010 366954816

605221700 705015552

702500790 900532160

171743540 353470912

[出力例]

152594452160

※AtCoderのテストケースより

[入力例]

21021 84344

50297 63294

54516 141752

94900 57596

36344 52689

[出力例]

1001

[入力例]

3143903 52425315

45033975 5838677

46260287 44381925

30221640 18863418

26498611 46791405

54981945 2245645

22456450 52922655

29491470 1347387

4940419 47997810

3497805 40421610

26049482 5033700

6698475 26498611

5838677 37795860

22076010 51649835

2694774 37952550

10155780 21558192

25151224 51394275

45175725 26498611

52098964 43921485

33622740 23803837

44014642 11862090

3111750 898258

52098964 9761085

50289075 14821257

21558192 50525010

[出力例]

20210805

■参照サイト
AtCoder Regular Contest 124

2021年8月4日2021年8月4日

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

C++の練習を兼ねて, AtCoder Regular Contest 124 の問題A (LR Constraints) ～問題B (XOR Matching 2) を解いてみた.

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

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

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

// 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 = 998244353;
int l[1010], r[1010], memo[1010];

int main(){
    
    // 1. 入力情報.
    int N, K;
    scanf("%d %d", &N, &K);
    vvi v(N);
    rep(i, K){
        char c[11];
        int k, n = i + 1;
        scanf("%s %d", c, &k);
        k--;
        
        // 最も左にあるカードが指定された場合.
        if(c[0] == 'L'){
            l[n] = k;
            r[n] = N - 1;
        }
        
        // 最も右にあるカードが指定された場合.
        if(c[0] == 'R'){
            l[n] = 0;
            r[n] = k;
        }
        
        // 使用済み.
        v[k].pb(n);
        memo[k]++;
    }
    
    // 2. 数字を, 新たに保存.
    rep(i, K){
        int n = i + 1;
        repx(j, l[n], r[n] + 1) if(!memo[j]) v[j].pb(n);
    }
    
    // 3. 集計.
    LL ans = 1;
    rep(i, N) ans = ans * (LL)v[i].size() % MOD;
    
    // 4. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 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 = 998244353;

int l[1010], r[1010], memo[1010];

int main(){

// 1. 入力情報.

int N, K;

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

vvi v(N);

rep(i, K){

char c[11];

int k, n = i + 1;

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

k--;

// 最も左にあるカードが指定された場合.

if(c[0] == 'L'){

l[n] = k;

r[n] = N - 1;

}

// 最も右にあるカードが指定された場合.

if(c[0] == 'R'){

l[n] = 0;

r[n] = k;

}

// 使用済み.

v[k].pb(n);

memo[k]++;

}

// 2. 数字を, 新たに保存.

rep(i, K){

int n = i + 1;

repx(j, l[n], r[n] + 1) if(!memo[j]) v[j].pb(n);

}

// 3. 集計.

LL ans = 1;

rep(i, N) ans = ans * (LL)v[i].size() % MOD;

// 4. 出力.

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

return 0;

}

[入力例]
3 2
L 1
R 2

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

[入力例]
30 10
R 6
R 8
R 7
R 25
L 26
L 13
R 14
L 11
L 23
R 30

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

[入力例]
5 3
L 2
R 3
L 4

[出力例]
2

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

[出力例]
9

[入力例]
50 17
R 29
R 45
R 33
L 36
L 35
R 5
L 6
L 43
L 48
R 7
L 32
R 17
L 41
R 2
R 50
R 28
L 11

[出力例]
733873656

[入力例]

3 2

L 1

R 2

[出力例]

※AtCoderのテストケースより

[入力例]

30 10

R 6

R 8

R 7

R 25

L 26

L 13

R 14

L 11

L 23

R 30

[出力例]

343921442

※AtCoderのテストケースより

[入力例]

5 3

L 2

R 3

L 4

[出力例]

[入力例]

7 5

L 5

R 2

L 3

R 4

L 1

[出力例]

[入力例]

50 17

R 29

R 45

R 33

L 36

L 35

R 5

L 6

L 43

L 48

R 7

L 32

R 17

L 41

R 2

R 50

R 28

L 11

[出力例]

733873656

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

// 解き直し.
// https://atcoder.jp/contests/arc124/editorial/2329
// 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 a(N), b(N);
    rep(i, N) scanf("%d", &a[i]);
    rep(i, N) scanf("%d", &b[i]);
    
    // 2. sort.
    sort(all(b));
    
    // 3. N 通り試す.
    set<int> ans;
    rep(i, N){
        // 3-1. x を 取得.
        int x = a[0] ^ b[i];
        
        // 3-2. すでに確認済みか？
        if(ans.count(x)) continue;
        
        // 3-3. 数列 c を 作成.
        vi c;
        rep(j, N) c.pb(a[j] ^ x);
        
        // 3-4. sort.
        sort(all(c));
        
        // 3-5. 良い数を保存.
        if(b == c) ans.insert(x);
    }
    
    // 4. 出力.
    printf("%d\n", ans.size());
    for(auto &p : ans) printf("%d\n", p);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc124/editorial/2329

// 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 a(N), b(N);

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

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

// 2. sort.

sort(all(b));

// 3. N 通り試す.

set<int> ans;

rep(i, N){

// 3-1. x を取得.

int x = a[0] ^ b[i];

// 3-2. すでに確認済みか？

if(ans.count(x)) continue;

// 3-3. 数列 c を作成.

vi c;

rep(j, N) c.pb(a[j] ^ x);

// 3-4. sort.

sort(all(c));

// 3-5. 良い数を保存.

if(b == c) ans.insert(x);

}

// 4. 出力.

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

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

return 0;

}

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

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

[入力例]
2
0 1
0 2

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

[入力例]
24
14911005 70152939 282809711 965900047 168465665 337027481 520073861 20800623 934711525 944543101 522277111 580736275 468493313 912814743 99651737 439502451 365446123 198473587 285587229 253330309 591640417 761745547 247947767 750367481
805343020 412569406 424258892 329301584 123050452 1042573510 1073384116 495212986 158432830 145726540 623594202 836660574 380872916 722447664 230460104 718360386 620079272 109804454 60321058 38178640 475708360 207775930 393038502 310271010

[出力例]
8
107543995
129376201
139205201
160626723
312334911
323172429
481902037
493346727
※AtCoderのテストケースより

[入力例]
5
9323 23050 4277 6413 18289
23409 11325 16692 6379 17676

[出力例]
0

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

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

[入力例]

1 2 3

6 4 7

[出力例]

※AtCoderのテストケースより

[入力例]

0 1

0 2

[出力例]

※AtCoderのテストケースより

[入力例]

14911005 70152939 282809711 965900047 168465665 337027481 520073861 20800623 934711525 944543101 522277111 580736275 468493313 912814743 99651737 439502451 365446123 198473587 285587229 253330309 591640417 761745547 247947767 750367481

805343020 412569406 424258892 329301584 123050452 1042573510 1073384116 495212986 158432830 145726540 623594202 836660574 380872916 722447664 230460104 718360386 620079272 109804454 60321058 38178640 475708360 207775930 393038502 310271010

[出力例]

107543995

129376201

139205201

160626723

312334911

323172429

481902037

493346727

※AtCoderのテストケースより

[入力例]

9323 23050 4277 6413 18289

23409 11325 16692 6379 17676

[出力例]

[入力例]

0 1 2 3 4 5 6 7

7 6 5 4 3 2 1 0

[出力例]

■参照サイト
AtCoder Regular Contest 124

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

C++の練習を兼ねて, AtCoder Regular Contest 124 の 問題C (C – LCM of GCDs) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 124 の 問題A (LR Constraints) ～ 問題B (XOR Matching 2) を解いてみた.

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++の練習を兼ねて, AtCoder Regular Contest 124 の問題C (C – LCM of GCDs) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 124 の問題A (LR Constraints) ～問題B (XOR Matching 2) を解いてみた.

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) を解いてみた.