AtCoder ABC 112 C - Pyramid (緑色, 300 点)

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;
}