paiza POH paizen #paizahack_02 (Perl/PHP/Python)

問題	https://paiza.jp/poh/paizen
タイム一覧/Ruby/C/C++/C#/Java	http://qiita.com/cielavenir/items/17f66daa2be639fd74f3
Perl/PHP/Python	http://qiita.com/cielavenir/items/5b57808a28a8b4c5c7b2
JavaScript	http://qiita.com/cielavenir/items/9dab2bfbcfa0047b345f
CoffeeScript/Go/Scala/VB/F#	http://qiita.com/cielavenir/items/32591dd03376ba534d1e

Perl (0.27/0.44)
accumをちゃんと初期化しないと死ぬ模様。面倒くさい。

#!/usr/bin/perl
use strict;
use warnings;
use feature 'say';
my @a=();
my @accum=();
my($h,$w)=split(/ /,<>);
for(my $i=0;$i<$h;$i++){
	my $line=<>;
	for(my $j=0;$j<$w;$j++){
		$a[$i][$j][0]=substr($line,$j,1)^1;
	}
}
for(my $i=0;$i<$h;$i++){for(my $j=0;$j<=$w;$j++){$accum[$i][$j]=0;}}
for(my $i=0;$i<$h;$i++){
	$accum[0][$a[$i][0][0]]++;
	for(my $j=1;$j<$w;$j++){
		if($a[$i][$j][0]){
			$a[$i][$j][0]+=$a[$i][$j-1][0];
			$accum[0][$a[$i][$j][0]]++;
		}
	}
}
for(my $i=1;$i<$h;$i++){for(my $j=0;$j<$w;$j++){for(my $k=1;$k<=$i;$k++){
	$a[$i][$j][$k]=$a[$i-1][$j][$k-1];
	if($a[$i][$j][$k]>$a[$i][$j][$k-1]){$a[$i][$j][$k]=$a[$i][$j][$k-1];}
	if(!$a[$i][$j][$k]){last;}
	$accum[$k][$a[$i][$j][$k]]++;
}}}
for(my $i=0;$i<$h;$i++){for(my $j=$w-1;$j>=0;$j--){$accum[$i][$j]+=$accum[$i][$j+1];}}
for(my $k=<>;$k--;){
	my($s,$t)=split(/ /,<>);
	say ($s<=$h&&$t<=$w?$accum[$s-1][$t^0]:0);
}

PHP (0.51/0.67)
splitしたのをintvalにarray_mapしないと、最後の範囲チェックで文字列同士の比較になって死にます。

#!/usr/bin/php
<?php
$a=array();
$accum=array();
list($h,$w)=array_map(intval,split(" ",fgets(STDIN)));
for($i=0;$i<$h;$i++){
	$line=fgets(STDIN);
	for($j=0;$j<$w;$j++){
		$a[$i][$j][0]=intval($line[$j])^1;
	}
}
for($i=0;$i<$h;$i++)for($j=0;$j<=$w;$j++)$accum[$i][$j]=0;
for($i=0;$i<$h;$i++){
	$accum[0][$a[$i][0][0]]++;
	for($j=1;$j<$w;$j++){
		if($a[$i][$j][0]){
			$a[$i][$j][0]+=$a[$i][$j-1][0];
			$accum[0][$a[$i][$j][0]]++;
		}
	}
}
for($i=1;$i<$h;$i++)for($j=0;$j<$w;$j++)for($k=1;$k<=$i;$k++){
	$a[$i][$j][$k]=min($a[$i-1][$j][$k-1],$a[$i][$j][$k-1]);
	if(!$a[$i][$j][$k])break;
	$accum[$k][$a[$i][$j][$k]]++;
}
for($i=0;$i<$h;$i++)for($j=$w-1;$j>=0;$j--)$accum[$i][$j]+=$accum[$i][$j+1];
for($k=intval(fgets(STDIN));$k--;){
	list($s,$t)=array_map(intval,split(" ",fgets(STDIN)));
	echo ($s<=$h&&$t<=$w?$accum[$s-1][$t]:0).PHP_EOL;
}
?>

Python (0.39/0.56)
Pythonっぽくはないが、Perl/PHPと比較すればきれいな方かと。

#!/usr/bin/python
import sys
if sys.version_info[0]>=3:
	raw_input=input
	xrange=range

h,w=[int(e) for e in raw_input().split()]
a=[[[0 if c=='1' else 1]+[0]*(h-1) for c in raw_input().rstrip()] for i in xrange(h)]
accum=[[0]*(w+1) for i in xrange(h)]
for i in xrange(h):
	accum[0][a[i][0][0]]+=1
	for j in xrange(1,w):
		if a[i][j][0]>0:
			a[i][j][0]+=a[i][j-1][0]
			accum[0][a[i][j][0]]+=1
for i in xrange(1,h):
	for j in xrange(w):
		for k in xrange(1,i+1):
			a[i][j][k]=min(a[i-1][j][k-1],a[i][j][k-1])
			if a[i][j][k]==0: break
			accum[k][a[i][j][k]]+=1
for i in xrange(h):
	for j in reversed(xrange(0,w)):
		accum[i][j]+=accum[i][j+1]
for i in xrange(int(raw_input())):
	s,t=[int(e) for e in raw_input().split()]
	print(accum[s-1][t] if s<=h and t<=w else 0)