zukaABCをコツコツ解いていきます。
本記事は，管理人の競技プロ精進日記としてログを取ったものです。モチベーションを爆上げするために，積極的にアウトプットしていく作戦です。
これから競技プログラミングを始めようと考えている人や，なんとなく敷居が高いと感じている人の参考になれば嬉しく思います。その他の記事は以下をご覧ください。
本記事の概要
Atcoderで初心者用のコンテストとして開催されているAtcoder Beginner Contest（通称ABC）を解いていくものです。今回はABC112-C「Pyramid」です。
ポイント
考えられる頂点の座標が$101 \times 101 = 10201$であり，調査された地点が高々100地点ですので，全探索を行っても計算量は$O(10201\times 100)=O(10^6)$です。大人しく全探索を行ってしまおうという問題です。
ポイントは，高度を求める
\max \left(H-\left|X-C_{X}\right|-\left|Y-C_{Y}\right|, 0\right)
\end{align}
の条件式です。直感的に捉えれば，頂点から離れた分だけ線形に高度が下がっていきますよということを表しています。また，0とのmaxを取っていますので，頂点から離れすぎてしまって高度が負の値をとる場合には，そこは0になります。
この問題のポイントは，このmaxを消去してあげる点にあります。後ほど説明を加えていきます。
また，用語も少しややこしいですね。「高さ」というのはピラミッドの頂点の高さを表し，「高度」というのはピラミッドの各座標の高さを表します。つまり「頂点座標の高度が高さ」ということになります。高度の最大値が高さと言ってもOKでしょう。
さて，全探索はどのように行えば良いのでしょうか。全探索のforループを考えてみましょう。
// 頂点のx座標
rep(x, 101){
// 頂点のy座標
rep(y, 101){
// 調査されたN個の座標が条件を満たしているかどうかを確認
rep(i, N){
// 高度を求める式に与えられた座標を当てはめたときに条件が成立するかを判断
}
}
}このような形になりますね。
注目して欲しいのは，頂点のx座標とy座標に関してforループを回しているだけで，高さ$H$に関する初期値が設定されていないという点です。高さ$H$の初期値がなければ，それぞれの調査された座標に対して高度の条件式が成り立っているかどうかを判断することができません。
そこで，高さ$H$に初期値を与えます。これは，調査された観測値の中で$h_i > 0$となる座標に関して$H-\left|X-C_{X}\right|-\left|Y-C_{Y}\right|$を計算すればOKです。なぜなら，$h_i > 0$であれば，maxを取ったときに必ず$H-\left|X-C_{X}\right|-\left|Y-C_{Y}\right|$側の値が採用されるからです。こうすれば，maxを消去することができます。
補足ですが，「調査された観測値の中で$h_i > 0$となる座標」が見つからずに初期値が定まらないということはあり得ません。なぜなら，もし全ての調査された観測値において$h_i=0$であれば，適当な座標を頂点とする高さ1のピラミッドが高さの条件式を全て満たしてしまい，ピラミッドが一意に定まらなくなってしまうからです。
さらに「高度を求める式に与えられた座標を当てはめたときに条件が成立するかを判断」する箇所でも，$h_i>0$か$h_i=0$かで場合分けして高度の条件式のmaxを消去してあげる必要があります。
まとめると，全探索部分はこんな感じになります。
int h;
int ans_x, ans_y, ans_h;
rep(x, 101){
rep(y, 101){
// initは高度が0より大きい地点を表す
h = H[init] + abs(X[init] - x) + abs(Y[init] - y);
// 条件式を満たしているかどうかのチェック
bool check = true;
rep(i, N){
// maxを消去する
if (H[i] > 0){
if (h - abs(X[i] - x) - abs(Y[i] - y) != H[i]) check = false;
}
else {
if (h - abs(X[i] - x) - abs(Y[i] - y) > 0) check = false;
}
}
// 答えは一意に定まる
if (check){
ans_x = x;
ans_y = y;
ans_h = h;
}
}
}maxの消去
実装
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
using namespace std;
typedef long long ll;
int N;
int X[110];
int Y[110];
int H[110];
int main(){
cin >> N;
rep(i, N) cin >> X[i] >> Y[i] >> H[i];
int init;
rep(i, N){
if (H[i] > 0) init = i;
}
int h;
int ans_x, ans_y, ans_h;
rep(x, 101){
rep(y, 101){
// initは高度が0より大きい地点を表す
h = H[init] + abs(X[init] - x) + abs(Y[init] - y);
// 条件式を満たしているかどうかのチェック
bool check = true;
rep(i, N){
// maxを消去する
if (H[i] > 0){
if (h - abs(X[i] - x) - abs(Y[i] - y) != H[i]) check = false;
}
else {
if (h - abs(X[i] - x) - abs(Y[i] - y) > 0) check = false;
}
}
// 答えは一意に定まる
if (check){
ans_x = x;
ans_y = y;
ans_h = h;
}
}
}
cout << ans_x << " " << ans_y << " " << ans_h << endl;
}
コメント