TopCoder SRM613: TaroFriends

ある２匹の猫が互いに背を向けている場合、両方の猫の向きを直して、向かい合わせることで必ず移動後の位置の差が小さくなる。

つまり任意の猫のペアが向かい合っているような初期状態だけを考えればよく、そのような状態は |coordinates|+1 通りしかないのでそれらを全て試す。

public class TaroFriends {
    public int getNumber(int[] coordinates, int X) {
        int ans = int.MaxValue;
        Array.Sort(coordinates);
        for (int i = 0; i <= coordinates.Length; i++) {
            var front = coordinates.Take(i).Select(p => p + X);
            var back = coordinates.Skip(i).Select(p => p - X);
            var moved = front.Concat(back);
            ans = Math.Min(ans, moved.Max() - moved.Min());
        }
        return ans;
    }
}