C++ | 個人用メモ帳

2021年10月13日

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

C++の練習を兼ねて, AtCoder Beginner Contest 221 の問題G (Jumping sequence) を解いてみた.

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

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

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

// C++(GCC 9.2.1)
// 解き直し.
// https://atcoder.jp/contests/abc221/editorial/2724
#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
#define all(x) x.begin(), x.end()
int D[2020];
// bitset<55> dp[11];
bitset<3636363> dp[2020];

int main(){
    
    // 1. 入力情報.
    int N, A, B, S = 0;
    scanf("%d %d %d", &N, &A, &B);
    rep(i, N){
        scanf("%d", &D[i]);
        S += D[i];
    }
    
    // 2. 例外をチェック.
    int D1 = (S + A + B) / 2;
    int D2 = (S + A - B) / 2;
    bool ok = true;
    ok &= ((S + A + B) == D1 * 2);
    ok &= ((S + A - B) == D2 * 2);
    ok &= (D1 >= 0);
    ok &= (D1 <= S);
    ok &= (D2 >= 0);
    ok &= (D2 <= S);
    if(!ok){
        puts("No");
        return 0;
    }
    
    // 3. dp更新.
    dp[0][0] = true;
    rep(i, N){
        // 3-1. 今回分設定.
        dp[i + 1] = dp[i];
        
        // 3-2. dpを左シフトしたものを考慮.
        dp[i + 1] <<= D[i];
        
        // 3-3. 前回分を反映.
        dp[i + 1] |= dp[i];
    }
    
    // 4. 例外をチェック.
    if(!dp[N][D1] || !dp[N][D2]){
        puts("No");
        return 0;
    }
    
    // 5. 経路の復元.
    // -> 以下のような変換ルールが, 発生したと見做す.
    // 上: (0, +D) -> (+D, -D) -- +D --> (+2D, 0)   -- /2 --> (+D, 0)
    // 下: (0, -D) -> (-D, +D) -- +D --> (0, +2D)   -- /2 --> (0, +D)
    // 左: (-D, 0) -> (-D, -D) -- +D --> (0, 0)     -- /2 --> (0, 0)
    // 右: (+D, 0) -> (+D, +D) -- +D --> (+2D, +2D) -- /2 --> (+D, +D)
    string ans = "";
    int curX = D1, curY = D2;
    repr(i, N - 1, 0){
        // 上.
        if(curX - D[i] >= 0 && dp[i][curX - D[i]] && dp[i][curY]){
            // 経路情報.
            ans.pb('U');
            
            // 今回分反映.
            curX -= D[i];
            curY -= 0;
            
            // 次へ.
            continue;
        }
        
        // 下.
        if(curY - D[i] >= 0 && dp[i][curX] && dp[i][curY - D[i]]){
            // 経路情報.
            ans.pb('D');
            
            // 今回分反映.
            curX -= 0;
            curY -= D[i];
            
            // 次へ.
            continue;
        }
        
        // 左.
        if(dp[i][curX] && dp[i][curY]){
            // 経路情報.
            ans.pb('L');
            
            // 今回分反映.
            curX -= 0;
            curY -= 0;
            
            // 次へ.
            continue;
        }
        
        // 右.
        if(curX - D[i] >= 0 && curY - D[i] >= 0 && dp[i][curX - D[i]] && dp[i][curY - D[i]]){
            // 経路情報.
            ans.pb('R');
            
            // 今回分反映.
            curX -= D[i];
            curY -= D[i];
            
            // 次へ.
            continue;
        }
    }
    
    // 6. 反転.
    reverse(all(ans));
    
    // 7. 出力.
    puts("Yes");
    printf("%s\n", ans.c_str());
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

// C++(GCC 9.2.1)

// 解き直し.

// https://atcoder.jp/contests/abc221/editorial/2724

#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

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

int D[2020];

// bitset<55> dp[11];

bitset<3636363> dp[2020];

int main(){

// 1. 入力情報.

int N, A, B, S = 0;

scanf("%d %d %d", &N, &A, &B);

rep(i, N){

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

S += D[i];

}

// 2. 例外をチェック.

int D1 = (S + A + B) / 2;

int D2 = (S + A - B) / 2;

bool ok = true;

ok &= ((S + A + B) == D1 * 2);

ok &= ((S + A - B) == D2 * 2);

ok &= (D1 >= 0);

ok &= (D1 <= S);

ok &= (D2 >= 0);

ok &= (D2 <= S);

if(!ok){

puts("No");

return 0;

}

// 3. dp更新.

dp[0][0] = true;

rep(i, N){

// 3-1. 今回分設定.

dp[i + 1] = dp[i];

// 3-2. dpを左シフトしたものを考慮.

dp[i + 1] <<= D[i];

// 3-3. 前回分を反映.

dp[i + 1] |= dp[i];

}

// 4. 例外をチェック.

if(!dp[N][D1] || !dp[N][D2]){

puts("No");

return 0;

}

// 5. 経路の復元.

// -> 以下のような変換ルールが, 発生したと見做す.

// 上: (0, +D) -> (+D, -D) -- +D --> (+2D, 0) -- /2 --> (+D, 0)

// 下: (0, -D) -> (-D, +D) -- +D --> (0, +2D) -- /2 --> (0, +D)

// 左: (-D, 0) -> (-D, -D) -- +D --> (0, 0) -- /2 --> (0, 0)

// 右: (+D, 0) -> (+D, +D) -- +D --> (+2D, +2D) -- /2 --> (+D, +D)

string ans = "";

int curX = D1, curY = D2;

repr(i, N - 1, 0){

// 上.

if(curX - D[i] >= 0 && dp[i][curX - D[i]] && dp[i][curY]){

// 経路情報.

ans.pb('U');

// 今回分反映.

curX -= D[i];

curY -= 0;

// 次へ.

continue;

}

// 下.

if(curY - D[i] >= 0 && dp[i][curX] && dp[i][curY - D[i]]){

// 経路情報.

ans.pb('D');

// 今回分反映.

curX -= 0;

curY -= D[i];

// 次へ.

continue;

}

// 左.

if(dp[i][curX] && dp[i][curY]){

// 経路情報.

ans.pb('L');

// 今回分反映.

curX -= 0;

curY -= 0;

// 次へ.

continue;

}

// 右.

if(curX - D[i] >= 0 && curY - D[i] >= 0 && dp[i][curX - D[i]] && dp[i][curY - D[i]]){

// 経路情報.

ans.pb('R');

// 今回分反映.

curX -= D[i];

curY -= D[i];

// 次へ.

continue;

}

// 6. 反転.

reverse(all(ans));

// 7. 出力.

puts("Yes");

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

return 0;

}

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

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

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

[入力例]
2 1 0
1 6

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

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

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

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

[入力例]
11 15 13
3 1 4 1 5 9 2 6 5 3 5

[出力例]
Yes
DRRRDRUUUUU

[入力例]
31 62 27
7 6 60 1 6 8 3 7 9 3 3 19 9 8 8 9 3 54 4 4 3 27 18 5 3 3 7 19 5 55 13

[出力例]
Yes
RRDDRRDRRDDRDDUDUDUUUUUUUUUUUUU

[入力例]

3 2 -2

1 2 3

[出力例]

Yes

LDR

※AtCoderのテストケースより

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

Yes

URD

[入力例]

2 1 0

1 6

[出力例]

※AtCoderのテストケースより

[入力例]

5 6 7

1 3 5 7 9

[出力例]

Yes

LRLUR

※AtCoderのテストケースより

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

Yes

LUDRU

[入力例]

11 15 13

3 1 4 1 5 9 2 6 5 3 5

[出力例]

Yes

DRRRDRUUUUU

[入力例]

31 62 27

7 6 60 1 6 8 3 7 9 3 3 19 9 8 8 9 3 54 4 4 3 27 18 5 3 3 7 19 5 55 13

[出力例]

Yes

RRDDRRDRRDDRDDUDUDUUUUUUUUUUUUU

■参照サイト
AtCoder Beginner Contest 221

2021年10月11日2021年10月11日

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

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

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

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

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

// C++(GCC 9.2.1)
// 解き直し.
// https://atcoder.jp/contests/abc221/editorial/2723
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vs = vector<set<int>>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
const LL MOD = 998244353;

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    vs G(N);
    rep(i, N - 1){
        int u, v;
        scanf("%d %d", &u, &v);
        u--;
        v--;
        G[u].insert(v);
        G[v].insert(u);
    }
    
    // 2. bfs(最短距離).
    // https://ja.wikipedia.org/wiki/幅優先探索
    auto bfs = [&](vs &G, int s, int* d){
        // 空のキュー.
        queue<int> q;
        
        // 探索地点 s をキュー q に追加.
        q.push(s);
        while(!q.empty()){
            // キューから取り出す.
            int u = q.front();
            q.pop();
            
            // 取り出した要素を処理.
            for(auto &e : G[u]){
                // 未訪問の頂点を処理.
                if(d[e])   continue;
                if(e != s) d[e] = d[u] + 1, q.push(e);
            }
        }
        return;
    };
    
    // 3. bfs(連結成分).
    // https://ja.wikipedia.org/wiki/幅優先探索
    auto bfs2 = [&](vs &G, int s, int* c, int l){
        // 空のキュー.
        queue<int> q;
        
        // 連結成分番号を設定.
        c[s] = l;
        
        // 探索地点 s をキュー q に追加.
        q.push(s);
        while(!q.empty()){
            // キューから取り出す.
            int u = q.front();
            q.pop();
            
            // 取り出した要素を処理.
            for(auto &e : G[u]){
                // 未訪問の頂点を処理.
                if(c[e])   continue;
                if(e != s) c[e] = l, q.push(e);
            }
        }
        return;
    };
    
    // 4. 直径 の 両端 の 頂点 x, y は？
    // 4-1. 頂点 1 から 各頂点までの距離を保存.
    int d1[N], dx[N], dy[N];
    rep(i, N) d1[i] = dx[i] = dy[i] = 0;
    bfs(G, 0, d1);
    
    // 4-2. 頂点 1 から 最も遠い 頂点 x を保存.
    int x = -1, r = 0;
    rep(i, N){
        if(r < d1[i]){
            r = max(r, d1[i]);
            x = i;
        }
    }
    assert(x != -1);
    
    // 4-3. 頂点 x から 各頂点までの距離を保存.
    bfs(G, x, dx);
    
    // 4-4. 頂点 x から 最も遠い 頂点 y を保存.
    int y = -1;
    r = 0;
    rep(i, N){
        if(r < dx[i]){
            r = max(r, dx[i]);
            y = i;
        }
    }
    assert(y != -1);
    
    // 4-5. 頂点 y から 各頂点までの距離を保存.
    bfs(G, y, dy);
    
    // 4-6. 直径 D は？
    int D = dx[y];
    
    // 5. 直径の偶奇に応じて, 場合の数を計算.
    // 5-1. 直径 D が 奇数.
    // ex.
    // 2
    // 1 2
    // -> 1 が 正解のはず.
    // -> hand_00.txt で, WA版 だったため, ロジック修正.
    LL ans = 1;
    if(D & 1){
        // 頂点 A, B を 抽出.
        int a = -1, b = -1;
        int D1 = (D - 1) / 2;
        int D2 = (D + 1) / 2;
        rep(i, N){
            if(dx[i] == D1 && dy[i] == D2) a = i;
            if(dx[i] == D2 && dy[i] == D1) b = i;
        }
        assert(a != -1);
        assert(b != -1);
        
        // グラフから, 辺 (a, b) を 除外.
        G[a].erase(b);
        G[b].erase(a);
        
        // 頂点 A から 各頂点までの距離を保存.
        int da[N], db[N];
        rep(i, N) da[i] = db[i] = 0;
        bfs(G, a, da);
        
        // 頂点 B から 各頂点までの距離を保存.
        bfs(G, b, db);
        
        // 頂点 A から, 距離 (D - 1) / 2 の 頂点数.
        LL m1 = 0;
        rep(i, N) if(da[i] == D1 && i != a) m1++;
        
        // 頂点 B から, 距離 (D - 1) / 2 の 頂点数.
        LL m2 = 0;
        rep(i, N) if(db[i] == D1 && i != b) m2++;
        
        // 場合の数を集計.
        ans = m1 * m2 % MOD;
    }
    
    // 5-2. 直径 D が 偶数.
    if(!(D & 1)){
        // 頂点 C を 抽出.
        int c = -1;
        int D3 = D / 2;
        rep(i, N){
             if(dx[i] == D3 && dy[i] == D3){
                 c = i;
                 break;
             }
        }
        assert(c != -1);
        
        // 頂点 C から 各頂点までの距離を保存.
        int dc[N];
        rep(i, N) dc[i] = 0;
        bfs(G, c, dc);
        
        // グラフから, 頂点 C と 繋がっている辺を削除.
        G[c].clear();
        rep(i, N) G[i].erase(c);
        
        // 部分木 に 分割.
        int connection[N], idx = 0;
        rep(i, N) connection[i] = 0;
        rep(i, N) if(!connection[i]) bfs2(G, i, connection, ++idx);
        
        // 部分木 ごとに m[i] を 計算.
        // 頂点 C からの距離が, D / 2 であるものを集計.
        LL m[idx + 1];
        rep(i, idx + 1) m[i] = 0;
        rep(i, N) if(dc[i] == D3) m[connection[i]]++;
        
        // 場合の数を集計.
        repx(i, 1, idx + 1){
            ans *= (m[i] + 1);
            ans %= MOD;
        }
        repx(i, 1, idx + 1){
            ans += MOD;
            ans -= m[i];
        }
        ans += MOD;
        ans--;
        ans %= MOD;
    }
    
    // 6. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

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

// C++(GCC 9.2.1)

// 解き直し.

// https://atcoder.jp/contests/abc221/editorial/2723

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vs = vector<set<int>>;

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

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

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

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

#define pb push_back

const LL MOD = 998244353;

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

vs G(N);

rep(i, N - 1){

int u, v;

scanf("%d %d", &u, &v);

u--;

v--;

G[u].insert(v);

G[v].insert(u);

}

// 2. bfs(最短距離).

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

auto bfs = [&](vs &G, int s, int* d){

// 空のキュー.

queue<int> q;

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

q.push(s);

while(!q.empty()){

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

int u = q.front();

q.pop();

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

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

// 未訪問の頂点を処理.

if(d[e]) continue;

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

}

return;

};

// 3. bfs(連結成分).

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

auto bfs2 = [&](vs &G, int s, int* c, int l){

// 空のキュー.

queue<int> q;

// 連結成分番号を設定.

c[s] = l;

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

q.push(s);

while(!q.empty()){

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

int u = q.front();

q.pop();

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

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

// 未訪問の頂点を処理.

if(c[e]) continue;

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

}

return;

};

// 4. 直径の両端の頂点 x, y は？

// 4-1. 頂点 1 から各頂点までの距離を保存.

int d1[N], dx[N], dy[N];

rep(i, N) d1[i] = dx[i] = dy[i] = 0;

bfs(G, 0, d1);

// 4-2. 頂点 1 から最も遠い頂点 x を保存.

int x = -1, r = 0;

rep(i, N){

if(r < d1[i]){

r = max(r, d1[i]);

x = i;

}

assert(x != -1);

// 4-3. 頂点 x から各頂点までの距離を保存.

bfs(G, x, dx);

// 4-4. 頂点 x から最も遠い頂点 y を保存.

int y = -1;

r = 0;

rep(i, N){

if(r < dx[i]){

r = max(r, dx[i]);

y = i;

}

assert(y != -1);

// 4-5. 頂点 y から各頂点までの距離を保存.

bfs(G, y, dy);

// 4-6. 直径 D は？

int D = dx[y];

// 5. 直径の偶奇に応じて, 場合の数を計算.

// 5-1. 直径 D が奇数.

// ex.

// 2

// 1 2

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

// -> hand_00.txt で, WA版だったため, ロジック修正.

LL ans = 1;

if(D & 1){

// 頂点 A, B を抽出.

int a = -1, b = -1;

int D1 = (D - 1) / 2;

int D2 = (D + 1) / 2;

rep(i, N){

if(dx[i] == D1 && dy[i] == D2) a = i;

if(dx[i] == D2 && dy[i] == D1) b = i;

}

assert(a != -1);

assert(b != -1);

// グラフから, 辺 (a, b) を除外.

G[a].erase(b);

G[b].erase(a);

// 頂点 A から各頂点までの距離を保存.

int da[N], db[N];

rep(i, N) da[i] = db[i] = 0;

bfs(G, a, da);

// 頂点 B から各頂点までの距離を保存.

bfs(G, b, db);

// 頂点 A から, 距離 (D - 1) / 2 の頂点数.

LL m1 = 0;

rep(i, N) if(da[i] == D1 && i != a) m1++;

// 頂点 B から, 距離 (D - 1) / 2 の頂点数.

LL m2 = 0;

rep(i, N) if(db[i] == D1 && i != b) m2++;

// 場合の数を集計.

ans = m1 * m2 % MOD;

}

// 5-2. 直径 D が偶数.

if(!(D & 1)){

// 頂点 C を抽出.

int c = -1;

int D3 = D / 2;

rep(i, N){

if(dx[i] == D3 && dy[i] == D3){

c = i;

break;

}

assert(c != -1);

// 頂点 C から各頂点までの距離を保存.

int dc[N];

rep(i, N) dc[i] = 0;

bfs(G, c, dc);

// グラフから, 頂点 C と繋がっている辺を削除.

G[c].clear();

rep(i, N) G[i].erase(c);

// 部分木に分割.

int connection[N], idx = 0;

rep(i, N) connection[i] = 0;

rep(i, N) if(!connection[i]) bfs2(G, i, connection, ++idx);

// 部分木ごとに m[i] を計算.

// 頂点 C からの距離が, D / 2 であるものを集計.

LL m[idx + 1];

rep(i, idx + 1) m[i] = 0;

rep(i, N) if(dc[i] == D3) m[connection[i]]++;

// 場合の数を集計.

repx(i, 1, idx + 1){

ans *= (m[i] + 1);

ans %= MOD;

}

repx(i, 1, idx + 1){

ans += MOD;

ans -= m[i];

}

ans += MOD;

ans--;

ans %= MOD;

}

// 6. 出力.

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

return 0;

}

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

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

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

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

[入力例]
2
1 2

[出力例]
1

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

[出力例]
20

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

[出力例]
6

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

[出力例]
753

[入力例]

1 2

1 3

1 4

4 5

[出力例]

※AtCoderのテストケースより

[入力例]

1 2

1 3

1 4

[出力例]

※AtCoderのテストケースより

[入力例]

1 2

[出力例]

[入力例]

1 2

1 3

1 4

3 5

3 6

2 9

2 10

4 7

4 8

[出力例]

[入力例]

1 2

2 3

3 4

3 5

5 10

5 12

2 9

2 8

1 11

1 6

1 7

[出力例]

[入力例]

1 3

3 6

3 5

3 2

3 4

5 11

5 12

5 19

4 9

4 10

4 17

2 7

2 8

2 18

1 15

1 16

6 13

6 14

6 20

[出力例]

753

■参照サイト
AtCoder Beginner Contest 221

2021年10月10日2021年10月11日

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

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

■感想.
1. 問題Eは, 方針が見えなかったので, 解説を参考にして, ようやく, AC版に到達出来た.
2. Binary Indexed Tree の復習が出来たので, 非常に良かったと思う.
※ 公式のライブラリを拝借させて頂いてます.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/abc221/editorial/2718
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using P = pair<LL, int>;
using vp = vector<P>;
#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 LL MOD = 998244353;
LL mPow2Mod[303030], pPow2Mod[303030];

// Binary Indexed Tree (Fenwick Tree)
// https://youtu.be/lyHk98daDJo?t=7960
template<typename T>
struct BIT{
    int n;
    vector<T> d;
    BIT(int n = 0) : n(n), d(n + 1) {}
    void add(int i, T x = 1){
        for(i++; i <= n; i += i & -i) d[i] += x;
    }
    T sum(int i){
        T x = 0;
        for(i++; i; i -= i & -i) x += d[i];
        return x;
    }
    T sum(int l, int r){
        return sum(r - 1) - sum(l - 1);
    }
};

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    map<P, int> m;
    vp v;
    rep(i, N){
        LL a;
        scanf("%lld", &a);
        P p = {a, i + 1};
        m[p] = 0;
        v.pb(p);
    }
    
    // 2. 2 の 冪乗(正／負).
    pPow2Mod[0] = mPow2Mod[0] = 1;
    rep(i, N + 1){
        pPow2Mod[i + 1] = (2         * pPow2Mod[i]) % MOD; // 正.
        mPow2Mod[i + 1] = (499122177 * mPow2Mod[i]) % MOD; // 負.
    }
    
    // 3. 座標圧縮.
    int idx = 0;
    for(auto &p : m) p.b = ++idx;
    
    // 4. 集計(解説通り).
    // ex.
    // 5
    // 2 1 1 3 2
    // -> {整数列 A の 要素(座標圧縮), BIT の 加算位置} 
    //    = {{2, 3}, {1, 1}, {1, 2}, {3, 5}, {2, 4}} のように 番号付けしておく.
    // 
    // B[1] = 0                     (BIT の 位置 3 に, 1 / 2  を 加算, 位置 2 までの総和)
    // B[2] = 0                     (BIT の 位置 1 に, 1 / 4  を 加算, 位置 0 までの総和)
    // B[3] = 1 / 4                 (BIT の 位置 2 に, 1 / 8  を 加算, 位置 1 までの総和)
    // B[4] = 1 / 4 + 1 / 8 + 1 / 2 (BIT の 位置 5 に, 1 / 16 を 加算, 位置 4 までの総和)
    // B[5] = 1 / 4 + 1 / 8 + 1 / 2 (BIT の 位置 4 に, 1 / 32 を 加算, 位置 3 までの総和)
    // -> よって, これらを集計すると, 22 が 計算結果と分かる.
    // ans = B[1] * 1 + B[2] * 2 + B[3] * 4 + B[4] * 8 + B[5] * 16 
    //     = 0 + 0 + 1 + 7 + 14
    //     = 22
    BIT<LL> ft(N + 1);
    LL ans = 0;
    rep(j, N){
        // 整数列 A の 要素 を 取得.
        P p = v[j];
        
        // BIT の 加算位置.
        int i = m[p];
        
        // 上記の場所に, 2 の 冪乗(負) を 加算.
        ft.add(i, mPow2Mod[j + 1]);
        
        // 区間[1, i) の 合計は？
        LL t = ft.sum(1, i) % MOD;
        
        // 計算結果に, 2 の 冪乗(正) を 乗算.
        t *= pPow2Mod[j];
        t %= MOD;
        
        // 集計.
        ans += t;
        ans %= MOD;
    }
    
    // 5. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

// 解き直し.

// https://atcoder.jp/contests/abc221/editorial/2718

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using P = pair<LL, int>;

using vp = vector;

#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 LL MOD = 998244353;

LL mPow2Mod[303030], pPow2Mod[303030];

// Binary Indexed Tree (Fenwick Tree)

// https://youtu.be/lyHk98daDJo?t=7960

template<typename T>

struct BIT{

int n;

vector<T> d;

BIT(int n = 0) : n(n), d(n + 1) {}

void add(int i, T x = 1){

for(i++; i <= n; i += i & -i) d[i] += x;

}

T sum(int i){

T x = 0;

for(i++; i; i -= i & -i) x += d[i];

return x;

}

T sum(int l, int r){

return sum(r - 1) - sum(l - 1);

}

};

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

map<P, int> m;

vp v;

rep(i, N){

LL a;

scanf("%lld", &a);

P p = {a, i + 1};

m[p] = 0;

v.pb(p);

}

// 2. 2 の冪乗(正／負).

pPow2Mod[0] = mPow2Mod[0] = 1;

rep(i, N + 1){

pPow2Mod[i + 1] = (2 * pPow2Mod[i]) % MOD; // 正.

mPow2Mod[i + 1] = (499122177 * mPow2Mod[i]) % MOD; // 負.

}

// 3. 座標圧縮.

int idx = 0;

for(auto &p : m) p.b = ++idx;

// 4. 集計(解説通り).

// ex.

// 5

// 2 1 1 3 2

// -> {整数列 A の要素(座標圧縮), BIT の加算位置}

// = {{2, 3}, {1, 1}, {1, 2}, {3, 5}, {2, 4}} のように番号付けしておく.

// B[1] = 0 (BIT の位置 3 に, 1 / 2 を加算, 位置 2 までの総和)

// B[2] = 0 (BIT の位置 1 に, 1 / 4 を加算, 位置 0 までの総和)

// B[3] = 1 / 4 (BIT の位置 2 に, 1 / 8 を加算, 位置 1 までの総和)

// B[4] = 1 / 4 + 1 / 8 + 1 / 2 (BIT の位置 5 に, 1 / 16 を加算, 位置 4 までの総和)

// B[5] = 1 / 4 + 1 / 8 + 1 / 2 (BIT の位置 4 に, 1 / 32 を加算, 位置 3 までの総和)

// -> よって, これらを集計すると, 22 が計算結果と分かる.

// ans = B[1] * 1 + B[2] * 2 + B[3] * 4 + B[4] * 8 + B[5] * 16

// = 0 + 0 + 1 + 7 + 14

// = 22

BIT<LL> ft(N + 1);

LL ans = 0;

rep(j, N){

// 整数列 A の要素を取得.

P p = v[j];

// BIT の加算位置.

int i = m[p];

// 上記の場所に, 2 の冪乗(負) を加算.

ft.add(i, mPow2Mod[j + 1]);

// 区間[1, i) の合計は？

LL t = ft.sum(1, i) % MOD;

// 計算結果に, 2 の冪乗(正) を乗算.

t *= pPow2Mod[j];

t %= MOD;

// 集計.

ans += t;

ans %= MOD;

}

// 5. 出力.

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

return 0;

}

[入力例]
3
1 2 1

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

[入力例]
3
1 2 2

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

[入力例]
3
3 2 1

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

[入力例]
10
198495780 28463047 859606611 212983738 946249513 789612890 782044670 700201033 367981604 302538501

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

[入力例]
5
2 1 1 3 2

[出力例]
22

[入力例]
12
7 1 8 12 10 1 7 1 2 3 2 7

[出力例]
2200

[入力例]
18
314 159 265 358 979 323 846 264 338 327 950 288 419 716 939 937 510 582

[出力例]
250796

[入力例]
50
77745357 56007369 14690761 15009778 16318676 543635 19285990 4665389 90156959 65710387 107007503 121452200 23627366 4481012 64288587 25502259 50766845 116813365 109065726 107219346 77674249 111528089 33125962 84048543 73052930 55805907 24566041 121284805 26215078 1741646 111161611 9771733 60086045 37896454 121038472 115137410 86356996 63491557 10084559 67313402 9936219 89391420 42994141 16709204 4292008 70006319 45320316 31282562 11880272 93106029

[出力例]
669312650

[入力例]

1 2 1

[出力例]

※AtCoderテストケースより

[入力例]

1 2 2

[出力例]

※AtCoderテストケースより

[入力例]

3 2 1

[出力例]

※AtCoderテストケースより

[入力例]

198495780 28463047 859606611 212983738 946249513 789612890 782044670 700201033 367981604 302538501

[出力例]

830

※AtCoderテストケースより

[入力例]

2 1 1 3 2

[出力例]

[入力例]

7 1 8 12 10 1 7 1 2 3 2 7

[出力例]

2200

[入力例]

314 159 265 358 979 323 846 264 338 327 950 288 419 716 939 937 510 582

[出力例]

250796

[入力例]

77745357 56007369 14690761 15009778 16318676 543635 19285990 4665389 90156959 65710387 107007503 121452200 23627366 4481012 64288587 25502259 50766845 116813365 109065726 107219346 77674249 111528089 33125962 84048543 73052930 55805907 24566041 121284805 26215078 1741646 111161611 9771733 60086045 37896454 121038472 115137410 86356996 63491557 10084559 67313402 9936219 89391420 42994141 16709204 4292008 70006319 45320316 31282562 11880272 93106029

[出力例]

669312650

■参照サイト
AtCoder Beginner Contest 221
Binary Indexed Tree (Fenwick Tree)

2021年10月7日

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

C++の練習を兼ねて, AtCoder Beginner Contest 221 の問題C (Select Mul) ～問題D (Online games) を解いてみた.

■感想.
1. 問題C, D は, 方針を絞り込めたので, AC版に到達できたと思う.
2. いもす法の復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

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

int main(){
    
    // 1. 入力情報.
    char x[22];
    scanf("%s", x);
    string N(x);
    
    // 2. 分離後の二数の積を全探索.
    int ans = 0, n = N.size();
    vi z(n);
    iota(all(z), 0);
    do{
        rep(i, n / 2){
            // 二数に分離.
            string s1 = "";
            string s2 = "";
            rep(j, i + 1)     s1.pb(N[z[j]]);
            repx(j, i + 1, n) s2.pb(N[z[j]]);
            
            // 先頭が, '0' か？
            if(s1[0] == '0' || s2[0] == '0') continue;
            
            // 二数の積.
            int n1 = stoi(s1);
            int n2 = stoi(s2);
            
            // 最大値更新.
            ans = max(ans, n1 * n2);
        }
    }while(next_permutation(all(z)));
    
    // 3. 出力.
    printf("%d\n", ans);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

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

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

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

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

#define pb push_back

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

int main(){

// 1. 入力情報.

char x[22];

scanf("%s", x);

string N(x);

// 2. 分離後の二数の積を全探索.

int ans = 0, n = N.size();

vi z(n);

iota(all(z), 0);

do{

rep(i, n / 2){

// 二数に分離.

string s1 = "";

string s2 = "";

rep(j, i + 1) s1.pb(N[z[j]]);

repx(j, i + 1, n) s2.pb(N[z[j]]);

// 先頭が, '0' か？

if(s1[0] == '0' || s2[0] == '0') continue;

// 二数の積.

int n1 = stoi(s1);

int n2 = stoi(s2);

// 最大値更新.

ans = max(ans, n1 * n2);

}

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

// 3. 出力.

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

return 0;

}

[入力例]
123

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

[入力例]
1010

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

[入力例]
998244353

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

[入力例]
2021

[出力例]
420

[入力例]
314159265

[出力例]
623527551

[入力例]
173205080

[出力例]
624912000

[入力例]

123

[出力例]

※AtCoderテストケースより

[入力例]

1010

[出力例]

100

※AtCoderテストケースより

[入力例]

998244353

[出力例]

939337176

※AtCoderテストケースより

[入力例]

2021

[出力例]

420

[入力例]

314159265

[出力例]

623527551

[入力例]

173205080

[出力例]

624912000

■C++版プログラム(問題D／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
LL a[202020], b[202020], ans[202020];
int c[404040];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    map<LL, int> im;
    map<int, LL> om;
    rep(i, N){
        scanf("%lld %lld", &a[i], &b[i]);
        im[a[i]] = 0;
        im[a[i] + b[i]] = 0;
    }
    
    // 2. 番号付け.
    int idx = -1;
    for(auto &p : im) p.b = ++idx, om[idx] = p.a;
    
    // 3. いもす法.
    rep(i, N){
        int l = im[a[i]];
        int r = im[a[i] + b[i]];
        c[l]++;
        c[r]--;
    }
    rep(i, 400000) c[i + 1] += c[i];
    
    // 4. k人がログインしていた日数.
    rep(i, 400000) ans[c[i]] += om[i + 1] - om[i];
    
    // 5. 出力.
    repx(i, 1, N + 1){
        printf("%lld", ans[i]);
        printf("%s", (i < N) ? " " : "\n");
    }
    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

LL a[202020], b[202020], ans[202020];

int c[404040];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

map<LL, int> im;

map<int, LL> om;

rep(i, N){

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

im[a[i]] = 0;

im[a[i] + b[i]] = 0;

}

// 2. 番号付け.

int idx = -1;

for(auto &p : im) p.b = ++idx, om[idx] = p.a;

// 3. いもす法.

rep(i, N){

int l = im[a[i]];

int r = im[a[i] + b[i]];

c[l]++;

c[r]--;

}

rep(i, 400000) c[i + 1] += c[i];

// 4. k人がログインしていた日数.

rep(i, 400000) ans[c[i]] += om[i + 1] - om[i];

// 5. 出力.

repx(i, 1, N + 1){

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

printf("%s", (i < N) ? " " : "\n");

}

return 0;

}

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

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

[入力例]
2
1000000000 1000000000
1000000000 1000000000

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

[入力例]
10
29 113
29 21
100 52
15 58
85 89
38 72
44 7
12 42
30 87
72 114

[出力例]
15 36 10 56 34 17 6 0 0 0

[入力例]
25
8642 9550
3534 5649
3177 4693
898 7837
3207 7538
11877 7261
6821 6304
8743 213
5200 10755
4530 10628
7694 1049
8492 9985
3108 9020
6921 10630
7481 4095
493 4566
8699 5737
2279 7706
6404 7709
11787 5039
8220 9497
7817 851
10152 5571
10144 7799
5539 2309

[出力例]
1066 1666 1078 295 196 1052 2008 1100 1430 1139 423 1918 3291 1488 433 62 0 0 0 0 0 0 0 0 0

[入力例]
50
106993193 110506795
52775875 93411737
58018201 76224909
10744043 8169294
65389174 25786656
85246147 96407126
8357758 83421294
47672496 62059620
85986379 39563845
62913817 107693619
47410286 99119327
117431975 36082668
99982039 80945023
53858763 119274201
63989315 87845094
15977620 14635186
26635628 107530968
96859987 18732383
50253111 49618390
99750465 122485976
23644033 51034554
14851679 36874388
15653638 55430517
78536425 115668447
207787 116135293
91217773 22887742
70638978 116239554
77819066 116028254
110968843 64273162
37752441 14081788
26432536 1833150
59889650 99660574
87080799 56031237
115222597 69051605
85844657 37146399
41362872 9604546
65235927 78184476
83556947 116427610
60575320 91698260
104769068 64143291
93331849 24615529
100866735 67411609
69168973 92662727
118036814 43409596
46570811 44040167
66152426 69582203
106945431 70741959
102770017 15526819
78050972 52740724
11939312 8779499

[出力例]
12886424 19901716 6974954 3269919 10695969 14661924 11717289 7564208 5020793 3898645 9607743 5111284 2380747 2972512 7522142 1631902 2049433 6798833 7398089 5735514 6235426 5362523 4456409 906877 9113869 7240208 6607709 4380632 7144754 4558219 8048914 3927706 6245368 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

[入力例]

1 2

2 3

3 1

[出力例]

2 2 0

※AtCoderテストケースより

[入力例]

1000000000 1000000000

[出力例]

0 1000000000

※AtCoderテストケースより

[入力例]

29 113

29 21

100 52

15 58

85 89

38 72

44 7

12 42

30 87

72 114

[出力例]

15 36 10 56 34 17 6 0 0 0

[入力例]

8642 9550

3534 5649

3177 4693

898 7837

3207 7538

11877 7261

6821 6304

8743 213

5200 10755

4530 10628

7694 1049

8492 9985

3108 9020

6921 10630

7481 4095

493 4566

8699 5737

2279 7706

6404 7709

11787 5039

8220 9497

7817 851

10152 5571

10144 7799

5539 2309

[出力例]

1066 1666 1078 295 196 1052 2008 1100 1430 1139 423 1918 3291 1488 433 62 0 0 0 0 0 0 0 0 0

[入力例]

106993193 110506795

52775875 93411737

58018201 76224909

10744043 8169294

65389174 25786656

85246147 96407126

8357758 83421294

47672496 62059620

85986379 39563845

62913817 107693619

47410286 99119327

117431975 36082668

99982039 80945023

53858763 119274201

63989315 87845094

15977620 14635186

26635628 107530968

96859987 18732383

50253111 49618390

99750465 122485976

23644033 51034554

14851679 36874388

15653638 55430517

78536425 115668447

207787 116135293

91217773 22887742

70638978 116239554

77819066 116028254

110968843 64273162

37752441 14081788

26432536 1833150

59889650 99660574

87080799 56031237

115222597 69051605

85844657 37146399

41362872 9604546

65235927 78184476

83556947 116427610

60575320 91698260

104769068 64143291

93331849 24615529

100866735 67411609

69168973 92662727

118036814 43409596

46570811 44040167

66152426 69582203

106945431 70741959

102770017 15526819

78050972 52740724

11939312 8779499

[出力例]

12886424 19901716 6974954 3269919 10695969 14661924 11717289 7564208 5020793 3898645 9607743 5111284 2380747 2972512 7522142 1631902 2049433 6798833 7398089 5735514 6235426 5362523 4456409 906877 9113869 7240208 6607709 4380632 7144754 4558219 8048914 3927706 6245368 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

■参照サイト
AtCoder Beginner Contest 221

2021年10月4日

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

C++の練習を兼ねて, AtCoder Beginner Contest 218 の問題H (Red and Blue Lamps) を解いてみた.

■感想.
1. 問題H は, 方針が見えなかったので, 解説を参考に実装したところ AC版に到達できた.
2. 個人的には, 実装に苦労したものの, 解説のロジックが, 非常に面白く感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/abc218/editorial/2602
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using P = pair<LL, int>;
using PQ = priority_queue<P>;
#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
LL b[202020];

int main(){
    
    // 1. 入力情報.
    int N, R;
    scanf("%d %d", &N, &R);
    set<int> st; // インデックス(操作時に使う予定).
    st.insert(N - 1);
    rep(i, N - 1){
        int a;
        scanf("%lld", &a);
        b[i + 0] += a;
        b[i + 1] += a;
        st.insert(i);
    }
    
    // 2. sort.
    PQ pq;
    rep(i, N) pq.push({b[i], i});
    
    // 3. R回繰り返す.
    R = min(R, N - R);
    LL ans = 0;
    while(!pq.empty() && R > 0){
        // 要素を取り出す.
        P u = pq.top();
        pq.pop();
        LL r = u.a;
        int i = u.b;
        
        // 左端, 右端 の インデックス.
        int idxL = *st.begin();
        int idxR = *(--st.end());
        
        // 左端 の 場合.
        bool ok = false;
        if(i == idxL){
            // 報酬加算.
            ans += r;
            
            // B[0], B[1]削除
            st.erase(st.begin());
            st.erase(st.begin());
            
            // フラグ更新.
            ok = true;
        }
        
        // 右端 の 場合.
        if(i == idxR){
            // 報酬加算.
            ans += r;
            
            // B[N], B[N - 1]削除.
            st.erase(--st.end());
            st.erase(--st.end());
            
            // フラグ更新.
            ok = true;
        }
        
        // それ以外 の 場合.
        if(i != idxL && i != idxR){
            // 存在しない場合.
            if(!st.count(i)) continue;
            
            // 報酬加算.
            ans += r;
            
            // B[i - 1], B[i], B[i + 1]取得.
            auto it = st.lower_bound(i);
            ++it;
            int tIdxR = *it;
            --it;
            --it;
            int tIdxL = *it;
            
            // B[i]更新.
            b[i] = b[tIdxL] - b[i] + b[tIdxR];
            
            // 追加.
            pq.push({b[i], i});
            
            // B[i - 1], B[i + 1]削除.
            st.erase(tIdxL);
            st.erase(tIdxR);
            
            // フラグ更新.
            ok = true;
        }
        
        // デクリメント.
        if(ok) R--;
    }
    
    // 4. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

// 解き直し.

// https://atcoder.jp/contests/abc218/editorial/2602

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using P = pair<LL, int>;

using PQ = priority_queue;

#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

LL b[202020];

int main(){

// 1. 入力情報.

int N, R;

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

set<int> st; // インデックス(操作時に使う予定).

st.insert(N - 1);

rep(i, N - 1){

int a;

scanf("%lld", &a);

b[i + 0] += a;

b[i + 1] += a;

st.insert(i);

}

// 2. sort.

PQ pq;

rep(i, N) pq.push({b[i], i});

// 3. R回繰り返す.

R = min(R, N - R);

LL ans = 0;

while(!pq.empty() && R > 0){

// 要素を取り出す.

P u = pq.top();

pq.pop();

LL r = u.a;

int i = u.b;

// 左端, 右端のインデックス.

int idxL = *st.begin();

int idxR = *(--st.end());

// 左端の場合.

bool ok = false;

if(i == idxL){

// 報酬加算.

ans += r;

// B[0], B[1]削除

st.erase(st.begin());

// フラグ更新.

ok = true;

}

// 右端の場合.

if(i == idxR){

// 報酬加算.

ans += r;

// B[N], B[N - 1]削除.

st.erase(--st.end());

// フラグ更新.

ok = true;

}

// それ以外の場合.

if(i != idxL && i != idxR){

// 存在しない場合.

if(!st.count(i)) continue;

// 報酬加算.

ans += r;

// B[i - 1], B[i], B[i + 1]取得.

auto it = st.lower_bound(i);

++it;

int tIdxR = *it;

--it;

int tIdxL = *it;

// B[i]更新.

b[i] = b[tIdxL] - b[i] + b[tIdxR];

// 追加.

pq.push({b[i], i});

// B[i - 1], B[i + 1]削除.

st.erase(tIdxL);

st.erase(tIdxR);

// フラグ更新.

ok = true;

}

// デクリメント.

if(ok) R--;

}

// 4. 出力.

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

return 0;

}

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

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

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

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

[入力例]
11 7
12345 678 90123 45678901 234567 89012 3456 78901 23456 7890

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

[入力例]
6 2
36 48 38 17 53

[出力例]
156

[入力例]
19 5
314 159 265 358 979 323 846 264 338 327 950 288 419 716 939 937 510 582

[出力例]
6885

[入力例]
20 12
32 31 42 15 30 42 48 32 49 50 52 20 8 53 18 5 39 34 52

[出力例]
600

[入力例]
50 7
110253291 6598438 106440061 28086927 26995611 26360301 28139813 91640793 43706518 73883983 76021961 1862112 110168433 1690248 12891670 122635038 14674036 32936523 57191454 113582837 108343620 76232476 37982706 69888172 48331131 59780499 46229096 49313209 75487258 24643503 115387228 84672747 16152296 88398861 107703767 101929368 60941425 107935538 122741402 98294501 72886527 97016986 43783312 88844825 110587306 21450700 38539034 55714661 5368450

[出力例]
1390868077

[入力例]

6 2

3 1 4 1 5

[出力例]

※AtCoderテストケースより

[入力例]

7 6

2 7 1 8 2 8

[出力例]

※AtCoderテストケースより

[入力例]

11 7

12345 678 90123 45678901 234567 89012 3456 78901 23456 7890

[出力例]

46207983

※AtCoderテストケースより

[入力例]

6 2

36 48 38 17 53

[出力例]

156

[入力例]

19 5

314 159 265 358 979 323 846 264 338 327 950 288 419 716 939 937 510 582

[出力例]

6885

[入力例]

20 12

32 31 42 15 30 42 48 32 49 50 52 20 8 53 18 5 39 34 52

[出力例]

600

[入力例]

50 7

110253291 6598438 106440061 28086927 26995611 26360301 28139813 91640793 43706518 73883983 76021961 1862112 110168433 1690248 12891670 122635038 14674036 32936523 57191454 113582837 108343620 76232476 37982706 69888172 48331131 59780499 46229096 49313209 75487258 24643503 115387228 84672747 16152296 88398861 107703767 101929368 60941425 107935538 122741402 98294501 72886527 97016986 43783312 88844825 110587306 21450700 38539034 55714661 5368450

[出力例]

1390868077

■参照サイト
AtCoder Beginner Contest 218

2021年10月3日2021年10月3日

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

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

■感想.
1. 問題C は, 方針が見えなかったので, 解説を参考に実装したところ AC版に到達できた.
2. 個人的には, 解説のロジックが, 不思議な感じがするとともに, 非常に面白く感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/arc127/editorial/2688
// 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 pb push_back

int main(){
    
    // 1. 入力情報.
    int N;
    char c[1010101];
    scanf("%d %s", &N, c);
    string s(c);
    
    // 2. (X - 1)作成.
    // ex.
    // N = 7, X = 1010 -> X - 1 = 0001001 を 作成.
    int l = s.size();
    int n = N - l;
    int x[N];
    int at = -1;
    repr(i, l - 1, 0){
        if(s[i] == '1'){
            at = i;
            break;
        }
    }
    rep(i, n) x[i] = 0;
    repx(i, n, n + at) x[i] = s[i - n] - '0';
    x[n + at] = 0;
    repx(i, n + at + 1, N) x[i] = 1;
    // rep(i, N) printf("%d", x[i]);
    // puts("");
    
    // 3. 文字列作成.
    // ex.
    // N = 5
    // X = 10110
    // -> X - 1 は, 10101.
    // N = 5.
    // B 10000
    // X 10101
    // -> 1 (X - 10000 を 計算)
    // 
    // N = 4
    // B 01000
    // X 00101
    // -> 10 (X - 00001 を 計算)
    // 
    // N = 3
    // B 00100
    // X 00100
    // -> 101 (X - 00100 を 計算)
    // 
    // N = 2
    // B 00010
    // X 00000
    // -> X が 0 となったので終了.
    // -> 1 + 101 = 1101 が出力されると理解.
    string ans = "";
    rep(i, N){
        // X[i] が 1.
        if(x[i]){
            x[i] = 0;
            ans.pb('1');
            continue;
        }
        
        // X[i] が 0.
        // 一番後ろの 1 の場所は？
        int cur = -1;
        repr(j, N - 1, 0){
            if(x[j]){
                cur = j;
                break;
            }
        }
        
        // X が 0(終了).
        if(cur == -1) break;
        
        // X[N - 1] が 1.
        if(cur == N - 1) x[N - 1] = 0;
        
        // X[N - 1] が 0.
        if(cur < N - 1){
            x[cur] = 0;
            repr(j, N - 1, cur + 1) x[j] = 1;
        }
        
        // '0' を 追加.
        ans.pb('0');
    }
    
    // 4. 先頭に, '1' を 追加.
    ans = "1" + ans;
    
    // 5. 出力.
    printf("%s\n", ans.c_str());
    return 0;
    
}

100

101

102

103

104

105

106

107

// 解き直し.

// https://atcoder.jp/contests/arc127/editorial/2688

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

int main(){

// 1. 入力情報.

int N;

char c[1010101];

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

string s(c);

// 2. (X - 1)作成.

// ex.

// N = 7, X = 1010 -> X - 1 = 0001001 を作成.

int l = s.size();

int n = N - l;

int x[N];

int at = -1;

repr(i, l - 1, 0){

if(s[i] == '1'){

at = i;

break;

}

rep(i, n) x[i] = 0;

repx(i, n, n + at) x[i] = s[i - n] - '0';

x[n + at] = 0;

repx(i, n + at + 1, N) x[i] = 1;

// rep(i, N) printf("%d", x[i]);

// puts("");

// 3. 文字列作成.

// ex.

// N = 5

// X = 10110

// -> X - 1 は, 10101.

// N = 5.

// B 10000

// X 10101

// -> 1 (X - 10000 を計算)

// N = 4

// B 01000

// X 00101

// -> 10 (X - 00001 を計算)

// N = 3

// B 00100

// X 00100

// -> 101 (X - 00100 を計算)

// N = 2

// B 00010

// X 00000

// -> X が 0 となったので終了.

// -> 1 + 101 = 1101 が出力されると理解.

string ans = "";

rep(i, N){

// X[i] が 1.

if(x[i]){

x[i] = 0;

ans.pb('1');

continue;

}

// X[i] が 0.

// 一番後ろの 1 の場所は？

int cur = -1;

repr(j, N - 1, 0){

if(x[j]){

cur = j;

break;

}

// X が 0(終了).

if(cur == -1) break;

// X[N - 1] が 1.

if(cur == N - 1) x[N - 1] = 0;

// X[N - 1] が 0.

if(cur < N - 1){

x[cur] = 0;

repr(j, N - 1, cur + 1) x[j] = 1;

}

// '0' を追加.

ans.pb('0');

}

// 4. 先頭に, '1' を追加.

ans = "1" + ans;

// 5. 出力.

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

return 0;

}

[入力例]
3
101

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

[入力例]
10
10100011

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

[入力例]
1000000
11111

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

[入力例]
4
1010

[出力例]
110

[入力例]
4
101

[出力例]
1001

[入力例]
5
10110

[出力例]
1101

[入力例]
31
11000111010010101001100101111

[出力例]
100110001110100101010011001

[入力例]
200
1100010111011011011111101001111010010111100001010001010110110110011110110000011010101101010000010001010000100100010101101010000111111101011111101000001100110000100001000011101100101110100000011011010

[出力例]
1011000101110110110111111010011110100101111000010100010101101101100111101100000110101011010100000100010100001001000101011010100001111111010111111010000011001100001000010000111011001011101000000011101

[入力例]
2021
1010111111010011000111001001111000100001011111010000101110010100001111101111111111010010001000110010000001111001001110111000101001000100011001000001101011110000110101101110010100101001100011010010000100101111110100110001110010011110001000010111110100001011100101000011111011111111110100100010001100100000011110010011101110001010010001000110010000011010111100001101011011100101001010011000110100100001001011111101001100011100100111100010000101111101000010111001010000111110111111111101001000100011001000000111100100111011100010100100010001100100000110101111000011010110111001010010100110001101001000010010111111010011000111001001111000100001011111010000101110010100001111101111111111010010001000110010000001111001001110111000101001000100011001000001101011110000110101101110010100101001100011010010000100101111110100110001110010011110001000010111110100001011100101000011111011111111110100100010001100100000011110010011101110001010010001000110010000011010111100001101011011100101001010011000110100100001

[出力例]
10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000101011111101001100011100100111100010000101111101000010111001010000111110111111111101001000100011001000000111100100111011100010100100010001100100000110101111000011010110111001010010100110001101001000010010111111010011000111001001111000100001011111010000101110010100001111101111111111010010001000110010000001111001001110111000101001000100011001000001101011110000110101101110010100101001100011010010000100101111110100110001110010011110001000010111110100001011100101000011111011111111110100100010001100100000011110010011101110001010010001000110010000011010111100001101011011100101001010011000110100100001001011111101001100011100100111100010000101111101000010111001010000111110111111111101001000100011001000000111100100111011100010100100010001100100000110101111000011010110111001010010100110001101001000010010111111010011000111001001111000100001011111010000101110010100001111101111111111010010001000110010000001111001001110111000101001000100011001000001101011110000110101101110010100101001100001110010001

[入力例]

101

[出力例]

※AtCoderのテストケースより

[入力例]

10100011

[出力例]

1001001111

※AtCoderのテストケースより

[入力例]

1000000

11111

[出力例]

1000000000000000000000000000000

※AtCoderのテストケースより

[入力例]

1010

[出力例]

110

[入力例]

101

[出力例]

1001

[入力例]

10110

[出力例]

1101

[入力例]

11000111010010101001100101111

[出力例]

100110001110100101010011001

[入力例]

200

1100010111011011011111101001111010010111100001010001010110110110011110110000011010101101010000010001010000100100010101101010000111111101011111101000001100110000100001000011101100101110100000011011010

[出力例]

1011000101110110110111111010011110100101111000010100010101101101100111101100000110101011010100000100010100001001000101011010100001111111010111111010000011001100001000010000111011001011101000000011101

[入力例]

2021

1010111111010011000111001001111000100001011111010000101110010100001111101111111111010010001000110010000001111001001110111000101001000100011001000001101011110000110101101110010100101001100011010010000100101111110100110001110010011110001000010111110100001011100101000011111011111111110100100010001100100000011110010011101110001010010001000110010000011010111100001101011011100101001010011000110100100001001011111101001100011100100111100010000101111101000010111001010000111110111111111101001000100011001000000111100100111011100010100100010001100100000110101111000011010110111001010010100110001101001000010010111111010011000111001001111000100001011111010000101110010100001111101111111111010010001000110010000001111001001110111000101001000100011001000001101011110000110101101110010100101001100011010010000100101111110100110001110010011110001000010111110100001011100101000011111011111111110100100010001100100000011110010011101110001010010001000110010000011010111100001101011011100101001010011000110100100001

[出力例]

10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000101011111101001100011100100111100010000101111101000010111001010000111110111111111101001000100011001000000111100100111011100010100100010001100100000110101111000011010110111001010010100110001101001000010010111111010011000111001001111000100001011111010000101110010100001111101111111111010010001000110010000001111001001110111000101001000100011001000001101011110000110101101110010100101001100011010010000100101111110100110001110010011110001000010111110100001011100101000011111011111111110100100010001100100000011110010011101110001010010001000110010000011010111100001101011011100101001010011000110100100001001011111101001100011100100111100010000101111101000010111001010000111110111111111101001000100011001000000111100100111011100010100100010001100100000110101111000011010110111001010010100110001101001000010010111111010011000111001001111000100001011111010000101110010100001111101111111111010010001000110010000001111001001110111000101001000100011001000001101011110000110101101110010100101001100001110010001

■参照サイト
AtCoder Regular Contest 127

2021年10月1日

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

C++の練習を兼ねて, AtCoder Regular Contest 127 の問題A (Leading 1s) ～問題B (Ternary Strings) を解いてみた.

■感想.
1. 問題A, B ともに, 方針が見えなかったので, 解説を参考に実装したところ AC版に到達できた.
2. 個人的には, 両問とも, 不思議な印象を持つ問題に見え, 非常に面白く感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/arc127/editorial/2686
// 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 pob pop_back
#define pub push_back

int main(){
    
    // 1. 入力情報.
    LL N;
    scanf("%lld", &N);
    
    // 2. 集計(解説通り).
    LL ans = 0;
    repx(i, 1, 16){
        // 範囲を作成.
        // ex.
        // 先頭が, 11111 の 場合.
        // [11111,         11112)
        // [111110,       111120)
        // [1111100,     1111200)
        // [11111000,   11112000)
        // .....
        string s(i, '1');
        string g = s;
        g.pob();
        g.pub('2');
        
        rep(j, 17 - i){
            // '0' を 追加.
            string cz(j, '0');
            string cs = s + cz;
            string cg = g + cz;
            
            // 数値化.
            LL ns = stoll(cs);
            LL ng = stoll(cg);
            
            // N以下の部分を集計.
            ans += max(0LL, min(N - ns + 1, ng - ns));
        }
    }
    
    // 3. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc127/editorial/2686

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

#define pub push_back

int main(){

// 1. 入力情報.

LL N;

scanf("%lld", &N);

// 2. 集計(解説通り).

LL ans = 0;

repx(i, 1, 16){

// 範囲を作成.

// ex.

// 先頭が, 11111 の場合.

// [11111, 11112)

// [111110, 111120)

// [1111100, 1111200)

// [11111000, 11112000)

// .....

string s(i, '1');

string g = s;

g.pob();

g.pub('2');

rep(j, 17 - i){

// '0' を追加.

string cz(j, '0');

string cs = s + cz;

string cg = g + cz;

// 数値化.

LL ns = stoll(cs);

LL ng = stoll(cg);

// N以下の部分を集計.

ans += max(0LL, min(N - ns + 1, ng - ns));

}

// 3. 出力.

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

return 0;

}

[入力例]
11

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

[入力例]
120

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

[入力例]
987654321

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

[入力例]
1010

[出力例]
134

[入力例]
202109252000

[出力例]
123456790122

[入力例]
101010101010101

[出力例]
13355780022446

[入力例]

[出力例]

※AtCoderのテストケースより

[入力例]

120

[出力例]

※AtCoderのテストケースより

[入力例]

987654321

[出力例]

123456789

※AtCoderのテストケースより

[入力例]

1010

[出力例]

134

[入力例]

202109252000

[出力例]

123456790122

[入力例]

101010101010101

[出力例]

13355780022446

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

// 解き直し.
// https://atcoder.jp/contests/arc127/editorial/2687
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vs = vector<string>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
#define all(x) x.begin(), x.end()

int main(){
    
    // 1. 入力情報.
    int N, L;
    scanf("%d %d", &N, &L);
    
    // 2. 基準とする三進数(解説通り).
    vs v1;
    int b = 2, idx = 0;
    while(++idx < L) b *= 3;
    rep(i, N){
        // 対象とする整数.
        int cur = b + i;
        
        // 三進数作成.
        string s = "";
        while(cur){
            int r = cur % 3;
            s.pb(r + '0');
            cur /= 3;
        }
        
        // 反転.
        reverse(all(s));
        
        // 保存.
        v1.pb(s);
    }
    
    // 3. 三進数(別パターン).
    // '0' -> '1'
    // '1' -> '2'
    // '2' -> '0'
    vs v2;
    for(auto &p : v1){
        // 変換.
        string q = "";
        rep(i, L){
            if(p[i] == '0') q.pb('1');
            if(p[i] == '1') q.pb('2');
            if(p[i] == '2') q.pb('0');
        }
        
        // 保存.
        v2.pb(q);
    }
    
    // 4. 三進数(別パターン).
    // '0' -> '2'
    // '1' -> '0'
    // '2' -> '1'
    vs v3;
    for(auto &p : v1){
        // 変換.
        string q = "";
        rep(i, L){
            if(p[i] == '0') q.pb('2');
            if(p[i] == '1') q.pb('0');
            if(p[i] == '2') q.pb('1');
        }
        
        // 保存.
        v3.pb(q);
    }
    
    // 5. sort(不要に見えるが念のため).
    vs ans;
    for(auto &p : v1) ans.pb(p);
    for(auto &p : v2) ans.pb(p);
    for(auto &p : v3) ans.pb(p);
    sort(all(ans));
    
    // 6. 出力.
    for(auto &p : ans) printf("%s\n", p.c_str());
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc127/editorial/2687

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vs = vector<string>;

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

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

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

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

#define pb push_back

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

int main(){

// 1. 入力情報.

int N, L;

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

// 2. 基準とする三進数(解説通り).

vs v1;

int b = 2, idx = 0;

while(++idx < L) b *= 3;

rep(i, N){

// 対象とする整数.

int cur = b + i;

// 三進数作成.

string s = "";

while(cur){

int r = cur % 3;

s.pb(r + '0');

cur /= 3;

}

// 反転.

reverse(all(s));

// 保存.

v1.pb(s);

}

// 3. 三進数(別パターン).

// '0' -> '1'

// '1' -> '2'

// '2' -> '0'

vs v2;

for(auto &p : v1){

// 変換.

string q = "";

rep(i, L){

if(p[i] == '0') q.pb('1');

if(p[i] == '1') q.pb('2');

if(p[i] == '2') q.pb('0');

}

// 保存.

v2.pb(q);

}

// 4. 三進数(別パターン).

// '0' -> '2'

// '1' -> '0'

// '2' -> '1'

vs v3;

for(auto &p : v1){

// 変換.

string q = "";

rep(i, L){

if(p[i] == '0') q.pb('2');

if(p[i] == '1') q.pb('0');

if(p[i] == '2') q.pb('1');

}

// 保存.

v3.pb(q);

}

// 5. sort(不要に見えるが念のため).

vs ans;

for(auto &p : v1) ans.pb(p);

for(auto &p : v2) ans.pb(p);

for(auto &p : v3) ans.pb(p);

sort(all(ans));

// 6. 出力.

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

return 0;

}

[入力例]
2 2

[出力例]
00
02
11
12
20
21
※AtCoderのテストケースより

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

[入力例]
3 2

[出力例]
00
01
02
10
11
12
20
21
22

[入力例]
4 3

[出力例]
010
011
012
021
102
120
121
122
200
201
202
210

[入力例]
5 3

[出力例]
010
011
012
021
022
100
102
120
121
122
200
201
202
210
211

[入力例]
6 5

[出力例]
01110
01111
01112
01120
01121
01122
12200
12201
12202
12220
12221
12222
20000
20001
20002
20010
20011
20012

[入力例]

2 2

[出力例]

※AtCoderのテストケースより

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

[入力例]

3 2

[出力例]

[入力例]

4 3

[出力例]

010

011

012

021

102

120

121

122

200

201

202

210

[入力例]

5 3

[出力例]

010

011

012

021

022

100

102

120

121

122

200

201

202

210

211

[入力例]

6 5

[出力例]

01110

01111

01112

01120

01121

01122

12200

12201

12202

12220

12221

12222

20000

20001

20002

20010

20011

20012

■参照サイト
AtCoder Regular Contest 127

2021年9月30日

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

C++の練習を兼ねて, AtCoder Beginner Contest 220 の問題G (Isosceles Trapezium) を解いてみた.

■感想.
1. 問題G は, 方針が見えなかったので, 解説を参考に実装したところ AC版に到達できた.
2. 個人的には, 垂直二等分線を考えて分類していくという方針が, 面白いと感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/abc220/editorial/2684
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using T3 = tuple<LL, 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 all(x) x.begin(), x.end()
LL x[1010], y[1010], c[1010];

struct info{
    LL x, y, c; // 二点 x, y 座標 の 合計(中点比較用), 重みの和.
    bool operator < (const info& rhs) const{
        return (c > rhs.c);
    }
};

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%lld %lld %lld", &x[i], &y[i], &c[i]);
    
    // 2. 二点について, 垂直二等分線などを集計.
    map<T3, int> m;
    int idx = -1;
    vector<vector<info>> v(N * N);
    rep(i, N){
        repx(j, i + 1, N){
            // i -> j の ベクトル.
            LL dx = x[j] - x[i];
            LL dy = y[j] - y[i];
            
            // 最大公約数で割る.
            LL g  = __gcd(abs(dx), abs(dy));
            dx /= g;
            dy /= g;
            
            // 垂直二等分線(傾き).
            // -> ベクトル(a, b) の 形で, a >= 0 となるように保存.
            LL a = -dy;
            LL b = dx;
            if(a < 0){
                a = -a;
                b = -b;
            }
            
            // a が 0 の ケース を 考慮.
            // -> 013.txt などのテストケースで, WA版となった原因と推測.
            // -> b の 符号は, 負にならないように修正.
            if(a == 0) b = abs(b);
            
            // 垂直二等分線(切片).
            // -> 直線 b * x - a * y + a * k = 0 を 保存するイメージ.
            //    但し, 切片は, 整数で保存したいので, 二点 x, y 座標 の 合計
            //    をベースに計算した値を保存.
            LL tx = x[i] + x[j];
            LL ty = y[i] + y[j];
            LL tc = c[i] + c[j];
            LL k = a * ty - b * tx;
            
            // 垂直二等分線が一致するグループごとに分類.
            T3 t = {a, b, k};
            if(!m.count(t)) m[t] = ++idx;
            info cur;
            cur.c = tc;
            cur.x = tx;
            cur.y = ty;
            v[m[t]].pb(cur);
        }
    }
    
    // 3. 選んだ４点の重みの和の最大値.
    LL ans = -1;
    rep(i, idx){
        // sort.
        sort(all(v[i]));
        
        // 先頭要素.
        info s = v[i][0];
        
        // 最大値更新.
        repx(j, 1, v[i].size()){
            // その他の要素.
            info g = v[i][j];
            
            // 中点が一致するか？
            bool ok = (s.x == g.x) && (s.y == g.y);
            
            // 中点が一致しなければ, 最大値更新.
            if(!ok) ans = max(ans, s.c + g.c);
        }
    }
    
    // 4. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

100

101

102

103

104

105

// 解き直し.

// https://atcoder.jp/contests/abc220/editorial/2684

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using T3 = tuple<LL, 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 all(x) x.begin(), x.end()

LL x[1010], y[1010], c[1010];

struct info{

LL x, y, c; // 二点 x, y 座標の合計(中点比較用), 重みの和.

bool operator < (const info& rhs) const{

return (c > rhs.c);

}

};

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

rep(i, N) scanf("%lld %lld %lld", &x[i], &y[i], &c[i]);

// 2. 二点について, 垂直二等分線などを集計.

map<T3, int> m;

int idx = -1;

vector<vector<info>> v(N * N);

rep(i, N){

repx(j, i + 1, N){

// i -> j のベクトル.

LL dx = x[j] - x[i];

LL dy = y[j] - y[i];

// 最大公約数で割る.

LL g = __gcd(abs(dx), abs(dy));

dx /= g;

dy /= g;

// 垂直二等分線(傾き).

// -> ベクトル(a, b) の形で, a >= 0 となるように保存.

LL a = -dy;

LL b = dx;

if(a < 0){

a = -a;

b = -b;

}

// a が 0 のケースを考慮.

// -> 013.txt などのテストケースで, WA版となった原因と推測.

// -> b の符号は, 負にならないように修正.

if(a == 0) b = abs(b);

// 垂直二等分線(切片).

// -> 直線 b * x - a * y + a * k = 0 を保存するイメージ.

// 但し, 切片は, 整数で保存したいので, 二点 x, y 座標の合計

// をベースに計算した値を保存.

LL tx = x[i] + x[j];

LL ty = y[i] + y[j];

LL tc = c[i] + c[j];

LL k = a * ty - b * tx;

// 垂直二等分線が一致するグループごとに分類.

T3 t = {a, b, k};

if(!m.count(t)) m[t] = ++idx;

info cur;

cur.c = tc;

cur.x = tx;

cur.y = ty;

v[m[t]].pb(cur);

}

// 3. 選んだ４点の重みの和の最大値.

LL ans = -1;

rep(i, idx){

// sort.

sort(all(v[i]));

// 先頭要素.

info s = v[i][0];

// 最大値更新.

repx(j, 1, v[i].size()){

// その他の要素.

info g = v[i][j];

// 中点が一致するか？

bool ok = (s.x == g.x) && (s.y == g.y);

// 中点が一致しなければ, 最大値更新.

if(!ok) ans = max(ans, s.c + g.c);

}

// 4. 出力.

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

return 0;

}

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

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

[入力例]
6
0 1 1
1 4 20
2 7 300
5 6 4000
4 3 50000
3 0 600000

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

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

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

[入力例]
12
0 0 5
5 0 7
2 0 6
3 0 5
-1 1 7
6 1 4
-2 3 20
7 3 1
-2 0 13
7 0 3
-6 5 11
11 5 3

[出力例]
37

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

[出力例]
25

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

[出力例]
17

[入力例]

0 3 10

3 3 10

-1 0 10

2 0 10000

4 0 10

[出力例]

※AtCoderのテストケースより

[入力例]

0 1 1

1 4 20

2 7 300

5 6 4000

4 3 50000

3 0 600000

[出力例]

650021

※AtCoderのテストケースより

[入力例]

-3 0 1

-2 0 1

-1 0 1

0 0 1

1 0 1

2 0 1

3 0 1

[出力例]

-1

※AtCoderのテストケースより

[入力例]

0 0 5

5 0 7

2 0 6

3 0 5

-1 1 7

6 1 4

-2 3 20

7 3 1

-2 0 13

7 0 3

-6 5 11

11 5 3

[出力例]

[入力例]

1 0 5

0 3 7

3 -1 2

1 5 6

6 0 3

4 6 4

-10 8 11

-4 10 7

[出力例]

[入力例]

0 1 5

0 3 7

-1 -1 3

-1 5 2

[出力例]

■参照サイト
AtCoder Beginner Contest 220

2021年9月29日

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

C++の練習を兼ねて, AtCoder Beginner Contest 220 の問題F (Distance Sums 2) を解いてみた.

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

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

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

// 解き直し.
// https://atcoder.jp/contests/abc220/editorial/2693
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vvi = vector<vector<int>>;
using P = pair<LL, int>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
#define a first
#define b second
LL subTree[202020]; // 部分木の大きさ.
LL dp[202020];      // 木dp.
int p[202020];      // 親頂点.

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    vvi G(N);
    rep(i, N - 1){
        int u, v;
        scanf("%d %d", &u, &v);
        u--, v--;
        G[u].pb(v);
        G[v].pb(u);
    }
    
    // 2. 頂点 1 から 各頂点までの距離を計算.
    // https://ja.wikipedia.org/wiki/幅優先探索
    auto bfs = [&](vvi &G, int s, int* d){
        // 2-1. 空のキュー.
        queue<int> q;
        
        // 2-2. 探索地点 s をキュー q に追加.
        q.push(s);
        while(!q.empty()){
            // 2-3. キューから取り出す.
            int u = q.front();
            q.pop();
            
            // 2-4. 取り出した要素を処理.
            for(auto &e : G[u]){
                // 2-5. 未訪問の頂点を処理.
                if(!d[e] && e != s) d[e] = d[u] + 1, q.push(e);
            }
        }
        return;
    };
    int d[N];
    rep(i, N) d[i] = 0;
    bfs(G, 0, d);
    
    // 3. 頂点 1 から 遠い順, 近い順 に 並び替え.
    // 3-1. {距離, 頂点番号} を 保存.
    priority_queue<P> fPq;
    priority_queue<P, vector<P>, greater<P>> nPq;
    rep(i, N){
        fPq.push({d[i], i});
        nPq.push({d[i], i});
    }
    
    // 3-2. 頂点 1 を 除外.
    nPq.pop();
    
    // 4. 部分木サイズなど.
    while(!fPq.empty()){
        // 4-1. 頂点 v を 取り出す.
        P i = fPq.top();
        fPq.pop();
        int v = i.b;
        
        // 4-2. 部分木更新.
        // -> 自頂点(サイズ 1)をカウント.
        subTree[v]++;
        
        // 4-3. 頂点 v を 根とする部分木.
        for(auto &u : G[v]){
            // 頂点 v の 子頂点 u を 選択.
            if(d[u] > d[v]){
                // 子頂点 u の 部分木サイズ を 加算.
                subTree[v] += subTree[u];
                
                // 親頂点 v を 保存.
                p[u] = v;
            }
        }
    }
    
    // 5. 木dp更新.
    rep(i, N) dp[0] += d[i];
    while(!nPq.empty()){
        // 5-1. 頂点 u を 取り出す.
        P i = nPq.top();
        nPq.pop();
        int u = i.b;
        
        // 5-2. 頂点 u について, dp更新.
        dp[u] = dp[p[u]] + (LL)N - 2 * subTree[u];
    }
    
    // 6. 出力.
    rep(i, N) printf("%lld\n", dp[i]);
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

110

111

// 解き直し.

// https://atcoder.jp/contests/abc220/editorial/2693

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vvi = vector<vector<int>>;

using P = pair<LL, int>;

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

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

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

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

#define pb push_back

#define a first

#define b second

LL subTree[202020]; // 部分木の大きさ.

LL dp[202020]; // 木dp.

int p[202020]; // 親頂点.

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

vvi G(N);

rep(i, N - 1){

int u, v;

scanf("%d %d", &u, &v);

u--, v--;

G[u].pb(v);

G[v].pb(u);

}

// 2. 頂点 1 から各頂点までの距離を計算.

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

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

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

queue<int> q;

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

q.push(s);

while(!q.empty()){

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

int u = q.front();

q.pop();

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

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

// 2-5. 未訪問の頂点を処理.

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

}

return;

};

int d[N];

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

bfs(G, 0, d);

// 3. 頂点 1 から遠い順, 近い順に並び替え.

// 3-1. {距離, 頂点番号} を保存.

priority_queue fPq;

priority_queue<P, vector, greater> nPq;

rep(i, N){

fPq.push({d[i], i});

nPq.push({d[i], i});

}

// 3-2. 頂点 1 を除外.

nPq.pop();

// 4. 部分木サイズなど.

while(!fPq.empty()){

// 4-1. 頂点 v を取り出す.

P i = fPq.top();

fPq.pop();

int v = i.b;

// 4-2. 部分木更新.

// -> 自頂点(サイズ 1)をカウント.

subTree[v]++;

// 4-3. 頂点 v を根とする部分木.

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

// 頂点 v の子頂点 u を選択.

if(d[u] > d[v]){

// 子頂点 u の部分木サイズを加算.

subTree[v] += subTree[u];

// 親頂点 v を保存.

p[u] = v;

}

// 5. 木dp更新.

rep(i, N) dp[0] += d[i];

while(!nPq.empty()){

// 5-1. 頂点 u を取り出す.

P i = nPq.top();

nPq.pop();

int u = i.b;

// 5-2. 頂点 u について, dp更新.

dp[u] = dp[p[u]] + (LL)N - 2 * subTree[u];

}

// 6. 出力.

rep(i, N) printf("%lld\n", dp[i]);

return 0;

}

[入力例]
3
1 2
2 3

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

[入力例]
2
1 2

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

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

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

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

[出力例]
18
22
30
30
16
24
28
20
28
24

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

[出力例]
100
93
88
117
117
111
87
90
110
140
140
140
136
159
159
113
97
120
108
125
131
131
148
148
148

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

[入力例]

1 2

2 3

[出力例]

※AtCoderテストケースより

[入力例]

1 2

[出力例]

※AtCoderテストケースより

[入力例]

1 6

1 5

1 3

1 4

1 2

[出力例]

※AtCoderテストケースより

[入力例]

1 2

1 5

2 3

2 4

5 6

5 8

5 10

7 8

8 9

[出力例]

[入力例]

1 2

2 3

1 4

1 5

4 10

4 11

4 12

5 13

13 14

13 15

3 6

3 7

7 8

7 9

8 16

8 17

17 18

17 19

19 20

19 21

19 22

20 23

20 24

20 25

[出力例]

100

117

111

110

140

136

159

113

120

108

125

131

148

■参照サイト
AtCoder Beginner Contest 220

2021年9月28日

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

C++の練習を兼ねて, AtCoder Beginner Contest 220 の問題E (Distance on Large Perfect Binary Tree) を解いてみた.

■感想.
1. 問題E は, 方針が見えなかったので, 解説を参考に実装したところ AC版に到達できた.
2. 数え上げを正確に実装する部分で, 苦労したように思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/abc220/editorial/2679
// 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
const LL MOD = 998244353;

int main(){
    
    // 1. 入力情報.
    int N, D;
    scanf("%d %d", &N, &D);
    
    // 2. 2 の 冪乗.
    vl mPow;
    mPow.pb(1);
    rep(i, N * 2){
        LL p = mPow.back();
        p <<= 1;
        p %= MOD;
        mPow.pb(p);
    }
    
    // 3. 深さ d ごとに集計.
    LL ans = 0;
    int n = N - 1;
    rep(d, N){
        // 3-1. 頂点 v が, i or j.
        LL f = 0;
        if(d + D <= n) f += mPow[D];
        
        // 3-2. それ以外.
        // -> 区間[d + 1, d + (D - 1)] から, x を 選択したときに,
        // d + k, d + (D - k) が, いずれも, (N - 1)以下になる場合, 集計.
        // -> 但し, k は, 0 < k < D を 満たす必要があるので, 範囲を求める際に, 要注意.
        if(D >= 2 && ((n - d) * 2 >= D)){
            int l = max(1,     min(n - d, d + D - n));
            int r = min(D - 1, max(n - d, d + D - n));
            f += mPow[D - 2] * (LL)(r - l + 1);
        }
        
        // 3-3. 集計.
        // -> 深さが d であるような頂点数は, mPow[d]個と見る.
        // -> なお, (i, j), (j, i) を 区別するため, 2通り.
        ans += f % MOD * 2LL % MOD * mPow[d] % MOD; 
        ans %= MOD;
    }
    
    // 4. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc220/editorial/2679

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

const LL MOD = 998244353;

int main(){

// 1. 入力情報.

int N, D;

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

// 2. 2 の冪乗.

vl mPow;

mPow.pb(1);

rep(i, N * 2){

LL p = mPow.back();

p <<= 1;

p %= MOD;

mPow.pb(p);

}

// 3. 深さ d ごとに集計.

LL ans = 0;

int n = N - 1;

rep(d, N){

// 3-1. 頂点 v が, i or j.

LL f = 0;

if(d + D <= n) f += mPow[D];

// 3-2. それ以外.

// -> 区間[d + 1, d + (D - 1)] から, x を選択したときに,

// d + k, d + (D - k) が, いずれも, (N - 1)以下になる場合, 集計.

// -> 但し, k は, 0 < k < D を満たす必要があるので, 範囲を求める際に, 要注意.

if(D >= 2 && ((n - d) * 2 >= D)){

int l = max(1, min(n - d, d + D - n));

int r = min(D - 1, max(n - d, d + D - n));

f += mPow[D - 2] * (LL)(r - l + 1);

}

// 3-3. 集計.

// -> 深さが d であるような頂点数は, mPow[d]個と見る.

// -> なお, (i, j), (j, i) を区別するため, 2通り.

ans += f % MOD * 2LL % MOD * mPow[d] % MOD;

ans %= MOD;

}

// 4. 出力.

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

return 0;

}

[入力例]
3 2

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

[入力例]
14142 17320

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

[入力例]
2 1

[出力例]
4

[入力例]
3 1

[出力例]
12

[入力例]
3 3

[出力例]
8

[入力例]
10 16

[出力例]
163840

[入力例]
2021 928

[出力例]
525614051

[入力例]
314159 265358

[出力例]
663838476

[入力例]

3 2

[出力例]

※AtCoderテストケースより

[入力例]

14142 17320

[出力例]

11284501

※AtCoderテストケースより

[入力例]

2 1

[出力例]

[入力例]

3 1

[出力例]

[入力例]

3 3

[出力例]

[入力例]

10 16

[出力例]

163840

[入力例]

2021 928

[出力例]

525614051

[入力例]

314159 265358

[出力例]

663838476

■参照サイト
AtCoder Beginner Contest 220

C++の練習を兼ねて, AtCoder Beginner Contest 221 の 問題G (Jumping sequence) を解いてみた.

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

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

C++の練習を兼ねて, AtCoder Beginner Contest 221 の 問題C (Select Mul) ～ 問題D (Online games) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 218 の 問題H (Red and Blue Lamps) を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 127 の 問題A (Leading 1s) ～ 問題B (Ternary Strings) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 220 の 問題G (Isosceles Trapezium) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 220 の 問題F (Distance Sums 2) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 220 の 問題E (Distance on Large Perfect Binary Tree) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 221 の問題G (Jumping sequence) を解いてみた.

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

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

C++の練習を兼ねて, AtCoder Beginner Contest 221 の問題C (Select Mul) ～問題D (Online games) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 218 の問題H (Red and Blue Lamps) を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 127 の問題A (Leading 1s) ～問題B (Ternary Strings) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 220 の問題G (Isosceles Trapezium) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 220 の問題F (Distance Sums 2) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 220 の問題E (Distance on Large Perfect Binary Tree) を解いてみた.