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

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

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

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

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

言語	最速実行時間	最遅実行時間	通過数 / 受験数
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の最速レコード推移

軒並み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);
  }
}

テストケース７の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;
?>

テストケース７の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

テストケース７の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 + "!!!"

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

◆Perl
Java、Rubyにつづき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

テストケース７の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;
}

テストケース７の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;
}

テストケース７の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();

    }
}

テストケース７の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は、技術を追い続けることが仕事につながり、スキルのある人がきちんと評価される場を作ることで、日本のITエンジニアの地位向上を目指したいと考えています。

「paiza転職」は、自分のプログラミング力が他社で通用するか（こっそり）腕試しができる、IT／Webエンジニアのための転職サービスです。プログラミングスキルチェック（コーディングのテスト）を受けて、スコアが一定基準を超えれば、書類選考なしで複数の会社へ応募ができます。

まずはスキルチェックだけ、という使い方もできます。すぐには転職を考えていない方でも、自分のプログラミングスキルを客観的に知ることができますので、興味がある方はぜひ一度ご覧ください。

また、paiza転職をご利用いただいている企業の人事担当や、paiza転職を使って転職を成功した方々へのインタビューもございます。こちらもぜひチェックしてみてください。
詳しくはこちら