SRM 696 div2 easy Ropestring
問題概要
-と.を含んだ文字列sが与えられる。この文字列を並び替える。-の連続した部分をひもとして考える。ひもの長さが偶数で大きいものから左へ、つぎ、奇数のもので、大きいものをつなげていく。ひもとひもの間には.をつけなければならない。.が余れば、最後につける
解法
-の連続した部分の長さをすべて求め、それを偶数と奇数に分け降順にソートしておく。そのあとは、偶数からひもを作り、ひもとひもの間には.をつける。同様に奇数の長さのひもに対しても行う。最後に、与えられた文字列分を切り抜き、答えとしている。これをしないと、.を最後につけすぎてしまっている可能性がある実装をしているため。
ミス
サンプルから推測したから問題概要が怪しい。
コード
#include <iostream> #include <algorithm> #include <vector> #include <queue> #include <cstdio> #include <string> using namespace std; typedef long long ll; #define rep(i,n) for(int i=0;i<(n);i++) const int INF = 1e9; class Ropestring{ public: string makerope(string s){ vector<int> dashgu, dashki; int cntperiod = 0; int l = 0; rep(r, s.size()){ if(s[r] == '-'){ while(s[r] == '-'){ r++; } int len = r - l; if(len % 2 == 1) dashki.push_back(len); else dashgu.push_back(len); l = r + 1; }else{ l = r + 1; } } sort(dashki.begin(), dashki.end()); reverse(dashki.begin(), dashki.end()); sort(dashgu.begin(), dashgu.end()); reverse(dashgu.begin(), dashgu.end()); string ans = ""; rep(i, dashgu.size()){ rep(j, dashgu[i]) ans += '-'; ans += '.'; cntperiod++; } cout << ans << endl; rep(i, dashki.size()){ rep(j, dashki[i]) ans += '-'; ans += '.'; cntperiod++; } rep(i, s.size() - cntperiod){ ans += '.'; } string ret = ans.substr(0, s.size()); return ret; } };