6月, 2019 | 個人用メモ帳

2019年6月30日

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

C++の練習を兼ねて, AtCoder Beginner Contest 049 の問題D (D – 連結 / Connectivity) を解いてみた.

■感想.
1. 解説上, Union-Find木について触れられていたので, Union-Find木に慣れるため, 解き直しした.

本家のサイトABC049/ARC065解説をご覧下さい.

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

// 解き直し.
// ABC049/ARC065解説.
// https://img.atcoder.jp/arc065/editorial.pdf
// 以下のライブラリを使ってみる.
// 素集合データ構造(Union-Find)
// https://ei1333.github.io/luzhiled/snippets/structure/union-find.html
#include <bits/stdc++.h>
using namespace std;
int ar[200001];
int br[200001];

struct UnionFind{

    vector<int> data;
    UnionFind(int sz){ data.assign(sz, -1); }
    
    // 頂点 x, y の 結合.
    bool unite(int x, int y){
        x = find(x), y = find(y);
        if(x == y)            return false;
        if(data[x] > data[y]) swap(x, y);
        data[x] += data[y];
        data[y] = x;
        return true;
    }
    
    // 頂点 k を 探索.
    int find(int k){
        if(data[k] < 0) return k;
        return data[k] = find(data[k]);
    }
    
    // 頂点 k を含む集合 の 大きさ.
    int size(int k){ return (-data[find(k)]); }
};

int main(){

    // 1. 入力情報取得.
    int N, K, L;
    int p, q;
    scanf("%d %d %d", &N, &K, &L);
    UnionFind ufc(N); // 道路で連結.
    UnionFind uft(N); // 鉄道で連結.
    
    // 2. 道路で連結している都市.
    for(int i = 0; i < K; i++){
        scanf("%d %d", &p, &q);
        p--, q--;
        ufc.unite(p, q);
    }
    
    // 3. 鉄道で連結している都市.
    for(int i = 0; i < L; i++){
        scanf("%d %d", &p, &q);
        p--, q--;
        uft.unite(p, q);
    }
    
    // 4. 各都市に, Union-Findでの根の都市番号を保存(道路, 鉄道).
    for(int i = 0; i < N; i++){
        ar[i] = ufc.find(i);
        br[i] = uft.find(i);
    }
    
    // 5. (ar[i], br[i]) の 出現回数を集計.
    map<pair<int, int>, int> m;
    for(int i = 0; i < N; i++){
        pair<int, int> p = make_pair(ar[i], br[i]);
        m[p]++;
    }
    
    // 6. 各都市について, 5. で確認した出現回数を出力.
    for(int i = 0; i < N; i++){
        pair<int, int> p = make_pair(ar[i], br[i]);
        printf("%d ", m[p]);
    }

    // 7. 後処理.
    return 0;

}

// 解き直し.

// ABC049/ARC065解説.

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

// 以下のライブラリを使ってみる.

// 素集合データ構造(Union-Find)

// https://ei1333.github.io/luzhiled/snippets/structure/union-find.html

#include <bits/stdc++.h>

using namespace std;

int ar[200001];

int br[200001];

struct UnionFind{

vector<int> data;

UnionFind(int sz){ data.assign(sz, -1); }

// 頂点 x, y の結合.

bool unite(int x, int y){

x = find(x), y = find(y);

if(x == y) return false;

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

data[x] += data[y];

data[y] = x;

return true;

}

// 頂点 k を探索.

int find(int k){

if(data[k] < 0) return k;

return data[k] = find(data[k]);

}

// 頂点 k を含む集合の大きさ.

int size(int k){ return (-data[find(k)]); }

};

int main(){

// 1. 入力情報取得.

int N, K, L;

int p, q;

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

UnionFind ufc(N); // 道路で連結.

UnionFind uft(N); // 鉄道で連結.

// 2. 道路で連結している都市.

for(int i = 0; i < K; i++){

scanf("%d %d", &p, &q);

p--, q--;

ufc.unite(p, q);

}

// 3. 鉄道で連結している都市.

for(int i = 0; i < L; i++){

scanf("%d %d", &p, &q);

p--, q--;

uft.unite(p, q);

}

// 4. 各都市に, Union-Findでの根の都市番号を保存(道路, 鉄道).

for(int i = 0; i < N; i++){

ar[i] = ufc.find(i);

br[i] = uft.find(i);

}

// 5. (ar[i], br[i]) の出現回数を集計.

map<pair<int, int>, int> m;

for(int i = 0; i < N; i++){

pair<int, int> p = make_pair(ar[i], br[i]);

m[p]++;

}

// 6. 各都市について, 5. で確認した出現回数を出力.

for(int i = 0; i < N; i++){

pair<int, int> p = make_pair(ar[i], br[i]);

printf("%d ", m[p]);

}

// 7. 後処理.

return 0;

}

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

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

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

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

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

[出力例]
5 1 1 5 5 1 5 1 1 5 

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

[出力例]
1 1 1 1 1 1 1 2 1 2 1 1

[入力例]

4 3 1

1 2

2 3

3 4

2 3

[出力例]

1 2 2 1

※AtCoderテストケースより

[入力例]

7 4 4

1 2

2 3

2 5

6 7

3 5

4 5

3 4

6 7

[出力例]

1 1 2 1 2 2 2

※AtCoderテストケースより

[入力例]

10 6 4

1 2

1 4

1 7

1 10

1 5

1 3

4 5

1 5

4 7

7 10

[出力例]

5 1 1 5 5 1 5 1 1 5

[入力例]

12 9 3

10 11

11 12

12 9

9 8

4 7

5 6

6 3

2 3

2 1

7 1

6 9

8 10

[出力例]

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

■参照サイト
AtCoder Beginner Contest 049
素集合データ構造(Union-Find)

2019年6月30日

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

C++の練習を兼ねて, AtCoder Beginner Contest 002 の問題D (D – 派閥) を解いてみた.

■感想.
1. 解説上, 最大クリーク問題について触れられていたので, 最大クリーク問題として解いたら, どうなるか見てみた.
2. 新しい知識が一つ増えたので良かったと思う.

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

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

// 最大クリーク問題とみて解いてみる.
// 以下のライブラリを使ってみる(※一部改変).
// Maximum Clique using backtracking in C
// http://www.martinbroadhurst.com/maximum-clique-using-backtracking-in-c.html
#include <bits/stdc++.h>
using namespace std;
int a[21][21];

static void maximum_clique_recursive(int **adj, int order, 
        int *current_clique, int *current_clique_size, int *max_clique,
        int *max_clique_size, int level){
    int i, connected;
    if(level == order){
        /* Found a new max clique */
        memcpy(max_clique, current_clique, order * sizeof(int));
        *max_clique_size = *current_clique_size;
        return;
    }
    /* Find out if current vertex is connected to all vertices in current clique */
    connected = 1;
    for(i = 0; i < level && connected; i++){
        if(current_clique[i] && !adj[level][i]){
            connected = 0;
            break;
        }
    }

    if(connected){
        /* Add this vertex to the clique */
        current_clique[level] = 1;
        (*current_clique_size)++;
        maximum_clique_recursive(adj, order, current_clique, current_clique_size, max_clique, 
                max_clique_size, level + 1);
        (*current_clique_size)--;
    }
    if(*current_clique_size + order - level > *max_clique_size){
        /* Still promising */
        current_clique[level] = 0;
        maximum_clique_recursive(adj, order, current_clique, current_clique_size, max_clique, 
                max_clique_size, level + 1);
    }
}

int maximum_clique(int **adj, int order, int **max_clique){
    int max_clique_size = 0;
    int current_clique_size = 0;
    int *current_clique = (int *)malloc(order * sizeof(int));
    *max_clique = (int *)malloc(order * sizeof(int));
    if(current_clique == NULL || *max_clique == NULL){
        free(current_clique);
        free(max_clique);
        return 0;
    }
    maximum_clique_recursive(adj, order, current_clique, &current_clique_size, *max_clique, 
            &max_clique_size, 0);
    free(current_clique);
    return max_clique_size;
}

int main(){
    
    // 1. 入力情報取得.
    int N, M;
    scanf("%d %d", &N, &M);
    for(int i = 0; i < M; i++){
        int x, y;
        scanf("%d %d", &x, &y);
        x--, y--;
        a[x][y]++;
        a[y][x]++;
    }
    
    // 2. 最大クリーク数を計算.
    int *adj[N];
    for(int i = 0; i < N; i++) adj[i] = a[i];
    int *max_clique = 0;
    int max_clique_size = maximum_clique(adj, N, &max_clique);
    
    // 3. 出力.
    printf("%d\n", max_clique_size);
    // for(int i = 0; i < N; i++) if(max_clique[i] == 1) printf("%u ", i);
    // putchar('\n');

    // 4. 後処理.
    free(max_clique);
    return 0;
    
}

// 最大クリーク問題とみて解いてみる.

// 以下のライブラリを使ってみる(※一部改変).

// Maximum Clique using backtracking in C

// http://www.martinbroadhurst.com/maximum-clique-using-backtracking-in-c.html

#include <bits/stdc++.h>

using namespace std;

int a[21][21];

static void maximum_clique_recursive(int **adj, int order,

int *current_clique, int *current_clique_size, int *max_clique,

int *max_clique_size, int level){

int i, connected;

if(level == order){

/* Found a new max clique */

memcpy(max_clique, current_clique, order * sizeof(int));

*max_clique_size = *current_clique_size;

return;

}

/* Find out if current vertex is connected to all vertices in current clique */

connected = 1;

for(i = 0; i < level && connected; i++){

if(current_clique[i] && !adj[level][i]){

connected = 0;

break;

}

if(connected){

/* Add this vertex to the clique */

current_clique[level] = 1;

(*current_clique_size)++;

maximum_clique_recursive(adj, order, current_clique, current_clique_size, max_clique,

max_clique_size, level + 1);

(*current_clique_size)--;

}

if(*current_clique_size + order - level > *max_clique_size){

/* Still promising */

current_clique[level] = 0;

maximum_clique_recursive(adj, order, current_clique, current_clique_size, max_clique,

max_clique_size, level + 1);

}

int maximum_clique(int **adj, int order, int **max_clique){

int max_clique_size = 0;

int current_clique_size = 0;

int *current_clique = (int *)malloc(order * sizeof(int));

*max_clique = (int *)malloc(order * sizeof(int));

if(current_clique == NULL || *max_clique == NULL){

free(current_clique);

free(max_clique);

return 0;

}

maximum_clique_recursive(adj, order, current_clique, &current_clique_size, *max_clique,

&max_clique_size, 0);

free(current_clique);

return max_clique_size;

}

int main(){

// 1. 入力情報取得.

int N, M;

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

for(int i = 0; i < M; i++){

int x, y;

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

x--, y--;

a[x][y]++;

a[y][x]++;

}

// 2. 最大クリーク数を計算.

int *adj[N];

for(int i = 0; i < N; i++) adj[i] = a[i];

int *max_clique = 0;

int max_clique_size = maximum_clique(adj, N, &max_clique);

// 3. 出力.

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

// for(int i = 0; i < N; i++) if(max_clique[i] == 1) printf("%u ", i);

// putchar('\n');

// 4. 後処理.

free(max_clique);

return 0;

}

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

[出力例(debug版)]
3
0 1 2 
※AtCoderテストケースより

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

[出力例(debug版)]
4
3 4 5 6 
※AtCoderテストケースより

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

[出力例(debug版)]
5
5 6 7 8 9 

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

[出力例(debug版)]
6
0 1 2 3 4 5

[入力例]

5 3

1 2

2 3

1 3

[出力例(debug版)]

0 1 2

※AtCoderテストケースより

[入力例]

7 9

1 2

1 3

2 3

4 5

4 6

4 7

5 6

5 7

6 7

[出力例(debug版)]

3 4 5 6

※AtCoderテストケースより

[入力例]

10 21

1 2

1 3

2 3

6 5

8 6

6 7

8 9

5 7

6 7

7 9

1 3

3 8

9 6

6 7

7 8

10 2

10 3

6 10

7 10

8 10

9 10

[出力例(debug版)]

5 6 7 8 9

[入力例]

7 18

1 2

1 3

1 4

1 5

1 6

1 7

2 3

2 4

2 5

2 6

3 4

3 5

3 6

3 7

4 5

4 6

5 6

5 7

[出力例(debug版)]

0 1 2 3 4 5

■参照サイト
AtCoder Beginner Contest 002
Maximum Clique using backtracking in C

2019年6月30日

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

C++の練習を兼ねて, AtCoder Beginner Contest 132 の問題D (D – Blue and Red Balls) を解いてみた.

■感想.
1. 仕切りに必要な, 赤いボール, 青いボールを考えてから, 残った赤いボール, 青いボールの並べ方に気付けたので, ACを取ることが出来たと思う.
2. 解答を見る前に, 解けたので, 及第点取れたと思う.
3. 課題としては, 復習が全く追い付いてないので, 考慮時間を限定して, なるべく多くの問題(※新しい知識の獲得)に触れるように方針の変更が必要と思った.

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

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

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const LL MOD = 1e9 + 7;
const LL MAX = 4321;
LL F[MAX];
LL IF[MAX];

// Fermat's little theorem を 適用するため, ap-2乗 などを計算できるようにする.
// @param a: べき乗したい正整数.
// @param b: 指数.
// @return: べき乗した計算結果(mod版).
LL inverse(LL a, LL b){
    LL t = 1;
    while(b) {
        if(b & 1) t = (t * a) % MOD;
        a *= a;
        a %= MOD;
        b >>= 1;
    }
    return t % MOD;
}

// 配列 IF に, 逆元を保存.
// @param: 特に無し.
// @return: 配列IF の update.
void initialize(){
    F[0] = 1, IF[0] = 1;
    for(LL i = 1; i < MAX; i++){
        F[i] = (F[i - 1] * i) % MOD;
        //逆元を、フェルマーの小定理を利用して求める
        IF[i] = inverse(F[i], MOD - 2) % MOD;
    }
}

// 組み合わせ(nCk)計算用(mod版).
// ※配列F, IF は, 事前に計算済のものを使う.
// @param n: 対象となる要素の個数.
// @param k: 選択する要素の個数.
// @return: 組み合わせ(nCk)の計算結果.
LL combination(LL n, LL k){
    if(n < 0 || k < 0 || k > n) return 0;
    LL ret = F[n] * IF[k] % MOD * IF[n - k] % MOD;
    return ret;
}

int main() {

    // 1. 入力情報取得.
    LL N, K;
    scanf("%lld %lld", &N, &K);
    initialize();
    
    // 2. 場合の数をカウントし, 出力.
    for(int i = 1; i <= K; i++){
        // 2-1. 各計算項目を設定.
        LL rp = i - 1;      // 仕切りに使う赤いボール.
        LL rr = N - K - rp; // 残った赤いボール.
        LL bp = i;          // 仕切りで使う青いボール.
        LL br = K - bp;     // 残った青いボール.
        // cout << "rp=" << rp << " rr=" << rr << " bp=" << bp << " br=" << br << endl;
        
        // 2-2. 場合の数を計算.
        // 残った赤いボールの並べ方.
        LL ans = combination(rr + bp, rr);
        ans %= MOD;
        // 残った青いボールの並べ方.
        ans *= combination(rp + br, br);
        ans %= MOD;
        
        // 2-3. 出力.
        printf("%lld\n", ans);
    }
    
    // 3. 後処理.
    return 0;

}

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

const LL MOD = 1e9 + 7;

const LL MAX = 4321;

LL F[MAX];

LL IF[MAX];

// Fermat's little theorem を適用するため, ap-2乗などを計算できるようにする.

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

// @param b: 指数.

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

LL inverse(LL a, LL b){

LL t = 1;

while(b) {

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

a *= a;

a %= MOD;

b >>= 1;

}

return t % MOD;

}

// 配列 IF に, 逆元を保存.

// @param: 特に無し.

// @return: 配列IF の update.

void initialize(){

F[0] = 1, IF[0] = 1;

for(LL i = 1; i < MAX; i++){

F[i] = (F[i - 1] * i) % MOD;

//逆元を、フェルマーの小定理を利用して求める

IF[i] = inverse(F[i], MOD - 2) % MOD;

}

// 組み合わせ(nCk)計算用(mod版).

// ※配列F, IF は, 事前に計算済のものを使う.

// @param n: 対象となる要素の個数.

// @param k: 選択する要素の個数.

// @return: 組み合わせ(nCk)の計算結果.

LL combination(LL n, LL k){

if(n < 0 || k < 0 || k > n) return 0;

LL ret = F[n] * IF[k] % MOD * IF[n - k] % MOD;

return ret;

}

int main() {

// 1. 入力情報取得.

LL N, K;

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

initialize();

// 2. 場合の数をカウントし, 出力.

for(int i = 1; i <= K; i++){

// 2-1. 各計算項目を設定.

LL rp = i - 1; // 仕切りに使う赤いボール.

LL rr = N - K - rp; // 残った赤いボール.

LL bp = i; // 仕切りで使う青いボール.

LL br = K - bp; // 残った青いボール.

// cout << "rp=" << rp << " rr=" << rr << " bp=" << bp << " br=" << br << endl;

// 2-2. 場合の数を計算.

// 残った赤いボールの並べ方.

LL ans = combination(rr + bp, rr);

ans %= MOD;

// 残った青いボールの並べ方.

ans *= combination(rp + br, br);

ans %= MOD;

// 2-3. 出力.

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

}

// 3. 後処理.

return 0;

}

[入力例]
5 3

[出力例(debug版)]
rp=0 rr=2 bp=1 br=2
3
rp=1 rr=1 bp=2 br=1
6
rp=2 rr=0 bp=3 br=0
1
※AtCoderテストケースより

[入力例]
2000 3

[出力例(debug版)]
rp=0 rr=1997 bp=1 br=2
1998
rp=1 rr=1996 bp=2 br=1
3990006
rp=2 rr=1995 bp=3 br=0
327341989
※AtCoderテストケースより

[入力例]
7 4

[出力例(debug版)]
rp=0 rr=3 bp=1 br=3
4
rp=1 rr=2 bp=2 br=2
18
rp=2 rr=1 bp=3 br=1
12
rp=3 rr=0 bp=4 br=0
1

[入力例]
1234 10

[出力例(debug版)]
rp=0 rr=1224 bp=1 br=9
1225
rp=1 rr=1223 bp=2 br=8
6747300
rp=2 rr=1222 bp=3 br=7
2597123
rp=3 rr=1221 bp=4 br=6
17982499
rp=4 rr=1220 bp=5 br=5
486989341
rp=5 rr=1219 bp=6 br=4
354498646
rp=6 rr=1218 bp=7 br=3
965128240
rp=7 rr=1217 bp=8 br=2
974617226
rp=8 rr=1216 bp=9 br=1
891920999
rp=9 rr=1215 bp=10 br=0
473065861

[入力例]

5 3

[出力例(debug版)]

rp=0 rr=2 bp=1 br=2

rp=1 rr=1 bp=2 br=1

rp=2 rr=0 bp=3 br=0

※AtCoderテストケースより

[入力例]

2000 3

[出力例(debug版)]

rp=0 rr=1997 bp=1 br=2

1998

rp=1 rr=1996 bp=2 br=1

3990006

rp=2 rr=1995 bp=3 br=0

327341989

※AtCoderテストケースより

[入力例]

7 4

[出力例(debug版)]

rp=0 rr=3 bp=1 br=3

rp=1 rr=2 bp=2 br=2

rp=2 rr=1 bp=3 br=1

rp=3 rr=0 bp=4 br=0

[入力例]

1234 10

[出力例(debug版)]

rp=0 rr=1224 bp=1 br=9

1225

rp=1 rr=1223 bp=2 br=8

6747300

rp=2 rr=1222 bp=3 br=7

2597123

rp=3 rr=1221 bp=4 br=6

17982499

rp=4 rr=1220 bp=5 br=5

486989341

rp=5 rr=1219 bp=6 br=4

354498646

rp=6 rr=1218 bp=7 br=3

965128240

rp=7 rr=1217 bp=8 br=2

974617226

rp=8 rr=1216 bp=9 br=1

891920999

rp=9 rr=1215 bp=10 br=0

473065861

■参照サイト
AtCoder Beginner Contest 132

2019年6月24日2019年6月24日

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

C++の練習を兼ねて, AtCoder Beginner Contest 035 の問題B (B – ドローン) ～問題C (C – オセロ) を解いてみた.

■感想.
1. 問題B は, ‘?’ をカウント後, 後から評価する点が面白いと感じた.
2. 問題C は, 遅延評価セグメント木が使えそうに見えたので, 下記, 参照サイトのライブラリをもとに, 提出した内容である.
※新しい知識となるが, セグメント木の理解が, 全然追い付いてないので, いろいろなパターンの問題に触れてみて, 本質をつかんでいく必要があると感じた.

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

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

#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)

int main() {
    
    // 1. 入力情報取得.
    string S;
    int T;
    cin >> S >> T;
    
    // 2. '?' を カウントしつつ, 文字列最終まで, 走査.
    int question = 0;
    int posX = 0, posY = 0;
    FOR(i, 0, S.size()){
        char c = S[i];
        // 命令が, 'L' の 場合.
        if(c == 'L') posX--;
        
        // 命令が, 'R' の 場合.
        if(c == 'R') posX++;
        
        // 命令が, 'U' の 場合.
        if(c == 'U') posY++;
        
        // 命令が, 'D' の 場合.
        if(c == 'D') posY--;
        
        // 命令が, '?' の 場合.
        if(c == '?') question++;
    }
    
    // 3. 最大値 を 計算.
    // int maxMD = 0;
    // 3-1. posX > 0  の 場合, 命令'?' は, 'R' だったと推定.
    // if(posX > 0) maxMD = posX + abs(posY) + question;
    // 3-2. posX < 0  の 場合, 命令'?' は, 'L' だったと推定.
    // if(posX < 0) maxMD = abs(posX) + abs(posY) + question;
    // 3-3. posX == 0 かつ posY > 0 の 場合, 命令'?' は, 'U' だったと推定.
    // if(posX == 0 && posY > 0) maxMD = posY + question;
    // 3-4. posX == 0 かつ posY < 0 の 場合, 命令'?' は, 'D' だったと推定.
    // if(posX == 0 && posY > 0) maxMD = abs(posY) + question;
    // 3-5. posX == 0 かつ posY == 0 の 場合, 命令'?' は, 'R' だったと推定(※なんでも良さそう).
    // if(posX == 0 && posY == 0) maxMD = question;
    // -> 3-1. ～ 3-5. は, 以下に集約されるはず.
    int maxMD = abs(posX) + abs(posY) + question;
    
    // 4. 最小値 を 計算.
    // -> 直観的には, abs(posX) + abs(posY) から question を 引いた数になりそう.
    // question が 非常に大きい場合は, 差分 を 2 で割った余りになりそう.
    int minMD = 0;
    if(abs(posX) + abs(posY) >= question) minMD = abs(posX) + abs(posY) - question;
    else                                  minMD = question - abs(posX) - abs(posY), minMD %= 2;
    
    // 5. 出力 ～ 後処理.
    if(T == 1) cout << maxMD << endl;
    else       cout << minMD << endl;
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

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

int main() {

// 1. 入力情報取得.

string S;

int T;

cin >> S >> T;

// 2. '?' をカウントしつつ, 文字列最終まで, 走査.

int question = 0;

int posX = 0, posY = 0;

FOR(i, 0, S.size()){

char c = S[i];

// 命令が, 'L' の場合.

if(c == 'L') posX--;

// 命令が, 'R' の場合.

if(c == 'R') posX++;

// 命令が, 'U' の場合.

if(c == 'U') posY++;

// 命令が, 'D' の場合.

if(c == 'D') posY--;

// 命令が, '?' の場合.

if(c == '?') question++;

}

// 3. 最大値を計算.

// int maxMD = 0;

// 3-1. posX > 0 の場合, 命令'?' は, 'R' だったと推定.

// if(posX > 0) maxMD = posX + abs(posY) + question;

// 3-2. posX < 0 の場合, 命令'?' は, 'L' だったと推定.

// if(posX < 0) maxMD = abs(posX) + abs(posY) + question;

// 3-3. posX == 0 かつ posY > 0 の場合, 命令'?' は, 'U' だったと推定.

// if(posX == 0 && posY > 0) maxMD = posY + question;

// 3-4. posX == 0 かつ posY < 0 の場合, 命令'?' は, 'D' だったと推定.

// if(posX == 0 && posY > 0) maxMD = abs(posY) + question;

// 3-5. posX == 0 かつ posY == 0 の場合, 命令'?' は, 'R' だったと推定(※なんでも良さそう).

// if(posX == 0 && posY == 0) maxMD = question;

// -> 3-1. ～ 3-5. は, 以下に集約されるはず.

int maxMD = abs(posX) + abs(posY) + question;

// 4. 最小値を計算.

// -> 直観的には, abs(posX) + abs(posY) から question を引いた数になりそう.

// question が非常に大きい場合は, 差分を 2 で割った余りになりそう.

int minMD = 0;

if(abs(posX) + abs(posY) >= question) minMD = abs(posX) + abs(posY) - question;

else minMD = question - abs(posX) - abs(posY), minMD %= 2;

// 5. 出力～後処理.

if(T == 1) cout << maxMD << endl;

else cout << minMD << endl;

return 0;

}

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

// AC版.
// ※※※ 以下のライブラリを使って, 解答を作成 ※※※.
// 遅延評価セグメント木をソラで書きたいあなたに.
// http://tsutaj.hatenablog.com/entry/2017/03/30/224339
// http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2236726
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int const INF = INT_MAX;

int N, Q;
struct LazySegmentTree {
private:
    int n;
    vector<LL> node, lazy;
public:
    LazySegmentTree(vector<LL> v) {
        int sz = (int)v.size();
        n = 1; while(n < sz) n *= 2;
        node.resize(2 * n - 1);
        lazy.resize(2 * n - 1, 0);
        // 元配列 の 値 を, セグメント木のノード に 保存.
        for(int i = 0; i < sz; i++)     node[i + n - 1] = v[i];
        for(int i = n - 2; i >= 0; i--) node[i] = node[i * 2 + 1] + node[i * 2 + 2];
    }
    void eval(int k, int l, int r) {
        if(lazy[k] != 0) {
            node[k] += lazy[k];
            if(r - l > 1) {
                lazy[2 * k + 1] += lazy[k] / 2;
                lazy[2 * k + 2] += lazy[k] / 2;
            }
            lazy[k] = 0;
        }
    }
    void add(int a, int b, LL x, int k = 0, int l = 0, int r = -1) {
        if(r < 0) r = n;
        eval(k, l, r);
        if(b <= l || r <= a) return;
        if(a <= l && r <= b) {
            lazy[k] += (r - l) * x;
            eval(k, l, r);
        }
        else {
            add(a, b, x, 2 * k + 1, l, (l + r) / 2);
            add(a, b, x, 2 * k + 2, (l + r) / 2, r);
            node[k] = node[2 * k + 1] + node[2 * k + 2];
        }
    }
    LL getSum(int a, int b, int k = 0, int l = 0, int r = -1) {
        if(r < 0) r = n;
        eval(k, l, r);
        if(b <= l || r <= a) return 0;
        if(a <= l && r <= b) return node[k];
        LL vl = getSum(a, b, 2 * k + 1,           l, (l + r) / 2);
        LL vr = getSum(a, b, 2 * k + 2, (l + r) / 2,           r);
        return vl + vr;
    }

};

int main() {

    // 1. 入力情報取得.
    int N, Q;
    cin >> N >> Q;
    
    // 2. 遅延評価セグメント木を呼び出す.
    LazySegmentTree seg(vector<LL>(N, 0));
    for(int i = 0; i < Q; i++){
        int l, r;
        cin >> l >> r;
        seg.add(l - 1, r, 1);
    }
    
    // 3. 出力 ～ 後処理.
    // 区間和 を mod 2 で, 出力.
    for(int i = 0; i < N; i++){
        int v = seg.getSum(i, i + 1);
        v %= 2;
        cout << v;
    }
    cout << endl;
    return 0;

}

// AC版.

// ※※※ 以下のライブラリを使って, 解答を作成 ※※※.

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

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

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

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

int const INF = INT_MAX;

int N, Q;

struct LazySegmentTree {

private:

int n;

vector<LL> node, lazy;

public:

LazySegmentTree(vector<LL> v) {

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

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

node.resize(2 * n - 1);

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

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

for(int i = 0; i < sz; i++) node[i + n - 1] = v[i];

for(int i = n - 2; i >= 0; i--) node[i] = node[i * 2 + 1] + node[i * 2 + 2];

}

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

if(lazy[k] != 0) {

node[k] += lazy[k];

if(r - l > 1) {

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

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

}

lazy[k] = 0;

}

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

if(r < 0) r = n;

eval(k, l, r);

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

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

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

eval(k, l, r);

}

else {

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

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

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

}

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

if(r < 0) r = n;

eval(k, l, r);

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

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

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

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

return vl + vr;

}

};

int main() {

// 1. 入力情報取得.

int N, Q;

cin >> N >> Q;

// 2. 遅延評価セグメント木を呼び出す.

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

for(int i = 0; i < Q; i++){

int l, r;

cin >> l >> r;

seg.add(l - 1, r, 1);

}

// 3. 出力～後処理.

// 区間和を mod 2 で, 出力.

for(int i = 0; i < N; i++){

int v = seg.getSum(i, i + 1);

v %= 2;

cout << v;

}

cout << endl;

return 0;

}

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

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

[入力例]
20 8
1 8
4 13
8 8
3 18
5 20
19 20
2 7
4 9

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

[入力例]
1 1
1 1

[出力例]
1

[入力例]
5 2
1 2
2 3

[出力例]
10100

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

[出力例]
0111101

※実際, 以下のような順で, 更新される.
0000000
↓
↓[1, 3]
↓
1110000
↓
↓[2, 4]
↓
1001000
↓
↓[1, 5]
↓
0110100
↓
↓[4, 6]
↓
0111010
↓
↓[5, 7]
↓
0111101

[入力例]

5 4

1 4

2 5

3 3

1 5

[出力例]

01010

※AtCoderテストケースより

[入力例]

20 8

1 8

4 13

8 8

3 18

5 20

19 20

2 7

4 9

[出力例]

10110000011110000000

※AtCoderテストケースより

[入力例]

1 1

[出力例]

[入力例]

5 2

1 2

2 3

[出力例]

10100

[入力例]

7 5

1 3

2 4

1 5

4 6

5 7

[出力例]

0111101

※実際, 以下のような順で, 更新される.

0000000

↓

↓[1, 3]

↓

1110000

↓

↓[2, 4]

↓

1001000

↓

↓[1, 5]

↓

0110100

↓

↓[4, 6]

↓

0111010

↓

↓[5, 7]

↓

0111101

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

2019年6月23日

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

C++の練習を兼ねて, AtCoder Regular Contest 006 の問題C (C – 積み重ね) を解いてみた.

■感想.
1. どこかで類題を見た記憶があったので, 探したところ, 本問も, yukicoder の No.4 おもりと天秤に似ていることが分かった.

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

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

// 段ボール箱の山のリストを更新する.
// @param ms: 段ボール箱のリスト.
// @param w: 追加予定の段ボール.
// @return ret: 段ボール箱の山のリスト.
vector<vector<int>> updateMountains(vector<vector<int>> ms, int w){

    // 1. 段ボールを, 既存の山に追加した場合.
    vector<vector<int>> ret;
    bool b = false;
    for(auto &m : ms){
        if(!b && m.back() >= w){
            m.push_back(w);
            b = true;
        }
        ret.push_back(m);
    }
    
    // 2. 段ボールを, 新規の山に追加した場合.
    if(!b){
        vector<int> v;
        v.push_back(w);
        ret.push_back(v);
    }

    return ret;

}


int main() {
    
    // 1. 入力情報取得.
    int N;
    cin >> N;
    int w[N];
    for(int i = 0; i < N; ++i) cin >> w[i];
    
    // 2. 段ボールを積んでいく.
    vector<vector<int>> mountains;
    
    // 2-1. 1箱目を追加.
    vector<int> mountain;
    mountain.push_back(w[0]);
    mountains.push_back(mountain);
    
    // 2-2. 2箱目以降を追加.
    for(int i = 1; i < N; i++){
        vector<vector<int>> lc = updateMountains(mountains, w[i]);
        swap(mountains, lc);
    }
    
    // 3. 出力.
    // for(auto &ms : mountains){
    //     for(auto &m : ms) cout << m << " ";
    //     cout << endl;
    // }
    cout << mountains.size() << endl;
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

// 段ボール箱の山のリストを更新する.

// @param ms: 段ボール箱のリスト.

// @param w: 追加予定の段ボール.

// @return ret: 段ボール箱の山のリスト.

vector<vector<int>> updateMountains(vector<vector<int>> ms, int w){

// 1. 段ボールを, 既存の山に追加した場合.

vector<vector<int>> ret;

bool b = false;

for(auto &m : ms){

if(!b && m.back() >= w){

m.push_back(w);

b = true;

}

ret.push_back(m);

}

// 2. 段ボールを, 新規の山に追加した場合.

if(!b){

vector<int> v;

v.push_back(w);

ret.push_back(v);

}

return ret;

}

int main() {

// 1. 入力情報取得.

int N;

cin >> N;

int w[N];

for(int i = 0; i < N; ++i) cin >> w[i];

// 2. 段ボールを積んでいく.

vector<vector<int>> mountains;

// 2-1. 1箱目を追加.

vector<int> mountain;

mountain.push_back(w[0]);

mountains.push_back(mountain);

// 2-2. 2箱目以降を追加.

for(int i = 1; i < N; i++){

vector<vector<int>> lc = updateMountains(mountains, w[i]);

swap(mountains, lc);

}

// 3. 出力.

// for(auto &ms : mountains){

// for(auto &m : ms) cout << m << " ";

// cout << endl;

// }

cout << mountains.size() << endl;

return 0;

}

[入力例]
5
4
3
1
2
1

[出力例(debug版)]
4 3 1 1 
2 
2
※AtCoderのテストケースより

[入力例]
7
93
249
150
958
442
391
25

[出力例(debug版)]
93 25 
249 150 
958 442 391 
3
※AtCoderのテストケースより

[入力例]
4
100
100
100
100

[出力例(debug版)]
100 100 100 100 
1
※AtCoderのテストケースより

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

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

[入力例]
25
34
12
7
89
45
90
47
3
58
79
66
19
23
50
8
11
75
39
45
67
20
25
1
81
2

[出力例(debug版)]
34 12 7 3 1 
89 45 19 8 2 
90 47 23 11 
58 50 39 20 
79 66 45 25 
75 67 
81 
7

100

101

102

103

104

105

106

107

108

[入力例]

[出力例(debug版)]

4 3 1 1

※AtCoderのテストケースより

[入力例]

249

150

958

442

391

[出力例(debug版)]

93 25

249 150

958 442 391

※AtCoderのテストケースより

[入力例]

100

[出力例(debug版)]

100 100 100 100

※AtCoderのテストケースより

[入力例]

[出力例(debug版)]

3 1 1

4 2

5 5 3

9 6 5

8 7

9 9

※AtCoderのテストケースより

[入力例]

[出力例(debug版)]

34 12 7 3 1

89 45 19 8 2

90 47 23 11

58 50 39 20

79 66 45 25

75 67

■参照サイト
AtCoder Regular Contest 006
No.4 おもりと天秤

2019年6月22日

■感想.
1. AtCoder Typical Contest 002 の A – 幅優先探索に似ているように見えたが, 解けそうになかったので, ネット上の情報を探した.
2. 01-BFS で解いていく方針が紹介されていた(※下記, 参照サイト)ので, もともとの幅優先探索のロジックを, 01-BFS用に書き換えた.
※但し, 書き換え前のコードを, ほとんどコメントアウトしているので, やや見づらくなってしまったように見える.
3. 新しい知識として, 01-BFS のアルゴリズムを体感できたので, 非常に勉強になったと思う.

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

// A - 幅優先探索
// https://atcoder.jp/contests/atc002
// -> 01-BFS版 に ロジック書き換え.
#include <bits/stdc++.h>
using namespace std;
// constexpr int MAX = 400;
constexpr int MAX = 250001;
constexpr int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};
int R, C;
int sx, sy, gx, gy;
int board[MAX];
int memo[MAX];

// 幅優先探索(01-BFS版).
// https://ja.wikipedia.org/wiki/幅優先探索
// 迷路を幅優先探索する.
// ※bfsの動作確認用.
// @param s: 探索開始地点の迷路上の座標.
// @return: 特に無し.
void bfs(int s){
    
    // 1. 空のキュー.
    // ※ 01-BFS の 場合は, deque を 使うとのこと.
    // queue<int> q;
    deque<int> q;
    
    // 2. 訪問済みフラグ設定.
    // ※スタート地点は, 距離ゼロを指定.
    memo[s] = 0;
    
    // 3. 探索地点 s をキュー q に追加.
    // q.push(s);
    q.push_back(s);
    while(!q.empty()){
        // 4. キューから取り出す.
        int v = q.front();
        // q.pop();
        q.pop_front();
        
        // 5. 取り出した要素を処理.
        // x: 列方向, y: 行方向 で考える.
        int nx, ny, n;
        int cx = v % C , cy = v / C;
        for(int i = 0; i < 4; ++i){
            nx = cx + dx[i];
            ny = cy + dy[i];
            n = nx + ny * C;
            // cout << "cx=" << cx << " nx=" << nx  << " cy=" << cy << " ny=" << ny << " n=" << n << " c=" << c << endl;
            // 6. 訪問不可能なマス であれば, 処理をスキップ.
            if(n < 0 || nx < 0 || nx >= C || ny < 0 || ny >= R) continue;
            
            // --- (ここから, ロジックから除外) --------------------------------------------------------------
            // if(board[n] == '#')                                 continue;
            
            // 7. 訪問先のマスで, 訪問可能 かつ スタート地点でない かつ 未訪問 であれば, 訪問済み(※最短ルート)を設定.
            // if(board[n] == '.' && n != s && memo[n] == 0) memo[n] = memo[v] + 1, q.push(n);
            // --- (ここまで, ロジックから除外) --------------------------------------------------------------
            
            // 7. 壁の場合は, 距離を 1 加算.
            int d = 0;
            if(board[n] == '#') d = memo[v] + 1;
            else                d = memo[v];
            
            // 8. より短い経路であれば, 更新.
            if(memo[n] > d){
                memo[n] = d;
                if(board[n] == '#') q.push_back(n);  // 壁の場合.
                else                q.push_front(n); // 壁でない場合.
            }
            
        }
    }
    return;
}

int main() {
    
    // 1. 入力情報取得.
    // cin >> R >> C >> sy >> sx >> gy >> gx;
    // sy--, sx--, gy--, gx--;
    cin >> R >> C;
    for(int i = 0; i < R; ++i){
        string s;
        cin >> s;
        for(int j = 0; j < C; ++j){
            board[i * C + j] = s[j];
            // スタート地点, ゴール地点を設定.
            if(s[j] == 's') sx = j, sy = i;
            if(s[j] == 'g') gx = j, gy = i;
        }
    }
    
    // 2. 探索を開始し, 探索距離を更新.
    for(int i = 0; i < R * C; i++) memo[i] = 1e9; // 01-BFSで, より短い距離に更新するために必要.
    bfs(sy * C + sx);
    // for(int i = 0; i < R; ++i){
    //     for(int j = 0; j < C; ++j){
    //         cout << memo[i * C + j] << " ";
    //     }
    //     cout << endl;
    // }
    
    // 3. 出力.
    int ans = memo[gy * C + gx];
    // cout << ans << endl;
    if(ans <= 2) cout << "YES" << endl;
    else         cout << "NO"  << endl;
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

110

// A - 幅優先探索

// https://atcoder.jp/contests/atc002

// -> 01-BFS版にロジック書き換え.

#include <bits/stdc++.h>

using namespace std;

// constexpr int MAX = 400;

constexpr int MAX = 250001;

constexpr int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};

int R, C;

int sx, sy, gx, gy;

int board[MAX];

int memo[MAX];

// 幅優先探索(01-BFS版).

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

// 迷路を幅優先探索する.

// ※bfsの動作確認用.

// @param s: 探索開始地点の迷路上の座標.

// @return: 特に無し.

void bfs(int s){

// 1. 空のキュー.

// ※ 01-BFS の場合は, deque を使うとのこと.

// queue<int> q;

deque<int> q;

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

// ※スタート地点は, 距離ゼロを指定.

memo[s] = 0;

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

// q.push(s);

q.push_back(s);

while(!q.empty()){

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

int v = q.front();

// q.pop();

q.pop_front();

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

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

int nx, ny, n;

int cx = v % C , cy = v / C;

for(int i = 0; i < 4; ++i){

nx = cx + dx[i];

ny = cy + dy[i];

n = nx + ny * C;

// cout << "cx=" << cx << " nx=" << nx << " cy=" << cy << " ny=" << ny << " n=" << n << " c=" << c << endl;

// 6. 訪問不可能なマスであれば, 処理をスキップ.

if(n < 0 || nx < 0 || nx >= C || ny < 0 || ny >= R) continue;

// --- (ここから, ロジックから除外) --------------------------------------------------------------

// if(board[n] == '#') continue;

// 7. 訪問先のマスで, 訪問可能かつスタート地点でないかつ未訪問であれば, 訪問済み(※最短ルート)を設定.

// if(board[n] == '.' && n != s && memo[n] == 0) memo[n] = memo[v] + 1, q.push(n);

// --- (ここまで, ロジックから除外) --------------------------------------------------------------

// 7. 壁の場合は, 距離を 1 加算.

int d = 0;

if(board[n] == '#') d = memo[v] + 1;

else d = memo[v];

// 8. より短い経路であれば, 更新.

if(memo[n] > d){

memo[n] = d;

if(board[n] == '#') q.push_back(n); // 壁の場合.

else q.push_front(n); // 壁でない場合.

}

return;

}

int main() {

// 1. 入力情報取得.

// cin >> R >> C >> sy >> sx >> gy >> gx;

// sy--, sx--, gy--, gx--;

cin >> R >> C;

for(int i = 0; i < R; ++i){

string s;

cin >> s;

for(int j = 0; j < C; ++j){

board[i * C + j] = s[j];

// スタート地点, ゴール地点を設定.

if(s[j] == 's') sx = j, sy = i;

if(s[j] == 'g') gx = j, gy = i;

}

// 2. 探索を開始し, 探索距離を更新.

for(int i = 0; i < R * C; i++) memo[i] = 1e9; // 01-BFSで, より短い距離に更新するために必要.

bfs(sy * C + sx);

// for(int i = 0; i < R; ++i){

// for(int j = 0; j < C; ++j){

// cout << memo[i * C + j] << " ";

// }

// cout << endl;

// }

// 3. 出力.

int ans = memo[gy * C + gx];

// cout << ans << endl;

if(ans <= 2) cout << "YES" << endl;

else cout << "NO" << endl;

return 0;

}

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

[出力例(debug版)]
0 0 0 0 0 0 0 0 0 0 
1 1 1 1 1 1 1 1 1 0 
1 0 0 0 0 0 0 0 1 0 
1 0 0 1 1 1 1 0 1 0 
2 1 0 0 0 0 1 0 1 0 
3 2 1 1 1 0 1 0 1 0 
2 2 1 0 1 0 1 0 1 0 
3 2 1 0 1 0 1 0 1 0 
2 1 1 0 1 0 1 0 1 0 
1 0 0 0 0 0 1 0 0 0 
YES
※AtCoderのテストケースより

[入力例]
4 5
s####
....#
#####
#...g

[出力例(debug版)]
0 1 1 1 2 
0 0 0 0 1 
1 1 1 1 2 
2 1 1 1 1 
YES
※AtCoderのテストケースより

[入力例]
1 10
s..####..g

[出力例(debug版)]
0 0 0 1 2 3 4 4 4 4 
NO

[入力例]
12 17
.####.####.######
s...#.####.######
##.##.####.######
#...#.#..#.##..##
###.#.####.###.##
#.....#..#.##..##
#####.####.###.##
#...#.#..#.##..##
#####.#.##.###.##
##....#.##.###g##
##.####.##.######
##.........#...##

[出力例(debug版)]
0 1 1 1 1 0 1 2 2 1 0 1 2 3 4 5 6 
0 0 0 0 1 0 1 2 2 1 0 1 2 3 4 5 6 
1 1 0 1 1 0 1 2 2 1 0 1 2 3 3 4 5 
1 0 0 0 1 0 1 1 1 1 0 1 2 2 2 3 4 
2 1 1 0 1 0 1 2 2 1 0 1 2 3 2 3 4 
1 0 0 0 0 0 1 1 1 1 0 1 2 2 2 3 4 
2 1 1 1 1 0 1 1 1 1 0 1 2 3 2 3 4 
2 1 1 1 1 0 1 0 0 1 0 1 2 2 2 3 4 
3 2 1 1 1 0 1 0 1 1 0 1 2 3 2 3 4 
2 1 0 0 0 0 1 0 1 1 0 1 2 3 2 3 4 
2 1 0 1 1 1 1 0 1 1 0 1 2 2 2 3 4 
2 1 0 0 0 0 0 0 0 0 0 1 1 1 1 2 3 
YES

[入力例]

10 10

s.........

#########.

#.......#.

#..####.#.

##....#.#.

#####.#.#.

g##.#.#.#.

###.#.#.#.

#.....#...

[出力例(debug版)]

0 0 0 0 0 0 0 0 0 0

1 1 1 1 1 1 1 1 1 0

1 0 0 0 0 0 0 0 1 0

1 0 0 1 1 1 1 0 1 0

2 1 0 0 0 0 1 0 1 0

3 2 1 1 1 0 1 0 1 0

2 2 1 0 1 0 1 0 1 0

3 2 1 0 1 0 1 0 1 0

2 1 1 0 1 0 1 0 1 0

1 0 0 0 0 0 1 0 0 0

YES

※AtCoderのテストケースより

[入力例]

4 5

s####

....#

#####

#...g

[出力例(debug版)]

0 1 1 1 2

0 0 0 0 1

1 1 1 1 2

2 1 1 1 1

YES

※AtCoderのテストケースより

[入力例]

1 10

s..####..g

[出力例(debug版)]

0 0 0 1 2 3 4 4 4 4

[入力例]

12 17

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

s...#.####.######

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

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

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

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

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

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

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

##....#.##.###g##

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

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

[出力例(debug版)]

0 1 1 1 1 0 1 2 2 1 0 1 2 3 4 5 6

0 0 0 0 1 0 1 2 2 1 0 1 2 3 4 5 6

1 1 0 1 1 0 1 2 2 1 0 1 2 3 3 4 5

1 0 0 0 1 0 1 1 1 1 0 1 2 2 2 3 4

2 1 1 0 1 0 1 2 2 1 0 1 2 3 2 3 4

1 0 0 0 0 0 1 1 1 1 0 1 2 2 2 3 4

2 1 1 1 1 0 1 1 1 1 0 1 2 3 2 3 4

2 1 1 1 1 0 1 0 0 1 0 1 2 2 2 3 4

3 2 1 1 1 0 1 0 1 1 0 1 2 3 2 3 4

2 1 0 0 0 0 1 0 1 1 0 1 2 3 2 3 4

2 1 0 1 1 1 1 0 1 1 0 1 2 2 2 3 4

2 1 0 0 0 0 0 0 0 0 0 1 1 1 1 2 3

YES

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

2019年6月20日

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

C++の練習を兼ねて, AtCoder Beginner Contest 088 の問題D (D – Grid Repainting) を解いてみた.

■感想.
1. どこかで類題を見た記憶があったので, 探したところ, AtCoder Typical Contest 002 の A – 幅優先探索に似ていることが分かった.
2. 幅優先探索(BFS) を復習出来たので, 良かったと思う.

本家のサイトAtcoder Beginner Contest 088 解説をご覧下さい.

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

// A - 幅優先探索.
// https://atcoder.jp/contests/atc002/tasks/abc007_3
// -> 上記の解答を, 少し修正した版.
#include <bits/stdc++.h>
using namespace std;
// constexpr int MAX = 400;
constexpr int MAX = 2601;
constexpr int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};
int R, C;
int sx, sy, gx, gy;
int board[MAX];
int memo[MAX];

// 幅優先探索.
// https://ja.wikipedia.org/wiki/幅優先探索
// 迷路を幅優先探索する.
// ※bfsの動作確認用.
// @param s: 探索開始地点の迷路上の座標.
// @return: 特に無し.
void bfs(int s){
    
    // 1. 空のキュー.
    queue<int> q;
    
    // 2. 訪問済みフラグ設定.
    // ※スタート地点は, 距離ゼロを指定.
    memo[s] = 0;
    
    // 3. 探索地点 s をキュー q に追加.
    q.push(s);
    while(!q.empty()){
        // 4. キューから取り出す.
        int v = q.front();
        q.pop();
        // 5. 取り出した要素を処理.
        // x: 列方向, y: 行方向 で考える.
        int nx, ny, n;
        int cx = v % C , cy = v / C;
        for(int i = 0; i < 4; ++i){
            nx = cx + dx[i];
            ny = cy + dy[i];
            n = nx + ny * C;
            // cout << "cx=" << cx << " nx=" << nx  << " cy=" << cy << " ny=" << ny << " n=" << n << " c=" << c << endl;
            // 6. 訪問不可能なマス であれば, 処理をスキップ.
            if(n < 0 || nx < 0 || nx >= C || ny < 0 || ny >= R) continue;
            if(board[n] == '#')                                 continue;
            
            // 7. 訪問先のマスで, 訪問可能 かつ スタート地点でない かつ 未訪問 であれば, 訪問済み(※最短ルート)を設定.
            if(board[n] == '.' && n != s && memo[n] == 0) memo[n] = memo[v] + 1, q.push(n);
        }
    }
    return;
}

int main() {
    
    // 1. 入力情報取得.
    cin >> R >> C;
    sy = 1, sx = 1, gy = R, gx = C;
    sy--, sx--, gy--, gx--;
    int dot = 0;
    for(int i = 0; i < R; ++i){
        string s;
        cin >> s;
        for(int j = 0; j < C; ++j){
            board[i * C + j] = s[j];
            // 白マスの個数をカウント.
            if(s[j] == '.') dot++;
        }
    }
    
    // 2. 探索を開始し, 探索距離を更新.
    bfs(sy * C + sx);
    // ゴールまでの最短距離(※ゼロの場合は, ゴールに辿り着けないと判定).
    int dist = memo[gy * C + gx];
    // for(int i = 0; i < R; ++i){
    //     for(int j = 0; j < C; ++j){
    //         cout << memo[i * C + j] << " ";
    //     }
    //     cout << endl;
    // }
    
    // 3. 出力.
    int ans = -1;
    // マス(1, 1), マス(H, W) の 色 は 変更できないので, (dist + 1) を 引く形に修正.
    if(dist > 0) ans = dot - (dist + 1);
    cout << ans << endl;
    return 0;
    
}

// A - 幅優先探索.

// https://atcoder.jp/contests/atc002/tasks/abc007_3

// -> 上記の解答を, 少し修正した版.

#include <bits/stdc++.h>

using namespace std;

// constexpr int MAX = 400;

constexpr int MAX = 2601;

constexpr int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};

int R, C;

int sx, sy, gx, gy;

int board[MAX];

int memo[MAX];

// 幅優先探索.

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

// 迷路を幅優先探索する.

// ※bfsの動作確認用.

// @param s: 探索開始地点の迷路上の座標.

// @return: 特に無し.

void bfs(int s){

// 1. 空のキュー.

queue<int> q;

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

// ※スタート地点は, 距離ゼロを指定.

memo[s] = 0;

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

q.push(s);

while(!q.empty()){

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

int v = q.front();

q.pop();

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

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

int nx, ny, n;

int cx = v % C , cy = v / C;

for(int i = 0; i < 4; ++i){

nx = cx + dx[i];

ny = cy + dy[i];

n = nx + ny * C;

// cout << "cx=" << cx << " nx=" << nx << " cy=" << cy << " ny=" << ny << " n=" << n << " c=" << c << endl;

// 6. 訪問不可能なマスであれば, 処理をスキップ.

if(n < 0 || nx < 0 || nx >= C || ny < 0 || ny >= R) continue;

if(board[n] == '#') continue;

// 7. 訪問先のマスで, 訪問可能かつスタート地点でないかつ未訪問であれば, 訪問済み(※最短ルート)を設定.

if(board[n] == '.' && n != s && memo[n] == 0) memo[n] = memo[v] + 1, q.push(n);

}

return;

}

int main() {

// 1. 入力情報取得.

cin >> R >> C;

sy = 1, sx = 1, gy = R, gx = C;

sy--, sx--, gy--, gx--;

int dot = 0;

for(int i = 0; i < R; ++i){

string s;

cin >> s;

for(int j = 0; j < C; ++j){

board[i * C + j] = s[j];

// 白マスの個数をカウント.

if(s[j] == '.') dot++;

}

// 2. 探索を開始し, 探索距離を更新.

bfs(sy * C + sx);

// ゴールまでの最短距離(※ゼロの場合は, ゴールに辿り着けないと判定).

int dist = memo[gy * C + gx];

// for(int i = 0; i < R; ++i){

// for(int j = 0; j < C; ++j){

// cout << memo[i * C + j] << " ";

// }

// cout << endl;

// }

// 3. 出力.

int ans = -1;

// マス(1, 1), マス(H, W) の色は変更できないので, (dist + 1) を引く形に修正.

if(dist > 0) ans = dot - (dist + 1);

cout << ans << endl;

return 0;

}

[入力例]
2 2
..
..

[出力例(debug版)]
0 1 
1 2 
1

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

[出力例(debug版)]
0 1 0 0 
1 2 0 0 
2 0 0 0 
-1

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

[出力例(debug版)]
0 1 0 
0 2 3 
4 3 4 
2
※AtCoderテストケースより

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

[出力例(debug版)]
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 
1 2 3 0 5 6 7 0 0 0 0 12 13 14 0 0 0 0 19 20 0 0 0 24 25 26 0 0 0 30 31 32 0 0 0 36 37 
2 3 0 0 0 7 8 0 0 0 0 0 14 0 0 23 22 21 20 0 0 0 0 0 26 0 0 0 0 0 32 0 0 0 0 0 38 
3 4 0 0 0 8 9 0 0 0 0 0 15 0 25 24 23 22 21 0 0 0 0 0 27 0 0 0 0 0 33 0 0 0 0 0 39 
4 0 0 0 0 0 10 0 0 0 0 0 16 0 26 25 24 23 22 0 0 0 0 0 28 0 0 0 0 0 34 0 0 0 0 0 40 
5 0 0 0 0 0 11 0 0 0 0 18 17 0 27 26 25 24 23 0 0 0 0 0 29 30 0 0 37 36 35 36 0 0 43 42 41 
6 0 14 15 16 0 12 0 0 0 0 0 18 0 28 27 26 25 24 0 0 0 0 0 30 0 40 39 38 0 36 0 46 45 44 0 42 
7 0 13 14 15 0 13 0 0 0 0 0 19 0 0 28 27 26 25 0 0 0 0 0 31 0 41 40 39 0 37 0 47 46 45 0 43 
8 0 12 13 14 0 14 0 0 0 0 21 20 21 0 0 0 0 26 27 0 0 0 33 32 33 0 0 0 39 38 39 0 0 0 45 44 
9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 
209
※AtCoderテストケースより

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

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

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

[入力例]

2 2

[出力例(debug版)]

0 1

1 2

[入力例]

3 4

..#.

.#..

[出力例(debug版)]

0 1 0 0

1 2 0 0

2 0 0 0

-1

[入力例]

3 3

..#

#..

...

[出力例(debug版)]

0 1 0

0 2 3

4 3 4

※AtCoderテストケースより

[入力例]

10 37

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

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

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

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

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

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

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

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

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

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

[出力例(debug版)]

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

1 2 3 0 5 6 7 0 0 0 0 12 13 14 0 0 0 0 19 20 0 0 0 24 25 26 0 0 0 30 31 32 0 0 0 36 37

2 3 0 0 0 7 8 0 0 0 0 0 14 0 0 23 22 21 20 0 0 0 0 0 26 0 0 0 0 0 32 0 0 0 0 0 38

3 4 0 0 0 8 9 0 0 0 0 0 15 0 25 24 23 22 21 0 0 0 0 0 27 0 0 0 0 0 33 0 0 0 0 0 39

4 0 0 0 0 0 10 0 0 0 0 0 16 0 26 25 24 23 22 0 0 0 0 0 28 0 0 0 0 0 34 0 0 0 0 0 40

5 0 0 0 0 0 11 0 0 0 0 18 17 0 27 26 25 24 23 0 0 0 0 0 29 30 0 0 37 36 35 36 0 0 43 42 41

6 0 14 15 16 0 12 0 0 0 0 0 18 0 28 27 26 25 24 0 0 0 0 0 30 0 40 39 38 0 36 0 46 45 44 0 42

7 0 13 14 15 0 13 0 0 0 0 0 19 0 0 28 27 26 25 0 0 0 0 0 31 0 41 40 39 0 37 0 47 46 45 0 43

8 0 12 13 14 0 14 0 0 0 0 21 20 21 0 0 0 0 26 27 0 0 0 33 32 33 0 0 0 39 38 39 0 0 0 45 44

9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45

209

※AtCoderテストケースより

[入力例]

50 50

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[出力例(debug版)]

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 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

1 2 3 0 5 6 7 0 0 0 0 12 13 14 0 0 0 0 19 0 0 0 0 0 25 26 0 0 0 0 0 32 0 0 0 0 0 0 39 0 0 0 0 0 0 46 47 48 49 50

2 3 0 0 0 7 8 0 0 0 0 0 14 0 0 23 22 21 20 0 0 0 0 0 0 27 0 37 36 35 34 33 0 45 44 43 42 41 40 0 56 55 54 53 0 47 48 49 50 51

3 4 0 0 0 8 9 0 0 0 0 0 15 0 25 24 23 22 21 0 0 0 0 0 0 28 0 38 37 36 35 34 0 46 45 44 43 42 41 0 55 54 53 52 0 48 49 50 51 52

4 0 0 0 0 0 10 0 0 0 0 0 16 0 26 25 24 23 22 0 0 0 0 0 0 29 0 0 0 0 0 35 0 0 0 0 0 43 42 0 54 53 52 51 50 49 50 51 52 53

5 0 0 0 0 0 11 0 0 0 0 18 17 0 27 26 25 24 23 0 0 0 0 0 0 30 0 40 39 38 37 36 0 46 47 46 45 44 43 0 55 54 0 0 0 50 51 52 53 54

6 0 14 15 16 0 12 0 0 0 0 0 18 0 28 27 26 25 24 0 0 0 0 0 0 31 0 41 40 39 38 37 0 45 46 47 46 45 44 0 56 55 56 57 0 51 52 53 54 55

7 0 13 14 15 0 13 0 0 0 0 0 19 0 0 28 27 26 25 0 0 0 0 0 0 32 0 42 41 40 39 38 0 44 45 46 47 46 45 0 57 56 57 58 0 52 53 54 55 56

8 0 12 13 14 0 14 0 0 0 0 21 20 21 0 0 0 0 26 0 0 0 0 0 34 33 0 0 0 0 0 39 0 43 44 45 46 47 46 0 0 0 0 0 0 53 54 55 56 57

9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 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 51 52 53 54 55 56 57 58

10 11 12 13 14 15 16 17 18 19 20 21 22 23 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 51 52 53 54 55 56 57 58 59

11 12 13 0 15 16 17 0 0 0 0 22 23 24 0 0 0 0 29 0 0 0 0 0 35 36 0 0 0 0 0 42 0 0 0 0 0 0 49 0 0 0 0 0 0 56 57 58 59 60

12 13 0 0 0 17 18 0 0 0 0 0 24 0 0 33 32 31 30 0 0 0 0 0 0 37 0 47 46 45 44 43 0 55 54 53 52 51 50 0 66 65 64 63 0 57 58 59 60 61

13 14 0 0 0 18 19 0 0 0 0 0 25 0 35 34 33 32 31 0 0 0 0 0 0 38 0 48 47 46 45 44 0 56 55 54 53 52 51 0 65 64 63 62 0 58 59 60 61 62

14 0 0 0 0 0 20 0 0 0 0 0 26 0 36 35 34 33 32 0 0 0 0 0 0 39 0 0 0 0 0 45 0 0 0 0 0 53 52 0 64 63 62 61 60 59 60 61 62 63

15 0 0 0 0 0 21 0 0 0 0 28 27 0 37 36 35 34 33 0 0 0 0 0 0 40 0 50 49 48 47 46 0 56 57 56 55 54 53 0 65 64 0 0 0 60 61 62 63 64

16 0 24 25 26 0 22 0 0 0 0 0 28 0 38 37 36 35 34 0 0 0 0 0 0 41 0 51 50 49 48 47 0 55 56 57 56 55 54 0 66 65 66 67 0 61 62 63 64 65

17 0 23 24 25 0 23 0 0 0 0 0 29 0 0 38 37 36 35 0 0 0 0 0 0 42 0 52 51 50 49 48 0 54 55 56 57 56 55 0 67 66 67 68 0 62 63 64 65 66

18 0 22 23 24 0 24 0 0 0 0 31 30 31 0 0 0 0 36 0 0 0 0 0 44 43 0 0 0 0 0 49 0 53 54 55 56 57 56 0 0 0 0 0 0 63 64 65 66 67

19 20 21 22 23 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 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68

20 21 22 23 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 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69

21 22 23 0 25 26 27 0 0 0 0 32 33 34 0 0 0 0 39 0 0 0 0 0 45 46 0 0 0 0 0 52 0 0 0 0 0 0 59 0 0 0 0 0 0 66 67 68 69 70

22 23 0 0 0 27 28 0 0 0 0 0 34 0 0 43 42 41 40 0 0 0 0 0 0 47 0 57 56 55 54 53 0 65 64 63 62 61 60 0 76 75 74 73 0 67 68 69 70 71

23 24 0 0 0 28 29 0 0 0 0 0 35 0 45 44 43 42 41 0 0 0 0 0 0 48 0 58 57 56 55 54 0 66 65 64 63 62 61 0 75 74 73 72 0 68 69 70 71 72

24 0 0 0 0 0 30 0 0 0 0 0 36 0 46 45 44 43 42 0 0 0 0 0 0 49 0 0 0 0 0 55 0 0 0 0 0 63 62 0 74 73 72 71 70 69 70 71 72 73

25 0 0 0 0 0 31 0 0 0 0 38 37 0 47 46 45 44 43 0 0 0 0 0 0 50 0 60 59 58 57 56 0 66 67 66 65 64 63 0 75 74 0 0 0 70 71 72 73 74

26 0 34 35 36 0 32 0 0 0 0 0 38 0 48 47 46 45 44 0 0 0 0 0 0 51 0 61 60 59 58 57 0 65 66 67 66 65 64 0 76 75 76 77 0 71 72 73 74 75

27 0 33 34 35 0 33 0 0 0 0 0 39 0 0 48 47 46 45 0 0 0 0 0 0 52 0 62 61 60 59 58 0 64 65 66 67 66 65 0 77 76 77 78 0 72 73 74 75 76

28 0 32 33 34 0 34 0 0 0 0 41 40 41 0 0 0 0 46 0 0 0 0 0 54 53 0 0 0 0 0 59 0 63 64 65 66 67 66 0 0 0 0 0 0 73 74 75 76 77

29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78

30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79

31 32 33 0 35 36 37 0 0 0 0 42 43 44 0 0 0 0 49 0 0 0 0 0 55 56 0 0 0 0 0 62 0 0 0 0 0 0 69 0 0 0 0 0 0 76 77 78 79 80

32 33 0 0 0 37 38 0 0 0 0 0 44 0 0 53 52 51 50 0 0 0 0 0 0 57 0 67 66 65 64 63 0 75 74 73 72 71 70 0 86 85 84 83 0 77 78 79 80 81

33 34 0 0 0 38 39 0 0 0 0 0 45 0 55 54 53 52 51 0 0 0 0 0 0 58 0 68 67 66 65 64 0 76 75 74 73 72 71 0 85 84 83 82 0 78 79 80 81 82

34 0 0 0 0 0 40 0 0 0 0 0 46 0 56 55 54 53 52 0 0 0 0 0 0 59 0 0 0 0 0 65 0 0 0 0 0 73 72 0 84 83 82 81 80 79 80 81 82 83

35 0 0 0 0 0 41 0 0 0 0 48 47 0 57 56 55 54 53 0 0 0 0 0 0 60 0 70 69 68 67 66 0 76 77 76 75 74 73 0 85 84 0 0 0 80 81 82 83 84

36 0 44 45 46 0 42 0 0 0 0 0 48 0 58 57 56 55 54 0 0 0 0 0 0 61 0 71 70 69 68 67 0 75 76 77 76 75 74 0 86 85 86 87 0 81 82 83 84 85

37 0 43 44 45 0 43 0 0 0 0 0 49 0 0 58 57 56 55 0 0 0 0 0 0 62 0 72 71 70 69 68 0 74 75 76 77 76 75 0 87 86 87 88 0 82 83 84 85 86

38 0 42 43 44 0 44 0 0 0 0 51 50 51 0 0 0 0 56 0 0 0 0 0 64 63 0 0 0 0 0 69 0 73 74 75 76 77 76 0 0 0 0 0 0 83 84 85 86 87

39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88

40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89

41 42 43 0 45 46 47 0 0 0 0 52 53 54 0 0 0 0 59 0 0 0 0 0 65 66 0 0 0 0 0 72 0 0 0 0 0 0 79 0 0 0 0 0 0 86 87 88 89 90

42 43 0 0 0 47 48 0 0 0 0 0 54 0 0 63 62 61 60 0 0 0 0 0 0 67 0 77 76 75 74 73 0 85 84 83 82 81 80 0 96 95 94 93 0 87 88 89 90 91

43 44 0 0 0 48 49 0 0 0 0 0 55 0 65 64 63 62 61 0 0 0 0 0 0 68 0 78 77 76 75 74 0 86 85 84 83 82 81 0 95 94 93 92 0 88 89 90 91 92

44 0 0 0 0 0 50 0 0 0 0 0 56 0 66 65 64 63 62 0 0 0 0 0 0 69 0 0 0 0 0 75 0 0 0 0 0 83 82 0 94 93 92 91 90 89 90 91 92 93

45 0 0 0 0 0 51 0 0 0 0 58 57 0 67 66 65 64 63 0 0 0 0 0 0 70 0 80 79 78 77 76 0 86 87 86 85 84 83 0 95 94 0 0 0 90 91 92 93 94

46 0 54 55 56 0 52 0 0 0 0 0 58 0 68 67 66 65 64 0 0 0 0 0 0 71 0 81 80 79 78 77 0 85 86 87 86 85 84 0 96 95 96 97 0 91 92 93 94 95

47 0 53 54 55 0 53 0 0 0 0 0 59 0 0 68 67 66 65 0 0 0 0 0 0 72 0 82 81 80 79 78 0 84 85 86 87 86 85 0 97 96 97 98 0 92 93 94 95 96

48 0 52 53 54 0 54 0 0 0 0 61 60 61 0 0 0 0 66 0 0 0 0 0 74 73 0 0 0 0 0 79 0 83 84 85 86 87 86 0 0 0 0 0 0 93 94 95 96 97

49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98

1696

■参照サイト
AtCoder Beginner Contest 088

2019年6月16日2019年6月16日

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

C++の練習を兼ねて, AtCoder Beginner Contest 023 の問題D (D – 射撃王) を解いてみた.

■感想.
1. 解答方針がよく分からなかったので, 解説から類推する形で解き直しした.
2. 二分探索を実装する部分で, 終了条件をどうすればよいか分からず, 手こずった.
=> これを解決するために, ゴリゴリ書く羽目になったものの, 以下の二点を対応したところ, AC版とすることが出来た.
① 風船の情報を, 構造体に保管して, 再利用できるようにした
② 確認対象としている高度で, 風船を割る方法が存在するかをチェックする関数の追加を行った

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

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

// 解き直し.
// ABC023 解説.
// https://www.slideshare.net/chokudai/abc023
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const LL MAX = 1e18 + 1;

struct balloon {
    LL h;     // 風船の高度.
    LL s;     // 風船の速度.
    double t; // 制限時間.
    bool operator < (const balloon &B) const { return t < B.t; }
};

// 確認対象としている高度で, 風船を割る方法が存在するかをチェック.
// @param v: 風船に関する情報.
// @param opt: 確認対象の高度.
// @return : 風船を割る方法の存在確認.
//    true : 風船を割る方法が存在する, false : 風船を割る方法が存在しない.
bool isExist(vector<balloon> v, LL opt){
    
    bool ret = true;
    for(int i = 0; i < v.size(); i++){
        double bHeight = v[i].h + v[i].s * i + 0.0;
        // i秒後 の 風船の高さが, 確認対象の高度 を 超えていたら, 風船を割る方法が存在しないと判定.
        if(opt < bHeight){
            // cout << "i=" << i << " v[i].h=" << v[i].h << " v[i].s=" << v[i].h << " bHeight=" << bHeight << endl;
            ret = false;
            break;
        }
    }
    
    return ret;

}

int main() {
    
    // 1. 入力情報取得.
    int N;
    cin >> N;
    LL H[N], S[N];
    vector<balloon> v;
    for(int i = 0; i < N; i++){
        balloon b;
        cin >> b.h >> b.s;
        v.push_back(b);
    }
    
    // 2. 解説通り.
    // 高さを固定して, 制限時間で, sort.
    // -> 二分探索で, opt を 探す
    LL hi = MAX;
    LL lo  = 1;
    LL opt = MAX;
    int counter = 0;
    // 無限ループ防止のため, カウンター入れる.
    while(counter < 100){
        
        // 2-1. 制限時間を保存.
        for(int i = 0; i < N; i++){
            double t = (opt - v[i].h) / v[i].s;
            v[i].t = t;
        }
        
        // 2-2. sort.
        sort(v.begin(), v.end());
        
        // 2-3. hi, lo, opt 更新.
        // if(counter > 98) cout << " hi=" << hi << " lo=" << lo << " opt=" << opt << endl;
        bool b = isExist(v, opt);
        if(b) hi = (lo + hi) / 2LL;
        else  lo = (lo + hi) / 2LL + 1;
        opt = (hi + lo) / 2;
        
        // 2-4. カウンター を インクリメント.
        counter++;
        
        // 2-5. 終了.
        if(hi - lo <= 0) break;
        
    }
    
    // 3. 出力.
    cout << opt << endl;
    return 0;
   
}

// 解き直し.

// ABC023 解説.

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

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

const LL MAX = 1e18 + 1;

struct balloon {

LL h; // 風船の高度.

LL s; // 風船の速度.

double t; // 制限時間.

bool operator < (const balloon &B) const { return t < B.t; }

};

// 確認対象としている高度で, 風船を割る方法が存在するかをチェック.

// @param v: 風船に関する情報.

// @param opt: 確認対象の高度.

// @return : 風船を割る方法の存在確認.

// true : 風船を割る方法が存在する, false : 風船を割る方法が存在しない.

bool isExist(vector<balloon> v, LL opt){

bool ret = true;

for(int i = 0; i < v.size(); i++){

double bHeight = v[i].h + v[i].s * i + 0.0;

// i秒後の風船の高さが, 確認対象の高度を超えていたら, 風船を割る方法が存在しないと判定.

if(opt < bHeight){

// cout << "i=" << i << " v[i].h=" << v[i].h << " v[i].s=" << v[i].h << " bHeight=" << bHeight << endl;

ret = false;

break;

}

return ret;

}

int main() {

// 1. 入力情報取得.

int N;

cin >> N;

LL H[N], S[N];

vector<balloon> v;

for(int i = 0; i < N; i++){

balloon b;

cin >> b.h >> b.s;

v.push_back(b);

}

// 2. 解説通り.

// 高さを固定して, 制限時間で, sort.

// -> 二分探索で, opt を探す

LL hi = MAX;

LL lo = 1;

LL opt = MAX;

int counter = 0;

// 無限ループ防止のため, カウンター入れる.

while(counter < 100){

// 2-1. 制限時間を保存.

for(int i = 0; i < N; i++){

double t = (opt - v[i].h) / v[i].s;

v[i].t = t;

}

// 2-2. sort.

sort(v.begin(), v.end());

// 2-3. hi, lo, opt 更新.

// if(counter > 98) cout << " hi=" << hi << " lo=" << lo << " opt=" << opt << endl;

bool b = isExist(v, opt);

if(b) hi = (lo + hi) / 2LL;

else lo = (lo + hi) / 2LL + 1;

opt = (hi + lo) / 2;

// 2-4. カウンターをインクリメント.

counter++;

// 2-5. 終了.

if(hi - lo <= 0) break;

}

// 3. 出力.

cout << opt << endl;

return 0;

}

[入力例]
4
5 6
12 4
14 7
21 2

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

[入力例]
6
100 1
100 1
100 1
100 1
100 1
1 30

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

[入力例]
10
10 5
12 8
8 15
4 12
30 7
45 6
18 12
22 13
17 8
25 5

[出力例]
68
具体的には, 
競技開始から 0秒後 に 風船6 を割る, 風船6 の ペナルティは 45 +  6 × 0 = 45
競技開始から 1秒後 に 風船8 を割る, 風船8 の ペナルティは 22 + 13 × 1 = 35
競技開始から 2秒後 に 風船5 を割る, 風船5 の ペナルティは 30 +  7 × 2 = 44
競技開始から 3秒後 に 風船7 を割る, 風船7 の ペナルティは 18 + 12 × 3 = 54
競技開始から 4秒後 に 風船3 を割る, 風船3 の ペナルティは  8 + 15 × 4 = 68
競技開始から 5秒後 に 風船4 を割る, 風船4 の ペナルティは  4 + 12 × 5 = 64
競技開始から 6秒後 に 風船9 を割る, 風船9 の ペナルティは 17 +  8 × 6 = 65
競技開始から 7秒後 に 風船2 を割る, 風船2 の ペナルティは 12 +  8 × 7 = 68
競技開始から 8秒後 に 風船10を割る, 風船10の ペナルティは 25 +  5 × 8 = 65
競技開始から 9秒後 に 風船1 を割る, 風船1 の ペナルティは 10 +  5 × 9 = 55

[入力例]

5 6

12 4

14 7

21 2

[出力例]

※AtCoderテストケースより

[入力例]

100 1

1 30

[出力例]

105

※AtCoderテストケースより

[入力例]

10 5

12 8

8 15

4 12

30 7

45 6

18 12

22 13

17 8

25 5

[出力例]

具体的には,

競技開始から 0秒後に風船6 を割る, 風船6 のペナルティは 45 + 6 × 0 = 45

競技開始から 1秒後に風船8 を割る, 風船8 のペナルティは 22 + 13 × 1 = 35

競技開始から 2秒後に風船5 を割る, 風船5 のペナルティは 30 + 7 × 2 = 44

競技開始から 3秒後に風船7 を割る, 風船7 のペナルティは 18 + 12 × 3 = 54

競技開始から 4秒後に風船3 を割る, 風船3 のペナルティは 8 + 15 × 4 = 68

競技開始から 5秒後に風船4 を割る, 風船4 のペナルティは 4 + 12 × 5 = 64

競技開始から 6秒後に風船9 を割る, 風船9 のペナルティは 17 + 8 × 6 = 65

競技開始から 7秒後に風船2 を割る, 風船2 のペナルティは 12 + 8 × 7 = 68

競技開始から 8秒後に風船10を割る, 風船10のペナルティは 25 + 5 × 8 = 65

競技開始から 9秒後に風船1 を割る, 風船1 のペナルティは 10 + 5 × 9 = 55

■参照サイト
AtCoder Beginner Contest 023

2019年6月16日

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

C++の練習を兼ねて, AtCoder Beginner Contest 006 の問題D (D – トランプ挿入ソート) を解いてみた.

■感想.
1. 解答方針がよく分からなかったので, 解説を丸写しする感覚で解き直しした.
2. 新しい知識として, LIS(Longest increase subsequence) のアルゴリズムを体感できたので, 非常に勉強になったと思う.

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

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

// 解き直し.
// AtCoder Beginner Contest 006 解説.
// https://www.slideshare.net/chokudai/abc006
#include <bits/stdc++.h>
using namespace std;
const int MAX = 3e4 + 1;

int main() {
    
    // 1. 入力情報取得.
    int N;
    cin >> N;
    vector<int> c(N);
    vector<int> dp;
    for(int i = 0; i < N; i++) cin >> c[i];
    
    // 2. 解説通り.
    // -> LIS で 解く必要があるとのこと.
    dp.push_back(c[0]);
    for(int i = 1; i < N; i++){
        // 2-1. dpテーブル末尾 の 要素(last) より大きな値(c[i])であれば, dpテーブル に 追加.
        int last = dp.back();
        if(last < c[i]) dp.push_back(c[i]);
        // 2-2. dpテーブル末尾 の 要素(last) より小さな値(c[i])であれば, 
        // dpテーブル上 の 更新場所 を 探索後, dpテーブル を 更新.
        if(last > c[i]){
            auto it = lower_bound(dp.begin(), dp.end(), c[i]);
            int dist = it - dp.begin();
            dp[dist] = c[i];
            // for(int i = 0; i < dp.size(); i++) cout << dp[i] << " ";
            // cout << endl;
        }
    }
    // for(int i = 0; i < dp.size(); i++) cout << dp[i] << " ";
    // cout << endl;
    
    // 3. カードを昇順に並べるのに必要な回数を計算し, 出力.
    int ans = N - dp.size();
    cout << ans << endl;
    return 0;
    
}

// 解き直し.

// AtCoder Beginner Contest 006 解説.

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

#include <bits/stdc++.h>

using namespace std;

const int MAX = 3e4 + 1;

int main() {

// 1. 入力情報取得.

int N;

cin >> N;

vector<int> c(N);

vector<int> dp;

for(int i = 0; i < N; i++) cin >> c[i];

// 2. 解説通り.

// -> LIS で解く必要があるとのこと.

dp.push_back(c[0]);

for(int i = 1; i < N; i++){

// 2-1. dpテーブル末尾の要素(last) より大きな値(c[i])であれば, dpテーブルに追加.

int last = dp.back();

if(last < c[i]) dp.push_back(c[i]);

// 2-2. dpテーブル末尾の要素(last) より小さな値(c[i])であれば,

// dpテーブル上の更新場所を探索後, dpテーブルを更新.

if(last > c[i]){

auto it = lower_bound(dp.begin(), dp.end(), c[i]);

int dist = it - dp.begin();

dp[dist] = c[i];

// for(int i = 0; i < dp.size(); i++) cout << dp[i] << " ";

// cout << endl;

}

// for(int i = 0; i < dp.size(); i++) cout << dp[i] << " ";

// cout << endl;

// 3. カードを昇順に並べるのに必要な回数を計算し, 出力.

int ans = N - dp.size();

cout << ans << endl;

return 0;

}

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

[出力例(debug版)]
1 2 5 
1 2 4 
1 2 4 6 
2
※AtCoderテストケースより

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

[出力例(debug版)]
1 2 3 
1 2 3 6 
1 2 3 4 
1 2 3 4 7 
3

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

[出力例(debug版)]
1 2 
1 2 3 
1 2 3 4 
1 2 3 4 5 
1 2 3 4 5 6 8 
1 2 3 4 5 6 8 
5

実際, 
1 9  2 12 3  7  4 11  5  6 10  8 
↓
↓(1回目)
↓
1 2 12  3 7  4 11  5  6 10  8  9
↓
↓(2回目)
↓
1 2  3  7 4 11  5  6 10  8  9 12
↓
↓(3回目)
↓
1 2  3  7 4  5  6 10  8  9 11 12
↓
↓(4回目)
↓
1 2  3  7 4  5  6  8  9 10 11 12
↓
↓(5回目)
↓
1 2  3  4 5  6  7  8  9 10 11 12
の 5回 と分かる.

[入力例]

[出力例(debug版)]

1 2 5

1 2 4

1 2 4 6

※AtCoderテストケースより

[入力例]

[出力例(debug版)]

1 2 3

1 2 3 6

1 2 3 4

1 2 3 4 7

[入力例]

[出力例(debug版)]

1 2

1 2 3

1 2 3 4

1 2 3 4 5

1 2 3 4 5 6 8

実際,

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

↓

↓(1回目)

↓

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

↓

↓(2回目)

↓

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

↓

↓(3回目)

↓

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

↓

↓(4回目)

↓

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

↓

↓(5回目)

↓

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

の 5回と分かる.

■参照サイト
AtCoder Beginner Contest 006

2019年6月16日

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

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

■感想.
1. 数え上げについて, 解答方針が全く見えなかったので, 解説を丸写しする感覚で解き直しした.
2. 数え上げに必要なライブラリが, 正常に動作していることの確認も出来たので良かったと思う.

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

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

// ABC 110解説
// https://img.atcoder.jp/abc110/editorial.pdf
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const LL MOD = 1e9 + 7;
const LL MAX = 123456;
LL F[MAX];
LL IF[MAX];

// Efficient program to print all prime factors of a given number
// https://www.geeksforgeeks.org/print-all-prime-factors-of-a-given-number/
// 与えられた正整数についての素因数分解を計算.
// @param X: 素因数分解を行う整数.
// @return ret: 素因数分解 の 結果 を 返却.
map<LL, LL> div(LL X) {
    
    // 1. X を 2で割り切れなくなるまで割っていく.
    map<LL, LL> ret;
    while(X % 2 == 0) ret[2]++, X >>= 1;
    
    // 2. X を 3以上の奇数で, 割り切れなくなるまで順次割っていく.
    for(LL i = 3; i <= sqrt(X); i += 2){
        while(X % i == 0){
            ret[i]++;
            X /= i;
        }
    }
    
    // 3. X が 2 より 大きな素数であれば, 追加.
    if(X > 2) ret[X]++;
    
    // 4. 出力.
    return ret;
}

// Fermat's little theorem を 適用するため, ap-2乗 などを計算できるようにする.
// @param a: べき乗したい正整数.
// @param b: 指数.
// @return: べき乗した計算結果(mod版).
LL inverse(LL a, LL b){
    LL t = 1;
    while(b) {
        if(b & 1) t = (t * a) % MOD;
        a *= a;
        a %= MOD;
        b >>= 1;
    }
    return t % MOD;
}

// 配列 IF に, 逆元を保存.
// @param: 特に無し.
// @return: 配列IF の update.
void initialize(){
    F[0] = 1, IF[0] = 1;
    for(LL i = 1; i < MAX; i++){
        F[i] = (F[i - 1] * i) % MOD;
        //逆元を、フェルマーの小定理を利用して求める
        IF[i] = inverse(F[i], MOD - 2) % MOD;
    }
}

// 組み合わせ(nCk)計算用(mod版).
// ※配列F, IF は, 事前に計算済のものを使う.
// @param n: 対象となる要素の個数.
// @param k: 選択する要素の個数.
// @return: 組み合わせ(nCk)の計算結果.
LL combination(LL n, LL k){
    if(n < 0 || k < 0 || k > n) return 0;
    LL ret = F[n] * IF[k] % MOD * IF[n - k] % MOD;
    return ret;
}

int main() {

    // 1. 入力情報取得.
    LL N, M;
    cin >> N >> M;
    initialize();
    
    // 2. 素因数分解.
    map<LL, LL> m = div(M);
    // for(auto &p : m) cout << "p.first=" << p.first << " p.second=" << p.second << endl;
    
    // 3. 場合の数をカウント.
    // -> 解説通り.
    LL ans = 1;
    for(auto &p : m) ans *= combination(p.second + N - 1, p.second), ans %= MOD;
    
    // 4. 出力 ～ 後処理.
    cout << ans << endl;
    return 0;

}

// ABC 110解説

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

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

const LL MOD = 1e9 + 7;

const LL MAX = 123456;

LL F[MAX];

LL IF[MAX];

// Efficient program to print all prime factors of a given number

// https://www.geeksforgeeks.org/print-all-prime-factors-of-a-given-number/

// 与えられた正整数についての素因数分解を計算.

// @param X: 素因数分解を行う整数.

// @return ret: 素因数分解の結果を返却.

map<LL, LL> div(LL X) {

// 1. X を 2で割り切れなくなるまで割っていく.

map<LL, LL> ret;

while(X % 2 == 0) ret[2]++, X >>= 1;

// 2. X を 3以上の奇数で, 割り切れなくなるまで順次割っていく.

for(LL i = 3; i <= sqrt(X); i += 2){

while(X % i == 0){

ret[i]++;

X /= i;

}

// 3. X が 2 より大きな素数であれば, 追加.

if(X > 2) ret[X]++;

// 4. 出力.

return ret;

}

// Fermat's little theorem を適用するため, ap-2乗などを計算できるようにする.

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

// @param b: 指数.

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

LL inverse(LL a, LL b){

LL t = 1;

while(b) {

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

a *= a;

a %= MOD;

b >>= 1;

}

return t % MOD;

}

// 配列 IF に, 逆元を保存.

// @param: 特に無し.

// @return: 配列IF の update.

void initialize(){

F[0] = 1, IF[0] = 1;

for(LL i = 1; i < MAX; i++){

F[i] = (F[i - 1] * i) % MOD;

//逆元を、フェルマーの小定理を利用して求める

IF[i] = inverse(F[i], MOD - 2) % MOD;

}

// 組み合わせ(nCk)計算用(mod版).

// ※配列F, IF は, 事前に計算済のものを使う.

// @param n: 対象となる要素の個数.

// @param k: 選択する要素の個数.

// @return: 組み合わせ(nCk)の計算結果.

LL combination(LL n, LL k){

if(n < 0 || k < 0 || k > n) return 0;

LL ret = F[n] * IF[k] % MOD * IF[n - k] % MOD;

return ret;

}

int main() {

// 1. 入力情報取得.

LL N, M;

cin >> N >> M;

initialize();

// 2. 素因数分解.

map<LL, LL> m = div(M);

// for(auto &p : m) cout << "p.first=" << p.first << " p.second=" << p.second << endl;

// 3. 場合の数をカウント.

// -> 解説通り.

LL ans = 1;

for(auto &p : m) ans *= combination(p.second + N - 1, p.second), ans %= MOD;

// 4. 出力～後処理.

cout << ans << endl;

return 0;

}

■参照サイト
AtCoder Beginner Contest 110

月: 2019年6月

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

C++の練習を兼ねて, AtCoder Beginner Contest 049 の問題D (D – 連結 / Connectivity) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 002 の問題D (D – 派閥) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 132 の問題D (D – Blue and Red Balls) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 035 の問題B (B – ドローン) ～問題C (C – オセロ) を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 006 の問題C (C – 積み重ね) を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 005 の問題C (C – 器物損壊！高橋君) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 088 の問題D (D – Grid Repainting) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 023 の問題D (D – 射撃王) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 006 の問題D (D – トランプ挿入ソート) を解いてみた.

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

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

C++の練習を兼ねて, AtCoder Beginner Contest 049 の 問題D (D – 連結 / Connectivity) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 002 の 問題D (D – 派閥) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 132 の 問題D (D – Blue and Red Balls) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 035 の 問題B (B – ドローン) ～ 問題C (C – オセロ) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 006 の 問題C (C – 積み重ね) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 005 の 問題C (C – 器物損壊！高橋君) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 088 の 問題D (D – Grid Repainting) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 023 の 問題D (D – 射撃王) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 006 の 問題D (D – トランプ挿入ソート) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 049 の問題D (D – 連結 / Connectivity) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 002 の問題D (D – 派閥) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 132 の問題D (D – Blue and Red Balls) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 035 の問題B (B – ドローン) ～問題C (C – オセロ) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 006 の問題C (C – 積み重ね) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 005 の問題C (C – 器物損壊！高橋君) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 088 の問題D (D – Grid Repainting) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 023 の問題D (D – 射撃王) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 006 の問題D (D – トランプ挿入ソート) を解いてみた.

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