C++ | 個人用メモ帳

2022年4月10日

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

C++の練習を兼ねて, AtCoder Regular Contest 138 の問題A (Larger Score) を解いてみた.

■感想.
1. 問題Aは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 解説にあるロジックで, 操作回数の最小値が計算できることが, 非常に印象深く感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/arc138/editorial/3746
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;
using PQ = priority_queue<int>;
using vi = vector<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 main(){
    
    // 1. 入力情報.
    int N, K;
    scanf("%d %d", &N, &K);
    vi a(N);
    vp op(N);
    rep(i, N){
        scanf("%d", &a[i]);
        op[i].a = a[i];
        op[i].b = -i;
    }
    
    // 2. sort.
    sort(all(op));
    
    // 3. 操作回数の最小値は？
    int ans = 2020202020;
    PQ pq;
    for(auto &p : op){
        int i = -p.b;
        if(i < K){
            pq.push(i);
            continue;
        }
        if(!pq.empty()){
            int j = pq.top();
            if(i >= K && a[j] < a[i]) ans = min(ans, i - j);
        }
    }
    
    // 4. 出力.
    printf("%d\n", (ans == 2020202020) ? -1 : ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc138/editorial/3746

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using P = pair<int, int>;

using PQ = priority_queue<int>;

using vi = vector<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 main(){

// 1. 入力情報.

int N, K;

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

vi a(N);

vp op(N);

rep(i, N){

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

op[i].a = a[i];

op[i].b = -i;

}

// 2. sort.

sort(all(op));

// 3. 操作回数の最小値は？

int ans = 2020202020;

PQ pq;

for(auto &p : op){

int i = -p.b;

if(i < K){

pq.push(i);

continue;

}

if(!pq.empty()){

int j = pq.top();

if(i >= K && a[j] < a[i]) ans = min(ans, i - j);

}

// 4. 出力.

printf("%d\n", (ans == 2020202020) ? -1 : ans);

return 0;

}

[入力例]
4 2
2 1 1 2

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

[入力例]
3 1
3 2 1

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

[入力例]
20 13
90699850 344821203 373822335 437633059 534203117 523743511 568996900 694866636 683864672 836230375 751240939 942020833 865334948 142779837 22252499 197049878 303376519 366683358 545670804 580980054

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

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

[出力例]
2

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

[出力例]
2

[入力例]
20 5
33 77 55 88 121 30 33 22 34 78 56 123 89 125 11 222 99 5 100 50

[出力例]
7

[入力例]
100 7
1111 3333 1112 3333 2222 3333 2223 100 282 208 1111 138 257 173 88 1111 345 234 118 1110 252 65 91 234 30 234 108 260 21 126 57 97 95 1110 200 234 234 72 1111 77 1111 66 99 222 1110 170 282 281 345 1111 292 226 174 209 1110 122 1110 219 179 345 167 345 1110 169 193 345 1111 170 234 1 1110 211 100 345 1110 211 1110 100 211 133 123 1110 222 108 78 1111 197 345 100 100 1000 1112 1113 2223 3334 2224 1110 1111 100 101

[出力例]
88

[入力例]

4 2

2 1 1 2

[出力例]

※AtCoderのテストケースより

[入力例]

3 1

3 2 1

[出力例]

-1

※AtCoderのテストケースより

[入力例]

20 13

90699850 344821203 373822335 437633059 534203117 523743511 568996900 694866636 683864672 836230375 751240939 942020833 865334948 142779837 22252499 197049878 303376519 366683358 545670804 580980054

[出力例]

※AtCoderのテストケースより

[入力例]

7 3

3 2 5 1 6 3 7

[出力例]

[入力例]

10 3

3 1 4 1 5 9 2 6 5 3

[出力例]

[入力例]

20 5

33 77 55 88 121 30 33 22 34 78 56 123 89 125 11 222 99 5 100 50

[出力例]

[入力例]

100 7

1111 3333 1112 3333 2222 3333 2223 100 282 208 1111 138 257 173 88 1111 345 234 118 1110 252 65 91 234 30 234 108 260 21 126 57 97 95 1110 200 234 234 72 1111 77 1111 66 99 222 1110 170 282 281 345 1111 292 226 174 209 1110 122 1110 219 179 345 167 345 1110 169 193 345 1111 170 234 1 1110 211 100 345 1110 211 1110 100 211 133 123 1110 222 108 78 1111 197 345 100 100 1000 1112 1113 2223 3334 2224 1110 1111 100 101

[出力例]

■参照サイト
大和証券プログラミングコンテスト2022 Spring(AtCoder Regular Contest 138)

2022年4月8日

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

C++の練習を兼ねて, AtCoder Beginner Contest 150 の問題D (Semi Common Multiple) を解いてみた.

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

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

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

// 解き直し.
// https://img.atcoder.jp/abc150/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--)
LL a[101010];

int main(){
    
    // 1. 入力情報.
    int N;
    LL M;
    scanf("%d %lld", &N, &M);
    rep(i, N) scanf("%lld", &a[i]);
    
    // 2. 2 で 割り切れる回数.
    set<int> st;
    rep(i, N){
        LL b = a[i];
        int x = 0;
        while(!(b & 1)){
            b >>= 1;
            ++x;
        }
        st.insert(x);
    }
    
    // 3. 例外.
    if(st.size() > 1){
        puts("0");
        return 0;
    }
    
    // 4. 最小公倍数.
    LL lcm = a[0] / 2;
    repx(i, 1, N){
        LL g = __gcd(lcm, a[i] / 2);
        lcm /= g;
        lcm *= (a[i] / 2);
    }
    
    // 5. 集計(85.txt で WA版となったので, ロジック修正).
    M += (lcm - M % lcm);
    LL ans = M / lcm / 2;
    
    // 6. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

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

LL a[101010];

int main(){

// 1. 入力情報.

int N;

LL M;

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

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

// 2. 2 で割り切れる回数.

set<int> st;

rep(i, N){

LL b = a[i];

int x = 0;

while(!(b & 1)){

b >>= 1;

++x;

}

st.insert(x);

}

// 3. 例外.

if(st.size() > 1){

puts("0");

return 0;

}

// 4. 最小公倍数.

LL lcm = a[0] / 2;

repx(i, 1, N){

LL g = __gcd(lcm, a[i] / 2);

lcm /= g;

lcm *= (a[i] / 2);

}

// 5. 集計(85.txt で WA版となったので, ロジック修正).

M += (lcm - M % lcm);

LL ans = M / lcm / 2;

// 6. 出力.

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

return 0;

}

[入力例]
2 50
6 10

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

[入力例]
3 100
14 22 40

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

[入力例]
5 1000000000
6 6 2 6 2

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

[入力例]
5 987654321
70 210 350 490 630

[出力例]
44792

[入力例]
10 1000000000
14 70 70 98 98 126 154 154 178 178

[出力例]
232

[入力例]
7 20200110
40 56 104 24 88 136 168

[出力例]
10

[入力例]
12 20220408
24 24 40 56 40 24 24 104 56 136 56 40

[出力例]
109

[入力例]

2 50

6 10

[出力例]

※AtCoderテストケースより

[入力例]

3 100

14 22 40

[出力例]

※AtCoderテストケースより

[入力例]

5 1000000000

6 6 2 6 2

[出力例]

166666667

※AtCoderテストケースより

[入力例]

5 987654321

70 210 350 490 630

[出力例]

44792

[入力例]

10 1000000000

14 70 70 98 98 126 154 154 178 178

[出力例]

232

[入力例]

7 20200110

40 56 104 24 88 136 168

[出力例]

[入力例]

12 20220408

24 24 40 56 40 24 24 104 56 136 56 40

[出力例]

109

■参照サイト
AtCoder Beginner Contest 150

2022年4月7日

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

C++の練習を兼ねて, AtCoder Beginner Contest 165 の問題F (LIS on Tree) を解いてみた.

■感想.
1. 問題Fは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 深さ優先探索の訓練を積めたので, 非常に良かったと思う.
3. LIS(Longest increase subsequence) を学習できたので, 非常に良かったと思う.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

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

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%d", &a[i]);
    vvi G(N);
    rep(i, N - 1){
        int u, v;
        scanf("%d %d", &u, &v);
        --u;
        --v;
        G[u].pb(v);
        G[v].pb(u);
    }
    
    // 2. dfs.
    // https://ja.wikipedia.org/wiki/深さ優先探索
    vi dp(N), ans(N);
    auto dfs = [&](auto&& self, vvi &G, int cur, int bef, int* m){
        // 終了条件.
        if(m[cur]) return;
        
        // 訪問済みフラグ設定.
        m[cur] = 1;
        
        // 隣接頂点.
        for(auto &nex : G[cur]){
            // Skip.
            if(nex == bef) continue;
            
            // dp更新.
            int at = lower_bound(all(dp), a[nex]) - dp.begin();
            int pd = dp[at];
            dp[at] = a[nex];
            
            // 狭義単調増加な数列の長さの最大値は？
            // -> 解説上 の LIS(Longest increase subsequence) の ロジック を 考慮すると, 
            //    初期化で, INF を設定するので, (INF - 1) の インデックス を 採用すれば, 良さそうに見える.
            ans[nex] = lower_bound(all(dp), INF - 1) - dp.begin();
            
            // 次へ.
            self(self, G, nex, cur, m);
            
            // dp戻し.
            dp[at] = pd;
        }
    };
    int memo[N];
    ans[0] = 1;
    rep(i, N) memo[i] = 0, dp[i] = INF;
    dp[0] = a[0];
    dfs(dfs, G, 0, -1, memo);
    
    // 3. 出力.
    rep(i, N) printf("%d\n", ans[i]);
    return 0;
    
}

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

using vvi = vector<vi>;

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

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

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

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

#define pb push_back

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

const int INF = 2020202020;

int a[202020];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

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

vvi G(N);

rep(i, N - 1){

int u, v;

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

--u;

--v;

G[u].pb(v);

G[v].pb(u);

}

// 2. dfs.

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

vi dp(N), ans(N);

auto dfs = [&](auto&& self, vvi &G, int cur, int bef, int* m){

// 終了条件.

if(m[cur]) return;

// 訪問済みフラグ設定.

m[cur] = 1;

// 隣接頂点.

for(auto &nex : G[cur]){

// Skip.

if(nex == bef) continue;

// dp更新.

int at = lower_bound(all(dp), a[nex]) - dp.begin();

int pd = dp[at];

dp[at] = a[nex];

// 狭義単調増加な数列の長さの最大値は？

// -> 解説上の LIS(Longest increase subsequence) のロジックを考慮すると,

// 初期化で, INF を設定するので, (INF - 1) のインデックスを採用すれば, 良さそうに見える.

ans[nex] = lower_bound(all(dp), INF - 1) - dp.begin();

// 次へ.

self(self, G, nex, cur, m);

// dp戻し.

dp[at] = pd;

}

};

int memo[N];

ans[0] = 1;

rep(i, N) memo[i] = 0, dp[i] = INF;

dp[0] = a[0];

dfs(dfs, G, 0, -1, memo);

// 3. 出力.

rep(i, N) printf("%d\n", ans[i]);

return 0;

}

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

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

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

[出力例]
1
2
2
2
3

[入力例]
12
2 3 5 6 11 12 15 17 18 22 24 27
1 2
2 5
2 4
6 4
7 1
7 8
7 9
9 10
4 3
3 11
3 12

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

[入力例]
20
1 3 4 7 8 11 12 17 21 25 28 31 33 49 55 77 100 101 123 222
1 6
1 7
1 9
18 9
19 9
20 9
3 7
3 10
3 11
16 11
17 11
8 7
8 5
5 2
5 4
2 12
2 13
13 14
13 15

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

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

[入力例]

1 2 5 3 4 6 7 3 2 4

1 2

2 3

3 4

4 5

3 6

6 7

1 8

8 9

9 10

[出力例]

※AtCoderテストケースより

[入力例]

2 5 7 9 10

1 2

4 1

5 4

3 4

[出力例]

[入力例]

2 3 5 6 11 12 15 17 18 22 24 27

1 2

2 5

2 4

6 4

7 1

7 8

7 9

9 10

4 3

3 11

3 12

[出力例]

[入力例]

1 3 4 7 8 11 12 17 21 25 28 31 33 49 55 77 100 101 123 222

1 6

1 7

1 9

18 9

19 9

20 9

3 7

3 10

3 11

16 11

17 11

8 7

8 5

5 2

5 4

2 12

2 13

13 14

13 15

[出力例]

■参照サイト
AtCoder Beginner Contest 165

2022年4月5日

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

C++の練習を兼ねて, AtCoder Beginner Contest 153 の問題E (Crested Ibis vs Monster) を解いてみた.

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

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

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

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

int main(){
    
    // 1. 入力情報.
    int H, N, aMax = 0;
    scanf("%d %d", &H, &N);
    rep(i, N){
        scanf("%d %d", &a[i], &b[i]);
        aMax = max(aMax, a[i]);
    }
    
    // 2. 初期化.
    rep(i, 20202) dp[i] = INF;
    dp[0] = 0;
    
    // 3. dp更新.
    rep(i, H + aMax + 1){
        // N種類の魔法を試す.
        // -> 前回のモンスターの体力 i から, 今回のモンスターの体力 i + a[j] を 減らすには？
        rep(j, N){
            int na = i + a[j];
            if(na <= H + aMax) dp[na] = min(dp[na], dp[i] + b[j]);
        }
    }
    
    // 4. 最小値は？
    int ans = INF;
    repx(i, H, H + aMax + 1) ans = min(ans, dp[i]);
    
    // 5. 出力.
    printf("%d\n", ans);
    return 0;
    
}

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

const int INF = 2020202020;

int a[1010], b[1010], dp[20202];

int main(){

// 1. 入力情報.

int H, N, aMax = 0;

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

rep(i, N){

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

aMax = max(aMax, a[i]);

}

// 2. 初期化.

rep(i, 20202) dp[i] = INF;

dp[0] = 0;

// 3. dp更新.

rep(i, H + aMax + 1){

// N種類の魔法を試す.

// -> 前回のモンスターの体力 i から, 今回のモンスターの体力 i + a[j] を減らすには？

rep(j, N){

int na = i + a[j];

if(na <= H + aMax) dp[na] = min(dp[na], dp[i] + b[j]);

}

// 4. 最小値は？

int ans = INF;

repx(i, H, H + aMax + 1) ans = min(ans, dp[i]);

// 5. 出力.

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

return 0;

}

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

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

[入力例]
100 6
1 1
2 3
3 9
4 27
5 81
6 243

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

[入力例]
9999 10
540 7550
691 9680
700 9790
510 7150
415 5818
551 7712
587 8227
619 8671
588 8228
176 2461

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

[入力例]
2020 12
64 35
55 121
51 31
45 64
60 103
66 69
77 110
25 39
8 19
75 110
80 100
3 12

[出力例]
1112

[入力例]
2022 20
11 12
19 22
2 5
5 7
16 17
17 18
6 8
19 20
22 23
7 8
13 18
16 18
7 8
9 10
10 11
24 25
6 7
18 19
9 10
5 6

[出力例]
2107

[入力例]

9 3

8 3

4 2

2 1

[出力例]

※AtCoderテストケースより

[入力例]

100 6

1 1

2 3

3 9

4 27

5 81

6 243

[出力例]

100

※AtCoderテストケースより

[入力例]

9999 10

540 7550

691 9680

700 9790

510 7150

415 5818

551 7712

587 8227

619 8671

588 8228

176 2461

[出力例]

139815

※AtCoderテストケースより

[入力例]

2020 12

64 35

55 121

51 31

45 64

60 103

66 69

77 110

25 39

8 19

75 110

80 100

3 12

[出力例]

1112

[入力例]

2022 20

11 12

19 22

2 5

5 7

16 17

17 18

6 8

19 20

22 23

7 8

13 18

16 18

7 8

9 10

10 11

24 25

6 7

18 19

9 10

5 6

[出力例]

2107

■参照サイト
AtCoder Beginner Contest 153

2022年4月4日

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

C++の練習を兼ねて, AtCoder Beginner Contest 135 の問題D (Digits Parade) を解いてみた.

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

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

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

// 解き直し.
// https://img.atcoder.jp/abc135/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 MOD = 1e9 + 7;
LL dp[101010][13]; // 先頭 i 文字まで見て, 13 で割った余りが, j となるもの.

int main(){
    
    // 1. 入力情報.
    char s[101010];
    scanf("%s", s);
    int N = strlen(s);
    
    // 2. dp更新.
    // -> 空文字を, 1通りと数えておく.
    dp[0][0] = 1;
    rep(i, N){
        // i文字目が, '?'.
        if(s[i] == '?'){
            // 前回, 13 で割った余りが, j だった.
            rep(j, 13){
                // '0' ～ '9' まで試す.
                rep(k, 10){
                    // 桁上がりするので, 今回の余りは, 10 * j に 変わるので注意.
                    int r = (10 * j + k) % 13;
                    dp[i + 1][r] += dp[i][j];
                    dp[i + 1][r] %= MOD;
                }
            }
        }
        
        // i文字目が, '?' 以外.
        if(s[i] != '?'){
            // 前回, 13 で割った余りが, j だった.
            rep(j, 13){
                // 桁上がりするので, 今回の余りは, 10 * j に 変わるので注意.
                int r = (10 * j + (s[i] - '0')) % 13;
                dp[i + 1][r] += dp[i][j];
                dp[i + 1][r] %= MOD;
            }
        }
    }
    
    // 3. 出力.
    printf("%lld\n", dp[N][5]);
    return 0;
    
}

// 解き直し.

// https://img.atcoder.jp/abc135/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 MOD = 1e9 + 7;

LL dp[101010][13]; // 先頭 i 文字まで見て, 13 で割った余りが, j となるもの.

int main(){

// 1. 入力情報.

char s[101010];

scanf("%s", s);

int N = strlen(s);

// 2. dp更新.

// -> 空文字を, 1通りと数えておく.

dp[0][0] = 1;

rep(i, N){

// i文字目が, '?'.

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

// 前回, 13 で割った余りが, j だった.

rep(j, 13){

// '0' ～ '9' まで試す.

rep(k, 10){

// 桁上がりするので, 今回の余りは, 10 * j に変わるので注意.

int r = (10 * j + k) % 13;

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

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

}

// i文字目が, '?' 以外.

if(s[i] != '?'){

// 前回, 13 で割った余りが, j だった.

rep(j, 13){

// 桁上がりするので, 今回の余りは, 10 * j に変わるので注意.

int r = (10 * j + (s[i] - '0')) % 13;

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

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

}

// 3. 出力.

printf("%lld\n", dp[N][5]);

return 0;

}

[入力例]
??2??5

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

[入力例]
?44

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

[入力例]
7?4

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

[入力例]
?6?42???8??2??06243????9??3???7258??5??7???????774????4?1??17???9?5?70???76???

[出力例]
153716888

[入力例]
1??

[出力例]
7

[入力例]
8???

[出力例]
77

[入力例]
8?81??5?

[出力例]
770

[入力例]
82?25?2503?760185?8??617???15835658?2??55??69762??

[出力例]
763846179

[入力例]
770727717?82808??9252191127251971298727583?17?0269?92731199011800680299961836881090875568506192396795068779998??5658266906993298105838?6215212993530867??8915??7211?996?689272?268952?963316055136811370?7353119560?177725?5880?772?860?9295165577?26008?660701267631371153559915505880883629?139?55553309952?231626768000805?5523169206293?5922?2587?27086?37536268560938053207122?920180623765?29?79391789039?2821?1??727?769?38?807?393?92989?7?371592?53?36271150?9516516013963?297376665763?5176?71673305667722

[出力例]
869231461

[入力例]

??2??5

[出力例]

768

※AtCoderテストケースより

[入力例]

?44

[出力例]

※AtCoderテストケースより

[入力例]

7?4

[出力例]

※AtCoderテストケースより

[入力例]

?6?42???8??2??06243????9??3???7258??5??7???????774????4?1??17???9?5?70???76???

[出力例]

153716888

[入力例]

1??

[出力例]

[入力例]

8???

[出力例]

[入力例]

8?81??5?

[出力例]

770

[入力例]

82?25?2503?760185?8??617???15835658?2??55??69762??

[出力例]

763846179

[入力例]

770727717?82808??9252191127251971298727583?17?0269?92731199011800680299961836881090875568506192396795068779998??5658266906993298105838?6215212993530867??8915??7211?996?689272?268952?963316055136811370?7353119560?177725?5880?772?860?9295165577?26008?660701267631371153559915505880883629?139?55553309952?231626768000805?5523169206293?5922?2587?27086?37536268560938053207122?920180623765?29?79391789039?2821?1??727?769?38?807?393?92989?7?371592?53?36271150?9516516013963?297376665763?5176?71673305667722

[出力例]

869231461

■参照サイト
AtCoder Beginner Contest 135

2022年4月2日

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

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

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

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

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

// 解き直し.
// https://img.atcoder.jp/abc149/editorial.pdf
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vi = vector<int>;
using vvi = vector<vi>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
const LL MOD = 1e9 + 7;
LL mPow2[202020], c[202020];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    vvi G(N);
    rep(i, N - 1){
        int a, b;
        scanf("%d %d", &a, &b);
        --a;
        --b;
        G[a].pb(b);
        G[b].pb(a);
    }
    
    // 2. 事前計算.
    mPow2[0] = 1;
    repx(i, 1, 202020) mPow2[i] = (mPow2[i - 1] * (LL)(5e8 + 4)) % MOD;
    rep(i, 202020) c[i] = (MOD + 1 - mPow2[i]) % MOD;
    // rep(i, N) printf("c[%d]=%lld\n", i, c[i]);
    
    // 3. dfs(部分木サイズ).
    // https://ja.wikipedia.org/wiki/深さ優先探索
    auto dfs = [](auto&& self, vvi &G, int cur, int bef, int* m, int* s){
        // 部分木サイズ(往路).
        ++s[cur];
        
        // 終了条件.
        if(m[cur]) return;
        m[cur] = 1;
        
        // 隣接頂点.
        for(auto &nex : G[cur]) if(nex != bef) self(self, G, nex, cur, m, s);
        
        // 部分木サイズ(復路).
        if(bef != -1) s[bef] += s[cur];
    };
    int subTree[N], memo[N];
    rep(i, N) subTree[i] = memo[i] = 0;
    dfs(dfs, G, 0, -1, memo, subTree);
    // rep(i, N) printf("subTree[%d]=%d\n", i, subTree[i]);
    
    // 4. S の 辺数(期待値).
    // https://ja.wikipedia.org/wiki/深さ優先探索
    LL ans = 0;
    function<void(vvi&, int, int, int*)> f = [&](vvi &G, int cur, int bef, int* m){
        // 終了条件.
        if(m[cur]) return;
        m[cur] = 1;
        
        // 隣接頂点.
        for(auto &nex : G[cur]){
            // 親頂点か否か.
            if(nex == bef) continue;
            
            // S に含まれる辺数の期待値を加算.
            ans += c[subTree[nex]] * c[N - subTree[nex]] % MOD;
            ans %= MOD;
            
            // 次へ.
            f(G, nex, cur, m);
        }
    };
    rep(i, N) memo[i] = 0;
    f(G, 0, -1, memo);
    
    // 5. S の 頂点数(期待値).
    // 5-1. 頂点数は, 辺数よりも, 1 多い.
    ++ans;
    ans %= MOD;
    
    // 5-2. 空グラフ除外.
    ans += (MOD - mPow2[N]);
    ans %= MOD;
    
    // 6. 黒く塗られた頂点数(期待値, 減算).
    ans += MOD - N * (LL)(5e8 + 4) % MOD;
    ans %= MOD;
    
    // 7. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

100

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vi = vector<int>;

using vvi = vector<vi>;

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

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

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

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

#define pb push_back

const LL MOD = 1e9 + 7;

LL mPow2[202020], c[202020];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

vvi G(N);

rep(i, N - 1){

int a, b;

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

--a;

--b;

G[a].pb(b);

G[b].pb(a);

}

// 2. 事前計算.

mPow2[0] = 1;

repx(i, 1, 202020) mPow2[i] = (mPow2[i - 1] * (LL)(5e8 + 4)) % MOD;

rep(i, 202020) c[i] = (MOD + 1 - mPow2[i]) % MOD;

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

// 3. dfs(部分木サイズ).

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

auto dfs = [](auto&& self, vvi &G, int cur, int bef, int* m, int* s){

// 部分木サイズ(往路).

++s[cur];

// 終了条件.

if(m[cur]) return;

m[cur] = 1;

// 隣接頂点.

for(auto &nex : G[cur]) if(nex != bef) self(self, G, nex, cur, m, s);

// 部分木サイズ(復路).

if(bef != -1) s[bef] += s[cur];

};

int subTree[N], memo[N];

rep(i, N) subTree[i] = memo[i] = 0;

dfs(dfs, G, 0, -1, memo, subTree);

// rep(i, N) printf("subTree[%d]=%d\n", i, subTree[i]);

// 4. S の辺数(期待値).

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

LL ans = 0;

function<void(vvi&, int, int, int*)> f = [&](vvi &G, int cur, int bef, int* m){

// 終了条件.

if(m[cur]) return;

m[cur] = 1;

// 隣接頂点.

for(auto &nex : G[cur]){

// 親頂点か否か.

if(nex == bef) continue;

// S に含まれる辺数の期待値を加算.

ans += c[subTree[nex]] * c[N - subTree[nex]] % MOD;

ans %= MOD;

// 次へ.

f(G, nex, cur, m);

}

};

rep(i, N) memo[i] = 0;

f(G, 0, -1, memo);

// 5. S の頂点数(期待値).

// 5-1. 頂点数は, 辺数よりも, 1 多い.

++ans;

ans %= MOD;

// 5-2. 空グラフ除外.

ans += (MOD - mPow2[N]);

ans %= MOD;

// 6. 黒く塗られた頂点数(期待値, 減算).

ans += MOD - N * (LL)(5e8 + 4) % MOD;

ans %= MOD;

// 7. 出力.

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

return 0;

}

[入力例]
3
1 2
2 3

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

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

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

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

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

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

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

[入力例]
2
1 2

[出力例]
0

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

[出力例]
781250007

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

[出力例]
697387702

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

[出力例]
783004770

100

101

102

103

104

105

106

[入力例]

1 2

2 3

[出力例]

125000001

※AtCoderのテストケースより

[入力例]

1 2

2 3

3 4

[出力例]

375000003

※AtCoderのテストケースより

[入力例]

1 2

1 3

1 4

[出力例]

250000002

※AtCoderのテストケースより

[入力例]

4 7

3 1

2 6

5 2

7 1

2 7

[出力例]

570312505

※AtCoderのテストケースより

[入力例]

1 2

[出力例]

[入力例]

2 1

3 1

1 5

2 6

2 7

4 3

5 8

5 9

5 10

[出力例]

781250007

[入力例]

1 2

1 3

1 4

2 5

2 6

2 7

3 8

3 9

3 10

4 11

4 12

4 13

[出力例]

697387702

[入力例]

1 2

1 3

4 2

5 2

6 2

7 3

8 3

9 3

4 10

4 11

5 12

5 13

12 14

12 15

7 16

7 17

9 18

9 19

18 20

[出力例]

783004770

■参照サイト
AtCoder Beginner Contest 149

2022年4月1日

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

C++の練習を兼ねて, AtCoder Beginner Contest 152 の問題D (Handstand 2) ～問題E (Flatten) を解いてみた.

■感想.
1. 問題D, Eは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 両問ともに, 解説のロジックで, 計算できることが, 非常に印象深く残ったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/abc152/editorial.pdf
#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 c[10][10];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    
    // 2. c[i][j] を 計算(解説通り).
    rep(n, N){
        string sn = to_string(n + 1);
        int i = sn.front() - '0';
        int j = sn.back() - '0';
        ++c[i][j];
    }
    
    // 3. 集計.
    // -> 解説の数式を適用.
    LL ans = 0;
    rep(i, 10) rep(j, 10) ans += c[i][j] * c[j][i];
    
    // 4. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

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

#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 c[10][10];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

// 2. c[i][j] を計算(解説通り).

rep(n, N){

string sn = to_string(n + 1);

int i = sn.front() - '0';

int j = sn.back() - '0';

++c[i][j];

}

// 3. 集計.

// -> 解説の数式を適用.

LL ans = 0;

rep(i, 10) rep(j, 10) ans += c[i][j] * c[j][i];

// 4. 出力.

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

return 0;

}

[入力例]
25

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

[入力例]
1

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

[入力例]
100

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

[入力例]
2020

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

[入力例]
200000

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

[入力例]
333

[出力例]
1152

[入力例]
8849

[出力例]
783233

[入力例]
21230

[出力例]
4507137

[入力例]
20200119

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

[入力例]
123456789

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

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

100

[出力例]

108

※AtCoderテストケースより

[入力例]

2020

[出力例]

40812

※AtCoderテストケースより

[入力例]

200000

[出力例]

400000008

※AtCoderテストケースより

[入力例]

333

[出力例]

1152

[入力例]

8849

[出力例]

783233

[入力例]

21230

[出力例]

4507137

[入力例]

20200119

[出力例]

4080448480152

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

[入力例]

123456789

[出力例]

152415789971049

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

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

// 解き直し.
// https://img.atcoder.jp/abc152/editorial.pdf
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using MP = map<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 a first
#define b second
const LL MOD = 1e9 + 7;
int b[1010101];
LL a[10101];

// Efficient program to print all prime factors of a given number
// https://www.geeksforgeeks.org/print-all-prime-factors-of-a-given-number/
// 与えられた正整数についての素因数分解を計算.
// @param X: 素因数分解を行う整数.
// @return ret: 素因数分解 の 結果 を 返却.
MP div(int X){
    // X を 2で割り切れなくなるまで割っていく.
    map<int, int> ret;
    while(!(X % 2)) ++ret[2], X >>= 1;
    
    // X を 3以上の奇数で, 割り切れなくなるまで順次割っていく.
    repex(i, 3, sqrt(X) + 1, 2){
        while(!(X % i)){
            ++ret[i];
            X /= i;
        }
    }
    
    // X が 2 より 大きな素数であれば, 追加.
    if(X > 2) ++ret[X];
    
    // 出力.
    return ret;
}

// 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) scanf("%lld", &a[i]);
    
    // 2. 素数を取得.
    repx(i, 2, 1010101){
        if(b[i]) continue;
        repex(j, i * 2, 1010101, i) b[j]++;
    }
    
    // 3. 素数を集計.
    MP lcm;
    repx(i, 2, 1010101) if(!b[i]) lcm[i] = 0;
    
    // 4. 素因数分解を行う.
    rep(i, N){
        MP m = div(a[i]);
        for(auto &p : m) lcm[p.a] = max(lcm[p.a], p.b);
    }
    
    // 5. L を 計算(解説通り).
    LL L = 1;
    for(auto &p : lcm){
        rep(i, p.b){
            L *= (LL)p.a;
            L %= MOD;
        }
    }
    
    // 6. 集計.
    // -> 解説の数式を適用.
    LL ans = 0;
    rep(i, N){
        ans += L * mPow((LL)a[i], MOD - 2);
        ans %= MOD;
    }
    
    // 7. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

100

// 解き直し.

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

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using MP = map<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 a first

#define b second

const LL MOD = 1e9 + 7;

int b[1010101];

LL a[10101];

// Efficient program to print all prime factors of a given number

// https://www.geeksforgeeks.org/print-all-prime-factors-of-a-given-number/

// 与えられた正整数についての素因数分解を計算.

// @param X: 素因数分解を行う整数.

// @return ret: 素因数分解の結果を返却.

MP div(int X){

// X を 2で割り切れなくなるまで割っていく.

map<int, int> ret;

while(!(X % 2)) ++ret[2], X >>= 1;

// X を 3以上の奇数で, 割り切れなくなるまで順次割っていく.

repex(i, 3, sqrt(X) + 1, 2){

while(!(X % i)){

++ret[i];

X /= i;

}

// X が 2 より大きな素数であれば, 追加.

if(X > 2) ++ret[X];

// 出力.

return ret;

}

// 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) scanf("%lld", &a[i]);

// 2. 素数を取得.

repx(i, 2, 1010101){

if(b[i]) continue;

repex(j, i * 2, 1010101, i) b[j]++;

}

// 3. 素数を集計.

MP lcm;

repx(i, 2, 1010101) if(!b[i]) lcm[i] = 0;

// 4. 素因数分解を行う.

rep(i, N){

MP m = div(a[i]);

for(auto &p : m) lcm[p.a] = max(lcm[p.a], p.b);

}

// 5. L を計算(解説通り).

LL L = 1;

for(auto &p : lcm){

rep(i, p.b){

L *= (LL)p.a;

L %= MOD;

}

// 6. 集計.

// -> 解説の数式を適用.

LL ans = 0;

rep(i, N){

ans += L * mPow((LL)a[i], MOD - 2);

ans %= MOD;

}

// 7. 出力.

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

return 0;

}

[入力例]
3
2 3 4

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

[入力例]
5
12 12 12 12 12

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

[入力例]
3
1000000 999999 999998

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

[入力例]
3
1 2 3

[出力例]
11

[入力例]
5
2 6 12 24 108

[出力例]
173

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

[出力例]
611

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

[出力例]
7381

[入力例]
11
78 108 34 111 19 73 52 85 9 36 64

[出力例]
606380251

[入力例]

2 3 4

[出力例]

※AtCoderテストケースより

[入力例]

12 12 12 12 12

[出力例]

※AtCoderテストケースより

[入力例]

1000000 999999 999998

[出力例]

996989508

※AtCoderテストケースより

[入力例]

1 2 3

[出力例]

[入力例]

2 6 12 24 108

[出力例]

173

[入力例]

3 1 4 1 5 9 2

[出力例]

611

[入力例]

1 2 3 4 5 6 7 8 9 10

[出力例]

7381

[入力例]

78 108 34 111 19 73 52 85 9 36 64

[出力例]

606380251

■参照サイト
AtCoder Beginner Contest 152

2022年4月1日

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

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

■感想.
1. 問題Eは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 実装に苦労したものの(特に, 二分探索後に, 幸福度を計算する箇所), 二分探索の復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/abc149/editorial.pdf
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
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 all(x) x.begin(), x.end()
int hCum[202020];
LL aCum[202020];

int main(){
    
    // 1. 入力情報.
    int N;
    LL M;
    scanf("%d %lld", &N, &M);
    vi a(N);
    map<int, int> ma;
    ma[0] = 0;
    rep(i, N){
        scanf("%d", &a[i]);
        hCum[a[i]]++;
        ma[a[i]]++;
    }
    
    // 2. sort.
    sort(all(a));
    reverse(all(a));
    
    // 3. 累積和.
    repr(i, 202020 - 2, 0) hCum[i] += hCum[i + 1];
    rep(i, N) aCum[i + 1] = aCum[i] + (LL)a[i];
    
    // 4. 評価関数.
    auto f = [&](int m) -> bool {
        // 4-1. 定数 m 以上になる握手の方法の通り数.
        // -> 左手で握手する人を決めて, 右手で握手できる人数を加算.
        LL c = 0;
        rep(i, N){
            int r = max(0, m - a[i]);
            c += (LL)hCum[r];
        }
        
        // 4-2. 判定結果.
        return (c >= M);
    };
    
    // 5. 二分探索で確認してみる.
    int l = -1, h = 2e5 + 1, m;
    while(l + 1 < h){
        int m = (h + l) >> 1;
        if(f(m)) l = m;
        else     h = m;
    }
    
    // 6. 集計.
    // 6-1. 最小でない幸福度.
    LL ans = 0, mCur = M;
    rep(i, N){
        // 残りの握手回数をチェック.
        int r = max(0, h - a[i]);
        if(mCur < (LL)hCum[r]) break;
        
        // 左手.
        ans += (LL)a[i] * (LL)hCum[r];
        
        // 右手.
        ans += aCum[hCum[r]];
        
        // 残りの握手回数を減算.
        mCur -= (LL)hCum[r];
    }
    
    // 6-2. 最小の幸福度.
    rep(i, N){
        // 残りの握手回数をチェック.
        int r = l - a[i];
        if(r < 0) continue;
        
        // 終了条件.
        if(mCur < (LL)ma[r]){
            // 左手.
            ans += (LL)a[i] * mCur;
            
            // 右手.
            ans += (LL)r * mCur;
            
            // 終了.
            break;
        }
        
        // 左手.
        ans += (LL)a[i] * (LL)ma[r];
        
        // 右手.
        ans += (LL)r * (LL)ma[r];
        
        // 残りの握手回数を減算.
        mCur -= (LL)ma[r];
    }
    
    // 7. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

110

111

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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 all(x) x.begin(), x.end()

int hCum[202020];

LL aCum[202020];

int main(){

// 1. 入力情報.

int N;

LL M;

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

vi a(N);

map<int, int> ma;

ma[0] = 0;

rep(i, N){

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

hCum[a[i]]++;

ma[a[i]]++;

}

// 2. sort.

sort(all(a));

reverse(all(a));

// 3. 累積和.

repr(i, 202020 - 2, 0) hCum[i] += hCum[i + 1];

rep(i, N) aCum[i + 1] = aCum[i] + (LL)a[i];

// 4. 評価関数.

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

// 4-1. 定数 m 以上になる握手の方法の通り数.

// -> 左手で握手する人を決めて, 右手で握手できる人数を加算.

LL c = 0;

rep(i, N){

int r = max(0, m - a[i]);

c += (LL)hCum[r];

}

// 4-2. 判定結果.

return (c >= M);

};

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

int l = -1, h = 2e5 + 1, m;

while(l + 1 < h){

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

if(f(m)) l = m;

else h = m;

}

// 6. 集計.

// 6-1. 最小でない幸福度.

LL ans = 0, mCur = M;

rep(i, N){

// 残りの握手回数をチェック.

int r = max(0, h - a[i]);

if(mCur < (LL)hCum[r]) break;

// 左手.

ans += (LL)a[i] * (LL)hCum[r];

// 右手.

ans += aCum[hCum[r]];

// 残りの握手回数を減算.

mCur -= (LL)hCum[r];

}

// 6-2. 最小の幸福度.

rep(i, N){

// 残りの握手回数をチェック.

int r = l - a[i];

if(r < 0) continue;

// 終了条件.

if(mCur < (LL)ma[r]){

// 左手.

ans += (LL)a[i] * mCur;

// 右手.

ans += (LL)r * mCur;

// 終了.

break;

}

// 左手.

ans += (LL)a[i] * (LL)ma[r];

// 右手.

ans += (LL)r * (LL)ma[r];

// 残りの握手回数を減算.

mCur -= (LL)ma[r];

}

// 7. 出力.

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

return 0;

}

[入力例]
5 3
10 14 19 34 33

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

[入力例]
9 14
1 3 5 110 24 21 34 5 3

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

[入力例]
9 73
67597 52981 5828 66249 75177 64141 40773 79105 16076

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

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

[出力例]
38

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

[出力例]
270

[入力例]
50 2022
33 60 77 9 77 34 98 109 88 77 9 104 103 46 67 6 25 119 55 77 120 65 71 67 77 8 19 56 90 73 57 77 116 76 33 111 63 92 18 50 12 28 77 72 39 69 77 116 112 96

[出力例]
300009

[入力例]
5000 20220401
13 18 8 6 25 9 22 5 11 7 8 10 3 10 10 22 6 8 7 23 19 15 21 27 23 27 12 9 6 6 13 16 16 17 20 12 11 16 6 17 6 6 1 25 7 13 1 17 21 11 16 12 22 20 3 11 7 22 23 18 16 21 1 2 7 9 17 15 19 21 17 2 22 12 22 8 20 17 10 8 17 25 18 11 18 21 2 7 10 25 16 17 21 23 9 7 17 17 21 10 23 19 18 11 18 20 6 15 10 5 12 2 17 19 10 12 27 3 19 15 8 8 15 23 13 17 12 23 3 3 15 2 25 7 27 12 25 10 18 22 2 17 12 7 11 13 19 27 17 5 9 3 17 7 27 12 9 25 12 10 9 22 7 23 17 10 13 6 21 19 13 9 2 9 15 23 7 16 22 20 13 17 18 25 17 17 3 25 1 22 5 7 5 8 18 11 5 3 8 17 1 6 8 9 18 3 21 23 22 9 12 1 1 19 27 21 13 8 20 2 25 1 15 25 20 25 22 27 8 17 7 27 27 7 17 22 17 21 10 17 17 18 21 12 21 22 9 17 6 27 8 25 12 10 9 12 12 15 11 6 27 13 21 10 2 17 7 20 9 8 20 7 11 19 3 25 11 11 16 13 3 19 11 19 6 8 25 11 6 13 17 8 1 22 10 17 12 7 1 5 3 21 20 13 7 7 5 20 1 27 16 23 8 23 6 10 15 2 20 6 25 17 23 21 22 2 7 11 9 13 10 3 9 23 8 22 18 8 2 13 10 20 10 10 11 18 9 8 8 27 17 17 15 7 22 10 23 5 3 17 15 22 6 23 15 17 3 6 13 2 25 20 13 22 23 7 9 5 9 13 13 21 23 10 27 17 25 23 11 23 27 25 23 19 27 25 20 7 9 15 22 3 13 7 25 18 17 15 22 5 8 7 25 7 10 17 18 7 16 2 15 13 17 22 12 19 23 21 27 17 7 17 13 16 27 23 1 11 22 19 7 23 19 25 18 7 9 13 8 13 25 20 22 11 3 18 18 23 15 9 21 3 27 1 5 21 25 17 19 8 1 11 3 15 22 18 27 10 27 13 9 8 13 13 18 9 16 20 23 16 18 3 9 15 7 12 19 22 13 10 6 3 2 13 22 3 22 15 15 27 16 10 2 17 1 7 2 6 5 1 7 7 10 17 3 10 6 8 6 13 7 20 2 7 11 25 7 16 11 16 20 23 19 18 27 25 5 13 7 11 17 1 11 5 1 12 6 3 7 17 17 16 8 10 19 15 20 12 17 8 2 10 7 9 8 7 3 13 8 20 10 1 17 17 3 3 23 12 8 17 8 8 20 10 10 20 23 11 6 13 18 5 25 22 7 5 11 6 19 9 17 13 2 13 12 7 5 23 27 3 25 6 7 15 17 7 16 23 19 8 11 12 27 2 15 7 12 18 8 12 16 8 11 7 1 15 10 9 8 10 1 13 21 1 10 5 22 3 17 20 10 17 25 25 19 18 12 2 8 17 12 6 15 11 22 7 9 1 8 23 21 7 10 7 10 11 10 1 25 2 5 7 19 13 16 17 9 17 16 10 19 25 22 12 7 17 16 17 12 2 22 8 6 20 9 21 11 16 1 7 17 22 6 8 23 19 5 2 17 6 21 9 25 19 1 1 25 11 25 10 18 23 9 7 23 11 7 22 8 27 10 16 12 6 13 20 11 3 8 7 10 2 9 20 11 23 2 13 25 17 23 17 7 11 11 3 23 1 20 16 16 16 13 7 7 13 16 2 6 10 17 11 20 16 19 12 8 17 3 6 13 27 10 17 20 17 10 10 12 23 10 22 8 7 11 15 6 7 12 15 22 1 8 18 13 21 12 25 6 20 20 27 2 16 27 5 27 7 10 18 22 13 3 23 27 22 6 17 13 13 21 22 17 22 7 20 17 3 8 1 21 16 12 5 18 17 5 18 22 19 19 25 13 13 7 9 15 25 25 10 7 17 16 9 22 16 25 8 8 11 21 5 2 1 27 22 13 8 2 13 9 19 5 11 2 17 3 17 19 10 11 1 16 8 15 17 11 7 22 23 8 7 8 23 20 19 1 27 12 13 20 7 6 11 18 1 16 8 15 17 3 17 16 5 16 25 9 16 11 21 17 10 17 15 7 1 13 12 27 7 23 10 5 16 6 18 2 22 1 19 15 3 17 17 13 21 18 16 6 2 13 8 10 25 17 9 6 12 2 7 19 16 6 12 11 3 15 9 9 11 3 7 25 16 13 7 3 20 20 1 25 21 7 27 22 12 9 6 16 15 22 3 7 1 18 8 12 10 10 8 3 16 20 16 9 27 2 18 22 16 25 8 21 27 5 18 21 5 17 25 16 22 17 15 17 12 27 20 11 10 11 9 19 3 25 16 3 19 9 12 22 6 15 20 9 20 13 10 7 17 15 19 2 7 8 25 16 3 12 18 20 1 17 11 9 27 22 2 11 9 27 7 23 23 16 22 25 3 11 9 10 11 7 27 12 16 20 12 10 8 9 15 16 11 17 17 13 25 3 21 23 12 16 13 5 21 1 7 23 21 7 21 22 17 20 19 16 20 2 12 17 5 8 17 9 16 19 10 17 11 8 15 23 13 25 13 2 8 10 3 9 2 7 22 18 22 18 1 8 9 27 6 1 5 1 8 7 18 8 8 9 21 27 9 9 21 17 7 23 8 3 13 25 9 23 27 6 6 6 15 7 3 13 17 19 11 20 15 7 10 10 3 15 25 23 15 17 8 7 22 25 17 7 9 16 19 27 19 15 7 6 8 7 23 15 18 9 25 27 21 6 18 19 23 9 18 25 11 25 18 17 15 10 15 17 21 27 22 20 5 2 16 12 22 17 2 17 10 12 16 5 3 2 20 9 22 6 27 2 12 21 16 6 12 25 13 7 7 5 10 12 17 7 17 23 13 17 25 19 6 17 19 11 17 23 3 12 12 1 18 27 8 7 13 27 1 12 5 16 13 19 11 17 20 21 7 23 23 3 10 8 1 22 12 22 7 18 6 7 10 5 12 17 18 17 11 20 15 22 21 22 23 20 12 2 15 7 23 11 11 22 17 12 1 6 12 27 8 18 7 12 16 21 20 1 25 7 22 8 27 20 25 20 17 15 12 17 16 8 18 11 15 17 11 12 18 8 15 17 9 7 10 20 17 8 23 5 12 3 12 17 23 6 8 15 16 12 12 12 25 15 21 10 10 22 17 2 17 27 19 7 22 11 10 19 27 7 5 18 3 21 1 8 3 25 15 5 7 6 19 21 12 23 11 17 8 15 22 21 8 11 19 20 7 11 1 11 16 9 6 21 18 12 9 2 1 18 23 7 12 11 17 3 17 19 8 8 6 23 17 6 15 27 18 20 25 23 10 13 23 17 21 6 23 8 23 6 7 3 25 21 11 1 7 7 23 25 8 9 16 5 16 3 5 2 27 10 25 19 5 13 25 1 6 17 13 1 17 10 1 1 18 20 27 1 10 23 3 25 10 2 9 17 18 17 25 9 9 9 9 6 17 16 27 1 22 6 9 2 27 10 16 2 5 10 7 17 21 10 8 16 18 22 23 22 13 18 27 27 17 23 3 25 27 3 3 23 17 6 1 18 7 23 7 9 27 8 13 9 25 15 3 2 9 19 11 17 8 19 18 17 12 8 25 12 6 11 27 7 25 1 3 17 5 6 12 16 9 2 7 7 2 6 17 1 19 25 7 2 21 6 19 6 1 7 1 2 7 2 10 23 19 7 21 17 10 1 3 23 12 25 15 6 19 21 6 1 11 7 5 22 9 25 13 25 7 8 25 1 11 27 23 8 25 13 17 17 17 16 18 6 13 25 18 23 5 7 20 17 7 11 11 19 7 25 18 19 25 12 16 11 8 9 8 7 17 23 3 20 19 3 13 2 9 10 23 23 12 5 5 2 5 15 21 21 23 17 7 11 16 17 7 20 23 17 11 10 19 8 27 25 15 5 25 15 15 12 18 10 7 2 20 11 17 6 15 5 16 1 21 8 9 20 25 17 12 9 21 7 13 8 17 27 27 7 17 27 21 10 7 20 13 7 22 17 7 15 1 12 17 25 19 17 7 20 23 1 27 1 12 13 25 11 18 22 7 5 25 16 3 19 5 15 10 19 7 2 3 7 8 10 15 21 23 23 8 8 7 17 27 8 17 3 22 12 19 9 20 1 7 6 27 18 6 20 6 13 7 16 21 9 1 20 2 9 8 7 11 27 27 7 10 11 27 25 16 3 1 22 1 2 12 2 17 27 19 16 3 25 22 17 2 27 18 13 7 15 27 2 13 1 3 15 19 17 7 10 18 25 6 11 8 11 11 15 13 16 7 25 25 7 11 22 6 3 11 1 23 7 3 11 17 20 10 3 22 27 7 2 12 6 7 17 19 16 22 17 3 5 19 10 9 19 13 20 11 19 9 21 15 10 20 9 27 17 11 22 27 10 11 5 6 12 8 27 16 7 19 17 22 2 5 2 9 10 18 6 9 3 18 12 12 12 1 17 17 10 9 5 9 5 1 16 2 17 3 19 25 16 27 23 15 15 9 7 11 20 5 6 6 20 25 19 19 20 12 20 8 9 7 27 11 13 8 9 27 6 7 21 1 17 17 18 9 2 17 21 11 20 2 10 7 8 17 21 18 13 13 2 21 17 3 1 17 13 7 16 19 21 22 10 17 7 13 13 27 6 9 5 12 17 3 1 16 6 18 13 23 6 16 21 7 9 17 20 9 13 23 7 1 10 8 27 17 16 13 11 21 20 25 17 9 11 21 3 22 11 7 6 13 12 7 23 7 21 20 25 11 22 20 1 23 2 23 25 17 20 20 2 16 27 15 27 27 21 11 13 8 10 20 13 17 5 22 6 17 17 18 27 8 13 22 3 3 13 23 1 17 17 16 12 19 3 27 3 7 19 7 12 3 9 9 7 23 23 1 23 10 16 20 18 13 25 13 1 17 18 9 10 6 2 23 7 13 16 7 22 11 3 10 5 7 22 18 6 16 1 2 17 2 23 12 8 5 10 11 7 15 18 5 17 15 23 12 17 17 22 10 16 17 15 17 3 23 17 27 17 25 15 12 18 11 5 5 11 7 6 25 19 5 9 19 20 19 19 21 15 21 6 19 27 18 13 22 20 18 10 12 9 7 20 17 5 17 17 20 5 22 13 16 3 17 13 20 11 21 19 21 19 6 1 21 10 18 9 6 18 27 12 12 17 1 7 16 23 12 22 17 21 23 25 9 8 2 8 19 20 5 17 11 20 11 12 25 7 21 20 19 15 27 7 10 9 13 1 5 21 17 19 18 27 16 7 10 7 22 7 25 22 25 1 17 13 2 3 13 23 16 17 27 3 25 13 18 7 21 21 15 3 9 18 3 12 27 5 10 13 25 27 10 25 1 10 23 1 17 22 10 7 23 12 3 1 12 17 10 17 23 17 17 27 3 7 25 27 1 18 8 12 2 7 5 27 21 15 8 20 15 16 16 10 7 16 16 15 27 11 20 27 3 5 18 22 1 12 9 13 16 6 21 19 7 17 17 1 21 16 27 1 23 21 12 5 15 13 1 23 15 13 7 21 12 19 10 17 7 7 3 1 11 7 21 1 1 7 11 16 22 1 8 7 3 7 21 7 19 12 11 23 23 17 3 20 7 2 17 1 2 16 8 10 17 3 10 12 20 10 23 22 23 19 2 17 7 12 3 2 5 12 21 19 20 27 20 9 3 2 7 13 13 3 11 1 27 6 12 19 8 20 22 1 2 8 6 23 9 11 2 13 13 9 20 3 15 19 5 11 7 17 23 23 20 11 27 13 20 11 21 16 16 11 5 3 23 13 18 12 17 11 13 11 2 2 27 21 11 25 7 25 7 18 1 1 20 9 21 23 3 17 6 17 1 6 15 7 27 2 10 19 20 5 19 8 20 27 11 12 7 5 25 21 16 10 16 1 15 12 7 25 9 27 15 7 21 15 11 13 19 10 13 17 11 25 17 5 18 23 10 25 25 20 7 3 5 22 21 15 12 7 7 21 23 27 5 15 17 10 6 6 21 10 19 20 15 3 6 8 10 12 19 19 15 3 21 22 15 8 5 8 1 9 20 5 1 7 9 20 19 23 18 23 17 25 22 17 27 27 17 8 22 8 22 12 17 21 11 10 8 2 21 13 12 19 8 2 15 1 27 7 17 1 10 12 7 17 5 23 12 9 18 13 7 3 9 7 15 9 27 6 17 18 15 11 19 18 15 8 5 25 20 17 1 9 1 12 25 16 16 17 21 15 23 1 5 15 12 22 19 11 3 5 7 8 3 15 22 18 16 9 12 11 17 5 12 9 6 18 7 9 2 6 1 17 5 1 25 27 10 20 12 19 23 22 13 21 15 11 3 10 16 17 19 1 17 3 3 13 2 8 3 16 1 17 17 25 17 27 25 1 17 22 19 21 7 17 12 6 21 3 7 5 21 3 1 6 12 20 6 6 1 7 20 20 12 19 6 17 19 23 6 17 5 16 9 1 12 7 18 15 7 1 10 20 15 7 6 5 15 5 13 3 7 10 13 23 17 7 7 7 19 20 6 7 1 8 5 9 20 21 17 3 27 17 6 3 5 6 21 17 27 8 12 10 10 17 11 12 20 7 17 19 12 16 8 6 13 16 12 25 1 1 17 13 16 7 12 1 7 16 15 6 8 23 25 22 13 25 7 19 18 22 23 16 5 6 20 10 1 25 8 19 6 23 5 20 7 17 25 6 22 18 12 18 25 15 3 27 9 8 17 3 27 7 8 10 6 15 18 7 3 10 19 3 13 20 17 10 15 19 6 3 11 25 15 2 15 18 18 22 23 22 7 7 13 9 11 11 12 22 1 5 10 6 25 16 17 17 1 2 22 23 10 3 21 23 18 1 7 3 27 7 13 21 17 25 10 16 25 16 27 6 25 6 17 22 7 7 8 18 16 22 3 8 16 19 27 2 22 27 12 21 13 23 23 23 13 21 11 18 3 25 22 19 23 25 9 11 10 11 5 19 8 15 13 16 3 2 15 5 15 19 20 17 9 6 11 17 16 27 7 15 23 16 20 25 8 7 23 3 22 15 21 3 1 23 15 10 27 27 15 27 3 25 5 10 13 22 25 15 7 22 15 21 8 1 17 7 11 12 27 22 20 10 7 2 7 2 12 25 12 8 20 7 16 5 23 5 6 17 25 15 20 16 15 7 25 12 2 16 21 7 16 21 25 17 18 8 23 17 9 8 10 27 20 11 9 7 12 25 15 1 12 21 25 5 5 17 19 19 7 19 11 12 19 21 23 23 21 21 8 6 20 20 3 22 3 18 13 23 19 13 17 17 13 3 2 13 18 9 22 22 6 19 18 6 17 22 17 8 18 16 18 19 10 17 23 19 27 20 9 5 21 12 18 17 6 1 13 7 17 2 3 25 10 27 20 25 2 1 1 16 5 21 25 5 23 2 23 20 10 22 21 7 13 10 16 9 1 23 13 11 7 21 13 20 25 13 13 6 17 7 17 27 7 8 17 18 15 17 10 13 23 27 17 25 17 5 21 7 7 7 17 23 9 1 23 18 18 20 3 21 8 17 2 6 23 27 7 1 18 18 23 8 16 23 15 10 17 1 6 1 6 18 23 2 17 12 9 2 18 10 11 16 17 19 25 22 27 13 15 12 13 2 6 22 27 21 16 20 17 27 11 17 8 15 3 8 5 7 9 21 11 17 23 21 23 1 13 20 11 17 2 5 6 16 22 13 2 17 22 18 23 7 20 1 3 1 7 25 18 6 6 11 21 5 17 3 17 5 27 18 2 15 7 25 7 16 7 25 13 15 10 5 17 11 2 9 6 11 2 8 27 15 3 3 17 12 8 19 5 6 27 13 8 12 2 6 25 23 17 22 18 6 16 8 6 23 12 15 18 21 1 5 18 18 1 3 6 15 27 10 27 12 25 13 11 6 11 19 17 22 23 22 3 17 8 10 9 7 17 17 9 6 20 18 15 7 2 7 18 19 8 7 8 16 2 7 15 25 13 13 22 23 10 20 13 11 16 11 20 7 21 1 12 17 25 6 20 8 10 10 21 15 9 7 2 7 16 13 17 22 20 20 11 7 19 21 9 20 6 15 21 6 6 7 17 12 7 23 7 2 27 16 7 12 21 17 23 20 9 8 3 20 12 25 27 10 23 23 21 3 5 22 9 8 16 10 7 1 25 21 13 19 1 21 6 23 7 10 11 16 7 5 17 1 27 12 17 16 21 8 27 9 23 1 1 16 10 10 20 9 3 20 17 12 23 11 16 5 3 8 8 3 7 1 27 12 1 16 1 5 7 7 17 11 8 8 17 11 7 15 7 1 21 15 1 12 13 16 10 15 17 27 23 19 20 7 7 17 20 18 12 27 6 21 15 1 20 17 17 3 9 3 27 20 12 7 23 16 7 5 23 7 6 23 18 3 22 22 11 18 20 27 2 18 11 25 12 3 13 17 11 3 5 5 12 3 8 22 2 23 9 23 16 17 12 17 2 18 7 15 25 19 13 7 22 23 16 2 21 13 1 25 9 19 9 6 7 27 5 1 27 10 25 17 8 17 5 21 23 13 18 19 10 3 15 27 9 5 23 3 15 20 1 17 3 7 9 19 27 18 15 7 15 1 7 7 11 5 23 16 20 23 5 7 1 8 13 10 21 22 5 5 17 21 15 5 7 16 13 18 17 17 6 17 18 21 22 23 15 19 13 22 9 12 7 23 1 23 27 21 25 21 20 19 17 3 16 19 3 6 15 7 9 19 5 11 2 5 7 3 7 25 5 11 7 18 7 22 10 20 1 1 22 5 15 22 16 10 21 3 3 6 6 9 16 15 19 10 20 25 21 7 22 27 9 9 5 17 23 12 5 18 11 6 15 19 17 19 10 2 15 1 27 5 5 9 3 11 16 12 17 17 23 11 18 9 13 23 12 16 6 17 23 6 2 6 17 6 7 3 20 21 7 11 3 8 19 13 2 8 2 27 6 16 2 17 25 15 6 12 17 8 11 19 2 11 7 9 9 18 2 6 17 8 5 25 17 22 22 15 16 16 17 13 27 11 6 18 7 10 12 3 12 22 23 27 12 22 13 3 7 16 27 11 7 17 2 12 11 18 7 9 19 9 7 22 15 8 17 5 16 17 17 23 22 13 1 11 7 21 19 18 17 5 23 6 7 5 1 17 6 19 23 1 7 7 1 17 7 27 11 3 11 7 1 3 2 27 22 16 3 20 17 2 20 9 10 7 22 16 7 3 20 17 2 16 8 17 11 16 8 10 7 22 10 7 2 7 23 17 12 7 11 7 8 2 8 10 19 18 7 21 8 15 9 8 7 23 20 17 1 22 10 10 1 11 9 19 12 22 6 13 21 11 19 27 3 20 23 25 12 7 16 20 1 11 6 18 7 11 5 13 16 9 10 25 20 17 11 3 22 7 25 17 6 25 11 12 9 2 15 17 7 15 13 17 22 17 23 17 21 17 5 16 17 16 5 17 15 8 12 10 22 17 17 13 17 7 6 3 16 20 16 16 7 27 3 8 17 5 17 15 25 3 22 21 17 12 7 16 22 17 7 25 1 27 8 3 11 16 7 7 8 1 21 7 2 3 7 13 1 17 17 1 6 12 5 6 23 6 7 10 20 9 18 9 25 15 1 15 22 20 9 7 22 20 9 1 25 9 9 5 27 5 13 21 17 19 25 17 3 21 13 17 9 9 7 27 17 3 22 13 16 19 6 11 12 15 6 3 16 8 1 12 12 1 23 22 7 27 27 8 20 11 25 7 21 1 19 23 27 18 17 3 17 3 17 7 2 13 21 13 1 3 11 20 6 2 16 22 3 9 16 20 25 15 1 23 5 18 6 19 1 11 17 6 19 23 15 9 17 13 25 7 21 11 7 8 10 27 1 15 12 20 9 13 5 19 7 10 18 10 15 2 17 1 18 13 21 12 8 1 20 19 22 23 8 22 11 15 18 11 23 11 13 7 27 10 12 7 6 5 3 25 18 13 5 7 27 13 17 23 10 17 18 27 3 8 18 3 23 3 16 25 22 6 3 21 3 13 22 6 11 8 15 25 3 13 15 17 2 7 2 19 10 3 12 9 11 7 16 2 20 12 19 8 19 12 6 25 23 7 12 7 25 10 23 9 21 25 27 12 16 16 8 10 11 9 17 22 17 25 9 12 23 5 23 20 21 19 15 5 1 17 11 7 25 23 15 6 9 3 8 13 22 17 9 9 10 17 12 8 10 17 13 6 19 22 3 27 13 2 6 2 17 10 11 8 17 13 23 8 6 13 2 6 22 21 22 19 17 3 9 18 25 22 5 16 6 5 16 3 23 13 15 13 19 9 6 17 23 21 21 10 18 17 1 8 6 21 23 11 13 2 9 9 5 17 17 13 20 19 7 3 8 1 9 13 21 1 16 17 18 19 9 13 19 7 17 8 23 20 10 9 5 23 13 21 3 18 3 2 13 13 7 11 27 7 10 6 11 2 1 3 22 20 17 5 22 11 21 23 7 20 15 9 1 1 10 9 13 19 13 25 17 8 12 2 2 9 2 1 7 22 6 9 22 9 18 5 18 7 6 25 15 17 25 23 18 6 1 3 3 19 25 10 23 6 16 9 27 12 22 18 16 21 11 6 16 2 10 5 16 17 19 20 17 15 10 19 21 3 17 22 22 21 21 6 22 10 23 5 18 2 22 8 17 23 23 13 3 7 11 11 12 22 21 5 10 13 10 1 7 3 17 10 22 6 9 9 19 25 25 22 2 16 25 22 7 21 8 9 27 5 11 13 2 5 19 20 19 10 8 22 6 15 7 16 12 13 2 18 21 21 10 25 19 3 21 18 22 15 8 13 17 7 7 7 27 5 2 2 16 7 3 17 2 21 27 5 17 21 21 1 2 12 17 15 25 16 3 13 23 1 1 6 23 1 17 17 20 16 13 25 27 15 1 10 21 20 7 7 17 7 27 7 17 3 11 1 18 18 18 15 7 1 19 2 10 25 27 7 8 11 22 13 2 9 23 13 11 16 17 25 17 27 5 18 27 8 2 7 16 3 23 2 11 8 6 12 6 27 3 10 9 9 1 12 9 10 21 8 19 2 12 7 6 18 3 16 17 9 19 7 17 16 27 20 16 19 19 1 19 1 10 21 25 17 8 23 9 5 13 11 8 11 7 2 25 18 17 7 23 1 7 3 16 7 3

[出力例]
610372398

[入力例]

5 3

10 14 19 34 33

[出力例]

202

※AtCoderテストケースより

[入力例]

9 14

1 3 5 110 24 21 34 5 3

[出力例]

1837

※AtCoderテストケースより

[入力例]

9 73

67597 52981 5828 66249 75177 64141 40773 79105 16076

[出力例]

8128170

※AtCoderテストケースより

[入力例]

6 8

1 1 3 2 2 1

[出力例]

[入力例]

18 12

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

[出力例]

270

[入力例]

50 2022

33 60 77 9 77 34 98 109 88 77 9 104 103 46 67 6 25 119 55 77 120 65 71 67 77 8 19 56 90 73 57 77 116 76 33 111 63 92 18 50 12 28 77 72 39 69 77 116 112 96

[出力例]

300009

[入力例]

5000 20220401

13 18 8 6 25 9 22 5 11 7 8 10 3 10 10 22 6 8 7 23 19 15 21 27 23 27 12 9 6 6 13 16 16 17 20 12 11 16 6 17 6 6 1 25 7 13 1 17 21 11 16 12 22 20 3 11 7 22 23 18 16 21 1 2 7 9 17 15 19 21 17 2 22 12 22 8 20 17 10 8 17 25 18 11 18 21 2 7 10 25 16 17 21 23 9 7 17 17 21 10 23 19 18 11 18 20 6 15 10 5 12 2 17 19 10 12 27 3 19 15 8 8 15 23 13 17 12 23 3 3 15 2 25 7 27 12 25 10 18 22 2 17 12 7 11 13 19 27 17 5 9 3 17 7 27 12 9 25 12 10 9 22 7 23 17 10 13 6 21 19 13 9 2 9 15 23 7 16 22 20 13 17 18 25 17 17 3 25 1 22 5 7 5 8 18 11 5 3 8 17 1 6 8 9 18 3 21 23 22 9 12 1 1 19 27 21 13 8 20 2 25 1 15 25 20 25 22 27 8 17 7 27 27 7 17 22 17 21 10 17 17 18 21 12 21 22 9 17 6 27 8 25 12 10 9 12 12 15 11 6 27 13 21 10 2 17 7 20 9 8 20 7 11 19 3 25 11 11 16 13 3 19 11 19 6 8 25 11 6 13 17 8 1 22 10 17 12 7 1 5 3 21 20 13 7 7 5 20 1 27 16 23 8 23 6 10 15 2 20 6 25 17 23 21 22 2 7 11 9 13 10 3 9 23 8 22 18 8 2 13 10 20 10 10 11 18 9 8 8 27 17 17 15 7 22 10 23 5 3 17 15 22 6 23 15 17 3 6 13 2 25 20 13 22 23 7 9 5 9 13 13 21 23 10 27 17 25 23 11 23 27 25 23 19 27 25 20 7 9 15 22 3 13 7 25 18 17 15 22 5 8 7 25 7 10 17 18 7 16 2 15 13 17 22 12 19 23 21 27 17 7 17 13 16 27 23 1 11 22 19 7 23 19 25 18 7 9 13 8 13 25 20 22 11 3 18 18 23 15 9 21 3 27 1 5 21 25 17 19 8 1 11 3 15 22 18 27 10 27 13 9 8 13 13 18 9 16 20 23 16 18 3 9 15 7 12 19 22 13 10 6 3 2 13 22 3 22 15 15 27 16 10 2 17 1 7 2 6 5 1 7 7 10 17 3 10 6 8 6 13 7 20 2 7 11 25 7 16 11 16 20 23 19 18 27 25 5 13 7 11 17 1 11 5 1 12 6 3 7 17 17 16 8 10 19 15 20 12 17 8 2 10 7 9 8 7 3 13 8 20 10 1 17 17 3 3 23 12 8 17 8 8 20 10 10 20 23 11 6 13 18 5 25 22 7 5 11 6 19 9 17 13 2 13 12 7 5 23 27 3 25 6 7 15 17 7 16 23 19 8 11 12 27 2 15 7 12 18 8 12 16 8 11 7 1 15 10 9 8 10 1 13 21 1 10 5 22 3 17 20 10 17 25 25 19 18 12 2 8 17 12 6 15 11 22 7 9 1 8 23 21 7 10 7 10 11 10 1 25 2 5 7 19 13 16 17 9 17 16 10 19 25 22 12 7 17 16 17 12 2 22 8 6 20 9 21 11 16 1 7 17 22 6 8 23 19 5 2 17 6 21 9 25 19 1 1 25 11 25 10 18 23 9 7 23 11 7 22 8 27 10 16 12 6 13 20 11 3 8 7 10 2 9 20 11 23 2 13 25 17 23 17 7 11 11 3 23 1 20 16 16 16 13 7 7 13 16 2 6 10 17 11 20 16 19 12 8 17 3 6 13 27 10 17 20 17 10 10 12 23 10 22 8 7 11 15 6 7 12 15 22 1 8 18 13 21 12 25 6 20 20 27 2 16 27 5 27 7 10 18 22 13 3 23 27 22 6 17 13 13 21 22 17 22 7 20 17 3 8 1 21 16 12 5 18 17 5 18 22 19 19 25 13 13 7 9 15 25 25 10 7 17 16 9 22 16 25 8 8 11 21 5 2 1 27 22 13 8 2 13 9 19 5 11 2 17 3 17 19 10 11 1 16 8 15 17 11 7 22 23 8 7 8 23 20 19 1 27 12 13 20 7 6 11 18 1 16 8 15 17 3 17 16 5 16 25 9 16 11 21 17 10 17 15 7 1 13 12 27 7 23 10 5 16 6 18 2 22 1 19 15 3 17 17 13 21 18 16 6 2 13 8 10 25 17 9 6 12 2 7 19 16 6 12 11 3 15 9 9 11 3 7 25 16 13 7 3 20 20 1 25 21 7 27 22 12 9 6 16 15 22 3 7 1 18 8 12 10 10 8 3 16 20 16 9 27 2 18 22 16 25 8 21 27 5 18 21 5 17 25 16 22 17 15 17 12 27 20 11 10 11 9 19 3 25 16 3 19 9 12 22 6 15 20 9 20 13 10 7 17 15 19 2 7 8 25 16 3 12 18 20 1 17 11 9 27 22 2 11 9 27 7 23 23 16 22 25 3 11 9 10 11 7 27 12 16 20 12 10 8 9 15 16 11 17 17 13 25 3 21 23 12 16 13 5 21 1 7 23 21 7 21 22 17 20 19 16 20 2 12 17 5 8 17 9 16 19 10 17 11 8 15 23 13 25 13 2 8 10 3 9 2 7 22 18 22 18 1 8 9 27 6 1 5 1 8 7 18 8 8 9 21 27 9 9 21 17 7 23 8 3 13 25 9 23 27 6 6 6 15 7 3 13 17 19 11 20 15 7 10 10 3 15 25 23 15 17 8 7 22 25 17 7 9 16 19 27 19 15 7 6 8 7 23 15 18 9 25 27 21 6 18 19 23 9 18 25 11 25 18 17 15 10 15 17 21 27 22 20 5 2 16 12 22 17 2 17 10 12 16 5 3 2 20 9 22 6 27 2 12 21 16 6 12 25 13 7 7 5 10 12 17 7 17 23 13 17 25 19 6 17 19 11 17 23 3 12 12 1 18 27 8 7 13 27 1 12 5 16 13 19 11 17 20 21 7 23 23 3 10 8 1 22 12 22 7 18 6 7 10 5 12 17 18 17 11 20 15 22 21 22 23 20 12 2 15 7 23 11 11 22 17 12 1 6 12 27 8 18 7 12 16 21 20 1 25 7 22 8 27 20 25 20 17 15 12 17 16 8 18 11 15 17 11 12 18 8 15 17 9 7 10 20 17 8 23 5 12 3 12 17 23 6 8 15 16 12 12 12 25 15 21 10 10 22 17 2 17 27 19 7 22 11 10 19 27 7 5 18 3 21 1 8 3 25 15 5 7 6 19 21 12 23 11 17 8 15 22 21 8 11 19 20 7 11 1 11 16 9 6 21 18 12 9 2 1 18 23 7 12 11 17 3 17 19 8 8 6 23 17 6 15 27 18 20 25 23 10 13 23 17 21 6 23 8 23 6 7 3 25 21 11 1 7 7 23 25 8 9 16 5 16 3 5 2 27 10 25 19 5 13 25 1 6 17 13 1 17 10 1 1 18 20 27 1 10 23 3 25 10 2 9 17 18 17 25 9 9 9 9 6 17 16 27 1 22 6 9 2 27 10 16 2 5 10 7 17 21 10 8 16 18 22 23 22 13 18 27 27 17 23 3 25 27 3 3 23 17 6 1 18 7 23 7 9 27 8 13 9 25 15 3 2 9 19 11 17 8 19 18 17 12 8 25 12 6 11 27 7 25 1 3 17 5 6 12 16 9 2 7 7 2 6 17 1 19 25 7 2 21 6 19 6 1 7 1 2 7 2 10 23 19 7 21 17 10 1 3 23 12 25 15 6 19 21 6 1 11 7 5 22 9 25 13 25 7 8 25 1 11 27 23 8 25 13 17 17 17 16 18 6 13 25 18 23 5 7 20 17 7 11 11 19 7 25 18 19 25 12 16 11 8 9 8 7 17 23 3 20 19 3 13 2 9 10 23 23 12 5 5 2 5 15 21 21 23 17 7 11 16 17 7 20 23 17 11 10 19 8 27 25 15 5 25 15 15 12 18 10 7 2 20 11 17 6 15 5 16 1 21 8 9 20 25 17 12 9 21 7 13 8 17 27 27 7 17 27 21 10 7 20 13 7 22 17 7 15 1 12 17 25 19 17 7 20 23 1 27 1 12 13 25 11 18 22 7 5 25 16 3 19 5 15 10 19 7 2 3 7 8 10 15 21 23 23 8 8 7 17 27 8 17 3 22 12 19 9 20 1 7 6 27 18 6 20 6 13 7 16 21 9 1 20 2 9 8 7 11 27 27 7 10 11 27 25 16 3 1 22 1 2 12 2 17 27 19 16 3 25 22 17 2 27 18 13 7 15 27 2 13 1 3 15 19 17 7 10 18 25 6 11 8 11 11 15 13 16 7 25 25 7 11 22 6 3 11 1 23 7 3 11 17 20 10 3 22 27 7 2 12 6 7 17 19 16 22 17 3 5 19 10 9 19 13 20 11 19 9 21 15 10 20 9 27 17 11 22 27 10 11 5 6 12 8 27 16 7 19 17 22 2 5 2 9 10 18 6 9 3 18 12 12 12 1 17 17 10 9 5 9 5 1 16 2 17 3 19 25 16 27 23 15 15 9 7 11 20 5 6 6 20 25 19 19 20 12 20 8 9 7 27 11 13 8 9 27 6 7 21 1 17 17 18 9 2 17 21 11 20 2 10 7 8 17 21 18 13 13 2 21 17 3 1 17 13 7 16 19 21 22 10 17 7 13 13 27 6 9 5 12 17 3 1 16 6 18 13 23 6 16 21 7 9 17 20 9 13 23 7 1 10 8 27 17 16 13 11 21 20 25 17 9 11 21 3 22 11 7 6 13 12 7 23 7 21 20 25 11 22 20 1 23 2 23 25 17 20 20 2 16 27 15 27 27 21 11 13 8 10 20 13 17 5 22 6 17 17 18 27 8 13 22 3 3 13 23 1 17 17 16 12 19 3 27 3 7 19 7 12 3 9 9 7 23 23 1 23 10 16 20 18 13 25 13 1 17 18 9 10 6 2 23 7 13 16 7 22 11 3 10 5 7 22 18 6 16 1 2 17 2 23 12 8 5 10 11 7 15 18 5 17 15 23 12 17 17 22 10 16 17 15 17 3 23 17 27 17 25 15 12 18 11 5 5 11 7 6 25 19 5 9 19 20 19 19 21 15 21 6 19 27 18 13 22 20 18 10 12 9 7 20 17 5 17 17 20 5 22 13 16 3 17 13 20 11 21 19 21 19 6 1 21 10 18 9 6 18 27 12 12 17 1 7 16 23 12 22 17 21 23 25 9 8 2 8 19 20 5 17 11 20 11 12 25 7 21 20 19 15 27 7 10 9 13 1 5 21 17 19 18 27 16 7 10 7 22 7 25 22 25 1 17 13 2 3 13 23 16 17 27 3 25 13 18 7 21 21 15 3 9 18 3 12 27 5 10 13 25 27 10 25 1 10 23 1 17 22 10 7 23 12 3 1 12 17 10 17 23 17 17 27 3 7 25 27 1 18 8 12 2 7 5 27 21 15 8 20 15 16 16 10 7 16 16 15 27 11 20 27 3 5 18 22 1 12 9 13 16 6 21 19 7 17 17 1 21 16 27 1 23 21 12 5 15 13 1 23 15 13 7 21 12 19 10 17 7 7 3 1 11 7 21 1 1 7 11 16 22 1 8 7 3 7 21 7 19 12 11 23 23 17 3 20 7 2 17 1 2 16 8 10 17 3 10 12 20 10 23 22 23 19 2 17 7 12 3 2 5 12 21 19 20 27 20 9 3 2 7 13 13 3 11 1 27 6 12 19 8 20 22 1 2 8 6 23 9 11 2 13 13 9 20 3 15 19 5 11 7 17 23 23 20 11 27 13 20 11 21 16 16 11 5 3 23 13 18 12 17 11 13 11 2 2 27 21 11 25 7 25 7 18 1 1 20 9 21 23 3 17 6 17 1 6 15 7 27 2 10 19 20 5 19 8 20 27 11 12 7 5 25 21 16 10 16 1 15 12 7 25 9 27 15 7 21 15 11 13 19 10 13 17 11 25 17 5 18 23 10 25 25 20 7 3 5 22 21 15 12 7 7 21 23 27 5 15 17 10 6 6 21 10 19 20 15 3 6 8 10 12 19 19 15 3 21 22 15 8 5 8 1 9 20 5 1 7 9 20 19 23 18 23 17 25 22 17 27 27 17 8 22 8 22 12 17 21 11 10 8 2 21 13 12 19 8 2 15 1 27 7 17 1 10 12 7 17 5 23 12 9 18 13 7 3 9 7 15 9 27 6 17 18 15 11 19 18 15 8 5 25 20 17 1 9 1 12 25 16 16 17 21 15 23 1 5 15 12 22 19 11 3 5 7 8 3 15 22 18 16 9 12 11 17 5 12 9 6 18 7 9 2 6 1 17 5 1 25 27 10 20 12 19 23 22 13 21 15 11 3 10 16 17 19 1 17 3 3 13 2 8 3 16 1 17 17 25 17 27 25 1 17 22 19 21 7 17 12 6 21 3 7 5 21 3 1 6 12 20 6 6 1 7 20 20 12 19 6 17 19 23 6 17 5 16 9 1 12 7 18 15 7 1 10 20 15 7 6 5 15 5 13 3 7 10 13 23 17 7 7 7 19 20 6 7 1 8 5 9 20 21 17 3 27 17 6 3 5 6 21 17 27 8 12 10 10 17 11 12 20 7 17 19 12 16 8 6 13 16 12 25 1 1 17 13 16 7 12 1 7 16 15 6 8 23 25 22 13 25 7 19 18 22 23 16 5 6 20 10 1 25 8 19 6 23 5 20 7 17 25 6 22 18 12 18 25 15 3 27 9 8 17 3 27 7 8 10 6 15 18 7 3 10 19 3 13 20 17 10 15 19 6 3 11 25 15 2 15 18 18 22 23 22 7 7 13 9 11 11 12 22 1 5 10 6 25 16 17 17 1 2 22 23 10 3 21 23 18 1 7 3 27 7 13 21 17 25 10 16 25 16 27 6 25 6 17 22 7 7 8 18 16 22 3 8 16 19 27 2 22 27 12 21 13 23 23 23 13 21 11 18 3 25 22 19 23 25 9 11 10 11 5 19 8 15 13 16 3 2 15 5 15 19 20 17 9 6 11 17 16 27 7 15 23 16 20 25 8 7 23 3 22 15 21 3 1 23 15 10 27 27 15 27 3 25 5 10 13 22 25 15 7 22 15 21 8 1 17 7 11 12 27 22 20 10 7 2 7 2 12 25 12 8 20 7 16 5 23 5 6 17 25 15 20 16 15 7 25 12 2 16 21 7 16 21 25 17 18 8 23 17 9 8 10 27 20 11 9 7 12 25 15 1 12 21 25 5 5 17 19 19 7 19 11 12 19 21 23 23 21 21 8 6 20 20 3 22 3 18 13 23 19 13 17 17 13 3 2 13 18 9 22 22 6 19 18 6 17 22 17 8 18 16 18 19 10 17 23 19 27 20 9 5 21 12 18 17 6 1 13 7 17 2 3 25 10 27 20 25 2 1 1 16 5 21 25 5 23 2 23 20 10 22 21 7 13 10 16 9 1 23 13 11 7 21 13 20 25 13 13 6 17 7 17 27 7 8 17 18 15 17 10 13 23 27 17 25 17 5 21 7 7 7 17 23 9 1 23 18 18 20 3 21 8 17 2 6 23 27 7 1 18 18 23 8 16 23 15 10 17 1 6 1 6 18 23 2 17 12 9 2 18 10 11 16 17 19 25 22 27 13 15 12 13 2 6 22 27 21 16 20 17 27 11 17 8 15 3 8 5 7 9 21 11 17 23 21 23 1 13 20 11 17 2 5 6 16 22 13 2 17 22 18 23 7 20 1 3 1 7 25 18 6 6 11 21 5 17 3 17 5 27 18 2 15 7 25 7 16 7 25 13 15 10 5 17 11 2 9 6 11 2 8 27 15 3 3 17 12 8 19 5 6 27 13 8 12 2 6 25 23 17 22 18 6 16 8 6 23 12 15 18 21 1 5 18 18 1 3 6 15 27 10 27 12 25 13 11 6 11 19 17 22 23 22 3 17 8 10 9 7 17 17 9 6 20 18 15 7 2 7 18 19 8 7 8 16 2 7 15 25 13 13 22 23 10 20 13 11 16 11 20 7 21 1 12 17 25 6 20 8 10 10 21 15 9 7 2 7 16 13 17 22 20 20 11 7 19 21 9 20 6 15 21 6 6 7 17 12 7 23 7 2 27 16 7 12 21 17 23 20 9 8 3 20 12 25 27 10 23 23 21 3 5 22 9 8 16 10 7 1 25 21 13 19 1 21 6 23 7 10 11 16 7 5 17 1 27 12 17 16 21 8 27 9 23 1 1 16 10 10 20 9 3 20 17 12 23 11 16 5 3 8 8 3 7 1 27 12 1 16 1 5 7 7 17 11 8 8 17 11 7 15 7 1 21 15 1 12 13 16 10 15 17 27 23 19 20 7 7 17 20 18 12 27 6 21 15 1 20 17 17 3 9 3 27 20 12 7 23 16 7 5 23 7 6 23 18 3 22 22 11 18 20 27 2 18 11 25 12 3 13 17 11 3 5 5 12 3 8 22 2 23 9 23 16 17 12 17 2 18 7 15 25 19 13 7 22 23 16 2 21 13 1 25 9 19 9 6 7 27 5 1 27 10 25 17 8 17 5 21 23 13 18 19 10 3 15 27 9 5 23 3 15 20 1 17 3 7 9 19 27 18 15 7 15 1 7 7 11 5 23 16 20 23 5 7 1 8 13 10 21 22 5 5 17 21 15 5 7 16 13 18 17 17 6 17 18 21 22 23 15 19 13 22 9 12 7 23 1 23 27 21 25 21 20 19 17 3 16 19 3 6 15 7 9 19 5 11 2 5 7 3 7 25 5 11 7 18 7 22 10 20 1 1 22 5 15 22 16 10 21 3 3 6 6 9 16 15 19 10 20 25 21 7 22 27 9 9 5 17 23 12 5 18 11 6 15 19 17 19 10 2 15 1 27 5 5 9 3 11 16 12 17 17 23 11 18 9 13 23 12 16 6 17 23 6 2 6 17 6 7 3 20 21 7 11 3 8 19 13 2 8 2 27 6 16 2 17 25 15 6 12 17 8 11 19 2 11 7 9 9 18 2 6 17 8 5 25 17 22 22 15 16 16 17 13 27 11 6 18 7 10 12 3 12 22 23 27 12 22 13 3 7 16 27 11 7 17 2 12 11 18 7 9 19 9 7 22 15 8 17 5 16 17 17 23 22 13 1 11 7 21 19 18 17 5 23 6 7 5 1 17 6 19 23 1 7 7 1 17 7 27 11 3 11 7 1 3 2 27 22 16 3 20 17 2 20 9 10 7 22 16 7 3 20 17 2 16 8 17 11 16 8 10 7 22 10 7 2 7 23 17 12 7 11 7 8 2 8 10 19 18 7 21 8 15 9 8 7 23 20 17 1 22 10 10 1 11 9 19 12 22 6 13 21 11 19 27 3 20 23 25 12 7 16 20 1 11 6 18 7 11 5 13 16 9 10 25 20 17 11 3 22 7 25 17 6 25 11 12 9 2 15 17 7 15 13 17 22 17 23 17 21 17 5 16 17 16 5 17 15 8 12 10 22 17 17 13 17 7 6 3 16 20 16 16 7 27 3 8 17 5 17 15 25 3 22 21 17 12 7 16 22 17 7 25 1 27 8 3 11 16 7 7 8 1 21 7 2 3 7 13 1 17 17 1 6 12 5 6 23 6 7 10 20 9 18 9 25 15 1 15 22 20 9 7 22 20 9 1 25 9 9 5 27 5 13 21 17 19 25 17 3 21 13 17 9 9 7 27 17 3 22 13 16 19 6 11 12 15 6 3 16 8 1 12 12 1 23 22 7 27 27 8 20 11 25 7 21 1 19 23 27 18 17 3 17 3 17 7 2 13 21 13 1 3 11 20 6 2 16 22 3 9 16 20 25 15 1 23 5 18 6 19 1 11 17 6 19 23 15 9 17 13 25 7 21 11 7 8 10 27 1 15 12 20 9 13 5 19 7 10 18 10 15 2 17 1 18 13 21 12 8 1 20 19 22 23 8 22 11 15 18 11 23 11 13 7 27 10 12 7 6 5 3 25 18 13 5 7 27 13 17 23 10 17 18 27 3 8 18 3 23 3 16 25 22 6 3 21 3 13 22 6 11 8 15 25 3 13 15 17 2 7 2 19 10 3 12 9 11 7 16 2 20 12 19 8 19 12 6 25 23 7 12 7 25 10 23 9 21 25 27 12 16 16 8 10 11 9 17 22 17 25 9 12 23 5 23 20 21 19 15 5 1 17 11 7 25 23 15 6 9 3 8 13 22 17 9 9 10 17 12 8 10 17 13 6 19 22 3 27 13 2 6 2 17 10 11 8 17 13 23 8 6 13 2 6 22 21 22 19 17 3 9 18 25 22 5 16 6 5 16 3 23 13 15 13 19 9 6 17 23 21 21 10 18 17 1 8 6 21 23 11 13 2 9 9 5 17 17 13 20 19 7 3 8 1 9 13 21 1 16 17 18 19 9 13 19 7 17 8 23 20 10 9 5 23 13 21 3 18 3 2 13 13 7 11 27 7 10 6 11 2 1 3 22 20 17 5 22 11 21 23 7 20 15 9 1 1 10 9 13 19 13 25 17 8 12 2 2 9 2 1 7 22 6 9 22 9 18 5 18 7 6 25 15 17 25 23 18 6 1 3 3 19 25 10 23 6 16 9 27 12 22 18 16 21 11 6 16 2 10 5 16 17 19 20 17 15 10 19 21 3 17 22 22 21 21 6 22 10 23 5 18 2 22 8 17 23 23 13 3 7 11 11 12 22 21 5 10 13 10 1 7 3 17 10 22 6 9 9 19 25 25 22 2 16 25 22 7 21 8 9 27 5 11 13 2 5 19 20 19 10 8 22 6 15 7 16 12 13 2 18 21 21 10 25 19 3 21 18 22 15 8 13 17 7 7 7 27 5 2 2 16 7 3 17 2 21 27 5 17 21 21 1 2 12 17 15 25 16 3 13 23 1 1 6 23 1 17 17 20 16 13 25 27 15 1 10 21 20 7 7 17 7 27 7 17 3 11 1 18 18 18 15 7 1 19 2 10 25 27 7 8 11 22 13 2 9 23 13 11 16 17 25 17 27 5 18 27 8 2 7 16 3 23 2 11 8 6 12 6 27 3 10 9 9 1 12 9 10 21 8 19 2 12 7 6 18 3 16 17 9 19 7 17 16 27 20 16 19 19 1 19 1 10 21 25 17 8 23 9 5 13 11 8 11 7 2 25 18 17 7 23 1 7 3 16 7 3

[出力例]

610372398

■参照サイト
AtCoder Beginner Contest 149

2022年3月29日

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

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

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

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

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

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

int main(){
    
    // 1. 入力情報.
    int N;
    LL K;
    scanf("%d %lld", &N, &K);
    vl a, b;
    rep(i, N){
        LL t;
        scanf("%lld", &t);
        a.pb(t);
    }
    rep(i, N){
        LL t;
        scanf("%lld", &t);
        b.pb(t);
    }
    
    // 2. sort.
    sort(all(a));
    sort(all(b));
    reverse(all(b));
    
    // 3. 評価関数.
    auto f = [&](LL m) -> bool {
        // 3-1. 修行回数をカウント.
        // -> 完食にかかる時間を, m 以下にできるかを, 各メンバー毎に確認し,
        //    超過分は, 修行回数に反映させる.
        LL k = 0;
        rep(i, N){
            LL t = a[i] * b[i] - m;
            if(t > 0){
                LL q = t / b[i];
                LL r = t % b[i];
                k += q + (r > 0);
            }
        }
        
        // 3-2. 判定結果.
        return (k <= K);
    };
    
    // 4. 二分探索で確認してみる.
    LL l = -1, h = 2e12 + 1, m;
    while(l + 1 < h){
        LL m = (h + l) >> 1LL;
        if(f(m)) h = m;
        else     l = m;
        // printf("h=%lld l=%lld m=%lld\n", h, l, m);
    }
    
    // 5. 出力.
    printf("%lld\n", h);
    return 0;
    
}

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vl = vector<LL>;

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

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

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

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

#define pb push_back

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

int main(){

// 1. 入力情報.

int N;

LL K;

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

vl a, b;

rep(i, N){

LL t;

scanf("%lld", &t);

a.pb(t);

}

rep(i, N){

LL t;

scanf("%lld", &t);

b.pb(t);

}

// 2. sort.

sort(all(a));

sort(all(b));

reverse(all(b));

// 3. 評価関数.

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

// 3-1. 修行回数をカウント.

// -> 完食にかかる時間を, m 以下にできるかを, 各メンバー毎に確認し,

// 超過分は, 修行回数に反映させる.

LL k = 0;

rep(i, N){

LL t = a[i] * b[i] - m;

if(t > 0){

LL q = t / b[i];

LL r = t % b[i];

k += q + (r > 0);

}

// 3-2. 判定結果.

return (k <= K);

};

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

LL l = -1, h = 2e12 + 1, m;

while(l + 1 < h){

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

if(f(m)) h = m;

else l = m;

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

}

// 5. 出力.

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

return 0;

}

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

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

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

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

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

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

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

[出力例]
7

[入力例]
20 32
81 18 82 83 42 20 32 50 37 37 37 117 119 63 99 104 34 29 31 99
108 94 5 72 99 81 122 98 97 12 114 15 85 6 8 12 28 26 51 94

[出力例]
3069

[入力例]
100 2022
175 889 1050 899 493 1109 480 410 194 274 940 594 993 685 929 499 1087 889 422 65 626 367 95 395 481 291 63 90 243 948 661 59 840 822 1011 583 994 532 791 120 653 1045 86 917 428 774 313 307 850 683 249 725 800 1000 194 138 943 728 1160 861 466 575 696 908 694 256 508 987 346 380 1200 328 772 567 1234 169 227 958 1178 1132 263 483 701 1199 770 840 279 399 219 512 359 999 846 1026 405 677 475 39 680 654
789 461 494 1030 915 230 308 639 80 365 259 619 888 901 152 1001 207 341 126 989 341 875 725 928 1185 913 495 54 918 1013 1007 328 129 222 672 854 865 888 960 111 114 999 293 898 153 696 133 543 571 680 443 1010 424 378 42 642 205 1159 516 992 331 1140 148 555 711 890 559 1097 840 1049 337 758 23 147 1008 227 280 1020 1176 956 307 688 403 1152 586 549 123 533 923 953 549 363 162 262 545 161 616 104 99 1010

[出力例]
310986

[入力例]
500 20220329
37625 31913 24870 10246 5597 6117 2413 80708 3713 71835 28673 17358 70496 78135 39198 56159 69643 62141 52081 85925 36168 53456 36791 19552 86319 94235 60978 73 48970 15774 96787 6203 39312 78991 39831 64409 69937 46172 88825 3364 17642 71353 92292 34332 72775 13590 57063 57262 65805 89570 42907 59477 50649 17386 15645 32122 20687 49918 36103 27749 68603 34616 5443 26360 80069 2565 46764 23616 77240 39090 39809 89091 36799 44416 40965 50181 83491 68503 63342 98144 3670 68623 32330 80673 932 25711 29150 25281 76132 99137 48546 25860 79432 96231 14213 6081 93038 46016 81327 2938 29152 3902 31157 2607 84550 81679 84559 44970 13987 27917 71876 28680 65172 92341 88527 83301 85380 25275 78139 7502 72015 53003 1522 28029 23607 41223 37666 19130 81285 36240 79704 94665 1288 41846 57565 64973 57022 35427 98862 89808 95744 8666 16810 27396 47933 71967 55470 42647 11546 56832 21494 62981 40456 34307 25131 91134 4961 91643 6728 78540 57311 73967 57535 49657 90885 77926 10778 71026 63575 10423 62872 17391 66113 93041 8546 98816 19757 47473 53228 67363 97553 43075 99385 81826 14701 97364 47361 43153 57201 7603 18133 5592 91956 25641 53938 18268 97690 98476 68837 5069 90913 58932 89428 60549 47294 1813 5439 8892 76360 44760 83349 22912 97203 89608 47449 33005 80860 6983 45462 37148 9697 85726 15241 3723 16232 13784 27340 52806 16193 86807 24704 59077 74832 37116 89428 92208 34378 21222 99483 53062 40897 81277 52983 70337 91622 77244 50129 78629 44828 59495 77416 54753 44417 43794 32880 5296 84727 11329 96828 36889 44764 89931 44450 32227 30184 63574 11978 39433 48341 82635 82003 79151 64875 38606 33350 74360 70450 10756 75963 49812 95020 96078 53031 28733 68596 86780 69917 45924 46967 29941 63478 47367 8198 75674 16062 27087 97145 7979 12181 1199 2368 95072 71203 54853 90622 1225 6060 73262 45713 69069 61253 65807 85266 99235 71278 74210 17839 37675 1054 15912 9527 20160 26684 74853 55543 97486 40330 56129 1661 48290 64480 92164 62873 68305 59187 3533 40781 35715 96842 56522 58245 49556 51024 96827 59958 47007 24472 91676 27841 22111 91365 34518 47384 8703 50678 88377 15334 48858 70168 21867 1831 28545 50540 75700 27378 46666 78682 8544 62946 64800 18977 28833 54515 3039 90347 14531 69205 52984 97325 20125 855 45019 42113 13506 32618 94325 83190 55278 84089 53509 86263 45247 96040 59799 94469 34717 90715 9403 83269 52358 62100 56992 25039 95692 74868 76712 19291 5221 13466 75001 67951 67917 64799 57736 98881 35159 94817 82349 73975 79043 632 57473 61687 8389 97251 99172 52119 62109 68718 1901 18325 68982 2134 12502 82296 36472 40997 33246 8050 46683 56391 65582 28395 78459 19568 15544 89253 27707 49788 46919 16236 55180 23156 18882 39544 24950 19806 8264 32044 2708 26739 51332 64592 68103 67851 11442 95862 64458 22022 91140 76445 54395 85252 61088 16910 88482 31605 36198 99017 81459 48080 34080 5124 59895 65204 74955 78709 55327 61890 99823 40246 53738 68584 85371 54849 61594 94088 19050 77087 34534
59010 20255 19482 78511 49049 19936 32557 99291 42203 49456 7865 14983 95989 69314 92747 62908 39231 831 9134 52535 24327 56398 76884 11563 79480 76035 3325 95646 20031 88304 60065 35328 5186 54238 59800 27732 14202 38682 9202 71431 2764 26160 94849 87853 23811 95518 16904 62774 64945 2025 89313 57743 77347 91056 5996 2024 19734 42747 76709 47954 85744 56704 91887 68624 29158 33388 8860 41326 30626 76320 38867 9994 70607 50896 21755 500 94586 76879 81137 19332 55507 76703 11837 65683 47652 61606 91630 32740 90 99074 13192 65843 21722 200 16681 58916 55279 97204 34487 73077 36963 48514 61354 70302 65235 50529 29272 70814 70461 62013 3186 31372 12227 84717 9372 977 94845 70512 17294 32834 30276 9608 82065 61097 36205 9849 83062 96798 14768 76693 98122 79180 31567 52884 15147 26515 80647 5907 64893 57939 7903 36880 55701 96824 17177 71544 99253 74819 65043 70471 6927 8608 64809 63519 100 52844 41069 700 57715 50281 80309 27200 57909 34611 12033 24774 82655 19208 81760 9031 33309 9312 3891 46442 16763 18791 41960 79402 33696 58886 56310 51721 67753 85790 32669 45890 13827 95470 70733 12954 78186 31574 27672 71917 96700 31900 79909 60854 12771 31590 94253 55392 20561 81713 86940 42014 73738 1200 58010 99733 91269 95867 29304 56580 57363 70097 33537 85968 18815 59636 63948 3389 2023 78141 7730 28647 65207 75793 75673 82387 78425 28024 22111 28743 95736 70783 34106 75291 65608 8540 51040 53513 53756 70135 38390 95521 45411 54559 4746 33090 95127 70952 2030 92034 64630 71398 62597 45700 33596 80810 23332 31194 91503 31282 89479 40570 6257 9272 47361 89079 8499 56972 91107 29355 75475 75001 17464 88173 51058 63999 41954 78259 88735 66791 25175 67869 87589 25370 16043 56293 93780 33195 31967 28658 34104 55377 1242 49709 53895 53925 97252 76023 2022 89453 66027 51111 65009 13114 68736 94184 52438 52723 8658 66955 34543 63144 53776 17584 29772 93815 61386 87999 77814 4144 63764 48671 28736 73960 54032 93427 50583 68395 65837 12709 900 46313 61277 52199 79704 19775 36702 77234 94539 53429 31067 80305 81045 81960 7533 89431 80 60009 91501 97534 85846 61857 26774 16809 17537 86751 29263 18329 35447 41421 56599 73589 19494 44277 71024 48802 66267 42048 17411 18360 12618 74638 12564 99663 50218 99060 96977 5808 35397 49093 78722 61516 31780 25168 29985 88898 55278 13287 13782 16583 33090 9425 48366 83891 66555 61870 27868 24779 3231 52664 43790 91014 58932 85335 97369 51929 36241 1500 56423 2050 42954 87402 1715 44440 68934 64793 99578 8777 25587 35031 57345 79418 77995 36254 73783 75360 12277 53072 26170 95122 98721 28810 45268 38976 50802 36781 32398 72050 70947 53134 85646 71050 72953 54233 4654 55954 974 29568 65128 17962 32795 4774 86883 21870 91824 10341 87696 3966 6594 88562 7600 36696 42613 65637 46916 93207 39481 14920 30012 56793 29281 38675 7487 58426 97489 11030 49291 15421 2652 71495 61962 1800 26330 3099 48280 62655 59020 82685 51028 16192 90417 82279 28684 77097 51096 63584

[出力例]
167129136

[入力例]

3 5

4 2 1

2 3 1

[出力例]

※AtCoderテストケースより

[入力例]

3 8

4 2 1

2 3 1

[出力例]

※AtCoderテストケースより

[入力例]

11 14

3 1 4 1 5 9 2 6 5 3 5

8 9 7 9 3 2 3 8 4 6 2

[出力例]

※AtCoderテストケースより

[入力例]

5 12

3 6 5 4 7

5 3 7 2 1

[出力例]

[入力例]

20 32

81 18 82 83 42 20 32 50 37 37 37 117 119 63 99 104 34 29 31 99

108 94 5 72 99 81 122 98 97 12 114 15 85 6 8 12 28 26 51 94

[出力例]

3069

[入力例]

100 2022

175 889 1050 899 493 1109 480 410 194 274 940 594 993 685 929 499 1087 889 422 65 626 367 95 395 481 291 63 90 243 948 661 59 840 822 1011 583 994 532 791 120 653 1045 86 917 428 774 313 307 850 683 249 725 800 1000 194 138 943 728 1160 861 466 575 696 908 694 256 508 987 346 380 1200 328 772 567 1234 169 227 958 1178 1132 263 483 701 1199 770 840 279 399 219 512 359 999 846 1026 405 677 475 39 680 654

789 461 494 1030 915 230 308 639 80 365 259 619 888 901 152 1001 207 341 126 989 341 875 725 928 1185 913 495 54 918 1013 1007 328 129 222 672 854 865 888 960 111 114 999 293 898 153 696 133 543 571 680 443 1010 424 378 42 642 205 1159 516 992 331 1140 148 555 711 890 559 1097 840 1049 337 758 23 147 1008 227 280 1020 1176 956 307 688 403 1152 586 549 123 533 923 953 549 363 162 262 545 161 616 104 99 1010

[出力例]

310986

[入力例]

500 20220329

37625 31913 24870 10246 5597 6117 2413 80708 3713 71835 28673 17358 70496 78135 39198 56159 69643 62141 52081 85925 36168 53456 36791 19552 86319 94235 60978 73 48970 15774 96787 6203 39312 78991 39831 64409 69937 46172 88825 3364 17642 71353 92292 34332 72775 13590 57063 57262 65805 89570 42907 59477 50649 17386 15645 32122 20687 49918 36103 27749 68603 34616 5443 26360 80069 2565 46764 23616 77240 39090 39809 89091 36799 44416 40965 50181 83491 68503 63342 98144 3670 68623 32330 80673 932 25711 29150 25281 76132 99137 48546 25860 79432 96231 14213 6081 93038 46016 81327 2938 29152 3902 31157 2607 84550 81679 84559 44970 13987 27917 71876 28680 65172 92341 88527 83301 85380 25275 78139 7502 72015 53003 1522 28029 23607 41223 37666 19130 81285 36240 79704 94665 1288 41846 57565 64973 57022 35427 98862 89808 95744 8666 16810 27396 47933 71967 55470 42647 11546 56832 21494 62981 40456 34307 25131 91134 4961 91643 6728 78540 57311 73967 57535 49657 90885 77926 10778 71026 63575 10423 62872 17391 66113 93041 8546 98816 19757 47473 53228 67363 97553 43075 99385 81826 14701 97364 47361 43153 57201 7603 18133 5592 91956 25641 53938 18268 97690 98476 68837 5069 90913 58932 89428 60549 47294 1813 5439 8892 76360 44760 83349 22912 97203 89608 47449 33005 80860 6983 45462 37148 9697 85726 15241 3723 16232 13784 27340 52806 16193 86807 24704 59077 74832 37116 89428 92208 34378 21222 99483 53062 40897 81277 52983 70337 91622 77244 50129 78629 44828 59495 77416 54753 44417 43794 32880 5296 84727 11329 96828 36889 44764 89931 44450 32227 30184 63574 11978 39433 48341 82635 82003 79151 64875 38606 33350 74360 70450 10756 75963 49812 95020 96078 53031 28733 68596 86780 69917 45924 46967 29941 63478 47367 8198 75674 16062 27087 97145 7979 12181 1199 2368 95072 71203 54853 90622 1225 6060 73262 45713 69069 61253 65807 85266 99235 71278 74210 17839 37675 1054 15912 9527 20160 26684 74853 55543 97486 40330 56129 1661 48290 64480 92164 62873 68305 59187 3533 40781 35715 96842 56522 58245 49556 51024 96827 59958 47007 24472 91676 27841 22111 91365 34518 47384 8703 50678 88377 15334 48858 70168 21867 1831 28545 50540 75700 27378 46666 78682 8544 62946 64800 18977 28833 54515 3039 90347 14531 69205 52984 97325 20125 855 45019 42113 13506 32618 94325 83190 55278 84089 53509 86263 45247 96040 59799 94469 34717 90715 9403 83269 52358 62100 56992 25039 95692 74868 76712 19291 5221 13466 75001 67951 67917 64799 57736 98881 35159 94817 82349 73975 79043 632 57473 61687 8389 97251 99172 52119 62109 68718 1901 18325 68982 2134 12502 82296 36472 40997 33246 8050 46683 56391 65582 28395 78459 19568 15544 89253 27707 49788 46919 16236 55180 23156 18882 39544 24950 19806 8264 32044 2708 26739 51332 64592 68103 67851 11442 95862 64458 22022 91140 76445 54395 85252 61088 16910 88482 31605 36198 99017 81459 48080 34080 5124 59895 65204 74955 78709 55327 61890 99823 40246 53738 68584 85371 54849 61594 94088 19050 77087 34534

59010 20255 19482 78511 49049 19936 32557 99291 42203 49456 7865 14983 95989 69314 92747 62908 39231 831 9134 52535 24327 56398 76884 11563 79480 76035 3325 95646 20031 88304 60065 35328 5186 54238 59800 27732 14202 38682 9202 71431 2764 26160 94849 87853 23811 95518 16904 62774 64945 2025 89313 57743 77347 91056 5996 2024 19734 42747 76709 47954 85744 56704 91887 68624 29158 33388 8860 41326 30626 76320 38867 9994 70607 50896 21755 500 94586 76879 81137 19332 55507 76703 11837 65683 47652 61606 91630 32740 90 99074 13192 65843 21722 200 16681 58916 55279 97204 34487 73077 36963 48514 61354 70302 65235 50529 29272 70814 70461 62013 3186 31372 12227 84717 9372 977 94845 70512 17294 32834 30276 9608 82065 61097 36205 9849 83062 96798 14768 76693 98122 79180 31567 52884 15147 26515 80647 5907 64893 57939 7903 36880 55701 96824 17177 71544 99253 74819 65043 70471 6927 8608 64809 63519 100 52844 41069 700 57715 50281 80309 27200 57909 34611 12033 24774 82655 19208 81760 9031 33309 9312 3891 46442 16763 18791 41960 79402 33696 58886 56310 51721 67753 85790 32669 45890 13827 95470 70733 12954 78186 31574 27672 71917 96700 31900 79909 60854 12771 31590 94253 55392 20561 81713 86940 42014 73738 1200 58010 99733 91269 95867 29304 56580 57363 70097 33537 85968 18815 59636 63948 3389 2023 78141 7730 28647 65207 75793 75673 82387 78425 28024 22111 28743 95736 70783 34106 75291 65608 8540 51040 53513 53756 70135 38390 95521 45411 54559 4746 33090 95127 70952 2030 92034 64630 71398 62597 45700 33596 80810 23332 31194 91503 31282 89479 40570 6257 9272 47361 89079 8499 56972 91107 29355 75475 75001 17464 88173 51058 63999 41954 78259 88735 66791 25175 67869 87589 25370 16043 56293 93780 33195 31967 28658 34104 55377 1242 49709 53895 53925 97252 76023 2022 89453 66027 51111 65009 13114 68736 94184 52438 52723 8658 66955 34543 63144 53776 17584 29772 93815 61386 87999 77814 4144 63764 48671 28736 73960 54032 93427 50583 68395 65837 12709 900 46313 61277 52199 79704 19775 36702 77234 94539 53429 31067 80305 81045 81960 7533 89431 80 60009 91501 97534 85846 61857 26774 16809 17537 86751 29263 18329 35447 41421 56599 73589 19494 44277 71024 48802 66267 42048 17411 18360 12618 74638 12564 99663 50218 99060 96977 5808 35397 49093 78722 61516 31780 25168 29985 88898 55278 13287 13782 16583 33090 9425 48366 83891 66555 61870 27868 24779 3231 52664 43790 91014 58932 85335 97369 51929 36241 1500 56423 2050 42954 87402 1715 44440 68934 64793 99578 8777 25587 35031 57345 79418 77995 36254 73783 75360 12277 53072 26170 95122 98721 28810 45268 38976 50802 36781 32398 72050 70947 53134 85646 71050 72953 54233 4654 55954 974 29568 65128 17962 32795 4774 86883 21870 91824 10341 87696 3966 6594 88562 7600 36696 42613 65637 46916 93207 39481 14920 30012 56793 29281 38675 7487 58426 97489 11030 49291 15421 2652 71495 61962 1800 26330 3099 48280 62655 59020 82685 51028 16192 90417 82279 28684 77097 51096 63584

[出力例]

167129136

■参照サイト
AtCoder Beginner Contest 144

2022年3月28日2022年3月28日

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

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

■感想.
1. 問題Fは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 実装に苦労したものの, 親頂点としてあり得る上限の個数に着目して, 同じ整数が複数登場した場合も, 対応出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/abc140/editorial.pdf
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
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 a first
#define b second
int memo[1 << 20];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    map<int, int> m;
    rep(i, 1 << N){
        int s;
        scanf("%d", &s);
        m[s]++;
    }
    
    // 2. スライム配置.
    bool ok = true;
    int mIdx = (1 << (N + 1));
    PQ pq; // 親頂点(候補).
    pq.push(1);
    map<int, int>::reverse_iterator itr;
    // S の 大きい要素から割り当てる.
    for(itr = m.rbegin(); itr != m.rend(); ++itr){
        // フラグ, 終了確認.
        if(!ok) break;
        
        // 親のサイズ, 整数の出現数.
        int ps = pq.size();
        int ns = itr->b;
        
        // 割り当て不可.
        if(ps < ns){
            ok = false;
            break;
        }
        
        // 整数の割り当て.
        // -> 同じ整数を, 一括で割り当てる.
        queue<int> q;
        int sCur = itr->a;
        while(!pq.empty() && ns){
            int c = pq.top();
            pq.pop();
            while(c < mIdx){
                memo[c] = sCur;
                if((c << 1) + 1 < mIdx) q.push((c << 1) + 1);
                c <<= 1;
            }
            --ns;
        }
        
        // 親頂点(次回以降).
        while(!q.empty()){
            int t = q.front();
            q.pop();
            pq.push(t);
        }
    }
    
    // 3. 出力.
    printf("%s\n", ok ? "Yes" : "No");
    return 0;
    
}

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

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

#define b second

int memo[1 << 20];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

map<int, int> m;

rep(i, 1 << N){

int s;

scanf("%d", &s);

m[s]++;

}

// 2. スライム配置.

bool ok = true;

int mIdx = (1 << (N + 1));

PQ pq; // 親頂点(候補).

pq.push(1);

map<int, int>::reverse_iterator itr;

// S の大きい要素から割り当てる.

for(itr = m.rbegin(); itr != m.rend(); ++itr){

// フラグ, 終了確認.

if(!ok) break;

// 親のサイズ, 整数の出現数.

int ps = pq.size();

int ns = itr->b;

// 割り当て不可.

if(ps < ns){

ok = false;

break;

}

// 整数の割り当て.

// -> 同じ整数を, 一括で割り当てる.

queue<int> q;

int sCur = itr->a;

while(!pq.empty() && ns){

int c = pq.top();

pq.pop();

while(c < mIdx){

memo[c] = sCur;

if((c << 1) + 1 < mIdx) q.push((c << 1) + 1);

c <<= 1;

}

--ns;

}

// 親頂点(次回以降).

while(!q.empty()){

int t = q.front();

q.pop();

pq.push(t);

}

// 3. 出力.

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

return 0;

}

[入力例]
2
4 2 3 1

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

[入力例]
2
1 2 3 1

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

[入力例]
1
1 1

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

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

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

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

[出力例]
Yes

[入力例]
3
5 5 5 5 6 5 6 7

[出力例]
No

[入力例]
5
52 52 13 47 1 29 2 55 21 30 43 1 53 2 31 2 7 50 1 18 37 23 15 3 28 5 52 9 49 29 30 37

[出力例]
Yes

[入力例]
7
35 7 8 33 19 12 25 1 5 13 26 2 33 52 36 15 52 32 6 52 5 23 2 55 9 33 33 8 33 5 17 33 35 53 50 33 17 7 33 8 37 25 11 50 30 33 19 33 37 51 8 7 20 34 32 32 33 33 33 23 20 33 9 33 23 19 30 51 18 12 3 22 33 50 31 33 19 33 31 23 22 53 12 33 13 15 54 13 11 15 15 33 52 2 33 33 53 30 27 33 24 33 20 54 31 17 17 21 52 28 33 37 15 33 35 18 33 17 33 32 15 26 32 14 5 50 33 27

[出力例]
Yes

[入力例]
10
82 64 51 66 1 88 89 12 69 87 81 6 55 65 119 77 76 32 19 48 112 46 52 91 50 76 39 30 29 48 89 105 78 89 120 92 28 56 50 57 95 62 17 65 113 99 5 14 53 46 43 113 94 15 19 60 123 110 23 49 27 100 5 22 3 44 78 15 20 65 92 89 80 28 29 101 93 43 41 70 28 100 22 90 27 22 103 9 92 79 43 21 46 52 80 105 35 115 69 62 98 44 40 72 23 60 87 115 46 114 60 21 34 58 28 4 56 107 43 21 63 20 115 97 56 23 114 114 114 62 11 23 36 24 23 79 64 25 17 18 16 19 93 28 92 113 24 23 29 47 19 35 88 59 59 84 22 86 119 110 102 58 11 85 109 2 34 58 48 110 93 101 86 39 94 8 12 76 13 108 15 32 80 9 12 83 90 48 117 93 121 92 20 108 48 80 92 65 116 96 87 31 94 52 99 1 117 112 22 49 17 75 30 35 100 107 33 44 81 46 116 19 33 35 80 93 44 85 81 19 21 15 31 28 55 73 20 41 108 88 19 86 97 72 48 41 109 16 32 17 57 56 83 102 113 74 93 19 74 76 13 80 33 39 20 113 13 23 6 7 99 10 78 104 43 108 80 70 108 71 77 86 7 26 2 74 56 110 47 73 31 110 74 115 32 70 45 24 40 28 122 19 92 34 24 13 24 2 87 57 51 51 48 37 87 74 106 115 63 76 97 31 49 114 19 104 51 112 106 24 69 111 71 63 22 66 94 55 118 69 111 46 115 54 25 30 73 35 44 117 105 62 58 103 22 16 81 99 101 66 52 26 63 105 58 29 79 103 51 2 80 30 49 61 98 70 30 75 119 78 62 100 49 51 117 109 1 78 48 10 46 80 105 115 4 29 18 60 39 45 108 103 57 40 82 96 87 9 89 83 73 82 117 36 84 25 85 10 27 11 74 92 10 21 69 57 36 83 97 23 110 115 69 90 46 66 102 119 101 118 16 43 39 23 118 24 13 80 5 81 106 58 43 33 40 117 108 121 52 30 41 90 114 6 99 82 52 83 78 80 55 13 35 39 17 97 80 94 76 119 101 18 18 49 66 88 116 29 52 37 118 75 30 82 2 119 80 26 92 92 113 30 64 100 81 50 92 7 57 10 96 14 23 70 79 43 30 107 115 32 114 24 112 55 34 118 109 95 38 83 115 103 18 68 7 70 30 84 55 11 78 14 7 92 51 73 19 39 81 57 93 84 57 34 28 29 91 47 107 52 113 11 83 47 17 107 21 12 114 56 27 109 76 9 91 54 7 24 7 1 56 54 15 25 75 66 72 52 74 32 43 84 49 66 78 38 38 72 84 117 91 69 90 11 47 27 21 117 20 52 101 77 64 60 88 83 80 94 92 47 27 27 11 101 94 27 41 63 74 21 4 67 115 25 8 18 118 80 104 10 118 20 93 23 24 118 47 86 109 89 46 72 4 74 74 2 109 93 13 110 82 74 98 72 109 108 97 59 44 105 85 7 17 33 56 5 36 111 5 31 14 95 77 60 108 121 29 118 74 13 77 24 3 64 80 74 87 120 30 46 101 61 44 25 36 43 21 56 103 90 92 38 68 38 41 34 76 69 105 7 101 23 64 40 101 9 92 13 3 100 51 2 32 75 26 22 117 13 76 24 69 113 78 48 55 79 78 9 32 61 77 79 83 8 56 38 32 119 76 36 104 119 49 116 54 27 70 90 43 5 89 116 24 41 117 120 69 61 2 69 103 106 32 18 81 28 51 3 20 49 88 75 46 60 26 105 20 18 99 97 56 114 53 93 21 6 40 32 51 71 77 33 86 75 9 19 13 91 30 74 120 116 72 58 81 58 37 58 83 72 47 17 38 118 14 74 47 15 36 91 85 13 110 11 100 66 35 102 45 4 86 9 26 101 86 49 89 55 79 99 51 115 82 17 3 113 62 105 23 43 14 33 84 69 78 3 70 53 36 76 97 17 58 91 84 62 7 55 73 8 40 112 90 59 25 97 116 55 84 52 28 91 114 65 30 41 88 48 23 102 61 100 77 21 43 72 92 22 8 17 74 107 99 68 21 32 64 121 62 78 80 1 50 13 48 51 48 60 90 37 85 67 51 107 85 108 84 102 65 98 25 83 110 114 28 91 1 113 105 118 19 111 50 84 43 108 116 59 48 108 68 17 79 73 112 78 108 2 14 17 69 32 105 47 50 17 30 6 83 68 23 19 10 17 1 39 52 25 91 118 29 58 46 72 78 91 52 118 97 58 29 89 63 11 52 101 1 47 120 2 6 20 30 122

[出力例]
Yes

[入力例]

4 2 3 1

[出力例]

Yes

※AtCoderテストケースより

[入力例]

1 2 3 1

[出力例]

Yes

※AtCoderテストケースより

[入力例]

1 1

[出力例]

※AtCoderテストケースより

[入力例]

4 3 5 3 1 2 7 8 7 4 6 3 7 2 3 6 2 7 3 2 6 7 3 4 6 7 3 4 2 5 2 3

[出力例]

※AtCoderテストケースより

[入力例]

1 2 3 5 6 5 6 7

[出力例]

Yes

[入力例]

5 5 5 5 6 5 6 7

[出力例]

[入力例]

52 52 13 47 1 29 2 55 21 30 43 1 53 2 31 2 7 50 1 18 37 23 15 3 28 5 52 9 49 29 30 37

[出力例]

Yes

[入力例]

35 7 8 33 19 12 25 1 5 13 26 2 33 52 36 15 52 32 6 52 5 23 2 55 9 33 33 8 33 5 17 33 35 53 50 33 17 7 33 8 37 25 11 50 30 33 19 33 37 51 8 7 20 34 32 32 33 33 33 23 20 33 9 33 23 19 30 51 18 12 3 22 33 50 31 33 19 33 31 23 22 53 12 33 13 15 54 13 11 15 15 33 52 2 33 33 53 30 27 33 24 33 20 54 31 17 17 21 52 28 33 37 15 33 35 18 33 17 33 32 15 26 32 14 5 50 33 27

[出力例]

Yes

[入力例]

82 64 51 66 1 88 89 12 69 87 81 6 55 65 119 77 76 32 19 48 112 46 52 91 50 76 39 30 29 48 89 105 78 89 120 92 28 56 50 57 95 62 17 65 113 99 5 14 53 46 43 113 94 15 19 60 123 110 23 49 27 100 5 22 3 44 78 15 20 65 92 89 80 28 29 101 93 43 41 70 28 100 22 90 27 22 103 9 92 79 43 21 46 52 80 105 35 115 69 62 98 44 40 72 23 60 87 115 46 114 60 21 34 58 28 4 56 107 43 21 63 20 115 97 56 23 114 114 114 62 11 23 36 24 23 79 64 25 17 18 16 19 93 28 92 113 24 23 29 47 19 35 88 59 59 84 22 86 119 110 102 58 11 85 109 2 34 58 48 110 93 101 86 39 94 8 12 76 13 108 15 32 80 9 12 83 90 48 117 93 121 92 20 108 48 80 92 65 116 96 87 31 94 52 99 1 117 112 22 49 17 75 30 35 100 107 33 44 81 46 116 19 33 35 80 93 44 85 81 19 21 15 31 28 55 73 20 41 108 88 19 86 97 72 48 41 109 16 32 17 57 56 83 102 113 74 93 19 74 76 13 80 33 39 20 113 13 23 6 7 99 10 78 104 43 108 80 70 108 71 77 86 7 26 2 74 56 110 47 73 31 110 74 115 32 70 45 24 40 28 122 19 92 34 24 13 24 2 87 57 51 51 48 37 87 74 106 115 63 76 97 31 49 114 19 104 51 112 106 24 69 111 71 63 22 66 94 55 118 69 111 46 115 54 25 30 73 35 44 117 105 62 58 103 22 16 81 99 101 66 52 26 63 105 58 29 79 103 51 2 80 30 49 61 98 70 30 75 119 78 62 100 49 51 117 109 1 78 48 10 46 80 105 115 4 29 18 60 39 45 108 103 57 40 82 96 87 9 89 83 73 82 117 36 84 25 85 10 27 11 74 92 10 21 69 57 36 83 97 23 110 115 69 90 46 66 102 119 101 118 16 43 39 23 118 24 13 80 5 81 106 58 43 33 40 117 108 121 52 30 41 90 114 6 99 82 52 83 78 80 55 13 35 39 17 97 80 94 76 119 101 18 18 49 66 88 116 29 52 37 118 75 30 82 2 119 80 26 92 92 113 30 64 100 81 50 92 7 57 10 96 14 23 70 79 43 30 107 115 32 114 24 112 55 34 118 109 95 38 83 115 103 18 68 7 70 30 84 55 11 78 14 7 92 51 73 19 39 81 57 93 84 57 34 28 29 91 47 107 52 113 11 83 47 17 107 21 12 114 56 27 109 76 9 91 54 7 24 7 1 56 54 15 25 75 66 72 52 74 32 43 84 49 66 78 38 38 72 84 117 91 69 90 11 47 27 21 117 20 52 101 77 64 60 88 83 80 94 92 47 27 27 11 101 94 27 41 63 74 21 4 67 115 25 8 18 118 80 104 10 118 20 93 23 24 118 47 86 109 89 46 72 4 74 74 2 109 93 13 110 82 74 98 72 109 108 97 59 44 105 85 7 17 33 56 5 36 111 5 31 14 95 77 60 108 121 29 118 74 13 77 24 3 64 80 74 87 120 30 46 101 61 44 25 36 43 21 56 103 90 92 38 68 38 41 34 76 69 105 7 101 23 64 40 101 9 92 13 3 100 51 2 32 75 26 22 117 13 76 24 69 113 78 48 55 79 78 9 32 61 77 79 83 8 56 38 32 119 76 36 104 119 49 116 54 27 70 90 43 5 89 116 24 41 117 120 69 61 2 69 103 106 32 18 81 28 51 3 20 49 88 75 46 60 26 105 20 18 99 97 56 114 53 93 21 6 40 32 51 71 77 33 86 75 9 19 13 91 30 74 120 116 72 58 81 58 37 58 83 72 47 17 38 118 14 74 47 15 36 91 85 13 110 11 100 66 35 102 45 4 86 9 26 101 86 49 89 55 79 99 51 115 82 17 3 113 62 105 23 43 14 33 84 69 78 3 70 53 36 76 97 17 58 91 84 62 7 55 73 8 40 112 90 59 25 97 116 55 84 52 28 91 114 65 30 41 88 48 23 102 61 100 77 21 43 72 92 22 8 17 74 107 99 68 21 32 64 121 62 78 80 1 50 13 48 51 48 60 90 37 85 67 51 107 85 108 84 102 65 98 25 83 110 114 28 91 1 113 105 118 19 111 50 84 43 108 116 59 48 108 68 17 79 73 112 78 108 2 14 17 69 32 105 47 50 17 30 6 83 68 23 19 10 17 1 39 52 25 91 118 29 58 46 72 78 91 52 118 97 58 29 89 63 11 52 101 1 47 120 2 6 20 30 122

[出力例]

Yes

■参照サイト
AtCoder Beginner Contest 140

C++の練習を兼ねて, AtCoder Regular Contest 138 の 問題A (Larger Score) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 150 の 問題D (Semi Common Multiple) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 165 の 問題F (LIS on Tree) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 153 の 問題E (Crested Ibis vs Monster) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 135 の 問題D (Digits Parade) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 152 の 問題D (Handstand 2) ～ 問題E (Flatten) を解いてみた.

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

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

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

C++の練習を兼ねて, AtCoder Regular Contest 138 の問題A (Larger Score) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 150 の問題D (Semi Common Multiple) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 165 の問題F (LIS on Tree) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 153 の問題E (Crested Ibis vs Monster) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 135 の問題D (Digits Parade) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 152 の問題D (Handstand 2) ～問題E (Flatten) を解いてみた.

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

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

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