新人女子の書いたコードを直すやつ - frostar@wiki

問題はここにあります。
要約すると

N D
p_1
p_2
...
p_N
m_1
m_2
...
m_D

という書式の入力が与えられ、それぞれのm_iに対して和がm_iを超えない最大の値になるようにp_jから異なる2個を選択するというものです。

とりあえず私の最終コードは↓みたいな感じ。言語はJavaです。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class Main {
	private static List<Integer> goods;
	public static void main(String args[]) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String line = br.readLine();
		String[] strs = line.split(" ");
		int g_max = Integer.valueOf(strs[0]);
		int d_max = Integer.valueOf(strs[1]);
		goods = new ArrayList<Integer>(g_max);
		int[] targets = new int[d_max];
 
		for(int i=0;i<g_max;i++){
			goods.add(Integer.parseInt(br.readLine()));
		}
		Collections.sort(goods);
 
		for(int i=0;i<d_max;i++){
			System.out.println(calc(Integer.parseInt(br.readLine())));
		}
	}
	static int calc(int target){
		if(target/2<goods.get(0))return 0;
		int end = goods.size()-1;
		if(target/2>=goods.get(end))return goods.get(end)+goods.get(end-1);
		int answer=0;
		int start=0;
 
		while(start<end){
			int s=0;
			while(goods.get(end)+goods.get(start)>target)end--;
			s = goods.get(end)+goods.get(start);
			if(s==target){
				answer = s;
				break;
			}
			if(answer<s)answer = s;
			start++;
		}
		return answer;
	}
}
 

とりあえずmainではそれぞれの値を取得。
与えられたgoods(p_j)をソートしてから、calcメソッドにそれぞれの目標値を渡して計算を行っています。
calcメソッドでは次のようなものは計算を行わなくても解がわかるのでそれを先に判別します。

• 一番小さいgoodsの要素の値段が目標値の半分以上のとき:0(line.32)
• 一番大きいgoodsの要素の値段が目標値の半分以下のとき:一番大きいgoodsの要素+二番目に大きいgoodsの要素(line.34)

それ以外の場合はそれぞれの計算を行います。
startとendという2つのindexをそれぞれ0とgoodsの要素数-1で初期化します。
また、中間結果変数answerを0で初期化します。
startの要素とendの要素の和が目標値以下になるまでendをデクリメントしていきます(line.35)。
目標値以下になったら、その合計値を目標値と比較し、等しければその値を答えとして返します。
そうでなければ、変数answerと合計値を比較し、合計値のほうが大きければanswerの値を更新します。
その後、startをインクリメントして、同じ処理をstartとendの大小関係が入れ替わるか等しくなるまで続けます。

startとendはループ中で常にstart<endが成り立っており、goodsがソートされているために
goods[start]<goods[end]が成り立ちます。
また、goods[start]<goods[start+1]も成り立つので、
goods[start]+goods[end]が目標値より大きい場合、
goods[start+1]+goods[end]も必ず目標値より大きくなります。
そのため、goods[start]+goods[end]<目標値が満たされた場合、
次の探索はgoods[start+1]に加算して目標値よりも小さくなるのはgoods[end]よりも小さい要素となるので、
ひとつ前のendより大きい値を探索する必要がなくなり、計算量が削減されます。

このアルゴリズムだとだいたいテストケース1で0.09秒でした。
Java最速は0.06秒らしいのでもっと早い方法があると思います(それともインスタンス生成コストとかをもっと減らしてるのかしら？)。
一応タイムを縮める方法として、目標値以下となる値を見つけるのを二分探索にしたり、マルチスレッドにしてみたりもやってみたのですが、いまいち縮まらなかったですね。