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

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

SRM604

TopCoder

眠さに耐えつつ参加したらEasyで凡ミスして前回の大勝利を失う大敗北でした。寝不足にはなったしこの結果は許されない。

結果報告

Level ProblemName Status Point
Easy PowerOfThree FailedSystemTest 0.0
Medium FoxConnection Opened 0.0
Hard ???? Unopened 0.0

Easy PowerOfThree

問題

(0,0)からスタートしてマイステップすこしずつ動くコマを考える。
各ステップk(=0,1,2,...)では、調度3^kの距離を、四方向のどこかに向けて動かなければならない。
X,Yを与えるので、頂点(X,Y)にたどり着くことができるか否かを答えよ

考えたこと

XとYの範囲がそれぞれ±10^9で与えられているので、k=20位まで探索すれば良さそうである。
方向も4方向しか無いんだし、正負だとか回転だとかを全て重複排除したら全探索でいけるんじゃないの？という方向でまず考えた。
暫く考えて後、この方針ではTLE不可避であることに気づく。
なぜなら、(a,b)からの移動の仕方として、(a+3^k,b),(a-3^k,b),(a,b+3^k),(a,b-3^k)はどうしても区別しないと行けないので、4^20くらいの計算時間が必要。
じゃあどうするか。
もし移動距離が２進数で移動方向が正方向のみだったら、XとYを２進数表記して各bitごとに片側にのみbitがたってるかを判定すれば良いわけだが…
と思ったところで、そういえば３進数って{-1,0,+1}を使って表現することもできる、みたいな話があることを思い出す。
よって、X、Yをそれぞれ上の形で３進数表記してあげて、各桁ごとに片側のみ非ゼロであるか否かを判定すれば良い。
…というところまではちゃんと考えられたのだが、Xの３進数表記を計算して後Yの３進数表記を計算仕様とした段で、キャリーの初期化を忘れてアボンした。
終了間際に気がついたのにresubがタッチの差で間に合わず、無念。
と言うか、コードコピペするくらいならちゃんと関数化しろってあれほど（ｒｙ

コード (SystemTest通過済み)
   string ableToGet(int x, int y){
     vector<int> xVec;
     vector<int> yVec;
     x = abs(x);
     y=abs(y);
     int car = 0;
     while( x != 0 ){
      int curnum = car;
      curnum += x%3;
      car = 0;
      if( curnum >= 2 ){
        curnum -= 3;
        car=1;
      }
      cout << curnum << ", ";
      xVec.push_back( curnum );
      x/=3;
     }
     if( car != 0 ){
       cout << car;
       xVec.push_back(car);
     }
     cout << endl;
     car = 0; //本番ではこの行を入れ忘れた。
     while( y != 0 ){
      int curnum = car;
      curnum += y%3;
      car = 0;
      if( curnum >= 2 ){
        curnum -= 3;
        car=1;
      }
      cout << curnum << ", ";
      yVec.push_back( curnum );
      y/=3;
     }
     if( car != 0 ){
      cout << car;
       yVec.push_back(car);
     }
     cout << endl;
     while( xVec.size() < yVec.size() ) xVec.push_back(0);
     while( yVec.size() < xVec.size() ) yVec.push_back(0);
     for( int i = 0 ; i < (int) xVec.size(); i++ ){
      if( abs(xVec[i])+abs(yVec[i]) != 1 ){
        return "Impossible";
      }
     }
     return "Possible";
落ちた人のコードを読んでみた

どうもチャレンジが下手すぎる感があるので、落ちていた人のEasyのコードを少し読んでみた。
一応、掲載コードは元ネタの唯の写経にするのではなくて不要部分を削除したり自分なりに書き換えて載せてます。

ケース1:条件分岐ミス

   def ableToGet(self,x,y):
      x=abs(x)
      y=abs(y)
      dist=1
      while x>0 or y>0:
         print(x,y) 
         xmod=x%(3*dist)
         ymod=y%(3*dist)
         if xmod*ymod!=0:
            return 'Impossible'
         if xmod!=0:
            if xmod==dist:
               x-=dist
            else:
               x+=dist
         else:
            if ymod==dist:
               y-=dist
            else:
               y+=dist
         dist*=3
      return 'Possible'
  • 現在の距離distを足し引きする相手は、3*distで割り切れない方で、足すべきか引くべきかは3*distの割った結果がdistであるか否かで判定。
  • 両方割り切れない場合はdistをどっちに割り振ってよいかわからないので破綻(つまり実現不可)

というもの。
一見ちゃんと動きそうに思えるのだけれど…意外にテストケース2(1,9)で無限ループに入る。
もっとわかりやすいケースで言えば、(0,3)で落ちる。
理由は、"xとyが両方共3*distで割り切れるケースはImpossible"という処理が抜けていること。

if( x*y != 0 ){//xとy両方が非ゼロの処理}
else if( x!= 0 ){//xが非ゼロの処理}
else{//yが非ゼロの処理}

この形の違和感に気づけるようにしたい。

ケース2:変数ミス

   vector<pair<long long, long long> > EndOf11Step;
   vector<pair<long long, long long> > OffsetAfter11Step;

   long long pow3[21];
   bool recUntil11Step(long long x, long long y , int step){
    int dx[]={1,-1,0,0};
    int dy[]={0,0,1,-1};
    if( x==0 && y==0 ) return true;
    if( step >= 11 ){
      EndOf11Step.push_back(make_pair(x,y));
      return false;
    }
    for( int i = 0 ; i < 4; i++ ){
      if( recUntil11Step(x+dx[i]*pow3[step],y+dy[i]*pow3[step],step+1) ) return true;
    }
    return false;
   }
   void recAfter11Step(long long x, long long y , int step ){
    int dx[]={1,-1,0,0};
    int dy[]={0,0,1,-1};
    EndOf11Step.push_back(make_pair(x,y));//ここが間違い。本当は下記
    //OffsetAfter11Step.push_back(make_pair(x,y));
    if( step >= 21 ) return;
    for( int i = 0 ; i < 4; i++ ){
      recAfter11Step(x+dx[i]*pow3[step],y+dy[i]*pow3[step],step+1);
    }
   }

   string ableToGet(int x, int y){
    pow3[0]=1;
    for( int i = 1 ; i < 21; i++ )pow3[i]=pow3[i-1]*3;
    EndOf11Step.clear();
    OffsetAfter11Step.clear();
    if( recUntil11Step(x,y,0) ) return "Possible";
    recAfter11Step(0,0,11);
    sort(EndOf11Step.begin(),EndOf11Step.end());
    sort(OffsetAfter11Step.begin(),OffsetAfter11Step.end());
    for( int i = 0 ; i < (int)EndOf11Step.size(); i++ ){
      pair<long long, long long> a = EndOf11Step[i];
      vector<pair<long long,long long> >::iterator it = lower_bound(OffsetAfter11Step.begin(),OffsetAfter11Step.end(),a);
      if( it!=OffsetAfter11Step.end() && *it==a ) return "Possible";
    }
    return "Impossible";

  }

最初そもそもコードが何をしているのかわからなかったんですが、ちゃんと読み解いたら理解した。
単純な全探索だと4^20=2^40=10^12くらいの時間がかかる所、
前半10ステップの終了状態(4^10=10^6)と後半ステップでとり得る値(1+4+16+...4^10=(4^11-1)/3個)それぞれ用意し、各前半のステップに対し、調度良い後半の要素を二分探索で求めるようにすると、10^6*log_2((4^11-1)/3)=2*10^7の時間でもとまる、というもの。
ちなみに実際に上記コードの誤り部を訂正すると1.9sくらいの実行時間とかも見えるけど通るっちゃ通る(ちゃんとした計算量の見積もりに比べると結構ギリギリ…どこかでオーダー10位ずれてる？）
ただ、残念なおとに後半部を格納すべきベクトルの名前が前半部のベクトルの名前だったためにこのコードでは11ステップ以降でマッチするケース(-570240,1412834とか)で落ちる。
コードの中身がわかってしまえば変数ミスは割りとわかりやすいけど、コードの意図がわからずにチャレンジフェーズで諦めてしまったのが良くなかったか。
と言うかこのコード、ぱっと見たらTLE狙って大きなケースとか投げてしまいたくなるな。テストケースに最大ケース入ってたから踏みとどまるとは思うけど。

Medium FoxConnection (Not Solved yet)

問題

木構造状に道路が配置された村の集合が与えられる。（道路の長さは全て１である）
各村には兎が一人居ることがあり、初期状態でどの村に兎がいるかも入力で与える。
今、兎たちが全員連結した位置に重複せず居るように、兎の位置を移動させたい。
兎の総移動距離の最小値を答えよ。

考えたこと

ある根ノードみたいなのを与えてあげて、その位置を含む連結成分に兎を寄せてあげる時の最小移動距離を、ノードをずらしながら行えばいいんじゃね？
などと考えてもみるものの、いまいち上記ことをコードとして実現できる感じはしない。
村の個数が最大50ということなので、dp[50][50][50]くらいのdpで計算するんじゃないか？と思い、
dp[i][j][k]=ノードiまでで、兎たちがj人親方向に連結しており、子方向に移動可能なフリーの兎をk人有する状態の最小移動数
なんて状態を考えてもみるも、そこから先に思考が続かなかった。

SRM603

TopCoder

眠さに耐えつつ参加したら二問解けてhighest rate更新する大勝利回でした。寝不足にはなったけどこの結果なら許します。

結果報告

Level ProblemName Status Point
Easy MaxMinTreeGame PassedSystemTest 214.89
Medium PairsOfStrings PassedSystemTest 222.02
Hard SumOfArrays Opened 0.0

436.91pointの総合59位。Petrさんに勝ったのは初めてじゃなかろうか。

Easy MaxMinTreeGame

問題

各ノードにスコアが与えられている木が与えられる。
(枝はi+1とedges[i]の間に枝が張られている、という形で定義。ノードiのスコアはcosts[i])
今、AさんとBさんがそれぞれ
「枝を一本選択削除し、木を二つに分割。分割要素二つのうち片方を除去する」
と言った操作をじゅんじゅんに繰り返す（Aさんが最初）
Aさんは最終的に残るノードのスコアを最大化・Bさんはスコアを最小化したい。
互いに最適な操作を行った時に得られるスコアを答えよ

考えたこと

なんかうまい具合に分割統治法的なアプローチとかで解けるんですか？とか考えたけどわからず。
メモを書きまくった結果、Aさんが最初に1つのノードを確定させる（つまり葉ノードを取る）以上にスコアを良くしようがなくね？　と推測する。
サブミットしたほうが先か考えるほうが先かはわすれたがコンテスト中に以下のところまで考察した
もしAさんが一回目の操作で小さな木を作って、最初に葉ノードを取る以上に良いスコアが得られると仮定する。
この時、小さな木の中には元の木の葉ノードが必ず含まれることから、Bさんはその葉ノードを取ることによって、上述のようなスコアを取ることを防ぐことが可能である。
よってこれは矛盾である。

要するに、葉ノードのうち最大スコアの値を返せばOKである。

コード
   int findend(vector <int> edges, vector <int> costs){
    int n_size = costs.size();
    int n_deg[n_size];
    memset( n_deg, 0 , sizeof(n_deg) );
    for( int i = 0 ; i < n_size-1; i++ ){
     //cout << i+1 << "-"<<edges[i] << endl;
     n_deg[i+1]++;
     n_deg[edges[i]]++;
    }
    int ans = 0;
    for( int i = 0 ; i < n_size; i++ ){
      if( n_deg[i] == 1 ){
        ans = max( ans, costs[i] );
      }
    }
    return ans;

  }

Medium PairsOfStrings

問題

整数nとkが与えられる
k種類のアルファベットからなる長さnの文字列ペア(A,B)で、
AC=CBが成立するような文字列Cが存在するものの個数を求めよ

考えたこと

A=a_0a_1a_2,...,a_{n-1}、B=b_0b_1b_2,...,b_{n-1}とすると、
AC=CBなるCが存在するとは、a_i=b_{(i+j)\%n}なるj

コード
int mod = 1000000007;
int pow( int k , int p){
  long long cur = k;
  long long ans = 1;
  while( p != 0 ){
    if( p % 2 == 1 ){
      ans *= cur;
      ans %= mod;
    }
    cur = cur*cur;
    cur %= mod;
    p/=2;
  }
  return ans;
}

class PairsOfStrings {
   public:
   int getNumber(int n, int k){
     vector<vector<int> > factors;
     int N = n;
     for( int i = 2 ; i*i <= N ; i++ ){
      vector<int> f;
      int cur = 1;
      while( N%i == 0 ){
        N/=i;
        cur*=i;
        ////cout << cur <<"-";
        f.push_back(cur);
      }
      //if( cur != 1 ) //cout << endl;
      factors.push_back(f);
     }
     if( N != 1 ){
       vector<int> f;
      f.push_back(N);
      factors.push_back(f);
     }
     vector<int> divs;
     divs.push_back(1);
     for( int i = 0 ; i < (int)factors.size(); i++ ){
      int s= divs.size();
      for( int j = 0 ; j < (int)factors[i].size(); j++ ){
        for( int k = 0 ; k < s; k++ ){
           divs.push_back(divs[k]*factors[i][j]);
        }
      }
     }
     sort( divs.begin(),divs.end());
     /*
     for( int i = 0 ; i < (int)divs.size(); i++ ){
      //cout << divs[i] << ", ";
     }
     //cout << endl;*/
     int size = divs.size();
     long long cnt[size];
     for( int i = 0 ; i < size; i++){
       int div = divs[i];
       cnt[i] = pow(k,div);
       //cout << i<<":"<<k<<"^"<<divs[i] <<"..."<<cnt[i]<<endl;
     }

     long long ans = 0;
     for( int i = 0 ; i < size; i++ ){
      int div = divs[i];
      //cout << div << "*"<<cnt[i];
      long long tmp = div*cnt[i];
      tmp %= mod;
      ans += tmp;
      ans %= mod;
      for( int j = i+1 ; j < size; j++ ){
        if( divs[j]%div==0 ){
          cnt[j]+=mod;
          cnt[j]-=cnt[i];
          cnt[j]%=mod;
        }
      }
     }


     return ans;

  }

約数リストを出す方法がぱっと思い浮かばなくて実装に凄い時間がかかった。
とは言えmediumを通せたと言うのはとても大きいことだと思うので、時間短縮も狙いつつ、通ったことを素直に喜ぼうと思う。
あとk^p のmodを取るところで2011年くらいのGoogleCodeJamが頭をよぎった(k^p(mod n)を計算する際にpが大きな値になるからってうっかりp%nとかつかって計算するとハマるってやつ)
けど、そんな問題だったらk^p計算するだけで滅茶苦茶時間食いそうですね。

約数を列挙するスマートな方法

即興で書こうと思ったらコメントアウト込みで２７行もかかった約数の列挙。
案の定というかなんというか、レッドコーダーの人の実装をみると７行程度でさっくり実装している。
ちゃんと動作検証はしてないけど大体以下の様な感じ。

 for( int i = 1 ; i*i <=N ; i++ ){
  if( N%i==0 ){
    divs.push_back(i);
    if(i*i!=N) divs.push_back(i/N); 
  }
 }
 sort( divs.begin(),divs.end());

こういう実装ノウハウもちゃんと吸収しないといかんな。と思う今日このごろ。

SRM602

TopCoder

正月休みにSRM602も復習しました。
この回は寝ぶっちしたわけですが、多分参加してたらレート落ちたと思います。Easy手間取りすぎ。

Easy TypoCoderDiv1

問題

うろ覚えなので本質を失わない程度に適当にかきます。
i番目のコンテストに勝利するとレートがD[i]上がり、敗北するとレートがD[i]下がるようなプロコンを考える。
プレイヤーの初期レートはXで、レート2200を超えると赤コーダーになる(確か本当は違う色だったけど忘れた)
プレイヤーは謙虚なので、2回連続で赤コーダーに居とどまるような勝ち方はしないものとする。
なお、レートは負の値になることはない。
与えられたD,Xに対して、プレイヤーが赤コーダと非赤コーダの行き来を最大何回おこせるかを答えよ

考えたこと

連続して赤コーダーに居留まることがない、っていう条件の意味がわからずテストケースと結構にらめっこした。
結局、赤コーダになった後は確実に黄色コーダー以下におちないといけないってことだから、
そのような条件を満たす時にしか赤コーダにはなれないってことだとわかる。
とは言え、その枝刈りをしたとしても勝ち負け全パターン探索は2^size(D)=2^50の探索だから無理ゲー
ゴニョゴニョ考えたけど結局のところi番目のコンテスト終了時のレートがkであるパターン数をdp[i][k]で管理すれば
50*2200の探索空間に収まりそうだな、って結論づけた。

コード

レートが負になる場合とか色々考慮忘れたりちんたら実装してたら妙に時間を食った。

int getmax(vector <int> D, int X){
    memset(dp,-1,sizeof(dp));
    int size = D.size();
    dp[0][X] = 0;
    int ans = 0;
    for( int i = 0 ; i < size; i++ ){
      for( int j = 0 ; j < 2200; j++ ){
        if( dp[i][j] != -1 ){
          if( j+D[i] < 2200 ){
            dp[i+1][j+D[i]]=max(dp[i+1][j+D[i]],dp[i][j]);
          }
          if( j+D[i] >= 2200 && i+1 == size ){
            ans= max( ans, dp[i][j]+1 );
          }
          if( j+D[i] >= 2200 && i+1 < size && j+D[i]-D[i+1] < 2200 ){
            dp[i+2][max(0,j+D[i]-D[i+1])]=max(dp[i+2][max(0,j+D[i]-D[i+1])],dp[i][j]+2);
          }
          dp[i+1][max(0,j-D[i])]=max(dp[i+1][max(0,j-D[i])],dp[i][j] );
        }
      }
      /*
      for( int j = 0 ; j < 2200; j++ ){
        if(dp[i][j] != -1 ){
          cout << "dp["<<i<<","<<j<<"]="<<dp[i][j] << ", ";
        }
      }
      cout << endl;*/
    }
    for( int j = 0 ; j < 2200; j++ ){
      /*
        if(dp[size][j] != -1 ){
          cout << "dp["<<size<<","<<j<<"]="<<dp[size][j] << ", ";
        }
        */
      ans =max(ans,dp[size][j]);
    }
  return ans;
  }

計算量は考察にも書いたとおりコンテスト数＊レート範囲。この場合50*2000

Medium PilingRectsDiv1

2*N枚の長方形の紙がある。それぞれ縦・横の長さは以下のように規定される
i番目の横幅=XS[i] if i

何も見ないで考える事

点数の定義を重複部ではなくて表面積の和集合の面積みたいに勘違い。はああなにそれ無理ゲーってなってた。

復習フェーズ

ここでチラリとkmjpさんのブログを拝見(http://kmjp.hatenablog.jp/entry/2013/12/29/1000)。
勘違いには気づいたもののN枚の紙の最適な並べ方が理解できずに「？？？」となった。
ここでwriterであるsnukeさんのブログも発見(http://snuke.hatenablog.com/entry/2013/12/29/040056)

とりあえず、全部横長の長方形になるように回転しておきます。(ちょっと考えると重ねる時には向きをそろえた方が有利なことが分かるので)

ﾅ､ﾅﾝﾀﾞｯﾃｰ！　というわけで改めて考えなおしてみると、確かにその通りだった。

以下、ラフな説明。
2枚の紙(H0,W0)と(H1,W1)を重ねることを考える。(H0H1の時を考えると、向きを変えずに重ねたばあいはH1*W0の重複部分がつくれる。
向きを変えた場合は、横幅：H0=i)]で、(H_y,W_y)がSに属する物が存在する。
ここで、もし(H_x,W_x)\in S,(H_y,W_y)\notin Sを(H_x,W_x)\notin S,(H_y,W_y)\in Sに入れ替えると、
min_{k\geq i, k\in S} H_kの値を変えずしてmin_{k\notin S}H_kの値を増やす(または不変)ことができるとわかる。
　値が増えるのなら矛盾だし、不変だとしても、これを延々と繰り返すことで添字i以上の高さベストNの集合をとった場合のTが最大点数を持つと言える。
(b) min_{k\geq i, k\in S} H_k>min_{k\notin S}H_kの時
(a)とほぼ同様なので略。ただこの場合は高さワーストNの場合に行き着く。

(2)でTにワーストNを持ってくるケースというのは、S側に高さベストNが集まっている状態であるといえる。
つまり結局、
あるiについて、
添字i以上の高さベストNを持ってきた時の高さ最小値(Hとする)* W_i + 第一項以外の長方形の高さの最小値(hとする)*第一項以外の横幅の最小値(wとする)
をi=0〜Nに関して求めて、その最大値を答えれば良いとわかる。

では、どのように実装するか、という話。
Nが最大10^5なので、log N以下の速度でH,h,wが求められればOKである。

  • Hの求め方：i=Nの時に優先度付きキューの二分木による実装を作っておいて、H_iの値に応じて最小値をpop+H_iをインサート、みたいな形でlog N時間で計算可。実装ではsetを用いた。
  • hの求め方：hlist[m]=min_{k\leq m} H_mという配列を用意。ベストNからあぶれた添字の最大値Kを保存しておけばh=hlist[K}と表せる。
  • wの求め方：i=0以外の場合はW_0に等しい。i=0の時に限ってなら、10^5の時間かけてwを求めるのも問題なし。
コード
 long long getmax(int N, vector <int> XS, vector <int> YS, int XA, int XB, int XC, int YA, int YB, int YC){
    vector<pair<ll,ll> > Rects;
    int size = XS.size();
    long long X=XS[0];
    long long Y=YS[0];
    for( int i = 0 ; i < 2*N ; i++){
      if( i < size ){
        Rects.push_back( make_pair(max(XS[i],YS[i]),min(XS[i],YS[i])) );
        X=XS[i];
        Y=YS[i];
      }
      else{
        X=(X*XA+XB)%XC+1;
        Y=(Y*YA+YB)%YC+1;
        Rects.push_back( make_pair(max(X,Y),min(X,Y)) );
      }
    }
    sort(Rects.begin(),Rects.end());

    long long minHeight[2*N];
    minHeight[0] = Rects[0].second;
    for( int i = 1 ; i < 2*N ; i++ ){
      minHeight[i] = min(minHeight[i-1],Rects[i].second);
    }
    set<pair<ll,int> > S;
    bool vis[N*2];
    memset( vis, false, sizeof( vis ) );
    for( int i = N ; i < 2*N; i++ ){
      S.insert( make_pair( Rects[i].second,i) );
      vis[i] = true;
    }
    long long ans = S.begin()->first*Rects[N].first + minHeight[N-1]*Rects[0].first;
    //cout << S.begin()->first <<"*"<<Rects[N].first<<"+"<<minHeight[N-1]<<"*"<<Rects[0].first<<endl;
    int ind = N-1;
    for( int j = N-1; j >= 0 ; j-- ){
      if( Rects[j].second > S.begin()->first ){
        vis[j]=true;
        vis[S.begin()->second]=false;
        ind = max( ind, S.begin()->second );
        S.erase( S.begin() );
        S.insert( make_pair(Rects[j].second, j) );
        ans = max(ans, S.begin()->first*Rects[j].first + minHeight[ind]*Rects[0].first);
        //cout << S.begin()->first <<"*"<<Rects[j].first<<"+"<<minHeight[ind]<<"*"<<Rects[0].first<<endl;
        if( j == 0 ){
          int minind =0;
          while( vis[minind]==true ) minind++; 
          ans = max(ans, S.begin()->first*Rects[j].first + minHeight[ind]*Rects[minind].first);
          //cout << S.begin()->first <<"*"<<Rects[j].first<<"+"<<minHeight[ind]<<"*"<<Rects[minind].first<<endl;
        }
      }
    }
    return ans;
  }
感想

本番に出されてこれは解ける気が全くしないというか、
向きを揃えることが分かったとしても、ベストN or ワーストNを利用するっていう所にまず気づける気がしなかった。
そこに気付いたならば、優先度付きキュー使うってのに気づくことはできそうな…気もするが、
iをNの方から走査させるって所が少しトリッキー（よくあるとはいえ）だし、ノーヒントなら気づけないかも知れない。
さらに、優先度付きキューを使うっていうのがわかってからも、hとかwを求めるために配列を付け加える必要が出て大変だった。
落とし穴の多い問題、というイメージ。

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;
  }

Win7で拡張子なしファイルの関連付け

Tips

覚え書きって言いながらそういえばプロコン以外の話したこと無くね？
と思ったので、今しがた知ったことを書いて無能を晒すことなどしてみる。

WindowsでMakeFileとか作ってる時、いつも「何で開きます？」って言われてウザかったんですが。
http://eosdesign.jp/archives/1670.html
http://kenkitagawa.cocolog-nifty.com/blog/2012/03/win7-4196.html
こういう記事を見つけてすっきり。

個人的にはvimの新規タブで開いて欲しかったので、

  1. 管理者権限でコマンドプロンプトを起動
  2. assoc .= noextension file
  3. ftype Noextension File = "[アプリケーションのパス]\vim.exe" --remote-tab-silent "%1"

なんてしました。

SRM564

TopCoder

ついに黄色から一発落ちしなかったのは久しぶりである。2012年最後のするめ。仮眠とってたら開始2分前とかに起きてわろた。

結果報告

Level ProblemName Status Point
Easy MonstersValley PassedSystemTest 157.55
Medium TheDivisionGame Opened(practiced) 0.0
Hard -- Unopened 0.0

2012年最後のレートは1599でした。
2011年最後が1488なので、あまり成長していないかも。あんまり体系的な練習してないしなあ、ううむ。

Easy MonstersValley

問題

モンスターが次々と現れてくる路がある。
モンスターの強さはdread[i]で表される。
プレイヤーはモンスターにお金を払い、モンスターを手下にすることが出来る。
モンスターはお金に目がないので、お金は1円か2円のどちらかで良い（必要額はprice[i]で表される）
プレイヤーの引き連れたモンスターの強さ合計値も新たに現れたモンスターの方が強く、かつモンスターを懐柔するだけのお金もない場合。
プレイヤーは喰われてしまう。
＊モンスターの強さが新たなモンスターより十分大きければ、プレイヤーはそのモンスターを手下にしても良いし、スルーしても良い。
この路を無事に渡り切るための最小な金額を答えよ

考えたこと

モンスター数は最大50なので、
どんだけ多く見積もっても100円あれば無事に生きて帰れる。
dp[i][j]を、i番目(i=0,1,...,モンスター数-1)のモンスターと対峙しており、これまでにj円支払った時の、自軍の強さの最大値とする。(-1の時、そのようなシチュエーションが存在しないとする)

  • dread[i] > dp[i][j]の時、かならずお金は払わなくてはいけない。dp[i+1][j+p[i]]よりdp[i][j]+dread[i]が大きい場合はそれに更新
  • dread[i] <= dp[i][j]の時、お金を払っても良いし、払わなくても良い。上の更新に加えて、dp[i+1][j]よりdp[i][j]が大きい場合はそれに更新。

これを繰り返して行って、dp[モンスター数][k]が-1でない最小のkを持ってくれば良い。

コード
  int minimumPrice(vector<long long> dread, vector <int> price){
   int size = dread.size();
      long long dp[51][202];
      for( int i = 0 ; i < 51; i++ ) for( int j = 0 ; j < 202; j++ ) dp[i][j] = -1;
      dp[0][0] = 0;
      for( int j = 0 ; j < size; j++){
        int p = price[j];
        ll d = dread[j];
        for( int k = 0 ; k <= 2*j; k++ ){
          if( dp[j][k] == -1 ) continue;
          //pay 
          dp[j+1][k+p] = max( dp[j+1][k+p],dp[j][k]+d );
          // not pay
          if( d <= dp[j][k] ){
            dp[j+1][k] = max( dp[j+1][k], dp[j][k] );
          }
        }
      }

      for( int j = 0 ; j <= size; j++ ){
        for( int k = 0 ; k <= 2*size; k++ ){
          cout << dp[j][k] << ", ";        
        }
        cout << endl;
      }
    for( int k = 0 ; k <= 201; k++ ){
      if( dp[size][k] >= dread[size-1] ) return k;
    }
    return 201;

  }

Medium TheDivisionGame

問題

数字の集合がある。
プレイヤーはその中の一つの数Xと、その1以外の約数Yを選び、XをX/Yで置き換えるとする。
この操作が行えなくなったプレイヤーが負けとなる。
[L,R]に含まれる連続した整数集合で、先手が勝つような集合は何通りあるか

考えたこと

grundy数の香りがやばい。
ゴリゴリ考えた結果
ある値がp^2p_1^3と素因数分解出来た時のgrundy数って5だよね、と結論付ける。
素数K個（重複を許す）の積で表される値は、約数として素数m個（重複を許す)の積で表される物をとり、素数K-m個(重複を許す)の積で表される値となる
これはNimでいう、K個のコインからm個のコインをのぞいた状態に相当する。
じゃあとりあえず素因数分解して素因数の個数を覚えとくかー
…そっからどうするの？
てか、素因数分解TLEするんだけど？

復習

素因数分解を高速にする場合は、まずはエラトステネスの篩である。
何かRが1001000000を最大で取りうるからびびってたけど、実際に必要な素数ってその平方根で良かった。

また、素因数分解の個数を求めるだけならば、
for( n in [L,R] ) for(p in 素数列) if( n%p==0 )...
とするのは効率が悪いようだ。
確かにこれだと数列の要素数*素数列の個数if文が行われる事になるし、
この場合の素数ベクトルは3000くらいになるので、R-Lの最大値1000000と合わせると3*10^9で激しく微妙。

int calc[R-L+1];
int cnt[R-L+1];
for( int i = L ; i <= R; i++ ) calc[i-L]=i;
for( int i = L ; i <= R; i++ ) cnt[i-L]=0;
for( p in 素数列){
 start = L以上のpの倍数;
 for( int val = start ; val <= R ; val += p ){
  while( calc[val-L] % p == 0 ){
   calc[val-L]/=p;
   cnt[i-L]++;
  }
 }
}
for( int i = L ; i <= R; i++ ){
  if( calc[i-L]!= 1) cnt[i-L]++;
}

とすると、素数の値だけスキップされるので効率が良い。


最後に、素因数分解の個数をした後はどうするか？というと
「与えられた数列の連続部分列で、その要素をすべてxorしたら0となる個数」
が、先手が負けるパターン数である。
先頭からi番目までの値のxorをXORS[i]で表すような配列と、
先頭〜j(

コード
  long long countWinningIntervals(int L, int R){
    // thanks Leo.DingliYu 
    long long result = 0;
    int times[1000001];
    vector<int> primes;
    bool isprime[100000];
    memset( isprime, true, sizeof(isprime) );
    memset( times, 0 , sizeof(times) );
    isprime[0]=false;
    isprime[1]=false;
    for( ll i = 2 ; i*i <= R; i++ ){
      if( isprime[i] ){
        primes.push_back( i );
        for( ll j = i+i ; j*j <= R; j+= i ){
          isprime[j] = false;
        }
      }
    }
    int primesize = primes.size();
    //cout << primesize << endl;
    int NUM[1000001];
    for( int i = 0 ; i <= R-L ; i++ ){
      NUM[i] = L+i;
    }
    for( int j = 0 ; j < primesize; j++){
      ll p = primes[j];
      ll start = ((L+p-1)/p)*p;
      for( int i = start ; i <= R ; i+=p ){
        while( NUM[i-L]%p == 0 ){
          NUM[i-L]/=p;
          times[i-L]++;
        }
      }
    }
    for( int i = 0 ; i <= R-L ; i++ ){
      if( NUM[i] != 1 ) times[i]++;
      //cout << times[i] << endl;
    }
    int XORS[1000001];
    XORS[0] = times[0];
    for( int i = 1 ; i <= R-L ; i++ ){
      XORS[i] = XORS[i-1]^times[i];
    }
    long long tim[128];
    memset( tim , 0 , sizeof(tim) );
    tim[0]=1;
    for( int i = 0 ; i <= R-L ; i++ ){
      // see [L+?,L+i] = [L,L+i]-{L,L+?] 
      int tot = i+1;
      //cout << XORS[i]<<endl;
      tot -= tim[XORS[i]];
      result += tot;
      tim[XORS[i]]++;
    }
    return result;
    }

SRM563

TopCoder

250-500-850とか

結果報告

Level ProblemName Status Point
Easy KnightCircuit2 PassedSystem Test 229.48
Medium AlternateColors2 PassedSystemTest 231.23
Hard DefectiveAddition Opened 0.0

2問答えて1問チャレンジ成功した大勝利回。
初の2桁順位じゃなかろうか？

1545->1486->1500->1497->1518->1457-> 1595とかそんな感じのレート遷移をしてる。
ちなみに、毎回色が変わる記録はここで途絶えた。

Easy KnightCircuit2

問題

入力で与えられる盤面を、チェスのナイトが動きまわるとする。場所は好きな所からはじめて良く、同じ所に戻ってきても良い。
最大で何種類の枡に到達出来るか答えよ

考えたこと

ガリガリ紙に書く。

  1. 短い辺が１だったら移動不可だから答えは１
  2. 短い辺が２だったら、長い辺の方向にひたすら移動出来るだけ。(長い辺+1)/2が超えた。
  3. 短い辺が３の時、全部移動可能…じゃなかった。3*3の時は真ん中に到達不可能。でも他は全部移動可能(3*4が移動可能と示せたらそれ以上のサイズは帰納法で示せる感じ)
コード
  int maxSize(int w, int h) {
    if( h < w ) return  maxSize( h, w );
    // must w <= h
    if( w == 1 ) return 1;
    if( w == 2 ) return (h+1)/2;
    if( h == 3 ) return 8;
    return w*h;
  }

計算量は勿論定数。

Medium AlternateColors2

問題

赤・緑・青のボールがn個あるとする。
プレイヤーは赤のボールを１つ取って捨てる・緑のボールを１つ取って捨てる・青のボールを１つ取って捨てる
という操作を延々と続ける。（ボールがない色に対する操作はスキップされる）
k回目に赤のボールを取るようなボールの個数のパターンを答えよ

考えたこと

ガリガリ場合分けした。
まず、k-1回目までに捨てられた赤玉の個数をpとする
(1) 緑のボールも青のボールもp個捨てられている場合
最低１つは赤玉があるとして、残ったn-k個は赤・緑・青のどれでも良い。
これは {}_{n-k+2} C_2として計算出来る。
(2)それ以外の場合、捨てられた個数の総数はk-1個なのだから
緑・青それぞれ、最大でmin(k-1-p,p)個、最小でmax(0, k-1-2p)個捨てられる事となる。
（そして捨てられた緑玉・青玉の数の和はk-1-pである)
(2)' k-1-p < p の場合 (この時、max(0,k-1-2p) = 0 であることに注意する)
緑・青の捨てられた玉の個数は(0,k-1-p),(1,k-1-p-1),...,(k-1-p-1,1),(k-1-p,0)
というk-1-p個の可能性がある。
どの場合も緑・青は既に枯渇しているはずだから、残った玉はすべて赤色である。
よって、k-p-1通りである。
(2)'' k-1-p>=pの場合
緑・青の捨てられた玉の個数は(p,k-1-2p),(p-1,k-1-2p-1),...,(k-1-2p-1,p-1),(k-1-2p,p)
のパターンが有る。
最初の場合と最後の場合は、k-1回玉を捨てた後、最低１つは赤玉があるとして、
残りは赤＆緑or 赤＆青で適当に割り振れば良い。つまりn-k+1通り。
＊k-1-2pはpでないことが保証されている(その場合は(1)で計算した）事に注意
残りは(2)'と一緒で、それぞれ１通りである。

コード
  long long countWays(int n, int k) {
    long long result=0;
    ll key = k-1;
    ll rest = n-key;
    for( ll T_r = (key+2)/3; T_r <= key ; T_r++ ){
      //cout << "now: "<< T_r  << endl;
      if( T_r * 3 == key ){
        //cout << rest << endl;
        if( rest == 1 ) result += 1;
        else result += (rest+1)*(rest)/2;
      }
      else{
        ll mi = max( 0LL, key-2*T_r);
        ll ma = min( T_r , key-T_r );
        //cout << mi << "-" << ma << endl;
        if( ma == T_r ){
          //cout << "rest..." << rest << endl;
          result += 2*(rest);
          ma--;
          if( mi == key-2*T_r ) mi++;
        }
        //cout << mi << "-" << ma << endl;
        ll range = ma-mi+1;
        result += range;
      }
      //cout << "result: "<< result << endl;
    }
    return result;
  }

計算量はO(k)。kは最大100000なので余裕で間に合う。

Hard DefectiveAddiction

問題

int 配列 cards と 整数nが与えられる
int配列と同じ長さの配列arrayで
array[i]

考えたこと

何か計算のところはごちゃごちゃ書いてあったけど結局xorでしょ、とまでは思った。
何か凄い賢い方法有りそうなんだけど、思いつかず。