Paiza ハッカソン「火消し霧島」
もう3回目ですね。Paizaのハッカソン。
天才火消しエンジニア霧島「もしPMおじさんが丸投げを覚えたら」｜paizaオンラインハッカソンLite
第三回オンラインハッカソン「天才火消しエンジニア霧島」開催！ - paiza開発日誌
正月・GWときて今度は夏休み。なるほどまとまった休みに問題に挑戦できる気配りなのですね。（もしかして中の人が休み使って対応してたりして・・）
さて今回は、プロジェクト人員組合せの最適化という問題で、
・・・・これ単純にナップザック問題だよねー
いつも問題になる入力処理のオーバーヘッドについて解決するために、
入力データ数を少なくして、かつ、一定のデータ量になると計算量が大きくなる類の問題を設定したとは思うだけど、これナップザック問題を調べればシンプルに解けてしまうでないかなあ。
動的計画法（DP:Dynamic Programing)というと大層ですが、要するにすべての組み合わせを重複する計算済のパターンをうまくつかって効率的に枝刈りをするもので、このナップザック問題に限って言えば、データ表現を適切に設定すれば、ソーティングとかの下準備も不要でシンプルこの上ない手順で解が求めらます。
それでは、DPのコンセプトをそのまんまにベタな実装をしてみますと、
amoriさんの採点結果[100点] 完璧ぃぃ！｜paizaオンラインハッカソンLite
テストケース１～６まで0.02秒、テストケースで0.04秒
・・・・これDP使ったら実質テストケース７だけの問題ですねえ。
実は実装べたべたで、作業用のテーブルをあえて問題条件の最大可能性に固定してあって、50万×50のテーブルを全部初期化してるんで、この0.02秒固定というのはこの初期化ルーチンですわな。
初期化を必要最小限のテーブルに限定したら、
amoriさんの採点結果[100点] 完璧ぃぃ！｜paizaオンラインハッカソンLite
と、テステケース１－５までが0.01秒になりました。
以下にソースはっておきますが、初期化や処理必要な部分の抽出をこれだけ手抜きしてるのにほぼできてしまっているというのは、テステケース甘すぎではないですかねえ。
（続く）
/* paiza Hackathon No.3 */
/* hk ver. 0.1 2014.08.9*/
/* by Amori */
/**/#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 -1
#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)
{
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;
for( i = 1; i <= n_subcon ; i++ ){
smp = sconlist[i][SC_MAN_POWER];
scost = sconlist[i][SC_COST];
for( j = 0 ; j <= total_manpower ; j++ ){
if( cost_tbl[i-1][j] != C_NIL){
AssignIfGreater(cost_tbl[i][j],cost_tbl[i-1][j]) ;
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;
}
