会津オンラインジャッジ:Maximum Sum Sequece

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
アバター
みけCAT
記事: 6247
登録日時: 9年前
住所: 千葉県
連絡を取る:

会津オンラインジャッジ:Maximum Sum Sequece

#1

投稿記事 by みけCAT » 9年前

問題は
http://rose.u-aizu.ac.jp/onlinejudge/Pr ... 22&lang=jp
です。
この問題に対し、以下のソースコードを書きました。

コード:

#include <stdio.h>

int main(void) {
	long long a[5000];
	long long ask[5000];
	int max;
	int i;
	int j;
	int k;
	int sign;
	long long saidaiti;
	long long now;
	while(1) {
		scanf("%d",&max);
		if(max==0)break;
		for(i=0;i<max;i++)scanf("%lld",&a[i]);
		for(i=0,j=-1,sign=0;i<max;i++) {
			if(a[i]*sign<=0 && a[i]!=0) {
				sign=(a[i]>0)?1:-1;
				j++;
				ask[j]=0;
			}
			ask[j]+=a[i];
		}
		for(i=0;i<=j;i++) {
			if(ask[i]>=0)break;
		}
		if(i>j) {
			saidaiti=a[0];
			for(i=1;i<max;i++) {
				if(a[i]>saidaiti)saidaiti=a[i];
			}
		} else {
			max=j+1;
			saidaiti=ask[0];
			for(i=1;i<=max;i++) {
				for(j=0;j<=max-i;j++) {
					now=0;
					for(k=j;k<j+i;k++)now+=ask[k];
					if(now>saidaiti)saidaiti=now;
				}
			}
		}
		printf("%d\n",saidaiti);
	}
	return 0;
}
Acceptedとはなったのですが、時間が00:50secもかかっています。
連続する符号が同じ数か0をまとめてから総当たりで調べるコードになっています。
やはり総当たりの部分が遅いのだと思いますが、どうしたら速くなるでしょうか?
よろしくお願いします。
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

box
記事: 1746
登録日時: 9年前

Re: 会津オンラインジャッジ:Maximum Sum Sequece

#2

投稿記事 by box » 9年前

それだけの時間がかかった理由がアルゴリズムに問題があるためなのか、
それともPCのスペックが低いためなのか、質問文からは判断できません。

これで、他にどういう情報を提示すればいいか、わかりましたね?

「どうしたら速くなるか」という問いに対する一つの答えは、
「スーパーコンピューターで実行する」です。
バグのないプログラムはない。
プログラムは思ったとおりには動かない。書いたとおりに動く。

アバター
五反田
記事: 21
登録日時: 9年前
住所: 千葉

Re: 会津オンラインジャッジ:Maximum Sum Sequece

#3

投稿記事 by 五反田 » 9年前

そのアルゴリズムだと入力の個数nに対してO(n^3)で(3重のforループがあるため最大でn^3に比例する時間がかかってしまいます)、ちょっと遅いので、アルゴリズムを変更するべきでしょう。

たとえば、入力に対して、それまでの入力の和を全て保持する配列Sを用意して、S_n=a_1+・・・+a_nとすれば、a_i~a_j(i<=j)までの和は
S_j-S_(i-1)で求められます。
その最大値を計算して出力するようにすれば、結構早くなるはずですよ。
(これは2重のforループでできるので、O(n^2)のオーダーになりますね。)

また、もっと早くしたければ、(AOJでは上のアルゴリズムで十分でしょうけれど)、O(n)のアルゴリズムも知られています。
よければ調べてみてください。

アバター
みけCAT
記事: 6247
登録日時: 9年前
住所: 千葉県
連絡を取る:

Re: 会津オンラインジャッジ:Maximum Sum Sequece

#4

投稿記事 by みけCAT » 9年前

box さんが書きました:「どうしたら速くなるか」という問いに対する一つの答えは、
「スーパーコンピューターで実行する」です。
最終的な実行環境は会津オンラインジャッジのサーバーに限られているので、
それでは意味がないと思います。
五反田 さんが書きました:たとえば、入力に対して、それまでの入力の和を全て保持する配列Sを用意して、S_n=a_1+・・・+a_nとすれば、a_i~a_j(i<=j)までの和は
S_j-S_(i-1)で求められます。
この方法で無事00:00secでAcceptされました。
思えば第9回日本情報オリンピック本選の問題1と同じ原理ですね。
(私は恥ずかしながらこの問題もできませんでした)
ありがとうございました。
とりあえず解決にさせていただきます。

コード:

#include <stdio.h>

int main(void) {
	long long a[5000];
	long long ask[5001];
	int max;
	int i;
	int j;
	int sign;
	long long saidaiti;
	long long now;
	while(1) {
		scanf("%d",&max);
		if(max==0)break;
		ask[0]=0;
		for(i=0;i<max;i++)scanf("%lld",&a[i]);
		for(i=0,j=0,sign=0;i<max;i++) {
			if(a[i]*sign<=0 && a[i]!=0) {
				sign=(a[i]>0)?1:-1;
				j++;
				ask[j]=0;
			}
			ask[j]+=a[i];
		}
		for(i=1;i<=j;i++) {
			if(ask[i]>=0)break;
		}
		if(i>j) {
			saidaiti=a[0];
			for(i=1;i<max;i++) {
				if(a[i]>saidaiti)saidaiti=a[i];
			}
		} else {
			max=j+1;
			saidaiti=ask[1];
			for(i=1;i<max;i++)ask[i]+=ask[i-1];
			for(i=1;i<=max;i++) {
				for(j=0;j<=max-i;j++) {
					now=ask[j+i]-ask[j];
					if(now>saidaiti)saidaiti=now;
				}
			}
		}
		printf("%lld\n",saidaiti);
	}
	return 0;
}
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

閉鎖

“C言語何でも質問掲示板” へ戻る