3月, 2020 | 個人用メモ帳

2020年3月7日

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

C++の練習を兼ねて, AtCoder Beginner Contest 158 の問題D (D – String Formation) を解いてみた.

■感想.
1. 解説見る前に, AC版となったので良かったと思う.
2. 但し, 実行時間が, 大きい(1224[ms])ため, 改善の余地があるはず.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

#include <bits/stdc++.h>
using namespace std;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define all(x) x.begin(), x.end()

int main(){
    
    // 1. 入力情報.
    char s[101010];
    int Q;
    scanf("%s %d", s, &Q);
    string S(s);
    
    // 2. 文字列を, Q回操作.
    int t, f;
    char c[11];
    bool flip = false;
    rep(i, Q){
        scanf("%d", &t);
        // 2-1. 文字列 S の前後を反転.
        if(t == 1) flip = !flip;
        
        // 2-2. 文字列 S の先頭, 末尾を操作.
        if(t == 2){
            scanf("%d %s", &f, c);
            string C(c);
            
            // 2-3. 文字列 S の先頭に C を追加.
            if(f == 1){
                if(flip) S.append(C);
                else     S.insert(0, C);
            }
            
            // 2-4. 文字列 S の末尾に C を追加.
            if(f == 2){
                if(flip) S.insert(0, C);
                else     S.append(C);
            }
        }
    }
    
    // 3. 反転チェック.
    if(flip) reverse(all(S));
    
    // 4. 出力.
    printf("%s\n", S.c_str());
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

#define repex(i, a, b, c) for(int i = a; i < b; i += c)

#define repx(i, a, b) repex(i, a, b, 1)

#define rep(i, n) repx(i, 0, n)

#define repr(i, a, b) for(int i = a; i >= b; i--)

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

int main(){

// 1. 入力情報.

char s[101010];

int Q;

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

string S(s);

// 2. 文字列を, Q回操作.

int t, f;

char c[11];

bool flip = false;

rep(i, Q){

scanf("%d", &t);

// 2-1. 文字列 S の前後を反転.

if(t == 1) flip = !flip;

// 2-2. 文字列 S の先頭, 末尾を操作.

if(t == 2){

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

string C(c);

// 2-3. 文字列 S の先頭に C を追加.

if(f == 1){

if(flip) S.append(C);

else S.insert(0, C);

}

// 2-4. 文字列 S の末尾に C を追加.

if(f == 2){

if(flip) S.insert(0, C);

else S.append(C);

}

// 3. 反転チェック.

if(flip) reverse(all(S));

// 4. 出力.

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

return 0;

}

[入力例]
a
4
2 1 p
1
2 2 c
1

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

[入力例]
a
6
2 2 a
2 1 b
1
2 2 c
1
1

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

[入力例]
y
1
2 1 x

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

[入力例]
abcba
15
2 2 d
2 1 e
1
2 2 f
1
2 1 g
1
2 1 i
1
1
2 1 j
2 2 k
1
2 2 l
2 1 m

[出力例]
mkgfeabcbadijl

[入力例]
formation
150
2 2 d
1
2 2 q
1
2 2 f
1
2 2 q
2 2 w
2 2 p
2 2 v
2 2 f
1
1
2 1 d
2 1 t
1
2 1 i
2 1 w
1
2 1 z
2 1 w
1
1
2 2 l
2 1 q
1
2 1 m
1
1
2 1 j
2 2 a
1
2 1 j
2 2 r
1
2 2 m
2 2 z
2 1 j
1
1
2 1 i
2 1 b
1
2 2 g
2 1 z
1
2 1 r
1
1
2 2 k
1
2 1 i
2 2 j
2 1 q
2 2 e
1
2 2 j
1
2 1 o
2 2 h
1
2 2 j
2 2 y
1
2 2 j
2 2 k
1
2 1 r
1
2 2 f
2 1 r
1
2 2 x
1
2 2 r
1
2 2 m
1
2 2 h
2 1 l
1
2 2 d
2 2 s
2 2 j
1
2 2 w
2 2 x
1
2 2 a
2 2 p
2 2 s
1
2 2 a
2 2 k
1
2 2 c
2 2 d
2 1 u
2 2 s
1
2 2 t
2 2 x
1
2 2 u
1
2 2 r
2 1 a
2 2 u
1
2 2 v
2 2 v
2 2 y
1
2 2 s
2 1 k
2 2 t
1
2 2 u
2 2 x
2 1 h
2 1 n
1
2 2 x
2 2 h
1
2 1 j
2 1 e
1
2 2 q
2 2 s
2 2 s
1
2 1 o
2 2 w
1
2 2 d
2 2 v
2 2 m
2 1 c
2 2 j
1
2 1 p
2 2 h
1
2 2 f
1
2 2 x
1
2 1 b
2 2 e

[出力例]
bxhcwxukyvvausdcspajsdlmxryjojqikzzmjaqwztdfdnoitamrofqqwpvfiwlmjrjibgrjehjkrfrhwxakutxrusthnxhjeqssodvmjpfe

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

[入力例]

2 1 p

2 2 c

[出力例]

cpa

※AtCoderテストケースより

[入力例]

2 2 a

2 1 b

2 2 c

[出力例]

aabc

※AtCoderテストケースより

[入力例]

2 1 x

[出力例]

※AtCoderテストケースより

[入力例]

abcba

2 2 d

2 1 e

2 2 f

2 1 g

2 1 i

2 1 j

2 2 k

2 2 l

2 1 m

[出力例]

mkgfeabcbadijl

[入力例]

formation

150

2 2 d

2 2 q

2 2 f

2 2 q

2 2 w

2 2 p

2 2 v

2 2 f

2 1 d

2 1 t

2 1 i

2 1 w

2 1 z

2 1 w

2 2 l

2 1 q

2 1 m

2 1 j

2 2 a

2 1 j

2 2 r

2 2 m

2 2 z

2 1 j

2 1 i

2 1 b

2 2 g

2 1 z

2 1 r

2 2 k

2 1 i

2 2 j

2 1 q

2 2 e

2 2 j

2 1 o

2 2 h

2 2 j

2 2 y

2 2 j

2 2 k

2 1 r

2 2 f

2 1 r

2 2 x

2 2 r

2 2 m

2 2 h

2 1 l

2 2 d

2 2 s

2 2 j

2 2 w

2 2 x

2 2 a

2 2 p

2 2 s

2 2 a

2 2 k

2 2 c

2 2 d

2 1 u

2 2 s

2 2 t

2 2 x

2 2 u

2 2 r

2 1 a

2 2 u

2 2 v

2 2 y

2 2 s

2 1 k

2 2 t

2 2 u

2 2 x

2 1 h

2 1 n

2 2 x

2 2 h

2 1 j

2 1 e

2 2 q

2 2 s

2 1 o

2 2 w

2 2 d

2 2 v

2 2 m

2 1 c

2 2 j

2 1 p

2 2 h

2 2 f

2 2 x

2 1 b

2 2 e

[出力例]

bxhcwxukyvvausdcspajsdlmxryjojqikzzmjaqwztdfdnoitamrofqqwpvfiwlmjrjibgrjehjkrfrhwxakutxrusthnxhjeqssodvmjpfe

■参照サイト
AtCoder Beginner Contest 158

2020年3月7日2020年3月7日

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

C++の練習を兼ねて, AtCoder Beginner Contest 027 の問題C (C – 倍々ゲーム) を解いてみた.

■感想.
1. 非常に苦労したものの, 試行錯誤から, 規則性を抽出できたので, AC版となった.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using P = pair<LL, 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 a first
#define b second
const int MAX = 63;
LL pow2[MAX];

int main(){
    
    // 1. 入力情報.
    LL N;
    scanf("%lld", &N);
    
    // 2. 2 の 冪乗 を 保存.
    pow2[0] = 1;
    rep(i, MAX) pow2[i + 1] = pow2[i] << 1;
    // rep(i, MAX) printf("%lld\n", pow2[i]);
    
    // 3. 青木君勝利する区間を保存.
    // 以下の区間を予想.
    // [1, 1]
    // [6, 9]
    // [26, 41]
    // [106, 109]
    // ...
    // [as, ae] と 置いたとき,
    // ae = -1 + (2 の 1乗) + (2 の 3乗) + (2 の 5乗) + ...
    // as = ae - (2 の 偶数乗) + 1
    // と仮定？
    // 
    // (2 の 60乗) … 1152921504606846976
    vector<P> v;
    LL as = 0, ae = -1;
    repex(i, 1, MAX, 2){
        ae = ae + pow2[i];
        as = ae - pow2[i - 1] + 1;
        v.pb({as, ae});
    }
    // rep(i, v.size()) printf("%lld %lld\n", v[i].a, v[i].b);
    
    // 4. 判定.
    bool aoki = false;
    rep(i, v.size()){
        if(N >= v[i].a && N <= v[i].b){
            aoki = true;
            break;
        }
    }
    
    // 5. 出力.
    printf("%s\n", aoki ? "Aoki" : "Takahashi");
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using P = pair<LL, 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 a first

#define b second

const int MAX = 63;

LL pow2[MAX];

int main(){

// 1. 入力情報.

LL N;

scanf("%lld", &N);

// 2. 2 の冪乗を保存.

pow2[0] = 1;

rep(i, MAX) pow2[i + 1] = pow2[i] << 1;

// rep(i, MAX) printf("%lld\n", pow2[i]);

// 3. 青木君勝利する区間を保存.

// 以下の区間を予想.

// [1, 1]

// [6, 9]

// [26, 41]

// [106, 109]

// ...

// [as, ae] と置いたとき,

// ae = -1 + (2 の 1乗) + (2 の 3乗) + (2 の 5乗) + ...

// as = ae - (2 の偶数乗) + 1

// と仮定？

// (2 の 60乗) … 1152921504606846976

vector<P> v;

LL as = 0, ae = -1;

repex(i, 1, MAX, 2){

ae = ae + pow2[i];

as = ae - pow2[i - 1] + 1;

v.pb({as, ae});

}

// rep(i, v.size()) printf("%lld %lld\n", v[i].a, v[i].b);

// 4. 判定.

bool aoki = false;

rep(i, v.size()){

if(N >= v[i].a && N <= v[i].b){

aoki = true;

break;

}

// 5. 出力.

printf("%s\n", aoki ? "Aoki" : "Takahashi");

return 0;

}

[入力例]
1

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

[入力例]
5

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

[入力例]
7

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

[入力例]
10

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

[入力例]
123456789123456789

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

[入力例]
25

[出力例]
Takahashi

[入力例]
123

[出力例]
Aoki

[入力例]
10921

[出力例]
Aoki

[入力例]
10922

[出力例]
Takahashi

[入力例]
111848105

[出力例]
Takahashi

[入力例]
111848106

[出力例]
Aoki

[入力例]
987654321987654321

[出力例]
Takahashi

[入力例]
3012345678901234567

[出力例]
Aoki

[入力例]

[出力例]

Aoki

※AtCoderテストケースより

[入力例]

[出力例]

Takahashi

※AtCoderテストケースより

[入力例]

[出力例]

Aoki

※AtCoderテストケースより

[入力例]

[出力例]

Takahashi

※AtCoderテストケースより

[入力例]

123456789123456789

[出力例]

Aoki

※AtCoderテストケースより

[入力例]

[出力例]

Takahashi

[入力例]

123

[出力例]

Aoki

[入力例]

10921

[出力例]

Aoki

[入力例]

10922

[出力例]

Takahashi

[入力例]

111848105

[出力例]

Takahashi

[入力例]

111848106

[出力例]

Aoki

[入力例]

987654321987654321

[出力例]

Takahashi

[入力例]

3012345678901234567

[出力例]

Aoki

■参照サイト
AtCoder Beginner Contest 027

2020年3月7日2020年3月7日

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

C++の練習を兼ねて, AtCoder Beginner Contest 027 の問題B (B – 島と橋) を解いてみた.

■感想.
1. 試行錯誤していたら, 累計和と橋の本数の関係に気付くことが出来たため, AC版となった.
※後から解説見たら, 同じ方針だったので, 良かったと思う.
2. 個人的には, 摩訶不思議な感じの問題に見えて, 非常に面白い問題と思った.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

#include <bits/stdc++.h>
using namespace std;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
int cum[111];

int main(){
    
    // 1. 入力情報.
    int N, a;
    scanf("%d", &N);
    rep(i, N){
        scanf("%d", &a);
        cum[i + 1] = cum[i] + a; // 累計和.
    }
    
    // 2. 平均人数 を 計算.
    int ave = cum[N] / N;
    
    // 3. 平均人数 に 島の個数 を かけた値が, 
    // 合計人数と異なる場合は, 橋の架け方によらず, 不可能.
    if(ave * N != cum[N]){
        puts("-1");
        return 0;
    }
    
    // 4. 橋が必要な島は, 累計和が, 平均人数の倍数 と 異なる島のように見える.
    int ans = 0;
    repx(i, 1, N + 1) if(cum[i] != ave * i) ans++;
    
    // 5. 出力.
    printf("%d\n", ans);
    return 0;
    
}

#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 cum[111];

int main(){

// 1. 入力情報.

int N, a;

scanf("%d", &N);

rep(i, N){

scanf("%d", &a);

cum[i + 1] = cum[i] + a; // 累計和.

}

// 2. 平均人数を計算.

int ave = cum[N] / N;

// 3. 平均人数に島の個数をかけた値が,

// 合計人数と異なる場合は, 橋の架け方によらず, 不可能.

if(ave * N != cum[N]){

puts("-1");

return 0;

}

// 4. 橋が必要な島は, 累計和が, 平均人数の倍数と異なる島のように見える.

int ans = 0;

repx(i, 1, N + 1) if(cum[i] != ave * i) ans++;

// 5. 出力.

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

return 0;

}

[入力例]
3
1 2 3

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

[入力例]
5
2 0 0 0 3

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

[入力例]
2
0 99

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

[入力例]
4
0 0 0 0

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

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

[出力例]
10

[入力例]
30
8 2 0 0 0 2 2 2 0 2 4 0 0 10 0 0 0 0 0 9 1 0 4 0 0 10 0 0 3 1

[出力例]
20

[入力例]
50
0 6 3 2 2 2 8 2 2 1 4 4 3 0 0 3 14 1 2 1 4 2 4 2 0 6 0 0 0 12 3 0 0 0 12 0 1 8 3 3 3 3 0 6 3 3 0 7 2 3

[出力例]
28

[入力例]

1 2 3

[出力例]

※AtCoderテストケースより

[入力例]

2 0 0 0 3

[出力例]

※AtCoderテストケースより

[入力例]

0 99

[出力例]

-1

※AtCoderテストケースより

[入力例]

0 0 0 0

[出力例]

※AtCoderテストケースより

[入力例]

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

[出力例]

[入力例]

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

[出力例]

[入力例]

0 6 3 2 2 2 8 2 2 1 4 4 3 0 0 3 14 1 2 1 4 2 4 2 0 6 0 0 0 12 3 0 0 0 12 0 1 8 3 3 3 3 0 6 3 3 0 7 2 3

[出力例]

■参照サイト
AtCoder Beginner Contest 027

2020年3月6日2020年3月6日

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

C++の練習を兼ねて, AtCoder Beginner Contest 028 の問題D (D – 乱数生成) を解いてみた.

■感想.
1. int型で提出したら, WAとなった, long long型で提出したら, AC版となった, 変数型に注意したいと思う(汗).
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

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

int main(){
    
    // 1. 入力情報.
    LL N, K;
    scanf("%lld %lld", &N, &K);
    
    // 2. 総数.
    LL t = N * N * N;
    
    // 3. 中央値が, K となるパターン.
    // 3-1. a < b < c で, b = K.
    LL p = 6 * (K - 1) * (N - K);
    
    // 3-2. a = b < c で, b = K.
    p += 3 * (N - K);
    
    // 3-3. a < b = c で, b = K.
    p += 3 * (K - 1);
    
    // 3-4. a = b = c で, b = K.
    p += 1;
    
    // 4. 出力.
    printf("%.20lf\n", (double)p / (double)t);
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

int main(){

// 1. 入力情報.

LL N, K;

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

// 2. 総数.

LL t = N * N * N;

// 3. 中央値が, K となるパターン.

// 3-1. a < b < c で, b = K.

LL p = 6 * (K - 1) * (N - K);

// 3-2. a = b < c で, b = K.

p += 3 * (N - K);

// 3-3. a < b = c で, b = K.

p += 3 * (K - 1);

// 3-4. a = b = c で, b = K.

p += 1;

// 4. 出力.

printf("%.20lf\n", (double)p / (double)t);

return 0;

}

[入力例]
3 2

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

[入力例]
3 1

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

[入力例]
765 573

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

[入力例]
54321 12345

[出力例]
0.00001939669378633539

[入力例]

3 2

[出力例]

0.48148148148148145475

※AtCoderテストケースより

[入力例]

3 1

[出力例]

0.25925925925925924487

※AtCoderテストケースより

[入力例]

765 573

[出力例]

0.00147697396984624381

※AtCoderテストケースより

[入力例]

54321 12345

[出力例]

0.00001939669378633539

■参照サイト
AtCoder Beginner Contest 028

2020年3月5日2020年3月5日

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

C++の練習を兼ねて, AtCoder Beginner Contest 029 の問題D (D – 1) を解いてみた.

■感想.
1. 現在見ている桁(cur) とその左側の桁に含まれる 1の個数(one) を考慮し, その加減算を行う条件を抽出するのに, 時間かかってしまった.

※なお, 解法イメージとしては, N = 123456 の場合,
1 ～ 100000
100001 ～ 110000, 110001 ～ 120000
120001 ～ 121000, 120001 ～ 122000, 122001 ～ 123000
～(略)～
123401 ～ 123410, 123411 ～ 123420, 123421 ～ 123430, 123431 ～ 123440, 123441 ～ 123450
123451 ～ 123456
のように, 区切りを設けて解いていく方針で実装した.

2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// コメントを修正して, 再提出.
#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--)
// c[0] … 1 ～      1:     1回
// c[1] … 1 ～     10:     2回
// c[2] … 1 ～    100:    21回 (= (c[1] - 1) * 10 + 10 + 1)
// c[3] … 1 ～   1000:   301回 (= (c[2] - 1) * 10 + 100 + 1)
// c[4] … 1 ～  10000:  4001回 (= (c[3] - 1) * 10 + 1000 + 1)
// c[5] … 1 ～ 100000: 50001回 (= (c[4] - 1) * 10 + 10000 + 1)
// ...
const LL c[] = {1, 2, 21, 301, 4001, 50001, 600001, 7000001, 80000001, 900000001, 10000000001, 200000000001};
const LL p10[] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000, 10000000000};

int main(){
    
    // 1. 入力情報.
    char a[22];
    scanf("%s", a);
    string N(a);
    
    // 2. '1' の 出現回数は？
    // -> 0 ～ (l - 1)桁 で 考える.
    int l = N.size();
    LL ans = 0;
    rep(i, l){
        // 2-0. 上限設定.
        int u = N[i] - '0';
        rep(j, u){
            // 2-1. 現在確認する桁.
            char cur = j + '0';
            
            // 2-2. i桁目よりも左側 の '1' の 個数.
            LL one = 0;
            rep(k, i) if(N[k] == '1') one++;
            
            // 2-3. i桁目よりも左側 の '1' の 個数 を カウント.
            ans += one * p10[l - 1 - i];
            
            // 2-4. 現在確認する桁が, '1' の 場合, 追加分 を カウント.
            ans += (p10[l - 1 - i] - 1) * (cur == '1');
            
            // 2-5. i桁目における c[l - 1 - i] を カウント.
            ans += c[l - 1 - i];
            
            // 2-6. i桁目が, '1' 以上 の 場合, 減算.
            ans -= (LL)(cur > '0');
        }
    }
    
    // 3. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// コメントを修正して, 再提出.

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

// c[0] … 1 ～ 1: 1回

// c[1] … 1 ～ 10: 2回

// c[2] … 1 ～ 100: 21回 (= (c[1] - 1) * 10 + 10 + 1)

// c[3] … 1 ～ 1000: 301回 (= (c[2] - 1) * 10 + 100 + 1)

// c[4] … 1 ～ 10000: 4001回 (= (c[3] - 1) * 10 + 1000 + 1)

// c[5] … 1 ～ 100000: 50001回 (= (c[4] - 1) * 10 + 10000 + 1)

// ...

const LL c[] = {1, 2, 21, 301, 4001, 50001, 600001, 7000001, 80000001, 900000001, 10000000001, 200000000001};

const LL p10[] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000, 10000000000};

int main(){

// 1. 入力情報.

char a[22];

scanf("%s", a);

string N(a);

// 2. '1' の出現回数は？

// -> 0 ～ (l - 1)桁で考える.

int l = N.size();

LL ans = 0;

rep(i, l){

// 2-0. 上限設定.

int u = N[i] - '0';

rep(j, u){

// 2-1. 現在確認する桁.

char cur = j + '0';

// 2-2. i桁目よりも左側の '1' の個数.

LL one = 0;

rep(k, i) if(N[k] == '1') one++;

// 2-3. i桁目よりも左側の '1' の個数をカウント.

ans += one * p10[l - 1 - i];

// 2-4. 現在確認する桁が, '1' の場合, 追加分をカウント.

ans += (p10[l - 1 - i] - 1) * (cur == '1');

// 2-5. i桁目における c[l - 1 - i] をカウント.

ans += c[l - 1 - i];

// 2-6. i桁目が, '1' 以上の場合, 減算.

ans -= (LL)(cur > '0');

}

// 3. 出力.

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

return 0;

}

[入力例]
12

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

[入力例]
345

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

[入力例]
999999999

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

[入力例]
123

[出力例]
57

[入力例]
213145

[出力例]
209127

[入力例]
654321

[出力例]
432373

[入力例]
314159265

[出力例]
354702389

[入力例]
888777666

[出力例]
812291337

[入力例]
301205670

[出力例]
341008408

[入力例]
1234567890

[出力例]
1429355270

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

345

[出力例]

175

※AtCoderテストケースより

[入力例]

999999999

[出力例]

900000000

※AtCoderテストケースより

[入力例]

123

[出力例]

[入力例]

213145

[出力例]

209127

[入力例]

654321

[出力例]

432373

[入力例]

314159265

[出力例]

354702389

[入力例]

888777666

[出力例]

812291337

[入力例]

301205670

[出力例]

341008408

[入力例]

1234567890

[出力例]

1429355270

■参照サイト
AtCoder Beginner Contest 029

2020年3月4日2020年3月4日

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

C++の練習を兼ねて, AtCoder Beginner Contest 157 の問題E (E – Simple String Queries) を解いてみた.

■感想.
1. 遅延評価セグメント木を使う必要があると思ったので, 下記のライブラリを拝借させて頂いた.
2. 遅延評価セグメント木の復習が出来たので, 良かった思う.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// コメント, ロジックを修正して再提出.
// ※※※ 以下のライブラリを使用(一部改変) ※※※.
// 遅延評価セグメント木をソラで書きたいあなたに.
// http://tsutaj.hatenablog.com/entry/2017/03/30/224339
// http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2236726
#include <bits/stdc++.h>
using namespace std;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back

struct LazySegmentTree{
private:
    int n;
    vector<int> node, lazy;
public:
    LazySegmentTree(vector<int> v){
        int sz = (int)v.size();
        n = 1; while(n < sz) n *= 2;
        node.resize(2 * n - 1);
        lazy.resize(2 * n - 1, 0);
        // 元配列 の 値 を, セグメント木のノード に 保存.
        rep(i, sz) node[i + n - 1] = v[i];
        repr(i, n - 2, 0) node[i] = node[i * 2 + 1] + node[i * 2 + 2];
    }
    void eval(int k, int l, int r){
        if(lazy[k] != 0) {
            node[k] += lazy[k];
            if(r - l > 1) {
                lazy[2 * k + 1] += lazy[k] / 2;
                lazy[2 * k + 2] += lazy[k] / 2;
            }
            lazy[k] = 0;
        }
    }
    void update(int a, int b, int x, int k = 0, int l = 0, int r = -1){
        if(r < 0) r = n;
        eval(k, l, r);
        if(b <= l || r <= a) return;
        if(a <= l && r <= b){
            lazy[k] += (r - l) * x;
            eval(k, l, r);
        }else{
            update(a, b, x, 2 * k + 1,           l, (l + r) / 2);
            update(a, b, x, 2 * k + 2, (l + r) / 2,           r);
            node[k] = max(node[2 * k + 1], node[2 * k + 2]);
        }
    }
    int query(int a, int b, int k = 0, int l = 0, int r = -1){
        if(r < 0) r = n;
        eval(k, l, r);
        if(b <= l || r <= a) return 0;
        if(a <= l && r <= b) return node[k];
        int vl = query(a, b, 2 * k + 1,           l, (l + r) / 2);
        int vr = query(a, b, 2 * k + 2, (l + r) / 2,           r);
        return max(vl, vr);
    }

};

int main(){
    
    // 1. 入力情報.
    int N, Q;
    char c[505050];
    scanf("%d %s %d", &N, c, &Q);
    
    // 2. 区間更新(遅延伝播セグメント木).
    LazySegmentTree seg(vector<int>(505050, 0));
    vector<LazySegmentTree> vSeg;
    rep(i, 26) vSeg.pb(seg);
    rep(j, N) vSeg[c[j] - 'a'].update(j, j + 1, 1);
    // rep(i, 26){
    //     rep(j, N) printf("%d ", vSeg[i].query(j, j + 1));
    //     puts("");
    // }
    
    // 3. 各クエリに回答.
    int n, iq, lq, rq, bef, cur, ans, bCnt, cCnt;
    char cq[5];
    rep(i, Q){
        scanf("%d", &n);
        if(n == 1){
            scanf("%d %s", &iq, cq);
            iq--;
            
            // 変更前の文字.
            bef = c[iq] - 'a';
            
            // 変更後の文字.
            cur = cq[0] - 'a';
            
            // 変更前文字の出現個数.
            bCnt = vSeg[bef].query(iq, iq + 1);
            
            // 変更前文字を減算.
            if(bCnt > 0) vSeg[bef].update(iq, iq + 1, -1);
            
            // 変更後文字の出現個数.
            cCnt = vSeg[cur].query(iq, iq + 1);
            
            // 変更後文字を加算.
            if(cCnt == 0) vSeg[cur].update(iq, iq + 1, 1);
            
            // 文字列を, 変更後文字 に 更新.
            c[iq] = cq[0];
        }else{
            scanf("%d %d", &lq, &rq);
            lq--, ans = 0;
            
            // 部分文字列(区間[lq, rq]) の 種類数は？
            rep(j, 26) ans += vSeg[j].query(lq, rq);
            
            // 出力.
            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

// コメント, ロジックを修正して再提出.

// ※※※ 以下のライブラリを使用(一部改変) ※※※.

// 遅延評価セグメント木をソラで書きたいあなたに.

// http://tsutaj.hatenablog.com/entry/2017/03/30/224339

// http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2236726

#include <bits/stdc++.h>

using namespace std;

#define repex(i, a, b, c) for(int i = a; i < b; i += c)

#define repx(i, a, b) repex(i, a, b, 1)

#define rep(i, n) repx(i, 0, n)

#define repr(i, a, b) for(int i = a; i >= b; i--)

#define pb push_back

struct LazySegmentTree{

private:

int n;

vector<int> node, lazy;

public:

LazySegmentTree(vector<int> v){

int sz = (int)v.size();

n = 1; while(n < sz) n *= 2;

node.resize(2 * n - 1);

lazy.resize(2 * n - 1, 0);

// 元配列の値を, セグメント木のノードに保存.

rep(i, sz) node[i + n - 1] = v[i];

repr(i, n - 2, 0) node[i] = node[i * 2 + 1] + node[i * 2 + 2];

}

void eval(int k, int l, int r){

if(lazy[k] != 0) {

node[k] += lazy[k];

if(r - l > 1) {

lazy[2 * k + 1] += lazy[k] / 2;

lazy[2 * k + 2] += lazy[k] / 2;

}

lazy[k] = 0;

}

void update(int a, int b, int x, int k = 0, int l = 0, int r = -1){

if(r < 0) r = n;

eval(k, l, r);

if(b <= l || r <= a) return;

if(a <= l && r <= b){

lazy[k] += (r - l) * x;

eval(k, l, r);

}else{

update(a, b, x, 2 * k + 1, l, (l + r) / 2);

update(a, b, x, 2 * k + 2, (l + r) / 2, r);

node[k] = max(node[2 * k + 1], node[2 * k + 2]);

}

int query(int a, int b, int k = 0, int l = 0, int r = -1){

if(r < 0) r = n;

eval(k, l, r);

if(b <= l || r <= a) return 0;

if(a <= l && r <= b) return node[k];

int vl = query(a, b, 2 * k + 1, l, (l + r) / 2);

int vr = query(a, b, 2 * k + 2, (l + r) / 2, r);

return max(vl, vr);

}

};

int main(){

// 1. 入力情報.

int N, Q;

char c[505050];

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

// 2. 区間更新(遅延伝播セグメント木).

LazySegmentTree seg(vector<int>(505050, 0));

vector<LazySegmentTree> vSeg;

rep(i, 26) vSeg.pb(seg);

rep(j, N) vSeg[c[j] - 'a'].update(j, j + 1, 1);

// rep(i, 26){

// rep(j, N) printf("%d ", vSeg[i].query(j, j + 1));

// puts("");

// }

// 3. 各クエリに回答.

int n, iq, lq, rq, bef, cur, ans, bCnt, cCnt;

char cq[5];

rep(i, Q){

scanf("%d", &n);

if(n == 1){

scanf("%d %s", &iq, cq);

iq--;

// 変更前の文字.

bef = c[iq] - 'a';

// 変更後の文字.

cur = cq[0] - 'a';

// 変更前文字の出現個数.

bCnt = vSeg[bef].query(iq, iq + 1);

// 変更前文字を減算.

if(bCnt > 0) vSeg[bef].update(iq, iq + 1, -1);

// 変更後文字の出現個数.

cCnt = vSeg[cur].query(iq, iq + 1);

// 変更後文字を加算.

if(cCnt == 0) vSeg[cur].update(iq, iq + 1, 1);

// 文字列を, 変更後文字に更新.

c[iq] = cq[0];

}else{

scanf("%d %d", &lq, &rq);

lq--, ans = 0;

// 部分文字列(区間[lq, rq]) の種類数は？

rep(j, 26) ans += vSeg[j].query(lq, rq);

// 出力.

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

}

return 0;

}

[入力例]
7
abcdbbd
6
2 3 6
1 5 z
2 1 1
1 4 a
1 7 d
2 1 7

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

[入力例]
1000
ggqtrvenemxwthumrlocwlctxxmbsooujmfccxllbwwykqvtwvcngsqxasbnmclqtsgsgxduumiplpoiipdwdejnmenbstbrnkbpkdgcdvdhlzeypkzakudjkzyggsfbpbivwgpsgxvkmbpgqykbzhwdagvcelocxoqxbaxzfjcccnwiwvddazswpizkwynkgavmngjvwwwzlyqvbygzwxbdvrdvodahopopgrnekzckoltfggxzaaqnzwdlxeeyxgrnkukaicrvykpylgfbgsxuthmmyehsuhioreqvlugbfeohfrenolimitmbvbwroeubkoufsmzrdlxfoakpjzvoieqvparrggzgljyytkaaikyjcpdoomeclhlczuahfdgjtcqxjztoigsrrduxhmvzxhksceuuumzlerqpomsaixwfbbjjawyqxziizpnpnhehiqxnxqfzeoruqfayxxebstkuzucanllavjsiyxhrorhgokqqdhzvfnubulwytmnqstoqsyeawpdeorrjcazpjknvofmqdapjmynbsmtisvjjqqhfgttvtzgozjnyyrulifotqwsdtvrvyadjpjwaekqpkftuiwmkswvfzgmomkoyskjgpvocsyierkwbnvbbejaaiprhsuhuntqetlchpcqklbsxapnpswhnvjufojhacomgyciblelllbtrrhilwykknjedzfqcqmurlpgbucydtlppevoupsctnefcdcfcyarhypwcughjnsaampromcofiyzklqfovbomtdmvyiujzwuuiawqufemluzzrvfyujylzmzjmocfuybaugumsnotomafbpetgakrrpngnooxvrperwzpgqssxutfjfwbaayermrhhlszodmkelfkqofufeqqdybflhcgmfwpppurkyzwptrlvvubsmvfkdhlxraxirqvvnhvagsegpkpdivdmtjeyxikbhiibhygiwumilqwzyzpgrja
100
2 85 132
1 279 a
1 302 k
1 561 v
2 10 369
2 41 126
1 213 q
1 306 d
2 43 82
1 685 o
1 195 a
1 79 l
1 710 z
1 752 n
2 21 51
2 45 172
2 64 360
1 264 y
1 19 w
2 95 182
1 176 v
1 591 c
2 46 108
2 36 413
1 742 c
2 16 31
2 35 185
2 84 376
1 101 k
1 373 x
2 47 223
1 138 t
1 622 a
1 215 t
2 3 287
1 540 e
1 456 p
2 59 386
1 787 s
1 618 k
2 63 225
1 244 k
1 603 w
1 744 u
1 734 i
2 30 308
1 342 m
1 276 p
1 764 a
2 24 174
1 156 s
2 78 180
1 650 t
1 574 z
1 621 a
1 32 v
2 73 240
1 426 p
2 1 388
1 286 r
1 777 d
2 80 254
1 704 d
2 20 185
1 532 e
1 62 l
2 50 200
1 606 w
2 82 283
2 1 98
1 608 w
1 36 x
1 553 w
2 64 195
1 739 r
2 43 300
1 99 w
1 336 g
2 89 190
2 37 242
1 212 r
1 751 j
1 624 i
2 54 205
1 298 p
2 1 128
1 764 t
2 95 152
2 31 420
1 105 l
2 2 22
1 594 r
1 406 p
2 97 130
2 43 380
1 589 u
1 112 k
1 177 g
1 505 f
2 28 147

[出力例]
22
26
25
20
16
26
26
25
22
26
10
26
26
26
26
26
26
26
26
26
26
26
26
26
26
26
25
26
26
26
26
26
26
24
26
14
19
26
26

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

[入力例]

abcdbbd

2 3 6

1 5 z

2 1 1

1 4 a

1 7 d

2 1 7

[出力例]

※AtCoderテストケースより

[入力例]

1000

ggqtrvenemxwthumrlocwlctxxmbsooujmfccxllbwwykqvtwvcngsqxasbnmclqtsgsgxduumiplpoiipdwdejnmenbstbrnkbpkdgcdvdhlzeypkzakudjkzyggsfbpbivwgpsgxvkmbpgqykbzhwdagvcelocxoqxbaxzfjcccnwiwvddazswpizkwynkgavmngjvwwwzlyqvbygzwxbdvrdvodahopopgrnekzckoltfggxzaaqnzwdlxeeyxgrnkukaicrvykpylgfbgsxuthmmyehsuhioreqvlugbfeohfrenolimitmbvbwroeubkoufsmzrdlxfoakpjzvoieqvparrggzgljyytkaaikyjcpdoomeclhlczuahfdgjtcqxjztoigsrrduxhmvzxhksceuuumzlerqpomsaixwfbbjjawyqxziizpnpnhehiqxnxqfzeoruqfayxxebstkuzucanllavjsiyxhrorhgokqqdhzvfnubulwytmnqstoqsyeawpdeorrjcazpjknvofmqdapjmynbsmtisvjjqqhfgttvtzgozjnyyrulifotqwsdtvrvyadjpjwaekqpkftuiwmkswvfzgmomkoyskjgpvocsyierkwbnvbbejaaiprhsuhuntqetlchpcqklbsxapnpswhnvjufojhacomgyciblelllbtrrhilwykknjedzfqcqmurlpgbucydtlppevoupsctnefcdcfcyarhypwcughjnsaampromcofiyzklqfovbomtdmvyiujzwuuiawqufemluzzrvfyujylzmzjmocfuybaugumsnotomafbpetgakrrpngnooxvrperwzpgqssxutfjfwbaayermrhhlszodmkelfkqofufeqqdybflhcgmfwpppurkyzwptrlvvubsmvfkdhlxraxirqvvnhvagsegpkpdivdmtjeyxikbhiibhygiwumilqwzyzpgrja

100

2 85 132

1 279 a

1 302 k

1 561 v

2 10 369

2 41 126

1 213 q

1 306 d

2 43 82

1 685 o

1 195 a

1 79 l

1 710 z

1 752 n

2 21 51

2 45 172

2 64 360

1 264 y

1 19 w

2 95 182

1 176 v

1 591 c

2 46 108

2 36 413

1 742 c

2 16 31

2 35 185

2 84 376

1 101 k

1 373 x

2 47 223

1 138 t

1 622 a

1 215 t

2 3 287

1 540 e

1 456 p

2 59 386

1 787 s

1 618 k

2 63 225

1 244 k

1 603 w

1 744 u

1 734 i

2 30 308

1 342 m

1 276 p

1 764 a

2 24 174

1 156 s

2 78 180

1 650 t

1 574 z

1 621 a

1 32 v

2 73 240

1 426 p

2 1 388

1 286 r

1 777 d

2 80 254

1 704 d

2 20 185

1 532 e

1 62 l

2 50 200

1 606 w

2 82 283

2 1 98

1 608 w

1 36 x

1 553 w

2 64 195

1 739 r

2 43 300

1 99 w

1 336 g

2 89 190

2 37 242

1 212 r

1 751 j

1 624 i

2 54 205

1 298 p

2 1 128

1 764 t

2 95 152

2 31 420

1 105 l

2 2 22

1 594 r

1 406 p

2 97 130

2 43 380

1 589 u

1 112 k

1 177 g

1 505 f

2 28 147

[出力例]

■参照サイト
AtCoder Beginner Contest 157
遅延評価セグメント木をソラで書きたいあなたに

2020年3月2日

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

C++の練習を兼ねて, AtCoder Beginner Contest 157 の問題D (D – Friend Suggestions) を解いてみた.

■感想.
1. 解説見る前に, AC版となったので, 良かったと思う, 一番時間を使った点は, ブロック関係を考慮して, 減算するためのロジックに気付くところだったと思う.
2. 幅優先探索の復習が出来たので, 良かった思う.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

#include <bits/stdc++.h>
using namespace std;
using vvi = vector<vector<int>>;
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 a first
#define b second
#define pb push_back
const int MAX = 101010;
int connection[MAX]; // 連結成分番号を保存.
int appearance[MAX]; // 連結成分番号の出現回数.
int ans[MAX];
vvi F(MAX);  // 友達関係.
vector<P> B; // ブロック関係.

// グラフを幅優先探索する.
// https://ja.wikipedia.org/wiki/幅優先探索
// ※bfsの動作確認用.
// @param G: グラフ.
// @param s: グラフの探索開始頂点.
// @param l: 連結成分番号(※1以上).
// @return: 特に無し.
void bfs(vvi &G, int s, int l){
    
    // 1. 空のキュー.
    queue<int> q;
    
    // 2. 訪問済みフラグ設定.
    connection[s] = l;
    
    // 3. 探索地点 s をキュー q に追加.
    q.push(s);
    while(!q.empty()){
        
        // 4. キューから取り出す.
        int u = q.front();
        q.pop();
        
        // 5. 取り出した要素を処理.
        for(auto &e : G[u]){
            
            // 6. 訪問済であれば, 処理をスキップ.
            if(connection[e] > 0)            continue;
            if(connection[e] == 0 && e != s) connection[e] = l, q.push(e);
        }
    }
    return;
}

int main(){
    
    // 1. 入力情報.
    int N, M, K;
    scanf("%d %d %d", &N, &M, &K);
    int a, b;
    rep(i, M){
        scanf("%d %d", &a, &b);
        a--, b--;
        F[a].pb(b);
        F[b].pb(a);
    }
    rep(i, K){
        scanf("%d %d", &a, &b);
        a--, b--;
        B.pb({a, b});
    }
    
    // 2. 各頂点に対する連結成分番号を設定.
    int id = 0;
    rep(i, N) if(connection[i] == 0) bfs(F, i, ++id);
    // rep(i, N) printf("i=%d con=%d\n", i, connection[i]);
    
    // 3. 各連結成分番号の出現回数を計算.
    rep(i, N) appearance[connection[i]]++;
    
    // 4. 友達候補の集計.
    rep(i, N){
        // 友達候補の数を計算.
        ans[i] += appearance[connection[i]];
        // 自分自身は, 減算.
        ans[i]--;
        // 友達関係を減算.
        ans[i] -= F[i].size();
    }
    
    // 5. ブロック関係を減算.
    rep(i, K){
        a = B[i].a;
        b = B[i].b;
        // 同じ連結成分にある場合だけ, 減算.
        if(connection[a] == connection[b]) ans[a]--, ans[b]--;
    }
    
    // 6. 出力.
    rep(i, N){
        printf("%d", ans[i]);
        if(i < N - 1) printf(" ");
    }
    return 0;
    
}

100

101

102

103

104

#include <bits/stdc++.h>

using namespace std;

using vvi = vector<vector<int>>;

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 a first

#define b second

#define pb push_back

const int MAX = 101010;

int connection[MAX]; // 連結成分番号を保存.

int appearance[MAX]; // 連結成分番号の出現回数.

int ans[MAX];

vvi F(MAX); // 友達関係.

vector<P> B; // ブロック関係.

// グラフを幅優先探索する.

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

// ※bfsの動作確認用.

// @param G: グラフ.

// @param s: グラフの探索開始頂点.

// @param l: 連結成分番号(※1以上).

// @return: 特に無し.

void bfs(vvi &G, int s, int l){

// 1. 空のキュー.

queue<int> q;

// 2. 訪問済みフラグ設定.

connection[s] = l;

// 3. 探索地点 s をキュー q に追加.

q.push(s);

while(!q.empty()){

// 4. キューから取り出す.

int u = q.front();

q.pop();

// 5. 取り出した要素を処理.

for(auto &e : G[u]){

// 6. 訪問済であれば, 処理をスキップ.

if(connection[e] > 0) continue;

if(connection[e] == 0 && e != s) connection[e] = l, q.push(e);

}

return;

}

int main(){

// 1. 入力情報.

int N, M, K;

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

int a, b;

rep(i, M){

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

a--, b--;

F[a].pb(b);

F[b].pb(a);

}

rep(i, K){

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

a--, b--;

B.pb({a, b});

}

// 2. 各頂点に対する連結成分番号を設定.

int id = 0;

rep(i, N) if(connection[i] == 0) bfs(F, i, ++id);

// rep(i, N) printf("i=%d con=%d\n", i, connection[i]);

// 3. 各連結成分番号の出現回数を計算.

rep(i, N) appearance[connection[i]]++;

// 4. 友達候補の集計.

rep(i, N){

// 友達候補の数を計算.

ans[i] += appearance[connection[i]];

// 自分自身は, 減算.

ans[i]--;

// 友達関係を減算.

ans[i] -= F[i].size();

}

// 5. ブロック関係を減算.

rep(i, K){

a = B[i].a;

b = B[i].b;

// 同じ連結成分にある場合だけ, 減算.

if(connection[a] == connection[b]) ans[a]--, ans[b]--;

}

// 6. 出力.

rep(i, N){

printf("%d", ans[i]);

if(i < N - 1) printf(" ");

}

return 0;

}

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

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

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

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

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

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

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

[出力例]
0 2 2 3 3

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

[出力例]
16 13 17 14 14 15 15 15 17 14 13 15 15 0 15 17 14 15 14 16

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

[出力例]
2 1 1 2 1 0 1 2 1 1 2 0 0 0 0 0 0 0 1 0 1

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

[出力例]
9 9 9 8 9 9 9 9 1 1 8 9 0 0 1 1 10 10 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

[入力例]

4 4 1

2 1

1 3

3 2

3 4

4 1

[出力例]

0 1 0 1

※AtCoderテストケースより

[入力例]

5 10 0

1 2

1 3

1 4

1 5

3 2

2 4

2 5

4 3

5 3

4 5

[出力例]

0 0 0 0 0

※AtCoderテストケースより

[入力例]

10 9 3

10 1

6 7

8 2

2 5

8 4

7 3

10 9

6 4

5 8

2 6

7 5

3 1

[出力例]

1 3 5 4 3 3 3 3 1 0

※AtCoderテストケースより

[入力例]

5 4 1

1 2

1 3

1 4

1 5

2 3

[出力例]

0 2 2 3 3

[入力例]

20 25 4

18 10

10 1

6 7

11 2

17 11

8 2

13 1

19 18

18 17

2 5

6 19

12 15

8 4

11 10

7 3

12 11

10 9

6 4

16 17

20 5

19 13

2 13

4 17

5 15

8 15

4 20

7 2

12 19

5 11

[出力例]

16 13 17 14 14 15 15 15 17 14 13 15 15 0 15 17 14 15 14 16

[入力例]

21 11 5

1 2

3 2

4 3

6 5

8 9

7 6

11 10

10 9

21 20

20 19

18 17

12 3

15 3

16 4

14 5

13 6

[出力例]

2 1 1 2 1 0 1 2 1 1 2 0 0 0 0 0 0 0 1 0 1

[入力例]

19 16 6

12 1

12 2

5 1

3 2

5 4

4 3

7 4

15 13

13 10

17 11

18 11

11 8

8 6

6 7

16 14

14 9

19 17

19 18

10 7

7 9

9 3

10 5

[出力例]

9 9 9 8 9 9 9 9 1 1 8 9 0 0 1 1 10 10 0

■参照サイト
AtCoder Beginner Contest 157

2020年3月1日

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

C++の練習を兼ねて, AtCoder Beginner Contest 030 の問題D (D – へんてこ辞書) を解いてみた.

■感想.
1. 解説見る前に, AC版となったので, 良かったと思う.
2. 但し, 細かい条件をいくつも考慮する必要があり, 実装で, 大変苦労した(汗).
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

#include <bits/stdc++.h>
using namespace std;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
const int MAX = 101010;
char k[MAX];
int b[MAX], loop[MAX], rLoop[MAX], mod[MAX];

int main(){
    
    // 1. 入力情報.
    int N, a;
    scanf("%d %d %s", &N, &a, k);
    rep(i, N){
        int tb;
        scanf("%d", &tb);
        b[i + 1] = tb;
    }
    int kl = strlen(k);
    
    // 2. 周期を確認.
    int cur = a, bef = 0, index = 1, t = 0;
    while(loop[cur] == 0 && index < MAX){
        // 2-1. 訪問済みを設定.
        loop[cur] = index;
        
        // 2-2. loop参照用に設定.
        rLoop[index] = cur;
        
        // 2-3. 前回分を保存.
        bef = cur;
        
        // 2-4. 次の単語を設定.
        cur = b[cur];
        
        // 2-5. 出現の順位を更新.
        index++;
    }
    t = loop[bef] - loop[cur] + 1; // 周期を設定.
    // rep(i, N + 1) printf("%d ", loop[i]);
    // puts("");
    // rep(i, N + 1) printf("%d ", rLoop[i]);
    // puts("");
    // printf("bef=%d cur=%d t=%d\n", bef, cur, t);
    // puts("");
    
    // 3. 周期に入るまでのStep数(loop[bef] - t).
    // ex.
    // 9 5
    // 12
    // 2 3 1 2 6 7 8 9 4
    // (step1)  5 -> 6
    // (step2)  6 -> 7
    // (step3)  7 -> 8
    // (step4)  8 -> 9
    // (step5)  9 -> 4
    // (step6)  4 -> 2 ※ 周期に入る直前(s = 6)
    // (step7)  2 -> 3
    // (step8)  3 -> 1
    // (step9)  1 -> 2 ※ 周期1回目終了(t = 3)
    // ... ～(略)～ ...
    // -> この場合, s = 6, t = 3 と見ることが出来る.
    int s = loop[bef] - t;
    int sl = to_string(s).size();
    // printf("s=%d t=%d\n", s, t);
    
    // 4. 10 の べき乗に対して, 周期で割った余りを事前計算.
    mod[0] = (1 % t);
    rep(i, MAX - 1) mod[i + 1] = (10 * mod[i]) % t;
    
    // 5. k Step を 確認.
    // 5-1. kl が sl 以下 の 場合.
    int ans = -1;
    if(kl <= sl){
        int nk = 0;
        rep(i, kl) nk *= 10, nk += k[i] - '0';
        if(nk <= s){
            ans = b[rLoop[nk]];
        }else{
            // 周期部分を抽出.
            nk -= s;
            // 剰余に変換.
            nk = (nk % t == 0) ? t : (nk % t);
            // 周期に入る直前 + 周期部分 で 取得.
            ans = b[rLoop[s + nk]];
        }
    }
    
    // 5-2. kl が sl より大きい場合.
    if(kl > sl){
        // (sl + 1) ～ kl桁 まで.
        int nsk = 0;
        rep(i, kl - sl) nsk += (k[i] - '0') * mod[kl - 1 - i], nsk %= t;
        
        // 1 ～ sl桁 まで.
        int nk = 0;
        repx(i, kl - sl, kl) nk *= 10, nk += k[i] - '0';
        
        // nk と s を 比較.
        if(nk >= s){
            // 周期部分を抽出.
            int n = nk - s;
            n += nsk;
            // 剰余に変換.
            n = (n % t == 0) ? t : (n % t);
            // 周期に入る直前 + 周期部分 で 取得.
            ans = b[rLoop[s + n]];
        }else{
            // 周期に入る直前における戻り分.
            int bs = nk - s; // 負の整数.
            // 周期部分で換算(bs回戻り).
            bs %= t;
            // 周期に入る直前 + 周期部分 で 取得.
            int n = nsk + bs;
            if(n < 0) n += t;
            n = (n % t == 0) ? t : (n % t);
            ans = b[rLoop[s + n]];
        }
    }
    
    // 6. 出力.
    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

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

const int MAX = 101010;

char k[MAX];

int b[MAX], loop[MAX], rLoop[MAX], mod[MAX];

int main(){

// 1. 入力情報.

int N, a;

scanf("%d %d %s", &N, &a, k);

rep(i, N){

int tb;

scanf("%d", &tb);

b[i + 1] = tb;

}

int kl = strlen(k);

// 2. 周期を確認.

int cur = a, bef = 0, index = 1, t = 0;

while(loop[cur] == 0 && index < MAX){

// 2-1. 訪問済みを設定.

loop[cur] = index;

// 2-2. loop参照用に設定.

rLoop[index] = cur;

// 2-3. 前回分を保存.

bef = cur;

// 2-4. 次の単語を設定.

cur = b[cur];

// 2-5. 出現の順位を更新.

index++;

}

t = loop[bef] - loop[cur] + 1; // 周期を設定.

// rep(i, N + 1) printf("%d ", loop[i]);

// puts("");

// rep(i, N + 1) printf("%d ", rLoop[i]);

// puts("");

// printf("bef=%d cur=%d t=%d\n", bef, cur, t);

// puts("");

// 3. 周期に入るまでのStep数(loop[bef] - t).

// ex.

// 9 5

// 12

// 2 3 1 2 6 7 8 9 4

// (step1) 5 -> 6

// (step2) 6 -> 7

// (step3) 7 -> 8

// (step4) 8 -> 9

// (step5) 9 -> 4

// (step6) 4 -> 2 ※ 周期に入る直前(s = 6)

// (step7) 2 -> 3

// (step8) 3 -> 1

// (step9) 1 -> 2 ※ 周期1回目終了(t = 3)

// ... ～(略)～ ...

// -> この場合, s = 6, t = 3 と見ることが出来る.

int s = loop[bef] - t;

int sl = to_string(s).size();

// printf("s=%d t=%d\n", s, t);

// 4. 10 のべき乗に対して, 周期で割った余りを事前計算.

mod[0] = (1 % t);

rep(i, MAX - 1) mod[i + 1] = (10 * mod[i]) % t;

// 5. k Step を確認.

// 5-1. kl が sl 以下の場合.

int ans = -1;

if(kl <= sl){

int nk = 0;

rep(i, kl) nk *= 10, nk += k[i] - '0';

if(nk <= s){

ans = b[rLoop[nk]];

}else{

// 周期部分を抽出.

nk -= s;

// 剰余に変換.

nk = (nk % t == 0) ? t : (nk % t);

// 周期に入る直前 + 周期部分で取得.

ans = b[rLoop[s + nk]];

}

// 5-2. kl が sl より大きい場合.

if(kl > sl){

// (sl + 1) ～ kl桁まで.

int nsk = 0;

rep(i, kl - sl) nsk += (k[i] - '0') * mod[kl - 1 - i], nsk %= t;

// 1 ～ sl桁まで.

int nk = 0;

repx(i, kl - sl, kl) nk *= 10, nk += k[i] - '0';

// nk と s を比較.

if(nk >= s){

// 周期部分を抽出.

int n = nk - s;

n += nsk;

// 剰余に変換.

n = (n % t == 0) ? t : (n % t);

// 周期に入る直前 + 周期部分で取得.

ans = b[rLoop[s + n]];

}else{

// 周期に入る直前における戻り分.

int bs = nk - s; // 負の整数.

// 周期部分で換算(bs回戻り).

bs %= t;

// 周期に入る直前 + 周期部分で取得.

int n = nsk + bs;

if(n < 0) n += t;

n = (n % t == 0) ? t : (n % t);

ans = b[rLoop[s + n]];

}

// 6. 出力.

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

return 0;

}

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

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

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

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

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

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

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

[出力例]
2

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

[出力例]
8

[入力例]
50 25
123
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 1 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 16

[出力例]
21

[入力例]
50 25
135
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 1 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 16

[出力例]
10

[入力例]
50 25
18
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 1 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 16

[出力例]
43

[入力例]
50 25
93
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 1 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 16

[出力例]
14

[入力例]
50 25
1234567890987654321
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 1 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 16

[出力例]
10

[入力例]
50 25
100
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 1 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 16

[出力例]
21

[入力例]
50 25
31415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679821480865132823066470938446095505822317253594081284811174502841027019385211055596446229489549303819644288109756659334461284756482337867831652712019091456485669234603486104543266482133936072602491412737245870066063155881748815209209628292540917153643678925903600113305305488204665213841469519415116094330572703657595919530921861173819326117931051185480744623799627495673518857527248912279381830119491
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 1 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 16

[出力例]
21

[入力例]

6 4

2 3 1 2 6 5

[出力例]

※AtCoderテストケースより

[入力例]

4 1

100000000000000000000

2 3 4 1

[出力例]

※AtCoderテストケースより

[入力例]

8 1

2 3 4 5 3 2 4 5

[出力例]

※AtCoderテストケースより

[入力例]

9 5

2 3 1 2 6 7 8 9 4

[出力例]

[入力例]

9 5

2 3 1 2 6 7 8 9 4

[出力例]

[入力例]

50 25

123

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 1 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 16

[出力例]

[入力例]

50 25

135

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 1 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 16

[出力例]

[入力例]

50 25

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 1 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 16

[出力例]

[入力例]

50 25

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 1 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 16

[出力例]

[入力例]

50 25

1234567890987654321

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 1 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 16

[出力例]

[入力例]

50 25

100

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 1 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 16

[出力例]

[入力例]

50 25

31415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679821480865132823066470938446095505822317253594081284811174502841027019385211055596446229489549303819644288109756659334461284756482337867831652712019091456485669234603486104543266482133936072602491412737245870066063155881748815209209628292540917153643678925903600113305305488204665213841469519415116094330572703657595919530921861173819326117931051185480744623799627495673518857527248912279381830119491

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 1 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 16

[出力例]

■参照サイト
AtCoder Beginner Contest 030

C++の練習を兼ねて, AtCoder Beginner Contest 158 の 問題D (D – String Formation) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 027 の 問題C (C – 倍々ゲーム) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 027 の 問題B (B – 島と橋) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 028 の 問題D (D – 乱数生成) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 029 の 問題D (D – 1) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 157 の 問題E (E – Simple String Queries) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 157 の 問題D (D – Friend Suggestions) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 030 の 問題D (D – へんてこ辞書) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 158 の問題D (D – String Formation) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 027 の問題C (C – 倍々ゲーム) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 027 の問題B (B – 島と橋) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 028 の問題D (D – 乱数生成) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 029 の問題D (D – 1) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 157 の問題E (E – Simple String Queries) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 157 の問題D (D – Friend Suggestions) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 030 の問題D (D – へんてこ辞書) を解いてみた.