個人用メモ帳

2021年4月23日2022年9月4日

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

C++の練習を兼ねて, AtCoder Grand Contest 027 の問題C (ABland Yard) を解いてみた.

■感想.
1. 問題Cは, 解答方針が見えなかったので, 解説を参考に実装して, ようやく, AC版に到達できた.
2. 文字列が作れるかどうかを, グラフの性質に基づいて解いていく部分が, 個人的には, 非常に面白い問題に感じた.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/agc027/editorial.pdf
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
set<int> G[202020];
int info[202020][3]; // 第一成分: 'A' の 個数, 第二成分: 'B' の 個数, 第三成分: 'A', 'B' の 種類数.

int main(){
    
    // 1. 入力情報.
    int N, M;
    char s[202020];
    scanf("%d %d %s", &N, &M, s);
    rep(i, M){
        int a, b;
        scanf("%d %d", &a, &b);
        a--, b--;
        G[a].insert(b);
        G[b].insert(a);
    }
    
    // 2. 各頂点ごとに, 'A', 'B' の 個数 を 保存.
    rep(i, N){
        // 2-1. 頂点 i の隣接頂点を確認して, 'A', 'B' の個数 を カウント.
        for(auto &v : G[i]){
            if(s[v] == 'A') info[i][0]++;
            if(s[v] == 'B') info[i][1]++;
        }
        
        // 2-2. 'A', 'B' が, 1個以上ある場合に, 種類数 を インクリメント.
        if(info[i][0]) info[i][2]++;
        if(info[i][1]) info[i][2]++;
    }
    
    // 3. 頂点(種類数 1) を 保存.
    queue<int> q;
    rep(i, N) if(info[i][2] == 1) q.push(i);
    
    // 4. グラフから, 種類数が, 1以下 の 頂点 を取り除いていく.
    while(!q.empty()){
        // 4-1. 頂点 u に 関する情報を取得.
        int u = q.front();
        q.pop();
        int lu = s[u] - 'A';
        
        // 4-2. 種類数 を 確認.
        if(!info[u][2]) continue;
        
        // 4-3. 取り出した要素を処理.
        for(auto &v : G[u]){
            // 4-4. 種類数 を 確認.
            if(!info[v][2]) continue;
            
            // 4-5. u, v が 等しい場合.
            if(u == v){
                info[u][lu]--;
                continue;
            }
            
            // 4-6. G[v] から, u を 取り除く.
            int lv = s[v] - 'A';
            G[v].erase(u);
            info[u][lv]--;
            info[v][lu]--;
            
            // 4-7. 種類数が, 1 の場合に, 追加.
            if((info[v][0] && !info[v][1]) || (!info[v][0] && info[v][1])) q.push(v), info[v][2] = 1;
        }
        
        // 4-8. G[u] を 処理.
        assert(info[u][0] == 0);
        assert(info[u][1] == 0);
        info[u][2] = 0;
        G[u].clear();
    }
    
    // 5. グラフが残存しているかチェック.
    int ans = 0;
    rep(i, N) ans += G[i].size();
    
    // 6. 出力.
    printf("%s\n", (ans == 0) ? "No" : "Yes");
    return 0;
    
}

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

#define pb push_back

set<int> G[202020];

int info[202020][3]; // 第一成分: 'A' の個数, 第二成分: 'B' の個数, 第三成分: 'A', 'B' の種類数.

int main(){

// 1. 入力情報.

int N, M;

char s[202020];

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

rep(i, M){

int a, b;

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

a--, b--;

G[a].insert(b);

G[b].insert(a);

}

// 2. 各頂点ごとに, 'A', 'B' の個数を保存.

rep(i, N){

// 2-1. 頂点 i の隣接頂点を確認して, 'A', 'B' の個数をカウント.

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

if(s[v] == 'A') info[i][0]++;

if(s[v] == 'B') info[i][1]++;

}

// 2-2. 'A', 'B' が, 1個以上ある場合に, 種類数をインクリメント.

if(info[i][0]) info[i][2]++;

if(info[i][1]) info[i][2]++;

}

// 3. 頂点(種類数 1) を保存.

queue<int> q;

rep(i, N) if(info[i][2] == 1) q.push(i);

// 4. グラフから, 種類数が, 1以下の頂点を取り除いていく.

while(!q.empty()){

// 4-1. 頂点 u に関する情報を取得.

int u = q.front();

q.pop();

int lu = s[u] - 'A';

// 4-2. 種類数を確認.

if(!info[u][2]) continue;

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

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

// 4-4. 種類数を確認.

if(!info[v][2]) continue;

// 4-5. u, v が等しい場合.

if(u == v){

info[u][lu]--;

continue;

}

// 4-6. G[v] から, u を取り除く.

int lv = s[v] - 'A';

G[v].erase(u);

info[u][lv]--;

info[v][lu]--;

// 4-7. 種類数が, 1 の場合に, 追加.

if((info[v][0] && !info[v][1]) || (!info[v][0] && info[v][1])) q.push(v), info[v][2] = 1;

}

// 4-8. G[u] を処理.

assert(info[u][0] == 0);

assert(info[u][1] == 0);

info[u][2] = 0;

G[u].clear();

}

// 5. グラフが残存しているかチェック.

int ans = 0;

rep(i, N) ans += G[i].size();

// 6. 出力.

printf("%s\n", (ans == 0) ? "No" : "Yes");

return 0;

}

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

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

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

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

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

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

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

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

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

[出力例]
Yes

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

[出力例]
No

100

101

102

103

104

105

106

107

108

109

110

111

[入力例]

2 3

1 1

1 2

2 2

[出力例]

Yes

※AtCoderのテストケースより

[入力例]

4 3

ABAB

1 2

2 3

3 1

[出力例]

※AtCoderのテストケースより

[入力例]

13 23

ABAAAABBBBAAB

7 1

10 6

1 11

2 10

2 8

2 11

11 12

8 3

7 12

11 2

13 13

11 9

4 1

9 7

9 6

8 13

8 6

4 10

8 7

4 3

2 1

8 12

6 9

[出力例]

Yes

※AtCoderのテストケースより

[入力例]

13 17

BBABBBAABABBA

7 1

7 9

11 12

3 9

11 9

2 1

11 5

12 11

10 8

1 11

1 8

7 7

9 10

8 8

8 12

6 2

13 11

[出力例]

※AtCoderのテストケースより

[入力例]

5 8

ABABA

1 2

1 3

1 1

1 5

2 3

4 5

3 4

2 4

[出力例]

Yes

[入力例]

7 12

AABBABA

1 2

2 3

3 4

4 5

5 6

6 7

7 1

1 7

2 3

1 5

6 4

3 6

[出力例]

■参照サイト
AtCoder Grand Contest 027

2021年4月21日

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

C++の練習を兼ねて, AtCoder Grand Contest 027 の問題A (Candy Distribution Again) ～問題B (Garbage Collector) を解いてみた.

■感想.
1. 問題Bは, 解答方針が見えなかったので, 解説を参考に実装して, ようやく, AC版に到達できた.
2. 解答に至るまでの実装方針が, 個人的には, 非常に不思議な印象を受ける面白い問題に感じた.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

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

int main(){
    
    // 1. 入力情報.
    int N, x;
    scanf("%d %d", &N, &x);
    rep(i, N) scanf("%d", &a[i]);
    
    // 2. sort.
    sort(a, a + N);
    
    // 3. お菓子を配る.
    rep(i, N){
        if(a[i] <= x) b[i] = a[i], x -= a[i];
        else          b[i] = x, x = 0;
    }
    if(x > 0) a[N - 1] += x; // 最終要素.
    
    // 4. 人数の最大値は？
    int ans = 0;
    rep(i, N) if(a[i] == b[i]) ans++;
    
    // 5. 出力.
    printf("%d\n", ans);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

int a[101], b[101];

int main(){

// 1. 入力情報.

int N, x;

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

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

// 2. sort.

sort(a, a + N);

// 3. お菓子を配る.

rep(i, N){

if(a[i] <= x) b[i] = a[i], x -= a[i];

else b[i] = x, x = 0;

}

if(x > 0) a[N - 1] += x; // 最終要素.

// 4. 人数の最大値は？

int ans = 0;

rep(i, N) if(a[i] == b[i]) ans++;

// 5. 出力.

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

return 0;

}

[入力例]
3 70
20 30 10

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

[入力例]
3 10
20 30 10

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

[入力例]
4 1111
1 10 100 1000

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

[入力例]
2 10
20 20

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

[入力例]
5 123
15 31 67 32 84

[出力例]
3

[入力例]

3 70

20 30 10

[出力例]

※AtCoderのテストケースより

[入力例]

3 10

20 30 10

[出力例]

※AtCoderのテストケースより

[入力例]

4 1111

1 10 100 1000

[出力例]

※AtCoderのテストケースより

[入力例]

2 10

20 20

[出力例]

※AtCoderのテストケースより

[入力例]

5 123

15 31 67 32 84

[出力例]

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

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

int main(){
    
    // 1. 入力情報.
    int N;
    LL X;
    scanf("%d %lld", &N, &X);
    rep(i, N) scanf("%d", &x[i]);
    
    // 2. 累積和.
    rep(i, N) xCum[i + 1] = xCum[i] + x[i];
    
    // 3. 必要なエネルギーの最小値を計算.
    LL ans = 202020202020202020;
    repx(k, 1, N + 1){
        LL cur = 0;
        repex(s, 1, N + 1, k){
            // 3-1. E(i, x) を 計算.
            int i = s / k;
            if(s % k != 0) i++;
            int g = min(N, s + k - 1);
            
            // 3-2. k に対するエネルギーを計算.
            int ns = N - g, ng = N - s + 1;
            if(i == 1) cur += 5 * (xCum[ng] - xCum[ns]);
            else       cur += (LL)(2 * i + 1) * (xCum[ng] - xCum[ns]);
        }
        
        // 3-3. 最小値更新.
        // -> test_13.txt, test_14.txt の Overflow対策.
        LL diff = (LL)(N + k) * X;
        if(ans - cur > diff) ans = cur + diff;
    }
    
    // 4. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

LL x[202020], xCum[202020];

int main(){

// 1. 入力情報.

int N;

LL X;

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

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

// 2. 累積和.

rep(i, N) xCum[i + 1] = xCum[i] + x[i];

// 3. 必要なエネルギーの最小値を計算.

LL ans = 202020202020202020;

repx(k, 1, N + 1){

LL cur = 0;

repex(s, 1, N + 1, k){

// 3-1. E(i, x) を計算.

int i = s / k;

if(s % k != 0) i++;

int g = min(N, s + k - 1);

// 3-2. k に対するエネルギーを計算.

int ns = N - g, ng = N - s + 1;

if(i == 1) cur += 5 * (xCum[ng] - xCum[ns]);

else cur += (LL)(2 * i + 1) * (xCum[ng] - xCum[ns]);

}

// 3-3. 最小値更新.

// -> test_13.txt, test_14.txt の Overflow対策.

LL diff = (LL)(N + k) * X;

if(ans - cur > diff) ans = cur + diff;

}

// 4. 出力.

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

return 0;

}

[入力例]
2 100
1 10

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

[入力例]
5 1
1 999999997 999999998 999999999 1000000000

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

[入力例]
10 8851025
38 87 668 3175 22601 65499 90236 790604 4290609 4894746

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

[入力例]
16 10
1 7 12 27 52 75 731 13856 395504 534840 1276551 2356789 9384806 19108104 82684732 535447408

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

[入力例]
3 14
15 9 26

[出力例]
320

[入力例]
25 47
1 5 11 20 23 24 30 41 42 43 46 55 59 68 74 87 90 92 101 105 115 120 124 137 142

[出力例]
10001

[入力例]
50 20210421
471016 997883 1801666 2830430 3345391 3447316 3702870 4755430 5061374 5880249 6034233 7136353 7448252 8342289 9089895 10138757 10688060 10859188 11516771 12205763 12313002 13266027 14088442 15145933 16347096 17568780 18572974 19696877 20818373 21063001 21212244 21610377 21667308 21763666 21828525 23057695 23862364 24786068 25097793 26064195 27246200 27953738 29139100 30229038 30841882 31533903 31968519 32828786 34016064 35155115

[出力例]
5660125250

[入力例]

2 100

1 10

[出力例]

355

※AtCoderのテストケースより

[入力例]

5 1

1 999999997 999999998 999999999 1000000000

[出力例]

19999999983

※AtCoderのテストケースより

[入力例]

10 8851025

38 87 668 3175 22601 65499 90236 790604 4290609 4894746

[出力例]

150710136

※AtCoderのテストケースより

[入力例]

16 10

1 7 12 27 52 75 731 13856 395504 534840 1276551 2356789 9384806 19108104 82684732 535447408

[出力例]

3256017715

※AtCoderのテストケースより

[入力例]

3 14

15 9 26

[出力例]

320

[入力例]

25 47

1 5 11 20 23 24 30 41 42 43 46 55 59 68 74 87 90 92 101 105 115 120 124 137 142

[出力例]

10001

[入力例]

50 20210421

471016 997883 1801666 2830430 3345391 3447316 3702870 4755430 5061374 5880249 6034233 7136353 7448252 8342289 9089895 10138757 10688060 10859188 11516771 12205763 12313002 13266027 14088442 15145933 16347096 17568780 18572974 19696877 20818373 21063001 21212244 21610377 21667308 21763666 21828525 23057695 23862364 24786068 25097793 26064195 27246200 27953738 29139100 30229038 30841882 31533903 31968519 32828786 34016064 35155115

[出力例]

5660125250

■参照サイト
AtCoder Grand Contest 027

2021年4月19日

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

C++の練習を兼ねて, AtCoder Grand Contest 017 の問題C (Snuke and Spells) を解いてみた.

■感想.
1. 問題Cは, 解答方針が見えなかったので, 解説を参考に実装して, ようやく, AC版に到達できた.
2. 解答に至るまでの実装方針が, 個人的には, 非常に不思議な印象を受ける面白い問題に感じた.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/agc017/editorial.pdf
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define a first
#define b second
int a[202020];
int cover[202020]; // 被覆[x - 1, x]
P section[202020]; // ボール i (q個) の 区間[i - q, i]

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    rep(i, N) scanf("%d", &a[i]);
    
    // 2. 初期化.
    int ans = 0;
    rep(i, 202020) section[i] = {i, i};
    rep(i, N){
        int v = a[i];
        section[v].a--;
    }
    repx(i, 1, N + 1){
        int s = section[i].a + 1;
        int e = section[i].b + 1;
        repx(j, s, e) cover[j]++;
    }
    repx(i, 1, N + 1) if(!cover[i]) ans++;
    
    // 3. クエリ回答.
    rep(i, M){
        // 3-1．ボール情報を取得.
        int x, y;
        scanf("%d %d", &x, &y);
        x--;
        
        // 3-2．区間[p - N[p], p] を 縮める.
        int p = a[x];
        int lp = ++section[p].a;
        if(lp > 0){
            cover[lp]--;
            if(cover[lp] == 0) ans++;
        }
        
        // 3-3．x番目 の ボールを, y に 変更.
        a[x] = y;
        
        // 3-4. 区間[q - N[q], q] を 伸ばす.
        int q = a[x];
        int lq = section[q].a--;
        if(lq > 0){
            cover[lq]++;
            if(cover[lq] == 1) ans--;
        }
        
        // 3-5. 出力.
        printf("%d\n", ans);
    }
    return 0;
    
}

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using P = pair<int, int>;

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

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

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

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

#define a first

#define b second

int a[202020];

int cover[202020]; // 被覆[x - 1, x]

P section[202020]; // ボール i (q個) の区間[i - q, i]

int main(){

// 1. 入力情報.

int N, M;

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

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

// 2. 初期化.

int ans = 0;

rep(i, 202020) section[i] = {i, i};

rep(i, N){

int v = a[i];

section[v].a--;

}

repx(i, 1, N + 1){

int s = section[i].a + 1;

int e = section[i].b + 1;

repx(j, s, e) cover[j]++;

}

repx(i, 1, N + 1) if(!cover[i]) ans++;

// 3. クエリ回答.

rep(i, M){

// 3-1．ボール情報を取得.

int x, y;

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

x--;

// 3-2．区間[p - N[p], p] を縮める.

int p = a[x];

int lp = ++section[p].a;

if(lp > 0){

cover[lp]--;

if(cover[lp] == 0) ans++;

}

// 3-3．x番目のボールを, y に変更.

a[x] = y;

// 3-4. 区間[q - N[q], q] を伸ばす.

int q = a[x];

int lq = section[q].a--;

if(lq > 0){

cover[lq]++;

if(cover[lq] == 1) ans--;

}

// 3-5. 出力.

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

}

return 0;

}

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

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

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

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

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

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

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

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

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

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

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

[入力例]

5 3

1 1 3 4 5

1 2

2 5

5 4

[出力例]

※AtCoderテストケースより

[入力例]

4 4

4 4 4 4

4 1

3 1

1 1

2 1

[出力例]

※AtCoderテストケースより

[入力例]

10 10

8 7 2 9 10 6 6 5 5 4

8 1

6 3

6 2

7 10

9 7

9 9

2 4

8 1

1 8

7 7

[出力例]

※AtCoderテストケースより

[入力例]

7 10

7 1 4 2 5 6 7

1 1

3 6

7 1

5 3

2 3

2 7

5 3

3 7

1 7

6 3

[出力例]

[入力例]

20 30

1 2 14 16 12 6 13 7 14 15 9 18 11 14 8 1 3 15 16 12

17 1

14 16

6 15

15 20

4 6

17 4

12 17

15 16

19 11

16 3

9 2

11 9

6 3

9 14

20 13

13 12

19 9

7 19

5 17

1 17

2 17

7 8

11 2

6 12

1 5

6 10

8 20

19 16

7 9

5 4

[出力例]

■参照サイト
AtCoder Grand Contest 017

2021年4月18日

Python（Qiskit）について（８）

概要

Qiskit について, サンプルプログラムを動かしてみた.
動作環境は, Google Colaboratory で行った
実行プログラム, 解説は, 下記の参照サイトをご覧ください

感想

本家のサイトが詳しいので, 今後も, どのような機能が利用できるかを, 時間を見つけて, 進めていこうと思う.

PrimitiveOps

operators etc

[編集内容(operators etc)]
from qiskit.aqua.operators import (X, Y, Z, I, CX, T, H, S, Zero, One, Plus, Minus, PrimitiveOp)

# X
print(X)
print(X.to_matrix().real)

# Y
print(Y)
print(Y.to_matrix().real)

# Z
print(Z)
print(Z.to_matrix().real)

# I
print(I)
print(I.to_matrix().real)

# CX
print(CX)
print(CX.to_matrix().real)

# T
print(T)
print(T.to_matrix().real)

# H
print(H)
print(H.to_matrix().real)

# S
print(S)
print(S.to_matrix().real)

# Zero
print(Zero)
print(Zero.to_matrix().real)

# One
print(One)
print(One.to_matrix().real)

# Plus
print(Plus)
print(Plus.to_matrix().real)

# Minus
print(Minus)
print(Minus.to_matrix().real)

[編集内容(operators etc)]

from qiskit.aqua.operators import (X, Y, Z, I, CX, T, H, S, Zero, One, Plus, Minus, PrimitiveOp)

# X

print(X)

print(X.to_matrix().real)

# Y

print(Y)

print(Y.to_matrix().real)

# Z

print(Z)

print(Z.to_matrix().real)

# I

print(I)

print(I.to_matrix().real)

# CX

print(CX)

print(CX.to_matrix().real)

# T

print(T)

print(T.to_matrix().real)

# H

print(H)

print(H.to_matrix().real)

# S

print(S)

print(S.to_matrix().real)

# Zero

print(Zero)

print(Zero.to_matrix().real)

# One

print(One)

print(One.to_matrix().real)

# Plus

print(Plus)

print(Plus.to_matrix().real)

# Minus

print(Minus)

print(Minus.to_matrix().real)

[出力結果]
X
[[0. 1.]
 [1. 0.]]
Y
[[0. 0.]
 [0. 0.]]
Z
[[ 1.  0.]
 [ 0. -1.]]
I
[[1. 0.]
 [0. 1.]]
q_0: ──■──
     ┌─┴─┐
q_1: ┤ X ├
     └───┘
[[1. 0. 0. 0.]
 [0. 0. 0. 1.]
 [0. 0. 1. 0.]
 [0. 1. 0. 0.]]
     ┌───┐
q_0: ┤ T ├
     └───┘
[[1.         0.        ]
 [0.         0.70710678]]
     ┌───┐
q_0: ┤ H ├
     └───┘
[[ 0.70710678  0.70710678]
 [ 0.70710678 -0.70710678]]
     ┌───┐
q_0: ┤ S ├
     └───┘
[[1. 0.]
 [0. 0.]]
DictStateFn({'0': 1})
[1. 0.]
DictStateFn({'1': 1})
[0. 1.]
CircuitStateFn(
     ┌───┐
q_0: ┤ H ├
     └───┘
)
[0.70710678 0.70710678]
CircuitStateFn(
     ┌───┐┌───┐
q_0: ┤ X ├┤ H ├
     └───┘└───┘
)
[ 0.70710678 -0.70710678]

[出力結果]

[[0. 1.]

[1. 0.]]

[[0. 0.]

[0. 0.]]

[[ 1. 0.]

[ 0. -1.]]

[[1. 0.]

[0. 1.]]

q_0: ──■──

┌─┴─┐

q_1: ┤ X ├

└───┘

[[1. 0. 0. 0.]

[0. 0. 0. 1.]

[0. 0. 1. 0.]

[0. 1. 0. 0.]]

┌───┐

q_0: ┤ T ├

└───┘

[[1. 0. ]

[0. 0.70710678]]

┌───┐

q_0: ┤ H ├

└───┘

[[ 0.70710678 0.70710678]

[ 0.70710678 -0.70710678]]

┌───┐

q_0: ┤ S ├

└───┘

[[1. 0.]

[0. 0.]]

DictStateFn({'0': 1})

[1. 0.]

DictStateFn({'1': 1})

[0. 1.]

CircuitStateFn(

┌───┐

q_0: ┤ H ├

└───┘

)

[0.70710678 0.70710678]

CircuitStateFn(

┌───┐┌───┐

q_0: ┤ X ├┤ H ├

└───┘└───┘

)

[ 0.70710678 -0.70710678]

Bell-State

[編集内容(Bell-State)]
import numpy as np

# Import Qiskit
from qiskit import QuantumCircuit
from qiskit import Aer, transpile
from qiskit.tools.visualization import plot_histogram, plot_state_city
import qiskit.quantum_info as qi

#Aer.backends()
simulator = Aer.get_backend('aer_simulator')

# Create circuit
circ = QuantumCircuit(2)
circ.h(0)
circ.cx(0, 1)
circ.measure_all()

# Transpile for simulator
simulator = Aer.get_backend('aer_simulator')
circ = transpile(circ, simulator)

# Run and get counts
result = simulator.run(circ, shots=10000, memory=True).result()
counts = result.get_counts(circ)
plot_histogram(counts, title='Bell-State counts')

[編集内容(Bell-State)]

import numpy as np

# Import Qiskit

from qiskit import QuantumCircuit

from qiskit import Aer, transpile

from qiskit.tools.visualization import plot_histogram, plot_state_city

import qiskit.quantum_info as qi

#Aer.backends()

simulator = Aer.get_backend('aer_simulator')

# Create circuit

circ = QuantumCircuit(2)

circ.h(0)

circ.cx(0, 1)

circ.measure_all()

# Transpile for simulator

simulator = Aer.get_backend('aer_simulator')

circ = transpile(circ, simulator)

# Run and get counts

result = simulator.run(circ, shots=10000, memory=True).result()

counts = result.get_counts(circ)

plot_histogram(counts, title='Bell-State counts')

[出力結果]
グラフが表示された.

1 2	[出力結果] グラフが表示された.

[編集内容(Bell-State)]
# Run and get memory
print(counts)

[編集内容(Bell-State)]

# Run and get memory

print(counts)

[出力結果]
{'11': 4999, '00': 5001}

1 2	[出力結果] {'11': 4999, '00': 5001}

3-Qubit GHZ-State

[編集内容(3-Qubit GHZ-State)]
import numpy as np

# Import Qiskit
from qiskit import QuantumCircuit
from qiskit import Aer, transpile
from qiskit.tools.visualization import plot_histogram, plot_state_city
import qiskit.quantum_info as qi

#Aer.backends()
simulator = Aer.get_backend('aer_simulator')

# Create circuit
circ = QuantumCircuit(3)
circ.h(0)
circ.cx(0, 1)
circ.cx(1, 2)
circ.measure_all()

# Transpile for simulator
simulator = Aer.get_backend('aer_simulator')
circ = transpile(circ, simulator)

# Run and get counts
result = simulator.run(circ, shots=10000, memory=True).result()
counts = result.get_counts(circ)
plot_histogram(counts, title='3-Qubit GHZ-State counts')

[編集内容(3-Qubit GHZ-State)]

import numpy as np

# Import Qiskit

from qiskit import QuantumCircuit

from qiskit import Aer, transpile

from qiskit.tools.visualization import plot_histogram, plot_state_city

import qiskit.quantum_info as qi

#Aer.backends()

simulator = Aer.get_backend('aer_simulator')

# Create circuit

circ = QuantumCircuit(3)

circ.h(0)

circ.cx(0, 1)

circ.cx(1, 2)

circ.measure_all()

# Transpile for simulator

simulator = Aer.get_backend('aer_simulator')

circ = transpile(circ, simulator)

# Run and get counts

result = simulator.run(circ, shots=10000, memory=True).result()

counts = result.get_counts(circ)

plot_histogram(counts, title='3-Qubit GHZ-State counts')

[出力結果]
グラフが表示された.

1 2	[出力結果] グラフが表示された.

[編集内容(3-Qubit GHZ-State)]
# Run and get memory
print(counts)

[編集内容(3-Qubit GHZ-State)]

# Run and get memory

print(counts)

[出力結果]
{'111': 4930, '000': 5070}

1 2	[出力結果] {'111': 4930, '000': 5070}

5-Qubit GHZ-State

[編集内容(5-Qubit GHZ-State)]
import numpy as np

# Import Qiskit
from qiskit import QuantumCircuit
from qiskit import Aer, transpile
from qiskit.tools.visualization import plot_histogram, plot_state_city
import qiskit.quantum_info as qi

#Aer.backends()
simulator = Aer.get_backend('aer_simulator')

# Create circuit
circ = QuantumCircuit(5)
circ.h(0)
circ.cx(0, 1)
circ.cx(1, 2)
circ.cx(2, 3)
circ.cx(3, 4)
circ.measure_all()

# Transpile for simulator
simulator = Aer.get_backend('aer_simulator')
circ = transpile(circ, simulator)

# Run and get counts
result = simulator.run(circ, shots=10000, memory=True).result()
counts = result.get_counts(circ)
plot_histogram(counts, title='5-Qubit GHZ-State counts')

[編集内容(5-Qubit GHZ-State)]

import numpy as np

# Import Qiskit

from qiskit import QuantumCircuit

from qiskit import Aer, transpile

from qiskit.tools.visualization import plot_histogram, plot_state_city

import qiskit.quantum_info as qi

#Aer.backends()

simulator = Aer.get_backend('aer_simulator')

# Create circuit

circ = QuantumCircuit(5)

circ.h(0)

circ.cx(0, 1)

circ.cx(1, 2)

circ.cx(2, 3)

circ.cx(3, 4)

circ.measure_all()

# Transpile for simulator

simulator = Aer.get_backend('aer_simulator')

circ = transpile(circ, simulator)

# Run and get counts

result = simulator.run(circ, shots=10000, memory=True).result()

counts = result.get_counts(circ)

plot_histogram(counts, title='5-Qubit GHZ-State counts')

[出力結果]
グラフが表示された.

1 2	[出力結果] グラフが表示された.

[編集内容(5-Qubit GHZ-State)]
# Run and get memory
print(counts)

[編集内容(5-Qubit GHZ-State)]

# Run and get memory

print(counts)

[出力結果]
{'11111': 4938, '00000': 5062}

1 2	[出力結果] {'11111': 4938, '00000': 5062}

参照サイト

2021年4月18日

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

C++の練習を兼ねて, AtCoder Regular Contest 116 の問題D (I Wanna Win The Game) を解いてみた.

■感想.
1. 問題Cは, 解答方針が見えなかったので, 解説を参考に実装して, ようやく, AC版に到達できた.
2. 苦手なdpの訓練を積めたので, 非常に良かったと思う.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// C++ (GCC 9.2.1)
// 解き直し.
// https://atcoder.jp/contests/arc116/editorial/893
#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 a first
#define b second
const LL MOD = 998244353;
const int LIMIT = 5050;
LL FAC[LIMIT], INV[LIMIT], dp[LIMIT];

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

// 組み合わせ(nCk)計算用(mod版).
// ※配列FAC, INV は, 事前に計算済のものを使う.
// @param n: 対象となる要素の個数.
// @param k: 選択する要素の個数.
// @return: 組み合わせ(nCk)の計算結果(mod版).
LL combination(LL n, LL k){
    if(n < 0 || k < 0 || k > n) return 0LL;
    if(n == k || k == 0LL) return 1LL;
    LL ret = FAC[n] * INV[k] % MOD * INV[n - k] % MOD;
    return ret;
}

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    FAC[0] = 1;
    repx(i, 1, LIMIT) FAC[i] = (LL)i * FAC[i - 1] % MOD;
    rep(i, LIMIT) INV[i] = mPow(FAC[i], MOD - 2);
    
    // 2. 解説通り.
    dp[0] = 1;
    repex(i, 2, M + 1, 2){
        rep(j, N){
            int idx = (i - 2 * j) / 2;
            if(idx < 0) break;
            dp[i] += combination((LL)N, (LL)(2 * j)) * dp[(i - 2 * j) / 2];
            dp[i] %= MOD;
        }
    }
    
    // 3. 出力.
    printf("%lld\n", dp[M]);
    return 0;
    
}

// C++ (GCC 9.2.1)

// 解き直し.

// https://atcoder.jp/contests/arc116/editorial/893

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

#define b second

const LL MOD = 998244353;

const int LIMIT = 5050;

LL FAC[LIMIT], INV[LIMIT], dp[LIMIT];

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

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

// @param b: 指数.

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

LL mPow(LL a, LL b){

LL t = 1;

while(b){

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

a = a * a % MOD;

b >>= 1;

}

return t % MOD;

}

// 組み合わせ(nCk)計算用(mod版).

// ※配列FAC, INV は, 事前に計算済のものを使う.

// @param n: 対象となる要素の個数.

// @param k: 選択する要素の個数.

// @return: 組み合わせ(nCk)の計算結果(mod版).

LL combination(LL n, LL k){

if(n < 0 || k < 0 || k > n) return 0LL;

if(n == k || k == 0LL) return 1LL;

LL ret = FAC[n] * INV[k] % MOD * INV[n - k] % MOD;

return ret;

}

int main(){

// 1. 入力情報.

int N, M;

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

FAC[0] = 1;

repx(i, 1, LIMIT) FAC[i] = (LL)i * FAC[i - 1] % MOD;

rep(i, LIMIT) INV[i] = mPow(FAC[i], MOD - 2);

// 2. 解説通り.

dp[0] = 1;

repex(i, 2, M + 1, 2){

rep(j, N){

int idx = (i - 2 * j) / 2;

if(idx < 0) break;

dp[i] += combination((LL)N, (LL)(2 * j)) * dp[(i - 2 * j) / 2];

dp[i] %= MOD;

}

// 3. 出力.

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

return 0;

}

[入力例]
5 20

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

[入力例]
10 5

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

[入力例]
3141 2718

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

[入力例]
3 10

[出力例]
9

[入力例]
7 16

[出力例]
16471

[入力例]
2020 418

[出力例]
670494756

[入力例]

5 20

[出力例]

475

※AtCoderのテストケースより

[入力例]

10 5

[出力例]

※AtCoderのテストケースより

[入力例]

3141 2718

[出力例]

371899128

※AtCoderのテストケースより

[入力例]

3 10

[出力例]

[入力例]

7 16

[出力例]

16471

[入力例]

2020 418

[出力例]

670494756

■参照サイト
AtCoder Regular Contest 116

2021年4月17日2021年4月18日

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

C++の練習を兼ねて, AtCoder Regular Contest 116 の問題C (Multiple Sequences) を解いてみた.

■感想.
1. 問題Cは, 解答方針が見えなかったので, 解説を参考に実装して, ようやく, AC版に到達できた.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// C++ (GCC 9.2.1)
// 解き直し.
// https://atcoder.jp/contests/arc116/editorial/892
#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 a first
#define b second
const LL MOD = 998244353;
const int LIMIT = 202020;
LL FAC[LIMIT], INV[LIMIT];

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

// 組み合わせ(nCk)計算用(mod版).
// ※配列FAC, INV は, 事前に計算済のものを使う.
// @param n: 対象となる要素の個数.
// @param k: 選択する要素の個数.
// @return: 組み合わせ(nCk)の計算結果(mod版).
LL combination(LL n, LL k){
    if(n < 0 || k < 0 || k > n) return 0LL;
    if(n == k || k == 0LL) return 1LL;
    LL ret = FAC[n] * INV[k] % MOD * INV[n - k] % MOD;
    return ret;
}

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    FAC[0] = 1;
    repx(i, 1, LIMIT) FAC[i] = (LL)i * FAC[i - 1] % MOD;
    rep(i, LIMIT) INV[i] = mPow(FAC[i], MOD - 2);
    
    // 2. 素数の抽出.
    set<int> st;
    st.insert(2);
    repex(i, 3, 500, 2) {
        bool isPrime = true;
        repex(j, 3, sqrt(i) + 1, 2) {
            if(i % j == 0){
                isPrime = false;
                break;
            }
        }
        if(isPrime) st.insert(i);
    }
    // for(auto &p : st) printf("%d ", p);
    // puts("");
    
    // 3. 解説通り.
    LL ans = 1;
    repx(k, 2, M + 1){
        // 3-1. 素因数分解を行う.
        int n = k;
        map<int, int> m;
        for(auto &p : st){
            while(n % p == 0){
                n /= p;
                m[p]++;
            }
        }
        
        // 3-2. n が 素数 の 場合(ex. 2 * 3 * 5 * 521 などの場合).
        if(n != 1) m[n] = 1;
        
        // 3-3. A[N] = k の場合 を 計算.
        LL t = 1;
        for(auto &p : m){
            t *= combination((LL)(N + p.b - 1), (LL)p.b);
            t %= MOD;
        }
        
        // 3-4. 加算.
        ans += t;
        ans %= MOD;
    }
    
    // 4. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

100

// C++ (GCC 9.2.1)

// 解き直し.

// https://atcoder.jp/contests/arc116/editorial/892

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

#define b second

const LL MOD = 998244353;

const int LIMIT = 202020;

LL FAC[LIMIT], INV[LIMIT];

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

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

// @param b: 指数.

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

LL mPow(LL a, LL b){

LL t = 1;

while(b){

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

a = a * a % MOD;

b >>= 1;

}

return t % MOD;

}

// 組み合わせ(nCk)計算用(mod版).

// ※配列FAC, INV は, 事前に計算済のものを使う.

// @param n: 対象となる要素の個数.

// @param k: 選択する要素の個数.

// @return: 組み合わせ(nCk)の計算結果(mod版).

LL combination(LL n, LL k){

if(n < 0 || k < 0 || k > n) return 0LL;

if(n == k || k == 0LL) return 1LL;

LL ret = FAC[n] * INV[k] % MOD * INV[n - k] % MOD;

return ret;

}

int main(){

// 1. 入力情報.

int N, M;

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

FAC[0] = 1;

repx(i, 1, LIMIT) FAC[i] = (LL)i * FAC[i - 1] % MOD;

rep(i, LIMIT) INV[i] = mPow(FAC[i], MOD - 2);

// 2. 素数の抽出.

set<int> st;

st.insert(2);

repex(i, 3, 500, 2) {

bool isPrime = true;

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

if(i % j == 0){

isPrime = false;

break;

}

if(isPrime) st.insert(i);

}

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

// puts("");

// 3. 解説通り.

LL ans = 1;

repx(k, 2, M + 1){

// 3-1. 素因数分解を行う.

int n = k;

map<int, int> m;

for(auto &p : st){

while(n % p == 0){

n /= p;

m[p]++;

}

// 3-2. n が素数の場合(ex. 2 * 3 * 5 * 521 などの場合).

if(n != 1) m[n] = 1;

// 3-3. A[N] = k の場合を計算.

LL t = 1;

for(auto &p : m){

t *= combination((LL)(N + p.b - 1), (LL)p.b);

t %= MOD;

}

// 3-4. 加算.

ans += t;

ans %= MOD;

}

// 4. 出力.

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

return 0;

}

[入力例]
3 4

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

[入力例]
20 30

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

[入力例]
200000 200000

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

[入力例]
5 7

[出力例]
61

[入力例]
7 15

[出力例]
575

[入力例]
12 15630

[出力例]
791562163

[入力例]

3 4

[出力例]

※AtCoderのテストケースより

[入力例]

20 30

[出力例]

71166

※AtCoderのテストケースより

[入力例]

200000 200000

[出力例]

835917264

※AtCoderのテストケースより

[入力例]

5 7

[出力例]

[入力例]

7 15

[出力例]

575

[入力例]

12 15630

[出力例]

791562163

■参照サイト
AtCoder Regular Contest 116

2021年4月16日

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

C++の練習を兼ねて, AtCoder Grand Contest 018 の問題C (Coins) を解いてみた.

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

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

// 解き直し.
// https://img.atcoder.jp/agc018/editorial.pdf
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
#define all(x) x.begin(), x.end()
LL cum[101010][3]; // 金, 銀, 銅 の 枚数 の 累積和.
LL lCoin[101010], rCoin[101010];

struct Coin{
    LL a, b, c, d; // 金, 銀, 銅, 差分.
    bool operator < (const Coin& rhs) const{
        return d > rhs.d;
    }
};

int main(){
    
    // 1. 入力情報.
    int X, Y, Z, A = 0;
    scanf("%d %d %d", &X, &Y, &Z);
    vector<Coin> v;
    A = X + Y + Z;
    rep(i, A){
        Coin c;
        scanf("%lld %lld %lld", &c.a, &c.b, &c.c);
        c.d = c.a - c.b;
        v.pb(c);
    }
    
    // 2. sort(金コイン枚数 - 銀コイン枚数).
    sort(all(v));
    reverse(all(v));
    // for(auto &p : v) printf("a=%lld b=%lld c=%lld d=%lld\n", p.a, p.b, p.c, p.d);
    
    // 3. 累計和.
    rep(i, A){
        cum[i + 1][0] = cum[i][0] + v[i].a; // 金.
        cum[i + 1][1] = cum[i][1] + v[i].b; // 銀.
        cum[i + 1][2] = cum[i][2] + v[i].c; // 銅.
    }
    
    // 4. 左側から貰う 銀コイン, 銅コイン の 和 を 計算.
    // 4-1. 初期化.
    LL gold, silver, bronze;
    priority_queue<Coin> pq;
    silver = cum[Y][1];
    bronze = 0;
    lCoin[Y] = silver + bronze;
    rep(i, Y){
        Coin c;
        c.a = v[i].a;
        c.b = v[i].b;
        c.c = v[i].c;
        c.d = c.b - c.c; // 銀コイン枚数 - 銅コイン枚数.
        pq.push(c);
    }
    
    // 4-2. K = Y ～ X + Y + Z で 確認.
    repx(i, Y, A){
        // コイン情報を取得.
        Coin c = v[i];
        
        // 銀コインの枚数を更新.
        silver += c.b;
        
        // コイン情報を保存.
        c.d = c.b - c.c;
        pq.push(c);
        
        // コイン情報を取り出す.
        c = pq.top();
        pq.pop();
        
        // 銀, 銅コインの枚数を更新.
        silver -= c.b;
        bronze += c.c;
        
        // コインの合計枚数を保存.
        lCoin[i + 1] = silver + bronze;
    }
    
    // 5. 右側から貰う 金コイン, 銅コイン の 和 を 計算.
    // 5-1. 初期化.
    pq = priority_queue<Coin>();
    gold = cum[A][0] - cum[A - X][0];
    bronze = 0;
    rCoin[A - X] = gold + bronze;
    repr(i, A - 1, A - X){
        Coin c;
        c.a = v[i].a;
        c.b = v[i].b;
        c.c = v[i].c;
        c.d = c.a - c.c; // 金コイン枚数 - 銅コイン枚数.
        pq.push(c);
    }
    
    // 5-2. K = Y + Z ～ 0 で 確認.
    repr(i, A - X - 1, 0){
        // コイン情報を取得.
        Coin c = v[i];
        
        // 金コインの枚数を更新.
        gold += c.a;
        
        // コイン情報を保存.
        c.d = c.a - c.c;
        pq.push(c);
        
        // コイン情報を取り出す.
        c = pq.top();
        pq.pop();
        
        // 金, 銅コインの枚数を更新.
        gold   -= c.a;
        bronze += c.c;
        
        // コインの合計枚数を保存.
        rCoin[i] = gold + bronze;
    }
    
    // 6. 最大値を計算.
    LL ans = 0;
    repx(i, Y, A - X + 1) ans = max(ans, lCoin[i] + rCoin[i]);
    // rep(i, A + 1) printf("%lld ", lCoin[i]);
    // puts("");
    // rep(i, A + 1) printf("%lld ", rCoin[i]);
    // puts("");
    
    // 7. 出力.
    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

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

#define pb push_back

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

LL cum[101010][3]; // 金, 銀, 銅の枚数の累積和.

LL lCoin[101010], rCoin[101010];

struct Coin{

LL a, b, c, d; // 金, 銀, 銅, 差分.

bool operator < (const Coin& rhs) const{

return d > rhs.d;

}

};

int main(){

// 1. 入力情報.

int X, Y, Z, A = 0;

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

vector<Coin> v;

A = X + Y + Z;

rep(i, A){

Coin c;

scanf("%lld %lld %lld", &c.a, &c.b, &c.c);

c.d = c.a - c.b;

v.pb(c);

}

// 2. sort(金コイン枚数 - 銀コイン枚数).

sort(all(v));

reverse(all(v));

// for(auto &p : v) printf("a=%lld b=%lld c=%lld d=%lld\n", p.a, p.b, p.c, p.d);

// 3. 累計和.

rep(i, A){

cum[i + 1][0] = cum[i][0] + v[i].a; // 金.

cum[i + 1][1] = cum[i][1] + v[i].b; // 銀.

cum[i + 1][2] = cum[i][2] + v[i].c; // 銅.

}

// 4. 左側から貰う銀コイン, 銅コインの和を計算.

// 4-1. 初期化.

LL gold, silver, bronze;

priority_queue<Coin> pq;

silver = cum[Y][1];

bronze = 0;

lCoin[Y] = silver + bronze;

rep(i, Y){

Coin c;

c.a = v[i].a;

c.b = v[i].b;

c.c = v[i].c;

c.d = c.b - c.c; // 銀コイン枚数 - 銅コイン枚数.

pq.push(c);

}

// 4-2. K = Y ～ X + Y + Z で確認.

repx(i, Y, A){

// コイン情報を取得.

Coin c = v[i];

// 銀コインの枚数を更新.

silver += c.b;

// コイン情報を保存.

c.d = c.b - c.c;

pq.push(c);

// コイン情報を取り出す.

c = pq.top();

pq.pop();

// 銀, 銅コインの枚数を更新.

silver -= c.b;

bronze += c.c;

// コインの合計枚数を保存.

lCoin[i + 1] = silver + bronze;

}

// 5. 右側から貰う金コイン, 銅コインの和を計算.

// 5-1. 初期化.

pq = priority_queue<Coin>();

gold = cum[A][0] - cum[A - X][0];

bronze = 0;

rCoin[A - X] = gold + bronze;

repr(i, A - 1, A - X){

Coin c;

c.a = v[i].a;

c.b = v[i].b;

c.c = v[i].c;

c.d = c.a - c.c; // 金コイン枚数 - 銅コイン枚数.

pq.push(c);

}

// 5-2. K = Y + Z ～ 0 で確認.

repr(i, A - X - 1, 0){

// コイン情報を取得.

Coin c = v[i];

// 金コインの枚数を更新.

gold += c.a;

// コイン情報を保存.

c.d = c.a - c.c;

pq.push(c);

// コイン情報を取り出す.

c = pq.top();

pq.pop();

// 金, 銅コインの枚数を更新.

gold -= c.a;

bronze += c.c;

// コインの合計枚数を保存.

rCoin[i] = gold + bronze;

}

// 6. 最大値を計算.

LL ans = 0;

repx(i, Y, A - X + 1) ans = max(ans, lCoin[i] + rCoin[i]);

// rep(i, A + 1) printf("%lld ", lCoin[i]);

// puts("");

// rep(i, A + 1) printf("%lld ", rCoin[i]);

// puts("");

// 7. 出力.

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

return 0;

}

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

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

[入力例]
3 3 2
16 17 1
2 7 5
2 16 12
17 7 7
13 2 10
12 18 3
16 15 19
5 6 2

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

[入力例]
6 2 4
33189 87907 277349742
71616 46764 575306520
8801 53151 327161251
58589 4337 796697686
66854 17565 289910583
50598 35195 478112689
13919 88414 103962455
7953 69657 699253752
44255 98144 468443709
2332 42580 752437097
39752 19060 845062869
60126 74101 382963164

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

[入力例]
5 4 3
11 6 1
12 7 2
13 8 3
19 15 11
20 16 12
10 4 7
11 5 8
12 6 9
23 20 18
15 13 21
18 19 10
30 31 22

[出力例]
189

[入力例]
12 11 10
112 46 40
61 35 96
41 115 24
55 101 118
12 81 70
114 118 25
84 30 5
102 91 21
59 24 85
93 4 50
76 8 83
75 68 76
73 16 104
120 100 39
22 21 27
27 55 29
29 37 23
72 89 25
21 45 75
99 23 49
102 110 43
53 19 106
120 67 8
61 31 65
76 62 58
80 107 115
81 6 51
32 110 76
97 86 111
46 101 8
46 116 93
27 18 69
40 61 19

[出力例]
3000

100

101

[入力例]

1 2 1

2 4 4

3 2 1

7 6 7

5 2 3

[出力例]

※AtCoderテストケースより

[入力例]

3 3 2

16 17 1

2 7 5

2 16 12

17 7 7

13 2 10

12 18 3

16 15 19

5 6 2

[出力例]

110

※AtCoderテストケースより

[入力例]

6 2 4

33189 87907 277349742

71616 46764 575306520

8801 53151 327161251

58589 4337 796697686

66854 17565 289910583

50598 35195 478112689

13919 88414 103962455

7953 69657 699253752

44255 98144 468443709

2332 42580 752437097

39752 19060 845062869

60126 74101 382963164

[出力例]

3093929975

※AtCoderテストケースより

[入力例]

5 4 3

11 6 1

12 7 2

13 8 3

19 15 11

20 16 12

10 4 7

11 5 8

12 6 9

23 20 18

15 13 21

18 19 10

30 31 22

[出力例]

189

[入力例]

12 11 10

112 46 40

61 35 96

41 115 24

55 101 118

12 81 70

114 118 25

84 30 5

102 91 21

59 24 85

93 4 50

76 8 83

75 68 76

73 16 104

120 100 39

22 21 27

27 55 29

29 37 23

72 89 25

21 45 75

99 23 49

102 110 43

53 19 106

120 67 8

61 31 65

76 62 58

80 107 115

81 6 51

32 110 76

97 86 111

46 101 8

46 116 93

27 18 69

40 61 19

[出力例]

3000

■参照サイト
AtCoder Grand Contest 018

2021年4月16日

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

C++の練習を兼ねて, AtCoder Grand Contest 020 の問題A (Move and Win) ～問題B (Ice Rink Game) を解いてみた.

■感想.
1. 問題Bは, 解答方針が見えなかったので, 解説を参考に実装して, ようやく, AC版に到達できた.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;

int main(){
    
    // 1. 入力情報.
    int N, A, B;
    scanf("%d %d %d", &N, &A, &B);
    
    // 2. 出力.
    printf("%s\n", ((B - A) % 2 == 0) ? "Alice" : "Borys");
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

int main(){

// 1. 入力情報.

int N, A, B;

scanf("%d %d %d", &N, &A, &B);

// 2. 出力.

printf("%s\n", ((B - A) % 2 == 0) ? "Alice" : "Borys");

return 0;

}

[入力例]
5 2 4

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

[入力例]
2 1 2

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

[入力例]
58 23 42

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

[入力例]

5 2 4

[出力例]

Alice

※AtCoderテストケースより

[入力例]

2 1 2

[出力例]

Borys

※AtCoderテストケースより

[入力例]

58 23 42

[出力例]

Borys

※AtCoderテストケースより

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

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

int main(){
    
    // 1. 入力情報.
    int K;
    scanf("%d", &K);
    rep(i, K) scanf("%lld", &a[i]);
    
    // 2. 人数の最小値, 最大値を更新.
    l[K] = r[K] = 2;
    repr(i, K - 1, 0){
        // 2-1. 最小値更新.
        LL tq = l[i + 1] / a[i];
        LL tr = l[i + 1] % a[i];
        LL tl = (tr == 0) ? tq : tq + 1;
        l[i] = tl * a[i];
        
        // 2-2. 最大値更新.
        r[i] = r[i + 1] / a[i] * a[i] + a[i] - 1;
    }
    
    // 3. 出力.
    if(l[0] > r[0]) puts("-1");
    else            printf("%lld% lld\n", l[0], r[0]);
    return 0;
    
}

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

LL a[101010], l[101010], r[101010];

int main(){

// 1. 入力情報.

int K;

scanf("%d", &K);

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

// 2. 人数の最小値, 最大値を更新.

l[K] = r[K] = 2;

repr(i, K - 1, 0){

// 2-1. 最小値更新.

LL tq = l[i + 1] / a[i];

LL tr = l[i + 1] % a[i];

LL tl = (tr == 0) ? tq : tq + 1;

l[i] = tl * a[i];

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

r[i] = r[i + 1] / a[i] * a[i] + a[i] - 1;

}

// 3. 出力.

if(l[0] > r[0]) puts("-1");

else printf("%lld% lld\n", l[0], r[0]);

return 0;

}

[入力例]
4
3 4 3 2

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

[入力例]
5
3 4 100 3 2

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

[入力例]
10
2 2 2 2 2 2 2 2 2 2

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

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

[出力例]
15 29

[入力例]
25
97 89 83 79 73 71 67 61 59 53 47 43 41 37 31 29 23 19 17 13 11 7 5 3 2

[出力例]
97 193

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

[出力例]
25 29

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

[出力例]
220 239

[入力例]

3 4 3 2

[出力例]

6 8

※AtCoderテストケースより

[入力例]

3 4 100 3 2

[出力例]

-1

※AtCoderテストケースより

[入力例]

2 2 2 2 2 2 2 2 2 2

[出力例]

2 3

※AtCoderテストケースより

[入力例]

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

[出力例]

15 29

[入力例]

97 89 83 79 73 71 67 61 59 53 47 43 41 37 31 29 23 19 17 13 11 7 5 3 2

[出力例]

97 193

[入力例]

5 4 3 2 1 5 4 3 2 1 5 4 3 2 1 5 4 3 2 1 5 4 3 2 1

[出力例]

25 29

[入力例]

100

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

[出力例]

220 239

■参照サイト
AtCoder Grand Contest 020

2021年4月15日2021年4月15日

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

C++の練習を兼ねて, AtCoder Grand Contest 043 の問題A (Range Flip Find Route) ～問題B (123 Triangle) を解いてみた.

■感想.
1. 問題A, Bは, 解答方針が見えなかったので, 解説を参考に実装して, ようやく, AC版に到達できた.
2. 苦手なdpの訓練を積めたので, 非常に良かったと思う.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

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

int main(){
    
    // 1. 入力情報.
    int H, W;
    scanf("%d %d", &H, &W);
    rep(i, H){
        char c[111];
        scanf("%s", c);
        rep(j, W) if(c[j] == '#') board[i][j] = 1;
    }
    
    // 2. dp更新.
    rep(i, H) rep(j, W) dp[i][j] = 2020202020;
    dp[0][0] = board[0][0];
    rep(i, H){
        rep(j, W){
            if(!i && !j) continue;
            if(i) dp[i][j] = min(dp[i][j], dp[i - 1][j] + (!board[i - 1][j] && board[i][j]));
            if(j) dp[i][j] = min(dp[i][j], dp[i][j - 1] + (!board[i][j - 1] && board[i][j]));
        }
    }
    
    // 3. 出力.
    printf("%d\n", dp[H - 1][W - 1]);
    return 0;
    
}

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

int board[111][111], dp[111][111];

int main(){

// 1. 入力情報.

int H, W;

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

rep(i, H){

char c[111];

scanf("%s", c);

rep(j, W) if(c[j] == '#') board[i][j] = 1;

}

// 2. dp更新.

rep(i, H) rep(j, W) dp[i][j] = 2020202020;

dp[0][0] = board[0][0];

rep(i, H){

rep(j, W){

if(!i && !j) continue;

if(i) dp[i][j] = min(dp[i][j], dp[i - 1][j] + (!board[i - 1][j] && board[i][j]));

if(j) dp[i][j] = min(dp[i][j], dp[i][j - 1] + (!board[i][j - 1] && board[i][j]));

}

// 3. 出力.

printf("%d\n", dp[H - 1][W - 1]);

return 0;

}

[入力例]
3 3
.##
.#.
##.

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

[入力例]
2 2
#.
.#

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

[入力例]
4 4
..##
#...
###.
###.

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

[入力例]
5 5
.#.#.
#.#.#
.#.#.
#.#.#
.#.#.

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

[入力例]
7 10
##.#.#..#.
#.#.#..#..
.#.#....#.
#.#..#.#.#
.#....#.#.
#..#.#.#..
..#.#.#.#.

[出力例]
5

[入力例]
25 73
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#
#...........#...........#...........#...........#...........#...........#
#.....#.....#..#######..#..#######..#..#######..#.#.......#.#.########..#
#....#.#....#.#.......#.#.#.......#.#.#.......#.#.#.......#.#.........#.#
#....#.#....#.#.......#.#.#.......#.#.#.......#.#.#.......#.#.........#.#
#...#...#...#.#.........#.#.........#.#.......#.#.#.......#.#.........#.#
#...#...#...#.#...####..#.#.........#.#.......#.#..#######..#.#########.#
#..#.###.#..#.#.......#.#.#.........#.#.......#.#.........#.#.........#.#
#..#.....#..#.#.......#.#.#.......#.#.#.......#.#.........#.#.........#.#
#.#.......#.#.#.......#.#.#.......#.#.#.......#.#.........#.#.........#.#
#.#.......#.#..#######..#..#######..#..#######..#.........#.#.########..#
#...........#...........#...........#...........#...........#...........#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#
#...........#...........#...........#...........#...........#...........#
#.########..#.#.......#.#..#######..#..#######..#..#######..#.....#.....#
#.........#.#.#.......#.#.#.......#.#.#.......#.#.#.......#.#....#.#....#
#.........#.#.#.......#.#.#.......#.#.#.......#.#.#.......#.#....#.#....#
#.........#.#.#.......#.#.#.......#.#.#.........#.#.........#...#...#...#
#.#########.#..#######..#.#.......#.#.#.........#.#...####..#...#...#...#
#.........#.#.........#.#.#.......#.#.#.........#.#.......#.#..#.###.#..#
#.........#.#.........#.#.#.......#.#.#.......#.#.#.......#.#..#.....#..#
#.........#.#.........#.#.#.......#.#.#.......#.#.#.......#.#.#.......#.#
#.########..#.........#.#..#######..#..#######..#..#######..#.#.......#.#
#...........#...........#...........#...........#...........#...........#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#

[出力例]
7

[入力例]

3 3

.##

.#.

##.

[出力例]

※AtCoderテストケースより

[入力例]

2 2

[出力例]

※AtCoderテストケースより

[入力例]

4 4

..##

#...

###.

[出力例]

※AtCoderテストケースより

[入力例]

5 5

.#.#.

#.#.#

.#.#.

#.#.#

.#.#.

[出力例]

※AtCoderテストケースより

[入力例]

7 10

##.#.#..#.

#.#.#..#..

.#.#....#.

#.#..#.#.#

.#....#.#.

#..#.#.#..

..#.#.#.#.

[出力例]

[入力例]

25 73

#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#

#...........#...........#...........#...........#...........#...........#

#.....#.....#..#######..#..#######..#..#######..#.#.......#.#.########..#

#....#.#....#.#.......#.#.#.......#.#.#.......#.#.#.......#.#.........#.#

#...#...#...#.#.........#.#.........#.#.......#.#.#.......#.#.........#.#

#...#...#...#.#...####..#.#.........#.#.......#.#..#######..#.#########.#

#..#.###.#..#.#.......#.#.#.........#.#.......#.#.........#.#.........#.#

#..#.....#..#.#.......#.#.#.......#.#.#.......#.#.........#.#.........#.#

#.#.......#.#.#.......#.#.#.......#.#.#.......#.#.........#.#.........#.#

#.#.......#.#..#######..#..#######..#..#######..#.........#.#.########..#

#...........#...........#...........#...........#...........#...........#

#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#

#...........#...........#...........#...........#...........#...........#

#.########..#.#.......#.#..#######..#..#######..#..#######..#.....#.....#

#.........#.#.#.......#.#.#.......#.#.#.......#.#.#.......#.#....#.#....#

#.........#.#.#.......#.#.#.......#.#.#.........#.#.........#...#...#...#

#.#########.#..#######..#.#.......#.#.#.........#.#...####..#...#...#...#

#.........#.#.........#.#.#.......#.#.#.........#.#.......#.#..#.###.#..#

#.........#.#.........#.#.#.......#.#.#.......#.#.#.......#.#..#.....#..#

#.........#.#.........#.#.#.......#.#.#.......#.#.#.......#.#.#.......#.#

#.########..#.........#.#..#######..#..#######..#..#######..#.#.......#.#

#...........#...........#...........#...........#...........#...........#

#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#

[出力例]

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

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

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    char c[MAX];
    scanf("%s", c);
    
    // 2. i以下の整数について, 2 で 合計何回割り切れるか.
    rep(i, 1e6 + 1){
        a[i + 1] = a[i];
        int p = i + 1;
        while(p % 2 == 0) a[i + 1]++, p >>= 1;
    }
    
    // 3. nCr の 偶奇を保存(n = N - 1, r = 0 ～ N - 1).
    rep(i, N){
        LL d = a[N - 1] - a[N - 1 - i] - a[i];
        odd[i] = (d > 0) ? false : true;
    }
    
    // 4. xN1 の 偶奇は？
    LL eo = 0;
    int one = 0;
    rep(i, N){
        int x = c[i] - '1';
        if(odd[i]) eo ^= (LL)x;
        if(x == 1) one++;
    }
    
    // 5. xN1 が 奇数の時.
    if(eo & 1){
        puts("1");
        return 0;
    }
    
    // 6. 入力に, 1 が 含まれる場合.
    if(one){
        puts("0");
        return 0;
    }
    
    // 7. 入力値を, 2で割った場合について, xN1 の 偶奇は？
    eo = 0;
    rep(i, N){
        int x = (c[i] - '1') / 2;
        if(odd[i]) eo ^= (LL)x;
    }
    
    // 8. xN1 が 奇数の時.
    if(eo & 1){
        puts("2");
        return 0;
    }
    
    // 9. 上記以外の場合.
    puts("0");
    return 0;
    
}

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

const int MAX = 1010101;

int x[MAX];

LL a[MAX];

bool odd[MAX];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

char c[MAX];

scanf("%s", c);

// 2. i以下の整数について, 2 で合計何回割り切れるか.

rep(i, 1e6 + 1){

a[i + 1] = a[i];

int p = i + 1;

while(p % 2 == 0) a[i + 1]++, p >>= 1;

}

// 3. nCr の偶奇を保存(n = N - 1, r = 0 ～ N - 1).

rep(i, N){

LL d = a[N - 1] - a[N - 1 - i] - a[i];

odd[i] = (d > 0) ? false : true;

}

// 4. xN1 の偶奇は？

LL eo = 0;

int one = 0;

rep(i, N){

int x = c[i] - '1';

if(odd[i]) eo ^= (LL)x;

if(x == 1) one++;

}

// 5. xN1 が奇数の時.

if(eo & 1){

puts("1");

return 0;

}

// 6. 入力に, 1 が含まれる場合.

if(one){

puts("0");

return 0;

}

// 7. 入力値を, 2で割った場合について, xN1 の偶奇は？

eo = 0;

rep(i, N){

int x = (c[i] - '1') / 2;

if(odd[i]) eo ^= (LL)x;

}

// 8. xN1 が奇数の時.

if(eo & 1){

puts("2");

return 0;

}

// 9. 上記以外の場合.

puts("0");

return 0;

}

[入力例]
4
1231

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

[入力例]
10
2311312312

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

[入力例]
50
22313123321323321222123232131213111222333313212212

[出力例]
0

[入力例]
50
13222321231112223232211331131121122321122321312323

[出力例]
1

[入力例]

1231

[出力例]

※AtCoderテストケースより

[入力例]

2311312312

[出力例]

※AtCoderテストケースより

[入力例]

22313123321323321222123232131213111222333313212212

[出力例]

[入力例]

13222321231112223232211331131121122321122321312323

[出力例]

■参照サイト
AtCoder Grand Contest 043

2021年4月12日

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

C++の練習を兼ねて, AtCoder Beginner Contest 198 の問題C (Compass Walking) ～問題D (Send More Money) を解いてみた.

■感想.
1. 問題C, Dは, 解答方針が見えなかったので, 解説を参考に実装して, ようやく, AC版に到達できた.
2. 問題D の覆面算をプログラムで, 計算できてしまうことが, 個人的には, 面白い問題に感じた.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

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

int main(){
    
    // 1. 入力情報.
    LL R, X, Y;
    scanf("%lld %lld %lld", &R, &X, &Y);
    
    // 2. 必要な歩数の最小値を計算.
    LL X2Y2 = X * X + Y * Y;
    LL ans = (LL)(sqrt(X2Y2) / R);
    if(ans * ans * R * R != X2Y2){
        if(X2Y2 <= 4 * R * R) ans = 2;
        else                  ans++;
    }
    
    // 3. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc198/editorial/1043

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

int main(){

// 1. 入力情報.

LL R, X, Y;

scanf("%lld %lld %lld", &R, &X, &Y);

// 2. 必要な歩数の最小値を計算.

LL X2Y2 = X * X + Y * Y;

LL ans = (LL)(sqrt(X2Y2) / R);

if(ans * ans * R * R != X2Y2){

if(X2Y2 <= 4 * R * R) ans = 2;

else ans++;

}

// 3. 出力.

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

return 0;

}

[入力例]
5 15 0

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

[入力例]
5 11 0

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

[入力例]
3 4 4

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

[入力例]
26 1176 490

[出力例]
49

[入力例]
3939 87912 15129

[出力例]
23

[入力例]

5 15 0

[出力例]

※AtCoderテストケースより

[入力例]

5 11 0

[出力例]

※AtCoderテストケースより

[入力例]

3 4 4

[出力例]

※AtCoderテストケースより

[入力例]

26 1176 490

[出力例]

[入力例]

3939 87912 15129

[出力例]

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

// 解き直し.
// https://atcoder.jp/contests/abc198/editorial/1050
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
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 all(x) x.begin(), x.end()
int a[26];

int main(){
    
    // 1. 入力情報.
    char c1[22], c2[22], c3[22];
    scanf("%s %s %s", c1, c2, c3);
    string S1(c1), S2(c2), S3(c3);
    
    // 2. 文字の種類数を数える.
    set<char> st;
    rep(i, S1.size()) st.insert(S1[i]);
    rep(i, S2.size()) st.insert(S2[i]);
    rep(i, S3.size()) st.insert(S3[i]);
    
    // 3. 11種類以上ある場合.
    int n = st.size();
    if(n > 10){
        puts("UNSOLVABLE");
        return 0;
    }
    
    // 4. アルファベットの出現順に採番.
    int idx = -1;
    for(auto &p : st) a[p - 'a'] = ++idx;
    
    // 5. 全探索.
    LL N1 = 0, N2 = 0, N3 = 0;
    vi z(10);
    iota(all(z), 0);
    bool ok = false;
    do{
        // 初期化.
        N1 = N2 = N3 = 0;
        
        // 先頭文字がゼロか否か.
        int z1 = z[a[S1[0] - 'a']];
        int z2 = z[a[S2[0] - 'a']];
        int z3 = z[a[S3[0] - 'a']];
        
        // 先頭文字がゼロの場合.
        if(z1 == 0 || z2 == 0 || z3 == 0) continue;
        
        // 覆面算の検算.
        rep(i, S1.size()) N1 = 10 * N1 + z[a[S1[i] - 'a']];
        rep(i, S2.size()) N2 = 10 * N2 + z[a[S2[i] - 'a']];
        rep(i, S3.size()) N3 = 10 * N3 + z[a[S3[i] - 'a']];
        if(N1 + N2 == N3){
            ok = true;
            break;
        }
    }while(next_permutation(all(z)));
    
    // 6. 出力.
    if(ok) printf("%lld\n%lld\n%lld\n", N1, N2, N3);
    else   puts("UNSOLVABLE");
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc198/editorial/1050

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

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

int a[26];

int main(){

// 1. 入力情報.

char c1[22], c2[22], c3[22];

scanf("%s %s %s", c1, c2, c3);

string S1(c1), S2(c2), S3(c3);

// 2. 文字の種類数を数える.

set<char> st;

rep(i, S1.size()) st.insert(S1[i]);

rep(i, S2.size()) st.insert(S2[i]);

rep(i, S3.size()) st.insert(S3[i]);

// 3. 11種類以上ある場合.

int n = st.size();

if(n > 10){

puts("UNSOLVABLE");

return 0;

}

// 4. アルファベットの出現順に採番.

int idx = -1;

for(auto &p : st) a[p - 'a'] = ++idx;

// 5. 全探索.

LL N1 = 0, N2 = 0, N3 = 0;

vi z(10);

iota(all(z), 0);

bool ok = false;

do{

// 初期化.

N1 = N2 = N3 = 0;

// 先頭文字がゼロか否か.

int z1 = z[a[S1[0] - 'a']];

int z2 = z[a[S2[0] - 'a']];

int z3 = z[a[S3[0] - 'a']];

// 先頭文字がゼロの場合.

if(z1 == 0 || z2 == 0 || z3 == 0) continue;

// 覆面算の検算.

rep(i, S1.size()) N1 = 10 * N1 + z[a[S1[i] - 'a']];

rep(i, S2.size()) N2 = 10 * N2 + z[a[S2[i] - 'a']];

rep(i, S3.size()) N3 = 10 * N3 + z[a[S3[i] - 'a']];

if(N1 + N2 == N3){

ok = true;

break;

}

}while(next_permutation(all(z)));

// 6. 出力.

if(ok) printf("%lld\n%lld\n%lld\n", N1, N2, N3);

else puts("UNSOLVABLE");

return 0;

}

[入力例]
a
b
c

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

[入力例]
x
x
y

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

[入力例]
p
q
p

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

[入力例]
abcd
efgh
ijkl

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

[入力例]
send
more
money

[出力例]
9567
1085
10652
※AtCoderテストケースより

[入力例]
abcdbde
faaccde
fdagheda

[出力例]
8950904
1885504
10836408

[入力例]
cgjibicjjh
hebdidbdaf
babbcabedac

[出力例]
2698182997
7413831305
10112014302

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

[出力例]

UNSOLVABLE

※AtCoderテストケースより

[入力例]

abcd

efgh

ijkl

[出力例]

UNSOLVABLE

※AtCoderテストケースより

[入力例]

send

money

[出力例]

9567

1085

10652

※AtCoderテストケースより

[入力例]

abcdbde

faaccde

fdagheda

[出力例]

8950904

1885504

10836408

[入力例]

cgjibicjjh

hebdidbdaf

babbcabedac

[出力例]

2698182997

7413831305

10112014302

■参照サイト
AtCoder Beginner Contest 198

C++の練習を兼ねて, AtCoder Grand Contest 027 の 問題C (ABland Yard) を解いてみた.

C++の練習を兼ねて, AtCoder Grand Contest 027 の 問題A (Candy Distribution Again) ～ 問題B (Garbage Collector) を解いてみた.

C++の練習を兼ねて, AtCoder Grand Contest 017 の 問題C (Snuke and Spells) を解いてみた.

概要

感想

PrimitiveOps

参照サイト

C++の練習を兼ねて, AtCoder Regular Contest 116 の 問題D (I Wanna Win The Game) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 116 の 問題C (Multiple Sequences) を解いてみた.

C++の練習を兼ねて, AtCoder Grand Contest 018 の 問題C (Coins) を解いてみた.

C++の練習を兼ねて, AtCoder Grand Contest 020 の 問題A (Move and Win) ～ 問題B (Ice Rink Game) を解いてみた.

C++の練習を兼ねて, AtCoder Grand Contest 043 の 問題A (Range Flip Find Route) ～ 問題B (123 Triangle) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 198 の 問題C (Compass Walking) ～ 問題D (Send More Money) を解いてみた.

C++の練習を兼ねて, AtCoder Grand Contest 027 の問題C (ABland Yard) を解いてみた.

C++の練習を兼ねて, AtCoder Grand Contest 027 の問題A (Candy Distribution Again) ～問題B (Garbage Collector) を解いてみた.

C++の練習を兼ねて, AtCoder Grand Contest 017 の問題C (Snuke and Spells) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 116 の問題D (I Wanna Win The Game) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 116 の問題C (Multiple Sequences) を解いてみた.

C++の練習を兼ねて, AtCoder Grand Contest 018 の問題C (Coins) を解いてみた.

C++の練習を兼ねて, AtCoder Grand Contest 020 の問題A (Move and Win) ～問題B (Ice Rink Game) を解いてみた.

C++の練習を兼ねて, AtCoder Grand Contest 043 の問題A (Range Flip Find Route) ～問題B (123 Triangle) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 198 の問題C (Compass Walking) ～問題D (Send More Money) を解いてみた.