yukicoder : No.1740 Alone 'a'

割と簡単目の回。
https://yukicoder.me/problems/no/1740

問題

アルファベット小文字で構成された文字列Sが与えられる。
以下を満たす文字列Tは何通りあるか。

• |S|=|T|
• T＜S
• Tはaを1文字だけ含む

解法

dp(n,a,b) := Tの先頭n文字目まで決めたとき、a: ’a'を含む数、b:T＜Sであることが確定したかどうか という状態を満たす組み合わせ数
を順に求めよう。n文字目まで決めたとき、n+1文字目を'a'～'z'まで当てはめてみればよい。
dp(0,false,false)=1から初めてdp(|S|,true,true)が解。

int N;
string S;
ll dp[202020][2][2];
const ll mo=998244353;
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>S;
	dp[0][0][0]=1;
	FOR(i,N) {
		int c=S[i];
		FOR(x,26) {
			if(x==0) {
				if(c=='a') {
					(dp[i+1][0][1]+=dp[i][0][0])%=mo;
					(dp[i+1][1][1]+=dp[i][1][0])%=mo;
				}
				else {
					(dp[i+1][1][1]+=dp[i][0][0])%=mo;
					(dp[i+1][1][1]+=dp[i][1][0])%=mo;
				}
			}
			else {
				if(x<c-'a') {
					(dp[i+1][1][0]+=dp[i][0][0])%=mo;
					(dp[i+1][1][1]+=dp[i][0][1])%=mo;
				}
				else if(x==c-'a') {
					(dp[i+1][0][0]+=dp[i][0][0])%=mo;
					(dp[i+1][0][1]+=dp[i][0][1])%=mo;
				}
				(dp[i+1][1][0]+=dp[i][1][0])%=mo;
				(dp[i+1][1][1]+=dp[i][1][1])%=mo;
			}
		}
	}
	
	cout<<dp[N][1][1]<<endl;
}

まとめ

★2.5でもいい気がする。