SRM688(Div2)に参加しました!
はじめてのSRM
— satanic@C++ (@satanic0258) April 15, 2016
競プロのカレンダーを見ていると、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になってなかったりしたらおかしいよな…」
みたいなことをベースに色々やりました。
確か「)」を「(」にしたらそれ以降の深さがすべてされて、
逆に「(」を「)」にしたらそれ以降の深さがすべてされる、
ということを基本に考えて以下のように書いてみました。
#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代入してるんだ…。これ間違ってるんじゃないのか?」みたいなのを発見して、これはいきなりチャレンジ成功!?…とか思ってたんですが…
他の人のコードでこれなら通らない!ってやつ見つけたのにChallengeの方法が分からなくて終わってしまった(泣)
— satanic@C++ (@satanic0258) April 15, 2016
となってしまいました(白目)。
結局どうしたら良いのかもよく分からず…
自分の環境では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(青)