スポンサーサイト

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

CodeChef February Challenge 2012

2012/02/01 18:30 ~ 02/11 18:30 (JST)
CodeChef February Challenge 2012 の参加記録

今月から 10 問になった。

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

結果

A. AC [1 pts]
B. -
C. -
D. -
E. AC [1 pts]
F. AC [1 pts]
G. AC [1 pts]
H. AC [1 pts]
I. AC [0.523 pts]
J. AC [1 pts]
Standing : 53/2000
Rank (Long) : ??? → 66
Rating (Long) : ??? → 165.802


問題

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

A. Box and Ball System
( 1, 2, ..., N ) の置換 ( σ(1), σ(2), ..., σ(N) ) で、
すべての i について d(i) = d(σ(i)) が成り立つもののの個数を mod 500009 で求めよ。
ただし、( 1, 2, ..., N ) 自身は数えないこと。

1 ≦ テストケース数 ≦ 10^5
3 ≦ N ≦ 2*10^9

E. Lucky Count

F4(x) := ( x を十進数表示したときの 4 の個数 )
F7(x) := ( x を十進数表示したときの 7 の個数 )
とするとき、
F4(L) + F4(L + 1) + ... + F4(R) = F7(L) + F7(L + 1) + ... + F7(R)
なる (L, R) の組 (1 ≦ L ≦ R ≦ N) は何通りあるか?

1 ≦ テストケース数 ≦ 10^5
1 ≦ N ≦ 10^5

F. Lucky Long

N に以下の操作を何回か施して lucky number にする。
最小何回の操作が必要か?

操作は
・ N++
・ N のある桁を 1 から 9 までの好きな数に変える
・ N*=10
のうちいずれか一つ

1 ≦ N ≦ 10^100000

G. Count of Maximum

長さ N の整数配列で最も多く現れる数を答えよ。
複数ある場合は最小のもの。

1 ≦ N ≦ 100

H. Restore the Recipe

未知数 A[i] ( i = 1, 2, .., N ) に対して、
A[Xi] + A[Xi+1] + ... + A[Yi] = Zi
という関係式が M 本与えられる。
すべての関係式をみたす A[] があればそれを一組求めよ。
なければそのことを指摘せよ。

解がある場合は、|A[i]| ≦ 10000 となる解が存在することが保証されている。

2 ≦ N ≦ 65536
1 ≦ M ≦ 2*10^5

I. Smart Chef vs Evil Chef

スタートとゴールが一つずつある迷路が複数与えられるので、すべての迷路でゴールを通過するような経路を求めよ。
短いほど高スコア。

J. Word Counting

長さ 500 以下の文字列 S が与えられる。
S のアナグラムは何通りあるか? mod 10^9+7 で。

解答

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

A.
const int M=500009;

const int P_MAX=1500;
vector<int> p; // P_MAX 以下の素数のリスト
void sieve(){
static bool er[P_MAX+1];
rep(i,P_MAX+1) er[i]=(i>=2);
for(int i=2;i*i<=P_MAX;i++) if(er[i]) for(int j=i*i;j<=P_MAX;j+=i) er[j]=false;
rep(i,P_MAX+1) if(er[i]) p.push_back(i);
}

int main(){
sieve();

const int L=2229283;
static int d[L],d_tmp[L]; // d[i] := ( i の約数の個数 )
rep(i,L) d[i]=1, d_tmp[i]=i;
rep(i,p.size()){
for(int j=p[i];j<L;j+=p[i]){
int c=0;
do{
d_tmp[j]/=p[i];
c++;
}while(d_tmp[j]%p[i]==0);
d[j]*=c+1;
}
}
rep(i,L) if(d_tmp[i]>1) d[i]*=2, d_tmp[i]=1;

int freq[500]={};
static int ans[L]={1};
for(int i=1;i<L;i++){
freq[d[i]]++;
ans[i]=(ll)ans[i-1]*freq[d[i]]%M;
}

int T; scanf("%d",&T);
while(T--){
int n; scanf("%d",&n);
if(n>=L) printf("%d\n",M-1);
else printf("%d\n",(ans[n]-1+M)%M);
}

return 0;
}

答えは、約数が等しい数どうしのグループにわけたときの各グループのサイズの階乗の積。
なので、各数の約数の個数がわかればいい。

mod の値が小さいのがどう考えてもあやしい。

実験してみると、L がある程度大きくなると答えは常に 0 になる ( 500009 の倍数 ) ことがわかる。
実際には 2229283 が境目になる。

この程度のサイズなら、うまくやれば約数の個数を前計算しておける。
篩を応用する。

小さなステップをいくつも積み重ねて解く問題。
とてもいい問題だと思った。

E.
int main(){
static int f4[100001],f7[100001];
rep(i,100001){
int a=i;
do{
if(a%10==4) f4[i]++;
if(a%10==7) f7[i]++;
a/=10;
}while(a>0);
}

static int _freq[200001],*freq=_freq+100000;
for(int i=100000,dif=0;i>0;i--){
dif+=f4[i]-f7[i];
freq[dif]++;
}

// ans[i] := ( f4[L]+..+f4[i] = f7[L]+..+f7[i] をみたす組 (L,i) の個数 (1<=L<=i) )
static int ans[100001];
for(int i=100000,dif=0;i>0;i--){
ans[i]=freq[dif];
dif+=f4[i]-f7[i];
freq[dif]--;
}

// ans[i] := ( f4[L]+..+f4[R] = f7[L]+..+f7[R] をみたす組 (L,R) の個数 (1<=L<=R<=i) )
rep(i,100000) ans[i+1]+=ans[i];

int T; scanf("%d",&T);
while(T--){ int n; scanf("%d",&n); printf("%d\n",ans[n]); }

return 0;
}

数える

F.
main(){
int T,c,i;
char s[100002];
for(scanf("%d ",&T);T--;){
gets(s);
for(c=i=0;s[i];i++) if(s[i]!='4' && s[i]!='7' && s[i]!='\r') c++;
printf("%d\n",c);
}
}

数える

G.
for(1..<>){
<>;
my @freq;
$freq[$_]++ for split / /,<>;

$ans=-1;
for(1..10000){ $ans=$freq[$_], $ians=$_ if $ans<$freq[$_]; }
printf "$ians $ans\n";
}

数える
perl

H.
struct edge{ int v,dist; };

int main(){
int n,m; scanf("%d%d",&n,&m);

static vector<edge> G[65537];
rep(i,m){
// X[l] + X[l+1] + ... + X[r] = z
int l,r,z; scanf("%d%d%d",&l,&r,&z);

// Y[r] - Y[l-1] = z
l--;
G[l].push_back((edge){r, z});
G[r].push_back((edge){l,-z});
}

static ll Y[65537];
static bool vis[65537];
rep(u,n+1) if(!vis[u]) {
vis[u]=true;
Y[u]=0;

queue<int> Q; Q.push(u);
while(!Q.empty()){
int u=Q.front(); Q.pop();

rep(i,G[u].size()){
const edge &e=G[u][i];
if(vis[e.v]){
// 矛盾がないかチェック
if(Y[e.v]-Y[u]!=e.dist){
puts("-1");
return 0;
}
}
else{
vis[e.v]=true;
Y[e.v]=Y[u]+e.dist;
Q.push(e.v);
}
}
}
}

rep(u,n) printf("%lld%c",Y[u+1]-Y[u],u<n-1?' ':'\n');

return 0;
}

B[i] := A[1] + A[2] + .. + A[i]
と変数変換する。
これに気付けるかどうかが最大のポイント。

この変換により、制約式は
B[i] - B[j] = Z
みたいな形になる。
これは、幾何的には 2 点 i, j が Z だけ離れていることを意味する。
これらの制約式がすべて満足されるかどうかは、各連結成分ごとに BFS することで調べられる。

I.
const char *DIR="ENWS";
const int INF=1<<29;
const int dx[]={1,0,-1,0},dy[]={0,-1,0,1};

int n,h[25],w[25];
char maze[25][70][70];

char ans[10001];
void solve(){
// 順番を決める
pair<int,int> len[25];
rep(id,n){
len[id].second=id;

int sx,sy,gx,gy;
rep(i,h[id]) rep(j,w[id]) {
if(maze[id][i][j]=='S') sx=j, sy=i;
if(maze[id][i][j]=='E') gx=j, gy=i;
}

int d[70][70];
rep(i,h[id]) rep(j,w[id]) d[i][j]=INF;
d[sy][sx]=0;
queue< pair<int,int> > Q; Q.push(make_pair(sx,sy));
while(!Q.empty()){
int x=Q.front().first,y=Q.front().second; Q.pop();

if(x==gx && y==gy) break;

rep(k,4){
int xx=x+dx[k],yy=y+dy[k];
if(0<=xx && xx<w[id] && 0<=yy && yy<h[id] && maze[id][yy][xx]!='#' && d[y][x]+1<d[yy][xx]){
d[yy][xx]=d[y][x]+1;
Q.push(make_pair(xx,yy));
}
}
}

len[id].first=d[gy][gx];
}

sort(len,len+n);

// 本処理
ans[0]='\0';
rep(t,n){
int id=len[t].second;

int sx,sy,gx,gy;
rep(i,h[id]) rep(j,w[id]) {
if(maze[id][i][j]=='S') sx=j, sy=i;
if(maze[id][i][j]=='E') gx=j, gy=i;
}

for(int i=0;ans[i];i++){
if(sx==gx && sy==gy) break;
int k;
if(ans[i]=='E') k=0;
if(ans[i]=='N') k=1;
if(ans[i]=='W') k=2;
if(ans[i]=='S') k=3;
int xx=sx+dx[k],yy=sy+dy[k];
if(0<=xx && xx<w[id] && 0<=yy && yy<h[id] && maze[id][yy][xx]!='#'){
sx=xx; sy=yy;
}
}

int pre[70][70];
bool vis[70][70]={};
vis[sy][sx]=true;
queue< pair<int,int> > Q; Q.push(make_pair(sx,sy));
while(!Q.empty()){
int x=Q.front().first,y=Q.front().second; Q.pop();

if(x==gx && y==gy) break;

rep(k,4){
int xx=x+dx[k],yy=y+dy[k];
if(0<=xx && xx<w[id] && 0<=yy && yy<h[id] && maze[id][yy][xx]!='#' && !vis[yy][xx]){
Q.push(make_pair(xx,yy));
vis[yy][xx]=true;
pre[yy][xx]=k;
}
}
}

int i_path=0;
char path[5000]={};
for(int x=gx,y=gy;;){
if(x==sx && y==sy) break;
int k=pre[y][x];
path[i_path++]=DIR[k];
x-=dx[k];
y-=dy[k];
}
for(int i=0;i<i_path-i-1;i++) swap(path[i],path[i_path-i-1]);
strcat(ans,path);
}
}

int main(){
int T; scanf("%d",&T);
while(T--){
scanf("%d",&n);
rep(k,n){
scanf("%d%d",h+k,w+k);
rep(i,h[k]) scanf("%s",maze[k][i]);
}
solve();
puts(ans);
}

return 0;
}

各迷路で最短路を求めて、最短路の短い順に結合しただけ。
特に何もしていない。

J.
const ll M=1000000007;

int main(){
const int INV[11]={-1,1,500000004,166666668,41666667,808333339,301388891,900198419,487524805,831947206,283194722};

int T; scanf("%d ",&T);
while(T--){
char s[501]; gets(s);

ll ans=1;
int freq[128]={};
for(int i=0,a=1;s[i];i++,a++){
freq[s[i]]++;
ans=ans*a%M;
}
rep(c,128) if(freq[c]>0) ans=ans*INV[freq[c]]%M;
printf("%lld\n",ans);
}

return 0;
}

数える
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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