SRM 518 250pt: LargestSubsequence

問題概要

長さL(<50)の文字列が与えられる。部分文字列の中で辞書順最大のものをもとめよ。

考えたこと

• 問題文短くて良い…。
• とりあえず辞書順と言えばgreedy。珍しく最小ではないけど考え方は変わらない。
• とにかくでかいやつを選ぶ。で、後は探索範囲をそれより後方に狭めていく。
• max_elementは確か最大値複数のときは一番前方のイテレータを返すことが保証されていたはずなので、それで。
• stringのまま扱うのが何かいやだったのでvectorで書いた。
• 無事通ってた。正答率は99%を越えていたらしい。

本番で通ったコード

計算量O(L^2)。

#include <algorithm>
#include <string>
#include <vector>
using namespace std;

struct LargestSubsequence {

	string getLargest(string s_) {
		string ret;
		vector<char> s(s_.begin(), s_.end());
		while(!s.empty()){
			vector<char>::iterator itr = max_element(s.begin(), s.end());
			ret += *itr;
			vector<char> tmp;
			for(itr++ ; itr != s.end(); itr++){
				tmp.push_back(*itr);
			}
			s = tmp;
		}
		return ret;
	}

};

このコードはなんかtmpを作っているあたりが気にくわないので、以下のようにしたい。

	string getLargest(string s_) {
		string ret;
		vector<char> s(s_.begin(), s_.end());

		vector<char>::iterator itr = max_element(s.begin(), s.end());
		ret += *itr;
		while(++itr != s.end()){
			ret += *(itr = max_element(itr, s.end()));
		}

		return ret;
	}

計算量を落とす

後ろからgreedyに選んでいく。
計算量はO(L)になる。str = ch + str;みたいな操作はしちゃダメ。

#include <algorithm>
#include <string>
#include <vector>
using namespace std;

struct LargestSubsequence {

	string getLargest(string s) {
		vector<char> ret;

		//後ろからgreedyに選ぶ
		for(int i=(int)s.length() - 1; i >= 0; i--){
			if(ret.empty() || ret.back() <= s[i]){
				ret.push_back(s[i]);
			}
		}

		reverse(ret.begin(), ret.end());
		return string(ret.begin(), ret.end());
	}

};