C++ | 個人用メモ帳

2021年12月31日

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

C++の練習を兼ねて, AtCoder Regular Contest 050 の問題C (LCM 111) を解いてみた.

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

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

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

// 解き直し.
// https://img.atcoder.jp/data/arc/050/review.pdf
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vl = vector<LL>;
using vvl = vector<vl>;
#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--)

// Fermat's little theorem から, 大きな冪乗の計算を行う.
// -> 但し, 割る数が, 素数と限らないので, 逆数計算に使用しないこと.
// @param a: べき乗したい正整数.
// @param b: 指数.
// @param m: 割る数.
// @return:  べき乗した計算結果(mod版).
LL mPow(LL a, LL b, LL m){
    LL t = 1;
    while(b){
        if(b & 1) t = (t * a) % m;
        a = a * a % m;
        b >>= 1;
    }
    return t;
}

// 行列乗算を行う.
// @param a: 行列.
// @param b: 行列.
// @param m: 割る数.
// @return:  計算結果(mod版).
vvl matrixMultiplication(vvl &a, vvl &b, LL m){
    int n = a.size();
    vvl ret(n, vl(n, 0LL));
    rep(i, n){
        rep(j, n){
            LL t = 0;
            rep(k, n){
                t += a[i][k] * b[k][j];
                t %= m;
            }
            ret[i][j] = t;
        }
    }
    return ret;
}

int main(){
    
    // 1. 入力情報.
    LL A, B, M;
    scanf("%lld %lld %lld", &A, &B, &M);
    
    // 2. (2, 2)行列のべき乗.
    auto f = [&](LL b, LL d, LL m) -> vvl{
        // 2-1. 返却用行列.
        vvl t(2, vl(2, 0LL));
        rep(i, 2) t[i][i] = 1;
        
        // 2-2. 基準とする行列.
        vvl a(2, vl(2, 0LL));
        a[0][0] = mPow(10LL, d, m);
        a[0][1] = a[1][1] = 1;
        
        // 2-3. べき乗計算.
        while(b){
            if(b & 1) t = matrixMultiplication(t, a, m);
            a = matrixMultiplication(a, a, m);
            b >>= 1;
        }
        
        // 2-4. 返却.
        return t;
    };
    
    // 3. one(A).
    // -> 解説の漸化式を, 以下のような行列と見る.
    // | a[k + 1] | = | 10  1 | * | a[k] |
    // |       1  |   |  0  1 |   |   1  |
    //
    vvl matrixA = f(A - 1, 1LL, M);
    LL oneA = (matrixA[0][0] + matrixA[0][1]) % M;
    
    // 4. one(B) / one(D).
    // -> 解説の漸化式を, 以下のような行列と見る.
    // | a[k + 1] | = | (10 の D乗)  1 | * | a[k] |
    // |       1  |   |         0    1 |   |   1  |
    //
    LL D = __gcd(A, B);
    vvl matrixBD = f(B / D - 1, D, M);
    LL oneBD = (matrixBD[0][0] + matrixBD[0][1]) % M;
    
    // 5. 出力.
    printf("%lld\n", oneA * oneBD % M);
    return 0;
    
}

100

// 解き直し.

// https://img.atcoder.jp/data/arc/050/review.pdf

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vl = vector<LL>;

using vvl = vector<vl>;

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

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

// -> 但し, 割る数が, 素数と限らないので, 逆数計算に使用しないこと.

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

// @param b: 指数.

// @param m: 割る数.

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

LL mPow(LL a, LL b, LL m){

LL t = 1;

while(b){

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

a = a * a % m;

b >>= 1;

}

return t;

}

// 行列乗算を行う.

// @param a: 行列.

// @param b: 行列.

// @param m: 割る数.

// @return: 計算結果(mod版).

vvl matrixMultiplication(vvl &a, vvl &b, LL m){

int n = a.size();

vvl ret(n, vl(n, 0LL));

rep(i, n){

rep(j, n){

LL t = 0;

rep(k, n){

t += a[i][k] * b[k][j];

t %= m;

}

ret[i][j] = t;

}

return ret;

}

int main(){

// 1. 入力情報.

LL A, B, M;

scanf("%lld %lld %lld", &A, &B, &M);

// 2. (2, 2)行列のべき乗.

auto f = [&](LL b, LL d, LL m) -> vvl{

// 2-1. 返却用行列.

vvl t(2, vl(2, 0LL));

rep(i, 2) t[i][i] = 1;

// 2-2. 基準とする行列.

vvl a(2, vl(2, 0LL));

a[0][0] = mPow(10LL, d, m);

a[0][1] = a[1][1] = 1;

// 2-3. べき乗計算.

while(b){

if(b & 1) t = matrixMultiplication(t, a, m);

a = matrixMultiplication(a, a, m);

b >>= 1;

}

// 2-4. 返却.

return t;

};

// 3. one(A).

// -> 解説の漸化式を, 以下のような行列と見る.

// | a[k + 1] | = | 10 1 | * | a[k] |

// | 1 | | 0 1 | | 1 |

vvl matrixA = f(A - 1, 1LL, M);

LL oneA = (matrixA[0][0] + matrixA[0][1]) % M;

// 4. one(B) / one(D).

// -> 解説の漸化式を, 以下のような行列と見る.

// | a[k + 1] | = | (10 の D乗) 1 | * | a[k] |

// | 1 | | 0 1 | | 1 |

LL D = __gcd(A, B);

vvl matrixBD = f(B / D - 1, D, M);

LL oneBD = (matrixBD[0][0] + matrixBD[0][1]) % M;

// 5. 出力.

printf("%lld\n", oneA * oneBD % M);

return 0;

}

[入力例]
2 3 100

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

[入力例]
2 2 121

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

[入力例]
10000000000 1 10007

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

[入力例]
2 3 2

[出力例]
1

[入力例]
314159265358979323 846264338327950288 197169399

[出力例]
86533291

[入力例]
2100 2230 20160402

[出力例]
149019

[入力例]
2021 1231 2022

[出力例]
989

[入力例]
20210101 20211231 567

[出力例]
237

[入力例]

2 3 100

[出力例]

※AtCoderのテストケースより

[入力例]

2 2 121

[出力例]

※AtCoderのテストケースより

[入力例]

10000000000 1 10007

[出力例]

825

※AtCoderのテストケースより

[入力例]

2 3 2

[出力例]

[入力例]

314159265358979323 846264338327950288 197169399

[出力例]

86533291

[入力例]

2100 2230 20160402

[出力例]

149019

[入力例]

2021 1231 2022

[出力例]

989

[入力例]

20210101 20211231 567

[出力例]

237

■参照サイト
AtCoder Regular Contest 050

2021年12月30日

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

C++の練習を兼ねて, AtCoder Regular Contest 047 の問題A (タブの開きすぎ) ～問題B (同一円周上) を解いてみた.

■感想.
1. 問題Bは, 方針が見えなかったので, 解説を参考に, AC版に到達できた.
2. マンハッタン距離に関する性質を復習できたので良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

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

int main(){
    
    // 1. 入力情報.
    int N, L;
    char S[101010];
    scanf("%d %d %s", &N, &L, S);
    int l = strlen(S);
    
    // 2. ブラウザをクラッシュさせる回数は？
    int ans = 0, cur = 1;
    rep(i, l){
        if(S[i] == '+'){
            if(cur < L) cur++;
            else        cur = 1, ans++;
        }
        if(S[i] == '-') cur--;
    }
    
    // 3. 出力.
    printf("%d\n", ans);
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

int main(){

// 1. 入力情報.

int N, L;

char S[101010];

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

int l = strlen(S);

// 2. ブラウザをクラッシュさせる回数は？

int ans = 0, cur = 1;

rep(i, l){

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

if(cur < L) cur++;

else cur = 1, ans++;

}

if(S[i] == '-') cur--;

}

// 3. 出力.

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

return 0;

}

[入力例]
6 2
+++-++

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

[入力例]
20 20
++-+-+++--+++++-++++

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

[入力例]
30 3
+++-+++++-++-++-++-++-+++++-++

[出力例]
5

[入力例]
10 1
++++++++++

[出力例]
10

[入力例]

6 2

+++-++

[出力例]

※AtCoderのテストケースより

[入力例]

20 20

++-+-+++--+++++-++++

[出力例]

※AtCoderのテストケースより

[入力例]

30 3

+++-+++++-++-++-++-++-+++++-++

[出力例]

[入力例]

10 1

++++++++++

[出力例]

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

// 解き直し.
// https://www.slideshare.net/chokudai/arc047-57126901
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vl = vector<LL>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
const LL INF = 202020202020202020;
LL x[101010], y[101010];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    LL d1 = -INF, d2 = INF, d3 = -INF, d4 = INF;
    rep(i, N){
        scanf("%lld %lld", &x[i], &y[i]);
        d1 = max(d1, x[i] + y[i]);
        d2 = min(d2, x[i] + y[i]);
        d3 = max(d3, x[i] - y[i]);
        d4 = min(d4, x[i] - y[i]);
    }
    
    // 2. D / 2.
    LL D = max(d1 - d2, d3 - d4) / 2;
    
    // 3. Px, Py の 洗い出し.
    vl px, py;
    px.pb(d1 - D);
    px.pb(d2 + D);
    py.pb(d3 - D);
    py.pb(d4 + D);
    
    // 4. 点 P.
    LL ansX = INF, ansY = INF;
    for(auto &cx : px){
        for(auto &cy : py){
            // 45度逆回転 で チェック.
            bool ok = true;
            LL tx = (cx + cy) / 2;
            LL ty = (cx - cy) / 2;
            LL mDistance = abs(x[0] - tx) + abs(y[0] - ty);
            repx(i, 1, N){
                if(mDistance != (abs(x[i] - tx) + abs(y[i] - ty))){
                    ok = false;
                    break;
                }
            }
            
            // 見つかった場合.
            if(ok){
                ansX = tx;
                ansY = ty;
                break;
            }
        }
    }
    assert(ansX != INF && ansY != INF);
    
    // 5. 出力.
    printf("%lld %lld\n", ansX, ansY);
    return 0;
    
}

// 解き直し.

// https://www.slideshare.net/chokudai/arc047-57126901

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vl = vector<LL>;

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

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

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

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

#define pb push_back

const LL INF = 202020202020202020;

LL x[101010], y[101010];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

LL d1 = -INF, d2 = INF, d3 = -INF, d4 = INF;

rep(i, N){

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

d1 = max(d1, x[i] + y[i]);

d2 = min(d2, x[i] + y[i]);

d3 = max(d3, x[i] - y[i]);

d4 = min(d4, x[i] - y[i]);

}

// 2. D / 2.

LL D = max(d1 - d2, d3 - d4) / 2;

// 3. Px, Py の洗い出し.

vl px, py;

px.pb(d1 - D);

px.pb(d2 + D);

py.pb(d3 - D);

py.pb(d4 + D);

// 4. 点 P.

LL ansX = INF, ansY = INF;

for(auto &cx : px){

for(auto &cy : py){

// 45度逆回転でチェック.

bool ok = true;

LL tx = (cx + cy) / 2;

LL ty = (cx - cy) / 2;

LL mDistance = abs(x[0] - tx) + abs(y[0] - ty);

repx(i, 1, N){

if(mDistance != (abs(x[i] - tx) + abs(y[i] - ty))){

ok = false;

break;

}

// 見つかった場合.

if(ok){

ansX = tx;

ansY = ty;

break;

}

assert(ansX != INF && ansY != INF);

// 5. 出力.

printf("%lld %lld\n", ansX, ansY);

return 0;

}

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

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

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

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

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

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

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

[出力例]
3 4

[入力例]
5
8 -2
4 -4
5 7
2 4
0 0

[出力例]
5 1

[入力例]
10
1 1
2 0
3 15
4 -2
-3 5
-4 6
17 9
12 0
-1 11
5 -3

[出力例]
7 7

[入力例]

1 2

3 4

2 5

[出力例]

2 3

※AtCoderのテストケースより

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

1 4

[入力例]

0 1

1 0

-1 0

[出力例]

0 -2016

※AtCoderのテストケースより

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

0 0

[入力例]

4 5

1 4

3 2

[出力例]

3 4

[入力例]

8 -2

4 -4

5 7

2 4

0 0

[出力例]

5 1

[入力例]

1 1

2 0

3 15

4 -2

-3 5

-4 6

17 9

12 0

-1 11

5 -3

[出力例]

7 7

■参照サイト
AtCoder Regular Contest 047

2021年12月29日

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

C++の練習を兼ねて, AtCoder Regular Contest 021 の問題A (DEAD END) ～問題B (Your Numbers are XORed…) を解いてみた.

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

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

■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--)
int a[4][4];

int main(){
    
    // 1. 入力情報.
    rep(i, 4) rep(j, 4) scanf("%d", &a[i][j]);
    
    // 2. 判定.
    bool ok = false;
    rep(i, 4){
        rep(j, 4){
            // 上下.
            if(i < 3 && a[i][j] == a[i + 1][j]) ok = true;
            
            // 左右.
            if(j < 3 && a[i][j] == a[i][j + 1]) ok = true;
        }
    }
    
    // 3. 出力.
    printf("%s\n", ok ? "CONTINUE" : "GAMEOVER");
    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 a[4][4];

int main(){

// 1. 入力情報.

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

// 2. 判定.

bool ok = false;

rep(i, 4){

rep(j, 4){

// 上下.

if(i < 3 && a[i][j] == a[i + 1][j]) ok = true;

// 左右.

if(j < 3 && a[i][j] == a[i][j + 1]) ok = true;

}

// 3. 出力.

printf("%s\n", ok ? "CONTINUE" : "GAMEOVER");

return 0;

}

[入力例]
2 8 2 2
32 2 8 8
4 64 2 128
2 8 4 2

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

[入力例]
2 4 16 4
8 32 128 8
2 64 16 2
32 4 32 4

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

[入力例]
2 4 2 4
4 2 4 2
2 4 2 4
4 2 4 2

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

[入力例]
2 4 8 16
4 8 16 32
8 16 32 64
16 32 64 128

[出力例]
GAMEOVER

[入力例]
2 2 2 2
8 8 8 8
2 2 2 2
8 8 8 8

[出力例]
CONTINUE

[入力例]
256 512 128 2048
128 1024 1024 512
256 2048 128 256
512 1024 2048 512

[出力例]
CONTINUE

[入力例]

2 8 2 2

32 2 8 8

4 64 2 128

2 8 4 2

[出力例]

CONTINUE

※AtCoderのテストケースより

[入力例]

2 4 16 4

8 32 128 8

2 64 16 2

32 4 32 4

[出力例]

GAMEOVER

※AtCoderのテストケースより

[入力例]

2 4 2 4

4 2 4 2

2 4 2 4

4 2 4 2

[出力例]

GAMEOVER

※AtCoderのテストケースより

[入力例]

2 4 8 16

4 8 16 32

8 16 32 64

16 32 64 128

[出力例]

GAMEOVER

[入力例]

2 2 2 2

8 8 8 8

2 2 2 2

8 8 8 8

[出力例]

CONTINUE

[入力例]

256 512 128 2048

128 1024 1024 512

256 2048 128 256

512 1024 2048 512

[出力例]

CONTINUE

■C++版プログラム(問題B／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 a[101010], b[101010];

int main(){
    
    // 1. 入力情報.
    int L;
    scanf("%d", &L);
    rep(i, L) scanf("%d", &b[i]);
    
    // 2. 存在すると仮定.
    rep(i, L - 1) a[i + 1] = a[i] ^ b[i];
    
    // 3. 出力.
    if(b[L - 1] == (a[0] ^ a[L - 1])) rep(i, L) printf("%d\n", a[i]);
    else                              puts("-1");
    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 a[101010], b[101010];

int main(){

// 1. 入力情報.

int L;

scanf("%d", &L);

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

// 2. 存在すると仮定.

rep(i, L - 1) a[i + 1] = a[i] ^ b[i];

// 3. 出力.

if(b[L - 1] == (a[0] ^ a[L - 1])) rep(i, L) printf("%d\n", a[i]);

else puts("-1");

return 0;

}

[入力例]
2
1
1

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

[入力例]
3
1
4
1

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

[入力例]
3
1
2
3

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

[入力例]
20
50
120
25
36
40
16
110
118
5
26
43
80
107
116
99
46
104
35
25
51

[出力例]
0
50
74
83
119
95
79
33
87
82
72
99
51
88
44
79
97
9
42
51

[入力例]
10
116834405
48108109
25179808
44419470
67536150
119978244
54763173
132583455
59949508
52125290

[出力例]
0
116834405
69784104
94954632
118304006
51095568
70062356
124686257
9019310
52125290

100

101

[入力例]

[出力例]

※AtCoderのテストケースより

[入力例]

[出力例]

-1

※AtCoderのテストケースより

[入力例]

[出力例]

※AtCoderのテストケースより

[入力例]

120

110

118

107

116

104

[出力例]

119

[入力例]

116834405

48108109

25179808

44419470

67536150

119978244

54763173

132583455

59949508

52125290

[出力例]

116834405

69784104

94954632

118304006

51095568

70062356

124686257

9019310

52125290

■参照サイト
AtCoder Regular Contest 021

2021年12月29日

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

C++の練習を兼ねて, AtCoder Regular Contest 132 の問題A (Permutation Grid) ～問題B (Shift and Reverse) を解いてみた.

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

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

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

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%d", &R[i + 1]);
    rep(i, N) scanf("%d", &C[i + 1]);
    
    // 2. 文字列生成.
    int Q;
    scanf("%d", &Q);
    string ans;
    rep(i, Q){
        int r, c;
        scanf("%d %d", &r, &c);
        if(R[r] + C[c] > N) ans.pb('#');
        else                ans.pb('.');
    }
    
    // 3. 出力.
    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

int R[101010], C[101010];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

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

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

// 2. 文字列生成.

int Q;

scanf("%d", &Q);

string ans;

rep(i, Q){

int r, c;

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

if(R[r] + C[c] > N) ans.pb('#');

else ans.pb('.');

}

// 3. 出力.

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

return 0;

}

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

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

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

[出力例]
.#.##.##.#

[入力例]

5 2 3 4 1

4 2 3 1 5

1 5

5 1

1 1

2 2

3 3

4 4

5 5

[出力例]

#.#.#.#

※AtCoderのテストケースより

[入力例]

1 3 7 6 5 4 2

6 4 2 7 1 5 3

1 5

3 3

7 2

6 1

5 7

2 5

4 3

3 1

6 3

5 4

[出力例]

.#.##.##.#

■C++版プログラム(問題B／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 p[101010];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%d", &p[i]);
    
    // 2. 1, 2 の 位置.
    int at1 = 0, at2 = 0;
    rep(i, N){
        if(p[i] == 1) at1 = i;
        if(p[i] == 2) at2 = i;
    }
    
    // 3. 操作回数の最小値.
    // 3-1. 1 -> 2 の 順.
    int ans = 2020202020;
    if((at1 + 1) % N == at2){
        // 反転無し.
        ans = min(ans, at1);
        
        // 二回反転.
        ans = min(ans, 2 + (N - at1));
    }
    
    // 3-2. 2 -> 1 の 順.
    if((at2 + 1) % N == at1){
        // 初回反転.
        ans = min(ans, 1 + (N - 1 - at1));
        
        // 最後に反転.
        ans = min(ans, 1 + (at1 + 1) % N);
    }
    
    // 4. 出力.
    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 p[101010];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

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

// 2. 1, 2 の位置.

int at1 = 0, at2 = 0;

rep(i, N){

if(p[i] == 1) at1 = i;

if(p[i] == 2) at2 = i;

}

// 3. 操作回数の最小値.

// 3-1. 1 -> 2 の順.

int ans = 2020202020;

if((at1 + 1) % N == at2){

// 反転無し.

ans = min(ans, at1);

// 二回反転.

ans = min(ans, 2 + (N - at1));

}

// 3-2. 2 -> 1 の順.

if((at2 + 1) % N == at1){

// 初回反転.

ans = min(ans, 1 + (N - 1 - at1));

// 最後に反転.

ans = min(ans, 1 + (at1 + 1) % N);

}

// 4. 出力.

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

return 0;

}

[入力例]
3
1 3 2

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

[入力例]
2
2 1

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

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

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

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

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

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

[出力例]
7

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

[出力例]
11

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

[出力例]
25

[入力例]

1 3 2

[出力例]

※AtCoderのテストケースより

[入力例]

2 1

[出力例]

※AtCoderのテストケースより

[入力例]

2 3 4 5 6 7 8 9 10 1

[出力例]

※AtCoderのテストケースより

[入力例]

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

[出力例]

※AtCoderのテストケースより

[入力例]

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

[出力例]

[入力例]

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

[出力例]

[入力例]

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

[出力例]

■参照サイト
AtCoder Regular Contest 132

2021年12月25日2021年12月25日

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

C++の練習を兼ねて, AtCoder Regular Contest 057 の問題C (2乗根) を解いてみた.

■感想.
1. 問題Cは, 方針が見えなかったので, 解説を参考に, AC版に到達できた.
2. 個人的には, 実装に非常に苦労したものの, 文字列ベースで, 大きな桁数を持つ, 整数同士の加算, 乗算の実装訓練が積めたので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/data/arc/057/editorial.pdf
// 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 pob pop_back
#define pub push_back
#define all(x) x.begin(), x.end()

// 与えられた文字列を整数と見て, 0 ～ 9倍した値を計算.
// @param s: 正整数.
// @return:  計算結果.
vs multiplyBetweenZeroToNine(string s){
    int sl = s.size();
    vs ret;
    
    // 0 ～ 9倍.
    rep(i, 10){
        string v;
        int c = 0;
        repr(j, sl - 1, 0){
            string x = to_string((s[j] - '0') * i + c);
            int xl = x.size();
            if(xl == 1){
                v.pub(x[0]);
                c = 0;
            }
            if(xl == 2){
                v.pub(x[1]);
                c = x[0] - '0';
                if(!j) v.pub(x[0]);
            }
            assert(xl >= 1 && xl <= 2);
        }
        reverse(all(v));
        ret.pub(v);
    }
    
    // 返却.
    return ret;
}

// 与えられた文字列を整数と見て, 乗算を行う.
// @param s: 正整数.
// @param t: 正整数.
// @return:  計算結果.
string sMultiply(string s, string t){
    string ret;
    int sl = s.size(), tl = t.size();
    vs s09 = multiplyBetweenZeroToNine(s);
    
    // 各桁単体で, 乗算.
    vs tCalc;
    repr(i, tl - 1, 0){
        string v = s09[t[i] - '0'];
        int vl = v.size();
        string zb(tl - 1 - i, '0');
        string zf(sl + tl - vl - zb.size(), '0');
        v = zf + v + zb;
        tCalc.pub(v);
    }
    
    // 集計.
    ret = tCalc[0];
    repx(i, 1, tl){
        string v;
        int c = 0;
        repr(j, sl + tl - 1, 0){
            string x = to_string((ret[j] - '0') + (tCalc[i][j] - '0') + c);
            int xl = x.size();
            if(xl == 1){
                v.pub(x[0]);
                c = 0;
            }
            if(xl == 2){
                v.pub(x[1]);
                c = x[0] - '0';
                if(!j) v.pub(x[0]);
            }
            assert(xl >= 1 && xl <= 2);
        }
        reverse(all(v));
        ret = v;
    }
    
    // 先頭が, '0' ならば 削除.
    if(ret[0] == '0') ret = ret.substr(1);
    
    // 返却.
    return ret;
}

// 与えられた文字列を整数と見て, 加算を行う.
// @param s: 正整数.
// @param t: 正整数.
// @return:  計算結果.
string sAdd(string s, string t){
    int sl = s.size();
    int tl = t.size();
    int ml = max(sl, tl) + 1;
    string zs(ml - sl, '0');
    string zt(ml - tl, '0');
    string ns = zs + s;
    string nt = zt + t;
    
    // 各桁を加算.
    string ret;
    int c = 0;
    repr(j, ml - 1, 0){
        string x = to_string((ns[j] - '0') + (nt[j] - '0') + c);
        int xl = x.size();
        if(xl == 1){
            ret.pub(x[0]);
            c = 0;
        }
        if(xl == 2){
            ret.pub(x[1]);
            c = x[0] - '0';
            if(!j) ret.pub(x[0]);
        }
        assert(xl >= 1 && xl <= 2);
    }
    while(ret.size() < ml) ret.pub('0');
    if(ret.back() == '0') ret.pob();
    reverse(all(ret));
    
    // 返却.
    return ret;
}

int main(){
    
    // 1. 入力情報.
    char c[1010];
    scanf("%s", c);
    string s(c);
    
    // ex.
    // 20211225 を 使って, 0 ～ 9倍した場合.
    // 
    // 000000000
    // 020211225
    // 040422450
    // 060633675
    // 080844900
    // 101056125
    // 121267350
    // 141478575
    // 161689800
    // 181901025
    // 
    // vs x = multiplyBetweenZeroToNine("20211225");
    // for(auto &p : x) printf("%s\n", p.c_str());
    
    // ex.
    // 2021 * 2022 -> 4086462 の 計算.
    // printf("%s\n", sMultiply("2021", "2022").c_str());
    // 
    // 3456 * 789 -> 2726784 の 計算.
    // printf("%s\n", sMultiply("3456", "789").c_str());
    // 
    // 20211225 * 20220101 -> 408673010833725 の 計算.
    // printf("%s\n", sMultiply("20211225", "20220101").c_str());
    // 
    // 31622776601683793319 * 314159265358979323846264338327
    // -> 9934588265796101234122867437613016024182958237313 の 計算.
    // printf("%s\n", sMultiply("31622776601683793319", "314159265358979323846264338327").c_str());
    // 
    // 12 + 15 -> 27 の 計算.
    // printf("%s\n", sAdd("12", "15").c_str());
    // 
    // 98765 + 4321 -> 103086 の 計算.
    // printf("%s\n", sAdd("98765", "4321").c_str());
    // 
    // 12345 + 54321 -> 66666 の 計算.
    // printf("%s\n", sAdd("12345", "54321").c_str());
    // 
    // 15249 + 86073 -> 101322 の 計算.
    // printf("%s\n", sAdd("15249", "86073").c_str());
    
    // 2. 事前準備(解説通り).
    // 2-1. A, A + 1 の 二乗.
    string a0 = sMultiply(s, s);
    string s1 = sAdd(s, "1");
    string a1 = sMultiply(s1, s1);
    
    // 2-2. 桁数揃える('0' 埋め).
    while(a0.size() < a1.size()) a0.insert(a0.begin(), '0');
    assert(a0.size() == a1.size());
    // printf("%s\n", a0.c_str());
    // printf("%s\n", a1.c_str());
    
    // 2-3. 偶数桁('0' 埋め).
    int odd = 0;
    if(a0.size() & 1){
        a0.pub('0');
        a1.pub('0');
        odd++;
    }
    
    // 3. N を 探索.
    string ans;
    rep(t, 101){
        string z(t * 2, '0');
        a0 = a0 + z;
        a1 = a1 + z;
        // printf("a0=%s a1=%s\n", a0.c_str(), a1.c_str());
        
        // 先頭 d 桁.
        bool ok = false;
        int al = a0.size();
        
        repex(d, 2 - odd, al, 2){
            // N の 候補.
            string n0 = a0.substr(0, d);
            string n1 = sAdd(n0, "1");
            string zb0(al - n0.size(), '0');
            string zb1(al - n1.size(), '0');
            string tn0 = n0 + zb0;
            string tn1 = n1 + zb1;
            // printf("n0=%s tn0=%s n1=%s tn1=%s\n", n0.c_str(), tn0.c_str(), n1.c_str(), tn1.c_str());
            
            // 判定(その1).
            if(tn0 >= a0 && tn0 < a1){
                if(n0[0] == '0') ans = n0.substr(1);
                else             ans = n0;
                ok = true;
                break;
            }
            
            // 判定(その2).
            // 41.txt, 42.txt で, WA版 だったため, 修正.
            if(tn1 >= a0 && tn1 < a1){
                if(n1[0] == '0') ans = n1.substr(1);
                else             ans = n1;
                ok = true;
                break;
            }
        }
        
        // 見つかった場合.
        if(ok) break;
    }
    
    // 4. 出力.
    printf("%s\n", ans.c_str());
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

// 解き直し.

// https://img.atcoder.jp/data/arc/057/editorial.pdf

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

#define pub push_back

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

// 与えられた文字列を整数と見て, 0 ～ 9倍した値を計算.

// @param s: 正整数.

// @return: 計算結果.

vs multiplyBetweenZeroToNine(string s){

int sl = s.size();

vs ret;

// 0 ～ 9倍.

rep(i, 10){

string v;

int c = 0;

repr(j, sl - 1, 0){

string x = to_string((s[j] - '0') * i + c);

int xl = x.size();

if(xl == 1){

v.pub(x[0]);

c = 0;

}

if(xl == 2){

v.pub(x[1]);

c = x[0] - '0';

if(!j) v.pub(x[0]);

}

assert(xl >= 1 && xl <= 2);

}

reverse(all(v));

ret.pub(v);

}

// 返却.

return ret;

}

// 与えられた文字列を整数と見て, 乗算を行う.

// @param s: 正整数.

// @param t: 正整数.

// @return: 計算結果.

string sMultiply(string s, string t){

string ret;

int sl = s.size(), tl = t.size();

vs s09 = multiplyBetweenZeroToNine(s);

// 各桁単体で, 乗算.

vs tCalc;

repr(i, tl - 1, 0){

string v = s09[t[i] - '0'];

int vl = v.size();

string zb(tl - 1 - i, '0');

string zf(sl + tl - vl - zb.size(), '0');

v = zf + v + zb;

tCalc.pub(v);

}

// 集計.

ret = tCalc[0];

repx(i, 1, tl){

string v;

int c = 0;

repr(j, sl + tl - 1, 0){

string x = to_string((ret[j] - '0') + (tCalc[i][j] - '0') + c);

int xl = x.size();

if(xl == 1){

v.pub(x[0]);

c = 0;

}

if(xl == 2){

v.pub(x[1]);

c = x[0] - '0';

if(!j) v.pub(x[0]);

}

assert(xl >= 1 && xl <= 2);

}

reverse(all(v));

ret = v;

}

// 先頭が, '0' ならば削除.

if(ret[0] == '0') ret = ret.substr(1);

// 返却.

return ret;

}

// 与えられた文字列を整数と見て, 加算を行う.

// @param s: 正整数.

// @param t: 正整数.

// @return: 計算結果.

string sAdd(string s, string t){

int sl = s.size();

int tl = t.size();

int ml = max(sl, tl) + 1;

string zs(ml - sl, '0');

string zt(ml - tl, '0');

string ns = zs + s;

string nt = zt + t;

// 各桁を加算.

string ret;

int c = 0;

repr(j, ml - 1, 0){

string x = to_string((ns[j] - '0') + (nt[j] - '0') + c);

int xl = x.size();

if(xl == 1){

ret.pub(x[0]);

c = 0;

}

if(xl == 2){

ret.pub(x[1]);

c = x[0] - '0';

if(!j) ret.pub(x[0]);

}

assert(xl >= 1 && xl <= 2);

}

while(ret.size() < ml) ret.pub('0');

if(ret.back() == '0') ret.pob();

reverse(all(ret));

// 返却.

return ret;

}

int main(){

// 1. 入力情報.

char c[1010];

scanf("%s", c);

string s(c);

// ex.

// 20211225 を使って, 0 ～ 9倍した場合.

// 000000000

// 020211225

// 040422450

// 060633675

// 080844900

// 101056125

// 121267350

// 141478575

// 161689800

// 181901025

// vs x = multiplyBetweenZeroToNine("20211225");

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

// ex.

// 2021 * 2022 -> 4086462 の計算.

// printf("%s\n", sMultiply("2021", "2022").c_str());

// 3456 * 789 -> 2726784 の計算.

// printf("%s\n", sMultiply("3456", "789").c_str());

// 20211225 * 20220101 -> 408673010833725 の計算.

// printf("%s\n", sMultiply("20211225", "20220101").c_str());

// 31622776601683793319 * 314159265358979323846264338327

// -> 9934588265796101234122867437613016024182958237313 の計算.

// printf("%s\n", sMultiply("31622776601683793319", "314159265358979323846264338327").c_str());

// 12 + 15 -> 27 の計算.

// printf("%s\n", sAdd("12", "15").c_str());

// 98765 + 4321 -> 103086 の計算.

// printf("%s\n", sAdd("98765", "4321").c_str());

// 12345 + 54321 -> 66666 の計算.

// printf("%s\n", sAdd("12345", "54321").c_str());

// 15249 + 86073 -> 101322 の計算.

// printf("%s\n", sAdd("15249", "86073").c_str());

// 2. 事前準備(解説通り).

// 2-1. A, A + 1 の二乗.

string a0 = sMultiply(s, s);

string s1 = sAdd(s, "1");

string a1 = sMultiply(s1, s1);

// 2-2. 桁数揃える('0' 埋め).

while(a0.size() < a1.size()) a0.insert(a0.begin(), '0');

assert(a0.size() == a1.size());

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

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

// 2-3. 偶数桁('0' 埋め).

int odd = 0;

if(a0.size() & 1){

a0.pub('0');

a1.pub('0');

odd++;

}

// 3. N を探索.

string ans;

rep(t, 101){

string z(t * 2, '0');

a0 = a0 + z;

a1 = a1 + z;

// printf("a0=%s a1=%s\n", a0.c_str(), a1.c_str());

// 先頭 d 桁.

bool ok = false;

int al = a0.size();

repex(d, 2 - odd, al, 2){

// N の候補.

string n0 = a0.substr(0, d);

string n1 = sAdd(n0, "1");

string zb0(al - n0.size(), '0');

string zb1(al - n1.size(), '0');

string tn0 = n0 + zb0;

string tn1 = n1 + zb1;

// printf("n0=%s tn0=%s n1=%s tn1=%s\n", n0.c_str(), tn0.c_str(), n1.c_str(), tn1.c_str());

// 判定(その1).

if(tn0 >= a0 && tn0 < a1){

if(n0[0] == '0') ans = n0.substr(1);

else ans = n0;

ok = true;

break;

}

// 判定(その2).

// 41.txt, 42.txt で, WA版だったため, 修正.

if(tn1 >= a0 && tn1 < a1){

if(n1[0] == '0') ans = n1.substr(1);

else ans = n1;

ok = true;

break;

}

// 見つかった場合.

if(ok) break;

}

// 4. 出力.

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

return 0;

}

[入力例]
1414

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

[入力例]
316

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

[入力例]
31415926535897932384626433

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

[入力例]
1

[出力例]
1

[入力例]
3

[出力例]
9

[入力例]
100

[出力例]
1

[入力例]
2021

[出力例]
40845

[入力例]
2022

[出力例]
409

[入力例]
99

[出力例]
99

[入力例]
6683666956608953246189934089371425990037946094722715577162854485114171268233408663920367919525867917

[出力例]
4467140398686638731498801480194475987696605386968501488168403774682433001741290717947510964261028998

[入力例]
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899

[出力例]
152415787751564791571474464067365843004074106033398993610227467007696607026298183353895046888649891435630676833646227616539860497650828260258961517027329730424343528139368390672370167350579

[入力例]
56454760053845953422243613732034661978800055038665136534301641951677146991773695469292399771680255459998392040285990743835137754965296688500005803009866189324487493777613680693035780473318184761620481

[出力例]
31871399327373207577472704494998710448088197344396620930404898037706068693506291937736503041850263469639551715557378903361075958031955071497686490040280520705238693309515154487338261200746958725239791

[入力例]
5030985070267740263115027271190705986153832806252199283818135658343911760033447528438356090831963749515642192222778158992357964886915352912770916696752489458734907596506669059112014213237908818248266413892743143702184963535643856058675237205734895902172738366271118432036164904274015935635597981889020986662605031457585676669570726216641146536677630591926962624207379097357282827038235920681465116560019296192894476569131920504537171187405241700357906257603185189570170461215268547458485135254509062615598792950132386202370545991251063114378044940875537316198682829867668500947754944791483746661309449266971859211017963674048038161991275399238985469713690851801674540489282852894424592325332966283742488093033014048498167054812727586882069887314428050471983311273700014340305985169563222074709353440669223258556837783409863227256251246385544267082251151042255428228250034097985711468506203960661635195964499105185027681543589318667566352625315455409013012408044382148509744504378719140423199692886798

[出力例]
2531081077725689943281083263649946991089389430395661783045309706682327086366686759119550266908076908048888398141892844269448607798118799328411388944231094892452828801792108255204346096146144511408088643188729086382797303495732920938560691922513266755811230804623244048521586809163931062307451839564879639445317223353348193124314992841665605489570325277908205983121238598869999100672593162539628132896674490295517419362184479426549621460581559019336355188990805781286118157245796832409174937820467452885388298207685649687735924480056535197241424775943097312410193168945421342844953491458459256445975307683735283733708876160777916694957419938320823744297629867416618404089020369735760515709069814498245548198348288144465271222988611869777200074659708550820687740586058954143829808016281997260443023002312795730757996699124322869306241909113286448861121065709687219327225250911272899341246791423034847110532457587336597234061948051001562170993059814600959225445159764614909515779704059142383952420223495

[入力例]

1414

[出力例]

※AtCoderテストケースより

[入力例]

316

[出力例]

※AtCoderテストケースより

[入力例]

31415926535897932384626433

[出力例]

9869604401089358618834491

※AtCoderテストケースより

[入力例]

[出力例]

[入力例]

[出力例]

[入力例]

100

[出力例]

[入力例]

2021

[出力例]

40845

[入力例]

2022

[出力例]

409

[入力例]

[出力例]

[入力例]

6683666956608953246189934089371425990037946094722715577162854485114171268233408663920367919525867917

[出力例]

4467140398686638731498801480194475987696605386968501488168403774682433001741290717947510964261028998

[入力例]

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899

[出力例]

152415787751564791571474464067365843004074106033398993610227467007696607026298183353895046888649891435630676833646227616539860497650828260258961517027329730424343528139368390672370167350579

[入力例]

56454760053845953422243613732034661978800055038665136534301641951677146991773695469292399771680255459998392040285990743835137754965296688500005803009866189324487493777613680693035780473318184761620481

[出力例]

31871399327373207577472704494998710448088197344396620930404898037706068693506291937736503041850263469639551715557378903361075958031955071497686490040280520705238693309515154487338261200746958725239791

[入力例]

5030985070267740263115027271190705986153832806252199283818135658343911760033447528438356090831963749515642192222778158992357964886915352912770916696752489458734907596506669059112014213237908818248266413892743143702184963535643856058675237205734895902172738366271118432036164904274015935635597981889020986662605031457585676669570726216641146536677630591926962624207379097357282827038235920681465116560019296192894476569131920504537171187405241700357906257603185189570170461215268547458485135254509062615598792950132386202370545991251063114378044940875537316198682829867668500947754944791483746661309449266971859211017963674048038161991275399238985469713690851801674540489282852894424592325332966283742488093033014048498167054812727586882069887314428050471983311273700014340305985169563222074709353440669223258556837783409863227256251246385544267082251151042255428228250034097985711468506203960661635195964499105185027681543589318667566352625315455409013012408044382148509744504378719140423199692886798

[出力例]

2531081077725689943281083263649946991089389430395661783045309706682327086366686759119550266908076908048888398141892844269448607798118799328411388944231094892452828801792108255204346096146144511408088643188729086382797303495732920938560691922513266755811230804623244048521586809163931062307451839564879639445317223353348193124314992841665605489570325277908205983121238598869999100672593162539628132896674490295517419362184479426549621460581559019336355188990805781286118157245796832409174937820467452885388298207685649687735924480056535197241424775943097312410193168945421342844953491458459256445975307683735283733708876160777916694957419938320823744297629867416618404089020369735760515709069814498245548198348288144465271222988611869777200074659708550820687740586058954143829808016281997260443023002312795730757996699124322869306241909113286448861121065709687219327225250911272899341246791423034847110532457587336597234061948051001562170993059814600959225445159764614909515779704059142383952420223495

■参照サイト
AtCoder Regular Contest 057

2021年12月24日2021年12月24日

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

C++の練習を兼ねて, AtCoder Regular Contest 036 の問題C (偶然ジェネレータ) を解いてみた.

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

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

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

// 解き直し.
// https://www.slideshare.net/chokudai/arc036
// 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 dp[303][303][303];

int main(){
    
    // 1. 入力情報.
    int N, K;
    char c[303];
    scanf("%d %d %s", &N, &K, c);
    
    // 2. 初期化(※0文字目(空文字)を, 1個と見る).
    dp[0][0][0] = 1;
    
    // 3. dp更新.
    rep(i, N){
        // 3-1. (0 の 個数) - (1 の 個数).
        int z = 0, o = 0, q = 0;
        bool ok = true;
        repr(j, i, 0){
            if(c[j] == '0') z++;
            if(c[j] == '1') o++;
            if(c[j] == '?') q++;
            if(abs(z - o) > K + q) ok = false;
        }
        
        // 3-2. 矛盾している場合.
        if(!ok) break;
        
        // 3-3. i文字目をベースに, (i - 1)文字目までの結果を反映.
        rep(j, K + 1){
            rep(k, K + 1){
                // '0' or '?' の 場合.
                if(c[i] == '0' || c[i] == '?'){
                    int nk = max(0, k - 1);
                    dp[i + 1][j + 1][nk] += dp[i][j][k];
                    dp[i + 1][j + 1][nk] %= MOD;
                }
                
                // '1' or '?' の 場合.
                if(c[i] == '1' || c[i] == '?'){
                    int nj = max(0, j - 1);
                    dp[i + 1][nj][k + 1] += dp[i][j][k];
                    dp[i + 1][nj][k + 1] %= MOD;
                }
            }
        }
    }
    
    // 4. 集計.
    LL ans = 0;
    rep(j, K + 1){
        rep(k, K + 1){
            ans += dp[N][j][k];
            ans %= MOD;
        }
    }
    
    // 5. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

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

// 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 dp[303][303][303];

int main(){

// 1. 入力情報.

int N, K;

char c[303];

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

// 2. 初期化(※0文字目(空文字)を, 1個と見る).

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

// 3. dp更新.

rep(i, N){

// 3-1. (0 の個数) - (1 の個数).

int z = 0, o = 0, q = 0;

bool ok = true;

repr(j, i, 0){

if(c[j] == '0') z++;

if(c[j] == '1') o++;

if(c[j] == '?') q++;

if(abs(z - o) > K + q) ok = false;

}

// 3-2. 矛盾している場合.

if(!ok) break;

// 3-3. i文字目をベースに, (i - 1)文字目までの結果を反映.

rep(j, K + 1){

rep(k, K + 1){

// '0' or '?' の場合.

if(c[i] == '0' || c[i] == '?'){

int nk = max(0, k - 1);

dp[i + 1][j + 1][nk] += dp[i][j][k];

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

}

// '1' or '?' の場合.

if(c[i] == '1' || c[i] == '?'){

int nj = max(0, j - 1);

dp[i + 1][nj][k + 1] += dp[i][j][k];

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

}

// 4. 集計.

LL ans = 0;

rep(j, K + 1){

rep(k, K + 1){

ans += dp[N][j][k];

ans %= MOD;

}

// 5. 出力.

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

return 0;

}

[入力例]
9 4
?011?1110

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

[入力例]
9 3
?011?1110

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

[入力例]
9 1
???1?????

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

[入力例]
12 5
???0??1??11?

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

[入力例]
1 1
?

[出力例]
2

[入力例]
2 1
10

[出力例]
1

[入力例]
5 2
?101?

[出力例]
3

[入力例]
7 3
?101??1

[出力例]
6

[入力例]
30 2
?0?11?1?????0?1?01001?101?0?00

[出力例]
0

[入力例]
50 5
1?00010110?1?001?000?0?0111101100??01?10101?1???0?

[出力例]
920

[入力例]
100 5
0?0110?1100????11?10???1?0011?0?10000?1???000??000?11?1???11110?0?1?11?0?011??010011011?1000?10?0010

[出力例]
333080

[入力例]
200 7
?0?11?1?????0?1?01001?101?0?000?001?00?1011??0?10?00?1111010?1?0???10?11?1?0011?00??0100111??????1??01?01?0100011??11?00?????00110?0?1?01?010??10010?0000?1?01??11?0?0??0?10??0???101?1?001??10?0???????

[出力例]
629811174

[入力例]
300 10
1??1?1???????1100101?1100100?1???110?1?11?0011?100?111????10?1110??11??11110001011?11?0?11?0010110?1?0?00?0?01??0?1??000??0000101000?0?0?1?0011??11101?1101010?1101??00?0?0?00??1???1?11?01100???0?11?000??1???01???00?1110?0?11??1?0100?1?0101??11?????0?100?111?001?110?100111?00100?0?10?011111000?00001?

[出力例]
704124254

[入力例]

9 4

?011?1110

[出力例]

※AtCoderのテストケースより

[入力例]

9 3

?011?1110

[出力例]

※AtCoderのテストケースより

[入力例]

9 1

???1?????

[出力例]

※AtCoderのテストケースより

[入力例]

12 5

???0??1??11?

[出力例]

172

※AtCoderのテストケースより

[入力例]

1 1

[出力例]

[入力例]

2 1

[出力例]

[入力例]

5 2

?101?

[出力例]

[入力例]

7 3

?101??1

[出力例]

[入力例]

30 2

?0?11?1?????0?1?01001?101?0?00

[出力例]

[入力例]

50 5

1?00010110?1?001?000?0?0111101100??01?10101?1???0?

[出力例]

920

[入力例]

100 5

0?0110?1100????11?10???1?0011?0?10000?1???000??000?11?1???11110?0?1?11?0?011??010011011?1000?10?0010

[出力例]

333080

[入力例]

200 7

?0?11?1?????0?1?01001?101?0?000?001?00?1011??0?10?00?1111010?1?0???10?11?1?0011?00??0100111??????1??01?01?0100011??11?00?????00110?0?1?01?010??10010?0000?1?01??11?0?0??0?10??0???101?1?001??10?0???????

[出力例]

629811174

[入力例]

300 10

1??1?1???????1100101?1100100?1???110?1?11?0011?100?111????10?1110??11??11110001011?11?0?11?0010110?1?0?00?0?01??0?1??000??0000101000?0?0?1?0011??11101?1101010?1101??00?0?0?00??1???1?11?01100???0?11?000??1???01???00?1110?0?11??1?0100?1?0101??11?????0?100?111?001?110?100111?00100?0?10?011111000?00001?

[出力例]

704124254

■参照サイト
AtCoder Regular Contest 036

2021年12月21日2021年12月21日

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

C++の練習を兼ねて, AtCoder Regular Contest 045 の問題C (エックスオア多橋君) を解いてみた.

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

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

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

// 解き直し.
// https://www.slideshare.net/chokudai/arc045
// 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 pb push_back
int memo[101010];

struct edge{
    int n;
    LL c;
};

vector<edge> G[101010];

int main(){
    
    // 1. 入力情報.
    int N;
    LL X;
    scanf("%d %lld", &N, &X);
    rep(i, N - 1){
        int x, y;
        LL c;
        scanf("%d %d %lld", &x, &y, &c);
        x--, y--;
        G[x].pb(edge{y, c});
        G[y].pb(edge{x, c});
    }
    
    // 2. dfs.
    // https://ja.wikipedia.org/wiki/深さ優先探索
    map<LL, LL> m;
    LL ans = 0;
    auto dfs = [&](auto&& self, int c, int b, LL cXor) -> void{
        // 2-1. 訪問済フラグ設定.
        memo[c] = 1;
        
        // 2-2. 数え上げ.
        ans += m[cXor ^ X];
        
        // 2-3. 根 から 頂点 c までの単純パス の XOR値 の 出現回数 を 保存.
        m[cXor]++;
        
        // 2-4. 次へ.
        for(auto &e : G[c]) if(!memo[e.n]) self(self, e.n, c, cXor ^ e.c);
    };
    dfs(dfs, 0, -1, 0LL);
    
    // 3. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

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

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

int memo[101010];

struct edge{

int n;

LL c;

};

vector<edge> G[101010];

int main(){

// 1. 入力情報.

int N;

LL X;

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

rep(i, N - 1){

int x, y;

LL c;

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

x--, y--;

G[x].pb(edge{y, c});

G[y].pb(edge{x, c});

}

// 2. dfs.

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

map<LL, LL> m;

LL ans = 0;

auto dfs = [&](auto&& self, int c, int b, LL cXor) -> void{

// 2-1. 訪問済フラグ設定.

memo[c] = 1;

// 2-2. 数え上げ.

ans += m[cXor ^ X];

// 2-3. 根から頂点 c までの単純パスの XOR値の出現回数を保存.

m[cXor]++;

// 2-4. 次へ.

for(auto &e : G[c]) if(!memo[e.n]) self(self, e.n, c, cXor ^ e.c);

};

dfs(dfs, 0, -1, 0LL);

// 3. 出力.

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

return 0;

}

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

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

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

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

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

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

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

[出力例]
3

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

[出力例]
5

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

[出力例]
11

[入力例]

6 7

1 2 5

2 3 3

3 4 6

2 5 2

5 6 7

[出力例]

※AtCoderテストケースより

[入力例]

6 3

1 2 1

2 3 3

3 4 2

4 5 3

4 6 1

[出力例]

※AtCoderテストケースより

[入力例]

10 1

9 10 1

6 10 1

5 2 1

8 6 1

4 5 1

7 6 0

3 8 0

3 1 1

8 2 0

[出力例]

※AtCoderテストケースより

[入力例]

3 0

1 2 0

1 3 0

[出力例]

[入力例]

10 5

1 4 3

1 5 1

9 5 4

5 10 1

3 1 5

2 3 9

2 6 2

2 7 6

7 8 5

[出力例]

[入力例]

20 21

6 5 16

6 10 27

5 4 21

5 11 18

5 3 9

1 4 3

2 4 8

3 7 1

8 3 11

8 12 10

8 13 23

7 15 19

7 9 18

9 20 12

14 9 25

1 16 13

17 1 22

16 18 27

19 16 12

[出力例]

■参照サイト
AtCoder Regular Contest 045

2021年12月20日

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

C++の練習を兼ねて, AtCoder Beginner Contest 232 の問題C (Graph Isomorphism) ～問題D (Weak Takahashi) を解いてみた.

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

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

■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 vi = vector<int>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
#define a first
#define b second
#define all(x) x.begin(), x.end()

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    vp v1, v2;
    rep(i, M){
        int a, b;
        scanf("%d %d", &a, &b);
        a--, b--;
        v1.pb({a, b});
    }
    rep(i, M){
        int c, d;
        scanf("%d %d", &c, &d);
        c--, d--;
        v2.pb({c, d});
    }
    
    // 2. sort.
    sort(all(v1));
    
    // 3. 同じ形か？
    vi z(N);
    iota(all(z), 0);
    bool ok = false;
    do{
        // 3-1. ある数列を対応させる.
        vp v;
        rep(i, M){
            int zc = z[v2[i].a];
            int zd = z[v2[i].b];
            if(zc > zd) swap(zc, zd);
            v.pb({zc, zd});
        }
        
        // 3-2. sort.
        sort(all(v));
        
        // 3-3. 比較.
        if(v == v1){
            ok = true;
            break;
        }
    }while(next_permutation(all(z)));
    
    // 4. 出力.
    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 vi = vector<int>;

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

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

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

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

#define pb push_back

#define a first

#define b second

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

int main(){

// 1. 入力情報.

int N, M;

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

vp v1, v2;

rep(i, M){

int a, b;

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

a--, b--;

v1.pb({a, b});

}

rep(i, M){

int c, d;

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

c--, d--;

v2.pb({c, d});

}

// 2. sort.

sort(all(v1));

// 3. 同じ形か？

vi z(N);

iota(all(z), 0);

bool ok = false;

do{

// 3-1. ある数列を対応させる.

vp v;

rep(i, M){

int zc = z[v2[i].a];

int zd = z[v2[i].b];

if(zc > zd) swap(zc, zd);

v.pb({zc, zd});

}

// 3-2. sort.

sort(all(v));

// 3-3. 比較.

if(v == v1){

ok = true;

break;

}

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

// 4. 出力.

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

return 0;

}

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

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

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

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

[入力例]
8 0

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

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

[出力例]
No

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

[出力例]
Yes

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

[出力例]
Yes
※ 整数 N が, 問題文の制約条件から範囲外であるケース.

100

101

102

103

104

105

106

107

108

109

110

111

112

113

[入力例]

4 4

1 2

1 3

1 4

3 4

1 3

1 4

2 3

3 4

[出力例]

Yes

※AtCoderテストケースより

[入力例]

5 6

1 2

1 3

1 4

3 4

3 5

4 5

1 2

1 3

1 4

1 5

3 5

4 5

[出力例]

※AtCoderテストケースより

[入力例]

8 0

[出力例]

Yes

※AtCoderテストケースより

[入力例]

5 6

1 2

1 4

2 4

1 3

1 5

3 5

1 2

2 3

2 5

3 5

3 4

4 5

[出力例]

[入力例]

8 9

1 4

1 3

1 2

4 5

3 5

3 4

5 8

3 6

3 7

1 2

1 3

1 9

7 8

2 8

2 3

3 4

2 5

2 6

[出力例]

Yes

[入力例]

10 12

1 2

1 3

1 4

2 5

3 5

3 6

4 6

4 7

2 7

5 9

7 10

6 8

1 2

1 6

1 7

2 3

2 10

7 10

4 7

4 8

8 10

8 9

5 6

4 6

[出力例]

Yes

※ 整数 N が, 問題文の制約条件から範囲外であるケース.

■C++版プログラム(問題D／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 board[111][111], dp[111][111];

int main(){
    
    // 1. 入力情報.
    int H, W;
    scanf("%d %d", &H, &W);
    rep(i, H){
        char c[111];
        scanf("%s", c);
        rep(j, W) if(c[j] == '.') board[i][j] = 1;
    }
    
    // 2. dp更新.
    int ans = 0;
    dp[0][0] = 1;
    rep(i, H){
        rep(j, W){
            // 移動可能な場合.
            if(board[i][j] && dp[i][j]){
                // 下方向.
                if(i + 1 < H && board[i + 1][j]) dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + 1);
                
                // 右方向.
                if(j + 1 < W && board[i][j + 1]) dp[i][j + 1] = max(dp[i][j + 1], dp[i][j] + 1);
            }
            
            // 最大値更新.
            ans = max(ans, dp[i][j]);
        }
    }
    
    // 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 board[111][111], dp[111][111];

int main(){

// 1. 入力情報.

int H, W;

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

rep(i, H){

char c[111];

scanf("%s", c);

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

}

// 2. dp更新.

int ans = 0;

dp[0][0] = 1;

rep(i, H){

rep(j, W){

// 移動可能な場合.

if(board[i][j] && dp[i][j]){

// 下方向.

if(i + 1 < H && board[i + 1][j]) dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + 1);

// 右方向.

if(j + 1 < W && board[i][j + 1]) dp[i][j + 1] = max(dp[i][j + 1], dp[i][j] + 1);

}

// 最大値更新.

ans = max(ans, dp[i][j]);

}

// 3. 出力.

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

return 0;

}

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

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

[入力例]
1 1
.

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

[入力例]
5 5
.....
.....
.....
.....
.....

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

[入力例]
32 32
..##..##..##.....#...####.##.##.
#...#.#.##.#.##..#####.#.##.#..#
##.#.##.###..##########.#.##.#..
##...#.#..######..#.###.####...#
.......########.####...##.#.####
..#..###...####.....#####...##.#
#..#.....#.#..###.#.#.#.....##..
..#.#.#.##..#.####..##.#.##.###.
#....#...#.#.......##.###.##.#.#
..#...#...##.#..##.#.#...###..##
.#..#.#.####.#.#.#...###.##.#.#.
.....##.#######...##.#.##.#.##..
#.##..........###.##.##...#..###
#.##.###...#####..###.#...##....
###...##..##..####.#..#....#.##.
.##.####..#..#.##.#..#.##.#.##.#
##..###...##...#.#.##...##......
..#..#.#.....#..##..#.####...#..
.#.####....#...##..#..#.#.#.##..
###.##..##.##.###.#...#.##.....#
...#..#.#..#.#..#...##.#.#.###.#
...##..#####.#..###.##.####..###
.#.#####.#.###.####...#.....####
###....###.#.##..##.##..#..#...#
..#.##..#..#.#...###.#..#.######
###.#####.##.###...##...#.#####.
#.#.##...##.#...#..####.....##.#
.##..##.##...##...##.#..##.....#
#...##.##.#.#.##..#..##.##.#...#
#.#####.##.#######.#.....##...#.
#..##.#####.###.....#####.#.#..#
##...#####.##.....####.###..#...

[出力例]
33

[入力例]
50 60
.#.###.##.##.###..#..####..##...##......##.#.##.#.#..##.#.##
..##..##.###...####..#.###..#.#.#.###...##..#.#.#....#.#.###
..#.###..#####.##.##..#.###.###..####..#...##..####.#.#..###
#.....#.#..###.###.#.#...#...#.....#...#.#######...##.......
#..#.#..####..##.....##.#####...#....#....##..#.##.#...#..##
.....####.#.##....###..#.#...###.###.##..#####..###.##.#...#
#..#..#....#..#.#.##.###..#.#.#########...##...##..#...#.###
.....##.#.#.#..#.##..##.#....#.#.##..#.....###.#############
##.....###.##.#...#####.......##.#.#..##.....####.##..##..##
######.##.###....#.#..##...###.....#..#.###.#.#.......#.#.#.
....#.........#.##..####..#.##....########...#..######...###
###.#.##..#..#..#....#.####..#....##....##.#..#..##..#...#..
...#..###..#####..#.##.##.#..###.#.##....#..###.##.##.##....
#..#.#..##.##.#.#...#..#..###.#.####...#....#..#..####..###.
#.###.####.......##.###...##....#.###.#.##.##.#.#....#.#####
##.##.#.#..#.#.#.###...#.#...###....##....#####.#..#....###.
.##.##.....#...####.#..#...#..#.##......#..#.#.##.#.#.#.....
#..#.###.#.###..#...####..#.##.###...#.#######..#..#...#...#
.###.#.#.#..###.##.....##.#..#....##....#.#.###.##.#....###.
#..#.#.#...#.##..####..####.#.#..###..####.#.#.##...###...#.
...#.###...##..###...#...##.##...#..#.....#########..###.###
...###.#....##.#.#.#..#...#.#...####.....#..#.####.#...#.###
#..##.####....#.#..#.#.##.##.####..###########.###..#######.
.....#..####....##.#...#..#..###...#.##..##..#.#.####.#..###
..#......#..###.#.....######.##.####......#..#.##...##.#....
#..#.##.##.##.......##.#..##.#..####...#.##.....#...#...#...
.#.###....#...#....#######.#....####.#...#.#.#####.###.#...#
#.##.##.##.##..#..#..##.#.#.#...##....#.#.#####.#.##...##..#
##...#.#..##...#......#######.#.#..##.####.#.#..#....#..##.#
....###..#.#...#.##..####....#..#..##.#.#####.##.......###.#
#.#..######.###..###...#....##..#.#.####.####...##.#...##.#.
...####.###.#.#..####...#..#....##....#...##.#...##.#.#.....
####.#.#...##.##.#.###.#.##..#...#.#...#####..#.#.###..##.##
.##.#...###.###...###...##...#.#.#..#..#...###.#..#..##...##
#.##.#.....###.#####..#...##..###.#.##..#..####.##.##..#.#..
#.#..#..#.###.##.....#.......###..#.##...##.#.#...###.##..#.
.##..#........##.###..#.#.#...#..######.####.###...#....#...
.#.#.#..##.###.###..#..##.....##.#....#.#..##..#####..##...#
#..##.#...#.#..######....#.##.##....##.#..#..####...##.##.#.
#.##...#.###......#.##.######...#..#.#..##.#.#.#....####...#
........#..#.##..####.....#.......####...#.##.###.####....#.
...######.###.########..#.#....######....###.##...##..#.##.#
##....#.#.#..#.#.##.###.#..#..###.#.......#..#...#.##.##....
.#.###.#.##.#######.##.....#...##..#..#..#..#..###...##.#...
..#...#.###....##.####...##....#...####.#.###.#.##....#####.
##..#..#.#..#.#####......#.###.......##..#...###...##......#
..#.#...#..#####...#####.##.....#.#.########.#.#.##..##..#.#
#..##.######...####.#######..###....###...#..###############
.......####.##.#..#....###.#.##..##...#####.####.###..#.#...
...#.#..#.###......#...#......#...#....###......########.#.#

[出力例]
88

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

[入力例]

3 4

.#..

..#.

..##

[出力例]

※AtCoderテストケースより

[入力例]

1 1

[出力例]

※AtCoderテストケースより

[入力例]

5 5

.....

[出力例]

※AtCoderテストケースより

[入力例]

32 32

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[出力例]

[入力例]

50 60

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[出力例]

■参照サイト
M-SOLUTIONS プロコンオープン2021(AtCoder Beginner Contest 232)

2021年12月19日2021年12月19日

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

C++の練習を兼ねて, AtCoder Regular Contest 056 の問題C (部門分け) を解いてみた.

■感想.
1. 問題Cは, 方針が見えなかったので, 解説を参考にして, AC版に到達できたと思う.
2. 実行時間を改善するため, 過去問(AtCoder Beginner Contest 187 (F – Close Group)) の解説プログラムを参考に, 一部改変して, 実装した.
3. 苦手な動的計画法の訓練を積めたので, 非常に良かったと思う.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/data/arc/056/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
LL wSum[1 << 17], w[22][22], dp[1 << 17];

int main(){
    
    // 1. 入力情報.
    int N, K;
    scanf("%d %d", &N, &K);
    rep(i, N) rep(j, N) scanf("%lld", &w[i][j]);
    
    // 2. 部分集合ごとの重みの総和.
    rep(i, 1 << N){
        vi s;
        rep(j, N) if(i & (1 << (N - 1 - j))) s.pb(j);
        for(auto &p : s) for(auto &q : s) wSum[i] += w[p][q];
        wSum[i] /= 2; // 重複カウントの除外.
    }
    
    // 3. dp更新.
    // 以下の実装は, N = 17 で, 5416[ms] などの時間が, かかってしまう(TLE版).
    /*
    repx(s, 1, 1 << N){
        // 3-1. 部分集合 S の index.
        vi sIndex;
        rep(i, N) if(s & (1 << (N - 1 - i))) sIndex.pb(i);
        
        // 3-2. dp[S] = dp[S - T] + K - (S - T と T 間 の 辺の重みの総和) を 計算.
        int l = sIndex.size();
        rep(i, 1 << l){
            // 部分集合 T.
            int t = 0;
            rep(j, l) if(i & (1 << (l - 1 - j))) t += (1 << (N - 1 - sIndex[j]));
            
            // dp計算式を実行.
            dp[s] = max(dp[s], dp[s - t] + K - (wSum[s] - wSum[s - t] - wSum[t]));
        }
    }
    */
    
    // 4. dp更新(修正版).
    // 
    // 過去問参照(AtCoder Beginner Contest 187 F - Close Group).
    // https://atcoder.jp/contests/abc187/editorial/488
    // https://atcoder.jp/contests/abc187/submissions/19205798
    // -> 部分集合 S と T が 同じケースを含めるため, 一部改変(for(int j = i; --j &= i; ) の 部分).
    // 以下の実装は, N = 17 で, 267[ms] 程度の実行時間 に 改善.
    repx(s, 1, 1 << N){
        for(int t = s; t &= s; t--) dp[s] = max(dp[s], dp[s - t] + K - (wSum[s] - wSum[s - t] - wSum[t]));
    }
    
    // 5. 出力.
    printf("%lld\n", dp[(1 << N) - 1]);
    return 0;
    
}

// 解き直し.

// https://img.atcoder.jp/data/arc/056/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

LL wSum[1 << 17], w[22][22], dp[1 << 17];

int main(){

// 1. 入力情報.

int N, K;

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

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

// 2. 部分集合ごとの重みの総和.

rep(i, 1 << N){

vi s;

rep(j, N) if(i & (1 << (N - 1 - j))) s.pb(j);

for(auto &p : s) for(auto &q : s) wSum[i] += w[p][q];

wSum[i] /= 2; // 重複カウントの除外.

}

// 3. dp更新.

// 以下の実装は, N = 17 で, 5416[ms] などの時間が, かかってしまう(TLE版).

repx(s, 1, 1 << N){

// 3-1. 部分集合 S の index.

vi sIndex;

rep(i, N) if(s & (1 << (N - 1 - i))) sIndex.pb(i);

// 3-2. dp[S] = dp[S - T] + K - (S - T と T 間の辺の重みの総和) を計算.

int l = sIndex.size();

rep(i, 1 << l){

// 部分集合 T.

int t = 0;

rep(j, l) if(i & (1 << (l - 1 - j))) t += (1 << (N - 1 - sIndex[j]));

// dp計算式を実行.

dp[s] = max(dp[s], dp[s - t] + K - (wSum[s] - wSum[s - t] - wSum[t]));

}

// 4. dp更新(修正版).

// 過去問参照(AtCoder Beginner Contest 187 F - Close Group).

// https://atcoder.jp/contests/abc187/editorial/488

// https://atcoder.jp/contests/abc187/submissions/19205798

// -> 部分集合 S と T が同じケースを含めるため, 一部改変(for(int j = i; --j &= i; ) の部分).

// 以下の実装は, N = 17 で, 267[ms] 程度の実行時間に改善.

repx(s, 1, 1 << N){

for(int t = s; t &= s; t--) dp[s] = max(dp[s], dp[s - t] + K - (wSum[s] - wSum[s - t] - wSum[t]));

}

// 5. 出力.

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

return 0;

}

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

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

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

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

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

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

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

[出力例]
40

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

[出力例]
235

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

[出力例]
711

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

[出力例]
212

100

101

102

103

[入力例]

3 3

0 1 5

1 0 1

5 1 0

[出力例]

※AtCoderのテストケースより

[入力例]

4 8

0 2 3 5

2 0 1 2

3 1 0 8

5 2 8 0

[出力例]

※AtCoderのテストケースより

[入力例]

5 10

0 10 1 2 1

10 0 1 2 1

1 1 0 6 7

2 2 6 0 8

1 1 7 8 0

[出力例]

※AtCoderのテストケースより

[入力例]

7 23

0 3 6 1 4 3 8

3 0 7 9 9 6 10

6 7 0 10 7 1 10

1 9 10 0 5 3 8

4 9 7 5 0 4 2

3 6 1 3 4 0 5

8 10 10 8 2 5 0

[出力例]

[入力例]

10 50

0 5 2 4 8 8 2 9 1 10

5 0 7 1 7 6 10 1 4 2

2 7 0 10 5 3 8 10 5 10

4 1 10 0 10 5 3 3 7 8

8 7 5 10 0 7 6 9 2 9

8 6 3 5 7 0 7 8 3 8

2 10 8 3 6 7 0 10 3 1

9 1 10 3 9 8 10 0 1 8

1 4 5 7 2 3 3 1 0 9

10 2 10 8 9 8 1 8 9 0

[出力例]

235

[入力例]

13 88

0 6 7 3 6 6 9 3 5 9 3 5 8

6 0 7 9 2 10 9 9 5 7 9 1 6

7 7 0 2 6 2 9 8 6 1 5 4 5

3 9 2 0 4 7 8 10 2 2 1 4 10

6 2 6 4 0 10 4 10 6 4 5 10 4

6 10 2 7 10 0 4 7 4 1 3 2 6

9 9 9 8 4 4 0 5 8 1 2 7 1

3 9 8 10 10 7 5 0 7 9 9 5 6

5 5 6 2 6 4 8 7 0 2 4 1 10

9 7 1 2 4 1 1 9 2 0 10 1 10

3 9 5 1 5 3 2 9 4 10 0 8 1

5 1 4 4 10 2 7 5 1 1 8 0 6

8 6 5 10 4 6 1 6 10 10 1 6 0

[出力例]

711

[入力例]

17 59

0 4 5 4 7 1 8 9 10 7 2 2 8 2 5 7 7

4 0 10 8 5 6 1 6 2 5 3 8 10 2 8 10 2

5 10 0 9 6 7 3 2 7 7 10 9 2 8 8 1 6

4 8 9 0 10 2 8 3 9 9 2 2 1 5 2 4 2

7 5 6 10 0 10 3 6 3 9 1 10 4 6 7 2 1

1 6 7 2 10 0 2 5 10 2 6 5 6 9 4 6 9

8 1 3 8 3 2 0 9 9 5 8 3 2 8 8 8 8

9 6 2 3 6 5 9 0 1 8 10 7 5 7 4 3 5

10 2 7 9 3 10 9 1 0 1 1 5 10 2 5 10 2

7 5 7 9 9 2 5 8 1 0 8 8 8 5 7 3 8

2 3 10 2 1 6 8 10 1 8 0 8 8 6 10 4 7

2 8 9 2 10 5 3 7 5 8 8 0 10 1 10 10 9

8 10 2 1 4 6 2 5 10 8 8 10 0 5 7 2 5

2 2 8 5 6 9 8 7 2 5 6 1 5 0 9 9 8

5 8 8 2 7 4 8 4 5 7 10 10 7 9 0 3 10

7 10 1 4 2 6 8 3 10 3 4 10 2 9 3 0 5

7 2 6 2 1 9 8 5 2 8 7 9 5 8 10 5 0

[出力例]

212

■参照サイト
AtCoder Regular Contest 056
AtCoder Beginner Contest 187 (F – Close Group)

2021年12月18日

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

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

■感想.
1. 問題Eは, 方針が見えなかったので, 解説および(複数の)正答者のプログラムを参考にして, AC版に到達できたと思う.
2. 01-BFSについて復習出来たので, 非常に良かったと思う.
3. 但し, 01-BFSは, いまいち, 本質を理解出来てないように見えるので, 引き続き, 今後の課題だと思われる.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// ※※※ 解答不能 ※※※
// https://atcoder.jp/contests/abc213/editorial/2397
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pof pop_front
#define pob pop_back
#define pub push_back
#define puf push_front
#define a first
#define b second
const int INF = 2020202020;
constexpr int MAX = 252525;
int board[MAX];

int main(){
    
    // 1. 入力情報.
    int H, W;
    scanf("%d %d", &H, &W);
    rep(i, H){
        char c[505];
        scanf("%s", c);
        rep(j, W) if(c[j] == '#') board[i * W + j] = 1;
    }
    
    // 2. 01-BFS(解説 および 複数の正答者プログラム参照).
    // https://ja.wikipedia.org/wiki/幅優先探索
    // https://betrue12.hateblo.jp/entry/2018/12/08/000020
    auto bfs01 = [&](int s, int* d){
        // 2-1. 空のキュー.
        deque<P> dq;
        
        // 2-2. キュー に 保存.
        // -> キューに, 座標のみ保存だと, 正しく動作しない模様, 
        //    正答者のプログラムをいくつか見たところ, 距離も合わせて保存する必要があるらしい.
        //    dijkstra法 に, やや近い実装方法になると思われる.
        dq.pub({s, 0});
        while(!dq.empty()){
            // 2-3. キュー の 先頭要素を取り出す.
            // x: 列方向, y: 行方向 で考える.
            P u = dq.front();
            int cx = u.a % W , cy = u.a / W;
            int dCur = u.b;
            dq.pof();
            
            // 2-4. 最短距離更新.
            if(dCur >= d[u.a]) continue;
            d[u.a] = dCur;
            
            // 2-5. 周辺のマス を 確認.
            // -> 解説にある図で, * に 対する操作.
            // ※※※ 但し,  * の マスへの 移動コストが, すべて 1 になる訳ではないので要注意. ※※※
            // .***.
            // *****
            // **T**
            // *****
            // .***.
            // 
            for(auto &x : {-2, -1, 0, 1, 2}){
                for(auto &y : {-2, -1, 0, 1, 2}){
                    // 移動先候補のマス.
                    int nx = cx + x;
                    int ny = cy + y;
                    int n = nx + ny * W;
                    
                    // 到達不可能なマスであれば, Skip.
                    if(nx < 0 || nx >= W || ny < 0 || ny >= H || abs(x) + abs(y) == 4)  continue;
                    
                    // 上下左右のマスで, '.' の場合は, コスト 0 の 移動, それ以外のマスは, コスト 1 の 移動と見る.
                    if(!board[n] && x * y == 0 && abs(x + y) == 1) dq.puf({n, dCur + 0});
                    else                                           dq.pub({n, dCur + 1});
                }
            }
        }
    };
    int d[MAX];
    rep(i, MAX) d[i] = INF;
    bfs01(0, d);
    
    // 3. 出力.
    printf("%d", d[H * W - 1]);
    return 0;
    
}

// ※※※ 解答不能 ※※※

// https://atcoder.jp/contests/abc213/editorial/2397

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using P = pair<int, int>;

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

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

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

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

#define pof pop_front

#define pob pop_back

#define pub push_back

#define puf push_front

#define a first

#define b second

const int INF = 2020202020;

constexpr int MAX = 252525;

int board[MAX];

int main(){

// 1. 入力情報.

int H, W;

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

rep(i, H){

char c[505];

scanf("%s", c);

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

}

// 2. 01-BFS(解説および複数の正答者プログラム参照).

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

// https://betrue12.hateblo.jp/entry/2018/12/08/000020

auto bfs01 = [&](int s, int* d){

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

deque<P> dq;

// 2-2. キューに保存.

// -> キューに, 座標のみ保存だと, 正しく動作しない模様,

// 正答者のプログラムをいくつか見たところ, 距離も合わせて保存する必要があるらしい.

// dijkstra法に, やや近い実装方法になると思われる.

dq.pub({s, 0});

while(!dq.empty()){

// 2-3. キューの先頭要素を取り出す.

// x: 列方向, y: 行方向で考える.

P u = dq.front();

int cx = u.a % W , cy = u.a / W;

int dCur = u.b;

dq.pof();

// 2-4. 最短距離更新.

if(dCur >= d[u.a]) continue;

d[u.a] = dCur;

// 2-5. 周辺のマスを確認.

// -> 解説にある図で, * に対する操作.

// ※※※ 但し, * のマスへの移動コストが, すべて 1 になる訳ではないので要注意. ※※※

// .***.

// *****

// **T**

// *****

// .***.

for(auto &x : {-2, -1, 0, 1, 2}){

for(auto &y : {-2, -1, 0, 1, 2}){

// 移動先候補のマス.

int nx = cx + x;

int ny = cy + y;

int n = nx + ny * W;

// 到達不可能なマスであれば, Skip.

if(nx < 0 || nx >= W || ny < 0 || ny >= H || abs(x) + abs(y) == 4) continue;

// 上下左右のマスで, '.' の場合は, コスト 0 の移動, それ以外のマスは, コスト 1 の移動と見る.

if(!board[n] && x * y == 0 && abs(x + y) == 1) dq.puf({n, dCur + 0});

else dq.pub({n, dCur + 1});

}

};

int d[MAX];

rep(i, MAX) d[i] = INF;

bfs01(0, d);

// 3. 出力.

printf("%d", d[H * W - 1]);

return 0;

}

[入力例]
5 5
..#..
#.#.#
##.##
#.#.#
..#..

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

[入力例]
5 7
.......
######.
.......
.######
.......

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

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

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

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

[出力例]
5

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

[出力例]
12

[入力例]

5 5

..#..

#.#.#

##.##

#.#.#

..#..

[出力例]

※AtCoderのテストケースより

[入力例]

5 7

.......

######.

.......

.######

.......

[出力例]

※AtCoderのテストケースより

[入力例]

8 8

.#######

########

#######.

[出力例]

※AtCoderのテストケースより

[入力例]

2 12

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

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

[出力例]

[入力例]

11 50

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

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

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

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

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

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

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

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

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

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

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

[出力例]

■参照サイト
AtCoder Beginner Contest 213
01-BFSのちょっと丁寧な解説

C++の練習を兼ねて, AtCoder Regular Contest 050 の 問題C (LCM 111) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 047 の 問題A (タブの開きすぎ) ～ 問題B (同一円周上) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 021 の 問題A (DEAD END) ～ 問題B (Your Numbers are XORed…) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 132 の 問題A (Permutation Grid) ～ 問題B (Shift and Reverse) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 057 の 問題C (2乗根) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 036 の 問題C (偶然ジェネレータ) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 045 の 問題C (エックスオア多橋君) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 232 の 問題C (Graph Isomorphism) ～ 問題D (Weak Takahashi) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 056 の 問題C (部門分け) を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 050 の問題C (LCM 111) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 047 の問題A (タブの開きすぎ) ～問題B (同一円周上) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 021 の問題A (DEAD END) ～問題B (Your Numbers are XORed…) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 132 の問題A (Permutation Grid) ～問題B (Shift and Reverse) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 057 の問題C (2乗根) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 036 の問題C (偶然ジェネレータ) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 045 の問題C (エックスオア多橋君) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 232 の問題C (Graph Isomorphism) ～問題D (Weak Takahashi) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 056 の問題C (部門分け) を解いてみた.

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