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

C++の練習を兼ねて, 競プロ典型 90 問の問題045 (Simple Grouping) を解いてみた.

■感想.
1. 問題045は, 実装方針が見えなかったので, (問題045 (Simple Grouping) 解説プログラム) を参考に実装したところ, AC版に到達出来た.
2. 苦手な動的計画法(本問では, bit DP)の訓練を積めたので, 非常に良かったと思う.
3. ある集合に対する部分集合を網羅する形については, いったん, 実装パターンの一つとして, 覚えてしまおうと思う.
4. 手強い問題が非常に多い気もするけど, 時間を見つけて, 引き続き, 取り組んでいきたいと思う.

詳細は, 本家のサイト(GitHub) 競プロ典型 90 問の問題045 をご覧下さい.

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

// 解答不能.
// https://github.com/E869120/kyopro_educational_90/blob/main/sol/045.cpp
// 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 INF = 2020202020202020202;
LL x[16], y[16], dp[16][1 << 16], d[16][16], dGroup[1 << 16];

int main(){
    
    // 1. 入力情報.
    int N, K;
    scanf("%d %d", &N, &K);
    rep(i, N) scanf("%lld %lld", &x[i], &y[i]);
    
    // 2. 二点間の距離を保存.
    rep(a, N) repx(b, a + 1, N) d[a][b] = (x[a] - x[b]) * (x[a] - x[b]) + (y[a] - y[b]) * (y[a] - y[b]);
    
    // 3. グループに含まれる点の集合に関する二点間距離.
    rep(bit, 1 << N){
        rep(a, N){
            repx(b, a + 1, N){
                bool ok1 = bit & (1 << a);
                bool ok2 = bit & (1 << b);
                if(ok1 && ok2) dGroup[bit] = max(dGroup[bit], d[a][b]);
            }
        }
    }
    
    // 4. dp更新(解説通り).
    rep(i, 16) rep(bit, 1 << N) dp[i][bit] = INF;
    dp[0][0] = 0;
    repx(cnt, 1, K + 1){
        repx(bit, 1, 1 << N){
            // ex. 
            // bit = 5 の 場合.
            // (1回目) b = 5 は, b = bit (= 5) で 初期化した値が, 0 でないので, 処理開始.
            // (2回目) b = 4 は, (b - 1) & bit = (5 - 1) & 5 = 100 & 101 = 100 = 4 に, 更新され, 処理を継続.
            // (3回目) b = 1 は, (b - 1) & bit = (4 - 1) & 5 = 011 & 101 = 010 = 1 に, 更新され, 処理を継続.
            // (4回目) b = 0 は, (b - 1) & bit = (1 - 1) & 5 = 000 & 101 = 000 = 0 に, 更新され, b = 0 と
            //         なるため, 処理は行わず, 終了.
            // 
            // bit = 6 の 場合.
            // (1回目) b = 6 は, b = bit (= 6) で 初期化した値が, 0 でないので, 処理開始.
            // (2回目) b = 4 は, (b - 1) & bit = (6 - 1) & 6 = 101 & 110 = 100 = 4 に, 更新され, 処理を継続.
            // (3回目) b = 2 は, (b - 1) & bit = (4 - 1) & 6 = 011 & 110 = 010 = 2 に, 更新され, 処理を継続.
            // (4回目) b = 0 は, (b - 1) & bit = (2 - 1) & 6 = 001 & 110 = 000 = 0 に, 更新され, b = 0 と
            //         なるため, 処理は行わず, 終了.
            // 
            // bit の 部分集合 b を 列挙する場合, このような実装で, 列挙可能なので, 暗記すること.
            for(int b = bit; b != 0; b = (b - 1) & bit){
                dp[cnt][bit] = min(dp[cnt][bit], max(dp[cnt - 1][bit - b], dGroup[b]));
            }
        }
    }
    
    // 5. 出力.
    printf("%lld\n", dp[K][(1 << N) - 1]);
    return 0;
    
}

// 解答不能.

// https://github.com/E869120/kyopro_educational_90/blob/main/sol/045.cpp

// 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 INF = 2020202020202020202;

LL x[16], y[16], dp[16][1 << 16], d[16][16], dGroup[1 << 16];

int main(){

// 1. 入力情報.

int N, K;

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

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

// 2. 二点間の距離を保存.

rep(a, N) repx(b, a + 1, N) d[a][b] = (x[a] - x[b]) * (x[a] - x[b]) + (y[a] - y[b]) * (y[a] - y[b]);

// 3. グループに含まれる点の集合に関する二点間距離.

rep(bit, 1 << N){

rep(a, N){

repx(b, a + 1, N){

bool ok1 = bit & (1 << a);

bool ok2 = bit & (1 << b);

if(ok1 && ok2) dGroup[bit] = max(dGroup[bit], d[a][b]);

}

// 4. dp更新(解説通り).

rep(i, 16) rep(bit, 1 << N) dp[i][bit] = INF;

dp[0][0] = 0;

repx(cnt, 1, K + 1){

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

// ex.

// bit = 5 の場合.

// (1回目) b = 5 は, b = bit (= 5) で初期化した値が, 0 でないので, 処理開始.

// (2回目) b = 4 は, (b - 1) & bit = (5 - 1) & 5 = 100 & 101 = 100 = 4 に, 更新され, 処理を継続.

// (3回目) b = 1 は, (b - 1) & bit = (4 - 1) & 5 = 011 & 101 = 010 = 1 に, 更新され, 処理を継続.

// (4回目) b = 0 は, (b - 1) & bit = (1 - 1) & 5 = 000 & 101 = 000 = 0 に, 更新され, b = 0 と

// なるため, 処理は行わず, 終了.

// bit = 6 の場合.

// (1回目) b = 6 は, b = bit (= 6) で初期化した値が, 0 でないので, 処理開始.

// (2回目) b = 4 は, (b - 1) & bit = (6 - 1) & 6 = 101 & 110 = 100 = 4 に, 更新され, 処理を継続.

// (3回目) b = 2 は, (b - 1) & bit = (4 - 1) & 6 = 011 & 110 = 010 = 2 に, 更新され, 処理を継続.

// (4回目) b = 0 は, (b - 1) & bit = (2 - 1) & 6 = 001 & 110 = 000 = 0 に, 更新され, b = 0 と

// なるため, 処理は行わず, 終了.

// bit の部分集合 b を列挙する場合, このような実装で, 列挙可能なので, 暗記すること.

for(int b = bit; b != 0; b = (b - 1) & bit){

dp[cnt][bit] = min(dp[cnt][bit], max(dp[cnt - 1][bit - b], dGroup[b]));

}

// 5. 出力.

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

return 0;

}

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

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

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

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

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

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

[入力例]
3 2
0 0
500000000 500000000
1000000000 1000000000

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

[入力例]
6 3
8 17
19 0
3 11
17 2
7 9
7 8

[出力例]
25

[入力例]
15 7
9072 13350
8690 5307
10119 8053
12181 2151
13862 8198
15328 12448
201 7924
3290 3864
9639 8669
7166 13829
5017 15790
8567 6296
3668 3896
4102 5898
2976 9086

[出力例]
20211656

[入力例]

3 2

0 1

1 2

2 0

[出力例]

※AtCoderテストケースより

[入力例]

5 3

0 0

1 1

0 2

2 3

3 1

[出力例]

※AtCoderテストケースより

[入力例]

10 4

0 3

3 5

2 7

9 0

5 6

4 3

7 8

6 5

9 9

2 1

[出力例]

※AtCoderテストケースより

[入力例]

3 2

0 0

500000000 500000000

1000000000 1000000000

[出力例]

500000000000000000

※AtCoderテストケースより

[入力例]

6 3

8 17

19 0

3 11

17 2

7 9

7 8

[出力例]

[入力例]

15 7

9072 13350

8690 5307

10119 8053

12181 2151

13862 8198

15328 12448

201 7924

3290 3864

9639 8669

7166 13829

5017 15790

8567 6296

3668 3896

4102 5898

2976 9086

[出力例]

20211656

■参照サイト
045 – Simple Grouping
問題045 (Simple Grouping) 解説
 問題045 (Simple Grouping) 解説プログラム

C++の練習を兼ねて, 競プロ典型 90 問 の 問題045 (Simple Grouping) を解いてみた.

コメントを残す コメントをキャンセル

C++の練習を兼ねて, 競プロ典型 90 問の問題045 (Simple Grouping) を解いてみた.

コメントを残すコメントをキャンセル