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

続き

さてテーブル全体の初期化が原因でくまなく0.01秒損していたのだから、ケース７ではおそらくほぼ最大設定の条件になっているはずなので、この初期化で0.01秒損していることになる。

もういっそのことテーブルの初期化を止めてstaticで設定される０を初期値としてしまおう。

ただ原理的には0行と0列についてのみ「０」が「コスト＝０」という意味をもってしまっているので、この行と列についてのみ処理を別にしてしまえばいい。

ver.0.2での変更は、初期化処理の省略と

//初期値変更により0列だけ特殊処理ver.0.2
　　AssignIfGreater(cost_tbl[i][smp],cost_tbl[i-1][0]+scost);
　　for( j = 1 ; j <= total_manpower ; j++ ){ // j=0 -> j=1 , ver.0.2

この一行追加とjの開始を１からにしただけ。

その結果が、

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

うん、読み通りケース７が0.03秒になったわｗ

さらに

if( j+smp <= limit_manpower ) //ver.0.3
　　　AssignIfGreater(cost_tbl[i][j+smp],cost_tbl[i-1][j]+scost);

 のを追加して、条件を超えてしまった人員・コストの組み合わせをスキップして、

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

ケース７が0.02秒

採点は100点だけど、まだSクラスということはケース６，７をそれぞれ0.01秒にすればSS,SSSということかな。

ここまでのソースは以下。

まだまだ無駄があるｗ

/* paiza Hackathon No.3 */
/* hk ver. 0.2 2014.08.10 */
/* by amori */
/*0.0 べたべた実装 */
/*0.1 初期化だけテーブル必要分のみ*/
/*0.2 いっそ初期化をやめる　　　　*/
/*0.3 条件超過の組み合わせをスキップ*/

#include<stdio.h>

// Parameter Declaration

#define AssignIfGreater(x,y) if( x < y ) x = 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;
//--------------------------------------------

void init_table(void)
{
/* テーブル初期化廃止ver.0.2
int i,j;

for( i = 0 ; i <= n_subcon ; i++ ){ //MAX_SUBCONから必要分のみ初期化
for( j = 0 ; j <= total_manpower ; j++){ //MAX_MANPOWERから必要分のみ初期化
cost_tbl[i][j]= C_NIL;
}
}
*/
return;
}
/*---------------------------------------*/
main()
{
int i,j;

int smp,scost,m_cost;

// 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];

//初期値変更により0列だけ特殊処理ver.0.2
AssignIfGreater(cost_tbl[i][smp],cost_tbl[i-1][0]+scost);
//limit_manpowerを超える条件は枝刈り　ver.0.3
for( j = 1 ; j <= limit_manpower ; j++ ){ // j=0 -> j=1 ver.0.2
// total_manpower -> limit_manpower ver0.3
if( cost_tbl[i-1][j] != C_NIL){
AssignIfGreater(cost_tbl[i][j],cost_tbl[i-1][j]) ;
if( j+smp <= limit_manpower ) //ver.0.3
AssignIfGreater(cost_tbl[i][j+smp],cost_tbl[i-1][j]+scost);
}
}

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