Hatena::Grouptopcoder

SRM diary(Sigmar)

SigmarのTopcoder SRM参加記録など雑記です。
社会人になってから競技プログラミングを始めました。どこまで行けるか分かりませんが合間を見つけてアルゴリズムの勉強をしています。

2011-09-14SRM518 Div1

SRM518 Div1 250 LargestSubsequence

| 01:22 | SRM518 Div1 250 LargestSubsequence - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM518 Div1 250 LargestSubsequence - SRM diary(Sigmar) SRM518 Div1 250 LargestSubsequence - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

やるだけ

のはずがないと思って余計なことを考えすぎて遅くなった

ダメダメ。。


ソースコード

class LargestSubsequence {
public:
	string getLargest(string s) {
		string res;
		int n=s.size();

		int idx=0;
		while(idx<n) {
			int maxc=idx;
			for(int i=idx; i<n; i++) {
				if(s[i]>s[maxc]) maxc=i;
			}
			res.push_back(s[maxc]);
			idx=maxc+1;
		}
		return res;
	}
};

SRM518 Div1 500 ConvexSequence

| 01:22 | SRM518 Div1 500 ConvexSequence - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM518 Div1 500 ConvexSequence - SRM diary(Sigmar) SRM518 Div1 500 ConvexSequence - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

全然分からん

・・・とりあえずconvex sequenceというのは最小値を中心として、そこから離れるにつれて値が大きくなるようだ

そしてその傾きは前と同じか大きくないといけない

・・・

・・・

最小値から左右に向かって、Greedyに傾きを増やしていけば良いのでは?

これは2分探索で最大の傾きを判定可能なので、できそう

あとは最小値は入力配列の最小値でいいのかというところだが・・・

入力配列の最小値をマイナスしても何もいいことがないので問題なさそう

計算量も問題ない

書いた

通った

提出


チャレンジで部屋内のコード見たらほとんどがナイーブなGreedy解法。何じゃこりゃ。

これは絶対TLEWAだな。と思ったら普通に皆通っていた。writer想定外解法だったようで・・

自分もそんな方法でいけるとは全く思いもしませんでしたが。


ソースコード

本番では最小値の位置を無駄にイテレーションしていたので修正しました

(特に修正しなくても問題はないですが・・)


(9/15追記)

よく考えると2分探索しなくてもO(n)で最大傾きを算出可能なので、O(n^2)まで落とせますね。また、両端の値はマイナスする必要がないようなので、最小値から左右に伸ばす以外に、左端から(マイナスの傾きを含め)段々傾きを大きくしていくような書き方も可能そうです。

class ConvexSequence {
public:
	ll calc(vector <int> a) {
		int n=a.size();

		ll b[52];
		ll prev=0;
		b[0]=a[0];
		for(int i=0; i<n-1; i++) {
			//二分探索でprev以上の最大の傾きを探索
			ll lo=prev, hi=10000000000LL, mid;
			while(hi-lo>1) {
				mid=(hi+lo)/2;
				bool ok=true;
				for(int j=i+1; j<n; j++) {
					b[j]=b[j-1]+mid;
					if(b[j]>a[j]) ok=false;
				}
				if(ok) lo=mid;
				else hi=mid;
			}
			b[i+1]=b[i]+lo;
			prev=lo;
		}

		ll res=0;
		for(int i=1; i<n; i++) res+=a[i]-b[i];
		return res;
	}

	long long getMinimum(vector <int> a) {
		long long res;

		int mini=min_element(a.begin(), a.end())-a.begin();
		vector <int> a1(a.begin()+mini, a.end());
		vector <int> a2(a.begin(), a.begin()+mini+1);
		reverse(a2.begin(), a2.end());
		ll r1=calc(a1);
		ll r2=calc(a2);
		res=r1+r2;

		return res;
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20110914