AIM Tech Round 5 (rated, Div. 1 + Div. 2) D. Order book

解法

サンプル2について考える．

4
ADD 1
ADD 2
ADD 3
ACCEPT 2

ACCEPTが正常に行われるには2がBUYの最善かSELLの最善である必要がある．したがって2未満はBUY，2より大きいものはSELL以外にすることが不可能でどちらにすべきか確定する．

このsampleのようにACCEPTが行われたタイミングでBUYにすべきかSELL にすべきかを確定していく．ACCEPTのタイミングでどのような処理を行うか考える．
ACCEPT p

pが存在しない(ADDされていない or すでにACCEPTで消された) 不可能な操作列なのでans=0で終了
pが未確定
- pがBUYの最善以下もしくは pがSELLの最善以上 → 不可能
- それ以外
  ans *= 2
  pより大きいものはSELL，p未満はBUYで確定する
  pを削除する
pが確定
- pが最善ではない → 不可能
- pが最善
  pより大きいものはSELL，p未満はBUYで確定する
  pを削除する

注意する点として最後がADDのケースがある．最後のACCEPTのあとにADDされたpのうち，BUYの最善とSELLの最善の間のものはBUYとSELLのどちらにするのか自由度がある．BUYとSELLを区切る位置がBUYの最善とSELLの最善の間のものの個数通り存在する．したがってこれを最後に答えに掛ける．

ここからは自分がどのように実装したかを書く．処理を行う上で必要なこととして pが存在するか？の判定，pが確定か？の判定，pはBUYとSELLのどちらか？の判定などがある．これらを行うために存在しているp，BUYに属しているp，SELLに属しているp をsetで持っておく．
また，未確定のものをBUYやSELLで確定したものに移す処理のため未確定のものをvectorで持っておく．
これらのデータ構造を用いることでどの処理をすべきなのか？を判定し順番に処理を行っていく．

場合分けとすべき処理をちゃんともれなく考える必要があって大変

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
// #define int ll
using PII = pair<ll, ll>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()

template<typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }

template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts) {
    return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type
fill_v(T &t, const V &v) { t=v; }
template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); }

template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a) {
    out<<'('<<a.first<<','<<a.second<<')'; return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
    out<<'[';
    for(const T &i: a) out<<i<<',';
    out<<']';
    return out;
}
template<class T>
ostream &operator <<(ostream& out, const set<T>& a) {
    out<<'{';
    for(const T &i: a) out<<i<<',';
    out<<'}';
    return out;
}
template<class T, class S>
ostream &operator <<(ostream& out, const map<T,S>& a) {
    out<<'{';
    for(auto &i: a) out<<i<<',';
    out<<'}';
    return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL
const int INF = 1<<30;
const ll LLINF = 1LL<<60;
const ll MOD = 1000000007;

signed main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    ll n;
    cin >> n;
    vector<string> s(n);
    vector<ll> p(n);
    REP(i, n) cin >> s[i] >> p[i];

    ll ans = 1;
    vector<ll> v;
    set<ll> buy, sell, st;
    REP(i, n) {
        if(s[i] == "ADD") {
            v.push_back(p[i]);
            st.insert(p[i]);
        } else {
            // pが存在しない
            if(st.find(p[i]) == st.end()) {
                ans = 0;
                break;
            }
            // pが未確定
            else if(buy.find(p[i])==buy.end() && sell.find(p[i])==sell.end()) {
                ll buy_best = (buy.size()?(*(buy.rbegin())):-1);
                ll sell_best = (sell.size()?(*(sell.begin())):LLINF);
                if(buy_best > p[i] || p[i] > sell_best) {
                    ans = 0;
                    break;
                }
                (ans *= 2) %= MOD;
                st.erase(p[i]);
                for(auto j: v) {
                    if(j < p[i]) buy.insert(j);
                    else if(j > p[i]) sell.insert(j);
                }
            }
            // pが確定
            else {
                if(buy.size() && p[i] == *(buy.rbegin())) {
                    st.erase(p[i]);
                    buy.erase(p[i]);
                } else if(sell.size() && p[i] == *(sell.begin())) {
                    st.erase(p[i]);
                    sell.erase(p[i]);
                } else {
                    ans = 0;
                    break;
                }
                for(auto j: v) {
                    if(j < p[i]) buy.insert(j);
                    else if(j > p[i]) sell.insert(j);
                }
            }
            v.clear();
        }
        // cout << "i=" << i << endl << "v=" << v << endl << "st=" << st << endl << "buy=" << buy << endl << "sell=" << sell << endl;
    }

    ll tmp = 0;
    REP(i, v.size()) {
        ll buy_best = (buy.size()?(*(buy.rbegin())):-1);
        ll sell_best = (sell.size()?(*(sell.begin())):LLINF);
        if(buy_best < v[i] && v[i] < sell_best) {
            tmp++;
        }
    }
    cout << ans * (tmp+1) % MOD << endl;

    return 0;
}

ferinの競プロ帳

競プロについてのメモ

AIM Tech Round 5 (rated, Div. 1 + Div. 2) D. Order book

解法