amori's blog

よろず技術系と趣味関係の雑記です。アニメの比重が高くなってます・・

Paiza ハッカソン「火消し霧島」その3

あとひとつ、あからさまに手抜きのところがある。

for( j = 1 ; j <= limit_manpower ; j++ ){ 
      if( cost_tbl[i-1][j] != C_NIL){
 

 これテーブルで値が入っていないところをスキップしているのだけど、基本的にこのテーブルの最初のほうはほとんどスパースだし、データの内容によっては最後のほうも結構すかすかかもしれない。(例えば各下請の人員が10人・5人単位だったりした場合など)

だから値が入っているところのみを辿るようにすればよく、幸いこのアルゴリズムでは行方向のサーチの順番は任意でよいので、値が未設定の人員ところにコストを代入する場合にのみ、その人員をインデックスとしてリストに加え、次の段階でそのリストに含まれている人員のコストだけを処理すればよい。

 

これでいけるかな、と思ったんだけどもうちょっと足りなかったようなので、後は姑息に、同じ配列参照が繰り返されているところを一度変数において再利用して配列参照の回数を低減しておいた。ループ内の処理がほとんどないので、これも意外に無視できない計算量だ。

(ほんとはもっときれいにデータ構造設計とアルゴリズムみなおすべきだが・・)

でもってこれでケース7まで0.01秒を達成ww。

amoriさんの採点結果[100点] 完璧ぃぃ!|paizaオンラインハッカソンLite

 

まだ、もうちょっと枝刈りと配列の節約する手が残っているけど、まあいいかw。

そういえば、全部0.01秒でもランクSのまんまだったなあ。今回はSSSとかないのかな。実は0.01秒未満でさらにランク分けがあるとか、だったらもう少しやってもいいんだが・・・・・・

 

以下、ver.0.5のソース 

お見苦しいソースですが、これでもまあクリアできる例ということで・・・・

/* paiza Hackathon No.3 */
/* hk ver. 0.5 2014.08.10 */
/* by amori */
/*0.0 べたべた実装 */
/*0.1 初期化だけテーブル必要分のみ*/
/*0.2 いっそ初期化をやめる    */
/*0.3条件超過の組み合わせをスキップ*/
/*0.4 列方向の有効値選択効率化*/
/*0.5 index参照を減らしてみる*/

#include<stdio.h>

// Parameter Declaration

#define AssignIfGreater(x,y) if( x < y ) x = y
#define AssignIfGreaterRef(x,y,z) if( x < y ) z = y

#define MAX_MANPOWER 500000
#define MAX_SUBCON 50
#define MAX_STAFF_OF_SUBCON 10000
#define MAX_BUDGET 5000000

#define C_NIL 0 //static による初期化(ver. 0.2)
#define SC_MAN_POWER 0
#define SC_COST 1


//--------------------------------------------
int sconlist[MAX_SUBCON+1][2];

static int cost_tbl[MAX_SUBCON+1][MAX_MANPOWER+1];
int total_manpower;
int total_cost;
int limit_manpower;

int req_mp, n_subcon;

int nlist[MAX_MANPOWER+1]; //ver 0.4
int tail_of_list; //ver 0.4
//--------------------------------------------

// 新しい組合せのmanpowerをリストで管理 ver 0.4
void add_to_list(int mp)
{
nlist[tail_of_list]=mp;
tail_of_list++;
return;
}
void init_table(void)
{
tail_of_list = 0;
return;
}
/*---------------------------------------*/
main()
{
int i,j,nj;
int *dst, val; //ver.0.5
int smp,scost,m_cost;
int current_tail; //ver.0.4

 

// req_mp 必要な人員
scanf("%d",&req_mp);
// n_subcon 下請け会社数
scanf("%d ",&n_subcon);

// subcon 情報を読み込み
total_manpower = 0;
total_cost = 0;
for( i = 1 ; i <= n_subcon ; i++ ){
scanf("%d %d\n",&smp, &scost);
sconlist[i][SC_MAN_POWER]= smp;
sconlist[i][SC_COST]= scost;
total_manpower += smp;
total_cost += scost;

}
limit_manpower = total_manpower - req_mp;

init_table();
// ここから組合せ探索
// cost_tbl[0][0]=0; //設定不要 ver.0.2
for( i = 1; i <= n_subcon ; i++ ){
smp = sconlist[i][SC_MAN_POWER];
scost = sconlist[i][SC_COST];

// list長の一時保持 ver.0.4
current_tail = tail_of_list;
// 新しいmanpowerはリストで管理する ver.0.4
if( smp <= limit_manpower )
if( cost_tbl[i-1][smp] == C_NIL){
add_to_list(smp);
}
//初期値変更により0列だけ特殊処理ver.0.2
dst = &( cost_tbl[i][smp] );
val = cost_tbl[i-1][0]+scost ;
AssignIfGreater(*dst, val);

//列の処理をmanpowerが設定されているところのみとする。 ver.0.4
for( j = 0 ; j < current_tail ; j++ ){
nj = nlist[j];
dst = &( cost_tbl[i][nj] );
val = cost_tbl[i-1][nj] ;
AssignIfGreater(*dst,val) ;

if( nj + smp <= limit_manpower ) { //ver.0.3 ver0.4
if( cost_tbl[i-1][nj+smp] == C_NIL){
add_to_list(nj+smp);
}
dst = &( cost_tbl[i][nj+smp] );
val = cost_tbl[i-1][nj]+scost ;
AssignIfGreater(*dst,val) ;

}
}

}
m_cost=0;
for( j = 0; j< tail_of_list ; j++){ //ver 0.4
if( nlist[j] <= limit_manpower ){
if( cost_tbl[n_subcon][nlist[j]] > m_cost) m_cost=cost_tbl[n_subcon][nlist[j]];
}
}
printf("%d\n", total_cost - m_cost);
return 0;
}