zukaABCをコツコツ解いていきます。
本記事は，管理人の競技プロ精進日記としてログを取ったものです。モチベーションを爆上げするために，積極的にアウトプットしていく作戦です。
これから競技プログラミングを始めようと考えている人や，なんとなく敷居が高いと感じている人の参考になれば嬉しく思います。その他の記事は以下をご覧ください。
本記事の概要
Atcoderで初心者用のコンテストとして開催されているAtcoder Beginner Contest（通称ABC）を解いていくものです。今回はABC112-C「Pyramid」です。
ポイント
考えられる頂点の座標が
ポイントは，高度を求める
の条件式です。直感的に捉えれば，頂点から離れた分だけ線形に高度が下がっていきますよということを表しています。また，0とのmaxを取っていますので，頂点から離れすぎてしまって高度が負の値をとる場合には，そこは0になります。
この問題のポイントは，このmaxを消去してあげる点にあります。後ほど説明を加えていきます。
また，用語も少しややこしいですね。「高さ」というのはピラミッドの頂点の高さを表し，「高度」というのはピラミッドの各座標の高さを表します。つまり「頂点座標の高度が高さ」ということになります。高度の最大値が高さと言ってもOKでしょう。
さて，全探索はどのように行えば良いのでしょうか。全探索のforループを考えてみましょう。
// 頂点のx座標
rep(x, 101){
// 頂点のy座標
rep(y, 101){
// 調査されたN個の座標が条件を満たしているかどうかを確認
rep(i, N){
// 高度を求める式に与えられた座標を当てはめたときに条件が成立するかを判断
}
}
}このような形になりますね。
注目して欲しいのは，頂点のx座標とy座標に関してforループを回しているだけで，高さ
そこで，高さ
補足ですが，「調査された観測値の中で
さらに「高度を求める式に与えられた座標を当てはめたときに条件が成立するかを判断」する箇所でも，
まとめると，全探索部分はこんな感じになります。
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;
}
コメント