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

C++の練習を兼ねて, AtCoder Regular Contest 103 の問題E (Tr/ee) を解いてみた.

■感想.
1. 問題Eは, 方針が見えなかったので, 解説を参考に, AC版に到達できた.
2. 個人的には, 特殊な性質を持つグラフを抽出するロジックが, 面白いと感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/arc103/editorial.pdf
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;
using vp = vector<P>;
#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 main(){
    
    // 1. 入力情報.
    char x[101010];
    scanf("%s", x);
    string s(x);
    int N = s.size();
    
    // 2. 条件を満たすか？
    bool ok = true;
    if(s[0] != '1' || s[N - 1] != '0') ok = false;
    repx(i, 1, N - 1) if(s[i] != s[N - 2 - i]) ok = false;
    
    // 3. 例外.
    if(!ok){
        puts("-1");
        return 0;
    }
    
    // 4. グラフ構築.
    // 4-1. 根 を 設定.
    s[N - 1] = '1';
    
    // 4-2. 文字 '1'.
    vp ans(N - 1);
    int c = 0;
    repx(i, 1, N){
        if(s[i] == '1'){
            // {子頂点, 親頂点} を 設定.
            ans[c] = {c + 1, i + 1};
            
            // 子頂点更新.
            c = i;
        }
    }
    
    // 4-3. 文字 '0'.
    rep(i, N){
        // 子頂点 を 設定.
        if(s[i] == '1') c = ans[i].b;
        
        // {子頂点, 親頂点} を 設定.
        if(s[i] == '0') ans[i] = {c, i + 1};
    }
    
    // 5. 出力.
    for(auto &p : ans) printf("%d %d\n", p.a, p.b);
    return 0;
    
}

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using P = pair<int, int>;

using vp = vector<P>;

#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 main(){

// 1. 入力情報.

char x[101010];

scanf("%s", x);

string s(x);

int N = s.size();

// 2. 条件を満たすか？

bool ok = true;

if(s[0] != '1' || s[N - 1] != '0') ok = false;

repx(i, 1, N - 1) if(s[i] != s[N - 2 - i]) ok = false;

// 3. 例外.

if(!ok){

puts("-1");

return 0;

}

// 4. グラフ構築.

// 4-1. 根を設定.

s[N - 1] = '1';

// 4-2. 文字 '1'.

vp ans(N - 1);

int c = 0;

repx(i, 1, N){

if(s[i] == '1'){

// {子頂点, 親頂点} を設定.

ans[c] = {c + 1, i + 1};

// 子頂点更新.

c = i;

}

// 4-3. 文字 '0'.

rep(i, N){

// 子頂点を設定.

if(s[i] == '1') c = ans[i].b;

// {子頂点, 親頂点} を設定.

if(s[i] == '0') ans[i] = {c, i + 1};

}

// 5. 出力.

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

return 0;

}

[入力例]
1111

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

[入力例]
1110

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

[入力例]
1010

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

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

[入力例]
1001110010

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

[入力例]
11000010101010000110

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

[入力例]

1111

[出力例]

-1

※AtCoderテストケースより

[入力例]

1110

[出力例]

1 2

2 3

3 4

※AtCoderテストケースより

[入力例]

1010

[出力例]

1 2

1 3

1 4

※AtCoderテストケースより

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

1 3

3 2

3 4

[入力例]

1001110010

[出力例]

1 4

4 2

4 3

4 5

5 6

6 9

9 7

9 8

9 10

[入力例]

11000010101010000110

[出力例]

1 2

2 7

7 3

7 4

7 5

7 6

7 9

9 8

9 11

11 10

11 13

13 12

13 18

18 14

18 15

18 16

18 17

18 19

19 20

■参照サイト
AtCoder Regular Contest 103

C++の練習を兼ねて, AtCoder Regular Contest 103 の 問題E (Tr/ee) を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 103 の問題E (Tr/ee) を解いてみた.

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