問題
問題文
古代すぬけ国では, AtCoder 社長「高橋君」の権威を高めるために, ピラミッドが建てられていた.
ピラミッドには 中心座標 $(C_X,C_Y)$ と 高さ $H$ が定まっており, 座標 $(X,Y)$ の高度は ${\rm max}(H−|X−C_X|−|Y−C_Y|,0)$ であった.
探検家の青木君は, このピラミッドの中心座標と高さを求めるために調査を行った. その結果, 次のような情報が得られた.
・$C_X,C_Y$ は $0$ 以上 $100$ 以下の整数で, $H$ は $1$ 以上の整数であった.
・上記と別に $N$ 個の情報が得られた. そのうち $i$ 個目の情報は, 「座標
$(x_i,y_i)$ の高度は $h_i$ である」
この情報は, ピラミッドの中心座標と高さを特定するのに十分であった. 情報を手掛かりに, これらの値を求めなさい.
制約
・$N$ は $1$ 以上 $100$ 以下の整数
・$x_i,y_i$ は $0$ 以上 $100$ 以下の整数
・$h_i$ は $0$ 以上 $10^9$ 以下の整数
・$N$ 個の座標 $(x_1,y_1),(x_2,y_2),(x_3,y_3),\ldots,(x_N,y_N)$ はすべて異なる
・ピラミッドの中心座標と高さをちょうど $1$ つに特定することができる
収録されている問題セット
回答
回答1 (AC)
ピラミッドの中心座標 $(C_X,C_Y)$ とヒントの個数 $N$ はすべて $1$ 以上 $100$ 以下なので、各 $(C_X,C_Y)$ に対し $N$ 個のヒントが当てはまるかどうかをチェックしていくことで解を求められそうです。
問題はピラミッドの高さ $H$ です。あいにく高さは $0 \le H \le 10^9$ となっているため、全検索は不可能です。そこで $H$ は計算で求める必要があります。問題文で $H$ を使っているのは、高度を求める式 ${\rm max}(H−|X−C_X|−|Y−C_Y|,0)$ だけです。座標 $(x_i,y_i)$ の高度 $h_i$ は $h_i={\rm max}(H−|x_i−C_X|−|y_i−C_Y|,0)$ によって求められるので、$h_i > 0$ ならば $h_i=H−|x_i−C_X|−|y_i−C_Y|$ となり、$C_X,C_y,x_i,y_i,h_i$ から $H$ を求めることができます。ただし、$h_i>0$ となっている $i$ を事前に見つけておく必要があります。
以上の考察をまとめたコードは以下のようになりました。繰返し回数は $C_X C_Y N \le 10^6$ なので、十分処理可能です。
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
int index;
vector<int> x(n), y(n), h(n);
for ( int i=0; i<n; i++ ) {
cin >> x.at(i) >> y.at(i) >> h.at(i);
if ( h.at(i)!=0 ) {
index = i;
}
}
for ( int cx=0; cx<=100; cx++ ) {
for ( int cy=0; cy<=100; cy++ ) {
int ch = h.at(index)+abs(x.at(index)-cx)+abs(y.at(index)-cy);
for (int i=0; i<n; i++ ) {
if ( max(ch-abs(x.at(i)-cx)-abs(y.at(i)-cy),0)!=h.at(i) ) {
break;
}
if ( i==n-1 ) {
cout << cx << ' ' << cy << ' ' << ch << endl;
}
}
}
}
}
調べたこと
AtCoder の解説 → ユーザ解説
回答1と同じ方針でした。
AtCoder の解説 → コンテスト全体の解説
回答1と同じ方針でした。$h_i > 0$ となる $i$ が存在することが指摘されていました。
リンク
前後の記事
- 前の記事 → AtCoderログ：0082 - 214 C