SRM 354 300pt: DateFormat

keyword

greedy　C++

問題概要

月/日または日/月の形で日付が複数与えられる。昇順になるような辞書順最低の日付を月/日のフォーマットで出力する問題。

解法

辞書順最小、と聞いたらまず貪欲を考える。前のものより大きく、有効な日付であるかどうかが前提条件。この中で小さいものを採用すればよい。

感想

解法はすぐに見えたけどコーディングにやたら時間がかかってしまった。繰り返しの表現がたくさんあってあまりよろしくない。

#include <string>
#include <vector>
#include <sstream>
#include <cstdio>
using namespace std;

struct DateFormat {

	string fromEuropeanToUs(vector <string> dateList) {
		string s;
		for(int i=0; i<dateList.size(); i++){
			s += dateList[i];
		}
		for(int i=0; i<s.length(); i++)if(s[i] == '/'){
			s[i] = ' ';
		}
		stringstream ss(s.c_str());
		vector<pair<int,int> > ds;
		int a, b;
		while(ss >> a >> b){
			ds.push_back( make_pair(a,b) );
		}

		pair<int,int> prev = make_pair(0,0);
		string ret;

		for(int i=0; i<ds.size(); i++){
			pair<int,int> a = ds[i], b = make_pair(a.second, a.first);
			if(is_valid(a) && is_valid(b)){
				if(prev < min(a,b)){
					ret += to_date(min(a,b));
					prev = min(a,b);
				}
				else if(prev < max(a,b)){
					ret += to_date(max(a,b));
					prev = max(a,b);
				}
				else{
					return "";
				}
			}
			else if(is_valid(a)){
				if(prev < a){
					ret += to_date(a);
					prev = a;
				}
				else{
					return "";
				}
			}
			else if(is_valid(b)){
				if(prev < b){
					ret += to_date(b);
					prev = b;
				}
				else{
					return "";
				}
			}
			else{
				return "";
			}
			if(i < ds.size() - 1){
				ret += " ";
			}
		}

		return ret;
	}

	bool is_valid(pair<int,int> p){
		return p.first <= 12;
	}

	string to_date(pair<int,int> p){
		int a = p.first, b = p.second;
		stringstream ss;
		if(a < 10) ss << "0";
		ss << a << "/";
		if(b < 10) ss << "0";
		ss << b;
		return ss.str();
	}

};