2013年12月15日日曜日

Paizaのオンラインハッカソンに参加してみた

ちょっと前に話題になった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