C++ | 個人用メモ帳

2020年7月7日

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

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

■感想.
1. 方針が見えなかったので, 解説を参考に実装したところ, AC版となった.
2. なじみの薄い multiset の訓練が出来たので, 非常に良かったと思う.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/abc170/editorial.pdf
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
LL A[202020];
int B[202020];
multiset<LL> rate[202020]; // それぞれの幼稚園に所属する幼児のレートの集合.
multiset<LL> maxRate;      // それぞれの幼稚園の最強園児のレートの集合.

int main(){
    
    // 1. 入力情報.
    int N, Q;
    scanf("%d %d", &N, &Q);
    repx(i, 1, N + 1) scanf("%lld %d", &A[i], &B[i]);
    
    // 2. 事前準備(以下, 解説通り).
    repx(i, 1, N + 1) rate[B[i]].insert(A[i]);
    repx(i, 1, 202020){
        if(rate[i].size() > 0){
            auto itr = rate[i].end();
            maxRate.insert(*(--itr));
        }
    }
    
    // 3. クエリ回答.
    int C, D;
    rep(i, Q){
        // 3-1. 転園情報.
        scanf("%d %d", &C, &D);
        int at = B[C]; // 転園元幼稚園.
        
        // 3-2. maxRate から 転園元幼稚園の最強園児のレートを削除.
        auto it1 = rate[at].end();
        auto it2 = maxRate.find(*(--it1));
        maxRate.erase(it2); // 1個だけ削除.
        
        // 3-3. 転園元幼稚園から転園する園児のレートを削除.
        auto it3 = rate[at].find(A[C]);
        rate[at].erase(it3); // 1個だけ削除.
        
        // 3-4. maxRate に 転園元幼稚園の最強園児のレートを追加.
        if(rate[at].size() > 0){
            auto it4 = rate[at].end();
            maxRate.insert(*(--it4));
        }
        
        // 3-5. maxRate から 転園先幼稚園の最強園児のレートを削除.
        if(rate[D].size() > 0){
            auto it5 = rate[D].end();
            auto it6 = maxRate.find(*(--it5));
            maxRate.erase(it6); // 1個だけ削除.
        }
        
        // 3-6. 転園先幼稚園に, 転園する園児のレートを追加.
        rate[D].insert(A[C]);
        
        // 3-7. maxRate に 転園先幼稚園の最強園児のレートを追加.
        auto it7 = rate[D].end();
        maxRate.insert(*(--it7));
        
        // 3-8. 転園する園児の所属する幼稚園の番号を更新.
        B[C] = D;
        
        // 3-9. 出力.
        auto it8 = maxRate.begin();
        LL ans = *it8;
        printf("%d\n", ans);
    }
    return 0;
    
}

// 解き直し.

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

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

#define pb push_back

LL A[202020];

int B[202020];

multiset<LL> rate[202020]; // それぞれの幼稚園に所属する幼児のレートの集合.

multiset<LL> maxRate; // それぞれの幼稚園の最強園児のレートの集合.

int main(){

// 1. 入力情報.

int N, Q;

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

repx(i, 1, N + 1) scanf("%lld %d", &A[i], &B[i]);

// 2. 事前準備(以下, 解説通り).

repx(i, 1, N + 1) rate[B[i]].insert(A[i]);

repx(i, 1, 202020){

if(rate[i].size() > 0){

auto itr = rate[i].end();

maxRate.insert(*(--itr));

}

// 3. クエリ回答.

int C, D;

rep(i, Q){

// 3-1. 転園情報.

scanf("%d %d", &C, &D);

int at = B[C]; // 転園元幼稚園.

// 3-2. maxRate から転園元幼稚園の最強園児のレートを削除.

auto it1 = rate[at].end();

auto it2 = maxRate.find(*(--it1));

maxRate.erase(it2); // 1個だけ削除.

// 3-3. 転園元幼稚園から転園する園児のレートを削除.

auto it3 = rate[at].find(A[C]);

rate[at].erase(it3); // 1個だけ削除.

// 3-4. maxRate に転園元幼稚園の最強園児のレートを追加.

if(rate[at].size() > 0){

auto it4 = rate[at].end();

maxRate.insert(*(--it4));

}

// 3-5. maxRate から転園先幼稚園の最強園児のレートを削除.

if(rate[D].size() > 0){

auto it5 = rate[D].end();

auto it6 = maxRate.find(*(--it5));

maxRate.erase(it6); // 1個だけ削除.

}

// 3-6. 転園先幼稚園に, 転園する園児のレートを追加.

rate[D].insert(A[C]);

// 3-7. maxRate に転園先幼稚園の最強園児のレートを追加.

auto it7 = rate[D].end();

maxRate.insert(*(--it7));

// 3-8. 転園する園児の所属する幼稚園の番号を更新.

B[C] = D;

// 3-9. 出力.

auto it8 = maxRate.begin();

LL ans = *it8;

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

}

return 0;

}

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

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

[入力例]
2 2
4208 1234
3056 5678
1 2020
2 2020

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

[入力例]
20 25
48039234 1
106894727 3
54034116 4
29384308 1
25419214 1
41960290 2
113411995 1
105430452 5
101633542 2
63004981 3
15337594 4
10494255 3
113037996 2
31400866 1
38043117 4
64839068 4
80433133 4
106837808 5
101886442 5
48230109 2
1 3
4 2
9 3
15 3
19 3
2 1
9 1
12 4
17 3
17 1
18 1
20 5
10 5
7 5
4 1
16 1
20 3
3 1
5 5
8 2
11 1
13 5
14 3
6 5
1 5

[出力例]
80433133
80433133
80433133
80433133
80433133
80433133
80433133
80433133
64839068
64839068
64839068
64839068
64839068
64839068
64839068
54034116
54034116
15337594
15337594
15337594
10494255
10494255
10494255
10494255
10494255

100

101

102

103

104

[入力例]

6 3

8 1

6 2

9 3

1 1

2 2

1 3

4 3

2 1

1 2

[出力例]

※AtCoderテストケースより

[入力例]

2 2

4208 1234

3056 5678

1 2020

2 2020

[出力例]

3056

4208

※AtCoderテストケースより

[入力例]

20 25

48039234 1

106894727 3

54034116 4

29384308 1

25419214 1

41960290 2

113411995 1

105430452 5

101633542 2

63004981 3

15337594 4

10494255 3

113037996 2

31400866 1

38043117 4

64839068 4

80433133 4

106837808 5

101886442 5

48230109 2

1 3

4 2

9 3

15 3

19 3

2 1

9 1

12 4

17 3

17 1

18 1

20 5

10 5

7 5

4 1

16 1

20 3

3 1

5 5

8 2

11 1

13 5

14 3

6 5

1 5

[出力例]

80433133

64839068

54034116

15337594

10494255

■参照サイト
AtCoder Beginner Contest 170

2020年7月7日

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

C++の練習を兼ねて, AtCoder Regular Contest 051 の問題A (塗り絵) ～問題B (互除法) を解いてみた.

■感想.
1. 問題A は, 図形の性質を絞り込めた点, 問題B は, Fibonacci数列に帰着出来たので, AC版になったと思う.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

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

int main(){
    
    // 1. 入力情報.
    int x1, y1, r;
    int x2, y2, x3, y3;
    scanf("%d %d %d %d %d %d %d", &x1, &y1, &r, &x2, &y2, &x3, &y3);
    
    // 2. 赤が無い場合.
    int cLx = x1 - r, cRx = x1 + r, cUy = y1 + r, cDy = y1 - r;
    if(x2 <= cLx && x3 >= cRx && y2 <= cDy && y3 >= cUy){
        puts("NO");
        puts("YES");
        return 0;
    }
    
    // 3. 青が無い場合.
    // -> 円の中心から, 長方形の四隅が, いずれも 距離 r 以下となっている場合.
    int lu = (x2 - x1) * (x2 - x1) + (y3 - y1) * (y3 - y1); // 左上.
    int ld = (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1); // 左下.
    int ru = (x3 - x1) * (x3 - x1) + (y3 - y1) * (y3 - y1); // 右上.
    int rd = (x3 - x1) * (x3 - x1) + (y2 - y1) * (y2 - y1); // 右下.
    int r2 = r * r;
    if(lu <= r2 && ld <= r2 && ru <= r2 && rd <= r2){
        puts("YES");
        puts("NO");
        return 0;
    }
    
    // 4. それ以外.
    puts("YES");
    puts("YES");
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

int main(){

// 1. 入力情報.

int x1, y1, r;

int x2, y2, x3, y3;

scanf("%d %d %d %d %d %d %d", &x1, &y1, &r, &x2, &y2, &x3, &y3);

// 2. 赤が無い場合.

int cLx = x1 - r, cRx = x1 + r, cUy = y1 + r, cDy = y1 - r;

if(x2 <= cLx && x3 >= cRx && y2 <= cDy && y3 >= cUy){

puts("NO");

puts("YES");

return 0;

}

// 3. 青が無い場合.

// -> 円の中心から, 長方形の四隅が, いずれも距離 r 以下となっている場合.

int lu = (x2 - x1) * (x2 - x1) + (y3 - y1) * (y3 - y1); // 左上.

int ld = (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1); // 左下.

int ru = (x3 - x1) * (x3 - x1) + (y3 - y1) * (y3 - y1); // 右上.

int rd = (x3 - x1) * (x3 - x1) + (y2 - y1) * (y2 - y1); // 右下.

int r2 = r * r;

if(lu <= r2 && ld <= r2 && ru <= r2 && rd <= r2){

puts("YES");

puts("NO");

return 0;

}

// 4. それ以外.

puts("YES");

return 0;

}

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

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

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

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

[入力例]
0 0 5
-2 -2 2 1

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

[入力例]
0 0 2
0 0 4 4

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

[入力例]
0 0 5
-4 -4 4 4

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

[入力例]

-1 -1 2

2 3 4 5

[出力例]

YES

※AtCoderのテストケースより

[入力例]

0 1 1

-2 0 4 3

[出力例]

YES

※AtCoderのテストケースより

[入力例]

0 0 5

-2 -2 2 1

[出力例]

YES

※AtCoderのテストケースより

[入力例]

0 0 2

0 0 4 4

[出力例]

YES

※AtCoderのテストケースより

[入力例]

0 0 5

-4 -4 4 4

[出力例]

YES

※AtCoderのテストケースより

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

#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 f[41];

int main(){
    
    // 1. 入力情報.
    int K;
    scanf("%d", &K);
    
    // 2. Fibonacci数列を計算.
    f[0] = 1, f[1] = 1;
    repx(i, 2, 41) f[i] = f[i - 1] + f[i - 2];
    // rep(i, 41) printf("%d\n", f[i]);
    
    // 3. 出力.
    printf("%d %d\n", f[K - 1], f[K]);
    return 0;
    
}

#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 f[41];

int main(){

// 1. 入力情報.

int K;

scanf("%d", &K);

// 2. Fibonacci数列を計算.

f[0] = 1, f[1] = 1;

repx(i, 2, 41) f[i] = f[i - 1] + f[i - 2];

// rep(i, 41) printf("%d\n", f[i]);

// 3. 出力.

printf("%d %d\n", f[K - 1], f[K]);

return 0;

}

[入力例]
1

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

[入力例]
3

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

但し, 上記のプログラムでは, 以下の内容が出力される.
2 3

[入力例]
12

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

但し, 上記のプログラムでは, 以下の内容が出力される.
144 233

[入力例]
25

[出力例]
75025 121393

[入力例]
40

[出力例]
102334155 165580141

[入力例]

[出力例]

1 1

※AtCoderのテストケースより

[入力例]

[出力例]

4 5

※AtCoderのテストケースより

但し, 上記のプログラムでは, 以下の内容が出力される.

2 3

[入力例]

[出力例]

314159265 358979323

※AtCoderのテストケースより

但し, 上記のプログラムでは, 以下の内容が出力される.

144 233

[入力例]

[出力例]

75025 121393

[入力例]

[出力例]

102334155 165580141

■参照サイト
AtCoder Regular Contest 051

2020年7月6日

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

C++の練習を兼ねて, AtCoder Beginner Contest 173 の問題D (Chat in a Circle) を解いてみた.

■感想.
1. 大きい方から, 最大2回ずつ加算していく方針で, AC版となった.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

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

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%lld", &A[i]);
    
    // 2. sort.
    sort(A, A + N, greater<LL>());
    
    // 3. 集計(※大きい値から, 最大2回ずつ加算).
    LL ans = A[0];
    int add = 1;
    repx(i, 1, N / 2 + 1){
        if(++add < N) ans += A[i];
        if(++add < N) ans += A[i];
    }
    
    // 4. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

LL A[202020];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

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

// 2. sort.

sort(A, A + N, greater<LL>());

// 3. 集計(※大きい値から, 最大2回ずつ加算).

LL ans = A[0];

int add = 1;

repx(i, 1, N / 2 + 1){

if(++add < N) ans += A[i];

}

// 4. 出力.

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

return 0;

}

[入力例]
4
2 2 1 3

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

[入力例]
7
1 1 1 1 1 1 1

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

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

[出力例]
81

[入力例]
13
18 23 27 1 5 9 7 13 17 22 8 19 28

[出力例]
263

[入力例]
33
314159265 35897932 3846264 338327 95028 8419 716 93 9 937 5105 82097 494459 23078 1640 628 620 89 986 28034 82 534 211 7067 982 14808 65132 823066470 938446095 50582231 725359 40812848 11174502

[出力例]
3501242955

[入力例]

2 2 1 3

[出力例]

※AtCoderテストケースより

[入力例]

1 1 1 1 1 1 1

[出力例]

※AtCoderテストケースより

[入力例]

5 2 2 1 8 3 7 9 10 13

[出力例]

[入力例]

18 23 27 1 5 9 7 13 17 22 8 19 28

[出力例]

263

[入力例]

314159265 35897932 3846264 338327 95028 8419 716 93 9 937 5105 82097 494459 23078 1640 628 620 89 986 28034 82 534 211 7067 982 14808 65132 823066470 938446095 50582231 725359 40812848 11174502

[出力例]

3501242955

■参照サイト
AtCoder Beginner Contest 173

2020年7月3日2020年7月3日

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

C++の練習を兼ねて, AtCoder Beginner Contest 172 の問題F (Unfair Nim) を解いてみた.

■感想.
1. 解答方針が, 全く見えなかったので, 解説を参考に実装したところ何とかAC版となった.
2. bit を計算する時, 1 でなく, 1LL を使うとか, S = a + b のチェックなど, 考慮事項も多く, いろいろ苦労したように思う.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

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

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%lld", &A[i]);
    
    // 2. 解説通り.
    // 2-1. S, X を 設定.
    LL S = A[0] + A[1], X = 0LL;
    repx(i, 2, N) X ^= A[i];
    
    // 2-2. D を 設定.
    LL D = (S - X) / 2LL;
    // printf("S=%lld X=%lld D=%lld\n", S, X, D);
    
    // 2-3. D が 非負整数で無い, または, D と X の 共通ビットがある,
    // または, D が A[0] よりも大きい場合.
    if(D < 0LL || (D & X) != 0LL || D > A[0]){
        puts("-1");
        return 0;
    }
    
    // 2-4. Y を 設定.
    LL Y = 0LL, a = D;
    repr(i, 40, 0){
        LL bit = 1LL << i;
        // printf("bit=%lld (X & bit)=%lld X=%lld Y=%lld (X + Y)=%lld\n", bit, (X & bit), X, Y, X + Y);
        if(X & bit){
            LL c = D ^ (Y | bit);
            // printf("c=%lld\n", c);
            if(c <= A[0]) Y |= bit, X -= bit, a = D ^ Y;
        }
    }
    
    // 2-5. S = a + b が成立しているかのチェック.
    // -> n2_03 などへの対策.
    // ex.
    // 2
    // 5 6
    // -> S = 11, a + b = 10 の ように 差分が出る場合がある.
    LL b = D ^ X;
    // printf("a=%lld b=%lld (a + b)=%lld\n", a, b, a + b);
    if(S != a + b){
        puts("-1");
        return 0;
    }
    
    // 2-6. a < A[0] であるかのチェック.
    // -> sample_03 などへの対策.
    if(a == 0){
        puts("-1");
        return 0;
    }
    
    // 3. 出力.
    printf("%lld\n", A[0] - a);
    return 0;
    
}

// C++ (GCC 9.2.1)

// 解き直し.

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

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

LL A[333];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

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

// 2. 解説通り.

// 2-1. S, X を設定.

LL S = A[0] + A[1], X = 0LL;

repx(i, 2, N) X ^= A[i];

// 2-2. D を設定.

LL D = (S - X) / 2LL;

// printf("S=%lld X=%lld D=%lld\n", S, X, D);

// 2-3. D が非負整数で無い, または, D と X の共通ビットがある,

// または, D が A[0] よりも大きい場合.

if(D < 0LL || (D & X) != 0LL || D > A[0]){

puts("-1");

return 0;

}

// 2-4. Y を設定.

LL Y = 0LL, a = D;

repr(i, 40, 0){

LL bit = 1LL << i;

// printf("bit=%lld (X & bit)=%lld X=%lld Y=%lld (X + Y)=%lld\n", bit, (X & bit), X, Y, X + Y);

if(X & bit){

LL c = D ^ (Y | bit);

// printf("c=%lld\n", c);

if(c <= A[0]) Y |= bit, X -= bit, a = D ^ Y;

}

// 2-5. S = a + b が成立しているかのチェック.

// -> n2_03 などへの対策.

// ex.

// 2

// 5 6

// -> S = 11, a + b = 10 のように差分が出る場合がある.

LL b = D ^ X;

// printf("a=%lld b=%lld (a + b)=%lld\n", a, b, a + b);

if(S != a + b){

puts("-1");

return 0;

}

// 2-6. a < A[0] であるかのチェック.

// -> sample_03 などへの対策.

if(a == 0){

puts("-1");

return 0;

}

// 3. 出力.

printf("%lld\n", A[0] - a);

return 0;

}

[入力例]
2
5 3

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

[入力例]
2
3 5

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

[入力例]
3
1 1 2

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

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

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

[入力例]
3
4294967297 8589934593 12884901890

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

[入力例]
10
192 210 39 247 115 265 70 299 85 250

[出力例]
3

[入力例]
15
321 92 304 214 1 298 69 321 220 298 186 233 189 320 192

[出力例]
10

[入力例]

5 3

[出力例]

※AtCoderテストケースより

[入力例]

3 5

[出力例]

-1

※AtCoderテストケースより

[入力例]

1 1 2

[出力例]

-1

※AtCoderテストケースより

[入力例]

10 9 8 7 6 5 4 3

[出力例]

※AtCoderテストケースより

[入力例]

4294967297 8589934593 12884901890

[出力例]

※AtCoderテストケースより

[入力例]

192 210 39 247 115 265 70 299 85 250

[出力例]

[入力例]

321 92 304 214 1 298 69 321 220 298 186 233 189 320 192

[出力例]

■参照サイト
AtCoder Beginner Contest 172

2020年6月28日

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

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

■感想.
1. 解答方針が, 全く見えなかったので, 解説の公式を実装したところ何とかAC版となった.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// C++ (GCC 9.2.1)
// 解き直し.
// https://img.atcoder.jp/abc172/editorial.pdf
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
const LL MOD = 1e9 + 7;
const int LIMIT = 1010101;
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;
}

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

// 組み合わせ(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. 解説通り.
    LL ans = 0;
    rep(k, n + 1){
        // 2-1. nCk.
        LL c = combination((LL)n, (LL)k);
        
        // 2-2. -1 の k乗.
        c *= mPow(MOD - 1, (LL)k);
        c %= MOD;
        
        // 2-3. mPk.
        c *= permutation((LL)m, (LL)k);
        c %= MOD;
        
        // 2-4. (m - k)P(n - k).
        c *= permutation((LL)(m - k), (LL)(n - k));
        c %= MOD;
        
        // 2-5. (m - k)P(n - k).
        c *= permutation((LL)(m - k), (LL)(n - k));
        c %= MOD;
        
        // 2-6. 集計.
        ans += c;
        ans %= MOD;
    }
    
    // 3. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// C++ (GCC 9.2.1)

// 解き直し.

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

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

const LL MOD = 1e9 + 7;

const int LIMIT = 1010101;

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;

}

// 順列(nPk)計算用(mod版).

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

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

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

// @return: 順列(nPk)の計算結果(mod版).

LL permutation(LL n, LL k){

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

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

return ret;

}

// 組み合わせ(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. 解説通り.

LL ans = 0;

rep(k, n + 1){

// 2-1. nCk.

LL c = combination((LL)n, (LL)k);

// 2-2. -1 の k乗.

c *= mPow(MOD - 1, (LL)k);

c %= MOD;

// 2-3. mPk.

c *= permutation((LL)m, (LL)k);

c %= MOD;

// 2-4. (m - k)P(n - k).

c *= permutation((LL)(m - k), (LL)(n - k));

c %= MOD;

// 2-5. (m - k)P(n - k).

c *= permutation((LL)(m - k), (LL)(n - k));

c %= MOD;

// 2-6. 集計.

ans += c;

ans %= MOD;

}

// 3. 出力.

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

return 0;

}

[入力例]
2 2

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

[入力例]
2 3

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

[入力例]
141421 356237

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

[入力例]
202020 303030

[出力例]
469521751

[入力例]

2 2

[出力例]

※AtCoderテストケースより

[入力例]

2 3

[出力例]

※AtCoderテストケースより

[入力例]

141421 356237

[出力例]

881613484

※AtCoderテストケースより

[入力例]

202020 303030

[出力例]

469521751

■参照サイト
AtCoder Beginner Contest 172

2020年6月27日

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

C++の練習を兼ねて, AtCoder Beginner Contest 172 の問題D (Sum of Divisors) を解いてみた.

■感想.
1. Nの上限が大きく見えたが, 何とかAC版となった.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

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

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    
    // 2. 約数を保存.
    repx(i, 1, 10101010) repex(j, i, 10101010, i) divisor[j]++;
    
    // 3. 集計.
    LL ans = 0;
    repx(i, 1, N + 1) ans += i * divisor[i];
    
    // 4. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

LL divisor[10101010];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

// 2. 約数を保存.

repx(i, 1, 10101010) repex(j, i, 10101010, i) divisor[j]++;

// 3. 集計.

LL ans = 0;

repx(i, 1, N + 1) ans += i * divisor[i];

// 4. 出力.

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

return 0;

}

[入力例]
4

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

[入力例]
100

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

[入力例]
10000000

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

[入力例]
172

[出力例]
86649

[入力例]
2020

[出力例]
16878752

[入力例]
202020

[出力例]
262648659389

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

100

[出力例]

26879

※AtCoderテストケースより

[入力例]

10000000

[出力例]

838627288460105

※AtCoderテストケースより

[入力例]

172

[出力例]

86649

[入力例]

2020

[出力例]

16878752

[入力例]

202020

[出力例]

262648659389

■参照サイト
AtCoder Beginner Contest 172

2020年6月24日

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

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

■感想.
1. 解答方針が全く見えなかったので, 解説を見て実装したところ, AC版となった.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// C++ (GCC 9.2.1)
// 解き直し.
// https://img.atcoder.jp/abc171/editorial.pdf
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
const LL MOD = 1e9 + 7;
const int LIMIT = 2020202;
LL FAC[LIMIT], INV[LIMIT], C[LIMIT], mPow25[LIMIT], mPow26[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 K;
    char c[1010101];
    scanf("%d %s", &K, c);
    int N = strlen(c);
    FAC[0] = 1, mPow25[0] = 1, mPow26[0] = 1;
    repx(i, 1, LIMIT){
        FAC[i] = (LL)i * FAC[i - 1] % MOD;
        mPow25[i] = mPow25[i - 1] * 25LL % MOD;
        mPow26[i] = mPow26[i - 1] * 26LL % MOD;
    }
    rep(i, LIMIT) INV[i] = mPow(FAC[i], MOD - 2);
    
    // 2. S[N] の 位置ごとに集計(解説通り).
    LL ans = 0;
    repx(i, N - 1, N + K){
        // 2-1. S[1] ～ S[N - 1] の 選び方.
        LL a = combination((LL)i, (LL)(N - 1));
        
        // 2-2. S[i]以外の文字の選び方.
        int cnt = (N + K - 1) - i; // S[N]以降の文字数.
        LL b = mPow25[K - cnt] * mPow26[cnt] % MOD;
        
        // 2-3. 集計.
        ans = (ans + a * b) % MOD;
    }
    
    // 3. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// C++ (GCC 9.2.1)

// 解き直し.

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

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

const LL MOD = 1e9 + 7;

const int LIMIT = 2020202;

LL FAC[LIMIT], INV[LIMIT], C[LIMIT], mPow25[LIMIT], mPow26[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 K;

char c[1010101];

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

int N = strlen(c);

FAC[0] = 1, mPow25[0] = 1, mPow26[0] = 1;

repx(i, 1, LIMIT){

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

mPow25[i] = mPow25[i - 1] * 25LL % MOD;

mPow26[i] = mPow26[i - 1] * 26LL % MOD;

}

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

// 2. S[N] の位置ごとに集計(解説通り).

LL ans = 0;

repx(i, N - 1, N + K){

// 2-1. S[1] ～ S[N - 1] の選び方.

LL a = combination((LL)i, (LL)(N - 1));

// 2-2. S[i]以外の文字の選び方.

int cnt = (N + K - 1) - i; // S[N]以降の文字数.

LL b = mPow25[K - cnt] * mPow26[cnt] % MOD;

// 2-3. 集計.

ans = (ans + a * b) % MOD;

}

// 3. 出力.

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

return 0;

}

[入力例]
5
oof

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

[入力例]
37564
whydidyoudesertme

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

[入力例]
314159
atcoderonehundredandseventyfirsttaskf

[出力例]
791705302

[入力例]

oof

[出力例]

575111451

※AtCoderテストケースより

[入力例]

37564

whydidyoudesertme

[出力例]

318008117

※AtCoderテストケースより

[入力例]

314159

atcoderonehundredandseventyfirsttaskf

[出力例]

791705302

■参照サイト
AtCoder Beginner Contest 171

2020年6月22日

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

C++の練習を兼ねて, AtCoder Beginner Contest 171 の問題D (Replacing) ～問題E (Red Scarf) を解いてみた.

■感想.
1. 解答方針を決めることが出来たので, 何とかAC版となった.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

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

int main(){
    
    // 1. 入力情報.
    int N, a, b, c, Q;
    LL S = 0;
    scanf("%d", &N);
    rep(i, N){
        scanf("%d", &a);
        S += (LL)a;
        memo[a]++;
    }
    scanf("%d", &Q);
    
    // 2. クエリ回答.
    rep(i, Q){
        // 2-1. 和を再計算.
        scanf("%d %d", &b, &c);
        LL t = memo[b];
        S = S - (LL)b * t + (LL)c * t;
        
        // 2-2. 操作結果を保存.
        memo[c] += t;
        memo[b] = 0;
        
        // 2-3. 出力.
        printf("%lld\n", S);
    }
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

LL memo[101010];

int main(){

// 1. 入力情報.

int N, a, b, c, Q;

LL S = 0;

scanf("%d", &N);

rep(i, N){

scanf("%d", &a);

S += (LL)a;

memo[a]++;

}

scanf("%d", &Q);

// 2. クエリ回答.

rep(i, Q){

// 2-1. 和を再計算.

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

LL t = memo[b];

S = S - (LL)b * t + (LL)c * t;

// 2-2. 操作結果を保存.

memo[c] += t;

memo[b] = 0;

// 2-3. 出力.

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

}

return 0;

}

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

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

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

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

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

[出力例]
102
200
2000
※AtCoderテストケースより

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

[出力例]
36
38
44
38
39
48
49
42
40
10

[入力例]

1 2 3 4

1 2

3 4

2 4

[出力例]

※AtCoderテストケースより

[入力例]

1 1 1 1

1 2

2 1

3 5

[出力例]

※AtCoderテストケースより

[入力例]

1 2

1 100

2 100

100 1000

[出力例]

102

200

2000

※AtCoderテストケースより

[入力例]

8 2 9 3 2 3 7

3 4

4 5

5 8

7 1

1 2

8 11

9 10

10 3

3 1

11 1

[出力例]

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

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

int main(){
    
    // 1. 入力情報.
    int N, Xor = 0;
    scanf("%d", &N);
    rep(i, N){
        scanf("%lld", &a[i]);
        Xor ^= a[i];
    }
    
    // 2. 出力.
    rep(i, N){
        printf("%lld", a[i] ^ Xor);
        if(i < N - 1) printf(" ");
    }
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

LL a[202020];

int main(){

// 1. 入力情報.

int N, Xor = 0;

scanf("%d", &N);

rep(i, N){

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

Xor ^= a[i];

}

// 2. 出力.

rep(i, N){

printf("%lld", a[i] ^ Xor);

if(i < N - 1) printf(" ");

}

return 0;

}

[入力例]
4
20 11 9 24

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

[入力例]
10
101 1006 923 1152 243 607 1005 864 98 444

[出力例]
1802 1153 1268 1007 1948 1328 1154 1039 1805 1747

[入力例]
30
95948301 25660905 107687938 81724256 69206777 19614799 120989871 55051935 54291228 121431164 20222913 50107698 60681606 48113387 117544838 103545334 20860918 75311129 72002798 59007479 1885982 84109468 24379967 70200226 26101243 23180604 56675644 103195012 79811653 114890223

[出力例]
10453951 77594715 55360944 33066706 17272651 67944957 34710813 107973421 102491822 35350990 68361843 131799168 112877620 133802841 36051508 51147844 68796996 22717867 23929180 111406149 87771820 2417966 72585101 17344016 78235721 71710862 105332878 50408502 31873527 67016797

[入力例]

20 11 9 24

[出力例]

26 5 7 22

※AtCoderテストケースより

[入力例]

101 1006 923 1152 243 607 1005 864 98 444

[出力例]

1802 1153 1268 1007 1948 1328 1154 1039 1805 1747

[入力例]

95948301 25660905 107687938 81724256 69206777 19614799 120989871 55051935 54291228 121431164 20222913 50107698 60681606 48113387 117544838 103545334 20860918 75311129 72002798 59007479 1885982 84109468 24379967 70200226 26101243 23180604 56675644 103195012 79811653 114890223

[出力例]

10453951 77594715 55360944 33066706 17272651 67944957 34710813 107973421 102491822 35350990 68361843 131799168 112877620 133802841 36051508 51147844 68796996 22717867 23929180 111406149 87771820 2417966 72585101 17344016 78235721 71710862 105332878 50408502 31873527 67016797

■参照サイト
AtCoder Beginner Contest 171

2020年6月21日

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

C++の練習を兼ねて, AtCoder Beginner Contest 170 の問題D (Not Divisible) を解いてみた.

■感想.
1. 実装方針が決まるまで苦労したものの, 何とかAC版となった.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

■C++版プログラム(問題D／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--)
#define pb push_back
int a[1010101], cnt[1010101], d[1010101];

int main(){
    
    // 1. 入力情報.
    int N;
    set<int> s;
    scanf("%d", &N);
    rep(i, N){
        scanf("%d", &a[i]);
        cnt[a[i]]++;
        s.insert(a[i]);
    }
    
    // 2. 割り切れるか確認.
    for(auto &p : s){
        repex(i, p * 2, 1010101, p) if(cnt[i]) d[i]++;
    }
    
    // 3. 出力.
    int ans = 0;
    rep(i, N) if(cnt[a[i]] == 1 && !d[a[i]]) ans++;
    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--)

#define pb push_back

int a[1010101], cnt[1010101], d[1010101];

int main(){

// 1. 入力情報.

int N;

set<int> s;

scanf("%d", &N);

rep(i, N){

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

cnt[a[i]]++;

s.insert(a[i]);

}

// 2. 割り切れるか確認.

for(auto &p : s){

repex(i, p * 2, 1010101, p) if(cnt[i]) d[i]++;

}

// 3. 出力.

int ans = 0;

rep(i, N) if(cnt[a[i]] == 1 && !d[a[i]]) ans++;

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

return 0;

}

[入力例]
5
24 11 8 3 16

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

[入力例]
4
5 5 5 5

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

[入力例]
10
33 18 45 28 8 19 89 86 2 4

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

[入力例]
30
87 12 64 100 57 48 54 18 91 63 81 94 13 17 5 99 98 77 85 56 64 72 33 16 84 60 44 50 92 2

[出力例]
10

[入力例]
50
186 33 122 31 138 129 149 32 22 144 163 27 153 180 140 199 111 42 128 177 36 88 131 29 61 131 91 171 89 38 26 48 122 29 149 186 151 184 124 19 144 123 65 174 113 183 186 106 49 186

[出力例]
28

[入力例]

24 11 8 3 16

[出力例]

※AtCoderテストケースより

[入力例]

5 5 5 5

[出力例]

※AtCoderテストケースより

[入力例]

33 18 45 28 8 19 89 86 2 4

[出力例]

※AtCoderテストケースより

[入力例]

87 12 64 100 57 48 54 18 91 63 81 94 13 17 5 99 98 77 85 56 64 72 33 16 84 60 44 50 92 2

[出力例]

[入力例]

186 33 122 31 138 129 149 32 22 144 163 27 153 180 140 199 111 42 128 177 36 88 131 29 61 131 91 171 89 38 26 48 122 29 149 186 151 184 124 19 144 123 65 174 113 183 186 106 49 186

[出力例]

■参照サイト
AtCoder Beginner Contest 170

2020年6月21日2020年6月21日

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

C++の練習を兼ねて, AtCoder Beginner Contest 169 の問題F (F – Knapsack for All Subsets) を解いてみた.

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

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

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

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

int main(){
    
    // 1. 入力情報.
    int N, S;
    scanf("%d %d", &N, &S);
    rep(i, N) scanf("%lld", &a[i]);
    
    // 2. 2 の べき乗 を 保存.
    mPow2[0] = 1;
    repx(i, 1, 3030) mPow2[i] = mPow2[i - 1] * 2, mPow2[i] %= MOD;
    
    // 3. dp更新.
    repx(i, 1, N + 1){
        repr(j, S, 0){
            int d = j - (int)a[i - 1];
            if(d > 0 && memo[d]) dp[i][j] += dp[i - 1][d], dp[i][j] %= MOD, memo[j]++;
            if(d == 0)           dp[i][j] += mPow2[i - 1], memo[j]++;
            dp[i][j] += dp[i - 1][j] * 2;
            dp[i][j] %= MOD;
        }
    }
    
    // 4. 出力.
    printf("%lld\n", dp[N][S]);
    return 0;
    
}

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

const LL MOD = 998244353;

LL dp[3030][3030], a[3030], memo[3030], mPow2[3030];

int main(){

// 1. 入力情報.

int N, S;

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

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

// 2. 2 のべき乗を保存.

mPow2[0] = 1;

repx(i, 1, 3030) mPow2[i] = mPow2[i - 1] * 2, mPow2[i] %= MOD;

// 3. dp更新.

repx(i, 1, N + 1){

repr(j, S, 0){

int d = j - (int)a[i - 1];

if(d > 0 && memo[d]) dp[i][j] += dp[i - 1][d], dp[i][j] %= MOD, memo[j]++;

if(d == 0) dp[i][j] += mPow2[i - 1], memo[j]++;

dp[i][j] += dp[i - 1][j] * 2;

dp[i][j] %= MOD;

}

// 4. 出力.

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

return 0;

}

[入力例]
3 4
2 2 4

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

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

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

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

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

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

[出力例]
24

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

[出力例]
96

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

[出力例]
806912

[入力例]
100 1234
37 97 66 35 28 118 7 100 81 73 60 114 99 70 12 64 104 26 86 34 66 35 46 73 96 61 76 2 53 47 18 91 25 91 104 41 92 29 32 109 68 41 21 85 65 115 99 105 36 56 75 75 32 34 58 79 14 63 10 9 55 123 61 51 46 94 55 92 51 96 86 112 96 97 90 56 70 59 120 56 102 99 24 56 28 42 101 101 61 31 26 41 39 8 70 74 12 75 97 44

[出力例]
329849245

[入力例]

3 4

2 2 4

[出力例]

※AtCoderテストケースより

[入力例]

5 8

9 9 9 9 9

[出力例]

※AtCoderテストケースより

[入力例]

10 10

3 1 4 1 5 9 2 6 5 3

[出力例]

3296

※AtCoderテストケースより

[入力例]

5 7

1 2 3 3 4

[出力例]

[入力例]

7 12

1 2 5 3 10 7 8

[出力例]

[入力例]

15 17

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

[出力例]

806912

[入力例]

100 1234

37 97 66 35 28 118 7 100 81 73 60 114 99 70 12 64 104 26 86 34 66 35 46 73 96 61 76 2 53 47 18 91 25 91 104 41 92 29 32 109 68 41 21 85 65 115 99 105 36 56 75 75 32 34 58 79 14 63 10 9 55 123 61 51 46 94 55 92 51 96 86 112 96 97 90 56 70 59 120 56 102 99 24 56 28 42 101 101 61 31 26 41 39 8 70 74 12 75 97 44

[出力例]

329849245

■参照サイト
AtCoder Beginner Contest 169

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

C++の練習を兼ねて, AtCoder Regular Contest 051 の 問題A (塗り絵) ～ 問題B (互除法) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 173 の 問題D (Chat in a Circle) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 172 の 問題F (Unfair Nim) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 172 の 問題D (Sum of Divisors) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 171 の 問題D (Replacing) ～ 問題E (Red Scarf) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 170 の 問題D (Not Divisible) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 169 の 問題F (F – Knapsack for All Subsets) を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 051 の問題A (塗り絵) ～問題B (互除法) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 173 の問題D (Chat in a Circle) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 172 の問題F (Unfair Nim) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 172 の問題D (Sum of Divisors) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 171 の問題D (Replacing) ～問題E (Red Scarf) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 170 の問題D (Not Divisible) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 169 の問題F (F – Knapsack for All Subsets) を解いてみた.