読者です 読者をやめる 読者になる 読者になる

PKU 3726 Windy's ABC

こういう文字が3種類ある問題はコードが3倍になるので嫌いであるということを報告しておきます。
必要な配列のサイズが入力依存で形が変わって(A+B+C=500でA*B*C必要)すべてを1回の宣言で網羅しようとするとMLEするので今回はJavaで。

import java.util.*;
class Main{
	public static void main(String args[]){
		Scanner s=new Scanner(System.in);
		int t;
		t=s.nextInt();
		int mod=20090305;
		while(true){
			if(t==0)System.exit(0);
			t--;
			
			int ra=s.nextInt();
			int rb=s.nextInt();
			int rc=s.nextInt();
			String str=s.next();
			int n=str.length();
			int a=0;
			int b=0;
			int c=0;
			for(int i=0;i<n;i++){
				if(str.charAt(i)=='A')a++;
				if(str.charAt(i)=='B')b++;
				if(str.charAt(i)=='C')c++;
			}
			int A[]=new int[a];
			int B[]=new int[b];
			int C[]=new int[c];
			int atA=0;
			int atB=0;
			int atC=0;
			for(int i=0;i<n;i++){
				if(str.charAt(i)=='A')A[atA++]=i;
				if(str.charAt(i)=='B')B[atB++]=i;
				if(str.charAt(i)=='C')C[atC++]=i;
			}
			int dp[][][]=new int[a+1][b+1][c+1];
			dp[0][0][0]=1;
			for(int i=0;i<=a;i++){
				for(int j=0;j<=b;j++){
					for(int k=0;k<=c;k++){
						if(dp[i][j][k]==0)continue;
						int now=i+j+k;
						if(i<a){
							if(now>=A[i]-ra&&now<=A[i]+ra)dp[i+1][j][k]=(dp[i+1][j][k]+dp[i][j][k])%mod;
						}
						if(j<b){
							if(now>=B[j]-rb&&now<=B[j]+rb)dp[i][j+1][k]=(dp[i][j+1][k]+dp[i][j][k])%mod;
						}
						if(k<c){
							if(now>=C[k]-rc&&now<=C[k]+rc)dp[i][j][k+1]=(dp[i][j][k+1]+dp[i][j][k])%mod;
						}
					}
				}
			}
			System.out.println(dp[a][b][c]);
		}
	}
}