8月, 2019 | 個人用メモ帳

2019年8月20日2019年8月20日

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

C++の練習を兼ねて, AtCoder Beginner Contest 138 の問題E (E – Strings of Impurity) を解いてみた.

■感想.
1. 複雑なロジックとなったが, なんとか実装できた.
2. TLE版を解消して, AC版に到達出来た.
※ TLE版にあるように, for文内で, vector の変数宣言することが, 非常に重たい処理であることが分かり, 勉強になった.
3. 苦手なdpの訓練を積めたので良かったと思う.

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

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

// b10, b14, b15 で, TLE と なった.
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const string ALPHABET = "abcdefghijklmnopqrstuvwxyz";
// 文字列 T の 先頭から, 順に, 文字列 S を 1グーゴル個連結した文字列(以下, S'と略記)中に, 出現する位置 を 保存.
LL dp[111111];
// 文字列 S の 各文字 の 出現位置 を 保管.
vector<vector<LL>> sPos(26);

int main(){
    
    // 1. 入力情報取得.
    char S[111111], T[111111];
    scanf("%s %s", S, T);
    int sl = strlen(S);
    int tl = strlen(T);
    
    // 2. 各文字の出現回数を保存.
    map<char, int> ms, mt;
    for(int i = 0; i < ALPHABET.size(); i++) ms[ALPHABET[i]] = 0, mt[ALPHABET[i]] = 0;
    for(int i = 0; i < sl; i++){
        ms[S[i]]++;
        int index = S[i] - 'a';
        sPos[index].push_back(i + 1);
    }
    for(int i = 0; i < tl; i++) mt[T[i]]++;
    // for(int i = 0; i < 26; i++){
    //     for(auto &p : sPos[i]) printf("%lld ", p);
    //     printf("\n");
    // }
    
    // 3. 存在しないケースを出力.
    // 文字列 S に 存在しない文字が, 文字列 T に 含まれている場合.
    for(auto &p : mt){
        char c = p.first;
        if(ms[c] == 0 && mt[c] > 0){
            printf("%d\n", -1);
            return 0;
        }
    }
    
    // 4. dp更新.
    // ex.
    // S = contest
    // T = sentence
    // -> 以下のように考える.
    // 文字列 T の 各文字 について, 文字列 S で, 何番目 を 使っているか見る.
    // s: 6
    // e: 5 -> 12
    // n: 3 -> 10 -> 17
    // t: 4 ->  7 -> 11 -> 14 -> 18
    // e: 5 -> 12 -> 19
    // n: 3 -> 10 -> 17 -> 24
    // c: 1 ->  8 -> 15 -> 22 -> 29
    // e: 5 -> 12 -> 19 -> 26 -> 33
    // -> 上記から, 33文字 と 判明.
    LL bef = 0; // 前回出現位置.
    for(int i = 0; i < tl; i++){
        // 今回チェックする文字列 T 中 の 文字 c.
        char c = T[i];
        int index = c - 'a';
        
        // 文字列 S 中 の 文字 c に関する出現位置情報.
        vector<LL> p = sPos[index];
        
        // 今回出現位置 は 前回出現位置 から 逆算.
        LL tmp = lower_bound(p.begin(), p.end(), (bef % sl + 1)) - p.begin();
        LL cPos = 0;
        if(tmp == p.size()) cPos = (bef / sl + 1) * sl + p[0]; // 末尾なら, 次のサイクルの最初の要素を設定.
        else                cPos = (bef / sl) * sl     + p[tmp];
        
        // 上記までで計算した位置を元に, dp を 更新.
        dp[i] = cPos;
        
        // 前回情報更新.
        bef = cPos;
    }
    
    // 5. 出力 ～ 後処理.
    // for(int i = 0; i < tl; i++) printf("%lld ", dp[i]);
    // printf("\n");
    printf("%lld\n", dp[tl - 1]);
    return 0;
    
}

// b10, b14, b15 で, TLE となった.

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

const string ALPHABET = "abcdefghijklmnopqrstuvwxyz";

// 文字列 T の先頭から, 順に, 文字列 S を 1グーゴル個連結した文字列(以下, S'と略記)中に, 出現する位置を保存.

LL dp[111111];

// 文字列 S の各文字の出現位置を保管.

vector<vector<LL>> sPos(26);

int main(){

// 1. 入力情報取得.

char S[111111], T[111111];

scanf("%s %s", S, T);

int sl = strlen(S);

int tl = strlen(T);

// 2. 各文字の出現回数を保存.

map<char, int> ms, mt;

for(int i = 0; i < ALPHABET.size(); i++) ms[ALPHABET[i]] = 0, mt[ALPHABET[i]] = 0;

for(int i = 0; i < sl; i++){

ms[S[i]]++;

int index = S[i] - 'a';

sPos[index].push_back(i + 1);

}

for(int i = 0; i < tl; i++) mt[T[i]]++;

// for(int i = 0; i < 26; i++){

// for(auto &p : sPos[i]) printf("%lld ", p);

// printf("\n");

// }

// 3. 存在しないケースを出力.

// 文字列 S に存在しない文字が, 文字列 T に含まれている場合.

for(auto &p : mt){

char c = p.first;

if(ms[c] == 0 && mt[c] > 0){

printf("%d\n", -1);

return 0;

}

// 4. dp更新.

// ex.

// S = contest

// T = sentence

// -> 以下のように考える.

// 文字列 T の各文字について, 文字列 S で, 何番目を使っているか見る.

// s: 6

// e: 5 -> 12

// n: 3 -> 10 -> 17

// t: 4 -> 7 -> 11 -> 14 -> 18

// e: 5 -> 12 -> 19

// n: 3 -> 10 -> 17 -> 24

// c: 1 -> 8 -> 15 -> 22 -> 29

// e: 5 -> 12 -> 19 -> 26 -> 33

// -> 上記から, 33文字と判明.

LL bef = 0; // 前回出現位置.

for(int i = 0; i < tl; i++){

// 今回チェックする文字列 T 中の文字 c.

char c = T[i];

int index = c - 'a';

// 文字列 S 中の文字 c に関する出現位置情報.

vector<LL> p = sPos[index];

// 今回出現位置は前回出現位置から逆算.

LL tmp = lower_bound(p.begin(), p.end(), (bef % sl + 1)) - p.begin();

LL cPos = 0;

if(tmp == p.size()) cPos = (bef / sl + 1) * sl + p[0]; // 末尾なら, 次のサイクルの最初の要素を設定.

else cPos = (bef / sl) * sl + p[tmp];

// 上記までで計算した位置を元に, dp を更新.

dp[i] = cPos;

// 前回情報更新.

bef = cPos;

}

// 5. 出力～後処理.

// for(int i = 0; i < tl; i++) printf("%lld ", dp[i]);

// printf("\n");

printf("%lld\n", dp[tl - 1]);

return 0;

}

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

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const string ALPHABET = "abcdefghijklmnopqrstuvwxyz";
// 文字列 T の 先頭から, 順に, 文字列 S を 1グーゴル個連結した文字列(以下, S'と略記)中に, 出現する位置 を 保存.
LL dp[111111];
// 文字列 S の 各文字 の 出現位置 を 保管.
vector<vector<LL>> sPos(26);

int main(){
    
    // 1. 入力情報取得.
    char S[111111], T[111111];
    scanf("%s %s", S, T);
    int sl = strlen(S);
    int tl = strlen(T);
    
    // 2. 各文字の出現回数を保存.
    map<char, int> ms, mt;
    for(int i = 0; i < ALPHABET.size(); i++) ms[ALPHABET[i]] = 0, mt[ALPHABET[i]] = 0;
    for(int i = 0; i < sl; i++){
        ms[S[i]]++;
        int index = S[i] - 'a';
        sPos[index].push_back(i + 1);
    }
    for(int i = 0; i < tl; i++) mt[T[i]]++;
    // for(int i = 0; i < 26; i++){
    //     for(auto &p : sPos[i]) printf("%lld ", p);
    //     printf("\n");
    // }
    
    // 3. 存在しないケースを出力.
    // 文字列 S に 存在しない文字が, 文字列 T に 含まれている場合.
    for(auto &p : mt){
        char c = p.first;
        if(ms[c] == 0 && mt[c] > 0){
            printf("%d\n", -1);
            return 0;
        }
    }
    
    // 4. dp更新.
    // ex.
    // S = contest
    // T = sentence
    // -> 以下のように考える.
    // 文字列 T の 各文字 について, 文字列 S で, 何番目 を 使っているか見る.
    // s: 6
    // e: 5 -> 12
    // n: 3 -> 10 -> 17
    // t: 4 ->  7 -> 11 -> 14 -> 18
    // e: 5 -> 12 -> 19
    // n: 3 -> 10 -> 17 -> 24
    // c: 1 ->  8 -> 15 -> 22 -> 29
    // e: 5 -> 12 -> 19 -> 26 -> 33
    // -> 上記から, 33文字 と 判明.
    LL bef = 0; // 前回出現位置.
    for(int i = 0; i < tl; i++){
        // 今回チェックする文字列 T 中 の 文字 c.
        char c = T[i];
        int index = c - 'a';
        
        // 文字列 S 中 の 文字 c に関する出現位置情報 … sPos[index].
        // 今回出現位置 は 前回出現位置 から 逆算.
        LL tmp = lower_bound(sPos[index].begin(), sPos[index].end(), (bef % sl + 1)) - sPos[index].begin();
        LL cPos = 0;
        if(tmp == sPos[index].size()) cPos = (bef / sl + 1) * sl + sPos[index][0]; // 末尾なら, 次のサイクルの最初の要素を設定.
        else                          cPos = (bef / sl) * sl     + sPos[index][tmp];
        
        // 上記までで計算した位置を元に, dp を 更新.
        dp[i] = cPos;
        
        // 前回情報更新.
        bef = cPos;
    }
    
    // 5. 出力 ～ 後処理.
    // for(int i = 0; i < tl; i++) printf("%lld ", dp[i]);
    // printf("\n");
    printf("%lld\n", dp[tl - 1]);
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

const string ALPHABET = "abcdefghijklmnopqrstuvwxyz";

// 文字列 T の先頭から, 順に, 文字列 S を 1グーゴル個連結した文字列(以下, S'と略記)中に, 出現する位置を保存.

LL dp[111111];

// 文字列 S の各文字の出現位置を保管.

vector<vector<LL>> sPos(26);

int main(){

// 1. 入力情報取得.

char S[111111], T[111111];

scanf("%s %s", S, T);

int sl = strlen(S);

int tl = strlen(T);

// 2. 各文字の出現回数を保存.

map<char, int> ms, mt;

for(int i = 0; i < ALPHABET.size(); i++) ms[ALPHABET[i]] = 0, mt[ALPHABET[i]] = 0;

for(int i = 0; i < sl; i++){

ms[S[i]]++;

int index = S[i] - 'a';

sPos[index].push_back(i + 1);

}

for(int i = 0; i < tl; i++) mt[T[i]]++;

// for(int i = 0; i < 26; i++){

// for(auto &p : sPos[i]) printf("%lld ", p);

// printf("\n");

// }

// 3. 存在しないケースを出力.

// 文字列 S に存在しない文字が, 文字列 T に含まれている場合.

for(auto &p : mt){

char c = p.first;

if(ms[c] == 0 && mt[c] > 0){

printf("%d\n", -1);

return 0;

}

// 4. dp更新.

// ex.

// S = contest

// T = sentence

// -> 以下のように考える.

// 文字列 T の各文字について, 文字列 S で, 何番目を使っているか見る.

// s: 6

// e: 5 -> 12

// n: 3 -> 10 -> 17

// t: 4 -> 7 -> 11 -> 14 -> 18

// e: 5 -> 12 -> 19

// n: 3 -> 10 -> 17 -> 24

// c: 1 -> 8 -> 15 -> 22 -> 29

// e: 5 -> 12 -> 19 -> 26 -> 33

// -> 上記から, 33文字と判明.

LL bef = 0; // 前回出現位置.

for(int i = 0; i < tl; i++){

// 今回チェックする文字列 T 中の文字 c.

char c = T[i];

int index = c - 'a';

// 文字列 S 中の文字 c に関する出現位置情報 … sPos[index].

// 今回出現位置は前回出現位置から逆算.

LL tmp = lower_bound(sPos[index].begin(), sPos[index].end(), (bef % sl + 1)) - sPos[index].begin();

LL cPos = 0;

if(tmp == sPos[index].size()) cPos = (bef / sl + 1) * sl + sPos[index][0]; // 末尾なら, 次のサイクルの最初の要素を設定.

else cPos = (bef / sl) * sl + sPos[index][tmp];

// 上記までで計算した位置を元に, dp を更新.

dp[i] = cPos;

// 前回情報更新.

bef = cPos;

}

// 5. 出力～後処理.

// for(int i = 0; i < tl; i++) printf("%lld ", dp[i]);

// printf("\n");

printf("%lld\n", dp[tl - 1]);

return 0;

}

[入力例]
contest
son

[出力例(debug版)]
6 9 10 
10
※AtCoderテストケースより

[入力例]
contest
programming

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

[入力例]
contest
sentence

[出力例(debug版)]
6 12 17 18 19 24 29 33 
33
※AtCoderテストケースより

[入力例]
aiueo
aiueo

[出力例(debug版)]
1 2 3 4 5 
5

[入力例]
jugemujugemugokonosurikirekaijarisuigyonosuigyomatsuunraimatsufuraimatsukunerutokoronisumutokoroyaburakojinoburakojipaipopaipopaiponoshuringanshuringannogurindaigurindainopompokopinopompokonanochokyumeinochosukezyugemuzyugemugokonosurikirekaizyarisuigyonosuigyomatuunraimatuhuraimatukuunerutokoronisumutokorol
magicalspell

[出力例(debug版)]
5 28 37 44 194 241 309 328 426 510 618 927 
927

[入力例]

contest

son

[出力例(debug版)]

6 9 10

※AtCoderテストケースより

[入力例]

contest

programming

[出力例(debug版)]

-1

※AtCoderテストケースより

[入力例]

contest

sentence

[出力例(debug版)]

6 12 17 18 19 24 29 33

※AtCoderテストケースより

[入力例]

aiueo

[出力例(debug版)]

1 2 3 4 5

[入力例]

jugemujugemugokonosurikirekaijarisuigyonosuigyomatsuunraimatsufuraimatsukunerutokoronisumutokoroyaburakojinoburakojipaipopaipopaiponoshuringanshuringannogurindaigurindainopompokopinopompokonanochokyumeinochosukezyugemuzyugemugokonosurikirekaizyarisuigyonosuigyomatuunraimatuhuraimatukuunerutokoronisumutokorol

magicalspell

[出力例(debug版)]

5 28 37 44 194 241 309 328 426 510 618 927

927

■参照サイト
AtCoder Beginner Contest 138

2019年8月19日

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

C++の練習を兼ねて, AtCoder Beginner Contest 138 の問題D (D – Ki) を解いてみた.

■感想.
1. 深さ優先探索時に, dp更新を行えば良いことに気付いたので, AC版に到達出来た.
2. 深さ優先探索の実装は, AtCoder Beginner Contest 070 (問題D Transit Tree Path) の解説をベースに実装している.

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

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

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int MAX = 210012;
vector<vector<int>> graph(MAX);
LL dp[MAX];

// グラフの経路を探索する.
// https://ja.wikipedia.org/wiki/深さ優先探索
// @param c: 探索地点となる頂点.
// @param b: 探索地点から見て, 前回探索済の頂点.
// @return : 特に無し.
void dfs(int c, int b){
    dp[c] += dp[b];
    for(int e : graph[c]){
        if(e == b) continue;
        dfs(e, c);
    }
}

int main(){
    
    // 1. 入力情報取得.
    int N, Q;
    scanf("%d %d", &N, &Q);
    for(int i = 0; i < N - 1; i++){
        int a, b;
        scanf("%d %d", &a, &b);
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    for(int i = 0; i < Q; i++){
        int p;
        LL x;
        scanf("%d %lld", &p, &x);
        dp[p] += x;
    }
    
    // 2. dp更新.
    dfs(1, 0);
    
    // 3. 出力 ～ 後処理.
    for(int i = 1; i <= N; i++) printf("%lld ", dp[i]);
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

const int MAX = 210012;

vector<vector<int>> graph(MAX);

LL dp[MAX];

// グラフの経路を探索する.

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

// @param c: 探索地点となる頂点.

// @param b: 探索地点から見て, 前回探索済の頂点.

// @return : 特に無し.

void dfs(int c, int b){

dp[c] += dp[b];

for(int e : graph[c]){

if(e == b) continue;

dfs(e, c);

}

int main(){

// 1. 入力情報取得.

int N, Q;

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

for(int i = 0; i < N - 1; i++){

int a, b;

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

graph[a].push_back(b);

graph[b].push_back(a);

}

for(int i = 0; i < Q; i++){

int p;

LL x;

scanf("%d %lld", &p, &x);

dp[p] += x;

}

// 2. dp更新.

dfs(1, 0);

// 3. 出力～後処理.

for(int i = 1; i <= N; i++) printf("%lld ", dp[i]);

return 0;

}

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

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

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

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

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

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

[入力例]

4 3

1 2

2 3

2 4

2 10

1 100

3 1

[出力例]

100 110 111 110

※AtCoderテストケースより

[入力例]

6 2

1 2

1 3

2 4

3 6

2 5

1 10

[出力例]

20 20 20 20 20 20

※AtCoderテストケースより

[入力例]

8 5

1 2

3 1

1 4

7 5

5 1

5 6

8 6

2 1

4 2

1 3

5 4

6 5

[出力例]

3 4 3 5 7 12 7 12

■参照サイト
AtCoder Beginner Contest 138

2019年8月15日

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

C++の練習を兼ねて, AtCoder Beginner Contest 019 の問題C (C – 高橋くんと魔法の箱) ～問題D (D – 高橋くんと木の直径) を解いてみた.

■感想.
1. C問題は, 2で割れる場合に, ひたすら割っていくことに気付けたので, AC版に到達出来た.
2. D問題は, 木の直径についての性質を復習出来たので, 良かったと思う, 但し, 入出力が, 特殊なパターンだったので, 慣れるまで苦労した.

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

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

#include <bits/stdc++.h>
using namespace std;

int main(){

    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    map<int, int> m;
    for(int i = 0; i < N; i++){
        int a;
        scanf("%d", &a);
        while(a % 2 == 0) a >>= 1;
        m[a]++;
    }
    
    // 2. 出力 ～ 後処理.
    printf("%d\n", m.size());
    return 0;

}

#include <bits/stdc++.h>

using namespace std;

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

map<int, int> m;

for(int i = 0; i < N; i++){

int a;

scanf("%d", &a);

while(a % 2 == 0) a >>= 1;

m[a]++;

}

// 2. 出力～後処理.

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

return 0;

}

[入力例]
3
1 2 3

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

[入力例]
4
2 4 8 16

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

[入力例]
4
2 3 5 7

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

[入力例]
100
950 369 38 887 498 212 660 1081 233 662 1233 161 733 362 813 1077 489 119 1130 412 855 973 324 1066 1037 1116 321 900 573 322 621 784 794 305 591 719 154 352 836 1148 476 949 1215 39 751 286 410 814 64 539 1058 872 98 926 759 121 934 988 1032 656 350 10 19 1096 483 663 581 600 525 90 216 1099 1084 988 708 403 818 498 978 613 849 1077 869 433 32 837 288 1204 128 873 675 591 611 1180 419 963 73 524 824 489

[出力例]
87

[入力例]

1 2 3

[出力例]

※AtCoderテストケースより

[入力例]

2 4 8 16

[出力例]

※AtCoderテストケースより

[入力例]

2 3 5 7

[出力例]

※AtCoderテストケースより

[入力例]

100

950 369 38 887 498 212 660 1081 233 662 1233 161 733 362 813 1077 489 119 1130 412 855 973 324 1066 1037 1116 321 900 573 322 621 784 794 305 591 719 154 352 836 1148 476 949 1215 39 751 286 410 814 64 539 1058 872 98 926 759 121 934 988 1032 656 350 10 19 1096 483 663 581 600 525 90 216 1099 1084 988 708 403 818 498 978 613 849 1077 869 433 32 837 288 1204 128 873 675 591 611 1180 419 963 73 524 824 489

[出力例]

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

#include <bits/stdc++.h>
using namespace std;

int main() {
    
    // 1. 入力情報取得.
    int N;
    scanf("%d", &N);
    
    // 2. 頂点 1 と 頂点 2 ～ 頂点 N の 各距離 を 質問.
    // -> 頂点 u で 最大距離 du を 取得.
    int dist = 0;
    int u = 0, du = 0;
    for(int i = 2; i <= N; i++){
        printf("? %d %d\n", 1, i);
        fflush(stdout);
        scanf("%d", &dist);
        if(du < dist) du = dist, u = i;
    }
        
    // 3. 頂点 u と 頂点 2 ～ 頂点 N (※頂点 u は 除く)の 各距離 を 質問.
    // -> 頂点 v で 最大距離 dv を 取得.
    int v = 0, dv = 0;
    // N = 2 の ケース がありうるので, i = 1 からスタートさせる形に修正.
    // ※テストケース subtask0_0.txt 等 で, WA となるため.
    // for(int i = 2; i <= N; i++){
    for(int i = 1; i <= N; i++){
        if(u == i) continue;
        printf("? %d %d\n", u, i);
        fflush(stdout);
        scanf("%d", &dist);
        if(dv < dist) dv = dist, v = i;
    }
    
    // 4. 木の直径を, dv で, 出力.
    printf("! %d", dv);
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

int main() {

// 1. 入力情報取得.

int N;

scanf("%d", &N);

// 2. 頂点 1 と頂点 2 ～頂点 N の各距離を質問.

// -> 頂点 u で最大距離 du を取得.

int dist = 0;

int u = 0, du = 0;

for(int i = 2; i <= N; i++){

printf("? %d %d\n", 1, i);

fflush(stdout);

scanf("%d", &dist);

if(du < dist) du = dist, u = i;

}

// 3. 頂点 u と頂点 2 ～頂点 N (※頂点 u は除く)の各距離を質問.

// -> 頂点 v で最大距離 dv を取得.

int v = 0, dv = 0;

// N = 2 のケースがありうるので, i = 1 からスタートさせる形に修正.

// ※テストケース subtask0_0.txt 等で, WA となるため.

// for(int i = 2; i <= N; i++){

for(int i = 1; i <= N; i++){

if(u == i) continue;

printf("? %d %d\n", u, i);

fflush(stdout);

scanf("%d", &dist);

if(dv < dist) dv = dist, v = i;

}

// 4. 木の直径を, dv で, 出力.

printf("! %d", dv);

return 0;

}

■参照サイト
AtCoder Beginner Contest 019

2019年8月13日2019年8月13日

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

C++の練習を兼ねて, AtCoder Beginner Contest 014 の問題C (C – AtColor) ～問題D (D – 閉路) を解いてみた.

■感想.
1. C問題は, どこかでAtCoder上, 類題を解いたような記憶があるが, 思い出せなかった, 但し, 個人的には, 計算量を減らすためのテクニックが, 非常に面白く感じている.
2. D問題は, 時間かかってしまったが, 正答に辿り着けたので良かったと思う.
※但し, 以下の参照リンクにある Lowest Common Ancestor(LCA) のライブラリを使って対応している.
3. 新しい知識として, Lowest Common Ancestor(LCA) について, 確認出来たのが良かったと思う.

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

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

#include <bits/stdc++.h>
using namespace std;
int enquete[1234321];
vector<int> dp(1234321);

int main(){
    
    // 1. 入力情報取得.
    int N;
    scanf("%d", &N);
    for(int i = 0; i < N; i++){
        int a, b;
        scanf("%d %d", &a, &b);
        b++;
        enquete[a]++;
        enquete[b]--;
    }
    // for(int i = 0; i < 10; i++) printf("%d ", enquete[i]);
    // printf("\n");
    
    // 2. アンケートの集計結果を移し替える.
    dp[0] = enquete[0];
    for(int i = 1; i < 1234321; i++) dp[i] = dp[i - 1] + enquete[i];
    
    // for(int i = 0; i < 10; i++) printf("%d ", dp[i]);
    // printf("\n");
    
    // 3. 出力 ～ 後処理.
    printf("%d\n", *max_element(dp.begin(), dp.end()));
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

int enquete[1234321];

vector<int> dp(1234321);

int main(){

// 1. 入力情報取得.

int N;

scanf("%d", &N);

for(int i = 0; i < N; i++){

int a, b;

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

b++;

enquete[a]++;

enquete[b]--;

}

// for(int i = 0; i < 10; i++) printf("%d ", enquete[i]);

// printf("\n");

// 2. アンケートの集計結果を移し替える.

dp[0] = enquete[0];

for(int i = 1; i < 1234321; i++) dp[i] = dp[i - 1] + enquete[i];

// for(int i = 0; i < 10; i++) printf("%d ", dp[i]);

// printf("\n");

// 3. 出力～後処理.

printf("%d\n", *max_element(dp.begin(), dp.end()));

return 0;

}

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

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

[入力例]
4
1000000 1000000
1000000 1000000
0 1000000
1 1000000

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

[入力例]
100
136503 224598
51762 227473
118706 691081
105346 164043
95202 286314
147233 1000000
61094 620146
71648 933208
23649 54046
86157 263199
85004 470255
60082 627227
68766 644867
24325 35614
55711 999999
711 796106
40687 999998
84349 387503
3580 317746
18768 767342
108388 373818
62692 568103
14337 588765
123410 536066
143583 985641
108777 533250
49973 314545
82427 279929
39612 999997
78370 543000
7161 927614
65274 65397
15537 634889
25676 531249
33818 255215
3237 453449
107745 107868
103907 810151
34446 837628
34974 489203
40306 62075
32991 735406
107029 891172
91407 640950
45380 608063
91619 999996
31057 336396
37763 633378
22130 999995
8508 785629
24537 761067
63997 64120
130679 424771
66233 783525
75690 985810
42724 151991
29494 994537
141443 999994
143276 642725
52379 696382
145141 196340
41983 638896
43539 974161
116923 117046
42087 137985
49647 328037
101449 396226
149746 477929
126780 999993
18620 802935
8983 594294
88445 502104
90562 90685
40269 573916
18692 841650
3219 893247
103796 999992
94320 216498
66610 815410
11425 791229
41143 79055
67395 460973
140620 140743
102016 730130
38544 250569
42694 918156
23922 999991
141635 676715
57294 514894
111019 825442
50344 596323
134441 581109
98751 98874
81459 696449
123639 694276
60057 515967
87253 437715
44599 292057
143235 896065
30291 193354

[出力例]
88

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

[入力例]

0 2

2 3

2 4

5 6

[出力例]

※AtCoderテストケースより

[入力例]

1000000 1000000

0 1000000

1 1000000

[出力例]

※AtCoderテストケースより

[入力例]

100

136503 224598

51762 227473

118706 691081

105346 164043

95202 286314

147233 1000000

61094 620146

71648 933208

23649 54046

86157 263199

85004 470255

60082 627227

68766 644867

24325 35614

55711 999999

711 796106

40687 999998

84349 387503

3580 317746

18768 767342

108388 373818

62692 568103

14337 588765

123410 536066

143583 985641

108777 533250

49973 314545

82427 279929

39612 999997

78370 543000

7161 927614

65274 65397

15537 634889

25676 531249

33818 255215

3237 453449

107745 107868

103907 810151

34446 837628

34974 489203

40306 62075

32991 735406

107029 891172

91407 640950

45380 608063

91619 999996

31057 336396

37763 633378

22130 999995

8508 785629

24537 761067

63997 64120

130679 424771

66233 783525

75690 985810

42724 151991

29494 994537

141443 999994

143276 642725

52379 696382

145141 196340

41983 638896

43539 974161

116923 117046

42087 137985

49647 328037

101449 396226

149746 477929

126780 999993

18620 802935

8983 594294

88445 502104

90562 90685

40269 573916

18692 841650

3219 893247

103796 999992

94320 216498

66610 815410

11425 791229

41143 79055

67395 460973

140620 140743

102016 730130

38544 250569

42694 918156

23922 999991

141635 676715

57294 514894

111019 825442

50344 596323

134441 581109

98751 98874

81459 696449

123639 694276

60057 515967

87253 437715

44599 292057

143235 896065

30291 193354

[出力例]

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

// 以下のライブラリを使ってみる.
// Another easy solution in <O(N logN, O(logN)>
// https://www.topcoder.com/community/competitive-programming/tutorials/range-minimum-query-and-lowest-common-ancestor/#Lowest%20Common%20Ancestor%20(LCA)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100001;
const int LOGMAXN = 17; // 2 の 17乗 … 131072
int L[MAXN], T[MAXN], P[MAXN][LOGMAXN];

// グラフの経路を探索する.
// 深さ優先探索(depth-first search).
// https://ja.wikipedia.org/wiki/深さ優先探索
// @param g: グラフ.
// @param c: 探索地点となる頂点.
// @param b: 探索地点から見て, 前回探索済の頂点.
// @param d: 探索開始地点からの距離.
// @return : 特に無し.
void dfs(const vector<vector<int>> &g, int c, int b, int d){
    L[c] = d, T[c] = b;
    for(auto &e : g[c]){
        if(e == b) continue;
        dfs(g, e, c, d + 1);
    }
}

void prepare(int N){
    // we initialize every element in P with -1.
    for(int i = 0; i < N; i++) for(int j = 0; 1 << j < N; j++) P[i][j] = -1;
    
    // the first ancestor of every node i is T[i].
    for(int i = 0; i < N; i++) P[i][0] = T[i];
    
    // bottom up dynamic programing.
    for(int j = 1; 1 << j < N; j++){
        for(int i = 0; i < N; i++){
            if(P[i][j - 1] != -1) P[i][j] = P[P[i][j - 1]][j - 1];
        }
    }
}

int query(int N, int p, int q){
    int log;
    // if p is situated on a higher level than q then we swap them.
    if(L[p] < L[q]) swap(p, q);
    
    // we compute the value of [log(L[p)].
    for(log = 1; 1 << log <= L[p]; log++);
    log--;
    
    // we find the ancestor of node p situated on the same level with q using the values in P.
    for(int i = log; i >= 0; i--){
        if(L[p] - (1 << i) >= L[q]) p = P[p][i];
        if(p == q) return p;
    }
    
    // we compute LCA(p, q) using the values in P.
    for(int i = log; i >= 0; i--){
        if(P[p][i] != -1 && P[p][i] != P[q][i]) p = P[p][i], q = P[q][i];
    }
    return T[p];
}

int main(){
    
    // 1. 入力情報取得.
    int N;
    int x, y;
    scanf("%d", &N);
    vector<vector<int>> graph(N);
    for(int i = 0; i < N - 1; i++){
        scanf("%d %d", &x, &y);
        x--, y--;
        graph[x].push_back(y);
        graph[y].push_back(x);
    }
    // for(auto &g : graph){
    //     for(int v : g) printf("%d ", v);
    //     printf("\n");
    // }
    
    // 2. 頂点 0 を 根 として, 各頂点までの距離を計算.
    dfs(graph, 0, -1, 0);
    // for(int i = 0; i < N; i++) printf("L[%d]=%d\n", i, L[i]);
    // for(int i = 0; i < N; i++) printf("T[%d]=%d\n", i, T[i]);
    
    // 3. 各クエリに対応する.
    prepare(N);
    int Q;
    int a, b;
    scanf("%d", &Q);
    while(Q--){
        scanf("%d %d", &a, &b);
        a--, b--;
        int p = query(N, a, b);
        // printf("a=%d b=%d p=%d\n", a, b, p);
        int ans = (L[a] - L[p]) + (L[b] - L[p]) + 1;
        printf("%d\n", ans);
    }
    
    // 4. 後処理.
    return 0;
    
}

100

101

102

103

// 以下のライブラリを使ってみる.

// Another easy solution in <O(N logN, O(logN)>

// https://www.topcoder.com/community/competitive-programming/tutorials/range-minimum-query-and-lowest-common-ancestor/#Lowest%20Common%20Ancestor%20(LCA)

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 100001;

const int LOGMAXN = 17; // 2 の 17乗 … 131072

int L[MAXN], T[MAXN], P[MAXN][LOGMAXN];

// グラフの経路を探索する.

// 深さ優先探索(depth-first search).

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

// @param g: グラフ.

// @param c: 探索地点となる頂点.

// @param b: 探索地点から見て, 前回探索済の頂点.

// @param d: 探索開始地点からの距離.

// @return : 特に無し.

void dfs(const vector<vector<int>> &g, int c, int b, int d){

L[c] = d, T[c] = b;

for(auto &e : g[c]){

if(e == b) continue;

dfs(g, e, c, d + 1);

}

void prepare(int N){

// we initialize every element in P with -1.

for(int i = 0; i < N; i++) for(int j = 0; 1 << j < N; j++) P[i][j] = -1;

// the first ancestor of every node i is T[i].

for(int i = 0; i < N; i++) P[i][0] = T[i];

// bottom up dynamic programing.

for(int j = 1; 1 << j < N; j++){

for(int i = 0; i < N; i++){

if(P[i][j - 1] != -1) P[i][j] = P[P[i][j - 1]][j - 1];

}

int query(int N, int p, int q){

int log;

// if p is situated on a higher level than q then we swap them.

if(L[p] < L[q]) swap(p, q);

// we compute the value of [log(L[p)].

for(log = 1; 1 << log <= L[p]; log++);

log--;

// we find the ancestor of node p situated on the same level with q using the values in P.

for(int i = log; i >= 0; i--){

if(L[p] - (1 << i) >= L[q]) p = P[p][i];

if(p == q) return p;

}

// we compute LCA(p, q) using the values in P.

for(int i = log; i >= 0; i--){

if(P[p][i] != -1 && P[p][i] != P[q][i]) p = P[p][i], q = P[q][i];

}

return T[p];

}

int main(){

// 1. 入力情報取得.

int N;

int x, y;

scanf("%d", &N);

vector<vector<int>> graph(N);

for(int i = 0; i < N - 1; i++){

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

x--, y--;

graph[x].push_back(y);

graph[y].push_back(x);

}

// for(auto &g : graph){

// for(int v : g) printf("%d ", v);

// printf("\n");

// }

// 2. 頂点 0 を根として, 各頂点までの距離を計算.

dfs(graph, 0, -1, 0);

// for(int i = 0; i < N; i++) printf("L[%d]=%d\n", i, L[i]);

// for(int i = 0; i < N; i++) printf("T[%d]=%d\n", i, T[i]);

// 3. 各クエリに対応する.

prepare(N);

int Q;

int a, b;

scanf("%d", &Q);

while(Q--){

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

a--, b--;

int p = query(N, a, b);

// printf("a=%d b=%d p=%d\n", a, b, p);

int ans = (L[a] - L[p]) + (L[b] - L[p]) + 1;

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

}

// 4. 後処理.

return 0;

}

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

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

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

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

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

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

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

[出力例]
4
3
5
5
3
7

[入力例]

1 2

1 3

1 4

4 5

2 3

2 5

2 4

[出力例]

※AtCoderテストケースより

[入力例]

1 2

2 3

3 4

4 5

5 6

1 3

1 4

1 5

1 6

[出力例]

※AtCoderテストケースより

[入力例]

3 1

2 1

2 4

2 5

3 6

3 7

4 5

1 6

5 6

4 7

5 3

[出力例]

※AtCoderテストケースより

[入力例]

2 1

3 1

12 2

2 4

4 6

4 5

7 5

8 5

11 8

9 7

10 7

12 3

2 3

3 6

9 11

10 9

3 11

[出力例]

■参照サイト
AtCoder Beginner Contest 014
Lowest Common Ancestor(LCA)

2019年8月10日

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

C++の練習を兼ねて, AtCoder Beginner Contest 137 の問題D (D – Summer Vacation) を解いてみた.

■感想.
1. 時間かかってしまったが, 正答に辿り着けたので良かったと思う.
2. 時間を見つけて, 引き続き, 復習を進めたいと思う.

本家のサイトABC 137解説をご覧下さい.

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

#include <bits/stdc++.h>
using namespace std;
const int MAX = 100001;
vector<vector<int>> A(MAX);
int reward[MAX];

int main(){

    // 1. 入力情報取得.
    int N, M;
    scanf("%d %d", &N, &M);
    for(int i = 0; i < N; i++){
        int a, b;
        scanf("%d %d", &a, &b);
        if(a <= M) A[a].push_back(b);
    }
    
    // 2. どの仕事を請けるか確定させる.
    //      (報酬支払日／仕事開始日)
    // No.1  M     日後 : 0日目
    // No.2  M - 1 日後 : 1日目まで.
    // No.3  M - 2 日後 : 2日目まで.
    // No.4  M - 3 日後 : 3日目まで.
    // ...
    // No.M      1 日後 : M - 1日目まで.
    // -> 仕事開始日が最も遅い, No.M から順に, 仕事出来るかどうかを決めていく.
    // -> 具体的には, 以下の流れで, 仕事を請けるか決定していくイメージ.
    // No.M       の 仕事 が, X(M)件     あれば, 一番報酬 の 大きい仕事 を 請ける.
    // No.(M - 1) の 仕事 が, X(M - 1)件 あれば, No.M の 残りの仕事 と 併せて, 一番報酬の大きい仕事を引き受ける.
    // 以下, 繰り返し.
    // ※N件の制約事項は, 4. で対応.
    priority_queue<int> pq;
    for(int d = M - 1; d >= 0; d--){
        // 2-1. d日目で, 可能な仕事の報酬を取得.
        for(auto &r : A[M - d]) pq.push(r);
        
        // 2-2. 仕事があれば, 報酬情報(1件)を, rewardテーブルに登録.
        if(pq.size() > 0){
            int r = pq.top();
            pq.pop();
            reward[d] = r;
        }
    }
    
    // 3. 報酬の大きい順に並べ替える.
    sort(reward, reward + MAX, greater<int>());
    
    // 4. 最大 N件 まで請けた場合に, 報酬の最大値を計算.
    int ans = 0;
    for(int i = 0; i < N; i++) ans += reward[i];
    
    // 5. 出力 ～ 後処理.
    printf("%d\n", ans);
    return 0;

}

#include <bits/stdc++.h>

using namespace std;

const int MAX = 100001;

vector<vector<int>> A(MAX);

int reward[MAX];

int main(){

// 1. 入力情報取得.

int N, M;

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

for(int i = 0; i < N; i++){

int a, b;

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

if(a <= M) A[a].push_back(b);

}

// 2. どの仕事を請けるか確定させる.

// (報酬支払日／仕事開始日)

// No.1 M 日後 : 0日目

// No.2 M - 1 日後 : 1日目まで.

// No.3 M - 2 日後 : 2日目まで.

// No.4 M - 3 日後 : 3日目まで.

// ...

// No.M 1 日後 : M - 1日目まで.

// -> 仕事開始日が最も遅い, No.M から順に, 仕事出来るかどうかを決めていく.

// -> 具体的には, 以下の流れで, 仕事を請けるか決定していくイメージ.

// No.M の仕事が, X(M)件あれば, 一番報酬の大きい仕事を請ける.

// No.(M - 1) の仕事が, X(M - 1)件あれば, No.M の残りの仕事と併せて, 一番報酬の大きい仕事を引き受ける.

// 以下, 繰り返し.

// ※N件の制約事項は, 4. で対応.

priority_queue<int> pq;

for(int d = M - 1; d >= 0; d--){

// 2-1. d日目で, 可能な仕事の報酬を取得.

for(auto &r : A[M - d]) pq.push(r);

// 2-2. 仕事があれば, 報酬情報(1件)を, rewardテーブルに登録.

if(pq.size() > 0){

int r = pq.top();

pq.pop();

reward[d] = r;

}

// 3. 報酬の大きい順に並べ替える.

sort(reward, reward + MAX, greater<int>());

// 4. 最大 N件まで請けた場合に, 報酬の最大値を計算.

int ans = 0;

for(int i = 0; i < N; i++) ans += reward[i];

// 5. 出力～後処理.

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

return 0;

}

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

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

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

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

[入力例]
1 1
2 1

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

[入力例]
120 130
62 3069
80 1908
38 333
104 3996
84 1644
50 6381
8 926
79 8063
3 3741
36 3288
76 6322
37 5784
38 7903
11 624
18 7040
67 6759
39 3002
14 843
45 5747
127 4828
92 2457
24 924
48 2116
119 2812
67 3782
83 7753
47 3421
73 169
15 6777
128 3209
98 4195
65 6485
20 2279
64 5393
78 6565
33 9644
28 7896
122 8236
42 8079
43 1875
24 3215
99 2206
40 3220
24 9879
126 2404
90 5148
91 6315
101 7658
22 5949
68 9861
6 2824
117 7105
23 6462
62 6703
60 5626
130 136
105 5060
15 3840
116 2945
10 3352
127 4674
76 9812
56 3277
129 1876
106 2237
119 6767
84 9951
81 629
41 3058
31 6328
129 520
24 9553
16 1919
125 7767
6 876
20 9750
111 8756
67 4480
125 7542
83 2216
76 2277
113 492
61 243
119 3425
12 7591
9 2479
92 8487
96 9414
58 7189
127 3710
82 2984
45 2355
105 7015
26 3590
107 8135
129 7670
114 9993
56 5309
78 4641
43 9680
65 10
79 2929
122 4441
40 4609
99 3202
60 2421
33 1313
89 5185
121 1152
10 7686
105 3877
24 1457
105 5262
4 4318
106 7050
5 794
88 5142
21 176
41 9411
15 2867

[出力例]
550000

[入力例]
100 70
62 2429
80 2233
38 1095
1 10000
84 10000
50 416
8 1676
79 10000
3 1068
36 2391
2 10000
37 1806
38 6454
11 880
18 3582
2 10000
39 2655
14 1305
45 7746
1 3770
92 8690
24 2501
48 10000
1 9999
67 6701
83 9999
47 6328
73 8211
15 9999
1 9827
98 3411
65 395
20 5641
64 9841
78 927
33 2220
28 7678
1 4802
42 2803
43 9675
24 6213
99 3858
40 9998
24 1154
126 3544
90 4348
91 1709
101 303
22 6851
68 565
6 7796
117 9620
23 9664
62 3585
60 9998
130 9997
2 6753
15 7639
116 8744
10 5263
2 3070
76 9996
56 2920
129 1686
106 593
2 3231
84 9000
81 811
41 2578
31 7434
129 3103
24 5876
16 5730
125 3088
6 6263
20 8000
111 6622
67 7167
125 4251
83 4461
76 2442
113 4417
61 7609
119 7000
12 6130
9 7323
92 7725
96 3250
58 5112
127 2863
82 5680
45 5905
105 6789
26 5130
107 5142
129 551
114 9341
56 5027
78 5425
43 9876

[出力例]
345543

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

[入力例]

3 4

4 3

4 1

2 2

[出力例]

※AtCoderテストケースより

[入力例]

5 3

1 2

1 3

1 4

2 1

2 3

[出力例]

※AtCoderテストケースより

[入力例]

1 1

2 1

[出力例]

※AtCoderテストケースより

[入力例]

120 130

62 3069

80 1908

38 333

104 3996

84 1644

50 6381

8 926

79 8063

3 3741

36 3288

76 6322

37 5784

38 7903

11 624

18 7040

67 6759

39 3002

14 843

45 5747

127 4828

92 2457

24 924

48 2116

119 2812

67 3782

83 7753

47 3421

73 169

15 6777

128 3209

98 4195

65 6485

20 2279

64 5393

78 6565

33 9644

28 7896

122 8236

42 8079

43 1875

24 3215

99 2206

40 3220

24 9879

126 2404

90 5148

91 6315

101 7658

22 5949

68 9861

6 2824

117 7105

23 6462

62 6703

60 5626

130 136

105 5060

15 3840

116 2945

10 3352

127 4674

76 9812

56 3277

129 1876

106 2237

119 6767

84 9951

81 629

41 3058

31 6328

129 520

24 9553

16 1919

125 7767

6 876

20 9750

111 8756

67 4480

125 7542

83 2216

76 2277

113 492

61 243

119 3425

12 7591

9 2479

92 8487

96 9414

58 7189

127 3710

82 2984

45 2355

105 7015

26 3590

107 8135

129 7670

114 9993

56 5309

78 4641

43 9680

65 10

79 2929

122 4441

40 4609

99 3202

60 2421

33 1313

89 5185

121 1152

10 7686

105 3877

24 1457

105 5262

4 4318

106 7050

5 794

88 5142

21 176

41 9411

15 2867

[出力例]

550000

[入力例]

100 70

62 2429

80 2233

38 1095

1 10000

84 10000

50 416

8 1676

79 10000

3 1068

36 2391

2 10000

37 1806

38 6454

11 880

18 3582

2 10000

39 2655

14 1305

45 7746

1 3770

92 8690

24 2501

48 10000

1 9999

67 6701

83 9999

47 6328

73 8211

15 9999

1 9827

98 3411

65 395

20 5641

64 9841

78 927

33 2220

28 7678

1 4802

42 2803

43 9675

24 6213

99 3858

40 9998

24 1154

126 3544

90 4348

91 1709

101 303

22 6851

68 565

6 7796

117 9620

23 9664

62 3585

60 9998

130 9997

2 6753

15 7639

116 8744

10 5263

2 3070

76 9996

56 2920

129 1686

106 593

2 3231

84 9000

81 811

41 2578

31 7434

129 3103

24 5876

16 5730

125 3088

6 6263

20 8000

111 6622

67 7167

125 4251

83 4461

76 2442

113 4417

61 7609

119 7000

12 6130

9 7323

92 7725

96 3250

58 5112

127 2863

82 5680

45 5905

105 6789

26 5130

107 5142

129 551

114 9341

56 5027

78 5425

43 9876

[出力例]

345543

■参照サイト
AtCoder Beginner Contest 137

2019年8月10日

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

C++の練習を兼ねて, AtCoder Beginner Contest 012 の問題D (D – バスと避けられない運命) を解いてみた.

■感想.
1. ワーシャル–フロイド法の復習が出来たので, 良かったと思う.
2. 解答を見る前に, 解けたので, 及第点は取れたと思う.

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

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

#include <bits/stdc++.h>
using namespace std;
const int MAX = 301;
const int INF = 123454321;
int rideTime[MAX][MAX];
int rideMaxTime[MAX];

int main(){
    
    // 1. 入力情報取得.
    int N, M;
    scanf("%d %d", &N, &M);
    for(int i = 0; i < MAX; i++) for(int j = 0; j < MAX; j++) if(i != j) rideTime[i][j] = INF;
    for(int i = 0; i < M; i++){
        int a, b, t;
        scanf("%d %d %d", &a, &b, &t);
        rideTime[a][b] = t;
        rideTime[b][a] = t;
    }
    
    // 2. ワーシャル–フロイド法.
    for(int k = 1; k <= N; k++){
        for(int i = 1; i <= N; i++){
            for(int j = 1; j <= N; j++){
                rideTime[i][j] = min(rideTime[i][j], rideTime[i][k] + rideTime[k][j]);
            }
        }
    }
    
    // 3. 各バス停を出発地点と仮定した場合の最大の乗車時間を確認.
    for(int i = 1; i <= N; i++) for(int j = 1; j <= N; j++) rideMaxTime[i] = max(rideMaxTime[i], rideTime[i][j]);
    
    // 4. 引っ越し先を決めて, 最大の乗車時間を確認.
    int ans = INF;
    for(int i = 1; i <= N; i++) ans = min(ans, rideMaxTime[i]);
    
    // 5. 出力 ～ 後処理.
    printf("%d\n", ans);
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

const int MAX = 301;

const int INF = 123454321;

int rideTime[MAX][MAX];

int rideMaxTime[MAX];

int main(){

// 1. 入力情報取得.

int N, M;

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

for(int i = 0; i < MAX; i++) for(int j = 0; j < MAX; j++) if(i != j) rideTime[i][j] = INF;

for(int i = 0; i < M; i++){

int a, b, t;

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

rideTime[a][b] = t;

rideTime[b][a] = t;

}

// 2. ワーシャル–フロイド法.

for(int k = 1; k <= N; k++){

for(int i = 1; i <= N; i++){

for(int j = 1; j <= N; j++){

rideTime[i][j] = min(rideTime[i][j], rideTime[i][k] + rideTime[k][j]);

}

// 3. 各バス停を出発地点と仮定した場合の最大の乗車時間を確認.

for(int i = 1; i <= N; i++) for(int j = 1; j <= N; j++) rideMaxTime[i] = max(rideMaxTime[i], rideTime[i][j]);

// 4. 引っ越し先を決めて, 最大の乗車時間を確認.

int ans = INF;

for(int i = 1; i <= N; i++) ans = min(ans, rideMaxTime[i]);

// 5. 出力～後処理.

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

return 0;

}

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

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

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

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

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

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

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

[出力例]
20

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

[出力例]
12

[入力例]

3 2

1 2 10

2 3 10

[出力例]

※AtCoderテストケースより

[入力例]

5 5

1 2 12

2 3 14

3 4 7

4 5 9

5 1 18

[出力例]

※AtCoderテストケースより

[入力例]

4 6

1 2 1

2 3 1

3 4 1

4 1 1

1 3 1

4 2 1

[出力例]

※AtCoderテストケースより

[入力例]

5 4

1 2 7

3 2 13

3 4 11

5 4 9

[出力例]

[入力例]

5 7

1 2 10

3 2 7

3 1 12

5 1 15

1 4 8

3 4 5

5 4 3

[出力例]

■参照サイト
AtCoder Beginner Contest 012

2019年8月9日

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

C++の練習を兼ねて, AtCoder Beginner Contest 011 の問題C (C – 123引き算) ～問題D (D – 大ジャンプ) を解いてみた.

■感想.
1. 問題C は, 3 を優先的に引いていけば解けることに気付けたので, AC版に到達できたと思う.
2. N が 299 の場合に, YES, NO のいずれのパターンも有り得るので, 面白いと思った.
3. 問題D は, N の階乗, 4 の N乗といった巨大な数の計算を, なるべく平準化する方針で, 実装できたように思う.
4. 解答を見る前に, 解けたので, 及第点は取れたと思う.

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

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

#include <bits/stdc++.h>
using namespace std;

int main(){
    
    // 1. 入力情報取得.
    int N, NG1, NG2, NG3;
    scanf("%d %d %d %d", &N, &NG1, &NG2, &NG3);
    
    // 2. N が NG1 ～ NG3 の いずれかに等しい場合.
    if(N == NG1 || N == NG2 || N == NG3){
        printf("%s\n", "NO");
        return 0;
    }
    
    // 3. 引き算を行う.
    int counter = 0;
    while(counter < 101){
        
        // 2-1. N が 0 になったら終了.
        int N1 = N - 1, N2 = N - 2, N3 = N - 3;
        if(N == 0) break;
        
        // 2-2. increment.
        counter++;
        // printf("counter=%d N=%d\n", counter, N);
        // 2-3. 1, 2, 3 の いずれかを N から 減算.
        if(N3 >= 0 && N3 != NG1 && N3 != NG2 && N3 != NG3){
            N -= 3;
            continue;
        }
        if(N2 >= 0 && N2 != NG1 && N2 != NG2 && N2 != NG3){
            N -= 2;
            continue;
        }
        if(N1 >= 0 && N1 != NG1 && N1 != NG2 && N1 != NG3){
            N--;
            continue;
        }
    }
    
    // 4. 出力.
    if(N == 0 && counter <= 100) printf("%s\n", "YES");
    else                         printf("%s\n", "NO");
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

int main(){

// 1. 入力情報取得.

int N, NG1, NG2, NG3;

scanf("%d %d %d %d", &N, &NG1, &NG2, &NG3);

// 2. N が NG1 ～ NG3 のいずれかに等しい場合.

if(N == NG1 || N == NG2 || N == NG3){

printf("%s\n", "NO");

return 0;

}

// 3. 引き算を行う.

int counter = 0;

while(counter < 101){

// 2-1. N が 0 になったら終了.

int N1 = N - 1, N2 = N - 2, N3 = N - 3;

if(N == 0) break;

// 2-2. increment.

counter++;

// printf("counter=%d N=%d\n", counter, N);

// 2-3. 1, 2, 3 のいずれかを N から減算.

if(N3 >= 0 && N3 != NG1 && N3 != NG2 && N3 != NG3){

N -= 3;

continue;

}

if(N2 >= 0 && N2 != NG1 && N2 != NG2 && N2 != NG3){

N -= 2;

continue;

}

if(N1 >= 0 && N1 != NG1 && N1 != NG2 && N1 != NG3){

N--;

continue;

}

// 4. 出力.

if(N == 0 && counter <= 100) printf("%s\n", "YES");

else printf("%s\n", "NO");

return 0;

}

[入力例]
2
1
7
15

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

[入力例]
5
1
4
2

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

[入力例]
300
57
121
244

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

[入力例]
123
1
2
3

[出力例]
NO

[入力例]
7
7
5
3

[出力例]
NO

[入力例]
299
234
123
77

[出力例(debug版)]
counter=1 N=299
counter=2 N=296
counter=3 N=293
counter=4 N=290
counter=5 N=287
counter=6 N=284
counter=7 N=281
counter=8 N=278
counter=9 N=275
counter=10 N=272
counter=11 N=269
counter=12 N=266
counter=13 N=263
counter=14 N=260
counter=15 N=257
counter=16 N=254
counter=17 N=251
counter=18 N=248
counter=19 N=245
counter=20 N=242
counter=21 N=239
counter=22 N=236
counter=23 N=233
counter=24 N=230
counter=25 N=227
counter=26 N=224
counter=27 N=221
counter=28 N=218
counter=29 N=215
counter=30 N=212
counter=31 N=209
counter=32 N=206
counter=33 N=203
counter=34 N=200
counter=35 N=197
counter=36 N=194
counter=37 N=191
counter=38 N=188
counter=39 N=185
counter=40 N=182
counter=41 N=179
counter=42 N=176
counter=43 N=173
counter=44 N=170
counter=45 N=167
counter=46 N=164
counter=47 N=161
counter=48 N=158
counter=49 N=155
counter=50 N=152
counter=51 N=149
counter=52 N=146
counter=53 N=143
counter=54 N=140
counter=55 N=137
counter=56 N=134
counter=57 N=131
counter=58 N=128
counter=59 N=125
counter=60 N=122
counter=61 N=119
counter=62 N=116
counter=63 N=113
counter=64 N=110
counter=65 N=107
counter=66 N=104
counter=67 N=101
counter=68 N=98
counter=69 N=95
counter=70 N=92
counter=71 N=89
counter=72 N=86
counter=73 N=83
counter=74 N=80
counter=75 N=78
counter=76 N=75
counter=77 N=72
counter=78 N=69
counter=79 N=66
counter=80 N=63
counter=81 N=60
counter=82 N=57
counter=83 N=54
counter=84 N=51
counter=85 N=48
counter=86 N=45
counter=87 N=42
counter=88 N=39
counter=89 N=36
counter=90 N=33
counter=91 N=30
counter=92 N=27
counter=93 N=24
counter=94 N=21
counter=95 N=18
counter=96 N=15
counter=97 N=12
counter=98 N=9
counter=99 N=6
counter=100 N=3
YES

[入力例]
299
233
123
77

[出力例(debug版)]
counter=1 N=299
counter=2 N=296
counter=3 N=293
counter=4 N=290
counter=5 N=287
counter=6 N=284
counter=7 N=281
counter=8 N=278
counter=9 N=275
counter=10 N=272
counter=11 N=269
counter=12 N=266
counter=13 N=263
counter=14 N=260
counter=15 N=257
counter=16 N=254
counter=17 N=251
counter=18 N=248
counter=19 N=245
counter=20 N=242
counter=21 N=239
counter=22 N=236
counter=23 N=234
counter=24 N=231
counter=25 N=228
counter=26 N=225
counter=27 N=222
counter=28 N=219
counter=29 N=216
counter=30 N=213
counter=31 N=210
counter=32 N=207
counter=33 N=204
counter=34 N=201
counter=35 N=198
counter=36 N=195
counter=37 N=192
counter=38 N=189
counter=39 N=186
counter=40 N=183
counter=41 N=180
counter=42 N=177
counter=43 N=174
counter=44 N=171
counter=45 N=168
counter=46 N=165
counter=47 N=162
counter=48 N=159
counter=49 N=156
counter=50 N=153
counter=51 N=150
counter=52 N=147
counter=53 N=144
counter=54 N=141
counter=55 N=138
counter=56 N=135
counter=57 N=132
counter=58 N=129
counter=59 N=126
counter=60 N=124
counter=61 N=121
counter=62 N=118
counter=63 N=115
counter=64 N=112
counter=65 N=109
counter=66 N=106
counter=67 N=103
counter=68 N=100
counter=69 N=97
counter=70 N=94
counter=71 N=91
counter=72 N=88
counter=73 N=85
counter=74 N=82
counter=75 N=79
counter=76 N=76
counter=77 N=73
counter=78 N=70
counter=79 N=67
counter=80 N=64
counter=81 N=61
counter=82 N=58
counter=83 N=55
counter=84 N=52
counter=85 N=49
counter=86 N=46
counter=87 N=43
counter=88 N=40
counter=89 N=37
counter=90 N=34
counter=91 N=31
counter=92 N=28
counter=93 N=25
counter=94 N=22
counter=95 N=19
counter=96 N=16
counter=97 N=13
counter=98 N=10
counter=99 N=7
counter=100 N=4
counter=101 N=1
NO

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

[入力例]

[出力例]

YES

※AtCoderテストケースより

[入力例]

[出力例]

YES

※AtCoderテストケースより

[入力例]

300

121

244

[出力例]

※AtCoderテストケースより

[入力例]

123

[出力例]

[入力例]

[出力例]

[入力例]

299

234

123

[出力例(debug版)]

counter=1 N=299

counter=2 N=296

counter=3 N=293

counter=4 N=290

counter=5 N=287

counter=6 N=284

counter=7 N=281

counter=8 N=278

counter=9 N=275

counter=10 N=272

counter=11 N=269

counter=12 N=266

counter=13 N=263

counter=14 N=260

counter=15 N=257

counter=16 N=254

counter=17 N=251

counter=18 N=248

counter=19 N=245

counter=20 N=242

counter=21 N=239

counter=22 N=236

counter=23 N=233

counter=24 N=230

counter=25 N=227

counter=26 N=224

counter=27 N=221

counter=28 N=218

counter=29 N=215

counter=30 N=212

counter=31 N=209

counter=32 N=206

counter=33 N=203

counter=34 N=200

counter=35 N=197

counter=36 N=194

counter=37 N=191

counter=38 N=188

counter=39 N=185

counter=40 N=182

counter=41 N=179

counter=42 N=176

counter=43 N=173

counter=44 N=170

counter=45 N=167

counter=46 N=164

counter=47 N=161

counter=48 N=158

counter=49 N=155

counter=50 N=152

counter=51 N=149

counter=52 N=146

counter=53 N=143

counter=54 N=140

counter=55 N=137

counter=56 N=134

counter=57 N=131

counter=58 N=128

counter=59 N=125

counter=60 N=122

counter=61 N=119

counter=62 N=116

counter=63 N=113

counter=64 N=110

counter=65 N=107

counter=66 N=104

counter=67 N=101

counter=68 N=98

counter=69 N=95

counter=70 N=92

counter=71 N=89

counter=72 N=86

counter=73 N=83

counter=74 N=80

counter=75 N=78

counter=76 N=75

counter=77 N=72

counter=78 N=69

counter=79 N=66

counter=80 N=63

counter=81 N=60

counter=82 N=57

counter=83 N=54

counter=84 N=51

counter=85 N=48

counter=86 N=45

counter=87 N=42

counter=88 N=39

counter=89 N=36

counter=90 N=33

counter=91 N=30

counter=92 N=27

counter=93 N=24

counter=94 N=21

counter=95 N=18

counter=96 N=15

counter=97 N=12

counter=98 N=9

counter=99 N=6

counter=100 N=3

YES

[入力例]

299

233

123

[出力例(debug版)]

counter=1 N=299

counter=2 N=296

counter=3 N=293

counter=4 N=290

counter=5 N=287

counter=6 N=284

counter=7 N=281

counter=8 N=278

counter=9 N=275

counter=10 N=272

counter=11 N=269

counter=12 N=266

counter=13 N=263

counter=14 N=260

counter=15 N=257

counter=16 N=254

counter=17 N=251

counter=18 N=248

counter=19 N=245

counter=20 N=242

counter=21 N=239

counter=22 N=236

counter=23 N=234

counter=24 N=231

counter=25 N=228

counter=26 N=225

counter=27 N=222

counter=28 N=219

counter=29 N=216

counter=30 N=213

counter=31 N=210

counter=32 N=207

counter=33 N=204

counter=34 N=201

counter=35 N=198

counter=36 N=195

counter=37 N=192

counter=38 N=189

counter=39 N=186

counter=40 N=183

counter=41 N=180

counter=42 N=177

counter=43 N=174

counter=44 N=171

counter=45 N=168

counter=46 N=165

counter=47 N=162

counter=48 N=159

counter=49 N=156

counter=50 N=153

counter=51 N=150

counter=52 N=147

counter=53 N=144

counter=54 N=141

counter=55 N=138

counter=56 N=135

counter=57 N=132

counter=58 N=129

counter=59 N=126

counter=60 N=124

counter=61 N=121

counter=62 N=118

counter=63 N=115

counter=64 N=112

counter=65 N=109

counter=66 N=106

counter=67 N=103

counter=68 N=100

counter=69 N=97

counter=70 N=94

counter=71 N=91

counter=72 N=88

counter=73 N=85

counter=74 N=82

counter=75 N=79

counter=76 N=76

counter=77 N=73

counter=78 N=70

counter=79 N=67

counter=80 N=64

counter=81 N=61

counter=82 N=58

counter=83 N=55

counter=84 N=52

counter=85 N=49

counter=86 N=46

counter=87 N=43

counter=88 N=40

counter=89 N=37

counter=90 N=34

counter=91 N=31

counter=92 N=28

counter=93 N=25

counter=94 N=22

counter=95 N=19

counter=96 N=16

counter=97 N=13

counter=98 N=10

counter=99 N=7

counter=100 N=4

counter=101 N=1

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

#include <bits/stdc++.h>
using namespace std;

int main(){
    
    // 1. 入力情報取得.
    int N, D, X, Y;
    scanf("%d %d %d %d", &N, &D, &X, &Y);
    
    // 2. 目的を達成できる確率は？
    // 2-1. X, Y が, D の倍数となる必要がありそう.
    if(X % D != 0 || Y % D != 0){
        printf("%d\n", 0);
        return 0;
    }
    
    // 2-2. X, Y を D で 割った後に, N との差分が, 奇数回なら, 目的達成できない.
    // test_131_18204705_-145637640_0.txt 等 の WA対応.
    X /= D, Y /= D;
    if((N - abs(X) - abs(Y)) % 2 != 0){
        printf("%d\n", 0);
        return 0;
    }
    
    // 2-3. 各移動方向の回数を確認.
    // X軸方向(+D) … r(回)
    // X軸方向(-D) … l(回)
    // Y軸方向(+D) … u(回)
    // Y軸方向(-D) … d(回)
    // -> 以下の条件が必要なはず.
    // D * (r - l) = X
    // D * (u - d) = Y
    // u + d + r + l = N
    // 
    // ex.
    // [入力例]
    // 11 8562174
    // 25686522 17124348
    // -> 各移動方向の回数は, 以下のようになる.
    // u  d  r  l  count
    // 5  3  3  0   9240
    // 4  2  4  1  34650
    // 3  1  5  2  27720
    // 2  0  6  3   4620
    // -----------------
    // 合計        76230 (通り)
    // -> 確率は, 76230 ÷ 4194304 (4 の 11乗) = 約 0.01817464828 と 計算できる.
    double ans = 0.0;
    int upper = (N - X - Y) / 2;
    for(int d = 0; d <= upper; d++){
        // u, d, r, l を 計算.
        int u = Y + d;
        int r = (N - u - d + X) / 2;
        int l = (N - u - d - X) / 2;
        // printf("u=%d d=%d r=%d l=%d\n", u, d, r, l);
        
        // 確率を集計.
        // N! / ( u! * d! * r! * l!) / (4 の N乗) を 加算.
        double part = 1.0;
        int base = N;
        for(int ui = 1; ui <= u; ui++) part *= (base * 1.0 / 4.0), part /= (ui + 0.0), base--;
        for(int di = 1; di <= d; di++) part *= (base * 1.0 / 4.0), part /= (di + 0.0), base--;
        for(int ri = 1; ri <= r; ri++) part *= (base * 1.0 / 4.0), part /= (ri + 0.0), base--;
        for(int li = 1; li <= l; li++) part *= (base * 1.0 / 4.0), part /= (li + 0.0), base--;
        ans += part;
    }
    
    // 3. 出力 ～ 後処理.
    printf("%.16f", ans);
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

int main(){

// 1. 入力情報取得.

int N, D, X, Y;

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

// 2. 目的を達成できる確率は？

// 2-1. X, Y が, D の倍数となる必要がありそう.

if(X % D != 0 || Y % D != 0){

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

return 0;

}

// 2-2. X, Y を D で割った後に, N との差分が, 奇数回なら, 目的達成できない.

// test_131_18204705_-145637640_0.txt 等の WA対応.

X /= D, Y /= D;

if((N - abs(X) - abs(Y)) % 2 != 0){

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

return 0;

}

// 2-3. 各移動方向の回数を確認.

// X軸方向(+D) … r(回)

// X軸方向(-D) … l(回)

// Y軸方向(+D) … u(回)

// Y軸方向(-D) … d(回)

// -> 以下の条件が必要なはず.

// D * (r - l) = X

// D * (u - d) = Y

// u + d + r + l = N

// ex.

// [入力例]

// 11 8562174

// 25686522 17124348

// -> 各移動方向の回数は, 以下のようになる.

// u d r l count

// 5 3 3 0 9240

// 4 2 4 1 34650

// 3 1 5 2 27720

// 2 0 6 3 4620

// -----------------

// 合計 76230 (通り)

// -> 確率は, 76230 ÷ 4194304 (4 の 11乗) = 約 0.01817464828 と計算できる.

double ans = 0.0;

int upper = (N - X - Y) / 2;

for(int d = 0; d <= upper; d++){

// u, d, r, l を計算.

int u = Y + d;

int r = (N - u - d + X) / 2;

int l = (N - u - d - X) / 2;

// printf("u=%d d=%d r=%d l=%d\n", u, d, r, l);

// 確率を集計.

// N! / ( u! * d! * r! * l!) / (4 の N乗) を加算.

double part = 1.0;

int base = N;

for(int ui = 1; ui <= u; ui++) part *= (base * 1.0 / 4.0), part /= (ui + 0.0), base--;

for(int di = 1; di <= d; di++) part *= (base * 1.0 / 4.0), part /= (di + 0.0), base--;

for(int ri = 1; ri <= r; ri++) part *= (base * 1.0 / 4.0), part /= (ri + 0.0), base--;

for(int li = 1; li <= l; li++) part *= (base * 1.0 / 4.0), part /= (li + 0.0), base--;

ans += part;

}

// 3. 出力～後処理.

printf("%.16f", ans);

return 0;

}

[入力例]
2 10000000
10000000 10000000

[出力例(debug版)]
u=1 d=0 r=1 l=0
0.1250000000000000
※AtCoderテストケースより

[入力例]
11 8562174
25686522 17124348

[出力例(debug版)]
u=2 d=0 r=6 l=3
u=3 d=1 r=5 l=2
u=4 d=2 r=4 l=1
u=5 d=3 r=3 l=0
0.0181746482849121
※AtCoderテストケースより

[入力例]
16 123456
617280 370368

[出力例(debug版)]
u=3 d=0 r=9 l=4
u=4 d=1 r=8 l=3
u=5 d=2 r=7 l=2
u=6 d=3 r=6 l=1
u=7 d=4 r=5 l=0
0.0048477202653885

[入力例]
45 12345
-246900 209865

[出力例(debug版)]
u=17 d=0 r=4 l=24
u=18 d=1 r=3 l=23
u=19 d=2 r=2 l=22
u=20 d=3 r=1 l=21
u=21 d=4 r=0 l=20
u=22 d=5 r=-1 l=19
u=23 d=6 r=-2 l=18
u=24 d=7 r=-3 l=17
u=25 d=8 r=-4 l=16
u=26 d=9 r=-5 l=15
u=27 d=10 r=-6 l=14
u=28 d=11 r=-7 l=13
u=29 d=12 r=-8 l=12
u=30 d=13 r=-9 l=11
u=31 d=14 r=-10 l=10
u=32 d=15 r=-11 l=9
u=33 d=16 r=-12 l=8
u=34 d=17 r=-13 l=7
u=35 d=18 r=-14 l=6
u=36 d=19 r=-15 l=5
u=37 d=20 r=-16 l=4
u=38 d=21 r=-17 l=3
u=39 d=22 r=-18 l=2
u=40 d=23 r=-19 l=1
u=41 d=24 r=-20 l=0
0.0000000004541866

[入力例]
51 123
1353 3936

[出力例(debug版)]
u=32 d=0 r=15 l=4
u=33 d=1 r=14 l=3
u=34 d=2 r=13 l=2
u=35 d=3 r=12 l=1
u=36 d=4 r=11 l=0
0.0000000000001572

[入力例]
7 123456789
246913578 370370367

[出力例(debug版)]
u=3 d=0 r=3 l=1
u=4 d=1 r=2 l=0
0.0149536132812500

[入力例]

2 10000000

10000000 10000000

[出力例(debug版)]

u=1 d=0 r=1 l=0

0.1250000000000000

※AtCoderテストケースより

[入力例]

11 8562174

25686522 17124348

[出力例(debug版)]

u=2 d=0 r=6 l=3

u=3 d=1 r=5 l=2

u=4 d=2 r=4 l=1

u=5 d=3 r=3 l=0

0.0181746482849121

※AtCoderテストケースより

[入力例]

16 123456

617280 370368

[出力例(debug版)]

u=3 d=0 r=9 l=4

u=4 d=1 r=8 l=3

u=5 d=2 r=7 l=2

u=6 d=3 r=6 l=1

u=7 d=4 r=5 l=0

0.0048477202653885

[入力例]

45 12345

-246900 209865

[出力例(debug版)]

u=17 d=0 r=4 l=24

u=18 d=1 r=3 l=23

u=19 d=2 r=2 l=22

u=20 d=3 r=1 l=21

u=21 d=4 r=0 l=20

u=22 d=5 r=-1 l=19

u=23 d=6 r=-2 l=18

u=24 d=7 r=-3 l=17

u=25 d=8 r=-4 l=16

u=26 d=9 r=-5 l=15

u=27 d=10 r=-6 l=14

u=28 d=11 r=-7 l=13

u=29 d=12 r=-8 l=12

u=30 d=13 r=-9 l=11

u=31 d=14 r=-10 l=10

u=32 d=15 r=-11 l=9

u=33 d=16 r=-12 l=8

u=34 d=17 r=-13 l=7

u=35 d=18 r=-14 l=6

u=36 d=19 r=-15 l=5

u=37 d=20 r=-16 l=4

u=38 d=21 r=-17 l=3

u=39 d=22 r=-18 l=2

u=40 d=23 r=-19 l=1

u=41 d=24 r=-20 l=0

0.0000000004541866

[入力例]

51 123

1353 3936

[出力例(debug版)]

u=32 d=0 r=15 l=4

u=33 d=1 r=14 l=3

u=34 d=2 r=13 l=2

u=35 d=3 r=12 l=1

u=36 d=4 r=11 l=0

0.0000000000001572

[入力例]

7 123456789

246913578 370370367

[出力例(debug版)]

u=3 d=0 r=3 l=1

u=4 d=1 r=2 l=0

0.0149536132812500

■参照サイト
AtCoder Beginner Contest 011

2019年8月6日2019年8月6日

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

C++の練習を兼ねて, AtCoder Beginner Contest 136 の問題E (E – Max GCD) を解いてみた.

■感想.
1. 操作を行っても, 和が変化しないこと, 及び, 答えの候補が, 和の約数であることまで, 予想出来たが, 具体的に, その後の処理が見えなかったので, 解答を参考に, 復習した.
2. 解説の方法で, 答えを見つけられることが, 非常に不思議に感じたものの, r の和が d の倍数となる性質を使っていることで, なるほどと感心した.

本家のサイトABC 136解説をご覧下さい.

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

// 解き直し.
// ABC 136解説
// https://img.atcoder.jp/abc136/editorial.pdf
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int N;
LL K, S, A[505], G;

// 与えられた正の整数のすべての約数を抽出.
// @param X: 約数を抽出したい正の整数.
// @return ret: すべての約数.
vector<LL> div(LL X){
    vector<LL> ret;
    ret.push_back(1);
    for(LL d = 2; d * d <= X; d++){
        if(X % d == 0){
            ret.push_back(d);
            if(d * d != X) ret.push_back(X / d);
        }
    }
    ret.push_back(X);
    sort(ret.begin(), ret.end());
    return ret;
}

int main(){

    // 1. 入力情報取得.
    scanf("%d %llu", &N, &K);
    for(int i = 0; i < N; i++){
        scanf("%llu", &A[i]);
        S += A[i];
        if(i == 0) G = A[i];
        else       G = __gcd(G, A[i]);
    }
    
    // 2. 解説通り.
    // S の 約数 を 計算.
    vector<LL> divisors = div(S);
    
    // 3. 各約数について, 操作の回数を計算.
    LL ans = G;
    for(auto &d : divisors){
        // 3-1. 各 A[i] を d で 割った余り を 確認.
        priority_queue<LL> r;
        for(int i = 0; i < N; i++) if(A[i] % d != 0) r.push(A[i] % d);
        
        // 3-2. d を 正にするもの, 負にするもの を 集計.
        int l = r.size();
        LL dPlus[l], dMinus[l];
        int index = 0;
        while(!r.empty()){
            // 余りを取得.
            LL v = r.top();
            r.pop();
            
            // d を 正 にする.
            dPlus[l - index - 1]  = d - v;
            // d を 負 にする.
            dMinus[l - index - 1] = -v;
            
            // index を increment.
            index++;
        }
        
        // 3-3. 前項で集計した結果の累積和を計算.
        // d を 正 にする.
        LL pCum[l];
        pCum[l - 1] = dPlus[l - 1];
        for(int i = l - 2; i >= 0; i--) pCum[i] = pCum[i + 1] + dPlus[i];
        
        // d を 負 にする.
        LL mCum[l];
        mCum[0] = dMinus[0];
        for(int i = 1; i < l; i++) mCum[i] = mCum[i - 1] + dMinus[i];
        
        // 3-4. 前項の累積和から, 操作回数が, K回以内で実現できるかをチェック.
        for(int i = 0; i < l - 1; i++){
            if(pCum[i + 1] + mCum[i] == 0 && pCum[i + 1] <= K){
                // 操作後の A の 全要素を割り切る正の整数について, 最大値を更新.
                ans = max(ans, d);
                break;
            }
        }
    }
    
    // 4. 出力 ～ 後処理.
    printf("%llu", ans);
    return 0;

}

// 解き直し.

// ABC 136解説

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

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

int N;

LL K, S, A[505], G;

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

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

// @return ret: すべての約数.

vector<LL> div(LL X){

vector<LL> ret;

ret.push_back(1);

for(LL d = 2; d * d <= X; d++){

if(X % d == 0){

ret.push_back(d);

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

}

ret.push_back(X);

sort(ret.begin(), ret.end());

return ret;

}

int main(){

// 1. 入力情報取得.

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

for(int i = 0; i < N; i++){

scanf("%llu", &A[i]);

S += A[i];

if(i == 0) G = A[i];

else G = __gcd(G, A[i]);

}

// 2. 解説通り.

// S の約数を計算.

vector<LL> divisors = div(S);

// 3. 各約数について, 操作の回数を計算.

LL ans = G;

for(auto &d : divisors){

// 3-1. 各 A[i] を d で割った余りを確認.

priority_queue<LL> r;

for(int i = 0; i < N; i++) if(A[i] % d != 0) r.push(A[i] % d);

// 3-2. d を正にするもの, 負にするものを集計.

int l = r.size();

LL dPlus[l], dMinus[l];

int index = 0;

while(!r.empty()){

// 余りを取得.

LL v = r.top();

r.pop();

// d を正にする.

dPlus[l - index - 1] = d - v;

// d を負にする.

dMinus[l - index - 1] = -v;

// index を increment.

index++;

}

// 3-3. 前項で集計した結果の累積和を計算.

// d を正にする.

LL pCum[l];

pCum[l - 1] = dPlus[l - 1];

for(int i = l - 2; i >= 0; i--) pCum[i] = pCum[i + 1] + dPlus[i];

// d を負にする.

LL mCum[l];

mCum[0] = dMinus[0];

for(int i = 1; i < l; i++) mCum[i] = mCum[i - 1] + dMinus[i];

// 3-4. 前項の累積和から, 操作回数が, K回以内で実現できるかをチェック.

for(int i = 0; i < l - 1; i++){

if(pCum[i + 1] + mCum[i] == 0 && pCum[i + 1] <= K){

// 操作後の A の全要素を割り切る正の整数について, 最大値を更新.

ans = max(ans, d);

break;

}

// 4. 出力～後処理.

printf("%llu", ans);

return 0;

}

[入力例]
2 3
8 20

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

[入力例]
2 10
3 5

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

[入力例]
4 5
10 1 2 22

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

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

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

[入力例]
5 0
5 15 35 45 75

[出力例]
5

[入力例]
5 1
3 6 9 12 18

[出力例]
3

[入力例]
2 1
3 5

[出力例]
4

[入力例]
500 123456789
11 22 33 44 55 66 77 88 99 110 121 132 143 154 165 176 187 198 209 220 231 242 253 264 275 286 297 308 319 330 341 352 363 374 385 396 407 418 429 440 451 462 473 484 495 506 517 528 539 550 561 572 583 594 605 616 627 638 649 660 671 682 693 704 715 726 737 748 759 770 781 792 803 814 825 836 847 858 869 880 891 902 913 924 935 946 957 968 979 990 1001 1012 1023 1034 1045 1056 1067 1078 1089 1100 1111 1122 1133 1144 1155 1166 1177 1188 1199 1210 1221 1232 1243 1254 1265 1276 1287 1298 1309 1320 1331 1342 1353 1364 1375 1386 1397 1408 1419 1430 1441 1452 1463 1474 1485 1496 1507 1518 1529 1540 1551 1562 1573 1584 1595 1606 1617 1628 1639 1650 1661 1672 1683 1694 1705 1716 1727 1738 1749 1760 1771 1782 1793 1804 1815 1826 1837 1848 1859 1870 1881 1892 1903 1914 1925 1936 1947 1958 1969 1980 1991 2002 2013 2024 2035 2046 2057 2068 2079 2090 2101 2112 2123 2134 2145 2156 2167 2178 2189 2200 2211 2222 2233 2244 2255 2266 2277 2288 2299 2310 2321 2332 2343 2354 2365 2376 2387 2398 2409 2420 2431 2442 2453 2464 2475 2486 2497 2508 2519 2530 2541 2552 2563 2574 2585 2596 2607 2618 2629 2640 2651 2662 2673 2684 2695 2706 2717 2728 2739 2750 2761 2772 2783 2794 2805 2816 2827 2838 2849 2860 2871 2882 2893 2904 2915 2926 2937 2948 2959 2970 2981 2992 3003 3014 3025 3036 3047 3058 3069 3080 3091 3102 3113 3124 3135 3146 3157 3168 3179 3190 3201 3212 3223 3234 3245 3256 3267 3278 3289 3300 3311 3322 3333 3344 3355 3366 3377 3388 3399 3410 3421 3432 3443 3454 3465 3476 3487 3498 3509 3520 3531 3542 3553 3564 3575 3586 3597 3608 3619 3630 3641 3652 3663 3674 3685 3696 3707 3718 3729 3740 3751 3762 3773 3784 3795 3806 3817 3828 3839 3850 3861 3872 3883 3894 3905 3916 3927 3938 3949 3960 3971 3982 3993 4004 4015 4026 4037 4048 4059 4070 4081 4092 4103 4114 4125 4136 4147 4158 4169 4180 4191 4202 4213 4224 4235 4246 4257 4268 4279 4290 4301 4312 4323 4334 4345 4356 4367 4378 4389 4400 4411 4422 4433 4444 4455 4466 4477 4488 4499 4510 4521 4532 4543 4554 4565 4576 4587 4598 4609 4620 4631 4642 4653 4664 4675 4686 4697 4708 4719 4730 4741 4752 4763 4774 4785 4796 4807 4818 4829 4840 4851 4862 4873 4884 4895 4906 4917 4928 4939 4950 4961 4972 4983 4994 5005 5016 5027 5038 5049 5060 5071 5082 5093 5104 5115 5126 5137 5148 5159 5170 5181 5192 5203 5214 5225 5236 5247 5258 5269 5280 5291 5302 5313 5324 5335 5346 5357 5368 5379 5390 5401 5412 5423 5434 5445 5456 5467 5478 5489 5500
[出力例]
1377750

[入力例]
500 987654321
1001 2002 3003 4004 5005 6006 7007 8008 9009 10010 11011 12012 13013 14014 15015 16016 17017 18018 19019 20020 21021 22022 23023 24024 25025 26026 27027 28028 29029 30030 31031 32032 33033 34034 35035 36036 37037 38038 39039 40040 41041 42042 43043 44044 45045 46046 47047 48048 49049 50050 51051 52052 53053 54054 55055 56056 57057 58058 59059 60060 61061 62062 63063 64064 65065 66066 67067 68068 69069 70070 71071 72072 73073 74074 75075 76076 77077 78078 79079 80080 81081 82082 83083 84084 85085 86086 87087 88088 89089 90090 91091 92092 93093 94094 95095 96096 97097 98098 99099 100100 101101 102102 103103 104104 105105 106106 107107 108108 109109 110110 111111 112112 113113 114114 115115 116116 117117 118118 119119 120120 121121 122122 123123 124124 125125 126126 127127 128128 129129 130130 131131 132132 133133 134134 135135 136136 137137 138138 139139 140140 141141 142142 143143 144144 145145 146146 147147 148148 149149 150150 151151 152152 153153 154154 155155 156156 157157 158158 159159 160160 161161 162162 163163 164164 165165 166166 167167 168168 169169 170170 171171 172172 173173 174174 175175 176176 177177 178178 179179 180180 181181 182182 183183 184184 185185 186186 187187 188188 189189 190190 191191 192192 193193 194194 195195 196196 197197 198198 199199 200200 201201 202202 203203 204204 205205 206206 207207 208208 209209 210210 211211 212212 213213 214214 215215 216216 217217 218218 219219 220220 221221 222222 223223 224224 225225 226226 227227 228228 229229 230230 231231 232232 233233 234234 235235 236236 237237 238238 239239 240240 241241 242242 243243 244244 245245 246246 247247 248248 249249 250250 251251 252252 253253 254254 255255 256256 257257 258258 259259 260260 261261 262262 263263 264264 265265 266266 267267 268268 269269 270270 271271 272272 273273 274274 275275 276276 277277 278278 279279 280280 281281 282282 283283 284284 285285 286286 287287 288288 289289 290290 291291 292292 293293 294294 295295 296296 297297 298298 299299 300300 301301 302302 303303 304304 305305 306306 307307 308308 309309 310310 311311 312312 313313 314314 315315 316316 317317 318318 319319 320320 321321 322322 323323 324324 325325 326326 327327 328328 329329 330330 331331 332332 333333 334334 335335 336336 337337 338338 339339 340340 341341 342342 343343 344344 345345 346346 347347 348348 349349 350350 351351 352352 353353 354354 355355 356356 357357 358358 359359 360360 361361 362362 363363 364364 365365 366366 367367 368368 369369 370370 371371 372372 373373 374374 375375 376376 377377 378378 379379 380380 381381 382382 383383 384384 385385 386386 387387 388388 389389 390390 391391 392392 393393 394394 395395 396396 397397 398398 399399 400400 401401 402402 403403 404404 405405 406406 407407 408408 409409 410410 411411 412412 413413 414414 415415 416416 417417 418418 419419 420420 421421 422422 423423 424424 425425 426426 427427 428428 429429 430430 431431 432432 433433 434434 435435 436436 437437 438438 439439 440440 441441 442442 443443 444444 445445 446446 447447 448448 449449 450450 451451 452452 453453 454454 455455 456456 457457 458458 459459 460460 461461 462462 463463 464464 465465 466466 467467 468468 469469 470470 471471 472472 473473 474474 475475 476476 477477 478478 479479 480480 481481 482482 483483 484484 485485 486486 487487 488488 489489 490490 491491 492492 493493 494494 495495 496496 497497 498498 499499 500500

[出力例]
125375250

[入力例]

2 3

8 20

[出力例]

※AtCoderテストケースより

[入力例]

2 10

3 5

[出力例]

※AtCoderテストケースより

[入力例]

4 5

10 1 2 22

[出力例]

※AtCoderテストケースより

[入力例]

8 7

1 7 5 6 8 2 6 5

[出力例]

※AtCoderテストケースより

[入力例]

5 0

5 15 35 45 75

[出力例]

[入力例]

5 1

3 6 9 12 18

[出力例]

[入力例]

2 1

3 5

[出力例]

[入力例]

500 123456789

11 22 33 44 55 66 77 88 99 110 121 132 143 154 165 176 187 198 209 220 231 242 253 264 275 286 297 308 319 330 341 352 363 374 385 396 407 418 429 440 451 462 473 484 495 506 517 528 539 550 561 572 583 594 605 616 627 638 649 660 671 682 693 704 715 726 737 748 759 770 781 792 803 814 825 836 847 858 869 880 891 902 913 924 935 946 957 968 979 990 1001 1012 1023 1034 1045 1056 1067 1078 1089 1100 1111 1122 1133 1144 1155 1166 1177 1188 1199 1210 1221 1232 1243 1254 1265 1276 1287 1298 1309 1320 1331 1342 1353 1364 1375 1386 1397 1408 1419 1430 1441 1452 1463 1474 1485 1496 1507 1518 1529 1540 1551 1562 1573 1584 1595 1606 1617 1628 1639 1650 1661 1672 1683 1694 1705 1716 1727 1738 1749 1760 1771 1782 1793 1804 1815 1826 1837 1848 1859 1870 1881 1892 1903 1914 1925 1936 1947 1958 1969 1980 1991 2002 2013 2024 2035 2046 2057 2068 2079 2090 2101 2112 2123 2134 2145 2156 2167 2178 2189 2200 2211 2222 2233 2244 2255 2266 2277 2288 2299 2310 2321 2332 2343 2354 2365 2376 2387 2398 2409 2420 2431 2442 2453 2464 2475 2486 2497 2508 2519 2530 2541 2552 2563 2574 2585 2596 2607 2618 2629 2640 2651 2662 2673 2684 2695 2706 2717 2728 2739 2750 2761 2772 2783 2794 2805 2816 2827 2838 2849 2860 2871 2882 2893 2904 2915 2926 2937 2948 2959 2970 2981 2992 3003 3014 3025 3036 3047 3058 3069 3080 3091 3102 3113 3124 3135 3146 3157 3168 3179 3190 3201 3212 3223 3234 3245 3256 3267 3278 3289 3300 3311 3322 3333 3344 3355 3366 3377 3388 3399 3410 3421 3432 3443 3454 3465 3476 3487 3498 3509 3520 3531 3542 3553 3564 3575 3586 3597 3608 3619 3630 3641 3652 3663 3674 3685 3696 3707 3718 3729 3740 3751 3762 3773 3784 3795 3806 3817 3828 3839 3850 3861 3872 3883 3894 3905 3916 3927 3938 3949 3960 3971 3982 3993 4004 4015 4026 4037 4048 4059 4070 4081 4092 4103 4114 4125 4136 4147 4158 4169 4180 4191 4202 4213 4224 4235 4246 4257 4268 4279 4290 4301 4312 4323 4334 4345 4356 4367 4378 4389 4400 4411 4422 4433 4444 4455 4466 4477 4488 4499 4510 4521 4532 4543 4554 4565 4576 4587 4598 4609 4620 4631 4642 4653 4664 4675 4686 4697 4708 4719 4730 4741 4752 4763 4774 4785 4796 4807 4818 4829 4840 4851 4862 4873 4884 4895 4906 4917 4928 4939 4950 4961 4972 4983 4994 5005 5016 5027 5038 5049 5060 5071 5082 5093 5104 5115 5126 5137 5148 5159 5170 5181 5192 5203 5214 5225 5236 5247 5258 5269 5280 5291 5302 5313 5324 5335 5346 5357 5368 5379 5390 5401 5412 5423 5434 5445 5456 5467 5478 5489 5500

[出力例]

1377750

[入力例]

500 987654321

1001 2002 3003 4004 5005 6006 7007 8008 9009 10010 11011 12012 13013 14014 15015 16016 17017 18018 19019 20020 21021 22022 23023 24024 25025 26026 27027 28028 29029 30030 31031 32032 33033 34034 35035 36036 37037 38038 39039 40040 41041 42042 43043 44044 45045 46046 47047 48048 49049 50050 51051 52052 53053 54054 55055 56056 57057 58058 59059 60060 61061 62062 63063 64064 65065 66066 67067 68068 69069 70070 71071 72072 73073 74074 75075 76076 77077 78078 79079 80080 81081 82082 83083 84084 85085 86086 87087 88088 89089 90090 91091 92092 93093 94094 95095 96096 97097 98098 99099 100100 101101 102102 103103 104104 105105 106106 107107 108108 109109 110110 111111 112112 113113 114114 115115 116116 117117 118118 119119 120120 121121 122122 123123 124124 125125 126126 127127 128128 129129 130130 131131 132132 133133 134134 135135 136136 137137 138138 139139 140140 141141 142142 143143 144144 145145 146146 147147 148148 149149 150150 151151 152152 153153 154154 155155 156156 157157 158158 159159 160160 161161 162162 163163 164164 165165 166166 167167 168168 169169 170170 171171 172172 173173 174174 175175 176176 177177 178178 179179 180180 181181 182182 183183 184184 185185 186186 187187 188188 189189 190190 191191 192192 193193 194194 195195 196196 197197 198198 199199 200200 201201 202202 203203 204204 205205 206206 207207 208208 209209 210210 211211 212212 213213 214214 215215 216216 217217 218218 219219 220220 221221 222222 223223 224224 225225 226226 227227 228228 229229 230230 231231 232232 233233 234234 235235 236236 237237 238238 239239 240240 241241 242242 243243 244244 245245 246246 247247 248248 249249 250250 251251 252252 253253 254254 255255 256256 257257 258258 259259 260260 261261 262262 263263 264264 265265 266266 267267 268268 269269 270270 271271 272272 273273 274274 275275 276276 277277 278278 279279 280280 281281 282282 283283 284284 285285 286286 287287 288288 289289 290290 291291 292292 293293 294294 295295 296296 297297 298298 299299 300300 301301 302302 303303 304304 305305 306306 307307 308308 309309 310310 311311 312312 313313 314314 315315 316316 317317 318318 319319 320320 321321 322322 323323 324324 325325 326326 327327 328328 329329 330330 331331 332332 333333 334334 335335 336336 337337 338338 339339 340340 341341 342342 343343 344344 345345 346346 347347 348348 349349 350350 351351 352352 353353 354354 355355 356356 357357 358358 359359 360360 361361 362362 363363 364364 365365 366366 367367 368368 369369 370370 371371 372372 373373 374374 375375 376376 377377 378378 379379 380380 381381 382382 383383 384384 385385 386386 387387 388388 389389 390390 391391 392392 393393 394394 395395 396396 397397 398398 399399 400400 401401 402402 403403 404404 405405 406406 407407 408408 409409 410410 411411 412412 413413 414414 415415 416416 417417 418418 419419 420420 421421 422422 423423 424424 425425 426426 427427 428428 429429 430430 431431 432432 433433 434434 435435 436436 437437 438438 439439 440440 441441 442442 443443 444444 445445 446446 447447 448448 449449 450450 451451 452452 453453 454454 455455 456456 457457 458458 459459 460460 461461 462462 463463 464464 465465 466466 467467 468468 469469 470470 471471 472472 473473 474474 475475 476476 477477 478478 479479 480480 481481 482482 483483 484484 485485 486486 487487 488488 489489 490490 491491 492492 493493 494494 495495 496496 497497 498498 499499 500500

[出力例]

125375250

■参照サイト
AtCoder Beginner Contest 136

2019年8月5日2019年8月6日

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

C++の練習を兼ねて, AtCoder Beginner Contest 136 の問題D (D – Gathering Children) を解いてみた.

■感想.
1. 解答を見る前に, 解けたので, 及第点取れたと思う.
2. 1グーゴル(巨大な偶数)回後の位置を, 初期位置のマスの文字(及び位置) と方向転換するマスの位置との関係から, 偶奇に場合分けして把握できたので, 良かったと思う.

本家のサイトABC 136解説をご覧下さい.

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

#include <bits/stdc++.h>
using namespace std;
const int MAX = 123321;
char S[MAX];
int nextL[MAX], nextR[MAX], goal[MAX], ans[MAX];

int main(){

    // 1. 入力情報取得.
    scanf("%s", S);
    int l = strlen(S);
    
    // 2. 各初期位置について, 以下の情報を保存(0-index).
    // 2-1. 初期位置に, 'R' が記載されていたとして, 次に, 'L' が 始めて出現するケース.
    int posL = -1;
    for(int i = l - 1; i >= 0; i--){
        if(S[i] == 'L') posL = i;
        nextL[i] = posL;
    }
    
    // 2-2. 初期位置に, 'L' が記載されていたとして, 次に, 'R' が 始めて出現するケース.
    int posR = -1;
    for(int i = 0; i < l; i++){
        if(S[i] == 'R') posR = i;
        nextR[i] = posR;
    }
    
    // 3. 各マスについて, 1グーゴル回後の位置を計算.
    // 初期位置が, 'R' or 'L' で 分岐.
    for(int i = 0; i < l; i++){
        if(S[i] == 'R'){
            int dist = nextL[i] - i;
            if(dist % 2 == 0) goal[i] = nextL[i];
            else              goal[i] = nextL[i] - 1;
        }
        if(S[i] == 'L'){
            int dist = i - nextR[i];
            if(dist % 2 == 0) goal[i] = nextR[i];
            else              goal[i] = nextR[i] + 1;
        }
    }
    
    // 4. 移動後の位置情報が, goalに保存されているので集計.
    for(int i = 0; i < l; i++) ans[goal[i]]++;
    
    // 5. 出力 ～ 後処理.
    for(int i = 0; i < l; i++) printf("%d ", ans[i]);
    return 0;

}

#include <bits/stdc++.h>

using namespace std;

const int MAX = 123321;

char S[MAX];

int nextL[MAX], nextR[MAX], goal[MAX], ans[MAX];

int main(){

// 1. 入力情報取得.

scanf("%s", S);

int l = strlen(S);

// 2. 各初期位置について, 以下の情報を保存(0-index).

// 2-1. 初期位置に, 'R' が記載されていたとして, 次に, 'L' が始めて出現するケース.

int posL = -1;

for(int i = l - 1; i >= 0; i--){

if(S[i] == 'L') posL = i;

nextL[i] = posL;

}

// 2-2. 初期位置に, 'L' が記載されていたとして, 次に, 'R' が始めて出現するケース.

int posR = -1;

for(int i = 0; i < l; i++){

if(S[i] == 'R') posR = i;

nextR[i] = posR;

}

// 3. 各マスについて, 1グーゴル回後の位置を計算.

// 初期位置が, 'R' or 'L' で分岐.

for(int i = 0; i < l; i++){

if(S[i] == 'R'){

int dist = nextL[i] - i;

if(dist % 2 == 0) goal[i] = nextL[i];

else goal[i] = nextL[i] - 1;

}

if(S[i] == 'L'){

int dist = i - nextR[i];

if(dist % 2 == 0) goal[i] = nextR[i];

else goal[i] = nextR[i] + 1;

}

// 4. 移動後の位置情報が, goalに保存されているので集計.

for(int i = 0; i < l; i++) ans[goal[i]]++;

// 5. 出力～後処理.

for(int i = 0; i < l; i++) printf("%d ", ans[i]);

return 0;

}

[入力例]
RRLRL

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

[入力例]
RRLLLLRLRRLL

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

[入力例]
RRRLLRLLRRRLLLLL

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

[入力例]
RLRRLLRRRLLLRRRRLLLLRRRRRLLLLLRRRRRRLLLLLLRRRRRRRLLLLLLLRRRRRRRRLLLLLLLLRRRRRRRRRLLLLLLLLLRRRRRRRRRRLLLLLLLLLL

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

[入力例]

RRLRL

[出力例]

0 1 2 1 1

※AtCoderテストケースより

[入力例]

RRLLLLRLRRLL

[出力例]

0 3 3 0 0 0 1 1 0 2 2 0

※AtCoderテストケースより

[入力例]

RRRLLRLLRRRLLLLL

[出力例]

0 0 3 2 0 2 1 0 0 0 4 4 0 0 0 0

※AtCoderテストケースより

[入力例]

RLRRLLRRRLLLRRRRLLLLRRRRRLLLLLRRRRRRLLLLLLRRRRRRRLLLLLLLRRRRRRRRLLLLLLLLRRRRRRRRRLLLLLLLLLRRRRRRRRRRLLLLLLLLLL

[出力例]

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

■参照サイト
AtCoder Beginner Contest 136

2019年8月4日

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

C++の練習を兼ねて, AtCoder Regular Contest 098 の問題D (D – Xor Sum 2) を解いてみた.

■感想.
1. 解答方針が, 全く見えなかったので, 解答を参照して, 解答を組み立てた.
2. 尺取り法の訓練が出来たので良かったと思う.
3. 条件を満たす整数の組(l, r) が見つかった毎に, (r – l + 1) を加算する必要があることに気付けたのが, 良かったと思う.

本家のサイトAtcoderRegularContest解説をご覧下さい.

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

// 解き直し.
// AtcoderRegularContest解説
// https://img.atcoder.jp/arc098/editorial.pdf
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
LL A[200002], CUM[200002], XOR[200002];

int main(){

    // 1. 入力情報取得.
    int N;
    scanf("%d", &N);
    for(int i = 1; i <= N; i++){
        scanf("%lld", &A[i]);
        CUM[i] = CUM[i - 1] + A[i];
        XOR[i] = XOR[i - 1] ^ A[i];
    }
    
    // 2. 解説通り.
    // 条件を満たす 整数の組(l, r) の 個数 を計算(※尺取り法っぽいロジックを使えるとのこと).
    LL ans = 0;
    int l = 1, r = 1;
    int counter = 0;
    while(l <= N){
        while(r <= N){
            // 2-1. 整数の組(l, r) に 対応する和, 排他的論理和を取得.
            LL Add = CUM[r] - CUM[l - 1];
            LL Xor = XOR[r] ^ XOR[l - 1]; // 変数名: xor だと, Compile error となった.
            
            // 2-2. 条件を満たすか確認.
            if(Add == Xor) ans += (r - l + 1);
            else           break;
            
            // 2-3. r を increment.
            r++;
            
            // 2-4. debug用.
            counter++;
            if(counter > 200002) break;
            
        }
        
        // 2-5. l を increment.
        l++;
        
    }
    
    // 3. 出力 ～ 後処理.
    printf("%lld\n", ans);
    return 0;

}

// 解き直し.

// AtcoderRegularContest解説

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

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

LL A[200002], CUM[200002], XOR[200002];

int main(){

// 1. 入力情報取得.

int N;

scanf("%d", &N);

for(int i = 1; i <= N; i++){

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

CUM[i] = CUM[i - 1] + A[i];

XOR[i] = XOR[i - 1] ^ A[i];

}

// 2. 解説通り.

// 条件を満たす整数の組(l, r) の個数を計算(※尺取り法っぽいロジックを使えるとのこと).

LL ans = 0;

int l = 1, r = 1;

int counter = 0;

while(l <= N){

while(r <= N){

// 2-1. 整数の組(l, r) に対応する和, 排他的論理和を取得.

LL Add = CUM[r] - CUM[l - 1];

LL Xor = XOR[r] ^ XOR[l - 1]; // 変数名: xor だと, Compile error となった.

// 2-2. 条件を満たすか確認.

if(Add == Xor) ans += (r - l + 1);

else break;

// 2-3. r を increment.

r++;

// 2-4. debug用.

counter++;

if(counter > 200002) break;

}

// 2-5. l を increment.

l++;

}

// 3. 出力～後処理.

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

return 0;

}

[入力例]
4
2 5 4 6

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

[入力例]
9
0 0 0 0 0 0 0 0 0

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

[入力例]
19
885 8 1 128 83 32 256 206 639 16 4 128 689 32 8 64 885 969 1

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

[入力例]
300
271 208 520 930 131 375 957 254 643 153 354 646 801 37 233 597 490 859 519 780 924 504 718 996 843 98 723 948 515 994 409 23 936 868 113 916 257 997 279 453 396 955 441 705 974 231 735 279 150 747 183 669 234 787 304 800 558 327 379 505 715 394 333 86 894 188 637 2 584 726 527 128 836 713 648 361 906 338 250 343 62 148 662 901 166 440 963 534 505 88 307 127 98 261 623 914 794 905 45 182 442 711 205 964 40 779 125 531 273 58 96 396 333 845 551 198 231 858 332 515 17 21 607 837 706 953 715 613 796 725 212 857 926 85 395 812 954 684 924 801 351 711 315 618 209 384 648 492 260 500 305 150 60 848 834 269 603 760 915 732 652 368 313 86 150 8 37 282 237 942 242 866 362 597 859 315 474 192 998 897 882 969 480 638 336 202 960 52 101 16 862 883 523 701 826 119 682 488 344 73 937 306 403 692 982 654 265 684 664 490 640 88 476 650 943 997 190 87 275 437 47 452 791 900 97 1 230 900 571 288 202 833 679 106 493 741 733 452 980 455 497 846 57 488 645 413 826 291 766 680 555 758 596 36 622 623 271 902 233 414 889 815 246 169 197 945 436 342 68 896 742 322 720 345 439 656 377 714 995 291 381 944 522 426 285 980 454 241 521 449 854 595 710 103 554 634 76 760 451 526

[出力例]
323

[入力例]

2 5 4 6

[出力例]

※AtCoderテストケースより

[入力例]

0 0 0 0 0 0 0 0 0

[出力例]

※AtCoderテストケースより

[入力例]

885 8 1 128 83 32 256 206 639 16 4 128 689 32 8 64 885 969 1

[出力例]

※AtCoderテストケースより

[入力例]

300

271 208 520 930 131 375 957 254 643 153 354 646 801 37 233 597 490 859 519 780 924 504 718 996 843 98 723 948 515 994 409 23 936 868 113 916 257 997 279 453 396 955 441 705 974 231 735 279 150 747 183 669 234 787 304 800 558 327 379 505 715 394 333 86 894 188 637 2 584 726 527 128 836 713 648 361 906 338 250 343 62 148 662 901 166 440 963 534 505 88 307 127 98 261 623 914 794 905 45 182 442 711 205 964 40 779 125 531 273 58 96 396 333 845 551 198 231 858 332 515 17 21 607 837 706 953 715 613 796 725 212 857 926 85 395 812 954 684 924 801 351 711 315 618 209 384 648 492 260 500 305 150 60 848 834 269 603 760 915 732 652 368 313 86 150 8 37 282 237 942 242 866 362 597 859 315 474 192 998 897 882 969 480 638 336 202 960 52 101 16 862 883 523 701 826 119 682 488 344 73 937 306 403 692 982 654 265 684 664 490 640 88 476 650 943 997 190 87 275 437 47 452 791 900 97 1 230 900 571 288 202 833 679 106 493 741 733 452 980 455 497 846 57 488 645 413 826 291 766 680 555 758 596 36 622 623 271 902 233 414 889 815 246 169 197 945 436 342 68 896 742 322 720 345 439 656 377 714 995 291 381 944 522 426 285 980 454 241 521 449 854 595 710 103 554 634 76 760 451 526

[出力例]

323

■参照サイト
AtCoder Regular Contest 098

C++の練習を兼ねて, AtCoder Beginner Contest 138 の 問題E (E – Strings of Impurity) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 138 の 問題D (D – Ki) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 019 の 問題C (C – 高橋くんと魔法の箱) ～ 問題D (D – 高橋くんと木の直径) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 014 の 問題C (C – AtColor) ～ 問題D (D – 閉路) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 137 の 問題D (D – Summer Vacation) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 012 の 問題D (D – バスと避けられない運命) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 011 の 問題C (C – 123引き算) ～ 問題D (D – 大ジャンプ) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 136 の 問題E (E – Max GCD) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 136 の 問題D (D – Gathering Children) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 098 の 問題D (D – Xor Sum 2) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 138 の問題E (E – Strings of Impurity) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 138 の問題D (D – Ki) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 019 の問題C (C – 高橋くんと魔法の箱) ～問題D (D – 高橋くんと木の直径) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 014 の問題C (C – AtColor) ～問題D (D – 閉路) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 137 の問題D (D – Summer Vacation) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 012 の問題D (D – バスと避けられない運命) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 011 の問題C (C – 123引き算) ～問題D (D – 大ジャンプ) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 136 の問題E (E – Max GCD) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 136 の問題D (D – Gathering Children) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 098 の問題D (D – Xor Sum 2) を解いてみた.