naoya_t@topcoder

SRM433 Div1 Medium: SettingTents

過去問, 練習 | 00:14 |

• 幅w=1〜N、高さh=1〜Mの長方形を考え、その中にぴったり収まる菱形の個数を得る関数count(w,h)を考えれば

• ４頂点が辺の上にあるとは限らない。本戦ではそれで失敗
• 同じ菱形を重複して数えていたりして悩んだ
• 時間あるのでatan使って角度でソートとかしちゃう

#define sz(a)  int((a).size())
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define all(c)  (c).begin(),(c).end()
#define evenp(x) (((x)&1)==0)
#define oddp(x) (((x)&1)==1)

class SettingTents {
  int count(int w, int h){
    double cx=0.5*w, cy=0.5*h;
    int c=0;
    int x0=0,x2=w;
    set<pair<pair<int,int>,pair<int,int> > > cnt;
    for(int y0=0;y0<=h;y0++){
      int y2=h-y0;
      if(y2==y0) continue;
      for(int x1=0;x1<=w;x1++){
        int x3=w-x1;
        if(x1==x3) continue;
        int rhs=w*(2*x1-w);
        int l=2*y0-h;
        if(abs(rhs)%abs(l)) continue;
        int yy=rhs/l+h; // 2y
        if(oddp(yy)) continue;
        int y1=yy/2, y3=h-y1;
        if(y1<0 || h<y1) continue;
        if(y0*y1*y2*y3>0) continue;
        if(x0==x1 && y0==y1) continue;
        if(x2==x1 && y2==y1) continue;
        if(x3==x1 && y3==y1) continue;
        vector<pair<double,pair<int,int> > > v(4);
        v[0] = make_pair(atan2(-cy+y0,-cx+x0), make_pair(x0,y0));
        v[1] = make_pair(atan2(-cy+y1,-cx+x1), make_pair(x1,y1));
        v[2] = make_pair(atan2(-cy+y2,-cx+x2), make_pair(x2,y2));
        v[3] = make_pair(atan2(-cy+y3,-cx+x3), make_pair(x3,y3));
        sort(all(v));
        cnt.insert(make_pair(v[0].second, v[1].second));
      }
    }
    c = cnt.size();
    if(evenp(w) && evenp(h)) c++;
    return c;
  }
 public:
  int countSites(int N, int M) {
    int c=0;
    for(int w=1;w<=N;w++)
      for(int h=1;h<=M;h++)
        c+=(N-w+1)*(M-h+1)*count(w,h);
    return c;
  }
};

SRM433 Div1 Easy: MagicWords

過去問, 練習 | 20:25 |

• next_permutationを使う方針はそのまま
• L/K周期の文字列になっているのでは
• Kとして可能性があるのは各文字の出現回数のGCDの約数のみ
• で、その最大がKなら可
• いちおうメモ化

typedef vector<int> vi;
#define sz(a)  int((a).size())
#define pb  push_back
#define all(c)  (c).begin(),(c).end()
#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++)
#define found(s,e)  ((s).find(e)!=(s).end())

int gcd(int m, int n)
{
  if (m == 0 || n == 0) return 0;
  if (m == 1 || n == 1) return 1;
  if (m == n) return m;
  while (1) {
        if (m == 0) return n;
        if (n == 0) return m;
        if (m > n) m %= n; else n %= m;
  }
}

class MagicWords {
  int L, subl, k;
  set<int> alt;

  int check(const string &s){
    int kmax=0;
    tr(alt,it){
      int k_=*it;
      int sl=L/k_;
      bool c=true;
      for(int j=1;j<k_;j++){
        rep(i,sl) if(s[i]!=s[i+sl*j]) {c=false;break;}
      }
      if(c) kmax=max(kmax,k_);
    }
    return (kmax==k)?1:0;
  }
 public:
  int count(vector<string> S, int K) {
    int N=sz(S);//1-8
    L=0; k=K;
    vector<int> chc(26,0);
    rep(i,N){
      int len=sz(S[i]); L+=len;
      rep(j,len){
        chc[ S[i][j]-'A' ]++;
      }
    }
    if(L%K) return 0;
    subl=L/k;
    int g=0;
    rep(i,26){
      if(chc[i]%K) return 0;
      if(chc[i]>0) {
        g=(g==0)?chc[i]:gcd(g,chc[i]);
      }
    }
    for(int i=1;i<=g;i++){
      if(g%i)continue;
      alt.insert(i);
    }

    map<string,int> memo;
    vi iota(N); rep(i,N) iota[i]=i;
    int cnt=0;
    do{
      string w="";
      rep(i,N) w+=S[iota[i]];
      if(found(memo,w)) cnt += memo[w];
      else cnt += (memo[w]=check(w));
    } while(next_permutation(all(iota)));
    return cnt;
  }
};

SRM433

02:44 |

01.21.2009

2問submit、2問沈没。0点＞＜

250点問題: MagicWords

• 単純にnext_permutation()ではTLEなのでメモ化
• Failed System Test

500点問題: SettingTents

• Challenge Timeで撃沈

1000点問題: BarbarianInvasion

• 開いた。題意は読み取れた。15分では無理だった。

0点。369/691位... レーティング落ちるだろうな

1537→1487

青...

SRM358 Div1 Easy: BrokenButtons

過去問, 練習 | 00:58 |

• SRM前のウォーミングアップ(2)
• とりあえずsubmit→Failed System Test

SRM359 Div1 Easy: DriveFailures

過去問, 練習 | 00:34 |

• SRM前のウォーミングアップ(1)
• 簡単...242.10points(5'09),Passed System Test

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

class DriveFailures {
 public:
  vector<double> failureChances(vector <double> failureProb) {
    int n=sz(failureProb);//1-15
    vector<double> ans(n+1,0.0);
    ans[0]=1.0;
    rep(i,n){
      vector<double> w(n+1,0.0);
      double r=failureProb[i];
      rep(j,n){
        w[j] +=ans[j]*(1.0-r);
        w[j+1] +=ans[j]*r;
      }
      rep(j,n+1) ans[j]=w[j];
    }
    return ans;
  }
};