C++ | 個人用メモ帳

2022年3月14日

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

C++の練習を兼ねて, AtCoder Beginner Contest 243 の問題C (Collision 2) ～問題D (Moves on Binary Tree) を解いてみた.

■感想.
1. 問題C, Dは, 方針を絞り込めたので, AC版に到達できたと思う.
2. 個人的には, 問題Dで, stack の考え方が使えたので, 非常に面白く感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using P = pair<int, 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 pb push_back
#define a first
#define b second
#define all(x) x.begin(), x.end()
int x[202020], y[202020];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    map<int, int> m;
    rep(i, N){
        scanf("%d %d", &x[i], &y[i]);
        m[y[i]]++;
    }
    char s[202020];
    scanf("%s", s);
    
    // 2. 座標圧縮.
    int idx = -1;
    for(auto &p : m) p.b = ++idx;
    
    // 3. グループ分け.
    vvp v(idx + 1);
    rep(i, N){
        // 左.
        if(s[i] == 'L') v[m[y[i]]].pb({x[i], -1});
        
        // 右.
        if(s[i] == 'R') v[m[y[i]]].pb({x[i], +1});
    }
    
    // 4. 衝突判定.
    bool ok = false;
    rep(i, idx + 1){
        // sort.
        sort(all(v[i]));
        
        // 左向きに移動する人のX座標(最大値).
        // 右向きに移動する人のX座標(最小値).
        int l = -1, r = 2020202020;
        for(auto &p : v[i]){
            if(p.b == 1) r = min(r, p.a);
            else         l = max(l, p.a);
        }
        
        // 判定.
        if(r < l){
            ok = true;
            break;
        }
    }
    
    // 5. 出力.
    printf("%s\n", ok ? "Yes" : "No");
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using P = pair<int, 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 pb push_back

#define a first

#define b second

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

int x[202020], y[202020];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

map<int, int> m;

rep(i, N){

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

m[y[i]]++;

}

char s[202020];

scanf("%s", s);

// 2. 座標圧縮.

int idx = -1;

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

// 3. グループ分け.

vvp v(idx + 1);

rep(i, N){

// 左.

if(s[i] == 'L') v[m[y[i]]].pb({x[i], -1});

// 右.

if(s[i] == 'R') v[m[y[i]]].pb({x[i], +1});

}

// 4. 衝突判定.

bool ok = false;

rep(i, idx + 1){

// sort.

sort(all(v[i]));

// 左向きに移動する人のX座標(最大値).

// 右向きに移動する人のX座標(最小値).

int l = -1, r = 2020202020;

for(auto &p : v[i]){

if(p.b == 1) r = min(r, p.a);

else l = max(l, p.a);

}

// 判定.

if(r < l){

ok = true;

break;

}

// 5. 出力.

printf("%s\n", ok ? "Yes" : "No");

return 0;

}

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

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

[入力例]
2
1 1
2 1
RR

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

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

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

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

[出力例]
Yes

[入力例]
7
5 1
10 2
11 3
18 4
15 3
11 2
8 1
LLRRLRL

[出力例]
Yes

[入力例]

2 3

1 1

4 1

RRL

[出力例]

Yes

※AtCoderテストケースより

[入力例]

1 1

2 1

[出力例]

※AtCoderテストケースより

[入力例]

1 3

1 4

0 0

0 2

0 4

3 1

2 4

4 2

4 4

3 3

RLRRRLRLRR

[出力例]

Yes

※AtCoderテストケースより

[入力例]

1 3

5 3

7 2

1 2

2 2

RRLLR

[出力例]

Yes

[入力例]

5 1

10 2

11 3

18 4

15 3

11 2

8 1

LLRRLRL

[出力例]

Yes

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pof pop_front
#define pob pop_back
#define puf push_front
#define pub push_back

int main(){
    
    // 1. 入力情報.
    int N;
    LL X;
    char s[1010101];
    scanf("%d %lld %s", &N, &X, s);
    
    // 2. 操作を保存.
    deque<char> dq;
    rep(i, N){
        // 空.
        if(dq.empty()){
            dq.pub(s[i]);
            continue;
        }
        
        // U.
        if(s[i] == 'U'){
            char c = dq.back();
            if(c != 'U') dq.pob();
            else         dq.pub(s[i]);
        }
        
        // L or R.
        if(s[i] != 'U') dq.pub(s[i]);
    }
    
    // 3. 移動.
    LL ans = X;
    while(!dq.empty()){
        char c = dq.front();
        dq.pof();
        
        // U.
        if(c == 'U') ans >>= 1;
        
        // L.
        if(c == 'L') ans <<= 1;
        
        // R.
        if(c == 'R') ans <<= 1, ++ans;
    }
    
    // 4. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

#define pof pop_front

#define pob pop_back

#define puf push_front

#define pub push_back

int main(){

// 1. 入力情報.

int N;

LL X;

char s[1010101];

scanf("%d %lld %s", &N, &X, s);

// 2. 操作を保存.

deque<char> dq;

rep(i, N){

// 空.

if(dq.empty()){

dq.pub(s[i]);

continue;

}

// U.

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

char c = dq.back();

if(c != 'U') dq.pob();

else dq.pub(s[i]);

}

// L or R.

if(s[i] != 'U') dq.pub(s[i]);

}

// 3. 移動.

LL ans = X;

while(!dq.empty()){

char c = dq.front();

dq.pof();

// U.

if(c == 'U') ans >>= 1;

// L.

if(c == 'L') ans <<= 1;

// R.

if(c == 'R') ans <<= 1, ++ans;

}

// 4. 出力.

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

return 0;

}

[入力例]
3 2
URL

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

[入力例]
4 500000000000000000
RRUU

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

[入力例]
30 123456789
LRULURLURLULULRURRLRULRRRUURRU

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

[入力例]
5 5
ULRRU

[出力例]
9

[入力例]
30 2020
RULULUURURRLRRURRRULLULLRURLRR

[出力例]
8280971

[入力例]
50 20220312
ULUURLUURULRRLLRULLLRRURULRURRRURRUURRLRRURLURLURR

[出力例]
5300633865183

[入力例]

3 2

URL

[出力例]

※AtCoderテストケースより

[入力例]

4 500000000000000000

RRUU

[出力例]

500000000000000000

※AtCoderテストケースより

[入力例]

30 123456789

LRULURLURLULULRURRLRULRRRUURRU

[出力例]

126419752371

※AtCoderテストケースより

[入力例]

5 5

ULRRU

[出力例]

[入力例]

30 2020

RULULUURURRLRRURRRULLULLRURLRR

[出力例]

8280971

[入力例]

50 20220312

ULUURLUURULRRLLRULLLRRURULRURRRURRUURRLRRURLURLURR

[出力例]

5300633865183

■参照サイト
AtCoder Beginner Contest 243

2022年3月12日2022年3月12日

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

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

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

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

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

// 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
LL a[202020], b[202020], aCum[404040];

int main(){
    
    // 1. 入力情報.
    int N;
    LL K;
    scanf("%d %lld", &N, &K);
    rep(i, N) scanf("%lld", &a[i]);
    
    // 2. 二回登場するまで繰り返す.
    LL x = 0;
    int cur = 0;
    vi v;
    while(b[cur] < 2){
        cur = (int)(x % N);
        x += a[cur];
        ++b[cur];
        v.pb(cur);
    }
    
    // 3. 累積和.
    v.pop_back();
    int vl = v.size();
    rep(i, vl) aCum[i + 1] = aCum[i] + a[v[i]];
    
    // 4. 集計.
    int f = 0;
    rep(i, vl){
        if(v[i] == cur){
            f = i;
            break;
        }
    }
    int g = v.size() - f;
    if(g == 0) g = f, f = 0;
    LL q = (K - f) / g;
    int r = (int)((K - f) % g);
    LL ans = 0;
    if(K <= f) ans = aCum[(int)K];
    else       ans = (aCum[vl] - aCum[f]) * q + aCum[f + r];
    
    // 5. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

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

LL a[202020], b[202020], aCum[404040];

int main(){

// 1. 入力情報.

int N;

LL K;

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

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

// 2. 二回登場するまで繰り返す.

LL x = 0;

int cur = 0;

vi v;

while(b[cur] < 2){

cur = (int)(x % N);

x += a[cur];

++b[cur];

v.pb(cur);

}

// 3. 累積和.

v.pop_back();

int vl = v.size();

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

// 4. 集計.

int f = 0;

rep(i, vl){

if(v[i] == cur){

f = i;

break;

}

int g = v.size() - f;

if(g == 0) g = f, f = 0;

LL q = (K - f) / g;

int r = (int)((K - f) % g);

LL ans = 0;

if(K <= f) ans = aCum[(int)K];

else ans = (aCum[vl] - aCum[f]) * q + aCum[f + r];

// 5. 出力.

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

return 0;

}

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

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

[入力例]
10 1000000000000
260522 914575 436426 979445 648772 690081 933447 190629 703497 47202

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

[入力例]
2 5
2 1

[出力例]
10

[入力例]
3 7
1 2 3

[出力例]
10

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

[出力例]
9

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

[出力例]
30

[入力例]
55 555
11181 11636 11482 4585 2301 3788 4582 9791 9348 6010 12000 2413 1358 9745 6246 10307 8984 8302 1355 262 4603 11354 1272 3283 11013 4294 12172 1279 4546 3144 2000 8336 8459 3579 9339 8673 10519 1051 2998 10661 1619 7076 9819 3810 7138 530 6761 11899 7076 3485 10276 4812 1249 11397 2504

[出力例]
2213206

[入力例]

5 3

2 1 6 3 1

[出力例]

※AtCoderテストケースより

[入力例]

10 1000000000000

260522 914575 436426 979445 648772 690081 933447 190629 703497 47202

[出力例]

826617499998784056

※AtCoderテストケースより

[入力例]

2 5

2 1

[出力例]

[入力例]

3 7

1 2 3

[出力例]

[入力例]

5 3

3 1 2 4 3

[出力例]

[入力例]

7 12

3 1 4 1 5 9 2

[出力例]

[入力例]

55 555

11181 11636 11482 4585 2301 3788 4582 9791 9348 6010 12000 2413 1358 9745 6246 10307 8984 8302 1355 262 4603 11354 1272 3283 11013 4294 12172 1279 4546 3144 2000 8336 8459 3579 9339 8673 10519 1051 2998 10661 1619 7076 9819 3810 7138 530 6761 11899 7076 3485 10276 4812 1249 11397 2504

[出力例]

2213206

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

2022年3月11日

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

C++の練習を兼ねて, AtCoder Beginner Contest 241 の問題C (Construct Highway) ～問題D (Sequence Query) を解いてみた.

■感想.
1. 問題C, Dは, 方針を絞り込めたので, AC版に到達できたと思う.
2. 問題D は, 場合分けが多く, 実装に苦労したものの, std::multiset の復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

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

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    vs v;
    rep(i, N){
        char c[1010];
        scanf("%s", c);
        string s(c);
        v.pb(s);
    }
    
    // 2. 黒マスが, 6つ以上連続するか？.
    bool ok = false;
    rep(i, N){
        rep(j, N){
            // 下.
            int c1 = 0;
            if(i < N - 5) rep(k, 6) if(v[i + k][j] == '#') ++c1;
            
            // 右.
            int c2 = 0;
            if(j < N - 5) rep(k, 6) if(v[i][j + k] == '#') ++c2;
            
            // 右下.
            int c3 = 0;
            if(i < N - 5 && j < N - 5) rep(k, 6) if(v[i + k][j + k] == '#') ++c3;
            
            // 左下.
            int c4 = 0;
            if(i < N - 5 && j >= 5) rep(k, 6) if(v[i + k][j - k] == '#') ++c4;
            
            // 判定.
            if(c1 >= 4) ok = true;
            if(c2 >= 4) ok = true;
            if(c3 >= 4) ok = true;
            if(c4 >= 4) ok = true;
            
            // 見つかった.
            if(ok) break;
        }
        // 見つかった.
        if(ok) break;
    }
    
    // 3. 出力.
    printf("%s\n", ok ? "Yes" : "No");
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vs = vector<string>;

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

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

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

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

#define pb push_back

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

vs v;

rep(i, N){

char c[1010];

scanf("%s", c);

string s(c);

v.pb(s);

}

// 2. 黒マスが, 6つ以上連続するか？.

bool ok = false;

rep(i, N){

rep(j, N){

// 下.

int c1 = 0;

if(i < N - 5) rep(k, 6) if(v[i + k][j] == '#') ++c1;

// 右.

int c2 = 0;

if(j < N - 5) rep(k, 6) if(v[i][j + k] == '#') ++c2;

// 右下.

int c3 = 0;

if(i < N - 5 && j < N - 5) rep(k, 6) if(v[i + k][j + k] == '#') ++c3;

// 左下.

int c4 = 0;

if(i < N - 5 && j >= 5) rep(k, 6) if(v[i + k][j - k] == '#') ++c4;

// 判定.

if(c1 >= 4) ok = true;

if(c2 >= 4) ok = true;

if(c3 >= 4) ok = true;

if(c4 >= 4) ok = true;

// 見つかった.

if(ok) break;

}

// 見つかった.

if(ok) break;

}

// 3. 出力.

printf("%s\n", ok ? "Yes" : "No");

return 0;

}

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

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

[入力例]
6
######
######
######
######
######
######

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

[入力例]
10
..........
#..##.....
..........
..........
....#.....
....#.....
.#...#..#.
..........
..........
..........

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

[入力例]
6
......
....#.
...#..
......
.#....
#.....

[出力例]
Yes

[入力例]
6
......
......
......
......
......
#...##

[出力例]
No

[入力例]
13
.............
.............
..#.#...#.#..
.............
..#.#...#.#..
.....#.#.....
..#.#...#.#..
.....#.#.....
..#.#...#.#..
.............
..#.#...#.#..
.............
.............

[出力例]
Yes

[入力例]

........

.#.##.#.

........

[出力例]

Yes

※AtCoderテストケースより

[入力例]

######

[出力例]

Yes

※AtCoderテストケースより

[入力例]

..........

#..##.....

..........

....#.....

.#...#..#.

..........

[出力例]

※AtCoderテストケースより

[入力例]

......

....#.

...#..

......

.#....

#.....

[出力例]

Yes

[入力例]

......

#...##

[出力例]

[入力例]

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

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

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

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

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

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

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

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

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

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

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

[出力例]

Yes

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

int main(){
    
    // 1. 入力情報.
    int Q;
    scanf("%d", &Q);
    
    // 2. クエリ回答.
    multiset<LL> mst;
    rep(i, Q){
        // 2-1. クエリ入力情報.
        int f;
        scanf("%d", &f);
        
        // 2-2. クエリ 1.
        if(f == 1){
            LL x;
            scanf("%lld", &x);
            mst.insert(x);
        }
        
        // 2-3. クエリ 2.
        if(f == 2){
            LL x, q = 0;
            int k;
            scanf("%lld %d", &x, &k);
            auto it = mst.upper_bound(x);
            
            // 空の場合.
            if(mst.empty()){
                puts("-1");
                continue;
            }
            
            // x が 小さい場合.
            if(x < *mst.begin()){
                puts("-1");
                continue;
            }
            
            // x が 大きい場合.
            if(x > *it){
                --it;
                --k;
                q = *it;
            }
            
            // 繰り返し.
            while(k > 0){
                if(it == mst.begin() || it == mst.end()) break;
                --it;
                --k;
                q = *it;
            }
            printf("%lld\n", (k == 0) ? q : -1);
        }
        
        // 2-4. クエリ 3.
        if(f == 3){
            LL x, q = 0;
            int k;
            scanf("%lld %d", &x, &k);
            auto it = mst.lower_bound(x);
            
            // 空の場合.
            if(mst.empty()){
                puts("-1");
                continue;
            }
            
            // x が 大きい場合.
            if(x > *(--mst.end())){
                puts("-1");
                continue;
            }
            
            // 最終要素の次を指していた場合.
            if(it == mst.end()) --it;
            
            // 繰り返し.
            while(k > 0){
                q = *it;
                ++it;
                --k;
                if(it == mst.end()) break;
            }
            printf("%lld\n", (k == 0) ? q : -1);
        }
    }
    return 0;
    
}

100

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

scanf("%d", &Q);

// 2. クエリ回答.

multiset<LL> mst;

rep(i, Q){

// 2-1. クエリ入力情報.

int f;

scanf("%d", &f);

// 2-2. クエリ 1.

if(f == 1){

LL x;

scanf("%lld", &x);

mst.insert(x);

}

// 2-3. クエリ 2.

if(f == 2){

LL x, q = 0;

int k;

scanf("%lld %d", &x, &k);

auto it = mst.upper_bound(x);

// 空の場合.

if(mst.empty()){

puts("-1");

continue;

}

// x が小さい場合.

if(x < *mst.begin()){

puts("-1");

continue;

}

// x が大きい場合.

if(x > *it){

--it;

--k;

q = *it;

}

// 繰り返し.

while(k > 0){

if(it == mst.begin() || it == mst.end()) break;

--it;

--k;

q = *it;

}

printf("%lld\n", (k == 0) ? q : -1);

}

// 2-4. クエリ 3.

if(f == 3){

LL x, q = 0;

int k;

scanf("%lld %d", &x, &k);

auto it = mst.lower_bound(x);

// 空の場合.

if(mst.empty()){

puts("-1");

continue;

}

// x が大きい場合.

if(x > *(--mst.end())){

puts("-1");

continue;

}

// 最終要素の次を指していた場合.

if(it == mst.end()) --it;

// 繰り返し.

while(k > 0){

q = *it;

++it;

--k;

if(it == mst.end()) break;

}

printf("%lld\n", (k == 0) ? q : -1);

}

return 0;

}

[入力例]
11
1 20
1 10
1 30
1 20
3 15 1
3 15 2
3 15 3
3 15 4
2 100 5
1 1
2 100 5

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

[入力例]
15
1 67
1 111
3 89 2
1 222
1 136
3 107 1
2 101 4
1 205
2 103 2
1 64
2 188 1
3 29 2
2 43 4
3 164 5
2 60 1

[出力例]
-1
111
-1
-1
136
67
-1
-1
-1

[入力例]
50
1 200
1 199
1 100
3 89 2
1 234
3 107 2
2 101 1
2 103 2
1 136
1 64
2 188 1
3 29 2
2 12 4
3 164 3
1 205
2 60 1
1 118
3 151 4
2 74 5
1 7
3 92 5
2 182 5
3 247 1
3 30 4
1 208
2 125 4
3 172 4
2 151 5
1 88
1 77
2 35 2
1 98
3 146 2
1 178
2 95 2
2 158 5
1 167
1 250
2 89 1
2 57 4
1 145
2 94 2
1 101
2 152 4
1 101
2 88 4
1 97
3 80 5
3 195 4
2 38 3

[出力例]
199
200
100
-1
136
100
-1
234
-1
234
-1
200
7
-1
136
7
208
7
-1
200
77
88
88
-1
77
101
7
101
208
-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

126

127

128

129

130

131

132

133

134

135

136

[入力例]

1 20

1 10

1 30

1 20

3 15 1

3 15 2

3 15 3

3 15 4

2 100 5

1 1

2 100 5

[出力例]

-1

※AtCoderテストケースより

[入力例]

1 67

1 111

3 89 2

1 222

1 136

3 107 1

2 101 4

1 205

2 103 2

1 64

2 188 1

3 29 2

2 43 4

3 164 5

2 60 1

[出力例]

-1

111

-1

136

-1

[入力例]

1 200

1 199

1 100

3 89 2

1 234

3 107 2

2 101 1

2 103 2

1 136

1 64

2 188 1

3 29 2

2 12 4

3 164 3

1 205

2 60 1

1 118

3 151 4

2 74 5

1 7

3 92 5

2 182 5

3 247 1

3 30 4

1 208

2 125 4

3 172 4

2 151 5

1 88

1 77

2 35 2

1 98

3 146 2

1 178

2 95 2

2 158 5

1 167

1 250

2 89 1

2 57 4

1 145

2 94 2

1 101

2 152 4

1 101

2 88 4

1 97

3 80 5

3 195 4

2 38 3

[出力例]

199

200

100

-1

136

100

-1

234

-1

234

-1

200

-1

136

208

-1

200

-1

101

208

-1

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

2022年3月10日

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

C++の練習を兼ねて, エクサウィザーズ 2019 の問題D (Modulo Operations) を解いてみた.

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

本家のサイトエクサウィザーズ 2019 解説をご覧下さい.

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

// 解き直し.
// https://img.atcoder.jp/exawizards2019/editorial.pdf
// 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
#define all(x) x.begin(), x.end()
const LL MOD = 1e9 + 7;
LL dp[202][101010], FAC[202];

// Fermat's little theorem から, 大きな冪乗の計算を行う.
// @param a: べき乗したい正整数.
// @param b: 指数.
// @return:  べき乗した計算結果(mod版).
LL mPow(LL a, LL b){
    LL t = 1;
    while(b){
        if(b & 1) t = (t * a) % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return t;
}

int main(){
    
    // 1. 入力情報.
    int N, X;
    scanf("%d %d", &N, &X);
    vi a;
    rep(i, N){
        int s;
        scanf("%d", &s);
        a.pb(s);
    }
    
    // 2. 事前計算.
    FAC[0] = 1;
    repx(i, 1, 202) FAC[i] = (LL)i * FAC[i - 1] % MOD;
    
    // 3. sort.
    sort(all(a));
    reverse(all(a));
    
    // 4. dp更新.
    dp[0][X] = 1;
    rep(i, N){
        // i回目操作(変化する確率).
        LL p = mPow((LL)(N - i), MOD - 2);
        
        // i回目操作(変化しない確率).
        LL q = (N - 1 - i) * p % MOD;
        
        // 前回分反映.
        rep(j, X + 1){
            // a[i]未満, a[i]以上 で 分岐.
            dp[i + 1][j] += dp[i][j] * ((j < a[i]) ? 1 : q);
            dp[i + 1][j] %= MOD;
        }
        
        // 今回分反映(a[i]以上, 変化する).
        repx(j, a[i], X + 1){
            if(!dp[i][j]) continue;
            int nj = j % a[i];
            dp[i + 1][nj] += dp[i][j] * p;
            dp[i + 1][nj] %= MOD;
        }
    }
    
    // 5. 集計.
    LL ans = 0;
    rep(i, X + 1){
        ans += dp[N][i] * (LL)i % MOD * FAC[N] % MOD;
        ans %= MOD;
    }
    
    // 6. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

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

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

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

const LL MOD = 1e9 + 7;

LL dp[202][101010], FAC[202];

// Fermat's little theorem から, 大きな冪乗の計算を行う.

// @param a: べき乗したい正整数.

// @param b: 指数.

// @return: べき乗した計算結果(mod版).

LL mPow(LL a, LL b){

LL t = 1;

while(b){

if(b & 1) t = (t * a) % MOD;

a = a * a % MOD;

b >>= 1;

}

return t;

}

int main(){

// 1. 入力情報.

int N, X;

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

vi a;

rep(i, N){

int s;

scanf("%d", &s);

a.pb(s);

}

// 2. 事前計算.

FAC[0] = 1;

repx(i, 1, 202) FAC[i] = (LL)i * FAC[i - 1] % MOD;

// 3. sort.

sort(all(a));

reverse(all(a));

// 4. dp更新.

dp[0][X] = 1;

rep(i, N){

// i回目操作(変化する確率).

LL p = mPow((LL)(N - i), MOD - 2);

// i回目操作(変化しない確率).

LL q = (N - 1 - i) * p % MOD;

// 前回分反映.

rep(j, X + 1){

// a[i]未満, a[i]以上で分岐.

dp[i + 1][j] += dp[i][j] * ((j < a[i]) ? 1 : q);

dp[i + 1][j] %= MOD;

}

// 今回分反映(a[i]以上, 変化する).

repx(j, a[i], X + 1){

if(!dp[i][j]) continue;

int nj = j % a[i];

dp[i + 1][nj] += dp[i][j] * p;

dp[i + 1][nj] %= MOD;

}

// 5. 集計.

LL ans = 0;

rep(i, X + 1){

ans += dp[N][i] * (LL)i % MOD * FAC[N] % MOD;

ans %= MOD;

}

// 6. 出力.

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

return 0;

}

[入力例]
2 19
3 7

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

[入力例]
5 82
22 11 6 5 13

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

[入力例]
10 100000
50000 50001 50002 50003 50004 50005 50006 50007 50008 50009

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

[入力例]
3 12
7 9 5

[出力例]
10

[入力例]
5 15
3 7 8 11 17

[出力例]
75

[入力例]
8 100
31 41 59 26 53 58 97 93

[出力例]
448560

[入力例]
12 567
2 3 5 8 13 21 34 55 89 144 233 377

[出力例]
183185992

[入力例]

2 19

3 7

[出力例]

※AtCoderテストケースより

[入力例]

5 82

22 11 6 5 13

[出力例]

288

※AtCoderテストケースより

[入力例]

10 100000

50000 50001 50002 50003 50004 50005 50006 50007 50008 50009

[出力例]

279669259

※AtCoderテストケースより

[入力例]

3 12

7 9 5

[出力例]

[入力例]

5 15

3 7 8 11 17

[出力例]

[入力例]

8 100

31 41 59 26 53 58 97 93

[出力例]

448560

[入力例]

12 567

2 3 5 8 13 21 34 55 89 144 233 377

[出力例]

183185992

■参照サイト
エクサウィザーズ 2019

2022年3月6日

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

C++の練習を兼ねて, Mujin Programming Challenge 2017 の問題A (Robot Racing) を解いてみた.

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

本家のサイト Mujin Programming Challenge 2017 解説をご覧下さい.

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

// 解き直し.
// https://img.atcoder.jp/mujin-pc-2017/editorial.pdf
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
const LL MOD = 1e9 + 7;
LL FAC[101010];
int x[101010];

int main(){

    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%d", &x[i]);
    
    // 2. 事前計算.
    FAC[0] = 1;
    repx(i, 1, N + 1) FAC[i] = (LL)i * FAC[i - 1] % MOD;
    
    // 3. 操作.
    stack<int> st;
    LL ans = 1;
    repx(i, 1, N + 1){
        // ロボット追加.
        st.push(x[i - 1]);
        
        // k番目の要素と見て, 座標チェック.
        int k = st.size();
        if(x[i - 1] < 2 * k - 1){
            st.pop();
            ans *= (LL)k;
            ans %= MOD;
        }
    }
    
    // 4. 残ったロボット.
    ans *= FAC[st.size()];
    ans %= MOD;
    
    // 5. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://img.atcoder.jp/mujin-pc-2017/editorial.pdf

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

const LL MOD = 1e9 + 7;

LL FAC[101010];

int x[101010];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

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

// 2. 事前計算.

FAC[0] = 1;

repx(i, 1, N + 1) FAC[i] = (LL)i * FAC[i - 1] % MOD;

// 3. 操作.

stack<int> st;

LL ans = 1;

repx(i, 1, N + 1){

// ロボット追加.

st.push(x[i - 1]);

// k番目の要素と見て, 座標チェック.

int k = st.size();

if(x[i - 1] < 2 * k - 1){

st.pop();

ans *= (LL)k;

ans %= MOD;

}

// 4. 残ったロボット.

ans *= FAC[st.size()];

ans %= MOD;

// 5. 出力.

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

return 0;

}

[入力例]
3
1 2 3

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

[入力例]
3
2 3 4

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

[入力例]
8
1 2 3 5 7 11 13 17

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

[入力例]
13
4 6 8 9 10 12 14 15 16 18 20 21 22

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

[入力例]
2
1 5

[出力例]
2

[入力例]
3
1 3 5

[出力例]
6

[入力例]
7
1 5 8 9 11 12 20

[出力例]
5040

[入力例]
20
2 12 21 29 30 35 47 54 65 70 71 78 80 85 89 100 106 107 118 119

[出力例]
146326063

[入力例]
120
1 2 5 11 25 33 35 42 45 46 51 52 59 64 68 69 78 88 89 99 108 118 122 123 127 128 129 136 141 150 153 154 162 164 173 175 178 187 192 195 201 206 213 216 226 236 245 252 255 264 265 272 278 285 291 299 307 311 317 322 325 329 333 336 340 346 350 353 362 365 366 370 374 383 387 392 401 405 409 418 420 423 425 429 435 436 440 448 450 453 458 465 471 476 482 489 494 501 504 511 513 522 523 526 527 533 542 550 552 556 557 567 568 572 582 585 586 595 604 606

[出力例]
588578382

[入力例]

1 2 3

[出力例]

※AtCoderのテストケースより

[入力例]

2 3 4

[出力例]

※AtCoderのテストケースより

[入力例]

1 2 3 5 7 11 13 17

[出力例]

10080

※AtCoderのテストケースより

[入力例]

4 6 8 9 10 12 14 15 16 18 20 21 22

[出力例]

311014372

※AtCoderのテストケースより

[入力例]

1 5

[出力例]

[入力例]

1 3 5

[出力例]

[入力例]

1 5 8 9 11 12 20

[出力例]

5040

[入力例]

2 12 21 29 30 35 47 54 65 70 71 78 80 85 89 100 106 107 118 119

[出力例]

146326063

[入力例]

120

1 2 5 11 25 33 35 42 45 46 51 52 59 64 68 69 78 88 89 99 108 118 122 123 127 128 129 136 141 150 153 154 162 164 173 175 178 187 192 195 201 206 213 216 226 236 245 252 255 264 265 272 278 285 291 299 307 311 317 322 325 329 333 336 340 346 350 353 362 365 366 370 374 383 387 392 401 405 409 418 420 423 425 429 435 436 440 448 450 453 458 465 471 476 482 489 494 501 504 511 513 522 523 526 527 533 542 550 552 556 557 567 568 572 582 585 586 595 604 606

[出力例]

588578382

■参照サイト
Mujin Programming Challenge 2017

2022年3月5日

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

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

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

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

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

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

int main(){
    
    // 1. 入力情報.
    int N, M, t = 0;
    scanf("%d %d", &N, &M);
    rep(i, N){
        scanf("%d", &d[i]);
        t += d[i];
    }
    vvi G(N);
    rep(i, M){
        int a, b;
        scanf("%d %d", &a, &b);
        --a;
        --b;
        G[a].pb(b);
        G[b].pb(a);
    }
    
    // 2. グラフが木となるか？
    if(t != 2 * N - 2){
        puts("-1");
        return 0;
    }
    
    // 3. 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;
    rep(i, N) c[i] = 0;
    rep(i, N) if(!c[i]) bfs(G, i, c, ++idx);
    
    // 4. 各連結成分ごとに, 不足次数で分ける.
    PQ pq;
    queue<int> q;
    vvi s(idx + 1);
    int lack[idx + 1], lackSum = 0;
    repx(i, 1, idx + 1) lack[i] = 0;
    rep(i, N) lack[c[i]] += (d[i] - G[i].size());
    rep(i, N){
        int res = d[i] - G[i].size();
        rep(_, res) s[c[i]].pb(i);
    }
    repx(i, 1, idx + 1){
        // 次数 1 不足.
        if(lack[i] == 1) q.push(s[i][0]);
        
        // 次数 2以上 不足.
        if(lack[i] > 1) pq.push({s[i].size(), s[i]});
        
        // 不足分合計.
        lackSum += lack[i];
    }
    
    // 5. 例外(不足分なし).
    // -> 出力なしのケース.
    if(lackSum == 0){
        puts("");
        return 0;
    }
    
    // 6. 例外(不足分あり).
    // -> 不足次数の合計を確認.
    //    random_21.txt で, WA版 となったため, ロジック修正.
    if(2 * idx - 2 != lackSum){
        puts("-1");
        return 0;
    }
    
    // 7. 操作.
    vp ans;
    while(!pq.empty()){
        auto p = pq.top();
        pq.pop();
        int n = p.b.size();
        rep(i, n){
            // 次数 1 不足 に 追加.
            if(i == n - 1){
                q.push(p.b.back());
                break;
            }
            
            // 辺を追加.
            if(!q.empty()){
                int v = q.front();
                q.pop();
                ans.pb({p.b[i], v});
            }
        }
    }
    
    // 8. 出力.
    if(q.size() != 2) puts("-1");
    if(q.size() == 2){
        int u = q.front();
        q.pop();
        int v = q.front();
        ans.pb({u, v});
        for(auto &p : ans) printf("%d %d\n", p.a + 1, p.b + 1);
    }
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

// 解き直し.

// https://atcoder.jp/contests/abc239/editorial/3388

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vi = vector<int>;

using vvi = vector<vi>;

using P = pair<int, int>;

using vp = vector<P>;

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

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

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

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

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

#define pb push_back

#define a first

#define b second

int d[202020];

int main(){

// 1. 入力情報.

int N, M, t = 0;

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

rep(i, N){

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

t += d[i];

}

vvi G(N);

rep(i, M){

int a, b;

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

--a;

--b;

G[a].pb(b);

G[b].pb(a);

}

// 2. グラフが木となるか？

if(t != 2 * N - 2){

puts("-1");

return 0;

}

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

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

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

// 4. 各連結成分ごとに, 不足次数で分ける.

PQ pq;

queue<int> q;

vvi s(idx + 1);

int lack[idx + 1], lackSum = 0;

repx(i, 1, idx + 1) lack[i] = 0;

rep(i, N) lack[c[i]] += (d[i] - G[i].size());

rep(i, N){

int res = d[i] - G[i].size();

rep(_, res) s[c[i]].pb(i);

}

repx(i, 1, idx + 1){

// 次数 1 不足.

if(lack[i] == 1) q.push(s[i][0]);

// 次数 2以上不足.

if(lack[i] > 1) pq.push({s[i].size(), s[i]});

// 不足分合計.

lackSum += lack[i];

}

// 5. 例外(不足分なし).

// -> 出力なしのケース.

if(lackSum == 0){

puts("");

return 0;

}

// 6. 例外(不足分あり).

// -> 不足次数の合計を確認.

// random_21.txt で, WA版となったため, ロジック修正.

if(2 * idx - 2 != lackSum){

puts("-1");

return 0;

}

// 7. 操作.

vp ans;

while(!pq.empty()){

auto p = pq.top();

pq.pop();

int n = p.b.size();

rep(i, n){

// 次数 1 不足に追加.

if(i == n - 1){

q.push(p.b.back());

break;

}

// 辺を追加.

if(!q.empty()){

int v = q.front();

q.pop();

ans.pb({p.b[i], v});

}

// 8. 出力.

if(q.size() != 2) puts("-1");

if(q.size() == 2){

int u = q.front();

q.pop();

int v = q.front();

ans.pb({u, v});

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

}

return 0;

}

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

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

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

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

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

[入力例]
4 0
3 3 3 3

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

[入力例]
2 1
1 1
1 2

[出力例]


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

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

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

[出力例]
1 2
3 4

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

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

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

[出力例]
6 2
1 5
1 7
6 1

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

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

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

[入力例]

6 2

1 2 1 2 2 2

2 3

1 4

[出力例]

6 2

5 6

4 5

※AtCoderテストケースより

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

5 4

6 2

5 6

[入力例]

5 1

1 1 1 1 4

2 3

[出力例]

-1

※AtCoderテストケースより

[入力例]

4 0

3 3 3 3

[出力例]

-1

※AtCoderテストケースより

[入力例]

2 1

1 1

1 2

[出力例]

[入力例]

5 0

1 1 2 2 2

[出力例]

3 1

4 2

5 3

4 5

[入力例]

5 2

2 1 1 2 2

1 5

4 5

[出力例]

1 2

3 4

[入力例]

12 5

2 2 2 2 2 2 2 2 2 2 1 1

1 7

2 8

2 3

4 5

4 10

[出力例]

1 11

3 12

5 7

6 8

9 10

6 9

[入力例]

8 3

5 2 1 1 1 2 1 1

1 3

1 4

2 8

[出力例]

6 2

1 5

1 7

6 1

[入力例]

20 7

6 2 1 3 2 1 1 1 1 5 1 1 1 1 2 5 1 1 1 1

1 2

1 3

16 17

4 5

10 11

1 5

10 13

[出力例]

15 6

10 7

10 8

16 9

16 12

16 14

1 18

1 19

1 20

2 15

4 10

16 4

■参照サイト
デンソークリエイトプログラミングコンテスト2022（AtCoder Beginner Contest 239）

2022年3月4日2022年3月4日

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

C++の練習を兼ねて, エクサウィザーズ 2019 の問題C (Snuke the Wizard) を解いてみた.

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

本家のサイトエクサウィザーズ 2019 解説をご覧下さい.

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

// 解き直し.
// https://img.atcoder.jp/exawizards2019/editorial.pdf
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using P = pair<char, char>;
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 main(){
    
    // 1. 入力情報.
    int N, Q;
    char s[202020];
    scanf("%d %d %s", &N, &Q, s);
    string S(s);
    S = '#' + S + '#';
    vp op;
    rep(i, Q){
        char t[11], d[11];
        scanf("%s %s", t, d);
        op.pb({t[0], d[0]});
    }
    
    // 2. 評価関数.
    // -> マス 0 に到達するか否か.
    auto f = [&](int m) -> bool {
        // 2-1. 呪文を, Q回詠唱.
        char c = S[m];
        int p = m, pMin = N + 1;
        for(auto &o : op){
            if(o.a != c) continue;
            p += (o.b == 'R') ? +1 : -1;
            if(p >= 1 && p <= N) c = S[p];
            pMin = min(pMin, p);
        }
        
        // 2-2. 判定結果.
        return (pMin > 0);
    };
    
    // 3. 二分探索で確認してみる.
    int l = 0, h = N + 1, m, ans = 0;
    while(l + 1 < h){
        int m = (h + l) >> 1;
        if(f(m)) h = m;
        else     l = m;
        // printf("h=%d l=%d m=%d\n", h, l, m);
    }
    ans = l;
    
    // 4. 評価関数.
    // -> マス (N + 1) に到達するか否か.
    auto g = [&](int m) -> bool {
        // 4-1. 呪文を, Q回詠唱.
        char c = S[m];
        int p = m, pMax = 0;
        for(auto &o : op){
            if(o.a != c) continue;
            p += (o.b == 'R') ? +1 : -1;
            if(p >= 1 && p <= N) c = S[p];
            pMax = max(pMax, p);
        }
        
        // 4-2. 判定結果.
        return (pMax < N + 1);
    };
    
    // 5. 二分探索で確認してみる.
    l = 0, h = N + 1, m;
    while(l + 1 < h){
        int m = (h + l) >> 1;
        if(g(m)) l = m;
        else     h = m;
        // printf("h=%d l=%d m=%d\n", h, l, m);
    }
    ans = max(0, l - ans);
    
    // 6. 出力.
    printf("%d\n", ans);
    return 0;
    
}

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using P = pair<char, char>;

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 main(){

// 1. 入力情報.

int N, Q;

char s[202020];

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

string S(s);

S = '#' + S + '#';

vp op;

rep(i, Q){

char t[11], d[11];

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

op.pb({t[0], d[0]});

}

// 2. 評価関数.

// -> マス 0 に到達するか否か.

auto f = [&](int m) -> bool {

// 2-1. 呪文を, Q回詠唱.

char c = S[m];

int p = m, pMin = N + 1;

for(auto &o : op){

if(o.a != c) continue;

p += (o.b == 'R') ? +1 : -1;

if(p >= 1 && p <= N) c = S[p];

pMin = min(pMin, p);

}

// 2-2. 判定結果.

return (pMin > 0);

};

// 3. 二分探索で確認してみる.

int l = 0, h = N + 1, m, ans = 0;

while(l + 1 < h){

int m = (h + l) >> 1;

if(f(m)) h = m;

else l = m;

// printf("h=%d l=%d m=%d\n", h, l, m);

}

ans = l;

// 4. 評価関数.

// -> マス (N + 1) に到達するか否か.

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

// 4-1. 呪文を, Q回詠唱.

char c = S[m];

int p = m, pMax = 0;

for(auto &o : op){

if(o.a != c) continue;

p += (o.b == 'R') ? +1 : -1;

if(p >= 1 && p <= N) c = S[p];

pMax = max(pMax, p);

}

// 4-2. 判定結果.

return (pMax < N + 1);

};

// 5. 二分探索で確認してみる.

l = 0, h = N + 1, m;

while(l + 1 < h){

int m = (h + l) >> 1;

if(g(m)) l = m;

else h = m;

// printf("h=%d l=%d m=%d\n", h, l, m);

}

ans = max(0, l - ans);

// 6. 出力.

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

return 0;

}

[入力例]
3 4
ABC
A L
B L
B R
A R

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

[入力例]
8 3
AABCBDBA
A L
B R
A R

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

[入力例]
10 15
SNCZWRCEWB
B R
R R
E R
W R
Z L
S R
Q L
W L
B R
C L
A L
N L
E R
Z L
S L

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

[入力例]
5 5
ABABA
A R
B R
A R
B R
A L

[出力例]
2

[入力例]
11 15
ABBCCDCCBBA
D R
C R
C R
A L
A R
B L
C R
B R
B R
A R
C L
B L
B L
A L
D R

[出力例]
2

[入力例]
50 50
IAHJAFEIHHBDIAJMECDLEMGBJMMDKILFLJFLBKMIEEDDDMMDFA
E L
L L
D L
C L
E L
M L
N R
A R
J L
E R
A L
E R
I L
D L
B L
H R
H L
M R
H L
D R
I L
F R
E L
F L
E L
A L
B L
J L
A R
H L
A L
I L
D R
M R
D R
G R
D R
F R
A R
F L
A L
J R
H L
J L
D R
A L
I L
L L
E R
K L

[出力例]
37

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

[入力例]

3 4

ABC

A L

B L

B R

A R

[出力例]

※AtCoderテストケースより

[入力例]

8 3

AABCBDBA

A L

B R

A R

[出力例]

※AtCoderテストケースより

[入力例]

10 15

SNCZWRCEWB

B R

R R

E R

W R

Z L

S R

Q L

W L

B R

C L

A L

N L

E R

Z L

S L

[出力例]

※AtCoderテストケースより

[入力例]

5 5

ABABA

A R

B R

A R

B R

A L

[出力例]

[入力例]

11 15

ABBCCDCCBBA

D R

C R

A L

A R

B L

C R

B R

A R

C L

B L

A L

D R

[出力例]

[入力例]

50 50

IAHJAFEIHHBDIAJMECDLEMGBJMMDKILFLJFLBKMIEEDDDMMDFA

E L

L L

D L

C L

E L

M L

N R

A R

J L

E R

A L

E R

I L

D L

B L

H R

H L

M R

H L

D R

I L

F R

E L

F L

E L

A L

B L

J L

A R

H L

A L

I L

D R

M R

D R

G R

D R

F R

A R

F L

A L

J R

H L

J L

D R

A L

I L

L L

E R

K L

[出力例]

■参照サイト
エクサウィザーズ 2019

2022年3月3日

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

C++の練習を兼ねて, キーエンスプログラミングコンテスト 2019 の問題D (Double Landscape) を解いてみた.

■感想.
1. 問題Dは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 書き込む数字を大きい方から見ていくという, 解説のロジックが興味深く感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

本家のサイトキーエンスプログラミングコンテスト 2019 解説をご覧下さい.

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

// 解き直し.
// https://img.atcoder.jp/keyence2019/editorial.pdf
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
const LL MOD = 1e9 + 7;
int a[1010101], b[1010101], aCum[1010101], bCum[1010101];

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    set<int> aSt, bSt;
    rep(i, N){
        int x;
        scanf("%d", &x);
        a[x]++;
        aCum[x]++;
        aSt.insert(x);
    }
    rep(i, M){
        int x;
        scanf("%d", &x);
        b[x]++;
        bCum[x]++;
        bSt.insert(x);
    }
    
    // 2. 例外(a, b で 同じ値が含まれる場合).
    if((aSt.size() != N) || (bSt.size() != M)){
        puts("0");
        return 0;
    }
    
    // 3. 累積和.
    rep(i, N * M + 1){
        aCum[i + 1] += aCum[i];
        bCum[i + 1] += bCum[i];
    }
    
    // 4. x が 大きい順に確認.
    LL ans = 1;
    repr(x, N * M, 1){
        // 4-1. a, b の 両方に現れる.
        if(a[x] && b[x]) continue;
        
        // 4-2. a のみ現れる.
        if(a[x] && !b[x]){
            ans *= (bCum[N * M] - bCum[x - 1]);
            ans %= MOD;
        }
        
        // 4-3. b のみ現れる.
        if(!a[x] && b[x]){
            ans *= (aCum[N * M] - aCum[x - 1]);
            ans %= MOD;
        }
        
        // 4-4. a, b に 現れない.
        if(!a[x] && !b[x]){
            LL y = (aCum[N * M] - aCum[x - 1]) * (bCum[N * M] - bCum[x - 1]);
            y %= MOD;
            y += MOD - (N * M - x);
            y %= MOD;
            ans *= y;
            ans %= MOD;
        }
    }
    
    // 5. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

const LL MOD = 1e9 + 7;

int a[1010101], b[1010101], aCum[1010101], bCum[1010101];

int main(){

// 1. 入力情報.

int N, M;

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

set<int> aSt, bSt;

rep(i, N){

int x;

scanf("%d", &x);

a[x]++;

aCum[x]++;

aSt.insert(x);

}

rep(i, M){

int x;

scanf("%d", &x);

b[x]++;

bCum[x]++;

bSt.insert(x);

}

// 2. 例外(a, b で同じ値が含まれる場合).

if((aSt.size() != N) || (bSt.size() != M)){

puts("0");

return 0;

}

// 3. 累積和.

rep(i, N * M + 1){

aCum[i + 1] += aCum[i];

bCum[i + 1] += bCum[i];

}

// 4. x が大きい順に確認.

LL ans = 1;

repr(x, N * M, 1){

// 4-1. a, b の両方に現れる.

if(a[x] && b[x]) continue;

// 4-2. a のみ現れる.

if(a[x] && !b[x]){

ans *= (bCum[N * M] - bCum[x - 1]);

ans %= MOD;

}

// 4-3. b のみ現れる.

if(!a[x] && b[x]){

ans *= (aCum[N * M] - aCum[x - 1]);

ans %= MOD;

}

// 4-4. a, b に現れない.

if(!a[x] && !b[x]){

LL y = (aCum[N * M] - aCum[x - 1]) * (bCum[N * M] - bCum[x - 1]);

y %= MOD;

y += MOD - (N * M - x);

y %= MOD;

ans *= y;

ans %= MOD;

}

// 5. 出力.

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

return 0;

}

[入力例]
2 2
4 3
3 4

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

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

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

[入力例]
2 2
4 4
4 4

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

[入力例]
14 13
158 167 181 147 178 151 179 182 176 169 180 129 175 168
181 150 178 179 167 180 176 169 182 177 175 159 173

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

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

[出力例]
6

[入力例]
5 10
10 20 30 40 50
41 42 43 44 50 45 46 47 48 49

[出力例]
202566790

[入力例]
18 11
163 190 191 192 193 194 195 196 171 186 187 188 189 176 177 178 197 198
121 185 160 111 196 189 165 144 184 180 198

[出力例]
710475014

[入力例]

2 2

4 3

3 4

[出力例]

※AtCoderテストケースより

[入力例]

3 3

5 9 7

3 6 9

[出力例]

※AtCoderテストケースより

[入力例]

2 2

4 4

[出力例]

※AtCoderテストケースより

[入力例]

14 13

158 167 181 147 178 151 179 182 176 169 180 129 175 168

181 150 178 179 167 180 176 169 182 177 175 159 173

[出力例]

343772227

※AtCoderテストケースより

[入力例]

2 3

3 6

4 6 5

[出力例]

[入力例]

5 10

10 20 30 40 50

41 42 43 44 50 45 46 47 48 49

[出力例]

202566790

[入力例]

18 11

163 190 191 192 193 194 195 196 171 186 187 188 189 176 177 178 197 198

121 185 160 111 196 189 165 144 184 180 198

[出力例]

710475014

■参照サイト
キーエンスプログラミングコンテスト 2019

2022年2月28日2022年2月28日

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

C++の練習を兼ねて, AtCoder Regular Contest 136 の問題A (A ↔ BB) ～問題B (Triple Shift) を解いてみた.

■感想.
1. 問題Bは, 実装してみたもののWA版となったため, 解説を参考に, 解き直ししてAC版に到達できた.
2. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

■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
#define all(x) x.begin(), x.end()

int main(){
    
    // 1. 入力情報.
    int N;
    char s[202020];
    scanf("%d %s", &N, s);
    
    // 2. 文字列操作.
    stack<char> st;
    rep(i, N){
        // 空でない.
        if(!st.empty()){
            // 'B' の 場合.
            char cur = st.top();
            if(cur == 'B'){
                // BA -> BBB -> AB
                if(s[i] == 'A'){
                    st.pop();
                    st.push('A');
                    st.push('B');
                    continue;
                }
                
                // BB -> A
                if(s[i] == 'B'){
                    st.pop();
                    st.push('A');
                    continue;
                }
            }
        }
        
        // それ以外.
        st.push(s[i]);
    }
    
    // 3. 文字列作成.
    string ans;
    while(!st.empty()){
        char t = st.top();
        st.pop();
        ans.pb(t);
    }
    
    // 4. 反転.
    reverse(all(ans));
    
    // 5. 出力.
    printf("%s\n", ans.c_str());
    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

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

int main(){

// 1. 入力情報.

int N;

char s[202020];

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

// 2. 文字列操作.

stack<char> st;

rep(i, N){

// 空でない.

if(!st.empty()){

// 'B' の場合.

char cur = st.top();

if(cur == 'B'){

// BA -> BBB -> AB

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

st.pop();

st.push('A');

st.push('B');

continue;

}

// BB -> A

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

st.pop();

st.push('A');

continue;

}

// それ以外.

st.push(s[i]);

}

// 3. 文字列作成.

string ans;

while(!st.empty()){

char t = st.top();

st.pop();

ans.pb(t);

}

// 4. 反転.

reverse(all(ans));

// 5. 出力.

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

return 0;

}

[入力例]
4
CBAA

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

[入力例]
1
A

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

[入力例]
6
BBBCBB

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

[入力例]
50
BAACACBABBACABCBBCBCBBCABAABCABACCCBABBBCCABCCABBB

[出力例]
AABCACAAABCABCACBCACAAAACAABCCCAAACCABCCAAB

[入力例]
100
BBAABAABBCABAAABCBBCAABAAABAACBBCABCCBCCCCAACCCBBABBCBBACBCACABAABBBABAAABBBCBABABBBBCCBAACBCBBACCBA

[出力例]
AAAAAABCAAAAACACAAAAAAAACACABCCBCCCCAACCCAAACAACBCACAAAAAAAAAAACAAAAACCAABCBCAACCAB

[入力例]

CBAA

[出力例]

CAAB

※AtCoderのテストケースより

[入力例]

[出力例]

※AtCoderのテストケースより

[入力例]

BBBCBB

[出力例]

ABCA

※AtCoderのテストケースより

[入力例]

BAACACBABBACABCBBCBCBBCABAABCABACCCBABBBCCABCCABBB

[出力例]

AABCACAAABCABCACBCACAAAACAABCCCAAACCABCCAAB

[入力例]

100

BBAABAABBCABAAABCBBCAABAAABAACBBCABCCBCCCCAACCCBBABBCBBACBCACABAABBBABAAABBBCBABABBBBCCBAACBCBBACCBA

[出力例]

AAAAAABCAAAAACACAAAAAAAACACABCCBCCCCAACCCAAACAACBCACAAAAAAAAAAACAAAAACCAABCBCAACCAB

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

// 説き直し.
// https://atcoder.jp/contests/arc136/editorial/3467
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
int a[5050], b[5050], ca[5050], cb[5050];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    set<int> st;
    rep(i, N){
        scanf("%d", &a[i]);
        ca[a[i]]++;
        st.insert(a[i]);
    }
    rep(i, N){
        scanf("%d", &b[i]);
        cb[b[i]]++;
    }
    
    // 2. 例外.
    rep(i, 5050){
        if(ca[i] != cb[i]){
            puts("No");
            return 0;
        }
    }
    
    // 3. sort.
    // 3-1. 数列 A.
    int aCnt = 0;
    rep(i, N){
        int aMin = 5050, at = -1;
        repx(j, i, N){
            if(aMin > a[j]){
                aMin = a[j];
                at = j;
            }
        }
        repr(j, at, i + 1) swap(a[j], a[j - 1]);
        aCnt += (at - i);
    }
    
    // 3-2. 数列 B.
    int bCnt = 0;
    rep(i, N){
        int bMin = 5050, at = -1;
        repx(j, i, N){
            if(bMin > b[j]){
                bMin = b[j];
                at = j;
            }
        }
        repr(j, at, i + 1) swap(b[j], b[j - 1]);
        bCnt += (at - i);
    }
    
    // 4. 出力.
    if(st.size() != N) puts("Yes");
    else               printf("%s\n", ((aCnt + bCnt) % 2 == 0)  ? "Yes" : "No");
    return 0;
    
}

// 説き直し.

// https://atcoder.jp/contests/arc136/editorial/3467

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

int a[5050], b[5050], ca[5050], cb[5050];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

set<int> st;

rep(i, N){

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

ca[a[i]]++;

st.insert(a[i]);

}

rep(i, N){

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

cb[b[i]]++;

}

// 2. 例外.

rep(i, 5050){

if(ca[i] != cb[i]){

puts("No");

return 0;

}

// 3. sort.

// 3-1. 数列 A.

int aCnt = 0;

rep(i, N){

int aMin = 5050, at = -1;

repx(j, i, N){

if(aMin > a[j]){

aMin = a[j];

at = j;

}

repr(j, at, i + 1) swap(a[j], a[j - 1]);

aCnt += (at - i);

}

// 3-2. 数列 B.

int bCnt = 0;

rep(i, N){

int bMin = 5050, at = -1;

repx(j, i, N){

if(bMin > b[j]){

bMin = b[j];

at = j;

}

repr(j, at, i + 1) swap(b[j], b[j - 1]);

bCnt += (at - i);

}

// 4. 出力.

if(st.size() != N) puts("Yes");

else printf("%s\n", ((aCnt + bCnt) % 2 == 0) ? "Yes" : "No");

return 0;

}

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

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

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

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

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

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

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

[出力例]
No

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

[出力例]
Yes

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

[出力例]
Yes

[入力例]

3 1 4 5

4 1 5 3

[出力例]

Yes

※AtCoderのテストケースより

[入力例]

1 2 2

2 1 2

[出力例]

Yes

※AtCoderのテストケースより

[入力例]

1 2 3

2 3 4

[出力例]

※AtCoderのテストケースより

[入力例]

2 1 3 5 4 7 6

1 5 6 7 2 4 3

[出力例]

[入力例]

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

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

[出力例]

Yes

[入力例]

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

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

[出力例]

Yes

■参照サイト
AtCoder Regular Contest 136

2022年2月27日2022年2月27日

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

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

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

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

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

// 説き直し.
// https://img.atcoder.jp/abc147/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--)
#define all(x) x.begin(), x.end()
int a[101][101], b[101][101];

int main(){
    
    // 1. 入力情報.
    int H, W;
    scanf("%d %d", &H, &W);
    rep(i, H) rep(j, W) scanf("%d", &a[i + 1][j + 1]);
    rep(i, H) rep(j, W) scanf("%d", &b[i + 1][j + 1]);
    
    // 2. dp更新.
    bitset<50505> dp[H + 2][W + 2];
    dp[1][1][25000 + abs(a[1][1] - b[1][1])] = true;
    rep(k, H + W + 1){
        rep(i, min(k + 1, H + 1)){
            int j = k - i;
            if(!i || !j) continue;
            if(i > H) continue;
            if(j > W) continue;
            
            // 今回分取得.
            bitset<50505> dp00 = dp[i][j];
            bitset<50505> dp01 = dp[i][j];
            bitset<50505> dp10 = dp[i][j];
            bitset<50505> dp11 = dp[i][j];
            
            // マス(i, j) -> マス(i + 1, j).
            dp[i + 1][j] |= (dp00 <<= abs(a[i + 1][j] - b[i + 1][j]));
            dp[i + 1][j] |= (dp01 >>= abs(a[i + 1][j] - b[i + 1][j]));
            
            // マス(i, j) -> マス(i, j + 1).
            dp[i][j + 1] |= (dp10 <<= abs(a[i][j + 1] - b[i][j + 1]));
            dp[i][j + 1] |= (dp11 >>= abs(a[i][j + 1] - b[i][j + 1]));
        }
    }
    
    // 3. 文字列化.
    string dpStr = dp[H][W].to_string();
    reverse(all(dpStr));
    
    // 4. 偏りの最小値は？
    // 4-1. 右側.
    int ans = 202020;
    repx(i, 25000, dpStr.size()){
        if(dpStr[i] == '1'){
            ans = min(ans, i - 25000);
            break;
        }
    }
    
    // 4-2. 左側.
    repr(i, 25000, 0){
        if(dpStr[i] == '1'){
            ans = min(ans, 25000 - i);
            break;
        }
    }
    
    // 5. 出力.
    printf("%d\n", ans);
    return 0;
    
}

// 説き直し.

// https://img.atcoder.jp/abc147/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--)

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

int a[101][101], b[101][101];

int main(){

// 1. 入力情報.

int H, W;

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

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

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

// 2. dp更新.

bitset<50505> dp[H + 2][W + 2];

dp[1][1][25000 + abs(a[1][1] - b[1][1])] = true;

rep(k, H + W + 1){

rep(i, min(k + 1, H + 1)){

int j = k - i;

if(!i || !j) continue;

if(i > H) continue;

if(j > W) continue;

// 今回分取得.

bitset<50505> dp00 = dp[i][j];

bitset<50505> dp01 = dp[i][j];

bitset<50505> dp10 = dp[i][j];

bitset<50505> dp11 = dp[i][j];

// マス(i, j) -> マス(i + 1, j).

dp[i + 1][j] |= (dp00 <<= abs(a[i + 1][j] - b[i + 1][j]));

dp[i + 1][j] |= (dp01 >>= abs(a[i + 1][j] - b[i + 1][j]));

// マス(i, j) -> マス(i, j + 1).

dp[i][j + 1] |= (dp10 <<= abs(a[i][j + 1] - b[i][j + 1]));

dp[i][j + 1] |= (dp11 >>= abs(a[i][j + 1] - b[i][j + 1]));

}

// 3. 文字列化.

string dpStr = dp[H][W].to_string();

reverse(all(dpStr));

// 4. 偏りの最小値は？

// 4-1. 右側.

int ans = 202020;

repx(i, 25000, dpStr.size()){

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

ans = min(ans, i - 25000);

break;

}

// 4-2. 左側.

repr(i, 25000, 0){

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

ans = min(ans, 25000 - i);

break;

}

// 5. 出力.

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

return 0;

}

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

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

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

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

[入力例]
2 2
1 5
7 11
3 8
21 25

[出力例]
2

[入力例]
3 3
76 5 11
7 0 35
39 45 7
3 39 1
0 15 47
7 77 2

[出力例]
3

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

[出力例]
0

[入力例]

2 2

1 2

3 4

2 1

[出力例]

※AtCoderテストケースより

[入力例]

2 3

1 10 80

80 10 1

1 2 3

4 5 6

[出力例]

※AtCoderテストケースより

[入力例]

2 2

1 5

7 11

3 8

21 25

[出力例]

[入力例]

3 3

76 5 11

7 0 35

39 45 7

3 39 1

0 15 47

7 77 2

[出力例]

[入力例]

3 5

8 12 9 7 0

8 10 14 6 10

0 17 18 8 3

5 18 12 2 6

11 9 1 10 18

1 10 17 12 1

[出力例]

■参照サイト
AtCoder Beginner Contest 147

C++の練習を兼ねて, AtCoder Beginner Contest 243 の 問題C (Collision 2) ～ 問題D (Moves on Binary Tree) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 241 の 問題C (Construct Highway) ～ 問題D (Sequence Query) を解いてみた.

C++の練習を兼ねて, エクサウィザーズ 2019 の 問題D (Modulo Operations) を解いてみた.

C++の練習を兼ねて, Mujin Programming Challenge 2017 の 問題A (Robot Racing) を解いてみた.

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

C++の練習を兼ねて, エクサウィザーズ 2019 の 問題C (Snuke the Wizard) を解いてみた.

C++の練習を兼ねて, キーエンス プログラミング コンテスト 2019 の 問題D (Double Landscape) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 136 の 問題A (A ↔ BB) ～ 問題B (Triple Shift) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 243 の問題C (Collision 2) ～問題D (Moves on Binary Tree) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 241 の問題C (Construct Highway) ～問題D (Sequence Query) を解いてみた.

C++の練習を兼ねて, エクサウィザーズ 2019 の問題D (Modulo Operations) を解いてみた.

C++の練習を兼ねて, Mujin Programming Challenge 2017 の問題A (Robot Racing) を解いてみた.

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

C++の練習を兼ねて, エクサウィザーズ 2019 の問題C (Snuke the Wizard) を解いてみた.

C++の練習を兼ねて, キーエンスプログラミングコンテスト 2019 の問題D (Double Landscape) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 136 の問題A (A ↔ BB) ～問題B (Triple Shift) を解いてみた.

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