A – 高橋くんと年齢
求め方は色々あると思いますが、3つの値の中央値を最大でも最小でもない数と考えると、A+B+C-max(A,B,C)-min(A,B,C)で求められそうです。
#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
int main(){
int a,b,c;
cin>>a>>b>>c;
cout<<a+b+c-min(a,min(b,c))-max(a,max(b,c))<<endl;
}
B – 高橋くんと文字列圧縮
ランレングス圧縮を行う問題です。
同じ文字ならカウンターを1増やす、違う文字ならカウンターを0にする。等で連続文字の数をカウントし、適宜出力すればOKです。
#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
int main(){
string s;
cin>>s;
char c=s[0];
int n=1;
for(int i=1;i<s.size();i++){
if(c!=s[i]){
cout<<c<<n;
c=s[i];
n=1;
}
else n++;
}
cout<<c<<n<<endl;
}
C – 高橋くんと魔法の箱
1と同じ出力になる数字を考えた場合、2だけでなく4,8,16…と2倍されていく数字全てが対象となります。
ここで指数的に対象の数が増えるなぁ～ということを考えると、10^9が最大でも、1と同じ出力の数字はそんなに多くないことが分かります。(大体30くらい)
なので、ある入力Aと同じ出力になる数字をset等で管理していき、同じ出力出ないときだけカウンターを増やせばOKです。
#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
int main(){
int N;
cin>>N;
set<int> as;
int ans=0;
int A[N];
for(int i=0;i<N;i++){
cin>>A[i];
}
sort(A,A+N);
for(int i=0;i<N;i++){
if(as.find(A[i])==as.end()) ans++;
for(int j=A[i];j<=1000000000;j*=2){
as.insert(j);
}
}
cout<<ans<<endl;
}
Aと同じ数字ですが、*2だけでなく/2も考えなければいけません。
私は事前にソートすることで、*2だけ考慮しても問題ないようにしました。(重複チェックの対象となる後に出る数字が、今見ている数字より大きい数のため、小さい方向は考えなくて良くなる)
D – 高橋くんと木の直径
質問するタイプの珍しい問題です。
木の直径は、以下の2手順で求められます。
- 適当な頂点と各頂点の距離を調べる
- 1で求めた距離の中で最長である頂点を選び、その頂点と各頂点の長さを調べる
2で求めた長さの最大が直径になります。N-1回の調査を2回行うのでNが最大の50でも98回の調査で終わります。100点解答の100回以内の質問も大丈夫そうですね。
#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
int main(){
int N;
cin>>N;
int mxi=-1;
int mx=0;
for(int i=2;i<=N;i++){
int d;
cout<<"? 1 "<<i<<endl;
cin>>d;
if(d>mx){
mx=d;
mxi=i;
}
}
int ans=-1;
mx=0;
for(int i=1;i<=N;i++){
if(i==mxi) continue;
int d;
cout<<"? "<<mxi<<" "<<i<<endl;
cin>>d;
if(d>mx){
mx=d;
ans=i;
}
}
cout<<"! "<<mx<<endl;
}
この手の質問する問題好きなのですが、最近のAtcoderではあまり見かけないですよね…
コメント