ferinの競プロ帳

競プロについてのメモ

Educational Codeforces Round 60 C. Magic Ship

問題ページ

解法

i日目に到達可能な場所がどのようになっているのか考える。(x1,y1)=(0,0)、s="UDRL"のときの例を以下に示す。 f:id:ferin_tech:20190219230025j:plain 風が吹く方向と逆方向に移動すればi日目で到達したマスはi+1日目以降でも到達可能なことがわかる。したがってi日目にはi以下の地点に移動することができる。1日経過するごとにひし形の中心が風の吹く方向に移動しひし形の大きさが1大きくなることがわかる。
i日目で到達したマスがi+1日目以降でも到達できることからゴールのマスにある日数で到達できるか?という判定問題には単調性が存在する。したがって二分探索を行うことができる。n日を1周としてX周したときに到達できるか?の判定はX周でひし形の中心が移動する位置とゴールのマンハッタン距離がn*X以下か?でO(1)で判定できる。何周でゴールに到達できるかを求めその周の何日目にゴールできるかを求めればよい。

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
// #define int ll
using PII = pair<ll, ll>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()

template<typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }

template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts) {
    return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type
fill_v(T &t, const V &v) { t=v; }
template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); }

template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a) {
    out<<'('<<a.first<<','<<a.second<<')'; return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a) {
    out<<'['; for(T i: a) {out<<i<<',';} out<<']'; return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL
const int INF = 1<<30;
const ll LLINF = 1LL<<60;
const ll MOD = 1000000007;

signed main(void) {
    cin.tie(0);
    ios::sync_with_stdio(false);

    ll sx, sy, gx, gy, n;
    string s;
    cin >> sx >> sy >> gx >> gy >> n >> s;
    gx -= sx; gy -= sy;

    ll turnx = 0, turny = 0;
    vector<ll> cx(n), cy(n);
    REP(i, n) {
        if(s[i] == 'U') cy[i] = 1, turny++;
        else if(s[i] == 'D') cy[i] = -1, turny--;
        else if(s[i] == 'R') cx[i] = 1, turnx++;
        else if(s[i] == 'L') cx[i] = -1, turnx--;
    }

    auto check = [&](ll mid) {
        ll x = turnx * mid, y = turny * mid, sz = n * mid;
        return abs(gx-x) + abs(gy-y) <= sz;
    };

    if(!check(1LL<<40)) {
        cout << -1 << endl;
        return 0;
    }

    ll lb = 0, ub = 1LL<<40;
    while(ub - lb > 1) {
        ll mid = (lb+ub)/2;
        if(check(mid)) ub = mid;
        else lb = mid;
    }

    ub--;
    ll x = ub * turnx, y = ub * turny, sz = ub * n;
    REP(i, n) {
        x += cx[i], y += cy[i], sz++;
        if(abs(gx-x) + abs(gy-y) <= sz) {
            cout << sz << endl;
            return 0;
        }
    }

    cout << -1 << endl;

    return 0;
}