Help us understand the problem. What is going on with this article?

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

More than 5 years have passed since last update.

# 評価

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

# コード

```#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);

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が足を引っ張るとは。競技プログラミング界隈では有名なんでしょうか。

```  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`まで見てません。

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`が便利です。

```  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つとも半額を超えると絶対にキャンペーン価格を超える」と先程述べました。
なので、最安値すら半額を超えていたら、絶対に組み合わせが存在しないことがわかります。

```  // 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`に見切りをつけています。

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

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

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

# 感想

どうでもいいですが、最初はn個の組み合わせだと思ってナップサック問題を調べてました。
ナップサック問題をDPで解くやり方がしっかり理解できたので、結果オーライ。

Why not register and get more from Qiita?
1. We will deliver articles that match you
By following users and tags, you can catch up information on technical fields that you are interested in as a whole
2. you can read useful information later efficiently
By "stocking" the articles you like, you can search right away