TopCoder SRM 333 Div1 Medium RepeatedPatterns

問題

'0'または'1'からなる文字列P1,P2が与えられる。
文字列S(n)を、P1を100万回繰り返した後、P2をn回繰り返した文字列とする。
文字列Sを、S(1)+S(2)+……と無限につなげたものとする。

文字列Tを、Sの先頭から10^16文字を取った文字列とする。
TにおいてゼロがzeroCount回連続して現れる最初の位置を求めよ。
現れない場合は-1を返せ。

制約条件

P1の文字数≦50
P2の文字数≦50
zeroCount≦10^16

方針

P1,P2に1が現れるかどうかで場合わけ。

どちらにも現れない場合、Tは0だけなので、zeroCountが10^16以下ならOK
P1のみに0が現れないとき、
(100万回P1)+(P2)+(100万回P1)+(P2)なので、
現れ方は三通り。

P2にのみ0が現れないとき、
何回目のP2の出現でzeroCountが現れるかを計算して、その位置を求める。

コーナーケースがかなり多いので難しい。

ソースコード

class RepeatedPatterns {
  public:
  long long findZeroSegment(string P1, string P2, string zeroCount) {
    int n=P1.size(), m=P2.size();
    ll zero=atoll(zeroCount.c_str());
    
    bool p1=0, p2=0;
    rep(i,n)if(P1[i]=='1')p1=1;
    rep(i,m)if(P2[i]=='1')p2=1;
    
    if(!p1&&!p2){
      if(zero>(ll)1e16)return -1;
      return 0;
    }
    if(!p1){
      int z1=0, z2=0;
      for(int i=0;P2[i]=='0';i++)z1++;
      for(int i=m-1;P2[i]=='0';i--)z2++;
      if(zero<=1000000ll*n+z1)return 0;
      if(zero<=1000000ll*n+z1+z2)return 1000000ll*n+m-z2;
      return -1;
    }
    
    if(zero<=max(n,m)*2){
      string tmp=P1+P1;
      int p=tmp.find(string(zero,'0'));
      if(p!=string::npos)return p;
      tmp=P1+P2+P1;
      p=tmp.find(string(zero,'0'));
      if(p!=string::npos)return ll(1000000-1)*n+p;
      tmp=P2+P1+P2;
      p=tmp.find(string(zero,'0'));
      if(p!=string::npos)return 1000000ll*n+p;
      tmp=P1+P2+P2;
      p=tmp.find(string(zero,'0'));
      if(p!=string::npos)return (2000000ll-1)*n+m+p;
    }
    if(p2)return -1;
    
    int z=0, zpos=n;
    for(int i=0;P1[i]=='0';i++)z++;
    for(int i=n-1;P1[i]=='0';i--)z++, zpos--;
    
    ll pos=(zero-z+m-1)/m;
    if((1000000.0*pos-1)*n+pos*(pos-1.0)/2*m+zpos>=1e17)return -1;
    pos=(1000000*pos-1)*n+pos*(pos-1)/2*m+zpos;
    if(pos+zero>(ll)1e16)return -1;
    return pos;
  }
};