スポンサーサイト

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

CodeChef February Cook-Off 2012

2012/01/23 01:00 ~ 03:30 (JST)
CodeChef January Cook-Off 2012 の参加記録

tourist 回。
なかなかいい結果を出せた。

Tags : プログラミング CodeChef 未解決

結果

A. -
B. -
C. AC (01:17:47)
D. AC (00:26:27)
E. 2WA, 8TLE
Standing : 22/??
Rank (Short) : 39 → 35
Rating (Short) : 1575.811 → 1647.295


問題

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

C. Careful Calculation

正整数 N が与えられる。
N1 = φ(N)
N2 = φ(N1)
N3 = φ(N2)

とするとき、Nx = 1 となる最小の x を求めよ。

φ はオイラーのトーティエント関数。
N は N = p1^k1・p2^k2・…・pm^km と素因数分解した形で与えられる。

1 < pi < 10^5
1 ≦ ki ≦ 10^9
各 pi は相異なる

D. Daily Train

9 部屋、54 席構成の電車が N 輌ある。
席は問題文中の図のように番号付けられている。

X 人のグループが、全員同じ部屋になるように席を予約したい。
席の割り当て方は何通りあるか?

1 ≦ X ≦ 6
1 ≦ N ≦ 10

解答

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

C.
map<int,int> prime_factorize(int a){
map<int,int> res;
for(int p=2;p*p<=a;p++) if(a%p==0) {
int cnt=0;
do{ a/=p; cnt++; }while(a%p==0);
res[p]=cnt;
}
if(a>1) res[a]=1;
return res;
}

int main(){
static map<int,int> pf[100000];
rep(i,100000) pf[i]=prime_factorize(i);

int T; scanf("%d",&T);
while(T--){
int m; scanf("%d",&m);

bool two=false;
static ll c[100000];
rep(i,100000) c[i]=0;
rep(i,m){
int p,k; scanf("%d%d",&p,&k);
c[p]+=k;
if(p==2) two=true;
}

map<int,int>::iterator it;
for(int i=99999;i>2;i--) if(c[i]>0) {
for(it=pf[i-1].begin();it!=pf[i-1].end();++it){
c[it->first]+=it->second*c[i];
}
}

if(!two) c[2]++;
printf("%lld\n",c[2]);
}

return 0;
}

φ をくりかえし作用させると、指数部がだんだん小さくなっていく。
最後の方になると 2^n という形になり、φ(2^n) = 2^(n-1), ..., φ(2) = 1 となって終わる。
というイメージ。

N = p1^k1・p2^k2・…・pm^km
と素因数分解されているとき、
φ(N) = p1^(k1-1)・p2^(k2-1)・…・pm^(km-1)・(p1-1)・(p2-1)・…・(pm-1)
であることを思い出す。

φ(φ(N)) については、φ(N) の各 (pi-1) の部分は素因数分解されて pj^kj たちに組み込まれると考えると、順番に計算していける。

( 3 以上の pi については ) pi-1 が偶数になるということが重要。
pi-1 は偶数なので、素因数分解すると必ず 2 を含む。
つまり、N が 2 のべき乗でない限りは、φ(N) には必ず一つ以上の 2 があらたに掛けられることになる。
なので、すべての 2 を消費するまでの φ を作用させる回数がボトルネックになっていて、これが答え。
最初の 1 回目だけは、N が 2 を素因数に持たないかもしれないので注意。

次のように実装した。
まず、10^5 より小さい数をすべて素因数分解した。
篩の要領でやれば速くできるけど、一つ一つ O(√N) で分解しても間に合った。†

それから、大きい素数から順に、φ を作用させたときに現れる素因数の分布を足していった。
最終的に、2 がいくつ現れるかが計算できたことになる。
大きい値から調べたのは、いわゆるトポロジカル順序というやつで、1 パスで全部計算できるから。

文章での説明が難しい...
コードを読んだ方がわかりやすいかもしれない。

† 素数 - 1 の形の数だけ分解すれば十分だった

D.
const int N_BIN=77;
int nCr[N_BIN+1][N_BIN+1];
void binom(){
rep(n,N_BIN+1) nCr[n][0]=1;
rep(n,N_BIN) rep(r,n+1) nCr[n+1][r+1]=nCr[n][r+1]+nCr[n][r];
}

int main(){
binom();

int x,n; scanf("%d%d",&x,&n);

int ans=0;
while(n--){
char s[64]; scanf("%s",s+1);
int aki[9]={};
for(int i=1;i<=35;i+=2) if(s[i]=='0') aki[(i-1)/4]++;
for(int i=2;i<=36;i+=2) if(s[i]=='0') aki[(i-1)/4]++;
for(int i=54;i>=37;i--) if(s[i]=='0') aki[26-(i-1)/2]++;

rep(i,9) if(aki[i]>=x) ans+=nCr[aki[i]][x];
}
printf("%d\n",ans);

return 0;
}

いわゆるやるだけ問題。
二項係数を足す。

E.

解けなかったけど、考えたところまで書いておく。
まず、x・y = gcd(x,y)・lcm(x,y) なので、方程式を gcd と lcm で書き直してみる。
変数の選択には自由度がある ( x・y と gcd を変数にするとか ) けど、直感的にこれがいいだろうと思った。
すると、方程式は
gcd・lcm = a + b・lcm + c・gcd
となる。

a, b, c の制約から、gcd ≦ 2・10^6 程度の上界が見積もれる。
なので、gcd の値を全探索してみる。
lcm の値は、存在すれば一意に定まる。

gcd, lcm が決まったとき、対応する (x, y) の個数は簡単にわかる。
すなわち、2^( lcm/gcd の異なる素因数の個数 )。

lcm/gcd もそれほど大きくならないので、篩で素因数の個数を前計算しておける。

以上のことから、
・ 前処理に 10^6 log log 10^6 程度
・ テストケース一つあたり 10^6 程度
で答えが出ているはずなんだけど、TLE がかなり厳しくて、この方針だとだめだった。
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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