paiza POH kirishima (Java/Coffee/Ruby/PHP/Python) #paizahack_lite

問題	https://paiza.jp/poh/kirishima
C/Go/C#/VB/JavaScript	http://qiita.com/cielavenir/items/aad18ccc8463e77a1c87
Java/CoffeeScript/Ruby/PHP/Python	http://qiita.com/cielavenir/items/d07e62d1dc61c2915003
Perl/Scala/F#/D	http://qiita.com/cielavenir/items/0b338f5c1b2e57ed915e
最速解答	http://qiita.com/cielavenir/items/2afc31eb9718e3170755
Swift	http://qiita.com/cielavenir/items/16440e1e3713a41a3830

Java

paizapohlite.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;
	}
	public static void main(String[]args){try{
		System.in.read(z,0,SIZE);
		int M,N,q,r,total=0,i,j;
		M=get();
		N=get();
		int[] num=new int[N];
		int[] cost=new int[N];
		for(total=j=0;j<N;j++){
			q=get();r=get();
			total+=q;
			num[j]=q;
			cost[j]=r;
		}
		int[] bag=new int[total+1];
		for(i=1;i<=total;i++)bag[i]=-1;
		for(j=0;j<N;j++){
			for(i=total;i>=num[j];i--){
				if(bag[i-num[j]]>=0){
					if(bag[i]<0||bag[i]>bag[i-num[j]]+cost[j]){
						bag[i]=bag[i-num[j]]+cost[j];
					}
				}
			}
		}
		j=-1;
		for(i=M;i<=total;i++)if(j<0||(bag[i]>=0&&j>bag[i]))j=bag[i];
		System.out.println(j);
	}catch(java.io.IOException e){}}
}

CoffeeScript
やはりまだ書き慣れないです。

paizapohlite.coffee

# !/usr/bin/env coffee
T=[]
stdin = process.openStdin()
stdin.setEncoding('utf8')

input_fragment=''
stdin.on 'data', (input) ->
		ref=(input_fragment+input).split("\n")
		input_fragment=ref.pop()
		for i in [0...ref.length]
			if ref[i]==''
				continue
			T.push(ref[i])


stdin.on 'end', (z) ->
	if input_fragment
		ref=(input_fragment+"\n").split("\n")
		input_fragment=ref.pop()
		for i in [0...ref.length]
			if ref[i]==''
				continue
			T.push(ref[i])
	M=Number(T[0])
	N=Number(T[1])
	num=Array(N)
	cost=Array(N)
	total=0
	for j in [0...N]
		arg=T[j+2].split(' ').map(Number)
		total+=arg[0]
		num[j]=arg[0]
		cost[j]=arg[1]
	bag=Array(total+1)
	bag[0]=0
	for i in [1..total]
		bag[i]=-1
	for j in [0...N]
		i=total
		while i>=num[j]
			if bag[i-num[j]]>=0
				if bag[i]<0 || bag[i]>bag[i-num[j]]+cost[j]
					bag[i]=bag[i-num[j]]+cost[j]
			i--
	j=-1
	for i in [M..total]
		if j<0 || (bag[i]>=0 && j>bag[i])
			j=bag[i]
	console.log(j)

Ruby
今回スクリプト言語の中では健闘している気がする。

paizapohlite.rb

# !/usr/bin/ruby
M=gets.to_i
N=gets.to_i
num=[0]*N
cost=[0]*N
total=0
N.times{|j|
	q,r=gets.split.map(&:to_i)
	total+=q
	num[j]=q
	cost[j]=r
}
bag=[0]+[-1]*total
N.times{|j|
	total.downto(num[j]){|i|
		if bag[i-num[j]]>=0
			if bag[i]<0 || bag[i]>bag[i-num[j]]+cost[j]
				bag[i]=bag[i-num[j]]+cost[j]
			end
		end
	}
}
j=-1
M.upto(total){|i|
	if j<0 || (bag[i]>=0&&j>bag[i])
		j=bag[i]
	end
}
p j

PHP

paizapohlite.php

# !/usr/bin/php
<?php
$M=intval(fgets(STDIN));
$N=intval(fgets(STDIN));
$num=array();
$cost=array();
$total=0;
for($j=0;$j<$N;$j++){
	list($q,$r)=array_map(intval,split(" ",fgets(STDIN)));
	$total+=$q;
	$num[$j]=$q;
	$cost[$j]=$r;
}
$bag=array();
$bag[0]=0;
for($i=1;$i<=$total;$i++)$bag[$i]=-1;
for($j=0;$j<$N;$j++){
	for($i=$total;$i>=$num[$j];$i--){
		if($bag[$i-$num[$j]]>=0){
			if($bag[$i]<0||$bag[$i]>$bag[$i-$num[$j]]+$cost[$j]){
				$bag[$i]=$bag[$i-$num[$j]]+$cost[$j];
			}
		}
	}
}
$j=-1;
for($i=$M;$i<=$total;$i++)if($j<0||($bag[$i]>=0&&$j>$bag[$i]))$j=$bag[$i];
echo $j.PHP_EOL;

Python

paizapohlite.py

# !/usr/bin/python
import sys
if sys.version_info[0]>=3: raw_input=input

M=int(raw_input())
N=int(raw_input())
num=[0]*N
cost=[0]*N
total=0
for j in range(N):
	q,r=[int(e) for e in raw_input().split()]
	total+=q
	num[j]=q
	cost[j]=r
bag=[0]+[-1]*total
for j in range(N):
	for i in reversed(range(num[j],total+1)):
		if bag[i-num[j]]>=0:
			if bag[i]<0 or bag[i]>bag[i-num[j]]+cost[j]:
				bag[i]=bag[i-num[j]]+cost[j]
j=-1
for i in range(M,total+1):
	if j<0 or (bag[i]>=0 and j>bag[i]):
		j=bag[i]
print(j)