個人用メモ帳

2021年12月25日2021年12月25日

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

2021年12月24日2021年12月24日

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

C++の練習を兼ねて, AtCoder Regular Contest 036 の問題C (偶然ジェネレータ) を解いてみた.

■感想.
1. 問題Cは, 方針が見えなかったので, 解説を参考に, AC版に到達できた.
2. 苦手な動的計画法の訓練を積めたので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://www.slideshare.net/chokudai/arc036
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#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--)
const LL MOD = 1e9 + 7;
LL dp[303][303][303];

int main(){
    
    // 1. 入力情報.
    int N, K;
    char c[303];
    scanf("%d %d %s", &N, &K, c);
    
    // 2. 初期化(※0文字目(空文字)を, 1個と見る).
    dp[0][0][0] = 1;
    
    // 3. dp更新.
    rep(i, N){
        // 3-1. (0 の 個数) - (1 の 個数).
        int z = 0, o = 0, q = 0;
        bool ok = true;
        repr(j, i, 0){
            if(c[j] == '0') z++;
            if(c[j] == '1') o++;
            if(c[j] == '?') q++;
            if(abs(z - o) > K + q) ok = false;
        }
        
        // 3-2. 矛盾している場合.
        if(!ok) break;
        
        // 3-3. i文字目をベースに, (i - 1)文字目までの結果を反映.
        rep(j, K + 1){
            rep(k, K + 1){
                // '0' or '?' の 場合.
                if(c[i] == '0' || c[i] == '?'){
                    int nk = max(0, k - 1);
                    dp[i + 1][j + 1][nk] += dp[i][j][k];
                    dp[i + 1][j + 1][nk] %= MOD;
                }
                
                // '1' or '?' の 場合.
                if(c[i] == '1' || c[i] == '?'){
                    int nj = max(0, j - 1);
                    dp[i + 1][nj][k + 1] += dp[i][j][k];
                    dp[i + 1][nj][k + 1] %= MOD;
                }
            }
        }
    }
    
    // 4. 集計.
    LL ans = 0;
    rep(j, K + 1){
        rep(k, K + 1){
            ans += dp[N][j][k];
            ans %= MOD;
        }
    }
    
    // 5. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://www.slideshare.net/chokudai/arc036

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

const LL MOD = 1e9 + 7;

LL dp[303][303][303];

int main(){

// 1. 入力情報.

int N, K;

char c[303];

scanf("%d %d %s", &N, &K, c);

// 2. 初期化(※0文字目(空文字)を, 1個と見る).

dp[0][0][0] = 1;

// 3. dp更新.

rep(i, N){

// 3-1. (0 の個数) - (1 の個数).

int z = 0, o = 0, q = 0;

bool ok = true;

repr(j, i, 0){

if(c[j] == '0') z++;

if(c[j] == '1') o++;

if(c[j] == '?') q++;

if(abs(z - o) > K + q) ok = false;

}

// 3-2. 矛盾している場合.

if(!ok) break;

// 3-3. i文字目をベースに, (i - 1)文字目までの結果を反映.

rep(j, K + 1){

rep(k, K + 1){

// '0' or '?' の場合.

if(c[i] == '0' || c[i] == '?'){

int nk = max(0, k - 1);

dp[i + 1][j + 1][nk] += dp[i][j][k];

dp[i + 1][j + 1][nk] %= MOD;

}

// '1' or '?' の場合.

if(c[i] == '1' || c[i] == '?'){

int nj = max(0, j - 1);

dp[i + 1][nj][k + 1] += dp[i][j][k];

dp[i + 1][nj][k + 1] %= MOD;

}

// 4. 集計.

LL ans = 0;

rep(j, K + 1){

rep(k, K + 1){

ans += dp[N][j][k];

ans %= MOD;

}

// 5. 出力.

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

return 0;

}

[入力例]
9 4
?011?1110

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

[入力例]
9 3
?011?1110

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

[入力例]
9 1
???1?????

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

[入力例]
12 5
???0??1??11?

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

[入力例]
1 1
?

[出力例]
2

[入力例]
2 1
10

[出力例]
1

[入力例]
5 2
?101?

[出力例]
3

[入力例]
7 3
?101??1

[出力例]
6

[入力例]
30 2
?0?11?1?????0?1?01001?101?0?00

[出力例]
0

[入力例]
50 5
1?00010110?1?001?000?0?0111101100??01?10101?1???0?

[出力例]
920

[入力例]
100 5
0?0110?1100????11?10???1?0011?0?10000?1???000??000?11?1???11110?0?1?11?0?011??010011011?1000?10?0010

[出力例]
333080

[入力例]
200 7
?0?11?1?????0?1?01001?101?0?000?001?00?1011??0?10?00?1111010?1?0???10?11?1?0011?00??0100111??????1??01?01?0100011??11?00?????00110?0?1?01?010??10010?0000?1?01??11?0?0??0?10??0???101?1?001??10?0???????

[出力例]
629811174

[入力例]
300 10
1??1?1???????1100101?1100100?1???110?1?11?0011?100?111????10?1110??11??11110001011?11?0?11?0010110?1?0?00?0?01??0?1??000??0000101000?0?0?1?0011??11101?1101010?1101??00?0?0?00??1???1?11?01100???0?11?000??1???01???00?1110?0?11??1?0100?1?0101??11?????0?100?111?001?110?100111?00100?0?10?011111000?00001?

[出力例]
704124254

[入力例]

9 4

?011?1110

[出力例]

※AtCoderのテストケースより

[入力例]

9 3

?011?1110

[出力例]

※AtCoderのテストケースより

[入力例]

9 1

???1?????

[出力例]

※AtCoderのテストケースより

[入力例]

12 5

???0??1??11?

[出力例]

172

※AtCoderのテストケースより

[入力例]

1 1

[出力例]

[入力例]

2 1

[出力例]

[入力例]

5 2

?101?

[出力例]

[入力例]

7 3

?101??1

[出力例]

[入力例]

30 2

?0?11?1?????0?1?01001?101?0?00

[出力例]

[入力例]

50 5

1?00010110?1?001?000?0?0111101100??01?10101?1???0?

[出力例]

920

[入力例]

100 5

0?0110?1100????11?10???1?0011?0?10000?1???000??000?11?1???11110?0?1?11?0?011??010011011?1000?10?0010

[出力例]

333080

[入力例]

200 7

?0?11?1?????0?1?01001?101?0?000?001?00?1011??0?10?00?1111010?1?0???10?11?1?0011?00??0100111??????1??01?01?0100011??11?00?????00110?0?1?01?010??10010?0000?1?01??11?0?0??0?10??0???101?1?001??10?0???????

[出力例]

629811174

[入力例]

300 10

1??1?1???????1100101?1100100?1???110?1?11?0011?100?111????10?1110??11??11110001011?11?0?11?0010110?1?0?00?0?01??0?1??000??0000101000?0?0?1?0011??11101?1101010?1101??00?0?0?00??1???1?11?01100???0?11?000??1???01???00?1110?0?11??1?0100?1?0101??11?????0?100?111?001?110?100111?00100?0?10?011111000?00001?

[出力例]

704124254

■参照サイト
AtCoder Regular Contest 036

2021年12月21日2021年12月21日

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

C++の練習を兼ねて, AtCoder Regular Contest 045 の問題C (エックスオア多橋君) を解いてみた.

■感想.
1. 問題Cは, 方針が見えなかったので, 解説を参考に, AC版に到達できた.
2. 個人的には, 深さ優先探索の訓練を積めたので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://www.slideshare.net/chokudai/arc045
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#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 memo[101010];

struct edge{
    int n;
    LL c;
};

vector<edge> G[101010];

int main(){
    
    // 1. 入力情報.
    int N;
    LL X;
    scanf("%d %lld", &N, &X);
    rep(i, N - 1){
        int x, y;
        LL c;
        scanf("%d %d %lld", &x, &y, &c);
        x--, y--;
        G[x].pb(edge{y, c});
        G[y].pb(edge{x, c});
    }
    
    // 2. dfs.
    // https://ja.wikipedia.org/wiki/深さ優先探索
    map<LL, LL> m;
    LL ans = 0;
    auto dfs = [&](auto&& self, int c, int b, LL cXor) -> void{
        // 2-1. 訪問済フラグ設定.
        memo[c] = 1;
        
        // 2-2. 数え上げ.
        ans += m[cXor ^ X];
        
        // 2-3. 根 から 頂点 c までの単純パス の XOR値 の 出現回数 を 保存.
        m[cXor]++;
        
        // 2-4. 次へ.
        for(auto &e : G[c]) if(!memo[e.n]) self(self, e.n, c, cXor ^ e.c);
    };
    dfs(dfs, 0, -1, 0LL);
    
    // 3. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://www.slideshare.net/chokudai/arc045

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

#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 memo[101010];

struct edge{

int n;

LL c;

};

vector<edge> G[101010];

int main(){

// 1. 入力情報.

int N;

LL X;

scanf("%d %lld", &N, &X);

rep(i, N - 1){

int x, y;

LL c;

scanf("%d %d %lld", &x, &y, &c);

x--, y--;

G[x].pb(edge{y, c});

G[y].pb(edge{x, c});

}

// 2. dfs.

// https://ja.wikipedia.org/wiki/深さ優先探索

map<LL, LL> m;

LL ans = 0;

auto dfs = [&](auto&& self, int c, int b, LL cXor) -> void{

// 2-1. 訪問済フラグ設定.

memo[c] = 1;

// 2-2. 数え上げ.

ans += m[cXor ^ X];

// 2-3. 根から頂点 c までの単純パスの XOR値の出現回数を保存.

m[cXor]++;

// 2-4. 次へ.

for(auto &e : G[c]) if(!memo[e.n]) self(self, e.n, c, cXor ^ e.c);

};

dfs(dfs, 0, -1, 0LL);

// 3. 出力.

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

return 0;

}

[入力例]
6 7
1 2 5
2 3 3
3 4 6
2 5 2
5 6 7

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

[入力例]
6 3
1 2 1
2 3 3
3 4 2
4 5 3
4 6 1

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

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

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

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

[出力例]
3

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

[出力例]
5

[入力例]
20 21
6 5 16
6 10 27
5 4 21
5 11 18
5 3 9
1 4 3
2 4 8
3 7 1
8 3 11
8 12 10
8 13 23
7 15 19
7 9 18
9 20 12
14 9 25
1 16 13
17 1 22
16 18 27
19 16 12

[出力例]
11

[入力例]

6 7

1 2 5

2 3 3

3 4 6

2 5 2

5 6 7

[出力例]

※AtCoderテストケースより

[入力例]

6 3

1 2 1

2 3 3

3 4 2

4 5 3

4 6 1

[出力例]

※AtCoderテストケースより

[入力例]

10 1

9 10 1

6 10 1

5 2 1

8 6 1

4 5 1

7 6 0

3 8 0

3 1 1

8 2 0

[出力例]

※AtCoderテストケースより

[入力例]

3 0

1 2 0

1 3 0

[出力例]

[入力例]

10 5

1 4 3

1 5 1

9 5 4

5 10 1

3 1 5

2 3 9

2 6 2

2 7 6

7 8 5

[出力例]

[入力例]

20 21

6 5 16

6 10 27

5 4 21

5 11 18

5 3 9

1 4 3

2 4 8

3 7 1

8 3 11

8 12 10

8 13 23

7 15 19

7 9 18

9 20 12

14 9 25

1 16 13

17 1 22

16 18 27

19 16 12

[出力例]

■参照サイト
AtCoder Regular Contest 045

2021年12月20日

C++ の動作確認をしてみた（５９９）

C++の練習を兼ねて, AtCoder Beginner Contest 232 の問題C (Graph Isomorphism) ～問題D (Weak Takahashi) を解いてみた.

■感想.
1. 問題C, Dは, 方針を絞り込めたので, AC版に到達できたと思う.
2. 苦手な動的計画法の訓練を積めたので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

本家のサイト AtCoder Beginner Contest 232 解説の各リンクをご覧下さい.

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;
using vp = vector<P>;
using vi = vector<int>;
#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
#define a first
#define b second
#define all(x) x.begin(), x.end()

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    vp v1, v2;
    rep(i, M){
        int a, b;
        scanf("%d %d", &a, &b);
        a--, b--;
        v1.pb({a, b});
    }
    rep(i, M){
        int c, d;
        scanf("%d %d", &c, &d);
        c--, d--;
        v2.pb({c, d});
    }
    
    // 2. sort.
    sort(all(v1));
    
    // 3. 同じ形か？
    vi z(N);
    iota(all(z), 0);
    bool ok = false;
    do{
        // 3-1. ある数列を対応させる.
        vp v;
        rep(i, M){
            int zc = z[v2[i].a];
            int zd = z[v2[i].b];
            if(zc > zd) swap(zc, zd);
            v.pb({zc, zd});
        }
        
        // 3-2. sort.
        sort(all(v));
        
        // 3-3. 比較.
        if(v == v1){
            ok = true;
            break;
        }
    }while(next_permutation(all(z)));
    
    // 4. 出力.
    printf("%s\n", ok ? "Yes" : "No");
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using P = pair<int, int>;

using vp = vector<P>;

using vi = vector<int>;

#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

#define a first

#define b second

#define all(x) x.begin(), x.end()

int main(){

// 1. 入力情報.

int N, M;

scanf("%d %d", &N, &M);

vp v1, v2;

rep(i, M){

int a, b;

scanf("%d %d", &a, &b);

a--, b--;

v1.pb({a, b});

}

rep(i, M){

int c, d;

scanf("%d %d", &c, &d);

c--, d--;

v2.pb({c, d});

}

// 2. sort.

sort(all(v1));

// 3. 同じ形か？

vi z(N);

iota(all(z), 0);

bool ok = false;

do{

// 3-1. ある数列を対応させる.

vp v;

rep(i, M){

int zc = z[v2[i].a];

int zd = z[v2[i].b];

if(zc > zd) swap(zc, zd);

v.pb({zc, zd});

}

// 3-2. sort.

sort(all(v));

// 3-3. 比較.

if(v == v1){

ok = true;

break;

}

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

// 4. 出力.

printf("%s\n", ok ? "Yes" : "No");

return 0;

}

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

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

[入力例]
5 6
1 2
1 3
1 4
3 4
3 5
4 5
1 2
1 3
1 4
1 5
3 5
4 5

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

[入力例]
8 0

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

[入力例]
5 6
1 2
1 4
2 4
1 3
1 5
3 5
1 2
2 3
2 5
3 5
3 4
4 5

[出力例]
No

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

[出力例]
Yes

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

[出力例]
Yes
※ 整数 N が, 問題文の制約条件から範囲外であるケース.

100

101

102

103

104

105

106

107

108

109

110

111

112

113

[入力例]

4 4

1 2

1 3

1 4

3 4

1 3

1 4

2 3

3 4

[出力例]

Yes

※AtCoderテストケースより

[入力例]

5 6

1 2

1 3

1 4

3 4

3 5

4 5

1 2

1 3

1 4

1 5

3 5

4 5

[出力例]

※AtCoderテストケースより

[入力例]

8 0

[出力例]

Yes

※AtCoderテストケースより

[入力例]

5 6

1 2

1 4

2 4

1 3

1 5

3 5

1 2

2 3

2 5

3 5

3 4

4 5

[出力例]

[入力例]

8 9

1 4

1 3

1 2

4 5

3 5

3 4

5 8

3 6

3 7

1 2

1 3

1 9

7 8

2 8

2 3

3 4

2 5

2 6

[出力例]

Yes

[入力例]

10 12

1 2

1 3

1 4

2 5

3 5

3 6

4 6

4 7

2 7

5 9

7 10

6 8

1 2

1 6

1 7

2 3

2 10

7 10

4 7

4 8

8 10

8 9

5 6

4 6

[出力例]

Yes

※ 整数 N が, 問題文の制約条件から範囲外であるケース.

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

// 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--)
int board[111][111], dp[111][111];

int main(){
    
    // 1. 入力情報.
    int H, W;
    scanf("%d %d", &H, &W);
    rep(i, H){
        char c[111];
        scanf("%s", c);
        rep(j, W) if(c[j] == '.') board[i][j] = 1;
    }
    
    // 2. dp更新.
    int ans = 0;
    dp[0][0] = 1;
    rep(i, H){
        rep(j, W){
            // 移動可能な場合.
            if(board[i][j] && dp[i][j]){
                // 下方向.
                if(i + 1 < H && board[i + 1][j]) dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + 1);
                
                // 右方向.
                if(j + 1 < W && board[i][j + 1]) dp[i][j + 1] = max(dp[i][j + 1], dp[i][j] + 1);
            }
            
            // 最大値更新.
            ans = max(ans, dp[i][j]);
        }
    }
    
    // 3. 出力.
    printf("%d\n", ans);
    return 0;
    
}

// 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--)

int board[111][111], dp[111][111];

int main(){

// 1. 入力情報.

int H, W;

scanf("%d %d", &H, &W);

rep(i, H){

char c[111];

scanf("%s", c);

rep(j, W) if(c[j] == '.') board[i][j] = 1;

}

// 2. dp更新.

int ans = 0;

dp[0][0] = 1;

rep(i, H){

rep(j, W){

// 移動可能な場合.

if(board[i][j] && dp[i][j]){

// 下方向.

if(i + 1 < H && board[i + 1][j]) dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + 1);

// 右方向.

if(j + 1 < W && board[i][j + 1]) dp[i][j + 1] = max(dp[i][j + 1], dp[i][j] + 1);

}

// 最大値更新.

ans = max(ans, dp[i][j]);

}

// 3. 出力.

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

return 0;

}

[入力例]
3 4
.#..
..#.
..##

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

[入力例]
1 1
.

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

[入力例]
5 5
.....
.....
.....
.....
.....

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

[入力例]
32 32
..##..##..##.....#...####.##.##.
#...#.#.##.#.##..#####.#.##.#..#
##.#.##.###..##########.#.##.#..
##...#.#..######..#.###.####...#
.......########.####...##.#.####
..#..###...####.....#####...##.#
#..#.....#.#..###.#.#.#.....##..
..#.#.#.##..#.####..##.#.##.###.
#....#...#.#.......##.###.##.#.#
..#...#...##.#..##.#.#...###..##
.#..#.#.####.#.#.#...###.##.#.#.
.....##.#######...##.#.##.#.##..
#.##..........###.##.##...#..###
#.##.###...#####..###.#...##....
###...##..##..####.#..#....#.##.
.##.####..#..#.##.#..#.##.#.##.#
##..###...##...#.#.##...##......
..#..#.#.....#..##..#.####...#..
.#.####....#...##..#..#.#.#.##..
###.##..##.##.###.#...#.##.....#
...#..#.#..#.#..#...##.#.#.###.#
...##..#####.#..###.##.####..###
.#.#####.#.###.####...#.....####
###....###.#.##..##.##..#..#...#
..#.##..#..#.#...###.#..#.######
###.#####.##.###...##...#.#####.
#.#.##...##.#...#..####.....##.#
.##..##.##...##...##.#..##.....#
#...##.##.#.#.##..#..##.##.#...#
#.#####.##.#######.#.....##...#.
#..##.#####.###.....#####.#.#..#
##...#####.##.....####.###..#...

[出力例]
33

[入力例]
50 60
.#.###.##.##.###..#..####..##...##......##.#.##.#.#..##.#.##
..##..##.###...####..#.###..#.#.#.###...##..#.#.#....#.#.###
..#.###..#####.##.##..#.###.###..####..#...##..####.#.#..###
#.....#.#..###.###.#.#...#...#.....#...#.#######...##.......
#..#.#..####..##.....##.#####...#....#....##..#.##.#...#..##
.....####.#.##....###..#.#...###.###.##..#####..###.##.#...#
#..#..#....#..#.#.##.###..#.#.#########...##...##..#...#.###
.....##.#.#.#..#.##..##.#....#.#.##..#.....###.#############
##.....###.##.#...#####.......##.#.#..##.....####.##..##..##
######.##.###....#.#..##...###.....#..#.###.#.#.......#.#.#.
....#.........#.##..####..#.##....########...#..######...###
###.#.##..#..#..#....#.####..#....##....##.#..#..##..#...#..
...#..###..#####..#.##.##.#..###.#.##....#..###.##.##.##....
#..#.#..##.##.#.#...#..#..###.#.####...#....#..#..####..###.
#.###.####.......##.###...##....#.###.#.##.##.#.#....#.#####
##.##.#.#..#.#.#.###...#.#...###....##....#####.#..#....###.
.##.##.....#...####.#..#...#..#.##......#..#.#.##.#.#.#.....
#..#.###.#.###..#...####..#.##.###...#.#######..#..#...#...#
.###.#.#.#..###.##.....##.#..#....##....#.#.###.##.#....###.
#..#.#.#...#.##..####..####.#.#..###..####.#.#.##...###...#.
...#.###...##..###...#...##.##...#..#.....#########..###.###
...###.#....##.#.#.#..#...#.#...####.....#..#.####.#...#.###
#..##.####....#.#..#.#.##.##.####..###########.###..#######.
.....#..####....##.#...#..#..###...#.##..##..#.#.####.#..###
..#......#..###.#.....######.##.####......#..#.##...##.#....
#..#.##.##.##.......##.#..##.#..####...#.##.....#...#...#...
.#.###....#...#....#######.#....####.#...#.#.#####.###.#...#
#.##.##.##.##..#..#..##.#.#.#...##....#.#.#####.#.##...##..#
##...#.#..##...#......#######.#.#..##.####.#.#..#....#..##.#
....###..#.#...#.##..####....#..#..##.#.#####.##.......###.#
#.#..######.###..###...#....##..#.#.####.####...##.#...##.#.
...####.###.#.#..####...#..#....##....#...##.#...##.#.#.....
####.#.#...##.##.#.###.#.##..#...#.#...#####..#.#.###..##.##
.##.#...###.###...###...##...#.#.#..#..#...###.#..#..##...##
#.##.#.....###.#####..#...##..###.#.##..#..####.##.##..#.#..
#.#..#..#.###.##.....#.......###..#.##...##.#.#...###.##..#.
.##..#........##.###..#.#.#...#..######.####.###...#....#...
.#.#.#..##.###.###..#..##.....##.#....#.#..##..#####..##...#
#..##.#...#.#..######....#.##.##....##.#..#..####...##.##.#.
#.##...#.###......#.##.######...#..#.#..##.#.#.#....####...#
........#..#.##..####.....#.......####...#.##.###.####....#.
...######.###.########..#.#....######....###.##...##..#.##.#
##....#.#.#..#.#.##.###.#..#..###.#.......#..#...#.##.##....
.#.###.#.##.#######.##.....#...##..#..#..#..#..###...##.#...
..#...#.###....##.####...##....#...####.#.###.#.##....#####.
##..#..#.#..#.#####......#.###.......##..#...###...##......#
..#.#...#..#####...#####.##.....#.#.########.#.#.##..##..#.#
#..##.######...####.#######..###....###...#..###############
.......####.##.#..#....###.#.##..##...#####.####.###..#.#...
...#.#..#.###......#...#......#...#....###......########.#.#

[出力例]
88

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

[入力例]

3 4

.#..

..#.

..##

[出力例]

※AtCoderテストケースより

[入力例]

1 1

[出力例]

※AtCoderテストケースより

[入力例]

5 5

.....

[出力例]

※AtCoderテストケースより

[入力例]

32 32

..##..##..##.....#...####.##.##.

#...#.#.##.#.##..#####.#.##.#..#

##.#.##.###..##########.#.##.#..

##...#.#..######..#.###.####...#

.......########.####...##.#.####

..#..###...####.....#####...##.#

#..#.....#.#..###.#.#.#.....##..

..#.#.#.##..#.####..##.#.##.###.

#....#...#.#.......##.###.##.#.#

..#...#...##.#..##.#.#...###..##

.#..#.#.####.#.#.#...###.##.#.#.

.....##.#######...##.#.##.#.##..

#.##..........###.##.##...#..###

#.##.###...#####..###.#...##....

###...##..##..####.#..#....#.##.

.##.####..#..#.##.#..#.##.#.##.#

##..###...##...#.#.##...##......

..#..#.#.....#..##..#.####...#..

.#.####....#...##..#..#.#.#.##..

###.##..##.##.###.#...#.##.....#

...#..#.#..#.#..#...##.#.#.###.#

...##..#####.#..###.##.####..###

.#.#####.#.###.####...#.....####

###....###.#.##..##.##..#..#...#

..#.##..#..#.#...###.#..#.######

###.#####.##.###...##...#.#####.

#.#.##...##.#...#..####.....##.#

.##..##.##...##...##.#..##.....#

#...##.##.#.#.##..#..##.##.#...#

#.#####.##.#######.#.....##...#.

#..##.#####.###.....#####.#.#..#

##...#####.##.....####.###..#...

[出力例]

[入力例]

50 60

.#.###.##.##.###..#..####..##...##......##.#.##.#.#..##.#.##

..##..##.###...####..#.###..#.#.#.###...##..#.#.#....#.#.###

..#.###..#####.##.##..#.###.###..####..#...##..####.#.#..###

#.....#.#..###.###.#.#...#...#.....#...#.#######...##.......

#..#.#..####..##.....##.#####...#....#....##..#.##.#...#..##

.....####.#.##....###..#.#...###.###.##..#####..###.##.#...#

#..#..#....#..#.#.##.###..#.#.#########...##...##..#...#.###

.....##.#.#.#..#.##..##.#....#.#.##..#.....###.#############

##.....###.##.#...#####.......##.#.#..##.....####.##..##..##

######.##.###....#.#..##...###.....#..#.###.#.#.......#.#.#.

....#.........#.##..####..#.##....########...#..######...###

###.#.##..#..#..#....#.####..#....##....##.#..#..##..#...#..

...#..###..#####..#.##.##.#..###.#.##....#..###.##.##.##....

#..#.#..##.##.#.#...#..#..###.#.####...#....#..#..####..###.

#.###.####.......##.###...##....#.###.#.##.##.#.#....#.#####

##.##.#.#..#.#.#.###...#.#...###....##....#####.#..#....###.

.##.##.....#...####.#..#...#..#.##......#..#.#.##.#.#.#.....

#..#.###.#.###..#...####..#.##.###...#.#######..#..#...#...#

.###.#.#.#..###.##.....##.#..#....##....#.#.###.##.#....###.

#..#.#.#...#.##..####..####.#.#..###..####.#.#.##...###...#.

...#.###...##..###...#...##.##...#..#.....#########..###.###

...###.#....##.#.#.#..#...#.#...####.....#..#.####.#...#.###

#..##.####....#.#..#.#.##.##.####..###########.###..#######.

.....#..####....##.#...#..#..###...#.##..##..#.#.####.#..###

..#......#..###.#.....######.##.####......#..#.##...##.#....

#..#.##.##.##.......##.#..##.#..####...#.##.....#...#...#...

.#.###....#...#....#######.#....####.#...#.#.#####.###.#...#

#.##.##.##.##..#..#..##.#.#.#...##....#.#.#####.#.##...##..#

##...#.#..##...#......#######.#.#..##.####.#.#..#....#..##.#

....###..#.#...#.##..####....#..#..##.#.#####.##.......###.#

#.#..######.###..###...#....##..#.#.####.####...##.#...##.#.

...####.###.#.#..####...#..#....##....#...##.#...##.#.#.....

####.#.#...##.##.#.###.#.##..#...#.#...#####..#.#.###..##.##

.##.#...###.###...###...##...#.#.#..#..#...###.#..#..##...##

#.##.#.....###.#####..#...##..###.#.##..#..####.##.##..#.#..

#.#..#..#.###.##.....#.......###..#.##...##.#.#...###.##..#.

.##..#........##.###..#.#.#...#..######.####.###...#....#...

.#.#.#..##.###.###..#..##.....##.#....#.#..##..#####..##...#

#..##.#...#.#..######....#.##.##....##.#..#..####...##.##.#.

#.##...#.###......#.##.######...#..#.#..##.#.#.#....####...#

........#..#.##..####.....#.......####...#.##.###.####....#.

...######.###.########..#.#....######....###.##...##..#.##.#

##....#.#.#..#.#.##.###.#..#..###.#.......#..#...#.##.##....

.#.###.#.##.#######.##.....#...##..#..#..#..#..###...##.#...

..#...#.###....##.####...##....#...####.#.###.#.##....#####.

##..#..#.#..#.#####......#.###.......##..#...###...##......#

..#.#...#..#####...#####.##.....#.#.########.#.#.##..##..#.#

#..##.######...####.#######..###....###...#..###############

.......####.##.#..#....###.#.##..##...#####.####.###..#.#...

...#.#..#.###......#...#......#...#....###......########.#.#

[出力例]

■参照サイト
M-SOLUTIONS プロコンオープン2021(AtCoder Beginner Contest 232)

2021年12月19日2021年12月19日

C++ の動作確認をしてみた（５９８）

C++の練習を兼ねて, AtCoder Regular Contest 056 の問題C (部門分け) を解いてみた.

■感想.
1. 問題Cは, 方針が見えなかったので, 解説を参考にして, AC版に到達できたと思う.
2. 実行時間を改善するため, 過去問(AtCoder Beginner Contest 187 (F – Close Group)) の解説プログラムを参考に, 一部改変して, 実装した.
3. 苦手な動的計画法の訓練を積めたので, 非常に良かったと思う.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/data/arc/056/editorial.pdf
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vi = vector<int>;
#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
LL wSum[1 << 17], w[22][22], dp[1 << 17];

int main(){
    
    // 1. 入力情報.
    int N, K;
    scanf("%d %d", &N, &K);
    rep(i, N) rep(j, N) scanf("%lld", &w[i][j]);
    
    // 2. 部分集合ごとの重みの総和.
    rep(i, 1 << N){
        vi s;
        rep(j, N) if(i & (1 << (N - 1 - j))) s.pb(j);
        for(auto &p : s) for(auto &q : s) wSum[i] += w[p][q];
        wSum[i] /= 2; // 重複カウントの除外.
    }
    
    // 3. dp更新.
    // 以下の実装は, N = 17 で, 5416[ms] などの時間が, かかってしまう(TLE版).
    /*
    repx(s, 1, 1 << N){
        // 3-1. 部分集合 S の index.
        vi sIndex;
        rep(i, N) if(s & (1 << (N - 1 - i))) sIndex.pb(i);
        
        // 3-2. dp[S] = dp[S - T] + K - (S - T と T 間 の 辺の重みの総和) を 計算.
        int l = sIndex.size();
        rep(i, 1 << l){
            // 部分集合 T.
            int t = 0;
            rep(j, l) if(i & (1 << (l - 1 - j))) t += (1 << (N - 1 - sIndex[j]));
            
            // dp計算式を実行.
            dp[s] = max(dp[s], dp[s - t] + K - (wSum[s] - wSum[s - t] - wSum[t]));
        }
    }
    */
    
    // 4. dp更新(修正版).
    // 
    // 過去問参照(AtCoder Beginner Contest 187 F - Close Group).
    // https://atcoder.jp/contests/abc187/editorial/488
    // https://atcoder.jp/contests/abc187/submissions/19205798
    // -> 部分集合 S と T が 同じケースを含めるため, 一部改変(for(int j = i; --j &= i; ) の 部分).
    // 以下の実装は, N = 17 で, 267[ms] 程度の実行時間 に 改善.
    repx(s, 1, 1 << N){
        for(int t = s; t &= s; t--) dp[s] = max(dp[s], dp[s - t] + K - (wSum[s] - wSum[s - t] - wSum[t]));
    }
    
    // 5. 出力.
    printf("%lld\n", dp[(1 << N) - 1]);
    return 0;
    
}

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vi = vector<int>;

#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

LL wSum[1 << 17], w[22][22], dp[1 << 17];

int main(){

// 1. 入力情報.

int N, K;

scanf("%d %d", &N, &K);

rep(i, N) rep(j, N) scanf("%lld", &w[i][j]);

// 2. 部分集合ごとの重みの総和.

rep(i, 1 << N){

vi s;

rep(j, N) if(i & (1 << (N - 1 - j))) s.pb(j);

for(auto &p : s) for(auto &q : s) wSum[i] += w[p][q];

wSum[i] /= 2; // 重複カウントの除外.

}

// 3. dp更新.

// 以下の実装は, N = 17 で, 5416[ms] などの時間が, かかってしまう(TLE版).

repx(s, 1, 1 << N){

// 3-1. 部分集合 S の index.

vi sIndex;

rep(i, N) if(s & (1 << (N - 1 - i))) sIndex.pb(i);

// 3-2. dp[S] = dp[S - T] + K - (S - T と T 間の辺の重みの総和) を計算.

int l = sIndex.size();

rep(i, 1 << l){

// 部分集合 T.

int t = 0;

rep(j, l) if(i & (1 << (l - 1 - j))) t += (1 << (N - 1 - sIndex[j]));

// dp計算式を実行.

dp[s] = max(dp[s], dp[s - t] + K - (wSum[s] - wSum[s - t] - wSum[t]));

}

// 4. dp更新(修正版).

// 過去問参照(AtCoder Beginner Contest 187 F - Close Group).

// https://atcoder.jp/contests/abc187/editorial/488

// https://atcoder.jp/contests/abc187/submissions/19205798

// -> 部分集合 S と T が同じケースを含めるため, 一部改変(for(int j = i; --j &= i; ) の部分).

// 以下の実装は, N = 17 で, 267[ms] 程度の実行時間に改善.

repx(s, 1, 1 << N){

for(int t = s; t &= s; t--) dp[s] = max(dp[s], dp[s - t] + K - (wSum[s] - wSum[s - t] - wSum[t]));

}

// 5. 出力.

printf("%lld\n", dp[(1 << N) - 1]);

return 0;

}

[入力例]
3 3
0 1 5
1 0 1
5 1 0

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

[入力例]
4 8
0 2 3 5
2 0 1 2
3 1 0 8
5 2 8 0

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

[入力例]
5 10
0 10 1 2 1
10 0 1 2 1
1 1 0 6 7
2 2 6 0 8
1 1 7 8 0

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

[入力例]
7 23
0 3 6 1 4 3 8
3 0 7 9 9 6 10
6 7 0 10 7 1 10
1 9 10 0 5 3 8
4 9 7 5 0 4 2
3 6 1 3 4 0 5
8 10 10 8 2 5 0

[出力例]
40

[入力例]
10 50
0 5 2 4 8 8 2 9 1 10
5 0 7 1 7 6 10 1 4 2
2 7 0 10 5 3 8 10 5 10
4 1 10 0 10 5 3 3 7 8
8 7 5 10 0 7 6 9 2 9
8 6 3 5 7 0 7 8 3 8
2 10 8 3 6 7 0 10 3 1
9 1 10 3 9 8 10 0 1 8
1 4 5 7 2 3 3 1 0 9
10 2 10 8 9 8 1 8 9 0

[出力例]
235

[入力例]
13 88
0 6 7 3 6 6 9 3 5 9 3 5 8
6 0 7 9 2 10 9 9 5 7 9 1 6
7 7 0 2 6 2 9 8 6 1 5 4 5
3 9 2 0 4 7 8 10 2 2 1 4 10
6 2 6 4 0 10 4 10 6 4 5 10 4
6 10 2 7 10 0 4 7 4 1 3 2 6
9 9 9 8 4 4 0 5 8 1 2 7 1
3 9 8 10 10 7 5 0 7 9 9 5 6
5 5 6 2 6 4 8 7 0 2 4 1 10
9 7 1 2 4 1 1 9 2 0 10 1 10
3 9 5 1 5 3 2 9 4 10 0 8 1
5 1 4 4 10 2 7 5 1 1 8 0 6
8 6 5 10 4 6 1 6 10 10 1 6 0

[出力例]
711

[入力例]
17 59
0 4 5 4 7 1 8 9 10 7 2 2 8 2 5 7 7
4 0 10 8 5 6 1 6 2 5 3 8 10 2 8 10 2
5 10 0 9 6 7 3 2 7 7 10 9 2 8 8 1 6
4 8 9 0 10 2 8 3 9 9 2 2 1 5 2 4 2
7 5 6 10 0 10 3 6 3 9 1 10 4 6 7 2 1
1 6 7 2 10 0 2 5 10 2 6 5 6 9 4 6 9
8 1 3 8 3 2 0 9 9 5 8 3 2 8 8 8 8
9 6 2 3 6 5 9 0 1 8 10 7 5 7 4 3 5
10 2 7 9 3 10 9 1 0 1 1 5 10 2 5 10 2
7 5 7 9 9 2 5 8 1 0 8 8 8 5 7 3 8
2 3 10 2 1 6 8 10 1 8 0 8 8 6 10 4 7
2 8 9 2 10 5 3 7 5 8 8 0 10 1 10 10 9
8 10 2 1 4 6 2 5 10 8 8 10 0 5 7 2 5
2 2 8 5 6 9 8 7 2 5 6 1 5 0 9 9 8
5 8 8 2 7 4 8 4 5 7 10 10 7 9 0 3 10
7 10 1 4 2 6 8 3 10 3 4 10 2 9 3 0 5
7 2 6 2 1 9 8 5 2 8 7 9 5 8 10 5 0

[出力例]
212

100

101

102

103

[入力例]

3 3

0 1 5

1 0 1

5 1 0

[出力例]

※AtCoderのテストケースより

[入力例]

4 8

0 2 3 5

2 0 1 2

3 1 0 8

5 2 8 0

[出力例]

※AtCoderのテストケースより

[入力例]

5 10

0 10 1 2 1

10 0 1 2 1

1 1 0 6 7

2 2 6 0 8

1 1 7 8 0

[出力例]

※AtCoderのテストケースより

[入力例]

7 23

0 3 6 1 4 3 8

3 0 7 9 9 6 10

6 7 0 10 7 1 10

1 9 10 0 5 3 8

4 9 7 5 0 4 2

3 6 1 3 4 0 5

8 10 10 8 2 5 0

[出力例]

[入力例]

10 50

0 5 2 4 8 8 2 9 1 10

5 0 7 1 7 6 10 1 4 2

2 7 0 10 5 3 8 10 5 10

4 1 10 0 10 5 3 3 7 8

8 7 5 10 0 7 6 9 2 9

8 6 3 5 7 0 7 8 3 8

2 10 8 3 6 7 0 10 3 1

9 1 10 3 9 8 10 0 1 8

1 4 5 7 2 3 3 1 0 9

10 2 10 8 9 8 1 8 9 0

[出力例]

235

[入力例]

13 88

0 6 7 3 6 6 9 3 5 9 3 5 8

6 0 7 9 2 10 9 9 5 7 9 1 6

7 7 0 2 6 2 9 8 6 1 5 4 5

3 9 2 0 4 7 8 10 2 2 1 4 10

6 2 6 4 0 10 4 10 6 4 5 10 4

6 10 2 7 10 0 4 7 4 1 3 2 6

9 9 9 8 4 4 0 5 8 1 2 7 1

3 9 8 10 10 7 5 0 7 9 9 5 6

5 5 6 2 6 4 8 7 0 2 4 1 10

9 7 1 2 4 1 1 9 2 0 10 1 10

3 9 5 1 5 3 2 9 4 10 0 8 1

5 1 4 4 10 2 7 5 1 1 8 0 6

8 6 5 10 4 6 1 6 10 10 1 6 0

[出力例]

711

[入力例]

17 59

0 4 5 4 7 1 8 9 10 7 2 2 8 2 5 7 7

4 0 10 8 5 6 1 6 2 5 3 8 10 2 8 10 2

5 10 0 9 6 7 3 2 7 7 10 9 2 8 8 1 6

4 8 9 0 10 2 8 3 9 9 2 2 1 5 2 4 2

7 5 6 10 0 10 3 6 3 9 1 10 4 6 7 2 1

1 6 7 2 10 0 2 5 10 2 6 5 6 9 4 6 9

8 1 3 8 3 2 0 9 9 5 8 3 2 8 8 8 8

9 6 2 3 6 5 9 0 1 8 10 7 5 7 4 3 5

10 2 7 9 3 10 9 1 0 1 1 5 10 2 5 10 2

7 5 7 9 9 2 5 8 1 0 8 8 8 5 7 3 8

2 3 10 2 1 6 8 10 1 8 0 8 8 6 10 4 7

2 8 9 2 10 5 3 7 5 8 8 0 10 1 10 10 9

8 10 2 1 4 6 2 5 10 8 8 10 0 5 7 2 5

2 2 8 5 6 9 8 7 2 5 6 1 5 0 9 9 8

5 8 8 2 7 4 8 4 5 7 10 10 7 9 0 3 10

7 10 1 4 2 6 8 3 10 3 4 10 2 9 3 0 5

7 2 6 2 1 9 8 5 2 8 7 9 5 8 10 5 0

[出力例]

212

■参照サイト
AtCoder Regular Contest 056
AtCoder Beginner Contest 187 (F – Close Group)

2021年12月18日

C++ の動作確認をしてみた（５９７）

C++の練習を兼ねて, AtCoder Beginner Contest 213 の問題E (Stronger Takahashi) を解いてみた.

■感想.
1. 問題Eは, 方針が見えなかったので, 解説および(複数の)正答者のプログラムを参考にして, AC版に到達できたと思う.
2. 01-BFSについて復習出来たので, 非常に良かったと思う.
3. 但し, 01-BFSは, いまいち, 本質を理解出来てないように見えるので, 引き続き, 今後の課題だと思われる.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

本家のサイト AtCoder Beginner Contest 213 解説の各リンクをご覧下さい.

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

// ※※※ 解答不能 ※※※
// https://atcoder.jp/contests/abc213/editorial/2397
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;
#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
#define a first
#define b second
const int INF = 2020202020;
constexpr int MAX = 252525;
int board[MAX];

int main(){
    
    // 1. 入力情報.
    int H, W;
    scanf("%d %d", &H, &W);
    rep(i, H){
        char c[505];
        scanf("%s", c);
        rep(j, W) if(c[j] == '#') board[i * W + j] = 1;
    }
    
    // 2. 01-BFS(解説 および 複数の正答者プログラム参照).
    // https://ja.wikipedia.org/wiki/幅優先探索
    // https://betrue12.hateblo.jp/entry/2018/12/08/000020
    auto bfs01 = [&](int s, int* d){
        // 2-1. 空のキュー.
        deque<P> dq;
        
        // 2-2. キュー に 保存.
        // -> キューに, 座標のみ保存だと, 正しく動作しない模様, 
        //    正答者のプログラムをいくつか見たところ, 距離も合わせて保存する必要があるらしい.
        //    dijkstra法 に, やや近い実装方法になると思われる.
        dq.pub({s, 0});
        while(!dq.empty()){
            // 2-3. キュー の 先頭要素を取り出す.
            // x: 列方向, y: 行方向 で考える.
            P u = dq.front();
            int cx = u.a % W , cy = u.a / W;
            int dCur = u.b;
            dq.pof();
            
            // 2-4. 最短距離更新.
            if(dCur >= d[u.a]) continue;
            d[u.a] = dCur;
            
            // 2-5. 周辺のマス を 確認.
            // -> 解説にある図で, * に 対する操作.
            // ※※※ 但し,  * の マスへの 移動コストが, すべて 1 になる訳ではないので要注意. ※※※
            // .***.
            // *****
            // **T**
            // *****
            // .***.
            // 
            for(auto &x : {-2, -1, 0, 1, 2}){
                for(auto &y : {-2, -1, 0, 1, 2}){
                    // 移動先候補のマス.
                    int nx = cx + x;
                    int ny = cy + y;
                    int n = nx + ny * W;
                    
                    // 到達不可能なマスであれば, Skip.
                    if(nx < 0 || nx >= W || ny < 0 || ny >= H || abs(x) + abs(y) == 4)  continue;
                    
                    // 上下左右のマスで, '.' の場合は, コスト 0 の 移動, それ以外のマスは, コスト 1 の 移動と見る.
                    if(!board[n] && x * y == 0 && abs(x + y) == 1) dq.puf({n, dCur + 0});
                    else                                           dq.pub({n, dCur + 1});
                }
            }
        }
    };
    int d[MAX];
    rep(i, MAX) d[i] = INF;
    bfs01(0, d);
    
    // 3. 出力.
    printf("%d", d[H * W - 1]);
    return 0;
    
}

// ※※※ 解答不能 ※※※

// https://atcoder.jp/contests/abc213/editorial/2397

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using P = pair<int, int>;

#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

#define a first

#define b second

const int INF = 2020202020;

constexpr int MAX = 252525;

int board[MAX];

int main(){

// 1. 入力情報.

int H, W;

scanf("%d %d", &H, &W);

rep(i, H){

char c[505];

scanf("%s", c);

rep(j, W) if(c[j] == '#') board[i * W + j] = 1;

}

// 2. 01-BFS(解説および複数の正答者プログラム参照).

// https://ja.wikipedia.org/wiki/幅優先探索

// https://betrue12.hateblo.jp/entry/2018/12/08/000020

auto bfs01 = [&](int s, int* d){

// 2-1. 空のキュー.

deque<P> dq;

// 2-2. キューに保存.

// -> キューに, 座標のみ保存だと, 正しく動作しない模様,

// 正答者のプログラムをいくつか見たところ, 距離も合わせて保存する必要があるらしい.

// dijkstra法に, やや近い実装方法になると思われる.

dq.pub({s, 0});

while(!dq.empty()){

// 2-3. キューの先頭要素を取り出す.

// x: 列方向, y: 行方向で考える.

P u = dq.front();

int cx = u.a % W , cy = u.a / W;

int dCur = u.b;

dq.pof();

// 2-4. 最短距離更新.

if(dCur >= d[u.a]) continue;

d[u.a] = dCur;

// 2-5. 周辺のマスを確認.

// -> 解説にある図で, * に対する操作.

// ※※※ 但し, * のマスへの移動コストが, すべて 1 になる訳ではないので要注意. ※※※

// .***.

// *****

// **T**

// *****

// .***.

for(auto &x : {-2, -1, 0, 1, 2}){

for(auto &y : {-2, -1, 0, 1, 2}){

// 移動先候補のマス.

int nx = cx + x;

int ny = cy + y;

int n = nx + ny * W;

// 到達不可能なマスであれば, Skip.

if(nx < 0 || nx >= W || ny < 0 || ny >= H || abs(x) + abs(y) == 4) continue;

// 上下左右のマスで, '.' の場合は, コスト 0 の移動, それ以外のマスは, コスト 1 の移動と見る.

if(!board[n] && x * y == 0 && abs(x + y) == 1) dq.puf({n, dCur + 0});

else dq.pub({n, dCur + 1});

}

};

int d[MAX];

rep(i, MAX) d[i] = INF;

bfs01(0, d);

// 3. 出力.

printf("%d", d[H * W - 1]);

return 0;

}

[入力例]
5 5
..#..
#.#.#
##.##
#.#.#
..#..

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

[入力例]
5 7
.......
######.
.......
.######
.......

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

[入力例]
8 8
.#######
########
########
########
########
########
########
#######.

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

[入力例]
2 12
.###########
###########.

[出力例]
5

[入力例]
11 50
.#################################################
####.####....####....###....##..###....##.....####
###.#.###.###.##..#########.###.######.##.########
###.#.###.###.##.##########.###.######.##.########
###.#.###.##.###.##########.###.######.##.########
##.....##....###.#######....###.###....##.....####
##.###.##.##.###.#######.######.######.##.########
##.###.##.###.##.#######.######.######.##.########
##.###.##.###.##..######.######.######.##.########
##.###.##....####....###....##...##....##.....####
#################################################.

[出力例]
12

[入力例]

5 5

..#..

#.#.#

##.##

#.#.#

..#..

[出力例]

※AtCoderのテストケースより

[入力例]

5 7

.......

######.

.......

.######

.......

[出力例]

※AtCoderのテストケースより

[入力例]

8 8

.#######

########

#######.

[出力例]

※AtCoderのテストケースより

[入力例]

2 12

.###########

###########.

[出力例]

[入力例]

11 50

.#################################################

####.####....####....###....##..###....##.....####

###.#.###.###.##..#########.###.######.##.########

###.#.###.###.##.##########.###.######.##.########

###.#.###.##.###.##########.###.######.##.########

##.....##....###.#######....###.###....##.....####

##.###.##.##.###.#######.######.######.##.########

##.###.##.###.##.#######.######.######.##.########

##.###.##.###.##..######.######.######.##.########

##.###.##....####....###....##...##....##.....####

#################################################.

[出力例]

■参照サイト
AtCoder Beginner Contest 213
01-BFSのちょっと丁寧な解説

2021年12月14日2021年12月14日

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

C++の練習を兼ねて, JOI 2021/2022 二次予選過去問の問題C (国土分割 (Land Division)) を解いてみた.

■感想.
1. 問題Cは, 実装に苦労したものの, 解説を見る前に, AC版に到達できたので十分だと思う.
2. 二次元累積和の復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
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
LL a[55][55], aCum[55][55];

int main(){
    
    // 1. 入力情報.
    int H, W;
    scanf("%d %d", &H, &W);
    rep(i, H) rep(j, W) scanf("%lld", &a[i][j]);
    
    // 2. 二次元累積和.
    // -> (px, py) ～ (qx, qy) は, 以下で計算.
    // aCum[qx][qy] - aCum[qx][py - 1] - aCum[px - 1][qy] + aCum[px - 1][py - 1].
    repx(i, 1, H + 1){
        repx(j, 1, W + 1){
            aCum[i][j] = aCum[i - 1][j] + aCum[i][j - 1] - aCum[i - 1][j - 1] + a[i - 1][j - 1];
        }
    }
    
    // 3. 分割.
    // 3-1. 列方向の分割.
    vvi cDivisors;
    repx(j, 1, W){
        // 1列目 ～ j列目まで含む場合.
        vi v;
        v.pb(j);
        
        // 基準となる人口をベースに探索.
        // (1, 1) ～ (H, j) の 範囲.
        LL p = aCum[H][j] - aCum[H][0] - aCum[0][j] + aCum[0][0];
        int l = j, r = j + 1;
        while(1){
            // 分割の探索終了.
            if(r > W) break;
            
            // (1, l + 1) ～ (H, r) の 範囲.
            LL cur = aCum[H][r] - aCum[H][l] - aCum[0][r] + aCum[0][l];
            
            // 新たな境界線が見つかった.
            if(cur == p){
                v.pb(r);
                l = r;
                r = l + 1;
            }
            
            // 見つからなかった.
            if(cur != p) r++;
        }
        
        // 探索した分割方法を追加.
        if(v.back() == W) cDivisors.pb(v);
    }
    /*
    for(auto &cDiv : cDivisors){
        for(auto &p : cDiv) printf("%d ", p);
        puts("");
    }
    */
    
    // 3-2. 行方向の分割.
    vvi rDivisors;
    repx(i, 1, H){
        // 1行目 ～ i行目まで含む場合.
        vi v;
        v.pb(i);
        
        // 基準となる人口をベースに探索.
        // (1, 1) ～ (i, W) の 範囲.
        LL p = aCum[i][W] - aCum[i][0] - aCum[0][W] + aCum[0][0];
        int u = i, d = i + 1;
        while(1){
            // 分割の探索終了.
            if(d > H) break;
            
            // (u + 1, 1) ～ (d, W) の 範囲.
            LL cur = aCum[d][W] - aCum[d][0] - aCum[u][W] + aCum[u][0];
            
            // 新たな境界線が見つかった.
            if(cur == p){
                v.pb(d);
                u = d;
                d = u + 1;
            }
            
            // 見つからなかった.
            if(cur != p) d++;
        }
        
        // 探索した分割方法を追加.
        if(v.back() == H) rDivisors.pb(v);
    }
    /*
    for(auto &rDiv : rDivisors){
        for(auto &p : rDiv) printf("%d ", p);
        puts("");
    }
    */
    
    // 4. 分割 を 全探索.
    int ans = cDivisors.size() + rDivisors.size();
    for(auto &cDiv : cDivisors){
        for(auto &rDiv : rDivisors){
            // チェック.
            bool ok = true;
            
            // 範囲.
            LL p = 0;
            int cBef = 0, rBef = 0;
            for(int cCur : cDiv){
                for(int rCur : rDiv){
                    // (rBef, cBef) ～ (rCur, cCur) の 範囲.
                    LL n = aCum[rCur][cCur] - aCum[rCur][cBef] - aCum[rBef][cCur] + aCum[rBef][cBef];
                    
                    // 初回のみ更新.
                    if(p == 0) p = n;
                    
                    // 評価.
                    if(p && p != n){
                        ok = false;
                        break;
                    }
                    
                    // 前回分更新.
                    rBef = rCur;
                }
                
                // 前回分更新.
                cBef = cCur;
                
                // 初期化.
                rBef = 0;
                
                // 判定(false)が決まっている場合.
                if(!ok) break;
            }
            
            // 加算.
            if(ok) ans++;
        }
    }
    
    // 5. 出力.
    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

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

LL a[55][55], aCum[55][55];

int main(){

// 1. 入力情報.

int H, W;

scanf("%d %d", &H, &W);

rep(i, H) rep(j, W) scanf("%lld", &a[i][j]);

// 2. 二次元累積和.

// -> (px, py) ～ (qx, qy) は, 以下で計算.

// aCum[qx][qy] - aCum[qx][py - 1] - aCum[px - 1][qy] + aCum[px - 1][py - 1].

repx(i, 1, H + 1){

repx(j, 1, W + 1){

aCum[i][j] = aCum[i - 1][j] + aCum[i][j - 1] - aCum[i - 1][j - 1] + a[i - 1][j - 1];

}

// 3. 分割.

// 3-1. 列方向の分割.

vvi cDivisors;

repx(j, 1, W){

// 1列目～ j列目まで含む場合.

vi v;

v.pb(j);

// 基準となる人口をベースに探索.

// (1, 1) ～ (H, j) の範囲.

LL p = aCum[H][j] - aCum[H][0] - aCum[0][j] + aCum[0][0];

int l = j, r = j + 1;

while(1){

// 分割の探索終了.

if(r > W) break;

// (1, l + 1) ～ (H, r) の範囲.

LL cur = aCum[H][r] - aCum[H][l] - aCum[0][r] + aCum[0][l];

// 新たな境界線が見つかった.

if(cur == p){

v.pb(r);

l = r;

r = l + 1;

}

// 見つからなかった.

if(cur != p) r++;

}

// 探索した分割方法を追加.

if(v.back() == W) cDivisors.pb(v);

}

for(auto &cDiv : cDivisors){

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

puts("");

}

// 3-2. 行方向の分割.

vvi rDivisors;

repx(i, 1, H){

// 1行目～ i行目まで含む場合.

vi v;

v.pb(i);

// 基準となる人口をベースに探索.

// (1, 1) ～ (i, W) の範囲.

LL p = aCum[i][W] - aCum[i][0] - aCum[0][W] + aCum[0][0];

int u = i, d = i + 1;

while(1){

// 分割の探索終了.

if(d > H) break;

// (u + 1, 1) ～ (d, W) の範囲.

LL cur = aCum[d][W] - aCum[d][0] - aCum[u][W] + aCum[u][0];

// 新たな境界線が見つかった.

if(cur == p){

v.pb(d);

u = d;

d = u + 1;

}

// 見つからなかった.

if(cur != p) d++;

}

// 探索した分割方法を追加.

if(v.back() == H) rDivisors.pb(v);

}

for(auto &rDiv : rDivisors){

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

puts("");

}

// 4. 分割を全探索.

int ans = cDivisors.size() + rDivisors.size();

for(auto &cDiv : cDivisors){

for(auto &rDiv : rDivisors){

// チェック.

bool ok = true;

// 範囲.

LL p = 0;

int cBef = 0, rBef = 0;

for(int cCur : cDiv){

for(int rCur : rDiv){

// (rBef, cBef) ～ (rCur, cCur) の範囲.

LL n = aCum[rCur][cCur] - aCum[rCur][cBef] - aCum[rBef][cCur] + aCum[rBef][cBef];

// 初回のみ更新.

if(p == 0) p = n;

// 評価.

if(p && p != n){

ok = false;

break;

}

// 前回分更新.

rBef = rCur;

}

// 前回分更新.

cBef = cCur;

// 初期化.

rBef = 0;

// 判定(false)が決まっている場合.

if(!ok) break;

}

// 加算.

if(ok) ans++;

}

// 5. 出力.

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

return 0;

}

[入力例]
2 3
10 10 20
10 10 20

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

[入力例]
1 4
2 1 1 2

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

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

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

[入力例]
1 1
10000

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

[入力例]
4 4
1 2 1 1
1 1 2 1
1 1 1 2
2 1 1 1

[出力例]
5

[入力例]
6 6
1 2 1 2 1 2
2 1 2 1 2 1
1 2 1 2 1 2
2 1 2 1 2 1
1 2 1 2 1 2
2 1 2 1 2 1

[出力例]
11

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

[出力例]
7

[入力例]
12 12
1 2 3 4 1 2 3 4 1 2 3 4
2 3 4 1 2 3 4 1 2 3 4 1
3 4 1 2 3 4 1 2 3 4 1 2
4 1 2 3 4 1 2 3 4 1 2 3
1 2 3 4 1 2 3 4 1 2 3 4
2 3 4 1 2 3 4 1 2 3 4 1
3 4 1 2 3 4 1 2 3 4 1 2
4 1 2 3 4 1 2 3 4 1 2 3
1 2 3 4 1 2 3 4 1 2 3 4
2 3 4 1 2 3 4 1 2 3 4 1
3 4 1 2 3 4 1 2 3 4 1 2
4 1 2 3 4 1 2 3 4 1 2 3

[出力例]
19

[入力例]
48 48
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

[出力例]
99

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

[入力例]

2 3

10 10 20

[出力例]

※AtCoderテストケースより

[入力例]

1 4

2 1 1 2

[出力例]

※AtCoderテストケースより

[入力例]

3 3

2 9 4

7 5 3

6 1 8

[出力例]

※AtCoderテストケースより

[入力例]

1 1

10000

[出力例]

※AtCoderテストケースより

[入力例]

4 4

1 2 1 1

1 1 2 1

1 1 1 2

2 1 1 1

[出力例]

[入力例]

6 6

1 2 1 2 1 2

2 1 2 1 2 1

1 2 1 2 1 2

2 1 2 1 2 1

1 2 1 2 1 2

2 1 2 1 2 1

[出力例]

[入力例]

9 9

1 2 3 1 2 3 1 2 3

3 1 2 3 1 2 3 1 2

2 3 1 2 3 1 2 3 1

1 2 3 1 2 3 1 2 3

3 1 2 3 1 2 3 1 2

2 3 1 2 3 1 2 3 1

1 2 3 1 2 3 1 2 3

3 1 2 3 1 2 3 1 2

2 3 1 2 3 1 2 3 1

[出力例]

[入力例]

12 12

1 2 3 4 1 2 3 4 1 2 3 4

2 3 4 1 2 3 4 1 2 3 4 1

3 4 1 2 3 4 1 2 3 4 1 2

4 1 2 3 4 1 2 3 4 1 2 3

1 2 3 4 1 2 3 4 1 2 3 4

2 3 4 1 2 3 4 1 2 3 4 1

3 4 1 2 3 4 1 2 3 4 1 2

4 1 2 3 4 1 2 3 4 1 2 3

1 2 3 4 1 2 3 4 1 2 3 4

2 3 4 1 2 3 4 1 2 3 4 1

3 4 1 2 3 4 1 2 3 4 1 2

4 1 2 3 4 1 2 3 4 1 2 3

[出力例]

[入力例]

48 48

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

[出力例]

■参照サイト
JOI 2021/2022 二次予選過去問

2021年12月13日

C++ の動作確認をしてみた（５９５）

C++の練習を兼ねて, AtCoder Regular Contest 054 の問題C (鯛焼き) を解いてみた.

■感想.
1. 問題Cは, 方針が見えなかったので, 解説を参考にして, AC版に到達できたと思う.
2. 行列の掃き出し法について復習出来たので, 非常に良かったと思う..
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/data/arc/054/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 pb push_back
#define all(x) x.begin(), x.end()

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    vs matrix;
    rep(i, N){
        char c[222];
        scanf("%s", c);
        string s(c);
        matrix.pb(s);
    }
    // puts("--- Matrix before update ---");
    // rep(i, N) printf("%s\n", matrix[i].c_str());
    
    // 2. 掃き出し法(mod2版).
    // https://ja.wikipedia.org/wiki/ガウスの消去法
    // 
    // ex.
    // [変更前行列]
    // 011001
    // 001001
    // 101011
    // 010110
    // 001100
    // 
    // [変更後行列]
    // 100001
    // 010000
    // 001001
    // 000101
    // 000011
    // 
    auto gauss = [&](vs &m, int N, int M) -> vs {
        // 2-1. 戻り値設定.
        vs ret = m;
        
        // 2-2. 各行を順次確認.
        rep(i, N){
            // 降順sort.
            sort(all(ret));
            reverse(all(ret));
            
            // 最初に, '1' となる位置.
            int at = M;
            rep(j, M){
                if(ret[i][j] == '1'){
                    at = j;
                    break;
                }
            }
            
            // 見つからなった場合.
            if(at == M) continue;
            
            // i行目以外(j行目)と比較して, 前項で求めた位置(列)に, '1' が 有れば, 掃き出す.
            rep(j, N){
                if(i != j && ret[j][at] == '1'){
                    // 操作対象を設定.
                    string o = ret[i]; // i行目.
                    string n = ret[j]; // j行目.
                    
                    // j行目の掃き出し.
                    rep(k, M) n[k] = '0' + ((n[k] - '0') ^ (o[k] - '0'));
                    
                    // j行目更新.
                    ret[j] = n;
                }
            }
        }
        
        // 2-3. 返却.
        return ret;
    };
    vs gMatrix = gauss(matrix, N, N);
    // puts("--- Matrix after update ---");
    // rep(i, N) printf("%s\n", gMatrix[i].c_str());
    
    // 3. 行列式.
    int ans = 1;
    rep(i, N) ans *= gMatrix[i][i] - '0';
    
    // 4. 出力.
    printf("%s\n", ans ? "Odd" : "Even");
    return 0;
    
}

100

// 解き直し.

// https://img.atcoder.jp/data/arc/054/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 pb push_back

#define all(x) x.begin(), x.end()

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

vs matrix;

rep(i, N){

char c[222];

scanf("%s", c);

string s(c);

matrix.pb(s);

}

// puts("--- Matrix before update ---");

// rep(i, N) printf("%s\n", matrix[i].c_str());

// 2. 掃き出し法(mod2版).

// https://ja.wikipedia.org/wiki/ガウスの消去法

// ex.

// [変更前行列]

// 011001

// 001001

// 101011

// 010110

// 001100

// [変更後行列]

// 100001

// 010000

// 001001

// 000101

// 000011

auto gauss = [&](vs &m, int N, int M) -> vs {

// 2-1. 戻り値設定.

vs ret = m;

// 2-2. 各行を順次確認.

rep(i, N){

// 降順sort.

sort(all(ret));

reverse(all(ret));

// 最初に, '1' となる位置.

int at = M;

rep(j, M){

if(ret[i][j] == '1'){

at = j;

break;

}

// 見つからなった場合.

if(at == M) continue;

// i行目以外(j行目)と比較して, 前項で求めた位置(列)に, '1' が有れば, 掃き出す.

rep(j, N){

if(i != j && ret[j][at] == '1'){

// 操作対象を設定.

string o = ret[i]; // i行目.

string n = ret[j]; // j行目.

// j行目の掃き出し.

rep(k, M) n[k] = '0' + ((n[k] - '0') ^ (o[k] - '0'));

// j行目更新.

ret[j] = n;

}

// 2-3. 返却.

return ret;

};

vs gMatrix = gauss(matrix, N, N);

// puts("--- Matrix after update ---");

// rep(i, N) printf("%s\n", gMatrix[i].c_str());

// 3. 行列式.

int ans = 1;

rep(i, N) ans *= gMatrix[i][i] - '0';

// 4. 出力.

printf("%s\n", ans ? "Odd" : "Even");

return 0;

}

[入力例]
3
110
101
011

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

[入力例]
3
110
111
011

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

[入力例]
2
00
00

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

[入力例]
12
000000100000
011111111111
000000100000
000111111100
100100000100
100111111100
100100000100
100111111100
100100000100
100111111100
100000000000
111111111111

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

[入力例]
5
10001
01010
00100
10100
01001

[出力例]
Odd

[入力例]
7
0010100
1010001
0010110
0110100
0011101
1110100
0110110

[出力例]
Even

[入力例]
20
10101011001000001011
01101000100000101010
00101010100110101101
01100001100101001011
10111100110110111011
00111001101011001010
01100100100101001101
01101101001010010001
00011011011101011100
01100001111010010011
01001000111001101101
00100101010111100001
01010101101111000000
11011100011101001001
00101101000111100100
01100001110011100111
01000110110011011101
01101000110000100110
10100011100101001010
11001010110101010111

[出力例]
Odd

[入力例]
30
111000000000000000000000000000
010000000000000000000000000000
001001000000000100000000000000
000100000000000000000100000000
001010000000000100000000000000
000001000000000000000000000000
010000100000000000000000000000
000000010000000100000000000000
000100001000000000000100000000
001000000100000000000000000000
000001000010000000000000000000
000100000001000000000000000000
000000000000100000000000000000
001000000000010000000100000000
000000000000001000000000000000
000100000000000100000000000000
000001000000000010000000000000
000000000000000001000000000000
000100000000000000100000000000
000000000000000100010000000000
000000000000000000001000000000
000001000000000000000100000000
000000000000000000000010000000
000000000000000000000001000000
000000000000000000000000100000
000000000000000100000100010000
000000000000000000000000001000
000000000000000000000000000100
000000000000000100000100000010
000000000000000000000000000001

[出力例]
Odd

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

[入力例]

110

101

011

[出力例]

Even

※AtCoderのテストケースより

[入力例]

110

111

011

[出力例]

Odd

※AtCoderのテストケースより

[入力例]

[出力例]

Even

※AtCoderのテストケースより

[入力例]

000000100000

011111111111

000000100000

000111111100

100100000100

100111111100

100100000100

100111111100

100100000100

100111111100

100000000000

111111111111

[出力例]

Even

※AtCoderのテストケースより

[入力例]

10001

01010

00100

10100

01001

[出力例]

Odd

[入力例]

0010100

1010001

0010110

0110100

0011101

1110100

0110110

[出力例]

Even

[入力例]

10101011001000001011

01101000100000101010

00101010100110101101

01100001100101001011

10111100110110111011

00111001101011001010

01100100100101001101

01101101001010010001

00011011011101011100

01100001111010010011

01001000111001101101

00100101010111100001

01010101101111000000

11011100011101001001

00101101000111100100

01100001110011100111

01000110110011011101

01101000110000100110

10100011100101001010

11001010110101010111

[出力例]

Odd

[入力例]

111000000000000000000000000000

010000000000000000000000000000

001001000000000100000000000000

000100000000000000000100000000

001010000000000100000000000000

000001000000000000000000000000

010000100000000000000000000000

000000010000000100000000000000

000100001000000000000100000000

001000000100000000000000000000

000001000010000000000000000000

000100000001000000000000000000

000000000000100000000000000000

001000000000010000000100000000

000000000000001000000000000000

000100000000000100000000000000

000001000000000010000000000000

000000000000000001000000000000

000100000000000000100000000000

000000000000000100010000000000

000000000000000000001000000000

000001000000000000000100000000

000000000000000000000010000000

000000000000000000000001000000

000000000000000000000000100000

000000000000000100000100010000

000000000000000000000000001000

000000000000000000000000000100

000000000000000100000100000010

000000000000000000000000000001

[出力例]

Odd

■参照サイト
AtCoder Regular Contest 054

2021年12月10日

C++ の動作確認をしてみた（５９４）

C++の練習を兼ねて, AtCoder Beginner Contest 205 の問題D (Kth Excluded) を解いてみた.

■感想.
1. 問題Dは, 方針を決めることができたので, AC版に到達できたと思う.
2. 桁数オーバーフローに注意する必要があると感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

本家のサイト AtCoder Beginner Contest 205 解説の各リンクをご覧下さい.

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vl = vector<LL>;
#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
#define all(x) x.begin(), x.end()

int main(){
    
    // 1. 入力情報.
    int N, Q;
    scanf("%d %d", &N, &Q);
    vl aCum, aMax;
    LL bef = 0, cur, aCount = 0;
    rep(i, N + 1){
        // 1-1. 今回分更新.
        if(i < N) scanf("%lld", &cur);
        else      cur = 2e18 + 1; // killer_00.txt, killer_01.txt の WA回避のため修正.
        
        // 1-2. 前回分 + 1 でない.
        if(cur != bef + 1){
            // 開始地点, 終了地点, 数列の長さ.
            LL s = bef + 1, g = cur - 1;
            aCount += (g - s + 1);
            
            // 数列の長さ.
            aCum.pb(aCount);
            
            // 終了地点.
            aMax.pb(g);
        }
        
        // 1-3. 前回分更新.
        bef = cur;
    }
    
    // 2. クエリ回答.
    rep(i, Q){
        // 2-1. 入力情報.
        LL k;
        scanf("%lld", &k);
        
        // 2-2. 対象区間は？
        int at = lower_bound(all(aCum), k) - aCum.begin();
        
        // 2-3. 出力.
        printf("%lld\n", aMax[at] - (aCum[at] - k));
    }
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vl = vector<LL>;

#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

#define all(x) x.begin(), x.end()

int main(){

// 1. 入力情報.

int N, Q;

scanf("%d %d", &N, &Q);

vl aCum, aMax;

LL bef = 0, cur, aCount = 0;

rep(i, N + 1){

// 1-1. 今回分更新.

if(i < N) scanf("%lld", &cur);

else cur = 2e18 + 1; // killer_00.txt, killer_01.txt の WA回避のため修正.

// 1-2. 前回分 + 1 でない.

if(cur != bef + 1){

// 開始地点, 終了地点, 数列の長さ.

LL s = bef + 1, g = cur - 1;

aCount += (g - s + 1);

// 数列の長さ.

aCum.pb(aCount);

// 終了地点.

aMax.pb(g);

}

// 1-3. 前回分更新.

bef = cur;

}

// 2. クエリ回答.

rep(i, Q){

// 2-1. 入力情報.

LL k;

scanf("%lld", &k);

// 2-2. 対象区間は？

int at = lower_bound(all(aCum), k) - aCum.begin();

// 2-3. 出力.

printf("%lld\n", aMax[at] - (aCum[at] - k));

}

return 0;

}

[入力例]
4 3
3 5 6 7
2
5
3

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

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

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

[入力例]
25 10
6 12 13 14 15 18 19 20 21 30 31 33 34 36 38 39 50 52 53 61 62 63 70 75 76
6
12
18
23
31
38
45
52
62
72

[出力例]
7
17
27
37
47
57
67
77
87
97

[入力例]
100 23
9 10 11 17 18 19 28 30 33 35 36 37 45 46 49 52 53 54 62 64 65 66 73 75 76 82 87 89 91 95 100 103 104 106 109 112 115 116 121 123 127 132 134 135 137 138 143 145 146 147 148 150 151 152 155 159 164 167 171 175 180 181 184 189 194 198 203 204 209 210 211 215 218 221 226 230 231 232 253 254 255 297 298 299 310 311 330 331 332 353 354 355 380 381 497 498 499 502 503 504
21
54
43
46
900
3
18
83
72
17
592
93
56
651
93
50
495
25
9
34
49
421
921

[出力例]
27
79
61
68
1000
3
24
122
105
23
692
139
81
751
139
72
595
34
12
48
71
521
1021

[入力例]
250 50
746613 746614 746615 2683153 3233720 4204660 4652794 5883835 6422788 6953670 7636076 8563481 9178735 9489843 9899172 10335868 10653155 11792699 11925921 13046145 13808643 14855572 15487195 16627308 17744167 18234255 19053679 19337935 20030518 21024520 21745112 22629723 22653485 23431917 24663819 25323066 26145758 27013488 27353017 27383022 27974175 28107805 28650712 29447740 30007066 30431360 30431361 30431362 30431363 30431364 33706250 34343267 35348883 36527092 36704391 37624195 38595540 38843525 39469807 40677306 40867726 41413646 41450599 42443129 42673155 43814255 44319778 45367530 46051714 46214520 46409682 46649187 47848776 48041150 49107102 49549002 50471556 51196857 52387753 52743126 53268887 53290116 53836692 54096175 55128955 55430769 56299460 56845910 58074768 58505119 59035065 59636949 60072005 60398854 61581656 62082401 62706903 63721251 63979740 64183740 64886128 65887076 65973029 66567134 67234932 67647604 68263536 68830022 69145848 70197165 71431412 71904605 72507825 72847177 72847178 72847179 74293680 74464402 74561173 75279390 76465146 76914292 76918559 77562993 77872863 78589101 78886401 79034982 79279781 79865710 80239004 81047599 81940328 82004122 82614772 83791664 84743572 85403795 85516862 85942481 86512389 87493211 87609539 88046984 88476486 89576066 90624417 91719247 91802642 92034759 92705104 93924733 94470025 95300864 95503652 96171236 96557301 96611825 97630015 97783772 98356198 98773823 99506358 99942052 101118416 101695959 102003307 102740910 102740911 102740912 102740913 102740914 107236281 107793841 108421371 109063986 110174581 110430309 111209218 112411974 113512766 113826936 114503106 115484856 115653990 116273123 116291391 116817712 117420207 118217824 118417034 119483434 119831598 119872135 121017712 121170135 121415639 122565788 123553520 123853682 124201031 124509002 125578997 125927099 125927100 125927101 125927102 125927103 125927104 125927105 130086977 130649975 130649976 130649977 132762225 133842101 133925877 134897737 136126419 136135464 137035030 137935786 139155540 139237102 140013889 141037552 141990744 142347628 143451636 144240520 144799072 145606437 146038290 146147363 146202540 147406002 148238354 149030196 149349615 150543917 150913307 152123371 153166373 153975225 154195402 155052997 155052998 155052999 155053000 155053001
110251
688332
1853162
2241472
2302113
3394423
4113196
4897496
5629575
6030655
6203046
7355841
7941409
8860266
9915464
10475700
11295594
11611593
12341892
12382850
13535801
14596820
14945771
15212412
16050416
16556751
16952026
16982735
17404171
18360731
18404043
18566152
19717961
20534388
20942279
21892954
22344006
22615407
22884648
23243021
23868687
24210078
24529796
25214811
26154712
26222830
26723591
27744901
28976714
29989729

[出力例]
110251
688332
1853165
2241475
2302116
3394428
4113201
4897503
5629582
6030663
6203054
7355851
7941420
8860278
9915479
10475716
11295611
11611610
12341911
12382869
13535821
14596841
14945793
15212434
16050439
16556774
16952050
16982759
17404195
18360757
18404069
18566178
19717989
20534417
20942308
21892985
22344037
22615438
22884681
23243054
23868721
24210112
24529830
25214846
26154749
26222867
26723628
27744941
28976757
29989773

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

[入力例]

4 3

3 5 6 7

[出力例]

※AtCoderテストケースより

[入力例]

5 2

1 2 3 4 5

[出力例]

※AtCoderテストケースより

[入力例]

25 10

6 12 13 14 15 18 19 20 21 30 31 33 34 36 38 39 50 52 53 61 62 63 70 75 76

[出力例]

[入力例]

100 23

9 10 11 17 18 19 28 30 33 35 36 37 45 46 49 52 53 54 62 64 65 66 73 75 76 82 87 89 91 95 100 103 104 106 109 112 115 116 121 123 127 132 134 135 137 138 143 145 146 147 148 150 151 152 155 159 164 167 171 175 180 181 184 189 194 198 203 204 209 210 211 215 218 221 226 230 231 232 253 254 255 297 298 299 310 311 330 331 332 353 354 355 380 381 497 498 499 502 503 504

900

592

651

495

421

921

[出力例]

1000

122

105

692

139

751

139

595

521

1021

[入力例]

250 50

746613 746614 746615 2683153 3233720 4204660 4652794 5883835 6422788 6953670 7636076 8563481 9178735 9489843 9899172 10335868 10653155 11792699 11925921 13046145 13808643 14855572 15487195 16627308 17744167 18234255 19053679 19337935 20030518 21024520 21745112 22629723 22653485 23431917 24663819 25323066 26145758 27013488 27353017 27383022 27974175 28107805 28650712 29447740 30007066 30431360 30431361 30431362 30431363 30431364 33706250 34343267 35348883 36527092 36704391 37624195 38595540 38843525 39469807 40677306 40867726 41413646 41450599 42443129 42673155 43814255 44319778 45367530 46051714 46214520 46409682 46649187 47848776 48041150 49107102 49549002 50471556 51196857 52387753 52743126 53268887 53290116 53836692 54096175 55128955 55430769 56299460 56845910 58074768 58505119 59035065 59636949 60072005 60398854 61581656 62082401 62706903 63721251 63979740 64183740 64886128 65887076 65973029 66567134 67234932 67647604 68263536 68830022 69145848 70197165 71431412 71904605 72507825 72847177 72847178 72847179 74293680 74464402 74561173 75279390 76465146 76914292 76918559 77562993 77872863 78589101 78886401 79034982 79279781 79865710 80239004 81047599 81940328 82004122 82614772 83791664 84743572 85403795 85516862 85942481 86512389 87493211 87609539 88046984 88476486 89576066 90624417 91719247 91802642 92034759 92705104 93924733 94470025 95300864 95503652 96171236 96557301 96611825 97630015 97783772 98356198 98773823 99506358 99942052 101118416 101695959 102003307 102740910 102740911 102740912 102740913 102740914 107236281 107793841 108421371 109063986 110174581 110430309 111209218 112411974 113512766 113826936 114503106 115484856 115653990 116273123 116291391 116817712 117420207 118217824 118417034 119483434 119831598 119872135 121017712 121170135 121415639 122565788 123553520 123853682 124201031 124509002 125578997 125927099 125927100 125927101 125927102 125927103 125927104 125927105 130086977 130649975 130649976 130649977 132762225 133842101 133925877 134897737 136126419 136135464 137035030 137935786 139155540 139237102 140013889 141037552 141990744 142347628 143451636 144240520 144799072 145606437 146038290 146147363 146202540 147406002 148238354 149030196 149349615 150543917 150913307 152123371 153166373 153975225 154195402 155052997 155052998 155052999 155053000 155053001

110251

688332

1853162

2241472

2302113

3394423

4113196

4897496

5629575

6030655

6203046

7355841

7941409

8860266

9915464

10475700

11295594

11611593

12341892

12382850

13535801

14596820

14945771

15212412

16050416

16556751

16952026

16982735

17404171

18360731

18404043

18566152

19717961

20534388

20942279

21892954

22344006

22615407

22884648

23243021

23868687

24210078

24529796

25214811

26154712

26222830

26723591

27744901

28976714

29989729

[出力例]

110251

688332

1853165

2241475

2302116

3394428

4113201

4897503

5629582

6030663

6203054

7355851

7941420

8860278

9915479

10475716

11295611

11611610

12341911

12382869

13535821

14596841

14945793

15212434

16050439

16556774

16952050

16982759

17404195

18360757

18404069

18566178

19717989

20534417

20942308

21892985

22344037

22615438

22884681

23243054

23868721

24210112

24529830

25214846

26154749

26222867

26723628

27744941

28976757

29989773

■参照サイト
AtCoder Beginner Contest 205

2021年12月7日2021年12月7日

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

C++の練習を兼ねて, AtCoder Beginner Contest 199 の問題F (Graph Smoothing) を解いてみた.

■感想.
1. 問題Fは, 方針が見えなかったので, 解説を参考に, 実装して, AC版に到達できたと思う.
2. 個人的には, 操作後の頂点に書かれている数の期待値が, 行列計算から, 算出できるというロジックが, 非常に面白く感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

本家のサイト AtCoder Beginner Contest 199 解説の各リンクをご覧下さい.

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

// 解き直し.
// https://atcoder.jp/contests/abc199/editorial/1167
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vi = vector<int>;
using vl = vector<LL>;
using vvi = vector<vi>;
using vvl = vector<vl>;
#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
const LL MOD = 1e9 + 7;
LL a[111];

// Fermat's little theorem から, 大きな冪乗の計算を行う.
// @param a: べき乗したい正整数.
// @param b: 指数.
// @return:  べき乗した計算結果(mod版).
LL mPow(LL a, LL b){
    LL t = 1;
    while(b){
        if(b & 1) t = (t * a) % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return t;
}

// 行列乗算を行う.
// @param a: 行列.
// @param b: 行列.
// @return:  計算結果(mod版).
vvl matrixMultiplication(vvl &a, vvl &b){
    int n = a.size();
    vvl ret(n, vl(n, 0LL));
    rep(i, n){
        rep(j, n){
            LL t = 0;
            rep(k, n){
                t += a[i][k] * b[k][j];
                t %= MOD;
            }
            ret[i][j] = t;
        }
    }
    return ret;
}

int main(){
    
    // 1. 入力情報.
    int N, M;
    LL K;
    scanf("%d %d %lld", &N, &M, &K);
    rep(i, N) scanf("%lld", &a[i]);
    vvi G(N);
    rep(i, M){
        int x, y;
        scanf("%d %d", &x, &y);
        x--, y--;
        G[x].pb(y);
        G[y].pb(x);
    }
    
    // 2. 逆数.
    LL im = mPow((LL)M, MOD - 2);
    LL i2 = mPow(2LL, MOD - 2);
    
    // 3. 行列 m.
    vvl matrix(N, vl(N, 0LL));
    rep(i, N){
        // 3-1. 頂点 i の 次数.
        LL d = (LL)G[i].size();
        
        // 3-2. (i, i)成分.
        // -> 1 - (d / M) * (1 / 2) を 設定.
        matrix[i][i] = (1 + (MOD - d) * im % MOD * i2 % MOD) % MOD;
        
        // 3-3. 頂点 i の 隣接頂点.
        // -> (1 / M) * (1 / 2) を 設定.
        for(auto &p : G[i]) matrix[p][i] = im * i2 % MOD;
    }
    
    // 4. 行列のべき乗.
    auto f = [&](vvl &m, LL b) -> vvl {
        // 4-1. 単位行列.
        vvl t(N, vl(N, 0LL));
        rep(i, N) t[i][i] = 1;
        
        // 4-2. べき乗計算.
        vvl a = m;
        while(b){
            if(b & 1) t = matrixMultiplication(t, a);
            a = matrixMultiplication(a, a);
            b >>= 1;
        }
        
        // 4-3. 返却.
        return t;
    };
    
    // 5. 行列 m の K 乗.
    vvl kMatrix = f(matrix, K);
    
    // 6. 出力.
    rep(i, N){
        LL ans = 0;
        rep(j, N){
            ans += a[j] * kMatrix[j][i];
            ans %= MOD;
        }
        printf("%lld\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

// 解き直し.

// https://atcoder.jp/contests/abc199/editorial/1167

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vi = vector<int>;

using vl = vector<LL>;

using vvi = vector<vi>;

using vvl = vector<vl>;

#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

const LL MOD = 1e9 + 7;

LL a[111];

// Fermat's little theorem から, 大きな冪乗の計算を行う.

// @param a: べき乗したい正整数.

// @param b: 指数.

// @return: べき乗した計算結果(mod版).

LL mPow(LL a, LL b){

LL t = 1;

while(b){

if(b & 1) t = (t * a) % MOD;

a = a * a % MOD;

b >>= 1;

}

return t;

}

// 行列乗算を行う.

// @param a: 行列.

// @param b: 行列.

// @return: 計算結果(mod版).

vvl matrixMultiplication(vvl &a, vvl &b){

int n = a.size();

vvl ret(n, vl(n, 0LL));

rep(i, n){

rep(j, n){

LL t = 0;

rep(k, n){

t += a[i][k] * b[k][j];

t %= MOD;

}

ret[i][j] = t;

}

return ret;

}

int main(){

// 1. 入力情報.

int N, M;

LL K;

scanf("%d %d %lld", &N, &M, &K);

rep(i, N) scanf("%lld", &a[i]);

vvi G(N);

rep(i, M){

int x, y;

scanf("%d %d", &x, &y);

x--, y--;

G[x].pb(y);

G[y].pb(x);

}

// 2. 逆数.

LL im = mPow((LL)M, MOD - 2);

LL i2 = mPow(2LL, MOD - 2);

// 3. 行列 m.

vvl matrix(N, vl(N, 0LL));

rep(i, N){

// 3-1. 頂点 i の次数.

LL d = (LL)G[i].size();

// 3-2. (i, i)成分.

// -> 1 - (d / M) * (1 / 2) を設定.

matrix[i][i] = (1 + (MOD - d) * im % MOD * i2 % MOD) % MOD;

// 3-3. 頂点 i の隣接頂点.

// -> (1 / M) * (1 / 2) を設定.

for(auto &p : G[i]) matrix[p][i] = im * i2 % MOD;

}

// 4. 行列のべき乗.

auto f = [&](vvl &m, LL b) -> vvl {

// 4-1. 単位行列.

vvl t(N, vl(N, 0LL));

rep(i, N) t[i][i] = 1;

// 4-2. べき乗計算.

vvl a = m;

while(b){

if(b & 1) t = matrixMultiplication(t, a);

a = matrixMultiplication(a, a);

b >>= 1;

}

// 4-3. 返却.

return t;

};

// 5. 行列 m の K 乗.

vvl kMatrix = f(matrix, K);

// 6. 出力.

rep(i, N){

LL ans = 0;

rep(j, N){

ans += a[j] * kMatrix[j][i];

ans %= MOD;

}

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

}

return 0;

}

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

[出力例]
3
500000005
500000008
※AtCoderテストケースより

[入力例]
3 2 2
12 48 36
1 2
1 3

[出力例]
750000036
36
250000031
※AtCoderテストケースより

[入力例]
4 5 1000
578 173 489 910
1 2
2 3
3 4
4 1
1 3

[出力例]
201113830
45921509
67803140
685163678
※AtCoderテストケースより

[入力例]
3 3 2
4 8 16
1 2
2 3
3 1

[出力例]
8
9
11

[入力例]
10 12 15
3 1 4 1 5 9 2 6 5 3
1 2
2 3
3 1
4 5
5 6
6 4
7 8
8 9
9 7
2 10
4 10
9 10

[出力例]
60105104
306664487
204426177
528008430
119334530
696618822
438064470
15348755
686133158
945296134

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

[出力例]
256833840
773912707
782215323
520721643
812754100
686558120
158488543
731923937
956199888
385308127
166469694
793620776
525611593
975959465
25353523
820154314
839516161
264137745
498907154
25353523

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

[入力例]

3 2 1

3 1 5

1 2

1 3

[出力例]

500000005

500000008

※AtCoderテストケースより

[入力例]

3 2 2

12 48 36

1 2

1 3

[出力例]

750000036

250000031

※AtCoderテストケースより

[入力例]

4 5 1000

578 173 489 910

1 2

2 3

3 4

4 1

1 3

[出力例]

201113830

45921509

67803140

685163678

※AtCoderテストケースより

[入力例]

3 3 2

4 8 16

1 2

2 3

3 1

[出力例]

[入力例]

10 12 15

3 1 4 1 5 9 2 6 5 3

1 2

2 3

3 1

4 5

5 6

6 4

7 8

8 9

9 7

2 10

4 10

9 10

[出力例]

60105104

306664487

204426177

528008430

119334530

696618822

438064470

15348755

686133158

945296134

[入力例]

20 25 123456789

1 2 5 9 9 2 1 0 4 9 8 9 4 8 7 3 1 6 4 7

1 2

2 3

3 4

4 5

5 1

6 1

7 2

8 3

9 4

10 5

6 11

11 16

16 6

7 12

12 17

17 7

8 13

13 18

18 8

9 14

14 19

19 9

10 15

15 20

20 10

[出力例]

256833840

773912707

782215323

520721643

812754100

686558120

158488543

731923937

956199888

385308127

166469694

793620776

525611593

975959465

25353523

820154314

839516161

264137745

498907154

25353523

■参照サイト
AtCoder Beginner Contest 199（Sponsored by Panasonic）

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

C++の練習を兼ねて, AtCoder Regular Contest 036 の 問題C (偶然ジェネレータ) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 045 の 問題C (エックスオア多橋君) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 232 の 問題C (Graph Isomorphism) ～ 問題D (Weak Takahashi) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 056 の 問題C (部門分け) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 213 の 問題E (Stronger Takahashi) を解いてみた.

C++の練習を兼ねて, JOI 2021/2022 二次予選 過去問 の 問題C (国土分割 (Land Division)) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 054 の 問題C (鯛焼き) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 205 の 問題D (Kth Excluded) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 199 の 問題F (Graph Smoothing) を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 036 の問題C (偶然ジェネレータ) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 045 の問題C (エックスオア多橋君) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 232 の問題C (Graph Isomorphism) ～問題D (Weak Takahashi) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 056 の問題C (部門分け) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 213 の問題E (Stronger Takahashi) を解いてみた.

C++の練習を兼ねて, JOI 2021/2022 二次予選過去問の問題C (国土分割 (Land Division)) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 054 の問題C (鯛焼き) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 205 の問題D (Kth Excluded) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 199 の問題F (Graph Smoothing) を解いてみた.