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

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

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

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

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