新人女子の書いたコードを直すだけの簡単なお仕事した

paizaという所で開催されている新人女子プログラマの書いたコードを直すだけの簡単なお仕事です！ | paizaオンラインハッカソン（POH）をやってみた。

たくさんある商品の中から2つを選んで設定された合計金額を超えない範囲でなるべく近い金額にするという問題。
やることは

商品の価格を受け取る
目標とする合計金額を受け取る
商品の組み合わせの中から条件に近い値を探す
結果を出力

ソートしてから探す

組み合わせから値を探す方法は、価格をソートした後で、高い側と安い側から順に商品を選んで探すやり方を考えた。
価格の配列をp、商品の個数をN、目標金額をmとして、

j=0, k=N-1から開始
p[j] + p[k] > m ならkを減らす
p[j] + p[k] == m なら終了
p[j] + p[k] < m なら過去の最良値と比較し、良ければ更新
jを1つ増やして2から繰り返す

実際に動かしてみると、最初にkを減らす処理が多いので二分探索に変更。

二分探索

t=1, k=0とする
tがN以上になるまで、tを2倍にする計算を繰り返す
tを2で割る
k+tがN以上なら3に戻る
p[k+t] < m ならkにtを加える
t > 1 なら3に戻る

kの上位ビットから順に立てられるかどうか調べていく感じ。
ここまでやって0.18秒。

商品点数が多すぎる

商品点数を20万、価格と目標金額を10〜100万の範囲でランダムとして計算したとき、計算結果のjの値はあまり大きくならない。だいたい10以下で済む。目標金額と一致する組み合わせが早々に見つかって計算が打ち切られているということになる。
商品点数を半分にすればソートにかかる時間は半分以下になるし、商品点数を削っても計算後のjが大きくなるだけで目標金額＝合計金額となる別の組み合わせが見つかるので計算結果は変わらない…はず。
もちろん目標金額＝合計金額とならなかった場合のやりなおし処理は必要だけれども。

探索に時間がかかるようになった

商品点数を削って計算したら結果を維持したまま速くできた。
ソートは速くなるが、その後ソート済みの配列上でjとkを詰めていく処理に時間がかかるようになった。
こんな感じ。

商品点数	ソート	最良値の探索	二分探索
多い	遅い	速い	速い
少ない	速い	遅い	速い

jとkを詰める処理が意外と遅いので商品点数を削りすぎてもいけない。いくつが最適なんだろうか、わからない。

結果

#!/usr/bin/perl

use strict;

my @m;
my @p;
my @p_not_used;
my $ENOUGH_N = 40000;

my ($N, $D) = split(/ /, <STDIN>);
$N = int($N);
$D = int($D);

# read price
for(my $i=0; $i<$N; $i++){
	push @p, int(<STDIN>);
}
if(@p > $ENOUGH_N){
	@p_not_used = splice @p, $ENOUGH_N;
}

@p = sort { $a <=> $b } @p;

# read limit
for(my $i=0; $i<$D; $i++){
	push @m, int(<STDIN>);
}

# process each day
foreach my $m (@m){
	my $best = 0;

	my $j=0;
	my $k=0;

	# find upper limit
	my $t=1;
	$t *=2 while $t < @p;
	while($t > 1){
		$t /= 2;
		next if $k + $t >= @p;
		$k += $t if $p[$k+$t] + $p[0] <= $m;
	}

	# look for better result
	while($j < $k){
		if($p[$j] + $p[$k] > $m){
			$k--;
			next;
		}
		my $current = $p[$j] + $p[$k];
		if($best < $current){
			$best = $current;
			last if $best == $m;
		}
		$j++;
	}

	if($best != $m && @p_not_used > 0){
		# add unused items
		if(@p_not_used > $ENOUGH_N){
			push @p, splice @p_not_used, 0, $ENOUGH_N;
		}else{
			push @p, @p_not_used;
			@p_not_used = ();
		}

		@p = sort { $a <=> $b } @p;
		
		redo;
	}
	print "$best\n";
}

これで0.10秒
あとは最初の入力が遅い。