SRM540

20時からの賞金回だけど，550という数字を観て絶望したのは僕だけじゃないはず．
と言うか250が解けなさ過ぎて真面目に焦った．
一応通ったけれど，考え方が直感に依存しすぎているのであまり喜べない

Level	ProblemName	Status	Point
Easy	ImportantSequence	PassedSystemTest	93.20
Medium	RandomColoring	Opened	0.00
Hard	----	----	----

Easy ImportantSequence

問題

ルドルフが正数列を黒板に転記していたら，アーサーが，隣り合う数字を足すor引くという演算をし，その結果と符号だけを黒板に残し，元の正数列を消してしまった．
例えば，元の正数列が２，３，４，５だとしたら，
その後アーサーによって，符号列"+,-,+"と，"5,-1,9"のみが黒板に残っていた，といった具合である．
符号列・演算結果列を入力として，ありえる元の正数列のパターン数を示せ．
但し，無限個作れる時は-1を返せ

考えたこと

符号列のどこかに+がある場合，その演算が施される値に上限が定められてしまうことから，解は有限になる．
逆にすべて-である場合，最初の値を大きくすることで無限に条件列を満たす正数列を作れる．

元の数列が"a,b"であると仮定した時，"+"と"c"が残されていたとしたら，
"0c"も言える．

これらの条件を使いながら，元の正数列のi番目の上限と下限を埋めていく．
その幅がもっとも小さい所が答える値となる…きがする．

コード

  int getCount(vector <int> B, string operators) {
    ll result=LLONG_MAX;
    int size = B.size();
    bool flag = true;
    long long ma[100];
    long long mi[100];
    for( int i = 0 ; i < 100 ; i++ ){
      ma[i] = LLONG_MAX/2;
      mi[i] = 1;
    }
    for( int i = 0 ; i < size; i++ ){
      if( operators[i] == '+' ){
        flag = false;
        ma[i] = min((ll)B[i]-1,ma[i]);
        ma[i+1] = B[i]-mi[i];
        mi[i+1] = max((ll)B[i]-ma[i],1LL);
      }
      else{
        mi[i] = max((ll)B[i]+1,mi[i]);
        ma[i+1] = ma[i]-B[i];
        mi[i+1] = max( mi[i]-B[i], 1LL);
      }
    }
    if( flag ) return -1;
    for( int i = 0 ; i <= size; i++ ){
      if( ma[i] < mi[i] ) return 0;
      result = min( result, ma[i]-mi[i]+1 );
    }
    return result;
  }

ぐにぐにいじくっていたらサンプルが通っていたのでだした．
計算量は，演算子列の長さをnとした時に．
正直通ると思っていなかった……

後付け考察

もうちょっと真面目に何故これで通ったのか考えたい…けど後日に回そう．

Medium RandomColoring

円状に並んでいるN個の区画を，R,G,Bの3要素で指定できる色で塗りたい．
（R,G,Bは0以上maxR,maxG,maxB未満の整数の値を取る）
0番目の区画を(startR,startG,startB)で塗り，以降
i+1番目の区画の色は，i番目の区画の色(r,g,b)に対して

• がすべて成り立つ
• のどれか一つが成り立つ

といった条件を満たす色(r',g',b')の中から，ランダムに選ぶものとする．
0,1,...N-1と順々に色分けをしていくので，
N-1番目の区画の色と0番目の色は，隣り合っているのに上記の条件が満たされない可能性がある．その確率を求めよ．

考えたこと

2つ目の条件が「どれか一つ成り立つ」ではなく「すべて成り立つ」だと思っていたので，r,g,bそれぞれに付いてdpでN-1番目の区画に値jの色で塗られる確率を求めて最終的な値を出す…なんて考えていた．
すべて成り立つ，じゃなくて「どれか一つ」なので，この方法は使えなさそう．
でも周りの様子を見ている限りだとdpであることに代わりはなさそうである．
imos法と一部でささやかれているのだけれどどうなんだろうか．