C++ | 個人用メモ帳

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) を解いてみた.

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

本家のサイト 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

2021年4月11日2021年4月11日

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

C++の練習を兼ねて, AtCoder Grand Contest 021 の問題A (Digit Sum 2) ～問題B (Holes) を解いてみた.

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

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

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

// 解き直し.
// https://img.atcoder.jp/agc021/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 main(){
    
    // 1. 入力情報.
    char c[111];
    scanf("%s", c);
    string N(c);
    int n = N.size();
    
    // 2. 各桁の和の最大値を計算.
    // 2-1. c999...999 の パターンであるか判定.
    bool ok = true;
    repr(i, n - 1, 1){
        if(N[i] != '9'){
            ok = false;
            break;
        }
    }
    
    // 2-2. 各桁の和を計算.
    int ans = 9 * (n - 1) + (N[0] - '0');
    if(!ok) ans--;
    
    // 3. 出力.
    printf("%d\n", ans);
    return 0;
    
}

// 解き直し.

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

// 1. 入力情報.

char c[111];

scanf("%s", c);

string N(c);

int n = N.size();

// 2. 各桁の和の最大値を計算.

// 2-1. c999...999 のパターンであるか判定.

bool ok = true;

repr(i, n - 1, 1){

if(N[i] != '9'){

ok = false;

break;

}

// 2-2. 各桁の和を計算.

int ans = 9 * (n - 1) + (N[0] - '0');

if(!ok) ans--;

// 3. 出力.

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

return 0;

}

[入力例]
100

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

[入力例]
9995

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

[入力例]
3141592653589793

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

[入力例]
2021

[出力例]
28

[入力例]
20210410

[出力例]
64

[入力例]
9999999999999999

[出力例]
144

[入力例]
11939623286980429648566048291655261423757411936705

[出力例]
441
※1e16よりも大きいケース(問題文の制約条件から外れるケース).

[入力例]

100

[出力例]

※AtCoderテストケースより

[入力例]

9995

[出力例]

※AtCoderテストケースより

[入力例]

3141592653589793

[出力例]

137

※AtCoderテストケースより

[入力例]

2021

[出力例]

[入力例]

20210410

[出力例]

[入力例]

9999999999999999

[出力例]

144

[入力例]

11939623286980429648566048291655261423757411936705

[出力例]

441

※1e16よりも大きいケース(問題文の制約条件から外れるケース).

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

// 解き直し.
// https://img.atcoder.jp/agc021/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 all(x) x.begin(), x.end()
#define pb push_back
const double PI = acos(-1);
LL x[111], y[111];
int memo[111];
double ans[111];

struct hole{
    LL x, y; // 座標.
    int i;   // 入力番号.
    bool operator < (const hole& rhs) const{
        return (x < rhs.x) || ((x == rhs.x) && (y < rhs.y));
    }
};

struct edge{
    double t; // 基準座標からの回転角.
    LL d;     // 座標間の距離(2乗).
    LL x, y;  // 座標.
    int i;    // 基準座標から見た凸包候補の入力番号.
    bool operator < (const edge& rhs) const{
        return (t < rhs.t) || ((t == rhs.t) && (d > rhs.d));
    }
};

struct point{
    LL x, y; // 座標.
};

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    vector<hole> v;
    rep(i, N){
        hole h;
        scanf("%lld %lld", &x[i], &y[i]);
        h.x = x[i];
        h.y = y[i];
        h.i = i;
        v.pb(h);
    }
    
    // 2. sort.
    sort(all(v));
    // for(auto &p : v) printf("%lld %lld %d\n", p.x, p.y, p.i);
    
    // 3. 凸包の作成.
    vector<hole> convex;
    hole o = v[0]; // 開始地点.
    int idx = o.i;
    convex.pb(o);
    point b; // 前回分ベクトル.
    b.x = o.x, b.y = o.y + 2e6 + 1;
    while(!memo[idx]){
        // 3-1. 訪問済みフラグ設定.
        memo[idx]++;
        
        // 3-2. 起点を取得.
        hole s = convex.back();
        
        // 3-3. 起点から線分を引いた場合の回転角, 距離 を 保存.
        vector<edge> candidate;
        rep(i, N){
            hole e = v[i];
            if(!memo[e.i]){
                edge p;
                
                // ベクトル v1, v2 の 内積から, 回転角を算出.
                double v1x = (double)(s.x - b.x), v1y = (double)(s.y - b.y);
                double v2x = (double)(e.x - s.x), v2y = (double)(e.y - s.y);
                double iProduct = v1x * v2x + v1y * v2y;
                double normBsSe = hypot(v1x, v1y) * hypot(v2x, v2y);
                double theta = acos(iProduct / normBsSe);
                p.t = theta;
                
                // 距離.
                p.d = (e.x - s.x) * (e.x - s.x) + (e.y - s.y) * (e.y - s.y);
                
                // 座標.
                p.x = e.x;
                p.y = e.y;
                
                // 入力番号.
                p.i = e.i;
                
                // 追加.
                candidate.pb(p);
            }
        }
        
        // 3-4. 凸包候補 が見つからなかった場合は, 終了.
        if(!candidate.size()) break;
        
        // 3-5. sort.
        sort(all(candidate));
        
        // 3-6. 凸包に保存してよいかチェック.
        bool ok = convex.size() > 2;
        if(ok){
            double theta1 = candidate[0].t;
            
            // ベクトル v1, v2 の 内積から, 回転角を算出.
            double v1x = (double)(s.x - b.x), v1y = (double)(s.y - b.y);
            double v2x = (double)(o.x - s.x), v2y = (double)(o.y - s.y);
            double iProduct = v1x * v2x + v1y * v2y;
            double normBsSo = hypot(v1x, v1y) * hypot(v2x, v2y);
            double theta2 = acos(iProduct / normBsSo);
            
            // 凸包内部に移動する場合は, 終了.
            if(theta2 < theta1) break;
        }
        
        // 3-7. 凸包に保存.
        hole h;
        h.i = candidate[0].i;
        h.x = x[h.i];
        h.y = y[h.i];
        convex.pb(h);
        
        // 3-8. 前回分ベクトル更新.
        b.x = s.x;
        b.y = s.y;
        
        // 3-9. index更新.
        idx = h.i;
        
        // 3-10. 訪問済みフラグ設定.
        if(ok){
            for(auto &p : candidate){
                if(p.i == idx) continue;
                if(!memo[p.i]){
                    // ベクトル va, vb が定数倍の差分であるかチェック.
                    // ※ 凸包の辺上にあるかのチェック.
                    LL vax = h.x - s.x, vay = h.y - s.y;
                    LL vbx = p.x - s.x, vby = p.y - s.y;
                    
                    // (vax = 0 and vbx = 0) or (vay = 0 and vby = 0) の 場合.
                    if((vax == 0 && vbx == 0) || (vay == 0 && vby == 0)) memo[p.i]++;
                    
                    // それ以外 の 場合.
                    if(vbx != 0 && vby != 0 && (vax % vbx == 0) && (vay % vby == 0)){
                        LL kx = vax / vbx, ky = vay / vby;
                        if(kx == ky) memo[p.i]++;
                    }
                }
            }
        }
    }
    
    // 4. 垂直二等分線(pq/qr) の 角度(差分) を 計算・保存.
    hole s = convex.front();
    hole e = convex.back();
    convex.pb(s);
    convex.insert(convex.begin(), e);
    repx(i, 1, convex.size() - 1){
        // 4-1. 穴 p, q, r.
        hole p = convex[i - 1];
        hole q = convex[i];
        hole r = convex[i + 1];
        
        // 4-2. ベクトル qr, qp の 内積から, 角度を算出.
        double qrx = (double)(r.x - q.x), qry = (double)(r.y - q.y);
        double qpx = (double)(p.x - q.x), qpy = (double)(p.y - q.y);
        double iProduct = qrx * qpx + qry * qpy;
        double normQrQp = hypot(qrx, qry) * hypot(qpx, qpy);
        double theta = acos(iProduct / normQrQp);
        
        // 4-3. 垂直二等分線 の 角度(差分).
        ans[q.i] = PI - theta;
        
        // 4-4. 360度で割る.
        ans[q.i] /= (2.0 * PI);
    }
    
    // 5. 出力.
    rep(i, N) printf("%.12lf\n", ans[i]);
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

// 解き直し.

// https://img.atcoder.jp/agc021/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 all(x) x.begin(), x.end()

#define pb push_back

const double PI = acos(-1);

LL x[111], y[111];

int memo[111];

double ans[111];

struct hole{

LL x, y; // 座標.

int i; // 入力番号.

bool operator < (const hole& rhs) const{

return (x < rhs.x) || ((x == rhs.x) && (y < rhs.y));

}

};

struct edge{

double t; // 基準座標からの回転角.

LL d; // 座標間の距離(2乗).

LL x, y; // 座標.

int i; // 基準座標から見た凸包候補の入力番号.

bool operator < (const edge& rhs) const{

return (t < rhs.t) || ((t == rhs.t) && (d > rhs.d));

}

};

struct point{

LL x, y; // 座標.

};

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

vector<hole> v;

rep(i, N){

hole h;

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

h.x = x[i];

h.y = y[i];

h.i = i;

v.pb(h);

}

// 2. sort.

sort(all(v));

// for(auto &p : v) printf("%lld %lld %d\n", p.x, p.y, p.i);

// 3. 凸包の作成.

vector<hole> convex;

hole o = v[0]; // 開始地点.

int idx = o.i;

convex.pb(o);

point b; // 前回分ベクトル.

b.x = o.x, b.y = o.y + 2e6 + 1;

while(!memo[idx]){

// 3-1. 訪問済みフラグ設定.

memo[idx]++;

// 3-2. 起点を取得.

hole s = convex.back();

// 3-3. 起点から線分を引いた場合の回転角, 距離を保存.

vector<edge> candidate;

rep(i, N){

hole e = v[i];

if(!memo[e.i]){

edge p;

// ベクトル v1, v2 の内積から, 回転角を算出.

double v1x = (double)(s.x - b.x), v1y = (double)(s.y - b.y);

double v2x = (double)(e.x - s.x), v2y = (double)(e.y - s.y);

double iProduct = v1x * v2x + v1y * v2y;

double normBsSe = hypot(v1x, v1y) * hypot(v2x, v2y);

double theta = acos(iProduct / normBsSe);

p.t = theta;

// 距離.

p.d = (e.x - s.x) * (e.x - s.x) + (e.y - s.y) * (e.y - s.y);

// 座標.

p.x = e.x;

p.y = e.y;

// 入力番号.

p.i = e.i;

// 追加.

candidate.pb(p);

}

// 3-4. 凸包候補が見つからなかった場合は, 終了.

if(!candidate.size()) break;

// 3-5. sort.

sort(all(candidate));

// 3-6. 凸包に保存してよいかチェック.

bool ok = convex.size() > 2;

if(ok){

double theta1 = candidate[0].t;

// ベクトル v1, v2 の内積から, 回転角を算出.

double v1x = (double)(s.x - b.x), v1y = (double)(s.y - b.y);

double v2x = (double)(o.x - s.x), v2y = (double)(o.y - s.y);

double iProduct = v1x * v2x + v1y * v2y;

double normBsSo = hypot(v1x, v1y) * hypot(v2x, v2y);

double theta2 = acos(iProduct / normBsSo);

// 凸包内部に移動する場合は, 終了.

if(theta2 < theta1) break;

}

// 3-7. 凸包に保存.

hole h;

h.i = candidate[0].i;

h.x = x[h.i];

h.y = y[h.i];

convex.pb(h);

// 3-8. 前回分ベクトル更新.

b.x = s.x;

b.y = s.y;

// 3-9. index更新.

idx = h.i;

// 3-10. 訪問済みフラグ設定.

if(ok){

for(auto &p : candidate){

if(p.i == idx) continue;

if(!memo[p.i]){

// ベクトル va, vb が定数倍の差分であるかチェック.

// ※ 凸包の辺上にあるかのチェック.

LL vax = h.x - s.x, vay = h.y - s.y;

LL vbx = p.x - s.x, vby = p.y - s.y;

// (vax = 0 and vbx = 0) or (vay = 0 and vby = 0) の場合.

if((vax == 0 && vbx == 0) || (vay == 0 && vby == 0)) memo[p.i]++;

// それ以外の場合.

if(vbx != 0 && vby != 0 && (vax % vbx == 0) && (vay % vby == 0)){

LL kx = vax / vbx, ky = vay / vby;

if(kx == ky) memo[p.i]++;

}

// 4. 垂直二等分線(pq/qr) の角度(差分) を計算・保存.

hole s = convex.front();

hole e = convex.back();

convex.pb(s);

convex.insert(convex.begin(), e);

repx(i, 1, convex.size() - 1){

// 4-1. 穴 p, q, r.

hole p = convex[i - 1];

hole q = convex[i];

hole r = convex[i + 1];

// 4-2. ベクトル qr, qp の内積から, 角度を算出.

double qrx = (double)(r.x - q.x), qry = (double)(r.y - q.y);

double qpx = (double)(p.x - q.x), qpy = (double)(p.y - q.y);

double iProduct = qrx * qpx + qry * qpy;

double normQrQp = hypot(qrx, qry) * hypot(qpx, qpy);

double theta = acos(iProduct / normQrQp);

// 4-3. 垂直二等分線の角度(差分).

ans[q.i] = PI - theta;

// 4-4. 360度で割る.

ans[q.i] /= (2.0 * PI);

}

// 5. 出力.

rep(i, N) printf("%.12lf\n", ans[i]);

return 0;

}

[入力例]
2
0 0
1 1

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

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

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

[出力例]
0.43160120892732328768
0.03480224363653196956
0.13880483535586193855
0.00000000000000000000
0.39479171208028279727
※AtCoderテストケースより

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

[入力例]
10
-23 78
-101 121
6 -9
-95 -64
-103 67
93 -35
97 99
31 29
47 -52
111 -8

[出力例]
0.000000000000
0.261719709303
0.000000000000
0.253710502864
0.015599264789
0.100076037181
0.211681970670
0.000000000000
0.042922608696
0.114289906496

[入力例]
25
-517 7628
8075 -2012
154 -40
-8256 11959
-9146 -6877
7850 3547
-948 -11197
-941 8748
-9147 -7807
10584 9401
-6647 12172
-8579 2928
6496 -93
11613 5783
10229 6921
4040 6678
5758 9469
9099 6744
-1513 10487
-5487 -2871
-1409 -9841
3928 -10419
9571 4500
-7524 -9713
4449 2480

[出力例]
0.000000000000
0.005121649771
0.000000000000
0.221538334289
0.007343339491
0.000000000000
0.060506653058
0.000000000000
0.112435325509
0.180521831195
0.046324389216
0.000000000000
0.000000000000
0.111913140296
0.000000000000
0.000000000000
0.000000000000
0.000000000000
0.000000000000
0.000000000000
0.000000000000
0.151884160566
0.000000000000
0.102411176608
0.000000000000

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

[入力例]

0 0

1 1

[出力例]

0.5

※AtCoderテストケースより

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

0.499999996646

[入力例]

0 0

2 8

4 5

2 6

3 10

[出力例]

0.43160120892732328768

0.03480224363653196956

0.13880483535586193855

0.00000000000000000000

0.39479171208028279727

※AtCoderテストケースより

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

0.431601208927

0.034802243637

0.138804835356

0.000000000000

0.394791712080

[入力例]

-23 78

-101 121

6 -9

-95 -64

-103 67

93 -35

97 99

31 29

47 -52

111 -8

[出力例]

0.000000000000

0.261719709303

0.000000000000

0.253710502864

0.015599264789

0.100076037181

0.211681970670

0.000000000000

0.042922608696

0.114289906496

[入力例]

-517 7628

8075 -2012

154 -40

-8256 11959

-9146 -6877

7850 3547

-948 -11197

-941 8748

-9147 -7807

10584 9401

-6647 12172

-8579 2928

6496 -93

11613 5783

10229 6921

4040 6678

5758 9469

9099 6744

-1513 10487

-5487 -2871

-1409 -9841

3928 -10419

9571 4500

-7524 -9713

4449 2480

[出力例]

0.000000000000

0.005121649771

0.000000000000

0.221538334289

0.007343339491

0.000000000000

0.060506653058

0.000000000000

0.112435325509

0.180521831195

0.046324389216

0.000000000000

0.111913140296

0.000000000000

0.151884160566

0.000000000000

0.102411176608

0.000000000000

■参照サイト
AtCoder Grand Contest 021

2021年4月9日

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

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

■感想.
1. 問題Cは, 解答方針が見えなかったので, 解説を参考に実装して, ようやく, AC版に到達できた.
2. 個人的には, 操作で使う数を, 有向グラフを使って調べる部分が, 非常に面白い問題に感じた.
3. Warshall–Floyd法の復習が出来たので, 非常に良かったと思う.
4. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

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

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%d", &a[i]);
    rep(i, N) scanf("%d", &b[i]);
    
    // 2. 2 の 冪乗 を 保存.
    vl cPow2;
    int count = 0;
    cPow2.pb(1);
    while(count < MAX - 1){
        // 2-1. 最大値を2倍.
        LL p = 2 * cPow2.back();
        
        // 2-2. 保存.
        cPow2.pb(p);
        
        // 2-3. インクリメント.
        count++;
    }
    // for(auto &p : cPow2) printf("%lld\n", p);
    
    // 3. S を 初期化.
    set<int> S;
    rep(i, MAX - 1) S.insert(i + 1);
    
    // 4. S を 固定しながら探索.
    LL ans = 202020202020202020;
    repr(i, MAX, 1){
        // 4-1. i を S から 除去.
        if(S.count(i)) S.erase(i);
        
        // 4-2. グラフ構築.
        int g[MAX][MAX];
        rep(u, MAX) rep(v, MAX) g[u][v] = (u != v) ? 1010101010 : 0;
        rep(u, MAX){
            // 有向辺 u -> v を 追加.
            for(auto &t : S){
                int v = u % t;
                g[u][v] = min(g[u][v], t);
            }
        }
        
        // 4-3. Warshall–Floyd法.
        // https://atcoder.jp/contests/abc022/tasks/abc022_c
        rep(k, MAX) rep(i, MAX) rep(j, MAX) g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
        
        // 4-4. 各 a[k] から b[k] に到達できるか？
        // ※ 解説上は, b[k] -> a[k] で, 到達可能できるか, と記載されていたがロジック変更.
        bool ok = true;
        rep(k, N){
            // 到達可能か？
            int d = g[a[k]][b[k]];
            if(d == 1010101010){
                ok = false;
                break;
            }
        }
        
        // 4-5. 到達可能な場合, 最小コスト更新.
        if(ok){
            // コスト集計.
            LL tAns = 0;
            for(auto &p : S) tAns += cPow2[p];
            
            // 最小コスト更新.
            ans = min(ans, tAns);
        }
        
        // 4-6. 到達不可能な場合は, S から 除去した要素を, (恒久的に)追加.
        if(!ok) S.insert(i);
    }
    
    // 5. 出力.
    printf("%lld\n", (ans == 202020202020202020) ? -1 : ans);
    return 0;
    
}

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vl = vector<LL>;

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

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

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

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

#define pb push_back

const int MAX = 51;

int a[MAX], b[MAX];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

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

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

// 2. 2 の冪乗を保存.

vl cPow2;

int count = 0;

cPow2.pb(1);

while(count < MAX - 1){

// 2-1. 最大値を2倍.

LL p = 2 * cPow2.back();

// 2-2. 保存.

cPow2.pb(p);

// 2-3. インクリメント.

count++;

}

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

// 3. S を初期化.

set<int> S;

rep(i, MAX - 1) S.insert(i + 1);

// 4. S を固定しながら探索.

LL ans = 202020202020202020;

repr(i, MAX, 1){

// 4-1. i を S から除去.

if(S.count(i)) S.erase(i);

// 4-2. グラフ構築.

int g[MAX][MAX];

rep(u, MAX) rep(v, MAX) g[u][v] = (u != v) ? 1010101010 : 0;

rep(u, MAX){

// 有向辺 u -> v を追加.

for(auto &t : S){

int v = u % t;

g[u][v] = min(g[u][v], t);

}

// 4-3. Warshall–Floyd法.

// https://atcoder.jp/contests/abc022/tasks/abc022_c

rep(k, MAX) rep(i, MAX) rep(j, MAX) g[i][j] = min(g[i][j], g[i][k] + g[k][j]);

// 4-4. 各 a[k] から b[k] に到達できるか？

// ※ 解説上は, b[k] -> a[k] で, 到達可能できるか, と記載されていたがロジック変更.

bool ok = true;

rep(k, N){

// 到達可能か？

int d = g[a[k]][b[k]];

if(d == 1010101010){

ok = false;

break;

}

// 4-5. 到達可能な場合, 最小コスト更新.

if(ok){

// コスト集計.

LL tAns = 0;

for(auto &p : S) tAns += cPow2[p];

// 最小コスト更新.

ans = min(ans, tAns);

}

// 4-6. 到達不可能な場合は, S から除去した要素を, (恒久的に)追加.

if(!ok) S.insert(i);

}

// 5. 出力.

printf("%lld\n", (ans == 202020202020202020) ? -1 : ans);

return 0;

}

[入力例]
3
19 10 14
0 3 4

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

[入力例]
3
19 15 14
0 0 0

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

[入力例]
2
8 13
5 13

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

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

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

[入力例]
1
50
13

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

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

[出力例]
-1

[入力例]
23
19 20 1 34 23 6 47 21 29 38 47 30 9 16 15 10 50 3 26 10 0 9 33
7 3 1 2 7 0 1 1 2 2 2 0 4 1 15 10 16 3 2 10 0 1 1

[出力例]
135458

[入力例]
33
47 5 1 45 35 5 17 23 50 14 37 43 48 10 37 50 5 2 38 33 9 33 12 40 33 10 23 33 32 25 16 9 47
6 5 1 3 2 5 6 2 9 14 6 12 6 3 2 19 5 2 17 12 9 33 12 40 0 10 1 5 4 4 16 9 16

[出力例]
2149584000

[入力例]

19 10 14

0 3 4

[出力例]

160

※AtCoderテストケースより

[入力例]

19 15 14

0 0 0

[出力例]

※AtCoderテストケースより

[入力例]

8 13

5 13

[出力例]

-1

※AtCoderテストケースより

[入力例]

2 0 1 8

[出力例]

※AtCoderテストケースより

[入力例]

[出力例]

137438953472

※AtCoderテストケースより

[入力例]

7 1 0 9 11 5

6 2 8 10 3 4

[出力例]

-1

[入力例]

19 20 1 34 23 6 47 21 29 38 47 30 9 16 15 10 50 3 26 10 0 9 33

7 3 1 2 7 0 1 1 2 2 2 0 4 1 15 10 16 3 2 10 0 1 1

[出力例]

135458

[入力例]

47 5 1 45 35 5 17 23 50 14 37 43 48 10 37 50 5 2 38 33 9 33 12 40 33 10 23 33 32 25 16 9 47

6 5 1 3 2 5 6 2 9 14 6 12 6 3 2 19 5 2 17 12 9 33 12 40 0 10 1 5 4 4 16 9 16

[出力例]

2149584000

■参照サイト
AtCoder Grand Contest 022

2021年4月8日

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

C++の練習を兼ねて, AtCoder Grand Contest 022 の問題A (Diverse Word) ～問題B (GCD Sequence) を解いてみた.

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

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

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

// 解き直し.
// https://img.atcoder.jp/agc022/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
int memo[26];

int main(){
    
    // 1. 入力情報.
    char c[33];
    scanf("%s", c);
    string S(c);
    int N = S.size();
    string ans = "";
    
    // 2. 多彩な単語を構成.
    // 2-1. 26文字未満.
    if(N < 26){
        // 出現した文字情報を保存.
        ans = S;
        rep(i, N) memo[S[i] - 'a']++;
        
        // 出現していない文字を探索.
        rep(i, 26){
            if(!memo[i]){
                ans.pb((char)('a' + i));
                break;
            }
        }
    }
    
    // 2-2. 26文字.
    if(N == 26){
        // 接尾辞(index)を抽出.
        int idx = 0;
        repr(i, N - 2, 0){
            if(S[i] < S[i + 1]){
                idx = i + 1;
                break;
            }
        }
        
        // idx = 0 の 場合.
        if(!idx) ans = "-1";
        
        // idx != 0 の 場合.
        if(idx){
            char q = 'z';
            repx(i, idx, N) if(S[idx - 1] < S[i]) q = min(q, S[i]);
            ans = S.substr(0, idx);
            ans.pop_back();
            ans.pb(q);
        }
    }
    
    // 3. 出力.
    printf("%s\n", ans.c_str());
    return 0;
    
}

// 解き直し.

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

int memo[26];

int main(){

// 1. 入力情報.

char c[33];

scanf("%s", c);

string S(c);

int N = S.size();

string ans = "";

// 2. 多彩な単語を構成.

// 2-1. 26文字未満.

if(N < 26){

// 出現した文字情報を保存.

ans = S;

rep(i, N) memo[S[i] - 'a']++;

// 出現していない文字を探索.

rep(i, 26){

if(!memo[i]){

ans.pb((char)('a' + i));

break;

}

// 2-2. 26文字.

if(N == 26){

// 接尾辞(index)を抽出.

int idx = 0;

repr(i, N - 2, 0){

if(S[i] < S[i + 1]){

idx = i + 1;

break;

}

// idx = 0 の場合.

if(!idx) ans = "-1";

// idx != 0 の場合.

if(idx){

char q = 'z';

repx(i, idx, N) if(S[idx - 1] < S[i]) q = min(q, S[i]);

ans = S.substr(0, idx);

ans.pop_back();

ans.pb(q);

}

// 3. 出力.

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

return 0;

}

[入力例]
atcoder

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

[入力例]
abc

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

[入力例]
zyxwvutsrqponmlkjihgfedcba

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

[入力例]
abcdefghijklmnopqrstuvwzyx

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

[入力例]
btcjhnlfyiadxmrezovqkusgpw

[出力例]
btcjhnlfyiadxmrezovqkusgw

[入力例]
mwrpxhaeznjsdkcvfiyqutolgb

[出力例]
mwrpxhaeznjsdkcvfiyt

[入力例]
odzvwbhirtxqgmpyusnlkjfeca

[出力例]
odzvwbhirtxqgms

[入力例]

atcoder

[出力例]

atcoderb

※AtCoderテストケースより

[入力例]

abc

[出力例]

abcd

※AtCoderテストケースより

[入力例]

zyxwvutsrqponmlkjihgfedcba

[出力例]

-1

※AtCoderテストケースより

[入力例]

abcdefghijklmnopqrstuvwzyx

[出力例]

abcdefghijklmnopqrstuvx

※AtCoderテストケースより

[入力例]

btcjhnlfyiadxmrezovqkusgpw

[出力例]

btcjhnlfyiadxmrezovqkusgw

[入力例]

mwrpxhaeznjsdkcvfiyqutolgb

[出力例]

mwrpxhaeznjsdkcvfiyt

[入力例]

odzvwbhirtxqgmpyusnlkjfeca

[出力例]

odzvwbhirtxqgms

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

// 解き直し.
// https://img.atcoder.jp/agc022/editorial.pdf
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
const int EVEN[] = {2, 10, 3, 9, 4, 8, 6, 12};
const int ODD[] = {6, 2, 10, 3, 9, 4, 8, 12};

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    
    // 2. Sを構成.
    // 2-1. N = 3.
    vi ans;
    if(N == 3) ans.pb(2), ans.pb(5), ans.pb(63);
    
    // 2-2. それ以外.
    bool odd = (N & 1);
    if(N > 3){
        // 奇数.
        if(odd) rep(i, N) ans.pb(12 * (i / 8) + ODD[i % 8]);
        
        // 偶数.
        if(!odd) rep(i, N) ans.pb(12 * (i / 8) + EVEN[i % 8]);
    }
    
    // 3. 出力.
    rep(i, N){
        printf("%d", ans[i]);
        printf("%s", (i < N - 1) ? " " : "\n");
    }
    return 0;
    
}

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

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

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

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

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

#define pb push_back

const int EVEN[] = {2, 10, 3, 9, 4, 8, 6, 12};

const int ODD[] = {6, 2, 10, 3, 9, 4, 8, 12};

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

// 2. Sを構成.

// 2-1. N = 3.

vi ans;

if(N == 3) ans.pb(2), ans.pb(5), ans.pb(63);

// 2-2. それ以外.

bool odd = (N & 1);

if(N > 3){

// 奇数.

if(odd) rep(i, N) ans.pb(12 * (i / 8) + ODD[i % 8]);

// 偶数.

if(!odd) rep(i, N) ans.pb(12 * (i / 8) + EVEN[i % 8]);

}

// 3. 出力.

rep(i, N){

printf("%d", ans[i]);

printf("%s", (i < N - 1) ? " " : "\n");

}

return 0;

}

[入力例]
3

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

[入力例]
4

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

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

[入力例]
25

[出力例]
6 2 10 3 9 4 8 12 18 14 22 15 21 16 20 24 30 26 34 27 33 28 32 36 42

[入力例]
111

[出力例]
6 2 10 3 9 4 8 12 18 14 22 15 21 16 20 24 30 26 34 27 33 28 32 36 42 38 46 39 45 40 44 48 54 50 58 51 57 52 56 60 66 62 70 63 69 64 68 72 78 74 82 75 81 76 80 84 90 86 94 87 93 88 92 96 102 98 106 99 105 100 104 108 114 110 118 111 117 112 116 120 126 122 130 123 129 124 128 132 138 134 142 135 141 136 140 144 150 146 154 147 153 148 152 156 162 158 166 159 165 160 164

[入力例]

[出力例]

2 5 63

※AtCoderテストケースより

[入力例]

[出力例]

2 5 20 63

※AtCoderテストケースより

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

2 10 3 9

[入力例]

[出力例]

6 2 10 3 9 4 8 12 18 14 22 15 21 16 20 24 30 26 34 27 33 28 32 36 42

[入力例]

111

[出力例]

6 2 10 3 9 4 8 12 18 14 22 15 21 16 20 24 30 26 34 27 33 28 32 36 42 38 46 39 45 40 44 48 54 50 58 51 57 52 56 60 66 62 70 63 69 64 68 72 78 74 82 75 81 76 80 84 90 86 94 87 93 88 92 96 102 98 106 99 105 100 104 108 114 110 118 111 117 112 116 120 126 122 130 123 129 124 128 132 138 134 142 135 141 136 140 144 150 146 154 147 153 148 152 156 162 158 166 159 165 160 164

■参照サイト
AtCoder Grand Contest 022

2021年4月4日

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

C++の練習を兼ねて, キーエンスプログラミングコンテスト 2021 の問題C (Robot on Grid) を解いてみた.

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

本家のサイトキーエンスプログラミングコンテスト 2021 解説の各リンクをご覧下さい.

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

// 解き直し.
// https://atcoder.jp/contests/keyence2021/editorial/564
// 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;
const LL DIV3 = 332748118;
const int MAX = 5050;
char board[MAX][MAX];
LL dp[MAX][MAX];

// 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;
}

int main(){
    
    // 1. 入力情報.
    int H, W, K;
    scanf("%d %d %d", &H, &W, &K);
    rep(h, MAX) rep(w, MAX) board[h][w] = '.';
    rep(i, K){
        int h, w;
        char c[11];
        scanf("%d %d %s", &h, &w, c);
        h--, w--;
        board[h][w] = c[0];
    }
    
    // 2. dp更新.
    dp[0][0] = 1;
    rep(h, H){
        rep(w, W){
            // 2-1. 開始地点は, Skip.
            if(h ==0 && w == 0) continue;
            
            // 2-2. 行方向更新.
            if(h){
                // マス目(h - 1, w) の 値.
                char op = board[h - 1][w];
                LL cur = dp[h - 1][w];
                
                // マス目(h - 1, w) が, 空欄 の 場合.
                if(op == '.'){
                    cur *= 2LL;
                    cur %= MOD;
                    cur *= DIV3;
                    cur %= MOD;
                }
                
                // マス目(h - 1, w) が, 'X', 'D' の 場合(何もしない).
                // if(op == 'X' || op == 'D'){}
                
                // マス目(h - 1, w) が, 'R' の 場合.
                if(op == 'R') cur = 0;
                
                // マス目(h, w) を 更新.
                dp[h][w] += cur;
                dp[h][w] %= MOD;
            }
            
            // 2-3. 列方向更新.
            if(w){
                // マス目(h, w - 1) の 値.
                char op = board[h][w - 1];
                LL cur = dp[h][w - 1];
                
                // マス目(h, w - 1) が, 空欄 の 場合.
                if(op == '.'){
                    cur *= 2LL;
                    cur %= MOD;
                    cur *= DIV3;
                    cur %= MOD;
                }
                
                // マス目(h, w - 1) が, 'X', 'R' の 場合(何もしない).
                // if(op == 'X' || op == 'R'){}
                
                // マス目(h, w - 1) が, 'D' の 場合.
                if(op == 'D') cur = 0;
                
                // マス目(h, w) を 更新.
                dp[h][w] += cur;
                dp[h][w] %= MOD;
            }
        }
    }
    
    // 3. 3 の (H * W - K)乗.
    LL ans = dp[H - 1][W - 1];
    ans *= mPow(3LL, (LL)(H * W - K));
    ans %= MOD;
    
    // 4. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

// 解き直し.

// https://atcoder.jp/contests/keyence2021/editorial/564

// 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;

const LL DIV3 = 332748118;

const int MAX = 5050;

char board[MAX][MAX];

LL dp[MAX][MAX];

// 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;

}

int main(){

// 1. 入力情報.

int H, W, K;

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

rep(h, MAX) rep(w, MAX) board[h][w] = '.';

rep(i, K){

int h, w;

char c[11];

scanf("%d %d %s", &h, &w, c);

h--, w--;

board[h][w] = c[0];

}

// 2. dp更新.

dp[0][0] = 1;

rep(h, H){

rep(w, W){

// 2-1. 開始地点は, Skip.

if(h ==0 && w == 0) continue;

// 2-2. 行方向更新.

if(h){

// マス目(h - 1, w) の値.

char op = board[h - 1][w];

LL cur = dp[h - 1][w];

// マス目(h - 1, w) が, 空欄の場合.

if(op == '.'){

cur *= 2LL;

cur %= MOD;

cur *= DIV3;

cur %= MOD;

}

// マス目(h - 1, w) が, 'X', 'D' の場合(何もしない).

// if(op == 'X' || op == 'D'){}

// マス目(h - 1, w) が, 'R' の場合.

if(op == 'R') cur = 0;

// マス目(h, w) を更新.

dp[h][w] += cur;

dp[h][w] %= MOD;

}

// 2-3. 列方向更新.

if(w){

// マス目(h, w - 1) の値.

char op = board[h][w - 1];

LL cur = dp[h][w - 1];

// マス目(h, w - 1) が, 空欄の場合.

if(op == '.'){

cur *= 2LL;

cur %= MOD;

cur *= DIV3;

cur %= MOD;

}

// マス目(h, w - 1) が, 'X', 'R' の場合(何もしない).

// if(op == 'X' || op == 'R'){}

// マス目(h, w - 1) が, 'D' の場合.

if(op == 'D') cur = 0;

// マス目(h, w) を更新.

dp[h][w] += cur;

dp[h][w] %= MOD;

}

// 3. 3 の (H * W - K)乗.

LL ans = dp[H - 1][W - 1];

ans *= mPow(3LL, (LL)(H * W - K));

ans %= MOD;

// 4. 出力.

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

return 0;

}

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

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

[入力例]
3 3 5
2 3 D
1 3 D
2 1 D
1 2 X
3 1 R

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

[入力例]
5000 5000 10
585 1323 R
2633 3788 X
1222 4989 D
1456 4841 X
2115 3191 R
2120 4450 X
4325 2864 X
222 3205 D
2134 2388 X
2262 3565 R

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

[入力例]
3 4 5
1 1 D
1 3 R
2 3 X
3 1 R
3 2 D

[出力例]
1296

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

[出力例]
865608789

[入力例]

2 2 3

1 1 X

2 1 R

2 2 R

[出力例]

※AtCoderテストケースより

[入力例]

3 3 5

2 3 D

1 3 D

2 1 D

1 2 X

3 1 R

[出力例]

150

※AtCoderテストケースより

[入力例]

5000 5000 10

585 1323 R

2633 3788 X

1222 4989 D

1456 4841 X

2115 3191 R

2120 4450 X

4325 2864 X

222 3205 D

2134 2388 X

2262 3565 R

[出力例]

139923295

※AtCoderテストケースより

[入力例]

3 4 5

1 1 D

1 3 R

2 3 X

3 1 R

3 2 D

[出力例]

1296

[入力例]

5 7 8

1 1 R

1 6 D

2 3 D

2 4 R

3 5 X

3 7 D

4 3 R

5 2 D

[出力例]

865608789

■参照サイト
キーエンスプログラミングコンテスト 2021

2021年4月4日

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

C++の練習を兼ねて, AtCoder Grand Contest 024 の問題C (Sequence Growing Easy) を解いてみた.

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

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

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

// 解き直し.
// https://img.atcoder.jp/agc024/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--)
int a[202020], x[202020];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%d", &a[i]);
    
    // 2. 解説通り.
    // 2-1. 先頭要素が, 正整数の場合.
    if(a[0]){
        puts("-1");
        return 0;
    }
    
    // 2-2. 隣接する要素が, 条件を満たさない場合.
    rep(i, N - 1){
        if(a[i] + 1 < a[i + 1]){
            puts("-1");
            return 0;
        }
    }
    
    // 3. 最小回数を算出.
    LL ans = 0;
    repr(i, N - 1, 0){
        if(x[i + 1]) x[i] = x[i + 1] - 1;
        if(x[i] != a[i]){
            ans += (LL)a[i];
            x[i] = a[i];
        }
    }
    
    // 4. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

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

int a[202020], x[202020];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

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

// 2. 解説通り.

// 2-1. 先頭要素が, 正整数の場合.

if(a[0]){

puts("-1");

return 0;

}

// 2-2. 隣接する要素が, 条件を満たさない場合.

rep(i, N - 1){

if(a[i] + 1 < a[i + 1]){

puts("-1");

return 0;

}

// 3. 最小回数を算出.

LL ans = 0;

repr(i, N - 1, 0){

if(x[i + 1]) x[i] = x[i + 1] - 1;

if(x[i] != a[i]){

ans += (LL)a[i];

x[i] = a[i];

}

// 4. 出力.

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

return 0;

}

[入力例]
4
0
1
1
2

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

[入力例]
3
1
2
1

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

[入力例]
9
0
1
1
0
1
2
2
1
2

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

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

[出力例]
17

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

[出力例]

-1

※AtCoderテストケースより

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

[出力例]

■参照サイト
AtCoder Grand Contest 024

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 021 の 問題A (Digit Sum 2) ～ 問題B (Holes) を解いてみた.

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

C++の練習を兼ねて, AtCoder Grand Contest 022 の 問題A (Diverse Word) ～ 問題B (GCD Sequence) を解いてみた.

C++の練習を兼ねて, キーエンス プログラミング コンテスト 2021 の 問題C (Robot on Grid) を解いてみた.

C++の練習を兼ねて, AtCoder Grand Contest 024 の 問題C (Sequence Growing Easy) を解いてみた.

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 021 の問題A (Digit Sum 2) ～問題B (Holes) を解いてみた.

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

C++の練習を兼ねて, AtCoder Grand Contest 022 の問題A (Diverse Word) ～問題B (GCD Sequence) を解いてみた.

C++の練習を兼ねて, キーエンスプログラミングコンテスト 2021 の問題C (Robot on Grid) を解いてみた.

C++の練習を兼ねて, AtCoder Grand Contest 024 の問題C (Sequence Growing Easy) を解いてみた.