Atcoder解いてみた ABC 112 C - Pyramid

問題はこちら

最初に書いたコード

考え方

• cx, cy, Hをforで回し、max(H - abs(x[i] - cx) - abs(y[i] - cy), 0)でhを計算する
• hとHが一致した場合、求める解の候補となるcx,cy,Hをベクターに追加していく
• 上記の作業を入力Nパターンに対して行う
• Nパターンの入力から求めた解の候補(cx,cy,Hの群)からNパターンで共通する解を求める

コード

# include <iostream>
# include <map>
#include <algorithm>
#include <vector>
#include <cmath>

using namespace std;


struct piramInfo {
    int cx;
    int cy;
    int h;
    int vote;
};

int main()
{
    int n;
    int x[100];
    int y[100];
    int h[100];

    std::vector<piramInfo> vecPiramInfo;

    cin >> n;

    piramInfo* pPiramInfo = vecPiramInfo.data();
    for (int i = 0; i < n; i++) {
        cin >> x[i];
        cin >> y[i];
        cin >> h[i];
    }

    for (int i = 0; i < n; i++) {
        for (int cx = 0; cx <= 100; cx++) {
            for (int cy = 0; cy <= 100; cy++) {
                for (int H = 0; H < 1000; H++) {
                    int tmph = max(H - abs(x[i] - cx) - abs(y[i] - cy), 0);
                    if (tmph == h[i] && H >= 1 && h[i] != 0) {
                        vecPiramInfo.push_back({ cx,cy,H,0 }); // 解の候補は格納する
                    }
                }
            }
        }
    }

    for (int i = 0; i < vecPiramInfo.size(); i++) {
        for (int j = 0; j < vecPiramInfo.size(); j++) {
            if (i != j) {
                if (vecPiramInfo[i].cx == vecPiramInfo[j].cx && vecPiramInfo[i].cy == vecPiramInfo[j].cy && vecPiramInfo[i].h == vecPiramInfo[j].h) {
                    vecPiramInfo[i].vote++;
                }
            }
        }
    }

    for (int i = 0; i < vecPiramInfo.size(); i++) {
        if (vecPiramInfo[i].vote == (n - 1)) {
            std::cout << vecPiramInfo[i].cx << " " << vecPiramInfo[i].cy << " " << vecPiramInfo[i].h << std::endl;
            break;
        }
    }

    return 0;
}

結果

一部のパターンでは正解するが、大半で制限時間オーバー

コードの良くなかった点

• 1以上の整数であるHでループを回しているところ
• vectorにpushしまくっているところ

この時点で一旦模範回答を確認した

模範回答を確認し、書いたコード

考え方

• cx,cyは探索してる
• 座標(X,Y)の高度の式を変形し、Hを求めるようにする
  ※この時、h=0の時は、座標(X,Y)が不明(hは、0以上の値しかとらないため)なため、h=0の時には、Hを求めない
  ※Hはただ1つの値しか取らない(この性質に注目することが重要!)
• 求めたHを用いて逆にhを求めて、入力したh一致と一致するかの確認を、Nパターンで行う
  →Nパターン全てで一致したときのcx,cy,Hを出力

上記により、1以上の整数であるHでループを回すこと・vectorにpushしまくることが不要になることに加えて、コードもシンプルに

コード

# include <iostream>
# include <map>
#include <algorithm>
#include <vector>
#include <cmath>

using namespace std;

int main()
{
    int n;
    int x[100];
    int y[100];
    int h[100];

    cin >> n;

    for (int i = 0; i < n; i++) {
        cin >> x[i];
        cin >> y[i];
        cin >> h[i];
    }


    for (int cx = 0; cx <= 100; cx++) {
        for (int cy = 0; cy <= 100; cy++) {
            // 入力されたパラメータx,y,hと、探索パラメータcx,cyからHを求める h=0の時には、Hを求めない
            int H = 0;
            for (int i = 0; i < n; i++) {
                if (h[i] != 0) H = h[i] + abs(x[i] - cx) + abs(y[i] - cy);
            }

            // 求めたHを使って算出したhが、N個の点で一致するか確認する
            bool isOk = true;
            for (int i = 0; i < n; i++) {
                if (h[i] != max(H - abs(x[i] - cx) - abs(y[i] - cy),0)) {
                    isOk = false;
                }
            }

            if(isOk){
                std::cout << cx << " " << cy << " " << H << std::endl;
                break;
            }

        }
    }

    return 0;
}