SRM532 Div1 Easy - DengklekMakingChains

TopCoder SRM

コーナーケース系のやつ

問題

チェーンがn個あり、i番目はs[i]である
各チェーンは '0' 〜 '9' の数字と '.' のみからなる3文字の文字列である
このチェーンを任意の順番で1列に繋ぎ、数字のみからなる連続な部分列を取り出し、数字の和をスコアとする
スコアの最大値を求めよ

1 <= n <= 50

解法

3文字とも数字のチェーンは全部ひとまとめにしてしまっていい
これらの集合をcenとし、数字じゃない文字を含むチェーンの集合をtとする
cenの右端と左端それぞれに繋げるのはそれぞれたかだか1個のチェーンだけ
これをtから重複しないように選んで全探索する
やることはこれだけ

気をつけた点は
・ 重複禁止の2重ループだと集合tがサイズ1のとき困る
=> "..." というダミーを入れればcenの左/右の片方だけに付ける場合も試せる🤠
・ cenを含む部分列のスコアより、tに含まれるあるチェーン単体の部分列のスコアの方が大きくなり得る
=> 各チェーン単体のスコアでも答えを更新しておけば良い🤠

実装があんまスマートじゃないかな？

class DengklekMakingChains {
public:
	int maxBeauty(vector<string> s) {
		vector<string> t;
		int res = 0, cen = 0;
		each(i,s) {
			if (isdigit(i[0]) && isdigit(i[1]) && isdigit(i[2])) cen += i[0]-'0' + i[1]-'0' + i[2]-'0';
			else {
				t.push_back(i);
				if (isdigit(i[1])) {
					if (isdigit(i[0])) chmax(res, i[1]-'0' + i[0]-'0');
					else if (isdigit(i[2])) chmax(res, i[1]-'0' + i[2]-'0');
					else chmax(res, i[1]-'0');
				} else {
					if (isdigit(i[0])) chmax(res, i[0]-'0');
					else if (isdigit(i[2])) chmax(res, i[2]-'0');
				}
			}
		}
		chmax(res, cen);
		t.push_back("...");
		int m = t.size();
		rep(l,m) rep(r,m) if (l!=r) {
			int sum = cen;
			if (isdigit(t[l][2])) {
				sum += t[l][2]-'0';
				if (isdigit(t[l][1])) sum += t[l][1]-'0';
			}
			if (isdigit(t[r][0])) {
				sum += t[r][0]-'0';
				if (isdigit(t[r][1])) sum += t[r][1]-'0';
			}
			chmax(res, sum);
		}
		return res;
	}
};