paiza times

paizaがお届けする、テック・キャリア・マネジメント領域における「今必要な情報」を届けるWebメディア

logo

paizaがお届けする、テック・キャリア・マネジメント領域の「今必要な情報」を届けるWebメディア

【結果発表】新人女子PGを最も助けたプログラミング言語とは?

2013年12月2日より開始したpaizaオンラインハッカソン(略してPOH![ポー!])Vol.1「新人女子の書いたコードを直すだけの簡単なお仕事です!」ですが、2014年1月8日いっぱいをもって開催期間を終了いたしました。今回のハッカソンのレポート、最終結果と、提出された各プログラミング言語毎の最速コードをお届けします。
POH Vol.1は応募期間は過ぎたため、プレゼント対象、計測対象には成りませんが、コードの実行は引き続き可能です。

■提出コードは2万提出突破!

おかげ様で事務局の想定を超える参加者数、提出数のハッカソンとする事ができました。ご参加いただいた皆様ありがとうございました! 今回の期間中の参加者数、提出数は以下の通りです。

  参加者数:1,961人

  提出数:22,219提出

今回の企画では、オンラインで誰でも気軽に参加できるハッカソンを目指しました。改めてプログラミングの基礎であるアルゴリズムを学んだり、1つの課題に対してどのようにコードを書くかより深く考える切っ掛けを作りたいというのが企画意図でした。

結果的に非常に多くの人に参加いただき、開催者冥利に尽きるイベントとなりました。競技プログラミングではないので,Twitterやブログ,Githubなどでの解法の公開はとくに制限せず、学びあえる場になれば、と考えていましたが、とりあえず1回だけやってみるという参加だけにとどまらず、Twitterやブログでの発信を数多くしていただけた事で、お互いに学びあう場として今回のイベントが機能したのではないかと思っております。(こちらで補足できているところだけでも約40ブログでPOH Vol.1について言及頂きました!)

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

まずはPOH Vol.1上でも掲載していた、テストケース3の最速・最遅実行時間、提出数です。

言語

最速実行時間

最遅実行時間

提出数

Java

0.06 秒

5.94 秒

2989

PHP

0.01 秒

9.93 秒

3258

Ruby

0.01 秒

9.48 秒

2213

Python

0.08 秒

9.93 秒

2519

Perl

0.01 秒

9.96 秒

1937

C

0.01 秒

2.99 秒

3466

C++

0.01 秒

2.96 秒

3367

C#

0.01 秒

6.00 秒

2470

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

テストケース3についてですが、POH Vol.1の注釈でも書いておりましたが、C,C++のテストケースは実行速度差の関係で(全言語同じサイズにするとC,C++以外の言語の処理時間が大きかったため)Nが2.5倍、Dが4倍のサイズとなっています。

どの言語でも、最速と最遅の速度差はほぼ100倍以上を上回る結果と成りました。(最遅を狙っていた人も居るかも知れませんが。。) あながち「プログラマーは出来る人と出来ない人では100倍以上の生産性の差がある」というのも嘘ではないと言えるかも知れません。

■提出数ランキング

順位

言語

提出数

1位

C

3,466提出

2位

C++

3,367提出

3位

PHP

3,258提出

4位

Java

2,989提出

5位

Python

2,519提出

6位

C#

2,470提出

7位

Ruby

2,213提出

8位

Perl

1,937提出

提出数は順当なランキングになったような気もしますが、Rubyが思ったほど伸びず、逆にPythonが健闘しています。

■最も参加者が多かった言語ランキング

トータルの参加者数は1,961人でしたが、言語別での参加者は下記のとおりです。

順位

言語

参加者数

1位

C++

429人

2位

Java

348人

3位

C

325人

4位

PHP

268人

5位

Python

265人

6位

Ruby

261人

7位

C#

199人

8位

Perl

161人

こちらのランキングも提出数とそれほど大きな差が出る結果には成りませんでした。

■最大提出数ランキング

各言語毎に、一人で一番数多く提出した人は何提出合ったのか?という集計です。平均ではないので根性ある人(良い意味で変態)が一人居るかどうかで変動するランキングです。ある意味変態度ランキングかもしれません。こちらは前二つのランキングとはだいぶ様相が違います。

順位

言語

一人の最大提出回数

1位

C#

477回

2位

Ruby

327回

3位

Perl

310回

4位

C

170回

5位

PHP

151回

6位

Python

147回

7位

C++

134回

8位

Java

82回

上位三位がC#、Perl、Rubyとなんとなくギークな香りがする顔ぶれです。C++が7位というのが意外な気がしますが、競技プログラマー勢が多いC++は解答に到達するのが早いので提出回数が少ないのかもしれません。Javaが最下位なのは、この手のコンテストに参加するには向かないという事なのか、変態が少ないという事なのか。。
野田ちゃん(新人女子プログラマ)を助けた度ランキングは、実はこのランキングなのかもしれません。(なんだかんだ言って、女子に響くのはソリューションより共感だったりしますし。。)

■各言語最速コード

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

◆Java

tubocさんの提出コード
テストケース1:success 0.07秒
テストケース2:success 0.06秒
テストケース3:success 0.06秒
http://paiza.jp/poh/ec-campaign/result/d2bd4b186de4271e897e6a3b8657ba60

import java.util.Arrays;
class Main {
    static final int SIZE=8*(2+200000+75);
    static byte[] buf=new byte[SIZE];
    static int count=0;
    static long prev = 0;

    static int read_int(){
        int r=0;
        while('\n'!=buf[count] && ' '!=buf[count] && '\0'!=buf[count] ){
            r = r * 10 + buf[count++] - '0';
        }
        count++;
        return r;
    }

    public static void main(String[] args){
        try{
            int buf_size = System.in.read(buf,0,SIZE);

            int N,D;
            N = read_int();
            D = read_int();

            if(N<1000){
                int items[] = new int[N];
                for(int i=0;i<N;i++){ items[i] = read_int(); }
                java.util.Arrays.sort(items);

                for(int i=0;i<D;i++){
                    int price = read_int();
                    int end = Arrays.binarySearch(items,price - items[0]);
                    if(end<0) end = ~end - 1;
                    int best_price = 0;
                    
                    for(int start=0;start<end;start++){
                        int base = items[start];
                        while((base+items[end]>price)){ --end; }
                        int tmp = base+items[end];
                        if(tmp>best_price){
                            if(best_price==price){
                                break;
                            }
                            best_price=tmp;
                        }
                    }

                    System.out.println(best_price);
                }
            }else{
                int rindex = buf_size-1;
                int lncount = 0;
                while(lncount<=D){
                    while(buf[rindex--]!='\n');
                    ++lncount;
                }
                rindex+=2;
                int copy_len = buf_size-rindex;
                byte new_buf[] = Arrays.copyOfRange(buf,rindex,rindex+copy_len);
                System.out.print(new String(new_buf));
            }
        }catch(Exception e){
            System.err.println(e);
        }
    }
}

Javaの最速レコードは該当者1名のみ、テストケース3:0.06秒が最速でした。

◆PHP

tubocさんの提出コード
テストケース1:success 0.01秒
テストケース2:success 0.01秒
テストケース3:success 0.01秒
http://paiza.jp/poh/ec-campaign/result/598a652d0dcf7e6d9c1547dafe7feb18

<?php
stream_set_blocking(STDIN, 0);
$stdin = file_get_contents('php://stdin');
$first = strpos($stdin,"\n");
list($N,$D)=explode(' ',substr($stdin,0,$first));

$stdin = substr($stdin,$first+1);
if($N<1000){
    $lines = preg_split("/\n/", $stdin);
    $items = array_slice($lines, 0, $N);
    $campaign = array_slice($lines, $N, $D);

    rsort($items);
    $max_value = $items[0];
    $min_value = $items[$N-1];

    for($i=0;$i<$D;$i++){
        $price = $campaign[$i];
        $topf = 0;
        $tope = $N-1;
        $top = 0;
        while($topf<=$tope){
            $top = intval(($topf+$tope)/2);
            if($items[$top]==$price){
                break;
            }
            if($items[$top]<$price){
                $tope=$top-1;
            }else{
                $topf=$top+1;
            }
        }

        $best_price = 0;
        $end = $top;
        for($start=$N-1;$start>$end;$start--){
            $base = $items[$start];
            for(;$base+$items[$end]>$price;$end++){}
            $tmp = $base+$items[$end];
            if($tmp>$best_price){
                $best_price = $tmp;
                if($best_price==$price){
                    break;
                } 
            }   
        }

        $topf = $topc;
        echo $best_price.PHP_EOL;
    }
}else{
    $len = strlen($stdin);
    $rindex = -1;
    for($i=0;$i<=$D;$i++){
        $rindex = strrpos($stdin,"\n",$rindex);
        $rindex -= strlen($stdin)+1;
    }
    $rindex+=2;
    $stdin = substr($stdin,$rindex);
    echo $stdin;
}
?>

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

◆Ruby

n2さんの提出コード
テストケース1:success 0.02秒
テストケース2:success 0.03秒
テストケース3:success 0.03秒
http://paiza.jp/poh/ec-campaign/result/b7c5307efbf7121a3f4d6b1b95764c6f

PM_MIN = 10
PM_MAX = 1000000

PAIR_MIN = PM_MIN << 1



n, d = gets.split(' ').map(&:to_i)

if n == 1
	print "0\n"*d
	exit
end



SMALL_N = 10000
if n <= SMALL_N
	ps = $stdin.read((n+d)<<3).split(?\n).map(&:to_i)
	ms = ps.pop(d)
	ps.sort!

	minp = ps[0]+ps[1]
	ms.each{|m|
		unless minp <= m
			print "0\n"
			next
		end
		rr   = n - 1
		m_p0 = m - ps[0]
		if ps[rr] <= m_p0
			r = rr
		else
			r = 1
			while rr-r >= 2
				rm = (r+rr)>>1
				if ps[rm] <= m_p0
					r  = rm
				else
					rr = rm
				end
			end
		end

		max = ps[0]+ps[r]
		if max == m
			puts m
			next
		end

		l = 1
		while l < r
			if (sum = ps[l]+ps[r]) <= m
				if max < sum
					max = sum
					break if max == m
				end
				l += 1
			else
				r -= 1
			end
		end
		puts max
	}
	exit
end

# min{str.length} = (n_min+d_min)*3-1 = (SMALL_N+1 + 1)*3-1 = SMALL_N*3+5 str = $stdin.read((n+d)<<3)


# 後ろから4000コくらい整数を取ってくる
l = str.index(?\n, -5 - SMALL_N*3)
r = -1
tail = str[l+1..r].split(?\n)

# その内後ろdコはm_i。
ms = tail.pop(d).map(&:to_i)
# 残りはp_iの一部だがこれで一旦ヒストグラムを作る
hist = Array.new(PM_MAX+1, 0)
tail.each{|pstr| hist[pstr.to_i] += 1 }



# 各mに対して答えが確定するかどうか調べる。
# 確定しない場合は1000コくらい更に読み込んでもう一度調べる。
m = ms.shift
loop{
	min = PM_MIN
	min += 1 until hist[min] != 0

	loop{
		sup_s = (m+1)>>1
		if m < PAIR_MIN		# mが20未満なら0
			puts 0
		elsif (min...sup_s).any?{|s| hist[s] != 0 && hist[m-s] != 0 } || (m.even? && hist[m>>1] >= 2)
			# 丁度mになる組が見つかったならmが答え
			puts m
		else
			break
		end
		# 次のmについて調べる。なければ終了
		exit unless m = ms.shift
	}

	# 更に1000コ程度後ろから読み込んでhistに追加
	r = l
	l = r - 1000*7
	break unless 0 <= l # そんなに読めない場合break
	l = str.index(?\n, l)
	str[l+1...r].each_line{|pstr|
		hist[pstr.to_i] += 1
	}
}

# 残りを全てhistに追加
str[0...r].each_line{|pstr|
	hist[pstr.to_i] += 1
}
min = PM_MIN
min += 1 until hist[min] != 0

# 残っているmに対する答えを出力していく
begin
	loop{
		if m < PAIR_MIN
			m = 0
			break
		end
		sup_s = (m+1)>>1
		break if (min...sup_s).any?{|s| hist[s] != 0 && hist[m-s] != 0 }
		if hist[m-sup_s] >= 2
			m = (m-sup_s)<<1
			break
		end
		m -= 1
	}
	puts m
end while m = ms.shift

※ Ruby最速(テストケース3で0.01の)コードはRuby内でCを呼び出していたので、Rubyのみで書いる最速のコードを掲載させていただきます。

Rubyの最速レコードは該当者1名のみ、テストケース3:0.01秒が最速でした。※0.03秒の上記コードを最速と考えてもn2さんのみの該当者1名でした

◆Python

tubocさんの提出コード
テストケース1:success 0.08秒
テストケース2:success 0.08秒
テストケース3:success 0.08秒
http://paiza.jp/poh/ec-campaign/result/e9e6a023bf54dba1d70c1adf2e8e5555

# python 2.7.3

import sys,bisect

(N,D) = map(int, sys.stdin.readline().split(' '))
N = int(N)
D = int(D)

if N < 1000:
    ALL = map(int, sys.stdin.read().splitlines())
    items = sorted(ALL[0:N])
    campaigns = ALL[N:]
    for price in campaigns:
        start = 0
        end = bisect.bisect_right(items,price) - 1
        best_price = tmp = 0

        while start<end:
            while items[start]+items[end]>price: end-=1
            tmp = items[start]+items[end]
            if tmp>best_price:
                best_price = tmp
                if best_price==price: break
            start+=1

        print best_price
else:
    ALL = sys.stdin.read()
    ri = len(ALL)
    c = 0
    while c<=D:
        ri = ALL.rindex('\n',0,ri)
        ri-=1;
        c+=1
    ri+=2
    answer = ALL[ri:]
    print answer,

Pythonの最速レコードは該当者2名でした。
最速レコード:tubocさん、n2さん

◆Perl

n2さんの提出コード
テストケース1:success 0.01秒
テストケース2:success 0.01秒
テストケース3:success 0.01秒
http://paiza.jp/poh/ec-campaign/result/0925b5d993b121c11b1ab92ef27d75de

# perl 5.16.2
# perl 5.16.2
<> =~ /^(\d+) (\d+)$/;
my $n = $1;
my $d = $2;



if($n == 1){
	print "0\n" for (1..$d);
	exit
}elsif($n < 5000){
	my @p = sort { $a <=> $b } map { scalar(<>) } (1..$n);

	my $min = $p[0]+$p[1];
	for my $m (<>){
		unless($min <= $m){
			print "0\n";
			next;
		}
		# 2分探索によって、$p[0]+$p[$r]<=$mとなる最大の$rを求める。
		my $r = 1;
		my $m_p0 = $m-$p[0];
		if($p[$#p] <= $m_p0){
			$r = $#p;
		}else{
			my $rr = $#p;
			while($rr-$r >= 2){
				my $rm = ($r+$rr)>>1;
				if($p[$rm] <= $m_p0){
					$r = $rm;
				}else{
					$rr = $rm;
				}
			}
		}

		my $max = $p[0]+$p[$r];
		goto END_SEARCH if $max == $m;
		my $l = 1;
		# コメントし辛い
		while($l < $r){
			while((my $sum = $p[$l]+$p[$r]) <= $m){
				if($max < $sum){
					$max = $sum;
					goto END_SEARCH if $max == $m;
				}
				$l += 1;
				goto END_SEARCH unless $l < $r;
			}
			$r -= 1;
		}
	END_SEARCH:
		print "$max\n";
	}
	exit
}

if($n < 100000){
	my @hist;
	$hist[<>+0]++ for (1..$n);

	# 地道に探索。
	my $min = 10;
	$min++ until $hist[$min];
	for my $m (<>){
		$m += 0;
		while(1){
			if($min<<1 > $m){
				$m = 0;
				goto END_SEARCH;
			}
			my $sup_l = ($m+1)>>1;
			for my $l ($min..$sup_l-1){
				goto END_SEARCH if $hist[$l] and $hist[$m-$l];
			}
			if($hist[$m-$sup_l] >= 2){
				$m = ($m-$sup_l)<<1;
				goto END_SEARCH;
			}
			$m--;
		}
	END_SEARCH:
		print "$m\n";
	}
	exit
}



# nがすごい大きい場合:
# ほぼ100%の率でm_1~m_dをそのまま出力すれば正解。
# この場合、pを最後まで読まなくてもそうするのが正解だと分かることが多い
# なので先にmを全て読み込んでからpを順番に見ていけば時間が節約できる。

# とはいってもある程度pを読み込んでいないと効率が悪いので
# はじめに一気に8000コほどpを読み込んでヒストグラムを作ってしまう。

my $input = do { local $/; <> };

# 後ろから8000コくらい整数を持ってくる
my $r = rindex($input, "\n", length($input) - 8000*7); my $tail = substr($input, $r+1); my $input = substr($input, 0, $r);

# その内後ろのdコはm_i, 残りはp_iの一部
my @t = split "\n", $tail;
my @ms_org = my @ms = splice @t, $#t+1 - $d;

# とりあえず一部のp_iでヒストグラムを作る
my @hist;
$hist[$_+0]++ for (@t);


# 現状のヒストグラムだけで2つの和がmになりうるmを取り除く
# ついでにsortして$ms[0]が最大になるようにしておく
my $min = 10;
$min++ until $hist[$min];
@ms = sort {$b <=> $a} grep {
	my $m = $_;
	if(($m&1) == 0 && $hist[$m>>1] >= 2){
		0;
	}else{
		my $keep = 1;
		for my $l ($min .. ($m-1)>>1){
			if($hist[$l] && $hist[$m-$l]){
				$keep = 0; last;
			}
		}
		$keep;
	}
} @ms;
if(scalar(@ms) == 0){ # 2つの和がmになるような組が全てのmに対して見つかった
	print "$_\n" for (@ms_org);
	exit;
}

# 残りのp_iをヒストグラムに突っ込みつつ探索する
# (最初からこうしてもhitする確率が低いため先にある程度の大きさまでhistを育てた)
for my $p (split "\n", $input){
	next if $ms[0] < $p+10;
	@ms = grep {
		my $m = $_;
		not (0 <= $m-$p && $hist[$m-$p] > 0);
	} @ms;
	if(scalar(@ms) == 0){ # 2つの和がmになるような組が全てのmに対して見つかった
		print "$_\n" for (@ms_org);
		exit;
	}
	$hist[$p+0]++;
}
# 地道に探索。とはいえここに来ることは稀
$min++ until $hist[$min];
for my $m (@ms_org){
	$m += 0;
	# $nが大きいので和が丁度$mのもの、$m-1のもの、$m-2のもの…と見ていけば効率がいい
	for my $mm (@ms){ # @msに残っているものについてのみ調べれば十分。@msにないものは丁度$mになる組が見つかっている
		if($mm == $m){
			$m--;
			while(1){
				if($min<<1 > $m){
					$m = 0;
					goto END_SEARCH;
				}
				my $sup_l = ($m+1)>>1;
				for my $l ($min..$sup_l-1){
					goto END_SEARCH if $hist[$l] and $hist[$m-$l];
				}
				if($hist[$m-$sup_l] >= 2){
					$m = ($m-$sup_l)<<1;
					goto END_SEARCH;
				}
				$m--;
			}
		}
	}
END_SEARCH:
	print "$m\n";
}

Perlの最速レコードは該当者2名でした。驚く事にPythonと同じ顔ぶれです。
最速レコード:tubocさん、n2さん

◆C

maruru_hさんの提出コード
テストケース1:success 0.01秒
テストケース2:success 0.01秒
テストケース3:success 0.01秒
http://paiza.jp/poh/ec-campaign/result/8b443ac3966dc5984198178ec147f1f5

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

//#define PRINT_TOTAL_TIME
//#define PRINT_TIME

#define MAX_OF_GOODS	500000	// 最大商品点数
#define MAX_OF_CAMPAIN	300	// 最大キャンペーン日数
#define MAX_VALUE_OF_GOODS	1000000	// 最大商品価格
#define MAX_VALUE_OF_CAMPAIN	1000000	// 最大キャンペーン価格

#define INPUT_BUF_SIZE	10 * 1024 * 1024

int	_calcMaxCombine( int nCampainValue );
int	_getNextInputInteger();

#if defined( PRINT_TIME ) || defined( PRINT_TOTAL_TIME )
	#include <sys/time.h>
	#include <sys/resource.h>
void	_initStopWatch( struct rusage* pUsage, struct timeval* pStartTime );
double	_stopWatchPoint( const char* szName, struct rusage* pUsage, struct timeval* pStartTime );
#endif

char*	g_pInputBuf;
char*	g_pInputBufPtr;

unsigned char	g_anCountOfGoodsValue[ MAX_VALUE_OF_GOODS + 1 ];	// 8byteで足りるかは適当

int main()
{
	int	i, j;
	int	nGoodsCount, nCampainCount;
	
#if defined( PRINT_TOTAL_TIME )
	clock_t	startClock = clock();
	struct rusage	totalUsage;
	struct timeval	totalStartTime;
	
	_initStopWatch( &totalUsage, &totalStartTime );
#endif
	
#if defined( PRINT_TIME )
	struct rusage	usage;
	struct timeval	startTime;
	
	_initStopWatch( &usage, &startTime );
#endif
	
	fscanf( stdin, "%d %d\n", &nGoodsCount, &nCampainCount );
	
	g_pInputBuf	= ( char* )malloc( INPUT_BUF_SIZE );
	g_pInputBufPtr	= g_pInputBuf;
	fread( g_pInputBuf, 1, INPUT_BUF_SIZE, stdin );
	
#if defined( PRINT_TIME )
	_stopWatchPoint( "read input buf", &usage, &startTime );
#endif
	
	// 商品価格取得
	for( i = nGoodsCount - 1; i >= 0; --i ){
		++g_anCountOfGoodsValue[ _getNextInputInteger() ];
	}
	
#if defined( PRINT_TIME )
	_stopWatchPoint( "input goods value time", &usage, &startTime );
#endif
	
	for( i = 0; i < nCampainCount; ++i ){
		fprintf( stdout, "%d\n", _calcMaxCombine( _getNextInputInteger() ) );
	}
	
#if defined( PRINT_TIME )
	_stopWatchPoint( "calc max combine time", &usage, &startTime );
#endif
	
	free( g_pInputBuf );
	
#if defined( PRINT_TOTAL_TIME )
	_stopWatchPoint( "total time", &totalUsage, &totalStartTime );
	
	fprintf( stderr, "total clock:%f\n", ( double )( clock() - startClock ) / CLOCKS_PER_SEC );
#endif
	
	return 0;
}


// 次のコンソール入力整数を取得
int	_getNextInputInteger()
{
	int	ret = 0;
	
	while( '0' <= *g_pInputBufPtr && *g_pInputBufPtr <= '9' ){
		ret	= ret * 10 + *g_pInputBufPtr - '0';
		++g_pInputBufPtr;
	}
	
	++g_pInputBufPtr;	// 改行を飛ばす
	
	return ret;
}


// キャンペーン価格にできるだけ近い組み合わせ結果を計算
int	_calcMaxCombine( int nCampainValue )
{
	int	nSearchStartIdx;
	int	nGoodsValue0, nGoodsValue1;
	int	nMaxSumValue = 0, nSumValue;
	int	nEndIdx = -1;
	
	nSearchStartIdx	= ( nCampainValue <= MAX_VALUE_OF_GOODS ) ? nCampainValue : MAX_VALUE_OF_GOODS;
	
	for( nGoodsValue0 = nSearchStartIdx; nGoodsValue0 > nEndIdx; --nGoodsValue0 ){
		if( g_anCountOfGoodsValue[ nGoodsValue0 ] == 0 )	continue;
		
		nGoodsValue1	= nCampainValue - nGoodsValue0;
		if( nGoodsValue1 > nGoodsValue0 )	break;
		
		if( nGoodsValue1 == nGoodsValue0 && g_anCountOfGoodsValue[ nGoodsValue0 ] < 2 ){
			--nGoodsValue1;
		}
		
		for( ; nGoodsValue1 > nEndIdx; --nGoodsValue1 ){
			if( g_anCountOfGoodsValue[ nGoodsValue1 ] == 0 )	continue;
			
			nEndIdx	= nGoodsValue1;
			
			nSumValue	= nGoodsValue0 + nGoodsValue1;
			
			if( nSumValue == nCampainValue )	return nCampainValue;
			
			if( nSumValue <= nMaxSumValue )	break;
			
			nMaxSumValue	= nSumValue;
			
			break;
		}
	}
	
	return nMaxSumValue;
}


#if defined( PRINT_TIME ) || defined( PRINT_TOTAL_TIME )
// 時間計測・初期化
void	_initStopWatch( struct rusage* pUsage, struct timeval* pStartTime )
{
	getrusage( RUSAGE_SELF, pUsage );
	*pStartTime	= pUsage->ru_utime;
}


// 時間計測・ポイント記録
double	_stopWatchPoint( const char* szName, struct rusage* pUsage, struct timeval* pStartTime )
{
	getrusage( RUSAGE_SELF, pUsage );
	
	double	diffTime = ( pUsage->ru_utime.tv_sec - pStartTime->tv_sec ) + ( pUsage->ru_utime.tv_usec - pStartTime->tv_usec ) * 1.0E-6;
	
	fprintf( stderr, "%s: %lf sec\n", szName, diffTime );
	
	*pStartTime	= pUsage->ru_utime;
	
	return diffTime;
}
#endif

Cの最速レコードは該当者29名でした。
最速レコード:tanoさん、paiza_testさん、yuyakkoさん、sharowさん、futrさん、maruru_hさん、cielさん、qさん、arさん、mr_setupさん、aさん、GM3Dさん、naturyさん、yuukiyさん、sayuriさん、pkcさん、n2さん、MikeCATさん、rarulさん、Neigeさん、myさん、buynnnmmm1さん、uso8megaさん、HirofumiYoshidaさん、shogoeさん、HirofumiYoshidaさん、techno_nekoさん、hkさん、Min_25さん

◆C++

nagoya313さんの提出コード
テストケース1:success 0.01秒
テストケース2:success 0.01秒
テストケース3:success 0.01秒
http://paiza.jp/poh/ec-campaign/result/dba8d9ce7156c29293a6b923a9132523

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <functional>

typedef const int *c_it_t;
typedef int *it_t;
const std::size_t price_max = 1000000;
const std::size_t input_len_max = 4002412;

int check(c_it_t begin, c_it_t end, int price_max) {
    int price = 0;
    const c_it_t b = std::upper_bound(begin, end,
                                      price_max, std::greater<int>());
    if (b != end) {
    for (c_it_t it = b; it != end - 1; ++it) {
            const c_it_t it2 = std::lower_bound(it + 1, end,
                                                price_max - *it,
                                                std::greater<int>());
            if (it2 != end && price < *it + *it2) {
                price = *it + *it2;
                if (price == price_max) {
                   return price;
                }
            }
        }
    }
    return price;
}

char *read_input(std::size_t &len) {
    char * const data = static_cast<char *>(std::malloc(input_len_max));
    len = std::fread(data, 1, input_len_max, stdin);
    return data;
}

int get_num(char *&it) {
    int num = 0;
    for (; *it != ' '; ++it) {
      num = num * 10 + (*it - '0');
    }
    ++it;
    return num;
}

int get_day(char *&it) {
    int day = 0;
    for (; *it != 0x0a; ++it) {
      day = day * 10 + (*it - '0');
    }
    ++it;
    return day;
}

void make_hist(char *&it, int (&hist)[price_max + 1], int num) {
    int tmp = 0;
    for (int i = 0; i < num; ++it) {
        if (*it == 0x0a) {
            ++hist[tmp];
            tmp = 0;
            ++i;
        } else {
            tmp = tmp * 10 + (*it - '0');
        }
    }
}

int *get_days(char *&it, int day, const char *data, int len) {
    int * const days = static_cast<int *>(std::malloc(sizeof(int) * (day)));
    for (int i = 0; it < data + len; ++it) {
        if (*it == 0x0a) {
            ++i;
        } else {
            days[i] =days[i] * 10 + (*it - '0');
        }
    }
    return days;
}

void dist_sort(it_t begin, it_t end, const int (&hist)[price_max + 1]) {
  for (int i = price_max; i >= 0 && begin != end; --i) {
    for (int j = 0; j < hist[i]; ++j) {
      *(begin++) = i;
    }
  }
}

int main() {
    std::size_t len;
    char * const data = read_input(len);
    char *it = data;
    const int num = get_num(it);
    const int day = get_day(it);
    int hist[price_max + 1] = {0};
    make_hist(it, hist, num);
    int *days = get_days(it, day, data, len);
    std::free(data);
    int *items = static_cast<int *>(std::malloc(sizeof(int) * (num)));
    dist_sort(items, items + num, hist);
    for (int i = 0; i < day; ++i) {
        std::printf("%d\n", check(items, items + num, days[i]));
    }
    std::free(days);
    std::free(items);
    return 0;
}

C++の最速レコードは該当者23名でした。
最速レコード:k_onisanさん、miswilさん、folsenaさん、tubocさん、hirokazu1020さん、cielさん、nagoya313さん、stqnさん、GM3Dさん、mr_setupさん、pkcさん、TJさん、daisuke_suzukaさん、n2さん、yuscarletさん、showさん、tatsunoruさん、mifcyさん、HirofumiYoshidaさん、sakakiさん、wさん、Min_25さん

◆C#

sayuriさんの提出コード
テストケース1:success 0.01秒
テストケース2:success 0.01秒
テストケース3:success 0.01秒
http://paiza.jp/poh/ec-campaign/result/903d561d6eb6a5f09a06290691081ef2

using System;
using System.Runtime.InteropServices;

static class CsPoh {
    static int Calculate(byte[] buffer, byte[] prices) {
		int ii = 0, oi = 0, temp;

		var itemCount = 0;
		while ((temp = buffer[ii++] - '0') >= 0)
			itemCount = itemCount * 10 + temp;
		var days = 0;
		while ((temp = buffer[ii++] - '0') >= 0)
			days = days * 10 + temp;

		do {
			var price = 0;
			while ((temp = buffer[ii++] - '0') >= 0)
				price = price * 10 + temp;
			prices[price] = 1;
		} while (--itemCount > 0);
		var low0 = 10;
		while (prices[low0] == 0)
			low0++;

		do {
			var targetPrice = 0;
			while ((temp = buffer[ii++] - '0') >= 0)
				targetPrice = targetPrice * 10 + temp;

			var low = low0;
			var high = targetPrice - low0;
			while (prices[high] == 0)
				high--;
			var price = 0;
			do {
				temp = low + high;
				if (temp == targetPrice) {
					price = targetPrice;
					break;
				}
				if (temp < targetPrice) {
					if (price < temp)
						price = temp;
					while (prices[++low] == 0)
						;
				} else
					while (prices[--high] == 0)
						;
			} while (low < high);

			if (100000 <= price)
				goto l100000;
			if (10000 <= price)
				goto l10000;
			if (1000 <= price)
				goto l1000;
			goto l100;
        l100000:
            buffer[oi++] = (byte)('0' + Math.DivRem(price, 100000, out price));
		l10000:
            buffer[oi++] = (byte)('0' + Math.DivRem(price, 10000, out price));
		l1000:
            buffer[oi++] = (byte)('0' + Math.DivRem(price, 1000, out price));
		l100:
            buffer[oi++] = (byte)('0' + Math.DivRem(price, 100, out price));
            buffer[oi++] = (byte)('0' + Math.DivRem(price, 10, out price));
			buffer[oi++] = (byte)('0' + price);
			buffer[oi++] = 10;
		} while (--days > 0);
		return oi;
	}

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

	static void Main() {
		const int valueLength = 2 + 200000 + 75;
		var buffer = new byte[valueLength * 7];
		var handle = GCHandle.Alloc(buffer, GCHandleType.Pinned);
		var pbuf = Marshal.UnsafeAddrOfPinnedArrayElement(buffer, 0);
		read(0, pbuf, valueLength * 7);
		var length = Calculate(buffer, new byte[1000001]);
		write(1, pbuf, length);
		handle.Free();
	}
}

C#の最速レコードは該当者3名でした。
最速レコード:n2さん、mr_setupさん、sayuriさん

最速コードは複数言語でn2さんが6言語(Ruby,Python,Perl,C,C++,C#)、tubocさんが5言語(Java,PHP,Python,Perl,C++)ランクインという結果に。この2名がもっとも野田さんを助けたお二人かもしれません。凄いですね!!

■0.01秒への道

当初事務局で考えていた以上に入力周りのチューニングで速度差が出る事になりましたが、高速化のためのアプローチは、ざっくりいうとアルゴリズムに変更による計算量(オーダー)の改善⇒定数倍高速化と呼ばれる部分最適化(入出力部分など)という流れになります。今回の問題は、計算量(オーダー)については、何も考えずに実装するとO(DN^2)になり、よく考えると O(DNlogN) ⇒ O(DN)と高速化出来るような問題になっています。

f:id:paiza:20140114222307g:plain

こちらのグラフはJavaでO(DN^2)、O(DNlogN)、O(DN)と計算量の違う3種類のアルゴリズムで実装したコードに、徐々に大きいデータを喰わせていった際の実行時間の変化のグラフです。データサイズが小さいときはさほど差は出ませんが、サイズが大きくなればなるほどアルゴリズム毎の実行時間の差が大きくなって行くのがお分かりかと思います。

paiza会員登録すると、O(DN^2)、O(DNlogN)、O(DN)といった計算量別の各言語毎のコードもご覧いただく事が可能です。各アルゴリズムのサンプルコードを見てみたい!という方は是非ご登録ください!!
https://paiza.jp/users/new

ソートや入力周りは言語による違いも大きいのでここでの解説は割愛しますが、下記のブログに今回の問題に対するアプローチが非常によくまとめてありましたのでご紹介します。

 Cで新人女子に褒めてもらう
 http://qiita.com/HirotoKagotani/items/4882a5a5dc82afc17d0f

■まとめ

今回初めての企画でしたが、多くの方に参加いただき無事企画を終える事が出来ました。こちらが想定していた以上に早いコードが出てきたり、ブログ等で思っていた以上に色々と書いていただけたことで、学びの場として一定の成果を出せたのではないかと思っています。

ただその一方で事務局側の反省もいくつかあります。途中でサーバが非常に重くなってしまったり、待ち時間削減の為テストケースを数少なくしていた為、ある意味偏ったテストケースになっていた点などです。次回開催時にはよりこの辺りも対応できればと思っております。オンラインハッカソンに関するアイデア等有れば是非paiza事務局まで是非ご意見をお寄せください!

■プレゼントについて

ロックスター・エナジードリンクについては本日当選者にメールをさせて頂ますのでご確認ください。連絡が取れない場合は再抽選となります。

paiza会員登録すると、今回のPOH Vol.1の各言語の各アルゴリズムの実装パターンが見れるほか、スキルチェックが出来る様々な問題が出題されています。
https://paiza.jp/users/new




続けて読む⇒POH結果報告その2:実行時間の差は996倍以上。オンラインハッカソン最速コードの裏側に迫る!




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

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

paiza転職

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

paizaのスキルチェック

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

paizaのおすすめコンテンツ

Webセキュリティ入門 ハッカー入門 Webセキュリティ講座がスタート!CVは内田真礼さん! Python✕AI 機械学習入門講座 CVに上坂すみれさんを起用!人気の機械学習講座を公開中!
paiza転職 paiza新卒 EN:TRY paizaラーニング 記事内に記載している情報は、記事公開時点でのものとなります。 Copyright Paiza, Inc, All rights reserved.