女子大生とペアプロ(ハッカソンVol.2)その後
女子大生とペアプロするだけの簡単なお仕事です!|paizaオンラインハッカソンVol.2にトライしてみた今度は女子大生とペアプロとなの続き。
前回はシンプルこの上ない「ウィジェットを置けるかどうか順番に試す」というコードでとりあえずテストケース3までは通ったので、次は順番に高速化してワンステップづつケースをクリアしていくつもりだったんだけど、テストケー4どうやらかなりのデータ量のようで多少の高速化ではこのケースを通過させることはできないようだ。
そこで少し真面目に計算量とアルゴリズムを見直してみた。
計算量に影響するは、
であろうか。
1のデータ入力数については前回は標準入力の遅さが無視できなかったので考慮する必要があるがとりあえず後回し。
3のウィジェットが置けるかどうかの判定についての効率化を少し試してみたが、これでは足りないみたいなので、4.のウィジェット数の影響を低減してみる。
考えてみたらウィジェット数って、最大値が高さ×幅の全組み合わせで300×300にもなりうるので、これが大きい方影響があるだろう。
ということで、ウィジェット配置可能性を探索したらそれを記憶しておいて後の処理ではその結果を流用することでウィジェットサイズごとの判定処理を探索する、という方針としてみた。
一度調べた結果を後で流用するためには、複数サイズのウィジェットの配置可能性を包含するような形で調べてそれを記録しなければならない。
ということは基本的には、大きめの矩形領域を順番に調べて、その結果を後で流用すればよい。つまりひとマスごとにそこを角としておけるすべてのサイズのウィジェットを数えておけば、ある特定のウィジェットがおけるかどうかは、そのサイズ以上のウィジェット配置可能領域を検索で調べればよい。
以上をふまえた書き直したプログラムの大まかな流れは、
- 設定データ読み込み
- 各マスごとに縦・横の連続領域領域をサーチ
- 連続領域のサーチ結果から各マスごとに配置可能なウィジェットのサイズを導出
- 導出されたサイズをサイズ別のカウンタに登録
- 配置するウィジェットのサイズから、サイズ別カウンタを検索して、高さが一致して、幅が対象ウィジェット以上についてカウンタ数を合計
というなった。
結果的にこの改造ですべてのテストケースを通過し、とりあえず100点の評価をもらってしまった。テストケース6と7に改善の余地があるけれども、たぶんこの数値はそろそれ標準入力の遅さに起因するものかもしれないのでとりあえず保留。
順番にクリアしようと思っていたのに、これではC判定とSS判定の間のご褒美がわからんじゃないかw
ちなみに以下が今回のコード。
まだ少し効率をあがられそうなとこはあるが、あんまり本質的ではないのでスピードはこれで頭打ちかも。
#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 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 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;
}
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;
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 );
}
}
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_widget_table( s , t ) );
}
return 0;
}
*1:x)<(y