動的計画法の練習

天才火消しエンジニア霧島「もしPMおじさんが丸投げを覚えたら」 | paizaオンラインハッカソン(POH)https://paiza.jp/poh/kirishima )に挑戦してみた。言語はPerlで。
ぱっと考えてやったので、効率は度外視。
「計算があわねーなー」と思っていたら、各下請け業者への支払額を、単価だと思ってそれに人員数をかけてしまっていたこと。
そこを修正したりして、結構時間かかった。

use strict;
use warnings;

my @input = <STDIN>;

my $m = shift @input;
chomp $m;
$m += 0;

my $n = shift @input;
chomp $n;
$n += 0;

my @qr = ();
foreach my $line ( @input ) {
	chomp $line;
	my ( $q, $r ) = split /\D+/, $line;
	$q += 0;
	$r += 0;
	push @qr, [ $q, $r ];
}
my $max = scalar @qr;
-- $max;

my @menber = ();
my @answer = ();

sub calc_menber {
	my $men = shift;
	my $q = 0;
	map { $q += $_->[0] } @{$men};
	return $q;
}

sub calc_cost {
	my $men = shift;
	my $q = 0;
	map { $q += $_->[1] } @{$men};
	return $q;
}

sub f {
	my $campany_number = shift;
	push @menber, $qr[$campany_number];

	# calc
	my $q = &calc_menber(\@menber);


	if ( $q < $m ) { # まだ人数に達していない。
		if ( $campany_number < $max ) {
			foreach my $count ( ( $campany_number+1 ).. $max ) {
				&f( $count );
			}
		}
	} else { # 人数に達した。
		push @answer, [@menber];
	}
	pop @menber;
}

map { &f($_) } ( 0..$max );

my $min = &calc_cost($answer[0]);
my $min_party = $answer[0];
foreach my $party ( @answer ) {
	my $mm = &calc_cost($party);
	if ( $min > $mm ) {
		$min = $mm;
		$min_party = $party;
	}
}

# 出力部
print $min;
print "\n";

んで、結果。
http://paiza.jp/poh/kirishima/result/6c57d2c964596181abb295c2c2cb3911
CASE6はタイムアウトだった模様。効率化せんとあかんなー。Rubyでもやってみるか?