SRM540 Div.1 - Isa@Diary

結果

o--(+4/-0) 282.82pts 58th(Div.1)
1481->1665(+184)

Highest更新 && 黄色到達 && Div.1初2ケタ！

250

A[0]を決め打ちすればBを満たすAは一意に決まる。
またA[0]を1増やした時にA[k]が増加するか減少するかは
符号列によって決まる。例えば

B:
   +   -   +
   3  -1   7
A:
 0   3   4   3
 1   2   3   4
 2   1   2   5
(^   v   v   ^) ^:増加　v:減少

と書いてやれば解る。
よって、例えばA[0]=1として全てのA[k]について計算し、
A[0]を増加させた時に増加するものの最小値と減少するものの最小値を取ればよい。
増加するか減少するかは符号が+ならば前の項の逆、-なら前の項と同じ。

あとは
減少していく項がなければいくらでも増やせるので-1を返す。
増加するものの最小値が負である場合、少なくともその値+1加えないと正にならないので

ans = (減少するものの最小値) - abs(増加するものの最小値) - 1;

であり、そうでない場合

ans = max(0, (減少するものの最小値) - (増加するものの最小値) + 1);

となる。

決め打ちしていく過程で10^9を50回足したり引いたりする必要があるので
64bit整数を使う必要がある。
(これに気づいていたのにはじめの上限を2*10^9にしていたのでresubmitした)

以下ソースコード

     int getCount(vector <int> B, string op) {
         vector<ll> val;
         vector<bool> pos;
         bool cur_pos = true;
         int n=B.size();
         ll upmin=(ll)1e+15,downmin=(ll)1e+15;
         ll current = 1;
         val.push_back((ll)1);
         pos.push_back(true);
         for(int i=0;i<n;i++){
             if(op[i] == '+'){
                 if(cur_pos){
                     cur_pos = false;
                 }else{
                     cur_pos = true;
                 }
                 current = B[i] - current;
             }else{
                 current = current - B[i];
             }
             val.push_back(current);
             pos.push_back(cur_pos);
         }
 
         for(int i=0;i<val.size();++i){
             if(pos[i] == true){
                 upmin = min(upmin, val[i]);
             }else{
                 downmin = min(downmin, val[i]);
             }
         }
 
         if(downmin == (ll)1e+15) return -1;
 
         ll res;
         if(upmin <= 0){
             res = downmin - abs(upmin) - 1;
         }else{
             res = downmin - upmin + 1;
         }
 
         if(res <= 0){
             return 0;
         }else{
             return res;
         }
     }

500,950

開いてません

challenge

250でlong longと書いていないソースに対し
{"1000000000","1000000000","1000000000","1000000000","1000000000"}
{"----+"}
を投げて4撃墜。ll使っている人でも落ちている人はいたのではじめのMAXも見ておけばよかった。

感想

レートがバブリーなのでまぁすぐ落ちるんだろうけどどれぐらい耐えられるのか。
がんばろう。