AtCoder Beginner Contest 112 C - 今日から始める競プロ日記
はじめに
chokudaiさんの今日の一問を解いてみた。
ABC112のC問題。
前に見たことある問題だけど、 その時は解けなかったので再挑戦ということになる。
今日の一門はPyramid!300点問題ながら参加者の多くを苦しめた一問。何度か言及してるので、解いてる人も多そうな問題かな。https://t.co/YQYRDqrt7t#chokudai今日の一問
— chokudai(高橋 直大)🍆🍡🌸 (@chokudai) 2019年8月21日
C - Pyramid
ピラミッドが一つある。
ピラミッドには中心座標(Cx, Cy)と高さHが定まっている(入力で与えられる訳ではない)。
また、座標(x, y)における高さは max(H-|x-Cx|-|y-Cy|, 0)で求められる。
中心座標と高さの条件は
0 <= Cx, Cy <= 100 1 <= H
である。
N個の入力の組、座標(xi, yi)と高さhiが与えられたとき、 中心座標(Cx, Cy)と高さHを求めよ。
解き方
中心座標の可能性がある座標を全探索する。
座標(x, y)の条件は以下の通り。
0 <= x <= 100 0 <= y <= 100
つまり、縦101マス、横101マス
101*101=10201
より合計10201マスを全探索する。
各座標でやること
- 入力の情報から
H = h + |x-Cx| + |y-Cy|
の計算をして高さを求める - その高さがすべての入力の情報と合致するかどうか判定する
すべての入力情報と合致した座標と高さが答えとなる
気を付ける点として、 入力のhは0の場合があるということ。
h=0というのは高さ0というよりは、 そこにピラミッドはないということであるので、 高さ=0のつもりで計算するとおかしくなる(たぶん)。
コード
公式解説のサンプルコードのURLを貼っておきます。
おわりに
解き終わってみれば簡単な問題だったけど、 時間がかかってしまった。