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

C++の練習を兼ねて, AtCoder Grand Contest 006 の問題A (Prefix and Suffix) ～問題B (Median Pyramid Easy) を解いてみた.

■感想.
1. 解答を見る前に, 何とか解答まで辿り着いたので良かったと思う.
2. 問題B は, 最初, X = N, N – 1, N + 1 に限定されると方針を立てて解いたが, WAとなって, 改めて調べたところ, X = 1, 2 * N – 1 以外の X で, 条件を満たす配置が見つかったので, 何とか解答に辿り着けた.

本家のサイトAtCoderGrandContest006解説をご覧下さい.

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

#include <bits/stdc++.h>
using namespace std;

int main() {
    
    // 1. 入力情報取得.
    int N;
    string s, t;
    cin >> N >> s >> t;
    
    // 2. 条件を満たす最も短い文字列を作成.
    int ans;
    for(int i = 0; i < N + 1; i++){
        string merge = s.substr(0, i) + t;
        ans = merge.size();
        string f = merge.substr(0, N);
        string e = merge.substr(ans - N, N);
        // cout << "s=" << s << " f=" << f << " t=" << t << " e=" << e << endl;
        if(f == s && e == t) break;
    }
    
    // 3. 出力.
    cout << ans << endl;
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

int main() {

// 1. 入力情報取得.

int N;

string s, t;

cin >> N >> s >> t;

// 2. 条件を満たす最も短い文字列を作成.

int ans;

for(int i = 0; i < N + 1; i++){

string merge = s.substr(0, i) + t;

ans = merge.size();

string f = merge.substr(0, N);

string e = merge.substr(ans - N, N);

// cout << "s=" << s << " f=" << f << " t=" << t << " e=" << e << endl;

if(f == s && e == t) break;

}

// 3. 出力.

cout << ans << endl;

return 0;

}

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

#include <bits/stdc++.h>
using namespace std;
const string YES = "Yes";
const string NO  = "No";

int main() {
    
    // 1. 入力情報取得.
    int N, X;
    cin >> N >> X;
    
    // 2. N が 2 に等しい 場合.
    if(N == 2){
        if(X == 2){
            cout << YES << endl;
            for(int i = 1; i <= 3; i++) cout << i << endl;
        }
        if(X != 2) cout << NO << endl;
        return 0;
    }
    
    // 3. N が 3以上 の 場合.
    int baseSize = 2 * N - 1;
    if(N >= 3){
        // 3-1. X = N の 場合.
        if(X == N){
            cout << YES << endl;
            for(int i = 1; i <= baseSize; i++) cout << i << endl;
            return 0;
        }
        
        // 3-2. X = 2 ～ N - 1 の 場合.
        if(X > 1 && X < N){
            vector<int> v;
            for(int i = 1; i <= baseSize; i++) if(i < X - 1 || i > X + 2) v.push_back(i);
            // for(auto &p : v) cout << p << endl;
            int border = N - 2;
            cout << YES << endl;
            for(int i = 0; i < border - 1; i++) cout << v[i] << endl;
            cout << (X + 1) << endl;
            cout << (X - 1) << endl;
            cout << X << endl;
            cout << (X + 2) << endl;
            for(int i = border - 1; i < baseSize - 4; i++) cout << v[i] << endl;
            return 0;
        }
        
        // 3-3. X = N + 1 ～ 2 * N - 2 の 場合.
        if(X > N && X < baseSize){
            vector<int> v;
            for(int i = 1; i <= baseSize; i++) if(i < X - 2 || i > X + 1) v.push_back(i);
            // for(auto &p : v) cout << p << endl;
            int border = N - 2;
            cout << YES << endl;
            for(int i = 0; i < border - 1; i++) cout << v[i] << endl;
            cout << (X - 1) << endl;
            cout << X << endl;
            cout << (X + 1) << endl;
            cout << (X - 2) << endl;
            for(int i = border - 1; i < baseSize - 4; i++) cout << v[i] << endl;
            return 0;
        }
        
    }
    
    // 4. 出力 ～ 後処理.
    cout << NO << endl;
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

const string YES = "Yes";

const string NO = "No";

int main() {

// 1. 入力情報取得.

int N, X;

cin >> N >> X;

// 2. N が 2 に等しい場合.

if(N == 2){

if(X == 2){

cout << YES << endl;

for(int i = 1; i <= 3; i++) cout << i << endl;

}

if(X != 2) cout << NO << endl;

return 0;

}

// 3. N が 3以上の場合.

int baseSize = 2 * N - 1;

if(N >= 3){

// 3-1. X = N の場合.

if(X == N){

cout << YES << endl;

for(int i = 1; i <= baseSize; i++) cout << i << endl;

return 0;

}

// 3-2. X = 2 ～ N - 1 の場合.

if(X > 1 && X < N){

vector<int> v;

for(int i = 1; i <= baseSize; i++) if(i < X - 1 || i > X + 2) v.push_back(i);

// for(auto &p : v) cout << p << endl;

int border = N - 2;

cout << YES << endl;

for(int i = 0; i < border - 1; i++) cout << v[i] << endl;

cout << (X + 1) << endl;

cout << (X - 1) << endl;

cout << X << endl;

cout << (X + 2) << endl;

for(int i = border - 1; i < baseSize - 4; i++) cout << v[i] << endl;

return 0;

}

// 3-3. X = N + 1 ～ 2 * N - 2 の場合.

if(X > N && X < baseSize){

vector<int> v;

for(int i = 1; i <= baseSize; i++) if(i < X - 2 || i > X + 1) v.push_back(i);

// for(auto &p : v) cout << p << endl;

int border = N - 2;

cout << YES << endl;

for(int i = 0; i < border - 1; i++) cout << v[i] << endl;

cout << (X - 1) << endl;

cout << X << endl;

cout << (X + 1) << endl;

cout << (X - 2) << endl;

for(int i = border - 1; i < baseSize - 4; i++) cout << v[i] << endl;

return 0;

}

// 4. 出力～後処理.

cout << NO << endl;

return 0;

}

[入力例]
4 4

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

[入力例]
2 1

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

[入力例]
2 2

[出力例]
Yes
1
2
3

[入力例]
3 2

[出力例]
Yes
3
1
2
4
5

[入力例]
3 4

[出力例]
Yes
3
4
5
2
1

[入力例]
5 2

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

[入力例]
5 8

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

[入力例]
6 3

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

[入力例]
11 2

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

[入力例]
11 20

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

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

[入力例]

4 4

[出力例]

Yes

※AtCoderのテストケースより

[入力例]

2 1

[出力例]

※AtCoderのテストケースより

[入力例]

2 2

[出力例]

Yes

[入力例]

3 2

[出力例]

Yes

[入力例]

3 4

[出力例]

Yes

[入力例]

5 2

[出力例]

Yes

[入力例]

5 8

[出力例]

Yes

[入力例]

6 3

[出力例]

Yes

[入力例]

11 2

[出力例]

Yes

[入力例]

11 20

[出力例]

Yes

■参照サイト
AtCoder Grand Contest 006

C++の練習を兼ねて, AtCoder Grand Contest 006 の 問題A (Prefix and Suffix) ～ 問題B (Median Pyramid Easy) を解いてみた.

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

C++の練習を兼ねて, AtCoder Grand Contest 006 の問題A (Prefix and Suffix) ～問題B (Median Pyramid Easy) を解いてみた.

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