Hatena::Grouptopcoder

naoya_t@topcoder RSSフィード

2009-01-14

SRM369 Div1 Easy: BeautifulString

| 18:16 | SRM369 Div1 Easy: BeautifulString - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM369 Div1 Easy: BeautifulString - naoya_t@topcoder SRM369 Div1 Easy: BeautifulString - naoya_t@topcoder のブックマークコメント

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;
  }
};
トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20090114