[AOJ] No. 0299 鉄道路線II

2019年12月31日2020年12月17日

問題

方針

買い物をする駅の番号の順番を変えても影響がないので、\( d_i \) を昇順に整列させます。ここで、\( d_i < p \) を満たす最大の \( d_i \) を \( l \) とし、\( d_i > p \) を満たす最小の \( d_i \) を \( r \) とします。\( d_i = p\) を満たす \( i \) が存在しないことに注意します。ここで、\( L(s, g) \) を 左回りで 駅 \( s \) から 駅\( g \) まで行く時のコストとして、\( R(s, g)\) を右回りで 駅 \( s \) から 駅\( g \) まで行く時のコストとします。このとき、

\[\begin{eqnarray}
L(s, g) &=& \begin{cases} 100(s – g) & ( g \leq s ) \\ 100(N – (g – s)) & ( g > s ) \end{cases}\\
R(s, g) &=& \begin{cases} 100(N – (s – g)) & ( g \leq s ) \\ 100(g – s) & ( g > s ) \end{cases}
\end{eqnarray}\]

となります。最適な駅の周り方は、方向を転換して回るのが少なくとも \( 1 \) 回だけなので、全探索を行います。

全て同じ方向に進むとき

全て左回りで行動するときの最小のコストは、\( L(p, r) \) となり、全て右回りで行動するときの最小のコストは \( R(p, l) \) となります。

駅 \( d_i \) まで左回りに進んだ後、右回りで進む

\( i = 0 \) のとき

このときの最小のコストは、\( 2L(p, d_0) + R(p, d_{M – 1}) \) となります。

\( i \neq 0 \) のとき

このときの最小のコストは、\( 2L(p, d_i) + R(p, d_{i – 1}) \) となります。

駅 \( d_i \) まで右回りに進んだ後、右回りで進む

\( i = M – 1\) のとき

このときの最小のコストは、\( 2R(p, d_i) + R(p, d_{0}) \) となります。

\( i \neq M – 1 \) のとき

このときの最小のコストは、\( 2R(p, d_i) + R(p, d_{i + 1}) \) となります。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int N, M, p;

int left(int s, int g) {
    if (g <= s) {
        return 100 * (s - g);
    } else {
        return 100 * (N - (g - s));
    }
}

int right(int s, int g) {
    if (g <= s) {
        return 100 * (N - (s - g));
    } else {
        return 100 * (g - s);
    }
}
int main() {
    
    cin >> N >> M >> p;
    vector<int> d(M);
    for (int i = 0; i < M; i++) {
        cin >> d[i];
    }
    sort(d.begin(), d.end());
    int l = -1;
    int r = -1;

    int kl = 200 * N;
    int kr = 200 * N;
    int idx = -1;
    for (int i = 0; i < M; i++) {
        if (kl > left(p, d[i])) {
            kl = left(p, d[i]);
            l = d[i];
        }
        if (kr > right(p, d[i])) {
            kr = right(p, d[i]);
            r = d[i];
        }
    }
    //cout << l << " " << r << "\n";
    int ans = min(left(p, r), right(p, l)); // 全て左回りまたは右回り
    for (int i = 0; i < M; i++) {
        int t1; // d[i]<-p d[i]->p p->d[i-1]
        if (i == 0) {
            t1 = 2 * left(p, d[i]) + right(p, d[M - 1]);
        } else {
            t1 = 2 * left(p, d[i]) + right(p, d[i - 1]);
        }
        int t2;
        if (i == M - 1) {
            t2 = 2 * right(p, d[i]) + left(p, d[0]);
        } else {
            t2 = 2 * right(p, d[i]) + left(p, d[i + 1]);
        }
        ans = min(ans, min(t1, t2));
    }
    cout << ans << "\n";
    return 0;
}