AOJ2141 Girls' Party

問題リンク Girls' Party

• 概要

ある整数Nと円形に並んだBチームとGチームの人たちが入力で与えられる。時計回りに数えていき、N人目の人が輪から外れる。輪から外れた次の人から再びN人目が輪から外れる。円がBチームのみ、もしくはGチームのみになるまでこれを繰り返す。また、1度だけN人目ではなくN+1人目の人を輪から外すことができる。入力文字列の最初の人を、初回の数えはじめとする。このとき、Bチームが勝利したときに残っているBチームの人数の最大値を答えよ。
1 <= N <= 2^30
2 <= 人数 <= 200

• 解法

深さ優先探索+枝刈りです。
数えはじめの人を先頭にした文字列によって円の状態が表せます。また、それらについて、N+1人目を抜くやり方を行ったかどうかの状態で更に分かれます。
ある円の状態のN人目(N+1人目)はMODを使うことで一発で計算できます。

• ソース

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

//Girls' Party
public class AOJ2141 {

	int N, res;
	Set<String>[] v;
	
	void dfs(int nb, int ng, int z, String s){
		if(nb<=res)return;
		if(ng==0){
			res = nb; return;
		}
		if(v[z].contains(s))return;
		v[z].add(s);
		int n = s.length(), d = (N-1)%n;
		if(s.charAt(d)=='B'){
			dfs(nb-1, ng, z, s.substring(d+1)+s.substring(0, d));
		}
		else{
			dfs(nb, ng-1, z, s.substring(d+1)+s.substring(0, d));
		}
		if(z==1)return;
		d = N%n;
		if(s.charAt(d)=='B'){
			dfs(nb-1, ng, 1, s.substring(d+1)+s.substring(0, d));
		}
		else{
			dfs(nb, ng-1, 1, s.substring(d+1)+s.substring(0, d));
		}
	}
	
	@SuppressWarnings("unchecked")
	void run(){
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		while(T--!=0){
			N = sc.nextInt();
			String s = sc.next();
			v = new Set[2];
			v[0] = new HashSet<String>(); v[1] = new HashSet<String>();
			res = 0;
			int nb = 0, ng = 0;
			for(char c:s.toCharArray())
				if(c=='B')nb++; 
				else ng++;
			dfs(nb, ng, 0, s);
			System.out.println(res);
		}
	}
	
	public static void main(String[] args) {
		new AOJ2141().run();
	}
}