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

C++の練習を兼ねて, AtCoder Regular Contest 007 の問題C (C – 節約生活) を解いてみた.

■感想.
1. 個人的には, 非常に面白い問題と感じた.
2. 但し, TLE版(2103[ms]) を AC版(1546[ms]) に持っていくための実装に, 非常に苦労した.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

#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 all(x) x.begin(), x.end()
int ox[11][111];

int main(){
    
    // 1. 入力情報.
    char c[22];
    scanf("%s", c);
    string s(c);
    
    // 2. 入寮情報を, 0, 1 に 変換.
    int l = s.size();
    rep(i, 111) if(s[i % l] == 'o') ox[0][i] = 1;
    // rep(i, 111) printf("%d", ox[0][i]);
    // puts("");
    
    // 3. 'o' の 数が, l と 同じならば, 終了.
    // ex.
    // ooo
    // -> 1 が 正解のはず.
    // -> このパターンを追加したことで, 01_rand_11.txt, 03_max.txt の WA を 回避できた.
    int oCount = 0;
    rep(i, l) if(s[i] == 'o') oCount++;
    if(l == oCount){
        puts("1");
        return 0;
    }
    
    // 4. 'o' の 数が, 1個ならば, 終了.
    // ex.
    // xxxxxxxxxo
    // -> 10 が 正解のはず.
    // -> TLE防止のため(7563[ms]).
    if(1 == oCount){
        printf("%d\n", l);
        return 0;
    }
    
    // 5. 視聴パターンをチェック.
    // 02_maxrand_04.txt を AC にするには？
    // ex.
    // xxxxxxoxxo
    // -> 5 が 正解.
    // 
    // [配置例]
    // xxxxxxoxxoxxxxxxoxxo
    //   xxxxxxoxxoxxxxxxoxxo
    //     xxxxxxoxxoxxxxxxoxxo
    //       xxxxxxoxxoxxxxxxoxxo
    //         xxxxxxoxxoxxxxxxoxxo
    // -> 上記のような配置で, 5 を 実現できる.
    // 
    // ex.
    // xooxo
    // -> スタート地点を, 3箇所とする場合, 以下のパターンをチェック.
    // {0, 1, 2}, {0, 1, 3}, {0, 1, 4}, 
    // {0, 2, 3}, {0, 2, 4}, 
    // {0, 3, 4}
    int ans = 1;
    repx(i, 1, l){
        // スタート地点を, (i + 1)箇所とする場合.
        vector<int> z(9);
        iota(all(z), 1);
        int mCount = 0;
        do{
            // for(auto &p : z) printf("%d ", p);
            // puts("");
            
            // 初期化.
            repx(j, 1, i + 1) rep(k, 111) ox[j][k] = 0;
            
            // 視聴パターンを設定.
            repx(j, 1, i + 1) repx(k, z[j], 111) if(s[(k - z[j]) % l] == 'o') ox[j][k] = 1;
            
            // 視聴パターンチェック.
            // l ～ (2 * l - 1)番目 を チェック.
            int count = 0;
            repx(k, l, 2 * l){
                int a = 0;
                rep(i2, i + 1) a |= ox[i2][k];
                count += a;
            }
            
            // 最大値更新.
            if(mCount < count){
                mCount = count;
                ans = i + 1;
                // printf("----- start i=%d -----\n", i);
                // rep(x, i + 1){
                //     repx(y, l, 2 * l) printf("%d", ox[x][y]);
                //     puts("");
                // }
                // puts("----- end -----");
            }
        }while(next_permutation(all(z)));
        // mCount が l個以上ならば, 終了.
        if(mCount >= l) break;
    }
    
    // 6. 出力.
    printf("%d\n", ans);
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

110

#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 all(x) x.begin(), x.end()

int ox[11][111];

int main(){

// 1. 入力情報.

char c[22];

scanf("%s", c);

string s(c);

// 2. 入寮情報を, 0, 1 に変換.

int l = s.size();

rep(i, 111) if(s[i % l] == 'o') ox[0][i] = 1;

// rep(i, 111) printf("%d", ox[0][i]);

// puts("");

// 3. 'o' の数が, l と同じならば, 終了.

// ex.

// ooo

// -> 1 が正解のはず.

// -> このパターンを追加したことで, 01_rand_11.txt, 03_max.txt の WA を回避できた.

int oCount = 0;

rep(i, l) if(s[i] == 'o') oCount++;

if(l == oCount){

puts("1");

return 0;

}

// 4. 'o' の数が, 1個ならば, 終了.

// ex.

// xxxxxxxxxo

// -> 10 が正解のはず.

// -> TLE防止のため(7563[ms]).

if(1 == oCount){

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

return 0;

}

// 5. 視聴パターンをチェック.

// 02_maxrand_04.txt を AC にするには？

// ex.

// xxxxxxoxxo

// -> 5 が正解.

// [配置例]

// xxxxxxoxxoxxxxxxoxxo

// -> 上記のような配置で, 5 を実現できる.

// ex.

// xooxo

// -> スタート地点を, 3箇所とする場合, 以下のパターンをチェック.

// {0, 1, 2}, {0, 1, 3}, {0, 1, 4},

// {0, 2, 3}, {0, 2, 4},

// {0, 3, 4}

int ans = 1;

repx(i, 1, l){

// スタート地点を, (i + 1)箇所とする場合.

vector<int> z(9);

iota(all(z), 1);

int mCount = 0;

do{

// for(auto &p : z) printf("%d ", p);

// puts("");

// 初期化.

repx(j, 1, i + 1) rep(k, 111) ox[j][k] = 0;

// 視聴パターンを設定.

repx(j, 1, i + 1) repx(k, z[j], 111) if(s[(k - z[j]) % l] == 'o') ox[j][k] = 1;

// 視聴パターンチェック.

// l ～ (2 * l - 1)番目をチェック.

int count = 0;

repx(k, l, 2 * l){

int a = 0;

rep(i2, i + 1) a |= ox[i2][k];

count += a;

}

// 最大値更新.

if(mCount < count){

mCount = count;

ans = i + 1;

// printf("----- start i=%d -----\n", i);

// rep(x, i + 1){

// repx(y, l, 2 * l) printf("%d", ox[x][y]);

// puts("");

// }

// puts("----- end -----");

}

}while(next_permutation(all(z)));

// mCount が l個以上ならば, 終了.

if(mCount >= l) break;

}

// 6. 出力.

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

return 0;

}

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

#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 all(x) x.begin(), x.end()
#define pb push_back
int ox[11][111];
set<set<int>> sSet[9];

int main(){
    
    // 1. 入力情報.
    char c[22];
    scanf("%s", c);
    string s(c);
    
    // 2. 入寮情報を, 0, 1 に 変換.
    int l = s.size();
    rep(i, 111) if(s[i % l] == 'o') ox[0][i] = 1;
    // rep(i, 111) printf("%d", ox[0][i]);
    // puts("");
    
    // 3. 'o' の 数が, l と 同じならば, 終了.
    // ex.
    // ooo
    // -> 1 が 正解のはず.
    // -> このパターンを追加したことで, 01_rand_11.txt, 03_max.txt の WA を 回避できた.
    int oCount = 0;
    rep(i, l) if(s[i] == 'o') oCount++;
    if(l == oCount){
        puts("1");
        return 0;
    }
    
    // 4. 'o' の 数が, 1個ならば, 終了.
    // ex.
    // xxxxxxxxxo
    // -> 10 が 正解のはず.
    // -> TLE防止のため(7563[ms]).
    // if(1 == oCount){
    //     printf("%d\n", l);
    //     return 0;
    // }
    // -> 5. の 事前処理を追加したので, 廃止.
    
    // 5. 順列を保存.
    // 02_maxrand_16.txt で, TLE版(2103[ms]) と なったため, 事前計算してみる.
    vector<int> z(9);
    iota(all(z), 1);
    do{
        rep(i, 9){
            set<int> s;
            rep(j, i + 1) s.insert(z[j]);
            sSet[i].insert(s);
        }
    }while(next_permutation(all(z)));
    
    // rep(i, 9){
    //     for(auto &p : sSet[i]){
    //         for(auto &q : p) printf("%d ", q);
    //         puts("");
    //     }
    // }
    
    // 6. 視聴パターンをチェック.
    // 02_maxrand_04.txt を AC にするには？
    // ex.
    // xxxxxxoxxo
    // -> 5 が 正解.
    // 
    // [配置例]
    // xxxxxxoxxoxxxxxxoxxo
    //   xxxxxxoxxoxxxxxxoxxo
    //     xxxxxxoxxoxxxxxxoxxo
    //       xxxxxxoxxoxxxxxxoxxo
    //         xxxxxxoxxoxxxxxxoxxo
    // -> 上記のような配置で, 5 を 実現できる.
    // 
    // ex.
    // xooxo
    // -> スタート地点を, 3箇所とする場合, 以下のパターンをチェック.
    // {0, 1, 2}, {0, 1, 3}, {0, 1, 4}, 
    // {0, 2, 3}, {0, 2, 4}, 
    // {0, 3, 4}
    int ans = 1;
    repx(i, 1, l){
        // スタート地点を, (i + 1)箇所とする場合.
        int mCount = 0;
        for(auto &p : sSet[i - 1]){
            // 初期化.
            repx(j, 1, i + 1) rep(k, 111) ox[j][k] = 0;
            
            // 視聴パターンを設定.
            int r = 0;
            for(auto &q : p){
                r++;
                repx(k, q, 111) if(s[(k - q) % l] == 'o') ox[r][k] = 1;
            }
            
            // 視聴パターンチェック.
            // l ～ (2 * l - 1)番目 を チェック.
            int count = 0;
            repx(k, l, 2 * l){
                int a = 0;
                rep(i2, i + 1) a |= ox[i2][k];
                count += a;
            }
            
            // 最大値更新.
            if(mCount < count){
                mCount = count;
                ans = i + 1;
                // printf("----- start i=%d -----\n", i);
                // rep(x, i + 1){
                //     repx(y, l, 2 * l) printf("%d", ox[x][y]);
                //     puts("");
                // }
                // puts("----- end -----");
            }
        }
        // mCount が l個以上ならば, 終了.
        if(mCount >= l) break;
    }
    
    // 7. 出力.
    printf("%d\n", ans);
    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

#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 all(x) x.begin(), x.end()

#define pb push_back

int ox[11][111];

set<set<int>> sSet[9];

int main(){

// 1. 入力情報.

char c[22];

scanf("%s", c);

string s(c);

// 2. 入寮情報を, 0, 1 に変換.

int l = s.size();

rep(i, 111) if(s[i % l] == 'o') ox[0][i] = 1;

// rep(i, 111) printf("%d", ox[0][i]);

// puts("");

// 3. 'o' の数が, l と同じならば, 終了.

// ex.

// ooo

// -> 1 が正解のはず.

// -> このパターンを追加したことで, 01_rand_11.txt, 03_max.txt の WA を回避できた.

int oCount = 0;

rep(i, l) if(s[i] == 'o') oCount++;

if(l == oCount){

puts("1");

return 0;

}

// 4. 'o' の数が, 1個ならば, 終了.

// ex.

// xxxxxxxxxo

// -> 10 が正解のはず.

// -> TLE防止のため(7563[ms]).

// if(1 == oCount){

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

// return 0;

// }

// -> 5. の事前処理を追加したので, 廃止.

// 5. 順列を保存.

// 02_maxrand_16.txt で, TLE版(2103[ms]) となったため, 事前計算してみる.

vector<int> z(9);

iota(all(z), 1);

do{

rep(i, 9){

set<int> s;

rep(j, i + 1) s.insert(z[j]);

sSet[i].insert(s);

}

}while(next_permutation(all(z)));

// rep(i, 9){

// for(auto &p : sSet[i]){

// for(auto &q : p) printf("%d ", q);

// puts("");

// }

// 6. 視聴パターンをチェック.

// 02_maxrand_04.txt を AC にするには？

// ex.

// xxxxxxoxxo

// -> 5 が正解.

// [配置例]

// xxxxxxoxxoxxxxxxoxxo

// -> 上記のような配置で, 5 を実現できる.

// ex.

// xooxo

// -> スタート地点を, 3箇所とする場合, 以下のパターンをチェック.

// {0, 1, 2}, {0, 1, 3}, {0, 1, 4},

// {0, 2, 3}, {0, 2, 4},

// {0, 3, 4}

int ans = 1;

repx(i, 1, l){

// スタート地点を, (i + 1)箇所とする場合.

int mCount = 0;

for(auto &p : sSet[i - 1]){

// 初期化.

repx(j, 1, i + 1) rep(k, 111) ox[j][k] = 0;

// 視聴パターンを設定.

int r = 0;

for(auto &q : p){

r++;

repx(k, q, 111) if(s[(k - q) % l] == 'o') ox[r][k] = 1;

}

// 視聴パターンチェック.

// l ～ (2 * l - 1)番目をチェック.

int count = 0;

repx(k, l, 2 * l){

int a = 0;

rep(i2, i + 1) a |= ox[i2][k];

count += a;

}

// 最大値更新.

if(mCount < count){

mCount = count;

ans = i + 1;

// printf("----- start i=%d -----\n", i);

// rep(x, i + 1){

// repx(y, l, 2 * l) printf("%d", ox[x][y]);

// puts("");

// }

// puts("----- end -----");

}

// mCount が l個以上ならば, 終了.

if(mCount >= l) break;

}

// 7. 出力.

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

return 0;

}

[入力例]
oxoxx

[出力例(debug版)]
----- start i=1 -----
10100
01010
----- end -----
----- start i=2 -----
10100
01010
00101
----- end -----
3
※AtCoderのテストケースより

[入力例]
oxxxxoooo

[出力例(debug版)]
----- start i=1 -----
100001111
110000111
----- end -----
----- start i=1 -----
100001111
111000011
----- end -----
----- start i=1 -----
100001111
111100001
----- end -----
----- start i=1 -----
100001111
111110000
----- end -----
2
※AtCoderのテストケースより

[入力例]
ox

[出力例(debug版)]
----- start i=1 -----
10
01
----- end -----
2
※AtCoderのテストケースより

[入力例]
o

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

[入力例]
xxxoxo

[出力例(debug版)]
----- start i=1 -----
000101
100010
----- end -----
----- start i=2 -----
000101
100010
010001
----- end -----
----- start i=3 -----
000101
100010
010001
101000
----- end -----
4
※AtCoderのテストケースより

[入力例]
oxoxxoooox

[出力例(debug版)]
----- start i=1 -----
1010011110
0101001111
----- end -----
----- start i=2 -----
1010011110
0101001111
1010100111
----- end -----
3

[入力例]
xxxxxxoxxo

[出力例(debug版)]
----- start i=1 -----
0000001001
1000000100
----- end -----
----- start i=2 -----
0000001001
1000000100
0100000010
----- end -----
----- start i=3 -----
0000001001
1000000100
0100000010
0010000001
----- end -----
----- start i=3 -----
0000001001
1000000100
0100000010
0010010000
----- end -----
----- start i=4 -----
0000001001
1000000100
0100000010
0010000001
1001000000
----- end -----
----- start i=4 -----
0000001001
1000000100
0100000010
1001000000
0010010000
----- end -----
----- start i=4 -----
0000001001
0100000010
1001000000
0010010000
0000100100
----- end -----
5

[入力例]
oxxxxxxxxx

[出力例(debug版)]
----- start i=1 -----
1000000000
0100000000
----- end -----
----- start i=2 -----
1000000000
0100000000
0010000000
----- end -----
----- start i=3 -----
1000000000
0100000000
0010000000
0001000000
----- end -----
----- start i=4 -----
1000000000
0100000000
0010000000
0001000000
0000100000
----- end -----
----- start i=5 -----
1000000000
0100000000
0010000000
0001000000
0000100000
0000010000
----- end -----
----- start i=6 -----
1000000000
0100000000
0010000000
0001000000
0000100000
0000010000
0000001000
----- end -----
----- start i=7 -----
1000000000
0100000000
0010000000
0001000000
0000100000
0000010000
0000001000
0000000100
----- end -----
----- start i=8 -----
1000000000
0100000000
0010000000
0001000000
0000100000
0000010000
0000001000
0000000100
0000000010
----- end -----
----- start i=9 -----
1000000000
0100000000
0010000000
0001000000
0000100000
0000010000
0000001000
0000000100
0000000010
0000000001
----- end -----
10

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

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

[入力例]

oxoxx

[出力例(debug版)]

----- start i=1 -----

10100

01010

----- end -----

----- start i=2 -----

10100

01010

00101

----- end -----

※AtCoderのテストケースより

[入力例]

oxxxxoooo

[出力例(debug版)]

----- start i=1 -----

100001111

110000111

----- end -----

----- start i=1 -----

100001111

111000011

----- end -----

----- start i=1 -----

100001111

111100001

----- end -----

----- start i=1 -----

100001111

111110000

----- end -----

※AtCoderのテストケースより

[入力例]

[出力例(debug版)]

----- start i=1 -----

----- end -----

※AtCoderのテストケースより

[入力例]

[出力例(debug版)]

※AtCoderのテストケースより

[入力例]

xxxoxo

[出力例(debug版)]

----- start i=1 -----

000101

100010

----- end -----

----- start i=2 -----

000101

100010

010001

----- end -----

----- start i=3 -----

000101

100010

010001

101000

----- end -----

※AtCoderのテストケースより

[入力例]

oxoxxoooox

[出力例(debug版)]

----- start i=1 -----

1010011110

0101001111

----- end -----

----- start i=2 -----

1010011110

0101001111

1010100111

----- end -----

[入力例]

xxxxxxoxxo

[出力例(debug版)]

----- start i=1 -----

0000001001

1000000100

----- end -----

----- start i=2 -----

0000001001

1000000100

0100000010

----- end -----

----- start i=3 -----

0000001001

1000000100

0100000010

0010000001

----- end -----

----- start i=3 -----

0000001001

1000000100

0100000010

0010010000

----- end -----

----- start i=4 -----

0000001001

1000000100

0100000010

0010000001

1001000000

----- end -----

----- start i=4 -----

0000001001

1000000100

0100000010

1001000000

0010010000

----- end -----

----- start i=4 -----

0000001001

0100000010

1001000000

0010010000

0000100100

----- end -----

[入力例]

oxxxxxxxxx

[出力例(debug版)]

----- start i=1 -----

1000000000

0100000000

----- end -----

----- start i=2 -----

1000000000

0100000000

0010000000

----- end -----

----- start i=3 -----

1000000000

0100000000

0010000000

0001000000

----- end -----

----- start i=4 -----

1000000000

0100000000

0010000000

0001000000

0000100000

----- end -----

----- start i=5 -----

1000000000

0100000000

0010000000

0001000000

0000100000

0000010000

----- end -----

----- start i=6 -----

1000000000

0100000000

0010000000

0001000000

0000100000

0000010000

0000001000

----- end -----

----- start i=7 -----

1000000000

0100000000

0010000000

0001000000

0000100000

0000010000

0000001000

0000000100

----- end -----

----- start i=8 -----

1000000000

0100000000

0010000000

0001000000

0000100000

0000010000

0000001000

0000000100

0000000010

----- end -----

----- start i=9 -----

1000000000

0100000000

0010000000

0001000000

0000100000

0000010000

0000001000

0000000100

0000000010

0000000001

----- end -----

■参照サイト
AtCoder Regular Contest 007

C++の練習を兼ねて, AtCoder Regular Contest 007 の 問題C (C – 節約生活) を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 007 の問題C (C – 節約生活) を解いてみた.

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