この解説では、

• A 問題「2nd Greatest Distance」の TLE 解法
• A 問題「2nd Greatest Distance」の正しくない方針
• A 問題「2nd Greatest Distance」の AC 解法
• サンプルコード

の 4 つを紹介します。

1. 解法1(実行速度が遅いTLE解法)

全ての家同士の距離を求め、実際に降順に並び替えることを考えてみましょう。 家 \(i,j\) 間の距離 \(\max(|x_i - x_j|, |y_i - y_j|)\) は \(O(1)\) で求められます。 \(\frac{N(N-1)}{2}\) 個の家の距離を求め並び替えるのは \(O(N^2 \log N)\) で実行できます。 残念ながら、このアルゴリズムは低速で正解することは難しいです。

2. 正しくない方針

全ての家同士の距離を実際に求めることは難しいということがわかりました。 そこで、距離が \(x\) 座標の差、\(y\) 座標の差のうち大きい方であるという性質を活用することを考えてみましょう。 以下の \(4\) つを求め、そのうち \(2\) 番目に大きい値を出力することを考えてみます。

• \(x\) 座標の差の最大値
• \(y\) 座標の差の最大値
• \(x\) 座標の差の \(2\) 番目に大きい値
• \(y\) 座標の差の \(2\) 番目に大きい値

\(x,y\) 座標の差の最大値は容易に求められます。\(x\) 座標の差の \(2\) 番目に大きい値というのは以下のどちらかです。(\(y\) 座標も同様です)

• \(2\) 番目に大きい値から最小値を引いた値
• 最大値から \(2\) 番目に小さい値を引いた値

以上のアルゴリズムは残念ながら不正解となってしまいます。これは同じ家の組に関する値が \(2\) つ含まれる可能性があるためです。

3. 解法3(想定解法)

先程の方針は同じ家の組に関する値が \(2\) つ含まれる可能性があることが問題でした。そこで、上記の \(4\) つの値に出現しうる家のみを候補として、全ての家同士の距離を求めることにしましょう。 現れうる家は高々 \(8\) 軒なので、全ての家同士の距離を求めることができます。これは適切に実装した場合 \(O(N)\) となり十分高速です。

4. サンプルコード(C++)

#include <algorithm>
#include <iostream>
#include <vector>
#include <set>
using ll = long long;
using namespace std;

const char EOLN = '\n';

int n;
vector<vector<int>> a;
set<int> ids;
int main()
{
  cin >> n;
  for (int i = 0; i < n; i++)
  {
    int x, y;
    cin >> x >> y;
    a.emplace_back(vector<int>{x, y, i});
  }
  for (int k = 0; k < 2; k++)
  {
    sort(a.begin(), a.end());
    for (int i = 0; i < 2; i++)
    {
      ids.emplace(a[i][2]);
      ids.emplace(a[n - 1 - i][2]);
    }
    for (auto &v : a)
      swap(v[0], v[1]);
  }

  vector<pair<int, int>> b;
  for (auto v : a)
    if (ids.count(v[2]) != 0)
      b.emplace_back(v[0], v[1]);
  vector<ll> d;
  for (int i = 0; i < b.size(); i++)
    for (int j = i + 1; j < b.size(); j++)
      d.emplace_back(max(abs(b[i].first - b[j].first), abs(b[i].second - b[j].second)));
  sort(d.begin(), d.end());
  cout << d[d.size() - 2] << endl;
  return 0;
}