A – Right Triangle
A – Right Triangle (atcoder.jp)
角ABCが90度であることが分かっているため、ABの長さとBCの長さを掛けて2で割った値が答えになります。
入力例1の図が分かりやすいですね。CAの長さも入力として与えられますが読み捨てましょう。
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
int main(){
int ab,bc,ca;
cin>>ab>>bc>>ca;
cout<<ab*bc/2<<endl;
}
B – Collatz Problem
B – Collatz Problem (atcoder.jp)
問題文に書いてあるf(n)の式をコードに落とします。
f(n)で算出したnの値を何かで管理し、重複値が出てきた場所が答えになります。
今回はsetを使いました。setは入れた値が自動でソートされるため、重複を探す際に二部探索が使われます。今回は制約が弱いので気にする必要はないですが、高速に動いてくれます。
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
int main(){
int s;
cin>>s;
set<int> se;
se.insert(s);
int c=2;
while(1){
if(s%2==0) s/=2;
else s=3*s+1;
if(se.find(s)!=se.end()) break;
se.insert(s);
c++;
}
cout<<c<<endl;
}
C – Grand Garden
1～5の範囲に水やりできるのに、1～3、4～5と2回に分けて水やりするのは明らかに悪手です。できるなら一気にやった方が得です。
Nの範囲も小さいので愚直にシミュレーションでOKです。
工夫として、逆順(初期値をh0～hN-1として、ある範囲の高さを1減らしてh0～hN-1を0にする)として考えました。
終了条件が”全て0になったかどうか”となるので、少し楽になります。
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
int main(){
int N;
cin>>N;
int h[N];
for(int i=0;i<N;i++){
cin>>h[i];
}
int c=0;
while(1){
int zc=0;
for(int i=0;i<N;i++){
if(h[i]<=0) zc++;
if(h[i]>0&&(i==0||h[i-1]<0)) c++;
h[i]--;
}
if(zc==N) break;
}
cout<<c<<endl;
}
D – Various Sushi
D – Various Sushi (atcoder.jp)
おいしさ基礎ポイントを最大化することを考えます。
具体的には、dで降順ソートし、上からK個選択します。
ここから、おいしさ基礎ポイントの減少を少なくしながら、種類ボーナスポイントを増やして答えが大きくなるかを見ていきます。
K個選ばなければいけないため、答えを最大化するには以下のように選択する必要があります。
- 2個以上選んでいる寿司のネタの中から最小のdiのものを選ばないようにする
- 1個も選んでいない寿司のネタの中から最大のdiのものを選ぶようにする
これらを、set等の高速に探索できるデータ構造で管理しながら見ていけばOKです。
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
int main(){
long long N,K;
cin>>N>>K;
pair<long long,long long> td[N];
for(int i=0;i<N;i++){
long long t,d;
cin>>t>>d;
td[i]=make_pair(d,t);
}
sort(td,td+N);
long long ans=0;
int f[N+1];
multiset<long long> add,del;
for(int i=0;i<N+1;i++) f[i]=0;
long long v=0;
for(int i=N-1;i>=N-1-K+1;i--){
ans+=td[i].first;
if(f[td[i].second]==0){
ans-=v*v;
v++;
ans+=v*v;
}
else del.insert(td[i].first);
f[td[i].second]++;
}
multiset<long long> s[N+1];
for(int i=0;i<N;i++){
s[td[i].second].insert(td[i].first);
}
for(int i=1;i<=N;i++){
if(s[i].size()>0){
if(f[i]==0){
add.insert(*s[i].rbegin());
}
}
}
long long sum=ans;
auto ita=add.rbegin();
auto itd=del.begin();
while(1){
if(ita==add.rend()||itd==del.end()) break;
//cout<<*ita<<","<<*itd<<endl;
sum+=*ita;
sum-=*itd;
sum-=v*v;
v++;
sum+=v*v;
ans=max(sum,ans);
ita++;
itd++;
}
cout<<ans<<endl;
}
コメント