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

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

評価

コード

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

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

  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で解くやり方がしっかり理解できたので、結果オーライ。