Entries

スポンサーサイト (この記事を編集する[管理者用])

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

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1186-dca4afa8
この記事にトラックバックする(FC2ブログユーザー)

Marathon Match 59 - BookSelection (参加記録) (この記事を編集する[管理者用])

2010年04月15日02時から,2週間.

Source

Problem Statement
standings

問題概要

本棚が1つ,本がたくさん与えられる.
本棚は高さ,幅が与えられ,本には,高さ,幅,価値が与えられる.
本棚に入れれる本の価値の合計を最大化する問題.入れ方を答える.
本棚に本を入れる際には,まず高さ10の仕切りを入れなくてはいけない.
仕切りの入れる場所,入れる数は自由.
本棚の高さは240以上1200以下で,幅は2400以上6000以下.
本の高さは平均80,幅は平均200でぐらい.
本の数は,本棚の面積/(80*200)の値の1倍~3倍ぐらい.最大ケースで1350で,平均200冊ぐらい?

自分の解法

以下のアルゴリズムを制限時間の間繰り返す.
1. 本をランダムに並べ替える
2. 最初のn冊の本は,小さい順に並び変えて,greedyに本棚に入れると全部入れることができる.というようなnの最大値を2分探索で求める.
3. その時の入れ方から,各段の高さ(仕切りの位置)を決める.ただし,余っている余白は,
   その余白がある程度大きいとき,余白だけでもう1段作る
   その余白がそんなに大きくないとき,全部の段に余白を均等に割りふる.
4. 本は全部入れてない状態に戻す.
5. 一番小さい高さの段に入れる本の価値が最大になるような入れ方をDPを使って求める.
6. まだ入れてない本だけ使って,2番目に小さい高さの段に入れる本の価値が最大になるような入れ方をDPで求める.
7. 同じことを3段目,4段目,…と入れて,それが暫定解より良いなら更新する.

自分の提出したソースコードはこの記事の一番下に貼りつけておきます.

サンプルテストの結果.(提出したコードと違うかもしれません)

Example scores:
0) 3145.0
1) 3470.0
2) 8040.0
3) 1803.0
4) 2239.0
5) 2601.0
6) 2287.0
7) 2851.0
8) 1444.0
9) 4195.0
参加記録

以下時系列順のログです.

1日目 (2010年04月15日) ぐらい

朝4時すぎに起きる.取り敢えず問題を読む.
漠然と考える.
段数が変わるときに,不連続に解が変わってしまう.
局所探索とか焼きなましみたいなのだと,途中で段数が変わらず,局所解に落ち込む.
それぞれの段の高さもなかなか変えにくい気もする.
そんな中,漠然と思いついたアルゴリズムが以下.
 1. 本をランダムに並び替えて,最初からn個の本を全部詰めれる,という最大のnを求める.
 2. 厳密に求めるのは難しいので,2分探索+高さでソートして,greedyに詰め込む方法ぐらいで.
 3. そして,greedyにn個の本を並べる.余った高さは全部の段に均等に割り振る.
 4. 後はちょっとだけ局所探索で改善する.
 1~4を制限時間の間繰り返す.
制限時間2秒しかないんですが…,大丈夫かな?
と思ったら本の数が結構少ないっぽい.万単位であるんだと思ってた.本の数は最大でも1350で,平均的にはその1/6かもっと少ないぐらい.
というか,参加するかどうか決めてない.
参加することになったら困るので,一応思考ログは残しておこう.
ピンポイントにSRM468が参加出来ないので,それの代わりに参加してみたい気もするけど.
参加するとしても目標は実際Marathonのために費やした時間が3時間ぐらいまででそこそこの順位を取ること.できれば上位20%を目指す.
もう20分ぐらい考えてしまったので,今日はこのぐらいでやめる….


とか言いつつ,とても適当にコード書いちゃった.意志が弱い.
朝7時ごろExample submit.参加するの決定.
一応答えは出てる.じゃあFull Submit.
443573点.暫定1位.まぁまだ開始5時間なのですぐ抜かれるだろうけど.
ローカルサーチを本当に近傍しか調べてなくて,ちょっと範囲広げたらスコア上がりそう.
範囲広げてExample Submitしたら,本の数が700個以上のときTLEした.
てか,スコア上がってるか確かめたいのに,結果メールが届いてないから,最初のExampleの結果がわからない….
なんか駄目な気がするけど,範囲を広げるのは300個以下のときにしよう….
この辺はちゃんと実装すれば間に合う気もするんだけどな…,今すごい愚直な方法で実装してるので.
でも面倒なので放置.
ちなみに,ローカルサーチは,
 1. 入れてない本で,入る隙間があるなら入れる
 2. 入れてない本で,1つ抜くことで入れられて,スコアが上がるなら入れ替える
 3. 本の数が300以下で,2つの本を同じ段から抜いて,入れることでスコアが上がるなら入れ替える
でやってみた.
遅延して,Exampleのメールが届いた.
あれ,近傍広げたら,スコア上がってたり減ってたり,これ上がるのか?w
ローカルで実行したら,だいたいスコア上がるからいけると思ったんだけどな….
最初の本をランダムに並べ替えて,ってところを,最初の1回のみ,単位面積当たりのスコアの大きいものから並び変えてみる.
これで明らかにスコア上がるケースが幾つかある.スコア下がるケースは誤差なので気にしない.
次にサブミットできる9時まで休憩.


9時ぐらいになったのでサブミット.
443573点→451496点.(暫定1位→暫定1位)
もう3時間以上普通に時間費やしたので,後は何か思いついたときにちょっとやるぐらいに留めて,2週間順位が落ちてく様子を観察する予定.


予定が変わって,実はSRM468に参加出来そうな気がしてきた.
23時頃帰宅して,抜かれてるとやっぱり歯がゆいので,ローカルサーチの高速化を少しだけやる.
23時50分頃サブミット.
451496点→457101点.(暫定3位→暫定2位)
1位とは1万点差.これは遠い.
各段に入ってる本の中で,単位幅あたりのスコアでソートして,スコアの小さい本をごっそり抜き取って入れ替えるとかいう処理を入れると良くなるのかなぁ,と漠然と思ったけど保留.

2日目 (2010年04月16日) ぐらい

SRM467の直前にちょっとだけやってみる.
ローカルサーチなんかしなくても,DPで十分求まるサイズなんじゃ?
ってことで,DPしてみる.
もちろん,全部の段を全部まとめてDPは無理なので,一段ずつだけど.
457101点→462815点.(暫定7位→暫定3位)
これって,むしろ,どの段をどの高さにするのが良いのかをどうやって巧く探索しますか?って問題じゃんか….


夜.
あまりの高さは均等に割り振ってたのだけど,余りの高さが大きい場合はそれで一段追加してみる.
後,DPするとき,各段終わった後,高さをギリギリまで使ってなければ,余った高さを次の段に繰り越すようにする.
サブミット.
462815点→465542点.(暫定5位→暫定4位)
DPするとき,高さの小さいものから順番に更新することで,単位高さ当たりのスコア最大のものまで使うとかやってみたけど,スコア上がらないので消した.
あと,ちょっとDPの高速化をしてみた.
465542点→464029点.(暫定4位→暫定5位)
あれぇ?
バグ入れてて,DPするとき,最後の要素を使ってなかった….修正.
464029点→466177点.(暫定7位→暫定5位)
小手先の高速化だけだとこんなもんですよねー.

6日目 (2010年04月20日) ぐらい

DPを嘘枝刈りいれて高速化してみる.
466177点→466777点.(暫定17位→暫定13位)
高さAから高さBまでの本のみを使って1段を埋めて得られるコストをDPで全部計算しておいて,それを使って
 dp[残り高さ][下の段で使った本の最大高さ]
をさらにDPで計算するという方法も試してみたけど,流石に2秒は厳しい.
でも,特に大きなサイズのケースで,良くなるんだよなぁ.

14日目 (2010年04月28日, 最終日) ぐらい

ちょっと疲れてて夕方から寝て起きたら終わってた.
暫定結果: 312人中46位.あれ,一応上位20%に入ってる.

あっさりと自分を抜いていった人もいるので,もっとさくっと上位を狙えるように慣れると良いのだろうなぁ….
取り敢えず,後で,上位の解答を見て勉強しろ!します…orz

提出したスパゲッティなソースコード (C++)
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<utility>
#include<set>
#include<queue>
#include<map>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<sstream>
#include<climits>
#include<sys/time.h>
using namespace std;

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define ll long long
#define VI vector<int> 
#define EPS 1e-10

void intSort(int d[],int s){int i=-1,j=s,k,t;if(s<=1)return;k=(d[0]+d[s-1])/2;for(;;){while(d[++i]<k);while(d[--j]>k);if(i>=j)break;t=d[i];d[i]=d[j];d[j]=t;}intSort(d,i);intSort(d+j+1,s-j-1);}
void intIntSort(int d[],int m[],int s){int i=-1,j=s,k,t;if(s<=1)return;k=(d[0]+d[s-1])/2;for(;;){while(d[++i]<k);while(d[--j]>k);if(i>=j)break;t=d[i];d[i]=d[j];d[j]=t;t=m[i];m[i]=m[j];m[j]=t;}intIntSort(d,m,i);intIntSort(d+j+1,m+j+1,s-j-1);}
void doubleIntSort(double d[],int m[],int s){int i,j,r;double k1,k2,t;if(s<=1)return;k1=(d[0]+d[s-1])/2.0;k2=k1+EPS;k1-=EPS;i=-1;j=s;for(;;){while(d[++i]<k1);while(d[--j]>k2);if(i>=j)break;t=d[i];d[i]=d[j];d[j]=t;r=m[i];m[i]=m[j];m[j]=r;}doubleIntSort(d,m,i);doubleIntSort(d+j+1,m+j+1,s-j-1);}

ll get_time(){ timeval t; gettimeofday(&t, 0); return t.tv_sec*1000000LL + t.tv_usec; }

int n; VI res; int opt;
int H, W, h[2221], w[2221], v[2221], permutation[2221];

int m, perH[150], used[150], place[2221], score;
int ind[2221], val[2221]; double vald[2221];
int dp[1400][6111];

int is_feasible(int k){
  int i, restH;
  rep(i,n) ind[i]=i, val[i]=h[i];
  intIntSort(val,ind,k);

  m=0; restH = H;
  rep(i,k){
    if(m==0 || used[m-1]+w[ind[i]] > W) restH-=10, used[m]=0, perH[m++]=0;
    if(m==0 || used[m-1]+w[ind[i]] > W) return 0;
    if(restH < h[ind[i]]-perH[m-1]) return 0;
    restH -= h[ind[i]]-perH[m-1]; perH[m-1]=h[ind[i]]; used[m-1]+=w[ind[i]];
  }

  if(restH<50) rep(i,m) perH[i] += restH/(m-i), restH -= restH/(m-i);
  else         perH[m++]=restH-10, intSort(perH,m);

  return 1;
}

void doDP(void){
  int i,ii,j,k,sz,mx,ww,vv;

  rep(j,W+1) dp[0][j]=0;
  rep(k,m){
    if(k){
      mx=0; rep(i,n) if(place[i]==k-1 && h[i]>mx) mx=h[i];
      perH[k]+=perH[k-1]-mx; perH[k-1]=mx;
    }

    sz=0;
    rep(i,n) if(place[i]==-1 && h[i]<=perH[k]) ind[sz++]=i;

    ii=0;
    rep(i,sz){
      ww=w[ind[i]]; vv=v[ind[i]];
      if(dp[ii][W] >= dp[ii][W-ww]+vv) continue;
      ind[ii]=ind[i];
      rep(j,W+1) dp[ii+1][j]=dp[ii][j];
      REP(j,ww,W+1) if(dp[ii+1][j] < dp[ii][j-ww]+vv) dp[ii+1][j]=dp[ii][j-ww]+vv;
      ii++;
    }

    sz=ii; j=W;
    for(i=sz-1;i>=0;i--) if(dp[i+1][j]!=dp[i][j]) place[ind[i]]=k, score+=v[ind[i]], j-=w[ind[i]];
  }
}

void solve(void){
  int i,a=0,b=n,c;

  while(b>a){
    c=(a+b+1)/2;
    if(is_feasible(c)) a=c; else b=c-1;
  }
  is_feasible(a);

  rep(i,n) place[i]=-1; score=0;
  doDP();
  
  if(opt < score){
    opt = score;
    rep(i,n) res[permutation[i]]=place[i];
  }
}


class BookSelection {
public:
VI arrange(int H_, int W_, VI bookHeights, VI bookWidths, VI bookValues){
  int i;
  ll tm1=-1, tm2=-1, start_time, rest_time;
  res.clear();

  srand(time(NULL));
  start_time = get_time();

  n=bookHeights.size(); H=H_; W=W_;
  rep(i,n) res.push_back(-1); opt=0;

  rep(i,n) permutation[i]=i, vald[i]=-bookValues[i]/(double)(bookHeights[i]*bookWidths[i]);
  doubleIntSort(vald,permutation,n);
  for(;;){
    rep(i,n) h[i]=bookHeights[permutation[i]];
    rep(i,n) w[i]=bookWidths[permutation[i]];
    rep(i,n) v[i]=bookValues[permutation[i]];
    if(tm2==-1) tm1=get_time();
    solve();
    if(tm2==-1) tm2=get_time(), fprintf(stderr,"fst time %lld\n",(tm2-tm1)/1000);
    rest_time = 2000000LL - (get_time()-start_time);
    if(rest_time < (tm2-tm1)+(tm2-tm1)/2+100000LL) break;
    random_shuffle(permutation,permutation+n);
  }

  return res;
}
};


int main(){
  int i, k, H, W, X;
  VI a,b,c,res;
  ll chk; double tim;
  BookSelection hoge;

  scanf("%d%d%d",&H,&W,&X);
  rep(i,X){ scanf("%d",&k); a.push_back(k); }
  rep(i,X){ scanf("%d",&k); b.push_back(k); }
  rep(i,X){ scanf("%d",&k); c.push_back(k); }

  chk = get_time();
  res = hoge.arrange(H,W,a,b,c);
  tim = (get_time()-chk)/1000000.0;
  fprintf(stderr,"time: %.3lf sec\n",tim);

  rep(i,X) printf("%d\n",res[i]);
  fflush(stdout);

  return 0;
}

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1186-dca4afa8
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。