C++ | 個人用メモ帳

2022年9月22日

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

C++の練習を兼ねて, AtCoder Regular Contest 033 の問題D (見たことのない多項式) を解いてみた.

■感想.
1. 問題Dは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, ラグランジュ補間について, 学習できたので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://www.slideshare.net/chokudai/arc033
// 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;
const int MAX = 101010;
LL p[MAX], q[MAX], c[MAX], qt[MAX];

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

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N + 1) scanf("%lld", &p[i]);
    LL T;
    scanf("%lld", &T);
    
    // 2. 例外.
    if(T <= (LL)N){
        printf("%lld\n", p[(int)T]);
        return 0;
    }
    
    // 3. ラグランジュ補間.
    // Q[i](x) = (x - 0) * (x - 1) * ... * (x - N) / (x - i)
    // ex. N = 5.
    // Q[0](0) =                                    (-1) * (-2) * (-3) * (-4) * (-5)
    // Q[1](1) =                             (+1) * (-1) * (-2) * (-3) * (-4)
    // Q[2](2) =                      (+2) * (+1) * (-1) * (-2) * (-3)
    // Q[3](3) =               (+3) * (+2) * (+1) * (-1) * (-2)
    // Q[4](4) =        (+4) * (+3) * (+2) * (+1) * (-1)
    // Q[5](5) = (+5) * (+4) * (+3) * (+2) * (+1)
    // 
    // 3-1. Q[0](0).
    q[0] = 1;
    rep(i, N) q[0] = q[0] * (MOD - i - 1) % MOD;
    
    // 3-2. Q[1](1) ～ Q[N](N).
    repx(i, 1, N + 1){
        q[i] = q[i - 1];
        q[i] *= i;
        q[i] %= MOD;
        q[i] *= mPow(MOD + (i - 1 - N), MOD - 2);
        q[i] %= MOD;
    }
    
    // 3-3. C[i] (= P[i] / Q[i](i)).
    rep(i, N + 1) c[i] = p[i] * mPow(q[i], MOD - 2) % MOD;
    
    // 3-4. 基準.
    LL b = 1;
    rep(i, N + 1) b = b * (T - i) % MOD;
    
    // 3-5. Q[0](T) ～ Q[N](T).
    rep(i, N + 1){
        qt[i] = b;
        qt[i] %= MOD;
        qt[i] *= mPow(T - i, MOD - 2);
        qt[i] %= MOD;
    }
    
    // 4. P(T).
    LL ans = 0;
    rep(i, N + 1) ans = (ans + c[i] * qt[i] % MOD) % MOD;
    
    // 5. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

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

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

const int MAX = 101010;

LL p[MAX], q[MAX], c[MAX], qt[MAX];

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

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

// @param b: 指数.

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

LL mPow(LL a, LL b){

LL t = 1;

while(b){

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

a = a * a % MOD;

b >>= 1;

}

return t;

}

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

rep(i, N + 1) scanf("%lld", &p[i]);

LL T;

scanf("%lld", &T);

// 2. 例外.

if(T <= (LL)N){

printf("%lld\n", p[(int)T]);

return 0;

}

// 3. ラグランジュ補間.

// Q[i](x) = (x - 0) * (x - 1) * ... * (x - N) / (x - i)

// ex. N = 5.

// Q[0](0) = (-1) * (-2) * (-3) * (-4) * (-5)

// Q[1](1) = (+1) * (-1) * (-2) * (-3) * (-4)

// Q[2](2) = (+2) * (+1) * (-1) * (-2) * (-3)

// Q[3](3) = (+3) * (+2) * (+1) * (-1) * (-2)

// Q[4](4) = (+4) * (+3) * (+2) * (+1) * (-1)

// Q[5](5) = (+5) * (+4) * (+3) * (+2) * (+1)

// 3-1. Q[0](0).

q[0] = 1;

rep(i, N) q[0] = q[0] * (MOD - i - 1) % MOD;

// 3-2. Q[1](1) ～ Q[N](N).

repx(i, 1, N + 1){

q[i] = q[i - 1];

q[i] *= i;

q[i] %= MOD;

q[i] *= mPow(MOD + (i - 1 - N), MOD - 2);

q[i] %= MOD;

}

// 3-3. C[i] (= P[i] / Q[i](i)).

rep(i, N + 1) c[i] = p[i] * mPow(q[i], MOD - 2) % MOD;

// 3-4. 基準.

LL b = 1;

rep(i, N + 1) b = b * (T - i) % MOD;

// 3-5. Q[0](T) ～ Q[N](T).

rep(i, N + 1){

qt[i] = b;

qt[i] %= MOD;

qt[i] *= mPow(T - i, MOD - 2);

qt[i] %= MOD;

}

// 4. P(T).

LL ans = 0;

rep(i, N + 1) ans = (ans + c[i] * qt[i] % MOD) % MOD;

// 5. 出力.

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

return 0;

}

[入力例]
2
1 3 7
3

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

[入力例]
5
4 16 106 484 1624 4384
1000000000

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

[入力例]
1
1 2
1

[出力例]
2

[入力例]
1
1 2
3

[出力例]
4

[入力例]
2
1 2 3
5

[出力例]
6

[入力例]
3
3 2 1 3
7

[出力例]
101

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

[出力例]
5440

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

[出力例]
1156402

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

[出力例]
812509535

[入力例]

1 3 7

[出力例]

※AtCoderテストケースより

[入力例]

4 16 106 484 1624 4384

1000000000

[出力例]

999984471

※AtCoderテストケースより

[入力例]

1 2

[出力例]

[入力例]

1 2

[出力例]

[入力例]

1 2 3

[出力例]

[入力例]

3 2 1 3

[出力例]

101

[入力例]

3 1 4 1 5 9 2

[出力例]

5440

[入力例]

3 9 0 8 5 2 9 10 9 1 10

[出力例]

1156402

[入力例]

3 5 4 6 0 8 9 2 0 3 1 5 7 8 0 3 7 2 1 6 9 10 9 8 2 3 1 8 7 10 7

[出力例]

812509535

■参照サイト
AtCoder Regular Contest 033

2022年9月21日

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

C++の練習を兼ねて, AtCoder Regular Contest 148 の問題C (Lights Out on Tree) を解いてみた.

■感想.
1. 問題Cは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 問題Cは, 解説のロジックにあるように, 頂点集合 S に含まれる各頂点の子頂点数に依存する性質があることが不思議に感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/arc148/editorial/4775
// 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
int p[202020];

int main(){
    
    // 1. 入力情報.
    int N, Q;
    scanf("%d %d", &N, &Q);
    vvi G(N);
    repx(i, 1, N){
        scanf("%d", &p[i]);
        --p[i];
        G[i].pb(p[i]);
        G[p[i]].pb(i);
    }
    
    // 2. クエリ回答.
    rep(i, Q){
        // 2-1. クエリ入力情報.
        int M;
        LL ans = 0;
        scanf("%d", &M);
        set<int> st;
        rep(j, M){
            // 頂点集合 S に含まれる頂点.
            int v;
            scanf("%d", &v);
            --v;
            
            // 頂点集合 S に, {親頂点, 子頂点} の 組み合わせがあった.
            if(v && st.count(p[v])) ans -= 2;
            
            // 保存.
            st.insert(v);
            
            // 集計.
            ans += G[v].size() + (v == 0);
        }
        
        // 2-2. 出力.
        printf("%lld\n", ans);
    }
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc148/editorial/4775

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

int p[202020];

int main(){

// 1. 入力情報.

int N, Q;

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

vvi G(N);

repx(i, 1, N){

scanf("%d", &p[i]);

--p[i];

G[i].pb(p[i]);

G[p[i]].pb(i);

}

// 2. クエリ回答.

rep(i, Q){

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

int M;

LL ans = 0;

scanf("%d", &M);

set<int> st;

rep(j, M){

// 頂点集合 S に含まれる頂点.

int v;

scanf("%d", &v);

--v;

// 頂点集合 S に, {親頂点, 子頂点} の組み合わせがあった.

if(v && st.count(p[v])) ans -= 2;

// 保存.

st.insert(v);

// 集計.

ans += G[v].size() + (v == 0);

}

// 2-2. 出力.

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

}

return 0;

}

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

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

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

[出力例]
1
2
2
4
4
6
6
8

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

[出力例]
2
2
7
3
7
8
10
8
10
15

[入力例]
30 15
1 2 5 1 2 5 2 7 4 10 10 7 3 1 3 8 1 15 15 18 18 19 19 17 8 17 2 2 2
1 1
1 2
1 3
1 7
1 13
2 20 18
2 5 3
3 26 19 18
4 7 4 19 20
5 5 7 2 15 20
6 9 13 11 12 25 27
7 1 2 15 18 7 4 5
8 23 24 25 26 27 28 29 30
9 1 2 3 4 5 6 7 8 9
10 2 4 6 8 10 11 13 15 17 19

[出力例]
5
7
3
3
1
4
6
7
9
13
6
18
8
14
15

100

101

102

[入力例]

6 6

1 1 2 2 5

6 1 2 3 4 5 6

3 2 5 6

1 3

3 1 2 3

3 4 5 6

4 2 3 4 5

[出力例]

※AtCoderテストケースより

[入力例]

12 8

1 1 2 1 2 3 3 5 9 9 8

1 12

1 8

1 5

2 7 3

2 5 8

3 7 2 5

4 1 2 5 10

5 3 2 9 8 12

[出力例]

[入力例]

18 10

3 1 6 1 5 1 3 2 4 5 7 6 17 4 17 7 2

2 9 18

2 8 12

3 17 6 4

1 5

5 3 8 17 11 13

3 1 2 3

4 3 12 4 5

7 1 3 5 7 9 11 13

6 2 3 7 11 10 8

10 17 1 13 2 11 16 5 8 10 7

[出力例]

[入力例]

30 15

1 2 5 1 2 5 2 7 4 10 10 7 3 1 3 8 1 15 15 18 18 19 19 17 8 17 2 2 2

1 1

1 2

1 3

1 7

1 13

2 20 18

2 5 3

3 26 19 18

4 7 4 19 20

5 5 7 2 15 20

6 9 13 11 12 25 27

7 1 2 15 18 7 4 5

8 23 24 25 26 27 28 29 30

9 1 2 3 4 5 6 7 8 9

10 2 4 6 8 10 11 13 15 17 19

[出力例]

■参照サイト
AtCoder Regular Contest 148

2022年9月20日

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

C++の練習を兼ねて, AtCoder Regular Contest 148 の問題A (mod M) ～問題B (dp) を解いてみた.

■感想.
1. 問題Bは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 問題B は, L が, 高々一つに決まるという解説のロジックが, 非常に不思議な印象を受けた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

■C++版プログラム(問題A／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--)
LL a[202020];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%lld", &a[i]);
    
    // 2. 最大公約数は？
    LL g = 0;
    rep(i, N - 1) g = (g == 0) ? abs(a[i + 1] - a[i]) : __gcd(g, abs(a[i + 1] - a[i]));
    
    // 3. 出力.
    printf("%d\n", g == 1 ? 2 : 1);
    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--)

LL a[202020];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

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

// 2. 最大公約数は？

LL g = 0;

rep(i, N - 1) g = (g == 0) ? abs(a[i + 1] - a[i]) : __gcd(g, abs(a[i + 1] - a[i]));

// 3. 出力.

printf("%d\n", g == 1 ? 2 : 1);

return 0;

}

[入力例]
3
1 4 8

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

[入力例]
4
5 10 15 20

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

[入力例]
10
3785 5176 10740 7744 3999 3143 9028 2822 4748 6888

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

[入力例]
20
15 108 30 36 91 39 82 15 46 119 100 114 105 50 67 64 4 6 62 77

[出力例]
2

[入力例]
30
3 39 2007 99 1407 1455 1551 471 579 591 711 795 819 927 1011 1023 1119 1239 1347 1371 1659 1695 1755 1803 1947 111 147 195 267 411

[出力例]
1

[入力例]

1 4 8

[出力例]

※AtCoderのテストケースより

[入力例]

5 10 15 20

[出力例]

※AtCoderのテストケースより

[入力例]

3785 5176 10740 7744 3999 3143 9028 2822 4748 6888

[出力例]

※AtCoderのテストケースより

[入力例]

15 108 30 36 91 39 82 15 46 119 100 114 105 50 67 64 4 6 62 77

[出力例]

[入力例]

3 39 2007 99 1407 1455 1551 471 579 591 711 795 819 927 1011 1023 1119 1239 1347 1371 1659 1695 1755 1803 1947 111 147 195 267 411

[出力例]

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

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

int main(){
    
    // 1. 入力情報.
    int N;
    char c[5050];
    scanf("%d %s", &N, c);
    string s(c);
    
    // 2. L の 位置は？
    int L = -1;
    rep(i, N){
        if(s[i] == 'p'){
            L = i;
            break;
        }
    }
    
    // 3. 例外.
    if(L == -1){
        printf("%s\n", s.c_str());
        return 0;
    }
    
    // 4. 辞書順最小となる文字列は？
    string ans = s;
    repx(R, L, N){
        string l = s.substr(0, L);
        string m = s.substr(L, R - L + 1);
        string r = s.substr(R + 1, N - R - 1);
        reverse(all(m));
        rep(i, m.size()) m[i] = (m[i] == 'p') ? 'd' : 'p';
        ans = min(ans, l + m + r);
    }
    
    // 5. 出力.
    printf("%s\n", ans.c_str());
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc148/editorial/4772

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

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

int main(){

// 1. 入力情報.

int N;

char c[5050];

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

string s(c);

// 2. L の位置は？

int L = -1;

rep(i, N){

if(s[i] == 'p'){

L = i;

break;

}

// 3. 例外.

if(L == -1){

printf("%s\n", s.c_str());

return 0;

}

// 4. 辞書順最小となる文字列は？

string ans = s;

repx(R, L, N){

string l = s.substr(0, L);

string m = s.substr(L, R - L + 1);

string r = s.substr(R + 1, N - R - 1);

reverse(all(m));

rep(i, m.size()) m[i] = (m[i] == 'p') ? 'd' : 'p';

ans = min(ans, l + m + r);

}

// 5. 出力.

printf("%s\n", ans.c_str());

return 0;

}

[入力例]
6
dpdppd

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

[入力例]
3
ddd

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

[入力例]
11
ddpdpdppddp

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

[入力例]
3
dpp

[出力例]
ddd

[入力例]
30
pddpddpdpddddddpppdppddpppddpp

[出力例]
dddpddpdpddddddpppdppddpppddpp

[入力例]
100
pdddppdpdppdppddppdddddpdpdpdddppdpppdpdpdpdpppppdpdppppdppdppdddpdddppdpdppdpdpddppppddppdpddddpddp

[出力例]
dddddpdpdpdpdddpddpppdpdpdpppppddppddpddpdpddpppddpdppppdppdppdddpdddppdpdppdpdpddppppddppdpddddpddp

[入力例]

dpdppd

[出力例]

dddpdd

※AtCoderのテストケースより

[入力例]

ddd

[出力例]

ddd

※AtCoderのテストケースより

[入力例]

ddpdpdppddp

[出力例]

ddddpdpdddp

※AtCoderのテストケースより

[入力例]

dpp

[出力例]

ddd

[入力例]

pddpddpdpddddddpppdppddpppddpp

[出力例]

dddpddpdpddddddpppdppddpppddpp

[入力例]

100

pdddppdpdppdppddppdddddpdpdpdddppdpppdpdpdpdpppppdpdppppdppdppdddpdddppdpdppdpdpddppppddppdpddddpddp

[出力例]

dddddpdpdpdpdddpddpppdpdpdpppppddppddpddpdpddpppddpdppppdppdppdddpdddppdpdppdpdpddppppddppdpddddpddp

■参照サイト
AtCoder Regular Contest 148

2022年9月19日2022年9月19日

■感想.
1. 問題Dは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
※ 問題D は, 過去記事の実装を書き換えた内容になっている.
2. 念のため, 箱情報について, 座標圧縮を考慮した版と, 考慮しない版とを確認して, どちらも, 問題なさそうだと分かった.
3. 個人的には, セグメント木（Range Maximum Query）の復習が出来たので, 非常に良かったと思う.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

■C++版プログラム(問題D／AC版, 座標圧縮なし).

// 解き直し.
// https://img.atcoder.jp/data/abc/038/editorial.pdf
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;
using vp = vector<P>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define a first
#define b second
#define all(x) x.begin(), x.end()
int dp[101010];

// AtCoder Library(https://github.com/atcoder/ac-library/blob/master/atcoder/segtree.hpp)
// -> 一部改変(2021/02/05).
template<class S, S (*op)(S, S), S (*e)()> struct SegmentTree{
public:
    SegmentTree() : SegmentTree(0){}
    explicit SegmentTree(int n) : SegmentTree(vector<S>(n, e())){}
    explicit SegmentTree(const vector<S>& v) : _n(int(v.size())){
        log = 0;
        while((1 << log) < _n) log++;
        size = 1 << log;
        d = vector<S>(2 * size, e());
        rep(i, _n) d[size + i] = v[i];
        repr(i, size - 1, 1) update(i);
    }
    void set(int p, S x){
        assert(0 <= p && p < _n);
        p += size;
        d[p] = x;
        repx(i, 1, log + 1) update(p >> i);
    }
    S get(int p){
        assert(0 <= p && p < _n);
        return d[p + size];
    }
    S prod(int l, int r){
        assert(0 <= l && l <= r && r <= _n);
        S sml = e(), smr = e();
        l += size;
        r += size;
        while(l < r){
            if(l & 1) sml = op(sml, d[l++]);
            if(r & 1) smr = op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }
        return op(sml, smr);
    }
    S all_prod(){
        return d[1];
    }
private:
    int _n, size, log;
    vector<S> d;
    void update(int k){
        d[k] = op(d[2 * k], d[2 * k + 1]);
    }
};

static int RMaQ_nodef(int l, int r){
    return max(l, r);
}
static int RMaQ_ef(){
    return 0;
}
using RMaQ = SegmentTree<int, RMaQ_nodef, RMaQ_ef>;

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    vp v(N);
    rep(i, N){
        scanf("%d %d", &v[i].a, &v[i].b);
        v[i].b *= -1;
    }
    
    // 2. sort.
    sort(all(v));
    
    // 3. dp更新.
    // -> Segment Tree の中で, Range Maximum Query として, 対応.
    RMaQ seg(101010);
    rep(i, N){
        // 区間[0, -v[i].b) の 最大値 に, 1 を 加算.
        dp[i + 1] = seg.prod(0, -v[i].b) + 1;
        
        // 前回以前分.
        int bef = seg.get(-v[i].b);
        
        // dp[i + 1] を 保存.
        seg.set(-v[i].b, max(bef, dp[i + 1]));
    }
    
    // 4. 出力.
    // -> dp[N] ではないことに注意.
    printf("%d\n", seg.prod(0, 101010));
    return 0;
    
}

100

101

102

103

104

105

106

// 解き直し.

// https://img.atcoder.jp/data/abc/038/editorial.pdf

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using P = pair<int, int>;

using vp = vector;

#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 a first

#define b second

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

int dp[101010];

// AtCoder Library(https://github.com/atcoder/ac-library/blob/master/atcoder/segtree.hpp)

// -> 一部改変(2021/02/05).

template<class S, S (*op)(S, S), S (*e)()> struct SegmentTree{

public:

SegmentTree() : SegmentTree(0){}

explicit SegmentTree(int n) : SegmentTree(vector<S>(n, e())){}

explicit SegmentTree(const vector<S>& v) : _n(int(v.size())){

log = 0;

while((1 << log) < _n) log++;

size = 1 << log;

d = vector<S>(2 * size, e());

rep(i, _n) d[size + i] = v[i];

repr(i, size - 1, 1) update(i);

}

void set(int p, S x){

assert(0 <= p && p < _n);

p += size;

d[p] = x;

repx(i, 1, log + 1) update(p >> i);

}

S get(int p){

assert(0 <= p && p < _n);

return d[p + size];

}

S prod(int l, int r){

assert(0 <= l && l <= r && r <= _n);

S sml = e(), smr = e();

l += size;

r += size;

while(l < r){

if(l & 1) sml = op(sml, d[l++]);

if(r & 1) smr = op(d[--r], smr);

l >>= 1;

r >>= 1;

}

return op(sml, smr);

}

S all_prod(){

return d[1];

}

private:

int _n, size, log;

vector<S> d;

void update(int k){

d[k] = op(d[2 * k], d[2 * k + 1]);

}

};

static int RMaQ_nodef(int l, int r){

return max(l, r);

}

static int RMaQ_ef(){

return 0;

}

using RMaQ = SegmentTree<int, RMaQ_nodef, RMaQ_ef>;

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

vp v(N);

rep(i, N){

scanf("%d %d", &v[i].a, &v[i].b);

v[i].b *= -1;

}

// 2. sort.

sort(all(v));

// 3. dp更新.

// -> Segment Tree の中で, Range Maximum Query として, 対応.

RMaQ seg(101010);

rep(i, N){

// 区間[0, -v[i].b) の最大値に, 1 を加算.

dp[i + 1] = seg.prod(0, -v[i].b) + 1;

// 前回以前分.

int bef = seg.get(-v[i].b);

// dp[i + 1] を保存.

seg.set(-v[i].b, max(bef, dp[i + 1]));

}

// 4. 出力.

// -> dp[N] ではないことに注意.

printf("%d\n", seg.prod(0, 101010));

return 0;

}

■C++版プログラム(問題D／AC版, 座標圧縮あり).

// AC版.
// 解き直し.
// https://img.atcoder.jp/data/abc/038/editorial.pdf
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;
using vp = vector<P>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define a first
#define b second
#define all(x) x.begin(), x.end()
#define pb push_back
int dp[101010];

// AtCoder Library(https://github.com/atcoder/ac-library/blob/master/atcoder/segtree.hpp)
// -> 一部改変(2021/02/05).
template<class S, S (*op)(S, S), S (*e)()> struct SegmentTree{
public:
    SegmentTree() : SegmentTree(0){}
    explicit SegmentTree(int n) : SegmentTree(vector<S>(n, e())){}
    explicit SegmentTree(const vector<S>& v) : _n(int(v.size())){
        log = 0;
        while((1 << log) < _n) log++;
        size = 1 << log;
        d = vector<S>(2 * size, e());
        rep(i, _n) d[size + i] = v[i];
        repr(i, size - 1, 1) update(i);
    }
    void set(int p, S x){
        assert(0 <= p && p < _n);
        p += size;
        d[p] = x;
        repx(i, 1, log + 1) update(p >> i);
    }
    S get(int p){
        assert(0 <= p && p < _n);
        return d[p + size];
    }
    S prod(int l, int r){
        assert(0 <= l && l <= r && r <= _n);
        S sml = e(), smr = e();
        l += size;
        r += size;
        while(l < r){
            if(l & 1) sml = op(sml, d[l++]);
            if(r & 1) smr = op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }
        return op(sml, smr);
    }
    S all_prod(){
        return d[1];
    }
private:
    int _n, size, log;
    vector<S> d;
    void update(int k){
        d[k] = op(d[2 * k], d[2 * k + 1]);
    }
};

static int RMaQ_nodef(int l, int r){
    return max(l, r);
}
static int RMaQ_ef(){
    return 0;
}
using RMaQ = SegmentTree<int, RMaQ_nodef, RMaQ_ef>;

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    vp v(N);
    map<int, int> ox, oy;
    rep(i, N){
        scanf("%d %d", &v[i].a, &v[i].b);
        ox[v[i].a] = 0;
        oy[v[i].b] = 0;
    }
    
    // 2. 座標圧縮.
    int idx = 0;
    for(auto &p : ox) p.b = ++idx;
    idx = 0;
    for(auto &p : oy) p.b = ++idx;
    
    // 3. 箱情報修正.
    vp boxes;
    for(auto &p : v) boxes.pb({ox[p.a], -oy[p.b]});
    
    // 4. sort.
    sort(all(boxes));
    
    // 5. dp更新.
    // -> Segment Tree の中で, Range Maximum Query として, 対応.
    RMaQ seg(101010);
    rep(i, N){
        // 区間[0, -v[i].b) の 最大値 に, 1 を 加算.
        dp[i + 1] = seg.prod(0, -boxes[i].b) + 1;
        
        // 前回以前分.
        int bef = seg.get(-boxes[i].b);
        
        // dp[i + 1] を 保存.
        seg.set(-boxes[i].b, max(bef, dp[i + 1]));
    }
    
    // 6. 出力.
    // -> dp[N] ではないことに注意.
    printf("%d\n", seg.prod(0, 101010));
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

// AC版.

// 解き直し.

// https://img.atcoder.jp/data/abc/038/editorial.pdf

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using P = pair<int, int>;

using vp = vector;

#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 a first

#define b second

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

#define pb push_back

int dp[101010];

// AtCoder Library(https://github.com/atcoder/ac-library/blob/master/atcoder/segtree.hpp)

// -> 一部改変(2021/02/05).

template<class S, S (*op)(S, S), S (*e)()> struct SegmentTree{

public:

SegmentTree() : SegmentTree(0){}

explicit SegmentTree(int n) : SegmentTree(vector<S>(n, e())){}

explicit SegmentTree(const vector<S>& v) : _n(int(v.size())){

log = 0;

while((1 << log) < _n) log++;

size = 1 << log;

d = vector<S>(2 * size, e());

rep(i, _n) d[size + i] = v[i];

repr(i, size - 1, 1) update(i);

}

void set(int p, S x){

assert(0 <= p && p < _n);

p += size;

d[p] = x;

repx(i, 1, log + 1) update(p >> i);

}

S get(int p){

assert(0 <= p && p < _n);

return d[p + size];

}

S prod(int l, int r){

assert(0 <= l && l <= r && r <= _n);

S sml = e(), smr = e();

l += size;

r += size;

while(l < r){

if(l & 1) sml = op(sml, d[l++]);

if(r & 1) smr = op(d[--r], smr);

l >>= 1;

r >>= 1;

}

return op(sml, smr);

}

S all_prod(){

return d[1];

}

private:

int _n, size, log;

vector<S> d;

void update(int k){

d[k] = op(d[2 * k], d[2 * k + 1]);

}

};

static int RMaQ_nodef(int l, int r){

return max(l, r);

}

static int RMaQ_ef(){

return 0;

}

using RMaQ = SegmentTree<int, RMaQ_nodef, RMaQ_ef>;

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

vp v(N);

map<int, int> ox, oy;

rep(i, N){

scanf("%d %d", &v[i].a, &v[i].b);

ox[v[i].a] = 0;

oy[v[i].b] = 0;

}

// 2. 座標圧縮.

int idx = 0;

for(auto &p : ox) p.b = ++idx;

idx = 0;

for(auto &p : oy) p.b = ++idx;

// 3. 箱情報修正.

vp boxes;

for(auto &p : v) boxes.pb({ox[p.a], -oy[p.b]});

// 4. sort.

sort(all(boxes));

// 5. dp更新.

// -> Segment Tree の中で, Range Maximum Query として, 対応.

RMaQ seg(101010);

rep(i, N){

// 区間[0, -v[i].b) の最大値に, 1 を加算.

dp[i + 1] = seg.prod(0, -boxes[i].b) + 1;

// 前回以前分.

int bef = seg.get(-boxes[i].b);

// dp[i + 1] を保存.

seg.set(-boxes[i].b, max(bef, dp[i + 1]));

}

// 6. 出力.

// -> dp[N] ではないことに注意.

printf("%d\n", seg.prod(0, 101010));

return 0;

}

[入力例]
5
8 8
5 3
2 2
4 2
2 1
※AtCoderテストケースより

[出力例]
4

[入力例]
8
3 1000
2 3
3 4
2 999
4 7
5 4
1 998
1 2

[出力例]
4

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

[出力例]
7

[入力例]
20
116 95
98 55
32 25
10 77
34 4
107 91
84 68
29 81
59 48
13 2
79 49
102 32
61 7
87 72
98 2
57 10
30 111
95 80
80 71
22 90

[出力例]
10

[入力例]
100
6031 2801
10151 8318
2192 3196
2379 5492
10246 11130
10065 10946
7763 8183
5729 6839
5341 9782
7726 10238
10825 10302
1604 5527
4842 6474
1393 7985
2584 12054
7045 10173
8557 6642
3391 6095
3499 2723
5252 3927
10494 9438
8839 766
3722 10274
7664 11264
812 1194
1154 3009
10013 10308
5285 9462
4586 3170
12060 2236
4342 5614
11035 8784
4231 11163
1980 3499
2316 10547
6582 1417
3239 4104
1381 7185
9779 8737
11792 10898
6135 5841
6292 46
3056 7476
1625 5051
10917 1602
2583 5298
12313 3842
53 8354
10625 4448
11271 584
4941 11890
6551 11988
7659 12104
11194 1147
9745 4446
9172 9747
4449 6324
10246 2878
3616 1752
3451 9236
3599 10505
6948 10871
4468 1146
148 12336
6728 1059
4602 4125
3056 3552
4651 9292
8904 11572
11476 11109
7336 8777
6145 9292
4917 9631
530 678
4333 11569
7502 3835
10436 7692
1838 3656
10749 8330
10101 1870
7952 2956
12261 4401
10132 3537
10100 5929
5591 10414
10089 986
3844 10329
8708 6312
2093 2806
11288 9057
6507 11709
9249 3108
3487 8066
7628 11532
1169 10729
6629 2277
2563 4960
440 3836
11544 11883
12215 875

[出力例]
17

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

[入力例]

8 8

5 3

2 2

4 2

2 1

※AtCoderテストケースより

[出力例]

[入力例]

3 1000

2 3

3 4

2 999

4 7

5 4

1 998

1 2

[出力例]

[入力例]

1 2

2 3

5 6

3 4

4 3

4 7

8 9

10 12

7 8

4 4

[出力例]

[入力例]

116 95

98 55

32 25

10 77

34 4

107 91

84 68

29 81

59 48

13 2

79 49

102 32

61 7

87 72

98 2

57 10

30 111

95 80

80 71

22 90

[出力例]

[入力例]

100

6031 2801

10151 8318

2192 3196

2379 5492

10246 11130

10065 10946

7763 8183

5729 6839

5341 9782

7726 10238

10825 10302

1604 5527

4842 6474

1393 7985

2584 12054

7045 10173

8557 6642

3391 6095

3499 2723

5252 3927

10494 9438

8839 766

3722 10274

7664 11264

812 1194

1154 3009

10013 10308

5285 9462

4586 3170

12060 2236

4342 5614

11035 8784

4231 11163

1980 3499

2316 10547

6582 1417

3239 4104

1381 7185

9779 8737

11792 10898

6135 5841

6292 46

3056 7476

1625 5051

10917 1602

2583 5298

12313 3842

53 8354

10625 4448

11271 584

4941 11890

6551 11988

7659 12104

11194 1147

9745 4446

9172 9747

4449 6324

10246 2878

3616 1752

3451 9236

3599 10505

6948 10871

4468 1146

148 12336

6728 1059

4602 4125

3056 3552

4651 9292

8904 11572

11476 11109

7336 8777

6145 9292

4917 9631

530 678

4333 11569

7502 3835

10436 7692

1838 3656

10749 8330

10101 1870

7952 2956

12261 4401

10132 3537

10100 5929

5591 10414

10089 986

3844 10329

8708 6312

2093 2806

11288 9057

6507 11709

9249 3108

3487 8066

7628 11532

1169 10729

6629 2277

2563 4960

440 3836

11544 11883

12215 875

[出力例]

■参照サイト
AtCoder Beginner Contest 038
パ研合宿2020 第1日「SpeedRun」／N – 背の順解説／セグメント木（Range Minimum Query）の使い方を参考にしました

2022年9月17日

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

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

■感想.
1. 問題Fは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 二分探索(応用版, 小数点含む) の復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/abc151/editorial.pdf
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using P = pair<double, double>;
using vp = vector<P>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
#define a first
#define b second
const double EPS = 1e-8;

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    vp o(N);
    double xMax = 0.0;
    double xMin = 1000.0;
    double yMax = 0.0;
    double yMin = 1000.0;
    rep(i, N){
        scanf("%lf %lf", &o[i].a, &o[i].b);
        
        // 二分探索 の 上限 を 設定する時に利用.
        xMax = max(xMax, o[i].a);
        xMin = min(xMin, o[i].a);
        yMax = max(yMax, o[i].b);
        yMin = min(yMin, o[i].b);
    }
    
    // 2. 評価関数.
    auto f = [&](double r) -> bool {
        // 2-1. 交点を全列挙.
        vp ps;
        rep(i, N){
            repx(j, i + 1, N){
                // 二点間の差分.
                double dx = o[i].a - o[j].a;
                double dy = o[i].b - o[j].b;
                
                // 交点(二つ)が, 無い場合.
                if(r * r * 4.0 + EPS - (dx * dx + dy * dy) < 0.0) return false;
                
                // 二つの交点間(距離 h).
                double h = sqrt(r * r * 4.0 - (dx * dx + dy * dy)) / 2.0;
                
                // 垂直方向(ベクトル, 二つ).
                double n = hypot(dx, dy);
                P v1 = {-dy / n * h, +dx / n * h};
                P v2 = {+dy / n * h, -dx / n * h};
                
                // 交点(二つ).
                double cx = (o[i].a + o[j].a) / 2.0;
                double cy = (o[i].b + o[j].b) / 2.0;
                P p1 = {cx + v1.a, cy + v1.b};
                P p2 = {cx + v2.a, cy + v2.b};
                
                // 保存.
                ps.pb(p1);
                ps.pb(p2);
            }
        }
        
        // 2-2. 判定.
        for(auto &p : ps){
            // N個の点から, 距離が, R以下のものがいくつあるか？
            int res = 0;
            rep(i, N){
                double d2 = (o[i].a - p.a) * (o[i].a - p.a) + (o[i].b - p.b) * (o[i].b - p.b);
                if(d2 <= r * r + EPS) ++res;
            }
            
            // 判定結果(OK)
            // -> N個の点からの距離が, いずれも, R以下のものが見つかった.
            if(res == N) return true;
        }
        
        // 2-3. 判定結果(NG).
        return false;
    };
    
    // 3. 二分探索で確認してみる.
    double l = 0.0, h = hypot(xMax - xMin, yMax - yMin);
    while(EPS < abs(h - l)){
        double m = (h + l) / 2.0;
        if(f(m)) h = m;
        else     l = m;
    }
    
    // 4. 出力.
    printf("%.15lf\n", h);
    return 0;
    
}

100

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using P = pair<double, double>;

using vp = vector;

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

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

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

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

#define pb push_back

#define a first

#define b second

const double EPS = 1e-8;

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

vp o(N);

double xMax = 0.0;

double xMin = 1000.0;

double yMax = 0.0;

double yMin = 1000.0;

rep(i, N){

scanf("%lf %lf", &o[i].a, &o[i].b);

// 二分探索の上限を設定する時に利用.

xMax = max(xMax, o[i].a);

xMin = min(xMin, o[i].a);

yMax = max(yMax, o[i].b);

yMin = min(yMin, o[i].b);

}

// 2. 評価関数.

auto f = [&](double r) -> bool {

// 2-1. 交点を全列挙.

vp ps;

rep(i, N){

repx(j, i + 1, N){

// 二点間の差分.

double dx = o[i].a - o[j].a;

double dy = o[i].b - o[j].b;

// 交点(二つ)が, 無い場合.

if(r * r * 4.0 + EPS - (dx * dx + dy * dy) < 0.0) return false;

// 二つの交点間(距離 h).

double h = sqrt(r * r * 4.0 - (dx * dx + dy * dy)) / 2.0;

// 垂直方向(ベクトル, 二つ).

double n = hypot(dx, dy);

P v1 = {-dy / n * h, +dx / n * h};

P v2 = {+dy / n * h, -dx / n * h};

// 交点(二つ).

double cx = (o[i].a + o[j].a) / 2.0;

double cy = (o[i].b + o[j].b) / 2.0;

P p1 = {cx + v1.a, cy + v1.b};

P p2 = {cx + v2.a, cy + v2.b};

// 保存.

ps.pb(p1);

ps.pb(p2);

}

// 2-2. 判定.

for(auto &p : ps){

// N個の点から, 距離が, R以下のものがいくつあるか？

int res = 0;

rep(i, N){

double d2 = (o[i].a - p.a) * (o[i].a - p.a) + (o[i].b - p.b) * (o[i].b - p.b);

if(d2 <= r * r + EPS) ++res;

}

// 判定結果(OK)

// -> N個の点からの距離が, いずれも, R以下のものが見つかった.

if(res == N) return true;

}

// 2-3. 判定結果(NG).

return false;

};

// 3. 二分探索で確認してみる.

double l = 0.0, h = hypot(xMax - xMin, yMax - yMin);

while(EPS < abs(h - l)){

double m = (h + l) / 2.0;

if(f(m)) h = m;

else l = m;

}

// 4. 出力.

printf("%.15lf\n", h);

return 0;

}

[入力例]
2
0 0
1 0

[出力例]
0.500000000000000000

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

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

[出力例]
0.707106781186548

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

[出力例]
6.726812023536855

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

[出力例]
1.000000000000000

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

[出力例]
5.590169945995560

[入力例]
15
65 110
65 61
141 101
101 116
56 107
151 109
91 69
120 99
84 160
147 79
126 83
171 118
130 98
91 169
157 170

[出力例]
71.317950059760392

[入力例]
50
389 163
517 301
405 508
358 278
264 430
470 428
154 510
354 352
73 506
125 506
104 179
160 295
194 380
240 184
490 98
470 22
169 316
117 180
392 436
201 51
240 214
265 462
296 455
137 194
495 217
469 505
195 186
288 104
141 511
276 195
297 156
308 67
180 264
171 466
22 118
31 447
107 378
40 111
141 442
40 445
154 413
248 268
158 24
65 412
217 109
462 427
331 334
281 233
443 414
470 488

[出力例]
312.995606999176516

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

[入力例]

0 0

1 0

[出力例]

0.500000000000000000

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

0.500000000000000

[入力例]

0 0

0 1

1 0

[出力例]

0.707106781186548

[入力例]

10 9

5 9

2 0

0 0

2 7

3 3

2 5

10 0

3 7

1 9

[出力例]

6.726812023536855

[入力例]

1 0

2 0

3 0

[出力例]

1.000000000000000

[入力例]

8 7

5 3

9 8

10 2

0 7

[出力例]

5.590169945995560

[入力例]

65 110

65 61

141 101

101 116

56 107

151 109

91 69

120 99

84 160

147 79

126 83

171 118

130 98

91 169

157 170

[出力例]

71.317950059760392

[入力例]

389 163

517 301

405 508

358 278

264 430

470 428

154 510

354 352

73 506

125 506

104 179

160 295

194 380

240 184

490 98

470 22

169 316

117 180

392 436

201 51

240 214

265 462

296 455

137 194

495 217

469 505

195 186

288 104

141 511

276 195

297 156

308 67

180 264

171 466

22 118

31 447

107 378

40 111

141 442

40 445

154 413

248 268

158 24

65 412

217 109

462 427

331 334

281 233

443 414

470 488

[出力例]

312.995606999176516

■参照サイト
AtCoder Beginner Contest 151

2022年9月15日2022年9月15日

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

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

■感想.
1. 問題Fは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 数列に関する性質を学習できたので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/abc147/editorial.pdf
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using P = pair<LL, LL>;
using vp = vector<P>;
using vvp = vector<vp>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
#define a first
#define b second
#define all(x) x.begin(), x.end()

int main(){
    
    // 1. 入力情報.
    LL N, X, D;
    scanf("%lld %lld %lld", &N, &X, &D);
    
    // 2. 例外.
    if(D == 0){
        printf("%lld\n", (X == 0) ? 1LL : N + 1);
        return 0;
    }
    
    // 3. 符号調整.
    if(D < 0){
        X *= -1;
        D *= -1;
    }
    
    // 4. 座標圧縮.
    // -> k * X mod D の 取り得る値を保存.
    map<LL, int> o;
    rep(k, N + 1) o[k * X % D] = 0;
    int idx = -1;
    for(auto &p : o) p.b = ++idx;
    
    // 5. 区間保存(k * X mod D ごと).
    vvp v(idx + 1);
    rep(k, N + 1){
        // 区間[l, r] の 計算.
        LL l = k ? (LL)k * (LL)(k - 1) / 2 : 0;
        LL r = k ? (LL)(k * N) - (LL)k * (LL)(k + 1) / 2 : 0;
        l *= D;
        l += k * X;
        r *= D;
        r += k * X;
        
        // 保存.
        v[o[k * X % D]].pb({l, r});
    }
    
    // 6. sort(k * X mod D ごと).
    rep(i, idx + 1){
        // sort.
        sort(all(v[i]));
        
        // 番兵.
        P p = v[i].back();
        v[i].pb({p.b + 202020202020202020, p.b + 202020202020202020});
    }
    
    // 7. 集計.
    LL ans = 0;
    rep(i, idx + 1){
        // 前回分.
        LL lBef = v[i][0].a;
        LL rBef = v[i][0].b;
        
        // 各区間の大小関係を比較して, 集計.
        repx(j, 1, v[i].size()){
            // 今回分.
           LL lCur = v[i][j].a;
           LL rCur = v[i][j].b;
           
           // 区間が連結してない場合.
           if(rBef < lCur){
               ans += (rBef - lBef + D) / D;
               lBef = lCur;
               rBef = rCur;
               continue;
           }
           
           // 区間が連結している場合.
           rBef = max(rBef, rCur);
        }
    }
    
    // 8. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using P = pair<LL, LL>;

using vp = vector;

using vvp = vector<vp>;

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

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

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

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

#define pb push_back

#define a first

#define b second

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

int main(){

// 1. 入力情報.

LL N, X, D;

scanf("%lld %lld %lld", &N, &X, &D);

// 2. 例外.

if(D == 0){

printf("%lld\n", (X == 0) ? 1LL : N + 1);

return 0;

}

// 3. 符号調整.

if(D < 0){

X *= -1;

D *= -1;

}

// 4. 座標圧縮.

// -> k * X mod D の取り得る値を保存.

map<LL, int> o;

rep(k, N + 1) o[k * X % D] = 0;

int idx = -1;

for(auto &p : o) p.b = ++idx;

// 5. 区間保存(k * X mod D ごと).

vvp v(idx + 1);

rep(k, N + 1){

// 区間[l, r] の計算.

LL l = k ? (LL)k * (LL)(k - 1) / 2 : 0;

LL r = k ? (LL)(k * N) - (LL)k * (LL)(k + 1) / 2 : 0;

l *= D;

l += k * X;

r *= D;

r += k * X;

// 保存.

v[o[k * X % D]].pb({l, r});

}

// 6. sort(k * X mod D ごと).

rep(i, idx + 1){

// sort.

sort(all(v[i]));

// 番兵.

P p = v[i].back();

v[i].pb({p.b + 202020202020202020, p.b + 202020202020202020});

}

// 7. 集計.

LL ans = 0;

rep(i, idx + 1){

// 前回分.

LL lBef = v[i][0].a;

LL rBef = v[i][0].b;

// 各区間の大小関係を比較して, 集計.

repx(j, 1, v[i].size()){

// 今回分.

LL lCur = v[i][j].a;

LL rCur = v[i][j].b;

// 区間が連結してない場合.

if(rBef < lCur){

ans += (rBef - lBef + D) / D;

lBef = lCur;

rBef = rCur;

continue;

}

// 区間が連結している場合.

rBef = max(rBef, rCur);

}

// 8. 出力.

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

return 0;

}

[入力例]
3 4 2

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

[入力例]
2 3 -3

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

[入力例]
100 14 20

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

[入力例]
4 3 10

[出力例]
15

[入力例]
7 5 -3

[出力例]
43

[入力例]
314 159 265

[出力例]
246596

[入力例]
2022 -9 15

[出力例]
10210074

[入力例]
2019 1208 -2100

[出力例]
1007787494

[入力例]
1234 567 890

[出力例]
313181180

[入力例]
123456 20202020 30303030

[出力例]
22862137621

[入力例]

3 4 2

[出力例]

※AtCoderテストケースより

[入力例]

2 3 -3

[出力例]

※AtCoderテストケースより

[入力例]

100 14 20

[出力例]

49805

※AtCoderテストケースより

[入力例]

4 3 10

[出力例]

[入力例]

7 5 -3

[出力例]

[入力例]

314 159 265

[出力例]

246596

[入力例]

2022 -9 15

[出力例]

10210074

[入力例]

2019 1208 -2100

[出力例]

1007787494

[入力例]

1234 567 890

[出力例]

313181180

[入力例]

123456 20202020 30303030

[出力例]

22862137621

■参照サイト
AtCoder Beginner Contest 147

2022年9月13日

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

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

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

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

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

// 解き直し.
// https://img.atcoder.jp/abc145/editorial.pdf
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
const LL INF = 202020202020202020;
LL dp[303][303], h[303];

int main(){
    
    // 1. 入力情報.
    int N, K;
    scanf("%d %d", &N, &K);
    rep(i, N) scanf("%lld", &h[i + 1]);
    
    // 2. 初期化.
    rep(i, N + 1) repx(j, 1, N + 1) dp[i][j] = INF;
    repx(i, 1, N + 1) dp[i][1] = h[i];
    
    // 3. dp更新.
    LL ans = INF;
    repx(x, 1, N + 1){
        // 最も右の項の番号が, x で, 削除しない項の集合サイズが, y の 時.
        repx(y, 2, x + 1) repx(i, y - 1, x) dp[x][y] = min(dp[x][y], dp[i][y - 1] + max(0LL, h[x] - h[i]));
        
        // 最小値更新.
        ans = min(ans, dp[x][N - K]);
    }
    
    // 4. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

const LL INF = 202020202020202020;

LL dp[303][303], h[303];

int main(){

// 1. 入力情報.

int N, K;

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

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

// 2. 初期化.

rep(i, N + 1) repx(j, 1, N + 1) dp[i][j] = INF;

repx(i, 1, N + 1) dp[i][1] = h[i];

// 3. dp更新.

LL ans = INF;

repx(x, 1, N + 1){

// 最も右の項の番号が, x で, 削除しない項の集合サイズが, y の時.

repx(y, 2, x + 1) repx(i, y - 1, x) dp[x][y] = min(dp[x][y], dp[i][y - 1] + max(0LL, h[x] - h[i]));

// 最小値更新.

ans = min(ans, dp[x][N - K]);

}

// 4. 出力.

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

return 0;

}

[入力例]
4 1
2 3 4 1

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

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

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

[入力例]
10 0
1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000

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

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

[出力例]
5

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

[出力例]
33

[入力例]
100 10
110 127 132 54 129 154 141 161 103 115 129 79 156 174 138 102 114 101 112 129 140 123 137 68 90 83 132 121 147 145 85 149 153 58 149 117 151 156 127 135 167 167 152 56 68 115 78 105 152 76 141 71 145 127 151 70 104 111 123 68 63 76 66 75 125 149 54 153 61 65 64 188 78 113 84 185 162 124 145 137 138 153 73 96 127 161 137 50 108 98 127 134 116 80 153 106 151 62 99 95

[出力例]
1234

[入力例]
300 77
682 884 1295 1125 1328 725 1635 623 1019 1447 855 1361 859 676 670 1736 1032 1062 1411 1648 974 555 812 542 1129 1638 1618 1720 513 575 1067 521 725 1000 1336 1592 1214 532 1089 782 1067 1741 604 1503 591 1584 971 1039 1240 1638 1169 739 1683 730 1545 1666 838 1243 1341 1140 576 829 1155 552 514 1728 522 721 1083 560 992 1262 982 865 556 1046 703 1040 1225 1367 785 1465 868 566 1507 572 1704 1654 862 1050 881 774 973 1181 1224 997 986 662 1379 803 651 1189 663 1640 1458 902 747 1398 1076 1457 1284 1749 1018 641 1182 1215 797 1289 1395 1062 1000 1027 1013 1019 1424 1739 1714 1610 799 620 1344 1196 1315 798 1000 773 909 1188 861 1540 1331 795 836 1000 1263 893 599 1249 1290 1404 1117 1265 1584 1340 1545 981 1320 903 851 1239 666 1029 612 1325 764 1369 984 1164 867 1368 556 1136 1019 1119 1035 604 1052 858 734 656 1253 1487 1371 864 1324 1000 943 679 1120 510 1000 547 1605 1029 610 1183 1339 1500 843 820 756 834 1565 526 1123 1719 603 1581 761 1654 1346 974 643 1400 543 1749 1168 782 1258 836 1297 1379 1375 1521 1319 1312 1698 1617 1347 1009 616 1038 1281 775 1267 1619 1015 826 1000 780 1012 1404 833 880 999 766 1085 601 1114 1036 1000 636 1004 1658 1048 1694 768 1166 828 1033 1366 1020 1252 1564 524 1456 687 1634 1109 506 1395 934 1498 1704 1000 1639 557 967 1009 1249 1440 1691 1450 1660 987 774 1569 1596 1453 1639 1734 673 1282 1187 549 1430 1149 1367 959 994

[出力例]
23456

[入力例]

4 1

2 3 4 1

[出力例]

※AtCoderテストケースより

[入力例]

6 2

8 6 9 1 2 1

[出力例]

※AtCoderテストケースより

[入力例]

10 0

1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000

[出力例]

4999999996

※AtCoderテストケースより

[入力例]

5 0

1 2 3 4 5

[出力例]

[入力例]

25 5

9 5 10 11 1 13 9 6 1 9 7 14 3 12 3 6 10 12 3 2 1 2 7 6 8

[出力例]

[入力例]

100 10

110 127 132 54 129 154 141 161 103 115 129 79 156 174 138 102 114 101 112 129 140 123 137 68 90 83 132 121 147 145 85 149 153 58 149 117 151 156 127 135 167 167 152 56 68 115 78 105 152 76 141 71 145 127 151 70 104 111 123 68 63 76 66 75 125 149 54 153 61 65 64 188 78 113 84 185 162 124 145 137 138 153 73 96 127 161 137 50 108 98 127 134 116 80 153 106 151 62 99 95

[出力例]

1234

[入力例]

300 77

682 884 1295 1125 1328 725 1635 623 1019 1447 855 1361 859 676 670 1736 1032 1062 1411 1648 974 555 812 542 1129 1638 1618 1720 513 575 1067 521 725 1000 1336 1592 1214 532 1089 782 1067 1741 604 1503 591 1584 971 1039 1240 1638 1169 739 1683 730 1545 1666 838 1243 1341 1140 576 829 1155 552 514 1728 522 721 1083 560 992 1262 982 865 556 1046 703 1040 1225 1367 785 1465 868 566 1507 572 1704 1654 862 1050 881 774 973 1181 1224 997 986 662 1379 803 651 1189 663 1640 1458 902 747 1398 1076 1457 1284 1749 1018 641 1182 1215 797 1289 1395 1062 1000 1027 1013 1019 1424 1739 1714 1610 799 620 1344 1196 1315 798 1000 773 909 1188 861 1540 1331 795 836 1000 1263 893 599 1249 1290 1404 1117 1265 1584 1340 1545 981 1320 903 851 1239 666 1029 612 1325 764 1369 984 1164 867 1368 556 1136 1019 1119 1035 604 1052 858 734 656 1253 1487 1371 864 1324 1000 943 679 1120 510 1000 547 1605 1029 610 1183 1339 1500 843 820 756 834 1565 526 1123 1719 603 1581 761 1654 1346 974 643 1400 543 1749 1168 782 1258 836 1297 1379 1375 1521 1319 1312 1698 1617 1347 1009 616 1038 1281 775 1267 1619 1015 826 1000 780 1012 1404 833 880 999 766 1085 601 1114 1036 1000 636 1004 1658 1048 1694 768 1166 828 1033 1366 1020 1252 1564 524 1456 687 1634 1109 506 1395 934 1498 1704 1000 1639 557 967 1009 1249 1440 1691 1450 1660 987 774 1569 1596 1453 1639 1734 673 1282 1187 549 1430 1149 1367 959 994

[出力例]

23456

■参照サイト
AtCoder Beginner Contest 145

2022年9月12日

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

C++の練習を兼ねて, AtCoder Beginner Contest 145 の問題E (All-you-can-eat) を解いてみた.

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

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

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

// 解き直し.
// https://img.atcoder.jp/abc145/editorial.pdf
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;
using vp = vector<P>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define a first
#define b second
#define all(x) x.begin(), x.end()
int dp[3030][3030];

int main(){
    
    // 1. 入力情報.
    int N, T;
    scanf("%d %d", &N, &T);
    vp v(N);
    rep(i, N) scanf("%d %d", &v[i].a, &v[i].b);
    
    // 2. sort.
    sort(all(v));
    
    // 3. dp更新.
    rep(i, N){
        // 最後の注文以外(時刻 T - 1 まで).
        rep(j, T){
            int t = j - v[i].a;
            dp[i + 1][j] = (t >= 0) ? max(dp[i][j], dp[i][t] + v[i].b) : dp[i][j];
        }
        
        // 最後の注文(時刻 T).
        dp[i + 1][T] = max(dp[i][T], dp[i][T - 1] + v[i].b);
    }
    
    // 4. 出力.
    printf("%d\n", dp[N][T]);
    return 0;
    
}

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using P = pair<int, int>;

using vp = vector;

#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 a first

#define b second

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

int dp[3030][3030];

int main(){

// 1. 入力情報.

int N, T;

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

vp v(N);

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

// 2. sort.

sort(all(v));

// 3. dp更新.

rep(i, N){

// 最後の注文以外(時刻 T - 1 まで).

rep(j, T){

int t = j - v[i].a;

dp[i + 1][j] = (t >= 0) ? max(dp[i][j], dp[i][t] + v[i].b) : dp[i][j];

}

// 最後の注文(時刻 T).

dp[i + 1][T] = max(dp[i][T], dp[i][T - 1] + v[i].b);

}

// 4. 出力.

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

return 0;

}

[入力例]
2 60
10 10
100 100

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

[入力例]
3 60
10 10
10 20
10 30

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

[入力例]
3 60
30 10
30 20
30 30

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

[入力例]
10 100
15 23
20 18
13 17
24 12
18 29
19 27
23 21
18 20
27 15
22 25

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

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

[出力例]
17

[入力例]
15 100
12 47
63 60
22 58
81 30
77 115
66 61
77 83
6 99
5 80
89 41
33 16
18 112
22 44
18 28
55 67

[出力例]
555

[入力例]
50 1234
58 505
77 474
54 519
43 545
17 485
29 537
40 543
27 548
36 458
39 497
39 505
45 478
32 555
48 470
28 475
55 466
30 511
16 555
39 569
11 777
29 475
16 491
40 546
18 547
17 506
66 478
49 482
50 577
40 520
41 492
34 490
23 499
57 489
30 492
11 500
32 543
53 529
48 499
35 449
44 486
11 555
55 515
52 533
46 504
54 467
50 532
40 535
49 535
38 525
32 480

[出力例]
20000

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

[入力例]

2 60

10 10

100 100

[出力例]

110

※AtCoderテストケースより

[入力例]

3 60

10 10

10 20

10 30

[出力例]

※AtCoderテストケースより

[入力例]

3 60

30 10

30 20

30 30

[出力例]

※AtCoderテストケースより

[入力例]

10 100

15 23

20 18

13 17

24 12

18 29

19 27

23 21

18 20

27 15

22 25

[出力例]

145

※AtCoderテストケースより

[入力例]

6 8

1 1

3 5

2 3

4 6

1 2

3 3

[出力例]

[入力例]

15 100

12 47

63 60

22 58

81 30

77 115

66 61

77 83

6 99

5 80

89 41

33 16

18 112

22 44

18 28

55 67

[出力例]

555

[入力例]

50 1234

58 505

77 474

54 519

43 545

17 485

29 537

40 543

27 548

36 458

39 497

39 505

45 478

32 555

48 470

28 475

55 466

30 511

16 555

39 569

11 777

29 475

16 491

40 546

18 547

17 506

66 478

49 482

50 577

40 520

41 492

34 490

23 499

57 489

30 492

11 500

32 543

53 529

48 499

35 449

44 486

11 555

55 515

52 533

46 504

54 467

50 532

40 535

49 535

38 525

32 480

[出力例]

20000

■参照サイト
AtCoder Beginner Contest 145

2022年9月11日2022年9月11日

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

C++の練習を兼ねて, AtCoder Beginner Contest 141 の問題F (Xor Sum 3) を解いてみた.

■感想.
1. 問題Fは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 実装に苦労したものの, 行列の掃き出し法について復習出来たので, 非常に良かったと思う.
※ 過去問 AtCoder Regular Contest 054 C – 鯛焼きを参考にして, 掃き出し法の実装を進めてみたものの, 文字列ベースだと, TLE版になるため, 整数ベースで実装し直した版で, 提出している.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/abc141/editorial.pdf
// 過去問参照(AtCoder Regular Contest 054 C - 鯛焼き)
// https://atcoder.jp/contests/arc054/tasks/arc054_c
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vs = vector<string>;
using vl = vector<LL>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
#define all(x) x.begin(), x.end()
LL a[101010];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    LL nXor = 0; // 興味深くないbitを全て立てた整数.
    rep(i, N){
        scanf("%lld", &a[i]);
        nXor ^= a[i];
    }
    
    /* 
    // 2. 行列(文字列版).
    vs matrix;
    rep(i, N){
        string s;
        repr(j, 59, 0){
            if(nXor & (1LL << j)) s.pb('0');
            else                  s.pb(((a[i] >> j) & 1) + '0');
        }
        matrix.pb(s);
    }
    // puts("--- Matrix before update ---");
    // rep(i, N) printf("%s\n", matrix[i].c_str());
    */
    
    /* 
    // TLE版となるので, コメントアウト.
    // 3. 掃き出し法(mod2版).
    // https://ja.wikipedia.org/wiki/ガウスの消去法
    // 
    // ex.
    // [変更前行列]
    // 011001
    // 001001
    // 101011
    // 010110
    // 001100
    // 
    // [変更後行列]
    // 100001
    // 010000
    // 001001
    // 000101
    // 000011
    // 
    auto gauss = [&](vs &m, int N, int M) -> vs {
        // 3-1. 戻り値設定.
        vs ret = m;
        
        // 3-2. 各行を順次確認.
        rep(i, N){
            // 降順sort.
            sort(all(ret));
            reverse(all(ret));
            
            // 最初に, '1' となる位置.
            int at = M;
            rep(j, M){
                if(ret[i][j] == '1'){
                    at = j;
                    break;
                }
            }
            
            // 見つからなった場合.
            if(at == M) continue;
            
            // i行目以外(j行目)と比較して, 前項で求めた位置(列)に, '1' が 有れば, 掃き出す.
            rep(j, N){
                if(i != j && ret[j][at] == '1'){
                    // 操作対象を設定.
                    string o = ret[i]; // i行目.
                    string n = ret[j]; // j行目.
                    
                    // j行目の掃き出し.
                    rep(k, M) n[k] = '0' + ((n[k] - '0') ^ (o[k] - '0'));
                    
                    // j行目更新.
                    ret[j] = n;
                }
            }
        }
        
        // 3-3. 返却.
        return ret;
    };
    vs gMatrix = gauss(matrix, N, 60);
    // puts("--- Matrix after update ---");
    // rep(i, N) printf("%s\n", gMatrix[i].c_str());
    */
    
    /*
    // 4. 掃き出し法(mod2版, 計算量削減版).
    // -> TLE版(sub1_27.txt で, 2153[ms])となるので, コメントアウト.
    // https://ja.wikipedia.org/wiki/ガウスの消去法
    auto gauss = [&](vs &m, int N, int M) -> vs {
        // 4-1. 戻り値設定.
        vs ret = m;
        
        // 4-2. 60桁目 → 1桁目 で, 行標準形 を 目指す.
        repr(i, M - 1, 0){
            // 基準行.
            string bRow;
            string base(60, '0');
            base[M - 1 - i] = '1';
            string upper(60, '0');
            repx(j, M - 1 - i, M) upper[j] = '1';
            
            // sort.
            sort(all(ret));
            
            // 操作.
            rep(j, N){
                // Skip.
                if(ret[j] < base) continue;
                
                // 基準行設定.
                if(!bRow.size()){
                    if(ret[j] <= upper) bRow = ret[j];
                    continue;
                }
                
                // Skip.
                if(ret[j] > upper && ret[j][M - 1 - i] == '0') continue;
                
                // 基準行反映.
                rep(k, M) ret[j][k] = '0' + ((ret[j][k] - '0') ^ (bRow[k] - '0'));
            }
        }
        
        // 4-3. 返却.
        return ret;
    };
    vs gMatrix = gauss(matrix, N, 60);
    // puts("--- Matrix after update ---");
    // rep(i, N) printf("%s\n", gMatrix[i].c_str());
    */
    
    /*
    // 5. X'あおい の 最大値は？
    LL bXor = 0; 
    rep(i, N){
        LL cur = 0;
        repr(j, 59, 0) cur += (1LL << j) * (gMatrix[i][59 - j] - '0');
        bXor ^= cur;
    }
    */
    
    // 6. 行列(整数版).
    vl matrix;
    rep(i, N){
        LL cur = a[i];
        repr(j, 59, 0){
            LL bit = 1LL << j;
            if((nXor & bit) && (a[i] & bit)) cur -= bit;
        }
        matrix.pb(cur);
    }
    // puts("--- Matrix before update ---");
    // rep(i, N) printf("%lld\n", matrix[i]);
    
    // 7. 掃き出し法(mod2版, 文字列廃止, 計算量削減版).
    // https://ja.wikipedia.org/wiki/ガウスの消去法
    auto gauss = [&](vl &m, int N, int M) -> vl {
        // 7-1. 戻り値設定.
        vl ret = m;
        
        // 7-2. 60桁目 → 1桁目 で, 行標準形 を 目指す.
        repr(i, M - 1, 0){
            // 基準行.
            LL bRow = 0;
            LL base = 1LL << i;
            LL upper = (base << 1) - 1;
            
            // sort.
            sort(all(ret));
            
            // 操作.
            rep(j, N){
                // Skip.
                if(ret[j] < base) continue;
                
                // 基準行設定.
                if(!bRow){
                    if(ret[j] <= upper) bRow = ret[j];
                    continue;
                }
                
                // Skip.
                if(ret[j] > upper && !(ret[j] & base)) continue;
                
                // 基準行反映.
                ret[j] ^= bRow;
            }
        }
        
        // 7-3. 返却.
        return ret;
    };
    vl gMatrix = gauss(matrix, N, 60);
    // puts("--- Matrix after update ---");
    // rep(i, N) printf("%lld\n", gMatrix[i]);
    
    // 8. X'あおい の 最大値は？
    LL bXor = 0; 
    rep(i, N){
        LL cur = 0;
        repr(j, 59, 0) cur += (1LL << j) & gMatrix[i];
        bXor ^= cur;
    }
    
    // 9. 出力.
    printf("%lld\n", bXor + bXor + nXor);
    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

// 解き直し.

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

// 過去問参照(AtCoder Regular Contest 054 C - 鯛焼き)

// https://atcoder.jp/contests/arc054/tasks/arc054_c

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vs = vector<string>;

using vl = vector<LL>;

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

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

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

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

#define pb push_back

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

LL a[101010];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

LL nXor = 0; // 興味深くないbitを全て立てた整数.

rep(i, N){

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

nXor ^= a[i];

}

// 2. 行列(文字列版).

vs matrix;

rep(i, N){

string s;

repr(j, 59, 0){

if(nXor & (1LL << j)) s.pb('0');

else s.pb(((a[i] >> j) & 1) + '0');

}

matrix.pb(s);

}

// puts("--- Matrix before update ---");

// rep(i, N) printf("%s\n", matrix[i].c_str());

// TLE版となるので, コメントアウト.

// 3. 掃き出し法(mod2版).

// https://ja.wikipedia.org/wiki/ガウスの消去法

// ex.

// [変更前行列]

// 011001

// 001001

// 101011

// 010110

// 001100

// [変更後行列]

// 100001

// 010000

// 001001

// 000101

// 000011

auto gauss = [&](vs &m, int N, int M) -> vs {

// 3-1. 戻り値設定.

vs ret = m;

// 3-2. 各行を順次確認.

rep(i, N){

// 降順sort.

sort(all(ret));

reverse(all(ret));

// 最初に, '1' となる位置.

int at = M;

rep(j, M){

if(ret[i][j] == '1'){

at = j;

break;

}

// 見つからなった場合.

if(at == M) continue;

// i行目以外(j行目)と比較して, 前項で求めた位置(列)に, '1' が有れば, 掃き出す.

rep(j, N){

if(i != j && ret[j][at] == '1'){

// 操作対象を設定.

string o = ret[i]; // i行目.

string n = ret[j]; // j行目.

// j行目の掃き出し.

rep(k, M) n[k] = '0' + ((n[k] - '0') ^ (o[k] - '0'));

// j行目更新.

ret[j] = n;

}

// 3-3. 返却.

return ret;

};

vs gMatrix = gauss(matrix, N, 60);

// puts("--- Matrix after update ---");

// rep(i, N) printf("%s\n", gMatrix[i].c_str());

// 4. 掃き出し法(mod2版, 計算量削減版).

// -> TLE版(sub1_27.txt で, 2153[ms])となるので, コメントアウト.

// https://ja.wikipedia.org/wiki/ガウスの消去法

auto gauss = [&](vs &m, int N, int M) -> vs {

// 4-1. 戻り値設定.

vs ret = m;

// 4-2. 60桁目 → 1桁目で, 行標準形を目指す.

repr(i, M - 1, 0){

// 基準行.

string bRow;

string base(60, '0');

base[M - 1 - i] = '1';

string upper(60, '0');

repx(j, M - 1 - i, M) upper[j] = '1';

// sort.

sort(all(ret));

// 操作.

rep(j, N){

// Skip.

if(ret[j] < base) continue;

// 基準行設定.

if(!bRow.size()){

if(ret[j] <= upper) bRow = ret[j];

continue;

}

// Skip.

if(ret[j] > upper && ret[j][M - 1 - i] == '0') continue;

// 基準行反映.

rep(k, M) ret[j][k] = '0' + ((ret[j][k] - '0') ^ (bRow[k] - '0'));

}

// 4-3. 返却.

return ret;

};

vs gMatrix = gauss(matrix, N, 60);

// puts("--- Matrix after update ---");

// rep(i, N) printf("%s\n", gMatrix[i].c_str());

// 5. X'あおいの最大値は？

LL bXor = 0;

rep(i, N){

LL cur = 0;

repr(j, 59, 0) cur += (1LL << j) * (gMatrix[i][59 - j] - '0');

bXor ^= cur;

}

// 6. 行列(整数版).

vl matrix;

rep(i, N){

LL cur = a[i];

repr(j, 59, 0){

LL bit = 1LL << j;

if((nXor & bit) && (a[i] & bit)) cur -= bit;

}

matrix.pb(cur);

}

// puts("--- Matrix before update ---");

// rep(i, N) printf("%lld\n", matrix[i]);

// 7. 掃き出し法(mod2版, 文字列廃止, 計算量削減版).

// https://ja.wikipedia.org/wiki/ガウスの消去法

auto gauss = [&](vl &m, int N, int M) -> vl {

// 7-1. 戻り値設定.

vl ret = m;

// 7-2. 60桁目 → 1桁目で, 行標準形を目指す.

repr(i, M - 1, 0){

// 基準行.

LL bRow = 0;

LL base = 1LL << i;

LL upper = (base << 1) - 1;

// sort.

sort(all(ret));

// 操作.

rep(j, N){

// Skip.

if(ret[j] < base) continue;

// 基準行設定.

if(!bRow){

if(ret[j] <= upper) bRow = ret[j];

continue;

}

// Skip.

if(ret[j] > upper && !(ret[j] & base)) continue;

// 基準行反映.

ret[j] ^= bRow;

}

// 7-3. 返却.

return ret;

};

vl gMatrix = gauss(matrix, N, 60);

// puts("--- Matrix after update ---");

// rep(i, N) printf("%lld\n", gMatrix[i]);

// 8. X'あおいの最大値は？

LL bXor = 0;

rep(i, N){

LL cur = 0;

repr(j, 59, 0) cur += (1LL << j) & gMatrix[i];

bXor ^= cur;

}

// 9. 出力.

printf("%lld\n", bXor + bXor + nXor);

return 0;

}

[入力例]
3
3 6 5

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

[入力例]
4
23 36 66 65

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

[入力例]
20
1008288677408720767 539403903321871999 1044301017184589821 215886900497862655 504277496111605629 972104334925272829 792625803473366909 972333547668684797 467386965442856573 755861732751878143 1151846447448561405 467257771752201853 683930041385277311 432010719984459389 319104378117934975 611451291444233983 647509226592964607 251832107792119421 827811265410084479 864032478037725181

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

[入力例]
10
27 22 11 12 7 5 4 3 2 1

[出力例]
50

[入力例]
18
314 159 265 358 979 323 846 264 338 327 950 288 419 716 939 937 510 582

[出力例]
1204

[入力例]
50
34605 73340 57646 1818 49584 118833 110169 73623 90519 34931 51339 78836 54020 110920 12428 102502 86264 101668 123187 54134 40830 20657 30747 64207 33537 90037 68502 27555 119034 104789 47549 21622 33656 78834 104976 34375 78348 110133 39783 75735 23418 21824 77753 96235 22827 29758 35425 36413 25474 21908

[出力例]
233451

[入力例]
500
172 106 502 212 158 420 214 222 165 62 304 503 478 240 315 363 63 131 107 215 340 160 19 283 85 408 277 484 149 44 335 158 318 191 111 260 92 264 88 136 311 457 354 260 112 205 535 139 337 497 139 362 8 443 357 208 372 104 372 305 536 172 254 469 499 444 450 337 23 299 428 273 488 21 315 514 178 533 260 217 410 172 525 396 481 181 137 97 500 10 181 538 53 0 135 465 50 491 250 157 342 548 141 450 353 112 272 548 174 66 136 549 4 55 209 335 464 105 9 423 363 185 52 20 418 208 456 309 493 285 416 64 313 183 345 215 87 142 167 424 323 222 163 43 88 479 102 36 332 96 313 219 549 53 317 499 496 74 184 393 230 328 334 510 115 433 130 193 285 259 532 306 458 541 25 157 403 214 3 443 464 461 4 315 505 196 302 248 34 140 448 15 550 293 310 542 191 416 212 83 432 185 239 68 241 276 528 15 108 476 25 272 25 358 76 27 305 464 306 550 312 500 70 439 2 312 113 371 74 506 284 6 206 136 419 218 327 303 341 238 493 208 493 257 524 264 174 512 267 101 483 32 66 46 197 453 385 310 16 505 355 190 308 177 490 168 177 26 539 50 232 326 413 193 448 378 479 265 176 476 405 240 154 317 541 13 12 417 29 296 493 109 463 307 428 96 398 480 452 295 156 175 300 51 84 274 123 248 247 67 386 58 325 531 92 252 121 516 63 62 156 366 320 248 217 454 58 222 357 125 135 68 370 12 377 215 216 161 24 386 360 3 52 118 18 359 17 246 513 305 39 164 242 272 209 436 502 429 340 332 427 544 232 60 117 407 467 73 226 368 507 240 64 122 18 198 26 335 392 483 11 533 179 489 523 290 145 198 497 75 6 377 487 190 544 414 170 138 182 540 323 332 139 229 378 365 126 381 458 260 390 212 516 171 374 473 332 389 324 224 266 333 394 223 449 285 312 431 267 404 144 93 52 273 474 322 317 422 59 448 184 442 420 32 108 84 494 0 392 518 193 12 113 164 29 335 280 67 372 539 501 498 218 122 147 248 203 218 463 70 163 174 414 88 194 487 334 228 462 545 378 328 313 292 375 126 372 218 472 264 51 334 217 489 299 205 395 182 299 272

[出力例]
2023

[入力例]

3 6 5

[出力例]

※AtCoderのテストケースより

[入力例]

23 36 66 65

[出力例]

188

※AtCoderのテストケースより

[入力例]

1008288677408720767 539403903321871999 1044301017184589821 215886900497862655 504277496111605629 972104334925272829 792625803473366909 972333547668684797 467386965442856573 755861732751878143 1151846447448561405 467257771752201853 683930041385277311 432010719984459389 319104378117934975 611451291444233983 647509226592964607 251832107792119421 827811265410084479 864032478037725181

[出力例]

2012721721873704572

※AtCoderのテストケースより

[入力例]

27 22 11 12 7 5 4 3 2 1

[出力例]

[入力例]

314 159 265 358 979 323 846 264 338 327 950 288 419 716 939 937 510 582

[出力例]

1204

[入力例]

34605 73340 57646 1818 49584 118833 110169 73623 90519 34931 51339 78836 54020 110920 12428 102502 86264 101668 123187 54134 40830 20657 30747 64207 33537 90037 68502 27555 119034 104789 47549 21622 33656 78834 104976 34375 78348 110133 39783 75735 23418 21824 77753 96235 22827 29758 35425 36413 25474 21908

[出力例]

233451

[入力例]

500

172 106 502 212 158 420 214 222 165 62 304 503 478 240 315 363 63 131 107 215 340 160 19 283 85 408 277 484 149 44 335 158 318 191 111 260 92 264 88 136 311 457 354 260 112 205 535 139 337 497 139 362 8 443 357 208 372 104 372 305 536 172 254 469 499 444 450 337 23 299 428 273 488 21 315 514 178 533 260 217 410 172 525 396 481 181 137 97 500 10 181 538 53 0 135 465 50 491 250 157 342 548 141 450 353 112 272 548 174 66 136 549 4 55 209 335 464 105 9 423 363 185 52 20 418 208 456 309 493 285 416 64 313 183 345 215 87 142 167 424 323 222 163 43 88 479 102 36 332 96 313 219 549 53 317 499 496 74 184 393 230 328 334 510 115 433 130 193 285 259 532 306 458 541 25 157 403 214 3 443 464 461 4 315 505 196 302 248 34 140 448 15 550 293 310 542 191 416 212 83 432 185 239 68 241 276 528 15 108 476 25 272 25 358 76 27 305 464 306 550 312 500 70 439 2 312 113 371 74 506 284 6 206 136 419 218 327 303 341 238 493 208 493 257 524 264 174 512 267 101 483 32 66 46 197 453 385 310 16 505 355 190 308 177 490 168 177 26 539 50 232 326 413 193 448 378 479 265 176 476 405 240 154 317 541 13 12 417 29 296 493 109 463 307 428 96 398 480 452 295 156 175 300 51 84 274 123 248 247 67 386 58 325 531 92 252 121 516 63 62 156 366 320 248 217 454 58 222 357 125 135 68 370 12 377 215 216 161 24 386 360 3 52 118 18 359 17 246 513 305 39 164 242 272 209 436 502 429 340 332 427 544 232 60 117 407 467 73 226 368 507 240 64 122 18 198 26 335 392 483 11 533 179 489 523 290 145 198 497 75 6 377 487 190 544 414 170 138 182 540 323 332 139 229 378 365 126 381 458 260 390 212 516 171 374 473 332 389 324 224 266 333 394 223 449 285 312 431 267 404 144 93 52 273 474 322 317 422 59 448 184 442 420 32 108 84 494 0 392 518 193 12 113 164 29 335 280 67 372 539 501 498 218 122 147 248 203 218 463 70 163 174 414 88 194 487 334 228 462 545 378 328 313 292 375 126 372 218 472 264 51 334 217 489 299 205 395 182 299 272

[出力例]

2023

■参照サイト
AtCoder Beginner Contest 141

2022年9月10日

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

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

■感想.
1. 問題Eは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, トポロジカルソートの復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/abc139/editorial.pdf
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
using PQ = priority_queue<int, vector<int>, greater<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
const int MAX = 505050;
int a[1010][1010], b[1010][1010], iDegree[MAX], d[MAX];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N){
        rep(j, N - 1){
            scanf("%d", &a[i][j]);
            --a[i][j];
        }
    }
    
    // 2. 頂点番号.
    int idx = -1;
    rep(i, N) repx(j, i + 1, N) b[i][j] = b[j][i] = ++idx;
    
    // 3. 有向グラフ.
    int gn = N * (N - 1) / 2;
    vvi G(gn);
    rep(i, N){
        rep(j, N - 2){
            int u = b[i][a[i][j]];
            int v = b[i][a[i][j + 1]];
            G[u].pb(v);
            ++iDegree[v]; // 入次数.
        }
    }
    
    // 3. 入次数ゼロの頂点は？
    PQ pq;
    rep(i, gn) if(!iDegree[i]) pq.push(i);
    
    // 4. トポロジカルソート.
    // https://ja.wikipedia.org/wiki/トポロジカルソート
    vi S;
    while(!pq.empty()){
        // キューから取り出す.
        int u = pq.top();
        pq.pop();
        
        // S に u を 追加.
        S.pb(u);
        
        // 隣接頂点.
        for(auto &v : G[u]){
            // u の 出力辺(u, v) を グラフから削除.
            iDegree[v]--;
            
            // 距離を更新.
            d[v] = max(d[v], d[u] + 1);
            
            // 入次数ゼロの頂点は, キューに追加.
            if(!iDegree[v]) pq.push(v);
        }
    }
    
    // 5. 閉路チェック.
    bool cycle = false;
    rep(i, gn) if(iDegree[i]) cycle = true;
    
    // 6. 例外(閉路検出時).
    if(cycle){
        puts("-1");
        return 0;
    }
    
    // 7. 最大パス長さは？
    int ans = 0;
    rep(i, gn) ans = max(ans, d[i]);
    
    // 8. 出力.
    printf("%d\n", ans + 1);
    return 0;
    
}

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

using vvi = vector<vi>;

using PQ = priority_queue<int, vector<int>, greater<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

const int MAX = 505050;

int a[1010][1010], b[1010][1010], iDegree[MAX], d[MAX];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

rep(i, N){

rep(j, N - 1){

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

--a[i][j];

}

// 2. 頂点番号.

int idx = -1;

rep(i, N) repx(j, i + 1, N) b[i][j] = b[j][i] = ++idx;

// 3. 有向グラフ.

int gn = N * (N - 1) / 2;

vvi G(gn);

rep(i, N){

rep(j, N - 2){

int u = b[i][a[i][j]];

int v = b[i][a[i][j + 1]];

G[u].pb(v);

++iDegree[v]; // 入次数.

}

// 3. 入次数ゼロの頂点は？

PQ pq;

rep(i, gn) if(!iDegree[i]) pq.push(i);

// 4. トポロジカルソート.

// https://ja.wikipedia.org/wiki/トポロジカルソート

vi S;

while(!pq.empty()){

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

int u = pq.top();

pq.pop();

// S に u を追加.

S.pb(u);

// 隣接頂点.

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

// u の出力辺(u, v) をグラフから削除.

iDegree[v]--;

// 距離を更新.

d[v] = max(d[v], d[u] + 1);

// 入次数ゼロの頂点は, キューに追加.

if(!iDegree[v]) pq.push(v);

}

// 5. 閉路チェック.

bool cycle = false;

rep(i, gn) if(iDegree[i]) cycle = true;

// 6. 例外(閉路検出時).

if(cycle){

puts("-1");

return 0;

}

// 7. 最大パス長さは？

int ans = 0;

rep(i, gn) ans = max(ans, d[i]);

// 8. 出力.

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

return 0;

}

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

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

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

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

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

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

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

[出力例]
-1

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

[出力例]
13

[入力例]

2 3

1 3

1 2

[出力例]

※AtCoderテストケースより

[入力例]

2 3 4

1 3 4

4 1 2

3 1 2

[出力例]

※AtCoderテストケースより

[入力例]

2 3

3 1

1 2

[出力例]

-1

※AtCoderテストケースより

[入力例]

3 5 2 4

3 1 5 4

1 2 5 4

3 2 5 1

4 1 2 3

[出力例]

-1

[入力例]

3 5 2 4 7 6

6 3 1 5 4 7

1 2 4 5 7 6

2 1 5 3 6 7

1 2 4 3 6 7

2 4 5 3 1 7

1 2 3 4 5 6

[出力例]

■参照サイト
AtCoder Beginner Contest 139

カテゴリー: C++

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

C++の練習を兼ねて, AtCoder Regular Contest 033 の問題D (見たことのない多項式) を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 148 の問題C (Lights Out on Tree) を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 148 の問題A (mod M) ～問題B (dp) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 038 の問題D (プレゼント) を解いてみた.

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

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

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

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

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

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

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

C++の練習を兼ねて, AtCoder Beginner Contest 145 の問題E (All-you-can-eat) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 141 の問題F (Xor Sum 3) を解いてみた.

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

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

C++の練習を兼ねて, AtCoder Regular Contest 033 の 問題D (見たことのない多項式) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 148 の 問題C (Lights Out on Tree) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 148 の 問題A (mod M) ～ 問題B (dp) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 038 の 問題D (プレゼント) を解いてみた.

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

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

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

C++の練習を兼ねて, AtCoder Beginner Contest 145 の 問題E (All-you-can-eat) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 141 の 問題F (Xor Sum 3) を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 033 の問題D (見たことのない多項式) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 148 の問題C (Lights Out on Tree) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 148 の問題A (mod M) ～問題B (dp) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 038 の問題D (プレゼント) を解いてみた.

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

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

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

C++の練習を兼ねて, AtCoder Beginner Contest 145 の問題E (All-you-can-eat) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 141 の問題F (Xor Sum 3) を解いてみた.

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