新人女子の書いたコードを直したけど架空の新人女子だったことに気づいた

架空だったでござる... ケース3どうやったら0.07とかで解けるんだろう...

# 評価
http://paiza.jp/poh/ec-campaign/result/0ddaf07b7e149a707b2e154fda391fc2

# コード
```cpp
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>

typedef int price;
typedef std::vector<price> knapsack;
typedef std::vector<price>::const_iterator knapsack_itr;

price max_available_price(const knapsack &items, const price cap)
{
  // Check at least there are some combination in items
  if(items[0] > cap / 2) return 0;

  // Detect last index for search
  knapsack_itr itr_last = std::lower_bound(items.begin(), items.end(), cap);
  const int item_size = itr_last - items.begin();
  knapsack_itr itr_last2 = std::lower_bound(items.begin(), itr_last, cap/2);
  const int item_size2 = itr_last2 - items.begin();

  // Find max price
  price price_max = 0;
  for(int i = 0; i < item_size2; ++i) {
    // To avoid duplicate combination, 'j' starts i+1
    for(int j = i + 1; j < item_size; ++j) {
      const price price_proposed = items[i] + items[j];
      // Found optimal solution
      if(price_proposed == cap) return price_proposed;
      // There are no combination after these case
      else if(price_proposed > cap) break;
      // Update max price
      else if(price_proposed > price_max) price_max = price_proposed;
    }
  }
  return price_max;
}

int main()
{
  // Read number of items & campaign_days
  int num_items, num_campaign_days;
  scanf("%d %d", &num_items, &num_campaign_days);

  // Read items
  knapsack items(num_items);
  for(int i = 0; i < num_items; ++i) scanf("%d", &items[i]);
  std::sort(items.begin(), items.end());
  
  // Read campaign capacities & calculate it
  for(int i = 0; i < num_campaign_days; ++i) {
    price capacity;
    scanf("%d", &capacity);
    std::cout << max_available_price(items, capacity) << std::endl;
  }
  return 0;
}

```

# 思いついた高速化小ネタ
## 1. cin遅い
まさかI/Oが足を引っ張るとは。競技プログラミング界隈では有名なんでしょうか。

```cpp
  for(int i = 0; i < num_items; ++i) scanf("%d", &items[i]);
```
`scanf`を使ってます。

追記:
`std::ios::sync_with_stdio(false);`すると`std::cin`からでも遅くならないようです

## 2. アイテムを全部探索しない
ループ変数(i,  j)の組み合わせでペアを探してるんですが、どちらも0〜`num_items`まで見てません。
問題をよくよく考えてみると3つのことに気が付きます。
1. `i`も`j`も0〜`num_items`までループすると、(m,n)と(n,m)のようにだぶってしまう
2. 2つとも半額を超えると絶対にキャンペーン価格を超える
3. `items[i]`だけでキャンペーンの価格を超えるようなものはどんな`items[j]`でもダメ

(1)より、`j`は`i+1`から始めることにしています。
(2)より、`i`は0〜キャンペーンの半額値のものまでしかループしていません。
(3)より、`j`はキャンペーン価格までしかループしていません。

ソート済のコレクションで、最初にnを超える位置を知るには`lower_bound`が便利です。

```cpp
  knapsack_itr itr_last = std::lower_bound(items.begin(), items.end(), cap);
  const int item_size = itr_last - items.begin();
  knapsack_itr itr_last2 = std::lower_bound(items.begin(), itr_last, cap/2);
  const int item_size2 = itr_last2 - items.begin();
```
`item_size`はキャンペーンの価格を超える最初のインデックスです。
`item_size2`はキャンペーンの価格の半額を超える最初のインデックスです。

## 3.絶対に組み合わせが無いとわかってたらそもそも探索しない
「2つとも半額を超えると絶対にキャンペーン価格を超える」と先程述べました。
なので、最安値すら半額を超えていたら、絶対に組み合わせが存在しないことがわかります。

```cpp
  // Check at least there are some combination in items
  if(items[0] > cap / 2) return 0;
```

## 4.見切りをつける
`items`は読み込み終わった後にソートしています。
ソートされているので、`items[i]+items[j]`よりも`items[i]+items[j+1]`のほうが確実に高いです。
なので、途中でキャンペーン価格を超えたら以降の`j+1〜item_size`に見切りをつけています。

```cpp
      // There are no combination after these case
      else if(price_proposed > cap) break;
```

また、途中でキャンペーン価格と同じ価格の組み合わせを見つけたら、これ以上良い解はないので以降見切りをつけています。

```cpp
      // Found optimal solution
      if(price_proposed == cap) return price_proposed;
```

# 感想
地味に時間かけてしまったので、やはり競技プログラミング向いてないなぁとおもいました。
どうでもいいですが、最初はn個の組み合わせだと思ってナップサック問題を調べてました。
ナップサック問題をDPで解くやり方がしっかり理解できたので、結果オーライ。