paiza POH kirishima (Perl/Scala/F#/D) #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

Perl

paizapohlite.pl

# !/usr/bin/perl
use strict;
use warnings;
use feature 'say';
my $M=<>;
my $N=<>;
my @num=();
my @cost=();
my $total=0;
my ($i,$j);

for($j=0;$j<$N;$j++){
	my($q,$r)=split(/ /,<>);
	$total+=$q;
	$num[$j]=$q;
	$cost[$j]=$r;
}
my @bag=();
$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];}}
say $j;

Scala
AC取れた。どういうわけか、スペースだとOK、タブだとWAという謎な状態になってる。

paizapohlite.scala

//must use spaces rather than tabs, or WA somehow.
object Main extends App{
    val M=readInt()
    val N=readInt()
    val num=new Array[Int](N)
    val cost=new Array[Int](N)
    var total=0
    for(j<-0 to N-1){
        val Array(q,r) = readLine().split(" ").map(_.toInt)
        total+=q
        num(j)=q
        cost(j)=r
    }
    val bag=new Array[Int](total+1)
    for(i<-1 to total)bag(i)=(-1)
    for(j<-0 to N-1){
        for(i<-total to num(j) by -1){
            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)
                }
            }
        }
    }
    var j=(-1)
    for(i<-M to total){
        if(j<0||(bag(i)>=0&&j>bag(i)))j=bag(i)
    }
    println(j)
}

F#
関数型言語として扱っていない。

paizapohlite.fs

open System
let M=int(Console.ReadLine())
let N=int(Console.ReadLine())
let num:int array=Array.zeroCreate(N)
let cost:int array=Array.zeroCreate(N)
let mutable total=0
for j in 0..N-1 do
 let arg:String array=Console.ReadLine().Split(' ')
 total<-total+int(arg.[0])
 num.[j]<-int(arg.[0])
 cost.[j]<-int(arg.[1])
let bag:int array=Array.zeroCreate(total+1)
for i in 1..total do
 bag.[i]<-(-1)
for j in 0..N-1 do
 for i in total..(-1)..num.[j] do
  if bag.[i-num.[j]]>=0 && (bag.[i]<0||bag.[i]>bag.[i-num.[j]]+cost.[j]) then
   bag.[i]<-bag.[i-num.[j]]+cost.[j]
let mutable j=(-1)
for i in M..total do
 if j<0||(bag.[i]>=0&&j>bag.[i]) then
  j<-bag.[i]
Console.WriteLine(j)

D

paizapohlite.d

import std.stdio;

int main(){
	int M,N,q,r,total=0,i,j;
	scanf("%d%d",&M,&N);
	int num[]=new int[N];
	int cost[]=new int[N];
	for(total=j=0;j<N;j++){
		scanf("%d%d",&q,&r);
		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];
	printf("%d\n",j);
	return 0;
}