Educational Codeforces Round 87 (Rated for Div. 2) 参加記

コンテストへのリンク

参加しました。結果は以下です。 （プレテスト中） Dができて嬉しかったです。

A

問題へのリンク

周期性があるのでごちゃごちゃやるといいです（こういうの嫌い）

void solve(){
    ll a,b,c,d;
    cin >> a >> b >> c >> d;
    if(a <= b){
        cout << b << endl;
        return;
    }
    if(c <= d){
        cout << -1 << endl;
        return;
    }
    ll ans = 0;
    ans = b + c * ((a - b + c - d-1) / (c - d));
    cout << ans << endl;

}

B

問題へのリンク

ランレングス圧縮して左右を見ます。

vector<pair<char,long long>> RunLengthEncoder_ForString(string v){
    vector<pair<char,long long>> RLE;
    long long cnt = 1;
    for(int i = 0; i < (int)v.size(); ++i){
        if(i == (int)v.size()-1){
            RLE.push_back(make_pair(v[i], cnt));
            continue;
        }
        if(v[i] == v[i+1])cnt++;
        else{
            RLE.push_back(make_pair(v[i],cnt));
            cnt = 1;
        }
    }
    return RLE;
}

void solve(){
    string S;
    cin >> S;
    auto v = RunLengthEncoder_ForString(S);
    ll ans = INFLL;
    for(int i = 1; i < v.size() -1; i++){
        if(v[i-1].first != v[i+1].first){
            chmin(ans, 2 + v[i].second);
        }
    }
    cout << (ans == INFLL ? 0 : ans) << endl;
}

C1

問題へのリンク

4の倍数多角形なので4等分すれば正方形になります。なぜか幾何ライブラリを使ったけど、いらなかったですね。。

提出へのリンク

double dist(const Point &a, const Point &b){
    double res = (a.real() - b.real()) * (a.real() - b.real());
    res += (a.imag() - b.imag()) * (a.imag() - b.imag());
    return sqrt(res);
}
void solve(){
    int N;
    cin >> N;
    vector<Point> v;
    v.push_back(Point(1,0));
    //2PIの2n等分
    double theta = PI / (double)N;
    rep(i,2*N-1){
        v.push_back(rotate(theta,v.back()));
    }
    double hen = dist(v[0],v[1]);
    rep(i,v.size()){
        v[i] /= hen;
    }
    double ne = dist(v[0],v[1]);
    cout << dist(v[0], v[N-1]) << endl;
}

C2

奇数ver。まだ見てません。

D

問題へのリンク

挿入はBITに、削除はBIT上の二分探索で。。TLが厳しかったりするらしいですが一応通っています（システス中ですが・・・）。

提出へのリンク

template<typename T>
class BIT{
  public:
    int N;
    vector<T> data;
    BIT(T _N):N(_N){
        data.assign(N+1, 0);
    };
    
    // a is 1-indexed
    void add(int a, T w){
        for(int x = a; x <= N; x += x & -x)data[x] += w;
    }
    // 1-indexed sum of prefix [0, a]
    T sum(int a){
        T res = 0;
        for(int x = a; x > 0; x -= x & -x)res += data[x];
        return res;
    }
    // 1-indexed sum of range [l, r]
    T sum(int l, int r){return sum(r) - sum(l-1);}

    // 0-indexed add
    void add0(int a, T w){add(a + 1, w);}
    // 0-indexed sum
    T sum0(int a){return sum(a + 1);}
    // 0-indexed sum of range
    T sum0(int l, int r){return sum0(r) - sum0(l-1);}
    // show the value
    void debug(){print(data);}
};

int main() {

    int N, Q;
    cin >> N >> Q;
    vector<int> a(N);
    vector<int> k(Q);
    rep(i,N)cin >> a[i];
    rep(i,Q)cin >> k[i];
    BIT<ll> B(N);
    rep(i,N)B.add(a[i],1);
    rep(i,Q){
        // 削除クエリ
        if(k[i] < 0){
            k[i] = -k[i];
            ll ok = 0;
            ll ng = N+1;
            while(ng - ok > 1){
                ll mid = (ok + ng) / 2;
                if(B.sum(mid) < k[i])ok = mid;
                else ng = mid;
            }
            B.add(ng, -1);
        }
        // addクエリ
        else{
            B.add(k[i],1);
        }
    }
    rep1(i,N+1){
        if(B.sum(i,i) > 0){
            cout << i << endl;
            return 0;
        }
    }
    cout << 0 << endl;
}

E

見たんですが、解けずに終わりました。 DPするらしいですね。