動的計画法の練習
天才火消しエンジニア霧島「もし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でもやってみるか?