Lilliput Steps

小さな一歩から着実に. 数学やプログラミングのことを書きます.

ABC 130F : Minimum Bounding Box

問題文：https://atcoder.jp/contests/abc130/tasks/abc130_f

概要

日本語なので略。

解法

x_{\rm{min}, \rm{L}} を 動く方向が L の点の x座標の最小値とする。他の方向についても同様とする。
すると、時刻 t での x 座標の最小値 x_{\rm{min}} (t) は、

x_{{\rm min}}(t) = {\rm min}( {\rm min}(x_{{\rm min}, {\rm D}}, x_{{\rm min}, {\rm U}}), x_{{\rm min}, {\rm R}} + t, x_{{\rm min}, {\rm L}} - t)

と書ける。
他の座標も同様の形で書き下すことができる。上記より、時刻 t での題意の値
(x_{\rm max}(t) - x_{\rm min}(t)) \times (y_{\rm max}(t) - y_{\rm min}(t))

は、(各時刻における x_{\rm min}(t)の値は \rm{O}(1)時間で計算できるので、)すべての tについてこれらの値を求めればその最小値を求めることで解を得られる。しかし tの候補は無限にあるため、候補となる tを絞り効率的に答えを求める必要がある。
(x_{\rm max}(t) - x_{\rm min}(t)) \times (y_{\rm max}(t) - y_{\rm min}(t)) は、非負整数 a_1, a_2, b_1, b_2および p_1, p_2, p_3, p_4 \in \{-1, 0, 1\}を用いて

(x_{\rm max}(t) - x_{\rm min}(t)) \times (y_{\rm max}(t) - y_{\rm min}(t)) = (a_1 + p_1 t - a_2 + p_2 t)(b_1 + p_3 t - b_2 + p_4 t)

と書けることに注意する。
2つの項の tの係数は常に -2から 2のいずれかになる。これらの符号が共に負のときは tはできるだけ大きいほうがよい。ともに正のときはできるだけ小さいほうが良い．符号が違うときは上に凸な2次関数となるため、極大値をとる点から離れるほど関数値が小さくなる。したがって、値 (x_{\rm max}(t) - x_{\rm min}(t)) \times (y_{\rm max}(t) - y_{\rm min}(t))は、関数形が一意に定まる区間ではその端点で最小値をとる。
よって、 x_{\rm max}(t)などの関数形が変化する点のみで値 (x_{\rm max}(t) - x_{\rm min}(t)) \times (y_{\rm max}(t) - y_{\rm min}(t))を計算すれば良い。このような点は定数個しかないため、 x_{\rm{min}, \rm{L}} などをもとめるところがボトルネックになる。時間計算量は \mathrm{O}(N)となる。

コード
#include <bits/stdc++.h>

using namespace std;

typedef long long Int;

const Int INF = 2000000000ll;

Int x_min[128], y_min[128], x_max[128], y_max[128];

double f(double t)
{
  if (t < 0) return 1e18;
  double x_ma = max({(double)max(x_max['U'], x_max['D']), x_max['R'] + t, x_max['L'] - t});
  double x_mi = min({(double)min(x_min['U'], x_min['D']), x_min['R'] + t, x_min['L'] - t});
  double y_ma = max({(double)max(y_max['L'], y_max['R']), y_max['U'] + t, y_max['D'] - t});
  double y_mi = min({(double)min(y_min['L'], y_min['R']), y_min['U'] + t, y_min['D'] - t});
  return (x_ma - x_mi) * (y_ma - y_mi);
}

int main()
{
  int N;
  
  scanf("%d", &N);
  
  for (int i = 0; i < 128; i++) {
	x_min[i] = y_min[i] = INF;
    x_max[i] = y_max[i] = -INF;
  }
  
  for (int i = 0; i < N; i++) {
    Int x, y;
    char s[2];
    scanf("%lld %lld %s", &x, &y, s);
    
    char c = s[0];
    x_min[c] = min(x_min[c], x);
    x_max[c] = max(x_max[c], x);
    y_min[c] = min(y_min[c], y);
    y_max[c] = max(y_max[c], y);
  }
  
  vector<double> cand;
  cand.push_back(0);
  cand.push_back(x_max['L'] - max(x_max['U'], x_max['D']));
  cand.push_back((x_max['L'] - x_max['R']) * 0.5);
  cand.push_back(max(x_max['U'], x_max['D']) - x_max['R']);
  
  cand.push_back(x_min['L'] - min(x_min['U'], x_min['D']));
  cand.push_back((x_min['L'] - x_min['R']) * 0.5);
  cand.push_back(min(x_min['U'], x_min['D']) - x_min['R']);
  
  cand.push_back(y_max['D'] - max(y_max['L'], y_max['R']));
  cand.push_back((y_max['D'] - y_max['U']) * 0.5);
  cand.push_back(max(y_max['L'], y_max['R']) - y_max['U']);
  
  cand.push_back(y_min['D'] - min(y_min['L'], y_min['R']));
  cand.push_back((y_min['D'] - y_min['U']) * 0.5);
  cand.push_back(min(y_min['L'], y_min['R']) - y_min['U']);
  
  double ans = 1e18;
  for (int i = 0; i < cand.size(); i++) {
    ans = min(ans, f(cand[i]));
  }
  
  printf("%.10lf\n", ans);
  return 0;
}
コメント

実装が偉いことになったんですが、どうやったら綺麗に実装できるんでしょうか……。
それと特にジャンルも決めずに問題を解いているので、何かオススメの問題がありましたらこの記事のコメントや Twitter のリプライで連絡していただけると嬉しいです。