AtCoder Beginner Contest 112

C - Pyramid

https://atcoder.jp/contests/abc112/tasks/abc112_c

方針

N 個の情報のうち、少なくとも 1 つは h が正です。もし全ての h が 0 だったと仮定すると、 調査を行わなかった地点を中心座標とする高さ H = 1 のピラミッドが全て候補になり、「ピラミッドの中心座標と高さをちょうど 1 つに特定することができる」という制約に反するからです。

中心座標を とすると、h > 0 であった情報(x, y, h) を用いて で H が1つに決まります。あとは他の N - 1 個の情報がすべて を満たすことを調べればよいです。 の取りうる範囲は 0 以上 100 以下なので、全探索できます。

ソースコード

#include <bits/stdc++.h>
using namespace std;
typedef tuple<int,int,int> tup;

int main(){
    int N;  cin >> N;
    vector<tup> infs(N);
    for(int i=0; i<N; i++){
        int x, y, h;  cin >> x >> y >> h;
        infs[i] = tup(h,x,y);
    }
    sort(infs.begin(), infs.end());

    for(int iCx=0; iCx<=100; iCx++){
        for(int iCy=0; iCy<=100; iCy++){
            int h = get<0>(infs[N-1]);
            int x = get<1>(infs[N-1]);
            int y = get<2>(infs[N-1]);

            int H = h + abs(iCx-x) + abs(iCy-y);
            bool flag = true;
            for(int i=0; i<N-1; i++){
                int hi = get<0>(infs[i]);
                int xi = get<1>(infs[i]);
                int yi = get<2>(infs[i]);
                if(hi != max( H - abs(xi-iCx) - abs(yi-iCy) ,0)){
                    flag = false;
                    break;
                }
            }
            if(flag){
                cout << iCx << " " << iCy << " " << H << endl;
            }
        }
    }
}

D - Partition

https://atcoder.jp/contests/abc112/tasks/abc112_d

方針

k が の公約数のとき、k は M の約数です。また の各項を k で割ったときの商を とすると、 となりますが、ここで の項はすべて 1 以上ですから、 すなわち となります。

以上のことより、 M の約数 k の中で を満たす最大のものを出力すればよいです。

M の約数の求め方ですが、1 から M までのすべての整数について、M を割り切るか否かを調べていくと間に合いません。k が M の約数のとき M/k も M の約数であることを用いると、探索の範囲を 1 から までに抑えることができます。

ソースコード

#include <bits/stdc++.h>
using namespace std;

int main(){
    int N, M;  cin >> N  >> M;
    vector<int> div; // M の約数を格納する。
    for(int i=1; i*i<=M; i++){
        if(M%i==0){
            div.push_back(i);
            div.push_back(M/i);
        }
    }

    sort(div.begin(), div.end());
    int n = div.size();
    for(int i=n-1; i>=0; i--){
        if(div[i] <= M/N){
            cout << div[i] << endl;
            return 0;
        }
    }
}

メモ

• 上の方法で div に値を詰めていくと、 M が平方数で と表されるとき、div に k が2個格納されてしまいます。今回は別にそれで問題ないです。