paiza POH kirishima #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|

|現在20言語でAC済。|タイム|URL|
|:--|:--|:--|
|C/C++/ObjC|**0.01s**|https://paiza.jp/poh/kirishima/result/c5f560e296bff006698f37be61f20627<br>https://paiza.jp/poh/kirishima/result/fb5c70c23e15b54aa11c870e8536fad4<br>https://paiza.jp/poh/kirishima/result/f8fc37e624d3f687af5ffe3af203ba98|
|D|0.02s|http://paiza.jp/poh/kirishima/result/bdf1713dd2f66f081e6934b5f2595d2c|
|Rust|0.03s|https://paiza.jp/poh/kirishima/result/063587be|
|Go|0.04s|https://paiza.jp/poh/kirishima/result/761a921590d710127dace405194262b7|
|Swift|0.04s|https://paiza.jp/poh/kirishima/result/711ebcb4|
|C#|0.08s|https://paiza.jp/poh/kirishima/result/eefdc22ea02da3acc86fcb6017765c96|
|F#|0.08s|http://paiza.jp/poh/kirishima/result/22e2bc1efa8d840f619c28ba1f368016|
|VB|0.11s|https://paiza.jp/poh/kirishima/result/40442da71119862d95575f1c45f110b4|
|JavaScript|0.11s|https://paiza.jp/poh/kirishima/result/e7c743f2fbaf6738643e7fd2bdbadc0f|
|Java|0.13s|https://paiza.jp/poh/kirishima/result/bd0353b88eac0b69f0f49bc3a56e2d5d|
|Kotlin|0.15s|https://paiza.jp/poh/kirishima/result/3af0d880|
|CoffeeScript|0.19s|https://paiza.jp/poh/kirishima/result/7964708eb0040f9e1fdc8e969b8fa91b|
|Scala|0.37s|http://paiza.jp/poh/kirishima/result/44a5abe9398ae61ebfaa36123f9aac82|
|Bash|1.93s|https://paiza.jp/poh/kirishima/result/fbc4bac0d37a8a2ddb3875f35e90361a|
|Ruby|1.94s|https://paiza.jp/poh/kirishima/result/6a821620c8cd86cf226af5d7bfcb185f|
|PHP|2.30s|https://paiza.jp/poh/kirishima/result/64e527f2882647e32d16d9e5f2972d40|
|Python2/Python3|2.88s<br>TLE|https://paiza.jp/poh/kirishima/result/8074cd389533c0a959da587baed10d05<br>http://paiza.jp/poh/kirishima/result/5df894a6f213eb166e3d5c1effbd8551|
|Perl|3.40s|https://paiza.jp/poh/kirishima/result/0be744e32084cd646356128b71c7163e|

火村氏の答案？を愚直に拡張してもO(2**n)なので間に合わないのは明らか。
私はナップザック問題の変形に持ち込みました。
なお、C#/VB/JavaはIOゲーを行いました。
R/BashはPOH1が解けたらやる予定(手元では通っているのだけど。)

↑に書いてあるBashは圧縮したRuby版を呼んでいるだけです。

[141203追記] Python3のtime limitが3秒っていうのはいくらなんでも短すぎると思います。

C/C++/ObjC

```c:paizapohlite.c
#include <stdio.h>
int num[50],cost[50];
int bag[500000];

int main(){
	int M,N,q,r,total=0,i,j;
	scanf("%d%d",&M,&N);
	for(total=j=0;j<N;j++){
		scanf("%d%d",&q,&r);
		total+=q;
		num[j]=q,cost[j]=r;
	}
	//std::vector<int>bag(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;
}
```

Go

```go:paizapohlite.go
package main
import(
	"fmt"
	"os"
	"text/scanner"
	"strconv"
)

var sin scanner.Scanner
func scanint() int{
	sin.Scan()
	ret,_ := strconv.Atoi(sin.TokenText())
	return ret
}

func main(){
	sin.Init(os.Stdin)
	M:=scanint()
	N:=scanint()
	num:=make([]int,N)
	cost:=make([]int,N)
	total:=0

	for j:=0;j<N;j++ {
		q:=scanint();
		r:=scanint()
		total+=q
		num[j]=q
		cost[j]=r
	}
	bag:=make([]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]}}
	fmt.Println(j);
}
```

C#

```csharp:paizapohlite.cs
using System;
class PaizaPOH3{
	const 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;
	}
	static void Main(){
		Console.OpenStandardInput().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];
		Console.WriteLine(j);
	}
}
```

VB
配列の宣言がC#と違うのね。。

```vbnet:paizapohlite.vb
module PaizaPOH3
	dim SIZE as integer=9999999
	dim z(SIZE-1) as byte
	dim input_count as integer=0

	function myget() as integer
		dim r as integer
		while 48<=z(input_count) andalso z(input_count)<=57
			r=r*10+z(input_count)-48
			input_count+=1
		end while
		input_count+=1
		return r
	end function

	sub Main()
		Console.OpenStandardInput().Read(z,0,SIZE)
		dim M as integer=myget()
		dim N as integer=myget()
		dim num(N-1) as integer
		dim cost(N-1) as integer
		dim total as integer=0
		for j as integer=0 to N-1
			dim q as integer=myget()
			dim r as integer=myget()
			total+=q
			num(j)=q
			cost(j)=r
		next

		dim bag(total) as integer
		for i as integer=1 to total
			bag(i)=-1
		next
		for j as integer=0 to N-1
			for i as integer=total to num(j) step -1
				if bag(i-num(j))>=0 then
					if bag(i)<0 orelse bag(i)>bag(i-num(j))+cost(j) then
						bag(i)=bag(i-num(j))+cost(j)
					end if
				end if
			next
		next
		dim j as integer=-1
		for i as integer=M to total
			if j<0 orelse (bag(i)>=0 andalso j>bag(i))
				j=bag(i)
			end if
		next
		Console.WriteLine(j)
	end sub
end module
```

JavaScript

```js:paizapohlite.node.js
#!/usr/bin/node
(function(){
	var T=[];
	var stdin = process.openStdin();
	stdin.setEncoding('utf8');

	var input_fragment="";
	stdin.on('data', function(input) {
			var ref=(input_fragment+input).split("\n");
			input_fragment=ref.pop();
			for(var i=0;i<ref.length;i++){
				if(ref[i]=='')continue;
				T.push(ref[i]);
			}
	});

	stdin.on('end', function(z) {
		if(input_fragment){
			var ref=(input_fragment+"\n").split("\n");
			input_fragment=ref.pop();
			for(var i=0;i<ref.length;i++){
				if(ref[i]=='')continue;
				T.push(ref[i]);
			}
		}

		var M=Number(T[0]);
		var N=Number(T[1]);
		var num=Array(N);
		var cost=Array(N);
		var total=0;
		var i,j;
		for(total=j=0;j<N;j++){
			var arg=T[j+2].split(' ').map(Number);
			total+=arg[0];
			num[j]=arg[0];
			cost[j]=arg[1];
		}
		var bag=Array(total+1);
		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];
		console.log(j);
	});
})();
```