ABC112 C - Pyramid
ABC112 C - Pyramid
ピラミッドの最高点を決める問題。
問題は以下。
〜考え方〜
グリッドの問題をやった後だったからか、制約含めて見てみて「座標を全探索する」という発想が素直に浮かんできた。まあ本番解いてるし(ACしてないけど)他の人の感想からなんとなく予想はついてたけど、実装までスムーズにいけたので少し成長を感じられて嬉しかった。
最初提出していたコードでは、少し実装が複雑になってしまったが、解説をチラ見して、
中心座標をあらかじめ決めるとその高さが一意に定まるので、それを使って他の情報と計算が一致するかどうかを考える
という考え方の方が説明のmaxをうまく使えて素直なのでそちらに直したら一個だけあったWAが取れた。
一応最後に自分の実装も最後にちらっと載せておくのでなぜ通らないのか考えていただける方がいたらお願いしたいです笑
コードは以下。
Submission #4240237 - AtCoder Beginner Contest 112
#include <bits/stdc++.h> using namespace std; #define rep(i,N) for(int i=0;i<int(N);++i) int main() { int N,ansX,ansY,ansH,xt,yt,ht,Ht; cin>>N; vector<int> x(N),y(N),h(N); rep(i,N){ cin>>x[i]>>y[i]>>h[i]; if(h[i]!=0){ xt=x[i],yt=y[i],ht=h[i]; } } rep(X,101)rep(Y,101){ Ht = ht+abs(xt-X)+abs(yt-Y); int cnt = 0; rep(i,N){ if(h[i]==max(0,Ht-abs(X-x[i])-abs(Y-y[i]))){ cnt++; } } if(cnt==N){ ansX=X,ansY=Y,ansH=Ht; break; } } cout<<ansX<<' '<<ansY<<' '<<ansH<<endl; }
↓~失敗の実装~
Submission #4240187 - AtCoder Beginner Contest 112
#include <bits/stdc++.h> using namespace std; #define rep(i,N) for(int i=0;i<int(N);++i) int main() { int N,ansX,ansY,ansH,xt,yt,ht,H1,Ht; cin>>N; vector<int> x(N),y(N),h(N); rep(i,N){ cin>>x[i]>>y[i]>>h[i]; if(h[i]!=0){ xt=x[i],yt=y[i],ht=h[i]; } } rep(X,101)rep(Y,101){ Ht = ht+abs(xt-X)+abs(yt-Y); int cnt = 0; rep(i,N){ if(h[i]==0)cnt++; else{ H1=h[i]+abs(x[i]-X)+abs(y[i]-Y); if(H1==Ht)cnt++; } } if(cnt==N){ ansX=X,ansY=Y,ansH=Ht; break; } } cout<<ansX<<' '<<ansY<<' '<<ansH<<endl; }