典型DP。まじめにやるときは400点はとりたいところ。
public class LittleElephantAndRGB{ public long getNumber(String[]a,int b){ String c=""; for(int i=0;i<a.length;i++)c+=a[i]; int n=c.length(); int dp[][]=new int[n+1][b+1]; int dp2[][]=new int[n+1][b+1]; for(int i=0;i<n;i++){ if(c.charAt(i)=='G')dp[i+1][1]++; else dp[i+1][0]++; for(int j=0;j<b;j++){ if(c.charAt(i)=='G'){ dp[i+1][j+1]+=dp[i][j]; }else{ dp[i+1][0]+=dp[i][j]; } } } for(int i=n-1;i>=0;i--){ if(c.charAt(i)=='G')dp2[i][1]++; else dp2[i][0]++; for(int j=0;j<b;j++){ if(c.charAt(i)=='G'){ dp2[i][j+1]+=dp2[i+1][j]; }else{ dp2[i][0]+=dp2[i+1][j]; } } } for(int i=0;i<n;i++){ for(int j=1;j<b;j++){ dp[i][j]+=dp[i][j-1]; } } for(int i=1;i<n;i++){ for(int j=0;j<b;j++) dp[i][j]+=dp[i-1][j]; } long ret=0; for(int i=1;i<n;i++){ ret+=(long)(i+1)*i*(n-i)/2; } //System.out.println(ret); for(int i=1;i<n;i++){ for(int j=0;j<b;j++){ ret-=dp2[i][j]*dp[i][b-j-1]; } } return ret; } }