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

C++の練習を兼ねて, AtCoder Grand Contest 032 の問題A (Limited Insertion) ～問題B (Balanced Neighbors) を解いてみた.

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

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

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

// 解き直し.
// https://img.atcoder.jp/agc032/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 pof pop_front
#define pob pop_back
#define pub push_back
#define puf push_front

int main(){
    
    // 1. 入力情報.
    int N, b;
    scanf("%d", &N);
    deque<int> dqI;
    rep(i, N){
        scanf("%d", &b);
        dqI.pub(b);
    }
    
    // 2. 操作を逆順に行う.
    // ex.
    // 10
    // 1 2 3 1 5 1 3 2 5 7
    // [1回目]
    // 1 2 3 1  5  1 3 2 5  7
    // 1 2 3 4 [5] 6 7 8 9 10 -> 一番右側で, b[i] と 等しいものは, 5.
    // -> dq = {5}
    // 
    // [2回目]
    // 1 2  3  1 1 3 2 5 7
    // 1 2 [3] 4 5 6 7 8 9 -> 一番右側で, b[i] と 等しいものは, 3.
    // -> dq = {3, 5}
    // 
    // [3回目]
    // 1  2  1 1 3 2 5 7
    // 1 [2] 3 4 5 6 7 8 -> 一番右側で, b[i] と 等しいものは, 2.
    // -> dq = {2, 3, 5}
    // 
    // [4回目]
    // 1 1 1 3 2 5  7
    // 1 2 3 4 5 6 [7] -> 一番右側で, b[i] と 等しいものは, 7.
    // -> dq = {7, 2, 3, 5}
    // 
    // [5回目]
    //  1  1 1 3 2 5
    // [1] 2 3 4 5 6 -> 一番右側で, b[i] と 等しいものは, 1.
    // -> dq = {1, 7, 2, 3, 5}
    // 
    // [6回目]
    // 1 1 3 2  5
    // 1 2 3 4 [5] -> 一番右側で, b[i] と 等しいものは, 5.
    // -> dq = {5, 1, 7, 2, 3, 5}
    // 
    // [7回目]
    // 1 1  3  2
    // 1 2 [3] 4 -> 一番右側で, b[i] と 等しいものは, 3.
    // -> dq = {3, 5, 1, 7, 2, 3, 5}
    // 
    // [8回目]
    //  1 1  2
    // [1] 2 3 -> 一番右側で, b[i] と 等しいものは, 1.
    // -> dq = {1, 3, 5, 1, 7, 2, 3, 5}
    // 
    // [9回目]
    // 1  2
    // 1 [2] -> 一番右側で, b[i] と 等しいものは, 2.
    // -> dq = {2, 1, 3, 5, 1, 7, 2, 3, 5}
    // 
    // [10回目]
    //  1
    // [1] -> 一番右側で, b[i] と 等しいものは, 1.
    // -> dq = {1, 2, 1, 3, 5, 1, 7, 2, 3, 5} ※ これを出力すれば回答となるはず.
    deque<int> dqO;
    while(!dqI.empty()){
        // 2-1. 入力情報 の サイズ, フラグ を 設定.
        int l = dqI.size();
        bool ok = false;
        
        // 2-2. 入力情報 を 右側から見ていって, 出現位置 の (index + 1) に 等しいものがあるかチェック.
        repr(i, l - 1, 0){
            // 見つかった場合.
            if(i + 1 == dqI[i]){
                ok = true;
                dqO.puf(i + 1);
                dqI.erase(dqI.begin() + i);
                break;
            }
        }
        
        // 2-3. 見つからなかった場合は, 終了.
        if(!ok) break;
    }
    
    // 3. 出力.
    if(dqI.size()){
        puts("-1");
    }else{
        while(!dqO.empty()){
            int ans = dqO.front();
            dqO.pof();
            printf("%d\n", ans);
        }
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

// 解き直し.

// https://img.atcoder.jp/agc032/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 pof pop_front

#define pob pop_back

#define pub push_back

#define puf push_front

int main(){

// 1. 入力情報.

int N, b;

scanf("%d", &N);

deque<int> dqI;

rep(i, N){

scanf("%d", &b);

dqI.pub(b);

}

// 2. 操作を逆順に行う.

// ex.

// 10

// 1 2 3 1 5 1 3 2 5 7

// [1回目]

// 1 2 3 1 5 1 3 2 5 7

// 1 2 3 4 [5] 6 7 8 9 10 -> 一番右側で, b[i] と等しいものは, 5.

// -> dq = {5}

// [2回目]

// 1 2 3 1 1 3 2 5 7

// 1 2 [3] 4 5 6 7 8 9 -> 一番右側で, b[i] と等しいものは, 3.

// -> dq = {3, 5}

// [3回目]

// 1 2 1 1 3 2 5 7

// 1 [2] 3 4 5 6 7 8 -> 一番右側で, b[i] と等しいものは, 2.

// -> dq = {2, 3, 5}

// [4回目]

// 1 1 1 3 2 5 7

// 1 2 3 4 5 6 [7] -> 一番右側で, b[i] と等しいものは, 7.

// -> dq = {7, 2, 3, 5}

// [5回目]

// 1 1 1 3 2 5

// [1] 2 3 4 5 6 -> 一番右側で, b[i] と等しいものは, 1.

// -> dq = {1, 7, 2, 3, 5}

// [6回目]

// 1 1 3 2 5

// 1 2 3 4 [5] -> 一番右側で, b[i] と等しいものは, 5.

// -> dq = {5, 1, 7, 2, 3, 5}

// [7回目]

// 1 1 3 2

// 1 2 [3] 4 -> 一番右側で, b[i] と等しいものは, 3.

// -> dq = {3, 5, 1, 7, 2, 3, 5}

// [8回目]

// 1 1 2

// [1] 2 3 -> 一番右側で, b[i] と等しいものは, 1.

// -> dq = {1, 3, 5, 1, 7, 2, 3, 5}

// [9回目]

// 1 2

// 1 [2] -> 一番右側で, b[i] と等しいものは, 2.

// -> dq = {2, 1, 3, 5, 1, 7, 2, 3, 5}

// [10回目]

// 1

// [1] -> 一番右側で, b[i] と等しいものは, 1.

// -> dq = {1, 2, 1, 3, 5, 1, 7, 2, 3, 5} ※ これを出力すれば回答となるはず.

deque<int> dqO;

while(!dqI.empty()){

// 2-1. 入力情報のサイズ, フラグを設定.

int l = dqI.size();

bool ok = false;

// 2-2. 入力情報を右側から見ていって, 出現位置の (index + 1) に等しいものがあるかチェック.

repr(i, l - 1, 0){

// 見つかった場合.

if(i + 1 == dqI[i]){

ok = true;

dqO.puf(i + 1);

dqI.erase(dqI.begin() + i);

break;

}

// 2-3. 見つからなかった場合は, 終了.

if(!ok) break;

}

// 3. 出力.

if(dqI.size()){

puts("-1");

}else{

while(!dqO.empty()){

int ans = dqO.front();

dqO.pof();

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

}

return 0;

}

[入力例]
3
1 2 1

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

[入力例]
2
2 2

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

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

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

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

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

[入力例]

1 2 1

[出力例]

※AtCoderのテストケースより

[入力例]

2 2

[出力例]

-1

※AtCoderのテストケースより

[入力例]

1 1 1 2 2 1 2 3 2

[出力例]

※AtCoderのテストケースより

[入力例]

1 2 3 1 5 1 3 2 5 7

[出力例]

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

// 解き直し.
// https://img.atcoder.jp/agc032/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);
    
    // 2. 補グラフ(Complement Graph)作成.
    vvi G(N);
    int sign = (N & 1), M = 0;
    // 2-1. N が 奇数 の 場合.
    if(sign) rep(i, N) repx(j, i + 1, N) if(i + j != N - 2) G[i].pb(j), M++;
    
    // 2-2. N が 偶数 の 場合.
    if(!sign) rep(i, N) repx(j, i + 1, N) if(i + j != N - 1) G[i].pb(j), M++;
    
    // 3. 出力.
    printf("%d\n", M);
    rep(i, N) for(auto &v : G[i]) printf("%d %d\n", i + 1, v + 1);
    return 0;
}

// 解き直し.

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

// 2. 補グラフ(Complement Graph)作成.

vvi G(N);

int sign = (N & 1), M = 0;

// 2-1. N が奇数の場合.

if(sign) rep(i, N) repx(j, i + 1, N) if(i + j != N - 2) G[i].pb(j), M++;

// 2-2. N が偶数の場合.

if(!sign) rep(i, N) repx(j, i + 1, N) if(i + j != N - 1) G[i].pb(j), M++;

// 3. 出力.

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

rep(i, N) for(auto &v : G[i]) printf("%d %d\n", i + 1, v + 1);

return 0;

}

[入力例]
3

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

[入力例]
4

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

[入力例]
5

[出力例]
8
1 2
1 3
1 5
2 4
2 5
3 4
3 5
4 5

[入力例]
6

[出力例]
12
1 2
1 3
1 4
1 5
2 3
2 4
2 6
3 5
3 6
4 5
4 6
5 6

[入力例]

[出力例]

1 3

2 3

※AtCoderのテストケースより

[入力例]

[出力例]

1 2

1 3

2 4

3 4

[入力例]

[出力例]

1 2

1 3

1 5

2 4

2 5

3 4

3 5

4 5

[入力例]

[出力例]

1 2

1 3

1 4

1 5

2 3

2 4

2 6

3 5

3 6

4 5

4 6

5 6

■参照サイト
AtCoder Grand Contest 032

C++の練習を兼ねて, AtCoder Grand Contest 032 の 問題A (Limited Insertion) ～ 問題B (Balanced Neighbors) を解いてみた.

コメントを残す コメントをキャンセル

C++の練習を兼ねて, AtCoder Grand Contest 032 の問題A (Limited Insertion) ～問題B (Balanced Neighbors) を解いてみた.

コメントを残すコメントをキャンセル