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; } } }