不定期プログラミング覚え書き

青コーダーと黄コーダーの間を彷徨う社会人プロコン勢が余力のあるときに復習した内容をまとめるブログ

SRM601

TopCoder

あけましておめでとうございます。今年もよろしくお願いします。
１年くらい更新さぼってたのはきっと気のせいですすみません。

まずは2013年の振り返りと今年の豊富を書きます。

  • TopCoderレート変動は2012末から2013末にかけて1599->1671。SRM100回参加超えしてこの体たらくである
  • TopCoderレートHighestは一年かけて更新してないんだぜ…
  • GoogleCodeJamはTシャツゲット圏内。プロコンで景品貰うのは初。ちなみに今日届いた。
  • CodeVS2.1予選ちゃっかり出てみたけど20位とかそんなん。
  • 2014年はもっとマラソン系のプロコンにも出てみたいと思います。SRMレートはまずHighest更新してから目標考えます。
    • Highest更新したし次回目標は1900にします。
  • と言うか今年はちゃんとプロコン復習書きます。多分。

それではここで昨年最後のSRM参加、SRM601を振り返ってみましょう。SRM602は寝ぶっちしました。酷い

結果報告

Level ProblemName Status Point
Easy WinterAndPresents PassedSystemTest 195.75
Medium WinterAndSnowman Opened(practiced) 0.0
Hard WinterAndShopping Opened 0.0

Easy WinterAndPresents

問題

林檎とオレンジのはいったバッグがいくらかある。
バッグは配列によって表現されており、i番目のバッグに入っている林檎・オレンジの個数はそれぞれapple[i]、orange[i]で表現されている。
あなたはこのバッグから、以下の操作によってプレゼントを作ることができる

  • \forall i, X<=apple[i ]+orange[i ]を満たすXを定める
  • 各バッグからXこの果物を取ってきて、それらを全て併せてプレゼントとする

あなたが作ることのできるプレゼントのパターン数を答えよ

考えたこと

とりあえずXを固定して考えることにする。あとバッグの総数をNとする。
Xが決まった時、i番目のバッグでは少なくともX-orange[i]個の林檎と、X-apple[i]個のオレンジを使わなくてならない。
これを任意のiについて加算してあげることで、
X*N個のうち、確定で使わなければならない林檎の数R・オレンジの数Oはわかる。
残りは林檎・オレンジどちらを使っても良いのだから、
この時プレゼントのパターン数はX*N-R-O+1パターンだとわかる。
これを任意のXについて計算して足し合わせれば答えが求まる。

コード

なんか林檎の総数求めたり色々余計な処理挟んでるのは試行錯誤の結果ということでおおめに見てください。

long long getnumber(vector <int> apple, vector <int> orange){
    int n_apple=int_max;
    int sum_apple=0;
    int n_orange=int_max;
    int sum_orange=0;
    int n_size = int_max;
    int size = apple.size();
    for( int i = 0; i < size ; i++ ){
      n_apple=min(n_apple,apple[i]);
      sum_apple+=apple[i];
      n_orange=min(n_orange,orange[i]);
      sum_orange+=orange[i];
      n_size = min(n_size,apple[i]+orange[i]);
    }
    long long ret=0;
    for( int i = 1 ; i <= n_size; i++ ){
      long long all_fruits = size * i;
      int minapple = 0;
      int minorange  =0;
      for( int j = 0 ; j < size; j++ ){
        minapple+=max( 0, i-orange[j]);
        minorange+=max( 0, i-apple[j]);
      }
      //cout << i << "..."<<minapple<<", "<<minorange << endl;
      ret += all_fruits-minapple-minorange+1;
    }
    return ret;
  }

Medium WinterAndSnowman

問題

N,Mという二つの数が与えられる。
{1,2,...,N}の部分集合Sと{1,2,...,M}の部分集合Tで、

  • SとT両方に含まれる整数は存在しないS\cap T=\emptyset
  • Sの要素全てのXORはTの要素全てのXORより小さい

という条件を満たすものの個数を求めよ

考えたこと

最初はS\cap T=\emptysetって条件忘れてて凄い検討違いのことしてた。
それが勘違いだとわかってからは殆ど手がとまった状況。
S,Tの最大値が2000かそこらなのでXORとったところで11bitまでだなーこれ使えそうだなーとは思うも、使い方がわからん。
愚直に考えようとするならば、
1,2,...,mまでを用いてSの要素全XORがs,Tの要素全XORがtとなるパターン数をdp[m,s,t]とかして管理すると、
dp[m,s,t] = dp[m-1,s^m,t ]+dp[m-1,s,t^s ]+dp[m-1,s,t ]のdpでできるけど、これだと2000*2048*2048でおよそ8*10^9くらいの探索になるから無理。
sとtは本来大小関係がわかれば良いだけだからそこに工夫のしがいはありそうだけれど、s^tでは大小関係がわからない…と言うくらいは考えてた。確か。

practiceにて

evimaさんのブログ(http://topcoder.g.hatena.ne.jp/evima/20131223)をガン見して理解した。
今回のポイントは

  • s^tはsとtの大小関係はわからないけれど、その値が非ゼロかいなかでsとtが等しいか否かは判断可能。もっと言えば、s^tの上位i-1bitを用いることで、sとtの上位i-1bitが等しいか否かを管理可能

という点。
これによって、上位i-bit目にしてsとtの大小関係が崩れるパターン数を
dp[m,s^tの上位i-1bit,sのi-bit目,tのi-bit目]といったdpテーブルで管理することができるようになる。
この時の探索範囲は2000*2048*2*2=1.6*10^7であり、
iを1〜11まで捜査するとしても全体の処理量は1.7*10^8ほどと、愚直な方法に比べて50倍くらいは早くなることがわかります。
10^8って言うとかなりグレーゾーンに見えます(http://www.itmedia.co.jp/enterprise/articles/0908/22/news001.html)が、
もっと真面目に計算するなら、2048のところはiの値によって小さくなるので、
2000*2*2*(1+2+4+8+16+,...1024+2048)=3.2*10^7と考えると安心でしょうか。
実際evimaさんはそこまでノートに計算してるっぽいですね。3200万ってあるし。

コード
  int getNumber(int N, int M){
    int mod = 1000000007;
    long long ans=0;
    for( int i = 0 ; i < 11 ; i++ ){
      int d = 11-i-1;
      memset( dp, 0 , sizeof(dp));
      dp[0][0][0][0]=1;
      for( int curNum = 1 ; curNum <= max(N,M) ; curNum ++ ){
        for( int curOffset = 0 ; curOffset < (1<<d); curOffset++ ){
          for( int Ni = 0 ; Ni <2 ; Ni++ ){
            for( int Mi = 0 ; Mi<2; Mi++ ){
              dp[curNum][curOffset][Ni][Mi] += dp[curNum-1][curOffset][Ni][Mi];
              dp[curNum][curOffset][Ni][Mi] %= mod;
              if( curNum <= N ){
                int nextOffset = curOffset ^ (curNum>>(i+1));
                int nextNi = Ni^((curNum >> i )%2);
              //  if( curOffset <= 1 ) cout<< nextOffset<< ","<<nextNi<<","<<Mi<<"<-"<<curNum-1<<","<<curOffset<<","<<Ni<<","<<Mi<<endl;
                
                dp[curNum][nextOffset][nextNi][Mi] += dp[curNum-1][curOffset][Ni][Mi];
                dp[curNum][nextOffset][nextNi][Mi] %= mod;
              }
              if( curNum <= M ){
                int nextOffset = curOffset ^ (curNum>>(i+1));
                int nextMi = Mi^((curNum >> i )%2);
                //if( curOffset <= 1 )cout<< nextOffset<< ","<<Ni<<","<<nextMi<<"<--"<<curNum-1<<","<<curOffset<<","<<Ni<<","<<Mi<<endl;
                dp[curNum][nextOffset][Ni][nextMi] += dp[curNum-1][curOffset][Ni][Mi];
                dp[curNum][nextOffset][Ni][nextMi] %= mod;
              }
            }
          }
        }
        /*
        for( int curOffset=0 ; curOffset < (1<<d) ; curOffset++) {
          for( int Ni = 0 ; Ni <2 ; Ni ++){
            for( int Mi = 0 ; Mi <2 ; Mi++ ){
              if( dp[curNum][curOffset][Ni][Mi] != 0 )
              cout << "dp["<<curNum <<","<<curOffset<<","<<Ni <<","<<Mi <<"] = "<<dp[curNum][curOffset][Ni][Mi] <<" ," ;
            }
          }
        }*/
      }
      //cout << endl;
        ans += dp[max(N,M)][0][0][1];
      ans %= mod;
    }

    return ans;
  }