スポンサーサイト

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

CodeChef May Long Contest 2011

CodeChef May Long Contest 2011 の参加記
2011/05/01 18:30 ~ 05/11 18:30 (JST)
コンテストの正式名が毎月微妙に変わっていて、参加者側としてはちょっと困る。

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

結果

問題を、問題ページの上から順に A, B, .. と呼ぶことにする。
A. AC [0.453 pts]
B. AC [1 pts]
C. -
D. -
E. -
F. AC [1 pts]
Standing : 42/608
Rank (Long) : 168 → 145
Rating (Long) : 54.806 → 64.297


問題

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

A. Bickering Cooks
N (2 ≦ N ≦ 500) 人の cook を 2 つの空でない集合 S, T に分けたい。
何組かの cook i と cook j の間には、d(i, j), q(i, j) という量が与えられている。

すべての組について、d(i, j) の総和をとったものを dTot,
集合 S と集合 T の間のすべての組について、d(i, j) の総和をとったものを d(S, T) とする。
qTot, q(S, T) も同様に定義する。

(q(S,T)/d(S,t))*(dTot/qTot) をできるだけ小さくするような S, T を求めよ。

B. The Great Wall of Byteland
2 × 2 の L 字型のブロック
X
XX

と、1 × 1 の正方形のブロック
#
を使って、2 × N の長方形を敷き詰める場合の数を mod 1000000007 で求めよ。
ブロックは、回転、反転させてもいい。

1 ≦ テストケースの数 ≦ 1000
1 ≦ N ≦ 109

C.

D.

E. Pruning Trees
辺に正の重みがついている、頂点数 n の木が与えられる。
木からいくつかの枝を取り除いてできるグラフが次の性質を持つようにする。

グラフの各連結成分 C について、
ある頂点 rC が存在し、C のすべての頂点 v に対して dist(rC, v) ≦ d となる。
( dist(u, v) は u, v をつなぐパスに含まれる枝の重みの和とする )

グラフに残っている枝の重みの和を最大化せよ。

1 ≦ n ≦ 100
0 ≦ d ≦ 109
1 ≦ 枝の重み ≦ 107

F. Tree Product
頂点に重みをもつ、高さ H の完全二分木が与えられる。
根から葉までの道で、道上の頂点の重みの積が最大になるものを mod 1000000007 で求めよ。

1 ≦ H ≦ 15
1 ≦ 頂点の重み ≦ 109

解答

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

A.
int main(){
srand(time(0));

int T; scanf("%d",&T);
while(T--){
int n,nd,nq; scanf("%d%d%d",&n,&nd,&nq);
static int d[500][500],q[500][500];
rep(u,n) rep(v,n) d[u][v]=q[u][v]=0;
int u0,v0;
rep(i,nd+nq){
int u,v,val; scanf("%d%d%d",&u,&v,&val);
u--, v--;
if(i<nd) d[u][v]=d[v][u]=val;
else q[u][v]=q[v][u]=val;
if(i<nd) u0=u, v0=v;
}

bool S[500];
rep(u,rand()%n) S[u]=true;
random_shuffle(S,S+n);

rep(t,20*n){
int a=rand()%n;
ll d_Ssum=0,d_Tsum=0,q_Ssum=0,q_Tsum=0;
rep(u,n){
if(S[u]) d_Ssum+=d[a][u], q_Ssum+=q[a][u];
else d_Tsum+=d[a][u], q_Tsum+=q[a][u];
}
if(S[a]){
if(d_Tsum*q_Ssum<d_Ssum*q_Tsum) S[a]=false;
}
else{
if(d_Ssum*q_Tsum<d_Tsum*q_Ssum) S[a]=true;
}
}

S[u0]=true, S[v0]=false;
printf("%d",count(S,S+n,true));
rep(u,n) if(S[u]) printf(" %d",u+1);
putchar('\n');
}

return 0;
}

S と T の初期状態をランダムに決めて、あとは、時間いっぱいまで、
「 1 つの元をランダムに選んで、それをもう一方の集合に移動させると解が良くなるなら、移動させる 」
という処理を繰り返した。

Editorials によると、Sparsest Cut と呼ばれている問題らしい。

B.
const ll M=1000000007;

int main(){
const ll a[3][3]={{1,4,2},{1,0,0},{0,1,0}};
ll apow[30][3][3]={};
memcpy(apow[0],a,sizeof a);

rep(t,29){
rep(i,3) rep(j,3) rep(k,3) {
apow[t+1][i][j]+=apow[t][i][k]*apow[t][k][j];
if(apow[t+1][i][j]>=M) apow[t+1][i][j]%=M;
}
}

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

ll v[3]={1,0,0};
rep(l,30){
if(n==0) break;
if(n&1){
ll v2[3]={};
rep(i,3) rep(j,3) {
v2[i]+=apow[l][i][j]*v[j];
if(v2[i]>=M) v2[i]%=M;
}
memcpy(v,v2,sizeof v2);
}
n>>=1;
}

printf("%lld\n",v[0]);
}

return 0;
}

ブロックがどのように並べられるかを紙の上で書いていたら、
a[i+3] = a[i+2] + 4a[i+1] + 2a[i]; a[0]=1, a[1]=1, a[2]=5
という漸化式が得られた。
ここで、a[i] は 2 × i の長方形に敷き詰めるときの並べ方の総数。

あとは、行列べき乗を log オーダーでやってやればいい。
この問題の難しい版が何ヶ月か前の CodeChef でも出題されていたのですぐにわかった。

ちなみに、厳密解は
http://www.wolframalpha.com/input/?i=a[n]%3Da[n-1]%2B4a[n-2]%2B2a[n-3]%2C+a[0]%3D1%2C+a[-1]%3D0%2C+a[-2]%3D0
で見ることができる。

E. (時間外)
const int INF=(1<<31)-1;

int n,lim,dis[100][100];
vi tree[100],sublist[100];
bool sub[100][100]; // sub[u][v] ==true <=> the subtree rooted at u includes v

void maketree(int u,int parent){
rep(v,n){
if(v!=parent && dis[u][v]<INF) {
tree[u].pb(v);
sub[u][v]=true;
maketree(v,u);
}
}
}

int dp1[100][100],dp2[100];

int dfs1(int v,int c);
int dfs2(int u);

int dfs1(int v,int c){
if(~dp1[v][c]) return dp1[v][c];

// case 1
if(tree[v].size()==0){ // v is a leaf
return dp1[v][c]=0;
}

// case 2
if(v==c || !sub[v][c]){
int ans=0;
rep(i,tree[v].size()){
int u=tree[v][i];
if(dis[u][c]<=lim) ans+=max(dfs2(u),dfs1(u,c)+dis[u][v]);
else ans+=dfs2(u);
}
return dp1[v][c]=ans;
}

// case 3
int ans=0;
rep(i,tree[v].size()){
int u=tree[v][i];
if(sub[u][c]) ans+=dis[u][v]+dfs1(u,c);
else{
if(dis[u][c]<=lim) ans+=max(dfs2(u),dfs1(u,c)+dis[u][v]);
else ans+=dfs2(u);
}
}
return dp1[v][c]=ans;
}

int dfs2(int u){
if(~dp2[u]) return dp2[u];

int ans=0;
rep(i,sublist[u].size()){
int c=sublist[u][i];
if(dis[u][c]<=lim) ans=max(ans,dfs1(u,c));
}
return dp2[u]=ans;
}

int main(){
int T; scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&lim);

// initialize
rep(u,n){
tree[u].clear();
sublist[u].clear();
rep(v,n){
dis[u][v]=INF;
sub[u][v]=false;
dp1[u][v]=-1;
}
dp2[u]=-1;
}

rep(i,n-1){
int u,v,w; scanf("%d%d%d",&u,&v,&w);
dis[u][v]=dis[v][u]=w;
}

maketree(0,-1);

// Warshall-Floyd
rep(u,n) dis[u][u]=0;
rep(k,n) rep(i,n) rep(j,n) {
if((ll)dis[i][k]+dis[k][j]<dis[i][j]) dis[i][j]=dis[i][k]+dis[k][j];
}

// transitive closure
rep(u,n) sub[u][u]=true;
rep(k,n) rep(i,n) rep(j,n) {
sub[i][j]|=(sub[i][k] && sub[k][j]);
}
rep(u,n) rep(v,n) if(sub[u][v]) sublist[u].pb(v);

int ans=0;
rep(u,n) if(dis[0][u]<=lim) ans=max(ans,dfs1(0,u));
printf("%d\n",ans);
}

return 0;
}

[ 2011/05/19 追記 ]

Editorials を見ながら解いた。
問題名に反して、枝刈りをする必要は全くない。

どれでもいいので、1 つの頂点を根とした根つき木を考える。上記コードでは 0 を根とした。
この木の上で DP する。

dp1(v, c) := v を根とする部分木について、v を含む連結成分の中心が c であるときの最適解
( 残した枝の重みの和の最大値 )

もちろん、dist(v, c) ≦ d である (v, c) に対してのみ定義される。
c は v を根とする部分木に必ずしも含まれないことに注意。

この DP を素直に書くと、O(n4) 時間かかる。( やってないけど、多分そうなる )
そこで、補助的にもう 1 つ DP を導入する。

dp2(u) := max{ dp1(u, c) | c は u を根とする部分木に含まれる かつ dist(u, c) ≦ d }

すなわち、中心 c が u を根とする部分木に含まれるときに限定した問題の最適解。

dp1 の遷移は、dp2 を用いると次のように書ける。
( 図を描いて考えると分かりやすい。 )

・ v が葉のとき
dp1(v, c) = 0

・ c == v であるか、または c が v を根とする部分木に含まれないとき
dp1(v, c) = ∑u is a child of v f (u, v, c)

・ c が v の子 u' を根とする部分木に含まれるとき
dp1(v, c) = dist(u', v) + dp1(u', c) + ∑u (≠ u') is a child of v f (u, v, c)

ここで、f (u, v, c) を次で定義する。

・ dist(u, c) ≦ d のとき
f (u, v, c) = max(dp2(u), dp1(u, c) + dist(u, v))

・ dist(u, c) > d のとき
f (u, v, c) = dp2(u)

これで、状態数が O(n2)、1 回の更新が O(n) になるので、全体で O(n3) となり、時間内に終了する。

F.
const ll M=1000000007;

int main(){
for(int h;scanf("%d",&h),h;){
static int v[1<<15];
for(int i=1;i<(1<<h);i++) scanf("%d",v+i);

static int path[1<<15];
static double dp[1<<15];
for(int j=(1<<(h-1));j<(1<<h);j++) dp[j]=log(v[j]);
for(int i=h-1;i>0;i--){
for(int j=(1<<i);j<(1<<(i+1));j+=2){
if(dp[j]>dp[j+1]){
dp[j/2]=log(v[j/2])+dp[j];
path[j/2]=j;
}
else{
dp[j/2]=log(v[j/2])+dp[j+1];
path[j/2]=j+1;
}
}
}

ll ans=1;
for(int i=0,u=1;i<h;i++){
ans=(ans*v[u])%M;
if(i<h-1) u=path[u];
}
printf("%lld\n",ans);
}

return 0;
}

DP するだけかと思いきや、意外にも、はまりやすいポイントがある良問。
重みが 109 と大きいので、DP で計算する際に mod をとりながら計算してしまいそうだが、そうすると、求まったものが重み最大の道とはかぎらなくなる。

なので、重みの log をとってスケーリングしたのち、log(重み) の和を最大化する問題に変換した。
別の案としては、多倍長整数を使ってもできると思う。
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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