公式の注によると、 「※ 実際のプロジェクトではこの様には行きませんので、人員を増やす場合は慎重に検討する事をお勧めいたします。」 とのことです^^;;;
| 問題 | 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 |
火村氏の答案？を愚直に拡張してもO(2**n)なので間に合わないのは明らか。
私はナップザック問題の変形に持ち込みました。
なお、C#/VB/JavaはIOゲーを行いました。
R/BashはPOH1が解けたらやる予定(手元では通っているのだけど。)
↑に書いてあるBashは圧縮したRuby版を呼んでいるだけです。
[141203追記] Python3のtime limitが3秒っていうのはいくらなんでも短すぎると思います。
C/C++/ObjC
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
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#
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#と違うのね。。
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
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);
});
})();