C++ | 個人用メモ帳

2021年5月5日2021年5月5日

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

C++の練習を兼ねて, AtCoder Grand Contest 036 の問題B (Do Not Duplicate) を解いてみた.

■感想.
1. 問題Bは, 解答方針が見えなかったので, 解説を参考に実装して, ようやく, AC版に到達できた.
2. 実装に苦労したものの, ダブリングを復習することが出来たので, 非常に良かったと思う..
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/agc036/editorial.pdf
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
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 pob pop_back
#define pub push_back
#define all(x) x.begin(), x.end()
int a[202020], y[202020], stock[202020];
LL g[59][202020];

int main(){
    
    // 1. 入力情報.
    int N;
    LL K;
    scanf("%d %lld", &N, &K);
    vvi v(202020);
    rep(i, N){
        scanf("%d", &a[i]);
        v[a[i]].pub(i);
    }
    
    // 2. y[a] を 計算.
    rep(i, N){
        int l = v[a[i]].size();
        if(l == 1) y[i] = i + N + 1;
        if(l != 1){
            int at = lower_bound(all(v[a[i]]), i) - v[a[i]].begin();
            if(at < l - 1) y[i] = v[a[i]][at + 1] + 1;
            else           y[i] = v[a[i]][0] + N + 1;
        }
    }
    
    // 3. Doubling.
    rep(i, N) g[0][i] = y[i];
    int u = 0;
    LL bef = 0, cur = 0, r = 0, maxG = 0;
    repx(i, 1, 59){
        rep(j, N){
            // 前回分取得.
            bef = g[i - 1][j];
            r = bef % N;
            
            // 今回分設定.
            cur = (bef - r) + g[i - 1][r];
            g[i][j] = cur;
            
            // 最大値更新.
            maxG = max(maxG, cur);
        }
        
        // 最大値が大きい場合は, 終了.
        // -> オーバーフロー防止のため.
        if(maxG > 1e18){
            u = i;
            break;
        }
    }
    
    // 4. Step 1 が 終了するタイミング の aStop は？
    LL aStop = 0, upper = N * K - 1;
    int idx = 0;
    while(upper - aStop > (LL)N){
        // 探索.
        LL t = 0;
        rep(i, u + 1){
            if(g[i][idx] - idx <= upper - aStop) t = g[i][idx];
            else                                 break;
        }
        
        // 更新.
        aStop += (t - idx);
        idx = t % N;
    }
    
    // 5. aStop, aStop + 1, ... , N * K - 1 について操作.
    int aStart = (int)(aStop % N);
    deque<int> ans;
    repx(i, aStart, N){
        if(stock[a[i]]){
            bool ok = true;
            while(ok){
                // 該当要素が見つかったら, フラグ更新.
                int t = ans.back();
                if(t == a[i]) ok = false;
                stock[t]--;
                ans.pob();
            }
        }else{
            stock[a[i]]++;
            ans.pub(a[i]);
        }
    }
    
    // 6. 出力.
    int l = ans.size();
    rep(i, l){
        printf("%d", ans[i]);
        printf("%s", (i < l - 1) ? " " : "\n");
    }
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

110

111

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

using vvi = vector<vi>;

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 pob pop_back

#define pub push_back

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

int a[202020], y[202020], stock[202020];

LL g[59][202020];

int main(){

// 1. 入力情報.

int N;

LL K;

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

vvi v(202020);

rep(i, N){

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

v[a[i]].pub(i);

}

// 2. y[a] を計算.

rep(i, N){

int l = v[a[i]].size();

if(l == 1) y[i] = i + N + 1;

if(l != 1){

int at = lower_bound(all(v[a[i]]), i) - v[a[i]].begin();

if(at < l - 1) y[i] = v[a[i]][at + 1] + 1;

else y[i] = v[a[i]][0] + N + 1;

}

// 3. Doubling.

rep(i, N) g[0][i] = y[i];

int u = 0;

LL bef = 0, cur = 0, r = 0, maxG = 0;

repx(i, 1, 59){

rep(j, N){

// 前回分取得.

bef = g[i - 1][j];

r = bef % N;

// 今回分設定.

cur = (bef - r) + g[i - 1][r];

g[i][j] = cur;

// 最大値更新.

maxG = max(maxG, cur);

}

// 最大値が大きい場合は, 終了.

// -> オーバーフロー防止のため.

if(maxG > 1e18){

u = i;

break;

}

// 4. Step 1 が終了するタイミングの aStop は？

LL aStop = 0, upper = N * K - 1;

int idx = 0;

while(upper - aStop > (LL)N){

// 探索.

LL t = 0;

rep(i, u + 1){

if(g[i][idx] - idx <= upper - aStop) t = g[i][idx];

else break;

}

// 更新.

aStop += (t - idx);

idx = t % N;

}

// 5. aStop, aStop + 1, ... , N * K - 1 について操作.

int aStart = (int)(aStop % N);

deque<int> ans;

repx(i, aStart, N){

if(stock[a[i]]){

bool ok = true;

while(ok){

// 該当要素が見つかったら, フラグ更新.

int t = ans.back();

if(t == a[i]) ok = false;

stock[t]--;

ans.pob();

}

}else{

stock[a[i]]++;

ans.pub(a[i]);

}

// 6. 出力.

int l = ans.size();

rep(i, l){

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

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

}

return 0;

}

[入力例]
3 2
1 2 3

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

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

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

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

[出力例]

※AtCoderのテストケースより

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

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

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

[出力例]
5

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

[出力例]
7

[入力例]
50 2021
13 18 53 45 22 3 13 45 18 4 54 22 20 55 39 19 14 29 8 9 47 15 39 46 9 31 24 31 27 25 16 42 31 44 24 31 45 53 2 45 53 53 47 25 10 2 3 18 11 21

[出力例]
53 47 25 10 2 3 18 11 21

[入力例]

3 2

1 2 3

[出力例]

2 3

※AtCoderのテストケースより

[入力例]

5 10

1 2 3 2 3

[出力例]

※AtCoderのテストケースより

[入力例]

6 1000000000000

1 1 2 2 3 3

[出力例]

※AtCoderのテストケースより

[入力例]

11 97

3 1 4 1 5 9 2 6 5 3 5

[出力例]

9 2 6

※AtCoderのテストケースより

[入力例]

7 11

7 1 2 7 3 4 5

[出力例]

[入力例]

15 7

15 2 1 7 1 2 1 5 3 8 2 12 10 13 5

[出力例]

[入力例]

50 2021

13 18 53 45 22 3 13 45 18 4 54 22 20 55 39 19 14 29 8 9 47 15 39 46 9 31 24 31 27 25 16 42 31 44 24 31 45 53 2 45 53 53 47 25 10 2 3 18 11 21

[出力例]

53 47 25 10 2 3 18 11 21

■参照サイト
AtCoder Grand Contest 036

2021年5月4日

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

C++の練習を兼ねて, ZONeエナジープログラミングコンテスト “HELLO SPACE” の問題C (MAD TEAM) ～問題D (宇宙人からのメッセージ) を解いてみた.

■感想.
1. 問題Cは, 解答方針が見えなかったので, 解説を参考に実装して, ようやく, AC版に到達できた.
2. 問題Cは, 実装に苦労したものの, 二分探索の復習が出来たので, 非常に良かったと思う.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/zone2021/editorial/1197
// 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[3030], b[3030], c[3030], d[3030], e[3030];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%d %d %d %d %d", &a[i], &b[i], &c[i], &d[i], &e[i]);
    
    // 2. 判定関数.
    auto f = [&](int x) -> bool{
        // 2-1. 能力値の取り得る値を圧縮.
        int m[32];
        rep(i, 32) m[i] = 0;
        rep(i, N){
            int fa = (a[i] >= x) ? 16 : 0;
            int fb = (b[i] >= x) ?  8 : 0;
            int fc = (c[i] >= x) ?  4 : 0;
            int fd = (d[i] >= x) ?  2 : 0;
            int fe = (e[i] >= x) ?  1 : 0;
            m[fa + fb + fc + fd + fe] = 1;
        }
        
        // 2-2. 能力値の組み合わせを確認して, 値 x を取り得るかチェック.
        bool ret = true;
        int ml = 0;
        rep(i, 1 << 15){
            int p1 = i >> 10;
            int p2 = (i >> 5) - (p1 << 5);
            int p3 = i - (p1 << 10) - (p2 << 5);
            
            int ok = 0;
            if(m[p1]) ok |= p1;
            if(m[p2]) ok |= p2;
            if(m[p3]) ok |= p3;
            
            if(ok == 31){
                ret = false;
                break;
            }
        }
        
        // 2-3. 結果を返却.
        return ret;
    };
    
    // 3. 二分探索してみる.
    int l = 0, h = 1e9 + 1, m;
    while(l + 1 < h){
        m = (l + h) >> 1;
        if(f(m)) h = m;
        else     l = m;
        // printf("h=%d l=%d m=%d\n", h, l, m);
    }
    
    // 4. 出力.
    printf("%d\n", l);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/zone2021/editorial/1197

// 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[3030], b[3030], c[3030], d[3030], e[3030];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

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

// 2. 判定関数.

auto f = [&](int x) -> bool{

// 2-1. 能力値の取り得る値を圧縮.

int m[32];

rep(i, 32) m[i] = 0;

rep(i, N){

int fa = (a[i] >= x) ? 16 : 0;

int fb = (b[i] >= x) ? 8 : 0;

int fc = (c[i] >= x) ? 4 : 0;

int fd = (d[i] >= x) ? 2 : 0;

int fe = (e[i] >= x) ? 1 : 0;

m[fa + fb + fc + fd + fe] = 1;

}

// 2-2. 能力値の組み合わせを確認して, 値 x を取り得るかチェック.

bool ret = true;

int ml = 0;

rep(i, 1 << 15){

int p1 = i >> 10;

int p2 = (i >> 5) - (p1 << 5);

int p3 = i - (p1 << 10) - (p2 << 5);

int ok = 0;

if(m[p1]) ok |= p1;

if(m[p2]) ok |= p2;

if(m[p3]) ok |= p3;

if(ok == 31){

ret = false;

break;

}

// 2-3. 結果を返却.

return ret;

};

// 3. 二分探索してみる.

int l = 0, h = 1e9 + 1, m;

while(l + 1 < h){

m = (l + h) >> 1;

if(f(m)) h = m;

else l = m;

// printf("h=%d l=%d m=%d\n", h, l, m);

}

// 4. 出力.

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

return 0;

}

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

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

[入力例]
5
6 13 6 19 11
4 4 12 11 18
20 7 19 2 5
15 5 12 20 7
8 7 6 18 5

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

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

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

[入力例]
15
79 22 32 32 45
24 71 100 54 103
108 33 5 28 104
62 8 51 20 36
77 25 2 101 12
28 14 54 65 41
89 12 90 119 98
92 40 112 67 20
18 5 31 85 10
16 70 31 62 111
55 67 1 84 86
84 37 9 64 96
118 1 31 92 106
83 114 43 58 35
76 107 59 96 39

[出力例]
96

※実際に, 2番目, 3番目, 15番目 の人を採用すると達成できる.
チーム全体のパワー:     max( 24, 108,  76) = 108
チーム全体のスピード:   max( 71,  33, 107) = 107
チーム全体のテクニック: max(100,   5,  59) = 100
チーム全体の知識:       max( 54,  28,  96) =  96
チーム全体の発想力:     max(103, 104,  39) = 104
-> チームの総合力は, min(108, 107, 100, 96, 104) = 96

[入力例]

3 9 6 4 6

6 9 3 1 1

8 8 9 3 7

[出力例]

※AtCoderテストケースより

[入力例]

6 13 6 19 11

4 4 12 11 18

20 7 19 2 5

15 5 12 20 7

8 7 6 18 5

[出力例]

※AtCoderテストケースより

[入力例]

6 7 5 18 2

3 8 1 6 3

7 2 8 7 7

6 3 3 4 7

12 8 9 15 9

9 8 6 1 10

12 9 7 8 2

10 3 17 4 10

3 1 3 19 3

3 14 7 13 1

[出力例]

※AtCoderテストケースより

[入力例]

79 22 32 32 45

24 71 100 54 103

108 33 5 28 104

62 8 51 20 36

77 25 2 101 12

28 14 54 65 41

89 12 90 119 98

92 40 112 67 20

18 5 31 85 10

16 70 31 62 111

55 67 1 84 86

84 37 9 64 96

118 1 31 92 106

83 114 43 58 35

76 107 59 96 39

[出力例]

※実際に, 2番目, 3番目, 15番目の人を採用すると達成できる.

チーム全体のパワー: max( 24, 108, 76) = 108

チーム全体のスピード: max( 71, 33, 107) = 107

チーム全体のテクニック: max(100, 5, 59) = 100

チーム全体の知識: max( 54, 28, 96) = 96

チーム全体の発想力: max(103, 104, 39) = 104

-> チームの総合力は, min(108, 107, 100, 96, 104) = 96

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

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

int main(){
    
    // 1. 入力情報.
    char S[505050];
    scanf("%s", S);
    int l = strlen(S);
    
    // 2. 文字列を操作.
    deque<char> dq;
    bool f = false;
    rep(i, l){
        if(S[i] == 'R'){
            f = !f;
            continue;
        }
        if(f) dq.puf(S[i]);
        else  dq.pub(S[i]);
    }
    
    // 3. 連続文字の削除.
    stack<char> st;
    if(f){
        rep(i, dq.size()){
            if(!st.empty()){
                if(st.top() == dq[i]){
                    st.pop();
                    continue;
                }
            }
            st.push(dq[i]);
        }
    }else{
        repr(i, dq.size() - 1, 0){
            if(!st.empty()){
                if(st.top() == dq[i]){
                    st.pop();
                    continue;
                }
            }
            st.push(dq[i]);
        }
    }
    
    // 4. 文字列を構成.
    string ans = "";
    while(!st.empty()){
        ans.pub(st.top());
        st.pop();
    }
    
    // 5. 出力.
    printf("%s\n", ans.c_str());
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

#define pub push_back

#define puf push_front

int main(){

// 1. 入力情報.

char S[505050];

scanf("%s", S);

int l = strlen(S);

// 2. 文字列を操作.

deque<char> dq;

bool f = false;

rep(i, l){

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

f = !f;

continue;

}

if(f) dq.puf(S[i]);

else dq.pub(S[i]);

}

// 3. 連続文字の削除.

stack<char> st;

if(f){

rep(i, dq.size()){

if(!st.empty()){

if(st.top() == dq[i]){

st.pop();

continue;

}

st.push(dq[i]);

}

}else{

repr(i, dq.size() - 1, 0){

if(!st.empty()){

if(st.top() == dq[i]){

st.pop();

continue;

}

st.push(dq[i]);

}

// 4. 文字列を構成.

string ans = "";

while(!st.empty()){

ans.pub(st.top());

st.pop();

}

// 5. 出力.

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

return 0;

}

[入力例]
ozRnonnoe

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

[入力例]
hellospaceRhellospace

[出力例]

※AtCoderテストケースより

[入力例]
abRacadabRa

[出力例]
badacba

[入力例]
fcccpkiRcckarpcvwwvcprkccddeeedkkqqqccffReewzzqqqooooRasssswwweotttoRqqffffqoooosvrnjjjjjaksrspzmmjjjmmmzpskaRkuRvdppppbpuuuudvvvRaammqqqohhiqReetfxxo

[出力例]
qioqukotoewaqdekakfcpkiwsvrnjaksrspzjmzpskavdbpdvtfo

[入力例]

ozRnonnoe

[出力例]

zone

※AtCoderテストケースより

[入力例]

hellospaceRhellospace

[出力例]

※AtCoderテストケースより

[入力例]

abRacadabRa

[出力例]

badacba

[入力例]

fcccpkiRcckarpcvwwvcprkccddeeedkkqqqccffReewzzqqqooooRasssswwweotttoRqqffffqoooosvrnjjjjjaksrspzmmjjjmmmzpskaRkuRvdppppbpuuuudvvvRaammqqqohhiqReetfxxo

[出力例]

qioqukotoewaqdekakfcpkiwsvrnjaksrspzjmzpskavdbpdvtfo

■参照サイト
ZONeエナジープログラミングコンテスト “HELLO SPACE”

2021年4月30日2021年4月30日

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

C++の練習を兼ねて, AtCoder Regular Contest 117 の問題A (God Sequence) ～問題C (Tricolor Pyramid) を解いてみた.

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

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

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

// 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 A, B;
    scanf("%d %d", &A, &B);
    
    // 2. 数列を計算.
    vi ans;
    if(A > B){
        rep(i, A)     ans.pb(i + 1);
        rep(i, B - 1) ans.pb(-i - 1);
        ans.pb(-(1 + A) * A / 2 + (B - 1) * B / 2);
    }
    if(A <= B){
        rep(i, B)     ans.pb(-i - 1);
        rep(i, A - 1) ans.pb(i + 1);
        ans.pb((1 + B) * B / 2 - (A - 1) * A / 2);
    }
    
    // 3. 出力.
    int l = ans.size();
    rep(i, l){
        printf("%d", ans[i]);
        printf("%s", (i < l - 1) ? " " : "\n");
    }
    return 0;
    
}

// 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 A, B;

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

// 2. 数列を計算.

vi ans;

if(A > B){

rep(i, A) ans.pb(i + 1);

rep(i, B - 1) ans.pb(-i - 1);

ans.pb(-(1 + A) * A / 2 + (B - 1) * B / 2);

}

if(A <= B){

rep(i, B) ans.pb(-i - 1);

rep(i, A - 1) ans.pb(i + 1);

ans.pb((1 + B) * B / 2 - (A - 1) * A / 2);

}

// 3. 出力.

int l = ans.size();

rep(i, l){

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

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

}

return 0;

}

[入力例]
1 1

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

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

[入力例]
1 4

[出力例]
-8 -6 -9 120 -97
※AtCoderのテストケースより

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

[入力例]
7 5

[出力例]
-8 -6 -9 120 -97
※AtCoderのテストケースより

※但し, 上記のプログラムでは, 以下の内容が出力される.
1 2 3 4 5 6 7 -1 -2 -3 -4 -18

[入力例]
12 10

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

[入力例]

1 1

[出力例]

1001 -1001

※AtCoderのテストケースより

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

-1 1

[入力例]

1 4

[出力例]

-8 -6 -9 120 -97

※AtCoderのテストケースより

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

-1 -2 -3 -4 10

[入力例]

7 5

[出力例]

-8 -6 -9 120 -97

※AtCoderのテストケースより

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

1 2 3 4 5 6 7 -1 -2 -3 -4 -18

[入力例]

12 10

[出力例]

1 2 3 4 5 6 7 8 9 10 11 12 -1 -2 -3 -4 -5 -6 -7 -8 -9 -33

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

// 解き直し.
// https://atcoder.jp/contests/arc117/editorial/1111
// 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;
LL a[101010];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%lld", &a[i]);
    
    // 2. sort.
    sort(a, a + N);
    
    // 3. ビルの景観の数は？
    LL ans = a[0] + 1;
    rep(i, N - 1){
        ans *= (a[i + 1] - a[i] + 1);
        ans %= MOD;
    }
    
    // 4. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc117/editorial/1111

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

LL a[101010];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

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

// 2. sort.

sort(a, a + N);

// 3. ビルの景観の数は？

LL ans = a[0] + 1;

rep(i, N - 1){

ans *= (a[i + 1] - a[i] + 1);

ans %= MOD;

}

// 4. 出力.

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

return 0;

}

[入力例]
2
1 2

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

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

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

[入力例]
7
314 159 265 358 979 323 846

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

[入力例]
12
5 103 20 90 40 24 11 70 121 54 21 32

[出力例]
672866091

[入力例]

1 2

[出力例]

※AtCoderのテストケースより

[入力例]

5 3 4 1 5 2

[出力例]

※AtCoderのテストケースより

[入力例]

314 159 265 358 979 323 846

[出力例]

492018656

※AtCoderのテストケースより

[入力例]

5 103 20 90 40 24 11 70 121 54 21 32

[出力例]

672866091

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

// 解き直し.
// https://atcoder.jp/contests/arc117/editorial/1113
// 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--)
const int LIMIT = 404040;
int a[LIMIT], b[LIMIT], f[LIMIT], g[LIMIT], combination[LIMIT];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    char c[404040];
    scanf("%s", c);
    
    // 2. f, g を 計算.
    b[0] = 1, g[0] = 1;
    repx(i, 1, N){
        int idx = 0, q = i;
        while(q % 3 == 0) q /= 3, idx++;
        a[i] = idx;
        b[i] = q;
    }
    rep(i, N - 1) f[i + 1] = f[i] + a[i + 1];
    rep(i, N - 1) g[i + 1] = g[i] * b[i + 1], g[i + 1] %= 3;
    rep(i, N){
        if(f[N - 1] - f[i] - f[N - 1 - i] == 0){
            if(g[N - 1] == 1){
                if(g[i] * g[N - 1 - i] == 1) combination[i] = 1;
                if(g[i] * g[N - 1 - i] == 2) combination[i] = 2;
                if(g[i] * g[N - 1 - i] == 4) combination[i] = 1;
            }
            if(g[N - 1] == 2){
                if(g[i] * g[N - 1 - i] == 1) combination[i] = 2;
                if(g[i] * g[N - 1 - i] == 2) combination[i] = 1;
                if(g[i] * g[N - 1 - i] == 4) combination[i] = 2;
            }
        }
    }
    
    // 3. 初期化.
    map<int, char> ans;
    ans[0] = 'R';
    ans[1] = 'W';
    ans[2] = 'B';
    
    // 4. 集計.
    int t = 0;
    rep(i, N){
        if(c[i] == 'R') t += 0 * combination[i];
        if(c[i] == 'W') t += 1 * combination[i];
        if(c[i] == 'B') t += 2 * combination[i];
        t %= 3;
    }
    if(!(N & 1)) t *= -1;
    t = (t + 3) % 3;
    
    // 5. 出力.
    printf("%c\n", ans[t]);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc117/editorial/1113

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

const int LIMIT = 404040;

int a[LIMIT], b[LIMIT], f[LIMIT], g[LIMIT], combination[LIMIT];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

char c[404040];

scanf("%s", c);

// 2. f, g を計算.

b[0] = 1, g[0] = 1;

repx(i, 1, N){

int idx = 0, q = i;

while(q % 3 == 0) q /= 3, idx++;

a[i] = idx;

b[i] = q;

}

rep(i, N - 1) f[i + 1] = f[i] + a[i + 1];

rep(i, N - 1) g[i + 1] = g[i] * b[i + 1], g[i + 1] %= 3;

rep(i, N){

if(f[N - 1] - f[i] - f[N - 1 - i] == 0){

if(g[N - 1] == 1){

if(g[i] * g[N - 1 - i] == 1) combination[i] = 1;

if(g[i] * g[N - 1 - i] == 2) combination[i] = 2;

if(g[i] * g[N - 1 - i] == 4) combination[i] = 1;

}

if(g[N - 1] == 2){

if(g[i] * g[N - 1 - i] == 1) combination[i] = 2;

if(g[i] * g[N - 1 - i] == 2) combination[i] = 1;

if(g[i] * g[N - 1 - i] == 4) combination[i] = 2;

}

// 3. 初期化.

map<int, char> ans;

ans[0] = 'R';

ans[1] = 'W';

ans[2] = 'B';

// 4. 集計.

int t = 0;

rep(i, N){

if(c[i] == 'R') t += 0 * combination[i];

if(c[i] == 'W') t += 1 * combination[i];

if(c[i] == 'B') t += 2 * combination[i];

t %= 3;

}

if(!(N & 1)) t *= -1;

t = (t + 3) % 3;

// 5. 出力.

printf("%c\n", ans[t]);

return 0;

}

[入力例]
3
BWR

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

[入力例]
4
RRBB

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

[入力例]
6
BWWRBW

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

[入力例]
8
WWBRBBWB

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

[入力例]
21
BWBRRBBRWBRBBBRRBWWWR

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

[入力例]
50
BBRBRGBBBGBRGRRBBGRRGRBRGBRRRGBGRRBBRGBGGGBRGGBRBR

[出力例]
R

[入力例]
100
RGRBGGGGRRGBBRBBRRRBRBRBGGRGGRRGRRRRRBGRRBGRRRRGGRRGBGRBGRRBBRGRGBRRBBRRRRRGBRGGGBRBRRBBGRGRGBGBBRGB

[出力例]
B

[入力例]

BWR

[出力例]

※AtCoderのテストケースより

[入力例]

RRBB

[出力例]

※AtCoderのテストケースより

[入力例]

BWWRBW

[出力例]

※AtCoderのテストケースより

[入力例]

WWBRBBWB

[出力例]

※AtCoderのテストケースより

[入力例]

BWBRRBBRWBRBBBRRBWWWR

[出力例]

※AtCoderのテストケースより

[入力例]

BBRBRGBBBGBRGRRBBGRRGRBRGBRRRGBGRRBBRGBGGGBRGGBRBR

[出力例]

[入力例]

100

RGRBGGGGRRGBBRBBRRRBRBRBGGRGGRRGRRRRRBGRRBGRRRRGGRRGBGRBGRRBBRGRGBRRBBRRRRRGBRGGGBRBRRBBGRGRGBGBBRGB

[出力例]

■参照サイト
AtCoder Regular Contest 117

2021年4月26日

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

C++の練習を兼ねて, AtCoder Grand Contest 035 の問題C (Skolem XOR Tree) を解いてみた.

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

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

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

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

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    
    // 2. 2の冪乗 を用意.
    vector<int> cPow2;
    set<int> stPow2;
    cPow2.pb(1);
    stPow2.insert(1);
    while(cPow2.back() < 1e5){
        // 最大値を2倍.
        int p = 2 * cPow2.back();
        
        // 保存.
        cPow2.pb(p);
        stPow2.insert(p);
    }
    
    // 3. N が 2の冪乗 である場合.
    if(stPow2.count(N)){
        puts("No");
        return 0;
    }
    
    // 4. 辺を保存(※解説通り).
    set<P> ans;
    ans.insert({1, 2});
    ans.insert({2, 3});
    ans.insert({3, N + 1});
    ans.insert({N + 1, N + 2});
    ans.insert({N + 2, N + 3});
    repx(i, 4, N + 1){
        if(i == N && !(N & 1)) break;
        if(i & 1){
            ans.insert({N + 1, i});
            ans.insert({i - 1, i});
        }else{
            ans.insert({N + 1, N + i});
            ans.insert({N + i, N + i + 1});
        }
    }
    
    // 5. N が 偶数の場合.
    if(!(N & 1)){
        int mPow2 = 1;
        for(auto &p : cPow2){
            if(p < N) mPow2 = p;
            else      break;
        }
        int t = N ^ mPow2 ^ 1;
        if(!(t & 1)) t += N;
        ans.insert({t, N});
        ans.insert({mPow2 + N, N * 2});
    }
    
    // 6. 出力.
    puts("Yes");
    for(auto &p: ans) printf("%d %d\n", p.a, p.b);
    return 0;
    
}

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using P = pair<int, int>;

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

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

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

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

#define pb push_back

#define a first

#define b second

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

// 2. 2の冪乗を用意.

vector<int> cPow2;

set<int> stPow2;

cPow2.pb(1);

stPow2.insert(1);

while(cPow2.back() < 1e5){

// 最大値を2倍.

int p = 2 * cPow2.back();

// 保存.

cPow2.pb(p);

stPow2.insert(p);

}

// 3. N が 2の冪乗である場合.

if(stPow2.count(N)){

puts("No");

return 0;

}

// 4. 辺を保存(※解説通り).

set ans;

ans.insert({1, 2});

ans.insert({2, 3});

ans.insert({3, N + 1});

ans.insert({N + 1, N + 2});

ans.insert({N + 2, N + 3});

repx(i, 4, N + 1){

if(i == N && !(N & 1)) break;

if(i & 1){

ans.insert({N + 1, i});

ans.insert({i - 1, i});

}else{

ans.insert({N + 1, N + i});

ans.insert({N + i, N + i + 1});

}

// 5. N が偶数の場合.

if(!(N & 1)){

int mPow2 = 1;

for(auto &p : cPow2){

if(p < N) mPow2 = p;

else break;

}

int t = N ^ mPow2 ^ 1;

if(!(t & 1)) t += N;

ans.insert({t, N});

ans.insert({mPow2 + N, N * 2});

}

// 6. 出力.

puts("Yes");

for(auto &p: ans) printf("%d %d\n", p.a, p.b);

return 0;

}

[入力例]
3

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

[入力例]
1

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

[入力例]
5

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

[入力例]
6

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

[入力例]
7

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

[入力例]
8

[出力例]
No

[入力例]
10

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

[入力例]
12

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

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

[入力例]

[出力例]

Yes

1 2

2 3

3 4

4 5

5 6

※AtCoderテストケースより

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

[出力例]

Yes

1 2

2 3

3 6

4 5

6 5

6 7

6 9

7 8

9 10

[入力例]

[出力例]

Yes

1 2

2 3

3 6

3 7

4 5

7 5

7 8

7 10

8 9

10 11

10 12

[入力例]

[出力例]

Yes

1 2

2 3

3 8

4 5

6 7

8 5

8 7

8 9

8 11

8 13

9 10

11 12

13 14

[入力例]

[出力例]

[入力例]

[出力例]

Yes

1 2

2 3

3 10

3 11

4 5

6 7

8 9

11 5

11 7

11 9

11 12

11 14

11 16

11 18

12 13

14 15

16 17

18 19

18 20

[入力例]

[出力例]

Yes

1 2

2 3

3 13

4 5

5 12

6 7

8 9

10 11

13 5

13 7

13 9

13 11

13 14

13 16

13 18

13 20

13 22

14 15

16 17

18 19

20 21

20 24

22 23

■参照サイト
AtCoder Grand Contest 035

2021年4月25日2021年4月25日

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

C++の練習を兼ねて, AtCoder Grand Contest 035 の問題A (XOR Circle) ～問題B (Even Degrees) を解いてみた.

■感想.
1. 問題A, Bは, 解答方針が見えなかったので, 解説を参考に実装して, ようやく, AC版に到達できた.
2. 問題B は, 実装に苦労したものの, グラフに対する理解を深めることが出来た気がするので, 非常に良かったと思う.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// C++(GCC 9.2.1)
// 解き直し.
// https://img.atcoder.jp/agc035/editorial.pdf
#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
#define a first
#define b second

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    map<int, int> m;
    rep(i, N){
        int a;
        scanf("%d", &a);
        m[a]++;
    }
    
    // 2. 判定.
    // 2-1. すべての帽子に書かれた数字が, 0.
    if(m.size() == 1 && m.count(0)){
        puts("Yes");
        return 0;
    }
    
    // 2-2. x が 書かれた帽子が, 2 * N / 3 枚, 0 が 書かれた帽子が, 1 * N / 3 枚.
    if(m.size() == 2 && N % 3 == 0){
        vector<int> v;
        for(auto &p : m) v.pb(p.a);
        if(v[0] == 0 && m[v[0]] == N / 3){
            puts("Yes");
            return 0;
        }
        if(v[1] == 0 && m[v[1]] == N / 3){
            puts("Yes");
            return 0;
        }
    }
    
    // 2-3. x ^ y ^ z = 0 の 書かれた帽子が, 1 * N / 3 枚ずつ.
    if(m.size() == 3 && N % 3 == 0){
        int xyz = 0;
        vector<int> v;
        for(auto &p : m) v.pb(p.a), xyz ^= p.a;
        if(xyz == 0 && m[v[0]] == N / 3 && m[v[1]] == N / 3 && m[v[2]] == N / 3){
            puts("Yes");
            return 0;
        }
    }
    
    // 2-4. それ以外.
    puts("No");
    return 0;
    
}

// C++(GCC 9.2.1)

// 解き直し.

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

#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

#define a first

#define b second

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

map<int, int> m;

rep(i, N){

int a;

scanf("%d", &a);

m[a]++;

}

// 2. 判定.

// 2-1. すべての帽子に書かれた数字が, 0.

if(m.size() == 1 && m.count(0)){

puts("Yes");

return 0;

}

// 2-2. x が書かれた帽子が, 2 * N / 3 枚, 0 が書かれた帽子が, 1 * N / 3 枚.

if(m.size() == 2 && N % 3 == 0){

vector<int> v;

for(auto &p : m) v.pb(p.a);

if(v[0] == 0 && m[v[0]] == N / 3){

puts("Yes");

return 0;

}

if(v[1] == 0 && m[v[1]] == N / 3){

puts("Yes");

return 0;

}

// 2-3. x ^ y ^ z = 0 の書かれた帽子が, 1 * N / 3 枚ずつ.

if(m.size() == 3 && N % 3 == 0){

int xyz = 0;

vector<int> v;

for(auto &p : m) v.pb(p.a), xyz ^= p.a;

if(xyz == 0 && m[v[0]] == N / 3 && m[v[1]] == N / 3 && m[v[2]] == N / 3){

puts("Yes");

return 0;

}

// 2-4. それ以外.

puts("No");

return 0;

}

[入力例]
3
1 2 3

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

[入力例]
4
1 2 4 8

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

[入力例]
2
0 0

[出力例]
Yes

[入力例]
6
2 2 0 0 2 2

[出力例]
Yes

[入力例]
9
2 5 7 2 5 7 2 5 7

[出力例]
Yes

[入力例]

1 2 3

[出力例]

Yes

※AtCoderのテストケースより

[入力例]

1 2 4 8

[出力例]

※AtCoderのテストケースより

[入力例]

0 0

[出力例]

Yes

[入力例]

2 2 0 0 2 2

[出力例]

Yes

[入力例]

2 5 7 2 5 7 2 5 7

[出力例]

Yes

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

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

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    set<P> gEdges;
    vvi G(N);
    rep(i, M){
        int a, b;
        scanf("%d %d", &a, &b);
        a--, b--;
        G[a].pb(b);
        G[b].pb(a);
        
        // 辺を保存.
        gEdges.insert({a, b});
        gEdges.insert({b, a});
    }
    
    // 2. 辺数が奇数の場合.
    if(gEdges.size() % 4 != 0){
        puts("-1");
        return 0;
    }
    
    // 3. 適当な根付き全域木.
    vvi sTree(N);
    set<P> stEdges;
    // https://ja.wikipedia.org/wiki/幅優先探索
    auto bfs = [&](vvi &G, int s, int* d){
        // 3-1. 空のキュー.
        queue<int> q;
        
        // 3-2. 探索地点 s をキュー q に追加.
        q.push(s);
        while(!q.empty()){
            // 3-3. キューから取り出す.
            int u = q.front();
            q.pop();
            
            // 3-4. 取り出した要素を処理.
            for(auto &v : G[u]){
                // 3-5. 訪問済であれば, 処理をスキップ.
                if(d[v])            continue;
                if(!d[v] && v != s){
                    d[v] = d[u] + 1;
                    q.push(v);
                    
                    // グラフに反映.
                    sTree[u].pb(v);
                    sTree[v].pb(u);
                    
                    // 辺を保存.
                    stEdges.insert({u, v});
                    stEdges.insert({v, u});
                    
                    // 親頂点を保存.
                    p[v] = u;
                }
            }
        }
        return;
    };
    int d[N];
    rep(i, N) d[i] = 0;
    bfs(G, 0, d);
    
    // 4. 根 から 遠い順 に並び替え.
    priority_queue<P> pq;
    rep(i, N) pq.push({d[i], i});
    
    // 5. 根付き全域木に含まれない辺について向きを付ける.
    set<P> ans;
    for(auto &e : gEdges){
        if(!stEdges.count(e)){
            if(!ans.count({e.a, e.b}) && !ans.count({e.b, e.a})){
                // 辺を保存.
                ans.insert(e);
                
                // 出次数を更新.
                oDegree[e.a]++;
            }
        }
    }
    
    // 6. ボトムアップで確定させていく.
    while(!pq.empty()){
        // 6-1. キューから取り出す.
        P cur = pq.top();
        pq.pop();
        
        // 6-2. 根に到達したら終了.
        int u = cur.b;
        if(u == 0) break;
        
        // 6-3. 子 -> 親.
        if(oDegree[u] & 1){
            // 辺を保存.
            ans.insert({u, p[u]});
            
            // 出次数を更新.
            oDegree[u]++;
            
            // 次へ.
            continue;
        }
        
        // 6-4. 親 -> 子.
        if(!(oDegree[u] & 1)){
            // 辺を保存.
            ans.insert({p[u], u});
            
            // 出次数を更新.
            oDegree[p[u]]++;
            
            // 次へ.
            continue;
        }
    }
    
    // 7. チェック.
    int odd = 0;
    rep(i, N) if(oDegree[i] & 1) odd++;
    assert(odd == 0);
    
    // 8. 出力.
    for(auto &p: ans) printf("%d %d\n", p.a + 1, p.b + 1);
    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

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

using vvi = vector<vi>;

using P = pair<int, int>;

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

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

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

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

#define pb push_back

#define a first

#define b second

int oDegree[101010], p[101010];

int main(){

// 1. 入力情報.

int N, M;

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

set gEdges;

vvi G(N);

rep(i, M){

int a, b;

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

a--, b--;

G[a].pb(b);

G[b].pb(a);

// 辺を保存.

gEdges.insert({a, b});

gEdges.insert({b, a});

}

// 2. 辺数が奇数の場合.

if(gEdges.size() % 4 != 0){

puts("-1");

return 0;

}

// 3. 適当な根付き全域木.

vvi sTree(N);

set stEdges;

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

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

// 3-1. 空のキュー.

queue<int> q;

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

q.push(s);

while(!q.empty()){

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

int u = q.front();

q.pop();

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

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

// 3-5. 訪問済であれば, 処理をスキップ.

if(d[v]) continue;

if(!d[v] && v != s){

d[v] = d[u] + 1;

q.push(v);

// グラフに反映.

sTree[u].pb(v);

sTree[v].pb(u);

// 辺を保存.

stEdges.insert({u, v});

stEdges.insert({v, u});

// 親頂点を保存.

p[v] = u;

}

return;

};

int d[N];

rep(i, N) d[i] = 0;

bfs(G, 0, d);

// 4. 根から遠い順に並び替え.

priority_queue pq;

rep(i, N) pq.push({d[i], i});

// 5. 根付き全域木に含まれない辺について向きを付ける.

set ans;

for(auto &e : gEdges){

if(!stEdges.count(e)){

if(!ans.count({e.a, e.b}) && !ans.count({e.b, e.a})){

// 辺を保存.

ans.insert(e);

// 出次数を更新.

oDegree[e.a]++;

}

// 6. ボトムアップで確定させていく.

while(!pq.empty()){

// 6-1. キューから取り出す.

P cur = pq.top();

pq.pop();

// 6-2. 根に到達したら終了.

int u = cur.b;

if(u == 0) break;

// 6-3. 子 -> 親.

if(oDegree[u] & 1){

// 辺を保存.

ans.insert({u, p[u]});

// 出次数を更新.

oDegree[u]++;

// 次へ.

continue;

}

// 6-4. 親 -> 子.

if(!(oDegree[u] & 1)){

// 辺を保存.

ans.insert({p[u], u});

// 出次数を更新.

oDegree[p[u]]++;

// 次へ.

continue;

}

// 7. チェック.

int odd = 0;

rep(i, N) if(oDegree[i] & 1) odd++;

assert(odd == 0);

// 8. 出力.

for(auto &p: ans) printf("%d %d\n", p.a + 1, p.b + 1);

return 0;

}

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

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

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

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

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

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

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

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

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

[入力例]

4 4

1 2

2 3

3 4

4 1

[出力例]

1 2

1 4

3 2

3 4

※AtCoderテストケースより

[入力例]

5 5

1 2

2 3

3 4

2 5

4 5

[出力例]

-1

※AtCoderテストケースより

[入力例]

17 20

1 2

1 6

1 9

6 7

6 5

7 5

5 4

3 5

4 13

4 14

13 14

15 4

10 9

8 9

10 11

10 12

11 12

17 12

11 16

11 17

[出力例]

1 2

1 9

4 14

4 15

5 3

5 4

5 6

5 7

6 1

6 7

9 8

9 10

11 10

11 12

11 16

11 17

12 10

12 17

13 4

13 14

[入力例]

21 26

1 2

1 7

1 9

2 4

2 3

3 5

3 6

3 14

5 6

6 20

6 21

7 8

8 14

8 15

8 16

8 9

9 11

11 16

11 10

11 12

11 13

12 13

10 17

10 18

10 19

17 18

[出力例]

1 2

1 9

2 3

2 4

3 6

3 14

5 3

5 6

6 20

6 21

7 1

7 8

8 9

8 14

8 15

8 16

10 18

10 19

11 9

11 10

11 13

11 16

12 11

12 13

17 10

17 18

■参照サイト
AtCoder Grand Contest 035

2021年4月24日

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

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

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

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

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

// 解き直し.
// https://img.atcoder.jp/agc027/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 LIMIT = 101010;
const int MAX = 500;
LL a[LIMIT], c1[MAX][MAX], c2[MAX][MAX], ans[MAX][MAX];
set<LL> c[MAX][MAX];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    
    // 2. 素数を用意.
    repx(i, 2, LIMIT){
        if(a[i]) continue;
        repex(j, i * 2, LIMIT, i) a[j]++;
    }
    vl p;
    repx(i, 2, LIMIT) if(!a[i] && p.size() < MAX * 2) p.pb((LL)i);
    
    // 3. 市松模様を敷き詰める.
    rep(i, MAX){
        // 3-1. 左上 -> 右下.
        int b = 2 * i;
        rep(j, b + 1){
            int r = j;
            int c = b - j;
            if(r >= 0 && r < MAX && c >= 0 && c < MAX) c1[r][c] = p[i];
        }
        
        // 3-2. 右上 -> 左下.
        rep(j, b + 1){
            int r = j;
            int c = MAX - b + j;
            if(r >= 0 && r < MAX && c >= 0 && c < MAX) c2[r][c] = p[i + MAX];
        }
    }
    
    // 4. 素数部分を確定させる.
    rep(i, MAX){
        rep(j, MAX){
            ans[i][j] = c1[i][j] * c2[i][j];
            c[i][j].insert(c1[i][j]);
            c[i][j].insert(c2[i][j]);
        }
    }
    
    // 5. 未確定部分を敷き詰める.
    // -> 1e15 制約に注意.
    rep(i, MAX){
        rep(j, MAX){
            // 5-1. すでに確定している場合は, Skip.
            if(ans[i][j]) continue;
            
            // 5-2. 上下左右を取得.
            set<LL> st;
            if(i)           for(auto &q : c[i - 1][j]) st.insert(q);
            if(i < MAX - 1) for(auto &q : c[i + 1][j]) st.insert(q);
            if(j)           for(auto &q : c[i][j - 1]) st.insert(q);
            if(j < MAX - 1) for(auto &q : c[i][j + 1]) st.insert(q);
            
            // 5-3. 最小公倍数.
            LL lcd = 1LL;
            for(auto &q : st) lcd *= q;
            assert(lcd <= 1e15);
            
            // 5-4. 値を設定.
            ans[i][j] = ++lcd;
        }
    }
    
    // 6. すべて異なっているかチェック.
    set<LL> st;
    rep(i, MAX) rep(j, MAX) st.insert(ans[i][j]);
    assert(st.size() == MAX * MAX);
    
    // 7. 出力.
    rep(i, N){
        rep(j, N){
            printf("%lld", ans[i][j]);
            printf("%s", (j < N - 1) ? " " : "\n");
        }
    }
    return 0;
    
}

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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 LIMIT = 101010;

const int MAX = 500;

LL a[LIMIT], c1[MAX][MAX], c2[MAX][MAX], ans[MAX][MAX];

set<LL> c[MAX][MAX];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

// 2. 素数を用意.

repx(i, 2, LIMIT){

if(a[i]) continue;

repex(j, i * 2, LIMIT, i) a[j]++;

}

vl p;

repx(i, 2, LIMIT) if(!a[i] && p.size() < MAX * 2) p.pb((LL)i);

// 3. 市松模様を敷き詰める.

rep(i, MAX){

// 3-1. 左上 -> 右下.

int b = 2 * i;

rep(j, b + 1){

int r = j;

int c = b - j;

if(r >= 0 && r < MAX && c >= 0 && c < MAX) c1[r][c] = p[i];

}

// 3-2. 右上 -> 左下.

rep(j, b + 1){

int r = j;

int c = MAX - b + j;

if(r >= 0 && r < MAX && c >= 0 && c < MAX) c2[r][c] = p[i + MAX];

}

// 4. 素数部分を確定させる.

rep(i, MAX){

rep(j, MAX){

ans[i][j] = c1[i][j] * c2[i][j];

c[i][j].insert(c1[i][j]);

c[i][j].insert(c2[i][j]);

}

// 5. 未確定部分を敷き詰める.

// -> 1e15 制約に注意.

rep(i, MAX){

rep(j, MAX){

// 5-1. すでに確定している場合は, Skip.

if(ans[i][j]) continue;

// 5-2. 上下左右を取得.

set<LL> st;

if(i) for(auto &q : c[i - 1][j]) st.insert(q);

if(i < MAX - 1) for(auto &q : c[i + 1][j]) st.insert(q);

if(j) for(auto &q : c[i][j - 1]) st.insert(q);

if(j < MAX - 1) for(auto &q : c[i][j + 1]) st.insert(q);

// 5-3. 最小公倍数.

LL lcd = 1LL;

for(auto &q : st) lcd *= q;

assert(lcd <= 1e15);

// 5-4. 値を設定.

ans[i][j] = ++lcd;

}

// 6. すべて異なっているかチェック.

set<LL> st;

rep(i, MAX) rep(j, MAX) st.insert(ans[i][j]);

assert(st.size() == MAX * MAX);

// 7. 出力.

rep(i, N){

rep(j, N){

printf("%lld", ans[i][j]);

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

}

return 0;

}

[入力例]
2

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

※但し, 上記のプログラムでは, 以下の値が出力される.
11402 194734759
195350467 17103

[入力例]
3

[出力例]
11402 194734759 17079
195350467 17103 486836896
17133 488376166 28505

[入力例]
4

[出力例]
11402 194734759 17079 485812156
195350467 17103 486836896 28465
17133 488376166 28505 1135952756
489746806 28555 1139544386 39907

[入力例]
5

[出力例]
11402 194734759 17079 485812156 28445
195350467 17103 486836896 28465 1133561696
17133 488376166 28505 1135952756 39851
489746806 28555 1139544386 39907 2499096062
28585 1142742546 39977 2506997648 62711

[入力例]

[出力例]

4 7

23 10

※AtCoderのテストケースより

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

11402 194734759

195350467 17103

[入力例]

[出力例]

11402 194734759 17079

195350467 17103 486836896

17133 488376166 28505

[入力例]

[出力例]

11402 194734759 17079 485812156

195350467 17103 486836896 28465

17133 488376166 28505 1135952756

489746806 28555 1139544386 39907

[入力例]

[出力例]

11402 194734759 17079 485812156 28445

195350467 17103 486836896 28465 1133561696

17133 488376166 28505 1135952756 39851

489746806 28555 1139544386 39907 2499096062

28585 1142742546 39977 2506997648 62711

■参照サイト
AtCoder Grand Contest 027

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

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

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

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

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

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

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

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

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

#define pb push_back

set<int> G[202020];

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

int main(){

// 1. 入力情報.

int N, M;

char s[202020];

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

rep(i, M){

int a, b;

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

a--, b--;

G[a].insert(b);

G[b].insert(a);

}

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

rep(i, N){

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

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

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

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

}

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

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

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

}

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

queue<int> q;

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

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

while(!q.empty()){

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

int u = q.front();

q.pop();

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

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

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

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

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

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

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

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

if(u == v){

info[u][lu]--;

continue;

}

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

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

G[v].erase(u);

info[u][lv]--;

info[v][lu]--;

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

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

}

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

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

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

info[u][2] = 0;

G[u].clear();

}

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

int ans = 0;

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

// 6. 出力.

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

return 0;

}

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

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

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

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

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

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

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

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

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

[出力例]
Yes

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

[出力例]
No

100

101

102

103

104

105

106

107

108

109

110

111

[入力例]

2 3

1 1

1 2

2 2

[出力例]

Yes

※AtCoderのテストケースより

[入力例]

4 3

ABAB

1 2

2 3

3 1

[出力例]

※AtCoderのテストケースより

[入力例]

13 23

ABAAAABBBBAAB

7 1

10 6

1 11

2 10

2 8

2 11

11 12

8 3

7 12

11 2

13 13

11 9

4 1

9 7

9 6

8 13

8 6

4 10

8 7

4 3

2 1

8 12

6 9

[出力例]

Yes

※AtCoderのテストケースより

[入力例]

13 17

BBABBBAABABBA

7 1

7 9

11 12

3 9

11 9

2 1

11 5

12 11

10 8

1 11

1 8

7 7

9 10

8 8

8 12

6 2

13 11

[出力例]

※AtCoderのテストケースより

[入力例]

5 8

ABABA

1 2

1 3

1 1

1 5

2 3

4 5

3 4

2 4

[出力例]

Yes

[入力例]

7 12

AABBABA

1 2

2 3

3 4

4 5

5 6

6 7

7 1

1 7

2 3

1 5

6 4

3 6

[出力例]

■参照サイト
AtCoder Grand Contest 027

2021年4月21日

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

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

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

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

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

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

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

int a[101], b[101];

int main(){

// 1. 入力情報.

int N, x;

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

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

// 2. sort.

sort(a, a + N);

// 3. お菓子を配る.

rep(i, N){

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

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

}

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

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

int ans = 0;

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

// 5. 出力.

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

return 0;

}

[入力例]
3 70
20 30 10

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

[入力例]
3 10
20 30 10

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

[入力例]
4 1111
1 10 100 1000

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

[入力例]
2 10
20 20

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

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

[出力例]
3

[入力例]

3 70

20 30 10

[出力例]

※AtCoderのテストケースより

[入力例]

3 10

20 30 10

[出力例]

※AtCoderのテストケースより

[入力例]

4 1111

1 10 100 1000

[出力例]

※AtCoderのテストケースより

[入力例]

2 10

20 20

[出力例]

※AtCoderのテストケースより

[入力例]

5 123

15 31 67 32 84

[出力例]

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

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

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

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

LL x[202020], xCum[202020];

int main(){

// 1. 入力情報.

int N;

LL X;

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

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

// 2. 累積和.

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

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

LL ans = 202020202020202020;

repx(k, 1, N + 1){

LL cur = 0;

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

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

int i = s / k;

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

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

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

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

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

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

}

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

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

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

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

}

// 4. 出力.

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

return 0;

}

[入力例]
2 100
1 10

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

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

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

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

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

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

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

[入力例]
3 14
15 9 26

[出力例]
320

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

[出力例]
10001

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

[出力例]
5660125250

[入力例]

2 100

1 10

[出力例]

355

※AtCoderのテストケースより

[入力例]

5 1

1 999999997 999999998 999999999 1000000000

[出力例]

19999999983

※AtCoderのテストケースより

[入力例]

10 8851025

38 87 668 3175 22601 65499 90236 790604 4290609 4894746

[出力例]

150710136

※AtCoderのテストケースより

[入力例]

16 10

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

[出力例]

3256017715

※AtCoderのテストケースより

[入力例]

3 14

15 9 26

[出力例]

320

[入力例]

25 47

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

[出力例]

10001

[入力例]

50 20210421

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

[出力例]

5660125250

■参照サイト
AtCoder Grand Contest 027

2021年4月19日

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

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

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

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

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

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

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

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using P = pair<int, int>;

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

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

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

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

#define a first

#define b second

int a[202020];

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

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

int main(){

// 1. 入力情報.

int N, M;

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

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

// 2. 初期化.

int ans = 0;

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

rep(i, N){

int v = a[i];

section[v].a--;

}

repx(i, 1, N + 1){

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

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

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

}

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

// 3. クエリ回答.

rep(i, M){

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

int x, y;

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

x--;

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

int p = a[x];

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

if(lp > 0){

cover[lp]--;

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

}

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

a[x] = y;

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

int q = a[x];

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

if(lq > 0){

cover[lq]++;

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

}

// 3-5. 出力.

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

}

return 0;

}

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

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

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

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

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

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

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

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

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

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

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

[入力例]

5 3

1 1 3 4 5

1 2

2 5

5 4

[出力例]

※AtCoderテストケースより

[入力例]

4 4

4 4 4 4

4 1

3 1

1 1

2 1

[出力例]

※AtCoderテストケースより

[入力例]

10 10

8 7 2 9 10 6 6 5 5 4

8 1

6 3

6 2

7 10

9 7

9 9

2 4

8 1

1 8

7 7

[出力例]

※AtCoderテストケースより

[入力例]

7 10

7 1 4 2 5 6 7

1 1

3 6

7 1

5 3

2 3

2 7

5 3

3 7

1 7

6 3

[出力例]

[入力例]

20 30

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

17 1

14 16

6 15

15 20

4 6

17 4

12 17

15 16

19 11

16 3

9 2

11 9

6 3

9 14

20 13

13 12

19 9

7 19

5 17

1 17

2 17

7 8

11 2

6 12

1 5

6 10

8 20

19 16

7 9

5 4

[出力例]

■参照サイト
AtCoder Grand Contest 017

2021年4月18日

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

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

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

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

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

// C++ (GCC 9.2.1)
// 解き直し.
// https://atcoder.jp/contests/arc116/editorial/893
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define a first
#define b second
const LL MOD = 998244353;
const int LIMIT = 5050;
LL FAC[LIMIT], INV[LIMIT], dp[LIMIT];

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

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

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

// C++ (GCC 9.2.1)

// 解き直し.

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

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

#define a first

#define b second

const LL MOD = 998244353;

const int LIMIT = 5050;

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

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

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

// @param b: 指数.

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

LL mPow(LL a, LL b){

LL t = 1;

while(b){

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

a = a * a % MOD;

b >>= 1;

}

return t % MOD;

}

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

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

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

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

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

LL combination(LL n, LL k){

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

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

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

return ret;

}

int main(){

// 1. 入力情報.

int N, M;

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

FAC[0] = 1;

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

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

// 2. 解説通り.

dp[0] = 1;

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

rep(j, N){

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

if(idx < 0) break;

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

dp[i] %= MOD;

}

// 3. 出力.

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

return 0;

}

[入力例]
5 20

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

[入力例]
10 5

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

[入力例]
3141 2718

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

[入力例]
3 10

[出力例]
9

[入力例]
7 16

[出力例]
16471

[入力例]
2020 418

[出力例]
670494756

[入力例]

5 20

[出力例]

475

※AtCoderのテストケースより

[入力例]

10 5

[出力例]

※AtCoderのテストケースより

[入力例]

3141 2718

[出力例]

371899128

※AtCoderのテストケースより

[入力例]

3 10

[出力例]

[入力例]

7 16

[出力例]

16471

[入力例]

2020 418

[出力例]

670494756

■参照サイト
AtCoder Regular Contest 116

C++の練習を兼ねて, AtCoder Grand Contest 036 の 問題B (Do Not Duplicate) を解いてみた.

C++の練習を兼ねて, ZONeエナジー プログラミングコンテスト “HELLO SPACE” の 問題C (MAD TEAM) ～ 問題D (宇宙人からのメッセージ) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 117 の 問題A (God Sequence) ～ 問題C (Tricolor Pyramid) を解いてみた.

C++の練習を兼ねて, AtCoder Grand Contest 035 の 問題C (Skolem XOR Tree) を解いてみた.

C++の練習を兼ねて, AtCoder Grand Contest 035 の 問題A (XOR Circle) ～ 問題B (Even Degrees) を解いてみた.

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

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

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

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

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

C++の練習を兼ねて, AtCoder Grand Contest 036 の問題B (Do Not Duplicate) を解いてみた.

C++の練習を兼ねて, ZONeエナジープログラミングコンテスト “HELLO SPACE” の問題C (MAD TEAM) ～問題D (宇宙人からのメッセージ) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 117 の問題A (God Sequence) ～問題C (Tricolor Pyramid) を解いてみた.

C++の練習を兼ねて, AtCoder Grand Contest 035 の問題C (Skolem XOR Tree) を解いてみた.

C++の練習を兼ねて, AtCoder Grand Contest 035 の問題A (XOR Circle) ～問題B (Even Degrees) を解いてみた.

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

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

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

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

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