Linear world POJ2674

投稿日：2022/12/26 更新日:2022/12/26

問題

$N$ 人の人が長さ $L$ の数直線上に並んでいる。また、全ての人は速さ $V$ で進む。 $i$ 番目の人は名前は $\text{NAME}_i$ で位置 $\text{POS}_i$ から $\text{DIR}_i$ で示された方向へ進む。

人は他の人に出会うと、反対方向へ進みます。

最後に落ちる人の名前と時間をもとめてください。

解法

いくつかのステップに分けて考える。

1.最後に落ちる時間と方向

一旦名前を求めることを忘れる。出会った時、反対方向を向いて進むというのは有名問題「Ants」のようにすれ違ったとみなせばよい。従って、正の方向に進むひとなら、 $(L-POS)/V$ 時間、負の方向に進むひとなら $L/V$ 時間かかることになる。この中から最大の値が、求める時間となる。

2.最後に落ちるのは左右どちらか？

正の向きを $p$ 、負の向きを $n$ とする。

先ほど、求めた最大の時間が $(L-POS)/V$ の値、つまり正の向きに進む人であれば、最後に落ちるのは $p$ 側。反対に、 $POS/V$ の値であれば、 $n$ 側となる。

3.各人々は左右どちらから落ちるのか？

人が $A_1, A_2, A_3, ... A_N$ と並んでいる。実際はすれ違っているのではなく、ぶつかった瞬間からどちらも反対方向に進むためこの並びは変わらない。

各人々が $p$ に落ちる、 $n$ 側に落ちるとした時、必ず $n_1, n_2, ... n_i, p_{(i+1)}, ...p_N$ のように全ての $n$ は左に、全ての $p$ は右に集まる。なぜならば $p, n$ のようになると、右に進む人は左に進む人にぶつかり、右に落ちれないという不整合が生じるからである。

また、ぶつかればそれぞれの $p, n$ を交換しているだけなので、 $p$ と $n$ の数は変わらない。よって、 $n$ の数を $N_n$ とすると、前半 $N_n$ 人は $n$ 側から落ちる人、それ以外の後半は $p$ 側から落ちる人となる。

4.最後に落ちる人の名前を求める

2で最後に落ちるのが $n, p$ どちらかが判明しているので、 $p$ 側であれば3で求めた $p$ 側の人々のうち最も $L$ から離れている人。 $n$ 側であれば $n$ 側の人々のうち $0$ から最も離れている人となる。

実装

変数is_positiveで最後に落ちるのが $p$ 側か $n$ 側かを記録している。

出力のフォーマットに注意する。

#include <iostream>
#include <vector>
#include <string>
#include <math.h>
#include <algorithm>
using namespace std;

struct Person {
    char dir;
    double pos;
    string name;
};

void solve(int n){
    double l, v;
    cin >> l >> v;
    vector<Person> ps(n);
    for(int i = 0;i < n; ++i){
        cin >> ps[i].dir >> ps[i].pos >> ps[i].name;
        ps[i].dir = tolower(ps[i].dir);
    }

    double ans_time = -1;
    double is_positive;
    for(int i = 0;i < n; ++i){
        if(ps[i].dir == 'p'){
            double t = (l - ps[i].pos) / v;
            if(t > ans_time){
                ans_time = t;
                is_positive = true;
            }
        }else{
            double t = ps[i].pos / v;
            if(t > ans_time){
                ans_time = t;
                is_positive = false;
            }
        }
    }

    int cnt_p = 0, cnt_n = 0;
    for(int i = 0;i < n; ++i){
        if(ps[i].dir == 'p'){
            cnt_p++;
        }else{
            cnt_n++;
        }
    }

    int name_i;
    if(is_positive){
        name_i = n - cnt_p;
    }else{
        name_i = cnt_n-1;
    }

    printf("%13.2f %s\n", floor(ans_time*100)/100, ps[name_i].name.c_str());

}

int main(){
    ios::sync_with_stdio(false);
    std::cin.tie(0);
    int n;
    cin >> n;
    while(n != 0){
        solve(n);
        cin >> n;
    }
    return 0;
}