個人用メモ帳

2022年1月13日2022年1月13日

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

C++の練習を兼ねて, AtCoder Beginner Contest 233 の問題E (Σ[k=0..10^100]floor(X／10^k)) を解いてみた.

■感想.
1. 問題Eは, 規則性を抽出できたので, AC版に到達できたと思う.
2. 個人的には, 文字列操作で, 数式の値を計算できる点が, 非常に面白いと感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
#define all(x) x.begin(), x.end()
LL xCum[505050];

int main(){
    
    // 1. 入力情報.
    char X[505050];
    scanf("%s", X);
    int xl = strlen(X);
    
    // 2. 累積和.
    rep(i, xl) xCum[i + 1] = xCum[i] + (X[i] - '0');
    
    // 3. 数式計算.
    LL cur = 0;
    string ans, sCur;
    rep(i, xl){
        // cur(一の位) を 連結.
        cur += xCum[xl - i];
        sCur = to_string(cur);
        ans.pb(sCur.back());
        
        // cur更新.
        sCur.pop_back();
        cur = sCur.empty() ? 0 : stoll(sCur);
    }
    
    // 4. sCur の 残り部分.
    while(!sCur.empty()){
        ans.pb(sCur.back());
        sCur.pop_back();
    }
    
    // 5. 反転.
    reverse(all(ans));
    
    // 6. 出力.
    printf("%s\n", ans.c_str());
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

#define pb push_back

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

LL xCum[505050];

int main(){

// 1. 入力情報.

char X[505050];

scanf("%s", X);

int xl = strlen(X);

// 2. 累積和.

rep(i, xl) xCum[i + 1] = xCum[i] + (X[i] - '0');

// 3. 数式計算.

LL cur = 0;

string ans, sCur;

rep(i, xl){

// cur(一の位) を連結.

cur += xCum[xl - i];

sCur = to_string(cur);

ans.pb(sCur.back());

// cur更新.

sCur.pop_back();

cur = sCur.empty() ? 0 : stoll(sCur);

}

// 4. sCur の残り部分.

while(!sCur.empty()){

ans.pb(sCur.back());

sCur.pop_back();

}

// 5. 反転.

reverse(all(ans));

// 6. 出力.

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

return 0;

}

[入力例]
1225

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

[入力例]
99999

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

[入力例]
314159265358979323846264338327950288419716939937510

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

[入力例]
2022

[出力例]
2246

[入力例]
20220113

[出力例]
22466791

[入力例]
99999999999999999999999999999999999999999999999999

[出力例]
111111111111111111111111111111111111111111111111060

[入力例]
1414213562373095048801688724209698078569671875376948073176679737990732478462107038850387534327641572

[出力例]
1571348402636772276446320804677442309521857639307720081307421931100813864957896709833763927030712805

[入力例]
9465039690052544287964210336050825544228009679340871984835320413138656028459737281236623910738318475221197599613262364812464866655324755821221092211133037516274251841210630051432736133150976832522422811910498103749718745467191658641434790862939619763285208867362914075814532379135342728574115700744736237670180291229335790961022435254588241322299644479124403665543873560838123902436045250773389704122393280276096137717904710238337845435209435565053211109596812055736852625864819104366036314395508017917284938196552386978929495097296123356714573475388624043832849619380113505044143557656041303934449636641560423687119165574111093463814413079614034373343396851681468981704840409761380396202541959237702953945058736591307184716535752522570421388219253081124048134322102930668723327553258017981593648669365309578446323005570228846649186185670506105605174070813173766429797749090127411781445934740635316646127229912315074634805283767052428230698613659200015308575040330926336887197767402712076391971685069

[出力例]
10516710766725049208849122595612028382475566310378746649817022681265173364955263645818471011931464972467997332903624849791627629617027506468023435790147819462526946490234033390480817925723307591691580902122775670833020828296879620712705323181044021959205787630403237862016147087928158587304573000827484708522422545810373101067802705838431379246999604976804892961715415067597915447151161389748210782358214755862329041908783011375930939372454928405614679010663124506374280695405354560406707015995008908796983264662835985532143883441440137063016192750431804493147610688200126116715715064062268115482721818490622692985687961749012326070904903421793371525937107612979409979672044899734867106891713288041892171050065262879230205240595280580633801542465836756804497927024558811854137030614731131090659609632628121753829247783966920940721317984078340117339082300903526407144219721211252679757162149711817018495696922124794527372005870852280475811887348510222239231750044812140374319108630447457862657746316268

[入力例]

1225

[出力例]

1360

※AtCoderテストケースより

[入力例]

99999

[出力例]

111105

※AtCoderテストケースより

[入力例]

314159265358979323846264338327950288419716939937510

[出力例]

349065850398865915384738153697722542688574377708317

※AtCoderテストケースより

[入力例]

2022

[出力例]

2246

[入力例]

20220113

[出力例]

22466791

[入力例]

99999999999999999999999999999999999999999999999999

[出力例]

111111111111111111111111111111111111111111111111060

[入力例]

1414213562373095048801688724209698078569671875376948073176679737990732478462107038850387534327641572

[出力例]

1571348402636772276446320804677442309521857639307720081307421931100813864957896709833763927030712805

[入力例]

9465039690052544287964210336050825544228009679340871984835320413138656028459737281236623910738318475221197599613262364812464866655324755821221092211133037516274251841210630051432736133150976832522422811910498103749718745467191658641434790862939619763285208867362914075814532379135342728574115700744736237670180291229335790961022435254588241322299644479124403665543873560838123902436045250773389704122393280276096137717904710238337845435209435565053211109596812055736852625864819104366036314395508017917284938196552386978929495097296123356714573475388624043832849619380113505044143557656041303934449636641560423687119165574111093463814413079614034373343396851681468981704840409761380396202541959237702953945058736591307184716535752522570421388219253081124048134322102930668723327553258017981593648669365309578446323005570228846649186185670506105605174070813173766429797749090127411781445934740635316646127229912315074634805283767052428230698613659200015308575040330926336887197767402712076391971685069

[出力例]

10516710766725049208849122595612028382475566310378746649817022681265173364955263645818471011931464972467997332903624849791627629617027506468023435790147819462526946490234033390480817925723307591691580902122775670833020828296879620712705323181044021959205787630403237862016147087928158587304573000827484708522422545810373101067802705838431379246999604976804892961715415067597915447151161389748210782358214755862329041908783011375930939372454928405614679010663124506374280695405354560406707015995008908796983264662835985532143883441440137063016192750431804493147610688200126116715715064062268115482721818490622692985687961749012326070904903421793371525937107612979409979672044899734867106891713288041892171050065262879230205240595280580633801542465836756804497927024558811854137030614731131090659609632628121753829247783966920940721317984078340117339082300903526407144219721211252679757162149711817018495696922124794527372005870852280475811887348510222239231750044812140374319108630447457862657746316268

■参照サイト
AtCoder Beginner Contest 233

2022年1月12日

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

C++の練習を兼ねて, AtCoder Beginner Contest 233 の問題C (Product) ～問題D (Count Interval) を解いてみた.

■感想.
1. 問題Dは, 連想配列による実装を試みたが, AC版に届かなかったので, 解説を参考の上, 修正版にて, AC版に到達できた.
2. 問題Cで, 深さ優先探索の訓練を積めたので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vl = vector<LL>;
using vvl = vector<vl>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back

int main(){
    
    // 1. 入力情報.
    int N;
    LL X;
    scanf("%d %lld", &N, &X);
    vvl bags;
    rep(i, N){
        int L;
        scanf("%d", &L);
        vl bag;
        rep(j, L){
            LL a;
            scanf("%lld", &a);
            bag.pb(a);
        }
        bags.pb(bag);
    }
    
    // 2. dfs.
    // https://ja.wikipedia.org/wiki/深さ優先探索
    auto dfs = [&](auto&& self, LL cX, int cDepth) -> int{
        // 2-1. 終了条件.
        if(cDepth == N) return (cX == 1);
        
        // 2-2. ボールの取り出し方を数える.
        int ret = 0;
        rep(i, bags[cDepth].size()){
            if(cX % bags[cDepth][i] == 0){
                LL nX = cX / bags[cDepth][i];
                ret += self(self, nX, cDepth + 1);
            }
        }
        
        // 2-3. 返却.
        return ret;
    };
    
    // 3. 出力.
    printf("%d\n", dfs(dfs, X, 0));
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vl = vector<LL>;

using vvl = vector<vl>;

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

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

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

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

#define pb push_back

int main(){

// 1. 入力情報.

int N;

LL X;

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

vvl bags;

rep(i, N){

int L;

scanf("%d", &L);

vl bag;

rep(j, L){

LL a;

scanf("%lld", &a);

bag.pb(a);

}

bags.pb(bag);

}

// 2. dfs.

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

auto dfs = [&](auto&& self, LL cX, int cDepth) -> int{

// 2-1. 終了条件.

if(cDepth == N) return (cX == 1);

// 2-2. ボールの取り出し方を数える.

int ret = 0;

rep(i, bags[cDepth].size()){

if(cX % bags[cDepth][i] == 0){

LL nX = cX / bags[cDepth][i];

ret += self(self, nX, cDepth + 1);

}

// 2-3. 返却.

return ret;

};

// 3. 出力.

printf("%d\n", dfs(dfs, X, 0));

return 0;

}

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

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

[入力例]
3 200
3 10 10 10
3 10 10 10
5 2 2 2 2 2

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

[入力例]
3 1000000000000000000
2 1000000000 1000000000
2 1000000000 1000000000
2 1000000000 1000000000

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

[入力例]
5 2020
5 2 5 10 20 40
11 1 2 4 5 10 15 20 40 50 101 202
3 1 10 202
8 1 2 2 5 8 10 10 20
12 1 1 2 2 5 5 7 10 12 20 101 202

[出力例]
73

[入力例]
7 20220112
5 1 2 4 8 16
3 1 2 4
2 1 877
3 1 8 131
5 1 2 4 8 16
3 1 1 11
7 1 2 4 11 16 131 877

[出力例]
79

[入力例]

2 40

3 1 8 4

2 10 5

[出力例]

※AtCoderテストケースより

[入力例]

3 200

3 10 10 10

5 2 2 2 2 2

[出力例]

※AtCoderテストケースより

[入力例]

3 1000000000000000000

2 1000000000 1000000000

[出力例]

※AtCoderテストケースより

[入力例]

5 2020

5 2 5 10 20 40

11 1 2 4 5 10 15 20 40 50 101 202

3 1 10 202

8 1 2 2 5 8 10 10 20

12 1 1 2 2 5 5 7 10 12 20 101 202

[出力例]

[入力例]

7 20220112

5 1 2 4 8 16

3 1 2 4

2 1 877

3 1 8 131

5 1 2 4 8 16

3 1 1 11

7 1 2 4 11 16 131 877

[出力例]

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

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

int main(){
    
    // 1. 入力情報.
    int N;
    LL K;
    scanf("%d %lld", &N, &K);
    rep(i, N) scanf("%lld", &a[i]);
    
    // 2. 累積和.
    rep(i, N) aCum[i + 1] = aCum[i] + a[i];
    
    // 3. 数え上げ(解説通り).
    LL ans = 0;
    map<LL, LL> m;
    repx(r, 1, N + 1){
        m[aCum[r - 1]]++;
        ans += m[aCum[r] - K];
    }
    
    // 4. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc233/editorial/3163

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

LL a[202020], aCum[202020];

int main(){

// 1. 入力情報.

int N;

LL K;

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

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

// 2. 累積和.

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

// 3. 数え上げ(解説通り).

LL ans = 0;

map<LL, LL> m;

repx(r, 1, N + 1){

m[aCum[r - 1]]++;

ans += m[aCum[r] - K];

}

// 4. 出力.

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

return 0;

}

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

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

[入力例]
2 -1000000000000000
1000000000 -1000000000

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

[入力例]
12 7
0 1 -9 5 10 7 -3 2 3 -6 -11 12

[出力例]
4

[入力例]
20 15
12 -21 10 14 -4 5 11 29 -6 7 -16 -10 0 14 11 -20 24 -10 1 26

[出力例]
8

[入力例]
50 123
84 3 -89 16 62 47 14 62 61 -32 24 70 29 30 -6 99 23 1 2 -18 21 90 -7 40 35 52 -4 89 -14 74 63 8 62 -84 8 109 -84 97 0 4 22 67 23 11 71 2 3 5 55 68

[出力例]
17

[入力例]

6 5

8 -3 5 7 0 -4

[出力例]

※AtCoderテストケースより

[入力例]

2 -1000000000000000

1000000000 -1000000000

[出力例]

※AtCoderテストケースより

[入力例]

12 7

0 1 -9 5 10 7 -3 2 3 -6 -11 12

[出力例]

[入力例]

20 15

12 -21 10 14 -4 5 11 29 -6 7 -16 -10 0 14 11 -20 24 -10 1 26

[出力例]

[入力例]

50 123

84 3 -89 16 62 47 14 62 61 -32 24 70 29 30 -6 99 23 1 2 -18 21 90 -7 40 35 52 -4 89 -14 74 63 8 62 -84 8 109 -84 97 0 4 22 67 23 11 71 2 3 5 55 68

[出力例]

■参照サイト
AtCoder Beginner Contest 233

2022年1月11日

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

C++の練習を兼ねて, 第九回アルゴリズム実技検定の問題L (嘘つきな生徒たち) を解いてみた.

■感想.
1. 問題Lは, LISを使う方針で実装してみたものの, ACに到達できず, 解説を参考に, 修正版にて, AC版に到達できた.
2. LIS(Longest increase subsequence) の応用版(広義単調増加列プラス追加条件) を, 確認することができたので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

本家のサイト第九回アルゴリズム実技検定の各リンクをご覧下さい.

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

// 解き直し.
// https://atcoder.jp/contests/past202112-open/editorial/3070
// -> hand_01.txt などで, WA版となったため, 解き直しとした.
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
#define all(x) x.begin(), x.end()
int a[202020], b[202020];

int main(){
    
    // 1. 入力情報.
    int N, P;
    scanf("%d %d", &N, &P);
    rep(i, N) scanf("%d", &a[i]);
    
    // 2. 数列 B.
    rep(i, N) b[i] =  a[N - 1 - i] - i;
    
    // 3. "広義"単調増加な数列の長さの最大値は？
    // 以下の問題を参照, 改変.
    // https://atcoder.jp/contests/typical90/tasks/typical90_bh
    // -> LIS(Longest increase subsequence) を 利用.
    vi dp;
    rep(i, N){
        // 値が 0 以上 P - (N - 1)以下でない項は, 変更が必要(解説より).
        // 本問では, LIS の 計算過程で, 別途, 下記条件が, 必要なので注意.
        if(b[i] < 0 || b[i] > P - (N - 1)) continue;
        
        // それ以外.
        if(dp.size() == 0 || dp.back() <= b[i]){
            dp.pb(b[i]);
        }else{
            int at = upper_bound(all(dp), b[i]) - dp.begin();
            dp[at] = b[i];
        }
    }
    // rep(i, dp.size()) printf("%d\n", dp[i]);
    
    // 4. 出力.
    printf("%d\n", N - dp.size());
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/past202112-open/editorial/3070

// -> hand_01.txt などで, WA版となったため, 解き直しとした.

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

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

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

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

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

#define pb push_back

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

int a[202020], b[202020];

int main(){

// 1. 入力情報.

int N, P;

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

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

// 2. 数列 B.

rep(i, N) b[i] = a[N - 1 - i] - i;

// 3. "広義"単調増加な数列の長さの最大値は？

// 以下の問題を参照, 改変.

// https://atcoder.jp/contests/typical90/tasks/typical90_bh

// -> LIS(Longest increase subsequence) を利用.

vi dp;

rep(i, N){

// 値が 0 以上 P - (N - 1)以下でない項は, 変更が必要(解説より).

// 本問では, LIS の計算過程で, 別途, 下記条件が, 必要なので注意.

if(b[i] < 0 || b[i] > P - (N - 1)) continue;

// それ以外.

if(dp.size() == 0 || dp.back() <= b[i]){

dp.pb(b[i]);

}else{

int at = upper_bound(all(dp), b[i]) - dp.begin();

dp[at] = b[i];

}

// rep(i, dp.size()) printf("%d\n", dp[i]);

// 4. 出力.

printf("%d\n", N - dp.size());

return 0;

}

[入力例]
5 10
7 5 10 3 2

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

[入力例]
5 10
9 8 7 7 5

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

[入力例]
11 1000000000
0 1 10 100 1000 10000 100000 1000000 10000000 100000000 1000000000

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

[入力例]
3 2
2 1 0

[出力例]
0

[入力例]
15 33
25 16 14 13 12 19 7 22 6 32 5 15 2 21 1

[出力例]
8

[入力例]
31 41
5 9 26 5 35 8 9 7 9 32 38 4 6 26 4 33 8 32 7 9 5 0 2 8 8 41 9 7 16 9 3

[出力例]
26

[入力例]
200 2020
1854 2020 1753 2019 1674 944 2017 1290 1123 2015 1392 1559 1569 2013 1017 1214 1258 2001 2000 1689 1561 1999 1667 1372 1998 1086 1140 1888 1255 1359 1850 1522 1223 1833 1645 1831 982 1799 1409 1219 1759 1357 1730 1024 1217 1700 1351 1699 1487 949 1659 1435 1650 1030 1606 1457 736 1580 809 1110 1560 866 1297 1550 950 971 1400 1185 1310 617 1221 1300 1053 1222 1158 1212 848 1200 610 1111 1100 1020 999 674 987 1017 980 608 774 970 853 1077 966 809 935 955 834 850 943 815 603 767 942 584 513 446 941 417 737 858 910 694 456 901 888 800 869 836 783 454 449 442 490 330 393 616 681 619 364 530 341 680 424 381 522 559 309 325 613 620 512 249 444 228 305 505 384 500 237 489 247 423 468 273 455 396 337 485 430 258 400 150 264 103 333 312 172 300 127 297 285 142 256 166 221 222 221 192 270 189 98 167 32 71 135 54 67 66 122 13 41 111 61 58 77 70 25 12 5 0

[出力例]
130

[入力例]
500 5050
5050 5049 5048 5047 5046 5045 5044 5043 5042 5041 4287 4147 3021 4341 1671 2034 4202 1787 1077 1787 5000 4999 4998 4997 4996 4995 4994 4993 4992 4991 2827 4990 4568 3815 4498 2679 1798 3529 1287 1122 4800 4799 4798 4797 4796 4795 4794 4793 4792 3992 3234 2468 1333 2364 4020 4376 4988 1832 3445 3052 4000 3999 3998 3997 3996 3995 3994 3993 3992 3991 1989 3990 1433 1400 1567 2967 4297 2893 3909 3770 3500 3499 3498 3497 3496 3495 3494 3493 3492 3491 2838 1761 1776 1125 2719 3355 1066 2470 3685 1125 3300 3299 3298 3297 3296 3295 3294 3293 3292 3291 3280 2207 3250 3232 2660 2604 2525 2021 3648 3000 2999 2998 2997 2996 2995 2994 2993 2992 2991 1983 1350 3797 1280 2643 2593 1177 1298 1411 2616 2500 2499 2498 2497 2496 2495 2494 2493 2492 2491 1918 1376 2689 3665 1218 3212 1481 3695 1034 2575 2300 2299 2298 2297 2296 2295 2294 2293 2292 2291 1650 1931 1012 1263 1756 1828 1327 1131 1373 1537 2000 1999 1998 1997 1996 1995 1994 1993 1992 1991 1468 1212 1143 1178 1486 1493 1599 1470 1497 1057 1900 1899 1898 1897 1896 1895 1894 1893 1892 1891 1926 1848 1043 1764 1028 1292 1451 1198 1844 1664 1700 1699 1698 1697 1696 1695 1694 1693 1692 1691 881 1328 547 646 1324 1118 1422 947 1374 1466 1500 1499 1498 1497 1496 1495 1494 1493 1492 1491 733 872 1111 1211 562 1022 653 726 806 1455 1300 1299 1298 1297 1296 1295 1294 1293 1292 1291 730 1498 695 1469 1177 1364 1065 1372 731 580 1200 1199 1198 1197 1196 1195 1194 1193 1192 1191 1190 1189 1188 1187 1186 1185 1184 1183 1182 1181 1180 1179 808 1242 1036 1147 1174 797 1255 1222 1147 708 1225 1433 1384 500 1313 1200 1003 1002 1001 1000 999 998 997 996 995 994 993 992 991 990 989 988 987 986 985 984 983 982 981 980 979 978 977 976 975 974 973 972 971 824 858 881 858 846 887 825 824 857 820 878 838 829 888 838 840 856 827 831 800 799 798 797 796 795 794 793 792 791 790 789 788 787 786 785 784 783 782 781 780 779 778 777 776 775 774 773 772 771 746 769 703 790 738 729 757 782 701 776 777 734 753 787 786 791 797 783 741 765 700 725 709 708 741 780 761 709 799 714 600 599 598 597 596 595 594 593 592 591 590 589 588 587 586 585 584 583 582 581 580 555 500 548 571 563 566 506 599 550 506 502 570 588 510 594 507 555 537 511 300 299 298 297 296 295 294 293 292 291 238 225 207 288 254 287 212 226 214 226 200 190 180 150 140 100 90 50 30 20 1

[出力例]
200

[入力例]

5 10

7 5 10 3 2

[出力例]

※AtCoderのテストケースより

[入力例]

5 10

9 8 7 7 5

[出力例]

※AtCoderのテストケースより

[入力例]

11 1000000000

0 1 10 100 1000 10000 100000 1000000 10000000 100000000 1000000000

[出力例]

※AtCoderのテストケースより

[入力例]

3 2

2 1 0

[出力例]

[入力例]

15 33

25 16 14 13 12 19 7 22 6 32 5 15 2 21 1

[出力例]

[入力例]

31 41

5 9 26 5 35 8 9 7 9 32 38 4 6 26 4 33 8 32 7 9 5 0 2 8 8 41 9 7 16 9 3

[出力例]

[入力例]

200 2020

1854 2020 1753 2019 1674 944 2017 1290 1123 2015 1392 1559 1569 2013 1017 1214 1258 2001 2000 1689 1561 1999 1667 1372 1998 1086 1140 1888 1255 1359 1850 1522 1223 1833 1645 1831 982 1799 1409 1219 1759 1357 1730 1024 1217 1700 1351 1699 1487 949 1659 1435 1650 1030 1606 1457 736 1580 809 1110 1560 866 1297 1550 950 971 1400 1185 1310 617 1221 1300 1053 1222 1158 1212 848 1200 610 1111 1100 1020 999 674 987 1017 980 608 774 970 853 1077 966 809 935 955 834 850 943 815 603 767 942 584 513 446 941 417 737 858 910 694 456 901 888 800 869 836 783 454 449 442 490 330 393 616 681 619 364 530 341 680 424 381 522 559 309 325 613 620 512 249 444 228 305 505 384 500 237 489 247 423 468 273 455 396 337 485 430 258 400 150 264 103 333 312 172 300 127 297 285 142 256 166 221 222 221 192 270 189 98 167 32 71 135 54 67 66 122 13 41 111 61 58 77 70 25 12 5 0

[出力例]

130

[入力例]

500 5050

5050 5049 5048 5047 5046 5045 5044 5043 5042 5041 4287 4147 3021 4341 1671 2034 4202 1787 1077 1787 5000 4999 4998 4997 4996 4995 4994 4993 4992 4991 2827 4990 4568 3815 4498 2679 1798 3529 1287 1122 4800 4799 4798 4797 4796 4795 4794 4793 4792 3992 3234 2468 1333 2364 4020 4376 4988 1832 3445 3052 4000 3999 3998 3997 3996 3995 3994 3993 3992 3991 1989 3990 1433 1400 1567 2967 4297 2893 3909 3770 3500 3499 3498 3497 3496 3495 3494 3493 3492 3491 2838 1761 1776 1125 2719 3355 1066 2470 3685 1125 3300 3299 3298 3297 3296 3295 3294 3293 3292 3291 3280 2207 3250 3232 2660 2604 2525 2021 3648 3000 2999 2998 2997 2996 2995 2994 2993 2992 2991 1983 1350 3797 1280 2643 2593 1177 1298 1411 2616 2500 2499 2498 2497 2496 2495 2494 2493 2492 2491 1918 1376 2689 3665 1218 3212 1481 3695 1034 2575 2300 2299 2298 2297 2296 2295 2294 2293 2292 2291 1650 1931 1012 1263 1756 1828 1327 1131 1373 1537 2000 1999 1998 1997 1996 1995 1994 1993 1992 1991 1468 1212 1143 1178 1486 1493 1599 1470 1497 1057 1900 1899 1898 1897 1896 1895 1894 1893 1892 1891 1926 1848 1043 1764 1028 1292 1451 1198 1844 1664 1700 1699 1698 1697 1696 1695 1694 1693 1692 1691 881 1328 547 646 1324 1118 1422 947 1374 1466 1500 1499 1498 1497 1496 1495 1494 1493 1492 1491 733 872 1111 1211 562 1022 653 726 806 1455 1300 1299 1298 1297 1296 1295 1294 1293 1292 1291 730 1498 695 1469 1177 1364 1065 1372 731 580 1200 1199 1198 1197 1196 1195 1194 1193 1192 1191 1190 1189 1188 1187 1186 1185 1184 1183 1182 1181 1180 1179 808 1242 1036 1147 1174 797 1255 1222 1147 708 1225 1433 1384 500 1313 1200 1003 1002 1001 1000 999 998 997 996 995 994 993 992 991 990 989 988 987 986 985 984 983 982 981 980 979 978 977 976 975 974 973 972 971 824 858 881 858 846 887 825 824 857 820 878 838 829 888 838 840 856 827 831 800 799 798 797 796 795 794 793 792 791 790 789 788 787 786 785 784 783 782 781 780 779 778 777 776 775 774 773 772 771 746 769 703 790 738 729 757 782 701 776 777 734 753 787 786 791 797 783 741 765 700 725 709 708 741 780 761 709 799 714 600 599 598 597 596 595 594 593 592 591 590 589 588 587 586 585 584 583 582 581 580 555 500 548 571 563 566 506 599 550 506 502 570 588 510 594 507 555 537 511 300 299 298 297 296 295 294 293 292 291 238 225 207 288 254 287 212 226 214 226 200 190 180 150 140 100 90 50 30 20 1

[出力例]

200

■参照サイト
第九回アルゴリズム実技検定

2022年1月10日2022年1月10日

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

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

■感想.
1. 問題Eは, 規則性を見つけることが出来たので, AC版に到達できたと思う.
2. 等差数を, 抽出してところ, 意外と少なく(ここでは, 339個だった), 非常に面白い問題と感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 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. 入力情報.
    LL X;
    scanf("%lld", &X);
    
    // 2. 等差数作成.
    vl aNumber;
    rep(i, 9) aNumber.pb(i + 1);
    repx(k, 2, 19){
        // 等差数が, k桁だったと仮定.
        // -> 初項 s, 公差 t で, k項 の 等差数列 が 存在するか？
        repx(s, 1, 10){
            repx(t, -9, 10){
                // 初項.
                string seq;
                seq.pb(s + '0');
                
                // 残りの項.
                int d = s;
                bool ok = true;
                rep(i, k - 1){
                    d += t;
                    if(d < 0 || d > 9){
                        ok = false;
                        break;
                    }
                    seq.pb(d + '0');
                }
                
                // 保存.
                if(ok) aNumber.pb(stoll(seq));
            }
        }
    }
    // for(auto &p : aNumber) printf("%lld\n", p);
    
    // 3. sort.
    sort(all(aNumber));
    
    // 4. 位置検索.
    int at = lower_bound(all(aNumber), X) - aNumber.begin();
    
    // 5. 出力.
    printf("%lld\n", aNumber[at]);
    return 0;
    
}

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

LL X;

scanf("%lld", &X);

// 2. 等差数作成.

vl aNumber;

rep(i, 9) aNumber.pb(i + 1);

repx(k, 2, 19){

// 等差数が, k桁だったと仮定.

// -> 初項 s, 公差 t で, k項の等差数列が存在するか？

repx(s, 1, 10){

repx(t, -9, 10){

// 初項.

string seq;

seq.pb(s + '0');

// 残りの項.

int d = s;

bool ok = true;

rep(i, k - 1){

d += t;

if(d < 0 || d > 9){

ok = false;

break;

}

seq.pb(d + '0');

}

// 保存.

if(ok) aNumber.pb(stoll(seq));

}

// for(auto &p : aNumber) printf("%lld\n", p);

// 3. sort.

sort(all(aNumber));

// 4. 位置検索.

int at = lower_bound(all(aNumber), X) - aNumber.begin();

// 5. 出力.

printf("%lld\n", aNumber[at]);

return 0;

}

[入力例]
152

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

[入力例]
88

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

[入力例]
8989898989

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

[入力例]
51

[出力例]
51

[入力例]
100

[出力例]
111

[入力例]
112

[出力例]
123

[入力例]
964

[出力例]
975

[入力例]
1248

[出力例]
1357

[入力例]
1234

[出力例]
1234

[入力例]
3141

[出力例]
3210

[入力例]
12321

[出力例]
12345

[入力例]
526718

[出力例]
543210

[入力例]
20220110

[出力例]
22222222

[入力例]
53536007464846939

[出力例]
55555555555555555

[入力例]
100000000000000000

[出力例]
111111111111111111

[入力例]

152

[出力例]

159

※AtCoderテストケースより

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

8989898989

[出力例]

9876543210

※AtCoderテストケースより

[入力例]

[出力例]

[入力例]

100

[出力例]

111

[入力例]

112

[出力例]

123

[入力例]

964

[出力例]

975

[入力例]

1248

[出力例]

1357

[入力例]

1234

[出力例]

1234

[入力例]

3141

[出力例]

3210

[入力例]

12321

[出力例]

12345

[入力例]

526718

[出力例]

543210

[入力例]

20220110

[出力例]

22222222

[入力例]

53536007464846939

[出力例]

55555555555555555

[入力例]

100000000000000000

[出力例]

111111111111111111

■参照サイト
AtCoder Beginner Contest 234

2022年1月10日

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

C++の練習を兼ねて, AtCoder Beginner Contest 234 の問題C (Happy New Year!) ～問題D (Prefix K-th Max) を解いてみた.

■感想.
1. 問題C, Dは, 規則性を見つけることが出来たので, AC版に到達できたと思う.
2. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
#define all(x) x.begin(), x.end()

int main(){
    
    // 1. 入力情報.
    LL K;
    scanf("%lld", &K);
    
    // 2. K番目に小さい正整数.
    auto f = [](LL n) -> string{
        // 返却用.
        string ret;
        
        // K番目に小さい正整数は？
        while(n){
            ret.pb((n % 2) ? '2' : '0');
            n >>= 1;
        }
        
        // 反転.
        reverse(all(ret));
        
        // 返却.
        return ret;
    };
    
    // 3. 出力.
    printf("%s\n", f(K).c_str());
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

#define pb push_back

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

int main(){

// 1. 入力情報.

LL K;

scanf("%lld", &K);

// 2. K番目に小さい正整数.

auto f = [](LL n) -> string{

// 返却用.

string ret;

// K番目に小さい正整数は？

while(n){

ret.pb((n % 2) ? '2' : '0');

n >>= 1;

}

// 反転.

reverse(all(ret));

// 返却.

return ret;

};

// 3. 出力.

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

return 0;

}

[入力例]
3

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

[入力例]
11

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

[入力例]
923423423420220108

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

[入力例]
1

[出力例]
2

[入力例]
2022

[出力例]
22222200220

[入力例]
20220110

[出力例]
2002202002000200022002220

[入力例]
314159265358979323

[出力例]
20002022200000222200020222222220220200222202020000022222022

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

[出力例]

2022

※AtCoderテストケースより

[入力例]

923423423420220108

[出力例]

220022020000202020002022022000002020002222002200002022002200

※AtCoderテストケースより

[入力例]

[出力例]

[入力例]

2022

[出力例]

22222200220

[入力例]

20220110

[出力例]

2002202002000200022002220

[入力例]

314159265358979323

[出力例]

20002022200000222200020222222220220200222202020000022222022

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using PQD = priority_queue<int>;
using PQA = 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--)

int main(){
    
    // 1. 入力情報.
    int N, K;
    scanf("%d %d", &N, &K);
    
    // 2. K番目に大きい値は？
    PQA pqa; // 大きい方から, K番目までの要素.
    PQD pqd; // 残りの要素.
    rep(i, N){
        int p;
        scanf("%d", &p);
        
        // K番目まで.
        if(i < K) pqa.push(p);
        
        // K番目よりも後.
        if(i >= K){
            // 比較対象の要素.
            pqd.push(p);
            int l = pqa.top();
            int r = pqd.top();
            
            // 入れ替え.
            if(l < r){
                pqa.pop();
                pqd.pop();
                pqd.push(l);
                pqa.push(r);
            }
        }
        
        // K番目以降.
        if(i >= K - 1) printf("%d\n", pqa.top());
    }
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using PQD = priority_queue<int>;

using PQA = 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--)

int main(){

// 1. 入力情報.

int N, K;

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

// 2. K番目に大きい値は？

PQA pqa; // 大きい方から, K番目までの要素.

PQD pqd; // 残りの要素.

rep(i, N){

int p;

scanf("%d", &p);

// K番目まで.

if(i < K) pqa.push(p);

// K番目よりも後.

if(i >= K){

// 比較対象の要素.

pqd.push(p);

int l = pqa.top();

int r = pqd.top();

// 入れ替え.

if(l < r){

pqa.pop();

pqd.pop();

pqd.push(l);

pqa.push(r);

}

// K番目以降.

if(i >= K - 1) printf("%d\n", pqa.top());

}

return 0;

}

[入力例]
3 2
1 2 3

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

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

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

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

[出力例]
1
2
3

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

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

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

[出力例]
6
7
8
8
9
10
10
11
12
12
13
13
14
15
15
16

[入力例]

3 2

1 2 3

[出力例]

※AtCoderテストケースより

[入力例]

11 5

3 7 2 5 11 6 1 9 8 10 4

[出力例]

※AtCoderテストケースより

[入力例]

5 3

1 2 3 4 5

[出力例]

[入力例]

10 3

7 3 2 1 9 4 5 6 10 8

[出力例]

[入力例]

20 5

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

[出力例]

■参照サイト
AtCoder Beginner Contest 234

2022年1月9日

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

C++の練習を兼ねて, AtCoder Regular Contest 093 の問題E (Bichrome Spanning Tree) を解いてみた.

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

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

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

// 解き直し.
// https://img.atcoder.jp/arc093/editorial.pdf
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vs = vector<set<int>>;
using T3 = tuple<LL, int, int>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define all(x) x.begin(), x.end()
const LL MOD = 1e9 + 7;
LL w[2020], mPow2[2020];
int u[2020], v[2020];

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

int main(){
    
    // 1. 入力情報.
    int N, M;
    LL X;
    scanf("%d %d %lld", &N, &M, &X);
    map<P, LL> m;
    rep(i, M){
        scanf("%d %d %lld", &u[i], &v[i], &w[i]);
        u[i]--;
        v[i]--;
        m[{u[i], v[i]}] = w[i];
        m[{v[i], u[i]}] = w[i];
    }
    
    // 2. sort.
    vector<T3> t;
    rep(i, M) t.emplace_back(w[i], u[i], v[i]);
    sort(all(t));
    
    // 3. 最小全域木(Kruskal's Algorithm).
    // 競プロ典型 90 問 (049 - Flip Digits 2)
    // https://github.com/E869120/kyopro_educational_90/blob/main/sol/049.cpp
    LL S = 0;
    vs T(N);
    UnionFind uf(N + 2);
    rep(i, t.size()){
        int a = get<1>(t[i]);
        int b = get<2>(t[i]);
        LL c = get<0>(t[i]);
        if(!uf.same(a, b)){
            uf.unite(a, b);
            T[a].insert(b);
            T[b].insert(a);
            S += c;
        }
    }
    
    // 4. D.
    LL D = X - S;
    
    // 5. bfs.
    // https://ja.wikipedia.org/wiki/幅優先探索
    auto bfs = [&](vs &G, int s, int* d){
        // 空のキュー.
        queue<int> q;
        
        // 探索地点 s をキュー q に追加.
        q.push(s);
        while(!q.empty()){
            // キューから取り出す.
            int u = q.front();
            q.pop();
            
            // 隣接頂点をチェック.
            for(auto &e : G[u]) if(!d[e] && e != s) d[e] = d[u] + 1, q.push(e);
        }
    };
    
    // 6. 最短経路上 の 辺の重み の 最大値.
    auto f = [&](vs &G, int g, int* d) -> LL{
        // 返却用.
        LL ret = 0;
        
        // 空のキュー.
        queue<int> q;
        
        // 探索地点 g をキュー q に追加.
        q.push(g);
        while(!q.empty()){
            // キューから取り出す.
            int u = q.front();
            q.pop();
            
            // 隣接頂点をチェック.
            for(auto &e : G[u]){
                if(d[e] == d[u] - 1){
                    // 距離が 1 小さい頂点を追加.
                    q.push(e);
                    
                    // 最短経路を構成する辺とみて, 辺の重みの最大値 を 更新.
                    ret = max(ret, m[{u, e}]);
                }
            }
        }
        
        // 返却.
        return ret;
    };
    
    // 7. D との 比較.
    // -> グラフ G に含まれるが, グラフ T に 含まれない 辺 のみ 計算.
    int eLower = 0, eEqual = 0, eUpper = 0;
    rep(i, M){
        // グラフ T に 含まれる辺か？
        if(T[u[i]].count(v[i])) continue;
        
        // 最短距離.
        int d[1010];
        rep(j, 1010) d[j] = 0;
        bfs(T, u[i], d);
        
        // グラフ T 上で, pathMax 計算.
        LL pathMax = f(T, v[i], d);
        
        // diff の 値 に応じて, カウント.
        LL diff = w[i] - pathMax;
        if(diff < D)  eLower++;
        if(diff == D) eEqual++;
        if(diff > D)  eUpper++;
    }
    
    // 8. 2 の 冪乗.
    mPow2[0] = 1;
    repx(i, 1, 2020){
        mPow2[i] = mPow2[i - 1] << 1;
        mPow2[i] %= MOD;
    }
    
    // 9. 塗り方の個数.
    LL ans = 1;
    
    // 9-1. D < 0.
    if(D < 0) ans = 0;
    
    // 9-2. D == 0.
    if(D == 0){
        // T の 辺 に 2種類の色 を 両方用いる場合.
        LL t1 = 1;
        t1 *= (mPow2[N - 1] - 2);
        t1 %= MOD;
        t1 *= mPow2[M - N + 1];
        t1 %= MOD;
        
        // それ以外.
        LL t2 = 1;
        t2 *= 2;
        t2 %= MOD;
        t2 *= (mPow2[eEqual] - 1);
        t2 %= MOD;
        t2 *= mPow2[eUpper];
        t2 %= MOD;
        
        // 合計.
        ans = t1 + t2;
        ans %= MOD;
    }
    
    // 9-3. D > 0.
    if(D > 0){
        ans *= 2;
        ans %= MOD;
        ans *= (mPow2[eEqual] - 1);
        ans %= MOD;
        ans *= mPow2[eUpper];
        ans %= MOD;
    }
    
    // 10. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using P = pair<int, int>;

using vi = vector<int>;

using vs = vector<set<int>>;

using T3 = tuple<LL, int, int>;

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

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

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

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

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

const LL MOD = 1e9 + 7;

LL w[2020], mPow2[2020];

int u[2020], v[2020];

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

// UnionFind

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

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

// -> 一部改変.

struct UnionFind{

vi d;

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

int find(int x){

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

}

bool unite(int x, int y){

x = find(x);

y = find(y);

if(x == y) return false;

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

d[x] += d[y];

d[y] = x;

return true;

}

bool same(int x, int y){

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

}

int size(int x){

return -d[find(x)];

}

};

int main(){

// 1. 入力情報.

int N, M;

LL X;

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

map<P, LL> m;

rep(i, M){

scanf("%d %d %lld", &u[i], &v[i], &w[i]);

u[i]--;

v[i]--;

m[{u[i], v[i]}] = w[i];

m[{v[i], u[i]}] = w[i];

}

// 2. sort.

vector<T3> t;

rep(i, M) t.emplace_back(w[i], u[i], v[i]);

sort(all(t));

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

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

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

LL S = 0;

vs T(N);

UnionFind uf(N + 2);

rep(i, t.size()){

int a = get<1>(t[i]);

int b = get<2>(t[i]);

LL c = get<0>(t[i]);

if(!uf.same(a, b)){

uf.unite(a, b);

T[a].insert(b);

T[b].insert(a);

S += c;

}

// 4. D.

LL D = X - S;

// 5. bfs.

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

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

// 空のキュー.

queue<int> q;

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

q.push(s);

while(!q.empty()){

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

int u = q.front();

q.pop();

// 隣接頂点をチェック.

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

}

};

// 6. 最短経路上の辺の重みの最大値.

auto f = [&](vs &G, int g, int* d) -> LL{

// 返却用.

LL ret = 0;

// 空のキュー.

queue<int> q;

// 探索地点 g をキュー q に追加.

q.push(g);

while(!q.empty()){

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

int u = q.front();

q.pop();

// 隣接頂点をチェック.

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

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

// 距離が 1 小さい頂点を追加.

q.push(e);

// 最短経路を構成する辺とみて, 辺の重みの最大値を更新.

ret = max(ret, m[{u, e}]);

}

// 返却.

return ret;

};

// 7. D との比較.

// -> グラフ G に含まれるが, グラフ T に含まれない辺のみ計算.

int eLower = 0, eEqual = 0, eUpper = 0;

rep(i, M){

// グラフ T に含まれる辺か？

if(T[u[i]].count(v[i])) continue;

// 最短距離.

int d[1010];

rep(j, 1010) d[j] = 0;

bfs(T, u[i], d);

// グラフ T 上で, pathMax 計算.

LL pathMax = f(T, v[i], d);

// diff の値に応じて, カウント.

LL diff = w[i] - pathMax;

if(diff < D) eLower++;

if(diff == D) eEqual++;

if(diff > D) eUpper++;

}

// 8. 2 の冪乗.

mPow2[0] = 1;

repx(i, 1, 2020){

mPow2[i] = mPow2[i - 1] << 1;

mPow2[i] %= MOD;

}

// 9. 塗り方の個数.

LL ans = 1;

// 9-1. D < 0.

if(D < 0) ans = 0;

// 9-2. D == 0.

if(D == 0){

// T の辺に 2種類の色を両方用いる場合.

LL t1 = 1;

t1 *= (mPow2[N - 1] - 2);

t1 %= MOD;

t1 *= mPow2[M - N + 1];

t1 %= MOD;

// それ以外.

LL t2 = 1;

t2 *= 2;

t2 %= MOD;

t2 *= (mPow2[eEqual] - 1);

t2 %= MOD;

t2 *= mPow2[eUpper];

t2 %= MOD;

// 合計.

ans = t1 + t2;

ans %= MOD;

}

// 9-3. D > 0.

if(D > 0){

ans *= 2;

ans %= MOD;

ans *= (mPow2[eEqual] - 1);

ans %= MOD;

ans *= mPow2[eUpper];

ans %= MOD;

}

// 10. 出力.

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

return 0;

}

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

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

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

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

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

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

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

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

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

[出力例]
8

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

[出力例]
56

[入力例]

3 3

1 2 1

2 3 1

3 1 1

[出力例]

※AtCoderテストケースより

[入力例]

3 3

1 2 1

2 3 1

3 1 2

[出力例]

※AtCoderテストケースより

[入力例]

5 4

1 2 3

1 3 3

2 4 6

2 5 8

[出力例]

※AtCoderテストケースより

[入力例]

8 10

4 6 10

8 4 11

5 8 9

1 8 10

3 8 128773450

7 8 10

4 2 4

3 4 1

3 1 13

5 2 2

[出力例]

※AtCoderテストケースより

[入力例]

7 9

1 2 2

2 3 3

1 7 3

4 1 4

7 4 5

3 4 2

6 3 3

6 5 6

5 4 1

[出力例]

[入力例]

15 22

1 3 5

3 2 11

4 3 8

1 4 6

1 5 2

5 4 9

5 10 7

10 9 8

9 8 11

8 7 5

7 4 1

4 6 7

2 6 15

15 6 7

15 12 10

6 7 3

7 12 8

12 13 3

12 11 2

13 14 4

11 14 1

11 8 6

[出力例]

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

2022年1月8日

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

C++の練習を兼ねて, 第九回アルゴリズム実技検定の問題K (ガソリンスタンド) を解いてみた.

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

本家のサイト第九回アルゴリズム実技検定の各リンクをご覧下さい.

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
#define a first
#define b second

int main(){
    
    // 1. 入力情報.
    int N, M, Q, K;
    scanf("%d %d %d %d", &N, &M, &Q, &K);
    vi gasStation;
    map<int, int> m;
    rep(i, K){
        int a;
        scanf("%d", &a);
        a--;
        gasStation.pb(a);
        m[a] = 1;
    }
    vvi G(N);
    rep(i, M){
        int u, v;
        scanf("%d %d", &u, &v);
        u--;
        v--;
        G[u].pb(v);
        G[v].pb(u);
    }
    
    // 2. ガソリンスタンドの番号付け.
    int idx = -1;
    for(auto &p : m) p.b = ++idx;
    
    // 3. bfs.
    // https://ja.wikipedia.org/wiki/幅優先探索
    auto bfs = [&](vvi &G, int s, vvi &d){
        // 空のキュー.
        queue<int> q;
        
        // 探索地点 s をキュー q に追加.
        q.push(s);
        while(!q.empty()){
            // キューから取り出す.
            int u = q.front();
            q.pop();
            
            // 取り出した要素を処理.
            for(auto &e : G[u]) if(!d[m[s]][e] && e != s) d[m[s]][e] = d[m[s]][u] + 1, q.push(e);
        }
    };
    
    // 4. 各ガソリンスタンドから, 各街までの最短距離.
    vvi d(K, vi(N));
    for(auto &p : gasStation) bfs(G, p, d);
    
    // 5. クエリ回答.
    rep(i, Q){
        // クエリ情報.
        int s, t;
        scanf("%d %d", &s, &t);
        s--, t--;
        
        // 道を通る回数の最小値.
        int ans = 2020202020;
        for(auto &p : gasStation) ans = min(ans, d[m[p]][s] + d[m[p]][t]);
        
        // 出力.
        printf("%d\n", ans);
    }
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

using vvi = vector<vi>;

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

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

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

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

#define pb push_back

#define a first

#define b second

int main(){

// 1. 入力情報.

int N, M, Q, K;

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

vi gasStation;

map<int, int> m;

rep(i, K){

int a;

scanf("%d", &a);

a--;

gasStation.pb(a);

m[a] = 1;

}

vvi G(N);

rep(i, M){

int u, v;

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

u--;

v--;

G[u].pb(v);

G[v].pb(u);

}

// 2. ガソリンスタンドの番号付け.

int idx = -1;

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

// 3. bfs.

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

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

// 空のキュー.

queue<int> q;

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

q.push(s);

while(!q.empty()){

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

int u = q.front();

q.pop();

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

for(auto &e : G[u]) if(!d[m[s]][e] && e != s) d[m[s]][e] = d[m[s]][u] + 1, q.push(e);

}

};

// 4. 各ガソリンスタンドから, 各街までの最短距離.

vvi d(K, vi(N));

for(auto &p : gasStation) bfs(G, p, d);

// 5. クエリ回答.

rep(i, Q){

// クエリ情報.

int s, t;

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

s--, t--;

// 道を通る回数の最小値.

int ans = 2020202020;

for(auto &p : gasStation) ans = min(ans, d[m[p]][s] + d[m[p]][t]);

// 出力.

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

}

return 0;

}

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

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

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

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

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

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

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

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

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

[入力例]

3 2 1 1

1 2

2 3

3 2

[出力例]

※AtCoderテストケースより

[入力例]

5 6 2 2

3 1

1 2

2 3

2 4

1 5

2 5

3 5

5 5

5 4

[出力例]

※AtCoderテストケースより

[入力例]

12 15 7 3

9 3 11

1 2

1 3

2 4

2 5

3 5

5 6

5 11

6 8

6 7

7 8

7 9

8 10

8 12

9 10

11 12

1 2

5 4

1 6

1 10

5 8

5 6

2 7

[出力例]

[入力例]

20 28 10 5

7 3 15 16 17

1 2

1 3

2 5

2 6

2 7

3 4

3 5

4 9

5 8

6 11

7 12

8 9

8 10

8 11

8 13

9 10

11 12

11 13

11 14

13 15

13 17

13 18

14 16

15 16

17 19

17 20

18 19

19 20

1 5

1 12

1 10

1 14

8 14

2 20

4 19

10 11

10 14

10 18

[出力例]

■参照サイト
第九回アルゴリズム実技検定

2022年1月8日2022年1月8日

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

C++の練習を兼ねて, AtCoder Beginner Contest 116 の問題D (Various Sushi) を解いてみた.

■感想.
1. 問題Dは, 方針が見えなかったので, 解説を参考に, AC版に到達できた.
2. 個人的には, 優先順位付きキューを活用することで, 解説のロジックが, 実装できることに, 非常に面白く感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

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

int main(){
    
    // 1. 入力情報.
    int N, K, t, d;
    scanf("%d %d", &N, &K);
    vp v;
    rep(i, N){
        scanf("%d %d", &t, &d);
        v.pb({d, t});
    }
    
    // 2. sort.
    sort(all(v));
    
    // 3. 集合 S.
    LL dSum = 0;
    map<int, int> m;
    PQA sIn;
    repr(i, N - 1, N - K){
        sIn.push({v[i].a, v[i].b});
        m[v[i].b]++;
        dSum += (LL)v[i].a;
    }
    
    // 4. 集合 S 以外.
    PQD sOut;
    rep(i, N - K) sOut.push({v[i].a, v[i].b});
    
    // 5. 寿司の入れ替え.
    LL ans = dSum + (LL)m.size() * (LL)m.size();
    while(!sIn.empty()){
        // 集合 S から, 取り出す.
        P x = sIn.top();
        sIn.pop();
        
        // ネタ の 種類数 が, 減る場合は, Skip.
        if(m[x.b] == 1) continue;
        
        // ネタ の 種類数 が, 変わらない場合は, おいしさ基礎ポイント, ネタの個数 を 更新.
        dSum -= x.a;
        m[x.b]--;
        
        // 集合 S 以外 を見る.
        while(!sOut.empty()){
            // 集合 S 以外 から 取り出す.
            P y = sOut.top();
            sOut.pop();
            
            // 集合 S に 含まれない ネタ を探す.
            if(!m.count(y.b)){
                // おいしさ基礎ポイント, ネタの個数 を 更新.
                dSum += y.a;
                m[y.b]++;
                
                // 満足度更新.
                ans = max(ans, dSum + (LL)m.size() * (LL)m.size());
                
                // 集合 S に 追加.
                sIn.push({y.a, y.b});
                
                // 次へ.
                break;
            }
        }
    }
    
    // 6. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using P = pair<int, int>;

using vp = vector<P>;

using PQD = priority_queue<P>;

using PQA = priority_queue<P, vector<P>, greater<P>>;

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

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

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

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

#define pb push_back

#define a first

#define b second

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

int main(){

// 1. 入力情報.

int N, K, t, d;

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

vp v;

rep(i, N){

scanf("%d %d", &t, &d);

v.pb({d, t});

}

// 2. sort.

sort(all(v));

// 3. 集合 S.

LL dSum = 0;

map<int, int> m;

PQA sIn;

repr(i, N - 1, N - K){

sIn.push({v[i].a, v[i].b});

m[v[i].b]++;

dSum += (LL)v[i].a;

}

// 4. 集合 S 以外.

PQD sOut;

rep(i, N - K) sOut.push({v[i].a, v[i].b});

// 5. 寿司の入れ替え.

LL ans = dSum + (LL)m.size() * (LL)m.size();

while(!sIn.empty()){

// 集合 S から, 取り出す.

P x = sIn.top();

sIn.pop();

// ネタの種類数が, 減る場合は, Skip.

if(m[x.b] == 1) continue;

// ネタの種類数が, 変わらない場合は, おいしさ基礎ポイント, ネタの個数を更新.

dSum -= x.a;

m[x.b]--;

// 集合 S 以外を見る.

while(!sOut.empty()){

// 集合 S 以外から取り出す.

P y = sOut.top();

sOut.pop();

// 集合 S に含まれないネタを探す.

if(!m.count(y.b)){

// おいしさ基礎ポイント, ネタの個数を更新.

dSum += y.a;

m[y.b]++;

// 満足度更新.

ans = max(ans, dSum + (LL)m.size() * (LL)m.size());

// 集合 S に追加.

sIn.push({y.a, y.b});

// 次へ.

break;

}

// 6. 出力.

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

return 0;

}

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

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

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

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

[入力例]
6 5
5 1000000000
2 990000000
3 980000000
6 970000000
6 960000000
4 950000000

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

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

[出力例]
70

[入力例]
20 7
8 764
5 313
10 861
6 544
8 1262
5 182
7 1202
3 130
5 850
3 981
5 590
10 771
6 50
4 1255
3 552
10 631
3 848
6 659
4 1091
6 1089

[出力例]
7777

[入力例]
50 10
11 6619934
5 1624101
12 5451794
3 9857183
5 1985828
11 11345963
2 5757194
3 6881103
9 1920811
14 8507495
14 5235040
10 4128252
15 1491606
11 768521
12 9822790
13 10069095
7 7116817
12 6611197
4 1247639
2 36843
9 10277716
3 19857
2 11561672
15 631937
5 7841766
13 2487890
13 13479705
8 1159151
2 12291992
7 2711313
7 1707463
10 985172
10 9394217
9 1626609
6 8081696
12 10331209
7 11885741
12 12131871
8 4794885
6 11949323
14 43035
10 9376463
3 12689389
12 7496508
3 8502162
14 4333674
10 15789860
6 9809565
9 7026972
5 1091517

[出力例]
123456789

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

[入力例]

5 3

1 9

1 7

2 6

2 5

3 1

[出力例]

※AtCoderテストケースより

[入力例]

7 4

1 1

2 1

3 1

4 6

4 5

[出力例]

※AtCoderテストケースより

[入力例]

6 5

5 1000000000

2 990000000

3 980000000

6 970000000

6 960000000

4 950000000

[出力例]

4900000016

※AtCoderテストケースより

[入力例]

12 5

1 2

2 5

1 7

1 5

7 10

7 3

5 10

4 4

1 6

2 9

5 8

4 9

[出力例]

[入力例]

20 7

8 764

5 313

10 861

6 544

8 1262

5 182

7 1202

3 130

5 850

3 981

5 590

10 771

6 50

4 1255

3 552

10 631

3 848

6 659

4 1091

6 1089

[出力例]

7777

[入力例]

50 10

11 6619934

5 1624101

12 5451794

3 9857183

5 1985828

11 11345963

2 5757194

3 6881103

9 1920811

14 8507495

14 5235040

10 4128252

15 1491606

11 768521

12 9822790

13 10069095

7 7116817

12 6611197

4 1247639

2 36843

9 10277716

3 19857

2 11561672

15 631937

5 7841766

13 2487890

13 13479705

8 1159151

2 12291992

7 2711313

7 1707463

10 985172

10 9394217

9 1626609

6 8081696

12 10331209

7 11885741

12 12131871

8 4794885

6 11949323

14 43035

10 9376463

3 12689389

12 7496508

3 8502162

14 4333674

10 15789860

6 9809565

9 7026972

5 1091517

[出力例]

123456789

■参照サイト
AtCoder Beginner Contest 116

2022年1月7日2022年1月7日

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

C++の練習を兼ねて, AtCoder Beginner Contest 100 の問題D (Patisserie ABC) を解いてみた.

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

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

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

// 解き直し.
// https://img.atcoder.jp/abc100/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()
LL x[1010], y[1010], z[1010];

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    rep(i, N) scanf("%lld %lld %lld", &x[i], &y[i], &z[i]);
    
    // 2. 全探索.
    LL ans = -202020202020202020;
    rep(i, 1 << 3){
        // 2-1. 符号.
        int s[3];
        rep(j, 3) s[j] = (i & (1 << j)) ? 1 : -1;
        
        // 2-2. 綺麗さ, おいしさ, 人気度 の (符号付き)合計.
        vl v;
        rep(j, N) v.pb(x[j] * s[0] + y[j] * s[1] + z[j] * s[2]);
        
        // 2-3. sort.
        sort(all(v));
        
        // 2-4. 大きい順に, M個.
        LL t = 0;
        rep(j, M) t += v[N - 1 - j];
        
        // 2-5. 最大値更新.
        ans = max(ans, t);
    }
    
    // 3. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

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

LL x[1010], y[1010], z[1010];

int main(){

// 1. 入力情報.

int N, M;

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

rep(i, N) scanf("%lld %lld %lld", &x[i], &y[i], &z[i]);

// 2. 全探索.

LL ans = -202020202020202020;

rep(i, 1 << 3){

// 2-1. 符号.

int s[3];

rep(j, 3) s[j] = (i & (1 << j)) ? 1 : -1;

// 2-2. 綺麗さ, おいしさ, 人気度の (符号付き)合計.

vl v;

rep(j, N) v.pb(x[j] * s[0] + y[j] * s[1] + z[j] * s[2]);

// 2-3. sort.

sort(all(v));

// 2-4. 大きい順に, M個.

LL t = 0;

rep(j, M) t += v[N - 1 - j];

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

ans = max(ans, t);

}

// 3. 出力.

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

return 0;

}

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

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

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

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

[入力例]
10 5
10 -80 21
23 8 38
-94 28 11
-26 -2 18
-69 72 79
-26 -86 -54
-72 -50 59
21 65 -32
40 -94 87
-62 18 82

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

[入力例]
3 2
2000000000 -9000000000 4000000000
7000000000 -5000000000 3000000000
6000000000 -1000000000 8000000000

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

[入力例]
5 3
144 15 -62
51 -54 131
135 -84 33
56 15 -20
-85 121 51

[出力例]
555

[入力例]
10 5
1040 -428 453
145 267 -916
177 664 1270
1111 -1139 800
-666 1125 872
214 -251 1048
663 103 -242
-696 964 108
1095 135 -450
915 193 -719

[出力例]
7777

[入力例]
30 12
2380290 -3874089 2225751
1397296 6482937 -1511776
936588 3280145 -5529143
3729139 798728 -1827712
4073447 -5934867 18870583
1465042 -2344443 1453900
4976600 4863530 1155788
831766 -6177751 6705880
-1387521 6911937 1305672
-2164290 1147022 9051983
-2071730 4990138 1143816
1486505 -8642625 1439353
2296136 -1319424 1215097
950669 1626133 2240346
-9345210 2486543 3900715
1967137 -1407849 1349998
1166523 3341920 2021650
-1377692 -2914269 1199173
1368469 -5705370 1025103
1823988 3869999 -1537211
-6939050 -1096274 -7844622
816106 -1355430 1813427
1202876 -249023 2224158
1120622 -9998050 4192084
-4739977 1249319 -1557077
992298 6869258 -1207735
1746909 1898002 -6951358
1903970 -8996164 1959390
-1541635 8794420 5602718
-4950188 1212287 1628534

[出力例]
123456789

100

101

102

103

104

105

106

107

108

109

110

111

112

113

[入力例]

5 3

3 1 4

1 5 9

2 6 5

3 5 8

9 7 9

[出力例]

※AtCoderテストケースより

[入力例]

5 3

1 -2 3

-4 5 -6

7 -8 -9

-10 11 -12

13 -14 15

[出力例]

※AtCoderテストケースより

[入力例]

10 5

10 -80 21

23 8 38

-94 28 11

-26 -2 18

-69 72 79

-26 -86 -54

-72 -50 59

21 65 -32

40 -94 87

-62 18 82

[出力例]

638

※AtCoderテストケースより

[入力例]

3 2

2000000000 -9000000000 4000000000

7000000000 -5000000000 3000000000

6000000000 -1000000000 8000000000

[出力例]

30000000000

※AtCoderテストケースより

[入力例]

5 3

144 15 -62

51 -54 131

135 -84 33

56 15 -20

-85 121 51

[出力例]

555

[入力例]

10 5

1040 -428 453

145 267 -916

177 664 1270

1111 -1139 800

-666 1125 872

214 -251 1048

663 103 -242

-696 964 108

1095 135 -450

915 193 -719

[出力例]

7777

[入力例]

30 12

2380290 -3874089 2225751

1397296 6482937 -1511776

936588 3280145 -5529143

3729139 798728 -1827712

4073447 -5934867 18870583

1465042 -2344443 1453900

4976600 4863530 1155788

831766 -6177751 6705880

-1387521 6911937 1305672

-2164290 1147022 9051983

-2071730 4990138 1143816

1486505 -8642625 1439353

2296136 -1319424 1215097

950669 1626133 2240346

-9345210 2486543 3900715

1967137 -1407849 1349998

1166523 3341920 2021650

-1377692 -2914269 1199173

1368469 -5705370 1025103

1823988 3869999 -1537211

-6939050 -1096274 -7844622

816106 -1355430 1813427

1202876 -249023 2224158

1120622 -9998050 4192084

-4739977 1249319 -1557077

992298 6869258 -1207735

1746909 1898002 -6951358

1903970 -8996164 1959390

-1541635 8794420 5602718

-4950188 1212287 1628534

[出力例]

123456789

■参照サイト
AtCoder Beginner Contest 100

2022年1月6日

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

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

■感想.
1. 問題Eは, 規則性が見つかって, 方針を絞り込めたので, AC版に到達できたと思う.
2. Union-Find木の復習が出来たので, 非常に良かったと思う.
※ 公式のライブラリを拝借させて頂いてます.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)

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

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    set<int> st[N];
    rep(i, M){
        int a, b;
        scanf("%d %d", &a, &b);
        a--, b--;
        
        // 辺(a, b) のみ保存(a < b に 注意).
        st[a].insert(b);
    }
    
    // 2. 連結成分の個数は？
    int ans[N + 1];
    rep(i, N + 1) ans[i] = 0;
    UnionFind uf(N + 2);
    repr(u, N - 1, 0){
        // 2-1. 頂点 u を 追加.
        // -> 連結成分 が, 1 増加したと見る.
        ans[u] = ans[u + 1] + 1;
        
        // 2-2. 頂点 u に 隣接している辺 を 追加.
        for(auto &v : st[u]){
            // UnionFind木で, 根(連結成分) が 異なる場合, 辺を追加.
            // -> 連結成分 が, 1 減少したと見る.
            if(!uf.same(u, v)){
                uf.unite(u, v);
                ans[u]--;
            }
        }
    }
    
    // 3. 出力.
    repx(i, 1, N + 1) printf("%d\n", ans[i]);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

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

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

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

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

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

// UnionFind

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

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

// -> 一部改変.

struct UnionFind{

vi d;

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

int find(int x){

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

}

bool unite(int x, int y){

x = find(x);

y = find(y);

if(x == y) return false;

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

d[x] += d[y];

d[y] = x;

return true;

}

bool same(int x, int y){

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

}

int size(int x){

return -d[find(x)];

}

};

int main(){

// 1. 入力情報.

int N, M;

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

set<int> st[N];

rep(i, M){

int a, b;

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

a--, b--;

// 辺(a, b) のみ保存(a < b に注意).

st[a].insert(b);

}

// 2. 連結成分の個数は？

int ans[N + 1];

rep(i, N + 1) ans[i] = 0;

UnionFind uf(N + 2);

repr(u, N - 1, 0){

// 2-1. 頂点 u を追加.

// -> 連結成分が, 1 増加したと見る.

ans[u] = ans[u + 1] + 1;

// 2-2. 頂点 u に隣接している辺を追加.

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

// UnionFind木で, 根(連結成分) が異なる場合, 辺を追加.

// -> 連結成分が, 1 減少したと見る.

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

uf.unite(u, v);

ans[u]--;

}

// 3. 出力.

repx(i, 1, N + 1) printf("%d\n", ans[i]);

return 0;

}

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

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

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

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

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

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

[入力例]
36 40
1 2
1 3
1 4
1 5
1 6
2 7
2 27
2 28
3 10
3 29
3 30
4 19
4 35
4 36
5 16
5 33
5 34
6 13
6 31
6 32
7 8
7 9
8 26
9 26
10 11
10 12
11 22
12 22
13 14
13 15
14 23
15 23
16 17
16 18
17 24
18 24
19 20
19 21
20 25
21 25

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

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

[入力例]

6 7

1 2

1 4

1 5

2 4

2 3

3 5

3 6

[出力例]

※AtCoderテストケースより

[入力例]

8 7

7 8

3 4

5 6

5 7

5 8

6 7

6 8

[出力例]

[入力例]

15 15

1 2

2 3

1 3

4 5

5 6

4 6

7 8

8 9

7 9

10 11

11 12

10 12

13 14

14 15

13 15

[出力例]

[入力例]

36 40

1 2

1 3

1 4

1 5

1 6

2 7

2 27

2 28

3 10

3 29

3 30

4 19

4 35

4 36

5 16

5 33

5 34

6 13

6 31

6 32

7 8

7 9

8 26

9 26

10 11

10 12

11 22

12 22

13 14

13 15

14 23

15 23

16 17

16 18

17 24

18 24

19 20

19 21

20 25

21 25

[出力例]

■参照サイト
NECプログラミングコンテスト2021(AtCoder Beginner Contest 229)
Union-Find木

C++の練習を兼ねて, AtCoder Beginner Contest 233 の 問題E (Σ[k=0..10^100]floor(X／10^k)) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 233 の 問題C (Product) ～ 問題D (Count Interval) を解いてみた.

C++の練習を兼ねて, 第九回 アルゴリズム実技検定 の 問題L (嘘つきな生徒たち) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 234 の 問題C (Happy New Year!) ～ 問題D (Prefix K-th Max) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 093 の 問題E (Bichrome Spanning Tree) を解いてみた.

C++の練習を兼ねて, 第九回 アルゴリズム実技検定 の 問題K (ガソリンスタンド) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 116 の 問題D (Various Sushi) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 100 の 問題D (Patisserie ABC) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 233 の問題E (Σ[k=0..10^100]floor(X／10^k)) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 233 の問題C (Product) ～問題D (Count Interval) を解いてみた.

C++の練習を兼ねて, 第九回アルゴリズム実技検定の問題L (嘘つきな生徒たち) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 234 の問題C (Happy New Year!) ～問題D (Prefix K-th Max) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 093 の問題E (Bichrome Spanning Tree) を解いてみた.

C++の練習を兼ねて, 第九回アルゴリズム実技検定の問題K (ガソリンスタンド) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 116 の問題D (Various Sushi) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 100 の問題D (Patisserie ABC) を解いてみた.

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