SRM 268 DIV1 Hard CommentNest

問題 Editorial

問題

複数行コメントを削除したい。それはネストできる。
複数行コメント"MLC"は以下の構文で定義される:

MLC := "/*" <Nester> "*/"
Nester := ("/*"も"*/"も含まない文字列) | <Nester> <MLC> <Nester>

プログラムlinesがvectorで与えられる。これは各行を表していて、文字列の一番最後にも改行があるものとする。
ここから取り除ける限り複数行コメントを取り除くことを繰り返す。
取り除ける複数行コメントが複数ある場合には、一番最初に始まるものを削除する。一番最初に始まるものが複数ある場合、その中で一番長いものを削除する。
この操作をした時、残った文字列の文字数を求めよ。ただし改行も文字数に数えるとする

解答

構文をきちんと実装する。
この構文の曖昧さは"/*/"と"*/*"の文字列をNesterにマッチさせてみてよく考えてみるとわかる。
その分岐を考えて(位置 * ネストの深さ)でDPをすれば良い。
「できるだけ左側」と「最大長さ」のために、左から見てって"/*"が現れたらそこからの最大長さをDPで求めてスキップ、という感じで

コメント

本番でのPetrさんにタイム勝った！今回は割と普通に書けてよかった。そんなに複雑でもないし。
しっかり問題文の構文通りに実装することがポイントだよね。きちんと問題通りに！

コード

#include <string>
#include <vector>
#include <cstring>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
using namespace std;
int dp[1111][1111];
struct CommentNest {
	string s; int n;
	int rec(int i, int d) {
		if(dp[i][d] != -1) return dp[i][d];
		int r = -INF;
		if(d == 0) {
			r = 0;
		}else if(i == n) {

		}else {
			//'/*'があってもNesterの左の部分が'/'だけならおｋ(つまりそのあとNesterは終了する)
			if(i+2 < n && s[i] == '/' && s[i+1] == '*' && s[i+2] == '/')
				r = max(r, 3+rec(i+3, d-1));
			//'*/'があってもNesterの左の部分が'*'だけならおｋ(つまりそのあとMLCになる)
			if(i+2 < n && s[i] == '*' && s[i+1] == '/' && s[i+2] == '*')
				r = max(r, 3+rec(i+3, d+1));

			if(i+1 < n && s[i] == '/' && s[i+1] == '*') {
				r = max(r, 2+rec(i+2, d+1));
			}else if(i+1 < n && s[i] == '*' && s[i+1] == '/') {
				r = max(r, 2+rec(i+2, d-1));
			}else {
				r = max(r, 1+rec(i+1, d));
			}
		}
		if(r <= -INF+10) r = -INF;
		return dp[i][d] = r;
	}
	int whatsLeft(vector <string> lines) {
		rep(i, lines.size()) s += lines[i], s += '@';
		n = s.size();
		int r = 0;
		mset(dp, -1);
		rep(i, n) {
			if(i+1 < n && s[i] == '/' && s[i+1] == '*') {
				int x = rec(i+2, 1);
				if(x != -INF) i += 2 + x, i --;
				else r ++;
			}else {
				r ++;
			}
		}
		return r;
	}
};