Codeforces Round #642 (Div. 3) 参加記

コンテストへのリンク

参加しました。結果は以下です。 Dできてよかったです。

A

問題へのリンク

以上にはできません。

void solve(){
    ll n,m;
    cin >> n >> m;
    ll ans;
    if(n == 1){
        ans = 0;
    }
    else if(n == 2){
        ans = m;
    }
    else ans = 2 * m;
    cout << ans << endl;
}

B

問題へのリンク

上から種類とるが、からは回しか取れないとする。

void solve(){
    int N, K;
    cin >> N >> K;
    vector<l_l> v;
    rep(i,N){
        int a;
        cin >> a;
        v.push_back({a,0});
    }
    rep(i,N){
        int a;
        cin >> a;
        v.push_back({a,1});
    }
    sort(all(v));
    reverse(all(v));
    int cnt = 0;
    ll ans = 0;
    rep(i,2*N){
        if(cnt == N)break;
        if(v[i].second == 1){
            if(K > 0){
                K--;
                ans += v[i].first;
                cnt++;
            }
        }
        else{
            ans += v[i].first;
            cnt++;
        }
    }
    cout << ans << endl;
}

C

問題へのリンク

中心に集めますが、囲い状に遷移させるので漸化式ができて計算します。

void solve(){
    ll N;
    cin >> N;
    ll cnt = N / 2;
    ll ans = 0;
    for(ll i = 1; i <= cnt; i++){
        ans += i * (2*i)*4;
    }
    cout << ans << endl;
}

D

問題へのリンク

愚直にシミュレーションがpriority_queueで実装できます。

void solve(){
    int N;
    cin >> N;
    vector<int> a(N,0);
    priority_queue<i_i, vector<i_i>> pq;
    //長さと左端
    pq.push({N, 0});
    int cnt = 0;
    while(not pq.empty()){
        auto tmp = pq.top();
        cnt++;
        pq.pop();
        //[l,r)
        int l = -tmp.second;
        int r = l + tmp.first;
        if(l == r)continue;
        if(cnt > N)break;
        int mid = ((r-l)&1) ? (l+r)/2 : (l+r)/2-1;
        //cerr <<"(" << l << " " << r << "): " << mid << endl;
        a[mid] = cnt;
        //cerr << "add: " << "(" << l << " " << mid << ")" << endl;
        //cerr << "add: " << "(" << mid+1 << " " << r << ")" << endl;
        pq.push({mid-l, -l});
        pq.push({r-mid-1, -mid-1});
    }
    rep(i,N){
        cout << a[i] << " ";
    }
    cout << endl;
}

E

問題へのリンク

K個ごとの周期に分けて0000,1111,000にすればいいと思ったけど、から落ちなかった。状態を持って耳DPでいいらしい。確かに。

記事にしました。

coonevo.hatenablog.com

お疲れ様でした。