今日は実家の滋賀に帰省中、ねむーです。

今回はAtCoder112(https://atcoder.jp/contests/abc112)にて開催されました、AtCoder Beginner Contest112の第3問「C - Pyramid」の問題と僕との戦闘記です。

0.はじめに

今回も、プログラミング言語はC#を使用しています。

1.問題文

古代すぬけ国では, AtCoder 社長「高橋君」の権威を高めるために, ピラミッドが建てられていた.

ピラミッドには中心座標 ( C X , C Y ) と高さ H が定まっており, 座標 ( X , Y ) の高度は m a x ( H − | X − C X | − | Y − C Y | , 0 ) であった.

探検家の青木君は, このピラミッドの中心座標と高さを求めるために調査を行った. その結果, 次のような情報が得られた.

C X , C Y は 0 以上 100 以下の整数で, H は 1 以上の整数であった.

上記と別に N 個の情報が得られた.

そのうち i 個目の情報は, 「座標 ( x i , y i ) の高度は h i である」この情報は, ピラミッドの中心座標と高さを特定するのに十分であった.

情報を手掛かりに, これらの値を求めなさい.

2.入力例

入力

出力

2 2 6

この場合, 中心座標は ( 2 , 2 ) , 高さは 6 と特定することができる.

3.初見の感想

入力を高さの順にソートしたい
入力点から隣に進むたびに1増やす全探索を行い、最大値をとる方策は思いついた(TLEになりそうだが…)

4.学びポイント

入力点から進むのではなく、頂点候補を固定してそこから入力点と照合して判定を行う方策をとる
高さは0より小さくならないので、その条件も加える

5.コードの簡単な解説

入力は構造体でリスト保管します

    struct Point
    {
        public int x;
        public int y;
        public int h;
        public Point(int x ,int y,int h)
        {
            this.x = x;
            this.y = y;
            this.h = h;
        }
    }
    static void Main(string[] args)
    {
        int N = int.Parse(System.Console.ReadLine());
        var list = new List<Point>();
        for (int i = 0; i < N; i++)
        {
            string[] temp = System.Console.ReadLine().Split(' ');
            int x = int.Parse(temp[0]);
            int y = int.Parse(temp[1]);
            int h = int.Parse(temp[2]);
            list.Add(new Point(x, y, h));
        }

頂点の位置で全探索します

        for(int cx = 0; cx <= 100; cx++)
        {
            for (int cy = 0; cy <= 100; cy++)
            {
                bool flag=true;
                int ch = -1;
                int hMax = int.MaxValue;
                for(int i = 0; i < N; i++)
                {
                    int x = list[i].x;
                    int y = list[i].y;
                    int h = list[i].h;
                    int d = Math.Abs(cx - x) + Math.Abs(cy - y);
                    if (h > 0)
                    {
                        int buf = h + d;
                        if (ch > 0 && ch != buf)
                        {
                            flag = false;
                            break;
                        }
                        else
                        {
                            ch = buf;
                        }

高さの値が0以上になるよう判定します

                   else
                    {
                        hMax = Math.Min(hMax, d);
                    }
                }
                if (flag && ch <= hMax)
                {
                    Console.WriteLine($"{cx} {cy} {ch}");
                }

6.全コード

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    struct Point
    {
        public int x;
        public int y;
        public int h;
        public Point(int x ,int y,int h)
        {
            this.x = x;
            this.y = y;
            this.h = h;
        }
    }
    static void Main(string[] args)
    {
        int N = int.Parse(System.Console.ReadLine());
        var list = new List<Point>();
        for (int i = 0; i < N; i++)
        {
            string[] temp = System.Console.ReadLine().Split(' ');
            int x = int.Parse(temp[0]);
            int y = int.Parse(temp[1]);
            int h = int.Parse(temp[2]);
            list.Add(new Point(x, y, h));
        }
        for(int cx = 0; cx <= 100; cx++)
        {
            for (int cy = 0; cy <= 100; cy++)
            {
                bool flag=true;
                int ch = -1;
                int hMax = int.MaxValue;
                for(int i = 0; i < N; i++)
                {
                    int x = list[i].x;
                    int y = list[i].y;
                    int h = list[i].h;
                    int d = Math.Abs(cx - x) + Math.Abs(cy - y);
                    if (h > 0)
                    {
                        int buf = h + d;
                        if (ch > 0 && ch != buf)
                        {
                            flag = false;
                            break;
                        }
                        else
                        {
                            ch = buf;
                        }
                    }
                    else
                    {
                        hMax = Math.Min(hMax, d);
                    }
                }
                if (flag && ch <= hMax)
                {
                    Console.WriteLine($"{cx} {cy} {ch}");
                }
            }
        }
    }
}

7.最後に

選択肢が少ないもので全探索！

肝に銘じておかなければ…

ねむーの日記~AtCoderな日々~

福岡に住むプログラミング好きのブログです！

【プログラミングコンテスト】AtCoder Beginner Contest 112③