AtCoder Beginner Contest 116(ABC116)

ABC

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

C – Grand Garden (atcoder.jp)

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;
}

コメント

タイトルとURLをコピーしました