絶対に許されない

Main.java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * 許せ
 * 
 * 1版:適当探索
 * 2版:IO改善
 * 3版:最悪でない入力に対する探索打ち切り改善
 * 4版:変則バケットソート
 * 5版:境界値バグ修正と命令単位の気休めチューニング(意味無し)
 * 6版:にぶたんを各日最初だけにして、残りは変則しゃくとりにする
 * 
 * @author dolpen
 */
public class Main {

    static final int max_m = 1000000;

    static int items;
    static int duration;

    static int[] itemPrices;
    static int[] campaignPrice;

    public static void main(String args[]) throws Exception {
        input();
        calc();
    }

    /**
     * 入力処理
     */
    static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        boolean[] pbucket = new boolean[max_m+1];
        boolean[] obucket = new boolean[max_m+1];
        String[] h = br.readLine().split(" ");
        items = Integer.parseInt(h[0]);
        duration = Integer.parseInt(h[1]);
        campaignPrice = new int[duration];
        int cnt = 0;
        for (int i = 0; i < items; i++) {
            int p = Integer.parseInt(br.readLine());
            if (!(pbucket[p]&obucket[p]))cnt++;
            obucket[p] = pbucket[p];
            pbucket[p] = true;
        }
        itemPrices = new int[cnt];
        items = cnt;
        int j = 0;
        for (int i = 0; i <= max_m; i++) {
            if (pbucket[i]) itemPrices[j++] = i;
            if (obucket[i]) itemPrices[j++] = i;
        }
        for (int i = 0; i < duration; i++)
            campaignPrice[i] = Integer.parseInt(br.readLine());
        br.close();
    }

    /**
     * 計算メイン
     */
    static void calc() {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < duration; i++) {
            int cp = campaignPrice[i];
            int left = 0;
            int right = getIndex(0, items - 1, cp);// 初期探索範囲 items-1でも特に問題無し
            int max = 0;
            while(left<right){
                int p = itemPrices[left] + itemPrices[right];
                if(p>cp){ // 右端を削る
                    right--;
                } else if(p<cp) { // 左端を削る
                    max = Math.max(max,p);
                    left++;
                } else {
                    max = cp;
                    break;
                }
            }
            sb.append(max).append('\n');
        }
        System.out.println(sb.toString());
    }

    /**
     * xを超えない最大のitemPriceのインデックスを得る。なければ-1
     * itemPriceは増加列にしておくこと
     *
     * @param left  左側(常にxを超えない)
     * @param right 右側(常にxを超える)
     * @param x     設定値
     * @return インデックス
     */
    static int getIndex(int left, int right, int x) {
        // 探索範囲全ては
        if (left>right || itemPrices[left] > x) return -1;
        if (itemPrices[right] <= x) return right;
        while (right - left > 1) { // 差が1になったときleftは最大の(<=x)
            int temp = (left + right) / 2;
            if (itemPrices[temp] > x) {
                right = temp;
            } else {
                left = temp;
            }
        }
        return left;
    }
}

野田さんに許されたい人生だった.md

許されたかった

なにがあったのか

https://paiza.jp/poh/ec-campaign/

なにをやったのか

あなたとJava

まずは適当に書く

• まずはScannerでいいや
• 入力、普通にソートした方がいいよね
• 例えば
  [19, 27, 35, 43, 51, 68, 76, 84, 92, 100]
  みたいに商品があって、目標金額が80のとき、探索範囲は
  [19, 27, 35, 43, 51, 68, 76]
  でいいので、それ以降は探索範囲に入れないようにする
• ある目標価格、仮に80に対して、左側から19に最適の商品、27に最適の商品...と探していくとき、
  27に対応する51、51に対する27は同じ組だから、対応する商品は選んだ1個目の商品の右側から探せば無駄無し。
  51に対応する商品を探すときは [68, 76] // 27との組み合わせは発見済み
  でよい。
• 相対的に右側の商品が安くなることは無いので、
  目標価格80について、27に対する最適の組み合わせ商品は、19に対する最適の組み合わせ商品より右側にはない。よって
  [19, 27, 35, 43, 51, 68, 76]
  の19に対応する最適の組み合わせである68を
  [27, 35, 43, 51, 68, 76]
  から探したら、27に対する最適の組み合わせは
  [35, 43, 51, 68] // 27より右側だが、さっきみつけた68より右にはない！
• これを繰り返して、探索範囲がなくなってしまったり、探索範囲の中に合計が目標価格を下回る組み合わせ候補がなかったら、既に見つかった組み合わせ価格の合計の最高値が答えである。
• 組み合わせの探索は二分探索でやろう。

みたいなことを考えて、適当に書いた。タイムは[0.13, 0.23, 1.40]

さよならScanner

BufferedReader最高。あと出力も一回にまとめる。 タイムは[0.8, 0.12, 0.76]

終了条件

目標金額ぴったりで探索打ち切るようにした。タイムは[0.8, 0.9, 0.18]

ソート遅い

最大金額が1Mなので、メモリをいっぱい使ってバケットソートした。
このとき、同じ価格の商品が2個以上連続しないようにした。
タイムは[0.9, 0.9, 0.15] ケース1ではサイズ小さすぎて逆効果

その後

二分探索を明らかに目標金額より大きい商品を探索範囲から抜くときだけにし、
探索範囲をシーケンシャルに走査することにした（必要以上の重複は取り除いたのだから）
タイム変わらずもうだめぽ。

〜

隣の席で同僚が言語最速出してた

自己ベスト : http://paiza.jp/poh/ec-campaign/result/f5b702f1e4b2644e7e9a3d0b3d8e36ad