PCK2013 Virtual

ソロ.

A 気温の差

問題概要

引き算を7回してください

解法

引き算を7回します.53秒0WA

B チケットの売上

問題概要

チケットの売れた枚数が与えられるので売上金額を計算する

解法

チケットの売れた枚数が与えられるので売上金額を計算する.3分16秒0WA

C 入場料金

問題概要

特定の組み合わせで安くなるチケットの最安値

解法

そのまま買うか割引が適用できるように買うかのどっちも試す.6分54秒0WA

D おそろいの景品

問題概要

ガシャポンを引きまくって同じのが2つでるのに何回かかる?

解法

鳩の巣原理.誤読で1WA13分

E 坊主めくりの結末

問題概要

坊主めくりをシミュレートして

解法

坊主めくりをシミュレートする.誤読で1WA形式ミスで1PE22分

F 陣形

問題概要

3種類の人がいっぱいいるから上手にチームを組んで

解法

組み方が限定されている人たちから貪欲に組んでいく.25分0WA

G プログラミングコンテスト

問題概要

加点と減点がなされるプロコンで,1位の時間が一番長いチームはどこか

解法

普通のセグ木を貼るだけ…なはずなんだけど最小のうち一番左をもつ実装ができず投げた.あとで解き直す.

H 勉強会

概要

賢さが決まっているN人の中から何人かリーダーが決まっていて,他の人をリーダーに振り分けていく.
ただし自分より賢く,賢さの差がr以下のリーダーの元にしかつくことができない.各クエリごとにrがいくつ以上である必要があるか求めよ.

解法

リーダーは最大で100人と少ない.rさえ決めればあぶれる人数は求められるのでmapでリーダーを持って,にぶたんでrの境界を探す.
upperboundとlowerboundがひたすらバグって厳しかった.

ソースコード

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define FOR(i,n,m) for(int i=(n);i<(m);i++)
#define REP(i,n) FOR(i,0,n)
#define REPR(i,n) for(int i=(n);i>=0;i--)
#define all(vec) vec.begin(),vec.end()
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using P=pair<ll,ll>;
using PP=pair<ll,P>;
using vp=vector<P>;
using vpp=vector<PP>;
using vs=vector<string>;
#define fi first
#define se second
#define pb push_back
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(a>b){a=b;return true;}return false;}
const ll MOD=1000000007LL;
const int INF=1<<30;
const ll LINF=1LL<<60;
int main(){
    int n,q;
    cin>>n>>q;
    vi vec(n);
    REP(i,n){
        cin>>vec[i];
    }
    vi d(vec);
    sort(all(d));
    map<int,int> ma;
    ma[-1]=0;
    REP(i,q){
        string st;
        cin>>st;
        int t;
        cin>>t;
        if(st=="ADD"){
            t--;
            ma[vec[t]]++;
        }else if(st=="REMOVE"){
            t--;
            ma[vec[t]]--;
            if(!ma[vec[t]]){
                ma.erase(vec[t]);
            }
        }else{
            int k=distance(upper_bound(all(d),(*ma.rbegin()).fi),d.end());
            if(k>t){
                cout<<"NA"<<endl;
                continue;
            }
            int ng=-1,ok=INF;
            while(ok-ng>1){
                int mid=(ok+ng)/2;
                int cnt=k;
                for(auto itr=ma.begin();itr!=ma.end();itr++){
                    auto itr2=itr;
                    itr2++;
                    if(itr2==ma.end()){
                        break;
                    }
                    int dist=distance(upper_bound(all(d),(*itr).fi),lower_bound(all(d),(*itr2).fi-mid));
                    if(dist>0){
                        cnt+=dist;
                    }
                }
                if(cnt>t){
                    ng=mid;
                }else{
                    ok=mid;
                }
            }
            cout<<ok<<endl;
        }
    }
    return 0;
}

I ハッピーエンド問題

わからん

まとめ

1時間57分で7完(3ペナ)
難易度はそこまで高くないんだけど複雑で実装が重い問題が多い.
当時のボーダーがわからないが今このセットが来たら確実に落ちているので,精進が必要.
Gのセグ木を実装できなかったこと,DEの凡ミスは大反省.