Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2215-9a7dacd6
この記事にトラックバックする(FC2ブログユーザー)

January 2012 Cook-Off 4問目 - Makx Sum (この記事を編集する[管理者用])

Source

codechef January 2012 Cook-Off 4問目
Problem Statement

問題概要

要素数N (10000以下) の数列が与えられる.各要素は-10000以上10000以下.
その数列の連続する部分列 (N*(N+1)/2個ある) のうち,和が大きい方からk1番目,k2番目,k3番目の和を求める問題.
k1, k2, k3は1以上2012以下.(k1 ≤ k2 ≤ k3)

解法

a番目の要素から,b番目の要素の部分列を[a, b]と書くことにする.
全てのkに対して,k番目で終わる部分列[i, k]のうち,和が最大のものをpriority_queueに入れておく.
これは,sum[k] = [0, k]の和を全部計算しておき,各kに対し,sum[i]が最小となるk未満のiを見つければ良いので,最初から1回なぞることでO(N)でできる.
後は,k3回だけ,priority_queueから取り出しつつ,[i, k]を取り出したら,k番目で終わる部分列のうち,和が次に大きいものをpriority_queueに突っ込むというのを繰り返す.
これは,sum[k]をソートしておいて,次のやつを愚直に探した.(コード参照)
和が等しくなるものをちゃんともれなく突っ込めるようにソートするときなどにちゃんと工夫する.
合計で,最悪ケースでO(N*k3),平均的(希望的)にはO(N log N + k3 log N)程度.
次に突っ込むのを探すのを工夫すれば最悪ケースでもO(N log N + k3 (log N)^2)程度にはできると思うけど,そこまでやる必要はないと思う.

C++のスパゲッティなコード
#include<cstdio>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<algorithm>
#include<string>
#include<utility>
using namespace std;

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

int main(){
  int i,j,k,l,m,n;
  int k1, k2, k3;
  int in[10001], sum[10001];
  pair<int,int> sums[10001]; int rev[10001];
  priority_queue< pair<int,pair<int,int> > > q;
  int size;

  scanf("%d",&size);
  while(size--){
    scanf("%d%d%d%d",&n,&k1,&k2,&k3);
    k1--; k2--; k3--;
    rep(i,n) scanf("%d",in+i);
    sum[0] = 0;
    rep(i,n) sum[i+1] = sum[i] + in[i];

    rep(i,n+1) sums[i] = make_pair(sum[i], i);
    sort(sums, sums+n+1);
    rep(i,n+1) rev[sums[i].second] = i;

    k = 0;
    while(q.size()) q.pop();
    m = 0;
    REP(i,1,n+1){
      q.push( make_pair(sum[i]-sum[m], make_pair(i,m)) );
      if(sum[m] > sum[i]) m=i;
    }

    for(;;){
      i = q.top().second.first;
      j = q.top().second.second;
      q.pop();
      if(k==k1) printf("%d ",sum[i]-sum[j]);
      if(k==k2) printf("%d ",sum[i]-sum[j]);
      if(k==k3){ printf("%d\n",sum[i]-sum[j]); break; }
      k++;

      m = rev[j];
      for(;;){
        m++;
        if(m >= n+1) break;
        j = sums[m].second;
        if(i <= j) continue;
        q.push( make_pair(sum[i]-sum[j], make_pair(i,j)) );
        break;
      }
    }
  }

  return 0;
}

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2215-9a7dacd6
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。