C++ | 個人用メモ帳

2021年6月20日

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

C++の練習を兼ねて, AtCoder Beginner Contest 206 の問題C (Swappable) ～問題D (KAIBUNsyo) を解いてみた.

■感想.
1. 規則性が抽出できたので, AC版に到達できたと思う.
2. 幅優先探索の復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 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 a first
#define b second

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    map<LL, LL> m;
    rep(i, N){
        LL a;
        scanf("%lld", &a);
        m[a]++;
    }
    
    // 2. 条件を満たす整数の組をカウント.
    LL ans = (LL)N * (LL)(N - 1) / 2LL;
    for(auto &p : m) if(p.b > 1) ans -= p.b * (p.b - 1) / 2;
    
    // 3. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

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

#define b second

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

map<LL, LL> m;

rep(i, N){

LL a;

scanf("%lld", &a);

m[a]++;

}

// 2. 条件を満たす整数の組をカウント.

LL ans = (LL)N * (LL)(N - 1) / 2LL;

for(auto &p : m) if(p.b > 1) ans -= p.b * (p.b - 1) / 2;

// 3. 出力.

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

return 0;

}

[入力例]
3
1 7 1

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

[入力例]
10
1 10 100 1000 10000 100000 1000000 10000000 100000000 1000000000

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

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

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

[入力例]
50
123 106 25 45 57 77 113 48 90 105 70 54 74 68 32 55 89 66 83 56 113 114 87 26 66 109 123 71 28 5 25 109 101 39 46 26 61 122 104 48 85 22 51 26 17 107 22 114 92 13

[出力例]
1214

[入力例]

1 7 1

[出力例]

※AtCoderテストケースより

[入力例]

1 10 100 1000 10000 100000 1000000 10000000 100000000 1000000000

[出力例]

※AtCoderテストケースより

[入力例]

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

[出力例]

173

※AtCoderテストケースより

[入力例]

123 106 25 45 57 77 113 48 90 105 70 54 74 68 32 55 89 66 83 56 113 114 87 26 66 109 123 71 28 5 25 109 101 39 46 26 61 122 104 48 85 22 51 26 17 107 22 114 92 13

[出力例]

1214

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
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
int a[202020];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N){
        scanf("%d", &a[i]);
        a[i]--;
    }
    
    // 2. グラフ作成.
    vvi G(202020);
    rep(i, N / 2){
        // 2-1. 回文を構成していない要素を, 辺に追加.
        if(a[i] != a[N - 1 - i]){
            G[a[i]].pb(a[N - 1 - i]);
            G[a[N - 1 - i]].pb(a[i]);
        }
    }
    
    // 3. グラフを連結成分に分解.
    // https://ja.wikipedia.org/wiki/幅優先探索
    auto bfs = [&](vvi &G, int s, int* c, int l){
        // 3-1. 空のキュー.
        queue<int> q;
        
        // 3-2. 連結成分番号を設定.
        c[s] = l;
        
        // 3-3. 探索地点 s をキュー q に追加.
        q.push(s);
        while(!q.empty()){
            // 3-4. キューから取り出す.
            int u = q.front();
            q.pop();
            
            // 3-5. 取り出した要素を処理.
            for(auto &e : G[u]){
                // 3-6. 訪問済であれば, 処理をスキップ.
                if(c[e])   continue;
                if(e != s) c[e] = l, q.push(e);
            }
        }
        return;
    };
    int b[202020], c[202020], idx = 0;
    rep(i, 202020) b[i] = c[i] = 0;
    rep(i, 202020) if(!c[i]) bfs(G, i, c, ++idx);
    
    // 4. 連結成分の要素数を保存し, カウント.
    int ans = 0;
    rep(i, 202020) b[c[i]]++;
    rep(i, 202020) if(b[i] > 1) ans += b[i] - 1;
    
    // 5. 出力.
    printf("%d\n", ans);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

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

int a[202020];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

rep(i, N){

scanf("%d", &a[i]);

a[i]--;

}

// 2. グラフ作成.

vvi G(202020);

rep(i, N / 2){

// 2-1. 回文を構成していない要素を, 辺に追加.

if(a[i] != a[N - 1 - i]){

G[a[i]].pb(a[N - 1 - i]);

G[a[N - 1 - i]].pb(a[i]);

}

// 3. グラフを連結成分に分解.

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

auto bfs = [&](vvi &G, int s, int* c, int l){

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

queue<int> q;

// 3-2. 連結成分番号を設定.

c[s] = l;

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

q.push(s);

while(!q.empty()){

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

int u = q.front();

q.pop();

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

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

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

if(c[e]) continue;

if(e != s) c[e] = l, q.push(e);

}

return;

};

int b[202020], c[202020], idx = 0;

rep(i, 202020) b[i] = c[i] = 0;

rep(i, 202020) if(!c[i]) bfs(G, i, c, ++idx);

// 4. 連結成分の要素数を保存し, カウント.

int ans = 0;

rep(i, 202020) b[c[i]]++;

rep(i, 202020) if(b[i] > 1) ans += b[i] - 1;

// 5. 出力.

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

return 0;

}

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

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

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

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

[入力例]
1
200000

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

[入力例]
7
5 6 8 11 7 13 5

[出力例]
2

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

[出力例]
5

[入力例]
50
35 72 56 75 25 88 107 66 86 13 32 20 4 30 102 15 65 89 78 53 71 110 54 57 107 107 104 64 11 93 56 22 73 21 84 96 108 59 22 38 110 51 39 53 26 20 84 111 74 20

[出力例]
24

[入力例]

1 5 3 2 5 2 3 1

[出力例]

※AtCoderテストケースより

[入力例]

1 2 3 4 1 2 3

[出力例]

※AtCoderテストケースより

[入力例]

200000

[出力例]

※AtCoderテストケースより

[入力例]

5 6 8 11 7 13 5

[出力例]

[入力例]

9 9 7 4 8 3 4 1 7 6 10 8 8 4 7

[出力例]

[入力例]

35 72 56 75 25 88 107 66 86 13 32 20 4 30 102 15 65 89 78 53 71 110 54 57 107 107 104 64 11 93 56 22 73 21 84 96 108 59 22 38 110 51 39 53 26 20 84 111 74 20

[出力例]

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

2021年6月16日

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

C++の練習を兼ねて, AtCoder Regular Contest 122 の問題C (Calculator) を解いてみた.

■感想.
1. 問題Cは, 解答方針が見えなかったので, 解説を参考に実装して, ようやく, AC版に到達できた.
2. 個人的には, フィボナッチ数列の性質を考慮し, 操作列を構成していくロジックが, 非常に, 面白く感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/arc122/editorial/2052
// 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

int main(){
    
    // 1. 入力情報.
    LL N;
    scanf("%lld", &N);
    
    // 2. フィボナッチ数列.
    vl f;
    f.pb(1);
    f.pb(1);
    while(f.back() < N){
        int l = f.size();
        f.pb(f[l - 1] + f[l - 2]);
    }
    // サイズ が 偶数の場合, 追加.
    int S = f.size();
    if(!(S & 1)){
        f.pb(f[S - 1] + f[S - 2]);
        S = f.size();
    }
    // rep(i, S) printf("%lld ", f[i]);
    // puts("");
    
    // 3. 操作列の候補を保存.
    queue<int> q;
    LL cur = N;
    while(cur > 0){
        // 3-1. フィボナッチ数列の値と比較.
        int idx = S - 1;
        while(cur < f[idx]) --idx;
        assert(cur >= f[idx]);
        
        // 3-2. 比較対象の数値から, フィボナッチ数列の値を減算.
        cur -= f[idx];
        
        // 3-3. 追加予定位置を保存.
        idx = S - 1 - idx;
        q.push(idx);
    }
    
    // 4. 操作列作成.
    LL x = 0, y = 0;
    int s = q.size();
    bool f34 = false;
    queue<int> op;
    while(x < N){
        // 4-1. 操作列の候補を確認し, 追加.
        if(!q.empty()){
            int idx = q.front();
            
            // 追加可能な位置に来ているかをチェック.
            if(op.size() == (idx + s - q.size())){
                q.pop();
                
                // 1 or 2 を 追加.
                if(idx & 1) op.push(2), y++;
                else        op.push(1), x++;
                continue;
            }
        }
        
        // 4-2. 3 or 4 を 追加.
        if(f34) op.push(3), x += y;
        else    op.push(4), y += x;
        
        // 4-3. フラグ更新.
        f34 = !f34;
    }
    
    // 5. 操作列修正(※01-015.txtで, 131回になるので本処理を追加し, 先頭が, 1 or 2 となるように調整).
    while(!op.empty()){
        int o = op.front();
        if(o == 3 || o == 4) op.pop();
        else                 break;
    }
    assert(op.size() <= 130);
    
    // 6. 出力.
    printf("%d\n", op.size());
    while(!op.empty()){
        int idx = op.front();
        op.pop();
        printf("%d\n", idx);
    }
    return 0;
    
}

100

// 解き直し.

// https://atcoder.jp/contests/arc122/editorial/2052

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

int main(){

// 1. 入力情報.

LL N;

scanf("%lld", &N);

// 2. フィボナッチ数列.

vl f;

f.pb(1);

while(f.back() < N){

int l = f.size();

f.pb(f[l - 1] + f[l - 2]);

}

// サイズが偶数の場合, 追加.

int S = f.size();

if(!(S & 1)){

f.pb(f[S - 1] + f[S - 2]);

S = f.size();

}

// rep(i, S) printf("%lld ", f[i]);

// puts("");

// 3. 操作列の候補を保存.

queue<int> q;

LL cur = N;

while(cur > 0){

// 3-1. フィボナッチ数列の値と比較.

int idx = S - 1;

while(cur < f[idx]) --idx;

assert(cur >= f[idx]);

// 3-2. 比較対象の数値から, フィボナッチ数列の値を減算.

cur -= f[idx];

// 3-3. 追加予定位置を保存.

idx = S - 1 - idx;

q.push(idx);

}

// 4. 操作列作成.

LL x = 0, y = 0;

int s = q.size();

bool f34 = false;

queue<int> op;

while(x < N){

// 4-1. 操作列の候補を確認し, 追加.

if(!q.empty()){

int idx = q.front();

// 追加可能な位置に来ているかをチェック.

if(op.size() == (idx + s - q.size())){

q.pop();

// 1 or 2 を追加.

if(idx & 1) op.push(2), y++;

else op.push(1), x++;

continue;

}

// 4-2. 3 or 4 を追加.

if(f34) op.push(3), x += y;

else op.push(4), y += x;

// 4-3. フラグ更新.

f34 = !f34;

}

// 5. 操作列修正(※01-015.txtで, 131回になるので本処理を追加し, 先頭が, 1 or 2 となるように調整).

while(!op.empty()){

int o = op.front();

if(o == 3 || o == 4) op.pop();

else break;

}

assert(op.size() <= 130);

// 6. 出力.

printf("%d\n", op.size());

while(!op.empty()){

int idx = op.front();

op.pop();

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

}

return 0;

}

[入力例]
4

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

※但し, 上記のプログラムでは, 以下の内容が出力される.
5
2
3
4
2
3

[入力例]
17

[出力例]
9
1
4
3
4
2
3
4
2
3

[入力例]
48

[出力例]
11
1
4
3
1
4
3
4
3
4
2
3

[入力例]
20210616

[出力例]
46
2
3
4
3
1
4
3
1
4
3
4
2
3
4
3
1
4
3
4
3
1
4
3
1
4
3
4
2
3
4
2
3
4
3
1
4
3
4
3
4
3
4
3
4
2
3

[入力例]
100000000000000000

[出力例]
108
1
4
3
4
3
4
3
4
3
4
3
4
2
3
4
2
3
4
2
3
4
2
3
4
2
3
4
2
3
4
3
1
4
3
4
3
1
4
3
4
2
3
4
3
4
2
3
4
2
3
4
3
4
3
1
4
3
4
3
1
4
3
1
4
3
4
2
3
4
3
1
4
3
1
4
3
1
4
3
1
4
3
1
4
3
4
3
4
3
4
2
3
4
2
3
4
2
3
4
2
3
4
3
4
2
3
4
3

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

[入力例]

[出力例]

※AtCoderのテストケースより

※但し, 上記のプログラムでは, 以下の内容が出力される.

[入力例]

[出力例]

[入力例]

[出力例]

[入力例]

20210616

[出力例]

[入力例]

100000000000000000

[出力例]

108

■参照サイト
東京海上日動プログラミングコンテスト2021（AtCoder Regular Contest 122)

2021年6月14日

C++ の動作確認をしてみた（４８３）

C++の練習を兼ねて, AtCoder Regular Contest 066 の問題E (Addition and Subtraction Hard) を解いてみた.

■感想.
1. 問題Cは, 解答方針が見えなかったので, 解説を参考に実装して, ようやく, AC版に到達できた.
2. 苦手な動的計画法の訓練を積めたので, 非常に良かったと思う.
3. 個人的には, 加算減算の数式が, 動的計画法で, 計算できてしまうことに不思議な印象を受け, 非常に, 面白く感じた.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/arc066/editorial.pdf
// 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 INF = 202020202020202020;
LL a[101010], dp[101010][3];
int op[101010];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N * 2 - 1){
        LL x;
        char c[11];
        if(i & 1){
            scanf("%s", c);
            op[i / 2 + 1] = (c[0] == '+') ? 1 : -1;
        }else{
            scanf("%lld", &x);
            a[i / 2] = x;
        }
    }
    op[0] = 1;
    
    // 2. dp更新.
    rep(i, N + 1) dp[i][0] = dp[i][1] = dp[i][2] = -INF;
    dp[0][0] = a[0];
    repx(i, 1, N){
        // 2-1. 符号が正の場合.
        if(op[i] > 0){
            // 括弧が, 0個開く状態に遷移する場合.
            // 0個 -> 0個.
            dp[i][0] = dp[i - 1][0] + a[i];
            
            // 1個 -> 0個.
            if(dp[i - 1][1] != -INF) dp[i][0] = max(dp[i][0], dp[i - 1][1] - a[i]);
            
            // 括弧が, 1個開く状態に遷移する場合.
            // 1個 -> 1個.
            if(dp[i - 1][1] != -INF) dp[i][1] = dp[i - 1][1] - a[i];
            
            // 括弧が, 2個開く状態に遷移する場合.
            // 2個 -> 2個.
            if(dp[i - 1][2] != -INF) dp[i][2] = dp[i - 1][2] + a[i];
        }
        
        // 2-2. 符号が負の場合.
        if(op[i] < 0){
            // 括弧が, 0個開く状態に遷移する場合.
            // 0個 -> 0個.
            dp[i][0] = dp[i - 1][0] - a[i];
            
            // 1個 -> 0個.
            if(dp[i - 1][1] != -INF) dp[i][0] = max(dp[i][0], dp[i - 1][1] + a[i]);
            
            // 括弧が, 1個開く状態に遷移する場合.
            // 1個 -> 1個.
            if(dp[i - 1][1] != -INF) dp[i][1] = dp[i - 1][1] + a[i];
            
            // 0個 -> 1個.
            dp[i][1] = max(dp[i][1], dp[i - 1][0] - a[i]);
            
            // 2個 -> 1個.
            if(dp[i - 1][2] != -INF) max(dp[i][1], dp[i - 1][2] + a[i]);
            
            // 括弧が, 2個開く状態に遷移する場合.
            // 2個 -> 2個.
            if(dp[i - 1][2] != -INF) dp[i][2] = dp[i - 1][2] + a[i];
            
            // 1個 -> 2個.
            if(dp[i - 1][1] != -INF) dp[i][2] = max(dp[i][2], dp[i - 1][1] + a[i]);
        }
    }
    // rep(i, N + 1) printf("%lld %lld %lld\n", dp[i][0], dp[i][1], dp[i][2]);
    
    // 3. 出力.
    printf("%lld\n", max({dp[N - 1][0], dp[N - 1][1], dp[N - 1][2]}));
    return 0;
    
}

// 解き直し.

// https://img.atcoder.jp/arc066/editorial.pdf

// 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 INF = 202020202020202020;

LL a[101010], dp[101010][3];

int op[101010];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

rep(i, N * 2 - 1){

LL x;

char c[11];

if(i & 1){

scanf("%s", c);

op[i / 2 + 1] = (c[0] == '+') ? 1 : -1;

}else{

scanf("%lld", &x);

a[i / 2] = x;

}

op[0] = 1;

// 2. dp更新.

rep(i, N + 1) dp[i][0] = dp[i][1] = dp[i][2] = -INF;

dp[0][0] = a[0];

repx(i, 1, N){

// 2-1. 符号が正の場合.

if(op[i] > 0){

// 括弧が, 0個開く状態に遷移する場合.

// 0個 -> 0個.

dp[i][0] = dp[i - 1][0] + a[i];

// 1個 -> 0個.

if(dp[i - 1][1] != -INF) dp[i][0] = max(dp[i][0], dp[i - 1][1] - a[i]);

// 括弧が, 1個開く状態に遷移する場合.

// 1個 -> 1個.

if(dp[i - 1][1] != -INF) dp[i][1] = dp[i - 1][1] - a[i];

// 括弧が, 2個開く状態に遷移する場合.

// 2個 -> 2個.

if(dp[i - 1][2] != -INF) dp[i][2] = dp[i - 1][2] + a[i];

}

// 2-2. 符号が負の場合.

if(op[i] < 0){

// 括弧が, 0個開く状態に遷移する場合.

// 0個 -> 0個.

dp[i][0] = dp[i - 1][0] - a[i];

// 1個 -> 0個.

if(dp[i - 1][1] != -INF) dp[i][0] = max(dp[i][0], dp[i - 1][1] + a[i]);

// 括弧が, 1個開く状態に遷移する場合.

// 1個 -> 1個.

if(dp[i - 1][1] != -INF) dp[i][1] = dp[i - 1][1] + a[i];

// 0個 -> 1個.

dp[i][1] = max(dp[i][1], dp[i - 1][0] - a[i]);

// 2個 -> 1個.

if(dp[i - 1][2] != -INF) max(dp[i][1], dp[i - 1][2] + a[i]);

// 括弧が, 2個開く状態に遷移する場合.

// 2個 -> 2個.

if(dp[i - 1][2] != -INF) dp[i][2] = dp[i - 1][2] + a[i];

// 1個 -> 2個.

if(dp[i - 1][1] != -INF) dp[i][2] = max(dp[i][2], dp[i - 1][1] + a[i]);

}

// rep(i, N + 1) printf("%lld %lld %lld\n", dp[i][0], dp[i][1], dp[i][2]);

// 3. 出力.

printf("%lld\n", max({dp[N - 1][0], dp[N - 1][1], dp[N - 1][2]}));

return 0;

}

[入力例]
3
5 - 1 - 3

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

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

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

[入力例]
5
1 - 20 - 13 + 14 - 5

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

[入力例]
10
7 + 7 - 8 - 11 + 6 - 11 + 6 - 2 + 3 - 5

[出力例]
50

※実際, 7 + 7 - (8 - (11 + 6) - (11 + 6) - (2 + 3) - 5) = 50 となる.

[入力例]
15
8 - 7 + 2 - 7 - 12 - 10 + 4 + 8 - 2 - 8 + 11 + 6 - 1 + 3 - 6

[出力例]
77

※実際, 8 - (7 + 2 - 7 - 12 - (10 + 4 + 8) - 2 - (8 + 11 + 6) - (1 + 3) - 6) = 77 となる.

[入力例]

5 - 1 - 3

[出力例]

※AtCoderテストケースより

[入力例]

1 - 2 + 3 - 4 + 5

[出力例]

※AtCoderテストケースより

[入力例]

1 - 20 - 13 + 14 - 5

[出力例]

※AtCoderテストケースより

[入力例]

7 + 7 - 8 - 11 + 6 - 11 + 6 - 2 + 3 - 5

[出力例]

※実際, 7 + 7 - (8 - (11 + 6) - (11 + 6) - (2 + 3) - 5) = 50 となる.

[入力例]

8 - 7 + 2 - 7 - 12 - 10 + 4 + 8 - 2 - 8 + 11 + 6 - 1 + 3 - 6

[出力例]

※実際, 8 - (7 + 2 - 7 - 12 - (10 + 4 + 8) - 2 - (8 + 11 + 6) - (1 + 3) - 6) = 77 となる.

■参照サイト
AtCoder Regular Contest 066

2021年6月13日

C++ の動作確認をしてみた（４８２）

C++の練習を兼ねて, AtCoder Regular Contest 122 の問題B (Insurance) を解いてみた.

■感想.
1. 規則性を抽出できたので, AC版に到達出来たと思う.
2. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 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--)
LL a[101010], aCum[101010];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N){
        scanf("%lld", &a[i]);
        a[i] *= 2;
    }
    
    // 2. sort.
    sort(a, a + N);
    
    // 3. 累積和.
    rep(i, N) aCum[i + 1] = aCum[i] + a[i];
    
    // 4. 期待値の最小化を計算.
    LL t = 202020202020202020;
    rep(i, N){
        LL x = a[i] / 2;
        LL l = N * x + aCum[N] - (N - i) * a[i] - aCum[i];
        t = min(t, l);
    }
    
    // 5. 出力.
    double ans = (double)t / (double)(N * 2.0);
    printf("%.12lf\n", ans);
    return 0;
    
}

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

LL a[101010], aCum[101010];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

rep(i, N){

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

a[i] *= 2;

}

// 2. sort.

sort(a, a + N);

// 3. 累積和.

rep(i, N) aCum[i + 1] = aCum[i] + a[i];

// 4. 期待値の最小化を計算.

LL t = 202020202020202020;

rep(i, N){

LL x = a[i] / 2;

LL l = N * x + aCum[N] - (N - i) * a[i] - aCum[i];

t = min(t, l);

}

// 5. 出力.

double ans = (double)t / (double)(N * 2.0);

printf("%.12lf\n", ans);

return 0;

}

[入力例]
3
3 1 4

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

※但し, 上記のプログラムでは, 以下の内容が出力される.
1.833333333333

[入力例]
10
866111664 178537096 844917655 218662351 383133839 231371336 353498483 865935868 472381277 579910117

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

※但し, 上記のプログラムでは, 以下の内容が出力される.
362925658.100000023842

[入力例]
30
180 214 268 205 256 151 318 244 251 85 285 101 3 105 64 20 68 267 102 40 104 150 200 126 21 169 269 37 272 254

[出力例]
121.733333333333

[入力例]
50
50568 31661 5354 6042 40506 15410 23562 36883 38669 29863 39256 36598 23453 7072 45569 14763 8168 50811 12511 44658 44841 44589 5892 38107 52243 10696 194 44022 14009 53824 40674 41169 32329 3475 819 30495 26017 6093 7410 21659 12755 14881 11716 46921 2523 4852 6089 10083 24530 53449

[出力例]
20365.040000000001

[入力例]

3 1 4

[出力例]

1.83333333333333333333

※AtCoderのテストケースより

※但し, 上記のプログラムでは, 以下の内容が出力される.

1.833333333333

[入力例]

866111664 178537096 844917655 218662351 383133839 231371336 353498483 865935868 472381277 579910117

[出力例]

362925658.10000000000000000000

※AtCoderのテストケースより

※但し, 上記のプログラムでは, 以下の内容が出力される.

362925658.100000023842

[入力例]

180 214 268 205 256 151 318 244 251 85 285 101 3 105 64 20 68 267 102 40 104 150 200 126 21 169 269 37 272 254

[出力例]

121.733333333333

[入力例]

50568 31661 5354 6042 40506 15410 23562 36883 38669 29863 39256 36598 23453 7072 45569 14763 8168 50811 12511 44658 44841 44589 5892 38107 52243 10696 194 44022 14009 53824 40674 41169 32329 3475 819 30495 26017 6093 7410 21659 12755 14881 11716 46921 2523 4852 6089 10083 24530 53449

[出力例]

20365.040000000001

■参照サイト
東京海上日動プログラミングコンテスト2021（AtCoder Regular Contest 122)

2021年6月13日

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

C++の練習を兼ねて, AtCoder Regular Contest 122 の問題A (Many Formulae) を解いてみた.

■感想.
1. 規則性を抽出できたので, AC版に到達出来たと思う.
2. 苦手な動的計画法の訓練を積めたので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 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 a[101010], f[101010], dp[101010][2];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%lld", &a[i]);
    
    // 2. フィボナッチ数列.
    f[0] = 1;
    f[1] = 1;
    rep(i, N) f[i + 2] = f[i + 1] + f[i], f[i + 2] %= MOD;
    
    // 3. dp更新.
    dp[0][0] = a[0];
    repx(i, 1, N){
        dp[i][0] = (dp[i - 1][0] + dp[i - 1][1]) + a[i] * f[i];
        dp[i][1] = dp[i - 1][0] + MOD * f[i - 1] - a[i] * f[i - 1];
        dp[i][0] %= MOD;
        dp[i][1] %= MOD;
    }
    
    // 4. 出力.
    printf("%lld\n", (dp[N - 1][0] + dp[N - 1][1]) % MOD);
    return 0;
    
}

// 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 a[101010], f[101010], dp[101010][2];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

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

// 2. フィボナッチ数列.

f[0] = 1;

f[1] = 1;

rep(i, N) f[i + 2] = f[i + 1] + f[i], f[i + 2] %= MOD;

// 3. dp更新.

dp[0][0] = a[0];

repx(i, 1, N){

dp[i][0] = (dp[i - 1][0] + dp[i - 1][1]) + a[i] * f[i];

dp[i][1] = dp[i - 1][0] + MOD * f[i - 1] - a[i] * f[i - 1];

dp[i][0] %= MOD;

dp[i][1] %= MOD;

}

// 4. 出力.

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

return 0;

}

[入力例]
3
3 1 5

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

[入力例]
4
1 1 1 1

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

[入力例]
10
866111664 178537096 844917655 218662351 383133839 231371336 353498483 865935868 472381277 579910117

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

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

[出力例]
137

[入力例]
15
33 111 86 66 150 116 125 21 88 32 59 87 80 62 13

[出力例]
500033

[入力例]

3 1 5

[出力例]

※AtCoderのテストケースより

[入力例]

1 1 1 1

[出力例]

※AtCoderのテストケースより

[入力例]

866111664 178537096 844917655 218662351 383133839 231371336 353498483 865935868 472381277 579910117

[出力例]

279919144

※AtCoderのテストケースより

[入力例]

3 1 4 1 5 9

[出力例]

137

[入力例]

33 111 86 66 150 116 125 21 88 32 59 87 80 62 13

[出力例]

500033

■参照サイト
東京海上日動プログラミングコンテスト2021（AtCoder Regular Contest 122)

2021年6月11日2021年6月11日

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

C++の練習を兼ねて, 競プロ典型 90 問の問題063 (Monochromatic Subgrid) を解いてみた.

■感想.
1. 問題063は, 実装方針を決めることが出来たので, AC版に到達出来たと思う.
2. 手強い問題が非常に多い気もするけど, 時間を見つけて, 引き続き, 取り組んでいきたいと思う.

詳細は, 本家のサイト(GitHub) 競プロ典型 90 問の問題063 をご覧下さい.

■C++版プログラム(問題063／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--)
#define a first
#define b second
int p[10][10101];

int main(){
    
    // 1. 入力情報.
    int H, W;
    scanf("%d %d", &H, &W);
    rep(i, H) rep(j, W) scanf("%d", &p[i][j]);
    
    // 2. 行の選択に応じた良い部分グリッドの最大値を計算.
    // -> 選択された各行について, 列成分が, すべて同じ値ものを, それらの値ごとにカウント.
    // ex. 
    // 5 7
    // 1 3 1 3 1 5 2
    // 2 5 2 1 3 5 2
    // 1 3 4 5 1 2 1
    // 4 3 5 3 4 2 3
    // 5 3 1 3 1 5 2
    // -> i = 25( = 11001) の場合, つまり 1, 2, 5行目が選択された場合, 
    // 2列目は, 3, 5, 3 なので, カウントしないが,
    // 6列目は, 5, 5, 5 なので, カウントしていく.
    int ans = 0;
    rep(i, 1 << H){
        // 2-1. 各列について, カウントの可否を判断し, カウント.
        map<int, int> m;
        rep(j, W){
            set<int> st;
            int one = 0;
            rep(k, H) if(i & (1 << k)) st.insert(p[k][j]), one++;
            if(st.size() == 1) m[*st.begin()] += one;
        }
        
        // 2-2. 最大値を更新.
        for(auto &p : m) ans = max(ans, p.b);
    }
    
    // 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--)

#define a first

#define b second

int p[10][10101];

int main(){

// 1. 入力情報.

int H, W;

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

rep(i, H) rep(j, W) scanf("%d", &p[i][j]);

// 2. 行の選択に応じた良い部分グリッドの最大値を計算.

// -> 選択された各行について, 列成分が, すべて同じ値ものを, それらの値ごとにカウント.

// ex.

// 5 7

// 1 3 1 3 1 5 2

// 2 5 2 1 3 5 2

// 1 3 4 5 1 2 1

// 4 3 5 3 4 2 3

// 5 3 1 3 1 5 2

// -> i = 25( = 11001) の場合, つまり 1, 2, 5行目が選択された場合,

// 2列目は, 3, 5, 3 なので, カウントしないが,

// 6列目は, 5, 5, 5 なので, カウントしていく.

int ans = 0;

rep(i, 1 << H){

// 2-1. 各列について, カウントの可否を判断し, カウント.

map<int, int> m;

rep(j, W){

set<int> st;

int one = 0;

rep(k, H) if(i & (1 << k)) st.insert(p[k][j]), one++;

if(st.size() == 1) m[*st.begin()] += one;

}

// 2-2. 最大値を更新.

for(auto &p : m) ans = max(ans, p.b);

}

// 3. 出力.

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

return 0;

}

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

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

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

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

[入力例]
5 3
7 7 7
7 7 7
7 7 7
7 7 7
7 7 7

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

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

[出力例]
10

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

[出力例]
30

[入力例]

4 6

1 1 1 1 1 2

1 2 2 2 2 2

1 2 2 3 2 3

1 2 3 2 2 3

[出力例]

※AtCoderテストケースより

[入力例]

3 3

1 2 3

4 5 6

7 8 9

[出力例]

※AtCoderテストケースより

[入力例]

5 3

7 7 7

[出力例]

※AtCoderテストケースより

[入力例]

5 7

1 3 1 3 1 5 2

2 3 3 3 3 5 3

1 1 4 5 1 2 1

4 3 3 3 3 2 3

5 3 1 3 1 5 2

[出力例]

[入力例]

8 25

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

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

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

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

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

2 5 5 1 5 9 5 1 1 5 5 7 5 4 1 5 2 4 5 2 5 9 5 5 7

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

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

[出力例]

■参照サイト
063 – Monochromatic Subgrid

2021年6月9日

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

C++の練習を兼ねて, 競プロ典型 90 問の問題058 (Original Calculator) を解いてみた.

■感想.
1. 問題058は, 実装に苦労したものの, 周期を抽出できたので, AC版に到達出来たと思う.
2. 手強い問題が非常に多い気もするけど, 時間を見つけて, 引き続き, 取り組んでいきたいと思う.

詳細は, 本家のサイト(GitHub) 競プロ典型 90 問の問題058 をご覧下さい.

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

// 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 int MOD = 1000;
const int MOD = 100000;
int memo[101010];

int main(){
    
    // 1. 入力情報.
    int N;
    LL K;
    scanf("%d %lld", &N, &K);
    
    // 2. ボタン A を 押下.
    // 2-1. 指定回数実行.
    auto f = [](int n, int u) -> int{
        // 終了条件.
        if(u <= 0) return n;
        
        // 初回処理.
        string sn = to_string(n);
        int cur = n, c = 1;
        rep(i, sn.size()) cur += sn[i] - '0';
        cur %= MOD;
        
        // 繰り返し処理.
        while(c < u){
            // 各桁の和.
            sn = to_string(cur);
            
            // 今回分更新.
            rep(i, sn.size()) cur += sn[i] - '0';
            cur %= MOD;
            
            // インクリメント.
            c++;
        }
        
        // 出力.
        return cur;
    };
    
    // 2-2. 周期(同じ整数が出現した時の整数は？).
    auto g = [&](int n) -> int{
        // 基準となる整数.
        memo[n]++;
        
        // 初回処理.
        string sn = to_string(n);
        int cur = n;
        rep(i, sn.size()) cur += sn[i] - '0';
        cur %= MOD;
        memo[cur]++;
        
        // 繰り返し処理.
        while(memo[cur] < 2){
            sn = to_string(cur);
            rep(i, sn.size()) cur += sn[i] - '0';
            cur %= MOD;
            memo[cur]++;
        }
        
        // 出力.
        return cur;
    };
    
    // 2-3. 周期(指定された整数 t が, 最初に出現するまでの操作回数は？).
    auto h = [&](int n, int t) -> int{
        // 終了条件.
        LL c = 0;
        if(n == t) return c;
        
        // 初回処理.
        string sn = to_string(n);
        int cur = n;
        rep(i, sn.size()) cur += sn[i] - '0';
        cur %= MOD;
        memo[cur]++;
        c++;
        
        // 繰り返し処理.
        while(cur != t){
            sn = to_string(cur);
            rep(i, sn.size()) cur += sn[i] - '0';
            cur %= MOD;
            memo[cur]++;
            c++;
        }
        
        // 出力.
        return c;
    };
    
    // 3. ボタン A 押下時の挙動.
    // 3-1. 初めて同じ整数が, 二回出現するケースを確認.
    int x = g(N);
    LL f2 = 0;
    rep(i, 101010) if(memo[i]) f2++;
    
    // 3-2. 前項の整数が, 一回目出現するまでを確認.
    rep(i, 101010) memo[i] = 0;
    LL f1 = h(N, x);
    
    // 4. K回操作後の整数を算出.
    // 4-1. 周期 および K回操作の最小化.
    LL f3 = f2 - f1;
    if(K > f1) K = f1 + (K - f1) % f3;
    
    // 4-2. 整数を取得.
    int ans = f(N, (int)K);
    
    // 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

// 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 int MOD = 1000;

const int MOD = 100000;

int memo[101010];

int main(){

// 1. 入力情報.

int N;

LL K;

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

// 2. ボタン A を押下.

// 2-1. 指定回数実行.

auto f = [](int n, int u) -> int{

// 終了条件.

if(u <= 0) return n;

// 初回処理.

string sn = to_string(n);

int cur = n, c = 1;

rep(i, sn.size()) cur += sn[i] - '0';

cur %= MOD;

// 繰り返し処理.

while(c < u){

// 各桁の和.

sn = to_string(cur);

// 今回分更新.

rep(i, sn.size()) cur += sn[i] - '0';

cur %= MOD;

// インクリメント.

c++;

}

// 出力.

return cur;

};

// 2-2. 周期(同じ整数が出現した時の整数は？).

auto g = [&](int n) -> int{

// 基準となる整数.

memo[n]++;

// 初回処理.

string sn = to_string(n);

int cur = n;

rep(i, sn.size()) cur += sn[i] - '0';

cur %= MOD;

memo[cur]++;

// 繰り返し処理.

while(memo[cur] < 2){

sn = to_string(cur);

rep(i, sn.size()) cur += sn[i] - '0';

cur %= MOD;

memo[cur]++;

}

// 出力.

return cur;

};

// 2-3. 周期(指定された整数 t が, 最初に出現するまでの操作回数は？).

auto h = [&](int n, int t) -> int{

// 終了条件.

LL c = 0;

if(n == t) return c;

// 初回処理.

string sn = to_string(n);

int cur = n;

rep(i, sn.size()) cur += sn[i] - '0';

cur %= MOD;

memo[cur]++;

c++;

// 繰り返し処理.

while(cur != t){

sn = to_string(cur);

rep(i, sn.size()) cur += sn[i] - '0';

cur %= MOD;

memo[cur]++;

c++;

}

// 出力.

return c;

};

// 3. ボタン A 押下時の挙動.

// 3-1. 初めて同じ整数が, 二回出現するケースを確認.

int x = g(N);

LL f2 = 0;

rep(i, 101010) if(memo[i]) f2++;

// 3-2. 前項の整数が, 一回目出現するまでを確認.

rep(i, 101010) memo[i] = 0;

LL f1 = h(N, x);

// 4. K回操作後の整数を算出.

// 4-1. 周期および K回操作の最小化.

LL f3 = f2 - f1;

if(K > f1) K = f1 + (K - f1) % f3;

// 4-2. 整数を取得.

int ans = f(N, (int)K);

// 5. 出力.

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

return 0;

}

[入力例]
5 3

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

[入力例]
0 100

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

[入力例]
99999 1000000000000000000

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

[入力例]
12 345

[出力例]
5055

[入力例]
123 9876543210

[出力例]
16555

[入力例]
31415 926535897932

[出力例]
26057

[入力例]

5 3

[出力例]

※AtCoderテストケースより

[入力例]

0 100

[出力例]

※AtCoderテストケースより

[入力例]

99999 1000000000000000000

[出力例]

84563

※AtCoderテストケースより

[入力例]

12 345

[出力例]

5055

[入力例]

123 9876543210

[出力例]

16555

[入力例]

31415 926535897932

[出力例]

26057

■参照サイト
058 – Original Calculator

2021年6月8日

C++ の動作確認をしてみた（４７８）

C++の練習を兼ねて, AtCoder Beginner Contest 202 の問題E (Count Descendants) を解いてみた.

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

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

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

// 解き直し.
// https://atcoder.jp/contests/ABC202/editorial/1864
#include <bits/stdc++.h>
using namespace std;
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
#define all(x) x.begin(), x.end()
int iTime[202020], oTime[202020], memo[202020];

int main(){
    
    // 1. 入力情報.
    int N, Q;
    scanf("%d", &N);
    vvi G(N), info(N + 1);
    repx(i, 1, N){
        int p;
        scanf("%d", &p);
        p--;
        G[i].pb(p);
        G[p].pb(i);
    }
    scanf("%d", &Q);
    
    // 2. 探索を行い, 頂点を訪れた順に保存.
    // https://ja.wikipedia.org/wiki/深さ優先探索
    int idx = 0;
    auto dfs = [&](auto&& self, int c, int d) -> void{
        // 2-1. 訪問済フラグ設定.
        memo[c] = 1;
        
        // 2-2. 深さごとに, 入った時刻を保存.
        info[d].pb(idx);
        
        // 2-3. 入った時刻を保存.
        iTime[c] = idx++;
        
        // 2-4. 取り出した要素を処理.
        for(auto &n : G[c]) if(!memo[n]) self(self, n, d + 1);
        
        // 2-5. 出た時刻を保存.
        oTime[c] = idx++;
        
        // 2-6. 終了.
        return;
    };
    dfs(dfs, 0, 0);
    
    // 3. クエリ回答.
    rep(i, Q){
        // 3-1. クエリ入力値.
        int U, D;
        scanf("%d %d", &U, &D);
        U--;
        
        // 3-2. 深さ D で, [iTime[U], oTime[U]) の個数を取得.
        int lAt = lower_bound(all(info[D]), iTime[U]) - info[D].begin();
        int rAt = lower_bound(all(info[D]), oTime[U]) - info[D].begin();
        
        // 3-3. 出力.
        printf("%d\n", rAt - lAt);
    }
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/ABC202/editorial/1864

#include <bits/stdc++.h>

using namespace std;

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

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

int iTime[202020], oTime[202020], memo[202020];

int main(){

// 1. 入力情報.

int N, Q;

scanf("%d", &N);

vvi G(N), info(N + 1);

repx(i, 1, N){

int p;

scanf("%d", &p);

p--;

G[i].pb(p);

G[p].pb(i);

}

scanf("%d", &Q);

// 2. 探索を行い, 頂点を訪れた順に保存.

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

int idx = 0;

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

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

memo[c] = 1;

// 2-2. 深さごとに, 入った時刻を保存.

info[d].pb(idx);

// 2-3. 入った時刻を保存.

iTime[c] = idx++;

// 2-4. 取り出した要素を処理.

for(auto &n : G[c]) if(!memo[n]) self(self, n, d + 1);

// 2-5. 出た時刻を保存.

oTime[c] = idx++;

// 2-6. 終了.

return;

};

dfs(dfs, 0, 0);

// 3. クエリ回答.

rep(i, Q){

// 3-1. クエリ入力値.

int U, D;

scanf("%d %d", &U, &D);

U--;

// 3-2. 深さ D で, [iTime[U], oTime[U]) の個数を取得.

int lAt = lower_bound(all(info[D]), iTime[U]) - info[D].begin();

int rAt = lower_bound(all(info[D]), oTime[U]) - info[D].begin();

// 3-3. 出力.

printf("%d\n", rAt - lAt);

}

return 0;

}

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

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

[入力例]
30
1 1 1 2 2 3 3 4 4 5 5 6 7 13 13 8 8 9 9 10 10 18 18 20 20 22 22 11 11
7
5 3
3 3
9 4
4 3
5 4
2 3
3 1

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

[入力例]
45
1 2 3 4 5 5 5 4 4 3 1 1 1 1 13 13 15 15 18 18 21 21 22 22 23 23 24 24 24 12 12 32 33 33 35 35 37 37 37 36 36 35 35 35
12
1 1
2 4
1 3
32 5
33 6
4 1
5 5
22 6
15 3
21 5
13 2
35 5

[出力例]
5
3
5
5
5
0
3
3
2
4
2
5

[入力例]

1 1 2 2 4 2

1 2

7 2

4 1

5 5

[出力例]

※AtCoderテストケースより

[入力例]

1 1 1 2 2 3 3 4 4 5 5 6 7 13 13 8 8 9 9 10 10 18 18 20 20 22 22 11 11

5 3

3 3

9 4

4 3

5 4

2 3

3 1

[出力例]

[入力例]

1 2 3 4 5 5 5 4 4 3 1 1 1 1 13 13 15 15 18 18 21 21 22 22 23 23 24 24 24 12 12 32 33 33 35 35 37 37 37 36 36 35 35 35

1 1

2 4

1 3

32 5

33 6

4 1

5 5

22 6

15 3

21 5

13 2

35 5

[出力例]

■参照サイト
エイシングプログラミングコンテスト2021（AtCoder Beginner Contest 202）

2021年6月7日2021年6月7日

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

C++の練習を兼ねて, AtCoder Beginner Contest 204 の問題C (Tour) ～問題D (Cooking) を解いてみた.

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

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

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
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

int main(){
    
    // 1. 入力情報.
    int N, M, ans = 0;
    scanf("%d %d", &N, &M);
    vvi G(N);
    rep(i, M){
        int a, b;
        scanf("%d %d", &a, &b);
        a--, b--;
        G[a].pb(b); // 有向グラフ.
    }
    
    // 2. 各頂点をスタート地点として探索.
    // https://ja.wikipedia.org/wiki/幅優先探索
    auto bfs = [&](vvi &G, int s){
        // 3-1. 初期化.
        int d[2020];
        rep(i, 2020) d[i] = 0;
        
        // 3-2. 空のキュー.
        queue<int> q;
        
        // 3-3. 探索地点 s をキュー q に追加.
        q.push(s);
        while(!q.empty()){
            // 3-4. キューから取り出す.
            int u = q.front();
            q.pop();
            
            // 3-5. インクリメント.
            ans++;
            
            // 3-6. 取り出した要素を処理.
            for(auto &e : G[u]){
                // 3-5. 訪問済であれば, 処理をスキップ.
                if(d[e])            continue;
                if(!d[e] && e != s) d[e] = d[u] + 1, q.push(e);
            }
        }
        return;
    };
    rep(i, N) bfs(G, i);
    
    // 3. 出力.
    printf("%d\n", ans);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

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

int main(){

// 1. 入力情報.

int N, M, ans = 0;

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

vvi G(N);

rep(i, M){

int a, b;

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

a--, b--;

G[a].pb(b); // 有向グラフ.

}

// 2. 各頂点をスタート地点として探索.

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

auto bfs = [&](vvi &G, int s){

// 3-1. 初期化.

int d[2020];

rep(i, 2020) d[i] = 0;

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

queue<int> q;

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

q.push(s);

while(!q.empty()){

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

int u = q.front();

q.pop();

// 3-5. インクリメント.

ans++;

// 3-6. 取り出した要素を処理.

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

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

if(d[e]) continue;

if(!d[e] && e != s) d[e] = d[u] + 1, q.push(e);

}

return;

};

rep(i, N) bfs(G, i);

// 3. 出力.

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

return 0;

}

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

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

[入力例]
3 0

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

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

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

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

[出力例]
39

[入力例]

3 3

1 2

2 3

3 2

[出力例]

※AtCoderテストケースより

[入力例]

3 0

[出力例]

※AtCoderテストケースより

[入力例]

4 4

1 2

2 3

3 4

4 1

[出力例]

※AtCoderテストケースより

[入力例]

11 12

1 2

1 9

2 8

2 5

2 3

2 4

3 10

11 3

4 6

6 7

7 4

5 7

[出力例]

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

// 解き直し.
// https://atcoder.jp/contests/ABC204/editorial/2013
// 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 t[101];
bool dp[101][101010];

int main(){
    
    // 1. 入力情報.
    int N, u = 0;
    scanf("%d", &N);
    rep(i, N){
        scanf("%d", &t[i]);
        u += t[i];
    }
    
    // 2. 境界値.
    u = (u + 1) / 2;
    
    // 3. dp更新.
    dp[0][0] = true;
    repx(i, 1, N + 1){
        repr(j, 101010 - 1, 0){
            dp[i][j] = dp[i - 1][j];
            if(j + t[i] < 101010){
                if(dp[i - 1][j]) dp[i][j + t[i - 1]] = true;
            }
        }
    }
    
    // 4. N品の料理を全て作るまでの最短時間を抽出.
    int ans = 0;
    repx(i, u, 101010){
        if(dp[N][i]){
            ans = i;
            break;
        }
    }
    
    // 5. 出力.
    printf("%d\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/ABC204/editorial/2013

// 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 t[101];

bool dp[101][101010];

int main(){

// 1. 入力情報.

int N, u = 0;

scanf("%d", &N);

rep(i, N){

scanf("%d", &t[i]);

u += t[i];

}

// 2. 境界値.

u = (u + 1) / 2;

// 3. dp更新.

dp[0][0] = true;

repx(i, 1, N + 1){

repr(j, 101010 - 1, 0){

dp[i][j] = dp[i - 1][j];

if(j + t[i] < 101010){

if(dp[i - 1][j]) dp[i][j + t[i - 1]] = true;

}

// 4. N品の料理を全て作るまでの最短時間を抽出.

int ans = 0;

repx(i, u, 101010){

if(dp[N][i]){

ans = i;

break;

}

// 5. 出力.

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

return 0;

}

[入力例]
5
8 3 7 2 5

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

[入力例]
2
1000 1

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

[入力例]
9
3 14 15 9 26 5 35 89 79

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

[入力例]
10
3 5 13 4 16 21 5 20 123 31

[出力例]
123

[入力例]
15
3 5 13 14 16 21 20 36 33 26 30 7 55 10 111

[出力例]
200

[入力例]
24
1 2 3 7 8 9 15 16 17 31 32 33 63 64 65 127 128 129 255 256 257 511 512 513

[出力例]
1527

[入力例]

8 3 7 2 5

[出力例]

※AtCoderテストケースより

[入力例]

1000 1

[出力例]

1000

※AtCoderテストケースより

[入力例]

3 14 15 9 26 5 35 89 79

[出力例]

138

※AtCoderテストケースより

[入力例]

3 5 13 4 16 21 5 20 123 31

[出力例]

123

[入力例]

3 5 13 14 16 21 20 36 33 26 30 7 55 10 111

[出力例]

200

[入力例]

1 2 3 7 8 9 15 16 17 31 32 33 63 64 65 127 128 129 255 256 257 511 512 513

[出力例]

1527

■参照サイト
AtCoder Beginner Contest 204

2021年6月6日2021年6月6日

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

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

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

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

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

// 解き直し.
// https://atcoder.jp/contests/abc203/editorial/1964
// 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 a[202020], f[202020], dp[202020][31];

int main(){
    
    // 1. 入力情報.
    int N, K;
    scanf("%d %d", &N, &K);
    rep(i, N) scanf("%d", &a[i + 1]);
    
    // 2. sort.
    sort(a, a + N + 1);
    
    // 3. f を 計算.
    int l = N, r = N;
    while(r){
        // 3-1. 判定.
        while(a[r] < 2 * a[l]) --l;
        
        // 3-2. 設定, および, デクリメント.
        f[r--] = l;
    }
    
    // 4. dp更新.
    repx(i, 1, N + 1) dp[i][0] = i;
    repx(i, 1, N + 1) repx(j, 1, 31) dp[i][j] = min(dp[i - 1][j] + 1, dp[f[i]][j - 1]);
    
    // 5. 操作回数を取得.
    int ans1 = 0, ans2 = 0;
    repr(j, 30, 0) if(dp[N][j] <= K) ans1 = j, ans2 = dp[N][j];
    
    // 6. 出力.
    printf("%d %d\n", ans1, ans2);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc203/editorial/1964

// 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 a[202020], f[202020], dp[202020][31];

int main(){

// 1. 入力情報.

int N, K;

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

rep(i, N) scanf("%d", &a[i + 1]);

// 2. sort.

sort(a, a + N + 1);

// 3. f を計算.

int l = N, r = N;

while(r){

// 3-1. 判定.

while(a[r] < 2 * a[l]) --l;

// 3-2. 設定, および, デクリメント.

f[r--] = l;

}

// 4. dp更新.

repx(i, 1, N + 1) dp[i][0] = i;

repx(i, 1, N + 1) repx(j, 1, 31) dp[i][j] = min(dp[i - 1][j] + 1, dp[f[i]][j - 1]);

// 5. 操作回数を取得.

int ans1 = 0, ans2 = 0;

repr(j, 30, 0) if(dp[N][j] <= K) ans1 = j, ans2 = dp[N][j];

// 6. 出力.

printf("%d %d\n", ans1, ans2);

return 0;

}

[入力例]
4 1
2 3 4 9

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

[入力例]
3 3
2 3 5

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

[入力例]
9 8
137 55 56 60 27 28 133 56 55

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

[入力例]
30 8
51 104 6 87 96 44 90 11 9 90 82 50 98 52 105 44 63 92 99 37 92 33 32 73 72 57 41 102 109 96

[出力例]
2 3

[入力例]
50 10
348 207 216 593 462 219 37 612 36 1191 149 496 1042 259 452 206 529 70 52 540 418 63 709 917 915 466 265 21 32 824 228 705 1129 835 101 59 1020 1087 300 431 1049 1153 1119 678 1069 839 1175 258 148 833

[出力例]
3 9

[入力例]

4 1

2 3 4 9

[出力例]

2 1

※AtCoderテストケースより

[入力例]

3 3

2 3 5

[出力例]

0 3

※AtCoderテストケースより

[入力例]

9 8

137 55 56 60 27 28 133 56 55

[出力例]

1 4

※AtCoderテストケースより

[入力例]

30 8

51 104 6 87 96 44 90 11 9 90 82 50 98 52 105 44 63 92 99 37 92 33 32 73 72 57 41 102 109 96

[出力例]

2 3

[入力例]

50 10

348 207 216 593 462 219 37 612 36 1191 149 496 1042 259 452 206 529 70 52 540 418 63 709 917 915 466 265 21 32 824 228 705 1129 835 101 59 1020 1087 300 431 1049 1153 1119 678 1069 839 1175 258 148 833

[出力例]

3 9

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

C++の練習を兼ねて, AtCoder Beginner Contest 206 の 問題C (Swappable) ～ 問題D (KAIBUNsyo) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 122 の 問題C (Calculator) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 066 の 問題E (Addition and Subtraction Hard) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 122 の 問題B (Insurance) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 122 の 問題A (Many Formulae) を解いてみた.

C++の練習を兼ねて, 競プロ典型 90 問 の 問題063 (Monochromatic Subgrid) を解いてみた.

C++の練習を兼ねて, 競プロ典型 90 問 の 問題058 (Original Calculator) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 202 の 問題E (Count Descendants) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 204 の 問題C (Tour) ～ 問題D (Cooking) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 206 の問題C (Swappable) ～問題D (KAIBUNsyo) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 122 の問題C (Calculator) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 066 の問題E (Addition and Subtraction Hard) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 122 の問題B (Insurance) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 122 の問題A (Many Formulae) を解いてみた.

C++の練習を兼ねて, 競プロ典型 90 問の問題063 (Monochromatic Subgrid) を解いてみた.

C++の練習を兼ねて, 競プロ典型 90 問の問題058 (Original Calculator) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 202 の問題E (Count Descendants) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 204 の問題C (Tour) ～問題D (Cooking) を解いてみた.

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