とすなで！（女子大生とペアプロ その３）
ラノベタイトル風に省略してみました
女子大生とペアプロするだけの簡単なお仕事です！｜paizaオンラインハッカソンVol.2の 女子大生とペアプロ（ハッカソンVol.2)その後
の続き。
基本的な考え方を素直にコードに落としたら、１００点になってしまったので、あとは最後のテストケースの時間短縮を少し工夫してみる。
パッと見て工夫の余地があるのが最後のウィジェット数の検索のところ
int search_widget_table(int s, int t )
{
int count,w_i;
count = 0;
for( w_i = t - 1; w_i < width ; w_i++ ){
count += widget_count[s-1][w_i];
}
return count;
}
特定の高さのウィジェットについて一定幅以上の個数を数え上げているのであるが、幅が大きくなるにつれてその個数は単調減少になるので、ゼロになったらそれ以上は数える必要はない。（実はデバッグするまで、この当たり前な事実に気がついてなかった・・）で、数え上げの打ち切り条件をいれてみる。
int search_widget_table(int s, int t )
{
int count,w_i;
count = 0;
for( w_i = t - 1; w_i < width ; w_i++ ){
if( widget_count[s-1][w_i] == 0 ){
return count;
}
count += widget_count[s-1][w_i];
}
return count;
}
if文ひとついれただけですが、さてその効果は、
お、0.01秒短縮された。そこそこ改善されてると言えるかな。さらに評価がSSからSSSに昇格ｗ
デレになっとるｗｗ
この数え上げをさらに工夫して一回ですべての数え上げを済ませてしまえばもっと効果があると思ってやってみたのだが、計測結果に反映するほどのものではなかった。
てことは、最後の手段の標準入力の効率化かな・・・・
追記：
その前に数え上げを事前にするのではなく、呼び出された時だけ実行して数え上げ数を必要最小限にするという修正をちょろっと加えたのだが、逆に少し遅くなった。
ということは、その都度呼び出すというほうのオーバーヘッドの影響のほうが大きかったということで、最後の2ケースはウィジェットの数が非常に大きいということなんだろうな。
0.02秒づつ遅くなったので期せずしてS判定をゲットできたわｗ
http://paiza.jp/poh/paizen/result/24097e83a4aba17b187c0b68af839bbf
以下、今回の修正版の一番速かった、数え上げ事前一括処理版のコード全体
＃min()関数がコンパイラ取らなかったのでマクロにしてあるのでけど不等号がHTMLに引っ掛かってしまっているみたい。
/* 領域辞書検索パターン*/
#include<stdio.h>
#include<stdlib.h>
// TABLE DATA, 探索結果値
#define MAX_SIZE 300
#define MAX_STR_SIZE 400
#define OCCUPIED 0
#define NOT_ASSIGNED -2 //初期化値
#define min_mcr(x,y) *1?(x):(y)
int height,width;
int s,t;
int grid[MAX_SIZE][MAX_SIZE];
int run_width_table[MAX_SIZE][MAX_SIZE];
int run_height_table[MAX_SIZE][MAX_SIZE];
int widget_count[MAX_SIZE][MAX_SIZE];
int widget_count_sum[MAX_SIZE][MAX_SIZE];
int ocp;
void init_tables(void)
{
int i,j;
for( i = 0 ; i < height ; i++)
for( j = 0 ; j < width ; j++){
run_width_table[i][j] = NOT_ASSIGNED;
run_height_table[i][j] = NOT_ASSIGNED;
widget_count[i][j] = 0;
}
}
int sum_and_entry( int wt_h, int wt_w )
{
if ( widget_count[wt_h][wt_w] == 0 ){
widget_count_sum[wt_h][wt_w] = 0;
return 0;
}else {
widget_count_sum[wt_h][wt_w] = widget_count[wt_h][wt_w] + sum_and_entry( wt_h ,wt_w+1);
return widget_count_sum[wt_h][wt_w];
}
}
int search_sum_table(int s, int t )
{
return widget_count_sum[s-1][t-1];
}
int search_widget_table(int s, int t )
{
int count,w_i;
count = 0;
for( w_i = t - 1; w_i < width ; w_i++ ){
if( widget_count[s-1][w_i] == 0 ){
return count;
}
count += widget_count[s-1][w_i];
}
return count;
}
void count_valid_widget( int g_h, int g_w )
{
int h, run_w, run_h ;
run_h = run_height_table[g_h][g_w];
run_w = run_width_table [g_h][g_w];
for ( h = 0 ; h < run_h ; h ++ ){
run_w = min_mcr( run_w, run_width_table [g_h + h][g_w]);
widget_count[h][run_w-1]++ ;
}
}
int search_run_height( int g_h, int g_w )
{
int length;
if ( g_h >= height ) return OCCUPIED ;
if ( g_w >= width ) return OCCUPIED ;
length = run_height_table[g_h][g_w];
if( length != NOT_ASSIGNED ){
return length;
}
if( grid[g_h][g_w] == 0 ){
return ( run_height_table[g_h][g_w] = search_run_height( g_h+1,g_w )+1);
}else {
return run_height_table[g_h][g_w] = OCCUPIED ;
}
}
int search_run_width(int g_h, int g_w )
{
int length;
if ( g_h >= height ) return OCCUPIED ;
if ( g_w >= width ) return OCCUPIED ;
length = run_width_table[g_h][g_w];
if( length != NOT_ASSIGNED ){
return length;
}
if( grid[g_h][g_w] == 0 ){
return ( run_width_table[g_h][g_w] = search_run_width( g_h, g_w+1 )+1);
}else {
return run_width_table[g_h][g_w] = OCCUPIED ;
}
}
void generate_widget_table(void)
{
int grid_h,grid_w,wdt_h;
for ( grid_h = 0 ; grid_h < height ; grid_h ++ )
for ( grid_w = 0 ; grid_w < width ; grid_w ++ ){
count_valid_widget( grid_h, grid_w );
}
// ウィジェットの数え上げをまとめて実施
for ( wdt_h = 0 ; wdt_h < height ; wdt_h ++ ){
if( sum_and_entry( wdt_h, 0 ) == 0 ) break;;
}
}
void generate_run_table(void)
{
int grid_h,grid_w;
for ( grid_h = height-1 ; grid_h >= 0 ; grid_h -- )
for ( grid_w = width -1 ; grid_w >= 0 ; grid_w -- ){
search_run_width( grid_h, grid_w );
search_run_height( grid_h, grid_w );
}
}
main()
{
int i,j;
char linestr[MAX_STR_SIZE];
int w_n;
ocp = 0;
// screen 高さ・幅を読み込みm
scanf("%d %d",&height,&width);
// screen 情報を読み込み
for( i = 0 ; i < height ; i++ ){
scanf("%s\n",linestr);
for( j = 0 ; j < width ; j++){ //screen情報を幅方向の通し番号で記録
grid[ i ][ j ] = linestr[j]-'0';
ocp += linestr[j]-'0';
}
}
init_tables();
generate_run_table(); // 領域サーチ＆検索テーブル作成
generate_widget_table();
scanf("%d\n",&w_n ); // WIDGET数読み込み
// WIDGETサイズ読み込み ＋ 配置数カウント
for( i = 0 ; i < w_n ; i++ ){ //widget個数分ループ
scanf("%d %d\n",&s,&t); //高さ・幅
if ( (s ==1)&&(t==1) ) printf( "%d\n",height*width - ocp );//ちょっと姑息にカウント・・
else printf("%d\n", search_sum_table( s , t ) );
}
return 0;
}
*1:x) < (y
