SRM539

結果報告

社会人になると午前１０時回に参加できなくなるんだなあ．
昨日一問だけ解いたので一応書いておく．
250-550-1000回．

Level	ProblemName	Status	Point
Easy	Over9000Rocks	PassedSystemTest(Practice)	----
Medium	SafeReturn	Opened	----
Hard	----	----	----

Easy Over9000Rocks

問題

石を入れる事の出来る箱が沢山あり，それぞれ入れられる最小値・最大値が決まっている．
現在自分は無限個の石を持っているので，
これらの箱に石を詰めてその総和を提示する事で，自分が9001個以上の石を持っている事を立証したい．
自分が詰められる石の個数は全部で何通りあるか．

考えたこと

各箱に入れられる個数が10^6位で箱は高々15個なので，全パターンsetにぶち込んだら何とかなりませんか？とか思って実装してみた．
あっという間にメモリ制限に引っかかって詰みました．
という訳で，各箱の使用する・しないすべてのパターンについて
詰められる石の最小値・最大値を区間として持っておき，最後に個数をカウントする方法に変更した．
最後の個数をカウントする機構でバッグバグになり4回位再提出して泣いた．
もっとスマートに書けるようにならないとな…

コード

  int countPossibilities(vector <int> lowerBound, vector <int> upperBound) {
    int result=0;
    int size = lowerBound.size();
    vector< pair<int,int> > vec;
    for( int i = 0 ; i < (1<<size) ; i++ ){
        long long mi = 0;
        long long ma = 0;
      for( int j = 0 ; j < size; j++ ){
        if( (i>>j)%2 == 1 ){
          mi += lowerBound[j];
          ma += upperBound[j];
        }
      }
      mi = max( mi, 9001LL);
      if( ma >= 9001 ){
        vec.push_back( make_pair( mi, ma ));
      }
    }
    sort( vec.begin(), vec.end() );
    int curma = 9001;
    for( int i = 0 ; i < (int)vec.size(); i++ ){
      //cout << vec[i].first << " " << vec[i].second <<":";
      int begin = max( curma, vec[i].first);
      cout << vec[i].second-begin+1<<endl;
      result+= max(0,vec[i].second-begin+1);
      curma = max(curma,vec[i].second+1);
    }
    return result;
  }

計算時間は箱の個数nに対して.

Medium SafeReturn

問題

0からNまでの街があり，0番目の街をスタートとして，1-Nの街それぞれにひとりずつ兵士を派遣したい．
各街の間は道路で結ばれていることがあり，それぞれどれくらい時間がかかるかは入力で与えられる．
各兵士は可能な限り最短な時間でで目的地までつかなくてはならない．
この国は物騒な所なので，一人で行くと途中で殺される可能性がある．
二人以上で道路を歩いている時は，１００％安全である．
殺される可能性のある兵士の数の最小値をこたえよ．

考えたこと

まずは各兵士がどのくらいの時間でいかなければいけないかを求める．
これは街の数が５０以下らしいのでワーシャルフロイドで50^3位時間かけても大丈夫だろう．
また，少なくとも最長時間かかる兵士には犠牲になってもらう事が確定的に明らか．
……でも，そこから先どないしたらええのん？

なんとなく最小全域木とかと関係ありそうな気がするんだけどもしかしたら圧倒的に気のせいかもしれない．

問題は少しいわくつきみたい．System Testが緩かったとかなんだろうか？
取り敢えず自習の優先度は少し低めにしておこうと思う