srupのメモ帳

競プロで解いた問題や勉強したことを記録していくメモ帳

Codeforces 363 Div2 A. Launch of Collider

問題

問題概要

粒子の数字(座標)とそれに対応するLRのどちらかが与えられる。Lの場合、その座標から左に動かすことができ、Rの場合、その座標から右に動かすことができる。粒子が1秒で1マス分、指定された 方向に動くことができる。最短何秒でぶつかるか。またはぶつかることがないか。

解法

小さな座標から大きな座標の方向へ、隣どおしの粒子を確認していく。左の粒子がRで右の粒子がLの時、粒子どおしがぶつかる。その中で、最短のものを求とめ、もし、一度も粒子がぶつかることがなければ、-1を出力すればいい。
私の回答だと、隣どおししか確認していないから、ダメなきがしたけど、実験したら、よさそう。

ミス

特になし。

コード

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <cstring>
using namespace std;
typedef vector<int> vint;
#define rep(i,n) for(int i=0;i<(n);i++)

int main(void){
    int n; scanf("%d", &n);
    string s; cin >> s;
    vint v(n);
    rep(i, n) scanf("%d", &v[i]);
    int ans = 1e9;
    for (int i = 0; i < n - 1; ++i){
        if(s[i] == 'R' && s[i + 1] == 'L'){
            ans = min(ans, (v[i + 1] - v[i]) / 2);
        }
    }
    if(ans == 1e9)printf("-1\n");
    else printf("%d\n", ans);
    return 0;
}