ちょっと前に話題になった
paizaのオンラインハッカソンに参加してみました。
とりあえず言語はjavaを選択。下記のような方針でコードを書きました。
1. 商品の金額データを昇順にソートする。
2. ソート済みのデータに対して先頭と後尾から挟み撃ちで検索をかけ、指定されたキャンペーン金額以下の最大値を検索する。
計算量は1がN(O*logN)で2がO(N)。なので全体としてはN(O*logN)になります。
2の探索はbinary searchを利用すればもう少し早くなりそうですが、どのみち1のソートでO(N*logN)かかるので、手を抜きました。
実際に書いたコードは次のようになります。
import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.InputStreamReader;
public class Main {
public static void quickSort(int[] arr, int left, int right){
if (left <= right) {
int p = arr[(left+right) / 2];
int l = left;
int r = right;
while(l <= r) {
while(arr[l] < p){ l++; }
while(arr[r] > p){ r--; }
if (l <= r) {
int tmp = arr[l];
arr[l] = arr[r];
arr[r] = tmp;
l++;
r--;
}
}
quickSort(arr, left, r);
quickSort(arr, l, right);
}
}
public static void main(String args[]){
try {
BufferedReader br =
new BufferedReader(new InputStreamReader(System.in));
String nd[] = br.readLine().split(" ");
int n = Integer.parseInt(nd[0]);
int d = Integer.parseInt(nd[1]);
int narr[] = new int[n];
int min = Integer.MAX_VALUE;
for(int i = 0; i < n; i++){
int a = Integer.parseInt(br.readLine());
if(a < min){
min = a;
}
narr[i] = a;
}
quickSort(narr,0,n-1);
for(int i = 0; i < d; i++){
int a = Integer.parseInt(br.readLine());
if(a <= min * 2){
System.out.println(0);
}else{
int start = 0;
int end = n -1;
int max = 0;
while(start < end){
int sum = narr[start] + narr[end];
if(sum <= a && sum > max) max = sum;
if(sum == a){
break;
}
if(sum > a){
end--;
}else{
start++;
}
}
System.out.println(max);
}
}
} catch (Exception e) {
e.printStackTrace();
System.err.println("Error:" + e.getMessage());
}
}
}
結果を見ると無事case3まで実行完了できているようでした。
Test case 1
通過
実行時間：0.08 秒
Test case 2
通過
実行時間：0.09 秒
Test case 3
通過
実行時間：0.22 秒
と、クリアしてしまったので、ここで満足しちゃいましたが、この先更に速度を挙げためのアイデアがいくつか考えられます。
1. 探索をbinary searchにする
2. 探索時に一度探索したデータをキャッシュ化して覚えておく。ただしキャンペーン日数が75しかないので、今回のデータセットではあまり効果が薄いかもしれません。
参考文献
1. 「クイックソートのサンプルコード」
http://homepage3.nifty.com/teranet/JavaAlgorithm/QuickSort.html
