スポンサーサイト

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

CodeChef February 2011 Challenge

CodeChef の月一ロングコンテスト CodeChef February 2011 Challenge の参加記録。
コンテスト期間は 2/1 15:00 ~ 2/11 15:00 (IST)。
CodeChef のコンテストは今回で三度目。

学校の試験期間とかぶっていたけど、結構時間をとって取り組んだのでそこそこ満足できる結果は出せた。
どの問題も制限時間がシビアで、定数倍の最適化に苦労した。

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

結果

問題の上から順に
Accepted (1[pt])
Accepted (0.734[pts])
Accepted (1[pt])
Accepted (1[pt])
Opened
Opened

Standing : 34/426
Rank : 514 → 272
Rating : 10.9839863694 → 27.700249522658


問題

Bogosort
n 個の数 1, 2, .., n がランダムに並べられている。
この数列を次のアルゴリズムを用いてソートするとき、アルゴリズム中のループ回数の期待値を既約分数で求めよ。
( 2 ≦ n ≦ 150 )

アルゴリズム
1. L <- 1, R <- n
2. 数列の L 番目から R 番目をランダムに並び替える (1-indexed)
3. 数列の左端から順に調べていって、i 番目の位置に i でないものが最初に現れる位置を L とする
4. 数列の右端から順に調べていって、i 番目の位置に i でないものが最初に現れる位置を R とする
5. if 数列が整列されている then end
6. goto 2.


Coloring Colorable Graphs
頂点数 500 以下、辺数 10000 以下の 3 彩色可能なグラフが与えられる。
できるだけ少ない色数で彩色せよ。実際に彩色した例も答えること。
使った色数が少ないほうが高得点。

Counting Terms
n ≦ 1015, k ≦ 1015, p ≦ 100 ( p は素数 ) が与えられる。
f(n, k) := [ ( x1 + x2 + .. + xk )n の展開式において係数が p で割り切れない項の数 ] とするとき、
∑[i=0→n] f(i,k) を mod 1000003 で求めよ。

Glass Measurement
与えられた n, x1, x2, ..., xn
( n ≦ 10, 1 ≦ xi ≦ 107, 1 ≦ min xi ≦ 105, すべて整数)
に対して、
S := { a1 x1 + a2 x2 + .. + an xn | ai ≧ 0 (整数) }
と定める。
次の 2 つの問いに答えよ。

1.
S に含まれないような最大の整数 M (≧0) を求めよ。そのような M がない場合はそのことを報告せよ。

2.
Q (≦ 106) 個の数 ( 正確にはその生成規則 ) が与えられるので、それらの数の中で S に含まれるものの数を答えよ。

Milestones
2 次元平面上に n (≦10000) 個の点が与えられる。(座標はすべて整数)
これらの点は高々 7 本の直線で覆えることが仮定されている。
同一直線上にある点の個数の最大値を求めよ。

Rush Hour
ラッシュアワー (パズル) を解け。 (必要な最小ステップ数を求めよ。)
ルールはここを参照。

ただし、与えられる問題は以下の条件をみたす。
・ 盤面サイズは 12×12 以下
・ 車の総数は 26 台以下
・ 対象の車 (外に出したい車) は常に水平方向を向いている
・ 最小ステップ数は 10 以下
・ 問題は一様ランダムに作られている (より詳しくは問題文に書いてある)

解答

言語は C++。テンプレはここを参照。
ただし、1 問だけ Java で書いた。

Bogosort
import java.util.Scanner;
import java.math.BigInteger;

class Rational{
public static final Rational ZERO=valueOf(BigInteger.ZERO);
public static final Rational ONE=valueOf(BigInteger.ONE);

private BigInteger deno,nume;

public Rational(BigInteger nu,BigInteger de){
BigInteger g=de.gcd(nu);
deno=de.divide(g); // reduction
nume=nu.divide(g);
}

// nu/de are already irreducible & nu, de are not referred from other variables
private Rational(BigInteger nu,BigInteger de,int dummy){
deno=de;
nume=nu;
}

public String toString(){
if(nume.equals(BigInteger.ZERO)) return "0";
if(deno.equals(BigInteger.ONE)) return nume.toString();
return nume.toString()+"/"+deno.toString();
}

static public Rational valueOf(BigInteger val){
return new Rational(val,BigInteger.ONE);
}

public Rational add(Rational val){
BigInteger g=deno.gcd(val.deno);
BigInteger deno2=deno.divide(g);
BigInteger nume2=nume.multiply(val.deno.divide(g))
.add(val.nume.multiply(deno2));
g=nume2.gcd(g);
return new Rational(nume2.divide(g),deno2.multiply(val.deno.divide(g)),0);
}

public Rational subtract(Rational val){
BigInteger g=deno.gcd(val.deno);
BigInteger deno2=deno.divide(g);
BigInteger nume2=nume.multiply(val.deno.divide(g))
.subtract(val.nume.multiply(deno2));
g=nume2.gcd(g);
return new Rational(nume2.divide(g),deno2.multiply(val.deno.divide(g)),0);
}

public Rational multiply(Rational val){
BigInteger g1=nume.gcd(val.deno);
BigInteger g2=deno.gcd(val.nume);
return new Rational(nume.divide(g1).multiply(val.nume.divide(g2)),
deno.divide(g2).multiply(val.deno.divide(g1)),0);
}

public Rational divide(Rational val){
BigInteger g1=nume.gcd(val.nume);
BigInteger g2=deno.gcd(val.deno);
return new Rational(nume.divide(g1).multiply(val.deno.divide(g2)),
deno.divide(g2).multiply(val.nume.divide(g1)),0);
}

public Rational add(BigInteger val){
return new Rational(nume.add(deno.multiply(val)),deno,0);
}

public Rational subtract(BigInteger val){
return new Rational(nume.subtract(deno.multiply(val)),deno,0);
}

public Rational multiply(BigInteger val){
BigInteger g=deno.gcd(val);
return new Rational(nume.multiply(val.divide(g)),deno.divide(g),0);
}

public Rational divide(BigInteger val){
BigInteger g=nume.gcd(val);
return new Rational(nume.divide(g),deno.multiply(val.divide(g)),0);
}
}

public class Main{
public static void main(String[] args){
BigInteger[] fact=new BigInteger[151];
fact[0]=BigInteger.ONE;
for(int i=1;i<=150;i++) fact[i]=fact[i-1].multiply(BigInteger.valueOf(i));

BigInteger[][] c=new BigInteger[151][151];
Rational[][] p=new Rational[151][151];
for(int n=0;n<=150;n++){
for(int k=0;k<=n;k++){
if(n-k==0) c[n][k]=BigInteger.ONE;
else if(n-k==1) c[n][k]=BigInteger.ZERO;
else{
c[n][k]=fact[n-k-2];
c[n][k]=c[n][k].multiply(BigInteger.valueOf(k+1));
c[n][k]=c[n][k].multiply(BigInteger.valueOf((n-k-2)*(n-k-1)+1));
}
p[n][k]=new Rational(c[n][k],fact[n]);
}
}

Rational[] ex=new Rational[151];
ex[0]=Rational.ZERO;
for(int n=1;n<=150;n++){
Rational coef=Rational.ONE;
coef=coef.subtract(p[n][0]);
coef=Rational.ONE.divide(coef);

ex[n]=Rational.ZERO;
for(int k=1;k<=n;k++){
ex[n]=ex[n].add(ex[n-k].multiply(c[n][k]));
}
ex[n]=ex[n].divide(fact[n]).add(BigInteger.ONE).multiply(coef);
}

Scanner sc=new Scanner(System.in);
for(int t=sc.nextInt();t>0;t--){
int n=sc.nextInt();
System.out.println(ex[n]);
}
}
}

多倍長有理数が必要な問題。
多倍長演算ライブラリも有理数ライブラリも持ってなかったので、多倍長演算を標準装備している Java で組んだ。
Java はよく知らないので、変なコードを書いてるかもしれない。

有理数クラスの実装は boost の Rational クラスを参考にした。
特に、和と差を計算する際に、あらかじめ分母分子の公約数で割っておいて高速化する工夫が役に立った。
( これがないと TLE になった。)

アルゴリズム自体は DP で期待値を求める、典型的な問題。
ただし、漸化式にループがあるのでちょっと式変形しないといけない。
類題は SRM488 TheBoredomDivOne とか。
苦手だったこの手の問題も、少しずつ解けるようになってきて嬉しい。

漸化式は
En = ∑[k=0→n] pn, k En-k + 1
ここで
En : サイズ n の問題の期待値
pn, k : サイズ n の問題で 1 回シャッフルして k 個の数字が固定される確率

pn, k は次の式になる。
pn, k = 0 (if n-k=1 or n-k<0)
pn, k = 1 (if n-k=0)
pn, k = (k+1) (n-k+2)! { (n-k-2)(n-k-1) + 1 } / (n!) (otherwise)

上の 2 つは境界での例外ケース。3 つめの式の導出を簡単に書いておく。
・ 全パターンは n! 個あるので、ちょうど k 個が固定される場合の数を n! で割ったものが pn, k.
・ ちょうど k 個が固定される場合の数は、k 個を固定するパターンが k+1 通りあって、残った n-k 個のなかで左端と右端にくる数には制約がかかるので、ここを包除原理でうまく間引く。

有理数の加減乗除を定数時間と見れば、計算量は O(n^2)。
実際は、数十桁の数を扱うのでもっと時間がかかる。
ちなみに、Editorials によると O(n) で解く方法があるらしい。

Coloring Colorable Graphs
/* naive greedy algorithm, O(n^2) */
int solve1(const vvb &adj,vi &color){
int n=adj.size();

int cmax=1;
rep(u,n){
int c; // determine the color of node u
{
bool used[501]={};
rep(v,u) if(adj[u][v]) used[color[v]]=true;
for(c=1;;c++) if(!used[c]) break;
}
color[u]=c;
cmax=max(cmax,c);
}

return cmax;
}

/* Largest First Algorithm (Welsh-Powell), O(n^2) */
int solve2(const vvb &adj,vi &color){
int n=adj.size();

vi deg(n);
rep(u,n)rep(v,u) if(adj[u][v]) deg[u]++,deg[v]++;

vector<pii> deg2(n);
rep(u,n) deg2[u]=mp(deg[u],u);
sort(deg2.begin(),deg2.end(),greater<pii>());

vi ord(n);
rep(i,n) ord[i]=deg2[i].second;

int cmax=1;
rep(i,n){
int u=ord[i],c;
{
bool used[501]={};
rep(j,i){
int v=ord[j];
if(adj[u][v]) used[color[v]]=true;
}
for(c=1;;c++) if(!used[c]) break;
}
color[u]=c;
cmax=max(cmax,c);
}

return cmax;
}

/* Smallest Last Algorithm, O(n^2) */
int solve3(const vvb &adj,vi &color){
int n=adj.size();

vi deg(n);
rep(u,n)rep(v,u) if(adj[u][v]) deg[u]++,deg[v]++;

vi ord(n);
rep(i,n){
int u=min_element(deg.begin(),deg.end())-deg.begin();
rep(v,n) if(adj[u][v]) deg[v]--;
deg[u]=INF;
ord[i]=u;
}
reverse(ord.begin(),ord.end());

int cmax=1;
rep(i,n){
int u=ord[i],c;
{
bool used[501]={};
rep(j,i){
int v=ord[j];
if(adj[u][v]) used[color[v]]=true;
}
for(c=1;;c++) if(!used[c]) break;
}
color[u]=c;
cmax=max(cmax,c);
}

return cmax;
}

/* DSatur Algorithm (Brelaz), O(n^2) */
int solve4(const vvb &adj,vi &color){
int n=adj.size();

vi deg(n),dsat(n);
vector< set<int> > adjcolor(n);
rep(u,n)rep(v,u) if(adj[u][v]) deg[u]++,deg[v]++;

int cmax=1;
vb colored(n);
rep(i,n){
int u=-1;
rep(v,n)if(!colored[v]){
if(u==-1
|| dsat[u]<dsat[v] || (dsat[u]==dsat[v] && deg[u]<deg[v])) u=v;
}

int c;
{
bool used[501]={};
rep(v,n)if(colored[v] && adj[u][v]) used[color[v]]=true;
for(c=1;;c++) if(!used[c]) break;
}
color[u]=c;
colored[u]=true;
cmax=max(cmax,c);

rep(v,n)if(adj[u][v]){ // update degree & degree of saturation
deg[v]--;
if(adjcolor[u].count(c)==0){
adjcolor[u].insert(c);
dsat[u]++;
}
}
}

return cmax;
}

/* Recursive Largest First Algorithm', O(n^3) */
int solve5(const vvb &adj,vi &color){
int n=adj.size();

vi deg(n);
rep(u,n)rep(v,u) if(adj[u][v]) deg[u]++,deg[v]++;

int c,cnt=0;
vb colored(n);
for(c=1;cnt<n;c++){
vb ban(n); // ban := { v in V | v is adjacent to some nodes colored c }
while(1){
int u=-1;
rep(v,n)if(!colored[v] && !ban[v]){
if(u==-1 || deg[u]<deg[v]) u=v;
}
if(u==-1) break;

color[u]=c;
colored[u]=true;
cnt++;

rep(v,n)if(adj[u][v]){
ban[v]=true;
deg[v]--;
}
}
}

return c;
}

int main(){
int T; scanf("%d",&T);
while(T--){
int n,m; scanf("%d%d",&n,&m);
vvb adj(n,vb(n));
rep(i,m){
int u,v; scanf("%d%d",&u,&v);
u--,v--;
adj[u][v]=adj[v][u]=true;
}

const int N=5;
int chnum[N];
vvi color(N,vi(n));
chnum[0]=solve1(adj,color[0]);
chnum[1]=solve2(adj,color[1]);
chnum[2]=solve3(adj,color[2]);
chnum[3]=solve4(adj,color[3]);
chnum[4]=solve5(adj,color[4]);

int iopt=min_element(chnum,chnum+N)-chnum;
rep(j,n){
if(j) putchar(' ');
printf("%d",color[iopt][j]);
}
putchar('\n');
}

return 0;
}

ここここを参考にして、5 種類のヒューリスティックスを試してみた。
1. 何の工夫もせずに順番に使っていない色を割り当てる。
2. 次数の大きいノードほど先に色を決める
3. 次数の小さいノードほど後で色を決める
4. 飽和次数の大きいノードから色を決める
5. 色でループして、各色について次数の大きいノードから色を決める

各方法を単独で試したときのスコアが以下
1. 0.31 pts
2. 0.39 pts
3. 0.666 pts
4. 0.495 pts
5. 0.638 pts

最終的に submit したコードは 5 種類の方法を全部試してみて一番いいものを採用する方法で、0.734 pts.

Editorials によると、グラフが 3 彩色可能なことを利用する、良いヒューリスティクスがあるらしい。
次数最大のノードに注目して、そのノードに隣接するノードだけで部分グラフを作ると、元のグラフが 3 彩色であることから、部分グラフは 2 部グラフになる。2 部グラフは線形時間で 2 彩色できる。みたいな感じ。

Counting Terms
const ll M=1000003;

ll modpow(int a,int n){ // calc a^n (mod M)
int r=1;
for(ll x=a;n;n>>=1,x=(x*x)%M) if(n&1) r=(r*x)%M;
return r;
}

int inv(int a){ // find x s.t. a*x=1 (mod M) (M:prime)
return modpow(a,M-2);
}

int factinv[100];
void precalc(void){
factinv[0]=1;
rep(i,99) factinv[i+1]=((ll)factinv[i]*inv(i+1))%M;
}

ll modnCr(ll n,ll r){ // calc nCr (mod M) (M:prime)
if(n<r) return 0;
if(n-r<r) r=n-r;

ll a=1;
for(int i=r;i>0;i--){
a=(a*((n-i+1)%M))%M;
}
return (a*factinv[r])%M;
}

int main(){
precalc();

int T; scanf("%d",&T);
while(T--){
ll n,k;
int p; scanf("%lld%lld%d",&n,&k,&p);

ll f[100]; // f[r] = kHr[r] : number of r-multicombination from k (r<p)
rep(r,p) f[r]=modnCr(k+r-1,r);

int len,a[60];
{ // n = a[0] + a[1]*p + a[2]*p^2 + ... + a[len-1]*p^(len-1)
int i=0;
ll m=n;
do{
a[i++]=m%p;
m/=p;
}while(m);
len=i;
}

ll dp[60][100];
dp[0][0]=f[0];
for(int j=1;j<p;j++) dp[0][j]=(dp[0][j-1]+f[j])%M;
for(int i=1;i<len;i++){
dp[i][0]=(f[0]*dp[i-1][p-1])%M;
for(int j=1;j<p;j++){
dp[i][j]=(dp[i][j-1]+(f[j]*dp[i-1][p-1])%M)%M;
}
}

ll ans=dp[0][a[0]];
for(int i=1;i<len;i++){
if(a[i]==0) continue;
ans=(dp[i][a[i]-1]+(f[a[i]]*ans)%M)%M;
}
printf("%lld\n",ans);
}

return 0;
}

展開式の各項の係数は多項係数になる。
n<p のときは、多項係数の式に p が現れないので、すべての項が p で割り切れない。
ゆえに、f(n, k) は重複組み合わせで書ける。

n≧p のときが問題。

p が素数のとき
( x1 + x2 + .. + xk )p ≡ x1p + x2p + .. + xkp (mod p)
に注目して式変形すると、次のことがわかった。

n の p 進展開を n = a0 + a1 p + .. + as ps とすれば、
f(n, k) = Π[i=0→s] f(ai, k)
各 ai は p より小さいから、f(n, k) が計算できる。

あとは f(i, k) を i = 0 → n で足し合わせればいい。
n ≦ 1015 なので、ナイーブにやっては間に合わない。
そこで、桁方向に進める DP をやる。これは Codeforces #51 D で勉強した。
以前はメモ化再帰で書いたので、今回は表を埋める DP で書いてみた。
ここの部分はもっとスマートに書けると思う。

0 を p 進展開するときの処理を間違えて、ちょっとはまった。

Glass Measurement
int gcd(int a,int b){ return b?gcd(b,a%b):a; }

int gcd(int n,int *x){
int g=x[0];
rep(i,n-1) g=gcd(g,x[i+1]);
return g;
}

int main(){
int T; scanf("%d",&T);
while(T--){
int n; scanf("%d",&n);
int x[10],xmin=INF;
rep(i,n){
scanf("%d",x+i);
xmin=min(xmin,x[i]);
}

int xmod[10]; // for speeding up of modular arithmetic
rep(i,n) xmod[i]=x[i]%xmin;

int g=gcd(n,x);
if(g>1) rep(i,n) x[i]/=g;
xmin/=g;

static ll dis[100000];
rep(i,xmin) dis[i]=1LL<<62;
dis[0]=0;

ll ans;
priority_queue< ll,vector<ll>,greater<ll> > pq; pq.push(0);
for(int cnt=0;;){
ll now=pq.top(); pq.pop();
int pos=now%xmin;
if(dis[pos]<now) continue;
if(++cnt==xmin){ ans=now-xmin; break; }

rep(i,n){
ll next=now+x[i];
int nextpos=pos+xmod[i]; if(nextpos>=xmin) nextpos-=xmin;
if(next<dis[nextpos]){
dis[nextpos]=next;
pq.push(next);
}
}
}

printf("%lld\n",g==1?ans:-1);

int Q,ans2=0;
ll a,b,c; scanf("%d%lld%lld%lld",&Q,&a,&b,&c);
ll q=b%c; a%=c;
rep(i,Q){
q+=a; if(q>=c) q-=c;
ll qdivg=q/g;
if(q%g==0 && dis[qdivg%xmin]<=qdivg) ans2++;
}
printf("%d %d\n",Q-ans2,ans2);
}

return 0;
}

よくわからなかったので、とりあえず小さいケースを出力してみて考えた。

最大の M があるかないかというのは、
gcd(x1, .., xn) = 1
かどうかを判定すればいい。
実際、x1, .., xn に共通の約数 (>1) があれば、それらの和も同じ約数をもつから作れない数が無数に出てくることになる。

M を求めるのには、Xmin := min xi ≦ 105 という制約をうまく使う。
作ることができる数を mod Xmin で見たときに、0, 1, .., Xmin-1 をすべて作ることができるような最初のタイミングが分かればいい。一度これらを作ることができたら、以降は Xmin を足すことですべての数を作ることができる。

そこで Xmin 個のノードからなるグラフを考える。
グラフのノードは、0, 1, .., Xmin-1 に対応している。
グラフのエッジは、ノードが表す数に各 xi を足したときの遷移を表す。
エッジの重みが xi になる。

数 0 は必ず作れることに注意すると、0, 1, .., Xmin-1 をすべて作ることができるような最初のタイミングを求めるのは、ノード 0 を始点とする単一始点最短路を求めることに相当する。
なので、Dijkstra のアルゴリズムが使える。

そのまま書くと TLE になったけど、剰余の計算を加減算で済ますことで微高速化したら間に合った。

Milestones (時間外)
int main(){
srand(77);

int T; scanf("%d",&T);
while(T--){
int n; scanf("%d",&n);
static int x[100000],y[100000];
rep(i,n) scanf("%d%d",x+i,y+i);

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

int ans=0;
rep(t,200){
int p=rand()%n,q=rand()%n,cnt=0;
if(p==q){ t--; continue; }
rep(i,n) if((x[q]-x[p])*(y[i]-y[p])==(y[q]-y[p])*(x[i]-x[p])) cnt++;
ans=max(ans,cnt);
}
printf("%d\n",ans);
}

return 0;
}

Editorials を見ながら解いた。

まさかの Monte Carlo 法。
高々 7 本の直線で覆えるという性質が、この方法でも十分高い確率で最適解を求められるようにしている。

50 個の点を選べばそれらの点からなる直線群の中に 7 本のうちの 1 本が必ずあるということを利用した、決定論的アルゴリズムで解いた人も多かったとのこと。

Rush Hour

想定解法は IDA* アルゴリズムらしい。
評価関数をうまく決められるかどうかが鍵。
いつかじっくりと解く。
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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