paiza POH paizen #paizahack_02

|問題|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|

## タイム一覧
- <del>今回は数値と文字列入力が混在しているので、入力ゲーで遊ぶのはやめにしました。</del>
- やはり、C/C#/Javaは入力ゲーしました。C#では0.2秒ほど改善しました。
- 3重ループの範囲で自明な最適化を行ったところ大体1.5倍速になりました。breakでさらに約1.2倍。
- 注：C/C++/C#/Javaは入力が約4倍であるのでタイムを単純に比較することはできない。

|言語|タイム (case 6/7)|URL|
|:--|:--|:--|
|C/C++/ObjC|0.05/0.07<br>0.04/0.07<br>**0.01/0.01**|S http://paiza.jp/poh/paizen/result/acf6478f17eb286b9195f2a916c9ac60<br>SSS http://paiza.jp/poh/paizen/result/8935f2ceabbc3383464992c292a5d8ae<br>S http://paiza.jp/poh/paizen/result/2c75e7a5d1dcda45b753649cb1a01a32|
|C#|0.56/0.92|S http://paiza.jp/poh/paizen/result/8d80b33213af1e18a1289b886fda526a|
|Java|0.74/0.79|S http://paiza.jp/poh/paizen/result/1d2c0086601102091543836b29f9e79a|
|D|0.02/0.02|S https://paiza.jp/poh/paizen/result/ad5855209f8df31cc2297d4d8043896e|
|Rust|0.05/0.04|S https://paiza.jp/poh/paizen/result/e125dd0a|
|Go|0.06/0.06|S https://paiza.jp/poh/paizen/result/e2a182f15712cce988382f4c9fed857f|
|Swift|0.08/0.08|S https://paiza.jp/poh/paizen/result/b32ee9ed|
|VB|0.13/0.16|S https://paiza.jp/poh/paizen/result/d8bc504a6f26e4758016a8f03b8c44d3|
|F#|0.16/0.16|S http://paiza.jp/poh/paizen/result/ee4f41838b41704ecccef81be44eef8a|
|JavaScript|0.32/0.32|S https://paiza.jp/poh/paizen/result/fc554f953df6f293a26a766cfc2f5c7d|
|Perl|0.27/0.44|SSS http://paiza.jp/poh/paizen/result/ebe8598b58953bf0df7cf0e892615428|
|Bash|0.28/0.45|S http://paiza.jp/poh/paizen/result/d5054843e2300b9bd8aaa0c2daf81e5f|
|Kotlin|0.37/0.36|S https://paiza.jp/poh/paizen/result/d2d29e97|
|CoffeeScript|0.42/0.43|S https://paiza.jp/poh/paizen/result/e561794a6559ebc2b38e1f4f0402f79b|
|PHP|0.51/0.67|S http://paiza.jp/poh/paizen/result/4097fa1b78e1cb96e26dba9717dda76b|
|Ruby|0.56/0.75|SSS https://paiza.jp/poh/paizen/result/2cc2a120e1a213ef4a279b23e2a3fcaa|
|Python/Python3|0.39/0.56<br>0.52/0.73|SS http://paiza.jp/poh/paizen/result/c39472dd72e865fcb0cfe426901a68f8<br>S https://paiza.jp/poh/paizen/result/9aeecc19f765798e8bfa6985762c894d|
|Scala|1.46/1.48|S https://paiza.jp/poh/paizen/result/94391a249d5a9f75989ea6f4f0a7b5b5|

[141227追記] Ruby 2.2 0.42s/0.54s http://paiza.jp/poh/paizen/result/5e82ce814f073fdd1fbffce530d30ca2

ほとんどのコメントが「す、凄いなんて思ってるわけじゃないんだから！」でした。C++は「マジ、神！見直しちゃった。。」でした。
「グッジョブ！木野ちゃん喜んでましたよ」は、
http://paiza.jp/poh/paizen/result/54fbf75eb29c51bffb5a33b667f9871a

Rubyが遅いですが、Rubyの配列アクセスは遅いということがAtCoder ABC001Dによりわかっているため、さほど気にしてはいません。
参考:

- TLE http://abc001.contest.atcoder.jp/submissions/108191
- AC http://abc001.contest.atcoder.jp/submissions/109448

あと、(next_permutationを20言語で書いてベンチマーク取った実験から推測できるものの)JavaScript速いですね。
<del>paizaのシステム上では数ヶ月前(?)からJavaScriptが使えるようになっています。ところがPOHでは使えないように設定されているため、その設定を外しただけです。</del>公式対応有難うございました。

## 参加記録

内容としては、Get a Rectangular Field ( http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1114 )やRectangular Searching ( http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0116 )といった問題の、クエリが複数与えられるバージョンと考えて良い。 
これらの問題の想定解法はO(H^2*W)である。
愚直にDPしてみた。

Ruby (TLE after test case 5)

```rb
#!/usr/bin/ruby
h,w=gets.split.map(&:to_i)
a=h.times.map{gets.chomp.chars.map{|c|[c=='1' ? 0 : 1]+[0]*(h-1)}}
0.step(h-1){|i|
	1.step(w-1){|j|
		a[i][j][0]+=a[i][j-1][0] if a[i][j][0]>0
	}
}
1.step(h-1){|i|
	0.step(w-1){|j|
		1.step(i){|k|
			a[i][j][k]=[a[i-1][j][k-1],a[i][j][k-1]].min
			break if a[i][j][k]==0
		}
	}
}
gets.to_i.times{
	s,t=gets.split.map(&:to_i)
	r=0
	if s<=h
		h.times{|i|w.times{|j|
			r+=1 if a[i][j][s-1]>=t
		}}
	end
	puts r
}
```

C (TLE after test case 3)

```c
#include <stdio.h>
#define m(a,b) (a<b?a:b)
int a[300][300][300];
int main(){
	int c,h,w,s,t,r,i,j,k;
	scanf("%d%d",&h,&w);getchar();
	for(i=0;i<h;i++,getchar())for(j=0;j<w;j++)a[i][j][0]=(getchar()-'0')^1;
	for(i=0;i<h;i++)for(j=1;j<w;j++)if(a[i][j][0])a[i][j][0]+=a[i][j-1][0];
	for(i=1;i<h;i++)for(j=0;j<w;j++)for(k=1;k<=i;k++){
		a[i][j][k]=m(a[i-1][j][k-1],a[i][j][k-1]);
		if(!a[i][j][k])break;
	}
	for(scanf("%d",&k);k--;){
		scanf("%d%d",&s,&t);
		r=0;
		if(s<=h)for(i=0;i<h;i++)for(j=0;j<h;j++)r+=a[i][j][s-1]>=t;
		printf("%d\n",r);
	}
	return 0;
}
```

O(H^2*W)が想定解法のはずである。ではなぜTLEを起こすのか。
よく見ると、 **Nの上限がH*W** とある。
つまり、後半の部分もDPしなければならない。
これで100点を取ることが可能である。

Ruby (1.15/1.64)

```rb
#!/usr/bin/ruby
h,w=gets.split.map(&:to_i)
a=h.times.map{gets.chomp.chars.map{|c|[c=='1' ? 0 : 1]+[0]*(h-1)}}
accum=h.times.map{[0]*(w+1)}
0.step(h-1){|i|
	accum[0][a[i][0][0]]+=1
	1.step(w-1){|j|
		if a[i][j][0]>0
			a[i][j][0]+=a[i][j-1][0]
			accum[0][a[i][j][0]]+=1
		end
	}
}
1.step(h-1){|i|
	0.step(w-1){|j|
		1.step(i){|k|
			a[i][j][k]=[a[i-1][j][k-1],a[i][j][k-1]].min
			break if a[i][j][k]==0
			accum[k][a[i][j][k]]+=1
		}
	}
}
0.step(h-1){|i|
	(w-1).downto(0){|j|
		accum[i][j]+=accum[i][j+1]
	}
}
gets.to_i.times{
	s,t=gets.split.map(&:to_i)
	p s<=h && t<=w ? accum[s-1][t] : 0
}
```

C (0.04/0.07)

```c
#include <stdio.h>
#define m(a,b) (a<b?a:b)
///
char z[9999999];
static int input_count=0;
int get(){
	int r=0;
	for(;'0'<=z[input_count]&&z[input_count]<='9';)r=r*10+z[input_count++]-'0';
	input_count++;
	return r;
}
int getC(){
	return z[input_count++];
}
///
int a[300][300][300],accum[300][301];
int main(){
	fread(z,1,sizeof(z),stdin);
	int h,w,s,t,i,j,k;
	//scanf("%d%d",&h,&w);getchar();
	h=get(),w=get();
	for(i=0;i<h;i++,getC())for(j=0;j<w;j++)a[i][j][0]=(getC()-'0')^1;
	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]=m(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];
	//scanf("%d",&k);
	k=get();
	for(;k--;){
		s=get(),t=get();
		//scanf("%d%d",&s,&t);
		printf("%d\n",s<=h&&t<=w?accum[s-1][t]:0);
	}
	return 0;
}
```

Qiitaはタグを5つまでしか付けられないため、C#とJavaもここに記す。

C# (0.56/0.92)

```csharp
using System;
using System.Linq;
class PaizaPOH2{
	const int SIZE=9999999;
	static byte[] z=new byte[SIZE];
	static int input_count=0;

	static int get(){
		int r=0;
		for(;'0'<=z[input_count]&&z[input_count]<='9';)r=r*10+z[input_count++]-'0';
		input_count++;
		return r;
	}
	static int getC(){
		return z[input_count++];
	}
	static void Main(){
		Console.OpenStandardInput().Read(z,0,SIZE);
		int h,w,s,t,i,j,k;
		//int[] arg=Console.ReadLine().Split(' ').Select(_=>int.Parse(_)).ToArray();
		//h=arg[0];
		//w=arg[1];
		h=get();
		w=get();
		int[,,] a=new int[h,w,h];
		int[,] accum=new int[h,w+1];
		for(i=0;i<h;i++){
			//string line=Console.ReadLine();
			for(j=0;j<w;j++)a[i,j,0]=(getC()-'0')^1;
			getC();
		}
		for(i=0;i<h;i++){
			accum[0,a[i,0,0]]++;
			for(j=1;j<w;j++){
				if(a[i,j,0]>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]=Math.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]]++;
		}
		for(i=0;i<h;i++)for(j=w-1;j>=0;j--)accum[i,j]+=accum[i,j+1];
		//k=int.Parse(Console.ReadLine());
		k=get();
		for(;k>0;k--){
			//arg=Console.ReadLine().Split(' ').Select(_=>int.Parse(_)).ToArray();
			//s=arg[0];
			//t=arg[1];
			s=get();
			t=get();
			Console.WriteLine(s<=h&&t<=w?accum[s-1,t]:0);
		}
	}
}
```

Java (0.74/0.79)

```java
//import java.util.*;
class Main{
	static final int SIZE=9999999;
	static byte[] z=new byte[SIZE];
	static int input_count=0;

	static int get(){
		int r=0;
		for(;'0'<=z[input_count]&&z[input_count]<='9';)r=r*10+z[input_count++]-'0';
		input_count++;
		return r;
	}
	static int getC(){
		return z[input_count++];
	}
	public static void main(String[]args){try{
		System.in.read(z,0,SIZE);
		//Scanner cin=new Scanner(System.in);
		int h,w,s,t,i,j,k;
		//h=cin.nextInt();
		//w=cin.nextInt();
		//cin.nextLine();
		h=get();
		w=get();
		int[][][] a=new int[h][w][h];
		int[][] accum=new int[h][w+1];
		for(i=0;i<h;i++){
			//String line=cin.nextLine();
			for(j=0;j<w;j++)a[i][j][0]=(getC()-'0')^1;
			getC();
		}
		for(i=0;i<h;i++){
			accum[0][a[i][0][0]]++;
			for(j=1;j<w;j++){
				if(a[i][j][0]>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]=Math.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]]++;
		}
		for(i=0;i<h;i++)for(j=w-1;j>=0;j--)accum[i][j]+=accum[i][j+1];
		//k=cin.nextInt();
		k=get();
		for(;k>0;k--){
			//s=cin.nextInt();
			//t=cin.nextInt();
			s=get();
			t=get();
			System.out.println(s<=h&&t<=w?accum[s-1][t]:0);
		}
	}catch(java.io.IOException e){}}
}
```