スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

CodeChef The January 2011 Cook-Off

CodeChef で毎月 1 回開かれる Coof-Off コンテストの参加記録。
日本時間では 1/24 1:00~3:30 に行われた。
Coof-Off コンテストは初参加。CodeChef 主催のコンテストは今回で 2 回目。

Tags : プログラミング CodeChef

Coof-Off コンテストは初めてだったので、簡単に概要説明。
あくまでも今回の場合で、今後も同じかどうかは分からない。

・ 問題は 5 問。
・ うち 3 問が Easy, 1 問が Medium, 1 問が Hard に分類されている。分類はコンテストが終わってから公表される。
・ 5 点満点。各問について、正解すれば 1 点。難易度による点数の差はない。
・ 点数が同じ場合は、正解までの時間が短いほうが順位が上。
・ 提出した解答が不正解の場合は、不正解 1 つにつき 20 分のペナルティ。何回でも提出できる。

結果

便宜上、問題を問題ページでみて上から順に A~E と呼ぶことにする。
A. WA,AC
B. -
C. AC
D. -
E. AC
Standing : 25/528


問題

問題セットの原文はここを参照。

A. Chef team
0 以上、264 より小な 2 つの整数 n, k が与えられる。
二項係数 nCk を計算せよ。
なお、結果は 264 より小さいことが保証されている。

B. Divisors number divisibility
1018 以下の正整数 n が与えられる。
条件「x は n の倍数 かつ x は n 個の約数をもつ」をみたす正整数 x の個数を答えよ。
そのような x が無数にあるときは INF と答えよ。

C. Holes in the text
アルファベット大文字だけからなる文字列が与えられる。
文字列中に穴はいくつあるか?
( たとえば、P は 1 つの穴をもつ。B は 2 つの穴をもつ。)

D. Time of collisions
n 個の質量が等しい球が一直線上に並べられている。
それぞれの球は異なる速度をもって等速直線運動をしている。
球は十分小さく、点とみなせる。

2 つ以上の球がぶつかるときは完全弾性衝突をするものとする。
たとえば、球 A, B, C, D, E がこの位置関係で一斉に衝突したときは、
球 A と E の速度が入れ替わり、球 B と D の速度が入れ替わり、 球 C の速度は変わらない。

時刻 0 における各球の位置と速度が与えられる。
球が衝突する時刻をすべて足し合わせた数を答えよ。
無限回の衝突が起こる場合は INF と答えよ。
結果は既約な帯分数で表すこと。

n ≦ 50000.
すべての球について、初期位置は絶対値 1000000 以下の整数, 初速は絶対値 20 以下の整数とする。

E. Whole submatrix
N×M のグリッドがあり、各格子点には 0 or 1 が割り当てられている。

(L,K)-window を次で定義する。

L+K 個の自然数の組 (R1, ..., RL, C1, ..., CK) であり、
LK 個のグリッド上の格子点 (Ri, Cj) (i = 1, ..., L; j = 1, ..., K) がすべて 1 であるものを (L,K)-window と定義する。
( 実際、図に描いてみると、窓に見えなくもない。)

与えられた N, M, L, K に対して、 グリッド上にある (L,K)-window の個数を mod 1000000080798150871 で答えよ。
1 ≦ L, N ≦ 1000; 1 ≦ K, M ≦3.

解答

言語は C++。テンプレはここを参照。

A.
ull gcd(ull a,ull b){
for(;b;swap(a,b)) a%=b;
return a;
}

int main(){
int T; scanf("%d",&T);
while(T--){
ull n,r; scanf("%llu%llu",&n,&r);
if(n<r){ puts("0"); continue; }
if(n-r<r) r=n-r;

vector<ull> deno,nume;
for(ull i=r;i>=2;i--) deno.pb(i);
for(ull i=n;i>=n-r+1;i--) nume.pb(i);

int nd=deno.size(),nn=nume.size();
rep(i,nd){
rep(j,nn){
ull g=gcd(deno[i],nume[j]);
deno[i]/=g,nume[j]/=g;
if(deno[i]==1) break;
}
}

ull ans=1;
rep(i,nn) ans*=nume[i];
printf("%llu\n",ans);
}

return 0;
}

結果が符号なし 64 bit 整数に収まるといってくれているので、計算途中でオーバーフローしないことだけを注意していればいい。
計算は二項係数の定義どおり。
nCr = n・…・(n-r+1)/(r!)
ただし、掛け合わせる前に約分をすべて済ましてしまうようにした。

Editorials に出ている方法のほうが、高速かつシンプルでよかった。

B. (時間外)
/* Xorshift RNG by George Marsaglia */
ull xor64(){
static ull x=88172645463325252LL;
x^=(x<<13);
x^=(x>>7);
return x^=(x<<17);
}

ull modmul(ull a,ull b,ull m){ // a*b (mod m)
ull r=0;
for(;b;b>>=1,a=(a<<1)%m) if(b&1) r=(r+a)%m;
return r;
}

ull modpow(ull a,ull n,ull m){ // a^n (mod m)
ull r=1;
for(ull x=a;n;n>>=1,x=modmul(x,x,m)) if(n&1) r=modmul(r,x,m);
return r;
}

bool MillerRabin(ull n,int k=30){
if(n<=1) return false;
if(!(n&1)) return n==2;
if(n%3==0) return n==3;

int s=0; // n-1 = 2^s * d (d: odd)
ull d=n-1;
while(!(d&1)) s++,d>>=1;

while(k--){
ull a=xor64()%(n-3)+2;
ull x=modpow(a,d,n);
if(x==1 || x==n-1) continue;
bool b=false;
for(int r=1;r<s;r++){
x=modmul(x,x,n);
if(x==1) return false;
if(x==n-1){ b=true; break; }
}
if(!b) return false;
}

return true;
}

int main(){
ull fact[30];
fact[0]=fact[1]=1;
for(int i=2;i<30;i++) fact[i]=i*fact[i-1];

const int Ne=1001000;
static bool er[Ne]; er[0]=er[1]=true;
for(int i=2;i*i<Ne;i++) if(!er[i]) for(int j=i*i;j<Ne;j+=i) er[j]=true;

vi p; rep(i,Ne) if(!er[i]) p.pb(i);

int T; scanf("%d",&T);
while(T--){
ull n; scanf("%llu",&n);

if(n==4){ puts("1"); continue; }

int cnt=0;
bool b=false;
for(int i=0;(ull)p[i]*p[i]*p[i]<=n;i++){
if(n%p[i]==0){
n/=p[i],cnt++;
if(n%p[i]==0){ puts("-1"); b=true; break; }
}
}
if(b) continue;

// first case ( n=1 )
if(n==1){ printf("%llu\n",fact[cnt]); continue; }

// second case ( n=p (p: prime) )
if(MillerRabin(n)){ printf("%llu\n",fact[cnt+1]); continue; }

// third case ( n=p^2 (p: prime) )
ull rtn=(ull)(sqrt((double)n)+0.5);
if((rtn-1)*(rtn-1)==n || rtn*rtn==n || (rtn+1)*(rtn+1)==n){
puts("-1"); continue;
}

// fourth case ( n=p*q (p,q: prime) )
printf("%llu\n",fact[cnt+2]);
}

return 0;
}

[ 2011/02/17 追記 ]

Editorials を見ながら。
CodeChef は丁寧な解説がついているから復習しやすくてとてもいい。
方針は Editorials そのままなので、大まかな流れだけ書くことにする。

答えは次のようになる。
  • n = 4 のとき、1

  • n ≠ 4 かつ n が平方因子をもたないとき、( n の素因数の数 ) !

  • n ≠ 4 かつ n が平方因子をもつとき、∞

○ 証明の概略
  • x が 2 のべき乗のときと、そうでないときで場合分け

  • n = Π pj と素因数分解すると、
    n = τ(x) から x = Π pjaj でないといけない。
    τ(x) = Π (aj + 1) = Π pj = n より、条件をみたす x の個数は n !

  • うまく x を決めれば、条件をみたす x が無数にあることがわかる

○ アルゴリズムの概略
1018 以下の n が平方因子をもつかどうかを判定するのが難しい。
まず、cbrt(n) 以下のすべての素数 p について、n を p で割れるだけ割る。( cbrt(・) は 3 乗根 )
もちろん、このときに平方因子が見つかればそこで終了。
見つからなければ、n は高々 2 つの素数の積になっているはず。
( もし 3 つ以上の素数の積なら、すでに見つかっていないとおかしい )
ここで 4 つに場合分けする。
・ n = 1 のとき → 簡単にチェックできる
・ n が素数のとき → 高速な素数判定アルゴリズムを使うとチェックできる
・ n が素数の平方のとき → 平方根をとればチェックできる
・ n が 2 素数の積のとき → 上のいずれにも該当しなければこのパターン

法則を見つけるのだけでもかなり難しい。
もし見つけられても、べき剰余や素数判定などの基本的な道具をあらかじめ用意しておかないと、とても時間内に書けない。

C.
int main(){
int hole[128];
hole['A']=1,hole['B']=2,hole['C']=0,hole['D']=1,hole['E']=0,hole['F']=0,
hole['G']=0,hole['H']=0,hole['I']=0,hole['J']=0,hole['K']=0,hole['L']=0,
hole['M']=0,hole['N']=0,hole['O']=1,hole['P']=1,hole['Q']=1,hole['R']=1,
hole['S']=0,hole['T']=0,hole['U']=0,hole['V']=0,hole['W']=0,hole['X']=0,
hole['Y']=0,hole['Z']=0;

int T; scanf("%d",&T);
while(T--){
char s[101]; scanf("%s",s);
int cnt=0;
for(int i=0;s[i];i++) cnt+=hole[s[i]];
printf("%d\n",cnt);
}

return 0;
}

やるだけ。
Q の穴が 1 つか 2 つかでちょっとだけ悩んだ。(フォントによっては 2 つにもみえる)

D. (時間外)
ll gcd(ll a,ll b){ return b?gcd(b,a%b):a; }

class MixedFraction{
ll a,n,d; // a+n/d

public:
MixedFraction(){ a=n=0; d=1; }

MixedFraction(ll A){ a=A; n=0; d=1; }

MixedFraction(ll N,ll D){
n=N,d=D;
if(d<0) n=-n,d=-d;
ll g=gcd(n,d);
n/=g,d/=g;
a=n/d;
n%=d;
}

MixedFraction &operator+=(const MixedFraction &mf){
ll g=gcd(d,mf.d);
d/=g;
n=n*(mf.d/g)+mf.n*d;
g=gcd(n,g);
n/=g;
d*=mf.d/g;

a+=mf.a+n/d;
n%=d;

return *this;
}

const char *c_str()const{
static char s[64];
if (a==0 && n==0) strcpy(s,"0");
else if(a!=0 && n==0) sprintf(s,"%lld",a);
else if(a==0 && n!=0) sprintf(s,"%lld/%lld",n,d);
else sprintf(s,"%lld %lld/%lld",a,n,d);
return s;
}
};

int main(){
int T; scanf("%d",&T);
while(T--){
int n; scanf("%d",&n);
static pii ball[50000];
rep(j,n) scanf("%d%d",&ball[j].first,&ball[j].second);
sort(ball,ball+n);

const int OFSET=20;
ll ans=0,ans2[41]={},N[41]={},S[41]={};
rep(j,n){
int x=ball[j].first,v=ball[j].second;
for(int d=1;d<=20-v;d++){
ll tmp=x*N[v+d+OFSET]-S[v+d+OFSET];
ans+=tmp/d;
ans2[d]+=tmp%d;
}
N[v+OFSET]++;
S[v+OFSET]+=x;
}

MixedFraction ans3(ans);
for(int d=1;d<=40;d++) ans3+=MixedFraction(ans2[d],d);
puts(ans3.c_str());
}

return 0;
}

[ 2011/02/17 追記 ]

Editorials を見ながら解いた。変数名もそのまま同じものを使った。

まず、球に区別はないので、球が衝突することは衝突せずにすりぬけることと同じである。
これを見抜けないと、解くきっかけすらつかめない。

それに気付けば、求めたい値の数式が書き下せる。
でもそのままだと O(N2) 時間かかるので遅すぎる。

そこで、速度の絶対値が 20 以下という制約に注目する。
2 つの球の速度差 d で式を分解する。1 ≦ d ≦ 40 である。
そうすると計算をうまく省略することができて、O(NlogN + NV) 時間のアルゴリズムが得られる。
ここで、 V = 2 max { vj }. NlogN はソートの分。

この問題のために帯分数クラスを作ってみた。
とりあえずは、問題で必要だったいくつかのコンストラクタ, += 演算子, c_str() 関数だけを実装した。
そのうち、ちゃんと仕上げて公開するかもしれない。( 需要はないだろうけど )

E.
const ull M=1000000080798150871ULL;

int main(){
static ull nCr[1001][1001];
rep(n,1001) nCr[n][0]=1;
for(int n=1;n<=1000;n++)rep(r,n+1) nCr[n][r]=(nCr[n-1][r]+nCr[n-1][r-1])%M;

int T; scanf("%d",&T);
while(T--){
int n,m,l,k; scanf("%d%d%d%d ",&n,&m,&l,&k);
int wall[1000]={};
rep(j,n){
char s[4]; scanf("%s",s);
rep(i,m) if(s[i]=='1') wall[j]|=1<<i;
}

ull ans=0;
rep(row,1<<m){
int cnt1=0;
rep(i,m) if(row&(1<<i)) cnt1++;
if(cnt1!=k) continue;

int s=0;
rep(j,n) if((row&wall[j])==row) s++;
if(s<l) continue;

ans=(ans+nCr[s][l])%M;
}

printf("%llu\n",ans);
}

return 0;
}

行数が列数に比べてとても少ないタイプの問題は、AOJ で解いたことがある。
(AOJ0525 おせんべいをひっくりかえす)

この問題も同じ考え方で解ける。
行に関しては全部の選び方を調べる。行数が少ないから、そうしても大したコストにはならない。
選ぶ行を固定してしまえば、列の選び方が何通りあるかはすぐにわかる。
選んだ行に対応する位置がすべて 1 になっている列の数を s とすると、列の選び方は、二項係数 sCl に等しい。
s ≦ 1000 なので、二項係数の値は前計算してもっておくことができる。
計算は、有名な漸化式 sCl = s-1Cl + s-1Cl-1 を使って、DP 式にやる。
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

Author : fura2
数学・コンピュータを中心に、考えたこと・やったことを書いていきます。

誤植等を含め、間違いはご指摘いただければ幸いです。

FC2カウンター
検索フォーム
最新記事
最新コメント
最新トラックバック
月別アーカイブ
リンク
RSSリンクの表示
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。