Problem:


問題名 箱根駅伝

日本のお正月の風物詩に箱根駅伝があります。箱根駅伝は、各チーム 10 人の走者が中継所ごとに襷をつなぎながらゴールを目指すというものです。テレビの放送では中継所で各チームの通過順位と共に前の中継所からの順位変動が表示されます。そこで、それを見て前の中継所の各チームの通過順として考えられるものが何通りあるか答えてください。ありえた通過順の数は非常に大きくなりうるので、1,000,000,007 で割った余りで答えて下さい。

Input

入力は以下の形で与えられます

n
c1
c2
...
cn

1行目にはチーム数を表す数字 n (1 ≤ n ≤ 200) が、続く n 行には 1 位から順に前の中継所からの順位変動 ci ('D' なら順位が落ちてる、'U' なら順位が上がってる、'-' なら順位が変わってない) が書いてあります。

Output

前の中継所でありえた通過順が何通りかを、 1,000,000,007 で割ったあまりで 1 行で出力して下さい。

Sample Input 1

3
-
U
D

Output for the Sample Input 1

1

この中継所を 1 位、 2 位、 3 位で通過したチームのチーム名をそれぞれ A, B, C とすると、前の中継所の通過順として考えられるのは 1 位：チーム A, 2 位：チーム C, 3 位：チーム B の 1 通りのみです。

Sample Input 2

5
U
U
-
D
D

Output for the Sample Input 2

5

この中継所の通過順にチーム名を A, B, C, D, E とすると、前の中継所の通過順として考えられるのは {D, E, C, A, B}, {D, E, C, B, A}, {E, D, C, A, B}, {E, D, C, B, A}, {D, A, C, E, B} の5通りです。

Sample Input 3

8
U
D
D
D
D
D
D
D

Output for the Sample Input 3

1

Sample Input 4

10
U
D
U
D
U
D
U
D
U
D

Output for the Sample Input 4

608

Sample Input 5

2
D
U

Output for the Sample Input 5

0



Sample input:
3
-
U
D


Sample output:
1

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**3
eps = 1.0 / 10**10
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n = I()
    c = [S() for _ in range(n)]
    dp = [[0]*(n+1) for _ in range(n+1)]
    dp[0][0] = 1
    for i in range(n):
        ci = c[i]
        if ci == '-':
            for j in range(n+1):
                dp[i+1][j] = dp[i][j]
        elif ci == 'D':
            for j in range(n+1):
                dp[i+1][j] += dp[i][j] * j
                if j > 0:
                    dp[i+1][j-1] += dp[i][j] * j * j
                    dp[i+1][j-1] %= mod
        else: # 'U'
            for j in range(n+1):
                if j < n:
                    dp[i+1][j+1] += dp[i][j]
                dp[i+1][j] += dp[i][j] * j
                dp[i+1][j] %= mod

    return dp[-1][0] % mod


print(main())

Submission status: Accepted

Solution code:
n = int(input())
c = [input() for i in range(n)]
MOD = 10 ** 9 + 7


dp = [[0] * (n + 1) for i in range(n + 1)]
dp[0][0] = 1

for i , char in enumerate(c):
    if char == "-":
        for j in range(n + 1):
            if j + 1 < n + 1:
                dp[i + 1][j + 1] += dp[i][j]
                dp[i + 1][j + 1] %= MOD

    if char == "U":
        for j in range(n + 1):
            dp[i + 1][j] += dp[i][j]
            dp[i + 1][j] %= MOD
            if j + 1 < n + 1:
                dp[i + 1][j + 1] += dp[i][j] * (i - j)
                dp[i + 1][j + 1] %= MOD

    if char == "D":   
        for j in range(n + 1):
            if j + 1 < n + 1:
                dp[i + 1][j + 1] += dp[i][j] * (i - j)
                dp[i + 1][j + 1] %= MOD
            if j + 2 < n + 1:
                dp[i + 1][j + 2] += dp[i][j] * (i - j) ** 2
                dp[i + 1][j + 2] %= MOD

print(dp[-1][-1])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

# 参考にしました(参考というよりほぼ写経)
# https://drken1215.hatenablog.com/entry/2019/10/05/173700

n = I()
dp = [[0] * (n+2) for _ in range(n+1)]
# 今回の順位と前回の順位を結んだグラフを考える
# dp[i][j] := i番目まで見たときに, j個繋がっているときの場合の数
dp[0][0] = 1
for i in range(n):
    s = input()
    if s == 'U':
        # Uのとき，今回順位から前回順位に向かう辺は必ず下向きなので
        # i+1番目まで見たときに今回順位からの辺によってjが増加することはない
        # jが増加するのは前回順位からの辺が上に伸びている場合
        # このとき，対応するペアを今回順位の中からi-j個の中から選ぶ
        for j in range(n):
            dp[i+1][j] += dp[i][j]# 今回順位からも前回順位からも下へ伸びている場合
            dp[i+1][j+1] += dp[i][j] * (i - j)# 今回順位からは下へ，前回順位からは上へ伸びている場合
            dp[i+1][j+1] %= mod 
    elif s == '-':
        # -のとき，今回順位から前回順位に向かう辺は必ず同じ位置であり，
        # 前回順位から今回順位へ向かう辺も必ず同じ位置である
        # つまり，jが1だけ増加する
        for j in range(n):
            dp[i+1][j+1] += dp[i][j]
    else:
        # Dのとき，今回順位から前回順位に向かう辺は必ず上向きなので
        # i+1番目まで見たときに今回順位からの辺によって必ずjが増加する
        # 前回順位から今回順位へ向かう辺が上向きの場合は，両方ともjが増加するのでj+2
        # 前回順位から今回順位へ向かう辺が下向きの場合は，jが増加しないのでj+1
        for j in range(n):
            dp[i+1][j+2] += dp[i][j] * (i - j) * (i - j)# 今回順位からも前回順位からも上へ伸びている場合
            dp[i+1][j+2] %= mod
            dp[i+1][j+1] += dp[i][j] * (i - j)# 今回順位からは上へ，前回順位からは下へ伸びている場合
            dp[i+1][j+1] %= mod
print(dp[n][n])

Submission status: Accepted

Solution code:
n = int(input())
s = [input() for i in range(n)]
s = "".join(s).replace("-","")
n = len(s)
mod = 10**9+7
dp = [[0 for i in range(n+1)] for j in range(n+1)]
dp[0][0] = 1
for i in range(n):
  si = s[i]
  if si == "D":
    for j in range(1,n+1):
      dp[i+1][j] = (dp[i+1][j]+dp[i][j]*j)%mod
      dp[i+1][j-1] = (dp[i+1][j-1]+dp[i][j]*j**2)%mod
  else:
    for j in range(n):
      dp[i+1][j+1] = (dp[i+1][j+1]+dp[i][j])%mod
      dp[i+1][j] = (dp[i+1][j]+dp[i][j]*j)%mod
print(dp[n][0])

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
write = sys.stdout.write
def solve():
    MOD = 10**9 + 7
    N = int(readline())
    S = []
    for i in range(N):
        s = readline().strip()
        if s == "-":
            N -= 1
            continue
        S.append(s == "D")
    memo = {}
    def dfs(i, a, b):
        if i == N:
            return (a == b == 0)
        key = (i, a, b)
        if key in memo:
            return memo[key]
        r = 0
        if S[i]:
            if a > 0:
                r += dfs(i+1, a, b) * a % MOD
            if a > 0 and b > 0:
                r += dfs(i+1, a-1, b-1) * a * b % MOD
        else:
            r += dfs(i+1, a+1, b+1)
            if b > 0:
                r += dfs(i+1, a, b) * b % MOD
        memo[key] = r = r % MOD
        return r
    write("%d\n" % dfs(0, 0, 0))
solve()

Submission status: Accepted

Solution code:
MOD = 10**9+7
n = int(input())
dp = [[0 for _ in range(n+1)] for _ in range(n+1)]
dp[0][0] = 1
for i in range(1, n+1):
	s = input()
	for j in range(n+1):
		if s == "U":
			if j > 0:
				dp[i][j] += dp[i-1][j-1]
			dp[i][j] += j * dp[i-1][j]
		elif s == "-":
			dp[i][j] += dp[i-1][j]
		else:
			if j < n:
				dp[i][j] += (j+1) * (j+1) * dp[i-1][j+1]
			dp[i][j] += j * dp[i-1][j]
		dp[i][j] %= MOD
print(dp[n][0])

Submission status: Accepted

Solution code:

"""
Writer: SPD_9X2
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2439

1位から順番に見ていく。
-ならそこの順位に決めざるを得ない

Uなら、左に空いた空きマスから1つ選んでそこに入れる(空きマスは減る)
Dなら、…？

dpであることは分かっている
重要なのはどの状態をまとめるか…

-は関係ないので無視してUDだけの問題にする
UDの列に通し番号を付ける。Uはそれより右に、Dは左にもっていかなくてはならない
そのような並び替えが構成できなくなるのは、左にもとよりUが多い場合・・・

Uだけの入れ方を考えてみる(Dはどこに入っても構わない)
左から見ていくと、入れる・入れないを決め、今までに出たUの中から1つ選んで入れればよい
→ただのdpで解ける

Dだけの入れ方も同様に分かる

あらかじめU,Dにおいてdpをしておく？

udp[左からi番目にUが入る場合のUの入り方][j][k] =
ん～？？？？？

=====解説を見た=====

Uならば、それより右に入れなきゃいけない→保留枠に入れ、Uのあったマスを開けておく
Dならば、そこにあったDを左の空きますにぶち込み、保留の中から1つUを選んでぶち込む or　空きますにする
→空きマスは1つ減る or 減らない

空きマスの数 = 保留の数なので、 O(N**2)で解ける

"""

n = int(input())

dp = [0] * (n+1)
dp[0] = 1
mod = 10**9+7

for loop in range(n):

    c = input()
    ndp = [0] * (n+1)
    if c == "-":
        continue

    
    elif c == "U":
        for i in range(n+1):

            if i != n: #保留に入れて空きますにする
                ndp[i+1] = dp[i]
                ndp[i+1] %= mod

            #保留に入れ、保留から1つ取り出して入れる

            ndp[i] += dp[i] * i
            ndp[i] %= mod
            

    else:
        for i in range(0,n+1):

            if i != 0: #そこにあったのは左の空きますに移動 & そのマスに保留からぶち込む
                ndp[i-1] += dp[i] * i * i
                ndp[i-1] %= mod

            #そこにあったのは左の空きますに、そこは空きますにする

            ndp[i] += dp[i] * i
            ndp[i] %= mod
    

    dp = ndp
    #print (dp)

print (dp[0])

Submission status: Accepted

Solution code:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

# 箱根


N = int(sys.stdin.readline())
C = [sys.stdin.readline().rstrip() for _ in range(N)]
C = [c for c in C if c != '-']
N = len(C)

# dp[i][j][k]:
# iまで見て、
# j個未割当の人が残ってて、
# j個未割当の場所が残ってる場合の数
dp = [[0] * (N + 1) for _ in range(N + 1)]
dp[0][0] = 1
for i, c in enumerate(C):
    for j in range(N):
        if c == 'D':
            if j - 1 >= 0:
                # 前回i位だった人を今まで見た場所に割り当てる
                dp[i + 1][j - 1] += dp[i][j] * j * j
                dp[i + 1][j - 1] %= MOD
            # 割り当てない
            dp[i + 1][j] += dp[i][j] * j
            dp[i + 1][j] %= MOD
        if c == 'U':
            # 前回i位だった人を今まで見た場所に割り当てる
            dp[i + 1][j] += dp[i][j] * j
            dp[i + 1][j] %= MOD
            # 割り当てない
            dp[i + 1][j + 1] += dp[i][j]
            dp[i + 1][j + 1] %= MOD
print(dp[-1][0])

Submission status: Accepted

Solution code:
N=int(input())
dp=[[0]*(N+1) for i in range(N+1)]
dp[0][0]=1
MOD=10**9+7
for i in range(N):
    s=input()
    for j in range(i+1):
        if s=="-":
            nj=j
            dp[i+1][nj]+=dp[i][j]
            dp[i+1][nj]%=MOD
        elif s=="U":#実際には下がる
            nj=j+1
            dp[i+1][nj]+=dp[i][j]
            dp[i+1][nj]%=MOD

            nj=j
            x=j
            dp[i+1][nj]+=dp[i][j]*x
            dp[i+1][nj]%=MOD
        elif s=="D":#実際には上がる
            nj=j
            x=j
            dp[i+1][nj]+=dp[i][j]*x
            dp[i+1][nj]%=MOD

            if nj==0:
                continue
            nj=j-1
            x=j*j
            dp[i+1][nj]+=dp[i][j]*x
            dp[i+1][nj]%=MOD
print(dp[N][0])

Submission status: Accepted

Solution code:
MOD = 1000000007
n = int(input())
dp = [[0] * (n + 1) for _ in range(n + 1)]
dp[0][0] = 1
for i in range(n):
    c = input()
    for j in range(n):
        if c == "-":
            dp[i + 1][j] += dp[i][j]
            dp[i + 1][j] %= MOD
        if c == "U":
            dp[i + 1][j] += j * dp[i][j]
            dp[i + 1][j] %= MOD
            if n > j:
                dp[i + 1][j + 1] += dp[i][j]
                dp[i + 1][j + 1] %= MOD
        if c == "D":
            dp[i + 1][j] += j * dp[i][j]
            dp[i + 1][j] %= MOD
            if j > 0:
                dp[i + 1][j - 1] += j * j * dp[i][j]
                dp[i + 1][j - 1] %= MOD
print(dp[n][0])