2021-05-23

ARC119 E: Pancakes

問題解説 AtCoder

公式解説とは異なる方法で解きました。

解法

操作を一回もしないときの $\displaystyle{\sum_{i=1}^{N-1} |A _ i - A _ {i+1}|}$ の値を求めておき、 $S$ とします。

$l=1$ または $r=N$ のときの見栄えの悪さの値は、 $S$ との差分を考えることで合計 $O(N)$ で求めることができます。よって、 $1 \lt l \lt r \lt N$ のときの見栄えの悪さの最小値を計算すればよいです。

以下、 $r$ に $1$ を加え半開区間で扱うことにすると、見栄えの悪さは $S - |A _ {l - 1}-A _ l| - |A _ {r-1}-A _ r| + |A _ {l - 1}-A _ {r-1}| + |A _ l-A _ r|$ となり、 $|A _ {l - 1}-A _ {r-1}| + |A _ l-A _ r|$ は点 $(A _ {l - 1}, A_l)$ と点 $(A_{r-1}, A_r)$ のマンハッタン距離なので、以下の問題を解くことに帰着されます。

$N-1$ 個の点 $P_2, P_3, \cdots, P_N$ があり、点 $P_i$ の座標は $(x _ i,y _ i) = (A_{i-1}, A_i)$ である。また、点には重みがあり、点 $P_i$ の重み $w_i$ は $|A _ {i-1}-A_i|$ である。 $d(P,Q)$ で $2$ 点 $P, Q$ のマンハッタン距離を表すとき、 $2 \leq i \lt j \leq N$ に対する $S + d(P_i, P_j) - w_i - w_j$ の最小値を求めよ。

対称性より、 $2 \leq i \lt j \leq N$ という条件は $2 \leq i, j \leq N, i \neq j$ としてもよいです。点を $x$ 座標の昇順に番号を振り直し、 $y$ 座標の昇順に点を処理するします。点 $j$ を見ていて点 $i$ を今まで処理した点とするとき、点 $i$ の番号が点 $j$ より小さければ見栄えの悪さは $S + (-x_i - y_i - w_i) + (x_j + y_j - w_j)$ 、そうでなければ $S + (x_i - y_i - w_i) + (-x_j + y_j - w_j)$ となります。よって区間の最小値を計算できるセグメント木を二本用意し、それぞれ $-x_i-y_i-w_i$ と $x_i-y_i-w_i$ を点 $i$ の番号の位置に配置すると、各 $j$ についての処理を時間計算量 $O(\log N)$ で行うことができ、全体の時間計算量は $O(N \log N)$ となります。

実装

atcoder.jp

#include <bits/stdc++.h>
using namespace std;
const long long INF = 1000000000000000;
template <typename T>
struct segment_tree{
    int N;
    vector<T> ST;
    segment_tree(int n){
        N = 1;
        while (N < n){
            N *= 2;
        }
        ST = vector<T>(N * 2 - 1, INF);
    }
    void update(int k, T x){
        k += N - 1;
        ST[k] = x;
        while (k > 0){
            k = (k - 1) / 2;
            ST[k] = min(ST[k * 2 + 1], ST[k * 2 + 2]);
        }
    }
    T range_min(int L, int R, int i, int l, int r){
        if (R <= l || r <= L){
            return INF;
        } else if (L <= l && r <= R){
            return ST[i];
        } else {
            int m = (l + r) / 2;
            return min(range_min(L, R, i * 2 + 1, l, m), range_min(L, R, i * 2 + 2, m, r));
        }
    }
    T range_min(int L, int R){
        return range_min(L, R, 0, 0, N);
    }
};
int main(){
  int N;
  cin >> N;
  vector<int> A(N);
  for (int i = 0; i < N; i++){
    cin >> A[i];
  }
  long long S = 0;
  for (int i = 0; i < N - 1; i++){
    S += abs(A[i + 1] - A[i]);
  }
  long long ans = S;
  for (int i = 0; i < N - 1; i++){
    long long tmp = S - abs(A[i + 1] - A[i]) + abs(A[i + 1] - A[0]);
    ans = min(ans, tmp);
  }
  for (int i = 1; i < N; i++){
    long long tmp = S - abs(A[i] - A[i - 1]) + abs(A[N - 1] - A[i - 1]);
    ans = min(ans, tmp);
  }
  vector<long long> x(N - 1), y(N - 1), w(N - 1);
  for (int i = 0; i < N - 1; i++){
    x[i] = A[i];
    y[i] = A[i + 1];
    w[i] = abs(A[i + 1] - A[i]);
  }
  vector<pair<long long, int>> P(N - 1);
  for (int i = 0; i < N - 1; i++){
    P[i] = make_pair(x[i], i);
  }
  sort(P.begin(), P.end());
  vector<int> pos(N - 1);
  for (int i = 0; i < N - 1; i++){
    pos[i] = lower_bound(P.begin(), P.end(), make_pair(x[i], i)) - P.begin();
  }
  vector<pair<long long, int>> P2(N - 1);
  for (int i = 0; i < N - 1; i++){
    P2[i] = make_pair(y[i], i);
  }
  sort(P2.begin(), P2.end());
  vector<int> id(N - 1);
  for (int i = 0; i < N - 1; i++){
    id[i] = P2[i].second;
  }
  segment_tree<long long> ST1(N - 1), ST2(N - 1);
  for (int i : id){
    long long mn1 = ST1.range_min(0, pos[i]);
    ans = min(ans, S + mn1 + x[i] + y[i] - w[i]);
    long long mn2 = ST2.range_min(pos[i] + 1, N - 1);
    ans = min(ans, S + mn2 - x[i] + y[i] - w[i]);
    ST1.update(pos[i], -x[i] - y[i] - w[i]);
    ST2.update(pos[i], x[i] - y[i] - w[i]);
  }
  cout << ans << endl;
}

2021-05-20

AOJ 1352: Cornering at Poles

問題解説 AOJ

https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1352

問題概要

座標平面上に半径 $100$ の円形のロボットがあり、その中心を原点からある点に移動させたい。ただし、ロボットと重なってはならない点が $N$ 個指定される。ロボットの最短移動距離を求めよ。

解法

中心を移動させ、半径 $100$ の円形が障害物であると考えると、中心は以下の直線・円弧の組み合わせで表される経路を通るとすることができます。

始点からある円への接線
終点からある円への接線
二円の共通接線
ある円上のこれら三種類の接線の接点である二点の間の弧

よって、接線と接点をすべて列挙したあと、各円について接点を偏角の順に並べ隣接する二点の間の弧が他の円と交差していないか、つまり他の円に含まれる部分の弧と重なっているかを判定すればよいです。

候補となる点・直線・円弧をすべて求めたら、グラフを作りダイクストラ法を行うと最短路の長さが答えになります。

実装

#include <bits/stdc++.h>
using namespace std;
const double EPS = 0.0000001;
const double PI = acos(-1);
struct point{
  double x, y;
  point(){
  }
  point(double x, double y): x(x), y(y){
  }
  point operator +(point P){
    return point(x + P.x, y + P.y);
  }
  point operator -(point P){
    return point(x - P.x, y - P.y);
  }
  point operator *(double k){
    return point(x * k, y * k);
  }
  point operator /(double k){
    return point(x / k, y / k);
  }
};
point rotate90(point P){
  return point(-P.y, P.x);
}
double arg(point P){
  return atan2(P.y, P.x);
}
double abs(point P){
  return sqrt(P.x * P.x + P.y * P.y);
}
double dist(point P, point Q){
  return abs(Q - P);
}
double dot(point P, point Q){
  return P.x * Q.x + P.y * Q.y;
}
double cross(point P, point Q){
  return P.x * Q.y - P.y * Q.x;
}
struct line{
  point A, B;
  line(point A, point B): A(A), B(B){
  }
};
point vec(line L){
  return L.B - L.A;
}
double point_line_distance(point P, line L){
  return abs(cross(vec(L), P - L.A)) / abs(vec(L));
}
double point_segment_distance(point P, line L){
  if (dot(P - L.A, vec(L)) < 0){
    return dist(P, L.A);
  } else if (dot(P - L.B, vec(L)) > 0){
    return dist(P, L.B);
  } else {
    return point_line_distance(P, L);
  }
}
struct circle{
  point C;
  double r;
  circle(point C, double r): C(C), r(r){
  }
};
pair<point, point> circle_intersection(circle C1, circle C2){
  double d = dist(C1.C, C2.C);
  double m = (C1.r * C1.r + d * d - C2.r * C2.r) / (2 * d);
  point H = C1.C + (C2.C - C1.C) / d * m;
  double h = sqrt(C1.r * C1.r - m * m);
  point D = rotate90(C2.C - C1.C) / d * h;
  return make_pair(H - D, H + D);
}
pair<point, point> tangent(point P, point C){
  double d = dist(P, C);
  double d2 = sqrt(d * d - 100 * 100);
  circle C1(P, d2);
  circle C2(C, 100);
  return circle_intersection(C1, C2);
}
vector<line> common_tangent(point A, point B){
  vector<line> ans;
  double d = dist(A, B);
  point D = rotate90(B - A) / d * 100;
  ans.push_back(line(A + D, B + D));
  ans.push_back(line(A - D, B - D));
  if (d > 200){
    double d2 = sqrt(d * d - 200 * 200);
    circle C1(A, 200);
    circle C2(B, d2);
    pair<point, point> P = circle_intersection(C1, C2);
    ans.push_back(line((A + P.first) / 2, B - (P.first - A) / 2));
    ans.push_back(line((A + P.second) / 2, B - (P.second - A) / 2));
  }
  return ans;
}
int main(){
  cout << fixed << setprecision(20);
  int N;
  point G;
  cin >> N >> G.x >> G.y;
  vector<point> C(N);
  for (int i = 0; i < N; i++){
    cin >> C[i].x >> C[i].y;
  }
  point S(0, 0);
  vector<vector<point>> T(N + 2);
  T[N].push_back(S);
  T[N + 1].push_back(G);
  vector<tuple<int, int, int, int>> E;
  E.push_back(make_tuple(N, 0, N + 1, 0));
  for (int i = 0; i < N; i++){
    pair<point, point> T1 = tangent(S, C[i]);
    T[i].push_back(T1.first);
    T[i].push_back(T1.second);
    E.push_back(make_tuple(N, 0, i, 0));
    E.push_back(make_tuple(N, 0, i, 1));
    pair<point, point> T2 = tangent(G, C[i]);
    T[i].push_back(T2.first);
    T[i].push_back(T2.second);
    E.push_back(make_tuple(i, 2, N + 1, 0));
    E.push_back(make_tuple(i, 3, N + 1, 0));
  }
  for (int i = 0; i < N; i++){
    for (int j = i + 1; j < N; j++){
      vector<line> L = common_tangent(C[i], C[j]);
      int cnt = L.size();
      for (int k = 0; k < cnt; k++){
        int id1 = T[i].size();
        int id2 = T[j].size();
        T[i].push_back(L[k].A);
        T[j].push_back(L[k].B);
        E.push_back(make_tuple(i, id1, j, id2));
        E.push_back(make_tuple(j, id2, i, id1));
      }
    }
  }
  vector<vector<int>> id(N + 2);
  int V = 0;
  for (int i = 0; i < N + 2; i++){
    int cnt = T[i].size();
    id[i] = vector<int>(cnt);
    for (int j = 0; j < cnt; j++){
      id[i][j] = V + j;
    }
    V += cnt;
  }
  int M = E.size();
  vector<vector<pair<double, int>>> E2(V);
  for (int i = 0; i < M; i++){
    point P = T[get<0>(E[i])][get<1>(E[i])];
    point Q = T[get<2>(E[i])][get<3>(E[i])];
    bool ok = true;
    for (int j = 0; j < N; j++){
      if (point_segment_distance(C[j], line(P, Q)) < 100 - EPS){
        ok = false;
      }
    }
    if (ok){
      double d = dist(P, Q);
      int u = id[get<0>(E[i])][get<1>(E[i])];
      int v = id[get<2>(E[i])][get<3>(E[i])];
      E2[u].push_back(make_pair(d, v));
    }
  }
  for (int i = 0; i < N; i++){
    int cnt = T[i].size();
    vector<pair<double, int>> P(cnt);
    for (int j = 0; j < cnt; j++){
      P[j] = make_pair(arg(T[i][j] - C[i]), j);
    }
    sort(P.begin(), P.end());
    P.push_back(pair<double, int>());
    P[cnt] = P[0];
    for (int j = 0; j < cnt; j++){
      double L = P[j].first;
      double R = P[j + 1].first;
      if (R < L){
        R += PI * 2;
      }
      bool ok = true;
      for (int k = 0; k < N; k++){
        if (i != k && dist(C[i], C[k]) < 200){
          pair<point, point> Q = circle_intersection(circle(C[i], 100), circle(C[k], 100));
          double l = arg(Q.first - C[i]);
          double r = arg(Q.second - C[i]);
          if (r < l){
            r += PI * 2;
          }
          if (l < R && r > L){
            ok = false;
          }
        }
      }
      if (ok){
        double d = (R - L) * 100;
        int u = id[i][P[j].second];
        int v = id[i][P[j + 1].second];
        E2[u].push_back(make_pair(d, v));
        E2[v].push_back(make_pair(d, u));
      }
    }
  }
  vector<double> d(V, -1);
  priority_queue<pair<double, int>, vector<pair<double, int>>, greater<pair<double, int>>> pq;
  pq.push(make_pair(0, id[N][0]));
  while (!pq.empty()){
    double dd = pq.top().first;
    int v = pq.top().second;
    pq.pop();
    if (d[v] == -1){
      d[v] = dd;
      for (auto P : E2[v]){
        int w = P.second;
        if (d[w] == -1){
          pq.push(make_pair(dd + P.first, w));
        }
      }
    }
  }
  if (d[id[N + 1][0]] == -1){
    cout << 0 << endl;
  } else {
    cout << d[id[N + 1][0]] << endl;
  }
}

2021-05-08

Codeforces Round #720 (Div. 2) C: Nastia and a Hidden Permutation

問題解説 Codeforces

codeforces.com

想定解とは異なると思われる解法で解きました。

問題概要

(インタラクティブ問題)

$1, 2, \cdots, n$ の順列 $p _ 1, p _ 2, \cdots, p _ n$ がある。この順列を質問をして当てたい。質問では、整数 $t, i, j, x \ (1 \leq t \leq 2, 1 \leq i, j \leq n, i \neq j, 1 \leq x \leq n - 1)$ を質問し、 $t=1$ ならば $\max(\min(x, p _ i), \min(x + 1, p _ j))$ の値を、 $t=2$ ならば $\min(\max(x, p _ i), \max(x + 1, p _ j))$ の値を知ることができる。

質問を $\displaystyle{\left\lfloor\frac{3n}{2}\right\rfloor+30}$ 回以下行い、順列 $p$ を答えよ。

解法

$n$ 個の要素を $\displaystyle{\left\lceil\frac{n}{2}\right\rceil}$ 個のペアに分け、定数個の例外を除いて各ペアについて 3 回の質問で値を特定します。以下、ペアになっている要素を $p _ a, p _ b$ とします。

何個かの $t, x$ の値について $p _ a, p _ b$ の値と得られる値の関係を調べる実験を行うと、 $t=1, x=n-1$ や $t=2, x=1$ のときに得られる値の種類が最も多くなるので、それらの質問をします。具体的には、 $t=1, x=n-1$ を質問した答えを $r _ 1$ 、 $t=2, x=1$ を質問した答えを $r _ 2$ とし、 $r _ 1, r _ 2$ の値で場合分けします。なお、場合分けは番号が小さいものをより優先するとします。

(1) $r _ 2 = 1$ のとき

$r _ 2 = 1$ より $\min(\max(1, p _ a), \max(2, p _ b)) = 1$ ですが、 $\max(2, p _ b)=1$ となることはないので $\max(1, p _ a)=1$ です。従って $p _ a=1$ となります。また、 $r _ 1 = \max(\min(n-1, 1), \min(n, p _ b)) = \max(1, \min(n, p _ b)) = p _ b$ なので、 $p _a = 1, p _ b = r _ 1$ となります。

(2) $r _ 1 = n$ のとき

$r _ 1 = n$ より $\max(\min(n - 1, p _ a), \min(n, p _ b)) = n$ ですが、 $\min(n - 1, p _ a) = n$ となることはないので $\max(n, p _ b) = n$ です。従って $p _ b = n$ となります。また、 $r _ 2 = \min(\max(1, p _ a), \max(2, n)) = \min(\max(1, p _ a), n)) = p _ a$ なので、 $p _ a = r _ 2, p _ b = n$ となります。

(3) $3 \leq r _ 1, r _ 2 \leq n - 2$ のとき

$r _ 1 = \max(\min(n - 1, p _ a), \min(n, p _ b)) \leq n - 2$ より $p _ a, p _ b \leq n - 2$ , $r _ 2 = \min(\max(1, p _ a), \max(2, p _ b)) \geq 3$ より $p _ a, p _ b \geq 3$ なので $3 \leq p _ a, p _ b \leq n - 2$ が成立します。よって、 $r _ 1 = \max(p _ a, p _ b), r _ 2 = \min(p _ a, p _ b)$ より $(p _ a, p _ b)$ としてあり得る組は $(p _ a, p _ b) = (r _ 1, r _ 2), (r _ 2, r _ 1)$ の 2 通り存在します。

そこで、 $t=1, x=r _ 2$ として質問すると、答えが $(p _ a, p _ b) = (r _ 1, r _ 2)$ のときは $\max(\min(r _ 2, p _ a),\min(r _ 2 + 1, p _ b)) = \max(\min(p _ b, p _ a), \min(p _ b + 1, p _ b) = \max(p _ b, p _ b) = p _ b = r _ 2$ , $(p _ a, p _ b) = (r _ 2, r _ 1)$ のときは $\max(\min(r _ 2, p _ a), \min(r _ 2 +1, p _ b)) = \max(min(p _ a, p _ a), \min(p _ a + 1, p _ b)) = p _ a = r _ 1$ となり、 $r _ 1 \neq r _2$ なのでこれらを判別することができます。

(4) $r _ 1 = n - 1, r _ 2 = 2$ のとき $r _ 1 = \max(\min(n - 1, p _ a), \min(n, p _ b)) \lt n$ より $p _ b \lt n$ が、 $r _ 2 = \min(\max(1, p _ a), \max(2, p _ b)) \gt 1$ より $p _a > 1$ がわかります。また、 $p _ a, p _ b \leq n - 2$ のときは $r _ 1 = \max(p _ a, p _ b) \leq n - 2$ より矛盾が生じ、 $p _ a, p _ b \geq 3$ のときは $r _ 2 = \min(p _ a, p _ b) \geq 3$ より矛盾が生じるため、 $(p _ a, p _ b)$ としてあり得る組は $(p _ a, p _ b) = (n, 1), (n, 2), (n - 1, 1), (n - 1, 2), (2, n - 1)$ の 5 通り存在します。

$t=1, x=1$ として質問したときの答えを $r _ 3$ 、 $t=2, x=n-1$ として質問したときの答えを $r _ 4$ とすると、 $(p _ a, p _ b) = (n, 1), (n, 2), (n - 1, 1), (n - 1, 2), (2, n - 1)$ のとき $(r _ 3, r _ 4)$ はそれぞれ $(r _ 3, r _ 4) = (1, n), (2, n), (1, n - 1), (2, n - 1), (2, n - 1)$ となるので、 $(r _ 3, r _ 4) = (2, n - 1)$ とならない最初の 3 通りは判別することはできます。

また、 $t=1, x=2$ として質問したときの答えを $r _ 5$ とすると、 $(p _ a, p _ b) = (n - 1, 2), (2, n - 1)$ のときそれぞれ $r_5 = 2, 3$ となり、残りの 2 通りも判別することができます。

(5) $r _ 1 = r _ 2 = 2$ のとき $r _ 1 = \max(\min(n - 1, p _ a), \min(n, p _ b)) \leq 2$ より $p _ a, p _ b \leq 2$ であり、 $p _ a = 1$ のときは $r _ 2 = \min(\max(1, 1), \max(2, p _ b)) = 1 \leq 2$ と矛盾が生じるので $p _ a = 2$ です。 $p$ は順列より $p _ a \neq p _ b$ なので $p _ b = 1$ です。

(6) $r _ 1 = r _ 2 = n - 1$ のとき $r _ 2 = \min(\max(1, p _ a), \max(2, p _ b)) \geq n - 1$ より $p _ a, p _ b \geq n - 1$ であり、 $p _ b = n$ のときは $r _ 1 = \min(\max(n - 1, p _ a), \max(n, n)) = n \leq n - 1$ と矛盾が生じるので $p _ b = n - 1$ です。 $p$ は順列より $p _ a \neq p _ b$ なので $p _ a = n$ です。

(7) $3 \leq r _ 1 \leq n - 2, r _ 2 = 2$ のとき $r _ 1 = \max(\min(n - 1, p _ a), \min(n, p _ b)) \leq n - 2$ より $p _ a, p _ b \leq n - 2$ 、 $r _ 2 = \min(\max(1, p _ a), \max(2, p _ b)) \geq 2$ より $p _ a \geq 2$ です。また、 $p _ a, p _ b \geq 3$ のときは $r _ 2 = \min(\max(1, p _ a), \max(2, p _ b)) = \max(p _ a, p _ b) \geq 3 \gt 2$ と矛盾が生じ、 $p _ a = 2, p _ b \leq 2$ のときは $r _ 1 = \max(\min(n - 1, p _ a), \min(n, p _ b)) = \max(p _ a, p _ b) \leq 3 \lt 3$ と矛盾が生じるので、 $(p _ a, p _ b)$ としてあり得る組は $(p _ a, p _ b) = (r _ 1, 1), (r _ 2, 2), (2, r _ 2)$ の 3 通り存在します。

$t = 1, x = 1$ として質問したときの答えを $r _ 3$ 、 $t = 1, x = 2$ として質問したときの答えを $r _ 4$ とすると、 $(p _ a, p _ b) = (r _ 1, 1), (r _ 2, 2), (2, r _ 2)$ のとき $(r _ 3, r _ 4)$ はそれぞれ $(r _ 3, r _ 4) = (1, 2), (2, 2), (2, 3)$ となり、これらを判別することができます。

(8) $r _ 1 = n - 1, 3 \leq r _ 2 \leq n - 2$ のとき $r _ 2 = \min(\max(1, p _ a), \max(2, p _ b)) \geq 3$ より $p _ a, p _ b \geq 3$ 、 $r _ 1 = \max(\min(n - 1, p _ a), \min(n, p _ b)) \leq n - 1$ より $p _ b \leq n - 1$ です。また、 $p _ a, p _ b \leq n - 2$ のときは $r _ 1 = \max(\min(n - 1, p _ a), \min(n, p _ b)) = \max(p _ a, p _ b) \leq n - 2 \lt n - 1$ と矛盾が生じ、 $p _ a \geq n - 1, p _ b = n - 1$ のときは $r _ 2 = \min(\max(1, p _ a), \max(2, p _ b)) = \min(p _ a, p _ b) \geq n - 1 \gt n - 2$ と矛盾が生じるので、 $(p _ a, p _ b)$ としてあり得る組は $(p _ a, p _ b) = (n, r _ 2), (n - 1, r _ 2), (r _ 2, n - 1)$ の 3 通り存在します。

$t = 2, x = n - 1$ として質問したときの答えを $r _ 3$ 、 $t = 2, x = n - 2$ として質問したときの答えを $r _ 4$ とすると、 $(p _ a, p _ b) = (n, r _ 2), (n - 1, r _ 2), (r _ 2, n - 1)$ のとき $(r _ 3, r _ 4)$ はそれぞれ $(r _ 3, r _ 4) = (n, n - 1), (n - 1, n - 1), (n - 1, n - 2)$ となり、これらを判別することができます。

以上より、次に示す方法で $p _ a, p _ b$ を特定することができます。

$t = 1, x = n - 1$ として質問したときの答えを $r _1$ 、 $t = 2, x = 1$ として質問したときの答えを $r _ 2$ とする。

(1) $r _ 2 = 1$ のとき、 $p _ a = 1, p _ b = r _ 1$

(2) $r _ 1 = n$ のとき、 $p _ a = r _ 2, p _ b = n$

(3) $3 \leq r _ 1, r _ 2 \leq n - 2$ のとき、 $t = 1, x = r2$ として質問し、その答えを $r _ 3$ とすると

(3-1) $r _ 3 = r _ 2$ のとき、 $p _ a = r _ 1, p _ b = r _ 2$

(3-2) そうでないとき、 $p _ a = r _ 2, p _ b = r _ 1$

(4) $r _ 1 = n - 1, r _ 2 = 2$ のとき、 $t = 1, x = 1$ として質問しその答えを $r _ 3$ 、 $t = 2, x = n - 1$ として質問しその答えを $r _ 4$ とする。

(4-1) $r _ 3 = 1, r _ 4 = n$ のとき、 $p _ a = n, p _ b = 1$

(4-2) $r _ 3 = 2, r _ 4 = n$ のとき、 $p _ a = n, p _ b = 2$

(4-3) $r _ 3 = 1, r _ 4 = n - 1$ のとき、 $p _ a = n - 1, p _ b = 1$

(4-4) $r _ 3 = 2, r _ 4 = n - 1$ のとき、 $t = 1, x = 2$ として質問しその答えを $r _ 5$ とする。

(4-4-1) $r _ 5 = 2$ のとき、 $p _ a = n - 1, p _ b = 2$

(4-4-2) そうでないとき、 $p _ a = 2, p _ b = n - 1$

(5) $r _ 1 = r _ 2 = 2$ のとき、 $p _ a = 2, p _ b = 1$

(6) $r _ 1 = r _ 2 = n - 1$ のとき、 $p _ a = n, p _ b = n - 1$

(7) $3 \leq r _ 1 \leq n - 1, r _ 2 = 2$ のとき、 $t = 1, x = 1$ として質問しその答えを $r _ 3$ とする。

(7-1) $r _ 3 = 1$ のとき、 $p _ a = r _ 1, p _ b = 1$

(7-2) そうでないとき、 $t = 1, x = 2$ として質問しその答えを $r _ 4$ とする。

(7-2-1) $r _ 4 = 2$ のとき、 $p _ a = r _ 1, p _ b = 2$

(7-2-2) そうでないとき、 $p _a = 2, p _ b = r _ 1$

(8) $r _ 1 = 2, 3 \leq r _ 2 \leq n - 1$ のとき、 $t = 2, x = n - 1$ として質問しその答えを $r _ 3$ とする。

(8-1) $r _ 3 = n$ のとき、 $p _ a = n, p _ b = r _ 2$

(8-2) そうでないとき、 $t = 2, x = n - 1$ として質問しその答えを $r _ 4$ とする。

(8-2-1) $r _ 4 = n - 1$ のとき、 $p _ a = n - 1, p _ b = r _ 2$

(8-2-2) そうでないとき、 $p _a = r _ 2, p _ b = n - 1$

$(p _ a, p _ b)$ の値を特定するのに 3 回以上質問しなければならないときもありますが、そのような場合でも 5 回以内の質問で特定することができ、このケースは十分小さい定数回しか出現しないため、クエリ数の上限以内で $p$ のすべての要素が特定できます。

実装

codeforces.com

#include <bits/stdc++.h>
using namespace std;
int main(){
  int T;
  cin >> T;
  for (int i = 0; i < T; i++){
    int n;
    cin >> n;
    vector<pair<int, int>> P;
    for (int j = 0; j < n / 2; j++){
      P.push_back(make_pair(j * 2, j * 2 + 1));
    }
    if (n % 2 == 1){
      P.push_back(make_pair(n - 2, n - 1));
    }
    int m = P.size();
    vector<int> p(n);
    for (int j = 0; j < m; j++){
      int a = P[j].first;
      int b = P[j].second;
      cout << "? " << 1 << ' ' << a + 1 << ' ' << b + 1 << ' ' << n - 1 << endl;
      int res1;
      cin >> res1;
      cout << "? " << 2 << ' ' << a + 1 << ' ' << b + 1 << ' ' << 1 << endl;
      int res2;
      cin >> res2;
      if (res2 == 1){
        p[a] = 1;
        p[b] = res1;
      } else if (res1 == n){
        p[a] = res2;
        p[b] = n;
      } else if (3 <= res1 && res1 <= n - 2 && 3 <= res2 && res2 <= n - 2){
        cout << "? " << 1 << ' ' << a + 1 << ' ' << b + 1 << ' ' << res2 << endl;
        int res3;
        cin >> res3;
        if (res3 == res2){
          p[a] = res1;
          p[b] = res2;
        } else {
          p[a] = res2;
          p[b] = res1;
        }
      } else if (res1 == n - 1 && res2 == 2){
        cout << "? " << 1 << ' ' << a + 1 << ' ' << b + 1 << ' ' << 1 << endl;
        int res3;
        cin >> res3;
        cout << "? " << 2 << ' ' << a + 1 << ' ' << b + 1 << ' ' << n - 1 << endl;
        int res4;
        cin >> res4;
        if (res3 == 1 && res4 == n){
          p[a] = n;
          p[b] = 1;
        } else if (res3 == 2 && res4 == n){
          p[a] = n;
          p[b] = 2;
        } else if (res3 == 1 && res4 == n - 1){
          p[a] = n - 1;
          p[b] = 1;
        } else {
          cout << "? " << 1 << ' ' << a + 1 << ' ' << b + 1 << ' ' << 2 << endl;
          int res5;
          cin >> res5;
          if (res5 == 2){
            p[a] = n - 1;
            p[b] = 2;
          } else {
            p[a] = 2;
            p[b] = n - 1;
          }
        }
      } else if (res1 == 2 && res2 == 2){
        p[a] = 2;
        p[b] = 1;
      } else if (res1 == n - 1 && res2 == n - 1){
        p[a] = n;
        p[b] = n - 1;
      } else if (res1 < n - 1 && res2 == 2){
        cout << "? " << 1 << ' ' << a + 1 << ' ' << b + 1 << ' ' << 1 << endl;
        int res3;
        cin >> res3;
        if (res3 == 1){
          p[a] = res1;
          p[b] = 1;
        } else {
          cout << "? " << 1 << ' ' << a + 1 << ' ' << b + 1 << ' ' << 2 << endl;
          int res4;
          cin >> res4;
          if (res4 == 2){
            p[a] = res1;
            p[b] = 2;
          } else {
            p[a] = 2;
            p[b] = res1;
          }
        }
      } else if (res1 == n - 1 && res2 > 2){
        cout << "? " << 2 << ' ' << a + 1 << ' ' << b + 1 << ' ' << n - 1 << endl;
        int res3;
        cin >> res3;
        if (res3 == n){
          p[a] = n;
          p[b] = res2;
        } else {
          cout << "? " << 2 << ' ' << a + 1 << ' ' << b + 1 << ' ' << n - 2 << endl;
          int res4;
          cin >> res4;
          if (res4 == n - 1){
            p[a] = n - 1;
            p[b] = res2;
          } else {
            p[a] = res2;
            p[b] = n - 1;
          }
        }
      }
    }
    cout << "!";
    for (int j = 0; j < n; j++){
      cout << ' ' << p[j];
    }
    cout << endl;
  }
}

2021-04-26

POJ 1025: Department

問題解説 POJ

poj.org

問題概要

10 階建ての建物があり、各階には 10 個の部屋があります。各部屋には部屋番号が定められており、x 階の y 番目の部屋 (ただし x, y は 1-indexed) の部屋番号は xxyy (x または y が一桁の場合は前に 0 を付ける) です。

この建物に何人かの人が入ります。人にはそれぞれ大文字のアルファベットで表される序列があり、序列が高い人ほど辞書順で小さいアルファベットが割り当てられます。二人以上の人が同じ序列を持つことはありません。それぞれの人にはある時刻に建物に入った後、何個かの部屋を決められた順序で訪れそれぞれの部屋に決められた時間だけ滞在します。それぞれの人は部屋を必ず部屋番号の昇順に訪れます。

現在人が入っている部屋に入りたい人がいる場合、その人は部屋の前で列を作って待つ必要があります。部屋に入っている人が出たとき、現在列に並んでいる人 (部屋から人が出た瞬間に到着した人を含む) のうち序列が最も高い人のみが部屋に入ることができます。

建物にはエレベーターが設置されています。人がエレベーターに乗れるのは一日の開始からの経過秒数が 5 の倍数であるときのみです。一日の開始から 5 秒ごとに、エレベーターに乗ろうとしている人 (その瞬間に到着した人を含む) がいるとき、そのうち序列が最も高い人のみがエレベーターに乗ることができます。別の階にいた場合でも、二人が同時刻にエレベーターに乗ることはできません。

建物の入口から 1 階の任意の部屋またはエレベーター乗り場への移動には 30 秒かかります。ある部屋と同じ階の別の部屋やエレベーター乗り場の間の移動には 10 秒かかります。エレベーターは 1 階分の昇降に 30 秒かかります。1 階の任意の部屋またはエレベーター乗り場から建物の出口への移動には 30 秒かかります。

それぞれの人が最もかかる時間が短くなるように行動したときの行動を出力してください。なお、建物を出る時刻は 24:00:00 より前になることが保証されます。

出力

序列の高い順に、それぞれの人の行動を出力してください。それぞれの人の行動は時刻の昇順に出力してください。

時刻 t1 から時刻 t2 にかけて建物の入口から 1 階の部屋またはエレベーター乗り場へ移動したとき、t1 t2 Entry と出力してください。

時刻 t1 から時刻 t2 にかけて部屋番号 x の部屋に滞在したとき、t1 t2 Stay in room x と出力してください。

時刻 t1 から時刻 t2 にかけてエレベーターに乗っていたとき、t1 t2 Stay in elevator と出力してください。

時刻 t1 から時刻 t2 にかけて部屋番号 x の部屋から同じ階にある部屋番号 y の部屋へ移動したとき、t1 t2 Transfer from room x to room y と出力してください。

時刻 t1 から時刻 t2 にかけて部屋番号 x の部屋から同じ階のエレベーター乗り場へ移動したとき、t1 t2 Transfer from room x to elevator と出力してください。

時刻 t1 から時刻 t2 にかけてある階のエレベーター乗り場から同じ階にある部屋番号 y の部屋へ移動したとき、t1 t2 Transfer from elevator to room y と出力してください。

時刻 t1 から時刻 t2 にかけて部屋番号 x の部屋の前で待っていたとき、t1 t2 Waiting in front of room x と出力してください。

時刻 t1 から時刻 t2 にかけてエレベーター乗り場で待っていたとき、t1 t2 Waiting in elevator queue と出力してください。

時刻 t1 から時刻 t2 にかけて1 階の部屋またはエレベーター乗り場から建物の出口へ移動したとき、t1 t2 Exit と出力してください。

解法

移動をそのまま実装しても解けますが、実装量が多くなるので、実装の工夫をすることを考えます。

部屋とエレベーター乗り場は性質が似ているので、エレベーター乗り場を各階の 0 番目の部屋であるとして扱うとにします。また、部屋間の移動は、直前の部屋からの移動にかかる時間・その部屋 (またはエレベーター) に滞在する時間・部屋番号で管理することにします。

出力がややこしいので、最初にそれぞれの人が各部屋に入る時刻と出る時刻を計算することにします。この情報から出力すべき情報を得ることは比較的容易なので、省略します。

優先度付きキューに時刻・人の序列・人の番号・その人が訪れる予定の部屋のうち何番目の部屋に行こうとしているかの組を入れ、人が部屋に入ろうとするという情報を時刻の昇順に処理します。それぞれの部屋についてその部屋に入っている人が出る時刻を持っておき、人が部屋に入ろうとしたが入ろうとした時刻がこの時刻より早いときはこの時刻に再び入ることを試みる、とすると、人を序列の順に正しく入れることができます。

ただし、入ろうとしている部屋がエレベーターである場合は別の条件で判定する必要があります。具体的には、最後にエレベーターに人が乗った時刻を持っておき、この時刻の 5 秒後より前にエレベーターに乗ろうとしたときはこの時刻の 5 秒後に再びエレベーターに乗ろうとする、とすればよいです。また、時刻が 5 の倍数でないときは 5 の倍数になるまで待つ必要があります。

計算量は悪いですが、序列の制約より人の人数は 26 人以下と少ないので、この解法でも実行時間 0ms で AC を得ることができました。

実装

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <utility>
#include <algorithm>
using namespace std;
int main(){
  vector<char> code;
  vector<int> entry;
  vector<vector<string>> name;
  vector<vector<int>> rooms, time1, time2;
  while (true){
    char c;
    cin >> c;
    if (c == '.'){
      break;
    }
    code.push_back(c);
    string time;
    cin >> time;
    int h = (time[0] - '0') * 10 + (time[1] - '0');
    int m = (time[3] - '0') * 10 + (time[4] - '0');
    int s = (time[6] - '0') * 10 + (time[7] - '0');
    entry.push_back(h * 3600 + m * 60 + s);
    name.push_back(vector<string>());
    rooms.push_back(vector<int>());
    time1.push_back(vector<int>());
    time2.push_back(vector<int>());
    int prev = 0;
    while (true){
      string id;
      cin >> id;
      if (id == "0"){
        break;
      }
      int t;
      cin >> t;
      int floor = (id[0] - '0') * 10 + (id[1] - '0') - 1;
      int room = (id[2] - '0') * 10 + (id[3] - '0');
      if (prev != floor){
        name.back().push_back("elevator");
        rooms.back().push_back(prev * 11);
        time1.back().push_back(10);
        time2.back().push_back(abs(prev - floor) * 30);
      }
      name.back().push_back("room " + id);
      rooms.back().push_back(floor * 11 + room);
      time1.back().push_back(10);
      time2.back().push_back(t);
      prev = floor;
    }
    if (prev != 0){
      name.back().push_back("elevator");
      rooms.back().push_back(prev * 11);
      time1.back().push_back(10);
      time2.back().push_back(prev * 30);
    }
    time1.back()[0] = 30;
  }
  int N = code.size();
  vector<pair<char, int>> P(N);
  for (int i = 0; i < N; i++){
    P[i] = make_pair(code[i], i);
  }
  sort(P.begin(), P.end());
  vector<int> next(110, 0);
  int last = 0;
  priority_queue<pair<pair<int, char>, pair<int, int>>, vector<pair<pair<int, char>, pair<int, int>>>, greater<pair<pair<int, char>, pair<int, int>>>> pq;
  for (int i = 0; i < N; i++){
    pq.push(make_pair(make_pair(entry[i] + 30, code[i]), make_pair(i, 0)));
  }
  vector<vector<int>> ans1(N), ans2(N);
  while (!pq.empty()){
    int time = pq.top().first.first;
    char agent = pq.top().first.second;
    int id = pq.top().second.first;
    int num = pq.top().second.second;
    pq.pop();
    int room = rooms[id][num];
    if (room % 11 != 0 && time < next[room]){
      pq.push(make_pair(make_pair(next[room], agent), make_pair(id, num)));
    } else if (room % 11 == 0 && time < last + 5){
      pq.push(make_pair(make_pair(last + 5, agent), make_pair(id, num)));
    } else if (room % 11 == 0 && time % 5 != 0){
      pq.push(make_pair(make_pair((time + 4) / 5 * 5, agent), make_pair(id, num)));
    } else {
      int stay = time2[id][num];
      ans1[id].push_back(time);
      ans2[id].push_back(time + stay);
      if (room % 11 != 0){
        next[room] = time + stay;
      } else {
        last = time;
      }
      if (num < rooms[id].size() - 1){
        int tmp = time + stay + time1[id][num + 1];
        pq.push(make_pair(make_pair(tmp, agent), make_pair(id, num + 1)));
      }
    }
  }
  for (int i = 0; i < N; i++){
    int id = P[i].second;
    int M = rooms[id].size();
    vector<int> ans;
    vector<string> st;
    ans.push_back(entry[id]);
    for (int j = 0; j < M; j++){
      int tmp = ans.back() + time1[id][j];
      ans.push_back(tmp);
      if (j == 0){
        st.push_back("Entry");
      } else {
        st.push_back("Transfer from " + name[id][j - 1] + " to " + name[id][j]);
      }
      if (ans1[id][j] != tmp){
        ans.push_back(ans1[id][j]);
        if (rooms[id][j] % 11 != 0){
          st.push_back("Waiting in front of " + name[id][j]);
        } else {
          st.push_back("Waiting in elevator queue");
        }
      }
      ans.push_back(ans2[id][j]);
      st.push_back("Stay in " + name[id][j]);
    }
    int T = ans.back();
    ans.push_back(T + 30);
    st.push_back("Exit");
    int cnt = st.size();
    vector<string> time(cnt + 1);
    for (int j = 0; j <= cnt; j++){
      int h = ans[j] / 3600;
      time[j] += (char) ('0' + h / 10);
      time[j] += (char) ('0' + h % 10);
      time[j] += ':';
      int m = ans[j] % 3600 / 60;
      time[j] += (char) ('0' + m / 10);
      time[j] += (char) ('0' + m % 10);
      time[j] += ':';
      int s = ans[j] % 60;
      time[j] += (char) ('0' + s / 10);
      time[j] += (char) ('0' + s % 10);
    }
    cout << code[id] << endl;
    for (int j = 0; j < cnt; j++){
      cout << time[j] << ' ' << time[j + 1] << ' ' << st[j] << endl;
    }
    cout << endl;
  }
}

2021-04-15

AOJ 1139: Earth Observation with a Mobile Robot Team

問題解説 AOJ

https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1139&lang=jp

解法

2 台のロボットの距離が $R$ 未満になったり $R$ 以上になったりすることが発生する時刻をすべて列挙することを考えます。

ロボットの組を全探索します。ロボットが 2 台とも動いていると考えにくいので、一方に対するもう一方の相対的な位置の変化を考えると、この変化は同じく平面上の折れ線になります。

この折れ線を線分に分解し、それぞれの線分について中心が原点で半径 $R$ の円との交点を求めればよいですが、ロボットが近づいているのか離れているのかは交点の情報のみではわかりません。

そこで、線分と円の交点を求める関数自体は作らず、直線と円の交点を求める関数のみ作り 2 つの交点を直線が向いている順に並んでいるように返すと、そのうちどちらの点であるかでロボットが近づいているのか離れているのかがわかります。

ロボット対応する頂点を作り、現在距離 $R$ 以内にあるロボットの組に対応する頂点の間に辺を持つグラフを隣接行列で持ち、辺の有無を更新していくことを考えます。辺を新たに追加したときに一方のロボットのみがデータを記憶しているときのみ BFS をすると、BFS の回数が最大 $N$ 回となります。

時間計算量は $O(N ^ 3 + N ^ 2 T \log(N ^ 2 T))$ です。

実装

judge.u-aizu.ac.jp

#include <bits/stdc++.h>
using namespace std;
const double EPS = 0.00000001;
struct point{
  double x, y;
  point(){
  }
  point(double x, double y): x(x), y(y){
  }
  point operator +(point P){
    return point(x + P.x, y + P.y);
  }
  point operator -(point P){
    return point(x - P.x, y - P.y);
  }
  point operator *(double k){
    return point(x * k, y * k);
  }
  point operator /(double k){
    return point(x / k, y / k);
  }
  bool operator < (point P) const{
    return x < P.x || x == P.x && y < P.y;
  }
};
double abs(point P){
  return sqrt(P.x * P.x + P.y * P.y);
}
double dist(point P, point Q){
  return abs(Q - P);
}
double dot(point P, point Q){
  return P.x * Q.x + P.y * Q.y;
}
double cross(point P, point Q){
  return P.x * Q.y - P.y * Q.x;
}
struct line{
  point A, B;
  line(point A, point B): A(A), B(B){
  }
};
point vec(line L){
  return L.B - L.A;
}
point projection(point P, line L){
  return L.A + vec(L) * dot(P - L.A, vec(L)) / abs(vec(L)) / abs(vec(L));
}
double point_line_distance(point P, line L){
  return abs(cross(L.A - P, vec(L))) / abs(vec(L));
}
struct circle{
  point C;
  double r;
  circle(point C, double r): C(C), r(r){
  }
};
vector<point> line_circle_intersection(line L, circle C){
  double d = point_line_distance(C.C, L);
  if (d > C.r){
    return vector<point>();
  }
  point P = projection(C.C, L);
  point D = vec(L) / abs(vec(L));
  double m = sqrt(C.r * C.r - d * d);
  vector<point> ans = {P - D * m, P + D * m};
  return ans;
}
int main(){
  while (true){
    int N, T;
    double R;
    cin >> N >> T >> R;
    if (N == 0 && T == 0 && R == 0){
      break;
    }
    vector<string> s(N);
    vector<point> P(N);
    vector<vector<double>> t(N, vector<double>(1));
    vector<vector<point>> v(N);
    for (int i = 0; i < N; i++){
      cin >> s[i];
      cin >> t[i][0] >> P[i].x >> P[i].y;
      while (t[i].back() != T){
        t[i].push_back(0);
        v[i].push_back(point());
        cin >> t[i].back() >> v[i].back().x >> v[i].back().y;
      }
    }
    vector<tuple<double, int, int, bool>> upd;
    for (int i = 0; i < N; i++){
      for (int j = i + 1; j < N; j++){
        if (dist(P[i], P[j]) < R){
          upd.push_back(make_tuple(0, i, j, true));
        }
        int cnt1 = v[i].size(), cnt2 = v[j].size();
        vector<tuple<double, point, int>> c;
        for (int k = 0; k < cnt1; k++){
          c.push_back(make_tuple(t[i][k], v[i][k], 0));
        }
        for (int k = 0; k < cnt2; k++){
          c.push_back(make_tuple(t[j][k], v[j][k], 1));
        }
        sort(c.begin(), c.end());
        int cnt = c.size();
        point v1(0, 0), v2(0, 0);
        vector<double> t2(cnt + 1);
        vector<point> dv(cnt);
        for (int k = 0; k < cnt; k++){
          t2[k] = get<0>(c[k]);
          if (get<2>(c[k]) == 0){
            v1 = get<1>(c[k]);
          }
          if (get<2>(c[k]) == 1){
            v2 = get<1>(c[k]);
          }
          dv[k] = v2 - v1;
        }
        t2[cnt] = T;
        point D = P[j] - P[i];
        for (int k = 0; k < cnt; k++){
          if (abs(dv[k]) > EPS){
            point D2 = D + dv[k] * (t2[k + 1] - t2[k]);
            line L(D, D2);
            if (point_line_distance(point(0, 0), L) < R){
              circle C(point(0, 0), R);
              vector<point> I = line_circle_intersection(L, C);
              for (int l = 0; l < 2; l++){
                double d = dot(I[l] - D, D2 - D) / dist(D, D2);
                if (- EPS < d && d < dist(D, D2) + EPS){
                  upd.push_back(make_tuple(t2[k] + d / abs(dv[k]), i, j, l == 0));
                }
              }
            }
            D = D2;
          }
        }
      }
    }
    sort(upd.begin(), upd.end());
    int M = upd.size();
    vector<vector<bool>> E(N, vector<bool>(N, false));
    vector<bool> used(N, false);
    used[0] = true;
    for (int i = 0; i < M; i++){
      int a = get<1>(upd[i]);
      int b = get<2>(upd[i]);
      bool e = get<3>(upd[i]);
      E[a][b] = e;
      E[b][a] = e;
      if (e && (used[a] ^ used[b])){
        queue<int> Q;
        if (!used[a]){
          used[a] = true;
          Q.push(a);
        }
        if (!used[b]){
          used[b] = true;
          Q.push(b);
        }
        while (!Q.empty()){
          int v = Q.front();
          Q.pop();
          for (int j = 0; j < N; j++){
            if (E[v][j] && !used[j]){
              used[j] = true;
              Q.push(j);
            }
          }
        }
      }
    }
    vector<string> ans;
    for (int i = 0; i < N; i++){
      if (used[i]){
        ans.push_back(s[i]);
      }
    }
    sort(ans.begin(), ans.end());
    int cnt = ans.size();
    for (int i = 0; i < cnt; i++){
      cout << ans[i] << endl;
    }
  }
}

2021-04-01

POJ 1031: Fence

問題解説 POJ

poj.org

問題概要

座標平面上があり、原点にはランプが置かれています。

また、 $N$ 頂点の多角形があり、その各辺に沿って高さ $h$ のフェンスが個置かれています。多角形の $i \ (1 \leq i \leq N)$ 番目の頂点の座標は点 $(x _ i, y _ i)$ です。フェンスはランプの光を反射させたり通過させたりすることはありません。

原点からの距離が $r$ の点における光の強さを $\displaystyle{\frac{k}{r}}$ とします。ここで、 $k$ は点の位置によらない定数です。

幅が微小な幅 $dl$ 、高さ $h$ の長方形に当たる光の量 $dI$ を $I _ 0 | \cos \alpha | dl h$ (ただし $dl$ はその点における光の強さ、 $\alpha$ はその平面に垂直な直線と光とその点を結ぶ直線のなす角とします。

全てのフェンスに対する当たる光の量の合計を求め、小数第 3 位以下を四捨五入して小数第 2 位までで答えてください。

制約

$N$ は整数
$3 \leq N \leq 100$
多角形の辺は原点を通らない

解法

問題文が少々曖昧ですが、頑張ってエスパーしましょう。厳密な議論は行いません。

以下、原点を $O$ とします。

点 $A(a, d)$ , $B(b, d)$ ( $0 \lt d, a \lt b$ ) の間にフェンスが張られているとき、これに当たる光の量を求めることを考えます。これができれば、適切に移動や回転を行うことで全てのフェンスをこの場合に帰着できるので、答えが得られます。

点 $P(x, d)$ ( $a \leq x \leq b$ ) に当たる光の強さは $OP = \sqrt{x ^ 2 + d ^ 2}$ で、 $|\cos\alpha|$ は $y$ 軸と直線 $OP$ のなす角に等しいので、 $\displaystyle \frac {d} {\sqrt{x ^ 2 + d ^ 2}}$ となります。よって、当たる光の量の合計は $\displaystyle {kh \int _ {a} ^ {b} \frac {d}{x ^ 2 + d ^ 2} dx}$ です。

この積分の値を $I$ とします。 $x = d \tan \theta$ と置換積分を行い、 $\displaystyle {\arctan \frac{a}{d}, \arctan \frac {b}{d}}$ をそれぞれ $\theta _ 1, \theta _ 2$ とすると

$\displaystyle {I = kh \int _ {\theta _ 1} ^ {\theta _ 2} \frac {d}{d ^ 2 (\tan ^ 2 \theta + 1)} \cdot \frac {d}{\cos ^ 2 \theta} d \theta = kh \int _ {\theta _ 1} ^ {\theta _ 2} d \theta = kh(\theta _ 2 - \theta _ 1)}$ となります。

また、 $\theta _ 1, \theta _ 2$ はそれぞれ直線 $OA, OB$ の $y$ 軸となす角なので、 $\theta _ 2 - \theta _ 1$ は角 $\angle AOB$ の大きさになります。

よって、各フェンスについてその両端と原点の間の角 (符号も考慮) を求め、その累積和の最大値と最小値の差 (ただし $2 \pi$ より大きいときは $2 \pi$ とする) の $kh$ 倍が答えになります。

実装

#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
using namespace std;
const double PI = acos((double) -1);
int main(){
  double k, h;
  int N;
  cin >> k >> h >> N;
  vector<double> x(N + 1), y(N + 1);
  for (int i = 0; i < N; i++){
    cin >> x[i] >> y[i];
  }
  x[N] = x[0];
  y[N] = y[0];
  vector<double> t(N + 1);
  for (int i = 0; i <= N; i++){
    t[i] = atan2(y[i], x[i]);
  }
  vector<double> d(N);
  for (int i = 0; i < N; i++){
    d[i] = t[i + 1] - t[i];
    if (d[i] > PI){
      d[i] -= PI * 2;
    }
    if (d[i] < -PI){
      d[i] += PI * 2;
    }
  }
  double mx = 0, mn = 0, sum = 0;
  for (int i = 0; i < N; i++){
    sum += d[i];
    mx = max(mx, sum);
    mn = min(mn, sum);
  }
  double ans = min(mx - mn, PI * 2) * k * h;
  cout << fixed << setprecision(2) << ans << endl;
}

2021-03-31

POJ 1024: Tester Program

問題解説 POJ

poj.org

問題概要

縦 $H$ マス、横 $W$ マスの二次元グリッドがある。グリッドの左から $i$ 列目、下から $j$ 行目のマスをマス $(i,j)$ と呼ぶ。

マス $(0,0)$ から始めて隣接したマスに移動することを何度か繰り返した。移動の経路が文字列 $S$ として与えられる。 $S$ の $i \ (1 \leq i \leq |S|)$ 文字目が U, D, L, R であるとき、 $i$ 回目でそれぞれ上、下、左、右に隣接するマスに移動したことを示す。グリッドの外に移動しようとしたり、同じマスを二度以上訪れるような経路は与えられないことが保証されている。

グリッドの隣接する 2 つのマスの組の間に壁を $M$ 個配置し、迷路を作った。 $i \ (1 \leq i \leq M)$ 番目の壁はマス $(x _ {i1}, y _ {i1})$ と $(x _ {i2}, y _ {i2})$ の間に配置されている。迷路の始点はマス $(0,0)$ であり、終点は移動を終えたマスである。文字列 $S$ で示された経路がこの迷路の唯一の最短路であり、この条件を満たすために余分な壁がない (つまり、壁を 1 つ取り除くと文字列 $S$ で示された経路は必ずこの迷路の唯一の最短路ではなくなる) なら CORRECT、そうでないなら INCORRECT と出力せよ。

制約

$S$ 以外の入力はすべて整数
$1 \leq H, W \leq 100$
$S$ は U, D, L, R のみからなる
文字列 $S$ で示された経路ではグリッドの外に移動することはない
文字列 $S$ で示された経路では同じマスを二度以上訪れることはない
$0 \leq x _ {i1}, x _ {i2} \lt W \ (1 \leq i \leq M)$
$0 \leq y _ {i1}, y _ {i2} \lt H \ (1 \leq i \leq M)$
マス $(x _ {i1}, y _ {i1}), (x _ {i2}, y _ {i2}) \ (1 \leq i \leq M)$ は辺を共有する
$(x _ {i1}, y _ {i1}, x _ {i2}, y _ {i2}) \neq (x _ {j1}, y _ {j1}, x _ {j2}, y _ {j2}) \ (1 \leq i \lt j \leq M)$ (たぶん)
$(x _ {i1}, y _ {i1}, x _ {i2}, y _ {i2}) \neq (x _ {j2}, y _ {j2}, x _ {j1}, y _ {j1}) \ (1 \leq i \lt j \leq M)$ (たぶん)

解法

まず、文字列 $S$ で示された経路に従って移動して終点を求め、経路上に壁がないか調べます。(実は、テストケースが弱いので経路上に壁があるかどうかの判定は行わなくても AC になります。)

迷路の最短路とその個数を BFS で計算することで、文字列 $S$ で示された経路が迷路の唯一の最短路であるか判定することができます。個数は大きくなりすぎないように、 $2$ との min を取っておきます。

余分な壁がないことの判定でそれぞれの壁について BFS を行うと、計算量が $O(N+MHW)$ となり $M$ は最大で $\Theta(HW)$ になりうるので TLE してしまうので、適切に前計算を行い高速に判定することを考えます。

ある壁が条件を満たすために必要である条件は、その壁を取り除いたときその場所を通る最短路が元の迷路の最短路 (上の判定をすべて通過したという仮定のもとで、これは $|S|$ に等しい) 以下であることです。

よって、始点からマス $(x,y)$ への最短路を $d _ {xy}$ , 終点からマス $(x,y)$ への最短路を $d' _ {xy}$ とおくと、壁 $i$ を取り除いたときその場所を $(x _ {i1}, y _ {i1})$ から $(x _ {i2}, y _ {i2})$ に向かう方向に通る最短路は $d _ {x _ {i1} y _ {i1}} + 1 + d' _ {x _ {i2} y _ {i2}}$ , $(x _ {i2}, y _ {i2})$ から $(x _ {i1}, y _ {i1})$ に向かう方向に通る最短路は $d _ {x _ {i2} y _ {i2}} + 1 + d' _ {x _ {i1} y _ {i1}}$ なので、壁 $i$ が必要であることは $\min(d _ {x _ {i1} y _ {i1}} + 1 + d' _ {x _ {i2} y _ {i2}}, d _ {x _ {i2} y _ {i2}} + 1 + d' _ {x _ {i1} y _ {i1}}) \leq |S|$ であること同値になります。

それぞれの壁について必要性を $O(1)$ で計算できたので、これでこの問題が解けました。

実装

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <utility>
using namespace std;
vector<int> dy, dx;
const int INF = 1000000;
int main(){
  dy = vector<int>(4);
  dy[0] = -1;
  dy[1] = 1;
  dy[2] = 0;
  dy[3] = 0;
  dx = vector<int>(4);
  dx[0] = 0;
  dx[1] = 0;
  dx[2] = -1;
  dx[3] = 1;
  int t;
  cin >> t;
  for (int i = 0; i < t; i++){
    int W, H;
    cin >> W >> H;
    string S;
    cin >> S;
    int M;
    cin >> M;
    vector<int> x1(M), y1(M), x2(M), y2(M);
    for (int j = 0; j < M; j++){
      cin >> x1[j] >> y1[j] >> x2[j] >> y2[j];
      if (x1[j] > x2[j]){
        swap(x1[j], x2[j]);
      }
      if (y1[j] > y2[j]){
        swap(y1[j], y2[j]);
      }
    }
    vector<vector<vector<bool>>> E(H, vector<vector<bool>>(W, vector<bool>(4, true)));
    for (int j = 0; j < W; j++){
      E[0][j][0] = false;
      E[H - 1][j][1] = false;
    }
    for (int j = 0; j < H; j++){
      E[j][0][2] = false;
      E[j][W - 1][3] = false;
    }
    for (int j = 0; j < M; j++){
      if (x1[j] == x2[j]){
        E[y1[j]][x1[j]][1] = false;
        E[y2[j]][x1[j]][0] = false;
      }
      if (y1[j] == y2[j]){
        E[y1[j]][x1[j]][3] = false;
        E[y1[j]][x2[j]][2] = false;
      }
    }
    int N = S.size();
    bool ok = true;
    int cy = 0, cx = 0;
    for (int j = 0; j < N; j++){
      int ny = cy, nx = cx;
      if (S[j] == 'U'){
        ny++;
        if (!E[cy][cx][1]){
          ok = false;
        }
      }
      if (S[j] == 'D'){
        ny--;
        if (!E[cy][cx][0]){
          ok = false;
        }
      }
      if (S[j] == 'L'){
        nx--;
        if (!E[cy][cx][2]){
          ok = false;
        }
      }
      if (S[j] == 'R'){
        nx++;
        if (!E[cy][cx][3]){
          ok = false;
        }
      }
      cy = ny;
      cx = nx;
    }
    if (!ok){
      cout << "INCORRECT" << endl;
    } else {
      vector<vector<int>> d1(H, vector<int>(W, INF));
      vector<vector<int>> cnt(H, vector<int>(W, 0));
      d1[0][0] = 0;
      cnt[0][0] = 1;
      queue<pair<int, int>> Q1;
      Q1.push(make_pair(0, 0));
      while (!Q1.empty()){
        int y = Q1.front().first;
        int x = Q1.front().second;
        Q1.pop();
        for (int j = 0; j < 4; j++){
          if (E[y][x][j]){
            int y2 = y + dy[j];
            int x2 = x + dx[j];
            if (d1[y2][x2] == INF){
              d1[y2][x2] = d1[y][x] + 1;
              cnt[y2][x2] = cnt[y][x];
              Q1.push(make_pair(y2, x2));
            } else if (d1[y2][x2] == d1[y][x] + 1){
              cnt[y2][x2] = min(cnt[y2][x2] + cnt[y][x], 2);
            }
          }
        }
      }
      if (cnt[cy][cx] >= 2){
        cout << "INCORRECT" << endl;
      } else if (d1[cy][cx] != N){
        cout << "INCORRECT" << endl;
      } else {
        vector<vector<int>> d2(H, vector<int>(W, INF));
        d2[cy][cx] = 0;
        queue<pair<int, int>> Q2;
        Q2.push(make_pair(cy, cx));
        while (!Q2.empty()){
          int y = Q2.front().first;
          int x = Q2.front().second;
          Q2.pop();
          for (int j = 0; j < 4; j++){
            if (E[y][x][j]){
              int y2 = y + dy[j];
              int x2 = x + dx[j];
              if (d2[y2][x2] == INF){
                d2[y2][x2] = d2[y][x] + 1;
                Q2.push(make_pair(y2, x2));
              }
            }
          }
        }
        for (int j = 0; j < M; j++){
          if (d1[y1[j]][x1[j]] + d2[y2[j]][x2[j]] + 1 > N && d1[y2[j]][x2[j]] + d2[y1[j]][x1[j]] + 1 > N){
            ok = false;
          }
        }
        if (!ok){
          cout << "INCORRECT" << endl;
        } else {
          cout << "CORRECT" << endl;
        }
      }
    }
  }
}