naoya_t@topcoder

SRM369 Div1 Easy: BeautifulString

過去問, 練習 | 18:16 |

Failed System Test...再投稿×2

• AAA..,BBB..を交互にはさんでいくが、A,Bの連続部分が何回ずつになるかが問題
• int a=min(countA,maxA*adiv), b=min(countB,maxB*bdiv); のところはlong longにしないとオーバーフロー

typedef long long ll;

class BeautifulString {
 public:
  int maximumLength(int countA, int countB, int maxA, int maxB) {
    maxA = min(maxA,countA); maxB = min(maxB,countB);
    if(maxA==0) return maxB;
    if(maxB==0) return maxA;
    int adivmin=(countA+maxA-1)/maxA, bdivmin=(countB+maxB-1)/maxB,
        adivmax=countA, bdivmax=countB;
    if(adivmin<bdivmin){ // adivmin >= bdivmin
      swap(countA,countB);
      swap(maxA,maxB);
      swap(adivmin,bdivmin);
      swap(adivmax,bdivmax);
    }
    int adiv=adivmin,bdiv=min(adivmin,bdivmax);
    if(adiv-bdiv>1) adiv=bdiv+1;
    int a=min((ll)countA,(ll)maxA*adiv), b=min((ll)countB,(ll)maxB*bdiv);
    return a+b;
  }
};

SRM370 Div1 Easy: DrawingMarbles

過去問, 練習 | 14:26 |

簡単！と思ってsubmitした（241.68pt）がFailed System Test→再挑戦（10%減点。201.60pt）

• 分母の2500C50とかlong longじゃ無理でしょでしょ
• c()をdoubleにすればOK。long doubleにするほどのことではない模様

失敗作：

#define sz(a)  int((a).size())
#define rep(var,n)  for(int var=0;var<(n);var++)

long long c(int n, int r)
{
  if (n == 0 || r == 0 || r == n) return 1LL;
  if (r > n-r) r = n-r;
  return c(n-1,r-1) * n / r;
}

class DrawingMarbles {
 public:
  double sameColor(vector<int> colors, int n) {
    int cn=sz(colors);
    long long num=0LL;
    int total=0LL;
    rep(i,cn){
      int ci=colors[i]; total+=ci;
      if(ci>=n) num+=c(ci,n);
    }
    return 1.0 * num / c(total,n);
  }
};

成功作：

#define sz(a)  int((a).size())
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n)  for(int var=0;var<(n);var++)

double c(int n, int r)
{
  if (n == 0 || r == 0 || r == n) return 1.0;
  if (r > n-r) r = n-r;
  return c(n-1,r-1) * n / r;
}

class DrawingMarbles {
 public:
  double sameColor(vector<int> colors, int n) {
    int cn=sz(colors);
    double r=0.0;
    int total=0LL;
    tr(colors,it) total+=(*it);
    double denom=c(total,n);
    rep(i,cn){
      int ci=colors[i]; total+=ci;
      if(ci>=n) r+=c(ci,n)/denom;
    }
    return r;
  }
};

SRM371 Div1 Easy: SpiralRoute

過去問, 練習 | 14:06 |

こんなのに19分ぐらいかかってる。時間かかりすぎ＞＜

最後の１〜２行（あるいは１〜２列）になるまで剥いたところで場合分け

class SpiralRoute {
 public:
  vector<int> thronePosition(int w, int l) {
    int xmax=w-1, ymax=l-1, xmin=0, ymin=0;
    vector<int> ans(2,0);
    while(w>2 && l>2){
      w-=2; l-=2; xmax--; ymax--; xmin++; ymin++;
    }
    if(w==l){
      ans[0]=xmin;
      ans[1]=(w==2)?ymax:ymin;
    }else if(w>l){
      ans[0]=(l==1)?xmax:xmin;
      ans[1]=ymax;
    }else{
      ans[0]=xmin;
      ans[1]=(w==1)?ymax:(ymin+1);
    }
    return ans;
  }
};