ABC107-C：Candles(300)

問題

https://beta.atcoder.jp/contests/abc107/tasks/arc101_a

数直線上に N つの点が与えられる。今地点 0 にいる。数直線上の点から K 個選ぶとき、移動距離の最小値を求めよ。

考え方

(i)正負に分けて全探索
最短距離を動くときの点の選び方は正の方向から i の点を選び、負の方向から k - i を選ぶ。 i, k - i を全探索すれば良い。正と負で List を分けてしまうのが楽。正または負の方向から何もとらないというパターンがあるので 0 を add しておく必要がある。

       public void solve(int testNumber, InputReader in, PrintWriter out) {

            int n = in.nextInt(), k = in.nextInt();
            List<Long> plus = new ArrayList<>();
            List<Long> minus = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                long x = in.nextLong();
                if (x < 0) {
                    minus.add(-x);
                } else if (x == 0) {
                    k--;
                } else if (x > 0) {
                    plus.add(x);
                }
            }
            plus.add(0L);
            minus.add(0L);

            Collections.sort(plus);
            Collections.sort(minus);

            long ans = LINF;
            for (int i = 0; i < plus.size(); i++) {
                int j = k - i;
                if (0 <= j && j < minus.size()) {
                    long min = min(plus.get(i), minus.get(k-i));
                    long max = max(plus.get(i), minus.get(k-i));

                    ans = min(ans, min*2 + max);
                }
            }

            for (int i = 0; i < minus.size(); i++) {
                int j = k - i;
                if (0 <= j && j < plus.size()) {
                    long min = min(minus.get(i), plus.get(k-i));
                    long max = max(minus.get(i), plus.get(k-i));

                    ans = min(ans, min*2 + max);
                }
            }

            out.println(ans);
        }

((ii)区間を全探索
最短距離を選ぶとき、選ぶ k つの点は連続している。よって k のとり方を全探索すれば良い。具体的には区間 [l, l+k-1] を全探索する。その時のパターンとしては

(A) (x[l] が負、) x[l+k-1] が負
⇒移動距離は負の方向の最大値なので x[l]

(B) x[l] が負、x[l+k-1] が正
⇒移動距離は負の方向と正の方向の合算。正または負の移動距離の小さい値で折り返す。

(C) x[l] が正 (、x[l+k-1] が正)
⇒移動距離は正の方向の最大値なので x[l+k-1]

という3パターンがありうる。

       public void solve(int testNumber, InputReader in, PrintWriter out) {

            int n = in.nextInt(), k = in.nextInt();
            long[] x = new long[n];

            for (int i = 0; i < n; i++) {
                long t = in.nextLong();
                x[i] = t;
            }

            long ans = LINF;
            for (int i = 0; i < n && i+k-1 < n; i++) {
                long tmp = 0;
                if (x[i+k-1] < 0) {
                    tmp = abs(x[i]);
                } else if (x[i] < 0 && x[i+k-1] >= 0) {
                    long min = min(abs(x[i]), abs(x[i+k-1]));
                    long max = max(abs(x[i]), abs(x[i+k-1]));
                    tmp = min*2 + max;
                } else if (x[i] >= 0) {
                    tmp = x[i+k-1];
                }
                ans = min(ans, tmp);
            }

            out.println(ans);

        }

ポイント

• 何を全探索するか
• 方針をちゃんと思考すること

類題

D - Static Sushi
⇒こちらのほうが難しいです。

雑記

これ本番中とけなかったの、なんでか未だによくわからない。多少実装面倒だけど、やるだけ問題・・・。