はまやんはまやんはまやん

hamayanhamayan's blog

鉄道路線II [パソコン甲子園2014 予選 E]

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0299?year=2014

考察過程

0. (似たような問題を今まで見たことありすぎて考察過程になってるか分からん)
1. 最適戦略を考えよう
2. 引き返す回数は最大1回でいいし、店に行く途中で引き返すことは無い
3. 全探索する対象を考える
4. 左側でi個の店に行ったら、右側ではN-i個の店に寄ればいい
5. 左から右と右から左のどっちとも試す
6. 全探索は前計算しておけば高速になって間に合いそう

解法

https://onlinejudge.u-aizu.ac.jp/status/users/hamayanhamayan/submissions/1/0299/judge/3156160/C++14

migi[i] := 出発する駅pから右にi個の店に行くまでにかかる費用
hidari[i] := 出発する駅pから左にi個の店に行くまでにかかる費用
これを前計算しておこう。
 
配列hidariの作り方を少し細かく説明しておく。
元の配列DにPを追加してM+1要素の配列にしておく。
このときのPの添字をstとする。
i=1のときは、左に1つ移動するのでst-1が左端になる。
i=2のときは、左に2つ移動するのでst-2が左端になる。
この左端の添字は負の数になる可能性があるので、循環を考えて、st-i+M+1とする。
これではst-iが正の数だった場合はM+1以上になるので、(st-i+M+1)%(M+1)とすると、正しい添字になる。
あとは、差分を取るが、差分も負の数になるかもしれないので、+Nをして、%Nをする。
これで距離がとれたので×100すると費用が求まる。
 
あとは答えを全探索する。
左でi個店に寄る場合は「P -> 左にi番目の店 -> P -> 右にM-i番目の店」のように左の方は往復するので、
hidari[i]*2+migi[M-i]が必要な費用となる。
これの最小を取れば答え(右→左の場合もやる)。

int N, M, P, D[10101];
int hidari[10101], migi[10101];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M >> P;
    rep(i, 0, M) cin >> D[i];
    D[M] = P;
    sort(D, D + M + 1);

    int st = 0;
    rep(i, 0, M + 1) if (D[i] == P) st = i;

    rep(i, 1, M + 1) hidari[i] = ((D[st] - D[(st - i + M + 1) % (M + 1)] + N) % N) * 100;
    rep(i, 1, M + 1) migi[i] = ((D[(st + i) % (M + 1)] - D[st] + N) % N) * 100;

    int ans = inf;
    rep(i, 0, M + 1) chmin(ans, hidari[i] * 2 + migi[M - i]);
    rep(i, 0, M + 1) chmin(ans, migi[i] * 2 + hidari[M - i]);
    cout << ans << endl;
}