C++ | 個人用メモ帳

2022年3月25日2022年3月25日

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

C++の練習を兼ねて, AtCoder Regular Contest 137 の問題A (Coprime Pair) ～問題B (Count 1’s) を解いてみた.

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

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

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

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

int main(){
    
    // 1. 入力情報.
    LL L, R;
    scanf("%lld %lld", &L, &R);
    
    // 2. y - x の 最大値は？
    // 01-007.txt などで, WA版だったので, 修正.
    LL ans = 0, x = L, y = R;
    rep(i, 1501){
        rep(j, 1501){
            if(y - j <= 0 || (y - j <= x + i)) continue;
            if(__gcd(x + i, y - j) == 1)       ans = max(ans, y - j - x - i);
        }
    }
    
    // 3. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc137/editorial/3592

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

int main(){

// 1. 入力情報.

LL L, R;

scanf("%lld %lld", &L, &R);

// 2. y - x の最大値は？

// 01-007.txt などで, WA版だったので, 修正.

LL ans = 0, x = L, y = R;

rep(i, 1501){

rep(j, 1501){

if(y - j <= 0 || (y - j <= x + i)) continue;

if(__gcd(x + i, y - j) == 1) ans = max(ans, y - j - x - i);

}

// 3. 出力.

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

return 0;

}

[入力例]
2 4

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

[入力例]
14 21

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

[入力例]
1 100

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

[入力例]
123 456

[出力例]
332

[入力例]
12345 67890

[出力例]
55544

[入力例]

2 4

[出力例]

※AtCoderのテストケースより

[入力例]

14 21

[出力例]

※AtCoderのテストケースより

[入力例]

1 100

[出力例]

※AtCoderのテストケースより

[入力例]

123 456

[出力例]

332

[入力例]

12345 67890

[出力例]

55544

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

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

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%d", &a[i]);
    
    // 2. 0, 1 の 出現数確認.
    // -> 01-001.txt などで, WA版となったのでロジック修正.
    int cnt10 = 0; // (1 の 個数) - (0 の 個数) の 最大値.
    int cnt01 = 0; // (0 の 個数) - (1 の 個数) の 最大値.
    rep(i, N){
        // 1 の 場合.
        if(a[i]){
            b[i + 1] = max(b[i] + 1, 1);
            c[i + 1] = max(c[i] - 1, -1);
        }
        
        // 0 の 場合.
        if(!a[i]){
            b[i + 1] = max(b[i] - 1, -1);
            c[i + 1] = max(c[i] + 1, 1);
        }
        
        // 最大値更新.
        cnt10 = max(cnt10, b[i + 1]);
        cnt01 = max(cnt01, c[i + 1]);
    }
    
    // 3. 出力.
    printf("%d\n", cnt10 + cnt01 + 1);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc137/editorial/3591

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

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

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

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

// 2. 0, 1 の出現数確認.

// -> 01-001.txt などで, WA版となったのでロジック修正.

int cnt10 = 0; // (1 の個数) - (0 の個数) の最大値.

int cnt01 = 0; // (0 の個数) - (1 の個数) の最大値.

rep(i, N){

// 1 の場合.

if(a[i]){

b[i + 1] = max(b[i] + 1, 1);

c[i + 1] = max(c[i] - 1, -1);

}

// 0 の場合.

if(!a[i]){

b[i + 1] = max(b[i] - 1, -1);

c[i + 1] = max(c[i] + 1, 1);

}

// 最大値更新.

cnt10 = max(cnt10, b[i + 1]);

cnt01 = max(cnt01, c[i + 1]);

}

// 3. 出力.

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

return 0;

}

[入力例]
4
0 1 1 0

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

[入力例]
5
0 0 0 0 0

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

[入力例]
6
0 1 0 1 0 1

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

[入力例]
1
1

[出力例]
2

[入力例]
11
0 0 1 0 1 0 1 0 1 1 0

[出力例]
5

[入力例]
100
0 1 1 0 0 0 1 0 1 1 1 1 0 0 1 1 0 1 0 1 1 0 0 0 1 1 1 0 0 0 1 0 1 1 0 0 0 1 0 0 1 1 1 0 0 0 1 0 0 1 0 0 0 0 0 1 0 1 1 0 0 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 0 0 1 1 0 1 1 1 0 0 1 0 1 1 0 0 0 1 1 1 1 0 0

[出力例]
18

[入力例]

0 1 1 0

[出力例]

※AtCoderのテストケースより

[入力例]

0 0 0 0 0

[出力例]

※AtCoderのテストケースより

[入力例]

0 1 0 1 0 1

[出力例]

※AtCoderのテストケースより

[入力例]

[出力例]

[入力例]

0 0 1 0 1 0 1 0 1 1 0

[出力例]

[入力例]

100

0 1 1 0 0 0 1 0 1 1 1 1 0 0 1 1 0 1 0 1 1 0 0 0 1 1 1 0 0 0 1 0 1 1 0 0 0 1 0 0 1 1 1 0 0 0 1 0 0 1 0 0 0 0 0 1 0 1 1 0 0 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 0 0 1 1 0 1 1 1 0 0 1 0 1 1 0 0 0 1 1 1 1 0 0

[出力例]

■参照サイト
AtCoder Regular Contest 137

2022年3月24日2022年3月24日

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

C++の練習を兼ねて, AtCoder Regular Contest 027 の問題C (最高のトッピングにしような) を解いてみた.

■感想.
1. 問題Cは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 苦手な動的計画法の訓練を積めたので, 非常に良かったと思う.
3. なお, 初回提出版では, MLE(メモリ制限超過)となったので, MLE回避するように修正して, 再提出している.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://www.slideshare.net/chokudai/arc027
// 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 dp[303][606], pd[303][606]; // dp[303][303][606] だと, MLE となるので, 修正.
int t[303], h[303];

int main(){
    
    // 1. 入力情報.
    int X, Y, N;
    scanf("%d %d %d", &X, &Y, &N);
    rep(i, N) scanf("%d %d", &t[i], &h[i]);
    
    // 2. dp更新.
    rep(i, N){
        // 初期化.
        rep(j, X + 1) rep(k, X + Y + 1) pd[j][k] = -1;
        pd[0][0] = 0;
        
        // 前回分反映.
        rep(j, X + 1) rep(k, X + Y + 1) pd[j][k] = max(pd[j][k], dp[j][k]);
        
        // 今回分反映.
        rep(j, min(i + 1, X)){
            rep(k, X + Y + 1){
                int nk = k - t[i];
                if(nk >= 0 && pd[j][nk] != -1){
                    dp[j + 1][k] = max(dp[j + 1][k], pd[j + 1][k]);
                    dp[j + 1][k] = max(dp[j + 1][k], pd[j][nk] + h[i]);
                }
            }
        }
    }
    
    // 3. 最大値.
    LL ans = 0;
    rep(j, X + 1) rep(k, X + Y + 1) ans = max(ans, dp[j][k]);
    
    // 4. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

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

// 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 dp[303][606], pd[303][606]; // dp[303][303][606] だと, MLE となるので, 修正.

int t[303], h[303];

int main(){

// 1. 入力情報.

int X, Y, N;

scanf("%d %d %d", &X, &Y, &N);

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

// 2. dp更新.

rep(i, N){

// 初期化.

rep(j, X + 1) rep(k, X + Y + 1) pd[j][k] = -1;

pd[0][0] = 0;

// 前回分反映.

rep(j, X + 1) rep(k, X + Y + 1) pd[j][k] = max(pd[j][k], dp[j][k]);

// 今回分反映.

rep(j, min(i + 1, X)){

rep(k, X + Y + 1){

int nk = k - t[i];

if(nk >= 0 && pd[j][nk] != -1){

dp[j + 1][k] = max(dp[j + 1][k], pd[j + 1][k]);

dp[j + 1][k] = max(dp[j + 1][k], pd[j][nk] + h[i]);

}

// 3. 最大値.

LL ans = 0;

rep(j, X + 1) rep(k, X + Y + 1) ans = max(ans, dp[j][k]);

// 4. 出力.

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

return 0;

}

[入力例]
3 5
4
3 30
3 40
5 60
7 80

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

[入力例]
3 3
4
3 30
3 40
5 60
7 80

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

[入力例]
1 5
4
3 30
3 40
5 60
7 80

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

[入力例]
6 12
4
3 30
3 40
5 60
7 80

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

[入力例]
1 1
1
1 11

[出力例]
11

[入力例]
7 15
10
7 100
2 33
6 66
4 44
8 55
1 9
12 111
10 178
7 77
5 55

[出力例]
333

[入力例]
12 33
25
3 642
2 174
10 129
6 1234
12 471
18 1013
10 207
6 642
3 1034
11 516
3 1075
9 201
9 1056
7 198
6 121
2 515
19 234
20 1111
3 924
5 770
2 677
4 1060
6 298
3 839
12 1010

[出力例]
10000

[入力例]
32 123
50
5 2237
11 527
12 69740
2 22416
8 77783
5 105904
12 122429
15 36253
7 115045
7 22468
12 108751
20 105233
4 34947
13 69463
5 5796
12 69023
3 31396
19 64113
8 30591
2 112723
7 113855
5 74920
17 63139
10 123438
19 26368
18 114828
3 8975
12 92652
25 117114
13 82653
5 106809
11 94419
17 54726
19 85275
16 91535
10 115684
7 101791
8 91513
3 122995
6 5408
7 79431
8 48599
19 115048
20 106513
11 64312
5 6456
7 102500
3 27527
19 23909
15 2042

[出力例]
2000000

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

[入力例]

3 5

3 30

3 40

5 60

7 80

[出力例]

100

※AtCoderテストケースより

[入力例]

3 3

3 30

3 40

5 60

7 80

[出力例]

※AtCoderテストケースより

[入力例]

1 5

3 30

3 40

5 60

7 80

[出力例]

※AtCoderテストケースより

[入力例]

6 12

3 30

3 40

5 60

7 80

[出力例]

210

※AtCoderテストケースより

[入力例]

1 1

1 11

[出力例]

[入力例]

7 15

7 100

2 33

6 66

4 44

8 55

1 9

12 111

10 178

7 77

5 55

[出力例]

333

[入力例]

12 33

3 642

2 174

10 129

6 1234

12 471

18 1013

10 207

6 642

3 1034

11 516

3 1075

9 201

9 1056

7 198

6 121

2 515

19 234

20 1111

3 924

5 770

2 677

4 1060

6 298

3 839

12 1010

[出力例]

10000

[入力例]

32 123

5 2237

11 527

12 69740

2 22416

8 77783

5 105904

12 122429

15 36253

7 115045

7 22468

12 108751

20 105233

4 34947

13 69463

5 5796

12 69023

3 31396

19 64113

8 30591

2 112723

7 113855

5 74920

17 63139

10 123438

19 26368

18 114828

3 8975

12 92652

25 117114

13 82653

5 106809

11 94419

17 54726

19 85275

16 91535

10 115684

7 101791

8 91513

3 122995

6 5408

7 79431

8 48599

19 115048

20 106513

11 64312

5 6456

7 102500

3 27527

19 23909

15 2042

[出力例]

2000000

■参照サイト
AtCoder Regular Contest 027

2022年3月24日

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

C++の練習を兼ねて, AtCoder Regular Contest 025 の問題C (ウサギとカメ) を解いてみた.

■感想.
1. 問題Cは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 実装に苦労したものの, 個人的には, ダイクストラ法(応用版) と尺取り法の復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://www.slideshare.net/chokudai/arc025
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vl = vector<LL>;
using vvl = vector<vl>;
#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 LL INF = 202020202020202020;

struct edge{
    int n; // 次の頂点.
    LL c;  // コスト.
    bool operator < (const edge &E) const{ return c > E.c; }
};

vector<edge> G[3030];

int main(){
    
    // 1. 入力情報.
    int N, M, R, T;
    scanf("%d %d %d %d", &N, &M, &R, &T);
    rep(i, M){
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        --a;
        --b;
        G[a].pb(edge{b, (LL)c});
        G[b].pb(edge{a, (LL)c});
    }
    
    // 2. ダイクストラ法.
    // https://ja.wikipedia.org/wiki/ダイクストラ法
    auto dijkstra = [&](int s, LL* d, int* m){
        // 2-1. 初期化.
        priority_queue<edge> pq;
        
        // 2-2. 始点設定.
        d[s] = 0;
        pq.push({s, 0LL});
        
        // 2-3. キュー pq が 空になるまで, 探索.
        while(!pq.empty()){
            // 2-4. 探索を継続するために, 頂点を取得.
            edge e = pq.top();
            pq.pop();
            int cn = e.n;
            LL cc = e.c;
            
            // 2-5. 訪問済みフラグ設定.
            if(m[cn]) continue;
            m[cn]++;
            
            // 2-6. 各隣接する頂点について, 距離を確認し, 移動コストを更新.
            for(auto &g : G[cn]){
                // 移動コスト更新.
                int nn = g.n;
                LL nc = cc + g.c;
                if(d[nn] > nc) d[nn] = nc, pq.push({nn, nc});
            }
        }
    };
    
    // 3. 最短経路のリスト作成.
    vvl v(N);
    rep(i, N){
        LL d[N];
        int memo[N];
        rep(j, N) d[j] = INF, memo[j] = 0;
        dijkstra(i, d, memo);
        rep(j, N) if(i != j) v[i].pb(d[j]);
        sort(all(v[i]));
    }
    /*
    for(auto &p : v){
        for(auto &q : p) printf("%d ", q);
        puts("\n-----");
    }
    */
    
    // 4. 組み合わせを集計.
    LL ans = 0;
    rep(i, N){
        // ウサギ, カメ の 最短経路長 を 評価.
        // -> X(ウサギの最短経路) * T(カメの速さ) > Y(カメの最短経路) * R(ウサギの速さ) に 注意.
        int r = 0;
        rep(l, N - 1){
            LL Y = v[i][l], X = v[i][r];
            while(X * T <= Y * R && r <= N - 2) X = v[i][++r];
            ans += (LL)(N - 1 - r);
        }
    }
    
    // 5. カメの速さ が ウサギの速さ よりも速かった場合.
    if(T > R) ans -= (LL)N * (LL)(N - 1);
    
    // 6. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

100

101

102

103

104

105

106

107

108

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vl = vector<LL>;

using vvl = vector<vl>;

#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 LL INF = 202020202020202020;

struct edge{

int n; // 次の頂点.

LL c; // コスト.

bool operator < (const edge &E) const{ return c > E.c; }

};

vector<edge> G[3030];

int main(){

// 1. 入力情報.

int N, M, R, T;

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

rep(i, M){

int a, b, c;

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

--a;

--b;

G[a].pb(edge{b, (LL)c});

G[b].pb(edge{a, (LL)c});

}

// 2. ダイクストラ法.

// https://ja.wikipedia.org/wiki/ダイクストラ法

auto dijkstra = [&](int s, LL* d, int* m){

// 2-1. 初期化.

priority_queue<edge> pq;

// 2-2. 始点設定.

d[s] = 0;

pq.push({s, 0LL});

// 2-3. キュー pq が空になるまで, 探索.

while(!pq.empty()){

// 2-4. 探索を継続するために, 頂点を取得.

edge e = pq.top();

pq.pop();

int cn = e.n;

LL cc = e.c;

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

if(m[cn]) continue;

m[cn]++;

// 2-6. 各隣接する頂点について, 距離を確認し, 移動コストを更新.

for(auto &g : G[cn]){

// 移動コスト更新.

int nn = g.n;

LL nc = cc + g.c;

if(d[nn] > nc) d[nn] = nc, pq.push({nn, nc});

}

};

// 3. 最短経路のリスト作成.

vvl v(N);

rep(i, N){

LL d[N];

int memo[N];

rep(j, N) d[j] = INF, memo[j] = 0;

dijkstra(i, d, memo);

rep(j, N) if(i != j) v[i].pb(d[j]);

sort(all(v[i]));

}

for(auto &p : v){

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

puts("\n-----");

}

// 4. 組み合わせを集計.

LL ans = 0;

rep(i, N){

// ウサギ, カメの最短経路長を評価.

// -> X(ウサギの最短経路) * T(カメの速さ) > Y(カメの最短経路) * R(ウサギの速さ) に注意.

int r = 0;

rep(l, N - 1){

LL Y = v[i][l], X = v[i][r];

while(X * T <= Y * R && r <= N - 2) X = v[i][++r];

ans += (LL)(N - 1 - r);

}

// 5. カメの速さがウサギの速さよりも速かった場合.

if(T > R) ans -= (LL)N * (LL)(N - 1);

// 6. 出力.

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

return 0;

}

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

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

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

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

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

[出力例]
6

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

[出力例]
12

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

[出力例]
50

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

[出力例]
50

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

[出力例]
565

[入力例]

4 5 2 1

1 2 4

1 3 3

1 4 6

2 3 5

3 4 4

[出力例]

※AtCoderテストケースより

[入力例]

5 4 7 7

1 2 1

2 3 1

3 4 1

4 5 1

[出力例]

※AtCoderテストケースより

[入力例]

3 3 1 2

1 2 5

2 3 8

1 3 7

[出力例]

[入力例]

4 6 2 3

1 2 2

1 3 5

1 4 3

2 3 3

2 4 5

3 4 2

[出力例]

[入力例]

5 7 2 5

1 2 6

1 3 5

2 3 2

3 5 3

2 5 1

2 4 7

4 5 4

[出力例]

[入力例]

6 8 5 4

1 2 8

2 3 2

1 3 5

3 4 3

2 4 10

4 5 5

2 6 7

[出力例]

[入力例]

12 18 7 6

1 2 10

1 8 5

2 7 8

2 3 7

2 11 3

11 12 11

3 4 2

4 12 5

4 6 3

3 5 10

5 6 1

5 10 2

6 10 3

7 10 2

7 9 3

9 10 5

8 9 1

7 8 2

[出力例]

565

■参照サイト
AtCoder Regular Contest 025

2022年3月22日

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

C++の練習を兼ねて, AtCoder Regular Contest 024 の問題C (だれじゃ) を解いてみた.

■感想.
1. 問題Cは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 計算量を削減するために, 累積和を使い, 出現回数をチェックしていくロジックが, 面白いと感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://www.slideshare.net/chokudai/arc024
// 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 a first
#define b second
#define all(x) x.begin(), x.end()
int sCum[101010][26];

int main(){
    
    // 1. 入力情報.
    int N, K;
    char c[101010];
    scanf("%d %d", &N, &K);
    scanf("%s", c);
    
    // 2. 累積和.
    rep(i, N){
        rep(j, 26) sCum[i + 1][j] = sCum[i][j];
        sCum[i + 1][c[i] - 'a']++;
    }
    
    // 3. ペアを保存.
    // -> {出現回数, 位置} を 保存.
    map<string, vi> m;
    rep(i, N - K + 1){
        string sCount;
        rep(j, 26) sCount += to_string(sCum[i + K][j] - sCum[i][j]);
        m[sCount].pb(i);
    }
    
    // 4. sort.
    for(auto &p : m) sort(all(p.b));
    
    // 5. 判定.
    bool ok = false;
    for(auto &p : m){
        // printf("p.a=%s p.b.front()=%d p.b.back()=%d\n", p.a.c_str(), p.b.front(), p.b.back());
        if(abs(p.b.front() - p.b.back()) >= K) ok = true;
        if(ok)                                 break;
    }
    
    // 6. 出力.
    printf("%s\n", ok ? "YES" : "NO");
    return 0;
    
}

// 解き直し.

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

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

#define b second

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

int sCum[101010][26];

int main(){

// 1. 入力情報.

int N, K;

char c[101010];

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

scanf("%s", c);

// 2. 累積和.

rep(i, N){

rep(j, 26) sCum[i + 1][j] = sCum[i][j];

sCum[i + 1][c[i] - 'a']++;

}

// 3. ペアを保存.

// -> {出現回数, 位置} を保存.

map<string, vi> m;

rep(i, N - K + 1){

string sCount;

rep(j, 26) sCount += to_string(sCum[i + K][j] - sCum[i][j]);

m[sCount].pb(i);

}

// 4. sort.

for(auto &p : m) sort(all(p.b));

// 5. 判定.

bool ok = false;

for(auto &p : m){

// printf("p.a=%s p.b.front()=%d p.b.back()=%d\n", p.a.c_str(), p.b.front(), p.b.back());

if(abs(p.b.front() - p.b.back()) >= K) ok = true;

if(ok) break;

}

// 6. 出力.

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

return 0;

}

[入力例]
8 3
abcdbcae

[出力例]
YES

[入力例]
7 4
abcdcba

[出力例]
NO

[入力例]
8 1
issample

[出力例]
YES

[入力例]
30 5
lujvpsozzdwiveigvtkusfrknrddwe

[出力例]
NO

[入力例]
22 11
abracadabraabracadabra

[出力例]
YES

[入力例]
100 10
wxxmdlhtjcpzbwjhbgfynhntmwiequmpfaoczyfyjccacshwizahrfryrsdleglzmuynpieidylytonbngrzzvnukkwczgjjphbb

[出力例]
YES

[入力例]
500 25
csqeiypjxtpaadtrnvusdnleqpizvhywlfkgyzmpjgzfpbjauuxeisxcyxsbfxmoohtiohigcbhouoxkicfrpytvrxhmnrxkkfwplvdsnpzkaivlserltkhaypwclyirghuzuyhtbxioxydpckpmweygptacpcgccsqgtpcevigribhtsndqinktmredwjqkldnxnecjapwmyehsghfipfwxuhezinndyhmyipbgkjcyrsjadnxqmnntlgnafuzjlqgfbcpsiusbvylapckjuvgjutjvpajbnlhcsowtclxkdyxfieqzwkovrrdbaxqwvwqceqvmlkpdglwuzwfxkhmnfnwmqfpvwgvrvslzryzgurifqdvivcrgidfaadddegvrdvxiokhgxpteqnojvldecfzdeifgfbccccdeqggghiiinppqrssttvtvaksxptqdrfxenqzhyjldpwwrjabivtapnxaxlsgrieztkzsubvfzbnqj

[出力例]
YES

[入力例]

8 3

abcdbcae

[出力例]

YES

[入力例]

7 4

abcdcba

[出力例]

[入力例]

8 1

issample

[出力例]

YES

[入力例]

30 5

lujvpsozzdwiveigvtkusfrknrddwe

[出力例]

[入力例]

22 11

abracadabraabracadabra

[出力例]

YES

[入力例]

100 10

wxxmdlhtjcpzbwjhbgfynhntmwiequmpfaoczyfyjccacshwizahrfryrsdleglzmuynpieidylytonbngrzzvnukkwczgjjphbb

[出力例]

YES

[入力例]

500 25

csqeiypjxtpaadtrnvusdnleqpizvhywlfkgyzmpjgzfpbjauuxeisxcyxsbfxmoohtiohigcbhouoxkicfrpytvrxhmnrxkkfwplvdsnpzkaivlserltkhaypwclyirghuzuyhtbxioxydpckpmweygptacpcgccsqgtpcevigribhtsndqinktmredwjqkldnxnecjapwmyehsghfipfwxuhezinndyhmyipbgkjcyrsjadnxqmnntlgnafuzjlqgfbcpsiusbvylapckjuvgjutjvpajbnlhcsowtclxkdyxfieqzwkovrrdbaxqwvwqceqvmlkpdglwuzwfxkhmnfnwmqfpvwgvrvslzryzgurifqdvivcrgidfaadddegvrdvxiokhgxpteqnojvldecfzdeifgfbccccdeqggghiiinppqrssttvtvaksxptqdrfxenqzhyjldpwwrjabivtapnxaxlsgrieztkzsubvfzbnqj

[出力例]

YES

■参照サイト
AtCoder Regular Contest 024

2022年3月22日

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

C++の練習を兼ねて, AtCoder Regular Contest 021 の問題C (増築王高橋君) を解いてみた.

■感想.
1. 問題Cは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 実装に苦労したものの, 二分探索(応用版, 桁数オーバーフロー注意)の復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://www.slideshare.net/chokudai/arc021
// 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[101010], d[101010];

int main(){
    
    // 1. 入力情報.
    int N;
    LL K;
    scanf("%lld %d", &K, &N);
    rep(i, N) scanf("%lld %lld", &a[i], &d[i]);
    
    // 2. 評価関数.
    auto f = [&](LL m) -> bool {
        // 2-1. 最後に選んだ増築費用を, m として, 合計 K 回 以上に出来るか？
        LL k = 0;
        rep(i, N) if(m >= a[i]) k += (m - a[i] + d[i]) / d[i];
        
        // 2-2. 判定結果.
        return (k >= K);
    };
    
    // 3. 二分探索で確認してみる.
    // -> 関数 f 内での オーバーフロー注意？
    LL l = 0, h = 2e12 + 1;
    while(l + 1 < h){
        LL m = (h + l) >> 1;
        if(f(m)) h = m;
        else     l = m;
        // printf("h=%lld l=%lld m=%lld\n", h, l, m);
    }
    
    // 4. 集計.
    LL ans = 0;
    rep(i, N){
        if(h >= a[i]){
            // 建物 i の 増築回数.
            LL q = (h - a[i] + d[i]) / d[i];
            
            // 増築価格更新.
            // -> オーバーフロー注意？
            ans += (a[i] * q) + (q - 1) * q / 2 * d[i];
            
            // 増築回数 の 減算.
            K -= q;
        }
    }
    
    // 5. 残分.
    // -> K が マイナスのケースも考慮.
    ans += h * K;
    
    // 6. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

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

// 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[101010], d[101010];

int main(){

// 1. 入力情報.

int N;

LL K;

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

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

// 2. 評価関数.

auto f = [&](LL m) -> bool {

// 2-1. 最後に選んだ増築費用を, m として, 合計 K 回以上に出来るか？

LL k = 0;

rep(i, N) if(m >= a[i]) k += (m - a[i] + d[i]) / d[i];

// 2-2. 判定結果.

return (k >= K);

};

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

// -> 関数 f 内でのオーバーフロー注意？

LL l = 0, h = 2e12 + 1;

while(l + 1 < h){

LL m = (h + l) >> 1;

if(f(m)) h = m;

else l = m;

// printf("h=%lld l=%lld m=%lld\n", h, l, m);

}

// 4. 集計.

LL ans = 0;

rep(i, N){

if(h >= a[i]){

// 建物 i の増築回数.

LL q = (h - a[i] + d[i]) / d[i];

// 増築価格更新.

// -> オーバーフロー注意？

ans += (a[i] * q) + (q - 1) * q / 2 * d[i];

// 増築回数の減算.

K -= q;

}

// 5. 残分.

// -> K がマイナスのケースも考慮.

ans += h * K;

// 6. 出力.

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

return 0;

}

[入力例]
4
3
10 3
12 4
15 5

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

[入力例]
8
4
1 1
10 1
100 1
1000 1

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

[入力例]
15
3
10 1
5 3
7 4

[出力例]
179

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

[出力例]
97

[入力例]
35
10
3 3
13 17
20 2
5 16
12 15
7 11
10 23
5 19
17 22
2 15

[出力例]
682

[入力例]
2022
15
28 103
63 88
20 122
118 23
111 41
19 37
77 114
50 89
54 56
14 79
3 42
95 80
74 38
59 40
122 108

[出力例]
7603076

[入力例]
20220322
20
777 943
582 728
1000 522
703 623
117 1133
305 821
1177 1001
1324 621
680 575
527 243
951 665
543 426
574 509
720 1173
87 84
603 293
692 737
704 567
93 78
190 1092

[出力例]
3692618300173731

100

101

102

103

104

105

106

107

108

109

110

[入力例]

10 3

12 4

15 5

[出力例]

※AtCoderテストケースより

[入力例]

1 1

10 1

100 1

1000 1

[出力例]

※AtCoderテストケースより

[入力例]

10 1

5 3

7 4

[出力例]

179

[入力例]

6 7

1 5

7 1

7 3

11 9

[出力例]

[入力例]

3 3

13 17

20 2

5 16

12 15

7 11

10 23

5 19

17 22

2 15

[出力例]

682

[入力例]

2022

28 103

63 88

20 122

118 23

111 41

19 37

77 114

50 89

54 56

14 79

3 42

95 80

74 38

59 40

122 108

[出力例]

7603076

[入力例]

20220322

777 943

582 728

1000 522

703 623

117 1133

305 821

1177 1001

1324 621

680 575

527 243

951 665

543 426

574 509

720 1173

87 84

603 293

692 737

704 567

93 78

190 1092

[出力例]

3692618300173731

■参照サイト
AtCoder Regular Contest 021

2022年3月20日

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

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

■感想.
1. 問題Eは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 解説のロジックで, 答えが計算可能なことに, 不思議な印象を受けた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/abc140/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--)
int p[101010], q[101010];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N){
        scanf("%d", &p[i + 1]);
        q[p[i + 1]] = i + 1;
    }
    
    // 2. 集計.
    LL ans = 0;
    multiset<int> S, T;
    S.insert(0);
    S.insert(0);
    T.insert(N + 1);
    T.insert(N + 1);
    repr(i, N, 1){
        // 追加.
        int at = q[i];
        S.insert(at);
        T.insert(at);
        
        // 集合 S で, 一番大きい要素, 二番目に大きい要素 を 設定.
        auto sItr = S.lower_bound(at);
        --sItr;
        int sMax1 = *sItr;
        --sItr;
        int sMax2 = *sItr;
        
        // 集合 T で, 一番小さい要素, 二番目に小さい要素 を 設定.
        auto tItr = T.lower_bound(at);
        ++tItr;
        int tMin1 = *tItr;
        ++tItr;
        int tMin2 = *tItr;
        
        // 加算.
        LL cur = (LL)(sMax1 - sMax2) * (LL)(tMin1 - at) + (LL)(at - sMax1) * (LL)(tMin2 - tMin1);
        // printf("sMax1=%d sMax2=%d tMin1=%d tMin2=%d at=%d cur=%lld\n", sMax1, sMax2, tMin1, tMin2, at, cur);
        ans += (LL)i * cur;
    }
    
    // 3. 出力.
    printf("%lld", ans);
    return 0;
    
}

// 解き直し.

// https://img.atcoder.jp/abc140/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--)

int p[101010], q[101010];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

rep(i, N){

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

q[p[i + 1]] = i + 1;

}

// 2. 集計.

LL ans = 0;

multiset<int> S, T;

S.insert(0);

T.insert(N + 1);

repr(i, N, 1){

// 追加.

int at = q[i];

S.insert(at);

T.insert(at);

// 集合 S で, 一番大きい要素, 二番目に大きい要素を設定.

auto sItr = S.lower_bound(at);

--sItr;

int sMax1 = *sItr;

--sItr;

int sMax2 = *sItr;

// 集合 T で, 一番小さい要素, 二番目に小さい要素を設定.

auto tItr = T.lower_bound(at);

++tItr;

int tMin1 = *tItr;

++tItr;

int tMin2 = *tItr;

// 加算.

LL cur = (LL)(sMax1 - sMax2) * (LL)(tMin1 - at) + (LL)(at - sMax1) * (LL)(tMin2 - tMin1);

// printf("sMax1=%d sMax2=%d tMin1=%d tMin2=%d at=%d cur=%lld\n", sMax1, sMax2, tMin1, tMin2, at, cur);

ans += (LL)i * cur;

}

// 3. 出力.

printf("%lld", ans);

return 0;

}

[入力例]
3
2 3 1

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

[入力例]
5
1 2 3 4 5

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

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

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

[入力例]
2
1 2

[出力例]
1

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

[出力例]
313

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

[出力例]
50685

[入力例]
500
377 148 304 214 25 117 54 93 176 65 52 185 498 436 420 412 365 153 409 10 218 104 99 141 184 250 62 11 90 437 26 46 350 228 398 139 376 361 380 466 288 3 279 140 108 340 423 367 208 385 158 63 277 446 478 271 440 323 337 439 318 491 364 308 5 40 322 269 127 237 303 390 276 387 258 4 328 315 346 424 389 143 285 333 6 459 8 273 164 101 201 111 188 356 120 53 110 81 313 225 247 317 255 150 28 434 467 464 403 371 60 112 488 292 402 357 426 235 226 106 332 421 198 351 425 254 195 31 13 219 383 260 173 494 363 163 186 246 345 94 204 449 309 166 15 335 352 314 211 232 455 114 443 115 147 233 165 89 282 64 142 240 430 413 72 203 71 294 224 167 121 79 59 388 453 362 170 1 36 135 14 396 190 347 393 399 41 457 193 159 448 321 395 220 287 368 378 493 354 267 476 245 391 102 408 187 43 284 431 486 22 298 468 251 252 359 341 180 48 179 316 35 116 427 401 217 128 319 16 87 126 207 76 33 349 202 155 21 261 311 75 404 131 484 84 24 500 256 348 156 161 381 97 230 382 435 289 66 206 327 133 344 263 137 212 44 428 32 86 2 305 253 229 134 400 296 405 290 61 334 236 91 172 80 98 372 394 241 414 302 306 264 418 268 485 370 38 70 100 17 223 410 373 419 162 95 171 169 310 221 29 18 496 295 473 58 227 145 407 49 462 450 441 358 312 154 411 125 499 136 461 23 192 96 123 366 55 301 174 88 210 438 30 68 360 353 336 331 375 326 160 320 286 479 458 415 417 330 37 105 481 281 119 422 83 205 259 447 77 452 470 249 73 168 149 278 243 12 69 272 124 463 152 291 483 56 42 406 178 231 416 300 432 222 132 343 182 197 45 293 213 274 191 454 200 355 270 487 78 183 181 109 74 477 122 244 451 480 307 57 474 374 177 239 129 146 248 39 429 460 138 471 379 92 27 324 9 209 215 342 262 433 175 50 445 238 196 444 283 242 492 19 189 469 82 497 266 67 369 490 103 51 475 495 465 113 34 472 144 265 392 339 442 299 199 329 338 456 151 85 118 325 107 489 386 275 384 482 280 7 257 297 194 234 216 397 47 157 130 20

[出力例]
60354172

[入力例]
2500
785 1950 694 1393 942 878 2101 1097 2338 1174 438 1467 221 1083 2248 742 1956 1876 2244 1339 81 2123 1524 1792 1021 2187 596 1144 600 1235 1210 2295 841 954 110 45 1772 528 1067 444 1714 2028 1085 2062 1191 196 1674 2022 1920 2442 2334 1115 2321 1780 1497 867 1117 2266 1087 2090 468 2257 1842 498 1878 983 34 1634 885 2004 1830 1317 295 1349 2138 1395 1599 2252 2136 1249 347 979 2125 1943 1630 1949 429 218 2160 2450 820 855 1676 719 418 861 1007 200 1863 493 327 1877 2238 1265 1367 1932 931 504 1639 1417 285 1795 1438 999 1530 480 1214 1070 1471 94 1036 2463 2206 1605 1289 1105 476 1457 374 53 639 832 1185 1867 1702 278 889 2030 1088 1018 2223 1638 2247 1407 247 510 2434 2065 1004 1506 784 614 738 86 189 836 707 324 1518 448 1570 345 1974 1283 570 1903 1308 291 1684 245 557 1914 256 1340 423 2289 1957 127 1489 85 1014 388 106 523 1999 1343 1162 2305 401 809 1366 2424 1700 2058 571 2005 194 2271 2003 1195 730 1855 161 822 2083 1472 70 1732 144 458 1757 799 925 1890 2464 1291 1813 1124 1409 260 236 1147 467 1479 51 1505 13 333 124 1759 471 1694 1344 1485 1831 1583 1628 2258 833 62 1827 383 972 1944 96 1824 2000 1360 488 1029 342 1545 355 1851 868 1064 1072 1001 2194 1951 1929 2116 788 746 1326 1899 1767 831 1113 2362 1377 1069 2038 1983 294 562 46 1695 2222 443 1777 1157 1227 1282 2200 579 269 1193 459 2129 919 1516 1653 215 1763 2015 1402 83 599 370 14 362 876 1712 973 1212 1190 219 1661 829 2453 927 1864 741 157 959 697 709 1137 2085 1076 1820 938 1882 1724 1213 1175 457 1705 2290 2272 2190 460 2072 1173 638 966 1966 1509 529 2198 2093 864 1410 507 1710 1131 2240 1754 1374 19 1874 653 1028 1345 1180 1561 1720 1602 2346 1199 601 622 924 627 319 2088 764 2416 1941 1948 1519 2468 930 205 1595 865 371 1541 702 906 819 2051 2373 2390 316 2366 2437 1743 1002 613 2404 1352 1677 1900 2211 2158 1267 305 947 138 2011 2150 2422 1209 470 1013 904 1722 309 1187 329 102 2393 1277 2188 1810 2361 279 2104 1106 1594 574 1019 1660 146 1290 213 1947 430 2241 2302 180 1839 893 626 1779 1525 1536 2349 2273 1721 495 1387 112 1140 2403 1838 623 882 337 1424 1625 224 520 692 214 783 361 380 923 669 1324 1111 1741 798 2353 1726 2301 266 619 1650 212 1556 1698 1287 1815 1391 63 2130 1805 1959 209 284 2 2245 1774 1486 1433 552 2178 732 899 610 1907 3 814 1789 1434 139 665 1053 1736 1224 1987 2391 962 679 597 1840 598 774 1733 1552 501 308 2192 114 888 2175 1010 1852 808 1463 1513 1219 33 823 358 2280 1023 2455 280 1383 804 1927 556 1794 2291 1332 620 2007 892 1646 1522 699 703 916 662 1880 79 1022 1152 612 1181 1451 775 346 898 558 1689 801 1269 1231 1885 874 1857 339 325 2498 2254 1784 235 2127 349 1662 71 1973 857 1406 58 1156 126 1107 2243 67 2159 2182 1544 1295 489 1223 2318 1870 1844 676 1627 2406 2328 1296 1641 113 2119 1125 321 1758 508 2025 1454 132 500 1033 1919 691 2451 2228 1149 949 1217 1799 2343 1370 1829 2294 1821 2106 990 2102 1037 1738 1244 2304 1154 854 2121 1469 1431 1112 717 1620 968 2298 1444 364 1917 1955 1618 1584 2377 395 1791 1640 1461 300 1008 1165 223 708 2396 1163 2135 1823 901 72 165 1276 939 1849 1593 174 109 2486 191 2091 815 1167 974 1574 1723 826 1122 1657 2173 1970 4 913 917 384 1633 406 2137 2071 1281 2363 159 1517 1527 252 25 1372 2205 1555 1094 301 1945 375 1664 1379 960 690 2429 675 928 1672 1381 1581 1697 1134 550 1652 1713 1926 2212 2285 1197 2151 704 1101 618 509 2407 830 270 739 428 1755 2024 149 2439 56 10 203 2133 2355 714 1998 1474 2374 1538 437 910 2397 1568 1009 583 441 234 103 2053 1846 1215 1776 2332 805 1845 2419 1311 426 720 576 382 2491 434 122 394 2232 1788 341 420 1453 1309 1709 451 2460 549 2475 880 503 2112 204 2400 244 581 274 1888 1207 2099 532 313 2069 1063 1992 2331 2063 1323 150 1024 1891 73 630 2270 1504 1632 1783 1104 2357 2214 1502 644 766 554 589 828 148 825 834 1095 29 1756 729 240 193 1055 1680 2394 1447 1145 178 1378 1881 982 1911 2210 1232 633 171 1673 1785 2359 2231 2048 683 2170 183 2490 2227 1427 18 1737 2103 2499 1262 1158 564 1682 2284 1904 449 1533 2381 2147 2484 2440 1335 2447 2480 162 1272 1858 1411 2410 1222 1439 945 379 2234 173 522 1571 2113 762 338 995 76 1166 1750 1984 187 1194 531 1728 230 229 1426 963 314 2013 185 1760 1671 1139 228 534 2436 1868 1564 2032 2327 1691 1127 1590 2191 894 1396 1035 1601 2128 1373 296 1790 1921 2380 1531 1740 1442 1925 773 657 1940 2168 757 357 478 1643 634 1108 2431 1141 1116 68 142 1543 254 650 494 1196 956 2329 1092 353 1218 870 875 1298 2261 170 722 141 712 1693 2446 1635 2307 485 1699 1869 951 846 2213 2287 2084 421 1853 992 517 1871 521 1537 42 303 518 1979 2189 265 1082 1186 1030 2452 572 386 2299 2408 1305 344 759 1077 1716 288 603 1663 251 1202 2268 2097 1142 354 1161 322 1675 1466 706 2172 965 461 1164 2311 210 2131 994 1686 607 2177 1727 2313 217 1293 1751 527 65 1579 220 2250 575 1735 2145 1996 725 1958 117 1521 2277 2385 793 2308 747 397 2274 1328 172 844 985 896 680 155 998 543 1368 1278 415 60 1084 17 2255 312 537 1261 2368 2282 735 2476 2309 1254 1535 1093 267 758 259 2193 883 116 1357 2215 1707 1553 2441 2183 1045 1796 1875 2076 918 2322 1415 2449 1251 5 718 1047 1425 376 677 1850 1136 1081 290 2111 2494 343 2479 1408 1171 2208 1894 1336 1764 2345 1245 1832 368 821 1997 1889 1109 1264 1394 2209 688 1170 1622 104 1569 2059 621 206 40 2296 1354 967 1268 1995 1576 511 2398 1960 580 800 1184 1612 2082 1416 47 1616 1648 2239 239 791 1146 463 1747 282 728 2432 891 1964 933 863 1459 915 1449 2417 1971 1240 1865 332 869 1135 1746 1437 1440 497 271 969 1886 1749 1032 1060 439 1651 1400 1048 232 26 2387 392 1333 1132 2010 1450 1797 175 1739 78 1573 334 2221 547 1835 585 642 1355 255 2461 1507 1906 2086 1300 936 553 1967 1418 1837 2249 283 84 2392 566 253 1860 1255 743 23 1793 763 120 1508 981 737 750 606 297 2375 381 1771 1392 1401 90 991 2456 1976 2496 1811 2224 540 1809 2352 2140 1183 286 1090 1346 1896 276 2060 671 797 2369 2482 292 1577 2413 997 2251 2161 1990 1938 1499 582 275 525 1347 2339 1916 1969 1246 559 2225 1054 1302 839 569 152 914 1031 769 2386 1562 1582 1205 695 446 2046 404 890 1334 77 237 372 1554 2040 2493 1399 2471 1079 1589 472 1478 1273 1934 1419 1312 356 41 1065 1814 2035 1520 2019 1912 929 238 95 156 1405 2166 105 1704 107 565 8 2372 473 1985 1706 1325 2107 2124 2014 140 845 1242 1089 505 932 755 1703 1511 733 1361 1715 1315 2066 751 2152 69 721 2002 1455 168 957 2412 1609 2364 2283 88 2047 611 1056 2155 1523 31 262 1526 1879 340 377 2425 1614 2379 1390 182 2333 756 1610 802 307 1512 99 701 1436 483 405 1898 28 2050 2389 648 1498 1624 181 66 306 2089 1848 135 1924 273 177 1825 2037 2288 587 2033 2448 2267 1297 1369 1243 43 1 1559 64 1192 1986 1005 2197 1314 2199 1119 1977 1429 2203 514 2149 1384 2078 1443 2180 1364 1993 887 776 1761 840 2080 943 2105 560 302 2418 555 2045 1188 82 131 1611 197 1266 1071 1550 961 970 1613 2041 2202 1435 944 1256 129 97 2320 1621 920 1656 490 1968 1120 842 538 1778 1380 1631 2039 1565 1606 1580 2246 1854 315 1670 111 32 466 1130 1567 1363 2169 1398 1362 226 818 1994 242 2061 1600 310 1049 2216 2314 716 1413 977 811 2337 1389 563 827 912 359 1385 1597 2459 2204 1375 1169 654 378 2122 749 1456 1241 1915 723 2281 996 2336 1587 629 55 258 748 851 2454 1052 1203 2286 2143 2077 264 948 693 241 1476 1280 2438 2371 1893 1801 866 1422 1954 2263 80 2036 636 153 1252 1669 796 1342 2264 2276 1586 52 1843 2079 222 2195 2017 1233 852 1981 1098 903 2382 2043 1414 2430 849 795 179 134 1572 2259 1388 978 2016 993 1234 980 643 1464 2340 1039 1745 591 1782 2469 1668 2120 1636 2146 790 1062 1348 568 2132 656 2021 673 631 2472 1762 1228 593 1040 860 647 136 909 2029 1096 1787 2176 2457 1321 1818 431 515 1274 616 1253 1226 1769 442 464 661 1826 1304 2443 810 940 1046 435 1692 1204 1766 813 2383 895 360 188 1129 9 1623 645 526 519 1806 1221 640 1798 2324 1006 2162 1200 658 1460 2341 588 2421 1591 61 778 649 1902 1484 1532 216 1872 1563 533 496 462 1884 859 744 133 1027 2074 502 1972 1493 789 373 440 2070 2462 687 425 1946 145 1428 101 1645 685 2465 2073 1991 335 897 1110 506 263 363 760 137 257 1980 862 1816 1619 705 1011 202 664 2351 479 348 1292 663 2365 872 884 907 158 1331 2142 396 37 2196 2326 926 1322 1462 477 2445 422 2144 921 1557 2049 328 2219 1468 536 419 535 779 781 49 1988 710 2096 1942 544 410 1482 1817 1404 2034 2444 1441 492 1936 681 545 752 922 736 1800 1341 2265 1465 2233 59 986 1933 670 1114 2098 123 1285 89 1074 1310 369 2376 2171 2237 2358 1935 387 2157 1198 1148 1803 7 577 1275 36 1327 1487 1121 2134 326 768 1059 953 1448 624 1989 93 198 400 2064 2100 1073 1731 2201 1103 1491 16 1247 512 770 1753 2500 2297 2087 1744 1909 27 1592 248 424 777 30 1432 243 1470 1051 1861 609 908 1748 1208 1458 1201 1248 761 287 1928 2052 1802 75 765 2154 812 713 900 1607 154 2020 1494 2181 1679 2300 277 674 1892 2370 1359 1102 2485 454 1481 1804 1042 567 311 1873 163 2141 231 2488 1020 391 911 1534 1236 792 1337 586 1216 261 1365 413 1316 1263 1123 233 689 1329 298 1666 176 2164 1965 2354 1307 225 121 628 1962 1649 2068 1558 1421 2497 1220 772 1765 806 1356 1717 847 2094 1729 646 1588 98 2184 491 2483 1629 414 682 499 484 700 1540 1901 678 835 602 1017 1834 147 1138 1176 119 2207 2217 1681 1617 399 964 143 989 2367 432 955 1603 1299 2347 843 935 2185 2310 2095 1475 1529 2179 2126 184 684 1615 186 1351 1034 2262 2110 2388 2163 786 2167 20 780 1133 1012 1690 1515 2018 856 1445 595 1930 1229 641 2415 1725 486 541 853 2487 1546 734 946 1038 1303 1178 1542 2378 416 1688 1608 1091 1382 2356 1931 2008 1126 2275 1866 652 551 44 2139 1403 1250 2075 1781 1151 2235 2306 2081 436 1412 2001 592 2420 24 366 1452 987 390 1923 686 2481 1397 455 594 2148 1100 1847 2054 1473 1500 2492 879 417 289 1128 2402 1856 1118 433 1841 753 1883 637 1177 1575 452 1514 1598 1978 1708 659 1496 1078 2458 2186 731 590 524 573 1260 975 2315 1353 1016 2426 2256 1271 617 548 2220 199 160 299 2292 1446 352 1510 1953 2109 208 715 2115 2427 1819 192 660 2466 1143 1313 934 1050 1922 952 1480 2006 1961 2253 1718 22 1168 988 666 971 330 1155 1975 632 1905 447 2401 2405 1211 1043 1752 1812 1279 201 1160 2348 1773 169 1153 92 1086 1044 1807 635 465 2495 1284 281 651 474 11 2319 2395 304 1836 1206 787 1338 1730 1318 1742 817 958 2044 367 2031 403 1696 393 1306 1080 1350 469 1862 1058 794 850 1503 2316 2067 1066 1659 128 1808 1833 2260 1179 1585 1822 937 2153 2042 578 667 1477 546 268 803 2114 950 1483 608 516 2474 941 2026 2242 625 1913 227 2384 1654 2118 848 2174 249 2350 164 1239 1230 1376 50 1897 1495 2055 1423 1665 724 1288 2303 2478 398 450 1658 858 318 905 2342 2325 6 453 1549 1939 1061 1952 711 2323 48 487 2269 873 1330 409 561 456 1734 1701 1026 35 824 2435 1719 74 1420 871 2428 696 118 1319 1828 1182 740 745 976 350 1687 530 2344 1041 408 881 2057 39 1238 385 54 2312 21 427 2467 2423 246 12 130 1320 807 2165 877 1501 250 1551 293 2156 1908 475 2409 2009 1015 1490 445 1068 389 1768 1172 2330 323 1159 481 1937 1647 1895 125 1225 1358 1548 411 1642 1770 542 1859 2317 2279 605 1301 1566 668 402 2226 2278 2012 837 1667 604 2236 211 167 1918 1626 272 1711 2027 2335 190 1258 726 2399 1596 2293 412 1539 1560 615 816 1644 38 1547 1604 1637 1982 1488 336 1683 1492 782 1786 672 2108 2473 2230 320 754 207 1430 902 1910 584 1685 727 1528 2470 1237 1000 2117 482 771 1678 2056 2489 331 1257 1150 1887 365 2218 838 1578 100 151 984 1025 1259 886 166 513 1189 2023 317 767 2229 1386 1075 1099 1286 2433 2360 108 1655 1003 2411 91 351 1294 87 195 539 655 2414 1270 15 698 57 407 1057 2477 1775 1963 115 1371 2092

[出力例]
7740144875

[入力例]

2 3 1

[出力例]

※AtCoderテストケースより

[入力例]

1 2 3 4 5

[出力例]

※AtCoderテストケースより

[入力例]

8 2 7 3 4 5 6 1

[出力例]

136

※AtCoderテストケースより

[入力例]

1 2

[出力例]

[入力例]

5 7 4 1 10 9 6 3 2 8

[出力例]

313

[入力例]

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

[出力例]

50685

[入力例]

500

377 148 304 214 25 117 54 93 176 65 52 185 498 436 420 412 365 153 409 10 218 104 99 141 184 250 62 11 90 437 26 46 350 228 398 139 376 361 380 466 288 3 279 140 108 340 423 367 208 385 158 63 277 446 478 271 440 323 337 439 318 491 364 308 5 40 322 269 127 237 303 390 276 387 258 4 328 315 346 424 389 143 285 333 6 459 8 273 164 101 201 111 188 356 120 53 110 81 313 225 247 317 255 150 28 434 467 464 403 371 60 112 488 292 402 357 426 235 226 106 332 421 198 351 425 254 195 31 13 219 383 260 173 494 363 163 186 246 345 94 204 449 309 166 15 335 352 314 211 232 455 114 443 115 147 233 165 89 282 64 142 240 430 413 72 203 71 294 224 167 121 79 59 388 453 362 170 1 36 135 14 396 190 347 393 399 41 457 193 159 448 321 395 220 287 368 378 493 354 267 476 245 391 102 408 187 43 284 431 486 22 298 468 251 252 359 341 180 48 179 316 35 116 427 401 217 128 319 16 87 126 207 76 33 349 202 155 21 261 311 75 404 131 484 84 24 500 256 348 156 161 381 97 230 382 435 289 66 206 327 133 344 263 137 212 44 428 32 86 2 305 253 229 134 400 296 405 290 61 334 236 91 172 80 98 372 394 241 414 302 306 264 418 268 485 370 38 70 100 17 223 410 373 419 162 95 171 169 310 221 29 18 496 295 473 58 227 145 407 49 462 450 441 358 312 154 411 125 499 136 461 23 192 96 123 366 55 301 174 88 210 438 30 68 360 353 336 331 375 326 160 320 286 479 458 415 417 330 37 105 481 281 119 422 83 205 259 447 77 452 470 249 73 168 149 278 243 12 69 272 124 463 152 291 483 56 42 406 178 231 416 300 432 222 132 343 182 197 45 293 213 274 191 454 200 355 270 487 78 183 181 109 74 477 122 244 451 480 307 57 474 374 177 239 129 146 248 39 429 460 138 471 379 92 27 324 9 209 215 342 262 433 175 50 445 238 196 444 283 242 492 19 189 469 82 497 266 67 369 490 103 51 475 495 465 113 34 472 144 265 392 339 442 299 199 329 338 456 151 85 118 325 107 489 386 275 384 482 280 7 257 297 194 234 216 397 47 157 130 20

[出力例]

60354172

[入力例]

2500

785 1950 694 1393 942 878 2101 1097 2338 1174 438 1467 221 1083 2248 742 1956 1876 2244 1339 81 2123 1524 1792 1021 2187 596 1144 600 1235 1210 2295 841 954 110 45 1772 528 1067 444 1714 2028 1085 2062 1191 196 1674 2022 1920 2442 2334 1115 2321 1780 1497 867 1117 2266 1087 2090 468 2257 1842 498 1878 983 34 1634 885 2004 1830 1317 295 1349 2138 1395 1599 2252 2136 1249 347 979 2125 1943 1630 1949 429 218 2160 2450 820 855 1676 719 418 861 1007 200 1863 493 327 1877 2238 1265 1367 1932 931 504 1639 1417 285 1795 1438 999 1530 480 1214 1070 1471 94 1036 2463 2206 1605 1289 1105 476 1457 374 53 639 832 1185 1867 1702 278 889 2030 1088 1018 2223 1638 2247 1407 247 510 2434 2065 1004 1506 784 614 738 86 189 836 707 324 1518 448 1570 345 1974 1283 570 1903 1308 291 1684 245 557 1914 256 1340 423 2289 1957 127 1489 85 1014 388 106 523 1999 1343 1162 2305 401 809 1366 2424 1700 2058 571 2005 194 2271 2003 1195 730 1855 161 822 2083 1472 70 1732 144 458 1757 799 925 1890 2464 1291 1813 1124 1409 260 236 1147 467 1479 51 1505 13 333 124 1759 471 1694 1344 1485 1831 1583 1628 2258 833 62 1827 383 972 1944 96 1824 2000 1360 488 1029 342 1545 355 1851 868 1064 1072 1001 2194 1951 1929 2116 788 746 1326 1899 1767 831 1113 2362 1377 1069 2038 1983 294 562 46 1695 2222 443 1777 1157 1227 1282 2200 579 269 1193 459 2129 919 1516 1653 215 1763 2015 1402 83 599 370 14 362 876 1712 973 1212 1190 219 1661 829 2453 927 1864 741 157 959 697 709 1137 2085 1076 1820 938 1882 1724 1213 1175 457 1705 2290 2272 2190 460 2072 1173 638 966 1966 1509 529 2198 2093 864 1410 507 1710 1131 2240 1754 1374 19 1874 653 1028 1345 1180 1561 1720 1602 2346 1199 601 622 924 627 319 2088 764 2416 1941 1948 1519 2468 930 205 1595 865 371 1541 702 906 819 2051 2373 2390 316 2366 2437 1743 1002 613 2404 1352 1677 1900 2211 2158 1267 305 947 138 2011 2150 2422 1209 470 1013 904 1722 309 1187 329 102 2393 1277 2188 1810 2361 279 2104 1106 1594 574 1019 1660 146 1290 213 1947 430 2241 2302 180 1839 893 626 1779 1525 1536 2349 2273 1721 495 1387 112 1140 2403 1838 623 882 337 1424 1625 224 520 692 214 783 361 380 923 669 1324 1111 1741 798 2353 1726 2301 266 619 1650 212 1556 1698 1287 1815 1391 63 2130 1805 1959 209 284 2 2245 1774 1486 1433 552 2178 732 899 610 1907 3 814 1789 1434 139 665 1053 1736 1224 1987 2391 962 679 597 1840 598 774 1733 1552 501 308 2192 114 888 2175 1010 1852 808 1463 1513 1219 33 823 358 2280 1023 2455 280 1383 804 1927 556 1794 2291 1332 620 2007 892 1646 1522 699 703 916 662 1880 79 1022 1152 612 1181 1451 775 346 898 558 1689 801 1269 1231 1885 874 1857 339 325 2498 2254 1784 235 2127 349 1662 71 1973 857 1406 58 1156 126 1107 2243 67 2159 2182 1544 1295 489 1223 2318 1870 1844 676 1627 2406 2328 1296 1641 113 2119 1125 321 1758 508 2025 1454 132 500 1033 1919 691 2451 2228 1149 949 1217 1799 2343 1370 1829 2294 1821 2106 990 2102 1037 1738 1244 2304 1154 854 2121 1469 1431 1112 717 1620 968 2298 1444 364 1917 1955 1618 1584 2377 395 1791 1640 1461 300 1008 1165 223 708 2396 1163 2135 1823 901 72 165 1276 939 1849 1593 174 109 2486 191 2091 815 1167 974 1574 1723 826 1122 1657 2173 1970 4 913 917 384 1633 406 2137 2071 1281 2363 159 1517 1527 252 25 1372 2205 1555 1094 301 1945 375 1664 1379 960 690 2429 675 928 1672 1381 1581 1697 1134 550 1652 1713 1926 2212 2285 1197 2151 704 1101 618 509 2407 830 270 739 428 1755 2024 149 2439 56 10 203 2133 2355 714 1998 1474 2374 1538 437 910 2397 1568 1009 583 441 234 103 2053 1846 1215 1776 2332 805 1845 2419 1311 426 720 576 382 2491 434 122 394 2232 1788 341 420 1453 1309 1709 451 2460 549 2475 880 503 2112 204 2400 244 581 274 1888 1207 2099 532 313 2069 1063 1992 2331 2063 1323 150 1024 1891 73 630 2270 1504 1632 1783 1104 2357 2214 1502 644 766 554 589 828 148 825 834 1095 29 1756 729 240 193 1055 1680 2394 1447 1145 178 1378 1881 982 1911 2210 1232 633 171 1673 1785 2359 2231 2048 683 2170 183 2490 2227 1427 18 1737 2103 2499 1262 1158 564 1682 2284 1904 449 1533 2381 2147 2484 2440 1335 2447 2480 162 1272 1858 1411 2410 1222 1439 945 379 2234 173 522 1571 2113 762 338 995 76 1166 1750 1984 187 1194 531 1728 230 229 1426 963 314 2013 185 1760 1671 1139 228 534 2436 1868 1564 2032 2327 1691 1127 1590 2191 894 1396 1035 1601 2128 1373 296 1790 1921 2380 1531 1740 1442 1925 773 657 1940 2168 757 357 478 1643 634 1108 2431 1141 1116 68 142 1543 254 650 494 1196 956 2329 1092 353 1218 870 875 1298 2261 170 722 141 712 1693 2446 1635 2307 485 1699 1869 951 846 2213 2287 2084 421 1853 992 517 1871 521 1537 42 303 518 1979 2189 265 1082 1186 1030 2452 572 386 2299 2408 1305 344 759 1077 1716 288 603 1663 251 1202 2268 2097 1142 354 1161 322 1675 1466 706 2172 965 461 1164 2311 210 2131 994 1686 607 2177 1727 2313 217 1293 1751 527 65 1579 220 2250 575 1735 2145 1996 725 1958 117 1521 2277 2385 793 2308 747 397 2274 1328 172 844 985 896 680 155 998 543 1368 1278 415 60 1084 17 2255 312 537 1261 2368 2282 735 2476 2309 1254 1535 1093 267 758 259 2193 883 116 1357 2215 1707 1553 2441 2183 1045 1796 1875 2076 918 2322 1415 2449 1251 5 718 1047 1425 376 677 1850 1136 1081 290 2111 2494 343 2479 1408 1171 2208 1894 1336 1764 2345 1245 1832 368 821 1997 1889 1109 1264 1394 2209 688 1170 1622 104 1569 2059 621 206 40 2296 1354 967 1268 1995 1576 511 2398 1960 580 800 1184 1612 2082 1416 47 1616 1648 2239 239 791 1146 463 1747 282 728 2432 891 1964 933 863 1459 915 1449 2417 1971 1240 1865 332 869 1135 1746 1437 1440 497 271 969 1886 1749 1032 1060 439 1651 1400 1048 232 26 2387 392 1333 1132 2010 1450 1797 175 1739 78 1573 334 2221 547 1835 585 642 1355 255 2461 1507 1906 2086 1300 936 553 1967 1418 1837 2249 283 84 2392 566 253 1860 1255 743 23 1793 763 120 1508 981 737 750 606 297 2375 381 1771 1392 1401 90 991 2456 1976 2496 1811 2224 540 1809 2352 2140 1183 286 1090 1346 1896 276 2060 671 797 2369 2482 292 1577 2413 997 2251 2161 1990 1938 1499 582 275 525 1347 2339 1916 1969 1246 559 2225 1054 1302 839 569 152 914 1031 769 2386 1562 1582 1205 695 446 2046 404 890 1334 77 237 372 1554 2040 2493 1399 2471 1079 1589 472 1478 1273 1934 1419 1312 356 41 1065 1814 2035 1520 2019 1912 929 238 95 156 1405 2166 105 1704 107 565 8 2372 473 1985 1706 1325 2107 2124 2014 140 845 1242 1089 505 932 755 1703 1511 733 1361 1715 1315 2066 751 2152 69 721 2002 1455 168 957 2412 1609 2364 2283 88 2047 611 1056 2155 1523 31 262 1526 1879 340 377 2425 1614 2379 1390 182 2333 756 1610 802 307 1512 99 701 1436 483 405 1898 28 2050 2389 648 1498 1624 181 66 306 2089 1848 135 1924 273 177 1825 2037 2288 587 2033 2448 2267 1297 1369 1243 43 1 1559 64 1192 1986 1005 2197 1314 2199 1119 1977 1429 2203 514 2149 1384 2078 1443 2180 1364 1993 887 776 1761 840 2080 943 2105 560 302 2418 555 2045 1188 82 131 1611 197 1266 1071 1550 961 970 1613 2041 2202 1435 944 1256 129 97 2320 1621 920 1656 490 1968 1120 842 538 1778 1380 1631 2039 1565 1606 1580 2246 1854 315 1670 111 32 466 1130 1567 1363 2169 1398 1362 226 818 1994 242 2061 1600 310 1049 2216 2314 716 1413 977 811 2337 1389 563 827 912 359 1385 1597 2459 2204 1375 1169 654 378 2122 749 1456 1241 1915 723 2281 996 2336 1587 629 55 258 748 851 2454 1052 1203 2286 2143 2077 264 948 693 241 1476 1280 2438 2371 1893 1801 866 1422 1954 2263 80 2036 636 153 1252 1669 796 1342 2264 2276 1586 52 1843 2079 222 2195 2017 1233 852 1981 1098 903 2382 2043 1414 2430 849 795 179 134 1572 2259 1388 978 2016 993 1234 980 643 1464 2340 1039 1745 591 1782 2469 1668 2120 1636 2146 790 1062 1348 568 2132 656 2021 673 631 2472 1762 1228 593 1040 860 647 136 909 2029 1096 1787 2176 2457 1321 1818 431 515 1274 616 1253 1226 1769 442 464 661 1826 1304 2443 810 940 1046 435 1692 1204 1766 813 2383 895 360 188 1129 9 1623 645 526 519 1806 1221 640 1798 2324 1006 2162 1200 658 1460 2341 588 2421 1591 61 778 649 1902 1484 1532 216 1872 1563 533 496 462 1884 859 744 133 1027 2074 502 1972 1493 789 373 440 2070 2462 687 425 1946 145 1428 101 1645 685 2465 2073 1991 335 897 1110 506 263 363 760 137 257 1980 862 1816 1619 705 1011 202 664 2351 479 348 1292 663 2365 872 884 907 158 1331 2142 396 37 2196 2326 926 1322 1462 477 2445 422 2144 921 1557 2049 328 2219 1468 536 419 535 779 781 49 1988 710 2096 1942 544 410 1482 1817 1404 2034 2444 1441 492 1936 681 545 752 922 736 1800 1341 2265 1465 2233 59 986 1933 670 1114 2098 123 1285 89 1074 1310 369 2376 2171 2237 2358 1935 387 2157 1198 1148 1803 7 577 1275 36 1327 1487 1121 2134 326 768 1059 953 1448 624 1989 93 198 400 2064 2100 1073 1731 2201 1103 1491 16 1247 512 770 1753 2500 2297 2087 1744 1909 27 1592 248 424 777 30 1432 243 1470 1051 1861 609 908 1748 1208 1458 1201 1248 761 287 1928 2052 1802 75 765 2154 812 713 900 1607 154 2020 1494 2181 1679 2300 277 674 1892 2370 1359 1102 2485 454 1481 1804 1042 567 311 1873 163 2141 231 2488 1020 391 911 1534 1236 792 1337 586 1216 261 1365 413 1316 1263 1123 233 689 1329 298 1666 176 2164 1965 2354 1307 225 121 628 1962 1649 2068 1558 1421 2497 1220 772 1765 806 1356 1717 847 2094 1729 646 1588 98 2184 491 2483 1629 414 682 499 484 700 1540 1901 678 835 602 1017 1834 147 1138 1176 119 2207 2217 1681 1617 399 964 143 989 2367 432 955 1603 1299 2347 843 935 2185 2310 2095 1475 1529 2179 2126 184 684 1615 186 1351 1034 2262 2110 2388 2163 786 2167 20 780 1133 1012 1690 1515 2018 856 1445 595 1930 1229 641 2415 1725 486 541 853 2487 1546 734 946 1038 1303 1178 1542 2378 416 1688 1608 1091 1382 2356 1931 2008 1126 2275 1866 652 551 44 2139 1403 1250 2075 1781 1151 2235 2306 2081 436 1412 2001 592 2420 24 366 1452 987 390 1923 686 2481 1397 455 594 2148 1100 1847 2054 1473 1500 2492 879 417 289 1128 2402 1856 1118 433 1841 753 1883 637 1177 1575 452 1514 1598 1978 1708 659 1496 1078 2458 2186 731 590 524 573 1260 975 2315 1353 1016 2426 2256 1271 617 548 2220 199 160 299 2292 1446 352 1510 1953 2109 208 715 2115 2427 1819 192 660 2466 1143 1313 934 1050 1922 952 1480 2006 1961 2253 1718 22 1168 988 666 971 330 1155 1975 632 1905 447 2401 2405 1211 1043 1752 1812 1279 201 1160 2348 1773 169 1153 92 1086 1044 1807 635 465 2495 1284 281 651 474 11 2319 2395 304 1836 1206 787 1338 1730 1318 1742 817 958 2044 367 2031 403 1696 393 1306 1080 1350 469 1862 1058 794 850 1503 2316 2067 1066 1659 128 1808 1833 2260 1179 1585 1822 937 2153 2042 578 667 1477 546 268 803 2114 950 1483 608 516 2474 941 2026 2242 625 1913 227 2384 1654 2118 848 2174 249 2350 164 1239 1230 1376 50 1897 1495 2055 1423 1665 724 1288 2303 2478 398 450 1658 858 318 905 2342 2325 6 453 1549 1939 1061 1952 711 2323 48 487 2269 873 1330 409 561 456 1734 1701 1026 35 824 2435 1719 74 1420 871 2428 696 118 1319 1828 1182 740 745 976 350 1687 530 2344 1041 408 881 2057 39 1238 385 54 2312 21 427 2467 2423 246 12 130 1320 807 2165 877 1501 250 1551 293 2156 1908 475 2409 2009 1015 1490 445 1068 389 1768 1172 2330 323 1159 481 1937 1647 1895 125 1225 1358 1548 411 1642 1770 542 1859 2317 2279 605 1301 1566 668 402 2226 2278 2012 837 1667 604 2236 211 167 1918 1626 272 1711 2027 2335 190 1258 726 2399 1596 2293 412 1539 1560 615 816 1644 38 1547 1604 1637 1982 1488 336 1683 1492 782 1786 672 2108 2473 2230 320 754 207 1430 902 1910 584 1685 727 1528 2470 1237 1000 2117 482 771 1678 2056 2489 331 1257 1150 1887 365 2218 838 1578 100 151 984 1025 1259 886 166 513 1189 2023 317 767 2229 1386 1075 1099 1286 2433 2360 108 1655 1003 2411 91 351 1294 87 195 539 655 2414 1270 15 698 57 407 1057 2477 1775 1963 115 1371 2092

[出力例]

7740144875

■参照サイト
AtCoder Beginner Contest 140

2022年3月19日

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

C++の練習を兼ねて, AtCoder Regular Contest 029 の問題C (高橋君と国家) を解いてみた.

■感想.
1. 問題Cは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 最小全域木(Kruskal’s Algorithm) の復習が出来たので, 非常に良かったと思う.
※ 公式のライブラリを拝借させて頂いてます.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://www.slideshare.net/chokudai/arc029
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vi = vector<int>;
using T3 = tuple<int, int, 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 all(x) x.begin(), x.end()

// https://github.com/atcoder/live_library/blob/master/uf.cpp
// UnionFind
// coding: https://youtu.be/TdR816rqc3s?t=726
// comment: https://youtu.be/TdR816rqc3s?t=6822
// -> 一部改変.
struct UnionFind{
    vi d;
    UnionFind(int n = 0): d(n, -1) {}
    int find(int x){
        return (d[x] < 0) ? x : (d[x] = find(d[x]));
    }
    bool unite(int x, int y){
        x = find(x);
        y = find(y);
        if(x == y) return false;
        if(d[x] > d[y]) swap(x, y);
        d[x] += d[y];
        d[y] = x;
        return true;
    }
    bool same(int x, int y){
        return find(x) == find(y);
    }
    int size(int x){
        return -d[find(x)];
    }
};

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    vector<T3> t;
    rep(i, N){
        int c;
        scanf("%d", &c);
        t.emplace_back(c, 0, i + 1);
    }
    rep(i, M){
        int a, b, r;
        scanf("%d %d %d", &a, &b, &r);
        t.emplace_back(r, a, b);
    }
    
    // 2. sort.
    sort(all(t));
    
    // 3. 最小全域木(Kruskal's Algorithm) の 構築.
    // 競プロ典型 90 問 (049 - Flip Digits 2)
    // https://github.com/E869120/kyopro_educational_90/blob/main/sol/049.cpp
    LL ans = 0;
    UnionFind uf(N + 2);
    rep(i, t.size()){
        // 3-1. グラフ情報.
        int u = get<1>(t[i]); // 頂点.
        int v = get<2>(t[i]); // 頂点.
        int c = get<0>(t[i]); // コスト.
        
        // 3-2. 辺を追加するか？
        if(!uf.same(u, v)){
            // 辺を追加.
            uf.unite(u, v);
            
            // コスト更新.
            ans += (LL)c;
        }
    }
    
    // 4. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vi = vector<int>;

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

// https://github.com/atcoder/live_library/blob/master/uf.cpp

// UnionFind

// coding: https://youtu.be/TdR816rqc3s?t=726

// comment: https://youtu.be/TdR816rqc3s?t=6822

// -> 一部改変.

struct UnionFind{

vi d;

UnionFind(int n = 0): d(n, -1) {}

int find(int x){

return (d[x] < 0) ? x : (d[x] = find(d[x]));

}

bool unite(int x, int y){

x = find(x);

y = find(y);

if(x == y) return false;

if(d[x] > d[y]) swap(x, y);

d[x] += d[y];

d[y] = x;

return true;

}

bool same(int x, int y){

return find(x) == find(y);

}

int size(int x){

return -d[find(x)];

}

};

int main(){

// 1. 入力情報.

int N, M;

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

vector<T3> t;

rep(i, N){

int c;

scanf("%d", &c);

t.emplace_back(c, 0, i + 1);

}

rep(i, M){

int a, b, r;

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

t.emplace_back(r, a, b);

}

// 2. sort.

sort(all(t));

// 3. 最小全域木(Kruskal's Algorithm) の構築.

// 競プロ典型 90 問 (049 - Flip Digits 2)

// https://github.com/E869120/kyopro_educational_90/blob/main/sol/049.cpp

LL ans = 0;

UnionFind uf(N + 2);

rep(i, t.size()){

// 3-1. グラフ情報.

int u = get<1>(t[i]); // 頂点.

int v = get<2>(t[i]); // 頂点.

int c = get<0>(t[i]); // コスト.

// 3-2. 辺を追加するか？

if(!uf.same(u, v)){

// 辺を追加.

uf.unite(u, v);

// コスト更新.

ans += (LL)c;

}

// 4. 出力.

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

return 0;

}

[入力例]
7 8
40
50
30
70
70
80
80
1 2 40
1 3 50
1 4 60
2 5 90
3 4 80
4 5 110
5 6 60
6 7 50

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

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

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

[入力例]
5 7
80
70
60
50
40
1 3 20
1 4 70
1 5 30
2 3 30
2 4 90
3 4 40
4 5 80

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

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

[出力例]
6

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

[出力例]
11

[入力例]
10 15
51
86
103
40
72
92
108
39
22
16
1 2 17
1 3 18
1 5 12
2 3 17
2 8 27
3 10 18
4 5 29
4 6 8
5 6 16
4 10 21
6 9 5
7 8 11
7 9 20
7 10 1
8 9 8

[出力例]
111

100

101

102

103

104

105

106

107

108

[入力例]

7 8

1 2 40

1 3 50

1 4 60

2 5 90

3 4 80

4 5 110

5 6 60

6 7 50

[出力例]

350

※AtCoderテストケースより

[入力例]

3 3

1 2 60

1 3 60

2 3 60

[出力例]

150

※AtCoderテストケースより

[入力例]

5 7

1 3 20

1 4 70

1 5 30

2 3 30

2 4 90

3 4 40

4 5 80

[出力例]

160

※AtCoderテストケースより

[入力例]

3 3

1 3 1

2 3 2

1 2 6

[出力例]

[入力例]

3 3

1 2 9

1 3 8

2 3 3

[出力例]

[入力例]

10 15

103

108

1 2 17

1 3 18

1 5 12

2 3 17

2 8 27

3 10 18

4 5 29

4 6 8

5 6 16

4 10 21

6 9 5

7 8 11

7 9 20

7 10 1

8 9 8

[出力例]

111

■参照サイト
AtCoder Regular Contest 029
Union-Find木
 競プロ典型 90 問の問題049

2022年3月18日

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

C++の練習を兼ねて, AtCoder Regular Contest 035 の問題C (アットコーダー王国の交通事情) を解いてみた.

■感想.
1. 問題Cは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. Warshall–Floyd法の復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://www.slideshare.net/chokudai/arc035
// 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 d[404][404];

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    rep(i, N) rep(j, N) if(i != j) d[i][j] = INF;
    rep(i, M){
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        --a, --b;
        d[a][b] = c;
        d[b][a] = c;
    }
    
    // 2. Warshall–Floyd法(※各頂点間の最短距離を保存).
    rep(k, N) rep(i, N) rep(j, N) d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
    
    // 3. クエリ回答.
    int K;
    scanf("%d", &K);
    rep(_, K){
        // 3-1. 道路を新たに建設.
        int x, y, z;
        scanf("%d %d %d", &x, &y, &z);
        --x, --y;
        
        // 3-2. 最短距離更新.
        rep(i, N) rep(j, N) d[i][j] = min({d[i][j], d[i][x] + d[y][j] + (LL)z, d[i][y] + d[x][j] + (LL)z});
        
        // 3-3. 幸福度.
        LL ans = 0;
        rep(i, N) repx(j, i + 1, N) ans += d[i][j];
        printf("%lld\n", ans);
    }
    return 0;
    
}

// 解き直し.

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

// 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 d[404][404];

int main(){

// 1. 入力情報.

int N, M;

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

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

rep(i, M){

int a, b, c;

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

--a, --b;

d[a][b] = c;

d[b][a] = c;

}

// 2. Warshall–Floyd法(※各頂点間の最短距離を保存).

rep(k, N) rep(i, N) rep(j, N) d[i][j] = min(d[i][j], d[i][k] + d[k][j]);

// 3. クエリ回答.

int K;

scanf("%d", &K);

rep(_, K){

// 3-1. 道路を新たに建設.

int x, y, z;

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

--x, --y;

// 3-2. 最短距離更新.

rep(i, N) rep(j, N) d[i][j] = min({d[i][j], d[i][x] + d[y][j] + (LL)z, d[i][y] + d[x][j] + (LL)z});

// 3-3. 幸福度.

LL ans = 0;

rep(i, N) repx(j, i + 1, N) ans += d[i][j];

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

}

return 0;

}

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

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

[入力例]
8 16
8 7 38
2 8 142
5 2 722
8 6 779
4 6 820
1 3 316
1 7 417
8 3 41
1 4 801
3 2 126
4 2 71
8 4 738
4 3 336
7 5 717
5 6 316
2 1 501
10
6 1 950
6 1 493
1 6 308
3 4 298
2 5 518
1 5 402
4 7 625
7 6 124
3 8 166
2 4 708

[出力例]
13649
12878
11954
11954
11280
11058
11058
8099
8099
8099
※AtCoderテストケースより

[入力例]
10 12
2 1 30
2 8 33
2 10 37
10 8 32
10 9 25
8 9 41
9 3 72
3 4 111
6 4 55
6 7 123
5 6 210
5 1 108
10
5 1 100
5 6 222
5 7 321
4 9 170
8 3 111
5 2 123
2 6 333
8 4 210
5 4 234
8 6 345

[出力例]
8338
8338
8314
8145
8143
8108
8108
8105
8074
8074

[入力例]

4 3

1 2 1

2 3 1

3 4 10

3 4 1

1 4 1

[出力例]

※AtCoderテストケースより

[入力例]

8 16

8 7 38

2 8 142

5 2 722

8 6 779

4 6 820

1 3 316

1 7 417

8 3 41

1 4 801

3 2 126

4 2 71

8 4 738

4 3 336

7 5 717

5 6 316

2 1 501

6 1 950

6 1 493

1 6 308

3 4 298

2 5 518

1 5 402

4 7 625

7 6 124

3 8 166

2 4 708

[出力例]

13649

12878

11954

11280

11058

8099

※AtCoderテストケースより

[入力例]

10 12

2 1 30

2 8 33

2 10 37

10 8 32

10 9 25

8 9 41

9 3 72

3 4 111

6 4 55

6 7 123

5 6 210

5 1 108

5 1 100

5 6 222

5 7 321

4 9 170

8 3 111

5 2 123

2 6 333

8 4 210

5 4 234

8 6 345

[出力例]

8338

8314

8145

8143

8108

8105

8074

■参照サイト
AtCoder Regular Contest 035

2022年3月18日

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

C++の練習を兼ねて, AtCoder Regular Contest 041 の問題C (ウサギ跳び) を解いてみた.

■感想.
1. 問題Cは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 実装に苦労したものの, 個人的には, 解説のロジックが, 不思議な印象を受けた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://www.slideshare.net/chokudai/arc041
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using P = pair<int, int>;
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 pof pop_front
#define pob pop_back
#define puf push_front
#define pub push_back
#define a first
#define b second

int main(){
    
    // 1. 入力情報.
    int N;
    LL L;
    scanf("%d %lld", &N, &L);
    vp v;
    rep(i, N){
        int x;
        char c[11];
        scanf("%d %s", &x, c);
        v.pub({x, ((c[0] == 'R') ? 1 : -1)});
    }
    
    // 2. ウサギを区間に分割.
    vvp rabbits;
    deque<P> dq;
    for(auto &p : v){
        // 空.
        if(dq.empty()){
            dq.pub(p);
            continue;
        }
        
        // 背中合わせでない.
        P r = dq.back();
        if(!(r.b == -1 && p.b == 1)) dq.pub(p);
        
        // 背中合わせである.
        if(r.b == -1 && p.b == 1){
            vp rabbit;
            while(!dq.empty()){
                rabbit.pub(dq.front());
                dq.pof();
            }
            rabbits.pub(rabbit);
            dq.pub(p);
        }
    }
    
    // 3. 残分を追加.
    vp rabbit;
    while(!dq.empty()){
        rabbit.pub(dq.front());
        dq.pof();
    }
    rabbits.pub(rabbit);
    /*
    for(auto &p : rabbits){
        for(auto &q : p) printf("%d %d\n", q.a, q.b);
        puts("------");
    }
    */
    
    // 4. 区間ごとに, 集計.
    LL ans = 0;
    for(auto &p : rabbits){
        // 4-1. 左向き, 右向きの個数.
        int l = 0, r = 0;
        LL lMin = L + 1, rMax = 0, t = 0;
        for(auto &q : p){
            if(q.b == -1){
                ++l;
                lMin = min(lMin, (LL)q.a);
            }
            if(q.b == +1){
                ++r;
                rMax = max(rMax, (LL)q.a);
            }
        }
        
        // 4-2. 左向き >= 右向き.
        if(l >= r){
            rep(i, r) t += (rMax - i - p[r - 1 - i].a);
            rep(i, l) t += (p[r + i].a - (i + 1) - rMax);
            ans += t;
        }
        
        // 4-3. 左向き < 右向き.
        if(l < r){
            rep(i, r) t += (lMin - (i + 1) - p[r - 1 - i].a);
            rep(i, l) t += (p[r + i].a - i - lMin);
            ans += t;
        }
    }
    
    // 5. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

110

111

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using P = pair<int, int>;

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

#define pob pop_back

#define puf push_front

#define pub push_back

#define a first

#define b second

int main(){

// 1. 入力情報.

int N;

LL L;

scanf("%d %lld", &N, &L);

vp v;

rep(i, N){

int x;

char c[11];

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

v.pub({x, ((c[0] == 'R') ? 1 : -1)});

}

// 2. ウサギを区間に分割.

vvp rabbits;

deque<P> dq;

for(auto &p : v){

// 空.

if(dq.empty()){

dq.pub(p);

continue;

}

// 背中合わせでない.

P r = dq.back();

if(!(r.b == -1 && p.b == 1)) dq.pub(p);

// 背中合わせである.

if(r.b == -1 && p.b == 1){

vp rabbit;

while(!dq.empty()){

rabbit.pub(dq.front());

dq.pof();

}

rabbits.pub(rabbit);

dq.pub(p);

}

// 3. 残分を追加.

vp rabbit;

while(!dq.empty()){

rabbit.pub(dq.front());

dq.pof();

}

rabbits.pub(rabbit);

for(auto &p : rabbits){

for(auto &q : p) printf("%d %d\n", q.a, q.b);

puts("------");

}

// 4. 区間ごとに, 集計.

LL ans = 0;

for(auto &p : rabbits){

// 4-1. 左向き, 右向きの個数.

int l = 0, r = 0;

LL lMin = L + 1, rMax = 0, t = 0;

for(auto &q : p){

if(q.b == -1){

++l;

lMin = min(lMin, (LL)q.a);

}

if(q.b == +1){

++r;

rMax = max(rMax, (LL)q.a);

}

// 4-2. 左向き >= 右向き.

if(l >= r){

rep(i, r) t += (rMax - i - p[r - 1 - i].a);

rep(i, l) t += (p[r + i].a - (i + 1) - rMax);

ans += t;

}

// 4-3. 左向き < 右向き.

if(l < r){

rep(i, r) t += (lMin - (i + 1) - p[r - 1 - i].a);

rep(i, l) t += (p[r + i].a - i - lMin);

ans += t;

}

// 5. 出力.

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

return 0;

}

[入力例]
1 5
1 R

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

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

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

[入力例]
4 10
1 L
5 R
6 L
10 R

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

[入力例]
1 7
7 L

[出力例]
6

[入力例]
2 5
2 R
4 L

[出力例]
1

[入力例]
5 20
5 R
8 R
12 L
15 L
17 L

[出力例]
16

[入力例]
7 25
2 R
5 L
8 R
11 R
12 L
15 R
17 L

[出力例]
5

[入力例]
19 55
2 R
5 L
8 R
11 R
12 L
15 R
17 L
19 R
22 R
27 R
29 R
33 R
35 L
40 L
43 L
48 R
49 L
52 L
54 L

[出力例]
50

[入力例]

1 5

1 R

[出力例]

※AtCoderのテストケースより

[入力例]

4 5

1 R

3 L

4 L

5 L

[出力例]

※AtCoderのテストケースより

[入力例]

4 10

1 L

5 R

6 L

10 R

[出力例]

※AtCoderのテストケースより

[入力例]

1 7

7 L

[出力例]

[入力例]

2 5

2 R

4 L

[出力例]

[入力例]

5 20

5 R

8 R

12 L

15 L

17 L

[出力例]

[入力例]

7 25

2 R

5 L

8 R

11 R

12 L

15 R

17 L

[出力例]

[入力例]

19 55

2 R

5 L

8 R

11 R

12 L

15 R

17 L

19 R

22 R

27 R

29 R

33 R

35 L

40 L

43 L

48 R

49 L

52 L

54 L

[出力例]

■参照サイト
AtCoder Regular Contest 041

2022年3月17日2022年3月17日

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

C++の練習を兼ねて, AtCoder Beginner Contest 214 の問題C (Distribution) ～問題D (Sum of Maximum Weights) を解いてみた.

■感想.
1. 問題C, Dは, 方針を絞り込めたので, AC版に到達できたと思う.
2. 個人的には, 問題Dで, 最小全域木(Kruskal’s Algorithm) の考え方で実装出来たので, 非常に良かったと思う.
※ 公式のライブラリを拝借させて頂いてます.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

■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--)
LL s[404040], t[404040], ans[404040];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%lld", &s[i]);
    rep(i, N) scanf("%lld", &t[i]);
    
    // 2. 更新.
    rep(i, N){
        ans[i] = ans[i + N] = t[i];
        s[i + N] = s[i];
    }
    rep(i, N * 2) if(ans[i + 1] > ans[i] + s[i]) ans[i + 1] = ans[i] + s[i];
    
    // 3. 出力.
    rep(i, N) printf("%lld\n", min(ans[i], ans[i + N]));
    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 s[404040], t[404040], ans[404040];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

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

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

// 2. 更新.

rep(i, N){

ans[i] = ans[i + N] = t[i];

s[i + N] = s[i];

}

rep(i, N * 2) if(ans[i + 1] > ans[i] + s[i]) ans[i + 1] = ans[i] + s[i];

// 3. 出力.

rep(i, N) printf("%lld\n", min(ans[i], ans[i + N]));

return 0;

}

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

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

[入力例]
4
100 100 100 100
1 1 1 1

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

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

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

[入力例]
8
84 87 78 16 94 36 87 93
50 22 63 28 91 60 64 27

[出力例]
50
22
63
28
44
60
64
27
※AtCoderテストケースより

[入力例]
10
11 10 7 5 9 5 10 11 2 5
18 20 1 80 31 40 34 29 32 69

[出力例]
18
20
1
8
13
22
27
29
32
34

[入力例]
20
2 11 2 9 7 12 7 12 8 1 2 10 9 8 2 10 3 1 4 9
139 446 336 1037 441 64 200 1119 505 582 148 612 759 572 691 208 956 1043 631 819

[出力例]
139
141
152
154
163
64
76
83
95
103
104
106
116
125
133
135
145
148
149
153

[入力例]

4 1 5

3 10 100

[出力例]

※AtCoderテストケースより

[入力例]

100 100 100 100

1 1 1 1

[出力例]

※AtCoderテストケースより

[入力例]

1 2 3 4

1 2 4 7

[出力例]

※AtCoderテストケースより

[入力例]

84 87 78 16 94 36 87 93

50 22 63 28 91 60 64 27

[出力例]

※AtCoderテストケースより

[入力例]

11 10 7 5 9 5 10 11 2 5

18 20 1 80 31 40 34 29 32 69

[出力例]

[入力例]

2 11 2 9 7 12 7 12 8 1 2 10 9 8 2 10 3 1 4 9

139 446 336 1037 441 64 200 1119 505 582 148 612 759 572 691 208 956 1043 631 819

[出力例]

139

141

152

154

163

103

104

106

116

125

133

135

145

148

149

153

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vi = vector<int>;
using T3 = tuple<int, int, 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 all(x) x.begin(), x.end()

// https://github.com/atcoder/live_library/blob/master/uf.cpp
// UnionFind
// coding: https://youtu.be/TdR816rqc3s?t=726
// comment: https://youtu.be/TdR816rqc3s?t=6822
// -> 一部改変.
struct UnionFind{
    vi d;
    UnionFind(int n = 0): d(n, -1) {}
    int find(int x){
        return (d[x] < 0) ? x : (d[x] = find(d[x]));
    }
    bool unite(int x, int y){
        x = find(x);
        y = find(y);
        if(x == y) return false;
        if(d[x] > d[y]) swap(x, y);
        d[x] += d[y];
        d[y] = x;
        return true;
    }
    bool same(int x, int y){
        return find(x) == find(y);
    }
    int size(int x){
        return -d[find(x)];
    }
};

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    vector<T3> t;
    rep(i, N - 1){
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        --u, --v;
        t.emplace_back(w, u, v);
    }
    
    // 2. sort.
    sort(all(t));
    
    // 3. 最小全域木(Kruskal's Algorithm) の 構築.
    // 競プロ典型 90 問 (049 - Flip Digits 2)
    // https://github.com/E869120/kyopro_educational_90/blob/main/sol/049.cpp
    LL ans = 0;
    UnionFind uf(N + 2);
    rep(i, t.size()){
        // 3-1. グラフ情報.
        int w = get<0>(t[i]); // 辺の重み.
        int u = get<1>(t[i]); // 頂点.
        int v = get<2>(t[i]); // 頂点.
        
        // 3-2. 集計(連結成分サイズを考慮).
        ans += (LL)uf.size(u) * (LL)uf.size(v) * (LL)w;
        
        // 3-3. 連結.
        uf.unite(u, v);
    }
    
    // 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 T3 = tuple<int, int, 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 all(x) x.begin(), x.end()

// https://github.com/atcoder/live_library/blob/master/uf.cpp

// UnionFind

// coding: https://youtu.be/TdR816rqc3s?t=726

// comment: https://youtu.be/TdR816rqc3s?t=6822

// -> 一部改変.

struct UnionFind{

vi d;

UnionFind(int n = 0): d(n, -1) {}

int find(int x){

return (d[x] < 0) ? x : (d[x] = find(d[x]));

}

bool unite(int x, int y){

x = find(x);

y = find(y);

if(x == y) return false;

if(d[x] > d[y]) swap(x, y);

d[x] += d[y];

d[y] = x;

return true;

}

bool same(int x, int y){

return find(x) == find(y);

}

int size(int x){

return -d[find(x)];

}

};

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

vector<T3> t;

rep(i, N - 1){

int u, v, w;

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

--u, --v;

t.emplace_back(w, u, v);

}

// 2. sort.

sort(all(t));

// 3. 最小全域木(Kruskal's Algorithm) の構築.

// 競プロ典型 90 問 (049 - Flip Digits 2)

// https://github.com/E869120/kyopro_educational_90/blob/main/sol/049.cpp

LL ans = 0;

UnionFind uf(N + 2);

rep(i, t.size()){

// 3-1. グラフ情報.

int w = get<0>(t[i]); // 辺の重み.

int u = get<1>(t[i]); // 頂点.

int v = get<2>(t[i]); // 頂点.

// 3-2. 集計(連結成分サイズを考慮).

ans += (LL)uf.size(u) * (LL)uf.size(v) * (LL)w;

// 3-3. 連結.

uf.unite(u, v);

}

// 4. 出力.

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

return 0;

}

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

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

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

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

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

[出力例]
121

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

[出力例]
614

[入力例]

1 2 10

2 3 20

[出力例]

※AtCoderテストケースより

[入力例]

1 2 1

2 3 2

4 2 5

3 5 14

[出力例]

※AtCoderテストケースより

[入力例]

1 2 3

1 3 7

2 4 6

7 2 2

5 3 5

6 3 1

[出力例]

121

[入力例]

1 2 6

2 4 5

5 2 3

9 5 9

10 5 7

1 3 3

3 8 10

3 7 12

3 6 2

7 11 8

7 12 11

[出力例]

614

■参照サイト
AtCoder Beginner Contest 214
Union-Find木
 競プロ典型 90 問の問題049

C++の練習を兼ねて, AtCoder Regular Contest 137 の 問題A (Coprime Pair) ～ 問題B (Count 1’s) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 027 の 問題C (最高のトッピングにしような) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 025 の 問題C (ウサギとカメ) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 024 の 問題C (だれじゃ) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 021 の 問題C (増築王高橋君) を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 029 の 問題C (高橋君と国家) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 035 の 問題C (アットコーダー王国の交通事情) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 041 の 問題C (ウサギ跳び) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 214 の 問題C (Distribution) ～ 問題D (Sum of Maximum Weights) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 137 の問題A (Coprime Pair) ～問題B (Count 1’s) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 027 の問題C (最高のトッピングにしような) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 025 の問題C (ウサギとカメ) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 024 の問題C (だれじゃ) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 021 の問題C (増築王高橋君) を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 029 の問題C (高橋君と国家) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 035 の問題C (アットコーダー王国の交通事情) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 041 の問題C (ウサギ跳び) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 214 の問題C (Distribution) ～問題D (Sum of Maximum Weights) を解いてみた.