C++ | 個人用メモ帳

2022年6月19日

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

C++の練習を兼ねて, AtCoder Beginner Contest 256 の問題C (Filling 3×3 array) ～問題E (Takahashi’s Anguish) を解いてみた.

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

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

■C++版プログラム(問題C／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--)

int main(){
    
    // 1. 入力情報.
    int h1, h2, h3, w1, w2, w3;
    scanf("%d %d %d %d %d %d", &h1, &h2, &h3, &w1, &w2, &w3);
    
    // 2. カウント.
    int ans = 0;
    repx(a, 1, min(h1, w1)){
        repx(b, 1, min(h1, w2)){
            repx(c, 1, min(h2, w1)){
                repx(d, 1, min(h2, w2)){
                    int v13 = h1 - a - b;
                    int v23 = h2 - c - d;
                    int v31 = w1 - a - c;
                    int v32 = w2 - b - d;
                    if(v13 <= 0 || v23 <= 0 || v31 <= 0 || v32 <= 0) continue;
                    int v331 = w3 - v13 - v23;
                    int v332 = h3 - v31 - v32;
                    if(v331 > 0 && v332 > 0 && v331 == v332) ++ans;
                }
            }
        }
    }
    
    // 3. 出力.
    printf("%d\n", ans);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

int main(){

// 1. 入力情報.

int h1, h2, h3, w1, w2, w3;

scanf("%d %d %d %d %d %d", &h1, &h2, &h3, &w1, &w2, &w3);

// 2. カウント.

int ans = 0;

repx(a, 1, min(h1, w1)){

repx(b, 1, min(h1, w2)){

repx(c, 1, min(h2, w1)){

repx(d, 1, min(h2, w2)){

int v13 = h1 - a - b;

int v23 = h2 - c - d;

int v31 = w1 - a - c;

int v32 = w2 - b - d;

if(v13 <= 0 || v23 <= 0 || v31 <= 0 || v32 <= 0) continue;

int v331 = w3 - v13 - v23;

int v332 = h3 - v31 - v32;

if(v331 > 0 && v332 > 0 && v331 == v332) ++ans;

}

// 3. 出力.

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

return 0;

}

[入力例]
3 4 6 3 3 7

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

[入力例]
3 4 5 6 7 8

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

[入力例]
5 13 10 6 13 9

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

[入力例]
20 25 30 22 29 24

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

[入力例]
10 7 13 9 9 12

[出力例]
395

[入力例]
15 20 17 20 17 15

[出力例]
6694

[入力例]
22 23 12 19 20 18

[出力例]
7535

[入力例]

3 4 6 3 3 7

[出力例]

※AtCoderテストケースより

[入力例]

3 4 5 6 7 8

[出力例]

※AtCoderテストケースより

[入力例]

5 13 10 6 13 9

[出力例]

120

※AtCoderテストケースより

[入力例]

20 25 30 22 29 24

[出力例]

30613

※AtCoderテストケースより

[入力例]

10 7 13 9 9 12

[出力例]

395

[入力例]

15 20 17 20 17 15

[出力例]

6694

[入力例]

22 23 12 19 20 18

[出力例]

7535

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

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

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N){
        int l, r;
        scanf("%d %d", &l, &r);
        ++s[l];
        --s[r];
    }
    
    // 2. いもす法.
    rep(i, 202020 - 1) s[i + 1] += s[i];
    
    // 3. 区間を集計.
    vp v;
    int x = 0;
    rep(i, 202020){
        // 左端.
        if(!x && s[i]) x = i;
        
        // 右端.
        if(x && !s[i]){
            v.pb({x, i});
            x = 0;
        }
    }
    
    // 4. 出力.
    for(auto &p : v) printf("%d %d\n", p.a, p.b);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using P = pair<int, int>;

using vp = vector<P>;

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

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

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

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

#define pb push_back

#define a first

#define b second

int s[202020];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

rep(i, N){

int l, r;

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

++s[l];

--s[r];

}

// 2. いもす法.

rep(i, 202020 - 1) s[i + 1] += s[i];

// 3. 区間を集計.

vp v;

int x = 0;

rep(i, 202020){

// 左端.

if(!x && s[i]) x = i;

// 右端.

if(x && !s[i]){

v.pb({x, i});

x = 0;

}

// 4. 出力.

for(auto &p : v) printf("%d %d\n", p.a, p.b);

return 0;

}

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

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

[入力例]
3
10 40
30 60
20 50

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

[入力例]
10
12 41
41 43
62 75
2 5
56 167
300 460
367 810
600 799
1270 1327
1034 1042

[出力例]
2 5
12 43
56 167
300 810
1034 1042
1270 1327

[入力例]
20
11 33
61 75
78 131
3 5
71 189
142 355
498 649
594 919
1281 1346
1041 1052
24 44
85 93
230 265
3035 3038
86 198
201 394
500 891
602 826
2386 2444
2415 2435

[出力例]
3 5
11 44
61 394
498 919
1041 1052
1281 1346
2386 2444
3035 3038

[入力例]

10 20

20 30

40 50

[出力例]

10 30

40 50

※AtCoderテストケースより

[入力例]

10 40

30 60

20 50

[出力例]

10 60

※AtCoderテストケースより

[入力例]

12 41

41 43

62 75

2 5

56 167

300 460

367 810

600 799

1270 1327

1034 1042

[出力例]

2 5

12 43

56 167

300 810

1034 1042

1270 1327

[入力例]

11 33

61 75

78 131

3 5

71 189

142 355

498 649

594 919

1281 1346

1041 1052

24 44

85 93

230 265

3035 3038

86 198

201 394

500 891

602 826

2386 2444

2415 2435

[出力例]

3 5

11 44

61 394

498 919

1041 1052

1281 1346

2386 2444

3035 3038

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

// 解き直し.
// https://atcoder.jp/contests/abc256/editorial/4135
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
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
const LL INF = 202020202020202020;
LL b[202020];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    vvi G(N);
    vi FG(N);
    rep(i, N){
        int x;
        scanf("%d", &x);
        --x;
        
        // 双方向のグラフ.
        G[i].pb(x);
        G[x].pb(i);
        
        // Functional Graph.
        FG[i] = x;
    }
    rep(i, N) scanf("%lld", &b[i]);
    
    // 2. bfs.
    // https://ja.wikipedia.org/wiki/幅優先探索
    auto bfs = [&](vvi &G, int s, int* c, int l){
        // 空のキュー.
        queue<int> q;
        
        // 連結成分番号を設定.
        c[s] = l;
        
        // 探索地点 s をキュー q に追加.
        q.push(s);
        while(!q.empty()){
            // キューから取り出す.
            int u = q.front();
            q.pop();
            
            // 取り出した要素を処理.
            for(auto &e : G[u]) if(!c[e] && e != s) c[e] = l, q.push(e);
        }
    };
    int c[N], idx = 0;
    vi v;
    rep(i, N) c[i] = 0;
    rep(i, N){
        if(!c[i]){
            // 連結成分の抽出.
            bfs(G, i, c, ++idx);
            
            // サイクルの起点となる頂点.
            v.pb(i);
        }
    }
    
    // 3. 集計.
    LL ans = 0;
    rep(i, v.size()){
        // 3-1. サイクルの起点は？
        set<int> st;
        int cur = v[i];
        while(!st.count(cur)){
            st.insert(cur);
            cur = FG[cur];
        }
        
        // 3-2. サイクルの起点から, 不満度の最小値を抽出.
        LL minC = INF;
        st.clear();
        while(!st.count(cur)){
            minC = min(minC, b[cur]);
            st.insert(cur);
            cur = FG[cur];
        }
        
        // 3-3. 加算.
        ans += minC;
    }
    
    // 4. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc256/editorial/4135

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

using vvi = vector<vi>;

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

const LL INF = 202020202020202020;

LL b[202020];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

vvi G(N);

vi FG(N);

rep(i, N){

int x;

scanf("%d", &x);

--x;

// 双方向のグラフ.

G[i].pb(x);

G[x].pb(i);

// Functional Graph.

FG[i] = x;

}

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

// 2. bfs.

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

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

// 空のキュー.

queue<int> q;

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

c[s] = l;

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

q.push(s);

while(!q.empty()){

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

int u = q.front();

q.pop();

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

for(auto &e : G[u]) if(!c[e] && e != s) c[e] = l, q.push(e);

}

};

int c[N], idx = 0;

vi v;

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

rep(i, N){

if(!c[i]){

// 連結成分の抽出.

bfs(G, i, c, ++idx);

// サイクルの起点となる頂点.

v.pb(i);

}

// 3. 集計.

LL ans = 0;

rep(i, v.size()){

// 3-1. サイクルの起点は？

set<int> st;

int cur = v[i];

while(!st.count(cur)){

st.insert(cur);

cur = FG[cur];

}

// 3-2. サイクルの起点から, 不満度の最小値を抽出.

LL minC = INF;

st.clear();

while(!st.count(cur)){

minC = min(minC, b[cur]);

st.insert(cur);

cur = FG[cur];

}

// 3-3. 加算.

ans += minC;

}

// 4. 出力.

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

return 0;

}

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

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

[入力例]
8
7 3 5 5 8 4 1 2
36 49 73 38 30 85 27 45

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

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

[出力例]
8

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

[出力例]
9

[入力例]
20
2 1 4 5 3 7 9 7 8 11 12 11 14 15 16 17 13 19 18 19
997 865 1169 1082 803 860 1262 860 980 790 984 760 657 734 731 684 769 1141 1106 1174

[出力例]
5051

[入力例]

2 3 2

1 10 100

[出力例]

※AtCoderテストケースより

[入力例]

7 3 5 5 8 4 1 2

36 49 73 38 30 85 27 45

[出力例]

※AtCoderテストケースより

[入力例]

2 3 2 5 4

5 7 3 6 5

[出力例]

[入力例]

10 10 5 3 4 8 5 5 2 9

3 8 5 12 3 7 10 4 6 7

[出力例]

[入力例]

2 1 4 5 3 7 9 7 8 11 12 11 14 15 16 17 13 19 18 19

997 865 1169 1082 803 860 1262 860 980 790 984 760 657 734 731 684 769 1141 1106 1174

[出力例]

5051

■参照サイト
東京海上日動プログラミングコンテスト2022（AtCoder Beginner Contest 256）

2022年6月18日

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

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

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

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

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

// 解き直し.
// https://img.atcoder.jp/arc073/editorial.pdf
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using P = pair<int, int>;
using vp = vector<P>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
#define a first
#define b second
#define all(x) x.begin(), x.end()
const int INF = 2020202020;

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    vp v;
    rep(i, N){
        // ボールの情報を保存.
        int x, y;
        scanf("%d %d", &x, &y);
        if(x > y) swap(x, y);
        v.pb({x, y});
    }
    
    // 2. (Rmax - Rmin) * (Bmax - Bmin) の 最大値は？
    // 2-1. Rmin = MIN かつ Bmax = MAX の 場合.
    int rMin = INF, rMax = 0, bMin = INF, bMax = 0;
    rep(i, v.size()){
        rMin = min(rMin, v[i].a);
        rMax = max(rMax, v[i].a);
        bMin = min(bMin, v[i].b);
        bMax = max(bMax, v[i].b);
    }
    LL ans1 = (LL)(rMax - rMin) * (LL)(bMax - bMin);
    
    // 2-2. Rmin = MIN かつ Rmax = MAX の 場合.
    // -> 赤色には, 何も考えずに, 好きなボールを割り当てる.
    rMin = INF, rMax = 0;
    rep(i, v.size()){
        rMin = min(rMin, v[i].a);
        rMax = max(rMax, v[i].b);
    }
    
    // 各袋について, ボールを交換.
    int bMinMax = INF;
    multiset<int> m;
    sort(all(v));
    for(auto &p : v) m.insert(p.a);
    for(auto &p : v){
        // 交換.
        auto itr1 = m.find(p.a);
        m.erase(itr1); // 1個だけ削除.
        m.insert(p.b); // 1個だけ追加.
        
        // 最初のボール.
        auto itr2 = m.begin();
        int s = *(itr2);
        
        // 最後のボール.
        auto itr3 = m.end();
        int e = *(--itr3);
        
        // 差分の最小値更新.
        bMinMax = min(bMinMax, e - s);
    }
    LL ans2 = (LL)(rMax - rMin) * (LL)bMinMax;
    
    // 3. 出力.
    printf("%lld\n", min(ans1, ans2));
    return 0;
    
}

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using P = pair<int, int>;

using vp = vector<P>;

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

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

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

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

#define pb push_back

#define a first

#define b second

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

const int INF = 2020202020;

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

vp v;

rep(i, N){

// ボールの情報を保存.

int x, y;

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

if(x > y) swap(x, y);

v.pb({x, y});

}

// 2. (Rmax - Rmin) * (Bmax - Bmin) の最大値は？

// 2-1. Rmin = MIN かつ Bmax = MAX の場合.

int rMin = INF, rMax = 0, bMin = INF, bMax = 0;

rep(i, v.size()){

rMin = min(rMin, v[i].a);

rMax = max(rMax, v[i].a);

bMin = min(bMin, v[i].b);

bMax = max(bMax, v[i].b);

}

LL ans1 = (LL)(rMax - rMin) * (LL)(bMax - bMin);

// 2-2. Rmin = MIN かつ Rmax = MAX の場合.

// -> 赤色には, 何も考えずに, 好きなボールを割り当てる.

rMin = INF, rMax = 0;

rep(i, v.size()){

rMin = min(rMin, v[i].a);

rMax = max(rMax, v[i].b);

}

// 各袋について, ボールを交換.

int bMinMax = INF;

multiset<int> m;

sort(all(v));

for(auto &p : v) m.insert(p.a);

for(auto &p : v){

// 交換.

auto itr1 = m.find(p.a);

m.erase(itr1); // 1個だけ削除.

m.insert(p.b); // 1個だけ追加.

// 最初のボール.

auto itr2 = m.begin();

int s = *(itr2);

// 最後のボール.

auto itr3 = m.end();

int e = *(--itr3);

// 差分の最小値更新.

bMinMax = min(bMinMax, e - s);

}

LL ans2 = (LL)(rMax - rMin) * (LL)bMinMax;

// 3. 出力.

printf("%lld\n", min(ans1, ans2));

return 0;

}

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

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

[入力例]
3
1010 10
1000 1
20 1020

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

[入力例]
2
1 1
1000000000 1000000000

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

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

[出力例]
66

[入力例]
25
27 17
26 18
11 21
26 31
28 17
10 14
15 22
15 12
10 15
18 21
16 29
25 15
15 23
26 16
31 11
15 24
24 16
19 32
28 14
15 18
33 16
16 10
35 31
26 28
30 27

[出力例]
425

[入力例]
50
229 378
159 183
472 144
391 150
336 219
155 169
263 413
297 335
285 468
222 255
352 183
378 348
369 185
429 452
239 340
253 223
177 406
294 237
130 439
183 234
458 215
377 296
151 233
427 392
352 255
219 228
418 408
326 130
324 184
284 153
215 202
500 362
499 404
211 304
391 161
196 443
257 322
405 144
323 364
435 388
357 143
130 273
437 408
336 364
435 392
190 176
409 223
236 130
334 131
187 296

[出力例]
98969

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

[入力例]

1 2

3 4

5 6

[出力例]

※AtCoderのテストケースより

[入力例]

1010 10

1000 1

20 1020

[出力例]

380

※AtCoderのテストケースより

[入力例]

1 1

1000000000 1000000000

[出力例]

999999998000000001

※AtCoderのテストケースより

[入力例]

3 5

7 5

3 6

1 3

11 9

9 3

7 12

5 2

1 6

11 8

[出力例]

[入力例]

27 17

26 18

11 21

26 31

28 17

10 14

15 22

15 12

10 15

18 21

16 29

25 15

15 23

26 16

31 11

15 24

24 16

19 32

28 14

15 18

33 16

16 10

35 31

26 28

30 27

[出力例]

425

[入力例]

229 378

159 183

472 144

391 150

336 219

155 169

263 413

297 335

285 468

222 255

352 183

378 348

369 185

429 452

239 340

253 223

177 406

294 237

130 439

183 234

458 215

377 296

151 233

427 392

352 255

219 228

418 408

326 130

324 184

284 153

215 202

500 362

499 404

211 304

391 161

196 443

257 322

405 144

323 364

435 388

357 143

130 273

437 408

336 364

435 392

190 176

409 223

236 130

334 131

187 296

[出力例]

98969

■参照サイト
AtCoder Regular Contest 073

2022年6月16日2022年6月16日

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

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

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

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

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

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

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    rep(i, N - 1) scanf("%lld", &s[i]);
    rep(i, M) scanf("%lld", &x[i]);
    
    // 2. 数列 B.
    repx(i, 1, N) b[i] = s[i - 1] - b[i - 1];
    
    // 3. C[i][j] を 保存.
    map<LL, int> m;
    rep(i, N){
        rep(j, M){
            LL c = x[j] - b[i];
            if(i & 1) c *= -1;
            ++m[c];
        }
    }
    
    // 4. 出現回数の最大値は？
    int ans = 0;
    for(auto &p : m) ans = max(ans, p.b);
    
    // 5. 出力.
    printf("%d\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc255/editorial/4098

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

#define a first

#define b second

LL s[101010], x[11], b[101010];

int main(){

// 1. 入力情報.

int N, M;

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

rep(i, N - 1) scanf("%lld", &s[i]);

rep(i, M) scanf("%lld", &x[i]);

// 2. 数列 B.

repx(i, 1, N) b[i] = s[i - 1] - b[i - 1];

// 3. C[i][j] を保存.

map<LL, int> m;

rep(i, N){

rep(j, M){

LL c = x[j] - b[i];

if(i & 1) c *= -1;

++m[c];

}

// 4. 出現回数の最大値は？

int ans = 0;

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

// 5. 出力.

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

return 0;

}

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

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

[入力例]
20 10
-183260318 206417795 409343217 238245886 138964265 -415224774 -499400499 -313180261 283784093 498751662 668946791 965735441 382033304 177367159 31017484 27914238 757966050 878978971 73210901
-470019195 -379631053 -287722161 -231146414 -84796739 328710269 355719851 416979387 431167199 498905398

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

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

[出力例]
3

[入力例]
16 7
121 10 -7 -5 55 80 -15 20 -17 23 8 -82 9 37 25
-21 -5 1 28 33 48 50

[出力例]
3

[入力例]
31 10
12 5 25 12 -20 8 64 27 -19 11 7 8 9 18 -7 13 22 7 -12 7 -6 18 -8 12 -8 0 -18 9 -3 18
-27 -11 5 8 10 11 22 23 33 35

[出力例]
7

[入力例]
101 10
54 169 86 -116 76 -106 -133 59 -161 97 74 99 97 112 -58 54 117 -58 57 117 -139 -110 102 140 111 116 -124 128 -169 1115 123 75 143 137 56 -134 109 -162 128 97 71 -128 109 66 63 124 66 77 145 921 108 91 91 100 -52 141 94 146 59 -136 78 -160 156 155 96 137 -73 61 -104 54 -15 101 -70 18 -60 -105 78 124 83 -50 97 90 51 -135 -117 172 143 99 -88 124 63 -82 164 -129 68 96 -163 148 -129 719
-500 -234 0 111 123 345 777 1000 1200 2022

[出力例]
5

[入力例]

9 2

2 3 3 4 -4 -7 -4 -1

-1 5

[出力例]

※AtCoderテストケースより

[入力例]

20 10

-183260318 206417795 409343217 238245886 138964265 -415224774 -499400499 -313180261 283784093 498751662 668946791 965735441 382033304 177367159 31017484 27914238 757966050 878978971 73210901

-470019195 -379631053 -287722161 -231146414 -84796739 328710269 355719851 416979387 431167199 498905398

[出力例]

※AtCoderテストケースより

[入力例]

6 3

3 1 4 1 5

1 2 3

[出力例]

[入力例]

16 7

121 10 -7 -5 55 80 -15 20 -17 23 8 -82 9 37 25

-21 -5 1 28 33 48 50

[出力例]

[入力例]

31 10

12 5 25 12 -20 8 64 27 -19 11 7 8 9 18 -7 13 22 7 -12 7 -6 18 -8 12 -8 0 -18 9 -3 18

-27 -11 5 8 10 11 22 23 33 35

[出力例]

[入力例]

101 10

54 169 86 -116 76 -106 -133 59 -161 97 74 99 97 112 -58 54 117 -58 57 117 -139 -110 102 140 111 116 -124 128 -169 1115 123 75 143 137 56 -134 109 -162 128 97 71 -128 109 66 63 124 66 77 145 921 108 91 91 100 -52 141 94 146 59 -136 78 -160 156 155 96 137 -73 61 -104 54 -15 101 -70 18 -60 -105 78 124 83 -50 97 90 51 -135 -117 172 143 99 -88 124 63 -82 164 -129 68 96 -163 148 -129 719

-500 -234 0 111 123 345 777 1000 1200 2022

[出力例]

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

2022年6月16日

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

C++の練習を兼ねて, AtCoder Beginner Contest 191 の問題D (Circle Lattice Points) を解いてみた.

■感想.
1. 問題Dは, 方針が見えなかったので, 解説を参考にして, ようやく, AC版に到達出来た.
2. 実装に, 大変苦労し, 個人的には, トラップ(小数点, 負数排除, 平行移動, XY座標の大小比較など)が, 非常に多いと感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

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

int main(){
    
    // 1. 入力情報.
    double x, y, r;
    scanf("%lf %lf %lf", &x, &y, &r);
    
    // 2. 10000倍 かつ 平行移動(負数 の パターン を 無くし, random_09.txt などの WA を 回避するため).
    LL X = D * x + 1e10;
    LL Y = D * y + 1e10;
    LL R = D * r;
    
    // 3. swap(handmade_marginal_00.txt などの WA を 回避するため).
    if(X > Y) swap(X, Y);
    
    // 4. x の 最小値, 最大値(但し, 10000 の 倍数).
    LL xMin = X - R;
    LL xMax = X + R;
    LL qMinX = xMin / D;
    LL qMaxX = xMax / D;
    while(qMinX * D < xMin) ++qMinX;
    while(qMaxX * D > xMax) --qMaxX;
    
    // 5. 格子点をカウントする.
    LL ans = 0;
    repx(i, (int)qMinX, (int)(qMaxX + 1)){
        // x方向.
        LL curX = (LL)i * (LL)D;
        
        // y方向.
        // -> handmade_marginal_01.txt などの WA を 回避するため, 1 加算.
        LL dy = (LL)sqrt(R * R - (curX - X) * (curX - X)) + 1;
        LL yMin = Y - dy;
        LL yMax = Y + dy;
        
        // y の 最小値, 最大値(但し, 10000 の 倍数).
        // -> qMinY * D < yMin, qMaxY * D > yMax は, 判定条件として甘いことが分かったため, 廃止.
        LL qMinY = yMin / D;
        LL qMaxY = yMax / D;
        LL dx = R * R - (curX - X) * (curX - X);
        while((qMinY * D - Y) * (qMinY * D - Y) > dx) ++qMinY;
        while((qMaxY * D - Y) * (qMaxY * D - Y) > dx) --qMaxY;
        
        // 集計.
        ans += (qMaxY - qMinY + 1);
    }
    
    // 6. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc191/editorial/611

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

const int D = 10000;

int main(){

// 1. 入力情報.

double x, y, r;

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

// 2. 10000倍かつ平行移動(負数のパターンを無くし, random_09.txt などの WA を回避するため).

LL X = D * x + 1e10;

LL Y = D * y + 1e10;

LL R = D * r;

// 3. swap(handmade_marginal_00.txt などの WA を回避するため).

if(X > Y) swap(X, Y);

// 4. x の最小値, 最大値(但し, 10000 の倍数).

LL xMin = X - R;

LL xMax = X + R;

LL qMinX = xMin / D;

LL qMaxX = xMax / D;

while(qMinX * D < xMin) ++qMinX;

while(qMaxX * D > xMax) --qMaxX;

// 5. 格子点をカウントする.

LL ans = 0;

repx(i, (int)qMinX, (int)(qMaxX + 1)){

// x方向.

LL curX = (LL)i * (LL)D;

// y方向.

// -> handmade_marginal_01.txt などの WA を回避するため, 1 加算.

LL dy = (LL)sqrt(R * R - (curX - X) * (curX - X)) + 1;

LL yMin = Y - dy;

LL yMax = Y + dy;

// y の最小値, 最大値(但し, 10000 の倍数).

// -> qMinY * D < yMin, qMaxY * D > yMax は, 判定条件として甘いことが分かったため, 廃止.

LL qMinY = yMin / D;

LL qMaxY = yMax / D;

LL dx = R * R - (curX - X) * (curX - X);

while((qMinY * D - Y) * (qMinY * D - Y) > dx) ++qMinY;

while((qMaxY * D - Y) * (qMaxY * D - Y) > dx) --qMaxY;

// 集計.

ans += (qMaxY - qMinY + 1);

}

// 6. 出力.

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

return 0;

}

[入力例]
0.2 0.8 1.1

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

[入力例]
100 100 1

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

[入力例]
42782.4720 31949.0192 99999.99

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

[入力例]
12 13 14

[出力例]
613

[入力例]
12.3 23.4 34.5

[出力例]
3737

[入力例]
12345.6789 98765.4321 10101.0101

[出力例]
320538029

[入力例]
55555.5555 66666.6666 77777.7777

[出力例]
19004696639

[入力例]

0.2 0.8 1.1

[出力例]

※AtCoderテストケースより

[入力例]

100 100 1

[出力例]

※AtCoderテストケースより

[入力例]

42782.4720 31949.0192 99999.99

[出力例]

31415920098

※AtCoderテストケースより

[入力例]

12 13 14

[出力例]

613

[入力例]

12.3 23.4 34.5

[出力例]

3737

[入力例]

12345.6789 98765.4321 10101.0101

[出力例]

320538029

[入力例]

55555.5555 66666.6666 77777.7777

[出力例]

19004696639

■参照サイト
AtCoder Beginner Contest 191

2022年6月15日2022年6月15日

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

C++の練習を兼ねて, AtCoder Regular Contest 043 の問題C (転倒距離) を解いてみた.

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

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

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

// 解き直し.
// https://www.slideshare.net/chokudai/arc043
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
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
const int MAX = 101010;
int ia[MAX], oa[MAX], ib[MAX], ob[MAX], a[MAX], b[MAX], tc[MAX], ic[MAX], oc[MAX], ca[MAX], cb[MAX];
LL f[MAX];

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

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    repx(i, 1, N + 1){
        scanf("%d", &ia[i]);
        oa[ia[i]] = i;
    }
    repx(i, 1, N + 1){
        scanf("%d", &ib[i]);
        ob[ib[i]] = i;
    }
    
    // 2. 順列 B の 並べ替え.
    repx(i, 1, N + 1) a[i] = i;
    repx(i, 1, N + 1) b[i] = oa[ib[i]];
    
    // 3. 順列 A, B との 転倒距離は？
    // -> フラグも保存する.
    LL T = 0;
    BIT<LL> ft(N + 2);
    repx(i, 1, N + 1){
        // 位置 b[i] に, 加算.
        ft.add(b[i], 1);
        
        // 区間[b[i] + 1, N + 1) の 合計は？
        f[b[i]] = ft.sum(b[i] + 1, N + 1);
        
        // 集計.
        T += f[b[i]];
    }
    
    // 4. 例外.
    if(T & 1){
        puts("-1");
        return 0;
    }
    
    // 5. 順列 C の 候補は？
    LL U = T / 2;
    repx(i, 1, N + 1){
        // 残り(バブルソート).
        if(f[i] > U){
            // 整数 i を, U 回 前方 に 移動.
            int at = -1;
            vi v;
            repx(j, 1, N + 1){
                if(b[j] >= i) v.pb(b[j]);
                if(b[j] == i) at = v.size();
            }
            
            // バブルソート(U 回).
            repr(j, at - 1, at - (int)U) swap(v[j], v[j - 1]);
            
            // 移し替え.
            repx(j, i, N + 1) tc[j] = v[j - i];
            
            // 終了.
            break;
        }
        
        // Skip(バブルソートのシュミレート).
        tc[i] = i;
        U -= f[i];
    }
    
    // 6. 順列 C は？
    // -> 順列 A を 1, 2, ..., N と 変換したので, 逆変換.
    repx(i, 1, N + 1){
        ic[i] = ia[tc[i]];
        oc[ic[i]] = i;
    }
    
    // 7. (A, C), (B, C) の 距離 を チェック.
    // -> 順列 C を 基準に 計算.
    repx(i, 1, N + 1){
        ca[i] = oc[ia[i]];
        cb[i] = oc[ib[i]];
    }
    LL d1 = 0, d2 = 0;
    BIT<LL> ft1(N + 2), ft2(N + 2);
    repx(i, 1, N + 1){
        // 位置 ca[i], cb[i] に, 加算.
        ft1.add(ca[i], 1);
        ft2.add(cb[i], 1);
        
        // 集計.
        // 区間[ca[i] + 1, N + 1), [cb[i] + 1, N + 1) を 集計対象とする.
        d1 += ft1.sum(ca[i] + 1, N + 1);
        d2 += ft2.sum(cb[i] + 1, N + 1);
    }
    assert(d1 == d2);
    
    // 8. 出力.
    repx(i, 1, N + 1) printf("%d%s", ic[i], (i < N) ? " " : "\n");
    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

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

const int MAX = 101010;

int ia[MAX], oa[MAX], ib[MAX], ob[MAX], a[MAX], b[MAX], tc[MAX], ic[MAX], oc[MAX], ca[MAX], cb[MAX];

LL f[MAX];

// Binary Indexed Tree (Fenwick Tree)

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

template<typename T>

struct BIT{

int n;

vector<T> d;

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

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

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

}

T sum(int i){

T x = 0;

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

return x;

}

T sum(int l, int r){

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

}

};

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

repx(i, 1, N + 1){

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

oa[ia[i]] = i;

}

repx(i, 1, N + 1){

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

ob[ib[i]] = i;

}

// 2. 順列 B の並べ替え.

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

repx(i, 1, N + 1) b[i] = oa[ib[i]];

// 3. 順列 A, B との転倒距離は？

// -> フラグも保存する.

LL T = 0;

BIT<LL> ft(N + 2);

repx(i, 1, N + 1){

// 位置 b[i] に, 加算.

ft.add(b[i], 1);

// 区間[b[i] + 1, N + 1) の合計は？

f[b[i]] = ft.sum(b[i] + 1, N + 1);

// 集計.

T += f[b[i]];

}

// 4. 例外.

if(T & 1){

puts("-1");

return 0;

}

// 5. 順列 C の候補は？

LL U = T / 2;

repx(i, 1, N + 1){

// 残り(バブルソート).

if(f[i] > U){

// 整数 i を, U 回前方に移動.

int at = -1;

vi v;

repx(j, 1, N + 1){

if(b[j] >= i) v.pb(b[j]);

if(b[j] == i) at = v.size();

}

// バブルソート(U 回).

repr(j, at - 1, at - (int)U) swap(v[j], v[j - 1]);

// 移し替え.

repx(j, i, N + 1) tc[j] = v[j - i];

// 終了.

break;

}

// Skip(バブルソートのシュミレート).

tc[i] = i;

U -= f[i];

}

// 6. 順列 C は？

// -> 順列 A を 1, 2, ..., N と変換したので, 逆変換.

repx(i, 1, N + 1){

ic[i] = ia[tc[i]];

oc[ic[i]] = i;

}

// 7. (A, C), (B, C) の距離をチェック.

// -> 順列 C を基準に計算.

repx(i, 1, N + 1){

ca[i] = oc[ia[i]];

cb[i] = oc[ib[i]];

}

LL d1 = 0, d2 = 0;

BIT<LL> ft1(N + 2), ft2(N + 2);

repx(i, 1, N + 1){

// 位置 ca[i], cb[i] に, 加算.

ft1.add(ca[i], 1);

ft2.add(cb[i], 1);

// 集計.

// 区間[ca[i] + 1, N + 1), [cb[i] + 1, N + 1) を集計対象とする.

d1 += ft1.sum(ca[i] + 1, N + 1);

d2 += ft2.sum(cb[i] + 1, N + 1);

}

assert(d1 == d2);

// 8. 出力.

repx(i, 1, N + 1) printf("%d%s", ic[i], (i < N) ? " " : "\n");

return 0;

}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[入力例]

1 2 3 4 5

5 4 3 2 1

[出力例]

5 2 1 3 4

※AtCoderのテストケースより

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

1 5 4 2 3

[入力例]

1 2 3 4 5

1 2 4 3 5

[出力例]

-1

※AtCoderのテストケースより

[入力例]

3 1 4 2 5 9 7 6 8

2 1 8 3 5 7 9 4 6

[出力例]

3 1 2 8 4 5 7 9 6

※AtCoderのテストケースより

[入力例]

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

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

[出力例]

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

[入力例]

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

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

[出力例]

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

[入力例]

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

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

[出力例]

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

[入力例]

100

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

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

[出力例]

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

■参照サイト
AtCoder Regular Contest 043

2022年6月13日

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

C++の練習を兼ねて, AtCoder Beginner Contest 255 の問題C (±1 Operation 1) ～問題D (±1 Operation 2) を解いてみた.

■感想.
1. 問題C, Dは, 方針を絞り込めたので, AC版に到達できたと思う.
2. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(){
    
    // 1. 入力情報.
    LL X, A, D, N;
    scanf("%lld %lld %lld %lld", &X, &A, &D, &N);
    
    // 2. 操作の最小回数は？
    // 2-1. 公差を調整.
    LL ans = 0;
    if(D < 0){
        D = -D;
        A = A - D * (N - 1);
    }
    
    // 2-2. 公差ゼロ.
    if(D == 0){
        printf("%lld\n", abs(A - X));
        return 0;
    }
    
    // 2-3. 初項以下.
    if(X <= A){
        printf("%lld\n", A - X);
        return 0;
    }
    
    // 2-4. 最終項以上.
    if(X >= A + D * (N - 1)){
        printf("%lld\n", X - A - D * (N - 1));
        return 0;
    }
    
    // 2-5. 上記以外.
    X -= A;
    X %= D;
    printf("%lld\n", min(X, D - X));
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

int main(){

// 1. 入力情報.

LL X, A, D, N;

scanf("%lld %lld %lld %lld", &X, &A, &D, &N);

// 2. 操作の最小回数は？

// 2-1. 公差を調整.

LL ans = 0;

if(D < 0){

D = -D;

A = A - D * (N - 1);

}

// 2-2. 公差ゼロ.

if(D == 0){

printf("%lld\n", abs(A - X));

return 0;

}

// 2-3. 初項以下.

if(X <= A){

printf("%lld\n", A - X);

return 0;

}

// 2-4. 最終項以上.

if(X >= A + D * (N - 1)){

printf("%lld\n", X - A - D * (N - 1));

return 0;

}

// 2-5. 上記以外.

X -= A;

X %= D;

printf("%lld\n", min(X, D - X));

return 0;

}

[入力例]
6 2 3 3

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

[入力例]
0 0 0 1

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

[入力例]
998244353 -10 -20 30

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

[入力例]
-555555555555555555 -1000000000000000000 1000000 1000000000000

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

[入力例]
31 41 59 26

[出力例]
10

[入力例]
2022 6 13 255

[出力例]
1

[入力例]

6 2 3 3

[出力例]

※AtCoderテストケースより

[入力例]

0 0 0 1

[出力例]

※AtCoderテストケースより

[入力例]

998244353 -10 -20 30

[出力例]

998244363

※AtCoderテストケースより

[入力例]

-555555555555555555 -1000000000000000000 1000000 1000000000000

[出力例]

444445

※AtCoderテストケースより

[入力例]

31 41 59 26

[出力例]

[入力例]

2022 6 13 255

[出力例]

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

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

int main(){
    
    // 1. 入力情報.
    int N, Q;
    scanf("%d %d", &N, &Q);
    rep(i, N) scanf("%lld", &a[i]);
    
    // 2. sort.
    sort(a, a + N);
    
    // 3. 累積和.
    rep(i, N) aCum[i + 1] = aCum[i] + a[i];
    
    // 4. クエリ回答.
    rep(i, Q){
        // クエリ入力情報.
        LL x;
        scanf("%lld", &x);
        
        // 大小関係が変わる場所.
        int at = lower_bound(a, a + N, x) - a;
        
        // 集計.
        LL ans = 0;
        ans += (aCum[N] - aCum[at]) - x * (LL)(N - at);
        ans += x * (LL)at - aCum[at];
        
        // 出力.
        printf("%lld\n", ans);
    }
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

LL a[202020], aCum[202020];

int main(){

// 1. 入力情報.

int N, Q;

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

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

// 2. sort.

sort(a, a + N);

// 3. 累積和.

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

// 4. クエリ回答.

rep(i, Q){

// クエリ入力情報.

LL x;

scanf("%lld", &x);

// 大小関係が変わる場所.

int at = lower_bound(a, a + N, x) - a;

// 集計.

LL ans = 0;

ans += (aCum[N] - aCum[at]) - x * (LL)(N - at);

ans += x * (LL)at - aCum[at];

// 出力.

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

}

return 0;

}

[入力例]
5 3
6 11 2 5 5
5
20
0

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

[入力例]
10 5
1000000000 314159265 271828182 141421356 161803398 0 777777777 255255255 536870912 998244353
555555555
321654987
1000000000
789456123
0

[出力例]
3316905982
2811735560
5542639502
4275864946
4457360498
※AtCoderテストケースより

[入力例]
20 5
31 41 5 9 26 53 5 89 79 3 23 8 4 62 6 4 33 8 32 7
7
18
28
48
67

[出力例]
418
410
424
614
880

[入力例]
50 10
432 253 635 391 609 376 699 1147 868 743 1134 13 1020 170 377 224 63 1075 493 814 543 125 200 389 1111 971 1201 869 1008 553 1066 718 573 917 657 822 156 823 286 667 124 318 455 1208 399 251 190 74 1032 16
745
865
308
718
725
1362
753
1065
106
532

[出力例]
16834
19026
18192
16452
16550
38842
16962
24966
24474
15580

[入力例]
100 20
1803 8552 1725 9877 6771 9125 5772 11782 11128 12113 7042 10138 6032 9172 6314 3764 6937 1890 1272 9446 6824 2119 9519 9323 10070 4772 9204 348 2247 354 6407 11843 5199 8523 3456 10969 10723 8382 9282 5975 12204 2284 2439 8162 12288 1247 8208 8505 3083 7978 11199 3294 8426 1079 6657 10610 11825 1156 6909 4633 6636 90 12222 2226 6813 2537 6725 8666 8031 10913 9074 544 1337 8284 3677 4406 9826 10673 6716 3174 2796 11006 12305 9376 6602 7472 2588 11044 6210 3100 1661 8277 10858 9201 3965 11476 4149 5037 7017 5033
1500
1782
4834
5
5555
3867
510
777
24
534
4581
1334
92
2872
577
19
216
2990
165
999

[出力例]
532269
509501
347337
669623
325615
385395
620599
595967
667723
618343
356425
545887
660927
436063
614367
668223
648775
429219
653773
575543

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

[入力例]

5 3

6 11 2 5 5

[出力例]

※AtCoderテストケースより

[入力例]

10 5

1000000000 314159265 271828182 141421356 161803398 0 777777777 255255255 536870912 998244353

555555555

321654987

1000000000

789456123

[出力例]

3316905982

2811735560

5542639502

4275864946

4457360498

※AtCoderテストケースより

[入力例]

20 5

31 41 5 9 26 53 5 89 79 3 23 8 4 62 6 4 33 8 32 7

[出力例]

418

410

424

614

880

[入力例]

50 10

432 253 635 391 609 376 699 1147 868 743 1134 13 1020 170 377 224 63 1075 493 814 543 125 200 389 1111 971 1201 869 1008 553 1066 718 573 917 657 822 156 823 286 667 124 318 455 1208 399 251 190 74 1032 16

745

865

308

718

725

1362

753

1065

106

532

[出力例]

16834

19026

18192

16452

16550

38842

16962

24966

24474

15580

[入力例]

100 20

1803 8552 1725 9877 6771 9125 5772 11782 11128 12113 7042 10138 6032 9172 6314 3764 6937 1890 1272 9446 6824 2119 9519 9323 10070 4772 9204 348 2247 354 6407 11843 5199 8523 3456 10969 10723 8382 9282 5975 12204 2284 2439 8162 12288 1247 8208 8505 3083 7978 11199 3294 8426 1079 6657 10610 11825 1156 6909 4633 6636 90 12222 2226 6813 2537 6725 8666 8031 10913 9074 544 1337 8284 3677 4406 9826 10673 6716 3174 2796 11006 12305 9376 6602 7472 2588 11044 6210 3100 1661 8277 10858 9201 3965 11476 4149 5037 7017 5033

1500

1782

4834

5555

3867

510

777

534

4581

1334

2872

577

216

2990

165

999

[出力例]

532269

509501

347337

669623

325615

385395

620599

595967

667723

618343

356425

545887

660927

436063

614367

668223

648775

429219

653773

575543

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

2022年6月12日

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

C++の練習を兼ねて, AtCoder Regular Contest 039 の問題C (幼稚園児高橋君) を解いてみた.

■感想.
1. 問題Cは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 近傍情報を更新しながら, 移動先を計算するロジックが, 興味深く思った.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://www.slideshare.net/chokudai/arc039
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using P = pair<LL, LL>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define a first
#define b second

// 四方位(近傍情報).
struct Quadrant{
    P u; // 上.
    P d; // 下.
    P l; // 左.
    P r; // 右.
};

int main(){
    
    // 1. 入力情報.
    int K;
    char c[202020];
    scanf("%d %s", &K, c);
    string S(c);
    
    // 2. TLE版.
    // -> 移動回数が少ない場合のチェック用としての実装.
    /*
    set<P> st;
    LL x = 0, y = 0;
    rep(i, S.size()){
        // 現在位置.
        if(!st.count({x, y})) st.insert({x, y});
        
        // 移動.
        // -> 登録済みの座標は, Skip.
        // 上.
        if(S[i] == 'U'){
            ++y;
            while(st.count({x, y})) ++y;
        }
        
        // 下.
        if(S[i] == 'D'){
            --y;
            while(st.count({x, y})) --y;
        }
        
        // 左.
        if(S[i] == 'L'){
            --x;
            while(st.count({x, y})) --x;
        }
        
        // 右.
        if(S[i] == 'R'){
            ++x;
            while(st.count({x, y})) ++x;
        }
    }
    printf("%lld %lld\n", x, y);
    */
    
    // 3. 近傍情報更新.
    auto f = [&](map<P, Quadrant> &m, P cur){
        // 各方向で, 訪問済, 未訪問 に分けて, 更新.
        // 上.
        P u = m[cur].u;
        if(m.count(u)) m[u].d = m[cur].d;
        if(!m.count(u)){
            m[u].u = {u.a + 0, u.b + 1};
            m[u].d = m[cur].d;
            m[u].l = {u.a - 1, u.b + 0};
            m[u].r = {u.a + 1, u.b + 0};
        }
        
        // 下.
        P d = m[cur].d;
        if(m.count(d)) m[d].u = m[cur].u;
        if(!m.count(d)){
            m[d].u = m[cur].u;
            m[d].d = {d.a + 0, d.b - 1};
            m[d].l = {d.a - 1, d.b + 0};
            m[d].r = {d.a + 1, d.b + 0};
        }
        
        // 左.
        P l = m[cur].l;
        if(m.count(l)) m[l].r = m[cur].r;
        if(!m.count(l)){
            m[l].u = {l.a + 0, l.b + 1};
            m[l].d = {l.a + 0, l.b - 1};
            m[l].l = {l.a - 1, l.b + 0};
            m[l].r = m[cur].r;
        }
        
        // 右.
        P r = m[cur].r;
        if(m.count(r)) m[r].l = m[cur].l;
        if(!m.count(r)){
            m[r].u = {r.a + 0, r.b + 1};
            m[r].d = {r.a + 0, r.b - 1};
            m[r].l = m[cur].l;
            m[r].r = {r.a + 1, r.b + 0};
        }
    };
    
    // 4. 格子点を移動.
    map<P, Quadrant> m;
    P cur = {0LL, 0LL};
    rep(i, S.size()){
        // 4-1. 訪問済み.
        if(m.count(cur)) f(m, cur);
        
        // 4-2. 未訪問.
        if(!m.count(cur)){
            // 現在位置.
            m[cur].u = {cur.a + 0, cur.b + 1};
            m[cur].d = {cur.a + 0, cur.b - 1};
            m[cur].l = {cur.a - 1, cur.b + 0};
            m[cur].r = {cur.a + 1, cur.b + 0};
            
            // 近傍情報更新.
            f(m, cur);
        }
        
        // 4-3. 移動.
        // 上.
        if(S[i] == 'U') cur = m[cur].u;
        
        // 下.
        if(S[i] == 'D') cur = m[cur].d;
        
        // 左.
        if(S[i] == 'L') cur = m[cur].l;
        
        // 右.
        if(S[i] == 'R') cur = m[cur].r;
    }
    
    // 5. 出力.
    printf("%lld %lld\n", cur.a, cur.b);
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using P = pair<LL, LL>;

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

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

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

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

#define a first

#define b second

// 四方位(近傍情報).

struct Quadrant{

P u; // 上.

P d; // 下.

P l; // 左.

P r; // 右.

};

int main(){

// 1. 入力情報.

int K;

char c[202020];

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

string S(c);

// 2. TLE版.

// -> 移動回数が少ない場合のチェック用としての実装.

set<P> st;

LL x = 0, y = 0;

rep(i, S.size()){

// 現在位置.

if(!st.count({x, y})) st.insert({x, y});

// 移動.

// -> 登録済みの座標は, Skip.

// 上.

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

++y;

while(st.count({x, y})) ++y;

}

// 下.

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

--y;

while(st.count({x, y})) --y;

}

// 左.

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

--x;

while(st.count({x, y})) --x;

}

// 右.

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

++x;

while(st.count({x, y})) ++x;

}

printf("%lld %lld\n", x, y);

// 3. 近傍情報更新.

auto f = [&](map<P, Quadrant> &m, P cur){

// 各方向で, 訪問済, 未訪問に分けて, 更新.

// 上.

P u = m[cur].u;

if(m.count(u)) m[u].d = m[cur].d;

if(!m.count(u)){

m[u].u = {u.a + 0, u.b + 1};

m[u].d = m[cur].d;

m[u].l = {u.a - 1, u.b + 0};

m[u].r = {u.a + 1, u.b + 0};

}

// 下.

P d = m[cur].d;

if(m.count(d)) m[d].u = m[cur].u;

if(!m.count(d)){

m[d].u = m[cur].u;

m[d].d = {d.a + 0, d.b - 1};

m[d].l = {d.a - 1, d.b + 0};

m[d].r = {d.a + 1, d.b + 0};

}

// 左.

P l = m[cur].l;

if(m.count(l)) m[l].r = m[cur].r;

if(!m.count(l)){

m[l].u = {l.a + 0, l.b + 1};

m[l].d = {l.a + 0, l.b - 1};

m[l].l = {l.a - 1, l.b + 0};

m[l].r = m[cur].r;

}

// 右.

P r = m[cur].r;

if(m.count(r)) m[r].l = m[cur].l;

if(!m.count(r)){

m[r].u = {r.a + 0, r.b + 1};

m[r].d = {r.a + 0, r.b - 1};

m[r].l = m[cur].l;

m[r].r = {r.a + 1, r.b + 0};

}

};

// 4. 格子点を移動.

map<P, Quadrant> m;

P cur = {0LL, 0LL};

rep(i, S.size()){

// 4-1. 訪問済み.

if(m.count(cur)) f(m, cur);

// 4-2. 未訪問.

if(!m.count(cur)){

// 現在位置.

m[cur].u = {cur.a + 0, cur.b + 1};

m[cur].d = {cur.a + 0, cur.b - 1};

m[cur].l = {cur.a - 1, cur.b + 0};

m[cur].r = {cur.a + 1, cur.b + 0};

// 近傍情報更新.

f(m, cur);

}

// 4-3. 移動.

// 上.

if(S[i] == 'U') cur = m[cur].u;

// 下.

if(S[i] == 'D') cur = m[cur].d;

// 左.

if(S[i] == 'L') cur = m[cur].l;

// 右.

if(S[i] == 'R') cur = m[cur].r;

}

// 5. 出力.

printf("%lld %lld\n", cur.a, cur.b);

return 0;

}

[入力例]
3
RLU

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

[入力例]
7
RURDRUL

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

[入力例]
25
RLRLRLRLRLRLURLRLRLRLRLRL

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

[入力例]
17
RRDDDLLULUUURRDUD

[出力例]
1 -2

[入力例]
50
ULUDRDUUDLUDLLDDUDLUDRULLRRUUDUUDUDDDURRDDDLLUURRR

[出力例]
5 4

[入力例]
300
LRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLR

[出力例]
150 0

[入力例]
500
URDDURUULUUDDUDDDDRURULDUDUUDURLRLDRRDDRUULLDURLRUDDUDLDDLULDRDUDDDURULUUULRDUURLUUDUDUURRDDLLURURRLRULLRUULRDLDRRRDLDDRDRDULUDULUUUDLDRRULLDDDDRRRRRDLDDLULLULRLURLRDLLLUURRULDRURDLLLDLRUUUUDLLDDLUURDDRDLRDLRDDRDRRLDLRRLUUDUUULRDDDLRRULRRDRULULLDLLUDUDLDRUUURRDDLUUULRLRRLULUUDDLDLLRLLUURDRLULUDDDUDRUUDRDLLULRLRLURRDLRULDLUDRRLDURUDLRRDUULLULULDRLULURLLDDUDDRURDRLURULLUDUURLUULDLRLLLDRUULDLRDDLLDULDLDRRRDDLUDRRDDLDRRRUDLRRRLLLDRLUDDRRDDRDDRLRRRURDDUUUURLLRRLDLRDDLDLLLUDDUUURURUULLLDDDLURRLLDLRDUL

[出力例]
-19 30

[入力例]
5000
LLLUULDRRLRDLRLDUULLDLRRLDRDUUDURRRUDDDLUDRDDUDLRRRLDDLLLURRRRLRDDDUDUURRDLRLULLURDDRLUDRRULRLLRRLRUDULUUUULUDRLUURUDRDLLURURURUURLRRDDURRDUDLUUDURRDUURRLDLRRRDDRDRLDUULLLULRLLULDDDUULRULRRDDUUUDRDDRDDDRRRULLDLUURLURUDRULDDDDUDURDUULRLRDDRUULDRLULLUDDUDDDLDUUDUDURUDRDLURRDRLLRRRULLDUDURRLDULLRDLLULLLLRDURURRDRLLRURDULRDULDDURUURRUDLLRLLRUUULLUURDULUDDDUDRDDUUDRUULRUUURDLRRUDDDDRUUURRULLDRLUDDLLUDRRDLDURULUDRDDRDDRRULRDUULURRLRDRRUDDUDRRDUDLDDUURUDRRLRDUUDRRDDDULRLRRULURUDRRLLDLRRUDLDRURULURRLUDRDDDDRUDLRUDDDRUDRDUULRLRLLDDLRDLLRULDUDDRRULDDULURRLUURLUUDDLUDLDLLRULULLLDDULURUDRUURLULURRDLRURLRLRDUUUDRURRLDDDLLUURLDRLRLLDLLURRUDDUURRRRUUURDLDLURLURDRLRDDDRRULLUULDUUURLLRDDRUURLUDDLRURURLURRURRUUULRURRLDRDURRLRRDRURULDLRUDDLRLRLUDLDUULDRUULDRULDULLRRURLRDLRURLRDRLRUDULUUUDDRRRUURLLRLLDLDURDULLRRRUDRULLUUDDRDLDRDDDLULRDURULLDLUUDRDULLRLLURDLURRLDDDDLDDDULLUURDLRURRLRRLUUUDDURDULULLUUULUURRUULLDURUDUURDURULLLRRULRRDULLDUDUUULDLUULDRULRULLUUURLURRLRDLRRRDURRLDRRURRLUURUUDUUULRUUUDURLLULLRLRULDRRLLRDLDDLRLDLDRLUDDDDDUUURLRRUDLLDRURRLLDLRLLRDRDLDUURLRUURUULURDLLLUDRDRDLLRRRRUURURRRULDURLURDDLLUURRRRRURLRLDUDUDUULRDRUDLDRULLUURRLLULDDDRULUDRDULRLLUUDLRRURLDULLDULLDLRRULUUULDLUDDRDUDDLRRURUDLUURLUDDLRURLLDRDULDRURRURRRRRRRUURLLDDULURURUDRURLLDDDRRULDRLRULULDRLRUDLDRLUUUDLDUDUURDRDLURLRDUULRUULLLDRLDURLURLDURUUUUDRLLDRRULUURRLRULLLRURRRLLDDULDLLURRULUDUDULDURDULUUDRUULLDLLRDLDLLLDRURRUDLDDDDURDLRLRRDLDLUDULDRUUDRDUULLULDLLRDRUDUULURUULURLRRUURULRLRLDLRURUDLDDUDDDDULDDRLDUUDLRRLUURURLDULULURLDDULLLDUURRDDURRUDRDULRURDURUDLDRDDURLUDLRRLDLDRUDRRDDRLDURURRUDLLLURRDRRDLLUDUDRUDRRURURRRURLUUUUDDUULLDRLRLDRULDDLRURRRDLRLDDDDDDURLLUDLDURURLRDRDUULLDUDDUDUDDDLLLDDLDULDURRLLLRRRLULUDRULDUDRDRUDLRLLRURUDULURDRLULRDDUUDULDDLDULLRLUDLRULRURUURRDRDUUULRRURUDLRDDRDRULLRULULRDLDLUUURRRLRDRDDLDDLULRULLDLRRDLLLDLDUDDURDRULUDDRRRURDLLDURLLURDUUDLRDRDUUUURRLLLURRLDUDDRRDDLRURUDRURDRULRDRUDUDLDUDRDRUUDRURDUDLLURULUDRRDDDULDUDDULDDRRDUDRURUDRDLRRLDDLRDUDRDRUURULURDLUDDULDRLLDURULDRDRULDRLLLUDDLURLDLLDUDRDUDUUUUULURURLLDRURURUULRLDULLDULRRDRLRUDLRULDURLUDLDDUDRLULRLUDUDLDLDRURRRLRDULLDDDDRULUDRLRLDURLDRRDLDLDRDDUDUUDRURULRRLUDRRDDLURURDUDUURUURLDRLLLDULLRLDLUDUULUDUDDDDDUDLDURUULLUDUDULULLRLLDUDULLDDRLLDRRLRURUDRULRLUUUUUDLLDDDLULRULDRUDUUURLLDLDULLRRLLDUDLULLRRULLDDDLDLLDDRLLULLULLRDLLLULURDRDURUDDLDUUURRUURRUDULRRLRUDRDDRLRRDDURRLLRDULURRDLRRLRUDDRULRRRULDURLRRRLDLRDUDDDUUUURRDLLDLDLDDRRURRRDDLRRDRRUDLLLLDRDULLDUURDRRLLRUDLLUDUDRURRRLDUUDDDUUULULDLDDLULLUULRRRURLRRLDRRRULDLRRLULURRDDRLULLDDUULRDDUULLRDUURRDRLDRRLLRDLLDRUDRDLRLULLDUULUDDLLLRLLLRDURLURUDUDLRLURUUDUURRLDUDRUUDDURRUDDDLRUDURUULRLDLRRUDRURRUDURDUUDUUURDLUUULLDRLUDRLRDLDULLRDDDLDRRLRRURLDUDUURDDLDLURRDRULDRDDDRDUDRLULUDDDUURDRLLRDDLLLLDRRRLDRDURDLDLUDDURLUDDDULDUDLLDLLDLRLDURUULRLLRRRURULRLLRUDRDLLDLDUDDLRRULDRLDLLRDRURDLLLURRDLULURLULRUDRURDURRUURUUDDLDLDDRLRULRDRRURLDRULDRDRRLUDLULRLUDLRUDLRUULUULRDRLRLDLLRDLDLRURUDDLDRDUURDLULLULRRUUULUUDLURLDRRURLURLRRDDRRRDRUDRLRLDRLDLDDDLURLLDLRRLDLLLUUDLULURRURRRURRDLRDLRLULRDDLUDDURUUDDURUDLRULLRLLLDUUUUDRRURRURRRRDUUDURULULRRLDRDRLLULRRURRRRUDRRDRUDLULLRRLLRRULULDRRLURUDRDDLLUUDLLLDUDLLDUUUDLLLRRRULUURDDULULUURUDDURLLDDUURDLUURRDLDRDULRDURRUUDLLUDDRLLRRULRRLULLDRLRDDDUDUURUDRRRLULRLUDRLRRLRULUUUUUURUDULULDDDLLDRULUUDDLLRRRRLRDLLRRURDDDUDRLDDLDDDLRDLLRLLLLRURRURRDRUDDRUDULRDDDRLURDRUUDDUDDULRUURDUDDRLRLRLDUUDRLURLDUULLULLLRDDDULRRRLULLDRUULURRRDDDDURDDULRDDLUDDUDRRUDDDRUUDDUDDLLRDURLLDURRRLDLULRDUDURUUDUDUDDLLLDLURDRLDLDLUURDDRRRLDLLRLDRRDUDLDRLRRLLLLDDRULDUDRRDRRDURDLLRUUDDURRLDURDULLUDDULRLLLDDRRLRDRDRURRDRULDDDDRLDLDRDDULDDLLRUDUDLRLULRLURLLRRDUDURUDURDDUDDLUUURDRLLDRLUURRLRULRDDLULDDUUDUULDDURRRDDURRDUUDRLLURLURLRLURLDUURLULURRULUUDLUDLDUDDDUULLRDDRDLDDDRUDLDDDRULRRRURRLDRUDDLRLRDULDLUURDRRUUULDDLDURULRULRRURLRULDDDDURULUDLLUULLDULUDRLURDULRDDUDURULLDLLDRRLRRRLLUDDDDDDLUUDDRLRLRRRLUDDLLRLDDRLDRRLLUUULLULDRULLLDULUDUDDLRULRDDDRRUDDRRLDULRLDURLULDLDULLRLURLDRLLLLDDLULUUDDLDDDDRULURDDDULDURLLDDDUDRUUULDLDLLLUDRRLDRDUURUDLRLULURURLLDULRLUDRRUDRLDDRRDULRULRULDDDRDUDULUDLLDULDUURLLUDURRLURURRDRRDLLDDLLUDDLDUURDLLLLRDLLRUURRUULLRDUUDDDDDRLDRRRDUDUURRRDURLULRRDUDLLLDURRLULLRRDDLUDRDRRURDRDUULDLDRUUUDLRLLLDUULRUUUULRDRUUUURUULURDURLUULDDDRLRUDDLRRULURRLLDLDURRLRRUDURDRLDURURDDLDUDRDRRRLRRLLDRDRLUUUDLRUUUDUURULRLLLLDLLLLUDUULRLURLRRRLUDDRRDDURDURLUDRRLLURLRUULLUDUURRDLDLDUDUDUDDDULRDRUURRDRUURRDURDLDURRUDDRLLUDRDURUDULLUUUURDUDRDLLLURUDUDDLLLLRRLURRRDLLULRURDRULRDLDURDDRLLLDLRDLDLLUDUUULUUUURRUDDUDRRLRRRDURULRURUUUDLRUDULDLUUUUDDDLLLUDDLLDRRRUDDUUUDDRRDRLRLURRLDUURRDLULRDUURDRDUDDDRDDDLLRDRLDRDRDLURULDLDDDDRRDRDUDULDDDRDURDLURRRUUDUDDRRRDDRDURRLULRLLDDRLURURRDULULRLLDURLDRDUDRDUDLLULDUDDURRDLLDRDUDUUULRRLDRDLRDULDUUDLULULRURULRRLRRRRLURRLLLDUULULURLLURLURDDDURUDLRDLLDUUDDDDUDRDURLLUUDDLLLDLRRLRRRLURULRLRRRUULDRRUURDRUDUULURLRUUDDLUDRUDRUUUUDURDLRLDDULDLRRRULUDULRRULDLRURUURDLLLDRULLRLULDULDDRULRDLDULLLDRDRURDUUDUULDULDLUUDRLRLRLUULLRDRRLLLRULLULUUDDDLRLDUUDRRRRLURULLRULURUDULRUDRLRDURLRLUULURDULRRRLLRLUDDDDLDLRRRUDRRULRDRULULUDRRLLLDRDRUULUUR

[出力例]
63 32

[入力例]

RLU

[出力例]

-1 1

※AtCoderテストケースより

[入力例]

RURDRUL

[出力例]

0 1

※AtCoderテストケースより

[入力例]

RLRLRLRLRLRLURLRLRLRLRLRL

[出力例]

-12 1

※AtCoderテストケースより

[入力例]

RRDDDLLULUUURRDUD

[出力例]

1 -2

[入力例]

ULUDRDUUDLUDLLDDUDLUDRULLRRUUDUUDUDDDURRDDDLLUURRR

[出力例]

5 4

[入力例]

300

LRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLRLR

[出力例]

150 0

[入力例]

500

URDDURUULUUDDUDDDDRURULDUDUUDURLRLDRRDDRUULLDURLRUDDUDLDDLULDRDUDDDURULUUULRDUURLUUDUDUURRDDLLURURRLRULLRUULRDLDRRRDLDDRDRDULUDULUUUDLDRRULLDDDDRRRRRDLDDLULLULRLURLRDLLLUURRULDRURDLLLDLRUUUUDLLDDLUURDDRDLRDLRDDRDRRLDLRRLUUDUUULRDDDLRRULRRDRULULLDLLUDUDLDRUUURRDDLUUULRLRRLULUUDDLDLLRLLUURDRLULUDDDUDRUUDRDLLULRLRLURRDLRULDLUDRRLDURUDLRRDUULLULULDRLULURLLDDUDDRURDRLURULLUDUURLUULDLRLLLDRUULDLRDDLLDULDLDRRRDDLUDRRDDLDRRRUDLRRRLLLDRLUDDRRDDRDDRLRRRURDDUUUURLLRRLDLRDDLDLLLUDDUUURURUULLLDDDLURRLLDLRDUL

[出力例]

-19 30

[入力例]

5000

LLLUULDRRLRDLRLDUULLDLRRLDRDUUDURRRUDDDLUDRDDUDLRRRLDDLLLURRRRLRDDDUDUURRDLRLULLURDDRLUDRRULRLLRRLRUDULUUUULUDRLUURUDRDLLURURURUURLRRDDURRDUDLUUDURRDUURRLDLRRRDDRDRLDUULLLULRLLULDDDUULRULRRDDUUUDRDDRDDDRRRULLDLUURLURUDRULDDDDUDURDUULRLRDDRUULDRLULLUDDUDDDLDUUDUDURUDRDLURRDRLLRRRULLDUDURRLDULLRDLLULLLLRDURURRDRLLRURDULRDULDDURUURRUDLLRLLRUUULLUURDULUDDDUDRDDUUDRUULRUUURDLRRUDDDDRUUURRULLDRLUDDLLUDRRDLDURULUDRDDRDDRRULRDUULURRLRDRRUDDUDRRDUDLDDUURUDRRLRDUUDRRDDDULRLRRULURUDRRLLDLRRUDLDRURULURRLUDRDDDDRUDLRUDDDRUDRDUULRLRLLDDLRDLLRULDUDDRRULDDULURRLUURLUUDDLUDLDLLRULULLLDDULURUDRUURLULURRDLRURLRLRDUUUDRURRLDDDLLUURLDRLRLLDLLURRUDDUURRRRUUURDLDLURLURDRLRDDDRRULLUULDUUURLLRDDRUURLUDDLRURURLURRURRUUULRURRLDRDURRLRRDRURULDLRUDDLRLRLUDLDUULDRUULDRULDULLRRURLRDLRURLRDRLRUDULUUUDDRRRUURLLRLLDLDURDULLRRRUDRULLUUDDRDLDRDDDLULRDURULLDLUUDRDULLRLLURDLURRLDDDDLDDDULLUURDLRURRLRRLUUUDDURDULULLUUULUURRUULLDURUDUURDURULLLRRULRRDULLDUDUUULDLUULDRULRULLUUURLURRLRDLRRRDURRLDRRURRLUURUUDUUULRUUUDURLLULLRLRULDRRLLRDLDDLRLDLDRLUDDDDDUUURLRRUDLLDRURRLLDLRLLRDRDLDUURLRUURUULURDLLLUDRDRDLLRRRRUURURRRULDURLURDDLLUURRRRRURLRLDUDUDUULRDRUDLDRULLUURRLLULDDDRULUDRDULRLLUUDLRRURLDULLDULLDLRRULUUULDLUDDRDUDDLRRURUDLUURLUDDLRURLLDRDULDRURRURRRRRRRUURLLDDULURURUDRURLLDDDRRULDRLRULULDRLRUDLDRLUUUDLDUDUURDRDLURLRDUULRUULLLDRLDURLURLDURUUUUDRLLDRRULUURRLRULLLRURRRLLDDULDLLURRULUDUDULDURDULUUDRUULLDLLRDLDLLLDRURRUDLDDDDURDLRLRRDLDLUDULDRUUDRDUULLULDLLRDRUDUULURUULURLRRUURULRLRLDLRURUDLDDUDDDDULDDRLDUUDLRRLUURURLDULULURLDDULLLDUURRDDURRUDRDULRURDURUDLDRDDURLUDLRRLDLDRUDRRDDRLDURURRUDLLLURRDRRDLLUDUDRUDRRURURRRURLUUUUDDUULLDRLRLDRULDDLRURRRDLRLDDDDDDURLLUDLDURURLRDRDUULLDUDDUDUDDDLLLDDLDULDURRLLLRRRLULUDRULDUDRDRUDLRLLRURUDULURDRLULRDDUUDULDDLDULLRLUDLRULRURUURRDRDUUULRRURUDLRDDRDRULLRULULRDLDLUUURRRLRDRDDLDDLULRULLDLRRDLLLDLDUDDURDRULUDDRRRURDLLDURLLURDUUDLRDRDUUUURRLLLURRLDUDDRRDDLRURUDRURDRULRDRUDUDLDUDRDRUUDRURDUDLLURULUDRRDDDULDUDDULDDRRDUDRURUDRDLRRLDDLRDUDRDRUURULURDLUDDULDRLLDURULDRDRULDRLLLUDDLURLDLLDUDRDUDUUUUULURURLLDRURURUULRLDULLDULRRDRLRUDLRULDURLUDLDDUDRLULRLUDUDLDLDRURRRLRDULLDDDDRULUDRLRLDURLDRRDLDLDRDDUDUUDRURULRRLUDRRDDLURURDUDUURUURLDRLLLDULLRLDLUDUULUDUDDDDDUDLDURUULLUDUDULULLRLLDUDULLDDRLLDRRLRURUDRULRLUUUUUDLLDDDLULRULDRUDUUURLLDLDULLRRLLDUDLULLRRULLDDDLDLLDDRLLULLULLRDLLLULURDRDURUDDLDUUURRUURRUDULRRLRUDRDDRLRRDDURRLLRDULURRDLRRLRUDDRULRRRULDURLRRRLDLRDUDDDUUUURRDLLDLDLDDRRURRRDDLRRDRRUDLLLLDRDULLDUURDRRLLRUDLLUDUDRURRRLDUUDDDUUULULDLDDLULLUULRRRURLRRLDRRRULDLRRLULURRDDRLULLDDUULRDDUULLRDUURRDRLDRRLLRDLLDRUDRDLRLULLDUULUDDLLLRLLLRDURLURUDUDLRLURUUDUURRLDUDRUUDDURRUDDDLRUDURUULRLDLRRUDRURRUDURDUUDUUURDLUUULLDRLUDRLRDLDULLRDDDLDRRLRRURLDUDUURDDLDLURRDRULDRDDDRDUDRLULUDDDUURDRLLRDDLLLLDRRRLDRDURDLDLUDDURLUDDDULDUDLLDLLDLRLDURUULRLLRRRURULRLLRUDRDLLDLDUDDLRRULDRLDLLRDRURDLLLURRDLULURLULRUDRURDURRUURUUDDLDLDDRLRULRDRRURLDRULDRDRRLUDLULRLUDLRUDLRUULUULRDRLRLDLLRDLDLRURUDDLDRDUURDLULLULRRUUULUUDLURLDRRURLURLRRDDRRRDRUDRLRLDRLDLDDDLURLLDLRRLDLLLUUDLULURRURRRURRDLRDLRLULRDDLUDDURUUDDURUDLRULLRLLLDUUUUDRRURRURRRRDUUDURULULRRLDRDRLLULRRURRRRUDRRDRUDLULLRRLLRRULULDRRLURUDRDDLLUUDLLLDUDLLDUUUDLLLRRRULUURDDULULUURUDDURLLDDUURDLUURRDLDRDULRDURRUUDLLUDDRLLRRULRRLULLDRLRDDDUDUURUDRRRLULRLUDRLRRLRULUUUUUURUDULULDDDLLDRULUUDDLLRRRRLRDLLRRURDDDUDRLDDLDDDLRDLLRLLLLRURRURRDRUDDRUDULRDDDRLURDRUUDDUDDULRUURDUDDRLRLRLDUUDRLURLDUULLULLLRDDDULRRRLULLDRUULURRRDDDDURDDULRDDLUDDUDRRUDDDRUUDDUDDLLRDURLLDURRRLDLULRDUDURUUDUDUDDLLLDLURDRLDLDLUURDDRRRLDLLRLDRRDUDLDRLRRLLLLDDRULDUDRRDRRDURDLLRUUDDURRLDURDULLUDDULRLLLDDRRLRDRDRURRDRULDDDDRLDLDRDDULDDLLRUDUDLRLULRLURLLRRDUDURUDURDDUDDLUUURDRLLDRLUURRLRULRDDLULDDUUDUULDDURRRDDURRDUUDRLLURLURLRLURLDUURLULURRULUUDLUDLDUDDDUULLRDDRDLDDDRUDLDDDRULRRRURRLDRUDDLRLRDULDLUURDRRUUULDDLDURULRULRRURLRULDDDDURULUDLLUULLDULUDRLURDULRDDUDURULLDLLDRRLRRRLLUDDDDDDLUUDDRLRLRRRLUDDLLRLDDRLDRRLLUUULLULDRULLLDULUDUDDLRULRDDDRRUDDRRLDULRLDURLULDLDULLRLURLDRLLLLDDLULUUDDLDDDDRULURDDDULDURLLDDDUDRUUULDLDLLLUDRRLDRDUURUDLRLULURURLLDULRLUDRRUDRLDDRRDULRULRULDDDRDUDULUDLLDULDUURLLUDURRLURURRDRRDLLDDLLUDDLDUURDLLLLRDLLRUURRUULLRDUUDDDDDRLDRRRDUDUURRRDURLULRRDUDLLLDURRLULLRRDDLUDRDRRURDRDUULDLDRUUUDLRLLLDUULRUUUULRDRUUUURUULURDURLUULDDDRLRUDDLRRULURRLLDLDURRLRRUDURDRLDURURDDLDUDRDRRRLRRLLDRDRLUUUDLRUUUDUURULRLLLLDLLLLUDUULRLURLRRRLUDDRRDDURDURLUDRRLLURLRUULLUDUURRDLDLDUDUDUDDDULRDRUURRDRUURRDURDLDURRUDDRLLUDRDURUDULLUUUURDUDRDLLLURUDUDDLLLLRRLURRRDLLULRURDRULRDLDURDDRLLLDLRDLDLLUDUUULUUUURRUDDUDRRLRRRDURULRURUUUDLRUDULDLUUUUDDDLLLUDDLLDRRRUDDUUUDDRRDRLRLURRLDUURRDLULRDUURDRDUDDDRDDDLLRDRLDRDRDLURULDLDDDDRRDRDUDULDDDRDURDLURRRUUDUDDRRRDDRDURRLULRLLDDRLURURRDULULRLLDURLDRDUDRDUDLLULDUDDURRDLLDRDUDUUULRRLDRDLRDULDUUDLULULRURULRRLRRRRLURRLLLDUULULURLLURLURDDDURUDLRDLLDUUDDDDUDRDURLLUUDDLLLDLRRLRRRLURULRLRRRUULDRRUURDRUDUULURLRUUDDLUDRUDRUUUUDURDLRLDDULDLRRRULUDULRRULDLRURUURDLLLDRULLRLULDULDDRULRDLDULLLDRDRURDUUDUULDULDLUUDRLRLRLUULLRDRRLLLRULLULUUDDDLRLDUUDRRRRLURULLRULURUDULRUDRLRDURLRLUULURDULRRRLLRLUDDDDLDLRRRUDRRULRDRULULUDRRLLLDRDRUULUUR

[出力例]

63 32

■参照サイト
AtCoder Regular Contest 039

2022年6月11日

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

C++の練習を兼ねて, AtCoder Beginner Contest 179 の問題D (Leaping Tak) を解いてみた.

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

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

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

// 解き直し.
// https://atcoder.jp/contests/abc179/editorial/121
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using P = pair<int, int>;
using vp = vector<P>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
#define a first
#define b second
const LL MOD = 998244353;
LL dp[404040], pd[404040];

int main(){
    
    // 1. 入力情報.
    int N, K;
    scanf("%d %d", &N, &K);
    vp v;
    rep(i, K){
        P p;
        scanf("%d %d", &p.a, &p.b);
        v.pb(p);
    }
    
    // 2. dp更新.
    pd[0] = 1;
    repx(i, 1, N + 1){
        // f の 復元(累積和).
        pd[i] = pd[i - 1] + dp[i];
        pd[i] %= MOD;
        
        // dp[i] = f[i] - f[i - 1] を 設定.
        dp[i] = MOD + pd[i] - pd[i - 1];
        dp[i] %= MOD;
        
        // 各 j で, dp[i + l[j]], dp[i + r[j] + 1] を 設定.
        for(auto &p : v){
            dp[i + p.a] += pd[i];
            dp[i + p.a] %= MOD;
            dp[i + p.b + 1] += (MOD - pd[i]);
            dp[i + p.b + 1] %= MOD;
        }
    }
    
    // 3. 出力.
    printf("%lld\n", dp[N]);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc179/editorial/121

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using P = pair<int, int>;

using vp = vector<P>;

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

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

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

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

#define pb push_back

#define a first

#define b second

const LL MOD = 998244353;

LL dp[404040], pd[404040];

int main(){

// 1. 入力情報.

int N, K;

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

vp v;

rep(i, K){

P p;

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

v.pb(p);

}

// 2. dp更新.

pd[0] = 1;

repx(i, 1, N + 1){

// f の復元(累積和).

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

pd[i] %= MOD;

// dp[i] = f[i] - f[i - 1] を設定.

dp[i] = MOD + pd[i] - pd[i - 1];

dp[i] %= MOD;

// 各 j で, dp[i + l[j]], dp[i + r[j] + 1] を設定.

for(auto &p : v){

dp[i + p.a] += pd[i];

dp[i + p.a] %= MOD;

dp[i + p.b + 1] += (MOD - pd[i]);

dp[i + p.b + 1] %= MOD;

}

// 3. 出力.

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

return 0;

}

[入力例]
5 2
1 1
3 4

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

[入力例]
5 2
3 3
5 5

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

[入力例]
5 1
1 2

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

[入力例]
60 3
5 8
1 3
10 15

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

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

[出力例]
123

[入力例]
20 5
2 2
6 7
9 10
13 15
18 19

[出力例]
66

[入力例]
33 7
5 6
11 12
15 18
22 22
25 27
28 29
30 31

[出力例]
102

[入力例]
123 7
3 3
7 7
13 15
27 28
35 36
51 57
75 77

[出力例]
184056934

[入力例]

5 2

1 1

3 4

[出力例]

※AtCoderテストケースより

[入力例]

5 2

3 3

5 5

[出力例]

※AtCoderテストケースより

[入力例]

5 1

1 2

[出力例]

※AtCoderテストケースより

[入力例]

60 3

5 8

1 3

10 15

[出力例]

221823067

※AtCoderテストケースより

[入力例]

10 3

1 2

4 5

7 7

[出力例]

123

[入力例]

20 5

2 2

6 7

9 10

13 15

18 19

[出力例]

[入力例]

33 7

5 6

11 12

15 18

22 22

25 27

28 29

30 31

[出力例]

102

[入力例]

123 7

3 3

7 7

13 15

27 28

35 36

51 57

75 77

[出力例]

184056934

■参照サイト
AtCoder Beginner Contest 179

2022年6月10日

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

C++の練習を兼ねて, AtCoder Beginner Contest 180 の問題D (Takahashi Unevolved) を解いてみた.

■感想.
1. 問題Dは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 解説にあるように, カコモンジムへ通う回数を, 最大64回に固定して, シミュレーションしていく解法が, 非常に面白く感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/abc180/editorial/219
// 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, A, B;
    scanf("%lld %lld %lld %lld", &X, &Y, &A, &B);
    
    // 2. 経験値の最大値は？
    // -> 強さ, 経験値 を シュミレート.
    LL ans = 0;
    rep(i, 65){
        // カコモンジムへ通う.
        LL s = X, e = 0;
        while(s < Y && e < i){
            // オーバーフロー防止.
            if(Y / A <= s) break;
            
            // 強さ A倍.
            s *= A;
            
            // 経験値増加.
            ++e;
        };
        
        // 強さが, Y以上になっているか？
        if(s >= Y){
            // 強さ (1 / A)倍.
            s /= A;
            
            // 経験値減少.
            --e;
        }
        
        // AtCoderジムへ通う.
        e += max(0LL, Y - 1 - s) / B;
        
        // 最大値更新.
        ans = max(ans, e);
    }
    
    // 3. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc180/editorial/219

// 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, A, B;

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

// 2. 経験値の最大値は？

// -> 強さ, 経験値をシュミレート.

LL ans = 0;

rep(i, 65){

// カコモンジムへ通う.

LL s = X, e = 0;

while(s < Y && e < i){

// オーバーフロー防止.

if(Y / A <= s) break;

// 強さ A倍.

s *= A;

// 経験値増加.

++e;

};

// 強さが, Y以上になっているか？

if(s >= Y){

// 強さ (1 / A)倍.

s /= A;

// 経験値減少.

--e;

}

// AtCoderジムへ通う.

e += max(0LL, Y - 1 - s) / B;

// 最大値更新.

ans = max(ans, e);

}

// 3. 出力.

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

return 0;

}

[入力例]
4 20 2 10

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

[入力例]
1 1000000000000000000 10 1000000000

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

[入力例]
3 1415926535 8 979

[出力例]
1446300

[入力例]
2022 20220610 2 123

[出力例]
164378

[入力例]
1732050 8075688 7 72935

[出力例]
86

[入力例]
22360 679774997896964091 7 36687312762

[出力例]
18528891

[入力例]

4 20 2 10

[出力例]

※AtCoderテストケースより

[入力例]

1 1000000000000000000 10 1000000000

[出力例]

1000000007

※AtCoderテストケースより

[入力例]

3 1415926535 8 979

[出力例]

1446300

[入力例]

2022 20220610 2 123

[出力例]

164378

[入力例]

1732050 8075688 7 72935

[出力例]

[入力例]

22360 679774997896964091 7 36687312762

[出力例]

18528891

■参照サイト
AtCoder Beginner Contest 180

2022年6月9日

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

C++の練習を兼ねて, AtCoder Regular Contest 139 の問題A (Trailing Zeros) ～問題B (Make N) を解いてみた.

■感想.
1. 問題Bは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

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

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N){
        int t;
        scanf("%d", &t);
        cPow2[i] = (1LL << t);
    }
    
    // 2. 数列 A を 構成.
    LL ans = cPow2[0];
    repx(i, 1, N){
        // 前回分結果を参照.
        LL q = ans / cPow2[i];
        LL r = ans % cPow2[i];
        
        // 余りがある.
        if(r) ++q;
        
        // 今回分候補.
        LL s = q * cPow2[i];
        
        // 大小比較.
        if(s <= ans) s += cPow2[i];
        
        // bit調整.
        if(!(s & cPow2[i])) s += cPow2[i];
        
        // 今回分更新.
        ans = s;
    }
    
    // 3. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

LL cPow2[101010];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

rep(i, N){

int t;

scanf("%d", &t);

cPow2[i] = (1LL << t);

}

// 2. 数列 A を構成.

LL ans = cPow2[0];

repx(i, 1, N){

// 前回分結果を参照.

LL q = ans / cPow2[i];

LL r = ans % cPow2[i];

// 余りがある.

if(r) ++q;

// 今回分候補.

LL s = q * cPow2[i];

// 大小比較.

if(s <= ans) s += cPow2[i];

// bit調整.

if(!(s & cPow2[i])) s += cPow2[i];

// 今回分更新.

ans = s;

}

// 3. 出力.

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

return 0;

}

[入力例]
4
0 1 3 2

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

[入力例]
5
4 3 2 1 0

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

[入力例]
1
40

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

[入力例]
8
2 0 2 2 0 4 2 4

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

[入力例]
12
2 0 2 2 0 6 0 8 2 3 5 9

[出力例]
512

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

[出力例]
117441536

[入力例]
100
0 7 2 36 22 14 3 7 5 5 13 35 6 0 27 34 28 12 33 33 0 32 36 1 4 18 19 20 29 7 23 32 19 38 37 24 36 6 4 9 0 10 29 36 11 32 39 2 0 17 22 24 15 0 23 32 1 15 31 0 6 38 6 18 16 5 8 9 7 15 12 9 8 34 31 36 5 7 39 11 10 21 8 5 28 30 14 25 31 39 0 27 4 3 28 30 29 24 2 5

[出力例]
3849918087200

[入力例]

0 1 3 2

[出力例]

※AtCoderのテストケースより

[入力例]

4 3 2 1 0

[出力例]

※AtCoderのテストケースより

[入力例]

[出力例]

1099511627776

※AtCoderのテストケースより

[入力例]

2 0 2 2 0 4 2 4

[出力例]

※AtCoderのテストケースより

[入力例]

2 0 2 2 0 6 0 8 2 3 5 9

[出力例]

512

[入力例]

23 4 17 9 10 23 15 22 19 9 20 22 24 12 1 14 4 14 17 21 17 20 11 15 15 2 2 14 16 18 0 5 1 18 22 5 14 5 20 8 13 21 8 20 0 6 13 24 24 10

[出力例]

117441536

[入力例]

100

0 7 2 36 22 14 3 7 5 5 13 35 6 0 27 34 28 12 33 33 0 32 36 1 4 18 19 20 29 7 23 32 19 38 37 24 36 6 4 9 0 10 29 36 11 32 39 2 0 17 22 24 15 0 23 32 1 15 31 0 6 38 6 18 16 5 8 9 7 15 12 9 8 34 31 36 5 7 39 11 10 21 8 5 28 30 14 25 31 39 0 27 4 3 28 30 29 24 2 5

[出力例]

3849918087200

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

// 解き直し.
// https://atcoder.jp/contests/arc139/editorial/3836
// 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. 入力情報.
    int T;
    scanf("%d", &T);
    
    // 2. テストケース.
    rep(i, T){
        // 操作情報.
        LL N, A, B, X, Y, Z;
        scanf("%lld %lld %lld %lld %lld %lld", &N, &A, &B, &X, &Y, &Z);
        
        // swap.
        if(Y * B > A * Z){
            swap(A, B);
            swap(Y, Z);
        }
        
        // コスト置き換え.
        Y = min(Y, A * X);
        Z = min(Z, B * X);
        
        // A で 全探索.
        LL ans = N * X;
        int u = sqrt(max({A, B, N, X, Y, Z})) + 1;
        rep(j, u + 1){
            // Skip.
            if(A * j > N) break;
            
            // 1 増加 … k 回.
            // A 増加 … j 回.
            LL k = N - A * j;
            ans = min(ans, X * k + Y * j);
        }
        
        // B で 全探索.
        rep(j, u + 1){
            // Skip.
            if(B * j > N) break;
            
            // 1 増加 … l 回.
            // A 増加 … k 回.
            // B 増加 … j 回.
            LL k = (N - B * j) / A;
            LL l = (N - B * j) % A;
            ans = min(ans, X * l + Y * k + Z * j);
        }
        
        // 出力.
        printf("%lld\n", ans);
    }
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc139/editorial/3836

// 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. 入力情報.

int T;

scanf("%d", &T);

// 2. テストケース.

rep(i, T){

// 操作情報.

LL N, A, B, X, Y, Z;

scanf("%lld %lld %lld %lld %lld %lld", &N, &A, &B, &X, &Y, &Z);

// swap.

if(Y * B > A * Z){

swap(A, B);

swap(Y, Z);

}

// コスト置き換え.

Y = min(Y, A * X);

Z = min(Z, B * X);

// A で全探索.

LL ans = N * X;

int u = sqrt(max({A, B, N, X, Y, Z})) + 1;

rep(j, u + 1){

// Skip.

if(A * j > N) break;

// 1 増加 … k 回.

// A 増加 … j 回.

LL k = N - A * j;

ans = min(ans, X * k + Y * j);

}

// B で全探索.

rep(j, u + 1){

// Skip.

if(B * j > N) break;

// 1 増加 … l 回.

// A 増加 … k 回.

// B 増加 … j 回.

LL k = (N - B * j) / A;

LL l = (N - B * j) % A;

ans = min(ans, X * l + Y * k + Z * j);

}

// 出力.

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

}

return 0;

}

[入力例]
5
10 3 5 2 3 6
10 3 5 1 1000000000 1000000000
139 2 139 1 1 1
139 1 1 1 1 1
139 7 10 3845 26982 30923

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

[入力例]
3
19 410 118 10 12 36
28 5 27 120 8 19
15 10 112 25 26 7

[出力例]
190
139
151

[入力例]
10
5 27 33 27 33 10
367 101 97 360 89 296
356 163 1670 2229 294 2104
22210 20463 1180 1423 7189 27349
96546 85717 99062 38671 64408 12833
428087 957323 524008 764193 831124 151120
2848490 8806972 3102003 4652749 7816487 1589401
2647523 1539654 6853977 1911564 2014335 9516618
417378 3673854 9480440 5925970 3262795 9490280
8960289 770367 364602 1730798 1749930 7559817

[出力例]
135
23307
67458
841379
418832667
327141088791
13253308999010
2117764511451
2473369506660
7082779836

[入力例]
20
6 20 87 64 34 7
82 8 17 96 34 9
308 143 331 229 216 156
407 125 205 150 333 367
3032 2513 2381 3514 3560 2087
3295 1839 1278 1709 2260 2581
3050 3254 4972 4036 6020 5585
5206 2806 5496 7172 3857 2522
5129 14571 10270 10633 7610 5848
8794 6857 14204 13178 5698 12289
23689 21296 23641 19172 23862 17712
26284 19956 21528 21533 26547 18181
47943 42530 37022 46535 46198 32736
30053 47292 34998 32635 30911 37386
214765 82103 226279 148757 72521 50203
115274 248505 25061 123613 174816 93462
748091 224818 872731 776979 327633 368494
885709 129641 646432 186800 1006696 172215
1247487 1840364 1971807 2229106 1738446 1319308
1871210 2216170 1482305 2121565 2133141 1368115

[出力例]
384
222
5470
5799
1827326
309043
12309800
17216657
54536657
25531484
937968
102429129
251940153
980779655
7521150205
1858277238
57215385522
20154848576
2780780756622
825088604440

[入力例]

10 3 5 2 3 6

10 3 5 1 1000000000 1000000000

139 2 139 1 1 1

139 1 1 1 1 1

139 7 10 3845 26982 30923

[出力例]

139

436604

※AtCoderのテストケースより

[入力例]

19 410 118 10 12 36

28 5 27 120 8 19

15 10 112 25 26 7

[出力例]

190

139

151

[入力例]

5 27 33 27 33 10

367 101 97 360 89 296

356 163 1670 2229 294 2104

22210 20463 1180 1423 7189 27349

96546 85717 99062 38671 64408 12833

428087 957323 524008 764193 831124 151120

2848490 8806972 3102003 4652749 7816487 1589401

2647523 1539654 6853977 1911564 2014335 9516618

417378 3673854 9480440 5925970 3262795 9490280

8960289 770367 364602 1730798 1749930 7559817

[出力例]

135

23307

67458

841379

418832667

327141088791

13253308999010

2117764511451

2473369506660

7082779836

[入力例]

6 20 87 64 34 7

82 8 17 96 34 9

308 143 331 229 216 156

407 125 205 150 333 367

3032 2513 2381 3514 3560 2087

3295 1839 1278 1709 2260 2581

3050 3254 4972 4036 6020 5585

5206 2806 5496 7172 3857 2522

5129 14571 10270 10633 7610 5848

8794 6857 14204 13178 5698 12289

23689 21296 23641 19172 23862 17712

26284 19956 21528 21533 26547 18181

47943 42530 37022 46535 46198 32736

30053 47292 34998 32635 30911 37386

214765 82103 226279 148757 72521 50203

115274 248505 25061 123613 174816 93462

748091 224818 872731 776979 327633 368494

885709 129641 646432 186800 1006696 172215

1247487 1840364 1971807 2229106 1738446 1319308

1871210 2216170 1482305 2121565 2133141 1368115

[出力例]

384

222

5470

5799

1827326

309043

12309800

17216657

54536657

25531484

937968

102429129

251940153

980779655

7521150205

1858277238

57215385522

20154848576

2780780756622

825088604440

■参照サイト
AtCoder Regular Contest 139

C++の練習を兼ねて, AtCoder Beginner Contest 256 の 問題C (Filling 3×3 array) ～ 問題E (Takahashi’s Anguish) を解いてみた.

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

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

C++の練習を兼ねて, AtCoder Beginner Contest 191 の 問題D (Circle Lattice Points) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 043 の 問題C (転倒距離) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 255 の 問題C (±1 Operation 1) ～ 問題D (±1 Operation 2) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 039 の 問題C (幼稚園児高橋君) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 179 の 問題D (Leaping Tak) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 180 の 問題D (Takahashi Unevolved) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 139 の 問題A (Trailing Zeros) ～ 問題B (Make N) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 256 の問題C (Filling 3×3 array) ～問題E (Takahashi’s Anguish) を解いてみた.

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

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

C++の練習を兼ねて, AtCoder Beginner Contest 191 の問題D (Circle Lattice Points) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 043 の問題C (転倒距離) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 255 の問題C (±1 Operation 1) ～問題D (±1 Operation 2) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 039 の問題C (幼稚園児高橋君) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 179 の問題D (Leaping Tak) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 180 の問題D (Takahashi Unevolved) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 139 の問題A (Trailing Zeros) ～問題B (Make N) を解いてみた.