ICPC国内予選2008 解答

Eではspaghetti source(http://www.prefield.com/algorithm/index.html)の幾何ライブラリを拝借しています。

A

#include <iostream>

using namespace std;

main() {
  int n, m;
  while (cin >> n >> m, n || m) {
    int t[n], h[m], tsum = 0, hsum = 0;
    for (int i = 0; i < n; i++) cin >> t[i], tsum += t[i];
    for (int i = 0; i < m; i++) cin >> h[i], hsum += h[i];

    int MIN = INT_MAX, _t, _h;
    for (int i = 0; i < n; i++)
      for (int j = 0; j < m; j++)
        if (tsum - t[i] + h[j] == hsum - h[j] + t[i] && MIN > t[i] + h[j])
          MIN = t[i] + h[j], _t = t[i], _h = h[j];

    if (MIN == INT_MAX) cout << -1 << endl;
    else cout << _t << " " << _h << endl;
  }
}

B

#include <iostream>
#include <vector>
#define MAX 300000

using namespace std;

int p[MAX + 1] = {0};
vector<int> v;

main() {
  for (int i = 6; i <= MAX; i++) {
    if ((i % 7 == 1 || i % 7 == 6) && !p[i]) {
      v.push_back(i);
      for (int j = i + i; j <= MAX; j += i) {
        p[j] = 1;
      }
    }
  }

  int n;
  while (cin >> n, n != 1) {
    cout << n << ":";
    for (int i = 0; i < v.size() && v[i] <= n; i++) {
      if (n % v[i] == 0) {
        cout << " " << v[i];
      }
    }
    cout << endl;
  }
}

C

#include <iostream>

using namespace std;

int P, Q, R;

typedef pair<int, int> result;

result formula (const string &s, int p) {
  if (isdigit(s[p])) return result(s[p] - '0', p + 1);
  if (isalpha(s[p])) return result(s[p] == 'P' ? P : s[p] == 'Q' ? Q : R, p + 1);
  if (s[p] == '-') {
    result res = formula(s, p + 1);
    return result(2 - res.first, res.second);
  }
  if (s[p] == '(') {
    result left = formula(s, p + 1);
    char op = s[left.second];
    result right = formula(s, left.second + 1);
    if (op == '*') {
      return result(min(left.first, right.first), right.second + 1);
    } else {
      return result(max(left.first, right.first), right.second + 1);
    }
  }
}

main() {
  string line;
  while (cin >> line, line != ".") {
    int sum = 0;
    for (P = 0; P <= 2; P++)
      for (Q = 0; Q <= 2; Q++)
        for (R = 0; R <= 2; R++)
          if (formula(line, 0).first == 2) sum++;
    cout << sum << endl;
  }
}

D

#include <iostream>
#include <queue>

using namespace std;

int dp[30][30][4], table[30][30], w, h, cost[4];
int dr[4] = {0, 1, 0, -1};
int dc[4] = {1, 0, -1, 0};

struct S {
  int r, c, state, w;
  bool operator < (const S &s) const { return w > s.w; }
  int &ref() { return dp[r][c][state]; }
  int &op() { return table[r][c]; }
};

inline bool valid (int r, int c) { return 0 <= r && r < h && 0 <= c && c < w; }

main() {
  while (cin >> w >> h, w || h) {
    for (int i = 0; i < h; i++)
      for (int j = 0; j < w; j++)
        cin >> table[i][j];
    for (int i = 0; i < 4; i++)
      cin >> cost[i];

    memset(dp, -1, sizeof(dp));

    S init;
    init.ref() = init.r = init.c = init.state = init.w = 0;

    priority_queue<S> que;
    que.push(init);

    while (1) {
      S here = que.top(); que.pop();
      if (here.r == h - 1 && here.c == w - 1) {
        cout << here.w << endl;
        break;
      }
      for (int i = 0; i <= 3; i++) {
        S there = here;
        there.state = (there.state + i) % 4;
        there.r += dr[there.state];
        there.c += dc[there.state];
        if (!valid(there.r, there.c)) continue;
        if (here.op() != i) there.w += cost[i];
        if (there.ref() == -1 || there.w < there.ref()) {
          there.ref() = there.w;
          que.push(there);
        }
      }
    }
  }
}

E

#include <iostream>
#include <vector>
#include <complex>
#define sq(x) ((x)*(x))

using namespace std;

const double EPS = 1e-6;

typedef complex<double> P;

double cross(const P &a, const P &b) {
  return imag(conj(a) * b);
}

double dot (const P &a, const P &b) {
  return real(conj(a) * b);
}

struct L : public vector<P> {
  L(const P &a, const P &b) {
    push_back(a); push_back(b);
  }
};

int ccw(P a, P b, P c) {
  b -= a, c -= a;
  if (cross(b, c) > 0) return +1;
  if (cross(b, c) < 0) return -1;
  if (dot(b, c) < 0) return +2;
  if (norm(b) < norm(c)) return -2;
  return 0;
}
bool intersectSS (const L &s, const L &t) {
  return ccw(s[0], s[1], t[0]) * ccw(s[0], s[1], t[1]) <= 0 &&
    ccw(t[0], t[1], s[0]) * ccw(t[0], t[1], s[1]) <= 0;
}
bool intersectSP (const L &s, const P &p) {
  return abs(s[0] - p) + abs(s[1] - p) - abs(s[1] - s[0]) < EPS;
}
P projection(const L &l, const P &p) {
  double t = dot(p - l[0], l[0] - l[1]) / norm(l[0] - l[1]);
  return l[0] + t * (l[0] - l[1]);
}
double distanceSP(const L &s, const P &p) {
  const P r = projection(s, p);
  if (intersectSP(s, r)) return abs(r - p);
  return min(abs(s[0] - p), abs(s[1] - p));
}
double distanceSS(const L &s, const L &t) {
  if (intersectSS(s, t)) return 0;
  return min(min(distanceSP(s, t[0]), distanceSP(s, t[1])),
             min(distanceSP(t, s[0]), distanceSP(t, s[1])));
}
main() {
  int N;
  while (cin >> N, N) {
    double sx, sy, ex, ey;
    cin >> sx >> sy >> ex >> ey;

    L course(P(sx, sy), P(ex, ey));
    double MINTMP = 1e50;
    for (int i = 0; i < N; i++) {
      double minx, miny, maxx, maxy, h;
      cin >> minx >> miny >> maxx >> maxy >> h;

      // 包含判定
      if (minx < min(sx, ex) && max(sx, ex) < maxx &&
          miny < min(sy, ey) && max(sy, ey) < maxy)
        MINTMP = 0;

      vector<L> lines;
      lines.push_back(L(P(maxx, miny), P(maxx, maxy)));
      lines.push_back(L(P(minx, maxy), P(maxx, maxy)));
      lines.push_back(L(P(minx, maxy), P(minx, miny)));
      lines.push_back(L(P(minx, miny), P(maxx, miny)));

      double MIN = 1e50;
      for (int j = 0; j < 4; j++) {
        MIN <?= distanceSS(course, lines[j]);
        // 交差判定
        if (intersectSS(course, lines[j])) MINTMP = 0;
      }

      MINTMP <?= MIN > h ? (sq(h) + sq(MIN)) / (2 * h) : MIN;
    }
    printf("%.4lf\n", MINTMP);
  }
}