naoya_t@topcoder

SRM473 Div1 Medium(500): RightTriangle

14:33 |

• に該当する場所が空いていない時の処理が最悪ケースでTLE
• の場所をインクリメントしておいて、あとで均せばO(points+places)で行けるじゃん
• それだけ。passed system test

typedef long long ll;
#define sz(a)  int((a).size())
#define pb  push_back
#define FOR(var,from,to) for(int var=(from);var<=(to);var++)
#define rep(var,n)  for(int var=0;var<(n);var++)
#define all(c)  (c).begin(),(c).end()
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define found(s,e)  ((s).find(e)!=(s).end())

typedef long long ll;

class RightTriangle {
 public:
  long long triangleCount(int places, int points, int a, int b, int c) {
    if(places & 1) return 0LL;

    vector<int> cnt(places,0);
    for(ll n=0; n<points; ++n) {
      ll ix = n*n*a + n*b + c;
      cnt[ix % places]++;
    }

    int r=0;
    rep(ix,places*2){
      int j=ix%places;
      cnt[j]+=r;
      r=max(cnt[j]-1,0);
      cnt[j]=min(1,cnt[j]);
    }
    
    vector<int> acc(places*2+1,0);
    acc[0]=0;
    rep(n,places) acc[n+1]=acc[n]+cnt[n];
    int ap=acc[places];
    rep(n,places+1) acc[places+n]=ap+acc[n];
    
    ll accum=0LL;
    int h=places/2;
    rep(n,places){
      int nh = (n + h) % places;
      if(cnt[n] && cnt[nh]) {
        accum += acc[n+h] - acc[n+1];
      }
    }
    return accum;
  }
};

SRM473

11:56 |

リハビリ

Div1では初めての３問submit →oxx

DIV	level	問題名	競技中	後で	System Test	通過率	備考	levenshtein
1	250	SequenceOfCommands	o	-	passed (233.65)	-	_	0
1	500	RightTriangle	撃沈	-	-	-	_	?
1	1000	RooksParty	撃沈	-	-	-	_	?

Easy(250): SequenceOfCommands

• まあ4回回せばいいんだけど
• 一巡した時の向きで場合分け
• passed; 233.65

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

int dx[4]={0,-1,0,1}, dy[4]={1,0,-1,0};

class SequenceOfCommands {
 public:
  string whatHappens(vector <string> commands) {
    int dir=0;
    int n=sz(commands),x=0,y=0;
    rep(i,n){
      tr(commands[i],it){
        switch(*it){
          case 'S': x+=dx[dir],y+=dy[dir]; break;
          case 'L': dir=(dir+1)%4; break;
          case 'R': dir=(dir+3)%4; break;
        }
      }
    }

    switch(dir){
      case 1: case 3:
        return "bounded";
      case 0:
        return (x!=0 || y!=0)? "unbounded" : "bounded";
      case 2:
        return "bounded";
    }
  }
};

Medium(500): RightTriangle

• 直角三角形になるのは長辺が直径のとき
• 撃沈。256.11 →0.0
• 以下、駄目コード (TLE)

typedef long long ll;
#define sz(a)  int((a).size())
#define pb  push_back
#define FOR(var,from,to) for(int var=(from);var<=(to);var++)
#define rep(var,n)  for(int var=0;var<(n);var++)
#define all(c)  (c).begin(),(c).end()
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define found(s,e)  ((s).find(e)!=(s).end())

typedef long long ll;

class RightTriangle {
 public:
  long long triangleCount(int places, int points, int a, int b, int c) {
    if(places & 1) return 0LL;
	vector<int> cnt(places,0);
    for(ll n=0; n<points; ++n) {
      ll ix = (n*n*a + n*b + c) % (long long)places;
      rep(j,places) {
        int jx=(ix+j)%places;
        if (cnt[jx]==0) { cnt[jx]=1; break; }
      }
    }
    vector<int> acc(places*2+1,0);
    acc[0]=0;
    rep(n,places) acc[n+1]=acc[n]+cnt[n];
    int ap=acc[places];
    rep(n,places+1) acc[places+n]=ap+acc[n];
    ll accum=0LL;
    int h=places/2;
    rep(n,places){
      int nh = (n + h) % places;
      if(cnt[n] && cnt[nh]) {
        accum += acc[n+h] - acc[n+1];
      }
    }
    return accum;
  }
};

Hard(1000): RooksParty

• ルークの動かし方ぐぐりましたごめんなさい
• 残り数十秒でサンプルケース通せたので記念submit
• 速攻轟沈。568.48 →0.0
• Practice Room通したけどとりあえず２件答えあわない。
  • →パターンをちゃんと網羅してませんね。2x2で ox xo みたいなのとかですら入ってない
  • あと、組み合わせ数の算出はMODしながらやる例のやつを使うべき
• 以下、駄目コード

typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<string> vs;
typedef vector<long long> vll;
#define sz(a)  int((a).size())
#define pb  push_back
#define FOR(var,from,to) for(int var=(from);var<=(to);var++)
#define rep(var,n)  for(int var=0;var<(n);var++)
#define all(c)  (c).begin(),(c).end()
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define found(s,e)  ((s).find(e)!=(s).end())

typedef pair<int,int> ii;

typedef long long ll;
const ll MOD=1000000009LL;

long long comb(int n, int r)
{
  if (n == 0 || r == 0 || r == n) return 1LL;
  if (r > n-r) r = n-r;
  return comb(n-1,r-1) * n / r;
}
int nc,sm;
vector<vector<ii> > gm;
vector<vector<int> > gmx;

ll sub(int ix,int r,int c){
  ll sum=0;
  if(ix==nc) return 1;
  if (r==0 || c==0) return -1;
  for(int j=sz(gm[ix])-1;j>=0;--j){
    ii p=gm[ix][j]; int pr=p.first, pc=p.second;
    if (pr<=r && pc<=c) {
      ll a=sub(ix+1,r-pr,c-pc);
      if (a>=0) sum += comb(r,pr)*comb(c,pc)*gmx[ix][j]*a;
    }
  }
  return sum % MOD;
}
class RooksParty {
 public:
  int countArrangements(int R, int C, vector<int> counts) {
    nc=sz(counts),sm=0; rep(i,nc)sm+=counts[i];
    if(nc==1){
      return (int)(comb(R*C,counts[0]));
    }
    gm.assign(nc,vector<ii>(0));
    gmx.assign(nc,0);
    rep(i,nc){
      int c=counts[i];
      for(int j=1;j<=min(c,30);j++){
        int k=(c+j-1)/j;
        gm[i].pb(ii(j,k));
        gmx[i].pb(comb(j*k,c));
      }
    }
    return (int)(sub(0,R,C) % MOD);
  }
};

Challenge Phase

• 1000が速攻轟沈
• 500も続いて撃沈
• 250は残った

結果

233.65points

Room: 10/19

Div1: 246/508

1461→1489 青残留