blue_jamのTopCoder日記

SRM337 Div1 Easy,Medium

SRM, Practice | 01:04

新しいPC使って始めてのPractice．

337のPracticeには2人ほど付き合ってくださった．感謝．

Easy概要

1から1000000のカードまたはジョーカー（ワイルドカード）が最大50枚配られる．

それらを使って階段を作りたい．

最長でどれだけの長さの階段が作れるか．

Easy方針

高々50枚なので，最長で50の階段．カードの数も1000000までなので，始点を定めてそこからどれだけの長さの階段ができるか調べる．

int tab[10000010];
class CardStraights {
    public:
    int longestStraight(vector <int> cards) {
        int res = 0;
        int joker = 0;
        int n = cards.size();
        memset(tab, 0, sizeof(tab));
        sort(cards.begin(), cards.end());
        for(int i=0;i<n;++i){
            if(cards[i] == 0){
                joker++;
            }
            else{
                tab[cards[i]]++;
            }
        }
        for(int i=1;i<=1000000;++i){
            int tmp = joker;
            int count = 0;
            for(int j=i;j<=1000000;++j){
                if(tab[j] == 0){
                    if(tmp > 0){
                        --tmp;
                    }
                    else{
                        break;
                    }
                }
                ++count;
            }
            res = max(count, res);
        }
        return res;
    }
};

Medium概要

高さがまちまちのビルがある．その壁面に長方形の広告を載せたい．

最大でどれだけの面積の広告を貼り付けられるか．

Medium方針

各地点でのx座標と高さをスタックに積みながら進む．

途中で，スタックに積んでいる高さよりも低いものが現れたら，面積を計算しながらスタックからおろして面積を計算．（その地点の高さより小さくなるまで続ける．）その後にスタックに積む．（最後におろしたスタックのx座標を使う）

これを続けていって，最大値が答え．

class BuildingAdvertise {
    public:
    void getR(vector<int> h, int n, vector<long long> &R){
        int j = 0;
        int m = h.size();
        for(int i=0; i<n; ++i){
            R.push_back(h[j]);
            int s = (j + 1) % m;
            h[j] = ((h[j] ^ h[s]) + 13) % 835454957;
            j = s;
        }
    }
    long long getMaxArea(vector <int> h, int n) {
        long long res = 0ll;
        vector<long long> R;
        stack<pair<int, int> > st;
        getR(h, n, R);
        st.push(make_pair(0, 0));
        for(int i=0;i<n;++i){
            if(R[i] < st.top().second){
                int last = 0;
                while(R[i] < st.top().second){
                    res = max(res, (long long)(i - st.top().first) * st.top().second);
                    last = st.top().first;
                    st.pop();
                }
                st.push(make_pair(last, R[i]));
            }
            else if(R[i] > st.top().second){
                st.push(make_pair(i, R[i]));
            }
        }
        while(!st.empty()){
            res = max(res, (long long)(n - st.top().first) * st.top().second);
            st.pop();
        }
        return res;
    }
};

hという配列から高さを表すRを作るという制約を忘れていて，一緒に練習していた人に指摘された．すごく恥ずかしかった．