paiza開発日誌

IT/Webエンジニア向け総合求人・学習サービス「paiza」(https://paiza.jp ギノ株式会社)の開発者が開発の事、プログラミングネタ、ITエンジニアの転職などについて書いています。

【結果発表】女子大生プログラマの心を鷲掴みにした最強のコード8選

2014年4月16日より開始したpaizaオンラインハッカソン(略してPOH![ポー!])Vol.2「女子大生とペアプロするだけのの簡単なお仕事です!」ですが、2014年5月14日いっぱいをもって開催期間を終了いたしました。(コードの実行自体は引き続き可能です)。 

今回のオンラインハッカソンも数多くご参加いただきありがとうございました! 今回はpaizaオンラインハッカソンVol.2のレポート、最終結果と、提出された各プログラミング言語毎の最速コード(女子大生プログラマ木野ちゃんの心を鷲掴みにした最強コード)についてお届けします。

■言語別 最速・最遅実行時間結果

POH Vol.2上でも掲載していましたが、まずはテストケース7(大規模データ)の最速・最遅実行時間、提出数です。

言語

最速実行時間

最遅実行時間

通過数 / 受験数

Java

0.04 秒

5.98 秒

327 / 1364 提出

PHP

0.09 秒

9.42 秒

245 / 922 提出

Ruby

0.05 秒

9.92 秒

127 / 754 提出

Python

0.16 秒

8.43 秒

142 / 674 提出

Perl

0.04 秒

9.79 秒

40 / 162 提出

C

0.01 秒

2.78 秒

290 / 1100 提出

C++

0.01 秒

2.95 秒

375 / 1110 提出

C#

0.01 秒

5.99 秒

193 / 762 提出

※最遅実行時間はLimitTime内で最も遅い実行時間だったものを表示しています。

テストケース7についてですが、POH Vol.2の注釈でも書いておりましたが、C、C++、C#、Javaのテストケースは実行速度差の関係で(全言語同じサイズにするとC、C++、C#、Java以外の言語の処理時間が大きかったため)H,Wの上限値が約2.3倍のサイズとなっています

各言語の最速レコードがどのように伸びていったかのグラフが下記です。

■テストケース7の最速レコード推移
f:id:paiza:20140520144944g:plain
軒並み5日目の4/20(日)にはほぼ最速に近いコードが提出されるという結果に成りました(C,C++は二日目にして0.01秒がでています、恐るべし!) ただC#だけは段階的に早くなっており、企画側として望んでいたような推移と成っています。PHPは最終日(5/14)に最速レコードを記録しており執念を感じます(勿論良い意味で!)

■テストケース7の言語別通過率

言語

TC7通過数

受験数

TC7通過率

Java

327

1364

24.0%

PHP

245

922

26.6%

Ruby

127

754

16.8%

Python

142

674

21.1%

Perl

40

162

24.7%

C

290

1100

26.4%

C++

375

1110

33.8%

C#

193

762

25.3%

テストケース7の通過率は全般的には20%台でしたが、Ruby勢は16.8%と苦戦、逆にC++勢はいつもながらですが、プロコン勢などが多いせいか33.8%とダントツの通過率と成りました。ただこのデータは人ユニークではないので、どれだけ高速化のためのトライを行なったか?という見方をした方が良いでしょう。つまりC++はねちっこく0.01秒をねらい何度もチャレンジする人が多く、RubyはS〜SSS評価が出ればあっさり終了している人が多い、と言う訳です。なんとなく言語により使っている人たちの性格の違いが透けてくるようで面白いですねw

■各言語最速コード

複数の方がテストケース3で0.01秒をマークしていた言語に関しては、編集部で選定したものを掲載しております。問題内容はPOH Vol.2をご確認ください。

Java

miswilさんの提出コード
テストケース1:0.04秒
テストケース2:0.04秒
テストケース3:0.04秒
テストケース4:0.04秒
テストケース5:0.04秒
テストケース6:0.04秒
テストケース7:0.04秒
http://paiza.jp/poh/paizen/result/b163d35364359d7e88b42d54323fa9ef

public class Main {
  static final int InBufsiz = 1048576;
  static final int OutBufsiz = 540000;
  static final int Hmax = 300;
  static final int Wmax = 300;
  static byte inbuf[] = new byte[InBufsiz];
  static byte outbuf[] = new byte [OutBufsiz];
  static int inbufnow = 0, outbufnow = 0;

  static int read_int(final char delim){
    int r = inbuf[inbufnow++] - '0';
    while(inbuf[inbufnow] != delim){
      r *= 10;
      r += inbuf[inbufnow++] - '0';
    }
    inbufnow++;
    return r;
  }
  
  static byte itoc(int i)
  { return (byte)(i + '0'); }
  
  static void write_int(int i){
    if(i < 10){
      outbuf[outbufnow++] = itoc(i);
    }else if(i < 100){
      int p = (outbufnow += 2);
      outbuf[--p] = itoc(i % 10);
      outbuf[--p] = itoc(i / 10);
    }else if(i < 1000){
      int p = (outbufnow += 3);
      outbuf[--p] = itoc(i % 10);
      outbuf[--p] = itoc((i /= 10) % 10);
      outbuf[--p] = itoc(i / 10);
    }else if(i < 10000){
      int p = (outbufnow += 4);
      outbuf[--p] = itoc(i % 10);
      outbuf[--p] = itoc((i /= 10) % 10);
      outbuf[--p] = itoc((i /= 10) % 10);
      outbuf[--p] = itoc(i / 10);
    }else{
      int p = (outbufnow += 5);
      outbuf[--p] = itoc(i % 10);
      outbuf[--p] = itoc((i /= 10) % 10);
      outbuf[--p] = itoc((i /= 10) % 10);
      outbuf[--p] = itoc((i /= 10) % 10);
      outbuf[--p] = itoc(i / 10);
    }
    outbuf[outbufnow++] = '\n';
  }

  public static void main (String[] args) {
    int row, height, width, max_height, max_width, min_seq0_right, forward, i, tmpi, tmpi2;
    int p, q, r, row_start, tmpp;
    
    try{
      System.in.read(inbuf,0,InBufsiz);
    }catch(Exception e){}
    final int H = read_int(' ');
    final int W = read_int('\n');
    final int Wp1 = W + 1;
    int table[] = new int[Hmax * Wmax], seq0_right[] = new int[H];
    int start_pos[] = new int[H * H];
    final int Screen_begin = inbufnow;
    inbufnow += H * Wp1;
    final int Screen_end = inbufnow - 1;
    final int N = read_int('\n');
     // make table
    tmpp = Screen_begin;
    i = 0;
    for(row = 0; row < H; ++row, tmpp += Wp1, i += H){
      height = i;
      tmpi = height + H - row;
      while(height < tmpi)
        start_pos[height++] = tmpp;
    }
  
    forward = 1;
    for(p = Screen_begin; p != Screen_begin + W; p += forward){
      min_seq0_right = seq0_right[0];
      q = p;
      for(i = 0; i < H; ++i, q += Wp1){
        if((seq0_right[i] -= forward) < 0){
          for(r = q; inbuf[r] == '0'; ++r);
          seq0_right[i] = r - q;
          // count the number of the widgets whose height is 1
          if(seq0_right[i] != 0) ++table[seq0_right[i] - 1];
        }
        if(min_seq0_right > seq0_right[i]) min_seq0_right = seq0_right[i];
      }
      forward = min_seq0_right > 0 ? min_seq0_right : 1;
  
      max_height = -1;
      row_start = p;
      for(row = 0, tmpi2 = 0; row < H; ++row, --max_height, row_start += Wp1, tmpi2 += H){
        if(inbuf[row_start] != '1'){
          if(max_height < 0){
            max_height = 1;
            r = row_start + Wp1;
            for(; r < Screen_end && inbuf[r] == '0'; r += Wp1)
              ++max_height;
          }
          // after this line, max_height should be greater than 1
          // the widgets whose height is 1 has already counted previously
        
          if(max_height != 1 && start_pos[tmpi2 + max_height - 1] <= row_start){
            // height should be greater than 0
            // count the number of the widgets who has 'height' height and 'width' width
            for(height = tmpi2 + 1, i = tmpi2 + max_height, tmpi = (max_height - 1) / 2;
                tmpi > 1; tmpi = (i - height) / 2){
              if(start_pos[height + tmpi] > row_start) height += tmpi + 1;
              else i -= tmpi - 1;
            }
            if(tmpi == 1)
              for(; start_pos[height] > row_start; ++height);
            height -= tmpi2;
        
            max_width = seq0_right[row];
            for(i = row + 1, tmpi = row + height; i < tmpi; ++i)
              if(max_width > seq0_right[i]) max_width = seq0_right[i];
        
            i = height * Wmax;
            do{
              if(max_width > (tmpi = seq0_right[row + height])) max_width = tmpi;
              width = i;
              tmpp = width + max_width;
              tmpi = max_width;
              ++table[tmpp - 1];
              start_pos[tmpi2 + height] = row_start + max_width;
              i += Wmax;
            }while(++height < max_height);
          }
        }
      }
    }
    // conquer
    for(height = 0; height < H; ++height)
      for(width = 0; width < W; ++width){
        final int tmp = table[height * Wmax + width];
        if(tmp != 0)
          for(i = 0, tmpi = tmp * (width + 1); i < width; ++i, tmpi -= tmp)
            table[height * Wmax + i] += tmpi;
      }
    // I do only output later
    for(i = 0; i < N; ++i){
      final int S = read_int(' ') - 1;
      final int T = read_int('\n') - 1;
  
      write_int(table[S * Wmax + T]);
    }
    System.out.write(outbuf, 0, outbufnow);
  }
}

テストケース7のJava最速レコードはmiswilさんとhakoaiさんの2名、0.04秒でした。


PHP
KoukiMinoさんの提出コード
テストケース1:0.01秒
テストケース2:0.01秒
テストケース3:0.01秒
テストケース4:0.02秒
テストケース5:0.03秒
テストケース6:0.09秒
テストケース7:0.09秒
http://paiza.jp/poh/paizen/result/46c1674eb59307fffd3b7fbe1beec65b

<?php
//$time_start_ex = microtime(true);
define('SL',31);	//分割する桁数(とりあえず32ビットの正の数分=31桁)
stream_set_blocking(STDIN, 0);
$stdin = file_get_contents('php://stdin');
$first = strpos($stdin,"\n");
list($H,$W)=explode(' ',substr($stdin,0,$first));
$stdin = substr($stdin,$first+1);
$lines = explode("\n", $stdin);
$home_lines = array_slice($lines, 0, $H);
$widgets = array_slice($lines, $H + 1, $lines[$H]);
//$time_end = microtime(true);
//$time = ($time_end - $time_start_ex) * 1000;
//echo "!!!INPUT_TIME->$time!!!".PHP_EOL;
//print_r('!!!check!!!');
//print_r($home_lines);
//print_r($widgets);

if ($W > SL){
	//ホームの幅が広い場合はSL幅で計算
	$WW = SL;
}
else {
	$WW = $W;
}

// $bin_max_val = pow(2,$WW) - 1;		//2進数最大値	
// $str_max_val = str_repeat('1',$WW);	//文字列最大値
//$str_min_val = str_repeat('0',$WW);		//文字列最小値

//衝突チェックブロック配列
$check_block = array();
//スキマチェック用リスト
$check_list = array();
for ($SH=1;$SH<=$H;++$SH){
//	$check_block[$SH] = array();
	$check_list[$SH] = array();
}

//$SORT_COND = $H - 1;
foreach ($home_lines as $j => $hl_val){
	//echo "-----j->$j\n";
	//[最初の準備] ホームの情報をSLの幅で分けて2進数にし、配列に格納
	$check_block[$j] = array();
	$pos = 0;
	while ($pos<$W){
		$work_home = substr($hl_val,$pos,SL);
		if (strlen($work_home)<$WW){
			//最後のブロックの右側を1で埋める
			$work_home = str_replace(array("\r\n","\r","\n"), '', $work_home);
			$work_home = str_pad($work_home,$WW,'1');
		}
		$check_block[$j][] = intval($work_home, 2);		//2進数に変換して格納
		$pos += SL;
	}

	$str_check_list = '';
	foreach ($check_block[$j] as $i => $val){
	 	$str_bin = decbin($val);
	 	if (strlen($str_bin)<$WW){
	 		$str_bin = str_pad($str_bin, $WW, '0', STR_PAD_LEFT);
	 	}
	 	$str_check_list .= $str_bin;
	}

	$pos = 0;
	while ($pos<$W){
		$first = strpos($str_check_list,'0',$pos);
		if ($first !== false){
			$second = strpos($str_check_list,'1',$first);
			if ($second !== false){
				$key = $second - $first;
				$pos = $second;
			}
			else {
				$key = $W - $first;
				$pos = $W;
			}
			if (!isset($check_list[1][$key])){
				$check_list[1][$key]=1;
			}
			else {
				++$check_list[1][$key];
			}
		}
		else {
			break;
		}
	}
}
if (count($check_list[1])>1){
	krsort($check_list[1]);
}

for ($SH=2;$SH<=$H;++$SH){
	$k = $H - $SH;
	$cl = &$check_list[$SH];
	for ($j=0;$j<=$k;++$j){
		$str_check_list = '';
		$cb = &$check_block[$j];
		$cbp = &$check_block[$j+1];
		foreach ($cb as $i => $val){
			//OR演算
			$cb[$i] = $cbp[$i] | $val;
			// if ($check_block[$j][$i]===0){
			// 	$str_check_list .= $str_min_val;
			// }
			// else {
			 	$str_bin = decbin($cb[$i]);
			 	if (strlen($str_bin)<$WW){
			 		$str_bin = str_pad($str_bin, $WW, '0', STR_PAD_LEFT);
			 	}
			 	$str_check_list .= $str_bin;
			// }
		}

		$pos = 0;
		while ($pos<$W){
			$first = strpos($str_check_list,'0',$pos);
			if ($first !== false){
				$second = strpos($str_check_list,'1',$first);
				if ($second !== false){
					$key = $second - $first;
					$pos = $second;
				}
				else {
					$key = $W - $first;
					$pos = $W;
				}
				if (!isset($cl[$key])){
					$cl[$key]=1;
				}
				else {
					++$cl[$key];
				}
				//print_r($check_list[$SH]);
			}
			else {
				break;
			}
		}
	}
	if (count($cl)>1){
		krsort($cl);
	}
}

//print_r($check_list);
//$time_end = microtime(true);
//$time = ($time_end - $time_start_ex) * 1000;
//echo "!!!PREPARED_TIME->$time!!!".PHP_EOL;
$echo_str = '';
foreach ($widgets as $w_val){
	//ウィジェットループ
	list($SH,$TW) = explode(' ',$w_val);
	$cnt = 0;
	if ($SH>$H && $TW>$W){
		//ウィジェットのほうが大きい
	}
	else {
		foreach ($check_list[$SH] as $key => $val){
			if ($key<$TW) break;
			$cnt += ($key-$TW+1) * $val;
		}
	}
	//$echo_str .= "SH->$SH TW->$TW ".$cnt.PHP_EOL;
	$echo_str .= $cnt.PHP_EOL;
}
echo $echo_str;
//$time_end = microtime(true);
//$time = ($time_end - $time_start_ex) * 1000;
//echo "!!!TOTAL_TIME->$time!!!".PHP_EOL;
?>

テストケース7のPHP最速レコード該当者1名のみ、0.09秒が最速でした。



Ruby
Javaに引き続きhakoaiさんのコードが最速でした!

hakoaiさんの提出コード
テストケース1:0.01秒
テストケース2:0.01秒
テストケース3:0.01秒
テストケース4:0.02秒
テストケース5:0.02秒
テストケース6:0.05秒
テストケース7:0.05秒
http://paiza.jp/poh/paizen/result/2c5c078c8f8bc5cbd8022ec39cbf92d8

lines = $stdin.read.split(?\n).map!{|item| item.split(" ")}

h = lines[0][0].to_i
w = lines[0][1].to_i

d = Array.new((w+1)*h+h)
p = Array.new(w+1)
ans = Array.new((h+1)*(w+1)+w+1,0)

i=0
while(i<h)
  j = d[i] = 0
  lines[i+1][0].each_byte do|c|
    d[(j+1)*h+i] = c==49?0:d[j*h+i]+1
    j+=1
  end
  i+=1
end

j=1
while(j<=w)
  k=0
  i = h-1
  while(i>=0)
    n=d[j*h+i]
    k+=1
    while(k<=n)do
      p[k] = i;
      k+=1
    end
    k-=1
    while(k>n)do
      ans[(p[k]-i)*(w+1)+k]+=1
      k-=1
    end
    i-=1
  end
  while(k>0)do
    ans[(p[k]+1)*(w+1)+k]+=1
    k-=1
  end
  j+=1
end

j=1
while(j<=w)
  base = add = 0
  i=h
  while(i>0)
    ans[i*(w+1)+j] = add += base += ans[i*(w+1)+j]
    i-=1
  end
  j+=1
end

n=lines[1+h][0].to_i
i=0
out = ""
while(i<n)
  s = lines[2+h+i][0].to_i
  t = lines[2+h+i][1].to_i
  if(s>h||t>w)
    out << "0"
  else
    out << ans[s*(w+1)+t].to_s
  end
  out << "\n"
  i+=1
end

print out

テストケース7のRuby最速レコード該当者1名のみ、0.05秒が最速でした。


Python
PHPに引き続きPythonもKoukiMinoさんのコードが最速でした!

KoukiMinoさんの提出コード
テストケース1:0.04秒
テストケース2:0.04秒
テストケース3:0.05秒
テストケース4:0.06秒
テストケース5:0.08秒
テストケース6:0.14秒
テストケース7:0.16秒
http://paiza.jp/poh/paizen/result/57e5fe1fcdfdf480de58dc48fce82c89

# -*- coding: utf-8 -*-
# python 2.7.3
#import sys,time
import sys
#time_start_ex = time.time()

SL=31		#分割する桁数(とりあえず32ビットの正の数分=31桁)

# def decbin(bin,w):
#     if bin == 0:
# 		return '0' * w
#     bin_str = ''
#     i = w - 1
#     while i >= 0:
# 		bi = (bin >> i) & 1
# 		bin_str += str(bi)
# 		i -= 1
#     return bin_str

(H,W) = map(int, sys.stdin.readline().split(' '))
ALL = map(str, sys.stdin.read().splitlines())
home_lines = ALL[0:H]
N = int(ALL[H])
widgets = ALL[H+1:]
#print '!!!check!!!'
#print home_lines
#print widgets

#time_end = time.time()
#ptime = time_end - time_start_ex
#ptime = ptime * 1000
#ptime = str(ptime)
#print "!!!INPUT_TIME->" + ptime + "!!!"


if W > SL:
	WW = SL
else:
	WW = W

bin_max_val = pow(2,WW) - 1		#2進数最大値 
str_max_val = '1' * WW

#衝突チェックブロック配列
block_cnt = W // SL + 1
check_block = [[0 for j in range(block_cnt)] for i in range(H + 1)];

#スキマチェック用リスト
check_list = [{} for i in range(H + 1)];

#print check_block
#print check_list

SORT_COND = H - 1
for j,hl_val in enumerate(home_lines):

	#[最初の準備] ホームの情報をSLの幅で分けて2進数にし、配列に格納
	bin_home_list = []
	pos = 0
	append = bin_home_list.append
	while pos<W:
		work_home = hl_val[pos:pos+SL]
		if len(work_home)<WW:
			work_home = work_home.ljust(WW,'1')
		append(int(work_home,2))
		pos += SL

	SH = j + 1
	while SH > 0:
		# [手順1] ウィジェットの高さパターンに応じてOR演算をしたリストを作成
		#(例)
		#     00100000
		#     01000011 ⇒ 01100111
		#     01100100
		#str_check_list = '';
		str_list = []
		append = str_list.append
		cblock = check_block[SH - 1]
		cblock_now = check_block[SH]
		for i,val in enumerate(bin_home_list):
			if SH==1:
				chk = val
			else:
				if cblock[i] == bin_max_val:
					chk = bin_max_val
				else:
					chk = cblock[i] | val
			cblock_now[i] = chk;

			#求めた2進数を文字列に変換
			if chk == bin_max_val:
				append(str_max_val)
			else:
				wk_str = bin(chk)
				wk_str = wk_str[2:].rjust(WW,'0')
				append(wk_str)

		# [手順2] 求めた2進数からゼロ文字列の長さリストを作成
		#(例)
		#     00100010101011 ⇒ 2,3,1,1,1
		str_check_list = "".join(str_list)
		clist = check_list[SH]
		pos = 0
		while pos < W:
			first = str_check_list.find('0',pos)
			if first >= 0:
				second = str_check_list.find('1',first)
				if second >= 0:
					key = second - first
					pos = second
				else:
					key = W - first
					pos = W
				if clist.has_key(key):
					clist[key] += 1
				else:
					clist[key] = 1
			else:
				break
		if j==SORT_COND:
			if len(clist) > 0:
			 	check_list[SH] = sorted(clist.items(),key=lambda x: x[0], reverse=True)
		SH -= 1

#time_end = time.time()
#ptime = time_end - time_start_ex
#ptime = ptime * 1000
#ptime = str(ptime)
#print "!!!PREPARED_TIME->" + ptime + "!!!"

#print check_list
#print_str = '';
print_list = ['0' for n in range(N)]
index=0
for index,w_val in enumerate(widgets):
	(SH,TW) = map(int, w_val.split(' '))
	cnt = 0
	if SH <= H:
		for key,val in check_list[SH]:
			if key < TW:
				break
			cnt += (key-TW+1) * val
		if cnt > 0:
			print_list[index] = str(cnt)
print "\n".join(print_list)
#time_end = time.time()
#ptime = time_end - time_start_ex
#ptime = ptime * 1000
#ptime = str(ptime)
#print "!!!TOTAL_TIME->" + ptime + "!!!"

テストケース7のPython最速レコード該当者1名のみ、0.14秒が最速でした。


Perl
JavaRubyにつづきPerlもhakoaiさん!!

hakoaiさんの提出コード
テストケース1:0.01秒
テストケース2:0.01秒
テストケース3:0.01秒
テストケース4:0.01秒
テストケース5:0.01秒
テストケース6:0.04秒
テストケース7:0.04秒
http://paiza.jp/poh/paizen/result/061225f304ec0aa484bdd3a646052742

<> =~  /^(\d+) (\d+)$/;
 
my $h = $1;
my $w = $2;
 
my $i;
my $j;
my $n;
my $k = 0;
my $base;
my $add;
my $s;
my $t;
my $out = "";
my $buf;
my @d = ();
my @p = ();
my @ans = ();
$d[$h][$w+1] = 0;
$p[$w+1] = 0;
$ans[$h+1][$w+1] = 0;
 
for $i(0..($h-1)){
	$buf = <>;
	chomp($buf);
	$j = $d[$i][0] = 0;
	for $ch (split //, $buf){
		$d[$i][$j+1] = (($ch == "1")?0:($d[$i][$j]+1));
		++$j;
	}
}
 
for $j (1..$w){
	for $i (0..($h-1)){
		$n = $d[$i][$j];
		while(++$k<=$n){
			$p[$k] = $i;	
		}
		while(--$k>$n){
			++$ans[$i-$p[$k]][$k];
		}
	}
	++$k;
	while(--$k){
		++$ans[$h-$p[$k]][$k];	
	}
}
 
$j = $w+1;
while(--$j){
	$base = $add = 0;
	$i = $h+1;
	while(--$i){
		$ans[$i][$j] = $add += $base += $ans[$i][$j]	
	}
}
 
<> =~  /^(\d+)$/;
$n = $1;
 
for(0..($n-1)){
	<> =~  /^(\d+) (\d+)$/;
	$s = $1;
	$t = $2;
	if($s>$h||$t>$w){
		$out = $out . "0\n";
	}
	else{
		$out = $out . "$ans[$s][$t]\n"
	}
}
print $out

テストケース7のPerl最速レコード該当者1名のみ、0.04秒が最速でした。


◆C
Leonardoneさんの提出コード
テストケース1:0.01秒
テストケース2:0.01秒
テストケース3:0.01秒
テストケース4:0.01秒
テストケース5:0.01秒
テストケース6:0.01秒
テストケース7:0.01秒
http://paiza.jp/poh/paizen/result/1e7a5bdf25a4c2a25172afaaa2cba7ea

/* paiza POH! vol.2
 * 
 * 
 * author: Leonardone @ NEETSDKASU
 */
#include <stdio.h>

#define OUTPUTSIZE (600000)
char output[OUTPUTSIZE];
char *optr = output;
 
inline void putInt(int v) {
	if (v < 10) {
		*optr = '0' + (char)v;
		++optr;
	} else {
		putInt(v / 10);
		*optr = '0' + (char)(v % 10);
		++optr;
	}
}
 
inline void putNewline(void) {
	*optr = '\n';
	++optr;
}
 
#define BUFSIZE (900000)
char buf[BUFSIZE];
char *ptr = buf;
 
inline int getInt(void) {
	int v = 0;
	while (*ptr < '0' || *ptr > '9') ++ptr;
	while (*ptr >= '0' && *ptr <= '9') {
		v = 10 * v + (int)(*ptr - '0');
		++ptr;
	}
	return v;
}
 
inline char getChar(void) {
	while (*ptr < '0' || *ptr > '9') ++ptr;
	return *ptr++;
}

int space2top[301];
int table[301][301];

typedef int * PINT;

int main(void) {
	int H, W, N, s, t, i, x, y;
	char str[310];
	PINT p, q;
	
	fread(buf, sizeof(char), BUFSIZE, stdin);
	
	H = getInt();
	W = getInt();
	
	for (y = 0; y < H; ++y) {
		q = space2top + 1;
		for (x = 0; x < W; ++x, ++q) {
			if (getChar() == '0') {
				p = q;
				s = ++(*p);
				t = 1;
				while (*p) {
					if (*p < s) {
						s = *p;
					}
					++table[t][s];
					++t;
					--p;
				}
			} else {
				*q = 0;
			}
		}
	}
	
	for (x = 1; x <= W; ++x) {
		p = table[x] + H;
		for (y = 1; y < H; ++y) {
			--p;
			*p += *(p + 1);
		}
	}
	
	N = getInt();
	
	for (i = 0; i < N; ++i) {
		s = getInt();
		t = getInt();
		putInt(table[t][s]);
		putNewline();
	}
	
	fwrite(output, sizeof(char), (int)optr - (int)output, stdout);
		
	return 0;
}

テストケース7のC言語最速レコード該当者は8名(chanさん、macchaさん、Leonardoneさん、miswilさん、hkさん、amoriさん、hakoaiさん、laycrsさん)、0.01秒が最速でした。


C++
ushさんの提出コード
テストケース1:0.01秒
テストケース2:0.01秒
テストケース3:0.01秒
テストケース4:0.01秒
テストケース5:0.01秒
テストケース6:0.01秒
テストケース7:0.01秒
http://paiza.jp/poh/paizen/result/3bcc155a71043344ee690edbb141d8d9

// O(H*W*(H+W)+N)time
// いわゆる「いもす法」で前処理しておき、各クエリにはO(1)で答えます
// 逐次的に前処理するようにしている
// 入力を一気に取得するようにしている
// 更に階差を取ることで途中をスキップできるようにした


#include <unistd.h>
#include <cstdio>
using namespace std;

const int MAX_ROW = 300;
const int MAX_COL = 300;

char buf[11*MAX_ROW*MAX_COL]; // 入力を一気に取得するためのバッファ
char* bufp = buf; // バッファ上の現在の位置
inline int nextInt() {
  while(*bufp < '0')
    ++bufp;
  register int res = *bufp++ -'0';
  while(*bufp >= '0')
    res = res * 10 + (*bufp++ -'0');
  return res;
}



int ans[MAX_ROW+10][MAX_COL+10]; // ans[h][w] : h*wの矩形を置ける位置の個数
int up[MAX_COL+10]; // up[j]: (1-originの)j列目で現在上にいくつ0が連続しているか

int main(void) {
  read(0, buf, sizeof buf);
  int nRow = nextInt();
  int nCol = nextInt();
  for(int i = 1; i <= nRow; ++i){
    while(*bufp < '0')
      ++bufp;
    for(int j = 1; j <= nCol; ++j){
      if(*bufp++ != '0'){
	up[j] = 0;
	continue;
      }
      
      up[j]++;
      int jj = j;
      for(int h = up[j]; h > 0; ){
	while(up[jj] >= h)
	  --jj;
	ans[h][j-jj]++;
	h = up[jj];
	ans[h][j-jj]--;
      }
    }
  }
  // 累積和を取る  
  for(int h = nRow; h >= 1; --h){
    for(int w = nCol; w >= 1; --w){
      ans[h][w] += ans[h][w+1] + ans[h+1][w] - ans[h+1][w+1];
    }
  }
  
  int nQuery = nextInt();
  for(int iQuery = 0; iQuery < nQuery; ++iQuery){
    int h = nextInt();
    int w = nextInt();
    printf("%d\n", ans[h][w]);
  }
  return 0;
}

テストケース7のC++最速レコード該当者は10名(ushさん、Leonardoneさん、testさん、miswilさん、testさん、tymtksさん、Komakiさん、hakoaiさん、simezi_tanさん、laycrsさん ※testさんが2名いますが別人です)、0.01秒が最速でした。


C#
さんの提出コード
テストケース1:0.01秒
テストケース2:0.01秒
テストケース3:0.01秒
テストケース4:0.01秒
テストケース5:0.01秒
テストケース6:0.01秒
テストケース7:0.01秒
http://paiza.jp/poh/paizen/result/6b31010b1b20a4e0d513cd68f4692af8

using System;
using System.Runtime.InteropServices;

class POH_2
{
    static byte[] buf;
    static int rP = 0;
    static int wP = 0;
    static int tmp = 0;

    static int read_int()
    {
        tmp = 0;
        while (buf[rP] >= '0' && buf[rP] <= '9')
        {
            tmp = tmp * 10 + buf[rP++] - '0';
        }
        rP++;

        return tmp;
    }

    [DllImport("libc")]
    static extern int read(int fd, IntPtr buf, int count);
    [DllImport("libc")]
    static extern int write(int fd, IntPtr buf, int count);


    public static void Main(String[] args)
    {
        int i, j, k = 0, h, w, n, add, bas, s, t;
        int[] p, map, ans;
        const int SIZE = 300 * 300 * 8 + 300 * 301;

        buf = new byte[SIZE];
        var handle = GCHandle.Alloc(buf, GCHandleType.Pinned);
        var pbuf = Marshal.UnsafeAddrOfPinnedArrayElement(buf,0);
        read(0, pbuf, SIZE);
        h = read_int();
        w = read_int();
        p = new int[w + 1];
        map = new int[(w + 1) * h];
        ans = new int[(h + 1) * (w + 1)];
        i = h;
        while (i-- > 0)
        {
            j = w;
            while (j-- > 0)
            {
                map[i * (w + 1) + j] = (buf[rP++] != '0') ? 0 : map[i * (w + 1) + j + 1] + 1;
            }
            rP++;
        }

        j = w;
        while (j-- > 0)
        {
            i = h;
            while (i-- > 0)
            {
                n = map[i * (w + 1) + j];
                while (++k <= n)
                {
                    p[k] = i;
                }
                while (--k > n)
                {
                    ++ans[(p[k] - i) * (w + 1) + k];
                }
            }
            ++k;
            while (--k > 0)
            {
                ++ans[(p[k] + 1) * (w + 1) + k];
            }
        }

        j = w + 1;
        while (--j > 0)
        {
            bas = add = 0;
            i = h + 1;
            while (--i > 0)
            {
                ans[i * (w + 1) + j] = add += bas += ans[i * (w + 1) + j];
            }
        }
        n = read_int();
        while (n-- > 0)
        {
            s = 0;
            t = 0;
            while (buf[rP] >= '0' && buf[rP] <= '9')
            {
                s = s * 10 + buf[rP++] - '0';
            }
            rP++;
            while (buf[rP] >= '0' && buf[rP] <= '9')
            {
                t = t * 10 + buf[rP++] - '0';
            }
            rP++;
            if (s > h || t > w) bas = 0;
            else bas = ans[s * (w + 1) + t];
            if (10000 <= bas) goto l10000;
            if (1000 <= bas) goto l1000;
            if (100 <= bas) goto l100;
            if (10 <= bas) goto l10;
            goto l1;
        l10000:
            buf[wP++] = (byte)('0' + Math.DivRem(bas, 10000, out bas));
        l1000:
            buf[wP++] = (byte)('0' + Math.DivRem(bas, 1000, out bas));
        l100:
            buf[wP++] = (byte)('0' + Math.DivRem(bas, 100, out bas));
        l10:
            buf[wP++] = (byte)('0' + Math.DivRem(bas, 10, out bas));
        l1:
            buf[wP++] = (byte)('0' + bas);
            buf[wP++] = (byte)'\n';
        }
        write(1, pbuf, wP);
        handle.Free();

    }
}

テストケース7のC#最速レコード該当者1名のみ、0.01秒が最速でした。

最速コードは複数言語でhakoaiさんが6言語(Java,Ruby,Perl,C,C++,C#)、miswilさんが3言語(Java,C,C++)、KoukiMinoさんが2言語(Python,PHP)ランクインという結果になりました。(C、C++の2言語で最速を取っている方は多いので、ここでは割愛させていただきます。)

O(H^3W^3)、O(H^2W^2)、O(min(H, W) HW) といった計算量別の各言語毎のコードはpaiza会員ページ内に掲載しております。各アルゴリズムのサンプルコードを見てみたい!という方は是非ご登録ください!!
https://paiza.jp/users/new

今回の問題の解法解説については5月28日(水)に更新予定ですのでご期待ください!

■まとめ

今回の企画では前回企画実施時の反省を踏まえて、サーバやテストケース数など増強をおこないましたが、一番の改善点としてはIOのチューニングによる実行速度の影響を少なくして、アルゴリズムによる高速化を中心の問題にした事かもしれません。逆にちょっととっつきにくい問題になってしまったかもしれない、というのが今回の反省点ですが、多くの方に楽しんでいただけたようなので、また次回さらにパワーアップして開催できればと考えております。オンラインハッカソンに関するアイデア等有れば是非paiza事務局まで是非ご意見をお寄せください!


各解法のアルゴリズム解説はこちら⇒もし女子大生プログラマに『アルゴリズム』を図解で教えるとしたら

■プレゼントについて

シャーク、ロックスター、レッドブルについては本日当選者にメールをさせて頂ますのでご確認ください。連絡が取れない場合は再抽選となりますのでご注意ください。当選者の発表は賞品の発送をもって代えさせて頂きます。


paiza会員登録すると、今回のPOH Vol.2の各言語の各アルゴリズムの実装パターンが見れるほか、スキルチェックが出来る様々な問題が出題されています。
paizaはプログミングスキルを評価し、転職をサポートするIT/Webエンジニア特化の転職サイトです。
https://paiza.jp/users/new


プログラミング入門講座|paizaラーニング

PHP入門編Ruby入門編Python入門編Java入門編JavaScript入門編C言語入門編C#入門編アルゴリズム入門編