【Perl】paizaオンラインハッカソンVol.1にてきとうに挑戦した結果

paizaオンラインハッカソンVol.1「新人女子プログラマの書いたコードを直すだけの簡単なお仕事です！」ってのがあったのでてきとうにPerlをかいてみた。

大体最初にぱっと思いつく感じのアルゴリズムの組み合わせ数を減らす程度の最適化を施したかんじのやつを提出。

my @price_for_item;
my @price_in_period;

my ($item_num, $period_num) = map {chomp;$_} split / /, <STDIN>;
for my $i (0 .. $item_num - 1){
	push @price_for_item, map {chomp;$_} scalar <STDIN>;
}
@price_for_item = sort {$a <=> $b} @price_for_item;
for my $p (0 .. $period_num - 1){
	push @price_in_period, map {chomp;$_} scalar <STDIN>;
}

my $str = '';

for my $p (0 .. $#price_in_period){
	my $max_price = $price_in_period[$p];
	my @price_for_item_use;
	my $is_last;
	for my $i (0 .. $#price_for_item){
		if($price_for_item[$i] > $max_price){
			@price_for_item_use = @price_for_item[0 .. $i - 1];
			$is_last = 1;
			last;
		}
	}
	if(! $is_last){
		@price_for_item_use = @price_for_item;
	}
	if(! @price_for_item_use){
		$str .= "0\n";
		next;
	}
	my $max_price_can = 0;
	my $minimum_index = 0;
	for my $i (reverse 0 .. $#price_for_item_use){
		my $base = $price_for_item_use[$i];
		my $max_price_append = $max_price - $base;
		my $max_price_can_append = $max_price_can - $base;
		for my $j (grep {$i != $_} $minimum_index .. $#price_for_item_use){
			my $append = $price_for_item_use[$j];
			if($max_price_can_append > $append){
				$minimum_index = $j;
				next;
			}
			if($max_price_append < $append){last}
			$max_price_can = $base + $append;
		}
	}
	$str .= $max_price_can . "\n";
}

print $str;

結果、ケース1で0.5秒くらい、その他はタイムアップという結果。
まあしょうがないね。

-- 追記

その後深く考えずに以下のように入力を一括で読むようにいじくったり、はてまた全部ourにしてみたりしたけどタイムは全く変わらなかったので、アルゴリズムの限界がこのタイムらしい。

our @price_for_item;
our @price_in_period;

local $/ = undef;
our $stdin = <STDIN>;

$stdin =~ s/^(\d+) (\d+)\n//;
our ($item_num, $period_num) = ($1, $2);
our @prices = $stdin =~ m/(\d+)[\r\n]*/g;
@price_in_period = @prices[$item_num .. $item_num + $period_num - 1];
@price_for_item = sort {$a <=> $b} @prices[0 .. $item_num - 1];

our $str = '';

for our $p (0 .. $#price_in_period){
	our $max_price = $price_in_period[$p];
	our @price_for_item_use = ();
	our $is_last = 0;
	for our $i (0 .. $#price_for_item){
		if($price_for_item[$i] > $max_price){
			@price_for_item_use = @price_for_item[0 .. $i - 1];
			$is_last = 1;
			last;
		}
	}
	if(! $is_last){
		@price_for_item_use = @price_for_item;
	}
	if(! @price_for_item_use){
		$str .= "0\n";
		next;
	}
	our $max_price_can = 0;
	our $minimum_index = 0;
	for our $i (reverse 0 .. $#price_for_item_use){
		our $base = $price_for_item_use[$i];
		our $max_price_append = $max_price - $base;
		our $max_price_can_append = $max_price_can - $base;
		for our $j (grep {$i != $_} $minimum_index .. $#price_for_item_use){
			our $append = $price_for_item_use[$j];
			if($max_price_can_append > $append){
				$minimum_index = $j;
				next;
			}
			if($max_price_append < $append){last}
			$max_price_can = $base + $append;
		}
	}
	$str .= $max_price_can . "\n";
}

print $str;