個人用メモ帳

2020年5月2日

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

C++の練習を兼ねて, AtCoder Regular Contest 026 の問題C (C – 蛍光灯) を解いてみた.

■感想.
1. 方針が全く分からなかったので, 解説を確認して, 実装したところ, 何とかAC版となった.
2. 遅延評価セグメント木が必要なため, 下記のライブラリを拝借させて頂いた.
3. 遅延評価セグメント木の復習が出来たので, 良かった思う.
4. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

本家のサイトARC 026 解説をご覧下さい.

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

// 解き直し.
// https://www.slideshare.net/chokudai/arc026
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
#define all(x) x.begin(), x.end()
#define INF 101010101010
LL dp[101010];

struct light{
    int l, r; // 蛍光灯の左端, 右端.
    LL c;     // 蛍光灯を点灯するのにかかる費用.
    bool operator < (const light& rhs) const{
        if(l != rhs.l) return l < rhs.l;
        else           return r > rhs.r;
    }
};

// ※※※ 以下のライブラリを使用(一部改変) ※※※.
// 遅延評価セグメント木をソラで書きたいあなたに.
// http://tsutaj.hatenablog.com/entry/2017/03/30/224339
// http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2236726
struct LazySegmentTree{
private:
    int n;
    vector<LL> node, lazy;
public:
    LazySegmentTree(vector<LL> v){
        int sz = (int)v.size();
        n = 1; while(n < sz) n *= 2;
        node.resize(2 * n - 1);
        lazy.resize(2 * n - 1, 0);
        // 元配列 の 値 を, セグメント木のノード に 保存.
        rep(i, sz) node[i + n - 1] = v[i];
        repr(i, n - 2, 0) node[i] = node[i * 2 + 1] + node[i * 2 + 2];
    }
    void eval(int k, int l, int r){
        if(lazy[k] != 0) {
            node[k] = lazy[k];
            if(r - l > 1) {
                lazy[2 * k + 1] += lazy[k] / 2;
                lazy[2 * k + 2] += lazy[k] / 2;
            }
            lazy[k] = 0;
        }
    }
    void update(int a, int b, LL x, int k = 0, int l = 0, int r = -1){
        if(r < 0) r = n;
        eval(k, l, r);
        if(b <= l || r <= a) return;
        if(a <= l && r <= b){
            lazy[k] = x;
            eval(k, l, r);
        }else{
            update(a, b, x, 2 * k + 1,           l, (l + r) / 2);
            update(a, b, x, 2 * k + 2, (l + r) / 2,           r);
            node[k] = min(node[2 * k + 1], node[2 * k + 2]);
        }
    }
    LL query(int a, int b, int k = 0, int l = 0, int r = -1){
        if(r < 0) r = n;
        eval(k, l, r);
        if(b <= l || r <= a) return INF;
        if(a <= l && r <= b) return node[k];
        LL vl = query(a, b, 2 * k + 1,           l, (l + r) / 2);
        LL vr = query(a, b, 2 * k + 2, (l + r) / 2,           r);
        return min(vl, vr);
    }

};

int main(){
    
    // 1. 入力情報.
    int N, L;
    scanf("%d %d", &N, &L);
    
    // 2. 蛍光灯を保存.
    vector<light> v;
    rep(i, N){
        int l, r;
        LL c;
        scanf("%d %d %lld", &l, &r, &c);
        light x;
        x.l = l + 1, x.r = r + 1, x.c = c;
        v.pb(x);
    }
    
    // 以下, 解説通り.
    // 3. sort.
    sort(all(v));
    
    // 4. 遅延伝播セグメント木を用意.
    LazySegmentTree seg(vector<LL>(101010, 0));
    rep(i, 101010) dp[i] = INF;
    repx(i, 1, 101010) seg.update(i, i + 1, INF);
    
    // 5. dp更新.
    rep(i, N){
        // 蛍光灯の情報を一つ取得.
        int l = v[i].l;
        int r = v[i].r;
        LL c  = v[i].c;
        
        // dp[l] ～ dp[r] の 最小値 を 取得.
        LL tmp = seg.query(l - 1, r);
        
        // dp[r] の 更新.
        dp[r] = min(dp[r], tmp + c);
        
        // SegmentTree の 更新.
        seg.update(r - 1, r, dp[r]);
        
        // printf("l=%d r=%d c=%lld tmp=%lld\n", l, r, c, tmp);
        // rep(i, L + 2) printf("%lld ", seg.query(i, i + 1));
        // puts("");
        // rep(i, L + 2) printf("%lld ", dp[i]);
        // puts("");
    }
    
    // 6. 出力.
    // rep(i, L + 2) printf("%lld ", dp[i]);
    // puts("");
    printf("%lld\n", dp[L + 1]);
    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

// 解き直し.

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

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

#define pb push_back

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

#define INF 101010101010

LL dp[101010];

struct light{

int l, r; // 蛍光灯の左端, 右端.

LL c; // 蛍光灯を点灯するのにかかる費用.

bool operator < (const light& rhs) const{

if(l != rhs.l) return l < rhs.l;

else return r > rhs.r;

}

};

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

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

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

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

struct LazySegmentTree{

private:

int n;

vector<LL> node, lazy;

public:

LazySegmentTree(vector<LL> v){

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

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

node.resize(2 * n - 1);

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

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

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

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

}

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

if(lazy[k] != 0) {

node[k] = lazy[k];

if(r - l > 1) {

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

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

}

lazy[k] = 0;

}

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

if(r < 0) r = n;

eval(k, l, r);

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

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

lazy[k] = x;

eval(k, l, r);

}else{

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

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

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

}

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

if(r < 0) r = n;

eval(k, l, r);

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

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

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

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

return min(vl, vr);

}

};

int main(){

// 1. 入力情報.

int N, L;

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

// 2. 蛍光灯を保存.

vector<light> v;

rep(i, N){

int l, r;

LL c;

scanf("%d %d %lld", &l, &r, &c);

light x;

x.l = l + 1, x.r = r + 1, x.c = c;

v.pb(x);

}

// 以下, 解説通り.

// 3. sort.

sort(all(v));

// 4. 遅延伝播セグメント木を用意.

LazySegmentTree seg(vector<LL>(101010, 0));

rep(i, 101010) dp[i] = INF;

repx(i, 1, 101010) seg.update(i, i + 1, INF);

// 5. dp更新.

rep(i, N){

// 蛍光灯の情報を一つ取得.

int l = v[i].l;

int r = v[i].r;

LL c = v[i].c;

// dp[l] ～ dp[r] の最小値を取得.

LL tmp = seg.query(l - 1, r);

// dp[r] の更新.

dp[r] = min(dp[r], tmp + c);

// SegmentTree の更新.

seg.update(r - 1, r, dp[r]);

// printf("l=%d r=%d c=%lld tmp=%lld\n", l, r, c, tmp);

// rep(i, L + 2) printf("%lld ", seg.query(i, i + 1));

// puts("");

// rep(i, L + 2) printf("%lld ", dp[i]);

// puts("");

}

// 6. 出力.

// rep(i, L + 2) printf("%lld ", dp[i]);

// puts("");

printf("%lld\n", dp[L + 1]);

return 0;

}

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

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

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

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

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

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

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

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

[入力例]
50 10000
0 200 45862
100 400 19945
200 600 17915
300 800 19465
400 1000 34803
500 1200 93461
600 1400 48616
700 1600 49099
800 1800 34606
900 2000 15496
1000 2200 89294
1100 2400 82648
1200 2600 89730
1300 2800 90761
1400 3000 3857
1500 3200 11030
1600 3400 51166
1700 3600 4678
1800 3800 95199
1900 4000 64122
2000 4200 19257
2100 4400 46096
2200 4600 59981
2300 4800 42505
2400 5000 46394
2500 5200 18534
2600 5400 93404
2700 5600 74100
2800 5800 4510
2900 6000 62913
3000 6200 70761
3100 6400 16118
3200 6600 24552
3300 6800 14180
3400 7000 81350
3500 7200 23663
3600 7400 56717
3700 7600 29262
3800 7800 2880
3900 8000 19465
4000 8200 73247
4100 8400 89105
4200 8600 79489
4300 8800 58709
4400 9000 14275
4500 9200 27125
4600 9400 71437
4700 9600 23357
4800 9800 88389
4900 10000 97890

[出力例]
218650

100

101

102

103

104

105

106

107

108

109

110

111

[入力例]

5 5

0 1 1

1 2 1

2 4 3

3 5 1

2 3 2

[出力例]

※AtCoderのテストケースより

[入力例]

8 10

0 2 1

2 3 1

0 4 1

0 2 1

3 7 1

0 10 1080

8 10 1

9 10 1

[出力例]

1080

※AtCoderのテストケースより

[入力例]

10 10

0 1 1

1 2 1

2 3 1

3 4 1

4 5 1

0 5 4

5 7 2

6 8 3

8 10 1

2 9 3

[出力例]

※AtCoderのテストケースより

[入力例]

5 5

0 1 100000

1 2 100000

2 3 100000

3 4 100000

4 5 100000

[出力例]

500000

※AtCoderのテストケースより

[入力例]

50 10000

0 200 45862

100 400 19945

200 600 17915

300 800 19465

400 1000 34803

500 1200 93461

600 1400 48616

700 1600 49099

800 1800 34606

900 2000 15496

1000 2200 89294

1100 2400 82648

1200 2600 89730

1300 2800 90761

1400 3000 3857

1500 3200 11030

1600 3400 51166

1700 3600 4678

1800 3800 95199

1900 4000 64122

2000 4200 19257

2100 4400 46096

2200 4600 59981

2300 4800 42505

2400 5000 46394

2500 5200 18534

2600 5400 93404

2700 5600 74100

2800 5800 4510

2900 6000 62913

3000 6200 70761

3100 6400 16118

3200 6600 24552

3300 6800 14180

3400 7000 81350

3500 7200 23663

3600 7400 56717

3700 7600 29262

3800 7800 2880

3900 8000 19465

4000 8200 73247

4100 8400 89105

4200 8600 79489

4300 8800 58709

4400 9000 14275

4500 9200 27125

4600 9400 71437

4700 9600 23357

4800 9800 88389

4900 10000 97890

[出力例]

218650

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

2020年5月2日

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

C++の練習を兼ねて, AtCoder Regular Contest 027 の問題A (A – 門限) ～問題B (B – 大事な数なのでZ回書きまLた。) を解いてみた.

■感想.
1. 問題B は, 実装方針が決まるまでに, 非常に苦労したものの, AC版となったので良かったと思う.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

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

int main(){
    
    // 1. 入力情報.
    int h, m;
    scanf("%d %d", &h, &m);
    
    // 2. 門限までの時間を計算.
    int ans = 18 * 60;
    ans -= h * 60;
    ans -= m;
    
    // 3. 出力.
    printf("%d\n", ans);
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

int main(){

// 1. 入力情報.

int h, m;

scanf("%d %d", &h, &m);

// 2. 門限までの時間を計算.

int ans = 18 * 60;

ans -= h * 60;

ans -= m;

// 3. 出力.

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

return 0;

}

[入力例]
16 23

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

[入力例]
17 59

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

[入力例]
13 0

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

[入力例]
2 7

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

[入力例]

16 23

[出力例]

※AtCoderのテストケースより

[入力例]

17 59

[出力例]

※AtCoderのテストケースより

[入力例]

13 0

[出力例]

300

※AtCoderのテストケースより

[入力例]

2 7

[出力例]

953

※AtCoderのテストケースより

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

#include <bits/stdc++.h>
using namespace std;
using vvi = vector<vector<int>>;
using LL = long long;
using P = pair<char, char>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define a first
#define b second
#define pb push_back
const int MAX = 55;
int connection[MAX]; // 連結成分番号を保存.
vvi G(MAX);

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

int main(){
    
    // 1. 入力情報.
    int N;
    char c1[33], c2[33];
    scanf("%d %s %s", &N, c1, c2);
    
    // 2. グループ分け.
    // '0' ～ '9': 頂点  0 ～ 頂点  9
    // 'A' ～ 'Z': 頂点 10 ～ 頂点 35
    set<int> vertex; // 出現した頂点を保存.
    rep(i, N){
        char cx = c1[i], cy = c2[i];
        if(cx >= '0' && cx <= '9'){
            if(cy >= '0' && cy <= '9'){
                G[cx - '0'].pb(cy - '0');
                G[cy - '0'].pb(cx - '0');
                vertex.insert(cx - '0');
                vertex.insert(cy - '0');
            }else{
                G[cx - '0'].pb(cy - 'A' + 10);
                G[cy - 'A' + 10].pb(cx - '0');
                vertex.insert(cx - '0');
                vertex.insert(cy - 'A' + 10);
            }
        }else{
            if(cy >= '0' && cy <= '9'){
                G[cx - 'A' + 10].pb(cy - '0');
                G[cy - '0'].pb(cx - 'A' + 10);
                vertex.insert(cx - 'A' + 10);
                vertex.insert(cy - '0');
            }else{
                G[cx - 'A' + 10].pb(cy - 'A' + 10);
                G[cy - 'A' + 10].pb(cx - 'A' + 10);
                vertex.insert(cx - 'A' + 10);
                vertex.insert(cy - 'A' + 10);
            }
        }
    }
    
    // 3. 各頂点に対する連結成分番号を設定.
    int id = 0;
    rep(i, 36) if(vertex.count(i) && connection[i] == 0) bfs(G, i, ++id);
    // rep(i, 36) printf("i=%d con=%d\n", i, connection[i]);
    
    // 4. グループ番号ごとに, グループ化.
    vector<vector<char>> group(36);
    rep(i, 10) if(connection[i]) group[connection[i]].pb(i + '0');
    repx(i, 10, 36) if(connection[i]) group[connection[i]].pb(i - 10 + 'A');
    
    // 5. 元の文字を書き換え.
    // ex.
    // 6
    // PRBLMB
    // ARC027
    // 
    // -> この場合は, s1, s2 は, 以下のように書き換えることになる.
    // AR7027
    // AR7027
    rep(i, N){
        if(c1[i] >= 'A' && c1[i] <= 'Z'){
            int g = connection[c1[i] - 'A' + 10];
            c1[i] = group[g][0];
        }
        if(c2[i] >= 'A' && c2[i] <= 'Z'){
            int g = connection[c2[i] - 'A' + 10];
            c2[i] = group[g][0];
        }
    }
    string s1(c1), s2(c2);
    // printf("%s\n%s\n", s1.c_str(), s2.c_str());
    
    // 6. 数字が確定してない箇所を集計.
    LL ans = 1;
    rep(i, N) if(c1[i] >= 'A' && c1[i] <= 'Z' && c2[i] >= 'A' && c2[i] <= 'Z') ans *= 10LL;
    
    // 7. 先頭要素を考慮.
    if(c1[0] >= 'A' && c1[0] <= 'Z' && c2[0] >= 'A' && c2[0] <= 'Z') ans = ans / 10LL * 9LL;
    
    // 8. 重複要素を考慮.
    map<P, int> m;
    rep(i, N) m[{c1[i], c2[i]}]++;
    for(auto &p : m){
        P q = p.a;
        if(p.a.a >= 'A' && p.a.a <= 'Z') rep(i, p.b - 1) ans /= 10LL;
    }
    
    // 9. 出力.
    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

#include <bits/stdc++.h>

using namespace std;

using vvi = vector<vector<int>>;

using LL = long long;

using P = pair<char, char>;

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

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

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

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

#define a first

#define b second

#define pb push_back

const int MAX = 55;

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

vvi G(MAX);

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

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

// ※bfsの動作確認用.

// @param G: グラフ.

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

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

// @return: 特に無し.

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

// 1. 空のキュー.

queue<int> q;

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

connection[s] = l;

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

q.push(s);

while(!q.empty()){

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

int u = q.front();

q.pop();

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

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

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

if(connection[e] > 0) continue;

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

}

return;

}

int main(){

// 1. 入力情報.

int N;

char c1[33], c2[33];

scanf("%d %s %s", &N, c1, c2);

// 2. グループ分け.

// '0' ～ '9': 頂点 0 ～頂点 9

// 'A' ～ 'Z': 頂点 10 ～頂点 35

set<int> vertex; // 出現した頂点を保存.

rep(i, N){

char cx = c1[i], cy = c2[i];

if(cx >= '0' && cx <= '9'){

if(cy >= '0' && cy <= '9'){

G[cx - '0'].pb(cy - '0');

G[cy - '0'].pb(cx - '0');

vertex.insert(cx - '0');

vertex.insert(cy - '0');

}else{

G[cx - '0'].pb(cy - 'A' + 10);

G[cy - 'A' + 10].pb(cx - '0');

vertex.insert(cx - '0');

vertex.insert(cy - 'A' + 10);

}

}else{

if(cy >= '0' && cy <= '9'){

G[cx - 'A' + 10].pb(cy - '0');

G[cy - '0'].pb(cx - 'A' + 10);

vertex.insert(cx - 'A' + 10);

vertex.insert(cy - '0');

}else{

G[cx - 'A' + 10].pb(cy - 'A' + 10);

G[cy - 'A' + 10].pb(cx - 'A' + 10);

vertex.insert(cx - 'A' + 10);

vertex.insert(cy - 'A' + 10);

}

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

int id = 0;

rep(i, 36) if(vertex.count(i) && connection[i] == 0) bfs(G, i, ++id);

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

// 4. グループ番号ごとに, グループ化.

vector<vector<char>> group(36);

rep(i, 10) if(connection[i]) group[connection[i]].pb(i + '0');

repx(i, 10, 36) if(connection[i]) group[connection[i]].pb(i - 10 + 'A');

// 5. 元の文字を書き換え.

// ex.

// 6

// PRBLMB

// ARC027

// -> この場合は, s1, s2 は, 以下のように書き換えることになる.

// AR7027

rep(i, N){

if(c1[i] >= 'A' && c1[i] <= 'Z'){

int g = connection[c1[i] - 'A' + 10];

c1[i] = group[g][0];

}

if(c2[i] >= 'A' && c2[i] <= 'Z'){

int g = connection[c2[i] - 'A' + 10];

c2[i] = group[g][0];

}

string s1(c1), s2(c2);

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

// 6. 数字が確定してない箇所を集計.

LL ans = 1;

rep(i, N) if(c1[i] >= 'A' && c1[i] <= 'Z' && c2[i] >= 'A' && c2[i] <= 'Z') ans *= 10LL;

// 7. 先頭要素を考慮.

if(c1[0] >= 'A' && c1[0] <= 'Z' && c2[0] >= 'A' && c2[0] <= 'Z') ans = ans / 10LL * 9LL;

// 8. 重複要素を考慮.

map<P, int> m;

rep(i, N) m[{c1[i], c2[i]}]++;

for(auto &p : m){

P q = p.a;

if(p.a.a >= 'A' && p.a.a <= 'Z') rep(i, p.b - 1) ans /= 10LL;

}

// 9. 出力.

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

return 0;

}

[入力例]
4
1XYX
1Z48

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

[入力例]
3
XXX
YYY

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

[入力例]
6
PRBLMB
ARC027

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

[入力例]
1
A
B

[出力例]
9

[入力例]
12
PRBLMBZQAOIJ
ARC02718C30F

[出力例]
100

[入力例]
10
WWWWXXXYYZ
XXXXYYYZZA

[出力例]
9

[入力例]
15
AAAAABBBBCCCDDE
BBBBBCCCCDDDEEF

[出力例]
9

[入力例]
18
1BCDEFGHIJKLMNOPQR
ABCDEFGHIJKLMNOPQR

[出力例]
100000000000000000

[入力例]
16
1BCDEFGHI3KLM5OP
ABCD2FGHIJK4MNOP

[出力例]
100000000000

[入力例]
17
ACEG1IKLMNO2QR3TU
BDFHIJLMNOPQRSTUV

[出力例]
90000

[入力例]

1XYX

1Z48

[出力例]

※AtCoderのテストケースより

[入力例]

XXX

YYY

[出力例]

※AtCoderのテストケースより

[入力例]

PRBLMB

ARC027

[出力例]

※AtCoderのテストケースより

[入力例]

[出力例]

[入力例]

PRBLMBZQAOIJ

ARC02718C30F

[出力例]

100

[入力例]

WWWWXXXYYZ

XXXXYYYZZA

[出力例]

[入力例]

AAAAABBBBCCCDDE

BBBBBCCCCDDDEEF

[出力例]

[入力例]

1BCDEFGHIJKLMNOPQR

ABCDEFGHIJKLMNOPQR

[出力例]

100000000000000000

[入力例]

1BCDEFGHI3KLM5OP

ABCD2FGHIJK4MNOP

[出力例]

100000000000

[入力例]

ACEG1IKLMNO2QR3TU

BDFHIJLMNOPQRSTUV

[出力例]

90000

■参照サイト
AtCoder Regular Contest 027

2020年4月30日2020年4月30日

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

C++の練習を兼ねて, AtCoder Regular Contest 026 の問題A (A – ダイナミックなポーズ) ～問題B (B – 完全数) を解いてみた.

■感想.
1. 問題B で, 約数の計算方法を復習できたので良かったと思う.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

本家のサイトARC 026 解説をご覧下さい.

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

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

int main(){
    
    // 1. 入力情報.
    int N, A, B;
    scanf("%d %d %d", &N, &A, &B);
    
    // 2. 出力.
    printf("%d\n", A * max(N - 5, 0) + B * min(N, 5));
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

int main(){

// 1. 入力情報.

int N, A, B;

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

// 2. 出力.

printf("%d\n", A * max(N - 5, 0) + B * min(N, 5));

return 0;

}

[入力例]
10 5 1

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

[入力例]
4 60 7

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

[入力例]

10 5 1

[出力例]

※AtCoderのテストケースより

[入力例]

4 60 7

[出力例]

※AtCoderのテストケースより

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

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

// 与えられた正の整数のすべての約数を抽出.
// @param X: 約数を抽出したい正の整数.
// @return ret: すべての約数.
vector<LL> div(LL X){
    vector<LL> ret;
    ret.pb(1);
    for(LL d = 2; d * d <= X; d++){
        if(X % d == 0){
            ret.pb(d);
            if(d * d != X) ret.pb(X / d);
        }
    }
    // subtask1_24.txt で WA版.
    // ret.pb(X);
    if(X > 1) ret.pb(X);
    return ret;
}

int main(){
    
    // 1. 入力情報.
    LL N;
    scanf("%lld", &N);
    
    // 2. 約数を計算.
    vector<LL> v = div(N);
    
    // 3. 約数の和を計算.
    LL sum = -N;
    for(auto &p : v) sum += p;
    
    // 4. 完全数か？
    string ans = "Perfect";
    if(sum > N) ans = "Abundant";
    if(sum < N) ans = "Deficient";
    
    // 5. 出力.
    printf("%s\n", ans.c_str());
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

#define pb push_back

// 与えられた正の整数のすべての約数を抽出.

// @param X: 約数を抽出したい正の整数.

// @return ret: すべての約数.

vector<LL> div(LL X){

vector<LL> ret;

ret.pb(1);

for(LL d = 2; d * d <= X; d++){

if(X % d == 0){

ret.pb(d);

if(d * d != X) ret.pb(X / d);

}

// subtask1_24.txt で WA版.

// ret.pb(X);

if(X > 1) ret.pb(X);

return ret;

}

int main(){

// 1. 入力情報.

LL N;

scanf("%lld", &N);

// 2. 約数を計算.

vector<LL> v = div(N);

// 3. 約数の和を計算.

LL sum = -N;

for(auto &p : v) sum += p;

// 4. 完全数か？

string ans = "Perfect";

if(sum > N) ans = "Abundant";

if(sum < N) ans = "Deficient";

// 5. 出力.

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

return 0;

}

[入力例]
6

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

[入力例]
24

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

[入力例]
27

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

[入力例]
945

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

[入力例]
1

[出力例]
Deficient

[入力例]
8128

[出力例]
Perfect

[入力例]
33550336

[出力例]
Perfect

[入力例]
8589869056

[出力例]
Perfect

[入力例]
10000000000

[出力例]
Abundant

[入力例]

[出力例]

Perfect

※AtCoderのテストケースより

[入力例]

[出力例]

Abundant

※AtCoderのテストケースより

[入力例]

[出力例]

Deficient

※AtCoderのテストケースより

[入力例]

945

[出力例]

Abundant

※AtCoderのテストケースより

[入力例]

[出力例]

Deficient

[入力例]

8128

[出力例]

Perfect

[入力例]

33550336

[出力例]

Perfect

[入力例]

8589869056

[出力例]

Perfect

[入力例]

10000000000

[出力例]

Abundant

■参照サイト
AtCoder Regular Contest 026
完全数

2020年4月28日2020年4月28日

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

C++の練習を兼ねて, AtCoder Regular Contest 025 の問題A (A – ゴールドラッシュ) ～問題B (B – チョコレート) を解いてみた.

■感想.
1. 問題A は, 苦手なdpの訓練を積めたので, 非常に良かったと思う.
2. 問題B は, 二次元累積和の復習が出来たので良かったと思う.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

本家のサイトARC 025 解説をご覧下さい.

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

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

int main(){
    
    // 1. 入力情報.
    rep(i, 7) scanf("%d", &D[i]);
    rep(i, 7) scanf("%d", &J[i]);
    
    // 2. 最適に鉱山を選んだ場合に得られる金の量は？
    dp[0][0] = D[0];
    dp[0][1] = J[0];
    rep(i, 7){
        dp[i + 1][0] = max(dp[i][0], dp[i][1]) + D[i + 1];
        dp[i + 1][1] = max(dp[i][0], dp[i][1]) + J[i + 1];
    }
    
    // 3. 出力.
    printf("%d\n", max(dp[7][0], dp[7][1]));
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

int D[10], J[10], dp[10][2];

int main(){

// 1. 入力情報.

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

rep(i, 7) scanf("%d", &J[i]);

// 2. 最適に鉱山を選んだ場合に得られる金の量は？

dp[0][0] = D[0];

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

rep(i, 7){

dp[i + 1][0] = max(dp[i][0], dp[i][1]) + D[i + 1];

dp[i + 1][1] = max(dp[i][0], dp[i][1]) + J[i + 1];

}

// 3. 出力.

printf("%d\n", max(dp[7][0], dp[7][1]));

return 0;

}

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

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

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

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

[入力例]
0 0 0 0 0 0 0
0 0 0 0 0 0 0

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

[入力例]
8 3 0 2 5 25 252
252 252 2 5 2 5 2

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

[入力例]
224 1964 1954 1506 547 894 1437
812 1474 1392 783 1375 1115 509

[出力例]
10163

[入力例]
1353 553 146 452 660 733 1384
1627 1450 324 1152 848 823 227

[出力例]
7608

[入力例]

4 2 0 5 6 2 5

6 1 4 3 6 4 6

[出力例]

※AtCoderのテストケースより

[入力例]

1 2 3 4 5 6 7

2 3 4 5 6 7 8

[出力例]

※AtCoderのテストケースより

[入力例]

0 0 0 0 0 0 0

[出力例]

※AtCoderのテストケースより

[入力例]

8 3 0 2 5 25 252

252 252 2 5 2 5 2

[出力例]

793

※AtCoderのテストケースより

[入力例]

224 1964 1954 1506 547 894 1437

812 1474 1392 783 1375 1115 509

[出力例]

10163

[入力例]

1353 553 146 452 660 733 1384

1627 1450 324 1152 848 823 227

[出力例]

7608

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

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

int main(){
    
    // 1. 入力情報.
    int H, W;
    scanf("%d %d", &H, &W);
    rep(i, H){
        rep(j, W){
            if((i + j) & 1) scanf("%d", &wC[i][j]);
            else            scanf("%d", &bC[i][j]);
        }
    }
    
    // 2. ブラック, ホワイトチョコレートについて, 二次元累積和を保存.
    repx(i, 1, H + 1){
        repx(j, 1, W + 1){
            bCum[i][j] = bC[i - 1][j - 1] + bCum[i - 1][j] + bCum[i][j - 1] - bCum[i - 1][j - 1];
            wCum[i][j] = wC[i - 1][j - 1] + wCum[i - 1][j] + wCum[i][j - 1] - wCum[i - 1][j - 1];
        }
    }
        
    // 3. 条件を満たす切り出し方を調査.
    int ans = 0;
    repx(h, 1, H + 1){
        repx(w, 1, W + 1){
            // 3-1. マスの数が小さい場合は, Skip.
            if(h * w <= ans) continue;
            
            // 3-2. 縦h, 横w の 切り出し方 を 調査.
            // 左上隅 を (sx, sy) と 置く.
            rep(sx, H - h + 1){
                rep(sy, W - w + 1){
                    // 右下隅 は, (sx + h - 1, sy + w - 1)
                    int gx = sx + h - 1;
                    int gy = sy + w - 1;
                    
                    // ブラック, ホワイトチョコレートの濃度合計.
                    int bSum = bCum[gx + 1][gy + 1] - bCum[sx][gy + 1] - bCum[gx + 1][sy] + bCum[sx][sy];
                    int wSum = wCum[gx + 1][gy + 1] - wCum[sx][gy + 1] - wCum[gx + 1][sy] + wCum[sx][sy];
                    
                    // 等しければ, 次の処理へ.
                    if(bSum == wSum){
                        ans = h * w; // 最大値更新.
                        break;
                    }
                }
            }
        }
    }
    
    // 4. 出力.
    printf("%d\n", ans);
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

int wC[111][111], bC[111][111]; // white, black.

int wCum[111][111], bCum[111][111]; // white, black.

int main(){

// 1. 入力情報.

int H, W;

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

rep(i, H){

rep(j, W){

if((i + j) & 1) scanf("%d", &wC[i][j]);

else scanf("%d", &bC[i][j]);

}

// 2. ブラック, ホワイトチョコレートについて, 二次元累積和を保存.

repx(i, 1, H + 1){

repx(j, 1, W + 1){

bCum[i][j] = bC[i - 1][j - 1] + bCum[i - 1][j] + bCum[i][j - 1] - bCum[i - 1][j - 1];

wCum[i][j] = wC[i - 1][j - 1] + wCum[i - 1][j] + wCum[i][j - 1] - wCum[i - 1][j - 1];

}

// 3. 条件を満たす切り出し方を調査.

int ans = 0;

repx(h, 1, H + 1){

repx(w, 1, W + 1){

// 3-1. マスの数が小さい場合は, Skip.

if(h * w <= ans) continue;

// 3-2. 縦h, 横w の切り出し方を調査.

// 左上隅を (sx, sy) と置く.

rep(sx, H - h + 1){

rep(sy, W - w + 1){

// 右下隅は, (sx + h - 1, sy + w - 1)

int gx = sx + h - 1;

int gy = sy + w - 1;

// ブラック, ホワイトチョコレートの濃度合計.

int bSum = bCum[gx + 1][gy + 1] - bCum[sx][gy + 1] - bCum[gx + 1][sy] + bCum[sx][sy];

int wSum = wCum[gx + 1][gy + 1] - wCum[sx][gy + 1] - wCum[gx + 1][sy] + wCum[sx][sy];

// 等しければ, 次の処理へ.

if(bSum == wSum){

ans = h * w; // 最大値更新.

break;

}

// 4. 出力.

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

return 0;

}

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

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

[入力例]
2 2
4 0
7 3

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

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

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

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

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

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

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

[入力例]
20 30
79 26 49 19 88 87 44 69 61 31 17 25 28 32 34 34 30 74 19 97 66 35 32 54 75 97 48 64 51 40
91 82 28 6 54 56 1 88 4 11 68 32 89 51 61 77 22 84 91 91 38 79 86 83 92 27 76 80 63 52
25 66 85 50 55 56 58 96 71 2 65 67 58 57 81 18 56 99 44 73 42 66 91 36 77 43 47 95 26 68
94 13 0 85 14 37 36 34 58 86 1 44 49 28 15 26 24 44 39 98 78 27 30 93 68 78 49 95 26 26
21 31 92 95 23 21 8 55 41 86 25 62 26 27 25 85 1 11 4 73 42 26 56 32 32 66 99 60 68 8
54 51 1 6 86 24 20 1 0 0 97 72 46 67 98 56 61 94 45 67 6 60 1 48 97 38 87 69 90 99
55 37 44 84 33 26 70 86 63 78 20 42 87 6 69 35 20 34 77 12 32 24 28 74 29 42 98 88 30 90
70 57 29 52 58 20 9 51 14 45 27 35 51 91 98 90 69 10 35 45 99 0 38 25 89 2 32 29 72 79
30 40 7 96 97 86 61 48 37 69 24 24 71 42 47 60 28 89 77 26 88 35 47 49 84 20 62 98 65 17
58 93 63 54 57 96 75 46 3 8 94 20 96 78 98 56 3 73 27 91 48 55 44 71 10 53 95 83 49 28
36 67 56 11 30 94 15 14 36 6 63 39 47 2 93 48 27 28 82 83 98 5 29 79 8 42 51 76 95 97
89 75 9 23 37 25 35 33 50 85 41 53 28 95 36 16 99 12 98 58 21 62 71 66 93 7 55 85 50 45
6 9 40 8 7 19 32 56 78 79 26 79 75 88 33 35 55 70 13 59 15 98 96 25 44 46 15 91 25 40
8 75 80 4 1 33 83 76 48 13 24 7 92 29 19 99 62 2 68 83 27 25 93 79 47 13 9 19 73 81
49 46 7 39 77 13 9 8 39 41 69 30 96 76 36 86 3 94 39 76 87 34 46 5 54 43 50 74 89 87
36 76 48 54 18 43 89 79 59 2 91 79 1 57 21 35 65 54 96 9 72 75 39 19 93 23 55 79 20 22
55 37 5 73 87 1 36 85 91 47 4 86 74 56 62 90 40 97 43 93 10 70 55 72 19 26 46 72 59 31
0 82 39 78 91 99 67 47 23 92 70 74 45 48 92 24 41 98 28 67 30 2 43 49 88 66 88 18 13 29
44 44 16 48 93 84 40 26 32 82 19 92 39 46 93 28 11 88 18 78 97 38 18 98 24 46 58 94 70 92
60 4 73 79 33 43 14 99 65 7 41 48 53 86 72 91 95 83 1 58 45 15 33 92 25 67 77 24 32 92

[出力例]
266

[入力例]
50 75
81 23 73 83 35 30 8 53 0 84 1 5 48 52 26 12 78 87 79 35 84 29 82 80 23 68 6 61 13 79 66 44 6 25 80 44 54 36 55 81 84 64 78 64 91 85 19 75 87 3 93 93 91 41 86 84 39 34 27 77 39 61 79 80 43 34 84 14 22 30 68 47 22 84 0
93 92 11 88 80 98 31 49 10 87 41 25 80 60 97 1 18 65 9 2 52 45 26 9 54 14 16 84 73 12 66 61 30 9 94 40 87 39 95 59 12 24 34 59 36 64 21 27 33 35 2 35 84 22 31 80 88 61 66 40 40 50 54 4 82 18 77 88 68 73 96 54 21 73 47
54 24 5 42 98 34 25 20 85 21 2 86 91 87 70 24 21 9 55 80 74 63 65 89 78 44 75 41 18 6 49 89 0 64 25 9 62 71 79 14 67 87 40 47 6 16 99 32 20 23 46 19 26 7 1 40 26 66 31 79 70 64 36 52 56 90 28 44 94 5 84 15 10 16 34
31 43 96 15 90 5 76 25 38 76 90 47 20 31 52 45 31 64 60 38 41 79 0 96 99 7 17 97 40 46 73 92 72 85 52 28 63 14 66 24 12 35 96 14 68 20 29 2 61 98 68 31 2 1 99 89 88 9 8 39 68 15 40 12 20 58 45 48 8 55 50 22 2 15 22
23 9 44 79 27 54 37 62 47 77 52 49 92 20 51 55 69 54 12 91 1 54 98 98 88 61 16 88 38 60 92 28 96 67 15 67 26 64 48 20 72 32 18 66 34 68 90 80 28 64 50 76 36 72 85 47 39 50 36 27 66 77 28 67 94 55 20 4 36 85 60 69 38 50 82
68 48 44 72 39 81 27 88 29 71 47 29 89 21 84 44 37 53 16 68 5 83 13 22 25 82 32 73 52 67 55 50 57 91 40 27 18 45 75 50 96 26 78 69 96 2 64 44 43 56 76 13 73 76 21 61 72 88 31 84 90 55 53 57 30 42 56 90 73 21 88 47 64 53 52
47 21 3 75 52 72 7 65 63 94 80 40 63 53 4 9 67 76 45 68 44 10 38 79 31 0 81 89 30 19 27 14 46 53 40 68 10 34 83 29 22 50 53 50 0 95 90 50 25 77 33 79 66 77 60 40 82 97 86 70 65 88 60 36 10 5 49 85 87 14 20 87 23 36 64
98 1 96 11 32 25 71 22 76 86 74 66 10 29 49 49 9 52 28 42 12 66 28 45 24 1 61 40 37 98 20 41 42 97 86 17 61 57 69 54 59 73 54 0 80 45 20 32 16 71 43 19 31 8 41 14 75 16 94 21 95 54 18 20 76 65 47 10 29 17 47 18 53 57 62
59 24 42 54 46 65 68 83 36 64 38 68 57 7 18 23 81 2 64 11 85 8 86 25 18 85 91 44 24 70 99 62 70 59 34 88 61 95 90 79 26 7 41 31 55 57 21 9 45 57 5 68 75 10 23 19 46 21 96 34 22 11 48 63 81 16 26 27 14 62 94 8 35 38 13
97 23 37 24 83 79 24 15 32 7 17 92 91 37 39 27 73 94 50 21 86 60 55 16 0 52 41 36 25 83 47 51 10 32 23 7 74 29 42 15 2 46 45 8 60 40 19 79 90 26 12 24 58 2 23 29 54 3 43 29 29 25 68 4 67 29 21 0 28 77 93 47 2 49 6
48 51 87 83 3 58 25 79 31 28 91 11 39 37 75 4 58 53 62 32 37 30 80 35 57 48 84 94 26 32 94 3 95 7 77 79 19 80 47 94 76 65 60 71 46 68 43 51 91 83 45 70 80 23 24 32 33 2 5 73 61 20 44 38 81 20 8 38 77 37 86 42 68 53 32
82 25 27 63 35 21 46 44 64 40 95 64 2 11 10 70 28 84 13 63 43 47 29 26 52 94 93 38 30 93 59 31 2 47 6 30 71 62 12 61 4 97 41 33 3 88 81 71 31 50 99 46 6 19 32 14 95 59 62 17 82 52 48 42 67 99 65 53 65 54 22 8 72 97 35
74 49 2 80 47 85 64 21 57 78 30 61 16 74 76 18 24 34 99 70 73 77 22 68 14 61 29 76 3 83 74 62 10 65 39 50 62 7 94 93 43 30 23 96 21 52 99 98 74 39 99 89 91 51 8 87 31 12 37 12 54 63 75 68 72 47 2 75 8 64 19 45 95 7 26
10 41 41 73 29 48 67 6 10 59 88 69 57 67 43 6 54 29 20 22 23 3 42 25 3 33 46 38 99 7 22 27 94 74 45 5 27 2 75 19 32 98 48 8 49 19 71 88 63 54 6 44 67 3 16 35 73 31 23 5 74 1 59 70 83 26 69 82 65 59 33 92 26 47 79
79 1 83 28 48 22 29 80 14 94 92 79 18 82 54 41 7 40 17 81 61 56 77 1 62 47 80 77 60 64 68 0 14 7 3 45 41 70 56 64 87 40 48 46 0 95 42 77 20 96 75 45 63 14 91 86 44 67 97 29 56 35 82 51 18 88 38 79 12 12 47 98 66 93 23
72 33 90 56 30 39 42 9 44 80 9 60 67 48 70 53 19 48 86 10 60 52 66 75 68 34 76 33 82 29 17 35 14 14 10 76 85 43 13 74 11 69 85 44 45 4 28 42 27 3 8 13 60 20 82 55 21 37 26 93 47 40 66 66 0 91 33 17 20 44 59 88 62 37 46
92 46 0 28 15 53 65 51 19 90 5 40 39 71 79 51 31 46 67 86 15 16 90 41 88 7 45 71 27 45 38 50 12 12 82 48 82 75 56 99 99 78 51 79 72 27 67 2 82 70 0 84 36 84 16 40 6 36 16 7 32 23 37 96 95 15 87 70 19 62 30 40 92 97 84
52 13 82 14 15 47 33 23 67 12 39 38 65 33 22 55 2 7 51 1 77 28 2 56 66 18 42 41 67 73 29 12 70 28 15 33 16 73 82 45 64 8 28 65 57 82 6 57 44 97 28 94 44 28 56 19 50 94 13 55 15 44 42 92 12 26 94 80 58 90 50 27 78 65 35
19 74 60 20 15 75 0 11 91 89 8 52 43 89 40 72 55 29 92 79 72 41 85 94 13 37 22 49 51 85 69 56 13 55 28 78 86 70 63 38 95 68 23 26 39 66 9 49 41 38 34 51 19 39 10 46 45 62 10 93 44 6 58 10 62 33 58 53 85 7 44 46 82 36 47
85 51 11 37 91 62 32 93 13 25 17 46 32 5 81 74 91 32 45 33 6 11 39 51 17 68 3 12 48 9 97 27 98 18 98 86 56 75 4 16 95 16 99 0 69 87 31 2 27 66 87 60 77 13 5 4 85 4 21 4 90 25 2 27 19 35 54 51 24 88 61 1 6 27 54
17 45 81 21 71 78 76 38 59 43 31 50 79 94 86 82 24 88 95 56 40 35 0 3 24 61 75 48 46 14 31 76 25 64 62 56 55 33 34 56 83 57 46 58 40 58 17 53 91 64 89 50 25 93 60 17 38 39 20 97 5 24 48 6 60 85 53 13 16 71 21 39 11 50 87
56 19 6 60 66 71 80 16 84 1 48 1 78 2 38 85 52 43 36 95 69 42 28 6 59 49 15 6 80 89 27 49 94 86 45 52 95 6 98 73 70 53 59 48 0 93 29 73 36 22 53 96 4 76 45 47 96 11 48 46 54 29 55 43 44 26 19 93 38 91 67 78 88 22 88
64 74 53 13 20 18 65 62 81 92 7 28 59 4 96 27 6 41 57 85 52 76 53 11 23 75 29 70 33 30 26 34 79 43 67 15 43 54 47 68 25 28 26 8 26 24 53 19 85 68 42 73 24 30 89 88 35 61 81 22 93 25 3 36 72 31 47 15 74 83 10 62 52 15 57
85 33 58 67 42 14 98 1 23 78 92 98 54 53 90 97 78 15 32 26 92 54 67 2 19 94 51 0 6 81 18 30 31 96 38 50 34 51 16 86 99 39 9 94 49 11 41 87 67 90 48 5 61 85 29 98 0 76 64 55 14 89 75 2 32 98 28 46 27 27 40 75 78 20 81
90 30 3 77 22 3 87 49 63 27 16 89 40 14 53 93 62 19 8 58 37 21 74 28 75 33 98 56 46 77 29 39 37 15 48 15 91 82 89 21 99 65 54 22 57 3 92 34 78 38 44 82 52 77 64 58 84 86 54 88 92 40 86 96 13 81 61 54 17 13 23 51 31 26 12
53 72 97 25 68 58 93 67 63 88 72 10 74 13 38 0 56 30 7 65 82 57 32 60 23 24 43 49 45 99 73 3 55 13 35 15 44 51 4 8 28 57 33 98 16 64 96 69 84 86 85 76 54 9 8 31 7 91 80 84 60 26 41 38 82 36 52 74 66 37 55 48 59 6 10
76 60 42 92 29 48 21 25 9 93 37 27 26 69 31 28 22 45 76 87 70 78 21 34 7 86 84 97 51 68 0 70 70 22 54 51 88 84 32 38 91 82 51 22 44 97 56 6 83 11 12 19 28 91 1 7 8 76 57 11 90 78 42 31 44 81 70 50 59 58 93 50 86 89 38
90 69 9 66 78 95 99 43 68 3 51 44 59 31 86 45 91 73 13 1 93 18 47 97 11 58 81 90 20 81 23 20 62 70 24 30 49 47 34 44 29 78 32 40 75 32 76 64 35 13 32 58 75 34 60 81 21 86 64 12 95 26 67 70 73 8 16 74 38 21 42 68 55 59 91
52 87 44 24 62 81 15 29 87 99 49 7 81 30 4 64 6 61 25 92 20 33 48 50 22 33 83 18 50 94 48 38 69 50 82 24 43 32 45 11 61 93 63 50 90 61 9 77 57 4 22 75 4 14 91 94 80 14 98 72 53 65 63 26 34 73 35 70 1 69 8 85 15 16 17
17 61 49 51 85 77 9 71 66 70 70 75 26 20 16 16 35 68 12 35 63 43 33 22 40 19 67 92 74 47 7 77 9 24 36 9 63 28 46 2 75 25 20 26 97 66 64 4 65 82 94 14 25 17 38 31 50 27 92 14 77 66 3 59 85 39 45 99 54 13 56 95 46 55 60
87 42 92 3 44 27 49 91 86 16 10 67 46 29 23 20 50 85 37 16 32 27 87 83 33 53 32 44 69 87 87 62 0 96 23 28 93 51 10 39 6 96 73 26 97 5 75 31 35 27 25 93 21 71 76 68 36 71 48 29 57 11 86 43 0 82 17 86 22 52 20 57 30 39 51
14 62 53 40 60 16 21 7 35 16 8 1 37 99 37 59 54 86 23 5 87 26 83 47 77 0 45 73 87 65 27 52 7 4 67 5 25 86 61 59 22 31 57 46 0 61 8 11 76 27 80 25 15 64 92 59 90 63 61 70 61 29 41 42 81 39 68 42 31 21 32 63 8 38 51
71 62 76 49 10 48 11 17 86 14 12 21 50 8 90 3 16 3 60 61 59 96 52 81 85 42 55 65 60 94 85 97 66 80 15 22 87 1 68 63 32 82 49 69 44 31 50 13 59 4 37 2 41 51 58 40 13 7 26 6 36 47 74 35 22 80 42 63 55 35 99 77 11 39 29
6 64 99 56 91 78 66 92 61 35 16 91 47 42 91 45 82 12 18 15 42 18 60 14 19 95 41 5 92 63 53 74 76 0 48 41 74 67 47 64 17 29 52 49 14 65 73 13 56 46 23 90 15 9 40 6 86 72 2 14 46 42 19 17 40 66 63 75 2 24 22 8 36 22 89
0 39 48 87 79 1 26 61 88 49 70 98 19 44 17 49 71 24 79 64 4 88 76 54 55 47 68 25 58 52 81 46 3 68 87 76 46 16 49 18 2 99 73 19 30 30 75 90 82 55 71 18 13 70 26 54 12 60 82 28 21 42 52 76 76 74 73 58 59 89 52 97 53 60 42
17 10 76 49 40 50 89 85 77 80 87 12 57 66 5 58 66 39 13 99 71 81 24 74 57 39 8 35 75 64 24 88 30 83 38 48 17 5 1 70 3 73 35 80 18 51 8 92 6 3 82 50 45 8 24 84 18 9 33 61 38 92 9 85 56 40 75 23 38 21 28 74 7 21 91
23 17 31 6 51 21 27 28 26 52 38 63 83 55 46 47 5 68 59 57 15 46 84 93 40 50 33 27 49 31 80 89 76 72 80 77 26 11 88 2 96 70 33 58 5 57 0 46 37 85 87 62 95 77 87 7 40 54 31 44 73 57 77 97 45 94 36 19 65 42 16 17 8 24 9
56 72 72 10 18 58 89 35 17 19 99 57 42 55 33 96 53 22 55 85 9 64 43 21 72 76 33 35 52 88 44 78 78 50 40 58 72 0 80 34 45 55 66 64 45 39 64 68 98 29 78 31 31 74 9 69 4 2 65 83 62 55 54 51 97 5 63 73 75 1 66 40 34 51 39
40 28 40 57 72 88 65 88 87 11 2 92 23 57 46 26 39 81 61 26 77 70 3 75 31 29 52 44 63 75 32 92 91 25 11 33 90 57 11 2 81 46 76 21 53 52 83 6 2 65 94 7 7 90 78 47 61 92 0 8 56 7 4 97 62 68 73 44 84 71 24 75 39 79 99
75 69 74 10 86 78 49 25 39 56 58 84 61 62 53 96 85 12 37 17 21 66 43 6 19 59 57 16 80 77 74 39 74 54 75 44 29 25 52 8 95 71 18 7 44 34 36 53 33 22 18 66 13 29 32 10 38 33 24 78 30 59 74 74 53 78 45 60 83 81 46 0 53 17 44
41 59 90 93 59 89 54 89 40 18 90 22 2 61 63 25 78 52 27 95 32 20 64 16 4 89 23 95 57 23 11 2 34 56 61 27 37 65 99 58 41 75 5 56 85 85 74 73 50 53 34 3 67 51 5 66 38 31 57 14 60 89 81 12 20 63 56 69 14 14 90 1 52 61 67
9 10 71 29 40 59 95 43 28 71 28 85 21 30 12 15 40 79 76 53 65 35 29 5 56 3 19 50 27 96 48 14 31 79 46 76 91 85 54 84 25 1 78 54 33 57 40 2 14 93 4 7 38 29 4 50 95 97 70 7 33 52 77 17 13 4 41 29 64 94 44 39 89 44 18
12 28 46 63 56 93 80 87 79 57 95 53 31 86 96 93 86 83 8 43 54 57 2 13 20 72 1 8 84 37 3 59 19 38 98 16 74 16 61 95 18 15 18 96 99 39 64 48 27 66 16 8 16 31 71 41 89 79 6 62 9 86 58 22 63 45 88 66 27 51 47 46 83 14 92
33 4 2 59 60 54 9 21 62 50 87 65 70 83 70 28 63 25 89 43 72 5 21 15 89 84 73 85 25 97 22 87 28 1 98 42 18 38 38 23 51 81 99 90 74 23 76 24 80 65 21 93 82 71 96 89 36 53 34 88 98 55 68 4 88 69 47 64 16 86 60 73 18 40 11
18 23 50 25 2 38 82 27 3 47 17 89 71 59 16 54 9 18 3 52 0 36 47 8 93 63 67 58 26 1 91 41 58 37 11 5 96 8 97 24 26 74 28 90 82 95 51 52 11 70 26 40 54 12 36 2 31 60 75 46 1 37 53 55 88 16 61 61 65 46 96 35 90 83 72
22 46 3 57 43 30 8 53 13 57 21 66 27 53 22 80 8 22 91 99 67 67 87 95 39 80 51 18 31 47 36 65 3 94 58 18 34 29 24 91 49 90 54 49 65 16 55 11 14 46 10 56 24 24 59 95 22 42 65 77 0 1 90 73 67 36 57 12 0 36 11 22 69 94 31
88 73 44 15 8 80 93 33 52 18 64 79 66 89 83 17 77 92 21 56 62 21 76 28 26 85 68 63 34 38 22 39 94 92 82 22 39 91 16 36 31 52 13 25 24 26 59 65 92 16 4 35 50 39 1 18 37 62 97 14 49 57 65 12 78 14 19 28 46 51 18 70 2 0 11
23 20 28 58 30 55 75 17 68 55 16 40 76 70 7 78 77 26 95 14 39 10 51 16 55 5 47 46 66 37 99 18 90 6 28 36 60 98 11 59 92 62 90 91 54 43 27 63 8 5 1 55 54 58 68 89 61 41 97 28 26 69 9 59 10 7 34 15 31 93 1 13 73 18 98
98 57 77 6 25 4 11 39 59 45 97 88 63 61 12 59 73 48 47 39 81 86 88 70 84 93 82 36 25 54 80 58 8 43 37 81 11 26 59 32 11 68 56 68 45 31 86 29 26 29 12 96 38 65 94 17 59 92 98 79 46 93 63 65 85 94 57 62 97 77 15 52 60 3 65
57 21 11 63 25 46 75 29 31 62 58 26 40 28 33 75 82 6 80 41 51 84 87 2 55 44 81 9 11 69 7 79 65 33 30 50 83 56 58 49 3 48 62 12 87 91 91 38 17 75 7 32 28 77 24 65 77 72 81 29 12 83 93 92 91 67 60 40 93 35 23 96 65 47 79

[出力例]
1960

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

[入力例]

3 4

4 6 2 5

3 5 6 7

2 5 5 6

[出力例]

※AtCoderのテストケースより

[入力例]

2 2

4 0

7 3

[出力例]

※AtCoderのテストケースより

[入力例]

2 3

0 0 0

1 2 3

[出力例]

※AtCoderのテストケースより

[入力例]

3 3

1 2 3

6 5 4

7 8 9

[出力例]

※AtCoderのテストケースより

[入力例]

1 5

0 1 2 3 4

[出力例]

※AtCoderのテストケースより

[入力例]

20 30

79 26 49 19 88 87 44 69 61 31 17 25 28 32 34 34 30 74 19 97 66 35 32 54 75 97 48 64 51 40

91 82 28 6 54 56 1 88 4 11 68 32 89 51 61 77 22 84 91 91 38 79 86 83 92 27 76 80 63 52

25 66 85 50 55 56 58 96 71 2 65 67 58 57 81 18 56 99 44 73 42 66 91 36 77 43 47 95 26 68

94 13 0 85 14 37 36 34 58 86 1 44 49 28 15 26 24 44 39 98 78 27 30 93 68 78 49 95 26 26

21 31 92 95 23 21 8 55 41 86 25 62 26 27 25 85 1 11 4 73 42 26 56 32 32 66 99 60 68 8

54 51 1 6 86 24 20 1 0 0 97 72 46 67 98 56 61 94 45 67 6 60 1 48 97 38 87 69 90 99

55 37 44 84 33 26 70 86 63 78 20 42 87 6 69 35 20 34 77 12 32 24 28 74 29 42 98 88 30 90

70 57 29 52 58 20 9 51 14 45 27 35 51 91 98 90 69 10 35 45 99 0 38 25 89 2 32 29 72 79

30 40 7 96 97 86 61 48 37 69 24 24 71 42 47 60 28 89 77 26 88 35 47 49 84 20 62 98 65 17

58 93 63 54 57 96 75 46 3 8 94 20 96 78 98 56 3 73 27 91 48 55 44 71 10 53 95 83 49 28

36 67 56 11 30 94 15 14 36 6 63 39 47 2 93 48 27 28 82 83 98 5 29 79 8 42 51 76 95 97

89 75 9 23 37 25 35 33 50 85 41 53 28 95 36 16 99 12 98 58 21 62 71 66 93 7 55 85 50 45

6 9 40 8 7 19 32 56 78 79 26 79 75 88 33 35 55 70 13 59 15 98 96 25 44 46 15 91 25 40

8 75 80 4 1 33 83 76 48 13 24 7 92 29 19 99 62 2 68 83 27 25 93 79 47 13 9 19 73 81

49 46 7 39 77 13 9 8 39 41 69 30 96 76 36 86 3 94 39 76 87 34 46 5 54 43 50 74 89 87

36 76 48 54 18 43 89 79 59 2 91 79 1 57 21 35 65 54 96 9 72 75 39 19 93 23 55 79 20 22

55 37 5 73 87 1 36 85 91 47 4 86 74 56 62 90 40 97 43 93 10 70 55 72 19 26 46 72 59 31

0 82 39 78 91 99 67 47 23 92 70 74 45 48 92 24 41 98 28 67 30 2 43 49 88 66 88 18 13 29

44 44 16 48 93 84 40 26 32 82 19 92 39 46 93 28 11 88 18 78 97 38 18 98 24 46 58 94 70 92

60 4 73 79 33 43 14 99 65 7 41 48 53 86 72 91 95 83 1 58 45 15 33 92 25 67 77 24 32 92

[出力例]

266

[入力例]

50 75

81 23 73 83 35 30 8 53 0 84 1 5 48 52 26 12 78 87 79 35 84 29 82 80 23 68 6 61 13 79 66 44 6 25 80 44 54 36 55 81 84 64 78 64 91 85 19 75 87 3 93 93 91 41 86 84 39 34 27 77 39 61 79 80 43 34 84 14 22 30 68 47 22 84 0

93 92 11 88 80 98 31 49 10 87 41 25 80 60 97 1 18 65 9 2 52 45 26 9 54 14 16 84 73 12 66 61 30 9 94 40 87 39 95 59 12 24 34 59 36 64 21 27 33 35 2 35 84 22 31 80 88 61 66 40 40 50 54 4 82 18 77 88 68 73 96 54 21 73 47

54 24 5 42 98 34 25 20 85 21 2 86 91 87 70 24 21 9 55 80 74 63 65 89 78 44 75 41 18 6 49 89 0 64 25 9 62 71 79 14 67 87 40 47 6 16 99 32 20 23 46 19 26 7 1 40 26 66 31 79 70 64 36 52 56 90 28 44 94 5 84 15 10 16 34

31 43 96 15 90 5 76 25 38 76 90 47 20 31 52 45 31 64 60 38 41 79 0 96 99 7 17 97 40 46 73 92 72 85 52 28 63 14 66 24 12 35 96 14 68 20 29 2 61 98 68 31 2 1 99 89 88 9 8 39 68 15 40 12 20 58 45 48 8 55 50 22 2 15 22

23 9 44 79 27 54 37 62 47 77 52 49 92 20 51 55 69 54 12 91 1 54 98 98 88 61 16 88 38 60 92 28 96 67 15 67 26 64 48 20 72 32 18 66 34 68 90 80 28 64 50 76 36 72 85 47 39 50 36 27 66 77 28 67 94 55 20 4 36 85 60 69 38 50 82

68 48 44 72 39 81 27 88 29 71 47 29 89 21 84 44 37 53 16 68 5 83 13 22 25 82 32 73 52 67 55 50 57 91 40 27 18 45 75 50 96 26 78 69 96 2 64 44 43 56 76 13 73 76 21 61 72 88 31 84 90 55 53 57 30 42 56 90 73 21 88 47 64 53 52

47 21 3 75 52 72 7 65 63 94 80 40 63 53 4 9 67 76 45 68 44 10 38 79 31 0 81 89 30 19 27 14 46 53 40 68 10 34 83 29 22 50 53 50 0 95 90 50 25 77 33 79 66 77 60 40 82 97 86 70 65 88 60 36 10 5 49 85 87 14 20 87 23 36 64

98 1 96 11 32 25 71 22 76 86 74 66 10 29 49 49 9 52 28 42 12 66 28 45 24 1 61 40 37 98 20 41 42 97 86 17 61 57 69 54 59 73 54 0 80 45 20 32 16 71 43 19 31 8 41 14 75 16 94 21 95 54 18 20 76 65 47 10 29 17 47 18 53 57 62

59 24 42 54 46 65 68 83 36 64 38 68 57 7 18 23 81 2 64 11 85 8 86 25 18 85 91 44 24 70 99 62 70 59 34 88 61 95 90 79 26 7 41 31 55 57 21 9 45 57 5 68 75 10 23 19 46 21 96 34 22 11 48 63 81 16 26 27 14 62 94 8 35 38 13

97 23 37 24 83 79 24 15 32 7 17 92 91 37 39 27 73 94 50 21 86 60 55 16 0 52 41 36 25 83 47 51 10 32 23 7 74 29 42 15 2 46 45 8 60 40 19 79 90 26 12 24 58 2 23 29 54 3 43 29 29 25 68 4 67 29 21 0 28 77 93 47 2 49 6

48 51 87 83 3 58 25 79 31 28 91 11 39 37 75 4 58 53 62 32 37 30 80 35 57 48 84 94 26 32 94 3 95 7 77 79 19 80 47 94 76 65 60 71 46 68 43 51 91 83 45 70 80 23 24 32 33 2 5 73 61 20 44 38 81 20 8 38 77 37 86 42 68 53 32

82 25 27 63 35 21 46 44 64 40 95 64 2 11 10 70 28 84 13 63 43 47 29 26 52 94 93 38 30 93 59 31 2 47 6 30 71 62 12 61 4 97 41 33 3 88 81 71 31 50 99 46 6 19 32 14 95 59 62 17 82 52 48 42 67 99 65 53 65 54 22 8 72 97 35

74 49 2 80 47 85 64 21 57 78 30 61 16 74 76 18 24 34 99 70 73 77 22 68 14 61 29 76 3 83 74 62 10 65 39 50 62 7 94 93 43 30 23 96 21 52 99 98 74 39 99 89 91 51 8 87 31 12 37 12 54 63 75 68 72 47 2 75 8 64 19 45 95 7 26

10 41 41 73 29 48 67 6 10 59 88 69 57 67 43 6 54 29 20 22 23 3 42 25 3 33 46 38 99 7 22 27 94 74 45 5 27 2 75 19 32 98 48 8 49 19 71 88 63 54 6 44 67 3 16 35 73 31 23 5 74 1 59 70 83 26 69 82 65 59 33 92 26 47 79

79 1 83 28 48 22 29 80 14 94 92 79 18 82 54 41 7 40 17 81 61 56 77 1 62 47 80 77 60 64 68 0 14 7 3 45 41 70 56 64 87 40 48 46 0 95 42 77 20 96 75 45 63 14 91 86 44 67 97 29 56 35 82 51 18 88 38 79 12 12 47 98 66 93 23

72 33 90 56 30 39 42 9 44 80 9 60 67 48 70 53 19 48 86 10 60 52 66 75 68 34 76 33 82 29 17 35 14 14 10 76 85 43 13 74 11 69 85 44 45 4 28 42 27 3 8 13 60 20 82 55 21 37 26 93 47 40 66 66 0 91 33 17 20 44 59 88 62 37 46

92 46 0 28 15 53 65 51 19 90 5 40 39 71 79 51 31 46 67 86 15 16 90 41 88 7 45 71 27 45 38 50 12 12 82 48 82 75 56 99 99 78 51 79 72 27 67 2 82 70 0 84 36 84 16 40 6 36 16 7 32 23 37 96 95 15 87 70 19 62 30 40 92 97 84

52 13 82 14 15 47 33 23 67 12 39 38 65 33 22 55 2 7 51 1 77 28 2 56 66 18 42 41 67 73 29 12 70 28 15 33 16 73 82 45 64 8 28 65 57 82 6 57 44 97 28 94 44 28 56 19 50 94 13 55 15 44 42 92 12 26 94 80 58 90 50 27 78 65 35

19 74 60 20 15 75 0 11 91 89 8 52 43 89 40 72 55 29 92 79 72 41 85 94 13 37 22 49 51 85 69 56 13 55 28 78 86 70 63 38 95 68 23 26 39 66 9 49 41 38 34 51 19 39 10 46 45 62 10 93 44 6 58 10 62 33 58 53 85 7 44 46 82 36 47

85 51 11 37 91 62 32 93 13 25 17 46 32 5 81 74 91 32 45 33 6 11 39 51 17 68 3 12 48 9 97 27 98 18 98 86 56 75 4 16 95 16 99 0 69 87 31 2 27 66 87 60 77 13 5 4 85 4 21 4 90 25 2 27 19 35 54 51 24 88 61 1 6 27 54

17 45 81 21 71 78 76 38 59 43 31 50 79 94 86 82 24 88 95 56 40 35 0 3 24 61 75 48 46 14 31 76 25 64 62 56 55 33 34 56 83 57 46 58 40 58 17 53 91 64 89 50 25 93 60 17 38 39 20 97 5 24 48 6 60 85 53 13 16 71 21 39 11 50 87

56 19 6 60 66 71 80 16 84 1 48 1 78 2 38 85 52 43 36 95 69 42 28 6 59 49 15 6 80 89 27 49 94 86 45 52 95 6 98 73 70 53 59 48 0 93 29 73 36 22 53 96 4 76 45 47 96 11 48 46 54 29 55 43 44 26 19 93 38 91 67 78 88 22 88

64 74 53 13 20 18 65 62 81 92 7 28 59 4 96 27 6 41 57 85 52 76 53 11 23 75 29 70 33 30 26 34 79 43 67 15 43 54 47 68 25 28 26 8 26 24 53 19 85 68 42 73 24 30 89 88 35 61 81 22 93 25 3 36 72 31 47 15 74 83 10 62 52 15 57

85 33 58 67 42 14 98 1 23 78 92 98 54 53 90 97 78 15 32 26 92 54 67 2 19 94 51 0 6 81 18 30 31 96 38 50 34 51 16 86 99 39 9 94 49 11 41 87 67 90 48 5 61 85 29 98 0 76 64 55 14 89 75 2 32 98 28 46 27 27 40 75 78 20 81

90 30 3 77 22 3 87 49 63 27 16 89 40 14 53 93 62 19 8 58 37 21 74 28 75 33 98 56 46 77 29 39 37 15 48 15 91 82 89 21 99 65 54 22 57 3 92 34 78 38 44 82 52 77 64 58 84 86 54 88 92 40 86 96 13 81 61 54 17 13 23 51 31 26 12

53 72 97 25 68 58 93 67 63 88 72 10 74 13 38 0 56 30 7 65 82 57 32 60 23 24 43 49 45 99 73 3 55 13 35 15 44 51 4 8 28 57 33 98 16 64 96 69 84 86 85 76 54 9 8 31 7 91 80 84 60 26 41 38 82 36 52 74 66 37 55 48 59 6 10

76 60 42 92 29 48 21 25 9 93 37 27 26 69 31 28 22 45 76 87 70 78 21 34 7 86 84 97 51 68 0 70 70 22 54 51 88 84 32 38 91 82 51 22 44 97 56 6 83 11 12 19 28 91 1 7 8 76 57 11 90 78 42 31 44 81 70 50 59 58 93 50 86 89 38

90 69 9 66 78 95 99 43 68 3 51 44 59 31 86 45 91 73 13 1 93 18 47 97 11 58 81 90 20 81 23 20 62 70 24 30 49 47 34 44 29 78 32 40 75 32 76 64 35 13 32 58 75 34 60 81 21 86 64 12 95 26 67 70 73 8 16 74 38 21 42 68 55 59 91

52 87 44 24 62 81 15 29 87 99 49 7 81 30 4 64 6 61 25 92 20 33 48 50 22 33 83 18 50 94 48 38 69 50 82 24 43 32 45 11 61 93 63 50 90 61 9 77 57 4 22 75 4 14 91 94 80 14 98 72 53 65 63 26 34 73 35 70 1 69 8 85 15 16 17

17 61 49 51 85 77 9 71 66 70 70 75 26 20 16 16 35 68 12 35 63 43 33 22 40 19 67 92 74 47 7 77 9 24 36 9 63 28 46 2 75 25 20 26 97 66 64 4 65 82 94 14 25 17 38 31 50 27 92 14 77 66 3 59 85 39 45 99 54 13 56 95 46 55 60

87 42 92 3 44 27 49 91 86 16 10 67 46 29 23 20 50 85 37 16 32 27 87 83 33 53 32 44 69 87 87 62 0 96 23 28 93 51 10 39 6 96 73 26 97 5 75 31 35 27 25 93 21 71 76 68 36 71 48 29 57 11 86 43 0 82 17 86 22 52 20 57 30 39 51

14 62 53 40 60 16 21 7 35 16 8 1 37 99 37 59 54 86 23 5 87 26 83 47 77 0 45 73 87 65 27 52 7 4 67 5 25 86 61 59 22 31 57 46 0 61 8 11 76 27 80 25 15 64 92 59 90 63 61 70 61 29 41 42 81 39 68 42 31 21 32 63 8 38 51

71 62 76 49 10 48 11 17 86 14 12 21 50 8 90 3 16 3 60 61 59 96 52 81 85 42 55 65 60 94 85 97 66 80 15 22 87 1 68 63 32 82 49 69 44 31 50 13 59 4 37 2 41 51 58 40 13 7 26 6 36 47 74 35 22 80 42 63 55 35 99 77 11 39 29

6 64 99 56 91 78 66 92 61 35 16 91 47 42 91 45 82 12 18 15 42 18 60 14 19 95 41 5 92 63 53 74 76 0 48 41 74 67 47 64 17 29 52 49 14 65 73 13 56 46 23 90 15 9 40 6 86 72 2 14 46 42 19 17 40 66 63 75 2 24 22 8 36 22 89

0 39 48 87 79 1 26 61 88 49 70 98 19 44 17 49 71 24 79 64 4 88 76 54 55 47 68 25 58 52 81 46 3 68 87 76 46 16 49 18 2 99 73 19 30 30 75 90 82 55 71 18 13 70 26 54 12 60 82 28 21 42 52 76 76 74 73 58 59 89 52 97 53 60 42

17 10 76 49 40 50 89 85 77 80 87 12 57 66 5 58 66 39 13 99 71 81 24 74 57 39 8 35 75 64 24 88 30 83 38 48 17 5 1 70 3 73 35 80 18 51 8 92 6 3 82 50 45 8 24 84 18 9 33 61 38 92 9 85 56 40 75 23 38 21 28 74 7 21 91

23 17 31 6 51 21 27 28 26 52 38 63 83 55 46 47 5 68 59 57 15 46 84 93 40 50 33 27 49 31 80 89 76 72 80 77 26 11 88 2 96 70 33 58 5 57 0 46 37 85 87 62 95 77 87 7 40 54 31 44 73 57 77 97 45 94 36 19 65 42 16 17 8 24 9

56 72 72 10 18 58 89 35 17 19 99 57 42 55 33 96 53 22 55 85 9 64 43 21 72 76 33 35 52 88 44 78 78 50 40 58 72 0 80 34 45 55 66 64 45 39 64 68 98 29 78 31 31 74 9 69 4 2 65 83 62 55 54 51 97 5 63 73 75 1 66 40 34 51 39

40 28 40 57 72 88 65 88 87 11 2 92 23 57 46 26 39 81 61 26 77 70 3 75 31 29 52 44 63 75 32 92 91 25 11 33 90 57 11 2 81 46 76 21 53 52 83 6 2 65 94 7 7 90 78 47 61 92 0 8 56 7 4 97 62 68 73 44 84 71 24 75 39 79 99

75 69 74 10 86 78 49 25 39 56 58 84 61 62 53 96 85 12 37 17 21 66 43 6 19 59 57 16 80 77 74 39 74 54 75 44 29 25 52 8 95 71 18 7 44 34 36 53 33 22 18 66 13 29 32 10 38 33 24 78 30 59 74 74 53 78 45 60 83 81 46 0 53 17 44

41 59 90 93 59 89 54 89 40 18 90 22 2 61 63 25 78 52 27 95 32 20 64 16 4 89 23 95 57 23 11 2 34 56 61 27 37 65 99 58 41 75 5 56 85 85 74 73 50 53 34 3 67 51 5 66 38 31 57 14 60 89 81 12 20 63 56 69 14 14 90 1 52 61 67

9 10 71 29 40 59 95 43 28 71 28 85 21 30 12 15 40 79 76 53 65 35 29 5 56 3 19 50 27 96 48 14 31 79 46 76 91 85 54 84 25 1 78 54 33 57 40 2 14 93 4 7 38 29 4 50 95 97 70 7 33 52 77 17 13 4 41 29 64 94 44 39 89 44 18

12 28 46 63 56 93 80 87 79 57 95 53 31 86 96 93 86 83 8 43 54 57 2 13 20 72 1 8 84 37 3 59 19 38 98 16 74 16 61 95 18 15 18 96 99 39 64 48 27 66 16 8 16 31 71 41 89 79 6 62 9 86 58 22 63 45 88 66 27 51 47 46 83 14 92

33 4 2 59 60 54 9 21 62 50 87 65 70 83 70 28 63 25 89 43 72 5 21 15 89 84 73 85 25 97 22 87 28 1 98 42 18 38 38 23 51 81 99 90 74 23 76 24 80 65 21 93 82 71 96 89 36 53 34 88 98 55 68 4 88 69 47 64 16 86 60 73 18 40 11

18 23 50 25 2 38 82 27 3 47 17 89 71 59 16 54 9 18 3 52 0 36 47 8 93 63 67 58 26 1 91 41 58 37 11 5 96 8 97 24 26 74 28 90 82 95 51 52 11 70 26 40 54 12 36 2 31 60 75 46 1 37 53 55 88 16 61 61 65 46 96 35 90 83 72

22 46 3 57 43 30 8 53 13 57 21 66 27 53 22 80 8 22 91 99 67 67 87 95 39 80 51 18 31 47 36 65 3 94 58 18 34 29 24 91 49 90 54 49 65 16 55 11 14 46 10 56 24 24 59 95 22 42 65 77 0 1 90 73 67 36 57 12 0 36 11 22 69 94 31

88 73 44 15 8 80 93 33 52 18 64 79 66 89 83 17 77 92 21 56 62 21 76 28 26 85 68 63 34 38 22 39 94 92 82 22 39 91 16 36 31 52 13 25 24 26 59 65 92 16 4 35 50 39 1 18 37 62 97 14 49 57 65 12 78 14 19 28 46 51 18 70 2 0 11

23 20 28 58 30 55 75 17 68 55 16 40 76 70 7 78 77 26 95 14 39 10 51 16 55 5 47 46 66 37 99 18 90 6 28 36 60 98 11 59 92 62 90 91 54 43 27 63 8 5 1 55 54 58 68 89 61 41 97 28 26 69 9 59 10 7 34 15 31 93 1 13 73 18 98

98 57 77 6 25 4 11 39 59 45 97 88 63 61 12 59 73 48 47 39 81 86 88 70 84 93 82 36 25 54 80 58 8 43 37 81 11 26 59 32 11 68 56 68 45 31 86 29 26 29 12 96 38 65 94 17 59 92 98 79 46 93 63 65 85 94 57 62 97 77 15 52 60 3 65

57 21 11 63 25 46 75 29 31 62 58 26 40 28 33 75 82 6 80 41 51 84 87 2 55 44 81 9 11 69 7 79 65 33 30 50 83 56 58 49 3 48 62 12 87 91 91 38 17 75 7 32 28 77 24 65 77 72 81 29 12 83 93 92 91 67 60 40 93 35 23 96 65 47 79

[出力例]

1960

■参照サイト
AtCoder Regular Contest 025

2020年4月27日2020年4月28日

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

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

■感想.
1. 方針を決めるのに時間かかったものの, AC版となったので, 良かったと思う.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
int r[202020], t[202020];
LL m[2020];

int main(){
    
    // 1. 入力情報.
    char c[202020];
    scanf("%s", c);
    int l = strlen(c);
    
    // 2. 10 の 冪乗 について, 2019 で 割った余りを保存.
    t[0] = 1;
    repx(i, 1, 202020) t[i] = 10 * t[i - 1] % 2019;
    // rep(i, 10) printf("t[%d]=%d\n", i, t[i]);
    
    // 3. 2019 で 割った余りを 保存.
    // i文字目までで, 2019で割った余りを保存.
    repr(i, l - 1, 0){
        r[i] = r[i + 1] + (c[i] - '0') * t[l - 1 - i];
        r[i] %= 2019;
    }
    // rep(i, l + 1) printf("r[%d]=%d\n", i, r[i]);
    
    // 4. 余りの個数を集計.
    rep(i, l + 1) m[r[i]]++;
    
    // 5. 条件を満たす整数の組は？
    LL ans = 0;
    rep(i, 2020) ans += m[i] * (m[i] - 1LL) / 2LL;
    
    // 6. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

int r[202020], t[202020];

LL m[2020];

int main(){

// 1. 入力情報.

char c[202020];

scanf("%s", c);

int l = strlen(c);

// 2. 10 の冪乗について, 2019 で割った余りを保存.

t[0] = 1;

repx(i, 1, 202020) t[i] = 10 * t[i - 1] % 2019;

// rep(i, 10) printf("t[%d]=%d\n", i, t[i]);

// 3. 2019 で割った余りを保存.

// i文字目までで, 2019で割った余りを保存.

repr(i, l - 1, 0){

r[i] = r[i + 1] + (c[i] - '0') * t[l - 1 - i];

r[i] %= 2019;

}

// rep(i, l + 1) printf("r[%d]=%d\n", i, r[i]);

// 4. 余りの個数を集計.

rep(i, l + 1) m[r[i]]++;

// 5. 条件を満たす整数の組は？

LL ans = 0;

rep(i, 2020) ans += m[i] * (m[i] - 1LL) / 2LL;

// 6. 出力.

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

return 0;

}

[入力例]
1817181712114

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

[入力例]
14282668646

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

[入力例]
2119

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

[入力例]
5927561483499133816681483285962193978296762292135521819997344122591819263711514166282293149468917732931372373582374231754637521338415522734986783746251827878858734285992236975761669764917192519634598499956141881618566486524156655583242728247725527832955998571927419919664517757174362165539848928432818819783288418317797891449995554482781481393773592238658854731667832175299162387233899479317587693629389288842517584816558249714533418663147625787276558616452141341356183268829976755771374161469264246991695389539282469276854743339244587176376811562583349151716683359386276825445915243943354271813118549572889596242256983768973299179492513813963166548373125884168652873488175139512567463419394877115371555596287468718681524769631398116896779714269685182377121875661883216277146935177167586657246684288426748585746111476633777625397857847791227846447781527652718365152611432287777972799773917717781292899491177181763659662268342866844661496823674993676359949711779674315715974281427356378439739315378244

[出力例]
211

[入力例]
97228238287242445316297743562293571698136258547357947664137676744787922269777911237528513861156186597324215846711127225828383558398319668244438459791753997581456126356261444731242776625764281311725613586397355614863752185811558675894635782967131872611431961158726691611425372722522665562681397975849497213965444742673553893915738645335128683673445578328225595493367171282659242892738752912911295787728215545426317145765628211362272374621969166257832285662363327561255897553853755271682266589525832262998889511715134226227154168212957786988328833191116875523548248455337535768365192923268929249874252126353512169866142966837557181422476466664955338134995881877252549618484182117218174122345398527169659642974627611471686184974374711987267623722773168192325477251751112133853763142417349415588322718385649659277221955384597588288176942628819731316544956935313883188633594571632613627766446643344927916349262771849311952587942677424288597585719968582134592698486959177783652764624175377469794827765346732911681649683413359145657988387492643414545325548837665575782416266892673692242364852675888531883526188461253945634113343286132513753585429947347372182593937985691453898465646446328747476274628154626297728935929953963898585918952811194147453916579168677672849821641933797722838938131542725837493913632992868367511339571668683828757739439956776122533293988889366784276374449214611872968942766922197779245996138537356134544698285131447816325558292577977548997853545522541448564824254479552321573399161123858827775385673488888495171737135739813928898754687367471134342693644164131174171545574941826528427248586426552437675241235972977272345518584125696796554613138697921324262591952918769893453287613249588119729333127965727212523556327126578141191375412541173713993162573285279976924655946263372519781349757669742328633567424128564312983372961442361631729926886814765664416273472295425554788847482942948379576435668296624794167157396645865427116931783746691476553952571459849762988567564214879132449873556937523212355725797428589474797685711535266513659394965935668687213882692816114744615356364781193973474619154221235759458314558489459818965936398842619375793188515872183129862358876577169777912757425334157419846998291713446764485567616995892432831774597473521269819277463276769345974943498375191863972984823235142339889637588736784269885985178552494447613562928448216147945673917615598679589629253937317614917195696198885316852914554918923238714647639513723477973155731356137112939947447454199248156415441747484149628483197329943878929171175788144434732954751896639559581292591957192638738932366443292999897583481226822891974225397453736381741998794469259947943421485918733756913221337924182313664899545531347374627619465397854734563419612962411255119972155175329931192982535934679935817947879265869983716856415652318195538225753828974793188889555569586176645879365184938433548174975733475178135257787886319618655824223462264769987925648418787766388455684643635816723297682311411587958118557972187116388476365933846454153362762238752759236612132584938618487639823343284949381224833396899911947775327981843262267362719922371877171585449155587545165176552397735931948777996667366677518287742189283451238862721982492612381753749972918459915757555275584426511598563278658311551589383488445451524985579351172293185142483352644298691416337389149215939353432317873623126293968676899498552693579268721435763459196423676442256957975362317726757864711193656262441342285212133985684361254816834143942551699442713829821876946336457868557937447545824455676834126317469182728672178557721544161737438235514642948656468391636319523116282696412734467791264413588474768494392835243221588166749523645165749472568641872764471849417478877454129149549518369989338692421774463976846343183935668135331961583712358461389781711724313474268117692477213625547261341363439281529343523788281942466236422758367325758213943348125311549725776431347671831847574929543284595844629115775117425823339744265127713698168615416336529916877581271688657217772772435329644139157618137634485387723415565646432779293522887785156918468698516218614156274927973235896957571974791524816269874973671959444618289434314627755921979641898942733647766815622882772532495253578612768527242213782636572443917973346391873358554189786439549173297542257457134627899514861847733767584125193843272652244466828835422452486492353835634625832342443536365222222288973721854255556685515895826221239521875471163879644365468485892466864739371584695792168599647968337932994954135341266123577555648515777656789918858723999514782758128383895895882648244295599999331123488235421364424247863674626585546875693179888692886778561772126339861922952724187529467443533224559739134238214389158953211824727428645523684638663959614215634286796921985531546371114983389237869757514117439656498279733918869886253524876447165831113865315312634612817552774589541182855661786459353989634922818962858643144565765531828745374841759773978732631399712455296473473552914328121479323762592182

[出力例]
6199

[入力例]
7659183897322581891441989417986522374719288564486137788587674721377878883159646365746363295255165129311581347555687884227489157749189591898738479514317888816248967165179829283276392434515956864326728221229728881257776356664878151211974914556868799938983352133475239727528421484656773281212727248642975331924732498222379128527119286615753355876978129291294846951793899362666563268474157666719546578474784124934184364866482226411334895149385186482573319694335391552913622269474868443726149576378754894269828835275524388692222346735534682281374644484574418711874514877756255212275792495739718226521827867537426952561597794785168763896168361352586881641572159283855129653847599888739264822278846934248972139944957676353334227121173448665127884696983933297885632168751861931155176281879546699648134131362739137317563564868435252661715479846149666181226718955959184398458596836155838232871169673863145224918563958187747631635155127437847679765347137373613385993619299314428364783212512678498836453297143981184695499798225152175649338675359279762274321564465678287316537447492174867579714232538435151468162472762564798948341138783847132856655672288638789918218672423359565556926812879113627929597664521446687895722863346417892781952917446229641769457337257952191472355468332969175769283815595636755423127835879669651575774415771954536781788862525939683915965495515994651825178797161978793589713917852215953263174812399976861948192875565146794919757651235237941319161711515966124265817755129852746179111712775762121952541557986275243758243696141818686275549522675973938133534244676293177165927825736182674177736526811242477111885163337212821696438241498992189559169598399149776884174121662446468818868465817322497833191567181764783215143315598873958481824725493435566592825841657234696365485222648892166481952517229591639529423588217345951872984864351734186334327735814288334563757759556411276219337386575153444739728375537487937693539223598146494698938113179331921239349493956472668989143812365898711398724693572739485475432259573622128597565438285271443215233216116634588855911514324495767311988688797877653539598383513826754632137458764233637852659848382751522189497287911598128491556467671944167396435591256746466685298727167414385649981543941632293441135938747687883175579177625367916944212353193383282699829214313573518355923575692126394947311582697946423543156566649766411861615895513972937467375734156199354532141982184164418259585184715924488388593893644292825257425673999732121341963671336995852288421545224663395854991889513488519712245932548118714291893685249331286356265485392659357695294417958549197441934521535866479761228292527845912991132768679437843847833591628661373269961622857945624553212744855818932341821631997186932896462661247523174154525586811625569731452977713883435833833769271458299657452826774267839887366337527279529566789794861799248241851521366467684926532819286458492812367714869251417654712139654251542628418491754794196457632171149687232834863416276667918726759743899478235853216545334373297655583472861964662258885589437363335877823743243189748711785468518223351943135516444361684123985611474787168356819531541671615541898814141984491843827163841885864875333472559226176927866296383258957732185484586862627287331274121648812366776824128494656761431678163181378356233991261943836757645747376122374846631245472966579218459377149617714334118452615777375765774158833335619853412316646696136838376317314214752711698946893965422252652961253615617566475933758368796587757726878118539882414652713296541451311584116363188723365262477631238378833384894456127275457498781546336764472563125541488862836713368531976241562636299927592272186783219374764137455774341916957622224457543523916578831134443275173552655558617789968262515739796869854863666133536698211981692336914755656771981132582631252499648898827938848734887948879678126676449936832957342661137625496372992171969281916713445999413935742213242327438511557443183872287655737768515839247873731759186359987424876834142423517944568986996448125425427257996412385337613285898736295817358494797772845711446783446728155768799658443363952285437724678126947168316924149858624237646695154112619957654213434323162128571989844146262959625549949368144862595742467191245232876661128826848371521393518343529755573596743813196123624159223817645558137571547614828451916365542515478488891444366719983288294947476976764174662293119552922632993749439862263198567758533521933794312113465254261131416187675851513336696958284738244411836274552228654749411469332797189891526542869957454776778334693133694597752823582988383821151279356291459653445982511732296335392136377265887912734332545153971526451528111326675533744577593944395571724375543761638269832394883553187676987343497657837759454379794771323621985491498677256322793168178487471353217742272279567142764931236819773792235221351714365256436788674531828537132981799158511184952458334366314476628726775871162698169597661342276529294185932212977855992614552357377296656182822915166432962273445211758182981924982284762143973853766482688712661919669641283885769981893284287622565557994571729299629645758964653876147248746672879834948928668768954783754353864676236331496613788153533636368588143847877171598649493762621256654677897234967435513698755465783485749439337734833725316453326673439826259284741753142371887437333524486385456438624758245672858111144628183529385554228576217994922215465491561577838883987928276899971495998261584325634392914722794811269449271272426481933554215625238941982536524896535498293827484442827343192712687835918666663532856658256312967673256753468829718816599655813277233424659818456265181966286672169633266848588364136572978161846945519551821431826174772451553777756165338713841355365746326334267937632789735548194471733938323842392792872572334114322578868396497657174458448222117597975398774729157618612869994331848822155474186433426839456574529823361495559573842748993736574463127179367665535361685645541993893975951533185821897171769459562882299814477366394744935187967923612468552295928821881289948588725256775969242512682274484129654979268841482718421355445728657299745417366771884141114558764931729334967196513514636983653739881385536447975921553219216473258286635448244515638937529923922637669396123761712741797622438835777131746317546665421671394734173152328313813421787512593655336478931415871697138898361212813764836327217569847519267917321794211671329996538778241967786869652733366576979616293357672831848872838157899571618444395437968133229317145871983584328712463322512328114224832783254333749918515738775396571461646413338712417461327645799463444584852928414328267466454446783395857176455333635223824488399717162215349229984686699181655788999647994515866293879677361839682576982914484612424255623672813914273881856322864129337358591635479167989341264452746428786117313748162598556619964778946963873388332939797291487851869444976231781623364519878961179952165441352748346375774924552896991959287619748112973226576839669568337565916339681211258218959418845332393132977869121732467692645531389382511548736145338717111342917194878784351754629674177315983713159687787736552712771794836684213953922152182286877768371124526452339989915299624739425557922669828318369452982423695734393795644524462716421963573245873295133882643166911131561213281568525996387573376688398346238184841444558259977452163641473589869325772641334222414552498868664381853164287895359412817116579863352615629738467792425267865535937724959687858379632376937611499643124713647859697296134512755281573585921831672263229314574232648412294211277827446588679662665443167183456921642221948766553773457615785377387559245456468775628988278814793621887499434934762884949791552373313715622184748764732544818627471726926755892776696275771875196587145934591844771494411293528331393186253171441687793695393414892312548287949749167861519582458657957462973418288145632411916812417582145252114624689379511976444526467391167631957592389334276872719475463497913458672388634234461265852816461755259634559642689854685496515229776944921928743548699654943622111815266367374293423473514964418527443966179964416957281361263549494287752433281185651594893852231441455267363954987753239631343662986323512259749294141157829741792554788472755325233965396449185788425295756577783623552311573882428338591817771571653933954954856777613212122753641145376495747442979941127986386813636554816772856948337953952639242971354636379172812323284251292794351522136179139464943968598293553913864746716128624258598683213311575967591454113517299765546414543919816683711355967877787549884262242627732597195824288756241994278166691596374926953186789863534178969543421764488834181751813237158179838779278328591817372634663338186545346537294356551546279911577475348774972596446845458513962996572425411122691922689821964655667294544563133286758744829441957432194484851926374687167979339443678127361284393444628319452828717648527661338939651158546337271584737637163297366442799276227657654354696889832559678569496263663752862364526636155781626529447526162253975689848799348857767272814319653727859334573347541868529734989421416966642597662355941875741951873693495183552779593959545672517146231884794936873173427415235157291188396298421629538513694137549647752489588258285992715558879972928538496999721968494581931169329665633948676714627449869697546112338386626418982691247944746865374454949189999853261618995752299936544357648339789743916597361265128257281892539633169868162447952176384978166217224558632269493356686838675821431377233494887234861697632711816999326825929497238268797213335259481495157282142276475679374946855216244599667889642648328969747438664447813177633816781548786528851411761594648132219239624752953714811517766329344683983389498969972365766331787183378416719493562311664687865737499895162562282281177971924526331454921959775425157841428358832774235251643216391735182581825466334153948483536744626512265326573979365879285918657274514881685787185144177443985438743376373446634498619192128868891588498365323742249583

[出力例]
24593

[入力例]

1817181712114

[出力例]

※AtCoderテストケースより

[入力例]

14282668646

[出力例]

※AtCoderテストケースより

[入力例]

2119

[出力例]

※AtCoderテストケースより

[入力例]

5927561483499133816681483285962193978296762292135521819997344122591819263711514166282293149468917732931372373582374231754637521338415522734986783746251827878858734285992236975761669764917192519634598499956141881618566486524156655583242728247725527832955998571927419919664517757174362165539848928432818819783288418317797891449995554482781481393773592238658854731667832175299162387233899479317587693629389288842517584816558249714533418663147625787276558616452141341356183268829976755771374161469264246991695389539282469276854743339244587176376811562583349151716683359386276825445915243943354271813118549572889596242256983768973299179492513813963166548373125884168652873488175139512567463419394877115371555596287468718681524769631398116896779714269685182377121875661883216277146935177167586657246684288426748585746111476633777625397857847791227846447781527652718365152611432287777972799773917717781292899491177181763659662268342866844661496823674993676359949711779674315715974281427356378439739315378244

[出力例]

211

[入力例]

97228238287242445316297743562293571698136258547357947664137676744787922269777911237528513861156186597324215846711127225828383558398319668244438459791753997581456126356261444731242776625764281311725613586397355614863752185811558675894635782967131872611431961158726691611425372722522665562681397975849497213965444742673553893915738645335128683673445578328225595493367171282659242892738752912911295787728215545426317145765628211362272374621969166257832285662363327561255897553853755271682266589525832262998889511715134226227154168212957786988328833191116875523548248455337535768365192923268929249874252126353512169866142966837557181422476466664955338134995881877252549618484182117218174122345398527169659642974627611471686184974374711987267623722773168192325477251751112133853763142417349415588322718385649659277221955384597588288176942628819731316544956935313883188633594571632613627766446643344927916349262771849311952587942677424288597585719968582134592698486959177783652764624175377469794827765346732911681649683413359145657988387492643414545325548837665575782416266892673692242364852675888531883526188461253945634113343286132513753585429947347372182593937985691453898465646446328747476274628154626297728935929953963898585918952811194147453916579168677672849821641933797722838938131542725837493913632992868367511339571668683828757739439956776122533293988889366784276374449214611872968942766922197779245996138537356134544698285131447816325558292577977548997853545522541448564824254479552321573399161123858827775385673488888495171737135739813928898754687367471134342693644164131174171545574941826528427248586426552437675241235972977272345518584125696796554613138697921324262591952918769893453287613249588119729333127965727212523556327126578141191375412541173713993162573285279976924655946263372519781349757669742328633567424128564312983372961442361631729926886814765664416273472295425554788847482942948379576435668296624794167157396645865427116931783746691476553952571459849762988567564214879132449873556937523212355725797428589474797685711535266513659394965935668687213882692816114744615356364781193973474619154221235759458314558489459818965936398842619375793188515872183129862358876577169777912757425334157419846998291713446764485567616995892432831774597473521269819277463276769345974943498375191863972984823235142339889637588736784269885985178552494447613562928448216147945673917615598679589629253937317614917195696198885316852914554918923238714647639513723477973155731356137112939947447454199248156415441747484149628483197329943878929171175788144434732954751896639559581292591957192638738932366443292999897583481226822891974225397453736381741998794469259947943421485918733756913221337924182313664899545531347374627619465397854734563419612962411255119972155175329931192982535934679935817947879265869983716856415652318195538225753828974793188889555569586176645879365184938433548174975733475178135257787886319618655824223462264769987925648418787766388455684643635816723297682311411587958118557972187116388476365933846454153362762238752759236612132584938618487639823343284949381224833396899911947775327981843262267362719922371877171585449155587545165176552397735931948777996667366677518287742189283451238862721982492612381753749972918459915757555275584426511598563278658311551589383488445451524985579351172293185142483352644298691416337389149215939353432317873623126293968676899498552693579268721435763459196423676442256957975362317726757864711193656262441342285212133985684361254816834143942551699442713829821876946336457868557937447545824455676834126317469182728672178557721544161737438235514642948656468391636319523116282696412734467791264413588474768494392835243221588166749523645165749472568641872764471849417478877454129149549518369989338692421774463976846343183935668135331961583712358461389781711724313474268117692477213625547261341363439281529343523788281942466236422758367325758213943348125311549725776431347671831847574929543284595844629115775117425823339744265127713698168615416336529916877581271688657217772772435329644139157618137634485387723415565646432779293522887785156918468698516218614156274927973235896957571974791524816269874973671959444618289434314627755921979641898942733647766815622882772532495253578612768527242213782636572443917973346391873358554189786439549173297542257457134627899514861847733767584125193843272652244466828835422452486492353835634625832342443536365222222288973721854255556685515895826221239521875471163879644365468485892466864739371584695792168599647968337932994954135341266123577555648515777656789918858723999514782758128383895895882648244295599999331123488235421364424247863674626585546875693179888692886778561772126339861922952724187529467443533224559739134238214389158953211824727428645523684638663959614215634286796921985531546371114983389237869757514117439656498279733918869886253524876447165831113865315312634612817552774589541182855661786459353989634922818962858643144565765531828745374841759773978732631399712455296473473552914328121479323762592182

[出力例]

6199

[入力例]

7659183897322581891441989417986522374719288564486137788587674721377878883159646365746363295255165129311581347555687884227489157749189591898738479514317888816248967165179829283276392434515956864326728221229728881257776356664878151211974914556868799938983352133475239727528421484656773281212727248642975331924732498222379128527119286615753355876978129291294846951793899362666563268474157666719546578474784124934184364866482226411334895149385186482573319694335391552913622269474868443726149576378754894269828835275524388692222346735534682281374644484574418711874514877756255212275792495739718226521827867537426952561597794785168763896168361352586881641572159283855129653847599888739264822278846934248972139944957676353334227121173448665127884696983933297885632168751861931155176281879546699648134131362739137317563564868435252661715479846149666181226718955959184398458596836155838232871169673863145224918563958187747631635155127437847679765347137373613385993619299314428364783212512678498836453297143981184695499798225152175649338675359279762274321564465678287316537447492174867579714232538435151468162472762564798948341138783847132856655672288638789918218672423359565556926812879113627929597664521446687895722863346417892781952917446229641769457337257952191472355468332969175769283815595636755423127835879669651575774415771954536781788862525939683915965495515994651825178797161978793589713917852215953263174812399976861948192875565146794919757651235237941319161711515966124265817755129852746179111712775762121952541557986275243758243696141818686275549522675973938133534244676293177165927825736182674177736526811242477111885163337212821696438241498992189559169598399149776884174121662446468818868465817322497833191567181764783215143315598873958481824725493435566592825841657234696365485222648892166481952517229591639529423588217345951872984864351734186334327735814288334563757759556411276219337386575153444739728375537487937693539223598146494698938113179331921239349493956472668989143812365898711398724693572739485475432259573622128597565438285271443215233216116634588855911514324495767311988688797877653539598383513826754632137458764233637852659848382751522189497287911598128491556467671944167396435591256746466685298727167414385649981543941632293441135938747687883175579177625367916944212353193383282699829214313573518355923575692126394947311582697946423543156566649766411861615895513972937467375734156199354532141982184164418259585184715924488388593893644292825257425673999732121341963671336995852288421545224663395854991889513488519712245932548118714291893685249331286356265485392659357695294417958549197441934521535866479761228292527845912991132768679437843847833591628661373269961622857945624553212744855818932341821631997186932896462661247523174154525586811625569731452977713883435833833769271458299657452826774267839887366337527279529566789794861799248241851521366467684926532819286458492812367714869251417654712139654251542628418491754794196457632171149687232834863416276667918726759743899478235853216545334373297655583472861964662258885589437363335877823743243189748711785468518223351943135516444361684123985611474787168356819531541671615541898814141984491843827163841885864875333472559226176927866296383258957732185484586862627287331274121648812366776824128494656761431678163181378356233991261943836757645747376122374846631245472966579218459377149617714334118452615777375765774158833335619853412316646696136838376317314214752711698946893965422252652961253615617566475933758368796587757726878118539882414652713296541451311584116363188723365262477631238378833384894456127275457498781546336764472563125541488862836713368531976241562636299927592272186783219374764137455774341916957622224457543523916578831134443275173552655558617789968262515739796869854863666133536698211981692336914755656771981132582631252499648898827938848734887948879678126676449936832957342661137625496372992171969281916713445999413935742213242327438511557443183872287655737768515839247873731759186359987424876834142423517944568986996448125425427257996412385337613285898736295817358494797772845711446783446728155768799658443363952285437724678126947168316924149858624237646695154112619957654213434323162128571989844146262959625549949368144862595742467191245232876661128826848371521393518343529755573596743813196123624159223817645558137571547614828451916365542515478488891444366719983288294947476976764174662293119552922632993749439862263198567758533521933794312113465254261131416187675851513336696958284738244411836274552228654749411469332797189891526542869957454776778334693133694597752823582988383821151279356291459653445982511732296335392136377265887912734332545153971526451528111326675533744577593944395571724375543761638269832394883553187676987343497657837759454379794771323621985491498677256322793168178487471353217742272279567142764931236819773792235221351714365256436788674531828537132981799158511184952458334366314476628726775871162698169597661342276529294185932212977855992614552357377296656182822915166432962273445211758182981924982284762143973853766482688712661919669641283885769981893284287622565557994571729299629645758964653876147248746672879834948928668768954783754353864676236331496613788153533636368588143847877171598649493762621256654677897234967435513698755465783485749439337734833725316453326673439826259284741753142371887437333524486385456438624758245672858111144628183529385554228576217994922215465491561577838883987928276899971495998261584325634392914722794811269449271272426481933554215625238941982536524896535498293827484442827343192712687835918666663532856658256312967673256753468829718816599655813277233424659818456265181966286672169633266848588364136572978161846945519551821431826174772451553777756165338713841355365746326334267937632789735548194471733938323842392792872572334114322578868396497657174458448222117597975398774729157618612869994331848822155474186433426839456574529823361495559573842748993736574463127179367665535361685645541993893975951533185821897171769459562882299814477366394744935187967923612468552295928821881289948588725256775969242512682274484129654979268841482718421355445728657299745417366771884141114558764931729334967196513514636983653739881385536447975921553219216473258286635448244515638937529923922637669396123761712741797622438835777131746317546665421671394734173152328313813421787512593655336478931415871697138898361212813764836327217569847519267917321794211671329996538778241967786869652733366576979616293357672831848872838157899571618444395437968133229317145871983584328712463322512328114224832783254333749918515738775396571461646413338712417461327645799463444584852928414328267466454446783395857176455333635223824488399717162215349229984686699181655788999647994515866293879677361839682576982914484612424255623672813914273881856322864129337358591635479167989341264452746428786117313748162598556619964778946963873388332939797291487851869444976231781623364519878961179952165441352748346375774924552896991959287619748112973226576839669568337565916339681211258218959418845332393132977869121732467692645531389382511548736145338717111342917194878784351754629674177315983713159687787736552712771794836684213953922152182286877768371124526452339989915299624739425557922669828318369452982423695734393795644524462716421963573245873295133882643166911131561213281568525996387573376688398346238184841444558259977452163641473589869325772641334222414552498868664381853164287895359412817116579863352615629738467792425267865535937724959687858379632376937611499643124713647859697296134512755281573585921831672263229314574232648412294211277827446588679662665443167183456921642221948766553773457615785377387559245456468775628988278814793621887499434934762884949791552373313715622184748764732544818627471726926755892776696275771875196587145934591844771494411293528331393186253171441687793695393414892312548287949749167861519582458657957462973418288145632411916812417582145252114624689379511976444526467391167631957592389334276872719475463497913458672388634234461265852816461755259634559642689854685496515229776944921928743548699654943622111815266367374293423473514964418527443966179964416957281361263549494287752433281185651594893852231441455267363954987753239631343662986323512259749294141157829741792554788472755325233965396449185788425295756577783623552311573882428338591817771571653933954954856777613212122753641145376495747442979941127986386813636554816772856948337953952639242971354636379172812323284251292794351522136179139464943968598293553913864746716128624258598683213311575967591454113517299765546414543919816683711355967877787549884262242627732597195824288756241994278166691596374926953186789863534178969543421764488834181751813237158179838779278328591817372634663338186545346537294356551546279911577475348774972596446845458513962996572425411122691922689821964655667294544563133286758744829441957432194484851926374687167979339443678127361284393444628319452828717648527661338939651158546337271584737637163297366442799276227657654354696889832559678569496263663752862364526636155781626529447526162253975689848799348857767272814319653727859334573347541868529734989421416966642597662355941875741951873693495183552779593959545672517146231884794936873173427415235157291188396298421629538513694137549647752489588258285992715558879972928538496999721968494581931169329665633948676714627449869697546112338386626418982691247944746865374454949189999853261618995752299936544357648339789743916597361265128257281892539633169868162447952176384978166217224558632269493356686838675821431377233494887234861697632711816999326825929497238268797213335259481495157282142276475679374946855216244599667889642648328969747438664447813177633816781548786528851411761594648132219239624752953714811517766329344683983389498969972365766331787183378416719493562311664687865737499895162562282281177971924526331454921959775425157841428358832774235251643216391735182581825466334153948483536744626512265326573979365879285918657274514881685787185144177443985438743376373446634498619192128868891588498365323742249583

[出力例]

24593

■参照サイト
AtCoder Beginner Contest 164

2020年4月26日

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

C++の練習を兼ねて, AtCoder Regular Contest 004 の問題A (A – 2点間距離の最大値 ( The longest distance )) ～問題B (B – 2点間距離の最大と最小 ( Maximum and Minimum )) を解いてみた.

■感想.
1. 問題B は, 方針決まるまで時間かかったものの, 一番長い辺を固定すれば解けることに気付いたので, AC版となった.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

int main(){
    
    // 1. 入力情報.
    int N;
    double x, y;
    scanf("%d", &N);
    rep(i, N){
        scanf("%lf %lf", &x, &y);
        p[i] = {x, y};
    }
    
    // 2. 最も長くなる線分の長さは？
    double ans = 0.0;
    rep(i, N - 1) repx(j, i + 1, N) ans = max(ans, hypot(p[i].a - p[j].a, p[i].b - p[j].b));
    
    // 3. 出力.
    printf("%.12lf\n", ans);
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

#define a first

#define b second

pair<double, double> p[111];

int main(){

// 1. 入力情報.

int N;

double x, y;

scanf("%d", &N);

rep(i, N){

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

p[i] = {x, y};

}

// 2. 最も長くなる線分の長さは？

double ans = 0.0;

rep(i, N - 1) repx(j, i + 1, N) ans = max(ans, hypot(p[i].a - p[j].a, p[i].b - p[j].b));

// 3. 出力.

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

return 0;

}

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

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

※上記のプログラムだと以下のように出力される.
3.605551275464

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

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

※上記のプログラムだと以下のように出力される.
10.630145812735

[入力例]
4
0 0
0 100
100 0
100 100

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

※上記のプログラムだと以下のように出力される.
141.421356237310

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

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

※上記のプログラムだと以下のように出力される.
4.000000000000

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

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

※上記のプログラムだと以下のように出力される.
4.242640687119

[入力例]

1 1

2 4

4 3

[出力例]

3.605551

※AtCoderのテストケースより

※上記のプログラムだと以下のように出力される.

3.605551275464

[入力例]

1 8

4 0

3 7

2 4

5 9

9 1

6 2

0 2

8 6

7 8

[出力例]

10.630146

※AtCoderのテストケースより

※上記のプログラムだと以下のように出力される.

10.630145812735

[入力例]

0 0

0 100

100 0

100 100

[出力例]

141.421356

※AtCoderのテストケースより

※上記のプログラムだと以下のように出力される.

141.421356237310

[入力例]

3 0

1 0

0 0

4 0

2 0

[出力例]

4.000000

※AtCoderのテストケースより

※上記のプログラムだと以下のように出力される.

4.000000000000

[入力例]

2 2

0 0

1 1

3 3

[出力例]

4.242641

※AtCoderのテストケースより

※上記のプログラムだと以下のように出力される.

4.242640687119

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

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

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%d", &d[i]);
    
    // 2. sort.
    sort(d, d + N);
    
    // 3. 0番目, N番目の距離 で 取り得る値の最大, 最小は？
    // 3-1. 最大.
    int aMax = 0;
    rep(i, N) aMax += d[i];
    
    // 3-2. 最小.
    // ※ 一番長い辺を固定して考える.
    int aMin = d[N - 1] - (aMax - d[N - 1]);
    if(aMin < 0) aMin = 0;
    
    // 4. 出力.
    printf("%d\n%d\n", aMax, aMin);
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

int d[555];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

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

// 2. sort.

sort(d, d + N);

// 3. 0番目, N番目の距離で取り得る値の最大, 最小は？

// 3-1. 最大.

int aMax = 0;

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

// 3-2. 最小.

// ※ 一番長い辺を固定して考える.

int aMin = d[N - 1] - (aMax - d[N - 1]);

if(aMin < 0) aMin = 0;

// 4. 出力.

printf("%d\n%d\n", aMax, aMin);

return 0;

}

[入力例]
1
1024

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

[入力例]
3
3
4
5

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

[入力例]
2
512
512

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

[入力例]
3
4
8
1

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

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

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

[入力例]
5
10
12
30
32
100

[出力例]
184
16

[入力例]
10
6
7
8
8
7
9
10
10
12
111

[出力例]
188
34

[入力例]

1024

[出力例]

1024

※AtCoderのテストケースより

[入力例]

[出力例]

※AtCoderのテストケースより

[入力例]

512

[出力例]

1024

※AtCoderのテストケースより

[入力例]

[出力例]

※AtCoderのテストケースより

[入力例]

[出力例]

※AtCoderのテストケースより

[入力例]

100

[出力例]

184

[入力例]

111

[出力例]

188

■参照サイト
AtCoder Regular Contest 004

2020年4月25日

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

C++の練習を兼ねて, AtCoder Regular Contest 014 の問題C (C – 魂の還る場所) を解いてみた.

■感想.
1. 各色のボールが, 偶数個か奇数個かで, 最後に円筒に残るボールの数が決まることに気付いたので, AC版となった.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

int main(){
    
    // 1. 入力情報.
    int N;
    char c[101010];
    scanf("%d %s", &N, c);
    
    // 2. 各ボール(R, G, B)の個数は？
    int r = 0, g = 0, b = 0;
    rep(i, N){
        if(c[i] == 'R') r++;
        if(c[i] == 'G') g++;
        if(c[i] == 'B') b++;
    }
    
    // 3. 出力.
    printf("%d\n", (r % 2) + (g % 2) + (b % 2));
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

int main(){

// 1. 入力情報.

int N;

char c[101010];

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

// 2. 各ボール(R, G, B)の個数は？

int r = 0, g = 0, b = 0;

rep(i, N){

if(c[i] == 'R') r++;

if(c[i] == 'G') g++;

if(c[i] == 'B') b++;

}

// 3. 出力.

printf("%d\n", (r % 2) + (g % 2) + (b % 2));

return 0;

}

[入力例]
9
RGBGGBGBR

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

[入力例]
6
RGBRGB

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

[入力例]
30
BBBBRGGRRBRBBGGGBGGGRBRBRBGBGR

[出力例]
0

[入力例]
100
GBRRRGGRRGGBGRGGBRRGBRRBGBBGBGBGGRGBBRBBGBGGGRGGRBBRBBRGGRGRGBRRRGRRRBRRGGGRRRBGGGBRBGBBBBBRGGRBBRRB

[出力例]
2

[入力例]
500
GBGBGGRBRGGGGBGGRGBBRGGBGGBGGGGGGGBBGBGGRBGRBRGGRGBBRBRRGRBBBGGGBRGRBRRRRBGBRBBRRBRBBBRGBBGRBGRRRRGRGRBBBGRGBGGRGBBBBGRRRBBGGRBRBBRBBGRBGBBGGGRRBBBRGRBRBRGGBGRBRGBRBGRGGRRGRRGGRBGBGBGRGBBBGBRRRBBRBRBBBBRBGGRRRGRRBBRGGGGGGBBRBGGRBRGBGBBRGRBGRGRRRGRGRGGGRBGBRRGBGGGGRGRRBRRGBBGGRBRGRRBRRRGRRGBRBRRBRGRBBBGRRRBGGRBGBBBBBRBRRGBRGRRBBRGRRRGBBGGGGBGBBRBBBGBRGGRRGBRRGGGGGGBBBRBGGBRRRGGBBRBRRRRBRRRGRGBBBBRBBGRGGGBRRBBRRRGRRGRGGRGRRGGGRRGRRRGRGRBGGGBRBRGBGGBGRGGRGGGRGRRBRRBRRBGRRRBBRBBRRGRRGRRGBGGRGBBBGBRB

[出力例]
2

[入力例]

RGBGGBGBR

[出力例]

※AtCoderのテストケースより

[入力例]

RGBRGB

[出力例]

※AtCoderのテストケースより

[入力例]

BBBBRGGRRBRBBGGGBGGGRBRBRBGBGR

[出力例]

[入力例]

100

GBRRRGGRRGGBGRGGBRRGBRRBGBBGBGBGGRGBBRBBGBGGGRGGRBBRBBRGGRGRGBRRRGRRRBRRGGGRRRBGGGBRBGBBBBBRGGRBBRRB

[出力例]

[入力例]

500

GBGBGGRBRGGGGBGGRGBBRGGBGGBGGGGGGGBBGBGGRBGRBRGGRGBBRBRRGRBBBGGGBRGRBRRRRBGBRBBRRBRBBBRGBBGRBGRRRRGRGRBBBGRGBGGRGBBBBGRRRBBGGRBRBBRBBGRBGBBGGGRRBBBRGRBRBRGGBGRBRGBRBGRGGRRGRRGGRBGBGBGRGBBBGBRRRBBRBRBBBBRBGGRRRGRRBBRGGGGGGBBRBGGRBRGBGBBRGRBGRGRRRGRGRGGGRBGBRRGBGGGGRGRRBRRGBBGGRBRGRRBRRRGRRGBRBRRBRGRBBBGRRRBGGRBGBBBBBRBRRGBRGRRBBRGRRRGBBGGGGBGBBRBBBGBRGGRRGBRRGGGGGGBBBRBGGBRRRGGBBRBRRRRBRRRGRGBBBBRBBGRGGGBRRBBRRRGRRGRGGRGRRGGGRRGRRRGRGRBGGGBRBRGBGGBGRGGRGGGRGRRBRRBRRBGRRRBBRBBRRGRRGRRGBGGRGBBBGBRB

[出力例]

■参照サイト
AtCoder Regular Contest 014

2020年4月25日

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

C++の練習を兼ねて, AtCoder Regular Contest 014 の問題A (A – 君が望むなら世界中全てのたこ焼きを赤と青に染め上げよう) ～問題B (B – あの日したしりとりの結果を僕達はまだ知らない。) を解いてみた.

■感想.
1. 問題A は、与えられた数字の偶奇で, 分岐する方針で, AC版となった.
2. 問題Bは, 実装に, やや苦戦したものの, AC版となった.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    
    // 2. 出力.
    printf("%s\n", (N & 1) ? "Red" : "Blue");
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

// 2. 出力.

printf("%s\n", (N & 1) ? "Red" : "Blue");

return 0;

}

[入力例]
4

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

[入力例]
9

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

[入力例]
13

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

[入力例]

[出力例]

Blue

※AtCoderのテストケースより

[入力例]

[出力例]

Red

※AtCoderのテストケースより

[入力例]

[出力例]

Red

※AtCoderのテストケースより

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

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

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    
    // 2. しりとりを行う.
    map<string, int> m;
    int index = -1;
    string bef = "#";
    rep(i, N){
        // 今回分保存.
        char c[33];
        scanf("%s", c);
        string cur(c);
        
        // 前回以前に, すでに出現しているか確認.
        if(m.count(cur)){
            index = i + 1;
            break;
        }else{
            m[cur]++;
        }
        
        // 前回の単語の末尾と, 今回の単語の先頭を比較.
        if(bef != "#" && bef.back() != cur.front()){
            index = i + 1;
            break;
        }
        
        // 前回分保存.
        bef = cur;
    }
    
    // 3. 勝敗判定.
    string ans = "DRAW";
    if(index > 0) ans = (index & 1) ? "LOSE" : "WIN";
    
    // 4. 出力.
    printf("%s\n", ans.c_str());
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

// 2. しりとりを行う.

map<string, int> m;

int index = -1;

string bef = "#";

rep(i, N){

// 今回分保存.

char c[33];

scanf("%s", c);

string cur(c);

// 前回以前に, すでに出現しているか確認.

if(m.count(cur)){

index = i + 1;

break;

}else{

m[cur]++;

}

// 前回の単語の末尾と, 今回の単語の先頭を比較.

if(bef != "#" && bef.back() != cur.front()){

index = i + 1;

break;

}

// 前回分保存.

bef = cur;

}

// 3. 勝敗判定.

string ans = "DRAW";

if(index > 0) ans = (index & 1) ? "LOSE" : "WIN";

// 4. 出力.

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

return 0;

}

[入力例]
4
ab
ba
ab
cb

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

[入力例]
3
atcoder
redcoder
recorder

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

[入力例]
5
test
tree
examination
pass
stack

[出力例]
WIN

[入力例]
5
sine
logarithm
cosine
hyperbolic
cotangent

[出力例]
WIN

[入力例]
28
stack
kind
direction
negative
edge
efficient
third
dynamic
cosine
end
decode
extra
algebra
algorithm
map
pop
programming
graph
hash
head
deque
enqueue
euler
route
erase
equation
not
tuple

[出力例]
DRAW

[入力例]

[出力例]

LOSE

※AtCoderのテストケースより

[入力例]

atcoder

redcoder

recorder

[出力例]

DRAW

※AtCoderのテストケースより

[入力例]

test

tree

examination

pass

stack

[出力例]

WIN

[入力例]

sine

logarithm

cosine

hyperbolic

cotangent

[出力例]

WIN

[入力例]

stack

kind

direction

negative

edge

efficient

third

dynamic

cosine

end

decode

extra

algebra

algorithm

map

pop

programming

graph

hash

head

deque

enqueue

euler

route

erase

equation

not

tuple

[出力例]

DRAW

■参照サイト
AtCoder Regular Contest 014

2020年4月25日

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

C++の練習を兼ねて, AtCoder Regular Contest 013 の問題A (A – 梱包できるかな？) ～問題B (B – 引越しできるかな？) を解いてみた.

■感想.
1. 問題A は、6通りのパターンを見る方針で, AC版となった.
2. 問題Bは, 縦, 横, 高さを入れ替えて, 小さい方から並び替えた後に, 縦, 横, 高さのそれぞれの最大値から, 計算できることに気付いたので, AC版となった.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

int main(){
    
    // 1. 入力情報.
    int N, M, L, P, Q, R;
    scanf("%d %d %d %d %d %d", &N, &M, &L, &P, &Q, &R);
    
    // 2. ダンボールに詰め込むことができる荷物の数の最大値は？
    //                 (縦) (横) (高)
    // 段ボール          N    M    L
    // 荷物(パターン1)   P    Q    R
    // 荷物(パターン2)   P    R    Q
    // 荷物(パターン3)   Q    P    R
    // 荷物(パターン4)   Q    R    P
    // 荷物(パターン5)   R    P    Q
    // 荷物(パターン6)   R    Q    P
    int ans = 0;
    ans = max(ans, (N / P) * (M / Q) * (L / R));
    ans = max(ans, (N / P) * (M / R) * (L / Q));
    ans = max(ans, (N / Q) * (M / P) * (L / R));
    ans = max(ans, (N / Q) * (M / R) * (L / P));
    ans = max(ans, (N / R) * (M / P) * (L / Q));
    ans = max(ans, (N / R) * (M / Q) * (L / P));
    
    // 3. 出力.
    printf("%d\n", ans);
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

int main(){

// 1. 入力情報.

int N, M, L, P, Q, R;

scanf("%d %d %d %d %d %d", &N, &M, &L, &P, &Q, &R);

// 2. ダンボールに詰め込むことができる荷物の数の最大値は？

// (縦) (横) (高)

// 段ボール N M L

// 荷物(パターン1) P Q R

// 荷物(パターン2) P R Q

// 荷物(パターン3) Q P R

// 荷物(パターン4) Q R P

// 荷物(パターン5) R P Q

// 荷物(パターン6) R Q P

int ans = 0;

ans = max(ans, (N / P) * (M / Q) * (L / R));

ans = max(ans, (N / P) * (M / R) * (L / Q));

ans = max(ans, (N / Q) * (M / P) * (L / R));

ans = max(ans, (N / Q) * (M / R) * (L / P));

ans = max(ans, (N / R) * (M / P) * (L / Q));

ans = max(ans, (N / R) * (M / Q) * (L / P));

// 3. 出力.

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

return 0;

}

[入力例]
10 10 10
1 1 1

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

[入力例]
10 3 1
2 1 1

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

[入力例]
5 10 3
2 5 3

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

[入力例]
8 8 8
1 1 9

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

[入力例]
100 97 89
2 3 5

[出力例]
28160

[入力例]
314 159 265
3 5 9

[出力例]
95506

[入力例]

10 10 10

1 1 1

[出力例]

1000

※AtCoderのテストケースより

[入力例]

10 3 1

2 1 1

[出力例]

※AtCoderのテストケースより

[入力例]

5 10 3

2 5 3

[出力例]

※AtCoderのテストケースより

[入力例]

8 8 8

1 1 9

[出力例]

※AtCoderのテストケースより

[入力例]

100 97 89

2 3 5

[出力例]

28160

[入力例]

314 159 265

3 5 9

[出力例]

95506

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

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

int main(){
    
    // 1. 入力情報.
    int C, b[3], v[3];
    scanf("%d", &C);
    memset(v, 0, sizeof(v));
    rep(i, C){
        rep(j, 3) scanf("%d", &b[j]);
        sort(b, b + 3);
        rep(j, 3) v[j] = max(v[j], b[j]);
    }
    
    // 2. 出力.
    printf("%d\n", v[0] * v[1] * v[2]);
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

int main(){

// 1. 入力情報.

int C, b[3], v[3];

scanf("%d", &C);

memset(v, 0, sizeof(v));

rep(i, C){

rep(j, 3) scanf("%d", &b[j]);

sort(b, b + 3);

rep(j, 3) v[j] = max(v[j], b[j]);

}

// 2. 出力.

printf("%d\n", v[0] * v[1] * v[2]);

return 0;

}

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

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

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

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

[入力例]
4
10 20 30
20 20 20
30 20 10
10 40 10

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

[入力例]
2
10 10 10
11 1 1

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

[入力例]
100
57 31 72
58 70 68
62 33 39
57 7 26
56 55 47
58 13 48
47 40 27
29 32 12
25 45 18
37 21 17
40 38 25
43 27 67
59 48 78
9 30 4
54 30 77
24 38 48
1 33 16
52 63 32
32 51 77
44 49 22
74 3 7
49 44 23
22 20 27
39 80 26
40 45 65
45 68 22
62 14 46
51 49 41
55 25 13
77 53 50
12 34 50
6 64 63
6 68 47
4 19 66
25 68 29
3 28 71
30 23 70
7 59 31
8 53 54
58 29 8
41 52 3
76 69 20
45 69 67
71 62 59
63 26 22
3 19 29
6 13 74
77 24 36
79 56 47
67 9 17
55 23 14
15 46 31
20 12 49
77 4 21
60 22 63
31 37 77
71 59 16
33 50 64
19 10 34
73 4 1
35 42 33
38 67 17
32 27 12
7 3 30
64 28 10
75 73 62
8 66 39
75 47 53
70 74 31
14 18 1
12 9 57
68 59 8
39 50 17
63 56 60
56 20 55
76 63 39
69 77 52
23 1 15
21 48 17
47 1 68
4 79 31
52 7 51
55 72 58
3 23 80
20 11 4
10 71 12
18 11 31
72 63 26
31 51 15
68 55 16
43 20 4
74 59 20
50 17 22
22 52 18
19 75 77
30 16 67
30 72 71
49 7 11
52 15 56
41 66 41

[出力例]
372000

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

[入力例]

10 20 30

20 20 20

[出力例]

12000

※AtCoderのテストケースより

[入力例]

10 20 30

20 20 20

30 20 10

[出力例]

12000

※AtCoderのテストケースより

[入力例]

10 20 30

20 20 20

30 20 10

10 40 10

[出力例]

16000

※AtCoderのテストケースより

[入力例]

10 10 10

11 1 1

[出力例]

1100

※AtCoderのテストケースより

[入力例]

100

57 31 72

58 70 68

62 33 39

57 7 26

56 55 47

58 13 48

47 40 27

29 32 12

25 45 18

37 21 17

40 38 25

43 27 67

59 48 78

9 30 4

54 30 77

24 38 48

1 33 16

52 63 32

32 51 77

44 49 22

74 3 7

49 44 23

22 20 27

39 80 26

40 45 65

45 68 22

62 14 46

51 49 41

55 25 13

77 53 50

12 34 50

6 64 63

6 68 47

4 19 66

25 68 29

3 28 71

30 23 70

7 59 31

8 53 54

58 29 8

41 52 3

76 69 20

45 69 67

71 62 59

63 26 22

3 19 29

6 13 74

77 24 36

79 56 47

67 9 17

55 23 14

15 46 31

20 12 49

77 4 21

60 22 63

31 37 77

71 59 16

33 50 64

19 10 34

73 4 1

35 42 33

38 67 17

32 27 12

7 3 30

64 28 10

75 73 62

8 66 39

75 47 53

70 74 31

14 18 1

12 9 57

68 59 8

39 50 17

63 56 60

56 20 55

76 63 39

69 77 52

23 1 15

21 48 17

47 1 68

4 79 31

52 7 51

55 72 58

3 23 80

20 11 4

10 71 12

18 11 31

72 63 26

31 51 15

68 55 16

43 20 4

74 59 20

50 17 22

22 52 18

19 75 77

30 16 67

30 72 71

49 7 11

52 15 56

41 66 41

[出力例]

372000

■参照サイト
AtCoder Regular Contest 013

2020年4月24日

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

C++の練習を兼ねて, AtCoder Beginner Contest 051 の問題C (C – Back and Forth) を解いてみた.

■感想.
1. 個人的には, 非常に面白い問題と感じた.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

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

int main(){
    
    // 1. 入力情報.
    int sx, sy, tx, ty;
    scanf("%d %d %d %d", &sx, &sy, &tx, &ty);
    
    // 2. イルカの最短経路を一つ求める.
    // 2-1. 右方向: (tx - sx)回
    string ans = "";
    rep(i, tx - sx) ans.pb('R');
    
    // 2-2. 上方向: (ty - sy)回
    rep(i, ty - sy) ans.pb('U');
    
    // 2-3. 左方向: (tx - sx)回
    rep(i, tx - sx) ans.pb('L');
    
    // 2-4. 下方向: (ty - sy)回
    rep(i, ty - sy) ans.pb('D');
    
    // 2-5. 下方向: 1回
    ans.pb('D');
    
    // 2-6. 右方向: (tx - sx + 1)回
    rep(i, tx - sx + 1) ans.pb('R');
    
    // 2-7. 上方向: (ty - sy + 1)回
    rep(i, ty - sy + 1) ans.pb('U');
    
    // 2-8. 左方向: 1回
    ans.pb('L');
    
    // 2-8. 上方向: 1回
    ans.pb('U');
    
    // 2-9. 左方向: (tx - sx + 1)回
    rep(i, tx - sx + 1) ans.pb('L');
    
    // 2-10.下方向: (ty - sy + 1)回
    rep(i, ty - sy + 1) ans.pb('D');
    
    // 2-11.右方向: 1回
    ans.pb('R');
    
    // 3. 出力.
    printf("%s\n", ans.c_str());
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

#define pb push_back

int main(){

// 1. 入力情報.

int sx, sy, tx, ty;

scanf("%d %d %d %d", &sx, &sy, &tx, &ty);

// 2. イルカの最短経路を一つ求める.

// 2-1. 右方向: (tx - sx)回

string ans = "";

rep(i, tx - sx) ans.pb('R');

// 2-2. 上方向: (ty - sy)回

rep(i, ty - sy) ans.pb('U');

// 2-3. 左方向: (tx - sx)回

rep(i, tx - sx) ans.pb('L');

// 2-4. 下方向: (ty - sy)回

rep(i, ty - sy) ans.pb('D');

// 2-5. 下方向: 1回

ans.pb('D');

// 2-6. 右方向: (tx - sx + 1)回

rep(i, tx - sx + 1) ans.pb('R');

// 2-7. 上方向: (ty - sy + 1)回

rep(i, ty - sy + 1) ans.pb('U');

// 2-8. 左方向: 1回

ans.pb('L');

// 2-8. 上方向: 1回

ans.pb('U');

// 2-9. 左方向: (tx - sx + 1)回

rep(i, tx - sx + 1) ans.pb('L');

// 2-10.下方向: (ty - sy + 1)回

rep(i, ty - sy + 1) ans.pb('D');

// 2-11.右方向: 1回

ans.pb('R');

// 3. 出力.

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

return 0;

}

[入力例]
0 0 1 2

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

※上記のプログラムだと以下のように出力される.
RUULDDDRRUUULULLDDDR

[入力例]
-2 -2 1 1

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

※上記のプログラムだと以下のように出力される.
RRRUUULLLDDDDRRRRUUUULULLLLDDDDR

[入力例]
0 0 1 1

[出力例]
RULDDRRUULULLDDR

[入力例]
11 19 31 47

[出力例]
RRRRRRRRRRRRRRRRRRRRUUUUUUUUUUUUUUUUUUUUUUUUUUUULLLLLLLLLLLLLLLLLLLLDDDDDDDDDDDDDDDDDDDDDDDDDDDDDRRRRRRRRRRRRRRRRRRRRRUUUUUUUUUUUUUUUUUUUUUUUUUUUUULULLLLLLLLLLLLLLLLLLLLLDDDDDDDDDDDDDDDDDDDDDDDDDDDDDR

[入力例]
3 14 15 92

[出力例]
RRRRRRRRRRRRUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUULLLLLLLLLLLLDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDRRRRRRRRRRRRRUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUULULLLLLLLLLLLLLDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDR

[入力例]

0 0 1 2

[出力例]

UURDDLLUUURRDRDDDLLU

※AtCoderテストケースより

※上記のプログラムだと以下のように出力される.

RUULDDDRRUUULULLDDDR

[入力例]

-2 -2 1 1

[出力例]

UURRURRDDDLLDLLULUUURRURRDDDLLDL

※AtCoderテストケースより

※上記のプログラムだと以下のように出力される.

RRRUUULLLDDDDRRRRUUUULULLLLDDDDR

[入力例]

0 0 1 1

[出力例]

RULDDRRUULULLDDR

[入力例]

11 19 31 47

[出力例]

RRRRRRRRRRRRRRRRRRRRUUUUUUUUUUUUUUUUUUUUUUUUUUUULLLLLLLLLLLLLLLLLLLLDDDDDDDDDDDDDDDDDDDDDDDDDDDDDRRRRRRRRRRRRRRRRRRRRRUUUUUUUUUUUUUUUUUUUUUUUUUUUUULULLLLLLLLLLLLLLLLLLLLLDDDDDDDDDDDDDDDDDDDDDDDDDDDDDR

[入力例]

3 14 15 92

[出力例]

RRRRRRRRRRRRUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUULLLLLLLLLLLLDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDRRRRRRRRRRRRRUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUULULLLLLLLLLLLLLDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDR

■参照サイト
AtCoder Beginner Contest 051

C++の練習を兼ねて, AtCoder Regular Contest 026 の 問題C (C – 蛍光灯) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 027 の 問題A (A – 門限) ～ 問題B (B – 大事な数なのでZ回書きまLた。) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 026 の 問題A (A – ダイナミックなポーズ) ～ 問題B (B – 完全数) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 025 の 問題A (A – ゴールドラッシュ) ～ 問題B (B – チョコレート) を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 004 の 問題A (A – 2点間距離の最大値 ( The longest distance )) ～ 問題B (B – 2点間距離の最大と最小 ( Maximum and Minimum )) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 014 の 問題C (C – 魂の還る場所) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 014 の 問題A (A – 君が望むなら世界中全てのたこ焼きを赤と青に染め上げよう) ～ 問題B (B – あの日したしりとりの結果を僕達はまだ知らない。) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 013 の 問題A (A – 梱包できるかな？) ～ 問題B (B – 引越しできるかな？) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 051 の 問題C (C – Back and Forth) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 026 の問題C (C – 蛍光灯) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 027 の問題A (A – 門限) ～問題B (B – 大事な数なのでZ回書きまLた。) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 026 の問題A (A – ダイナミックなポーズ) ～問題B (B – 完全数) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 025 の問題A (A – ゴールドラッシュ) ～問題B (B – チョコレート) を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 004 の問題A (A – 2点間距離の最大値 ( The longest distance )) ～問題B (B – 2点間距離の最大と最小 ( Maximum and Minimum )) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 014 の問題C (C – 魂の還る場所) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 014 の問題A (A – 君が望むなら世界中全てのたこ焼きを赤と青に染め上げよう) ～問題B (B – あの日したしりとりの結果を僕達はまだ知らない。) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 013 の問題A (A – 梱包できるかな？) ～問題B (B – 引越しできるかな？) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 051 の問題C (C – Back and Forth) を解いてみた.