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

C++の練習を兼ねて, AtCoder Regular Contest 057 の問題C (2乗根) を解いてみた.

■感想.
1. 問題Cは, 方針が見えなかったので, 解説を参考に, AC版に到達できた.
2. 個人的には, 実装に非常に苦労したものの, 文字列ベースで, 大きな桁数を持つ, 整数同士の加算, 乗算の実装訓練が積めたので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/data/arc/057/editorial.pdf
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vs = vector<string>;
#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()

// 与えられた文字列を整数と見て, 0 ～ 9倍した値を計算.
// @param s: 正整数.
// @return:  計算結果.
vs multiplyBetweenZeroToNine(string s){
    int sl = s.size();
    vs ret;
    
    // 0 ～ 9倍.
    rep(i, 10){
        string v;
        int c = 0;
        repr(j, sl - 1, 0){
            string x = to_string((s[j] - '0') * i + c);
            int xl = x.size();
            if(xl == 1){
                v.pub(x[0]);
                c = 0;
            }
            if(xl == 2){
                v.pub(x[1]);
                c = x[0] - '0';
                if(!j) v.pub(x[0]);
            }
            assert(xl >= 1 && xl <= 2);
        }
        reverse(all(v));
        ret.pub(v);
    }
    
    // 返却.
    return ret;
}

// 与えられた文字列を整数と見て, 乗算を行う.
// @param s: 正整数.
// @param t: 正整数.
// @return:  計算結果.
string sMultiply(string s, string t){
    string ret;
    int sl = s.size(), tl = t.size();
    vs s09 = multiplyBetweenZeroToNine(s);
    
    // 各桁単体で, 乗算.
    vs tCalc;
    repr(i, tl - 1, 0){
        string v = s09[t[i] - '0'];
        int vl = v.size();
        string zb(tl - 1 - i, '0');
        string zf(sl + tl - vl - zb.size(), '0');
        v = zf + v + zb;
        tCalc.pub(v);
    }
    
    // 集計.
    ret = tCalc[0];
    repx(i, 1, tl){
        string v;
        int c = 0;
        repr(j, sl + tl - 1, 0){
            string x = to_string((ret[j] - '0') + (tCalc[i][j] - '0') + c);
            int xl = x.size();
            if(xl == 1){
                v.pub(x[0]);
                c = 0;
            }
            if(xl == 2){
                v.pub(x[1]);
                c = x[0] - '0';
                if(!j) v.pub(x[0]);
            }
            assert(xl >= 1 && xl <= 2);
        }
        reverse(all(v));
        ret = v;
    }
    
    // 先頭が, '0' ならば 削除.
    if(ret[0] == '0') ret = ret.substr(1);
    
    // 返却.
    return ret;
}

// 与えられた文字列を整数と見て, 加算を行う.
// @param s: 正整数.
// @param t: 正整数.
// @return:  計算結果.
string sAdd(string s, string t){
    int sl = s.size();
    int tl = t.size();
    int ml = max(sl, tl) + 1;
    string zs(ml - sl, '0');
    string zt(ml - tl, '0');
    string ns = zs + s;
    string nt = zt + t;
    
    // 各桁を加算.
    string ret;
    int c = 0;
    repr(j, ml - 1, 0){
        string x = to_string((ns[j] - '0') + (nt[j] - '0') + c);
        int xl = x.size();
        if(xl == 1){
            ret.pub(x[0]);
            c = 0;
        }
        if(xl == 2){
            ret.pub(x[1]);
            c = x[0] - '0';
            if(!j) ret.pub(x[0]);
        }
        assert(xl >= 1 && xl <= 2);
    }
    while(ret.size() < ml) ret.pub('0');
    if(ret.back() == '0') ret.pob();
    reverse(all(ret));
    
    // 返却.
    return ret;
}

int main(){
    
    // 1. 入力情報.
    char c[1010];
    scanf("%s", c);
    string s(c);
    
    // ex.
    // 20211225 を 使って, 0 ～ 9倍した場合.
    // 
    // 000000000
    // 020211225
    // 040422450
    // 060633675
    // 080844900
    // 101056125
    // 121267350
    // 141478575
    // 161689800
    // 181901025
    // 
    // vs x = multiplyBetweenZeroToNine("20211225");
    // for(auto &p : x) printf("%s\n", p.c_str());
    
    // ex.
    // 2021 * 2022 -> 4086462 の 計算.
    // printf("%s\n", sMultiply("2021", "2022").c_str());
    // 
    // 3456 * 789 -> 2726784 の 計算.
    // printf("%s\n", sMultiply("3456", "789").c_str());
    // 
    // 20211225 * 20220101 -> 408673010833725 の 計算.
    // printf("%s\n", sMultiply("20211225", "20220101").c_str());
    // 
    // 31622776601683793319 * 314159265358979323846264338327
    // -> 9934588265796101234122867437613016024182958237313 の 計算.
    // printf("%s\n", sMultiply("31622776601683793319", "314159265358979323846264338327").c_str());
    // 
    // 12 + 15 -> 27 の 計算.
    // printf("%s\n", sAdd("12", "15").c_str());
    // 
    // 98765 + 4321 -> 103086 の 計算.
    // printf("%s\n", sAdd("98765", "4321").c_str());
    // 
    // 12345 + 54321 -> 66666 の 計算.
    // printf("%s\n", sAdd("12345", "54321").c_str());
    // 
    // 15249 + 86073 -> 101322 の 計算.
    // printf("%s\n", sAdd("15249", "86073").c_str());
    
    // 2. 事前準備(解説通り).
    // 2-1. A, A + 1 の 二乗.
    string a0 = sMultiply(s, s);
    string s1 = sAdd(s, "1");
    string a1 = sMultiply(s1, s1);
    
    // 2-2. 桁数揃える('0' 埋め).
    while(a0.size() < a1.size()) a0.insert(a0.begin(), '0');
    assert(a0.size() == a1.size());
    // printf("%s\n", a0.c_str());
    // printf("%s\n", a1.c_str());
    
    // 2-3. 偶数桁('0' 埋め).
    int odd = 0;
    if(a0.size() & 1){
        a0.pub('0');
        a1.pub('0');
        odd++;
    }
    
    // 3. N を 探索.
    string ans;
    rep(t, 101){
        string z(t * 2, '0');
        a0 = a0 + z;
        a1 = a1 + z;
        // printf("a0=%s a1=%s\n", a0.c_str(), a1.c_str());
        
        // 先頭 d 桁.
        bool ok = false;
        int al = a0.size();
        
        repex(d, 2 - odd, al, 2){
            // N の 候補.
            string n0 = a0.substr(0, d);
            string n1 = sAdd(n0, "1");
            string zb0(al - n0.size(), '0');
            string zb1(al - n1.size(), '0');
            string tn0 = n0 + zb0;
            string tn1 = n1 + zb1;
            // printf("n0=%s tn0=%s n1=%s tn1=%s\n", n0.c_str(), tn0.c_str(), n1.c_str(), tn1.c_str());
            
            // 判定(その1).
            if(tn0 >= a0 && tn0 < a1){
                if(n0[0] == '0') ans = n0.substr(1);
                else             ans = n0;
                ok = true;
                break;
            }
            
            // 判定(その2).
            // 41.txt, 42.txt で, WA版 だったため, 修正.
            if(tn1 >= a0 && tn1 < a1){
                if(n1[0] == '0') ans = n1.substr(1);
                else             ans = n1;
                ok = true;
                break;
            }
        }
        
        // 見つかった場合.
        if(ok) break;
    }
    
    // 4. 出力.
    printf("%s\n", ans.c_str());
    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

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

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

// 解き直し.

// https://img.atcoder.jp/data/arc/057/editorial.pdf

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vs = vector<string>;

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

// 与えられた文字列を整数と見て, 0 ～ 9倍した値を計算.

// @param s: 正整数.

// @return: 計算結果.

vs multiplyBetweenZeroToNine(string s){

int sl = s.size();

vs ret;

// 0 ～ 9倍.

rep(i, 10){

string v;

int c = 0;

repr(j, sl - 1, 0){

string x = to_string((s[j] - '0') * i + c);

int xl = x.size();

if(xl == 1){

v.pub(x[0]);

c = 0;

}

if(xl == 2){

v.pub(x[1]);

c = x[0] - '0';

if(!j) v.pub(x[0]);

}

assert(xl >= 1 && xl <= 2);

}

reverse(all(v));

ret.pub(v);

}

// 返却.

return ret;

}

// 与えられた文字列を整数と見て, 乗算を行う.

// @param s: 正整数.

// @param t: 正整数.

// @return: 計算結果.

string sMultiply(string s, string t){

string ret;

int sl = s.size(), tl = t.size();

vs s09 = multiplyBetweenZeroToNine(s);

// 各桁単体で, 乗算.

vs tCalc;

repr(i, tl - 1, 0){

string v = s09[t[i] - '0'];

int vl = v.size();

string zb(tl - 1 - i, '0');

string zf(sl + tl - vl - zb.size(), '0');

v = zf + v + zb;

tCalc.pub(v);

}

// 集計.

ret = tCalc[0];

repx(i, 1, tl){

string v;

int c = 0;

repr(j, sl + tl - 1, 0){

string x = to_string((ret[j] - '0') + (tCalc[i][j] - '0') + c);

int xl = x.size();

if(xl == 1){

v.pub(x[0]);

c = 0;

}

if(xl == 2){

v.pub(x[1]);

c = x[0] - '0';

if(!j) v.pub(x[0]);

}

assert(xl >= 1 && xl <= 2);

}

reverse(all(v));

ret = v;

}

// 先頭が, '0' ならば削除.

if(ret[0] == '0') ret = ret.substr(1);

// 返却.

return ret;

}

// 与えられた文字列を整数と見て, 加算を行う.

// @param s: 正整数.

// @param t: 正整数.

// @return: 計算結果.

string sAdd(string s, string t){

int sl = s.size();

int tl = t.size();

int ml = max(sl, tl) + 1;

string zs(ml - sl, '0');

string zt(ml - tl, '0');

string ns = zs + s;

string nt = zt + t;

// 各桁を加算.

string ret;

int c = 0;

repr(j, ml - 1, 0){

string x = to_string((ns[j] - '0') + (nt[j] - '0') + c);

int xl = x.size();

if(xl == 1){

ret.pub(x[0]);

c = 0;

}

if(xl == 2){

ret.pub(x[1]);

c = x[0] - '0';

if(!j) ret.pub(x[0]);

}

assert(xl >= 1 && xl <= 2);

}

while(ret.size() < ml) ret.pub('0');

if(ret.back() == '0') ret.pob();

reverse(all(ret));

// 返却.

return ret;

}

int main(){

// 1. 入力情報.

char c[1010];

scanf("%s", c);

string s(c);

// ex.

// 20211225 を使って, 0 ～ 9倍した場合.

// 000000000

// 020211225

// 040422450

// 060633675

// 080844900

// 101056125

// 121267350

// 141478575

// 161689800

// 181901025

// vs x = multiplyBetweenZeroToNine("20211225");

// for(auto &p : x) printf("%s\n", p.c_str());

// ex.

// 2021 * 2022 -> 4086462 の計算.

// printf("%s\n", sMultiply("2021", "2022").c_str());

// 3456 * 789 -> 2726784 の計算.

// printf("%s\n", sMultiply("3456", "789").c_str());

// 20211225 * 20220101 -> 408673010833725 の計算.

// printf("%s\n", sMultiply("20211225", "20220101").c_str());

// 31622776601683793319 * 314159265358979323846264338327

// -> 9934588265796101234122867437613016024182958237313 の計算.

// printf("%s\n", sMultiply("31622776601683793319", "314159265358979323846264338327").c_str());

// 12 + 15 -> 27 の計算.

// printf("%s\n", sAdd("12", "15").c_str());

// 98765 + 4321 -> 103086 の計算.

// printf("%s\n", sAdd("98765", "4321").c_str());

// 12345 + 54321 -> 66666 の計算.

// printf("%s\n", sAdd("12345", "54321").c_str());

// 15249 + 86073 -> 101322 の計算.

// printf("%s\n", sAdd("15249", "86073").c_str());

// 2. 事前準備(解説通り).

// 2-1. A, A + 1 の二乗.

string a0 = sMultiply(s, s);

string s1 = sAdd(s, "1");

string a1 = sMultiply(s1, s1);

// 2-2. 桁数揃える('0' 埋め).

while(a0.size() < a1.size()) a0.insert(a0.begin(), '0');

assert(a0.size() == a1.size());

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

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

// 2-3. 偶数桁('0' 埋め).

int odd = 0;

if(a0.size() & 1){

a0.pub('0');

a1.pub('0');

odd++;

}

// 3. N を探索.

string ans;

rep(t, 101){

string z(t * 2, '0');

a0 = a0 + z;

a1 = a1 + z;

// printf("a0=%s a1=%s\n", a0.c_str(), a1.c_str());

// 先頭 d 桁.

bool ok = false;

int al = a0.size();

repex(d, 2 - odd, al, 2){

// N の候補.

string n0 = a0.substr(0, d);

string n1 = sAdd(n0, "1");

string zb0(al - n0.size(), '0');

string zb1(al - n1.size(), '0');

string tn0 = n0 + zb0;

string tn1 = n1 + zb1;

// printf("n0=%s tn0=%s n1=%s tn1=%s\n", n0.c_str(), tn0.c_str(), n1.c_str(), tn1.c_str());

// 判定(その1).

if(tn0 >= a0 && tn0 < a1){

if(n0[0] == '0') ans = n0.substr(1);

else ans = n0;

ok = true;

break;

}

// 判定(その2).

// 41.txt, 42.txt で, WA版だったため, 修正.

if(tn1 >= a0 && tn1 < a1){

if(n1[0] == '0') ans = n1.substr(1);

else ans = n1;

ok = true;

break;

}

// 見つかった場合.

if(ok) break;

}

// 4. 出力.

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

return 0;

}

[入力例]
1414

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

[入力例]
316

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

[入力例]
31415926535897932384626433

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

[入力例]
1

[出力例]
1

[入力例]
3

[出力例]
9

[入力例]
100

[出力例]
1

[入力例]
2021

[出力例]
40845

[入力例]
2022

[出力例]
409

[入力例]
99

[出力例]
99

[入力例]
6683666956608953246189934089371425990037946094722715577162854485114171268233408663920367919525867917

[出力例]
4467140398686638731498801480194475987696605386968501488168403774682433001741290717947510964261028998

[入力例]
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899

[出力例]
152415787751564791571474464067365843004074106033398993610227467007696607026298183353895046888649891435630676833646227616539860497650828260258961517027329730424343528139368390672370167350579

[入力例]
56454760053845953422243613732034661978800055038665136534301641951677146991773695469292399771680255459998392040285990743835137754965296688500005803009866189324487493777613680693035780473318184761620481

[出力例]
31871399327373207577472704494998710448088197344396620930404898037706068693506291937736503041850263469639551715557378903361075958031955071497686490040280520705238693309515154487338261200746958725239791

[入力例]
5030985070267740263115027271190705986153832806252199283818135658343911760033447528438356090831963749515642192222778158992357964886915352912770916696752489458734907596506669059112014213237908818248266413892743143702184963535643856058675237205734895902172738366271118432036164904274015935635597981889020986662605031457585676669570726216641146536677630591926962624207379097357282827038235920681465116560019296192894476569131920504537171187405241700357906257603185189570170461215268547458485135254509062615598792950132386202370545991251063114378044940875537316198682829867668500947754944791483746661309449266971859211017963674048038161991275399238985469713690851801674540489282852894424592325332966283742488093033014048498167054812727586882069887314428050471983311273700014340305985169563222074709353440669223258556837783409863227256251246385544267082251151042255428228250034097985711468506203960661635195964499105185027681543589318667566352625315455409013012408044382148509744504378719140423199692886798

[出力例]
2531081077725689943281083263649946991089389430395661783045309706682327086366686759119550266908076908048888398141892844269448607798118799328411388944231094892452828801792108255204346096146144511408088643188729086382797303495732920938560691922513266755811230804623244048521586809163931062307451839564879639445317223353348193124314992841665605489570325277908205983121238598869999100672593162539628132896674490295517419362184479426549621460581559019336355188990805781286118157245796832409174937820467452885388298207685649687735924480056535197241424775943097312410193168945421342844953491458459256445975307683735283733708876160777916694957419938320823744297629867416618404089020369735760515709069814498245548198348288144465271222988611869777200074659708550820687740586058954143829808016281997260443023002312795730757996699124322869306241909113286448861121065709687219327225250911272899341246791423034847110532457587336597234061948051001562170993059814600959225445159764614909515779704059142383952420223495

[入力例]

1414

[出力例]

※AtCoderテストケースより

[入力例]

316

[出力例]

※AtCoderテストケースより

[入力例]

31415926535897932384626433

[出力例]

9869604401089358618834491

※AtCoderテストケースより

[入力例]

[出力例]

[入力例]

[出力例]

[入力例]

100

[出力例]

[入力例]

2021

[出力例]

40845

[入力例]

2022

[出力例]

409

[入力例]

[出力例]

[入力例]

6683666956608953246189934089371425990037946094722715577162854485114171268233408663920367919525867917

[出力例]

4467140398686638731498801480194475987696605386968501488168403774682433001741290717947510964261028998

[入力例]

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899

[出力例]

152415787751564791571474464067365843004074106033398993610227467007696607026298183353895046888649891435630676833646227616539860497650828260258961517027329730424343528139368390672370167350579

[入力例]

56454760053845953422243613732034661978800055038665136534301641951677146991773695469292399771680255459998392040285990743835137754965296688500005803009866189324487493777613680693035780473318184761620481

[出力例]

31871399327373207577472704494998710448088197344396620930404898037706068693506291937736503041850263469639551715557378903361075958031955071497686490040280520705238693309515154487338261200746958725239791

[入力例]

5030985070267740263115027271190705986153832806252199283818135658343911760033447528438356090831963749515642192222778158992357964886915352912770916696752489458734907596506669059112014213237908818248266413892743143702184963535643856058675237205734895902172738366271118432036164904274015935635597981889020986662605031457585676669570726216641146536677630591926962624207379097357282827038235920681465116560019296192894476569131920504537171187405241700357906257603185189570170461215268547458485135254509062615598792950132386202370545991251063114378044940875537316198682829867668500947754944791483746661309449266971859211017963674048038161991275399238985469713690851801674540489282852894424592325332966283742488093033014048498167054812727586882069887314428050471983311273700014340305985169563222074709353440669223258556837783409863227256251246385544267082251151042255428228250034097985711468506203960661635195964499105185027681543589318667566352625315455409013012408044382148509744504378719140423199692886798

[出力例]

2531081077725689943281083263649946991089389430395661783045309706682327086366686759119550266908076908048888398141892844269448607798118799328411388944231094892452828801792108255204346096146144511408088643188729086382797303495732920938560691922513266755811230804623244048521586809163931062307451839564879639445317223353348193124314992841665605489570325277908205983121238598869999100672593162539628132896674490295517419362184479426549621460581559019336355188990805781286118157245796832409174937820467452885388298207685649687735924480056535197241424775943097312410193168945421342844953491458459256445975307683735283733708876160777916694957419938320823744297629867416618404089020369735760515709069814498245548198348288144465271222988611869777200074659708550820687740586058954143829808016281997260443023002312795730757996699124322869306241909113286448861121065709687219327225250911272899341246791423034847110532457587336597234061948051001562170993059814600959225445159764614909515779704059142383952420223495

■参照サイト
AtCoder Regular Contest 057

C++の練習を兼ねて, AtCoder Regular Contest 057 の 問題C (2乗根) を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 057 の問題C (2乗根) を解いてみた.

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