C++ | 個人用メモ帳

2022年5月25日

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

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

■感想.
1. 問題Eは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 幅優先探索の復習が出来たので, 非常に良かったと思う.
3. 苦手な動的計画法の訓練を積めたので, 非常に良かったと思う.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/abc190/editorial/630
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
const int INF = 1010101010;

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    vvi G(N);
    rep(i, M){
        int a, b;
        scanf("%d %d", &a, &b);
        --a, --b;
        G[a].pb(b);
        G[b].pb(a);
    }
    int K;
    scanf("%d", &K);
    int c[K];
    rep(i, K){
        scanf("%d", &c[i]);
        --c[i];
    }
    
    // 2. bfs.
    // https://ja.wikipedia.org/wiki/幅優先探索
    int p[K][101010];
    rep(i, K) rep(j, N) p[i][j] = INF;
    auto bfs = [&](vvi &G, int s, int i){
        // 空のキュー.
        queue<int> q;
        
        // 開始地点は, 距離ゼロ.
        p[i][s] = 0;
        
        // 探索地点 s をキュー q に追加.
        q.push(s);
        while(!q.empty()){
            // キューから取り出す.
            int u = q.front();
            q.pop();
            
            // 取り出した要素を処理.
            for(auto &e : G[u]) if(p[i][e] == INF && e != s) p[i][e] = p[i][u] + 1, q.push(e);
        }
    };
    rep(i, K) bfs(G, c[i], i);
    
    // 3. 魔法石どうしの距離 に 変換.
    int d[K][K];
    rep(i, K) rep(j, K) d[i][j] = p[i][c[j]];
    
    // 4. dp更新(※解説通り).
    // 4-1. 初期化.
    int ks = 1 << K;
    int dp[ks][K];
    rep(i, ks) rep(j, K) dp[i][j] = INF;
    rep(i, K) dp[1 << i][i] = 0;
    
    // 4-2. dp更新.
    rep(s, ks){
        rep(i, K){
            if(!(s & (1 << i))) continue;
            rep(j, K) dp[s][i] = min(dp[s][i], dp[s - (1 << i)][j] + d[i][j]);
        }
    }
    
    // 5. 最小値取得.
    int ans = INF;
    rep(i, K) ans = min(ans, dp[ks - 1][i] + 1);
    
    // 6. 出力.
    printf("%d\n", (ans >= INF) ? -1 : ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc190/editorial/630

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

using vvi = vector<vi>;

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

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

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

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

#define pb push_back

const int INF = 1010101010;

int main(){

// 1. 入力情報.

int N, M;

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

vvi G(N);

rep(i, M){

int a, b;

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

--a, --b;

G[a].pb(b);

G[b].pb(a);

}

int K;

scanf("%d", &K);

int c[K];

rep(i, K){

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

--c[i];

}

// 2. bfs.

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

int p[K][101010];

rep(i, K) rep(j, N) p[i][j] = INF;

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

// 空のキュー.

queue<int> q;

// 開始地点は, 距離ゼロ.

p[i][s] = 0;

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

q.push(s);

while(!q.empty()){

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

int u = q.front();

q.pop();

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

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

}

};

rep(i, K) bfs(G, c[i], i);

// 3. 魔法石どうしの距離に変換.

int d[K][K];

rep(i, K) rep(j, K) d[i][j] = p[i][c[j]];

// 4. dp更新(※解説通り).

// 4-1. 初期化.

int ks = 1 << K;

int dp[ks][K];

rep(i, ks) rep(j, K) dp[i][j] = INF;

rep(i, K) dp[1 << i][i] = 0;

// 4-2. dp更新.

rep(s, ks){

rep(i, K){

if(!(s & (1 << i))) continue;

rep(j, K) dp[s][i] = min(dp[s][i], dp[s - (1 << i)][j] + d[i][j]);

}

// 5. 最小値取得.

int ans = INF;

rep(i, K) ans = min(ans, dp[ks - 1][i] + 1);

// 6. 出力.

printf("%d\n", (ans >= INF) ? -1 : ans);

return 0;

}

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

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

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

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

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

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

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

[出力例]
9
※魔法石を[3, 4, 9, 7, 9, 16, 17, 18, 20] と並べると, 魔法石 3 4 7 17 18 20 を 含む 長さ 9 の列 が 出来る.

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

[出力例]
13
※魔法石を[1, 3, 12, 2, 4, 9, 5, 6, 7, 11, 10, 8, 15] と並べると, 魔法石 1 2 3 5 7 9 10 11 12 15 を 含む 長さ 13 の列 が 出来る.

100

101

102

103

104

[入力例]

4 3

1 4

2 4

3 4

1 2 3

[出力例]

※AtCoderテストケースより

[入力例]

4 3

1 4

2 4

1 2

1 2 3

[出力例]

-1

※AtCoderテストケースより

[入力例]

10 10

3 9

3 8

8 10

2 10

5 8

6 8

5 7

6 7

1 6

2 4

1 2 7 9

[出力例]

※AtCoderテストケースより

[入力例]

20 17

1 2

3 4

4 5

4 9

7 9

6 8

6 15

10 13

10 11

10 12

12 14

16 17

17 18

18 19

19 20

18 20

9 16

3 4 7 17 18 20

[出力例]

※魔法石を[3, 4, 9, 7, 9, 16, 17, 18, 20] と並べると, 魔法石 3 4 7 17 18 20 を含む長さ 9 の列が出来る.

[入力例]

25 27

1 3

3 17

17 18

3 12

2 12

2 3

2 4

4 9

9 13

13 19

5 13

5 9

5 14

14 20

5 6

6 16

16 24

16 25

6 7

7 11

10 11

10 23

8 10

8 15

8 21

21 22

8 11

1 2 3 5 7 9 10 11 12 15

[出力例]

※魔法石を[1, 3, 12, 2, 4, 9, 5, 6, 7, 11, 10, 8, 15] と並べると, 魔法石 1 2 3 5 7 9 10 11 12 15 を含む長さ 13 の列が出来る.

■参照サイト
AtCoder Beginner Contest 190

2022年5月21日

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

C++の練習を兼ねて, AtCoder Beginner Contest 122 の問題D (We Like AGC) を解いてみた.

■感想.
1. 問題Dは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 実装に苦労したものの, 苦手な動的計画法の訓練を積めたので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/abc122/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 = 1e9 + 7;
// (i - 3) 文字目, (i - 2) 文字目, (i - 1) 文字目, i 文字目 を 管理.
// 文字 A, C, G, T は, 0, 1, 2, 3 に 対応させる.
LL dp[101][4][4][4][4];
string sAgc[] = {"AGCA", "GACA", "ACGA", "AAGC", "CAGC", "GAGC", "TAGC", "AGAC", "CGAC", "GGAC", "TGAC", "ACGC", "AGGC", "ATGC", "AGCC", "AGTC", "AGCG", "CACG", "ACGG", "AACG", "CACG", "TACG", "AGCT", "GACT", "ACGT"};
int agc[303];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    
    // 2. 除外したい部分文字列.
    // -> 解説にあるように, 特定の文字列が含まれない場合をチェック.
    //    文字 A, C, G, T は, 0, 1, 2, 3 に 対応させる.
    map<char, int> m;
    m['A'] = 0;
    m['C'] = 1;
    m['G'] = 2;
    m['T'] = 3;
    for(auto &s : sAgc){
        int x = 0;
        x += m[s[0]] * 64;
        x += m[s[1]] * 16;
        x += m[s[2]] * 4;
        x += m[s[3]] * 1;
        ++agc[x];
    }
    
    // 3. dp初期化.
    rep(i, 4) dp[0][0][0][0][i] = 1;
    rep(i, 4) rep(j, 4) dp[1][0][0][j][i] += dp[0][0][0][0][j];
    rep(a, 4){
        rep(b, 4){
            rep(c, 4){
                // 特定の部分文字列を含むか？
                // AGC (021).
                if(c == 0 && b == 2 && a == 1) continue;
                
                // GAC (201).
                if(c == 2 && b == 0 && a == 1) continue;
                
                // ACG (012).
                if(c == 0 && b == 1 && a == 2) continue;
                
                // 特定の部分文字列を含まない場合.
                dp[2][0][c][b][a] += dp[1][0][0][c][b];
            }
        }
    }
    
    // 4. dp更新.
    repx(i, 3, N){
        // i 文字目.
        rep(a, 4){
            // (i - 1) 文字目.
            rep(b, 4){
                // (i - 2) 文字目.
                rep(c, 4){
                    // (i - 3) 文字目.
                    rep(d, 4){
                        // 除外したい部分文字列であるか？
                        int x = 0;
                        x += d * 64;
                        x += c * 16;
                        x += b * 4;
                        x += a * 1;
                        if(agc[x]) continue;
                        
                        // 前回分反映.
                        rep(e, 4){
                            dp[i][d][c][b][a] += dp[i - 1][e][d][c][b];
                            dp[i][d][c][b][a] %= MOD;
                        }
                    }
                }
            }
        }
    }
    
    // 5. 集計.
    LL ans = 0;
    rep(a, 4) rep(b, 4) rep(c, 4) rep(d, 4) ans = (ans + dp[N - 1][d][c][b][a]) % MOD;
    
    // 6. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

100

// 解き直し.

// https://img.atcoder.jp/abc122/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 = 1e9 + 7;

// (i - 3) 文字目, (i - 2) 文字目, (i - 1) 文字目, i 文字目を管理.

// 文字 A, C, G, T は, 0, 1, 2, 3 に対応させる.

LL dp[101][4][4][4][4];

string sAgc[] = {"AGCA", "GACA", "ACGA", "AAGC", "CAGC", "GAGC", "TAGC", "AGAC", "CGAC", "GGAC", "TGAC", "ACGC", "AGGC", "ATGC", "AGCC", "AGTC", "AGCG", "CACG", "ACGG", "AACG", "CACG", "TACG", "AGCT", "GACT", "ACGT"};

int agc[303];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

// 2. 除外したい部分文字列.

// -> 解説にあるように, 特定の文字列が含まれない場合をチェック.

// 文字 A, C, G, T は, 0, 1, 2, 3 に対応させる.

map<char, int> m;

m['A'] = 0;

m['C'] = 1;

m['G'] = 2;

m['T'] = 3;

for(auto &s : sAgc){

int x = 0;

x += m[s[0]] * 64;

x += m[s[1]] * 16;

x += m[s[2]] * 4;

x += m[s[3]] * 1;

++agc[x];

}

// 3. dp初期化.

rep(i, 4) dp[0][0][0][0][i] = 1;

rep(i, 4) rep(j, 4) dp[1][0][0][j][i] += dp[0][0][0][0][j];

rep(a, 4){

rep(b, 4){

rep(c, 4){

// 特定の部分文字列を含むか？

// AGC (021).

if(c == 0 && b == 2 && a == 1) continue;

// GAC (201).

if(c == 2 && b == 0 && a == 1) continue;

// ACG (012).

if(c == 0 && b == 1 && a == 2) continue;

// 特定の部分文字列を含まない場合.

dp[2][0][c][b][a] += dp[1][0][0][c][b];

}

// 4. dp更新.

repx(i, 3, N){

// i 文字目.

rep(a, 4){

// (i - 1) 文字目.

rep(b, 4){

// (i - 2) 文字目.

rep(c, 4){

// (i - 3) 文字目.

rep(d, 4){

// 除外したい部分文字列であるか？

int x = 0;

x += d * 64;

x += c * 16;

x += b * 4;

x += a * 1;

if(agc[x]) continue;

// 前回分反映.

rep(e, 4){

dp[i][d][c][b][a] += dp[i - 1][e][d][c][b];

dp[i][d][c][b][a] %= MOD;

}

// 5. 集計.

LL ans = 0;

rep(a, 4) rep(b, 4) rep(c, 4) rep(d, 4) ans = (ans + dp[N - 1][d][c][b][a]) % MOD;

// 6. 出力.

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

return 0;

}

[入力例]
3

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

[入力例]
4

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

[入力例]
100

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

[入力例]
5

[出力例]
865

[入力例]
6

[出力例]
3247

[入力例]
10

[出力例]
643550

[入力例]
12

[出力例]
9058467

[入力例]
77

[出力例]
781042769

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

[出力例]

230

※AtCoderテストケースより

[入力例]

100

[出力例]

388130742

※AtCoderテストケースより

[入力例]

[出力例]

865

[入力例]

[出力例]

3247

[入力例]

[出力例]

643550

[入力例]

[出力例]

9058467

[入力例]

[出力例]

781042769

■参照サイト
AtCoder Beginner Contest 122

2022年5月18日2022年5月18日

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

C++の練習を兼ねて, AtCoder Regular Contest 137 の問題C (Distinct Numbers) を解いてみた.

■感想.
1. 問題Cは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/arc137/editorial/3590
// 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. 入力情報.
    int N, a, s, t;
    scanf("%d", &N);
    rep(i, N){
        scanf("%d", &a);
        if(i == N - 2) s = a;
        if(i == N - 1) t = a;
    }
    
    // 2. 先手必勝.
    if(s + 2 <= t){
        puts("Alice");
        return 0;
    }
    
    // 3. それ以外.
    printf("%s\n", ((t - N + 1) & 1) ? "Alice" : "Bob");
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc137/editorial/3590

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

int N, a, s, t;

scanf("%d", &N);

rep(i, N){

scanf("%d", &a);

if(i == N - 2) s = a;

if(i == N - 1) t = a;

}

// 2. 先手必勝.

if(s + 2 <= t){

puts("Alice");

return 0;

}

// 3. それ以外.

printf("%s\n", ((t - N + 1) & 1) ? "Alice" : "Bob");

return 0;

}

[入力例]
2
2 4

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

[入力例]
3
0 1 2

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

[入力例]
5
1 2 5 7 8

[出力例]
Bob

[入力例]
10
1 2 5 7 8 10 11 12 15 16

[出力例]
Alice

[入力例]

2 4

[出力例]

Alice

※AtCoderのテストケースより

[入力例]

0 1 2

[出力例]

Bob

※AtCoderのテストケースより

[入力例]

1 2 5 7 8

[出力例]

Bob

[入力例]

1 2 5 7 8 10 11 12 15 16

[出力例]

Alice

■参照サイト
AtCoder Regular Contest 137

2022年5月17日

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

C++の練習を兼ねて, AtCoder Beginner Contest 251 の問題C (Poem Online Judge) ～問題E (Prefix Equality) を解いてみた.

■感想.
1. 問題D, Eは, 方針が見えなかったので, 解説を参考に実装したところ, AC版に到達できた.
2. 問題E で, 苦手な動的計画法の訓練を積めたので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

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

int main(){
    
    // 1. 入力情報.
    int N, score = -1, ans = 0;
    scanf("%d", &N);
    set<string> st;
    rep(i, N){
        char c[22];
        int t;
        scanf("%s %d", c, &t);
        string s(c);
        if(!st.count(s)){
            st.insert(s);
            if(t > score){
                score = max(score, t);
                ans = i + 1;
            }
        }
    }
    
    // 2. 出力.
    printf("%d\n", ans);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

int main(){

// 1. 入力情報.

int N, score = -1, ans = 0;

scanf("%d", &N);

set<string> st;

rep(i, N){

char c[22];

int t;

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

string s(c);

if(!st.count(s)){

st.insert(s);

if(t > score){

score = max(score, t);

ans = i + 1;

}

// 2. 出力.

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

return 0;

}

[入力例]
3
aaa 10
bbb 20
aaa 30

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

[入力例]
5
aaa 9
bbb 10
ccc 10
ddd 10
bbb 11

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

[入力例]
10
bb 3
ba 1
aa 4
bb 1
ba 5
aa 9
aa 2
ab 6
bb 5
ab 3

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

[入力例]
20
aykwsc 7
nfnmrr 19
nfnmrr 40
aykwsc 18
aykwsc 17
ytdnae 34
rdaeaa 55
nfnmrr 88
aykwsc 34
aykwsc 76
nfnmrr 55
xvafua 77
rdaeaa 100
nfnmrr 99
xvafua 11
nfnmrr 13
nfnmrr 17
xvafua 56
nfnmrr 78
xvafua 80

[出力例]
12

[入力例]

aaa 10

bbb 20

aaa 30

[出力例]

※AtCoderテストケースより

[入力例]

aaa 9

bbb 10

ccc 10

ddd 10

bbb 11

[出力例]

※AtCoderテストケースより

[入力例]

bb 3

ba 1

aa 4

bb 1

ba 5

aa 9

aa 2

ab 6

bb 5

ab 3

[出力例]

※AtCoderテストケースより

[入力例]

aykwsc 7

nfnmrr 19

nfnmrr 40

aykwsc 18

aykwsc 17

ytdnae 34

rdaeaa 55

nfnmrr 88

aykwsc 34

aykwsc 76

nfnmrr 55

xvafua 77

rdaeaa 100

nfnmrr 99

xvafua 11

nfnmrr 13

nfnmrr 17

xvafua 56

nfnmrr 78

xvafua 80

[出力例]

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

// 解き直し.
// https://atcoder.jp/contests/abc251/editorial/3958
// 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

int main(){
    
    // 1. 入力情報.
    int W;
    scanf("%d", &W);
    
    // 2. 297個のおもりを用意.
    vi ans;
    repx(i, 1, 100) ans.pb(i);
    repex(i, 100, 10000, 100) ans.pb(i);
    repex(i, 10000, 1000000, 10000) ans.pb(i);
    
    // 3. 出力.
    puts("297");
    rep(i, 297) printf("%d%s", ans[i], (i < 296) ? " " : "\n");
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc251/editorial/3958

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

int main(){

// 1. 入力情報.

int W;

scanf("%d", &W);

// 2. 297個のおもりを用意.

vi ans;

repx(i, 1, 100) ans.pb(i);

repex(i, 100, 10000, 100) ans.pb(i);

repex(i, 10000, 1000000, 10000) ans.pb(i);

// 3. 出力.

puts("297");

rep(i, 297) printf("%d%s", ans[i], (i < 296) ? " " : "\n");

return 0;

}

[入力例]
6

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

[入力例]
12

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

※但し, 上記のプログラムでは, 以下の内容が出力される.
297
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 200 300 400 500 600 700 800 900 1000 1100 1200 1300 1400 1500 1600 1700 1800 1900 2000 2100 2200 2300 2400 2500 2600 2700 2800 2900 3000 3100 3200 3300 3400 3500 3600 3700 3800 3900 4000 4100 4200 4300 4400 4500 4600 4700 4800 4900 5000 5100 5200 5300 5400 5500 5600 5700 5800 5900 6000 6100 6200 6300 6400 6500 6600 6700 6800 6900 7000 7100 7200 7300 7400 7500 7600 7700 7800 7900 8000 8100 8200 8300 8400 8500 8600 8700 8800 8900 9000 9100 9200 9300 9400 9500 9600 9700 9800 9900 10000 20000 30000 40000 50000 60000 70000 80000 90000 100000 110000 120000 130000 140000 150000 160000 170000 180000 190000 200000 210000 220000 230000 240000 250000 260000 270000 280000 290000 300000 310000 320000 330000 340000 350000 360000 370000 380000 390000 400000 410000 420000 430000 440000 450000 460000 470000 480000 490000 500000 510000 520000 530000 540000 550000 560000 570000 580000 590000 600000 610000 620000 630000 640000 650000 660000 670000 680000 690000 700000 710000 720000 730000 740000 750000 760000 770000 780000 790000 800000 810000 820000 830000 840000 850000 860000 870000 880000 890000 900000 910000 920000 930000 940000 950000 960000 970000 980000 990000

[入力例]

[出力例]

1 2 3

※AtCoderテストケースより

[入力例]

[出力例]

2 5 1 2 5 1

※AtCoderテストケースより

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

297

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 200 300 400 500 600 700 800 900 1000 1100 1200 1300 1400 1500 1600 1700 1800 1900 2000 2100 2200 2300 2400 2500 2600 2700 2800 2900 3000 3100 3200 3300 3400 3500 3600 3700 3800 3900 4000 4100 4200 4300 4400 4500 4600 4700 4800 4900 5000 5100 5200 5300 5400 5500 5600 5700 5800 5900 6000 6100 6200 6300 6400 6500 6600 6700 6800 6900 7000 7100 7200 7300 7400 7500 7600 7700 7800 7900 8000 8100 8200 8300 8400 8500 8600 8700 8800 8900 9000 9100 9200 9300 9400 9500 9600 9700 9800 9900 10000 20000 30000 40000 50000 60000 70000 80000 90000 100000 110000 120000 130000 140000 150000 160000 170000 180000 190000 200000 210000 220000 230000 240000 250000 260000 270000 280000 290000 300000 310000 320000 330000 340000 350000 360000 370000 380000 390000 400000 410000 420000 430000 440000 450000 460000 470000 480000 490000 500000 510000 520000 530000 540000 550000 560000 570000 580000 590000 600000 610000 620000 630000 640000 650000 660000 670000 680000 690000 700000 710000 720000 730000 740000 750000 760000 770000 780000 790000 800000 810000 820000 830000 840000 850000 860000 870000 880000 890000 900000 910000 920000 930000 940000 950000 960000 970000 980000 990000

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

// 解き直し.
// https://atcoder.jp/contests/abc251/editorial/3960
// 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[303030], dp1[303030][2], dp2[303030][2];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%lld", &a[i + 1]);
    
    // 2. dp更新.
    // 2-1. 行動 1 を 行わない.
    dp1[1][1] = 202020202020202020;
    repx(i, 2, N + 1){
        // 行動 i を 行わない.
        dp1[i][0] = dp1[i - 1][1];
        
        // 行動 i を 行う.
        dp1[i][1] = min(dp1[i - 1][0], dp1[i - 1][1]) + a[i];
    }
    
    // 2-2. 行動 1 を 行う.
    dp2[1][0] = 202020202020202020;
    dp2[1][1] = a[1];
    repx(i, 2, N + 1){
        // 行動 i を 行わない.
        dp2[i][0] = dp2[i - 1][1];
        
        // 行動 i を 行う.
        dp2[i][1] = min(dp2[i - 1][0], dp2[i - 1][1]) + a[i];
    }
    
    // 3. 出力.
    printf("%lld\n", min(dp1[N][1], min(dp2[N][0], dp2[N][1])));
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc251/editorial/3960

// 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[303030], dp1[303030][2], dp2[303030][2];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

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

// 2. dp更新.

// 2-1. 行動 1 を行わない.

dp1[1][1] = 202020202020202020;

repx(i, 2, N + 1){

// 行動 i を行わない.

dp1[i][0] = dp1[i - 1][1];

// 行動 i を行う.

dp1[i][1] = min(dp1[i - 1][0], dp1[i - 1][1]) + a[i];

}

// 2-2. 行動 1 を行う.

dp2[1][0] = 202020202020202020;

dp2[1][1] = a[1];

repx(i, 2, N + 1){

// 行動 i を行わない.

dp2[i][0] = dp2[i - 1][1];

// 行動 i を行う.

dp2[i][1] = min(dp2[i - 1][0], dp2[i - 1][1]) + a[i];

}

// 3. 出力.

printf("%lld\n", min(dp1[N][1], min(dp2[N][0], dp2[N][1])));

return 0;

}

[入力例]
5
2 5 3 2 5

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

[入力例]
20
29 27 79 27 30 4 93 89 44 88 70 75 96 3 78 39 97 12 53 62

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

[入力例]
30
30 49 56 91 84 119 106 110 74 27 111 108 120 64 47 84 110 61 75 25 119 115 86 60 32 27 120 56 65 23

[出力例]
1000

[入力例]
50
1111 5764 9932 7890 7777 1045 4763 4839 1132 3456 7777 8284 6694 214 2851 7890 7130 6349 1076 5135 3067 279 5955 6341 11126 414 9876 7777 5694 2244 6985 2998 7329 6318 6789 2659 3957 2395 3137 2250 5555 3439 4928 7662 3333 2222 4567 939 5336 6666

[出力例]
100000

[入力例]

2 5 3 2 5

[出力例]

※AtCoderテストケースより

[入力例]

29 27 79 27 30 4 93 89 44 88 70 75 96 3 78 39 97 12 53 62

[出力例]

426

※AtCoderテストケースより

[入力例]

30 49 56 91 84 119 106 110 74 27 111 108 120 64 47 84 110 61 75 25 119 115 86 60 32 27 120 56 65 23

[出力例]

1000

[入力例]

1111 5764 9932 7890 7777 1045 4763 4839 1132 3456 7777 8284 6694 214 2851 7890 7130 6349 1076 5135 3067 279 5955 6341 11126 414 9876 7777 5694 2244 6985 2998 7329 6318 6789 2659 3957 2395 3137 2250 5555 3439 4928 7662 3333 2222 4567 939 5336 6666

[出力例]

100000

■参照サイト
パナソニックグループプログラミングコンテスト2022（AtCoder Beginner Contest 251）

2022年5月15日

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

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

■感想.
1. 問題Eは, 方針が見えなかったので, 解説を参考に実装したところ, AC版に到達できた.
2. 集合の性質を上手く使うことで, 高速判定できる点が, 大変参考になったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/abc250/editorial/3906
// 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
int a[202020], b[202020], pa[202020], pb[202020], q[202020];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%d", &a[i]);
    rep(i, N) scanf("%d", &b[i]);
    
    // 2. 事前計算①.
    set<int> aSt, bSt;
    vi va, vb;
    rep(i, N){
        // 整数列 A.
        if(!aSt.count(a[i])) va.pb(a[i]);
        aSt.insert(a[i]);
        pa[i] = aSt.size();
        
        // 整数列 B.
        if(!bSt.count(b[i])) vb.pb(b[i]);
        bSt.insert(b[i]);
        pb[i] = bSt.size();
    }
    
    // 3. 事前計算②.
    set<int> st;
    int na = va.size(), nb = vb.size();
    rep(i, N){
        // 整数列 A.
        if(i < na){
            if(st.count(va[i])) st.erase(va[i]);
            else                st.insert(va[i]);
        }
        
        // 整数列 B.
        if(i < nb){
            if(st.count(vb[i])) st.erase(vb[i]);
            else                st.insert(vb[i]);
        }
        
        // サイズ.
        q[i + 1] = st.size();
    }
    
    // 4. クエリ回答.
    int Q;
    scanf("%d", &Q);
    rep(i, Q){
        // 4-1. クエリ入力情報.
        int x, y;
        scanf("%d %d", &x, &y);
        --x, --y;
        
        // 4-2. 出力.
        if(pa[x] != pb[y]) puts("No");
        else               printf("%s\n", (!q[pa[x]]) ? "Yes" : "No");
    }
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc250/editorial/3906

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

int a[202020], b[202020], pa[202020], pb[202020], q[202020];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

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

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

// 2. 事前計算①.

set<int> aSt, bSt;

vi va, vb;

rep(i, N){

// 整数列 A.

if(!aSt.count(a[i])) va.pb(a[i]);

aSt.insert(a[i]);

pa[i] = aSt.size();

// 整数列 B.

if(!bSt.count(b[i])) vb.pb(b[i]);

bSt.insert(b[i]);

pb[i] = bSt.size();

}

// 3. 事前計算②.

set<int> st;

int na = va.size(), nb = vb.size();

rep(i, N){

// 整数列 A.

if(i < na){

if(st.count(va[i])) st.erase(va[i]);

else st.insert(va[i]);

}

// 整数列 B.

if(i < nb){

if(st.count(vb[i])) st.erase(vb[i]);

else st.insert(vb[i]);

}

// サイズ.

q[i + 1] = st.size();

}

// 4. クエリ回答.

int Q;

scanf("%d", &Q);

rep(i, Q){

// 4-1. クエリ入力情報.

int x, y;

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

--x, --y;

// 4-2. 出力.

if(pa[x] != pb[y]) puts("No");

else printf("%s\n", (!q[pa[x]]) ? "Yes" : "No");

}

return 0;

}

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

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

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

[出力例]
No
Yes
Yes
No
Yes
No
Yes
No
Yes
Yes

[入力例]
100
5 11 6 10 12 11 7 3 5 13 6 18 13 10 2 5 4 19 11 20 13 12 4 11 1 16 16 20 19 20 13 13 10 12 8 9 11 6 5 7 2 9 4 19 9 4 15 2 17 14 18 8 18 1 19 1 13 18 2 14 11 14 6 10 19 4 10 14 5 4 8 14 11 11 14 9 12 18 20 18 1 18 9 6 19 10 19 14 5 6 8 9 12 3 15 10 11 9 11 16
10 5 12 5 11 7 6 3 7 2 18 11 13 3 4 19 7 18 19 4 5 20 8 12 12 19 1 18 6 16 3 5 20 9 10 14 17 4 13 18 20 13 19 16 19 3 5 13 18 1 14 15 10 13 10 13 18 13 5 18 10 16 18 2 13 6 11 1 1 1 16 18 5 10 11 11 1 6 5 17 3 2 1 12 18 9 9 7 18 13 4 2 9 12 18 18 8 15 20 1
10
7 7
3 90
20 22
59 12
18 16
50 55
35 32
50 60
25 97
88 99

[出力例]
Yes
No
Yes
No
Yes
Yes
Yes
Yes
No
Yes

[入力例]

1 2 3 4 5

1 2 2 4 3

1 1

2 2

2 3

3 3

4 4

4 5

5 5

[出力例]

Yes

※AtCoderテストケースより

[入力例]

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

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

2 5

5 5

6 5

3 4

11 7

6 10

9 7

7 8

9 9

10 11

[出力例]

Yes

[入力例]

100

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

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

7 7

3 90

20 22

59 12

18 16

50 55

35 32

50 60

25 97

88 99

[出力例]

Yes

■参照サイト
AtCoder Beginner Contest 250

2022年5月14日

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

C++の練習を兼ねて, AtCoder Beginner Contest 250 の問題C (Adjacent Swaps) ～問題D (250-like Number) を解いてみた.

■感想.
1. 問題C, Dは, 方針を絞り込めたので, AC版に到達できた.
2. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

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

int main(){
    
    // 1. 入力情報.
    int N, Q;
    scanf("%d %d", &N, &Q);
    rep(i, N){
        io[i + 1] = i + 1; // 位置から見たボールの番号.
        oi[i + 1] = i + 1; // ボールの番号から見た位置.
    }
    
    // 2. 操作.
    rep(i, Q){
        // ボール情報.
        int x;
        scanf("%d", &x);
        int pos1 = oi[x];
        int pos2 = (pos1 == N) ? pos1 - 1 : pos1 + 1;
        int y = io[pos2];
        
        // 操作.
        swap(io[pos1], io[pos2]);
        swap(oi[x], oi[y]);
    }
    
    // 4. 出力.
    repx(i, 1, N + 1) printf("%d%s", io[i], (i < N) ? " " : "\n");
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

int io[202020], oi[202020];

int main(){

// 1. 入力情報.

int N, Q;

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

rep(i, N){

io[i + 1] = i + 1; // 位置から見たボールの番号.

oi[i + 1] = i + 1; // ボールの番号から見た位置.

}

// 2. 操作.

rep(i, Q){

// ボール情報.

int x;

scanf("%d", &x);

int pos1 = oi[x];

int pos2 = (pos1 == N) ? pos1 - 1 : pos1 + 1;

int y = io[pos2];

// 操作.

swap(io[pos1], io[pos2]);

swap(oi[x], oi[y]);

}

// 4. 出力.

repx(i, 1, N + 1) printf("%d%s", io[i], (i < N) ? " " : "\n");

return 0;

}

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

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


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

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

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

[出力例]
1 2 3 4 5 7 6 8 10 9
※AtCoderテストケースより

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

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

[入力例]

5 5

[出力例]

1 2 3 5 4

※AtCoderテストケースより

[入力例]

7 7

[出力例]

1 2 3 4 5 7 6

※AtCoderテストケースより

[入力例]

10 6

[出力例]

1 2 3 4 5 7 6 8 10 9

※AtCoderテストケースより

[入力例]

20 30

[出力例]

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

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

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

int main(){
    
    // 1. 入力情報.
    LL N;
    scanf("%lld", &N);
    
    // 2. 素数を取得.
    repx(i, 2, 1010101) if(!a[i]) repex(j, i * 2, 1010101, i) a[j]++;
    vl ps, qs;
    repx(i, 2, 1010101) if(!a[i]) ps.pb(i);
    for(auto &p : ps) qs.pb(p * p * p);
    qs.erase(qs.begin());
    
    // 3. 集計.
    int ans = 0;
    for(auto &p : ps){
        LL t = N / p;
        if(!t) break;
        int at = upper_bound(all(qs), t) - qs.begin();
        ans += at;
        if(!qs.empty()) qs.erase(qs.begin());
    }
    
    // 4. 出力.
    printf("%d\n", ans);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vl = vector<LL>;

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

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

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

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

#define pb push_back

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

int a[1010101];

int main(){

// 1. 入力情報.

LL N;

scanf("%lld", &N);

// 2. 素数を取得.

repx(i, 2, 1010101) if(!a[i]) repex(j, i * 2, 1010101, i) a[j]++;

vl ps, qs;

repx(i, 2, 1010101) if(!a[i]) ps.pb(i);

for(auto &p : ps) qs.pb(p * p * p);

qs.erase(qs.begin());

// 3. 集計.

int ans = 0;

for(auto &p : ps){

LL t = N / p;

if(!t) break;

int at = upper_bound(all(qs), t) - qs.begin();

ans += at;

if(!qs.empty()) qs.erase(qs.begin());

}

// 4. 出力.

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

return 0;

}

[入力例]
250

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

[入力例]
1

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

[入力例]
123456789012345

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

[入力例]
1029

[出力例]
5

[入力例]
2022

[出力例]
6

[入力例]
20220514

[出力例]
316

[入力例]
3141592653

[出力例]
2549

[入力例]
1000000000000000000

[出力例]
11871859

[入力例]

250

[出力例]

※AtCoderテストケースより

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

123456789012345

[出力例]

226863

※AtCoderテストケースより

[入力例]

1029

[出力例]

[入力例]

2022

[出力例]

[入力例]

20220514

[出力例]

316

[入力例]

3141592653

[出力例]

2549

[入力例]

1000000000000000000

[出力例]

11871859

■参照サイト
AtCoder Beginner Contest 250

2022年5月12日

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

C++の練習を兼ねて, AtCoder Regular Contest 131 の問題C (Zero XOR) を解いてみた.

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

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

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

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

int main(){
    
    // 1. 入力情報.
    int N, v = 0;
    scanf("%d", &N);
    rep(i, N){
        scanf("%d", &a[i]);
        v ^= a[i];
    }
    
    // 2. 奇数.
    if(N & 1) puts("Win");
    
    // 3. 偶数.
    if(!(N & 1)){
        bool ok = false;
        rep(i, N) if(v == a[i]) ok = true;
        printf("%s\n", ok ? "Win" : "Lose");
    }
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc131/editorial/3049

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

int a[404040];

int main(){

// 1. 入力情報.

int N, v = 0;

scanf("%d", &N);

rep(i, N){

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

v ^= a[i];

}

// 2. 奇数.

if(N & 1) puts("Win");

// 3. 偶数.

if(!(N & 1)){

bool ok = false;

rep(i, N) if(v == a[i]) ok = true;

printf("%s\n", ok ? "Win" : "Lose");

}

return 0;

}

[入力例]
6
9 14 11 3 5 8

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

[入力例]
1
131

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

[入力例]
8
12 23 34 45 56 78 89 98

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

[入力例]
10
123 103 16 35 82 84 2 32 85 97

[出力例]
Lose

[入力例]
10
59 95 64 107 91 1 105 69 54 100

[出力例]
Win

[入力例]
25
37 94 66 42 29 40 6 26 1 30 24 92 10 7 35 70 79 52 111 42 73 111 34 15 8

[出力例]
Win

[入力例]

9 14 11 3 5 8

[出力例]

Lose

※AtCoderのテストケースより

[入力例]

131

[出力例]

Win

※AtCoderのテストケースより

[入力例]

12 23 34 45 56 78 89 98

[出力例]

Win

※AtCoderのテストケースより

[入力例]

123 103 16 35 82 84 2 32 85 97

[出力例]

Lose

[入力例]

59 95 64 107 91 1 105 69 54 100

[出力例]

Win

[入力例]

37 94 66 42 29 40 6 26 1 30 24 92 10 7 35 70 79 52 111 42 73 111 34 15 8

[出力例]

Win

■参照サイト
AtCoder Regular Contest 131

2022年5月6日

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

C++の練習を兼ねて, AtCoder Beginner Contest 244 の問題C (Yamanote Line Game) ～問題D (Swap Hats) を解いてみた.

■感想.
1. 問題C, Dは, 方針を絞り込めたので, AC版に到達出来たと思う.
2. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

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

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    
    // 2. 初期化.
    set<int> st;
    rep(i, 2 * N + 1) st.insert(i + 1);
    
    // 3. ゲーム.
    while(!st.empty()){
        // 高橋君の宣言できる整数.
        int t = *st.begin();
        printf("%d\n", t);
        
        // 整数を削除.
        st.erase(t);
        fflush(stdout);
        
        // 青木君の宣言できる整数.
        int a;
        scanf("%d", &a);
        
        // ゲームが終了した場合.
        if(!a) break;
        
        // 整数を削除.
        st.erase(a);
    }
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

// 2. 初期化.

set<int> st;

rep(i, 2 * N + 1) st.insert(i + 1);

// 3. ゲーム.

while(!st.empty()){

// 高橋君の宣言できる整数.

int t = *st.begin();

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

// 整数を削除.

st.erase(t);

fflush(stdout);

// 青木君の宣言できる整数.

int a;

scanf("%d", &a);

// ゲームが終了した場合.

if(!a) break;

// 整数を削除.

st.erase(a);

}

return 0;

}

※インタラクティブな問題のため, 入出力は, 未記載としている.

1	※インタラクティブな問題のため, 入出力は, 未記載としている.

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

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

int main(){
    
    // 1. 入力情報.
    char s1[11], s2[11], s3[11], t1[11], t2[11], t3[11];
    scanf("%s %s %s %s %s %s", s1, s2, s3, t1, t2, t3);
    
    // 2. 差分.
    int ans = 0;
    if(s1[0] != t1[0]) ++ans;
    if(s2[0] != t2[0]) ++ans;
    if(s3[0] != t3[0]) ++ans;
    
    // 3. 出力.
    printf("%s\n", (!ans || (ans == 3)) ? "Yes" : "No");
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

int main(){

// 1. 入力情報.

char s1[11], s2[11], s3[11], t1[11], t2[11], t3[11];

scanf("%s %s %s %s %s %s", s1, s2, s3, t1, t2, t3);

// 2. 差分.

int ans = 0;

if(s1[0] != t1[0]) ++ans;

if(s2[0] != t2[0]) ++ans;

if(s3[0] != t3[0]) ++ans;

// 3. 出力.

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

return 0;

}

[入力例]
R G B
R G B

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

[入力例]
R B G
R G B

[出力例]
No

[入力例]
B R G
R G B

[出力例]
Yes

[入力例]

R G B

[出力例]

Yes

※AtCoderテストケースより

[入力例]

R B G

R G B

[出力例]

[入力例]

B R G

R G B

[出力例]

Yes

■参照サイト
AtCoder Beginner Contest 244

2022年5月5日

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

C++の練習を兼ねて, AtCoder Grand Contest 017 の問題D (Game on Tree) を解いてみた.

■感想.
1. 問題Dは, 方針が見えなかったので, 解説を参考に実装して, AC版に到達出来た.
2. 深さ優先探索の訓練を積めたので, 非常に良かったと思う.
3. 個人的には, 解説上のロジックで, 計算可能であることが, 摩訶不思議な感じがして, 非常に面白いと感じた.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

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

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    vvi G(N);
    rep(i, N - 1){
        int u, v;
        scanf("%d %d", &u, &v);
        --u;
        --v;
        G[u].pb(v);
        G[v].pb(u);
    }
    
    // 2. dfs.
    // https://ja.wikipedia.org/wiki/深さ優先探索
    auto dfs = [&](auto&& self, vvi &G, int cur, int bef, int* g) -> int {
        // 終了条件.
        if(bef != -1 && G[cur].size() == 1) return (g[cur] = 0);
        if(g[cur] != -1)                    return g[cur];
        
        // 隣接頂点(Grundy数 の XOR計算).
        int ret = 0;
        for(auto &nex : G[cur]){
            if(nex != bef) ret ^= (self(self, G, nex, cur, g) + 1);
        }
        
        // 返却.
        return (g[cur] = ret);
    };
    int grundy[101010];
    rep(i, N) grundy[i] = -1;
    int ans = dfs(dfs, G, 0, -1, grundy);
    // rep(i, N) printf("%d ", grundy[i]);
    // puts("");
    
    // 3. 出力.
    printf("%s\n", ans ? "Alice" : "Bob");
    return 0;
    
}

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

using vvi = vector<vi>;

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

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

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

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

#define pb push_back

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

vvi G(N);

rep(i, N - 1){

int u, v;

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

--u;

--v;

G[u].pb(v);

G[v].pb(u);

}

// 2. dfs.

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

auto dfs = [&](auto&& self, vvi &G, int cur, int bef, int* g) -> int {

// 終了条件.

if(bef != -1 && G[cur].size() == 1) return (g[cur] = 0);

if(g[cur] != -1) return g[cur];

// 隣接頂点(Grundy数の XOR計算).

int ret = 0;

for(auto &nex : G[cur]){

if(nex != bef) ret ^= (self(self, G, nex, cur, g) + 1);

}

// 返却.

return (g[cur] = ret);

};

int grundy[101010];

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

int ans = dfs(dfs, G, 0, -1, grundy);

// rep(i, N) printf("%d ", grundy[i]);

// puts("");

// 3. 出力.

printf("%s\n", ans ? "Alice" : "Bob");

return 0;

}

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

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

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

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

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

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

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

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

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

[出力例]
Bob

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

[出力例]
Alice

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

[出力例]
Bob

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

[出力例]
Alice

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

[入力例]

1 2

2 3

2 4

4 5

[出力例]

Alice

※AtCoderテストケースより

[入力例]

1 2

2 3

1 4

4 5

[出力例]

Bob

※AtCoderテストケースより

[入力例]

1 2

2 4

5 1

6 3

3 2

[出力例]

Alice

※AtCoderテストケースより

[入力例]

1 2

3 7

4 6

2 3

2 4

1 5

[出力例]

Bob

※AtCoderテストケースより

[入力例]

1 2

1 3

2 4

3 5

4 6

5 7

[出力例]

Bob

[入力例]

1 2

1 3

1 8

2 4

3 5

4 6

5 7

[出力例]

Alice

[入力例]

1 2

1 3

1 4

8 2

9 2

10 2

8 11

5 3

6 3

4 7

7 12

7 13

[出力例]

Bob

[入力例]

1 2

1 6

1 7

1 12

1 14

13 12

3 2

3 4

3 5

4 17

18 5

19 18

10 6

11 6

11 20

7 8

9 8

14 15

16 15

[出力例]

Alice

■参照サイト
AtCoder Grand Contest 017

2022年5月5日

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

C++の練習を兼ねて, AtCoder Regular Contest 128 の問題A (Gold and Silver) ～問題B (Balls of Three Colors) を解いてみた.

■感想.
1. 問題A, Bは, 方針が見えなかったので, 解説を参考に実装して, AC版に到達出来た.
2. 特に, 問題A は実装方針が見えなかったため, 解説プログラムを参考に実装している,
とりあえず, 交換するという操作を, XOR演算が発生する, という読み替えが必要と理解している.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// ※※※ 解答不能 ※※※.
// https://atcoder.jp/contests/arc128/editorial/2787
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
int a[202020], ans[202020];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%d", &a[i]);
    
    // 2. 操作を記録.
    rep(i, N - 1){
        if(a[i] > a[i + 1]){
            ans[i] ^= 1;
            ans[i + 1] ^= 1;
        }
    }
    
    // 3. 出力.
    rep(i, N) printf("%d%s", ans[i], (i < N - 1) ? " " : "\n");
    return 0;
    
}

// ※※※ 解答不能 ※※※.

// https://atcoder.jp/contests/arc128/editorial/2787

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

int a[202020], ans[202020];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

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

// 2. 操作を記録.

rep(i, N - 1){

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

ans[i] ^= 1;

ans[i + 1] ^= 1;

}

// 3. 出力.

rep(i, N) printf("%d%s", ans[i], (i < N - 1) ? " " : "\n");

return 0;

}

[入力例]
3
3 5 2

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

[入力例]
4
1 1 1 1

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

[入力例]
10
426877385 186049196 624834740 836880476 19698398 709113743 436942115 436942115 436942115 503843678

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

[入力例]

3 5 2

[出力例]

0 1 1

※AtCoderのテストケースより

[入力例]

1 1 1 1

[出力例]

0 0 0 0

※AtCoderのテストケースより

[入力例]

426877385 186049196 624834740 836880476 19698398 709113743 436942115 436942115 436942115 503843678

[出力例]

1 1 0 1 1 1 1 0 0 0

※AtCoderのテストケースより

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

// 解き直し.
// https://atcoder.jp/contests/arc128/editorial/2786
// 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. 入力情報.
    int T;
    scanf("%d", &T);
    
    // 2. テストケース.
    rep(i, T){
        // 各色のボール情報.
        int r, g, b, ans = 2020202020;
        scanf("%d %d %d", &r, &g, &b);
        
        // すべてのボールを同じ色に出来るか？
        // 赤.
        if(abs(g - b) % 3 == 0) ans = min(ans, max(g, b));
        
        // 緑.
        if(abs(b - r) % 3 == 0) ans = min(ans, max(b, r));
        
        // 青.
        if(abs(r - g) % 3 == 0) ans = min(ans, max(r, g));
        
        // 出力.
        printf("%d\n", (ans == 2020202020) ? -1 : ans);
    }
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc128/editorial/2786

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

int T;

scanf("%d", &T);

// 2. テストケース.

rep(i, T){

// 各色のボール情報.

int r, g, b, ans = 2020202020;

scanf("%d %d %d", &r, &g, &b);

// すべてのボールを同じ色に出来るか？

// 赤.

if(abs(g - b) % 3 == 0) ans = min(ans, max(g, b));

// 緑.

if(abs(b - r) % 3 == 0) ans = min(ans, max(b, r));

// 青.

if(abs(r - g) % 3 == 0) ans = min(ans, max(r, g));

// 出力.

printf("%d\n", (ans == 2020202020) ? -1 : ans);

}

return 0;

}

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

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

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

[出力例]
4
-1
5
8
9

[入力例]
10
118 116 110
31 18 110
85 54 78
68 104 114
99 75 70
68 36 37
68 35 87
9 104 55
53 70 58
110 87 26

[出力例]
116
-1
78
104
99
-1
68
-1
70
110

[入力例]

1 2 2

1 2 3

1 2 4

[出力例]

-1

※AtCoderのテストケースより

[入力例]

3 1 4

1 5 9

2 6 5

3 5 8

9 7 9

[出力例]

-1

[入力例]

118 116 110

31 18 110

85 54 78

68 104 114

99 75 70

68 36 37

68 35 87

9 104 55

53 70 58

110 87 26

[出力例]

116

-1

104

-1

110

■参照サイト
大和証券プログラミングコンテスト2021（AtCoder Regular Contest 128）

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

C++の練習を兼ねて, AtCoder Beginner Contest 122 の 問題D (We Like AGC) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 137 の 問題C (Distinct Numbers) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 251 の 問題C (Poem Online Judge) ～ 問題E (Prefix Equality) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 250 の 問題C (Adjacent Swaps) ～ 問題D (250-like Number) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 131 の 問題C (Zero XOR) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 244 の 問題C (Yamanote Line Game) ～ 問題D (Swap Hats) を解いてみた.

C++の練習を兼ねて, AtCoder Grand Contest 017 の 問題D (Game on Tree) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 128 の 問題A (Gold and Silver) ～ 問題B (Balls of Three Colors) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 122 の問題D (We Like AGC) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 137 の問題C (Distinct Numbers) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 251 の問題C (Poem Online Judge) ～問題E (Prefix Equality) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 250 の問題C (Adjacent Swaps) ～問題D (250-like Number) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 131 の問題C (Zero XOR) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 244 の問題C (Yamanote Line Game) ～問題D (Swap Hats) を解いてみた.

C++の練習を兼ねて, AtCoder Grand Contest 017 の問題D (Game on Tree) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 128 の問題A (Gold and Silver) ～問題B (Balls of Three Colors) を解いてみた.