Problem:


Score : 500 points

Problem Statement

A robot is put at the origin in a two-dimensional plane.
Initially, the robot is facing in the positive x-axis direction.

This robot will be given an instruction sequence s.
s consists of the following two kinds of letters, and will be executed in order from front to back.

F : Move in the current direction by distance 1.

T : Turn 90 degrees, either clockwise or counterclockwise.

The objective of the robot is to be at coordinates (x, y) after all the instructions are executed.
Determine whether this objective is achievable.

Constraints

s consists of F and T.

1 \leq |s| \leq 8 000

x and y are integers.

|x|, |y| \leq |s|

Input

Input is given from Standard Input in the following format:

s
x y

Output

If the objective is achievable, print Yes; if it is not, print No.

Sample Input 1

FTFFTFFF
4 2

Sample Output 1

Yes

The objective can be achieved by, for example, turning counterclockwise in the first T and turning clockwise in the second T.

Sample Input 2

FTFFTFFF
-2 -2

Sample Output 2

Yes

The objective can be achieved by, for example, turning clockwise in the first T and turning clockwise in the second T.

Sample Input 3

FF
1 0

Sample Output 3

No

Sample Input 4

TF
1 0

Sample Output 4

No

Sample Input 5

FFTTFF
0 0

Sample Output 5

Yes

The objective can be achieved by, for example, turning counterclockwise in the first T and turning counterclockwise in the second T.

Sample Input 6

TTTT
1 0

Sample Output 6

No



Sample input:
FTFFTFFF
4 2


Sample output:
Yes

Submission status: Memory Limit Exceeded

Solution code:
S = list(input())
x, y = map(int, input().split())
c = 0
p = 0
q = 0
now = 0
R = []
L = []
for i in range(len(S)):
    if S[i] == "T":
        if p != 0:
            R.append(p)
            p = 0
        elif q != 0:
            L.append(q)
            q = 0
        c += 1
    elif c == 0:
        now += 1
    elif c % 2 == 0:
        p += 1
    else:
        q += 1
if p != 0:
    R.append(p)
if q != 0:
    L.append(q)

dp_x = [[0]*20000 for _ in range(len(R)+2)]
dp_y = [[0]*20000 for _ in range(len(L)+1)]
c = 0
dp_x[0][8000] = 1
dp_y[0][8000] = 1
for i in range(1, len(R)+2):
    for j in range(16001):
        if i == 1:
            if j - now >= 0:
                if dp_x[i-1][j-now] == 1:
                    dp_x[i][j] = 1
        else:
            if j - R[i-2] >= 0:
                if dp_x[i-1][j-R[i-2]] == 1:
                    dp_x[i][j] = 1
            if j + R[i-2] <= 16001:
                if dp_x[i-1][j+R[i-2]] == 1:
                    dp_x[i][j] = 1

for i in range(1, len(L)+1):
    for j in range(16001):
        if j - L[i-1] >= 0:
            if dp_y[i-1][j-L[i-1]] == 1:
                dp_y[i][j] = 1
        if j + L[i-1] <= 16001:
            if dp_y[i-1][j+L[i-1]] == 1:
                dp_y[i][j] = 1

if dp_x[len(R)+1][x+8000] == 1 and dp_y[len(L)][y+8000] == 1:
    print("Yes")
else:
    print("No")

Submission status: Memory Limit Exceeded

Solution code:
s=input()+'T'
x,y=list(map(int,input().split()))
x+=8000
y+=8000
n=len(s)
i=0

while i<n and s[i]=='F':
    i+=1

dx=[[0]*16001 for _ in range(4001)]
dy=[[0]*16001 for _ in range(4001)]

dx[0][i+8000]=1
dy[0][8000]=1

lstx=[]
lsty=[]
d='x'
cnt=0

while i<n:
    if s[i]=='F':
        cnt+=1
    else:
        if cnt>0:
            if d=='x':
                lstx.append(cnt)
            else:
                lsty.append(cnt)
        
        if d=='x':
            d='y'
        else:
            d='x'
        cnt=0
    
    i+=1

for i,cx in enumerate(lstx):
    for j in range(16001):
        if dx[i][j]==0:
            continue
        if j+cx<16001:
            dx[i+1][j+cx]=1
        if j-cx>-1:
            dx[i+1][j-cx]=1

for i,cy in enumerate(lsty):
    for j in range(16001):
        if dy[i][j]==0:
            continue
        if j+cy<16001:
            dy[i+1][j+cy]=1
        if j-cy>-1:
            dy[i+1][j-cy]=1

if dx[len(lstx)][x]==1 and dy[len(lsty)][y]==1:
    print('Yes')
else:
    print('No')

Submission status: Memory Limit Exceeded

Solution code:
s=input()
x,y=map(int,input().split())
t=s.split("T")
x-=len(t[0])
dx,dy=[],[]

for i,tt in enumerate(t[1:]):
  ttt=len(tt)
  if i%2==1:
    dx.append(ttt)
  else:
    dy.append(ttt)
x=abs(x)
y=abs(y)
if max(x,y)>8000:
  print("No")
  exit(0)
def is_ok(n,mode):
  if mode=="x":
    l=dx
  else:
    l=dy
  nn=len(l)
  dp=[[0]*16001 for _ in range(nn+1)]
  n+=8000
  dp[0][8000]=1
  for i in range(1,nn+1):
    for j in range(16001):
      t=l[i-1]
      if j+t<=16000:
        dp[i][j+t]|=dp[i-1][j]
      if j-t>=0:
        dp[i][j-t]|=dp[i-1][j]
  if dp[nn][n]==1:
    return True
  else:
    return False

if is_ok(x,"x") and is_ok(y,"y"):
  print("Yes")
else:
  print("No")

Submission status: Memory Limit Exceeded

Solution code:
s=input()
x,y=map(int,input().split())
t=s.split("T")
x-=len(t[0])
dx,dy=[],[]

for i,tt in enumerate(t[1:]):
  ttt=len(tt)
  if i%2==1:
    dx.append(ttt)
  else:
    dy.append(ttt)
x=abs(x)
y=abs(y)
if max(x,y)>8000:
  print("No")
  exit(0)
def is_ok(n,mode):
  if mode=="x":
    l=dx
  else:
    l=dy
  nn=len(l)
  dp=[[0]*16001 for _ in range(nn+1)]
  n+=8000
  dp[0][8000]=1
  for i in range(1,nn+1):
    for j in range(16001):
      t=l[i-1]
      if j+l[i-1]<=16000:
        dp[i][j+t]|=dp[i-1][j]
      if j-l[i-1]>=0:
        dp[i][j-t]|=dp[i-1][j]
  if dp[nn][n]==1:
    return True
  else:
    return False

if is_ok(x,"x") and is_ok(y,"y"):
  print("Yes")
else:
  print("No")

Submission status: Memory Limit Exceeded

Solution code:
s=input()
x,y=map(int,input().split())
t=s.split("T")
x-=len(t[0])
dx,dy=[],[]

for i,tt in enumerate(t[1:]):
  if i%2==1:
    dx.append(len(tt))
  else:
    dy.append(len(tt))
x=abs(x)
y=abs(y)
if max(x,y)>8000:
  print("No")
  exit(0)
def is_ok(n,l):
  nn=len(l)
  dp=[[0]*16001 for _ in range(nn+1)]
  n+=8000
  dp[0][8000]=1
  for i in range(1,nn+1):
    for j in range(16001):
      t=l[i-1]
      if j+l[i-1]<=16000:
        dp[i][j+t]|=dp[i-1][j]
      if j-l[i-1]>=0:
        dp[i][j-t]|=dp[i-1][j]
  if dp[nn][n]==1:
    return True
  else:
    return False

if is_ok(abs(x),dx) and is_ok(abs(y),dy):
  print("Yes")
else:
  print("No")

Submission status: Memory Limit Exceeded

Solution code:
s=input()
x,y=map(int,input().split())
t=s.split("T")
x-=len(t[0])
dx,dy=[],[]

for i,tt in enumerate(t[1:]):
  if i%2==1:
    dx.append(len(tt))
  else:
    dy.append(len(tt))
x=abs(x)
y=abs(y)
if max(x,y)>8000:
  print("No")
  exit(0)
def is_ok(n,l):
  dp=[[0]*16001 for _ in range(len(l)+1)]
  n+=8000
  dp[0][8000]=1
  for i in range(1,len(l)+1):
    for j in range(16001):
      if j+l[i-1]<=16000:
        dp[i][j+l[i-1]]|=dp[i-1][j]
      if j-l[i-1]>=0:
        dp[i][j-l[i-1]]|=dp[i-1][j]
  if dp[len(l)][n]==1:
    return True
  else:
    return False

if is_ok(abs(x),dx) and is_ok(abs(y),dy):
  print("Yes")
else:
  print("No")

Submission status: Memory Limit Exceeded

Solution code:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
from itertools import groupby
import sys
M = 8000
M2 = M * 2
def main(s, x, y):
    g = [x, y]
    o = [[], []]

    direction = count = 0
    first = True
    for c in s:
        if c == 'T':
            if first:
                g[0] -= count
                first = False
            elif count > 0:
                o[direction].append(count)
            count = 0
            direction ^= 1
        else:
            count += 1
    if first:
        g[0] -= count
    elif count > 0:
        o[direction].append(count)

    for d in range(2):
        l = o[d]
        dp = [[False] * (M2 + 1) for _ in range(len(l) + 1)]
        dp[0][M] = True
        for i, v in enumerate(l):
            for a in range(M2 + 1):
                if dp[i][a] == False: continue
                if a >= v:
                    dp[i + 1][a - v] = True
                if a + v <= M2:
                    dp[i + 1][a + v] = True
        if dp[len(l)][g[d] + M] == False:
            print('No')
            return
    print('Yes')

if __name__ == '__main__':
    input = sys.stdin.readline
    s = input().rstrip()
    x, y = map(int, input().split())
    main(s, x, y)

Submission status: Memory Limit Exceeded

Solution code:
import sys
# input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
MOD = 10 ** 9 + 7


S = list(input())
x, y = map(int, input().split())

N = 8010

X = [0]
Y = [0]
flag = True
for s in S:
    if s == 'F':
        if flag:
            X[-1] += 1
        else:
            Y[-1] += 1
    else:
        if flag:
            if Y[-1] != 0:
                Y.append(0)
        else:
            if X[-1] != 0:
                X.append(0)
        flag = not flag

dp = [[0] * (2 * N) for _ in range(len(X))]
if S[0] == 'F':
    dp[0][X[0] + N] = 1
else:
    dp[0][X[0] + N] = 1
    dp[0][-X[0] + N] = 1

for i in range(1, len(X)):
    x_ = X[i]
    for j in range(2 * N):
        if j >= x_:
            if dp[i - 1][j - x_]:
                dp[i][j] = 1
        if j + x_ < 2 * N:
            if dp[i - 1][j + x_]:
                dp[i][j] = 1

# print (dp)
if dp[-1][x + N] == 0:
    print ('No')
    exit()

dp = [[0] * (2 * N) for _ in range(len(Y))]
dp[0][Y[0] + N] = 1
dp[0][-Y[0] + N] = 1

for i in range(1, len(Y)):
    y_ = Y[i]
    for j in range(2 * N):
        if j >= y_:
            if dp[i - 1][j - y_]:
                dp[i][j] = 1
        if j + y_ < 2 * N:
            if dp[i - 1][j + y_]:
                dp[i][j] = 1

if dp[-1][y + N] == 0:
    print ('No')
    exit()

print ('Yes')

Submission status: Memory Limit Exceeded

Solution code:
import sys
import itertools
from itertools import accumulate
def main():
    import itertools
    def eratosthenes_sieve(n):
        table = [0] * (n + 1)
        prime_list = []
        for i in range(2, n + 1):
            if table[i] == 0:
                prime_list.append(i)
                for j in range(i + i, n + 1, i):
                    table[j] = 1
        return prime_list
        def inputs():return (int(x) for x in input().split())
    input = sys.stdin.readline
    def inputs():
        return [int(x) for x in input().split()]
    S = input()
    x,y=inputs()
    cnt=0
    s =[]
    if S[0]=="T":
        s.append(0)
        cnt+=1
    else:
        cnt+=1
    for i in range(len(S)-2):
        if S[i]==S[i+1]:
            cnt+=1
        else:
            s.append(cnt)
            cnt=1
    s.append(cnt)
    flag=1
    x1 = []
    y1 = []
    for i in range(len(s)):
        if i%2==0:
            if flag==1:
              if i!=0:
                x1.append(s[i])
            else:
                y1.append(s[i])
        else:
            flag=(flag+s[i])%2
    x2 = sum(x1)+s[0]
    y2= sum(y1)
    m = max(x2,y2,len(S))
    dpx=[[-1]*(m*2+5) for i in range(len(x1)+1)]
    dpx[0][m+s[0]]=1
    dpy =[[-1]*(m*2+5) for i in range(len(y1)+1)]
    dpy[0][m]=1
    for i in range(len(x1)):
        for j in range(m*2):
          if dpx[i][j]!=-1:
            if j+x1[i]<=(m)*2:
                dpx[i+1][j+x1[i]]=1
            if j-x1[i]>=0:
                dpx[i+1][j-x1[i]]=1      
    for i in range(len(y1)):
        for j in range(m*2):
          if dpy[i][j]!=-1:
            if j+y1[i]<=m*2:
                dpy[i+1][j+y1[i]]=1
                #print(j+y1[i])
            if j-y1[i]>=0:
                dpy[i+1][j-y1[i]]=1
                #print(j-y1[i])
    if dpx[len(x1)][m+x]==1 and dpy[len(y1)][m+y]==1:
        print("Yes")
    else:
        print("No")
main()

Submission status: Memory Limit Exceeded

Solution code:
import sys
import itertools
from itertools import accumulate
def main():
    import itertools
    def eratosthenes_sieve(n):
        table = [0] * (n + 1)
        prime_list = []
        for i in range(2, n + 1):
            if table[i] == 0:
                prime_list.append(i)
                for j in range(i + i, n + 1, i):
                    table[j] = 1
        return prime_list
        def inputs():return (int(x) for x in input().split())
    input = sys.stdin.readline
    def inputs():
        return [int(x) for x in input().split()]
    S = list(input())
    x,y=inputs()
    cnt=0
    s =[]
    if S[0]=="T":
        s.append(0)
        cnt+=1
    else:
        cnt+=1
    for i in range(len(S)-2):
        if S[i]==S[i+1]:
            cnt+=1
        else:
            s.append(cnt)
            cnt=1
    s.append(cnt)
    #print(s)
    flag=1
    x1 = []
    y1 = []
    ansx=s[0]
    ansy=0
    flagx=0
    flagy= 0
    for i in range(len(s)):
        if i%2==0:
            if flag==1:
              if i!=0:
                x1.append(s[i])
            else:
                y1.append(s[i])
        else:
            flag=(flag+s[i])%2
    dpx=[[-1]*(16001) for i in range(len(x1)+1)]
    dpx[0][8000+s[0]]=1
    dpy =[[-1]*(16001) for i in range(len(y1)+1)]
    dpy[0][8000]=1
    for i in range(len(x1)):
        for j in range(16000):
            if j+x1[i]<=16000 and dpx[i][j]!=-1:
                dpx[i+1][j+x1[i]]=1
            if j-x1[i]>=0 and dpx[i][j]!=-1:
                dpx[i+1][j-x1[i]]=1      
    for i in range(len(y1)):
        for j in range(16000):
            if j+y1[i]<=16000 and dpy[i][j]!=-1:
                dpy[i+1][j+y1[i]]=1
                #print(j+y1[i])
            if j-y1[i]>=0 and dpy[i][j]!=-1:
                dpy[i+1][j-y1[i]]=1
                #print(j-y1[i])
    
    if dpx[len(x1)][8000+x]==1 and dpy[len(y1)][8000+y]==1:
        print("Yes")
    else:
        print("No")
main()

Submission status: Memory Limit Exceeded

Solution code:
s = input()
x,y = map(int,input().split())
k = 0
data = [[],[]]
f = 0
p = 1
for s_ in s:
    if p==1 and s_=='F':
        x -= 1
        continue
    p = 0
    if s_ == 'T':
        if f:
            data[k].append(f)
        k = (k+1)%2
        f = 0
    else:
        f += 1
if f:
    data[k].append(f)

nx = sum(data[0])
ny = sum(data[1])

if nx<x or ny<y:
    print('No')
    exit()

dpx = [[0]*16001 for _ in range(len(data[0])+1)]
dpy = [[0]*16001 for _ in range(len(data[1])+1)]
x_zero = 8001
y_zero = 8001
dpx[0][x_zero] = 1
dpy[0][y_zero] = 1

for i in range(len(data[0])):
    for j in range(len(dpx[i])):
        if dpx[i][j]==1:
            dpx[i+1][j+data[0][i]] = 1
            dpx[i+1][j-data[0][i]] = 1

for i in range(len(data[1])):
    for j in range(len(dpy[i])):
        if dpy[i][j]==1:
            dpy[i+1][j+data[1][i]] = 1
            dpy[i+1][j-data[1][i]] = 1
if dpx[-1][x_zero+x]==1 and dpy[-1][y_zero+y]==1:
    print('Yes')
else:
    print('No')

Submission status: Memory Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

"""
参考：https://img.atcoder.jp/abc082/editorial.pdf
　　　https://atcoder.jp/contests/abc082/submissions/3930644
・メモリ節約のため、dictをsetにした。
"""

S = input()
X, Y = map(int, input().split())

S2 = []
tmp = 0
# 連続するF毎にまとまるように文字列Sを変形させる
for i in range(len(S)):
    if S[i] == 'F':
        tmp += 1
    # T毎に区切る
    else:
        S2.append(tmp)
        tmp = 0
S2.append(tmp)

# 文字列がFのみだとこの後のDPできないので別処理
if len(S2) == 1:
    if X == S2[0] and Y == 0:
        print('Yes')
    else:
        print('No')
    exit()

# あるかないか分かればいいので、dictじゃなくてsetにする
dpx = [set() for _ in range(len(S2))]
dpy = [set() for _ in range(len(S2))]
# xの初期化：step0は右移動、step1ではそのまま
dpx[0].add(S2[0])
dpx[1].add(S2[0])
# yの初期化：step0は何もなし、step1で上下どちらかに移動
dpy[0].add(0)
dpy[1].add(S2[1])
dpy[1].add(-S2[1])
for i in range(2, len(S2)):
    # 左右に移動する
    for v in dpx[i-1]:
        if i % 2 == 0:
            # 到達可能な位置から+-した位置に送る
            dpx[i].add(v-S2[i])
            dpx[i].add(v+S2[i])
        else:
            # yをやる時はxはそのまま
            dpx[i].add(v)
    # 上下に移動する
    for v in dpy[i-1]:
        if i % 2 == 1:
            dpy[i].add(v-S2[i])
            dpy[i].add(v+S2[i])
        else:
            dpy[i].add(v)
# 最後のstepでXとYが到達可能ならOK
if X in dpx[len(S2)-1] and Y in dpy[len(S2)-1]:
    print('Yes')
else:
    print('No')

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    S = input().split('T')
    x, y = map(int, input().split())

    X = []
    Y = []
    flag = 0
    for s in S:
        if flag == 0:
            X.append(len(s))
        else:
            Y.append(len(s))
        flag ^= 1

    A = set()
    A.add(X[0])
    for i in X[1:]:
        tmp = set()
        for a in A:
            tmp.add(a + i)
            tmp.add(a - i)
        A = tmp

    B = set()
    B.add(0)
    for j in Y:
        tmp = set()
        for b in B:
            tmp.add(b + j)
            tmp.add(b - j)
        B = tmp

    if x in A and y in B:
        print('Yes')
    else:
        print('No')


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
s = input()
x, y = map(int, input().split())

# Tで区切り、各Tの前にFが何文字あるか数える
steps = []
cnt = 0
for i in range(len(s)):
    if s[i] == "F":
        cnt += 1
    elif s[i] == "T":
        steps.append(cnt)
        cnt = 0
# 最後のブロックについて
if cnt > 0:
    steps.append(cnt)

step_X = steps[0::2]
step_Y = steps[1::2]

# X軸方向の最大値
max_X = sum(step_X)
# dp_X[i][j] = X軸方向の移動をi回行って、jに到達できるか
# j = 0, 1, ..., 2*max_X だが、実際のX座標は -max_X, ..., 0, ..., max_X
# 原点(x=0)は、j = max_Xに相当する
dp_X = [[0 for _ in range(2 * max_X + 1)] for _ in range(len(step_X) + 1)]
dp_X[0][max_X] = 1
# 最初に右へ移動する場合
if s[0] == "F":
    dp_X[1][max_X + step_X[0]] = 1
    for i in range(1, len(step_X)):
        for j in range(2 * max_X + 1):
            if dp_X[i][j] == 1:
                # +X方向に移動
                if j + step_X[i] <= 2 * max_X:
                    dp_X[i + 1][j + step_X[i]] = 1
                # -X方向に移動
                if 0 <= j - step_X[i]:
                    dp_X[i + 1][j - step_X[i]] = 1
# 最初に回転する場合
else:
    for i in range(len(step_X)):
        for j in range(2 * max_X + 1):
            if dp_X[i][j] == 1:
                # +X方向に移動
                if j + step_X[i] <= 2 * max_X:
                    dp_X[i + 1][j + step_X[i]] = 1
                # -X方向に移動
                if 0 <= j - step_X[i]:
                    dp_X[i + 1][j - step_X[i]] = 1

# Y軸方向の最大値
max_Y = sum(step_Y)
# dp_Y[i][j] = Y軸方向の移動をi回行って、jに到達できるか
# j = 0, 1, ..., 2*max_Y だが、実際のY座標は -max_Y, ..., 0, ..., max_Y
# 原点(y=0)は、j = max_Yに相当する
dp_Y = [[0 for _ in range(2 * max_Y + 1)] for _ in range(len(step_Y) + 1)]
dp_Y[0][max_Y] = 1
for i in range(len(step_Y)):
    for j in range(2 * max_Y + 1):
        if dp_Y[i][j] == 1:
            # +Y方向に移動
            if j + step_Y[i] <= 2 * max_Y:
                dp_Y[i + 1][j + step_Y[i]] = 1
            # -Y方向に移動
            if 0 <= j - step_Y[i]:
                dp_Y[i + 1][j - step_Y[i]] = 1

if -max_X <= x <= max_X and -max_Y <= y <= max_Y:
    if dp_X[-1][x + max_X] == 1 and dp_Y[-1][y + max_Y] == 1:
        print("Yes")
        exit()
print("No")

Submission status: Accepted

Solution code:
def YesNo(b):
    print("Yes" if b else "No")


def solve(l, t0, t):
    s = {t0}
    for v in l:
        s, ps = set(), s
        for a in ps:
            s.add(a+v)
            s.add(a-v)
    return t in s


s = input()
x, y = map(int, input().split())

f = s.split('T')
x0 = len(f[0])
xl = [len(v) for v in f[2::2]]
yl = [len(v) for v in f[1::2]]

YesNo(solve(xl, x0, x) and solve(yl, 0, y))

Submission status: Accepted

Solution code:

def YesNo(b):
    print("Yes" if b else "No")


def solve(v, l, ini):
    ml = 8000*2+1
    dp = [[False]*ml for i in range(len(l)+1)]
    for i in range(len(ini)):
        dp[0][ini[i]+8000] = True
    for i in range(1, len(l)+1):
        for j in range(ml):
            if (j+l[i-1]) < ml and dp[i-1][j]:
                dp[i][j+l[i-1]] = True
            if (j-l[i-1]) >= 0 and dp[i-1][j]:
                dp[i][j-l[i-1]] = True
    return dp[len(l)][v+8000]


s = input()
x, y = map(int, input().split())
si = 0
while si < len(s) and s[si] == 'F':
    si += 1

s = s[si:]
if len(s) == 0:
    YesNo(x == si and y == 0)
else:
    f = s.split('T')[1:]
    xl, yl = [0], [0]
    for i in range(len(f)):
        if len(f[i]) == 0:
            continue
        if i % 2 == 0:
            yl.append(len(f[i]))
        else:
            xl.append(len(f[i]))

    YesNo(solve(x, xl, [si]) and solve(y, yl[1:], [-yl[0], yl[0]]))

Submission status: Accepted

Solution code:
s = input().strip()
x,y = map(int,input().split())
AX = []
AY = []
flag = 0
cnt = 0
for i in range(len(s)):
    if s[i]=="F":
        cnt += 1
    else:
        if flag==0:
            if cnt>0:
                AX.append(cnt)
                cnt = 0
            flag = 1
        else:
            if cnt>0:
                AY.append(cnt)
                cnt = 0
            flag = 0
if cnt>0 and flag==0:
    AX.append(cnt)
if cnt>0 and flag==1:
    AY.append(cnt)
Nx = sum(AX)
dpX = [[0 for _ in range(2*Nx+1)] for _ in range(len(AX)+1)]
dpX[0][Nx] = 1
if s[0]=="F":
    dpX[1][Nx+AX[0]] = 1
    for i in range(1,len(AX)):
        for j in range(2*Nx+1):
            if j+AX[i]<=2*Nx:
                dpX[i+1][j+AX[i]] = dpX[i+1][j+AX[i]] or dpX[i][j]
            if 0<=j-AX[i]:
                dpX[i+1][j-AX[i]] = dpX[i+1][j-AX[i]] or dpX[i][j]
else:
    for i in range(len(AX)):
        for j in range(2*Nx+1):
            if j+AX[i]<=2*Nx:
                dpX[i+1][j+AX[i]] = dpX[i+1][j+AX[i]] or dpX[i][j]
            if 0<=j-AX[i]:
                dpX[i+1][j-AX[i]] = dpX[i+1][j-AX[i]] or dpX[i][j]
Ny = sum(AY)
dpY = [[0 for _ in range(2*Ny+1)] for _ in range(len(AY)+1)]
dpY[0][Ny] = 1
for i in range(len(AY)):
    for j in range(2*Ny+1):
        if j+AY[i]<=2*Ny:
            dpY[i+1][j+AY[i]] = dpY[i+1][j+AY[i]] or dpY[i][j]
        if 0<=j-AY[i]:
            dpY[i+1][j-AY[i]] = dpY[i+1][j-AY[i]] or dpY[i][j]
if Nx==0 and x!=0 or Ny==0 and y!=0:
    print("No")
elif abs(x)>Nx or abs(y)>Ny:
    print("No")
elif dpX[len(AX)][Nx+x]==1 and dpY[len(AY)][Ny+y]==1:
    print("Yes")
else:
    print("No")

Submission status: Accepted

Solution code:
s = str(input()); n = len(s)
gx,gy = map(int,input().split())
Yoko = []; Tate = []
Flag = 0; cnt = 0
Max_x = 0; Max_y = 0
for i in range(n):
  if s[i] == "F":
    cnt += 1
    if i == n-1: #最後なら登録
      if Flag == 0:
        Max_x += cnt
        Yoko.append(cnt)
      else:
        Max_y += cnt
        Tate.append(cnt)      
  else: #T
    if Flag == 0:
      Max_x += cnt
      Yoko.append(cnt)
    else:
      Max_y += cnt
      Tate.append(cnt)
    cnt = 0
    Flag = Flag^1
#print(Yoko,Tate)
MAX_dpx = Max_x*2+1
dp = [0 for _ in range(MAX_dpx)]
dp[Max_x] = 1

for i,x in enumerate(Yoko):
  p = [0 for _ in range(MAX_dpx)]
  p,dp = dp,p
  for j in range(MAX_dpx):
    if i == 0: #i=0の時は右向きだけ
      if 0<=j+x<MAX_dpx:
        dp[j+x] = max(dp[j+x], p[j])
    else:
      if 0<=j+x<MAX_dpx:
        dp[j+x] = max(dp[j+x], p[j])
      if 0<=j-x<MAX_dpx:
        dp[j-x] = max(dp[j-x], p[j])
  #print(dp)
#print(dp)
#print(gx+Max_x,MAX_dpx)
if gx+Max_x >= MAX_dpx or gx+Max_x < 0 or dp[gx+Max_x] == 0:
  print("No");exit()

MAX_dpy = Max_y*2+1
dp = [0 for _ in range(MAX_dpy)]
dp[Max_y] = 1

for i,y in enumerate(Tate):
  p = [0 for _ in range(MAX_dpy)]
  p,dp = dp,p
  for j in range(MAX_dpy):
    if 0<=j+y<MAX_dpy:
      dp[j+y] = max(dp[j+y], p[j])
    if 0<=j-y<MAX_dpy:
      dp[j-y] = max(dp[j-y], p[j])
  #print(dp)
#print(dp)
if gy+Max_y >= MAX_dpy or gy+Max_y < 0 or dp[gy+Max_y] == 0:
  print("No")
else:
  print("Yes")

Submission status: Accepted

Solution code:
import sys
S = list(input())
x, y = map(int, input().split())
c = 0
p = 0
q = 0
now = 0
R = []
L = []
for i in range(len(S)):
    if S[i] == "T":
        if p != 0:
            R.append(p)
            p = 0
        elif q != 0:
            L.append(q)
            q = 0
        c += 1
    elif c == 0:
        now += 1
    elif c % 2 == 0:
        p += 1
    else:
        q += 1
if p != 0:
    R.append(p)
if q != 0:
    L.append(q)

A = 2*(sum(R)+now)
B = 2*(sum(L))
dp_x = [[0]*(A+2) for _ in range(len(R)+2)]
dp_y = [[0]*(B+2) for _ in range(len(L)+1)]
c = 0
dp_x[0][sum(R)+now] = 1
dp_y[0][sum(L)] = 1
for i in range(1, len(R)+2):
    for j in range(A+2):
        if i == 1:
            if j - now >= 0:
                if dp_x[i-1][j-now] == 1:
                    dp_x[i][j] = 1
        else:
            if j - R[i-2] >= 0:
                if dp_x[i-1][j-R[i-2]] == 1:
                    dp_x[i][j] = 1
            if j + R[i-2] <= A+1:
                if dp_x[i-1][j+R[i-2]] == 1:
                    dp_x[i][j] = 1

for i in range(1, len(L)+1):
    for j in range(B+2):
        if j - L[i-1] >= 0:
            if dp_y[i-1][j-L[i-1]] == 1:
                dp_y[i][j] = 1
        if j + L[i-1] <= B+1:
            if dp_y[i-1][j+L[i-1]] == 1:
                dp_y[i][j] = 1

if A + 1 < x+sum(R)+now or x+sum(R)+now < 0:
    print("No")
    sys.exit()

if B + 1 < y+sum(L) or y+sum(L) < 0:
    print("No")
    sys.exit()

if dp_x[len(R)+1][x+sum(R)+now] == 1 and dp_y[len(L)][y+sum(L)] == 1:
    print("Yes")
else:
    print("No")

Submission status: Accepted

Solution code:
import numpy as np
MOD = 10**9 + 7

def fft_convolve(f, g):
  Lf, Lg = f.shape[-1], g.shape[-1]
  L = Lf + Lg - 1
  fft_len = 1 << L.bit_length()
  fh, fl = f >> 15, f & (1 << 15) - 1
  gh, gl = g >> 15, g & (1 << 15) - 1
  def conv(f, g):
    Ff = np.fft.rfft(f, fft_len)
    Fg = np.fft.rfft(g, fft_len)
    h = np.fft.irfft(Ff * Fg)
    return np.rint(h)[..., :L].astype(np.int64) % MOD
  x = conv(fl, gl)
  z = conv(fh, gh)
  y = conv(fl + fh, gl + gh) - x - z
  return (x + (y << 15) + (z << 30)) % MOD

s = input()
x, y = map(int, input().split())

Rob = list(s.split("T"))

X = [len(r) for r in Rob[::2]]
Y = [len(r) for r in Rob[1::2]]

Xst = X[0]
X = X[1:]

if abs(x-Xst) <= sum(X) and abs(y) <= sum(Y):
  f = np.array([1], np.int64)
  for i in X:
    L = [0]*(2*i+1)
    L[0], L[-1] = 1, 1
    f = np.convolve(f, np.array(L, np.int64))
  FlagX = f[abs(x-Xst)+sum(X)]

  g = np.array([1], np.int64)
  for j in Y:
    L = [0]*(2*j+1)
    L[0], L[-1] = 1, 1
    g = np.convolve(g, np.array(L, np.int64))
  FlagY = g[abs(y)+sum(Y)]

  if FlagX and FlagY:
    print("Yes")
  else:
    print("No")
else:
  print("No")

Submission status: Accepted

Solution code:
import numpy as np
MOD = 10**9 + 7

def fft_convolve(f, g):
  Lf, Lg = f.shape[-1], g.shape[-1]
  L = Lf + Lg - 1
  fft_len = 1 << L.bit_length()
  fh, fl = f >> 15, f & (1 << 15) - 1
  gh, gl = g >> 15, g & (1 << 15) - 1
  def conv(f, g):
    Ff = np.fft.rfft(f, fft_len)
    Fg = np.fft.rfft(g, fft_len)
    h = np.fft.irfft(Ff * Fg)
    return np.rint(h)[..., :L].astype(np.int64) % MOD
  x = conv(fl, gl)
  z = conv(fh, gh)
  y = conv(fl + fh, gl + gh) - x - z
  return (x + (y << 15) + (z << 30)) % MOD

s = input()
x, y = map(int, input().split())

Rob = list(s.split("T"))

X = [len(r) for r in Rob[::2]]
Y = [len(r) for r in Rob[1::2]]

def solve():
  global X
  Xst = X[0]
  X = X[1:]
  if abs(x-Xst) <= sum(X) and abs(y) <= sum(Y):
    f = np.array([1], np.int64)
    for i in X:
      L = [0]*(2*i+1)
      L[0], L[-1] = 1, 1
      f = np.convolve(f, np.array(L, np.int64))
    FlagX = f[abs(x-Xst)+sum(X)]
    g = np.array([1], np.int64)
    for j in Y:
      L = [0]*(2*j+1)
      L[0], L[-1] = 1, 1
      g = np.convolve(g, np.array(L, np.int64))
    FlagY = g[abs(y)+sum(Y)]
    if FlagX and FlagY:
      print("Yes")
    else:
      print("No")
  else:
    print("No")

solve()

Submission status: Accepted

Solution code:
import numpy as np
MOD = 10**9 + 7

def fft_convolve(f, g):
  Lf, Lg = f.shape[-1], g.shape[-1]
  L = Lf + Lg - 1
  fft_len = 1 << L.bit_length()
  fh, fl = f >> 15, f & (1 << 15) - 1
  gh, gl = g >> 15, g & (1 << 15) - 1
  def conv(f, g):
    Ff = np.fft.rfft(f, fft_len)
    Fg = np.fft.rfft(g, fft_len)
    h = np.fft.irfft(Ff * Fg)
    return np.rint(h)[..., :L].astype(np.int64) % MOD
  x = conv(fl, gl)
  z = conv(fh, gh)
  y = conv(fl + fh, gl + gh) - x - z
  return (x + (y << 15) + (z << 30)) % MOD

s = input()
x, y = map(int, input().split())

Rob = list(s.split("T"))

X = [len(r) for r in Rob[::2]]
Y = [len(r) for r in Rob[1::2]]

if x < 0:
  y = abs(y)
  Xst = X[0]
  X = sorted(X[1:])
  if abs(x-Xst) <= sum(X) and y <= sum(Y):
    f = np.array([1], np.int64)
    for i in X:
      L = [0]*(2*i+1)
      L[0], L[-1] = 1, 1
      f = np.convolve(f, np.array(L, np.int64))
    FlagX = f[abs(x-Xst)+sum(X)]
    g = np.array([1], np.int64)
    for j in Y:
      L = [0]*(2*j+1)
      L[0], L[-1] = 1, 1
      g = np.convolve(g, np.array(L, np.int64))
    FlagY = g[y+sum(Y)]
    if FlagX and FlagY:
      print("Yes")
    else:
      print("No")
  else:
    print("No")
else:
  x, y = abs(x), abs(y)
  if x <= sum(X) and y <= sum(Y):
    f = np.array([1], np.int64)
    for i in X:
      L = [0]*(2*i+1)
      L[0], L[-1] = 1, 1
      f = np.convolve(f, np.array(L, np.int64))
    FlagX = f[x+sum(X)]
    g = np.array([1], np.int64)
    for j in Y:
      L = [0]*(2*j+1)
      L[0], L[-1] = 1, 1
      g = np.convolve(g, np.array(L, np.int64))
    FlagY = g[y+sum(Y)]
    if FlagX and FlagY:
      print("Yes")
    else:
      print("No")
  else:
    print("No")

Submission status: Accepted

Solution code:
from collections import defaultdict
def main():
    S = input() + 'T'
    x, y = map(int, input().split())
    #データ加工
    moveX, moveY = [], []
    if S[0] == 'T': moveX.append(0)
    move ={0:moveX, 1:moveY}
    direct = 0
    step = 0
    for s in S:
        if s == 'T':
            if step > 0:
                move[direct].append(step)
                step = 0
            direct ^= 1 
        else:
            step += 1
    #判定
    if possible(x, moveX[1:], moveX[0]) and possible(y, moveY):
        print('Yes')
    else:
        print('No')


def possible(target, move, offset=0):
    l = len(move)
    dp = [defaultdict(lambda:False) for _ in range(l+1)]
    #初期化
    dp[0][0] = True
    for i,m in enumerate(move):
        for key in dp[i]:
            dp[i+1][key+m] = True
            dp[i+1][key-m] = True
    return dp[l][target-offset]


main()

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    S = readline().strip()
    x, y = map(int, readline().split())

    S = S.split('T')
    x0 = len(S[0])
    X = [len(s) for s in S[2::2]]
    Y = [len(s) for s in S[1::2]]

    def solve(vec, p0, p):
        s = {p0}
        for v in vec:
            s, s_prev = set(), s
            for w in s_prev:
                s.add(w + v)
                s.add(w - v)
        return p in s

    if solve(X, x0, x) and solve(Y, 0, y):
        print('Yes')
    else:
        print('No')

    return


if __name__ == '__main__':
    main()