sataniC++

C++、競プロ、数学などについて色々考えたりします。

SRM688(Div2)に参加しました！

競プロ参加 競プロ参加-SRM

競プロのカレンダーを見ていると、2016/04/16 00:00(日本時間)からSRMがあるということだったので、TopCoder SRMに初参戦してみました。


初参戦ということでレートは1200から始まり、Div2の問題を解くみたいですね。


さっそくスタート！

Coding Phase

Easy(250)

「括弧の深さ…これどっかでやったことあるな…」と思い、迷わずいもす法で解くことを決めました。

#include <algorithm>
#include <string>
#include <vector>
 
class ParenthesesDiv2Easy {
    public:
    int getDepth(std::string s){
        int n = s.size();
        std::vector<int> depth(n, 0);
        std::vector<int> cumSum(n, 0);
        for(int i=0; i<n; ++i){
            if(s[i]=='('){
                ++depth[i];
            }else{
                --depth[i];
            }
        }
        cumSum[0]=depth[0];
        for(int i=1; i<n; ++i){
            cumSum[i]=cumSum[i-1]+depth[i];
        }
        std::sort(cumSum.begin(), cumSum.end());
        return cumSum[n-1];
    }
};

サンプルケースも結構すんなり通ったので、これで提出。
これにはあまり時間がかかりませんでした。

Medium(500)

「深さがマイナスになってたり最後の深さが0になってなかったりしたらおかしいよな…」
みたいなことをベースに色々やりました。

確か「)」を「(」にしたらそれ以降の深さがすべて+2されて、
逆に「(」を「)」にしたらそれ以降の深さがすべて-2される、
ということを基本に考えて以下のように書いてみました。

#include <algorithm>
#include <string>
#include <vector>
 
class ParenthesesDiv2Medium {
    public:
    std::vector<int> correct(std::string s){
        int n = s.size();
        std::vector<int> depth(n, 0);
        std::vector<int> cumSum(n, 0);
        for(int i=0; i<n; ++i){
            if(s[i]=='('){
                ++depth[i];
            }else{
                --depth[i];
            }
        }
        cumSum[0]=depth[0];
        for(int i=1; i<n; ++i){
            cumSum[i]=cumSum[i-1]+depth[i];
        }
        std::vector<int> ans;
        for(int i=0; i<n; ++i){
            if(cumSum[i]<0){
                ans.push_back(i);
                for(int j=i; j<n; ++j){
                    cumSum[j]+=2;
                }
            }
        }
        if(cumSum[n-1]!=0){
            for(int i=n-2; i>=0; --i){
                if(cumSum[i]<2 && cumSum[i+1]>=2){
                    ans.push_back(i+1);
                    for(int j=i+1; j<n; ++j){
                        cumSum[j]-=2;
                    }
                    i=n;
                    if(cumSum[n-1]==0){
                        break;
                    }
                }
            }
        }
        return ans;
    }
};

ちょいちょい調整しながらサンプルケースが全部通ったところで提出。
割と時間がかかってしまいましたが、そのままHardへと進んで行きました。

Hard(1000)

LとRで指定された範囲外の各括弧の数を記録しておいて…とかやった気がします(遠い目)。

何回やっても結局サンプルケースがすべて通ることなくタイムオーバー。
あとちょっと…なような気がしてましたがはたして本当にそうだったのかはわかりません。


Challenge Phase

(この前の5分休憩の時にトイレ行ってたらもうこのフェイズ始まってて焦ったのは秘密)

このChallenge PhaseというものがTopCoder特有(？)で、とても新鮮でしたね。
「他の人のコード見て判断って、こんなん本当に出来るのかな」とちょっと不安もありました。


ところが、
「あれ、なんでここで0代入してるんだ…。これ間違ってるんじゃないのか？」みたいなのを発見して、これはいきなりチャレンジ成功！？…とか思ってたんですが…

となってしまいました(白目)。
結局どうしたら良いのかもよく分からず…

自分の環境ではArenaがなんだか重かったので、もしかしたら表示バグでも起こしてたのかもしれませんね。


というわけで、次のSRMでの目標が早速出来てしまいました(笑)。
次のSRMは2016/04/24 01:00(日本時間)なので、そこでChallengeにリベンジしてみたいと思います。


最終結果

スコア
問題 満点スコア 獲得スコア かかった時間
Easy 250 236.15 06:57
Medium 500 284.99 29:55
Hard 1000 0.00 --:--

計:521.14

レート

1200(白)→1231(青)


あとがき

初めてのSRMでしたが、なんとなくやったことがあるような問題だったので割と健闘出来ました。
レートも上がって…ってこれ、1200以上になったってことは次Div1なのでは…？(冷汗)

…次のSRMも張り切って頑張りたいと思います。