Coder-Strike 2014 Round1 - E. E-mail Addresses

DよりEの方が簡単だった。
http://codeforces.com/contest/412/problem/E

問題

文字列Sが与えられる。
このうち、メールアドレスとして有効なsubstringは何通りあるか。

有効なメールアドレスは以下のような構成を取る。

1. 先頭はアルファベットで始まり、アルファベット・数字・アンダースコアで構成される
2. 続いて'@'が来る
3. 続いて数字またはアルファベットが1文字以上が来る
4. 続いて'.'が来る
5. 続いてアルファベットが1文字以上が来る

解法

上記の５段階の構成をそのままステートマシンとして考え、DPで数を数えていけばよい。

他の人は'@'と'.'の位置を列挙して前後のアルファベットを数え上げてる人が多かったけど、こっちの方が簡単だと思う。

string S;
ll dp[1000001][5];
ll ret=0;

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>S;
	FOR(i,S.size()) {
		if(S[i]>='a' && S[i]<='z') {
			dp[i+1][0]=1+dp[i][0];
			dp[i+1][2]=dp[i][1]+dp[i][2];
			dp[i+1][4]=dp[i][3]+dp[i][4];
			ret+=dp[i+1][4];
		}
		else if(S[i]>='0' && S[i]<='9') {
			dp[i+1][0]=dp[i][0];
			dp[i+1][2]=dp[i][1]+dp[i][2];
		}
		else if(S[i]=='_') dp[i+1][0]=dp[i][0];
		else if(S[i]=='@') dp[i+1][1]=dp[i][0];
		else if(S[i]=='.') dp[i+1][3]=dp[i][2];
	}
	
	cout << ret << endl;
}

まとめ

こっちはすんなり解けてよかった。