個人用メモ帳

2021年1月22日

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

C++の練習を兼ねて, AtCoder Regular Contest 072 の問題E (Alice in linear land) を解いてみた.

■感想.
1. 問題Eは, 方針が見えなかったので, 解説を参考に実装して, AC版に到達できたので, 良かったと思う.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/arc072/editorial.pdf
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
LL d[505050], A[505050], q[505050], B[505050];

int main(){
    
    // 1. 入力情報.
    int N;
    LL D;
    scanf("%d %lld", &N, &D);
    rep(i, N) scanf("%lld", &d[i]);
    
    // 2. 目的地(座標 D)までの距離を事前計算.
    // -> 最初は, 目的地までの距離は, D のはず.
    A[0] = D;
    LL bef = A[0] - D, cur = 0;
    repx(i, 1, N + 1){
        // 2-1. 現在地点から左向きに進んだ場合.
        LL l = bef - d[i - 1];
        
        // 2-2. 前回地点から右向きに進んだ場合.
        LL r = bef + d[i - 1];
        
        // 2-3. 座標 D までの距離を計算.
        LL d0 = abs(D - bef);
        LL d1 = abs(D - l);
        LL d2 = abs(D - r);
        
        // 2-4. 今回地点を更新.
        if(d0 <= d1){
            if(d0 <= d2) cur = bef;
            else         cur = r;
        }
        if(d0 <= d2){
            if(d0 <= d1) cur = bef;
            else         cur = l;
        }
        
        // 2-5. 前回地点の座標を更新.
        bef = cur;
        
        // 2-6. 目的地までの距離を更新.
        A[i] = min(abs(cur - D), abs(cur + D));
    }
    
    // 3. 計画情報を取得.
    int Q;
    scanf("%d", &Q);
    rep(i, Q) scanf("%d", &q[i]);
    
    // 4. 目的地に辿り着けない距離を計算.
    B[N] = 1;
    repr(i, N - 1, 0){
        B[i] = B[i + 1];
        if(B[i + 1] > d[i] / 2LL) B[i] += d[i];
    }
    
    // 5. クエリ回答.
    rep(i, Q) printf("%s\n", (A[q[i] - 1] >= B[q[i]]) ? "YES" : "NO");
    return 0;
    
}

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

LL d[505050], A[505050], q[505050], B[505050];

int main(){

// 1. 入力情報.

int N;

LL D;

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

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

// 2. 目的地(座標 D)までの距離を事前計算.

// -> 最初は, 目的地までの距離は, D のはず.

A[0] = D;

LL bef = A[0] - D, cur = 0;

repx(i, 1, N + 1){

// 2-1. 現在地点から左向きに進んだ場合.

LL l = bef - d[i - 1];

// 2-2. 前回地点から右向きに進んだ場合.

LL r = bef + d[i - 1];

// 2-3. 座標 D までの距離を計算.

LL d0 = abs(D - bef);

LL d1 = abs(D - l);

LL d2 = abs(D - r);

// 2-4. 今回地点を更新.

if(d0 <= d1){

if(d0 <= d2) cur = bef;

else cur = r;

}

if(d0 <= d2){

if(d0 <= d1) cur = bef;

else cur = l;

}

// 2-5. 前回地点の座標を更新.

bef = cur;

// 2-6. 目的地までの距離を更新.

A[i] = min(abs(cur - D), abs(cur + D));

}

// 3. 計画情報を取得.

int Q;

scanf("%d", &Q);

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

// 4. 目的地に辿り着けない距離を計算.

B[N] = 1;

repr(i, N - 1, 0){

B[i] = B[i + 1];

if(B[i + 1] > d[i] / 2LL) B[i] += d[i];

}

// 5. クエリ回答.

rep(i, Q) printf("%s\n", (A[q[i] - 1] >= B[q[i]]) ? "YES" : "NO");

return 0;

}

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

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

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

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

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

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

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

[出力例]
NO
NO
NO
NO
NO
NO
NO
YES
YES
YES
NO
YES
NO
YES
YES

[入力例]

4 10

3 4 3 3

4 3

[出力例]

YES

※AtCoderのテストケースより

[入力例]

5 9

4 4 2 3 2

1 4 2 3 5

[出力例]

YES

※AtCoderのテストケースより

[入力例]

6 15

4 3 5 4 2 1

1 2 3 4 5 6

[出力例]

YES

※AtCoderのテストケースより

[入力例]

20 77

12 13 13 8 8 12 13 3 2 11 1 5 8 5 14 10 7 14 6 11

8 5 19 15 9 16 8 7 2 6 4 7 14 3 11

[出力例]

YES

■参照サイト
AtCoder Regular Contest 072

2021年1月21日2021年1月21日

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

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

■感想.
1. 問題Dは, 方針が見えなかったので, 解説を参考に実装して, AC版に到達できたので, 良かったと思う.
2. 個人的には, 摩訶不思議な感じがして, 非常に面白いと感じた.
3. Union-Find木の復習が出来たので, 非常に良かったと思う.
※ 公式のライブラリを拝借させて頂いてます.
4. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/arc097/editorial.pdf
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
int p[101010];

// https://github.com/atcoder/live_library/blob/master/uf.cpp
// UnionFind
// coding: https://youtu.be/TdR816rqc3s?t=726
// comment: https://youtu.be/TdR816rqc3s?t=6822
// -> 一部改変.
struct UnionFind{
    vector<int> d;
    UnionFind(int n = 0): d(n, -1) {}
    int find(int x){
        return (d[x] < 0) ? x : (d[x] = find(d[x]));
    }
    bool unite(int x, int y){
        x = find(x);
        y = find(y);
        if(x == y) return false;
        if(d[x] > d[y]) swap(x, y);
        d[x] += d[y];
        d[y] = x;
        return true;
    }
    bool same(int x, int y){
        return find(x) == find(y);
    }
    int size(int x){
        return -d[find(x)];
    }
};

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    rep(i, N){
        scanf("%d", &p[i]);
        p[i]--;
    }
    
    // 2. UnionFind木 に, 辺 を 登録.
    UnionFind uf(N);
    rep(i, M){
        // 2-1. 辺を取得.
        int x, y;
        scanf("%d %d", &x, &y);
        x--, y--;
        
        // 2-2. グラフに辺を登録.
        uf.unite(x, y);
    }
    
    // 3. i と p[i] が 同じ連結成分にあるか？
    int ans = 0;
    rep(i, N) if(uf.same(i, p[i])) ans++;
    
    // 4. 出力.
    printf("%d\n", ans);
    return 0;
    
}

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

int p[101010];

// https://github.com/atcoder/live_library/blob/master/uf.cpp

// UnionFind

// coding: https://youtu.be/TdR816rqc3s?t=726

// comment: https://youtu.be/TdR816rqc3s?t=6822

// -> 一部改変.

struct UnionFind{

vector<int> d;

UnionFind(int n = 0): d(n, -1) {}

int find(int x){

return (d[x] < 0) ? x : (d[x] = find(d[x]));

}

bool unite(int x, int y){

x = find(x);

y = find(y);

if(x == y) return false;

if(d[x] > d[y]) swap(x, y);

d[x] += d[y];

d[y] = x;

return true;

}

bool same(int x, int y){

return find(x) == find(y);

}

int size(int x){

return -d[find(x)];

}

};

int main(){

// 1. 入力情報.

int N, M;

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

rep(i, N){

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

p[i]--;

}

// 2. UnionFind木に, 辺を登録.

UnionFind uf(N);

rep(i, M){

// 2-1. 辺を取得.

int x, y;

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

x--, y--;

// 2-2. グラフに辺を登録.

uf.unite(x, y);

}

// 3. i と p[i] が同じ連結成分にあるか？

int ans = 0;

rep(i, N) if(uf.same(i, p[i])) ans++;

// 4. 出力.

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

return 0;

}

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

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

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

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

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

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

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

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

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

[出力例]
3
※実際, {1, 3, 4}, {2, 5, 6, 7, 11}, {8, 9, 10, 15}, {12}, {13, 14} と 連結成分に分割され,
{i, p[i]} = {5, 7}, {7, 2}, {12, 12} の 3つの組み合わせがカウントされることが分かる.

[入力例]

5 2

5 3 1 4 2

1 3

5 4

[出力例]

※AtCoderテストケースより

[入力例]

3 2

3 2 1

1 2

2 3

[出力例]

※AtCoderテストケースより

[入力例]

10 8

5 3 6 8 7 10 9 1 2 4

3 1

4 1

5 9

2 5

6 5

3 5

8 9

7 9

[出力例]

※AtCoderテストケースより

[入力例]

5 1

1 2 3 4 5

1 5

[出力例]

※AtCoderテストケースより

[入力例]

15 10

15 13 9 8 7 3 2 1 6 5 4 12 11 10 14

3 1

4 1

5 2

6 2

6 7

8 9

10 9

11 2

15 9

13 14

[出力例]

※実際, {1, 3, 4}, {2, 5, 6, 7, 11}, {8, 9, 10, 15}, {12}, {13, 14} と連結成分に分割され,

{i, p[i]} = {5, 7}, {7, 2}, {12, 12} の 3つの組み合わせがカウントされることが分かる.

■参照サイト
AtCoder Regular Contest 097
Union-Find木

2021年1月20日

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

C++の練習を兼ねて, AtCoder Regular Contest 098 の問題E (Range Minimum Queries) を解いてみた.

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

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

// 解き直し.
// https://img.atcoder.jp/arc098/editorial.pdf
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using PQ = priority_queue<int, vector<int>, greater<int>>;
using vpq = vector<PQ>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
int a[2020];

int main(){
    
    // 1. 入力情報.
    int N, K, Q;
    scanf("%d %d %d", &N, &K, &Q);
    rep(i, N) scanf("%d", &a[i]);
    
    // 2. 最小値 X を 固定して 最大値 Y を チェック.
    int ans = 2020202020;
    rep(i, N){
        // 2-1. 最小値 X を 設定.
        int X = a[i];
        
        // 2-2. 数列の分割.
        vpq vPQ;
        PQ pq;
        rep(j, N + 1){
            // i, j が 等しい場合も含めるようにする.
            if(X <= a[j]){
                pq.push(a[j]);
            }else{
                if(pq.size()) vPQ.pb(pq), pq = {};
            }
        }
        
        // 2-3. 分割後の各数列について, 数列のサイズを, m とした場合に, 
        // 小さい方から, 最大(m - K + 1)個まで抽出.
        pq = {};
        rep(j, vPQ.size()){
            int idx = vPQ[j].size() - K + 1;
            while(!vPQ[j].empty() && idx > 0){
                // 数列の要素を取得.
                int y = vPQ[j].top();
                vPQ[j].pop();
                
                // 最大値 Y の 候補 を 追加.
                pq.push(y);
                
                // デクリメント.
                idx--;
            }
        }
        
        // 2-4. Q番目 に 小さいものを取得.
        int Y = -1, qIdx = Q;
        while(!pq.empty() && qIdx > 0){
            // Y を 更新.
            Y = pq.top();
            pq.pop();
            
            // デクリメント.
            qIdx--;
        };
        
        // 2-5. Y - X の 最小値 を 更新.
        if(!qIdx && Y != -1) ans = min(ans, Y - X);
    }
    
    // 3. 出力.
    printf("%d\n", ans);
    return 0;
    
}

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using PQ = priority_queue<int, vector<int>, greater<int>>;

using vpq = vector<PQ>;

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

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

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

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

#define pb push_back

int a[2020];

int main(){

// 1. 入力情報.

int N, K, Q;

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

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

// 2. 最小値 X を固定して最大値 Y をチェック.

int ans = 2020202020;

rep(i, N){

// 2-1. 最小値 X を設定.

int X = a[i];

// 2-2. 数列の分割.

vpq vPQ;

PQ pq;

rep(j, N + 1){

// i, j が等しい場合も含めるようにする.

if(X <= a[j]){

pq.push(a[j]);

}else{

if(pq.size()) vPQ.pb(pq), pq = {};

}

// 2-3. 分割後の各数列について, 数列のサイズを, m とした場合に,

// 小さい方から, 最大(m - K + 1)個まで抽出.

pq = {};

rep(j, vPQ.size()){

int idx = vPQ[j].size() - K + 1;

while(!vPQ[j].empty() && idx > 0){

// 数列の要素を取得.

int y = vPQ[j].top();

vPQ[j].pop();

// 最大値 Y の候補を追加.

pq.push(y);

// デクリメント.

idx--;

}

// 2-4. Q番目に小さいものを取得.

int Y = -1, qIdx = Q;

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

// Y を更新.

Y = pq.top();

pq.pop();

// デクリメント.

qIdx--;

};

// 2-5. Y - X の最小値を更新.

if(!qIdx && Y != -1) ans = min(ans, Y - X);

}

// 3. 出力.

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

return 0;

}

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

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

[入力例]
10 1 6
1 1 2 3 5 8 13 21 34 55

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

[入力例]
11 7 5
24979445 861648772 623690081 433933447 476190629 262703497 211047202 971407775 628894325 731963982 822804784

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

[入力例]
30 7 12
13 8 7 3 14 11 13 5 7 15 1 6 12 15 14 11 2 3 13 6 4 7 15 3 11 10 7 12 14 10

[出力例]
5

[入力例]
100 11 22
10 57 60 48 16 11 102 62 71 23 20 80 23 29 25 40 49 103 90 61 123 39 104 41 58 122 41 59 115 75 83 25 121 101 87 4 87 72 110 8 31 78 42 120 56 46 88 55 85 69 37 41 63 76 52 106 118 27 8 114 33 73 6 8 27 95 63 52 88 98 28 8 103 95 38 52 36 123 72 37 53 47 25 89 12 22 53 39 80 35 44 56 107 72 109 39 43 102 91 76

[出力例]
23

[入力例]

5 3 2

4 3 1 5 2

[出力例]

※AtCoderテストケースより

[入力例]

10 1 6

1 1 2 3 5 8 13 21 34 55

[出力例]

※AtCoderテストケースより

[入力例]

11 7 5

24979445 861648772 623690081 433933447 476190629 262703497 211047202 971407775 628894325 731963982 822804784

[出力例]

451211184

※AtCoderテストケースより

[入力例]

30 7 12

13 8 7 3 14 11 13 5 7 15 1 6 12 15 14 11 2 3 13 6 4 7 15 3 11 10 7 12 14 10

[出力例]

[入力例]

100 11 22

10 57 60 48 16 11 102 62 71 23 20 80 23 29 25 40 49 103 90 61 123 39 104 41 58 122 41 59 115 75 83 25 121 101 87 4 87 72 110 8 31 78 42 120 56 46 88 55 85 69 37 41 63 76 52 106 118 27 8 114 33 73 6 8 27 95 63 52 88 98 28 8 103 95 38 52 36 123 72 37 53 47 25 89 12 22 53 39 80 35 44 56 107 72 109 39 43 102 91 76

[出力例]

■参照サイト
AtCoder Regular Contest 098

2021年1月19日

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

C++の練習を兼ねて, AtCoder Regular Contest 111 の問題E (Simple Math 3) を解いてみた.

■感想.
1. 問題Eは, 方針が見えなかったので, 解説を参考に実装して, AC版に到達できたので, 良かったと思う.
2. 下記のライブラリを拝借させて頂いた.
※ 公式のライブラリを拝借させて頂いてます.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

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

// AtCoder Library(https://github.com/atcoder/ac-library/blob/master/atcoder/math.hpp)
// -> 一部改変(2021/01/19).
LL floor_sum(LL n, LL m, LL a, LL b){
    LL ans = 0;
    if(a >= m){
        ans += (n - 1) * n * (a / m) / 2;
        a %= m;
    }
    if(b >= m){
        ans += n * (b / m);
        b %= m;
    }
    LL y_max = (a * n + b) / m, x_max = (y_max * m - b);
    if(y_max == 0) return ans;
    ans += (n - (x_max + a - 1) / a) * y_max;
    ans += floor_sum(y_max, a, m, (a - x_max % a) % a);
    return ans;
}

int main(){
    
    // 1. 入力情報.
    int T;
    scanf("%d", &T);
    
    // 2. クエリ回答.
    rep(i, T){
        // 2-1. 数式の構成要素を取得.
        LL A, B, C, D;
        scanf("%lld %lld %lld %lld", &A, &B, &C, &D);
        
        // 2-2. K を 計算.
        LL K = (D - 2) / (C - B);
        
        // 2-3. 与式の各項を計算.
        LL acd = floor_sum(K + 1, D, C, A);
        LL abd = floor_sum(K + 1, D, B, A - 1);
        LL ans = K - acd + abd;
        
        // 2-4. 出力.
        printf("%lld\n", ans);
    }
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc111/editorial/494

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

// AtCoder Library(https://github.com/atcoder/ac-library/blob/master/atcoder/math.hpp)

// -> 一部改変(2021/01/19).

LL floor_sum(LL n, LL m, LL a, LL b){

LL ans = 0;

if(a >= m){

ans += (n - 1) * n * (a / m) / 2;

a %= m;

}

if(b >= m){

ans += n * (b / m);

b %= m;

}

LL y_max = (a * n + b) / m, x_max = (y_max * m - b);

if(y_max == 0) return ans;

ans += (n - (x_max + a - 1) / a) * y_max;

ans += floor_sum(y_max, a, m, (a - x_max % a) % a);

return ans;

}

int main(){

// 1. 入力情報.

int T;

scanf("%d", &T);

// 2. クエリ回答.

rep(i, T){

// 2-1. 数式の構成要素を取得.

LL A, B, C, D;

scanf("%lld %lld %lld %lld", &A, &B, &C, &D);

// 2-2. K を計算.

LL K = (D - 2) / (C - B);

// 2-3. 与式の各項を計算.

LL acd = floor_sum(K + 1, D, C, A);

LL abd = floor_sum(K + 1, D, B, A - 1);

LL ans = K - acd + abd;

// 2-4. 出力.

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

}

return 0;

}

[入力例]
2
3 1 2 5
99 101 103 105

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

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

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

[入力例]
30
15 61 117 191
20 58 139 151
101 107 205 269
93 54 103 121
33 48 68 166
105 50 172 275
40 7 88 140
89 7 79 145
111 14 51 156
26 115 168 280
84 32 33 89
39 29 86 135
107 51 174 227
56 82 194 290
32 120 156 167
13 107 181 214
62 110 114 175
71 85 124 233
68 120 204 215
26 120 222 335
94 79 102 216
15 14 22 114
75 35 82 115
12 98 217 280
24 116 239 268
10 9 106 144
96 4 62 152
65 17 43 106
116 39 48 117
112 60 153 273

[出力例]
2
0
1
1
3
0
1
0
0
2
43
1
0
1
2
2
21
4
0
1
4
6
0
1
1
1
0
1
4
1

100

101

102

103

104

105

106

107

108

109

[入力例]

3 1 2 5

99 101 103 105

[出力例]

※AtCoderのテストケースより

[入力例]

3 8 11 13

1 3 9 12

5 1 7 8

6 9 20 22

3 6 15 23

4 4 16 17

12 11 22 32

12 1 10 18

6 7 19 26

12 11 19 20

3 9 15 20

3 11 18 25

2 4 10 17

1 4 7 8

2 9 11 17

[出力例]

[入力例]

15 61 117 191

20 58 139 151

101 107 205 269

93 54 103 121

33 48 68 166

105 50 172 275

40 7 88 140

89 7 79 145

111 14 51 156

26 115 168 280

84 32 33 89

39 29 86 135

107 51 174 227

56 82 194 290

32 120 156 167

13 107 181 214

62 110 114 175

71 85 124 233

68 120 204 215

26 120 222 335

94 79 102 216

15 14 22 114

75 35 82 115

12 98 217 280

24 116 239 268

10 9 106 144

96 4 62 152

65 17 43 106

116 39 48 117

112 60 153 273

[出力例]

■参照サイト
AtCoder Regular Contest 111
ac-library/atcoder/math.hpp

2021年1月18日

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

C++の練習を兼ねて, AtCoder Regular Contest 068 の問題E (Snuke Line) を解いてみた.

■感想.
1. 問題Eは, 方針が見えなかったので, 解説を参考に実装して, AC版に到達できたので, 良かったと思う.
2. 遅延評価セグメント木が必要なため, 下記のライブラリを拝借させて頂いた.
3. 遅延評価セグメント木が復習できたので, 非常に良かったと思う.
4. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/arc068/editorial.pdf
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;
using vi = vector<int>;
using vp = vector<P>;
using vvp = vector<vp>;
#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
int l[303030], r[303030], iCum[101010];

// ※※※ 以下のライブラリを使用(一部改変) ※※※.
// 遅延評価セグメント木をソラで書きたいあなたに.
// 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;
    vi node, lazy;
public:
    LazySegmentTree(vi v){
        int sz = (int)v.size();
        n = 1; while(n < sz) n *= 2;
        node.resize(2 * n - 1);
        lazy.resize(2 * n - 1, 0);
        rep(i, sz) node[i + n - 1] = v[i];
        repr(i, n - 2, 0) node[i] = node[i * 2 + 1] + node[i * 2 + 2];
    }
    void eval(int k, int l, int r){
        if(lazy[k] != 0) {
            node[k] += lazy[k];
            if(r - l > 1) {
                lazy[2 * k + 1] += lazy[k] / 2;
                lazy[2 * k + 2] += lazy[k] / 2;
            }
            lazy[k] = 0;
        }
    }
    void update(int a, int b, int x, int k = 0, int l = 0, int r = -1){
        if(r < 0) r = n;
        eval(k, l, r);
        if(b <= l || r <= a) return;
        if(a <= l && r <= b){
            lazy[k] += (r - l) * x;
            eval(k, l, r);
        }else{
            update(a, b, x, 2 * k + 1,           l, (l + r) / 2);
            update(a, b, x, 2 * k + 2, (l + r) / 2,           r);
            node[k] = node[2 * k + 1] + node[2 * k + 2];
        }
    }
    int query(int a, int b, int k = 0, int l = 0, int r = -1){
        if(r < 0) r = n;
        eval(k, l, r);
        if(b <= l || r <= a) return 0;
        if(a <= l && r <= b) return node[k];
        int vl = query(a, b, 2 * k + 1,           l, (l + r) / 2);
        int vr = query(a, b, 2 * k + 2, (l + r) / 2,           r);
        return vl + vr;
    }

};

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    set<int> st;
    rep(i, N){
        scanf("%d %d", &l[i], &r[i]);
        int d = r[i] - l[i] + 1;
        st.insert(d); // 区間幅の種類を保存.
        iCum[d]++;    // 区間幅の個数を保存.
    }
    
    // 2. 区間幅に, indexを割り当て.
    int idx = -1;
    map<int, int> m;
    for(auto &p : st) m[p] = ++idx;
    
    // 3. 区間を長さごとに分類.
    vvp v(idx + 1);
    rep(i, N){
        int d = r[i] - l[i] + 1;
        v[m[d]].pb({l[i], r[i]});
    }
    
    // 4. 累積和.
    rep(i, M) iCum[i + 1] += iCum[i];
    
    // 5. 各間隔 d について, 購入可能な名産品の種類数を計算.
    // 解説上, Binary Indexed Tree (Fenwick Tree) を使う方針が示されていたが, 
    // 実装方法が見えなかったので, LazySegmentTree による実装で対応した.
    LazySegmentTree seg(vi(M + 1, 0));
    int k = 0;
    repx(d, 1, M + 1){
        // 5-1. 必ず, 1回以上訪問する区間.
        int ans = iCum[M] - iCum[d];
        
        // 5-2. 最大でも, 1回しか訪問できない区間.
        if(k <= idx && v[k][0].b - v[k][0].a + 1 <= d){
            // 区間への加算.
            rep(i, v[k].size()) seg.update(v[k][i].a, v[k][i].b + 1, 1);
            
            // インクリメント.
            k++;
        }
        
        // 5-3. 駅番号 が dの倍数 における 種類数 を カウント.
        repex(i, d, M + 1, d) ans += seg.query(i, i + 1);
        
        // 5-4. 出力.
        printf("%d\n", ans);
    }
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using P = pair<int, int>;

using vi = vector<int>;

using vp = vector<P>;

using vvp = vector<vp>;

#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

int l[303030], r[303030], iCum[101010];

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

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

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

vi node, lazy;

public:

LazySegmentTree(vi v){

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

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

node.resize(2 * n - 1);

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

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

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

}

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

if(lazy[k] != 0) {

node[k] += lazy[k];

if(r - l > 1) {

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

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

}

lazy[k] = 0;

}

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

if(r < 0) r = n;

eval(k, l, r);

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

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

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

eval(k, l, r);

}else{

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

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

node[k] = node[2 * k + 1] + node[2 * k + 2];

}

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

if(r < 0) r = n;

eval(k, l, r);

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

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

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

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

return vl + vr;

}

};

int main(){

// 1. 入力情報.

int N, M;

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

set<int> st;

rep(i, N){

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

int d = r[i] - l[i] + 1;

st.insert(d); // 区間幅の種類を保存.

iCum[d]++; // 区間幅の個数を保存.

}

// 2. 区間幅に, indexを割り当て.

int idx = -1;

map<int, int> m;

for(auto &p : st) m[p] = ++idx;

// 3. 区間を長さごとに分類.

vvp v(idx + 1);

rep(i, N){

int d = r[i] - l[i] + 1;

v[m[d]].pb({l[i], r[i]});

}

// 4. 累積和.

rep(i, M) iCum[i + 1] += iCum[i];

// 5. 各間隔 d について, 購入可能な名産品の種類数を計算.

// 解説上, Binary Indexed Tree (Fenwick Tree) を使う方針が示されていたが,

// 実装方法が見えなかったので, LazySegmentTree による実装で対応した.

LazySegmentTree seg(vi(M + 1, 0));

int k = 0;

repx(d, 1, M + 1){

// 5-1. 必ず, 1回以上訪問する区間.

int ans = iCum[M] - iCum[d];

// 5-2. 最大でも, 1回しか訪問できない区間.

if(k <= idx && v[k][0].b - v[k][0].a + 1 <= d){

// 区間への加算.

rep(i, v[k].size()) seg.update(v[k][i].a, v[k][i].b + 1, 1);

// インクリメント.

k++;

}

// 5-3. 駅番号が dの倍数における種類数をカウント.

repex(i, d, M + 1, d) ans += seg.query(i, i + 1);

// 5-4. 出力.

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

}

return 0;

}

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

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

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

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

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

[出力例]
15
15
14
14
11
12
7
5
3
5
7
7
6
3
2

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

[出力例]
33
33
33
30
28
25
19
16
17
20
19
15
9
4
3
2
2
2
1

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

[入力例]

3 3

1 2

2 3

3 3

[出力例]

※AtCoderのテストケースより

[入力例]

7 9

1 7

5 9

5 7

5 9

1 1

6 8

3 4

[出力例]

※AtCoderのテストケースより

[入力例]

15 15

2 5

3 8

10 15

1 3

11 15

3 6

8 13

10 12

4 5

10 13

6 8

11 14

4 9

11 13

6 10

[出力例]

[入力例]

33 19

9 13

2 4

1 5

7 12

5 13

10 12

10 19

9 11

4 7

11 12

4 8

6 13

11 13

9 13

2 8

7 12

10 18

3 11

10 12

1 4

9 11

2 10

7 14

8 15

3 4

1 8

4 7

10 12

3 5

5 7

3 11

6 10

7 10

[出力例]

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

2021年1月17日2021年1月17日

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

C++の練習を兼ねて, AtCoder Regular Contest 038 の問題A (カードと兄妹) ～問題B (マス目と駒) を解いてみた.

■感想.
1. 問題Bは, 方針が見えなかったので, 解説を参考に実装して, AC版に到達できたので, 良かったと思う.
2. メモ化再帰の復習が出来たので, 非常に良かったと思う.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

■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 a[1010];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%d", &a[i]);
    
    // 2. sort.
    sort(a, a + N, greater<int>());
    
    // 3. スコアを計算.
    int ans = 0;
    rep(i, N) if(i % 2 == 0) ans += a[i];
    
    // 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 a[1010];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

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

// 2. sort.

sort(a, a + N, greater<int>());

// 3. スコアを計算.

int ans = 0;

rep(i, N) if(i % 2 == 0) ans += a[i];

// 4. 出力.

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

return 0;

}

[入力例]
2
400 628

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

[入力例]
5
2 5 9 6 5

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

[入力例]

400 628

[出力例]

628

※AtCoderのテストケースより

[入力例]

2 5 9 6 5

[出力例]

※AtCoderのテストケースより

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

// 解き直し.
// https://www.slideshare.net/chokudai/arc038
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
int board[111][111], memo[111][111];

int main(){
    
    // 1. 入力情報.
    int H, W;
    scanf("%d %d", &H, &W);
    rep(i, H){
        char c[111];
        scanf("%s", c);
        // 障害物設定.
        rep(j, W) if(c[j] == '#') board[i][j] = 1;
    }
    
    // 2. 勝敗判定.
    // -> 0: 負け, 1: 勝ち, 2: 未定.
    auto dfs = [&](auto&& self, int x, int y) -> int{
        // 2-1. 盤外 の 場合.
        if(x < 0 || y < 0 || x >= H || y >= W) return 1;
        
        // 2-2. 障害物 の 場合.
        if(board[x][y]) return 1;
        
        // 2-3. 探索済み の 場合.
        if(memo[x][y] < 2) return memo[x][y];
        
        // 2-4. マスの移動と勝敗確定.
        int ret = 0;
        if(self(self, x + 1, y + 0) == 0) ret = 1; // 下.
        if(self(self, x + 1, y + 1) == 0) ret = 1; // 右下.
        if(self(self, x + 0, y + 1) == 0) ret = 1; // 右.
        
        // 2-5. メモ化及び返却.
        memo[x][y] = ret;
        return ret;
    };
    
    // 3. マス(i, j) の 勝敗を設定.
    rep(i, 111) rep(j, 111) memo[i][j] = 2;
    rep(i, H) rep(j, W) dfs(dfs, i, j);
    
    // 4. 出力.
    printf("%s\n", (memo[0][0] == 1) ? "First" : "Second");
    return 0;
    
}

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

int board[111][111], memo[111][111];

int main(){

// 1. 入力情報.

int H, W;

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

rep(i, H){

char c[111];

scanf("%s", c);

// 障害物設定.

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

}

// 2. 勝敗判定.

// -> 0: 負け, 1: 勝ち, 2: 未定.

auto dfs = [&](auto&& self, int x, int y) -> int{

// 2-1. 盤外の場合.

if(x < 0 || y < 0 || x >= H || y >= W) return 1;

// 2-2. 障害物の場合.

if(board[x][y]) return 1;

// 2-3. 探索済みの場合.

if(memo[x][y] < 2) return memo[x][y];

// 2-4. マスの移動と勝敗確定.

int ret = 0;

if(self(self, x + 1, y + 0) == 0) ret = 1; // 下.

if(self(self, x + 1, y + 1) == 0) ret = 1; // 右下.

if(self(self, x + 0, y + 1) == 0) ret = 1; // 右.

// 2-5. メモ化及び返却.

memo[x][y] = ret;

return ret;

};

// 3. マス(i, j) の勝敗を設定.

rep(i, 111) rep(j, 111) memo[i][j] = 2;

rep(i, H) rep(j, W) dfs(dfs, i, j);

// 4. 出力.

printf("%s\n", (memo[0][0] == 1) ? "First" : "Second");

return 0;

}

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

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

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

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

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

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


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

[出力例]
Second

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

[出力例]
First

[入力例]

2 3

.#.

...

[出力例]

First

※AtCoderのテストケースより

[入力例]

4 4

....

...#

....

.#..

[出力例]

Second

※AtCoderのテストケースより

[入力例]

11 44

............................................

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

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

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

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

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

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

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

............................................

[出力例]

Second

※AtCoderのテストケースより

[入力例]

8 9

.....#...

..#.#....

..##.....

.#..###..

.#.#...#.

...####..

.....#..#

..#......

[出力例]

Second

[入力例]

11 52

....................................................

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

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

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

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

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

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

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

....................................................

[出力例]

First

■参照サイト
AtCoder Regular Contest 038

2021年1月17日

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

C++の練習を兼ねて, AtCoder Regular Contest 045 の問題A (スペース高橋君) ～問題B (ドキドキデート大作戦高橋君) を解いてみた.

■感想.
1. 久しぶりに, 解説確認前に, AC版に到達できたので, 良かったと思う..
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

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

int main(){
    
    // 1. 入力情報.
    char c[1010];
    scanf("%[a-zA-Z@ ]", c);
    string S(c);
    // printf("%s\n", S.c_str());
    
    // 2. スペースで分割.
    int l = S.size();
    vector<string> T;
    string s;
    rep(i, l){
        if(S[i] == ' '){
            T.pb(s);
            s = "";
        }else{
            s.pb(S[i]);
        }
    }
    if(s.size() > 0) T.pb(s);
    
    
    // 3. 出力.
    int tl = T.size();
    rep(i, tl){
        if(T[i] == "Left") printf("<");
        if(T[i] == "Right") printf(">");
        if(T[i] == "AtCoder") printf("A");
        if(i < tl - 1) printf(" ");
    }
    puts("");
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

#define pb push_back

int main(){

// 1. 入力情報.

char c[1010];

scanf("%[a-zA-Z@ ]", c);

string S(c);

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

// 2. スペースで分割.

int l = S.size();

vector<string> T;

string s;

rep(i, l){

if(S[i] == ' '){

T.pb(s);

s = "";

}else{

s.pb(S[i]);

}

if(s.size() > 0) T.pb(s);

// 3. 出力.

int tl = T.size();

rep(i, tl){

if(T[i] == "Left") printf("<");

if(T[i] == "Right") printf(">");

if(T[i] == "AtCoder") printf("A");

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

}

puts("");

return 0;

}

[入力例]
Left Right AtCoder

[出力例]
< > A
※AtCoderのテストケースより

[入力例]
Left Left Right Right AtCoder

[出力例]
< < > > A
※AtCoderのテストケースより

[入力例]
Right Right AtCoder Left Left AtCoder

[出力例]
> > A < < A
※AtCoderのテストケースより

[入力例]

Left Right AtCoder

[出力例]

< > A

※AtCoderのテストケースより

[入力例]

Left Left Right Right AtCoder

[出力例]

< < > > A

※AtCoderのテストケースより

[入力例]

Right Right AtCoder Left Left AtCoder

[出力例]

> > A < < A

※AtCoderのテストケースより

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;
using vp = vector<P>;
using vi = vector<int>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
#define a first
#define b second
int a[303030], b[303030];

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    vp v;
    rep(i, M){
        int s, t;
        scanf("%d %d", &s, &t);
        s--;
        a[s]++;
        a[t]--;
        v.pb({s, t});
    }
    
    // 2. いもす法.
    rep(i, N + 1) a[i + 1] += a[i];
    
    // 3. 掃除区間を整理(累積和).
    rep(i, N + 1) if(a[i] >= 2) b[i + 1] = 1; // 指定された教室が, 2個以上の区間に含まれる.
    rep(i, N + 1) b[i + 1] += b[i];
    
    // 4. サボってもバレない掃除区間を抽出.
    vi ans;
    rep(i, M){
        int d = v[i].b - v[i].a;
        if(b[v[i].b] - b[v[i].a] == d) ans.pb(i + 1);
    }
    
    // 5. 出力.
    printf("%d\n", ans.size());
    for(auto &p : ans) printf("%d\n", p);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using P = pair<int, int>;

using vp = vector<P>;

using vi = vector<int>;

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

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

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

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

#define pb push_back

#define a first

#define b second

int a[303030], b[303030];

int main(){

// 1. 入力情報.

int N, M;

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

vp v;

rep(i, M){

int s, t;

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

s--;

a[s]++;

a[t]--;

v.pb({s, t});

}

// 2. いもす法.

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

// 3. 掃除区間を整理(累積和).

rep(i, N + 1) if(a[i] >= 2) b[i + 1] = 1; // 指定された教室が, 2個以上の区間に含まれる.

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

// 4. サボってもバレない掃除区間を抽出.

vi ans;

rep(i, M){

int d = v[i].b - v[i].a;

if(b[v[i].b] - b[v[i].a] == d) ans.pb(i + 1);

}

// 5. 出力.

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

for(auto &p : ans) printf("%d\n", p);

return 0;

}

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

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

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

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

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

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

[入力例]
30 11
1 5
5 10
10 13
13 15
15 18
18 23
23 25
25 27
28 30
11 19
7 8

[出力例]
5
3
4
5
10
11

[入力例]

10 5

1 4

5 5

6 8

9 10

5 6

[出力例]

※AtCoderのテストケースより

[入力例]

3 6

1 1

2 2

3 3

[出力例]

※AtCoderのテストケースより

[入力例]

10 3

1 4

2 6

6 10

[出力例]

※AtCoderのテストケースより

[入力例]

30 11

1 5

5 10

10 13

13 15

15 18

18 23

23 25

25 27

28 30

11 19

7 8

[出力例]

■参照サイト
AtCoder Regular Contest 045

2021年1月16日

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

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

■感想.
1. 問題E は解答方針が見えなかったので, 解説を参考に実装し, AC版に到達できたので, 良かったと思う.
2. 但し, 傾きに紐づく頂点情報を管理するなどで, 実装に非常に苦労した.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/arc082/editorial.pdf
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using T3 = tuple<int, int, int>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define a first
#define b second
const LL MOD = 998244353;
LL mPow[202];
int x[202], y[202];
T3 tilt[202][202]; // 頂点 i, 頂点 j に 対する傾き.

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%d %d", &x[i], &y[i]);
    
    // 2. 2 の 冪乗.
    mPow[0] = 1LL;
    rep(i, N) mPow[i + 1] = mPow[i] << 1, mPow[i + 1] %= MOD;
    
    // 3. 二点間の傾きを保存(傾き b / a, 切片 c として, {a, b, c} を 保存).
    map<T3, int> m; // {傾き, index}
    rep(i, N){
        // 頂点 A を 取得.
        int iX = x[i], iY = y[i];
        repx(j, i + 1, N){
            // 頂点 B を 取得.
            int jX = x[j], jY = y[j];
            
            // 傾きを計算.
            int a = jX - iX, b = jY - iY;
            int g = __gcd(a, b);
            a /= g;
            b /= g;
            
            // 符号を調整.
            if(a < 0) a = -a, b = -b;
            if(a == 0 && b != 0) b = 1;
            if(a != 0 && b == 0) a = 1;
            
            // 切片(※a倍している状態で保存).
            int c = 0;
            if(a != 0) c = a * iY - b * iX;
            else       c = iX;
            
            // 傾きを保存.
            T3 t = {a, b, c};
            m[t] = 0;
            tilt[i][j] = t;
        }
    }
    
    // 4. index を 設定.
    int idx = -1;
    for(auto &p : m) p.b = ++idx;
    // for(auto &p : m){
    //     int a = get<0>(p.a);
    //     int b = get<1>(p.a);
    //     int c = get<2>(p.a);
    //     int i = p.b;
    //     printf("a=%d b=%d c=%d i=%d\n", a, b, c, i);
    // }
    
    // 5. 二点間の傾きに紐づく頂点を保存.
    vector<set<int>> v(idx + 1);
    rep(i, N){
        repx(j, i + 1, N){
            // 頂点 i, 頂点 j に 対する傾きに対応する頂点情報を保存.
            int at = m[tilt[i][j]];
            v[at].insert(i);
            v[at].insert(j);
        }
    }
    
    // 6. 集計.
    // 6-1. 0点集合.
    LL ans = mPow[N];
    ans += (MOD - 1LL);
    ans %= MOD;
    
    // 6-2. 1点集合.
    ans += (MOD - (LL)N);
    ans %= MOD;
    
    // 6-3. 2点以上集合.
    for(auto &p : m){
        // 傾きに対応するindexから, 該当する頂点数を取得.
        T3 t = p.a;
        int at = m[t];
        int k = v[at].size();
        ans += (MOD - mPow[k]);
        ans %= MOD;
        ans += (LL)k;
        ans %= MOD;
        ans += 1LL;
        ans %= MOD;
    }
    
    // 7. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

110

111

// 解き直し.

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

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using T3 = tuple<int, int, int>;

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

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

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

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

#define a first

#define b second

const LL MOD = 998244353;

LL mPow[202];

int x[202], y[202];

T3 tilt[202][202]; // 頂点 i, 頂点 j に対する傾き.

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

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

// 2. 2 の冪乗.

mPow[0] = 1LL;

rep(i, N) mPow[i + 1] = mPow[i] << 1, mPow[i + 1] %= MOD;

// 3. 二点間の傾きを保存(傾き b / a, 切片 c として, {a, b, c} を保存).

map<T3, int> m; // {傾き, index}

rep(i, N){

// 頂点 A を取得.

int iX = x[i], iY = y[i];

repx(j, i + 1, N){

// 頂点 B を取得.

int jX = x[j], jY = y[j];

// 傾きを計算.

int a = jX - iX, b = jY - iY;

int g = __gcd(a, b);

a /= g;

b /= g;

// 符号を調整.

if(a < 0) a = -a, b = -b;

if(a == 0 && b != 0) b = 1;

if(a != 0 && b == 0) a = 1;

// 切片(※a倍している状態で保存).

int c = 0;

if(a != 0) c = a * iY - b * iX;

else c = iX;

// 傾きを保存.

T3 t = {a, b, c};

m[t] = 0;

tilt[i][j] = t;

}

// 4. index を設定.

int idx = -1;

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

// for(auto &p : m){

// int a = get<0>(p.a);

// int b = get<1>(p.a);

// int c = get<2>(p.a);

// int i = p.b;

// printf("a=%d b=%d c=%d i=%d\n", a, b, c, i);

// }

// 5. 二点間の傾きに紐づく頂点を保存.

vector<set<int>> v(idx + 1);

rep(i, N){

repx(j, i + 1, N){

// 頂点 i, 頂点 j に対する傾きに対応する頂点情報を保存.

int at = m[tilt[i][j]];

v[at].insert(i);

v[at].insert(j);

}

// 6. 集計.

// 6-1. 0点集合.

LL ans = mPow[N];

ans += (MOD - 1LL);

ans %= MOD;

// 6-2. 1点集合.

ans += (MOD - (LL)N);

ans %= MOD;

// 6-3. 2点以上集合.

for(auto &p : m){

// 傾きに対応するindexから, 該当する頂点数を取得.

T3 t = p.a;

int at = m[t];

int k = v[at].size();

ans += (MOD - mPow[k]);

ans %= MOD;

ans += (LL)k;

ans %= MOD;

ans += 1LL;

ans %= MOD;

}

// 7. 出力.

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

return 0;

}

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

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

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

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

[入力例]
1
3141 2718

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

[入力例]
7
3 6
9 3
10 3
6 9
3 4
6 3
3 0

[出力例]
97

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

[出力例]
33554091

[入力例]

0 0

0 1

1 0

1 1

[出力例]

※AtCoderテストケースより

[入力例]

0 0

0 1

0 2

0 3

1 1

[出力例]

※AtCoderテストケースより

[入力例]

3141 2718

[出力例]

※AtCoderテストケースより

[入力例]

3 6

9 3

10 3

6 9

3 4

6 3

3 0

[出力例]

[入力例]

7 5

12 6

3 2

10 0

12 3

2 5

14 7

2 12

15 15

16 12

10 13

18 13

2 6

19 11

20 17

16 14

21 23

18 0

23 11

4 22

9 20

7 10

21 1

7 3

9 12

[出力例]

33554091

■参照サイト
AtCoder Regular Contest 082

2021年1月12日

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

C++の練習を兼ねて, AtCoder Beginner Contest 188 の問題F (+1-1×2) を解いてみた.

■感想.
1. 問題F は解答方針が見えなかったので, 解説を参考に実装し, AC版に到達できたので, 良かったと思う.
2. メモ化再帰の復習が出来たので, 非常に良かったと思う.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

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

int main(){
    
    // 1. 入力情報.
    LL X, Y;
    scanf("%lld %lld", &X, &Y);
    
    // 2. 操作回数を計算.
    // -> y に ついて メモ化しながら, 再帰処理を行うとの解説あり.
    map<LL, LL> memo;
    auto dfs = [&](auto&& self, LL x, LL y) -> LL{
        // 2-1. x, y の 差分(絶対値), y の 偶奇 を 設定.
        LL d = abs(x - y);
        bool odd = (1 & y);
        
        // 2-2. y が 1 の 場合.
        if(y == 1LL){
            if(!memo.count(y)) memo[y] = d;
            return d;
        }
        
        // 2-3. y が 1以外の奇数 の 場合.
        if(odd){
            LL y1 = (y + 1LL) / 2LL;
            LL y2 = (y - 1LL) / 2LL;
            if(!memo.count(y1)) memo[y1] = self(self, x, y1);
            if(!memo.count(y2)) memo[y2] = self(self, x, y2);
            return min({d, memo[y1] + 2LL, memo[y2] + 2LL});
        }
        
        // 2-4. y が 偶数 の 場合.
        if(!odd){
            LL y3 = y / 2LL;
            if(!memo.count(y3)) memo[y3] = self(self, x, y3);
            return min(d, memo[y3] + 1LL);
        }
    };
    LL ans = dfs(dfs, X, Y);
    
    // 3. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc188/editorial/471

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

int main(){

// 1. 入力情報.

LL X, Y;

scanf("%lld %lld", &X, &Y);

// 2. 操作回数を計算.

// -> y についてメモ化しながら, 再帰処理を行うとの解説あり.

map<LL, LL> memo;

auto dfs = [&](auto&& self, LL x, LL y) -> LL{

// 2-1. x, y の差分(絶対値), y の偶奇を設定.

LL d = abs(x - y);

bool odd = (1 & y);

// 2-2. y が 1 の場合.

if(y == 1LL){

if(!memo.count(y)) memo[y] = d;

return d;

}

// 2-3. y が 1以外の奇数の場合.

if(odd){

LL y1 = (y + 1LL) / 2LL;

LL y2 = (y - 1LL) / 2LL;

if(!memo.count(y1)) memo[y1] = self(self, x, y1);

if(!memo.count(y2)) memo[y2] = self(self, x, y2);

return min({d, memo[y1] + 2LL, memo[y2] + 2LL});

}

// 2-4. y が偶数の場合.

if(!odd){

LL y3 = y / 2LL;

if(!memo.count(y3)) memo[y3] = self(self, x, y3);

return min(d, memo[y3] + 1LL);

}

};

LL ans = dfs(dfs, X, Y);

// 3. 出力.

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

return 0;

}

[入力例]
3 9

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

[入力例]
7 11

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

[入力例]
1000000000000000000 1000000000000000000

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

[入力例]
12345678987654321 987654321123456789

[出力例]
3086419779899700

[入力例]
314159265358979323 846264338327950288

[出力例]
102593180776991753

[入力例]

3 9

[出力例]

※AtCoderテストケースより

[入力例]

7 11

[出力例]

※AtCoderテストケースより

[入力例]

1000000000000000000 1000000000000000000

[出力例]

※AtCoderテストケースより

[入力例]

12345678987654321 987654321123456789

[出力例]

3086419779899700

[入力例]

314159265358979323 846264338327950288

[出力例]

102593180776991753

■参照サイト
AtCoder Beginner Contest 188

2021年1月12日

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

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

■感想.
1. 問題E は解答方針が見えなかったので, 解説を参考に実装し, AC版に到達できたので, 良かったと思う.
2. DAG(Directed Acyclic Graph) の復習と, 苦手な dp の訓練を積めたので, 非常に良かったと思う.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/abc188/editorial/477
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vi = vector<int>;
using vvi = vector<vi>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
LL a[202020], dp[202020];

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    rep(i, N) scanf("%lld", &a[i]);
    vvi G(N);
    rep(i, M){
        int x, y;
        scanf("%d %d", &x, &y);
        x--, y--;
        G[x].pb(y);
    }
    
    // 2. 初期化.
    rep(i, N) dp[i] = 202020202020202020;
    
    // 3. dp更新.
    // -> 頂点 x から 頂点 y へ向かって, dp更新.
    rep(x, N) for(auto &y : G[x]) dp[y] = min({dp[y], dp[x], a[x]});
    
    // 4. 利益の最大値を計算.
    LL ans = -202020202020202020;
    rep(i, N) ans = max(ans, a[i] - dp[i]);
    
    // 5. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc188/editorial/477

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vi = vector<int>;

using vvi = vector<vi>;

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

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

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

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

#define pb push_back

LL a[202020], dp[202020];

int main(){

// 1. 入力情報.

int N, M;

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

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

vvi G(N);

rep(i, M){

int x, y;

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

x--, y--;

G[x].pb(y);

}

// 2. 初期化.

rep(i, N) dp[i] = 202020202020202020;

// 3. dp更新.

// -> 頂点 x から頂点 y へ向かって, dp更新.

rep(x, N) for(auto &y : G[x]) dp[y] = min({dp[y], dp[x], a[x]});

// 4. 利益の最大値を計算.

LL ans = -202020202020202020;

rep(i, N) ans = max(ans, a[i] - dp[i]);

// 5. 出力.

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

return 0;

}

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

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

[入力例]
5 5
13 8 3 15 18
2 4
1 2
4 5
2 3
1 3

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

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

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

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

[出力例]
6

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

[出力例]
10

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

[出力例]
15

[入力例]

4 3

2 3 1 5

2 4

1 2

1 3

[出力例]

※AtCoderテストケースより

[入力例]

5 5

13 8 3 15 18

2 4

1 2

4 5

2 3

1 3

[出力例]

※AtCoderテストケースより

[入力例]

3 1

1 100 1

2 3

[出力例]

-99

※AtCoderテストケースより

[入力例]

5 4

3 7 6 12 8

2 3

3 4

2 5

3 5

[出力例]

[入力例]

7 10

5 10 2 3 4 12 7

1 4

4 7

3 5

2 3

6 7

3 6

2 6

4 5

5 6

6 7

[出力例]

[入力例]

11 11

3 4 2 5 12 11 13 5 16 17 12

4 5

4 6

4 7

1 4

2 4

3 4

5 8

5 9

5 10

6 10

6 11

[出力例]

■参照サイト
AtCoder Beginner Contest 188

C++の練習を兼ねて, AtCoder Regular Contest 072 の 問題E (Alice in linear land) を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 098 の 問題E (Range Minimum Queries) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 111 の 問題E (Simple Math 3) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 068 の 問題E (Snuke Line) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 038 の 問題A (カードと兄妹) ～ 問題B (マス目と駒) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 045 の 問題A (スペース高橋君) ～ 問題B (ドキドキデート大作戦高橋君) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 188 の 問題F (+1-1×2) を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 072 の問題E (Alice in linear land) を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 098 の問題E (Range Minimum Queries) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 111 の問題E (Simple Math 3) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 068 の問題E (Snuke Line) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 038 の問題A (カードと兄妹) ～問題B (マス目と駒) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 045 の問題A (スペース高橋君) ～問題B (ドキドキデート大作戦高橋君) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 188 の問題F (+1-1×2) を解いてみた.

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