AtCoder ではとても珍しい、注意して考えることの多い、重めの全探索な問題
問題概要
ピラミッドの高さを当てたい。
ピラミッドには 中心座標 (Cx, Cy) と 高さ H が定まっており, 座標 (X, Y) の高度は max(H−|X−CX|−|Y−CY|, 0) である。
また、0 <= Cx, Cy <= 100 であることがわかっている。
今、N 個の以下のような情報が与えられる。ピラミッドの高さを特定せよ。なお、ピラミッドの高さが一意に特定できることが保証されている。
- xi, yi, hi: 座標 (xi, yi) におけるピラミッドの高度は hi
制約
- N は 1 以上 100 以下の整数
- xi, yi は 0 以上 100 以下の整数
- hi は 0 以上 以下の整数
考えたこと
ICPC ではありそうな問題。一瞬、数学的に考えたくなるのだがすごくややこしい。そうなるともう全探索だろうという感じ。しかも 0 <= Cx, Cy <= 100 という思わせぶりな制約までついている。
なので、Cx, Cy を全探索するのはきっとそれはそう
次に、Cx, Cy を決め打ったら、高さが決まらないかを考えてみる。そうすると
- ある i について hi > 0 だったら、ピラミッドの高さは、hi + |xi - Cx| + |yi - Cy|
になることがわかる。ここで注意点として、hi = 0 だと、ピラミッドの裾野は全部高さが 0 なため、ピラミッドの高さがわからない。
さて、もし hi > 0 になるような i があるなら、問題は解決していて、ピラミッドの高さが決まるので、それで矛盾がないかを check すればいい。
すべての i に対して hi = 0 となる場合が問題であるが、そんなことは起こりえないことに気づく。なぜなら問題として「ピラミッドの高さが一意に特定できる」というのがあるから。すべての i に対して hi = 0 だったら、ピラミッドの高さは複数ありえてしまう。
#include <iostream> #include <vector> #include <cmath> using namespace std; int main() { int N; cin >> N; vector<long long> vx(N), vy(N), vh(N); int si = -1; for (int i = 0; i < N; ++i) { cin >> vx[i] >> vy[i] >> vh[i]; if (vh[i] > 0) si = i; } long long resx = -1, resy = -1, resh = -1; for (long long x = 0; x <= 100; ++x) { for (long long y = 0; y <= 100; ++y) { long long h = vh[si] + abs(x - vx[si]) + abs(y - vy[si]); bool ok = true; for (int i = 0; i < N; ++i) { if (vh[i] > 0 && h - vh[i] != abs(x - vx[i]) + abs(y - vy[i])) ok = false; if (vh[i] == 0 && h > abs(x - vx[i]) + abs(y - vy[i])) ok = false; } if (ok) resx = x, resy = y, resh = h; } } cout << resx << " " << resy << " " << resh << endl; }