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

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

More than 5 years have passed since last update.

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

評価

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

  // 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. ijも0〜num_itemsまでループすると、(m,n)と(n,m)のようにだぶってしまう
2. 2つとも半額を超えると絶対にキャンペーン価格を超える
3. items[i]だけでキャンペーンの価格を超えるようなものはどんなitems[j]でもダメ

(1)より、ji+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
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  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
ユーザーは見つかりませんでした