| 問題 | 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 |
タイム一覧
今回は数値と文字列入力が混在しているので、入力ゲーで遊ぶのはやめにしました。- やはり、C/C#/Javaは入力ゲーしました。C#では0.2秒ほど改善しました。
- 3重ループの範囲で自明な最適化を行ったところ大体1.5倍速になりました。breakでさらに約1.2倍。
- 注：C/C++/C#/Javaは入力が約4倍であるのでタイムを単純に比較することはできない。
[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速いですね。
paizaのシステム上では数ヶ月前(?)からJavaScriptが使えるようになっています。ところがPOHでは使えないように設定されているため、その設定を外しただけです。公式対応有難うございました。
参加記録
内容としては、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)
#!/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)
#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^2W)が想定解法のはずである。ではなぜTLEを起こすのか。
よく見ると、 **Nの上限がHW** とある。
つまり、後半の部分もDPしなければならない。
これで100点を取ることが可能である。
Ruby (1.15/1.64)
#!/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)
#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)
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)
//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){}}
}