Hatena::Grouptopcoder

naoya_t@topcoder RSSフィード

2010-01-15

SRM458 Div1 Hard: ModuloFourDivisor

| 22:39 | SRM458 Div1 Hard: ModuloFourDivisor - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM458 Div1 Hard: ModuloFourDivisor - naoya_t@topcoder SRM458 Div1 Hard: ModuloFourDivisor - naoya_t@topcoder のブックマークコメント

昨日の900点問題を解いてみた。

Nの約数を列挙するためには素因数分解すればいいんですが…

最初、オイラーのφ関数がどうのとかあれこれ考えていたのですが、ここではmod 4だけが問題になっているので、4で割った余りがそれぞれ0,1,2,3な素数(※0は無いですね。2は2だけ)は同一視して

N = 2^S x (4k+1)^T x (4k+3)^U

が見えたら解けたも同然...

a,c

4で割って余りが0になるのはS≧2な全パターンなので

S=0,S=1:

 a = 0

S≧2:

 a = [2..S]x[0..T]x[0..U] = (S-1)(T+1)(U+1) > 0

同様に、余りが2になるのはS=1な全パターンなので

S=0:

 c = 0

S>=1:

 c = [1]x[0..T]x[0..U] = (T+1)(U+1) ≧1

c≠0のとき、aはcで割り切れなければならない。∵a=(S-1)c

あと

  • a≠0のとき(Nは4の倍数)には必ずc≠0(2の倍数)
  • c=0(Nは2の倍数でない)のときには必ずa=0(当然4の倍数でもない)

b,d

余りが1(または3)になるのはS=0の場合。Uが偶数なら1,奇数なら3になる。Tはいくつでも関係ない。よって

b = [0]x[0..T]x[0,2,4,...n<=U] = (T+1)[(U+2)/2] ≧1

d = [0]x[0..T]x[1,3,5,...m<=U] = (T+1)[(U+1)/2] ≧0

  • U=0のときd=0
  • Uが奇数のときb=d
  • Uが偶数のときb=d+(T+1)

という関係が成り立つ。b≠dのとき [(U+2)/2]=[(U+1)/2]+1 のため (T+1) はbとdの最大公約数に等しいことも使える。

  • あと、c>0のときc=b+d

以上の条件をクリアするものをA,B,C,Dの全組み合わせ(高々50^4通り)の中から数え上げればよい。

Mediumより簡単じゃないか...

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

ll gcd(ll m, ll 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 ModuloFourDivisor {
  bool possible(ll a,ll b,ll c,ll d){
    if (b==0) return false;
    if (a>0 && c==0) return false;
    if (c==0 && a>0) return false;
    if (c>0) {
      if (a % c) return false;
      if (b+d != c) return false;
    }
    if (d==0 || b==d) return true;
    if (b == d+gcd(b,d)) return true; // ※※
    return false;
  }

 public:
  int countQuadruplets(vector<long long> A, vector<long long> B, vector<long long> C, vector<long long> D) {
    int cnt=0;
    tr(A,at) tr(B,bt) tr(C,ct) tr(D,dt)
      if (possible(*at,*bt,*ct,*dt)) cnt++;
    return cnt;
  }
};

最初、※※のチェックをc>0のときにしかしていなくてfailed system test → そこを直したら通った

トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20100115

2009-10-21

SRM451 Div1 Medium: BaronsAndCoins

| 16:00 | SRM451 Div1 Medium: BaronsAndCoins - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM451 Div1 Medium: BaronsAndCoins - naoya_t@topcoder SRM451 Div1 Medium: BaronsAndCoins - naoya_t@topcoder のブックマークコメント

投稿コード(墜落)

  • yが小さい順にソート。先頭にスタート地点(0,0)を入れる
  • 後ろから見て行った
  • 比べる値が間違っている: dy>1の時は、dx[0]の最大値,dx[dy-1]の最小値の両方を求め、前後と比較する必要がある
  • cons,car,cdrマクロはネタ
#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 forr(var,from,to) for(int var=(from);var<=(to);var++)
#define forrr(var,from,to) for(int var=(to);var>=(from);var--)
#define found(s,e)  ((s).find(e)!=(s).end())

typedef pair<int,int> i_i;
typedef pair<int,pair<int,int> > i_ii;
#define cons(x,y) make_pair((x),(y))
#define car(x) ((x).first)
#define cdr(x) ((x).second)
#define sub(p,q) make_pair(car(p)-car(q),cdr(p)-cdr(q))
#define cadr(x) (x).second.first
#define cddr(x) (x).second.second

class BaronsAndCoins {
 public:
  int getMaximum(vector <int> x, vector <int> y) {
    int N=sz(x);

    vector<i_i> p(N);
    rep(i,N) p[i]=cons(y[i],x[i]); p.pb(cons(0,0)); N++;
    
    vector<vector<i_i> > tt(N,vector<i_i>(N));
    sort(all(p)); // reverse(all(p));
    
    forr(i,0,N-2){
      forr(j,i+1,N-1){
        tt[i][j] = sub(p[j],p[i]);
      }
    }

    priority_queue<pair<int,pair<int,int> > > pq;  // j,cnt,ymax
    forr(j,1,N-1) pq.push(cons(j,cons(1,INT_MAX)));
    map<int,int> score;

    int cntmax=0;
    while(!pq.empty()){
      i_ii x = pq.top(); pq.pop();
      int j=car(x),cnt=cadr(x),last_dxmax = cddr(x);
      if (found(score,j) && score[j]>cnt) continue;
      score[j] = cnt;
      forrr(i,0,j-1){
        i_i dif = tt[i][j];
        int dy=car(dif),dx=cdr(dif); if (dy==0) continue;
        int dxmax = (dx - (dy*(dy-1)/2))/dy;
        if (dxmax <= 0 || dxmax >= last_dxmax) continue;
        if (i==0) {
          if (cnt>cntmax) cntmax = cnt;
        } else {
          pq.push(cons(i,cons(cnt+1,dxmax)));
        }
      }
    }
    return cntmax;
  }
};

最終コード (Passed System Test)

  • 前からダイクストラ的に
#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 FOR(var,from,to) for(int var=(from);var<=(to);var++)
#define FORR(var,from,to) for(int var=(to);var>=(from);var--)
#define found(s,e)  ((s).find(e)!=(s).end())

typedef pair<int,int> i_i;
typedef pair<int,pair<int,int> > i_ii;
#define cons(x,y) make_pair((x),(y))
#define car(x) ((x).first)
#define cdr(x) ((x).second)
#define cadr(x) (x).second.first
#define cddr(x) (x).second.second

class BaronsAndCoins {
  vector<i_i> p;
  vector<vector<i_i> > tt, sx;

 public:
  int getMaximum(vector <int> x, vector <int> y) {
    int N=sz(x);

    p.resize(N);
    rep(i,N) p[i]=cons(x[i],y[i]);
    p.pb(cons(0,0)); N++;
    sort(all(p));
    
    tt.resize(N);
    sx.resize(N);
    rep(i,N) {
      tt[i].resize(N);
      sx[i].resize(N);
    }
        
    FOR(i,0,N-2){
      FOR(j,i+1,N-1){
        int dx = car(p[j]) - car(p[i]);
        int dy = cdr(p[j]) - cdr(p[i]);
        if (dy==0) continue;
        
        int sx0max = (dx - (dy*(dy-1)/2))/dy;
        if (sx0max <= 0) continue;
        int sx1min = sx0max + (dy-1) + ((dx - (dy*(dy-1)/2) - sx0max*dy)?1:0);

        tt[i][j] = cons(dx,dy);
        sx[i][j] = cons(sx0max,sx1min);
      }
    }

    vector<map<int,int> > sc(N,map<int,int>());
    sc[0][0] = 0; // dmin, cnt

    int cntmax = 0;
    FOR(i,0,N-2) {
      tr(sc[i],it) {
        int dmin = car(*it), cnt = cdr(*it);
        FOR(j,i+1,N-1) {
          if (car(tt[i][j]) <= 0) continue;

          i_i s = sx[i][j];
          int smin=car(s), smax=cdr(s);
          if (dmin < smin) {
            int cnt_next = cnt + 1;
            if (found(sc[j],smax)) {
              sc[j][smax] = max(cnt_next,sc[j][smax]);
            } else {
              sc[j][smax] = cnt_next;
            }
            if (cnt_next > cntmax) cntmax = cnt_next;
          }
        }
      }
    }
    return cntmax;
  }
};
トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20091021

2009-10-18

SRM450 Div1 Easy: OrderedNim

| 05:59 | SRM450 Div1 Easy: OrderedNim - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM450 Div1 Easy: OrderedNim - naoya_t@topcoder SRM450 Div1 Easy: OrderedNim - naoya_t@topcoder のブックマークコメント

(Div2 Mediumと同じ問題)

自分の番で2個以上とれる時は無条件に勝つのか。それだけのことか><

#define sz(a)  int((a).size())

class OrderedNim {
 public:
  string winner(vector<int> layout) {
    int n=sz(layout), r=1;
    for(int i=n-2;i>=0;i--){
      if(layout[i]==1) r=1-r;
      else r=1; ///ここ重要
    }
    return r ? "Alice" : "Bob";
  }
};
トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20091018

2009-09-30

SRM beta 2 Div1 Easy: TwistedMatrix

| 11:13 | SRM beta 2 Div1 Easy: TwistedMatrix - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM beta 2 Div1 Easy: TwistedMatrix - naoya_t@topcoder SRM beta 2 Div1 Easy: TwistedMatrix - naoya_t@topcoder のブックマークコメント

提出コード(もちろん通らない)

#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
using namespace std;

typedef long long ll;
#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++)

ll ubin(const string& s){
  ll n=0LL;
  for (int i=0,c=sz(s); i<c; i++){
    n = (n<<1LL) | (s[i]=='1'?1:0);
  }
  return n;
}
vector<ll> lex(const vector<string>& A){
  int n=sz(A);
  vector<ll> v(n,0LL);
  rep(i,n){
    v[i] = ubin(A[i]);
  }
  return v;
}
vector<string> turn(const vector<string>& A,int xmin,int ymin,int dir){
  vector<string> At(all(A));
  switch(dir){
    case 1: // cw
      At[ymin][xmin]     = A[ymin+1][xmin];
      At[ymin][xmin+1]   = A[ymin][xmin];
      At[ymin+1][xmin]   = A[ymin+1][xmin+1];
      At[ymin+1][xmin+1] = A[ymin][xmin+1];
      break;
    case -1: // ccw
      At[ymin][xmin]     = A[ymin][xmin+1];
      At[ymin][xmin+1]   = A[ymin+1][xmin+1];
      At[ymin+1][xmin]   = A[ymin][xmin];
      At[ymin+1][xmin+1] = A[ymin+1][xmin];
      break;
  }
  return At;
}

class TwistedMatrix {

 public:
  int d(int c1, int c2){ /// これは使ってないよ
    if (c1==c2) return 0;
    if (c2=='?') return 9;
    return c2-c1;
  }

  int N, M;
  
  int diff(const vector<string>& A, const vector<string>& B){
    int cnt = 0;
    rep(n,N){
      rep(m,M){
        if (A[n][m]=='?' || B[n][m]=='?') continue;
        if (B[n][m]!=A[n][m]) cnt++;
      }
    }
    return cnt;
  }
  vector<string> zero(const vector<string>& A){
    vector<string> z(all(A));
    rep(n,N){
      rep(m,M){
        if (A[n][m]=='?') z[n][m] = '0';
      }
    }
    return z;
  }
  
  vector <string> solve(vector <string> A, vector <string> B) {
    N=sz(A);
    M=sz(A[0]);

    vector<ll> minlex(N, (1LL << M) - 1LL);
    vector<string> ans(0);
    
    rep(n,N-1){
      rep(m,M-1){
        vector<string> At1 = turn(A,m,n,1);
        if(diff(At1,B)==0) {
          if (lex(At1) < minlex){
            ans = zero(At1);
            minlex = lex(At1);
          }
        }
        vector<string> At2 = turn(A,m,n,-1);
        if(diff(At2,B)==0) {
          if (lex(At2) < minlex){
            ans = zero(At2);
            minlex = lex(At2);
          }
        }
      }
    }
    return ans;
  }
};

修正コード(これは通る)

int ubin(const string& s){
  int n=0;
  for (int i=0,c=sz(s); i<c; i++){
    n = (n<<1) | (s[i]=='1'?1:0);
  }
  return n;
}
vector<int> lex(const vector<string>& A){
  int n=sz(A);
  vector<int> v(n,0);
  rep(i,n){
    v[i] = ubin(A[i]);
  }
  return v;
}
vector<string> turn(const vector<string>& A,int xmin,int ymin,int dir){
  vector<string> At(all(A));
  switch(dir){
    case 1: // cw
      At[ymin][xmin]     = A[ymin+1][xmin];
      At[ymin][xmin+1]   = A[ymin][xmin];
      At[ymin+1][xmin]   = A[ymin+1][xmin+1];
      At[ymin+1][xmin+1] = A[ymin][xmin+1];
      break;
    case -1: // ccw
      At[ymin][xmin]     = A[ymin][xmin+1];
      At[ymin][xmin+1]   = A[ymin+1][xmin+1];
      At[ymin+1][xmin]   = A[ymin][xmin];
      At[ymin+1][xmin+1] = A[ymin+1][xmin];
      break;
  }
  return At;
}

class TwistedMatrix {
  int N, M;

 public:
  int diff(const vector<string>& A, const vector<string>& B){
    int cnt = 0;
    rep(n,N){
      rep(m,M){
        if (A[n][m]=='?' || B[n][m]=='?') continue;
        if (B[n][m]!=A[n][m]) cnt++;
      }
    }
    return cnt;
  }

  vector<string> zero(const vector<string>& A, const vector<string>& B){
    vector<string> z(all(A));
    rep(n,N){
      rep(m,M){
        if (A[n][m]=='?') {
          z[n][m] = (B[n][m]=='?') ? '0' : B[n][m];
        }
      }
    }
    return z;
  }
  
  vector <string> solve(vector <string> A, vector <string> B) {
    N=sz(A);
    M=sz(A[0]);

    // vector<ll> minlex(N, (1LL << M) - 1LL);
    vector<int> minlex(N, (1 << M));
    vector<string> ans(0);
    
    rep(n,N-1){
      rep(m,M-1){
        for(int dir=-1;dir<=1;dir+=2) {
          vector<string> At = turn(A,m,n,dir);
          if(diff(At,B)==0) {
            vector<string> tmp = zero(At,B);
            vector<int> la = lex(tmp);
            if (la < minlex){
              ans = tmp;
              minlex = la;
            }
          }
        }
      }
    }
    return ans;
  }
};
トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20090930

2009-09-10

SRM448 Div1 Easy: TheBlackJackDivOne

| 02:14 | SRM448 Div1 Easy: TheBlackJackDivOne - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM448 Div1 Easy: TheBlackJackDivOne - naoya_t@topcoder SRM448 Div1 Easy: TheBlackJackDivOne - naoya_t@topcoder のブックマークコメント

なんで落とされたか

#define sz(a)  int((a).size())
#define pb  push_back
#define all(c)  (c).begin(),(c).end()
#define mset(arr,val)  memset(arr,val,sizeof(arr))
#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())

class TheBlackJackDivOne {
  vector<int> rest;
  
  int cval(int c){
    if ('0'<=c &&c<='9')return c-'0';
    switch(c){
      case 'T':case'J':case'Q':case 'K': return 10;
      case 'A': return 11;
    }
  }
    
 public:
  double sb(double r,int re,int to,int ma){
    double d=0;

    for(int i=1;i<=11;i++){
      if(rest[i]==0) continue;

      double m_ = 1.0*rest[i]/re;
      int to_ = to - i;

      if(to_<=0) { d += r*ma*m_; continue; }

      rest[i]--;
      d += sb(r*m_,re-1,to_,ma+1);
      rest[i]++;
    }
    return d;
  }
  
  double expected(vector<string> cards) {
    int i;
    rest.resize(12); rep(i,12) rest[i]=0;
    for(i=2;i<=9;i++) rest[i]+=4;
    rest[10]+=16; rest[11]+=4;
    
    int n=sz(cards);

    vector<int> v(n);
    int sc=0;
    rep(i,n){
      int c = cval(cards[i][0]);
      v[i] = c;
      rest[c]--;
      sc+=c;
      // if(sc>21) return 0.0; ////OOPS
      if(sc>=21) return 0.0;
    }

    return sb(1.0, 52-n,21-sc,1);
  }
};

>21を>=21にすればokですね

これだけのことでした。馬鹿なの?死ぬの?

とりあえず書き取り練習

>= >= >= >= >= >= >= >= >= >= >= >= >= >= >= >= >= >= >= >=

>= >= >= >= >= >= >= >= >= >= >= >= >= >= >= >= >= >= >= >=

>= >= >= >= >= >= >= >= >= >= >= >= >= >= >= >= >= >= >= >=

トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20090910