C - Pyramid
はじめに
競技プログラミング、AtCoder Beginner Contest 112
C - Pyramid
言語はC#
何かあればTwitter→@pirorirori_n712まで
問題
問題文
古代すぬけ国では, AtCoder 社長「高橋君」の権威を高めるために, ピラミッドが建てられていた. ピラミッドには 中心座標 (CX,CY)と 高さ Hが定まっており, 座標 (X,Y)の高度は max(H−|X−CX|−|Y−CY|,0)であった. 探検家の青木君は, このピラミッドの中心座標と高さを求めるために調査を行った. その結果, 次のような情報が得られた. ・CX,CYは 0以上100以下の整数で, Hは 1以上の整数であった. ・上記と別に N個の情報が得られた. そのうち i個目の情報は, 「座標 (xi,yi)の高度は hiである」 この情報は, ピラミッドの中心座標と高さを特定するのに十分であった. 情報を手掛かりに, これらの値を求めなさい.
制約
・Nは1以上 100以下の整数 ・xi,yiは0以上100以下の整数 ・hiは0以上10~9以下の整数 ・N個の座標(x1,y1),(x2,y2),(x3,y3),...,(xN,yN)はすべて異なる ・ピラミッドの中心座標と高さをちょうど1つに特定することができる
入力
入力は以下の形式で標準入力から与えられる。 N x1 y1 h1 x2 y2 h2 x3 y3 h3 : xN yN hN
出力
特定した中心座標と高さを表す整数CX,CY,Hを空白区切りで, 1 行に出力しなさい.
解き方
こちらの解き方を参考にしています。
https://img.atcoder.jp/abc112/editorial.pdf
atcoder.jp
まず問題文の中で注目するポイントは以下の部分です。
座標 (X,Y)の高度は max(H−|X−CX|−|Y−CY|,0)
入力から座標(X,Y)とその高度を得られるので
この式を変形すれば
ピラミッド全体の高さであるHを出すことができそうです。
使えそうなので、とりあえず変形しておきます。
座標 (X,Y)の高度をhとすると、以下のように変形できます。
h=max(H−|X−CX|−|Y−CY|,0)
0の場合はhも0になることは分かるので、ひとまずのけます。
h=H−|X−CX|−|Y−CY|
-H=-h−|X−CX|−|Y−CY|
-H×(-1)=(-h−|X−CX|−|Y−CY|)×(-1)
H=h+|X−CX|+|Y−CY|
これで高さを出す式に変形できました。
次に問題文の以下の部分に注目します。
（C問題は問題文や制約の中で数が小さいものがあれば、
そこを基準に考えていくと答えに辿りつけることが多い気がします。）
CX,CYは 0以上100以下の整数で, Hは 1以上の整数であった.
頂点のCX、CYは0以上100以下ということは
全てのパターン（組み合わせ）を考えても
101×101通りしか存在しないことになります。
ここから、
中心座標を一つずつ列挙していきながら
入力されたもののうちhiが0以外のもの
（hiが0だと中心座標が変わっても常に高さが0になってしまい、正しい答えが得られない）から
一つ（xi yi hi（iは任意））をとって、
先ほど変形した式で高さ（H）を求め
その高さ（H）を使って求めた
それぞれの頂点(x1 y1,x2 y2,…,xN yN)の高度（max(H−|X−CX|−|Y−CY|,0)）が
他の入力されたもの(h1,h2,…,hN)と一致すれば
その時点での頂点と求めた高さが
答えになると言えそうです。
文章では分かりにくいので、
コードにすると以下のようなイメージです。
//中心座標をループで全パターン列挙
for (int i = 0; i <= 100; ++i)
{
for (int j = 0; j <= 100; ++j)
{
//基準とする入力を（X,Y,H）（Hは0ではない）とする。
//基準の入力から高さを求める。
var height = H + Math.Abs(X - i) + Math.Abs(Y - j);
//全ての高度が一致するかどうか
var isCorrect = true;
//上で出した高さから、それぞれの入力の高度を求め
//実際に入力された高度と数が一致するかを確認する。
for (int k = 0; k < N; ++k)
{
if (Math.Max(0, height - Math.Abs(xi - i) - Math.Abs(yi - j)) != hi)
{
//一致しないので、この中心座標は間違い
isCorrect = false;
}
}
if (isCorrect)
{
//全ての高度が一致したので、この中心座標は正しい
}
}
}
後はすべての高度が一致した時点で、
その時点の中心座標と求めた高さを出力すれば完了です。
全体のコード
using System;
using System.Linq;
using System.Collections.Generic;
class Cmondai
{
static void Main()
{
var N = Int32.Parse(Console.ReadLine());
var list = new List<long[]>();
for (int i=0;i<N;++i)
{
var xyh = Console.ReadLine().Split(' ').Select(num => Int64.Parse(num)).ToArray();
var x = xyh[0];
var y = xyh[1];
var h = xyh[2];
list.Add(new long[3] { x, y, h });
}
//入力されたものの中で高度が0以外のものから適当に「基準」を一つ選ぶ
var kizyun = list.Where(x=>x[2]!=0).First();
//中心座標をループで一つずつ列挙
for (int i=0;i<=100;++i)
{
for (int j=0;j<=100;++j)
{
//「基準」から高さを求める
var height = kizyun[2]+ Math.Abs(kizyun[0] - i) + Math.Abs(kizyun[1] - j);
//全ての高度が一致するかどうか
var isCorrect = true;
//全ての入力で高度が一致するかどうかを調べる
for (int k = 0; k < N; ++k)
{
//問題文にある条件式に「基準」から求めた高さと入力された座標をそのまま入れて、高度を求める
//計算結果と入力された高度が一致するかどうか
if (Math.Max(0,height- Math.Abs(list[k][0] - i) - Math.Abs(list[k][1] - j)) != list[k][2])
{
//一つでも一致しなければ、中心座標は正しくないので次の中心座標にうつる
isCorrect = false;
break;
}
}
//全ての高度が一致したら中心座標は正しいので、出力する
if (isCorrect)
{
Console.WriteLine($"{i} {j} {height}");
return;
}
}
}
}
}
