Problem:


問題 4:　部活のスケジュール表 (Schedule)

問題

IOI 高校のプログラミング部には，J 君と O 君と I 君の 3 人の部員がいる．
プログラミング部では，部活のスケジュールを組もうとしている．

今，N 日間の活動のスケジュールを決めようとしている．
各活動日のスケジュールとして考えられるものは，各部員については活動に参加するかどうかの 2 通りがあり，部としては全部で 8 通りある．
部室の鍵はただ 1 つだけであり，最初は J 君が持っている．
各活動日には，その日の活動に参加する部員のうちのいずれか 1 人が鍵を持っている必要があり，活動後に参加した部員のいずれかが鍵を持って帰る．

プログラミング部では，活動日には毎回必ず活動が行われるように，あらかじめ各活動日の責任者を定めた．
責任者は，必ずその日の活動に出席しなければならない．

スケジュールを決めようとしている日数と，各活動日の責任者が誰であるかの情報が与えられた時，すべての活動日に部活動を行うことができるようなスケジュール表として考えられるものの数を 10007 で割った余りを求めるプログラムを作成せよ．
ただし，部活の終了時に鍵を持って帰る部員は，その日の活動に参加している部員の誰でもよく，最終日は誰が鍵を持って帰ってもよいものとする．

入力

入力は，2 行からなる．

1 行目には，スケジュールを決めようとしている日数を表す 1 つの整数 N (2 ≤ N ≤ 1000) が書かれている．

2 行目には，各活動日の責任者を表す N 文字からなる文字列が書かれている．
この文字列の i 文字目 (1 ≤ i ≤ N) は，i 日目の活動日の責任者を表す．
すなわち，i 文字目が J, O, I であることはそれぞれ i 日目の活動日の責任者が J 君，O 君，I 君であることを意味する．

出力

スケジュール表として考えられるものの数を 10007 で割った余りを 1 行で出力せよ．

入出力例

入力例 1

  

2
OI

出力例 1

   

7

入出力例 1 において，2 日間の活動日のスケジュールを考える．1 日目の責任者は O 君，2 日目の責任者は I 君である．
問題文の条件をみたすスケジュール表は 7 通り考えられる．

 

  
   1 日目 
   2 日目 
 

 

  スケジュール 1   
  J, O
  O, I
 

 

  スケジュール 2   
  J, O
  J, I
 

 

  スケジュール 3   
  J, O
  J, O, I
 

 

  スケジュール 4   
  J, O, I
  I
 

 

  スケジュール 5   
  J, O, I
  J, I
 

 

  スケジュール 6   
  J, O, I
  O, I
 

 

  スケジュール 7   
  J, O, I
  J, O, I
 

 
この表では，J, O, I はそれぞれその日に J 君, O 君, I 君が参加することを表す．
1 日目の責任者は O 君であるが，最初鍵を持っているのは J 君であるため，1 日目の活動には J 君, O 君の両方が参加する必要があることに注意せよ．
また，1 日目に鍵を持って帰った人は 2 日目にも参加しないといけないので，1 日目と 2 日目の両方に参加する人が少なくとも 1 人存在しなければならないことに注意せよ．

   

入力例 2
  

  

20
JIOIJOIJOJOIIIOJIOII

出力例 2

   

4976

入出力例 2 において，条件をみたすスケジュール表は全部で 72493594992 通り考えられる．それを 10007 で割った余りである 4976 を出力する．

問題文と自動審判に使われるデータは、情報オリンピック日本委員会が作成し公開している問題文と採点用テストデータです。



Sample input:
2
OI


Sample output:
7

Submission status: Wrong Answer

Solution code:
N = int(input())

C = input()

S = list(C)

dp = [[0 for i in range(8)] for j in range(N + 1)]

dp[0][1] = 1

for i in range(N):
    
    if C[i] == "J":
        dp[i + 1][1] = dp[i][1] + dp[i][2] + dp[i][3] + dp[i][4];
        dp[i + 1][2] = dp[i][1] + dp[i][2] + dp[i][3] + dp[i][4] + dp[i][5] + dp[i][6];
        dp[i + 1][3] = dp[i][1] + dp[i][2] + dp[i][3] + dp[i][4] + dp[i][6] + dp[i][7];
        dp[i + 1][4] = dp[i][1] + dp[i][2] + dp[i][3] + dp[i][4] + dp[i][5] + dp[i][6] + dp[i][7];
        dp[i + 1][5] = 0;
        dp[i + 1][6] = 0;
        dp[i + 1][7] = 0;
    if C[i] == 'O':
        dp[i + 1][1] = 0;
        dp[i + 1][2] = dp[i][1] + dp[i][2] + dp[i][3] + dp[i][4] + dp[i][5] + dp[i][6];
        dp[i + 1][3] = 0;
        dp[i + 1][4] = dp[i][1] + dp[i][2] + dp[i][3] + dp[i][4] + dp[i][5] + dp[i][6] + dp[i][7];
        dp[i + 1][5] = dp[i][2] + dp[i][4] + dp[i][5] + dp[i][6];
        dp[i + 1][6] = dp[i][2] + dp[i][3] + dp[i][4] + dp[i][5] + dp[i][6] + dp[i][7];
        dp[i + 1][7] = 0;
    if C[i] == "I":
        dp[i + 1][1] = 0;
        dp[i + 1][2] = 0;
        dp[i + 1][3] = dp[i][1] + dp[i][2] + dp[i][3] + dp[i][4] + dp[i][6] + dp[i][7];
        dp[i + 1][4] = dp[i][1] + dp[i][2] + dp[i][3] + dp[i][4] + dp[i][5] + dp[i][6] + dp[i][7];
        dp[i + 1][5] = 0;
        dp[i + 1][6] = dp[i][2] + dp[i][3] + dp[i][4] + dp[i][5] + dp[i][6] + dp[i - 1][7];
        dp[i + 1][7] = dp[i][3] + dp[i][4] + dp[i][6] + dp[i][7];

print((dp[N][1] + dp[N][2] + dp[N][3] + dp[N][4] + dp[N][5] + dp[N][6] + dp[N][7]) % 10007)

Submission status: Wrong Answer

Solution code:
n=input()
s=raw_input()
mod=10007
dp=[[0]*(1<<3) for _ in xrange(n+1)]
for i in xrange(n):
    if s[i]=="J":shift=2
    elif s[i]=="O":shift=1
    else:shift=0
    for j in xrange(8):
        if j&(1<<shift)!=0:
            if i==0:
                if j&(1<<2)!=0:
                    dp[i+1][j]=1
            else:
                for k in xrange(8):
                    if k&j!=0:
                        dp[i+1][j]+=dp[i][k]
                        dp[i+1][j]=dp[i+1][j]%mod
print(sum(dp[n]))

Submission status: Accepted

Solution code:
dp = [[0]*8 for i in range(1001)]
dp[0][1] = 1
n = input()
s = raw_input()
for i in range(n):
    b = 1 if s[i] == "J" else 2 if s[i] == "O" else 4
    for j in range(8):
        for k in range(8):
            if (k & b) and (j & k):
                dp[i + 1][k] = (dp[i + 1][k] + dp[i][j]) % 10007
print reduce(lambda x, a: (x + a) % 10007, dp[n])

Submission status: Accepted

Solution code:
N = int(input())

C = input()

S = list(C)

dp = [[0 for i in range(8)] for j in range(N + 1)]

dp[0][1] = 1

for i in range(N):
    if C[i] == "J":
        dp[i + 1][1] = dp[i][1] + dp[i][2] + dp[i][3] + dp[i][4];
        dp[i + 1][2] = dp[i][1] + dp[i][2] + dp[i][3] + dp[i][4] + dp[i][5] + dp[i][6];
        dp[i + 1][3] = dp[i][1] + dp[i][2] + dp[i][3] + dp[i][4] + dp[i][6] + dp[i][7];
        dp[i + 1][4] = dp[i][1] + dp[i][2] + dp[i][3] + dp[i][4] + dp[i][5] + dp[i][6] + dp[i][7];
        dp[i + 1][5] = 0;
        dp[i + 1][6] = 0;
        dp[i + 1][7] = 0;
    if C[i] == 'O':
        dp[i + 1][1] = 0;
        dp[i + 1][2] = dp[i][1] + dp[i][2] + dp[i][3] + dp[i][4] + dp[i][5] + dp[i][6];
        dp[i + 1][3] = 0;
        dp[i + 1][4] = dp[i][1] + dp[i][2] + dp[i][3] + dp[i][4] + dp[i][5] + dp[i][6] + dp[i][7];
        dp[i + 1][5] = dp[i][2] + dp[i][4] + dp[i][5] + dp[i][6];
        dp[i + 1][6] = dp[i][2] + dp[i][3] + dp[i][4] + dp[i][5] + dp[i][6] + dp[i][7];
        dp[i + 1][7] = 0;
    if C[i] == 'I':
        dp[i + 1][1] = 0;
        dp[i + 1][2] = 0;
        dp[i + 1][3] = dp[i][1] + dp[i][2] + dp[i][3] + dp[i][4] + dp[i][6] + dp[i][7];
        dp[i + 1][4] = dp[i][1] + dp[i][2] + dp[i][3] + dp[i][4] + dp[i][5] + dp[i][6] + dp[i][7];
        dp[i + 1][5] = 0;
        dp[i + 1][6] = dp[i][2] + dp[i][3] + dp[i][4] + dp[i][5] + dp[i][6] + dp[i][7];
        dp[i + 1][7] = dp[i][3] + dp[i][4] + dp[i][6] + dp[i][7];

print((dp[N][1] + dp[N][2] + dp[N][3] + dp[N][4] + dp[N][5] + dp[N][6] + dp[N][7]) % 10007)

Submission status: Accepted

Solution code:
n=input()
s=raw_input()
mod=10007
dp=[[0]*(1<<3) for _ in xrange(n+1)]
for i in xrange(n):
    if s[i]=="J":shift=2
    elif s[i]=="O":shift=1
    else:shift=0
    for j in xrange(8):
        if j&(1<<shift)!=0:
            if i==0:
                if j&(1<<2)!=0:
                    dp[i+1][j]=1
            else:
                for k in xrange(8):
                    if k&j!=0:
                        dp[i+1][j]+=dp[i][k]
                        dp[i+1][j]=dp[i+1][j]%mod
print(sum(dp[n])%mod)

Submission status: Accepted

Solution code:
N = input()
S = raw_input()
T = [0]*8
for i in range(8):
    if i&1 and i>>"JOI".index(S[0])&1:
        T[i] = 1
for s in S[1:]:
    P = T
    T = [0]*8
    for i in range(8):
        for j in range(8):
            if j>>"JOI".index(s)&1 and i&j:
                T[j] += P[i]
print sum(T)%10007

Submission status: Accepted

Solution code:
def plus(s):
    global c
    d = [0] * 7
    for i in range(7):
        if s in g[i]:
            for j in range(7):
                if g[i] & g[j] != set():
                    d[i] += c[j]
    c = d

n = int(input())
s = input()
g = [set(["J"]), set(["O"]), set(["I"]), set(["J", "O"]), set(["J", "I"]), set(["O", "I"]), set(["J", "O", "I"])]
c = [1, 0, 0, 0, 0, 0, 0, 0]
for i in range(n):
    plus(s[i])

print(sum(c) % 10007)

Submission status: Accepted

Solution code:
n = int(input())
res = input()

dic = {"J":0, "O":1, "I":2}
zo = [0,1]
dp =[[[0 for j in zo] for o in zo] for i in zo]

res1 = dic[res[0]]

if res1 == 0:
  for o in zo:
    for i in zo:
      dp[1][o][i] = 1
elif res1 == 1:
  for i in zo:
    dp[1][1][i] = 1
else:
  for o in zo:
    dp[1][o][1] = 1

for d in range(1, n):
  resd = dic[res[d]]
  new = [[[0 for i in zo] for o in zo] for j in zo]
  new[0][0][0] = 0
  new[1][1][1] = sum([dp[x][y][z] for x in zo for y in zo for z in zo])
  new[0][0][1] = sum([dp[x][y][1] for x in zo for y in zo]) if resd == 2 else 0
  new[0][1][0] = sum([dp[x][1][y] for x in zo for y in zo]) if resd == 1 else 0
  new[1][0][0] = sum([dp[1][x][y] for x in [0,1] for y in [0,1]]) if resd == 0 else 0
  new[0][1][1] = sum([dp[x][1][y] + dp[x][y][1] for x in zo for y in zo]) - sum(dp[x][1][1] for x in zo) if resd in [1, 2] else 0
  new[1][0][1] = sum([dp[1][x][y] + dp[x][y][1] for x in zo for y in zo]) - sum(dp[1][x][1] for x in zo) if resd in [0, 2] else 0
  new[1][1][0] = sum([dp[x][1][y] + dp[1][x][y] for x in zo for y in zo]) - sum(dp[1][1][x] for x in zo) if resd in [0, 1] else 0
  dp = new

ans = 0
for i in zo:
  for j in zo:
    for k in zo:
      ans += dp[i][j][k]

print(ans % 10007)

Submission status: Accepted

Solution code:
def main():
  
  n = int(input())
  res = input()
  
  dic = {"J":0, "O":1, "I":2}
  zo = [0,1]
  dp =[[[0 for j in zo] for o in zo] for i in zo]
  
  res1 = dic[res[0]]
  
  if res1 == 0:
    for o in zo:
      for i in zo:
        dp[1][o][i] = 1
  elif res1 == 1:
    for i in zo:
      dp[1][1][i] = 1
  else:
    for o in zo:
      dp[1][o][1] = 1
  
  for d in range(1, n):
    resd = dic[res[d]]
    new = [[[0 for i in zo] for o in zo] for j in zo]
    new[0][0][0] = 0
    new[1][1][1] = sum([dp[x][y][z] for x in zo for y in zo for z in zo])
    new[0][0][1] = sum([dp[x][y][1] for x in zo for y in zo]) if resd == 2 else 0
    new[0][1][0] = sum([dp[x][1][y] for x in zo for y in zo]) if resd == 1 else 0
    new[1][0][0] = sum([dp[1][x][y] for x in [0,1] for y in [0,1]]) if resd == 0 else 0
    new[0][1][1] = sum([dp[x][1][y] + dp[x][y][1] for x in zo for y in zo]) - sum(dp[x][1][1] for x in zo) if resd in [1, 2] else 0
    new[1][0][1] = sum([dp[1][x][y] + dp[x][y][1] for x in zo for y in zo]) - sum(dp[1][x][1] for x in zo) if resd in [0, 2] else 0
    new[1][1][0] = sum([dp[x][1][y] + dp[1][x][y] for x in zo for y in zo]) - sum(dp[1][1][x] for x in zo) if resd in [0, 1] else 0
    dp = new
  
  ans = 0
  for i in zo:
    for j in zo:
      for k in zo:
        ans += dp[i][j][k]
  
  print(ans % 10007)

main()

Submission status: Accepted

Solution code:
dp = [range(8) for i in range(1001)]

for i in range(1001) :
	for j in range(8) :
		dp[i][j] = 0

dp[0][1] = 1

n = input()
s = raw_input().strip()

for i in range(n) :
	b = 0
	if s[i] != 'J' :
		b += 1
		if s[i] != 'O' :
			b += 1
	
	for j in range(8) :
		for k in range(8) :
			if (((k >> b) & 1) and (j & k) != 0) :
				dp[i + 1][k] = (dp[i + 1][k] + dp[i][j]) % 10007

sum = 0
for i in range(8) :
	sum = (sum + dp[n][i]) % 10007

print sum

Submission status: Accepted

Solution code:
#D問題
mod = 10007
N = int(input())
S = list(str(input()))
dp = [[0 for i in range(7)] for j in range(N)]#j,o,i,jo,oi,ij,joi

for i in range(N):
    s = S[i]
    if i == 0:
        if s == "J":
            dp[0][0]+=1
            dp[0][3]+=1
            dp[0][5]+=1
            dp[0][6]+=1
        elif s == "O":
            dp[0][3]+=1
            dp[0][6]+=1
        else:
            dp[0][5]+=1
            dp[0][6]+=1
    else:
        if s == "J":
            dp[i][0] = dp[i-1][0]+dp[i-1][3]+dp[i-1][5]+dp[i-1][6]
            dp[i][3] = dp[i-1][0]+dp[i-1][1]+dp[i-1][3]+dp[i-1][4]+dp[i-1][5]+dp[i-1][6]
            dp[i][5] = dp[i-1][0]+dp[i-1][2]+dp[i-1][3]+dp[i-1][4]+dp[i-1][5]+dp[i-1][6]
            dp[i][6] = dp[i-1][0]+dp[i-1][1]+dp[i-1][2]+dp[i-1][3]+dp[i-1][4]+dp[i-1][5]+dp[i-1][6]
        elif s == "O":
            dp[i][1] = dp[i-1][1]+dp[i-1][3]+dp[i-1][4]+dp[i-1][6]
            dp[i][3] = dp[i-1][0]+dp[i-1][1]+dp[i-1][3]+dp[i-1][4]+dp[i-1][5]+dp[i-1][6]
            dp[i][4] = dp[i-1][1]+dp[i-1][2]+dp[i-1][3]+dp[i-1][4]+dp[i-1][5]+dp[i-1][6]
            dp[i][6] = dp[i-1][0]+dp[i-1][1]+dp[i-1][2]+dp[i-1][3]+dp[i-1][4]+dp[i-1][5]+dp[i-1][6]
        elif s == "I":
            dp[i][2] = dp[i-1][2]+dp[i-1][4]+dp[i-1][5]+dp[i-1][6]
            dp[i][4] = dp[i-1][1]+dp[i-1][2]+dp[i-1][3]+dp[i-1][4]+dp[i-1][5]+dp[i-1][6]
            dp[i][5] = dp[i-1][0]+dp[i-1][2]+dp[i-1][3]+dp[i-1][4]+dp[i-1][5]+dp[i-1][6]
            dp[i][6] = dp[i-1][0]+dp[i-1][1]+dp[i-1][2]+dp[i-1][3]+dp[i-1][4]+dp[i-1][5]+dp[i-1][6]
    
print(sum(dp[N-1])%mod)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Schedule
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0595

"""
import sys

from collections import Counter
from itertools import product

def solve(n, data):
    status = Counter({(1, 0, 0): 1})
    for ch in data:
        u = Counter()
        for j, o, i in product((0, 1), repeat=3):
            if {'J': j, 'O': o, 'I': i}[ch]:
                for k, v in status.items():
                    pj, po, pi = k
                    if any([(j and pj), (o and po), (i and pi)]):
                        u[(j, o, i)] += v
        status = Counter({k: v % 10007 for k, v in u.items()})
    return sum(status.values()) % 10007


def main(args):
    n = int(input())
    data = input()
    ans = solve(n, data)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])