AOJ0563 Walking Santa(歩くサンタクロース)

またしてもサンタです。
この問題は非典型寄りで自分の考察に場合分けが多かったので、解説が長くなってしまいました。

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0563
N個の家が整数座標に位置している。
サンタは、このN個の家全てにチョコレートケーキを届けたい。
トナカイを使ってケーキを傷付けてしまう危険を減らしたいので、どこかの整数座標に降り立ってからサンタが歩いて届けることにした。
しかしサンタは一度に1つのチョコレートしか運ぶことが出来ない。
最適な場所を選んで降り立ったとき、サンタが全ての家にチョコレートケーキを届けるのに必要な最小の時間と、降り立つべき場所を出力せよ。

解法

まずマンハッタン距離はx成分+y成分なので、簡単にx方向とy方向に分けて考えることが出来るという重要な特徴があります。
この問題も、x座標とy座標を分け、それぞれで1次元上での同じ問題を解く方針で勝てます。

1次元に落とし込めたので、サンタがどこに降りるのが最適か考えていきます。

まず邪魔をしてくるやつがいます。
基本往復なのに最後の家だけ往復しなくてよいという制約です。
なるべく単純な問題にしたいので、この条件を無くしたいです。
そこで、最後の家以外は2個存在することにします。
すると、「サンタの降りた場所と各家との距離の総和を最小化する」という問題に帰着できます。

まずは最後の家云々を無視して、各家との距離の総和を最小化する単純な問題だけを考えます。

家が2つあるとします。
このとき、サンタは2つの家の間ならばどこに降りても最適です。
(「間」はちょうど家の上も含むとします。)
両側に1つずつ増やしてみましょう。
内側のペアと外側のペアをつくるというふうに考えると、ペアの間のどこに降りてもその2つの家との距離の総和は変わらないので、内側のペアの間ならどこに降りても最適だと分かります。
更に2個ずつ増やしていっても同じことが言えます。

(黒丸にすればよかった)
つまり、家の数が偶数のときは、一番内側の2つの家の間が最適です。

奇数の時はどうなるかというと、ペアを作ったときに仲間はずれが出てしまいます。
偶数個の家については最適な降り方が分かっているので、偶数に1つ付け足すと考えます。
すると、付け足す家の場所はサンタの降りる場所(一番内側の2つの家の間のどこか)と同じであるときが最適です。

つまり、奇数個の家があるときは、ちょうど真ん中の家の上に降りるのが最適だと分かります(そうすれば残りの偶数個についても最適になるから)。

では元の問題に戻って、最後の家だけ1個である、というルールについて考えましょう。
最後の家は自由に選べるので、2N個の家から1つだけ家を取り除けるということです。
まず家が2N個のときはこれまで通り、一番内側の家の間(Nが奇数のときその2つの家は同じ場所にある)に降りるのが最適です。

この状態から任意の家を取り除いたときにどうなるかというと、元は1番内側だった2つの家のどちらかに降りるのが最適になります。たかだか1個取り除いたくらいではちょっとしかずれません。

つまり、最適になる可能性があるのは、サンタが2N個の家の内側2つの家のどちらかに降りたときだけです。

x方向、y方向でそれぞれ2つずつ最適解の候補があるので全部でたかだか4つしか候補がありません。
(Nが奇数の時は一意に定まりますが、実装を楽にするために偶数と同じ処理方法にしました。)
あとは4つを全部試してしまうのが楽です。
このときどの家を取り除いたらいいかですが、これは簡単で、2次元平面で考えたとき降りる場所からマンハッタン距離で最も遠い家を取り除けばいいです。

計算量はソートが一番大きくなるので、全体の計算量もです。

コード

using namespace std;

typedef long long ll;

#define int long long

const int dx[2] = { 0, 1 }, dy[2] = { 0, 1 };

int W, H, N, X[100000], Y[100000];
int X_[100000], Y_[100000];

int Calculate(int x, int y)
{
    int res = 0;
    int ma = 0;
    for (int i = 0; i < N; i++)
    {
        ma = max(ma, abs(x - X[i]) + abs(y - Y[i]));
        res += 2 * (abs(x - X[i]) + abs(y - Y[i]));
    }
    return res - ma;
}

signed main()
{
    cin >> W >> H >> N;
    for (int i = 0; i < N; i++)
    {
        cin >> X[i] >> Y[i];
        X_[i] = X[i]; Y_[i] = Y[i];
    }
    sort(X_, X_ + N);
    sort(Y_, Y_ + N);
    int idX = (N - 1) / 2, idY = (N - 1) / 2;
    int ansX, ansY, mi = LLONG_MAX / 2;
    for (int i = 0; i < 2; i++)
    {
        for (int j = 0; j < 2; j++)
        {
            int cost = Calculate(X_[idX + dx[i]], Y_[idY + dy[j]]);
            if (mi > cost)
            {
                mi = cost;
                ansX = X_[idX + dx[i]]; ansY = Y_[idY + dy[j]];
            }
        }
    }
    printf("%lld\n%lld %lld\n", mi, ansX, ansY);
    return 0;
}