ABC116 参加記

みなさんお疲れさまでした。

atcoder.jp

A - Right Triangle

A - Right Triangle

直角三角形の面積を求める。直角の場所が固定なので a*b/2 が答え。

B - Collatz Problem

B - Collatz Problem

今まで出てきた値をstd::setで管理するとわかりやすい。

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

int main() {
    ll s, ans = 1;
    set<ll> st;
    cin >> s;
    while(st.count(s)==0){
        st.insert(s);
        if(s%2) s = 3*s+1;
        else s /= 2;
        ans++;
    }
    cout << ans << endl;
    return 0;
}

C - Grand Garden

C - Grand Garden

前から順に見ていったとき、高さが前より増加していればそこを新たな水やりの開始点としてansに差分を加算します。高さが減少していればそこをいままでの水やりのうちその高さ以上のものの終点とします。

#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for (int i = 0; i < n; i++)

int main() {
    int n, h[105]{}, ans=0;
    cin >> n;
    REP(i,n) cin >> h[i+1];
    REP(i,n) ans += max(0,h[i+1]-h[i]);
    cout << ans << endl;
    return 0;
}

D - Various Sushi

D - Various Sushi

大きいものから貪欲が厳しそうだったので、全部選んでからまずい寿司を貪欲に取り除いていく方針にしました。取り除いたときに満足度の減少が少ない順に取り除きたいのでpriority_queueに入れておきます。あとはqueの中身がK個になるまで取り除きます。ただし、取り除こうとしているものがその種類の最後の1つだった場合、種類数が減るのでその分を加味します。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const int MAX_N = int(1e5 + 5);
#define REP(i, n) for (int i = 0; i < n; i++)

int main() {
    ll n, k, ans=0, cnt[MAX_N]{}, ma[MAX_N]{};
    cin >> n >> k;
    priority_queue<P> que;
    REP(i,n){
        ll t, d;
        cin >> t >> d;
        ans += d;
        cnt[t]++;
        ma[t] = max(ma[t],d);  // その種類の最大値
        que.push({-d,t});
    }
    ll x=0;
    REP(i,n+1)if(cnt[i]>0) x++;
    ans += x*x;
    while(que.size()>k){
        P p = que.top();
        ll d = p.first, t = p.second;
        que.pop();
        if(cnt[t]==1) d = -ma[t] - (x*2-1);  // 最後の1つ
        if(que.top().first <= d){
            ans += d;
            cnt[t]--;
            if(cnt[t]==0) x--;
        }
        else{
            que.push({d,t});
        }
    }
    cout << ans << endl;
    return 0;
}

コメント

D問題が難しかったです。x種類以上取ると決め打ちしてから貪欲する方法もあるそうです。