SRM 650 Div. 1 Easy: TaroFillingAStringDiv1

解法

偶数個間が空いている時、例えば2個空いている時、A__Bのようになっている時はABABしかあり得ないが、A__Aのようになっている時はAABAかABAAかABBAのように3通り考えられる。一般化すると、間が2k個空いている時、それを挟む文字が同じであれば、2k+1通り考えられる。同様に、間が2k+1個空いている時、それを挟む文字が異なっていれば、2k+2通り考えられる。答えるべきパターン数は、これらの積である。

コード

import java.util.ArrayList;
import java.util.Collections;

public class TaroFillingAStringDiv1 {

	public int getNumber(int N, int[] position, String value) {
		ArrayList<Position> list = new ArrayList<>();
		for (int i = 0; i < position.length; i++) {
			list.add(new Position(position[i], value.charAt(i)));
		}
		Collections.sort(list);

		int MOD = 1000000007;
		long ans = 1;
		int before = 0;
		char beforeChar = ' ';
		for (Position pos : list) {
			int dist = pos.position - before - 1;
			if (dist > 0) {
				if (dist % 2 == 0 && beforeChar == pos.value) {
					ans *= (dist + 1);
					ans %= MOD;
				} else if (dist % 2 != 0 && beforeChar != pos.value && beforeChar != ' ') {
					ans *= (dist + 1);
					ans %= MOD;
				}
			}

			before = pos.position;
			beforeChar = pos.value;
		}

		return (int) ans;
	}

	class Position implements Comparable<Position> {
		int position;
		char value;

		public Position(int p, char v) {
			this.position = p;
			this.value = v;
		}

		@Override
		public int compareTo(Position arg0) {
			return this.position - arg0.position;
		}
	}
}