Submission #73713441

---

Source Code Expand

import java.util.ArrayList;
import java.util.Scanner;



public class Main {
	public static void main(String[] args) {
		//new Main().C();
		new D().go();
	}
	
	void A() {
		Scanner in = new Scanner(System.in);

		int N = in.nextInt();
		int M = in.nextInt();

		int max = (N+1)/2;

		System.out.println( max>=M ? "Yes":"No" );
	}


	
	void B() {
		Scanner in = new Scanner(System.in);

		String s = in.next();
		int[] count = new int[26];
		
		for (int i=0;i<s.length();i++) {
			char ch = s.charAt(i);
			count[ch-'a']++;
		}

		int max=0;
		for (int i=0;i<count.length;i++) {
			max = Integer.max(max,count[i]);
		}

		StringBuilder sb = new StringBuilder();
		for (int i=0;i<s.length();i++) {
			char ch = s.charAt(i);
			if ( count[ch-'a'] == max ) {
				
			} else {
				sb.append(ch);
			}
		}
		
		System.out.println(sb.toString());
	}

	void C() {
		int ret = C2();
		System.out.println( ret );
	}
	int C2() {
		Scanner in = new Scanner(System.in);
		String S = in.next() +"#";
		String T = in.next() +"#";
		
		int x=0,y=0;
		int step = 0;
		while (true) {
			int x0=0;
			int y0=0;
			while ( S.charAt(x) == 'A' ) {x++;x0++;}
			while ( T.charAt(y) == 'A' ) {y++;y0++;}
			
			//System.out.println( S.charAt(x) + " " + T.charAt(y) );
			
			if ( S.charAt(x) != T.charAt(y) ) return -1;
			
			step += Math.abs(x0-y0);
			if ( S.charAt(x) == '#' ) return step;
			x++;y++;
		}
	}
}
class D {
	String S;
	int[][] A;
	int[] len;
	
	ArrayList<String> key;
	ArrayList<Integer> value;
	
	
	public D() {
		Scanner in = new Scanner(System.in);
		String S = in.next();
		A = new int[3][1000000];
		len = new int[3];
		
		for (int i=0;i<S.length();i++) {
			int idx = S.charAt(i)-'A';
			A[idx][ len[idx]++ ] = i;
		}
		
		key = new ArrayList<>();
		value = new ArrayList<>();
//		for (int idx=0;idx<3;idx++) {
//			for (int i=0;i<len[idx];i++) System.out.print( A[idx][i] +" ");
//			System.out.println("");
//		}
	}
	
	void go() {
		int answer = 0;
		for (int i=0;i<len[0];i++) {
			for (int j=0;j<len[1];j++) {
				for (int k=0;k<len[0];k++) {
					if ( A[0][i] < A[1][j] && A[1][j]<A[2][k] ) {
						int ret = seek(i+1,j+1,k+1,1);
						answer = Integer.max(answer,ret);
						//System.out.println(ret);
					}
				}
			}
		}
		System.out.println(answer);
	}

	int seek(int i,int j, int k,int depth) {
		String id = i+"_"+j+"_"+k;
		int idx = key.indexOf(id);
		if ( idx>=0 ) return value.indexOf(idx);
		
		for (;i<len[0];i++) {
			for (;j<len[1];j++) {
				for (;k<len[0];k++) {
					if ( A[0][i] < A[1][j] && A[1][j]<A[2][k] ) return seek(i+1,j+1,k+1,depth+1); 
				}
			}
		}
		key.add( id );
		value.add(depth);
		return depth;
	}
}

/**
 * AllPatternDegi(int N, int D): D進数のN桁全組み合わせを列挙するクラス。
 * boolean next(): 次の組み合わせに進み、状態が更新される。全列挙が終わると false を返す。
 * int[] getStatus(): 現在の組み合わせ（状態）を取得する。
 */
class allPatternDegi {
	int N,D;
	int[] status;
	
	public allPatternDegi(int n,int d) {
		N = n;
		D = d;
		status = null;
	}
	
	boolean next() {
		if ( status==null ) {
			status = new int[N];
			return true;
		}
		
		int idx=0;
		while ( idx<N ) {
			status[idx]++;
			if ( status[idx]<D ) return true;
			
			status[idx]=0;
			idx++;
		}
		
		return false;
	}
}

Submission Info

Judge Result