【結果発表】炎上中の20万人月PJを鎮火させた14言語のコード

f:id:paiza:20140903163517j:plain
※会員ページにて本日より天才火消しエンジニア霧島の水着壁紙(2560x1600、1024x768)がダウンロードいただけますので、会員登録がまだの方はご登録が必要です。

2014年7月30日より開始したpaizaオンラインハッカソン（略してPOH![ポー！]）Lite「天才火消しエンジニア霧島　もしPMおじさんが『丸投げ』を覚えたら」ですが、2014年8月27日いっぱいをもって開催期間を終了いたしました。(コードの実行自体は引き続き可能です)。　

今回のオンラインハッカソンは、誰でも参加しやすいように問題の難易度をこれまでよりも少し下げ、ヒント機能等もつけた形でした。今回も数多くご参加いただき無事オンラインハッカソンを終える事が出来ました！　今回はpaizaオンラインハッカソンLiteのレポート、最終結果と、提出された各プログラミング言語毎の最速コードについてお届けします。

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

paizaオンラインハッカソンLite上でも掲載していましたが、まずはテストケース７(大規模データ)の最速・最遅実行時間、提出数です。

言語	最速実行時間	最遅実行時間	通過数 / 受験数
Java	0.01 秒	5.72 秒	210 / 767 提出
PHP	0.01 秒	14.97 秒	124 / 642 提出
Ruby	0.02 秒	14.43 秒	374 / 1223 提出
Python	0.01 秒	5.88 秒	116 / 468 提出
Perl	0.01 秒	5.88 秒	15 / 116 提出
C	0.01 秒	2.49 秒	88 / 523 提出
C++	0.01 秒	2.79 秒	281 / 784 提出
C#	0.01 秒	5.41 秒	184 / 593 提出
JavaScript	0.03 秒	5.64 秒	49 / 380 提出
Objective-C(Beta)	0.01 秒	0.01 秒	3 / 3 提出
Scala(Beta)	0.28 秒	0.60 秒	6 / 97 提出
Go(Beta)	0.01 秒	1.75 秒	21 / 70 提出
Haskell(Beta)	0.01 秒	2.19 秒	9 / 45 提出
CoffeeScript(Beta)	0.10 秒	0.19 秒	4 / 10 提出
Bash(Beta)	0.01 秒	2.34 秒	8 / 73 提出
Erlang(Beta)	1.16 秒	2.08 秒	2 / 12 提出
R(Beta)	0.10 秒	0.10 秒	1 / 23 提出
COBOL(Beta)	0.01 秒	1.73 秒	2 / 8 提出
VB(Beta)	0.01 秒	0.29 秒	21 / 26 提出
F#(Beta)	0.03 秒	0.08 秒	4 / 4 提出

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

今回提出数ではRubyが1223提出と1位でした。2位以下は2位C++（784提出）、3位Java（767提出）、4位PHP（642提出）、5位C#（593提出）、6位C（523提出）、7位Python（468提出）、8位JavaScript（380提出）、9位Perl（116提出）という順番でした。

β版の言語ではScalaが97提出と健闘しています。実を言うとβ版の言語は事務局側ではあまり動作テストが出来ていなかったのですが、各言語ともCase7を通す提出がありました。

次に各言語別のテストケース7の通過率を見てみましょう。

■テストケース7の言語別通過率

言語	TC7通過数	受験数	TC7通過率
Java	210	767	27.4%
PHP	124	642	19.3%
Ruby	374	1223	30.6%
Python	116	468	24.8%
Perl	15	116	12.9%
C	88	523	16.8%
C++	281	784	35.8%
C#	184	593	31.0%
JavaScript	49	380	12.9%
Objective-C(Beta)	3	3	100.0%
Scala(Beta)	6	97	6.2%
Go(Beta)	21	70	30.0%
Haskell(Beta)	9	45	20.0%
CoffeeScript(Beta)	4	10	40.0%
Bash(Beta)	8	73	11.0%
Erlang(Beta)	2	12	16.7%
R(Beta)	1	23	4.3%
COBOL(Beta)	2	8	25.0%
VB(Beta)	21	26	80.8%
F#(Beta)	4	4	100.0%

テストケース7の通過率は全般的には25％台でしたが、ベータ版言語を除くとC++が35.8％と一番成果率が高く、続いてC#の31.0％、Rubyの30.6％と続いています。C++が強いのは毎度ながらの傾向です。POH2ではRubyは通過率で再開でしたが今回は3位と健闘しています。逆にJavaScript、Perlがイケてない結果になっています。PerlはこれまでのPOHに比べてもダントツに参加人数も少なく、なんとなくオワコン的な香りが…。

■各言語最速コード

以下編集部で選定した最速コードになります。問題内容はpaizaオンラインハッカソンLiteをご確認ください。

◆Java

KoukiMinoさんの提出コード
テストケース1：0.07秒
テストケース2：0.07秒
テストケース3：0.07秒
テストケース4：0.07秒
テストケース5：0.07秒
テストケース6：0.07秒
テストケース7：0.07秒
http://paiza.jp/poh/kirishima/result/939e3303a1b0588b7fb51748e2ed227a

import java.util.Arrays;
 
public class Main {
 // static-OJISAN!!
 static final int SIZE=8*(12+16*50);
 static byte[] buf=new byte[SIZE];
 static int count=0;
 static int answer = Integer.MAX_VALUE;
 static int m,n;
 static qclass q[];
 
 static class qclass implements Comparable {
  Float tanka;
  Integer ninzu;
  Integer kingaku;
  public int compareTo(Object obj) {
   qclass operand = (qclass) obj;
   if (this.tanka < operand.tanka) {
    return -1;
   } else if (this.tanka > operand.tanka) {
    return 1;
   } else {
    return 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;
 }
 
 static void getMinCost(int index, int sumq, int sumr) {
  if (sumq >= m){
   if (sumr < answer){
    answer = sumr;
   }
  }
  else {
   if (index >= n){
   }
   else {
    int least_q = m - sumq;
    float least_r = sumr;
    int next_index = index + 1;
    for (int i=next_index;i<n;i++){
     if (q[i].ninzu < least_q){
       least_q = least_q - q[i].ninzu;
       least_r = least_r + q[i].kingaku;
     }
    }
    if (least_r >= answer){
    }
    else{
     getMinCost(next_index, sumq + q[index].ninzu, sumr + q[index].kingaku);
     getMinCost(next_index, sumq , sumr);
    }
   }
  }
 }
 
 public static void main(String[] args){
  try{
   // long start = System.currentTimeMillis();
   // long stop;
   int buf_size = System.in.read(buf,0,SIZE);
 
   // stop = System.currentTimeMillis();
   // System.out.println(""!!!INPUT_TIME->"" + (stop - start));
 
   // 1 ≦ m ≦ 200000
   m = read_int();
 
   // 1 ≦ n ≦ 50
   n = read_int();
 
   q = new qclass[n];
 
   // 1 ≦ q_i ≦ 10000
   // 1 ≦ r_i ≦ 5000000
   for (int i=0;i<n;i++){
    q[i] = new qclass();
    q[i].ninzu = read_int();
    q[i].kingaku = read_int();
    q[i].tanka = (float)q[i].kingaku / q[i].ninzu;
   }
 
   Arrays.sort(q);
 
   // for (int i=0;i<n;i++){
   //  System.out.println(""tanka->"" + q[i].tanka + "" ninzu->"" + q[i].ninzu + "" kingaku->"" + q[i].kingaku);
   // }
 
   getMinCost(0,0,0);
   // System.out.println(answer);
   int oi = 0;
   int shou;
   int flg = 0;
   if (10000000 <= answer){
    shou = answer / 10000000;
    answer = answer % 10000000;
    buf[oi++] = (byte)('0' + shou);
    flg = 1;
   }
   if (1000000 <= answer){
    shou = answer / 1000000;
    answer = answer % 1000000;
    buf[oi++] = (byte)('0' + shou);
    flg = 1;
   }
   else {
    if (flg == 1){
     buf[oi++] = (byte)('0');
    }
   }
   if (100000 <= answer){
    shou = answer / 100000;
    answer = answer % 100000;
    buf[oi++] = (byte)('0' + shou);
    flg = 1;
   }
   else {
    if (flg == 1){
     buf[oi++] = (byte)('0');
    }
   }
   if (10000 <= answer){
    shou = answer / 10000;
    answer = answer % 10000;
    buf[oi++] = (byte)('0' + shou);
    flg = 1;
   }
   else {
    if (flg == 1){
     buf[oi++] = (byte)('0');
    }
   }
   if (1000 <= answer){
    shou = answer / 1000;
    answer = answer % 1000;
    buf[oi++] = (byte)('0' + shou);
    flg = 1;
   }
   else {
    if (flg == 1){
     buf[oi++] = (byte)('0');
    }
   }
   if (100 <= answer){
    shou = answer / 100;
    answer = answer % 100;
    buf[oi++] = (byte)('0' + shou);
    flg = 1;
   }
   else {
    if (flg == 1){
     buf[oi++] = (byte)('0');
    }
   }
   if (10 <= answer){
    shou = answer / 10;
    answer = answer % 10;
    buf[oi++] = (byte)('0' + shou);
    flg = 1;
   }
   else {
    if (flg == 1){
     buf[oi++] = (byte)('0');
    }
   }
   buf[oi++] = (byte)('0' + answer);
   buf[oi++] = 10;
 
   System.out.write(buf,0,oi);
 
   // stop = System.currentTimeMillis();
   // System.out.println(""!!!TOTAL_TIME->"" + (stop - start));
  }catch(Exception e){
   System.err.println(e);
  }
 }
}

◆PHP

wmoaiさんの提出コード
テストケース1：0.01秒
テストケース2：0.01秒
テストケース3：0.01秒
テストケース4：0.01秒
テストケース5：0.01秒
テストケース6：0.01秒
テストケース7：0.01秒
http://paiza.jp/poh/kirishima/result/1ca47aa23ff22112a860fa3106768c69

<?php
  // v2
  stream_set_blocking(STDIN, 0);
  $stdin = file_get_contents('php://stdin');
  $first = strpos($stdin,""\n"");
  $m = substr($stdin,0,$first);
  $stdin = substr($stdin,$first+1);
  $second = strpos($stdin,""\n"");

  $stdin = substr($stdin,$second+1);
  $qrs = preg_split(""/\n/"", trim($stdin));

  $remain = 0;
  $nqrs = array();
  foreach ($qrs as $qr) {
    list($q,$r) = array_map('intval', explode(' ', $qr));
    $nqrs[$q][] = $r;
    $remain += $q;
  }
  krsort($nqrs);

  $result = array();
  foreach ($nqrs as $q => $rs) {
    foreach ($rs as $r) {
      foreach ($result as $rq => $rr) {
        if ($rq+$remain >= $m && $rq < $m) {
          $result[$rq+$q] = !isset($result[$rq+$q]) ? $rr+$r : min($rr+$r, $result[$rq+$q]);
        }
      }
      $result[$q] = !isset($result[$q]) ? $r : min($r, $result[$q]);

      asort($result);
      $pq = 0;
      $buffer = array();
      foreach ($result as $cq => $cr) {
        if ($pq < $cq) {
          $buffer[$cq] = $cr;
          if ($cq >= $m) {
            break;
          }
          $pq = $cq;
        }
      }
      $result = $buffer;
      $remain -= $q;
    }
  }
  echo end($result).""\n"";
?>

◆Ruby

quarter_moonさんの提出コード
テストケース1：0.02秒
テストケース2：0.02秒
テストケース3：0.02秒
テストケース4：0.02秒
テストケース5：0.02秒
テストケース6：0.03秒
テストケース7：0.02秒
http://paiza.jp/poh/kirishima/result/d65cd4721b5177f951d4edd4f3b264f1

# 自分の得意な言語で
# Let's チャレンジ！！

GC.disable
m_,n_,*qr = $<.read.lines.map {|e| e.split.map {|s| s.to_i } }
m,n = m_[0],n_[0]
@p,@q,@r = qr.map {|e| [e[0].to_f / e[1], e[0], e[1]] } .sort.reverse.transpose
@m,@n = m,n
@current_least_cost = 10**10

def lowerbound(offs, criteria)
  return nil unless offs < @n
  return 0 if criteria <= 0

  sum = 0
  i = offs
  while i < @n do
    sum += @q[i]
    i += 1
    break if sum >= criteria
  end

  if sum >= criteria
    last_const = 1.0 - ((sum - criteria).to_f / @q[i-1])
    last_cost = (last_const * @r[i-1]).ceil
    if offs < i-1
      @r[offs...(i-1)].inject(:+) + last_cost
    else
      last_cost
    end
  else
    nil
  end
end

def dfs(i, max, criteria, cost_acc)
  if i == max
    if 0 >= criteria
      if cost_acc < @current_least_cost
        @current_least_cost = cost_acc
      end
      0
    else
      nil
    end
  else
    if @current_least_cost < cost_acc
      nil
    else
      cost0 = dfs(i+1, max, criteria-@q[i], cost_acc+@r[i])
      if cost0
        c = cost0 + @r[i]
        lbr = lowerbound(i+1, criteria)
        if lbr and c < lbr
          c
        else
          cost1 = dfs(i+1, max, criteria, cost_acc)
          cost1 ? (c < cost1 ? c : cost1) : c
        end
      else
        dfs(i+1, max, criteria, cost_acc)
      end
    end
  end
end

min = dfs(0, n, m, 0)
puts min

◆Python

KoukiMinoさんの提出コード
テストケース1：0.01秒
テストケース2：0.01秒
テストケース3：0.01秒
テストケース4：0.01秒
テストケース5：0.01秒
テストケース6：0.01秒
テストケース7：0.01秒
http://paiza.jp/poh/kirishima/result/4d302149dc357c597172ec1f0bbff830

# -*- coding: utf-8 -*-
# python 2.7.6
import sys

# index番目以降の下請け会社から人数の総和がm以上となるように選ぶ
def getMinCost(index, sumq, sumr):
	global m
	global n
	global q
	global answer

	if sumq >= m:
		# プロジェクトに必要な人員数m人を越えた
		if sumr <= answer:
			# 求める最低金額を格納
			answer = sumr
	else:
		if index >= n:
			# 下請け会社総数を越えた
			pass
		else:
			# 現時点より残りの最低コストを求める
			least_q = m - sumq
			least_r = 0
			for i in range(index + 1, n):
				(next_tanka,next_q,next_r) = q[i]
				if next_q < least_q:
					least_r += next_r
					least_q -= next_q

			if sumr + least_r >= answer:
				pass
			else:
				# 選択して次の下請け会社へ
				getMinCost(index + 1, sumq + q[index][1], sumr + q[index][2])

				# 選択せずに次の下請け会社へ
				getMinCost(index + 1, sumq , sumr)

# プロジェクトに必要な人員数	1 ≦ m ≦ 200000
m = int(raw_input())

# 下請け会社の数 			1 ≦ n ≦ 50
n = int(raw_input())

ALL = map(str, sys.stdin.read().splitlines())

# 下請け会社の人員数		1 ≦ q_i ≦ 10000
q = []

# 発注に必要な費用[単位：万円]	1 ≦ r_i ≦ 5000000
r = []

total = 0
app = q.append
for line in ALL:
	(q_w,r_w) = map(int, line.split(' '))

	# (単価,人数,発注費用)　を格納
	app((float(r_w)/q_w, q_w, r_w))

# 単価の少ない順にソート
q = sorted(q,key=lambda x: x[0])

# 求める最小金額
answer = sys.maxint

# 解答出力
getMinCost(0, 0, 0)
print str(answer)

◆Perl

KoukiMinoさんの提出コード
テストケース1：0.01秒
テストケース2：0.01秒
テストケース3：0.01秒
テストケース4：0.01秒
テストケース5：0.01秒
テストケース6：0.01秒
テストケース7：0.01秒
http://paiza.jp/poh/kirishima/result/9903b417ad05a4c8757ca416cd19d640

# プロジェクトに必要な人員数	1 ≦ m ≦ 200000
our $m = <>;

# 下請け会社の数 			1 ≦ n ≦ 50
our $n = <>;

# 下請け会社の人員数		1 ≦ q_i ≦ 10000
# 発注に必要な費用[単位：万円]	1 ≦ r_i ≦ 5000000
our @q = ();
for my $line (<>) {
	($q_w,$r_w) = split(/ /,$line);
	$q[@q] = [$r_w/$q_w,$q_w,$r_w];
}

# 単価の少ない順にソート
@q = sort { @$a[0] <=> @$b[0] } @q;

# 求める最小金額
our $answer = 5000000 * 50;

getMinCost(0,0,0);
print $answer.""\n"";

# [関数] 人数の総和が$m以上となる最小コストを再帰的に求める
sub getMinCost {
	(my $index, my $sumq, my $sumr) = @_;
	if ($sumq >= $m){
		# プロジェクトに必要な人員数m人を越えた
		if ($sumr <= $answer){
			# 求める最低金額を格納
			$answer = $sumr;
		}
	}
	else {
		if ($index >= $n){
			# 下請け会社総数を越えた
		}
		else {
			# 現時点より残りの最低コストを求める
			my $least_q = $m - $sumq;
			my $least_r = $sumr;
			my $next_index = $index + 1;
			for ($i=$next_index;$i<$n;$i++){
				if ($q[$i][1] < $least_q){
					$least_q -= $q[$i][1];
					$least_r += $q[$i][2];
				}
				# else{
				# 	$least_r += $least_q * $q[$i][0];
				# 	break;
				# }
			}

			if ($least_r >= $answer){
				# 現在の金額に残りコストを足すと、
				# 最低金額を越えてしまうので
				# 処理しない
			}
			else {
				# 選択して次の下請け会社へ
				getMinCost($next_index, $sumq + $q[$index][1], $sumr + $q[$index][2]);

				# 選択せずに次の下請け会社へ
				getMinCost($next_index, $sumq , $sumr);
			}
		}
	}

}

◆C

tomyさんの提出コード
テストケース1：0.01秒
テストケース2：0.01秒
テストケース3：0.01秒
テストケース4：0.01秒
テストケース5：0.01秒
テストケース6：0.01秒
テストケース7：0.01秒
http://paiza.jp/poh/kirishima/result/bcb81e98c26b1fd08c689587410fee1a

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

/* 会社情報を記憶するCOMPANY型 */
typedef struct
{
	int person;		//会社人数
	int price;		//値段
}COMPANY;

int main(void)
{
	int i = 0, j = 0;
	int neads = 0, cnt_of_com = 0;		//neads:必要人数 、 cnt_of_com:下請け会社数
	int sum_person = 0, sum_price = 0;	//sum_person:総人数、 sum_price:全社合計金額
	int sum_deny_price = 0;				//sum_deny_price:発注しない会社の合計金額
	int deniable_person = 0;			//発注しないことができる最大人数（下請け総人数 - 必要人数）
	int *price_deny_com;				//発注しない会社の総額を格納する配列
	COMPANY *company;					//会社情報を格納する配列

	/* 必要人数と下請け会社数を取得 */
	scanf(""%d"", &neads);	getchar();
	scanf(""%d"", &cnt_of_com);	getchar();

	/* 会社情報を格納する配列の領域を動的確保 */
	company = (COMPANY*)malloc(sizeof(COMPANY)*cnt_of_com);

	/* 各会社の情報を取得 */
	for(i = 0; i < cnt_of_com; i++)
	{
		scanf(""%d %d"", &company[i].person, &company[i].price);		getchar();
	}

	/* 総人数と全社合計金額セット */
	for(i = 0; i < cnt_of_com; i++)
	{
		sum_person += company[i].person;
		sum_price  += company[i].price;
	}

	/* 動的計画法に使う配列を動的確保 */
	price_deny_com = (int*)malloc(sizeof(int*)*sum_person);

	/* 動的計画法に使う配列を-1で初期化 */
	for(i = 0; i < sum_person; i++)
		price_deny_com[i] = -1;
	price_deny_com[0] = 0;		//先頭は0にする

	/* 雇わない最大人数セット */
	deniable_person = sum_person - neads;

	/* 動的計画法を用いて発注しない会社の合計金額を出していく */
	for(i = 0; i < cnt_of_com; i++)	//すべての会社に対して処理
	{
		for(j = sum_person - 1; j >= 0; j--)	//後ろから先頭まで走査
		{
			if(price_deny_com[j] != -1)		//-1でないとき
				if(j + company[i].person <= deniable_person)	//雇わない限界数を超えないとき
					if(price_deny_com[j + company[i].person] < price_deny_com[j] + company[i].price)	//値段が高くなるとき
						price_deny_com[j + company[i].person] = price_deny_com[j] + company[i].price;	//更新
		}
	}

	/* 発注しない会社の合計額の最大値を求める */
	for(j = 0; j < sum_person; j++)
	{
		if(sum_deny_price < price_deny_com[j])
			sum_deny_price = price_deny_com[j];
	}

	/* 結果出力 */
	/* 全社合計額 - 発注しない会社の合計額の最大 = 発注する会社の合計額の最少 */
	printf(""%d\n"", sum_price - sum_deny_price);

	/* メモリ解放 */
	free(price_deny_com);
	free(company);

	return 0;
}

◆C++

piza_taroさんの提出コード
テストケース1：0.01秒
テストケース2：0.01秒
テストケース3：0.01秒
テストケース4：0.01秒
テストケース5：0.01秒
テストケース6：0.01秒
テストケース7：0.01秒
http://paiza.jp/poh/kirishima/result/45c1a788afd84b574c0d548bfd11b34c

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;
int main(){
    int M, N, i, j;

    scanf(""%d%d"",&M, &N);

    vector<int> num(N), cost(N);
    for( i=0; i<N; i++) scanf(""%d%d"",&num[i],&cost[i] );

    unsigned int total = accumulate(num.begin(), num.end(), 0);

    vector<unsigned int> X(total+1 ,-1); X[0]=0;
    for(j=0; j<N; j++) {
        int k = num[j];
        for( i=total-k; i>=0; i--)
            if( X[i]!=-1 ) {
                int x = X[i]+cost[j];
                if( X[k+i]>x ) X[k+i]=x;
            }
    }
    cout<< *min_element(X.begin() + M, X.end()) << endl;
    return 0;
}

◆C#

IL_kさんの提出コード
テストケース1：0.01秒
テストケース2：0.01秒
テストケース3：0.01秒
テストケース4：0.01秒
テストケース5：0.01秒
テストケース6：0.01秒
テストケース7：0.01秒
http://paiza.jp/poh/kirishima/result/675bb572bdc976817dbcca4348197527

using System;
using System.Text;
using System.Runtime.InteropServices;
using System.Collections.Generic;

namespace ConsoleApplication2
{
    class Program
    {
        [DllImport(""libc"")]
        static extern int read(int handle, byte[] buf, int n);
        [DllImport(""libc"")]
        static extern int write(int handle, byte[] buf, int n);
        [DllImport(""libc"")]
        static extern void printf(string format, int value);
        static int readRef = 0, wref = 0;
        static byte[] rBuf = new byte[10000];
        static byte[] wBuf = new byte[100];

        static int readint()
        {
            int ret = 0, tmp;
            while ((tmp = rBuf[readRef++] - '0') >= 0)
                ret = ret * 10 + tmp;
            return ret;
        }

        static void Main(string[] args)
        {
            int m, n, maxMan=0, target, maxCost=0, wallet=1, current, val;
            read(0, rBuf, 10000);
            m = readint();  //  目標
            n = readint();  //  会社数
            int[] man = new int[n];
            int[] cost = new int[n];

            for (int i = 0; i < n; i++)
            {
                maxMan += man[i] = readint();   //  人数
                maxCost += cost[i] = readint(); //  費用
            }
            target = maxMan - m;                //  不要な人月最大値
            int[] dp = new int[target + 1];
            dp[0] = 1;                          //  使用中は1以上とする
            if (man[0] <= target)
                wallet = dp[man[0]] = cost[0] + dp[0];  //  初期値
            for (int i = 1; i < n; i++ )
            {
                current = man[i];               //  処理中の会社の人月
                for (int column = target - current; column >= 0; column--)
                {
                    if (dp[column] > 0 && (val = dp[column] + cost[i]) > dp[column + current] )
                    {
                        dp[column + current] = val;
                        if (val > wallet)
                            wallet = val;       //  残る金額最大を目指す
                    }
                }
            }
            printf(""%d\n"", maxCost - wallet + 1);  //   費用最大値-残る金=最小金額+1
        }
    }
}

◆JavaScript

KoukiMinoさんの提出コード
テストケース1：0.03秒
テストケース2：0.03秒
テストケース3：0.03秒
テストケース4：0.03秒
テストケース5：0.03秒
テストケース6：0.03秒
テストケース7：0.03秒
http://paiza.jp/poh/kirishima/result/968e0d3dd66b06ec5d29c43000eaa695

var fs = require(""fs"");
var fd = process.stdin.fd;
var content = """";
var BUFFER_SIZE = 4096;
var buffer = new Buffer(BUFFER_SIZE);
var bp;
while( (bp = fs.readSync(fd, buffer, 0, BUFFER_SIZE)) > 0) {
	content += buffer.slice(0, bp).toString();
}
var lines = content.toString().split('\n');
var m = lines.shift() * 1;
var n = lines.shift() * 1;
var q = [];
for(var i=0,l=n; i<l; i++) {
	var work = lines[i].replace(/(^\s+)|(\s+$)/g, """").split("" "");
	q[i] = {
		tanka: work[1] / work[0]
		,ninzu: work[0] * 1
		,kingaku: work[1] * 1
	}
}
q.sort(function(a,b){return a.tanka - b.tanka});
// for(var i=0,l=n; i<l; i++) {
// 	console.log(q[i]);
// }
var answer = Number.MAX_VALUE;
getMinCost(0,0,0);
console.log(answer);
function getMinCost(index, sumq, sumr){
	if (sumq >= m){
		if (sumr < answer){
			answer = sumr;
		}
	}
	else {
		if (index >= n){

		}
		else {
			var least_q = m - sumq;
			var least_r = sumr;
			var next_index = index + 1;
			for (var i=next_index,l=n;i<l;i++){
				if (q[i].ninzu < least_q){
					least_q -= q[i].ninzu;
					least_r += q[i].kingaku;
				}
			}
			if (least_r >= answer){

			}
			else {
				getMinCost(index + 1, sumq + q[index].ninzu, sumr + q[index].kingaku);
				getMinCost(index + 1, sumq , sumr);
			}
		}
	}
}

◆Go(Beta)

erukitiさんの提出コード
テストケース1：0.01秒
テストケース2：0.01秒
テストケース3：0.01秒
テストケース4：0.01秒
テストケース5：0.01秒
テストケース6：0.01秒
テストケース7：0.01秒
http://paiza.jp/poh/kirishima/result/3697cdea2b8e89a821e3ec78db6ca688

package main

import (
	""bufio""
	""fmt""
	""os""
	""strconv""
	""strings""
)

var sc = bufio.NewScanner(os.Stdin)

func nextLine() string {
	sc.Scan()
	return sc.Text()
}

func atoi(s string) int {
	n, _ := strconv.Atoi(s)
	return n
}

func atoi64(s string) int64 {
	n, _ := strconv.ParseInt(s, 10, 64)
	return n
}

type Q struct {
	q int
	r int64
}

func main() {
	m := atoi(nextLine())
	n := atoi(nextLine())
	q := make([]Q, n)
	max := 0
	max_value := int64(0)
	for i := 0; i < n; i++ {
		a := strings.Split(nextLine(), "" "")
		q[i] = Q{atoi(a[0]), atoi64(a[1])}
		max += q[i].q
		max_value += q[i].r
	}
	max -= m
	dp := make([]int64, max+1)

	for i := 0; i < n; i++ {
		for j := max; j >= 0; j-- {
			if j+q[i].q <= max && dp[j+q[i].q] < dp[j]+q[i].r {
				dp[j+q[i].q] = dp[j] + q[i].r
			}
		}
	}

	a := int64(0)
	for i := 0; i <= max; i++ {
		if a <= dp[i] {
			a = dp[i]
		}
	}
	// fmt.Println(a)
	// fmt.Println(dp)
	fmt.Println(max_value - a)
}

◆Haskell(Beta)

arowMさんの提出コード
テストケース1：0.01秒
テストケース2：0.01秒
テストケース3：0.01秒
テストケース4：0.01秒
テストケース5：0.01秒
テストケース6：0.01秒
テストケース7：0.01秒
http://paiza.jp/poh/kirishima/result/663571175ff83439ea4e51f444a16ba5

{-# OPTIONS_GHC -O2 -Wall -fno-warn-missing-signatures -fno-warn-type-defaults #-}

import Data.List

main = interact $ (`shows` ""\n"") . sv . lines

data Plan = Plan { cost :: Int, numPerson :: Int }
  deriving (Show,Eq,Ord)
sumPlan (Plan c1 n1) (Plan c2 n2) = Plan (c1+c2) (n1+n2)

sv :: [String] -> Int
sv (m':_:qs) = cost . head . dropWhile ((< m) . numPerson) . dp . map readAsPlan $ qs
  where m = read m' :: Int
sv _ = error ""Invalid Input""

dp :: [Plan] -> [Plan]
dp [] = [Plan 0 0]
dp (q:qs) = mergePlans oldOs newOs
  where
    oldOs = dp qs
    newOs = Plan 0 0 : map (sumPlan q) oldOs

-- |
-- >>> mergePlans [Plan 3 40, Plan 5 20, Plan 3 20, Plan 4 10] [Plan 5 10, Plan 4 30]
-- [Plan {cost = 0, numPerson = 0},Plan {cost = 3, numPerson = 40}]
mergePlans :: [Plan] -> [Plan] -> [Plan]
mergePlans xs ys = takeBestCases (Plan 0 0). sort $ xs ++ ys

takeBestCases :: Plan -> [Plan] -> [Plan]
takeBestCases p [] = [p]
takeBestCases (p@(Plan c n)) (p1@(Plan c1 n1): xs)
  | c == c1 = takeBestCases p1 xs
  | n < n1 = p : takeBestCases p1 xs
  | otherwise = takeBestCases p xs

readAsPlan w = Plan c n
  where (n:c:_) = map read . words $ w

◆CoffeeScript(Beta)

KoukiMinoさんの提出コード
テストケース1：0.10秒
テストケース2：0.10秒
テストケース3：0.10秒
テストケース4：0.10秒
テストケース5：0.10秒
テストケース6：0.10秒
テストケース7：0.10秒
http://paiza.jp/poh/kirishima/result/bea7699ce5cf1779fb98460843c1140b

"getMinCost = (index, sumq, sumr, m, n, q) ->
  if sumq >= m
    q[n].kingaku = sumr if sumr < q[n].kingaku
  else
    if index < n
      least_q = m - sumq
      least_r = sumr
      next_index = index + 1
      i = next_index
      while i < n
        if q[i].ninzu < least_q
          least_q -= q[i].ninzu
          least_r += q[i].kingaku
        i++
      if least_r < q[n].kingaku
        getMinCost index + 1, sumq + q[index].ninzu, sumr + q[index].kingaku, m, n, q
        getMinCost index + 1, sumq, sumr, m, n, q
  return
fs = require(""fs"")
fd = process.stdin.fd
content = """"
BUFFER_SIZE = 4096
buffer = new Buffer(BUFFER_SIZE)
bp = undefined
content += buffer.slice(0, bp).toString()  while (bp = fs.readSync(fd, buffer, 0, BUFFER_SIZE)) > 0
lines = content.toString().split(""\n"")
m = lines.shift() * 1
n = lines.shift() * 1
q = []
i = 0
while i < n
  work = lines[i].replace(/(^\s+)|(\s+$)/g, """").split("" "")
  q[i] =
    tanka: work[1] / work[0]
    ninzu: work[0] * 1
    kingaku: work[1] * 1
  i++
q.sort (a, b) ->
  a.tanka - b.tanka
q[n] = 
    kingaku: Number.MAX_VALUE
getMinCost 0, 0, 0, m, n, q
console.log q[n].kingaku"

◆VB(Beta)

KoukiMinoさんの提出コード
テストケース1：0.01秒
テストケース2：0.01秒
テストケース3：0.01秒
テストケース4：0.01秒
テストケース5：0.02秒
テストケース6：0.01秒
テストケース7：0.01秒
http://paiza.jp/poh/kirishima/result/d9a0e433abf515b928ee1e009796973e

Imports System
Imports System.Text
Imports System.Runtime.InteropServices

Public Class qclass
    Implements IComparable
    Private _tanka As Single
    Public ReadOnly Property tanka As Single
        Get
            Return Me._tanka
        End Get
    End Property
    
    Private _ninzu As Integer
    Public ReadOnly Property ninzu As Integer
        Get
            Return Me._ninzu
        End Get
    End Property
    
    Private _kingaku As Integer
    Public ReadOnly Property kingaku As Integer
        Get
            Return Me._kingaku
        End Get
    End Property
    
    Public Sub New(ByVal ninzu As Integer, ByVal kingaku As Integer)
        MyBase.New
        Me._ninzu = ninzu
        Me._kingaku = kingaku
        Me._tanka = (CType(kingaku,Single) / ninzu)
    End Sub
    
    Public Function CompareTo(ByVal obj As Object) As Integer Implements IComparable.CompareTo
        Return Me.tanka.CompareTo(CType(obj,qclass).tanka)
    End Function
End Class

Class kirishima
    
    Private Declare Function read Lib ""libc"" (ByVal fd As Integer, ByVal buf As IntPtr, ByVal count As Integer) As Integer
    Private Declare Function write Lib ""libc"" (ByVal fd As Integer, ByVal buf As IntPtr, ByVal count As Integer) As Integer
    
    Private Shared answer As Integer = Int32.MaxValue
    Private Shared qp As System.Collections.ArrayList = New System.Collections.ArrayList
    Private Shared m As Integer
    Private Shared n As Integer
    
    Private Shared Function read_int(ByRef pbuf() As Byte, ByRef pcount As Integer) As Integer
        Dim r As Integer = 0
        While (10 <> pbuf(pcount) AndAlso 32 <> pbuf(pcount))
             r = r * 10  + pbuf(pcount) - 48
             pcount = pcount + 1
        End While
        pcount = pcount + 1
        Return r
    End Function

    Private Shared Sub getMinCost(ByVal index As Integer, ByVal sumq As Integer, ByVal sumr As Integer)
        If (sumq >= m) Then
            If (sumr <= answer) Then
                answer = sumr
            End If
        ElseIf (index >= n) Then
            
        Else
            Dim least_q As Integer = (m - sumq)
            Dim least_r As Single = sumr
            Dim next_index As Integer = (index + 1)
            Dim i As Integer = next_index
            Do While (i < n)
                Dim work As qclass = CType(qp(i),qclass)
                If (work.ninzu < least_q) Then
                    least_q = (least_q - work.ninzu)
                    least_r = (least_r + work.kingaku)
                End If
                i = (i + 1)
            Loop
            If (least_r >= answer) Then
                
            Else
                Dim work As qclass = CType(qp(index),qclass)
                getMinCost(next_index, (sumq + work.ninzu), (sumr + work.kingaku))
                getMinCost(next_index, sumq, sumr)
            End If
        End If
    End Sub
    
    public Shared Sub Main()
        Const valueLength As Integer = 10000
        Dim buffer As Byte() = New Byte(((valueLength * 7)) - 1) {}
        Dim count As Integer = 0
        Dim handle As GCHandle = GCHandle.Alloc(buffer, GCHandleType.Pinned)
        Dim pbuf As Object = Marshal.UnsafeAddrOfPinnedArrayElement(buffer, 0)
        read(0, pbuf, (valueLength * 7))
        m = read_int(buffer, count)
        n = read_int(buffer, count)
        Dim r_w As Integer
        Dim q_w As Integer
        Dim i As Integer = 0
        Do While (i < n)
             q_w = read_int(buffer, count)
             r_w = read_int(buffer, count)
             qp.Add(New qclass(q_w, r_w))
             i = (i + 1)
        Loop
        qp.Sort
        getMinCost(0, 0, 0)
        ' Console.Write(""{0}"", answer)
        Dim oi As Integer = 0
        Dim shou As Integer
        If (10000000 <= answer) Then
            goto l10000000
        End If
        If (1000000 <= answer) Then
            goto l1000000
        End If
        If (100000 <= answer) Then
            goto l100000
        End If
        If (10000 <= answer) Then
            goto l10000
        End If
        If (1000 <= answer) Then
            goto l1000
        End If
        If (100 <= answer) Then
            goto l100
        End If
        If (10 <= answer) Then
            goto l10
        End If
        goto l1
        l10000000:
            shou = answer \ 10000000
            answer = answer - shou * 10000000
            buffer(oi) = 48 + shou
            oi = oi + 1
        l1000000:
            shou = answer \ 1000000
            answer = answer - shou * 1000000
            buffer(oi) = 48 + shou
            oi = oi + 1
        l100000:
            shou = answer \ 100000
            answer = answer - shou * 100000
            buffer(oi) = 48 + shou
            oi = oi + 1
        l10000:
            shou = answer \ 10000
            answer = answer - shou * 10000
            buffer(oi) = 48 + shou
            oi = oi + 1
        l1000:
            shou = answer \ 1000
            answer = answer - shou * 1000
            buffer(oi) = 48 + shou
            oi = oi + 1
        l100:
            shou = answer \ 100
            answer = answer - shou * 100
            buffer(oi) = 48 + shou
            oi = oi + 1
        l10:
            shou = answer \ 10
            answer = answer - shou * 10
            buffer(oi) = 48 + shou
            oi = oi + 1
        l1:
            buffer(oi) = 48 + answer
            oi = oi + 1
            buffer(oi) = 10
            oi = oi + 1
        write(1, pbuf, oi)
        handle.Free
    End Sub
End Class

O(2^n)のコード、動的計画法によるコードといった計算量別の各言語毎のコードはpaiza会員ページ内に掲載しております。各アルゴリズムのサンプルコードを見てみたい！という方は是非ご登録ください！！
https://paiza.jp/users/new

f:id:paiza:20140903164326j:plain
※会員ページにて本日より天才火消しエンジニア霧島の水着壁紙(2560x1600、1024x768)がダウンロードいただけますので、会員登録がまだの方はご登録が必要です。

今回の問題の解法解説については9月11日(木)に更新予定ですのでご期待ください！
⇒【POH Lite解説】もし先輩女子エンジニアが『アルゴリズム』を図解で教えてくれるとしたら

■POH Liteをハックする！

最後にCOBOLのコードを紹介して終わりたいと思います。。。
えー、、見ての通りなのですが、今回の問題は二分探索的に何回も試せば割と解答にはたどり着きやすいので、各ケースごとの解答を何回も提出して探し出せばこのような解法も可能だったようです。一本取られました。事務局サイドとしてはハッカソンなのでこういうのもありかなと思っております。

◆COBOL(Beta)

cielさんの提出コード
テストケース1：0.01秒
テストケース2：0.01秒
テストケース3：0.01秒
テストケース4：0.01秒
テストケース5：0.01秒
テストケース6：0.01秒
テストケース7：0.01秒
http://paiza.jp/poh/kirishima/result/582b65b67aebe73cfb7df7a4ed118537

identification division.
	program-id. paizapoh3.
	data division.
	working-storage section.
		77 m PIC X(6).
		77 mover redefines m PIC Z(6).
		77 n PIC 9(6).
		77 o PIC 9(6) value 1.
		77 p PIC 9(6) value 10.
		77 q PIC 9(6) value 40.
		77 r PIC 9(6) value 60.
		77 s PIC 9(6) value 75.
		77 t PIC 9(6) value 250.
		77 u PIC 9(6) value 2000.
		77 v PIC 9(6) value 20000.
		77 w PIC 9(6) value 200000.
	procedure division.
	main.
		accept m.
		move mover to n.
		if n=o
			display 1
		else if n=p
			display 1038
		else if n=q
			display 4171
		else if n=r
			display 6600
		else if n=s
			display 8061
		else if n=t
			display 23072
		else if n=u
			display 5000000
		else if n=v
			display 3162243
		else if n=w
			display 48768277
		end-if
		end-if
		end-if
		end-if
		end-if
		end-if
		end-if
		end-if
		end-if.
		stop run.