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 |
テストケース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)と高速化出来るような問題になっています。
こちらのグラフは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転職を使って転職を成功した方々へのインタビューもございます。こちらもぜひチェックしてみてください。
詳しくはこちら