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: Accepted

Solution code:
# -*- coding: utf-8 -*-
def check(z, zz, z_list):
  if len(z_list) == 0:
    if z != zz:
      return 0
    else:
      return 1
  else:
    z_n = len(z_list)
    z_hash = {}
    z_hash[0] = {}
    z_hash[0][zz] = 1
    z_hash[z_n] = {}
    z_hash[z_n][z] = 1
    for i in range(0,z_n):
      if i+1 not in z_hash:
        z_hash[i+1] = {}
        for b_z in z_hash[i]:
          a_z = b_z + z_list[i]
          z_hash[i+1][a_z] = 1
          a_z = b_z - z_list[i]
          z_hash[i+1][a_z] = 1
      else:
        for b_z in z_hash[i]:
          a_z = b_z + z_list[i]
          if a_z in z_hash[i+1]:
            return 1
          a_z = b_z - z_list[i]
          if a_z in z_hash[i+1]:
            return 1
        return 0
      if z_n-i-1 not in z_hash:
        z_hash[z_n-i-1] = {}
        for a_z in z_hash[z_n-i]:
          b_z = a_z + z_list[z_n-i-1]
          z_hash[z_n-i-1][b_z] = 1
          b_z = a_z - z_list[z_n-i-1]
          z_hash[z_n-i-1][b_z] = 1
      else:
        for a_z in z_hash[z_n-i]:
          b_z = a_z + z_list[z_n-i-1]
          if b_z in z_hash[z_n-i-1]:
            return 1
          b_z = a_z - z_list[z_n-i-1]
          if b_z in z_hash[z_n-i-1]:
            return 1
        return 0



s = input()
x, y = map(int, input().split())
data = s.split("T")
xx, yy = 0, 0
i = 0
x_list = []
y_list = []
for Fs in data:
  if len(Fs) == 0:
    i += 1
  else:
    if i == 0:
      xx = len(Fs)
    elif i % 2 == 0:
      x_list.append(len(Fs))
    else:
      y_list.append(len(Fs))
    i += 1
if check(x, xx, x_list) == 1 and check(y, yy, y_list) == 1:
  print("Yes")
else:
  print("No")

Submission status: Accepted

Solution code:
s = input()
x,y = map(int,input().split(" "))
l = [len(c) for c in s.split("T")]
X = l[::2]
Y = l[1::2]
 
ansX = set([X[0]])
for i in range(1,len(X)):
    ansX = set([c+X[i] for c in ansX]+[c-X[i] for c in ansX])
 
ansY = set([0])
for i in range(0,len(Y)):
    ansY = set([c+Y[i] for c in ansY]+[c-Y[i] for c in ansY])
    
if x in ansX and y in ansY:
    print("Yes")
else:
    print("No")

Submission status: Accepted

Solution code:
#import numpy as np
import math
import sys
import itertools
MAX_INT = int(10e12)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

s = S()
x,y = IL()
N = len(s)

xlist = []
ylist = []

f = 0
cnt = 0
for i in range(N):
  if s[i] == "F":
    cnt += 1
  elif s[i] == "T":
    if f == 0:
      xlist.append(cnt)
      f = 1
    else:
      ylist.append(cnt)
      f = 0
    cnt = 0
else:
  if f == 0:
    xlist.append(cnt)
  else:
    ylist.append(cnt)

x -= xlist.pop(0)
Xsum = sum(xlist)
Ysum = sum(ylist)

if (Xsum-x)%2 != 0:
  print("No")
  exit()
else:
  Xnum = (Xsum-abs(x))//2
if (Ysum-y)%2 != 0:
  print("No")
  exit()
else:
  Ynum = (Ysum-abs(y))//2

#print(Xnum,Ynum)

XDP = [[0]*(abs(Xnum)+1) for _ in range(len(xlist)+1)]
YDP = [[0]*(abs(Ynum)+1) for _ in range(len(ylist)+1)]

XDP[0][0] = 1
YDP[0][0] = 1

for i in range(1,len(xlist)+1):
  for j in range(Xnum+1):
    if XDP[i-1][j] == 1:
      XDP[i][j] = 1
      if j+xlist[i-1] < Xnum+1:
        XDP[i][j+xlist[i-1]] = 1
#print(Xnum)
#print(xlist)
#print(XDP)

for i in range(1,len(ylist)+1):
  for j in range(Ynum+1):
    if YDP[i-1][j] == 1:
      YDP[i][j] = 1
      if j+ylist[i-1] < Ynum+1:
        YDP[i][j+ylist[i-1]] = 1
#print(Ynum)
#print(ylist)
#print(YDP)

if XDP[-1][-1] == 1 and YDP[-1][-1] == 1:
  print("Yes")
else:
  print("No")

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from functools import reduce


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007



s = S()
x, y = LI()
components = [len(i) for i in s.split('T')]
initial_x = components[0]
components = components[1:]
y_component = [j for j in components[::2] if j]
x_component = [j for j in components[1::2] if j]
x_len = len(x_component)
y_len = len(y_component)
x_D = defaultdict(int)
y_D = defaultdict(int)


x_D[initial_x] = 1
for i in range(x_len):
    nxt_x_D = defaultdict(int)
    for pos in x_D.keys():
        nxt_x_D[pos + x_component[i]] = nxt_x_D[pos - x_component[i]] = 1
    x_D = nxt_x_D


y_D[0] = 1
for i in range(y_len):
    nxt_y_D = defaultdict(int)
    for pos in y_D.keys():
        nxt_y_D[pos + y_component[i]] = nxt_y_D[pos - y_component[i]] = 1
    y_D = nxt_y_D



if x_D[x] and y_D[y]:
    print('Yes')
else:
    print('No')

Submission status: Accepted

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
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()))

s = input()
n = len(s)
x,y = LI()
lst = []
tmp = 0
for i in range(n):
    if s[i] == 'T':
        lst.append(tmp)
        tmp = 0
    else:
        tmp += 1
if s[-1] != 'T':
    lst.append(tmp)
m = len(lst)
dpx = defaultdict(int)
dpy = defaultdict(int)
dpx[0] = True
dpy[0] = True
for i in range(m):
    if i % 2:
        tmp = defaultdict(int)
        for k in dpy.keys():
            tmp[k + lst[i]] = True
            tmp[k - lst[i]] = True
        dpy = tmp
    else:
        tmp = defaultdict(int)
        if i == 0:
            for k in dpx.keys():
                tmp[k + lst[i]] = True
        else:
            for k in dpx.keys():
                tmp[k + lst[i]] = True
                tmp[k - lst[i]] = True
        dpx = tmp
if dpx[x] and dpy[y]:
    print('Yes')
else:
    print('No')

Submission status: Accepted

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

l=[0]
for i in s:
    if i=="F":
        l[-1]+=1
    else:
        l.append(0)
lx=[0]
ly=[0]
for i in range(len(l)):
    if i==0:
        continue
    if i%2==0:
        lx.append(l[i])
    else:
        ly.append(l[i])

q=[l[0]]
for i in lx:
    ll=set()
    for j in q:
        ll.add(j+i)
        ll.add(j-i)
    q=list(ll)
if x not in set(q):
    print("No")
    exit()

q=[0]
for i in ly:
    ll=set()
    for j in q:
        ll.add(j+i)
        ll.add(j-i)
    q=list(ll)
if y in set(q):
    print("Yes")
else:
    print("No")

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def main():
    S = list(input())
    X, Y = map(int, input().split())

    Xs = []
    Ys = []
    line = True
    first = True
    x0, y0 = 0, 0
    a = 0
    for s in S:
        if s == 'F':
            a += 1
        else:
            if first:
                if a > 0:
                    x0 = a
                a = 0
                first = False
                line = False
                continue
            if a > 0:
                if line:
                    Xs.append(a)
                else:
                    Ys.append(a)
                a = 0
            if line:
                line = False
            else:
                line = True
    if a > 0:
        if line:
            Xs.append(a)
        else:
            Ys.append(a)

    Lx = sum(Xs)+x0
    dpx = [[False for _ in range(2*Lx+1)] for _ in range(len(Xs)+1)]
    dpx[0][x0+Lx] = True

    for i, x in enumerate(Xs):
        for j in range(2*Lx+1):
            if j+x <= 2*Lx:
                dpx[i+1][j+x] = dpx[i][j] or dpx[i+1][j+x]
            if j-x >= 0:
                dpx[i+1][j-x] = dpx[i][j] or dpx[i+1][j-x]

    Ly = sum(Ys)+y0
    dpy = [[False for _ in range(2*Ly+1)] for _ in range(len(Ys)+1)]
    dpy[0][y0+Ly] = True

    for i, y in enumerate(Ys):
        for j in range(2*Ly+1):
            if j+y <= 2*Ly:
                dpy[i+1][j+y] = dpy[i][j] or dpy[i+1][j+y]
            if j-y >= 0:
                dpy[i+1][j-y] = dpy[i][j] or dpy[i+1][j-y]
    #print(Lx, Ly)
    if (not -Lx <= X <= Lx) or (not -Ly <= Y <= Ly): 
        print('No')
    elif dpx[-1][X+Lx] and dpy[-1][Y+Ly]:
        print('Yes')
    else:
        print('No')


if __name__ == "__main__":
    main()

Submission status: Accepted

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

D = [[], []]
st_x = 0
st_y = 0
st = 0
while st <= len(s)-1 and s[st] == "F":
    x -= 1
    st += 1

di = 0
for i in range(st, n):
    if s[i] == "T":
        di = (di+1) % 2
        D[di].append(0)
    else:
        D[di][-1] += 1

# print(D)


ANS = [0, 0]
st_po = [0, 0]
go_po = [x, y]
for i in range(2):
    mid = sum(D[i]) + 5
    DP = [[0] * (mid*2) for i in range(len(D[i]) + 1)]
    DP[0][st_po[i] + mid] = 1
    for j in range(len(D[i])):
        dd = D[i][j]
        for k in range(len(DP[0])):
            aa = 0
            bb = 0
            if 0 <= k-dd <= len(DP[0])-1:
                aa = DP[j][k-dd]
            if 0 <= k+dd <= len(DP[0])-1:
                bb = DP[j][k+dd]

            DP[j+1][k] = int(aa or bb)

    if 0 <= go_po[i]+mid <= len(DP[0])-1:
        ANS[i] = DP[-1][go_po[i]+mid]
    # print("len",mid*2)
    #if i == 1:
        # print(DP[1][7999+mid])
# print(ANS)

print("Yes" if ANS[0] and ANS[1] else "No")

Submission status: Accepted

Solution code:
s = input()
x, y = map(int, input().split())
l = s.split("T")
#print(l)
x -= len(l[0])
ys = []
xs = []
if len(l) == 1:
  if x == 0 and y == 0:
    print("Yes")
  else:
    print("No")
  exit(0)
for i in range(len(l)):
  if i == 0:
    continue
  if i % 2:
    ys.append(len(l[i]))
  else:
    xs.append(len(l[i]))
#移動しうるマスの総数はなんとか全列挙できるレベル
#先頭からi番目まで見たとき、移動可能であるマス
#何x何のDPなら追いつくのか考える
#bitDPするよりずっと現実的
#集合を使うと無駄なカウントがない
dpx = set()
dpx.add(0)
for i in range(len(xs)):
  nextset = set()
  for j in dpx:
    nextset.add(j + xs[i])
    nextset.add(j - xs[i])
  dpx = nextset
dpy = set()
dpy.add(0)
for i in range(len(ys)):
  nextset = set()
  for j in dpy:
    nextset.add(j + ys[i])
    nextset.add(j - ys[i])
  dpy = nextset
if x in dpx and y in dpy:
  print("Yes")
else:
  print("No")

Submission status: Accepted

Solution code:
s = input()
x,y = map(int,input().split())
 
X = []
Y = []
flag = 0
tmp = 0
for i in s:
    if i == "T":
        if flag == 0:
            if tmp != 0:
                X.append(tmp)
            flag = 1
            tmp = 0
        else:
            if tmp != 0:
                Y.append(tmp)
            flag = 0
            tmp = 0
    else:
        tmp += 1
if tmp != 0:
    if flag == 0:
        X.append(tmp)
    else:
        Y.append(tmp)

if s[0] !="T":
    tmpX = X[0]
    del X[0]
else:
    tmpX = 0

X = sorted(X)
Y = sorted(Y)
sumX = sum(X)
sumY = sum(Y)
tmpY = 0
 
ans = 0
 
if (x+sumX-tmpX)%2 == 1:
    ans = 1
else:
    mokuhyoX = (x+sumX-tmpX)//2
if (y+sumY-tmpY)%2 == 1:
    ans = 1
else:
    mokuhyoY = (y+sumY-tmpY)//2
if ans == 0:
	if mokuhyoX < 0 or mokuhyoY < 0:
	    ans = 1

# mokuhyoX
if ans == 0:
    dpX = [[False]*(mokuhyoX+1) for _ in range(len(X)+1)]
    dpX[0][0] = True
    for i in range(len(X)):
        for j in range(mokuhyoX+1):
            dpX[i+1][j] = dpX[i+1][j] or dpX[i][j]
            if j >= X[i]:
                dpX[i+1][j] = dpX[i+1][j] or dpX[i][j-X[i]]
    
    
# mokuhyoY
if ans == 0:
    dpY = [[False]*(mokuhyoY+1) for _ in range(len(Y)+1)]
    dpY[0][0] = True
    for i in range(len(Y)):
        for j in range(mokuhyoY+1):
            dpY[i+1][j] = dpY[i+1][j] or dpY[i][j]
            if j >= Y[i]:
                dpY[i+1][j] = dpY[i+1][j] or dpY[i][j-Y[i]]
 
if ans==0:
    if dpX[len(X)][mokuhyoX] == dpY[len(Y)][mokuhyoY] == True:
        ans = 0
    else:
        ans = 1
    
if ans == 1:
    print("No")
else:
    print("Yes")

Submission status: Accepted

Solution code:
s = input()
x,y = map(int,input().split())
wayx = []
wayy = []
pad = 15000
can_reachx = [False for i in range(pad*2+1)]
can_reachy = [False for i in range(pad*2+1)]


state = True
seq = 0
for c in s:
    if c == "T":
        if state:
            wayx.append(seq)
            seq = 0
            state = False
        else:
            wayy.append(seq)
            seq = 0
            state = True
    else:
        seq += 1


if state:
    wayx.append(seq)
    seq = 0
    state = False
else:
    wayy.append(seq)
    seq = 0
    state = True

can_reachx[pad+wayx[0]] = True
can_reachy[pad] = True

for i in range(1,len(wayx)):
    w = wayx[i]
    b = []
    for j in range(len(can_reachx)):
        if can_reachx[j]:
            if j+w <= pad*2:
                b.append(j+w)
            if j-w >= 0:
                b.append(j-w)
            can_reachx[j] = False
    for t in b:
        can_reachx[t] = True

for w in wayy:
    b = []
    for i in range(len(can_reachy)):
        if can_reachy[i]:
            if i+w <= pad*2:
                b.append(i+w)
            if i-w >= 0:
                b.append(i-w)
            can_reachy[i] = False
    for t in b:
        can_reachy[t] = True

if can_reachx[x+pad] and can_reachy[y+pad]:
    print("Yes")
else:
    print("No")

Submission status: Accepted

Solution code:
S = input()
X, Y = [int(_) for _ in input().split()]
V = [[0], [0]]
d = 0
f = 1
for s in S:
    if s == 'F':
        if f:
            X -= 1
        else:
            V[d][-1] += 1
    else:
        f = 0
        d = 1 - d
        if V[d][-1]:
            V[d] += [0]
V = [sorted(_) for _ in V]
xs = set()


def judge(diff, vs):
    se = set([0])
    for v in vs:
        sen = set()
        for s in se:
            sen.add(s + v)
            sen.add(s - v)
        se = sen
    if diff not in se:
        print('No')
        exit()


judge(X, V[0])
judge(Y, V[1])
print('Yes')

Submission status: Accepted

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

count = [[], []]
now = 0
for f in s.split('T') :
    count[now].append(len(f))
    now ^= 1

def solve() :
    dp = set([count[0][0]])
    for c in count[0][1:] :
        if c == 0 :
            continue
        dp_ = set()
        for xi in dp :
            dp_.add(xi+c)
            dp_.add(xi-c)
        dp = dp_
    if not x in dp :
        return 'No'
    
    dp = set([0])
    for c in count[1] :
        if c == 0 :
            continue
        dp_ = set()
        for yi in dp :
            dp_.add(yi+c)
            dp_.add(yi-c)
        dp = dp_
    if not y in dp :
        return 'No'
    return 'Yes'

print(solve())

Submission status: Accepted

Solution code:
def cango(l,x):
    n=sum(l)
    if abs(x)>n:
        return False
    dp=[False]*(n+1)
    dp[0]=True
    for i in range(len(l)):
        dp1=[False]*(n+1)
        for j in range(n+1):
            if dp[j]:
                dp1[abs(j-l[i])]=True
                dp1[j+l[i]]=True
        for i in range(n+1):
            dp[i]=dp1[i]
    return dp[abs(x)]

l=eval("['"+input().replace('T',"','")+"']")
for i in range(len(l)):
    l[i]=len(l[i])
x,y=map(int,input().split())
if len(l)==1:
    print(['No','Yes'][x==l[0] and y==0])
elif len(l)==2:
    print(['No','Yes'][x==l[0] and abs(y)==abs(l[1])])
else:
    print(['No','Yes'][cango(l[2::2],x-l[0]) and cango(l[1::2],y)])

Submission status: Accepted

Solution code:
s = input()
xy = list(map(int,input().split()))
data = [[0],[0]]
direct = 0
for i in s:
    if i == "F":
        data[direct][-1] += 1
    else:
        direct ^= 1
        data[direct].append(0)
judge = [False, False]
for direct in range(2):
    set_now = set((data[direct][0],))
    for d in data[direct][1:]:
        s_next = set()
        for e in set_now:
            s_next.add(e+d)
            s_next.add(e-d)
        set_now = s_next

    if xy[direct] in set_now:
        judge[direct] = True

if judge[0] and judge[1]:
    print("Yes")
else:
    print("No")

Submission status: Accepted

Solution code:
from collections import deque


s = input()

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

xlis = []
ylis = []

slis = deque()
for i in s:
    slis.append(i)


while True:
    if len(slis) > 0 and slis[0] == "F":
        x -= 1
        slis.popleft()
    else:
        break

#print(slis,x)

direct = 0
tnum = 0
fnum = 0

while len(slis) > 0:

    nows = slis.popleft()

    if nows == "T":

        if tnum == 0 and fnum != 0:

            if  direct == 0:
                xlis.append(fnum)
            else:
                ylis.append(fnum)

            fnum = 0

        tnum += 1

    if nows == "F":

        direct = (direct + tnum) % 2
        tnum = 0
        fnum += 1

if fnum != 0:

    if direct == 0:
        xlis.append(fnum)
    else:
        ylis.append(fnum)




xdic = {}
ydic = {}


xdic[0] = 1
ydic[0] = 1


for i in xlis:

    nxdic = {}

    for j in xdic:
        nxdic[j + i] = 1
        nxdic[j - i] = 1

    xdic = nxdic.copy()

for i in ylis:

    nydic = {}

    for j in ydic:
        nydic[j + i] = 1
        nydic[j - i] = 1

    ydic = nydic.copy()

if x in xdic and y in ydic:
    print ("Yes")

else:
    print ("No")

Submission status: Accepted

Solution code:
s = list(map(len,input().split("T")))
x = s[::2]
y = s[1::2]
gx,gy = map(int,input().split())
if sum(x) < abs(gx) or sum(y) < abs(gy):
  print("No")
  exit(0)
dpx = [0]*(len(x)+1)
dpy = [0]*(len(y)+1)
dpx[0] = set([0])
dpy[0] = set([0])
for i in range(1,len(x)+1):
  s1 = set([v + x[i-1] for v in dpx[i-1]])
  s2 = set([v - x[i-1] for v in dpx[i-1]])
  if i == 1:
    dpx[i] = s1
  else:
    dpx[i] = s1|s2
for i in range(1,len(y)+1):
  s1 = set([v + y[i-1] for v in dpy[i-1]])
  s2 = set([v - y[i-1] for v in dpy[i-1]])
  dpy[i] = s1|s2
if gx in dpx[-1] and gy in dpy[-1]:
  print("Yes")
else:
  print("No")

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from heapq import heappush, heappop
import sys
import math
import bisect
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return list(sys.stdin.readline().rstrip())
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
mod = 1000000007

#A
"""
a, b = LI()
print((a+b+1)//2)
"""

#B
"""
a = S()
a = a[:-1]
b = S()
b = b[:-1]
a.sort()
b.sort(reverse=True)
if a < b:
    print("Yes")
else:
    print("No")
"""

#C
"""
n = I()
a = LI()
a.sort()
seta = set(a)
ans = 0
for i in seta:
    x = bisect.bisect_right(a,i) - bisect.bisect_left(a,i)
    if x != 0 and x >= i:
        ans += x - i
    else:
        ans += x
print(ans)        
"""

# D
# 解説AC
# X,Y軸に分解して、移動は常に同じ方向に行われる（TFFFTならFは常に同じ方向）
# ためTFFFFFTFFFF→TF5TF4として考えて奇数番目のFがx偶数番目がyに寄与
# あとはDP
s = S()
X, Y = LI()
dx = defaultdict(int)
dy = defaultdict(int)
i = 0
num = 0
lis = []
for i in range(len(s)):
    if s[i] == "T":
        lis.append(num)
        num = 0
    else:
        num += 1
if s[-1] == "F":
    lis.append(num)
dx[lis[0]] = True
dy[0] = True
for i in range(1, len(lis)):
    if not i % 2:
        ndx = defaultdict(int)
        for key, _ in dx.items():
            ndx[key + lis[i]] = True
            ndx[key - lis[i]] = True
        dx = ndx
    else:
        ndy = defaultdict(int)
        for key, _ in dy.items():
            ndy[key + lis[i]] = True
            ndy[key - lis[i]] = True
        dy = ndy
if dx[X] and dy[Y]:
    print("Yes")
else:
    print("No")

Submission status: Accepted

Solution code:
import numpy as np

def main():
    s = input().split("T")
    x, y = map(int, input().split())
    xs = []
    x -= len(s[0])
    for i in range(2, len(s), 2):
        tmp = len(s[i])
        if tmp != 0:
            xs.append(tmp)
    ys = []
    for i in range(1, len(s), 2):
        tmp = len(s[i])
        if tmp != 0:
            ys.append(tmp)
    
    sum_x = sum(xs)
    sum_y = sum(ys)
    x = abs(x)
    y = abs(y)
    if sum_x < x or sum_y < y:
        print("No")
    else:
        rest_x = sum_x - x
        rest_y = sum_y - y
        if rest_x&1 or rest_y&1:
            print("No")
        else:
            ok = True
            if rest_x > 0:
                dp = np.array([[False]*8001 for i in range(len(xs)+1)])
                dp[0][0] = True
                for i in range(1, len(xs)+1):
                    dp[i] = dp[i] | dp[i-1]
                    dp[i][xs[i-1]:] = dp[i-1][xs[i-1]:] | dp[i-1][:-xs[i-1]]
                    # dp[i][:-xs[i-1]] = dp[i-1][:-xs[i-1]] | dp[i-1][xs[i-1]:]
                if not dp[-1][rest_x//2]:
                    ok = False
            if rest_y > 0:
                dp = np.array([[False]*8001 for i in range(len(ys)+1)])
                dp[0][0] = True
                for i in range(1, len(ys)+1):
                    dp[i] = dp[i] | dp[i-1]
                    dp[i][ys[i-1]:] = dp[i-1][ys[i-1]:] | dp[i-1][:-ys[i-1]]
                    # dp[i][:-ys[i-1]] = dp[i-1][:-ys[i-1]] | dp[i-1][ys[i-1]:]
                if not dp[-1][rest_y//2]:
                    ok = False
            if ok:
                print("Yes")
            else:
                print("No")
                    

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict as d
s=input()+"T"
x,y=map(int,input().split())
p=[[],[]]
c,e=0,0
for i in s:
    if i=="T":
        if e!=0:
            p[c].append(e)
            e=0
        c=(c+1)%2
    else:
        e+=1
def f(a,c,q):
    g=d(int)
    r=0
    if q!=0:
        if len(a)>0 and s[0]=="F":
            g[a[0]]=1
            r=1
        else:
            g[0]=1
    else:
        g[0]=1
    for j in a[r:]:
        t=d(int)
        for i,h in g.items():
            t[i-j]=1
            t[i+j]=1
        else:
            g=t
    return g[c]!=0
print("Yes" if f(p[0],x,1)*f(p[1],y,0)==1 else"No")

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**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 II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

# def can_reach(x, default_pos, x_moves):  # 全探索
#     for tries in range(2**len(x_moves)):  # x_moves は最大 4000, 2**100 で既に 10**30 なのでぜんぜん間に合わない。
#         result = default_pos
#         for digit in range(len(x_moves)):
#             result += (x_moves[digit] if tries & (1<<digit) else -x_moves[digit])
#         if result == x:
#             return True
#     return False

# def can_reach(x_aim, default_pos, x_moves):  # ソートして貪欲 → ACだが嘘解法かもしれない。
#     for i in sorted(x_moves, reverse=True):
#         if x_aim > default_pos:
#             default_pos += i
#         else:
#             default_pos -= i
#     if default_pos == x_aim:
#         return True
#     else:
#         return False

# def can_reach(x_aim, default_pos, x_moves):  # dp → TLE
#     def dp(i, pos):
#         if i == 0:
#             if pos == default_pos: return True
#             else: return False
#         else:
#             return dp(i-1, pos - x_moves[i-1])  or dp(i-1, pos + x_moves[i-1])

#     return dp(len(x_moves), x_aim)

# def can_reach(x_aim, default_pos, x_moves):  # dp with table → TLE
#     dp = [[False for _ in range(20000)] for _ in range(len(x_moves)+1)]  # 20000 * 8000 = O(10**8) ぐらい
#     def read_dp(i, j):
#         return dp[i][j+10000]
#     def write_dp(i, j, k):
#         dp[i][j+10000] = k
#     write_dp(0, default_pos, True)
#     for i in range(len(x_moves)):
#         for j in range(20000):
#             if dp[i][j] == True:
#                 dp[i+1][j+x_moves[i]] = True
#                 dp[i+1][j-x_moves[i]] = True
#     return read_dp(len(x_moves), x_aim)
    

def can_reach(x_aim, default_pos, x_moves):  # dp with set → AC
    dp = set([default_pos])
    for i in x_moves:
        new_dp = []
        for j in dp:
            new_dp.append(j+i)
            new_dp.append(j-i)
        dp = set(new_dp)
    return x_aim in dp


def main(): 
    s = SI()
    x, y = LI()

    x_moves = []
    y_moves = []
    moving_x = True
    for i in s.split('T'):
        if moving_x:
            x_moves.append(len(i))
        else:
            y_moves.append(len(i))
        moving_x = not moving_x

    if can_reach(x, x_moves[0], x_moves[1:]) and can_reach(y, 0, y_moves):
        print('Yes')
    else:
        print('No')


main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**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 II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

# def can_reach(x, default_pos, x_moves):
#     for tries in range(2**len(x_moves)):  # x_moves は最大 4000, 2**100 で既に 10**30 なのでぜんぜん間に合わない。
#         result = default_pos
#         for digit in range(len(x_moves)):
#             result += (x_moves[digit] if tries & (1<<digit) else -x_moves[digit])
#         if result == x:
#             return True
#     return False

# def can_reach(x_aim, default_pos, x_moves):  # ソートして貪欲？
#     for i in sorted(x_moves, reverse=True):
#         if x_aim > default_pos:
#             default_pos += i
#         else:
#             default_pos -= i
#     if default_pos == x_aim:
#         return True
#     else:
#         return False

# def can_reach(x_aim, default_pos, x_moves):  # dp → TLE
#     def dp(i, pos):
#         if i == 0:
#             if pos == default_pos: return True
#             else: return False
#         else:
#             return dp(i-1, pos - x_moves[i-1])  or dp(i-1, pos + x_moves[i-1])

#     return dp(len(x_moves), x_aim)

# def can_reach(x_aim, default_pos, x_moves):  # dp with table
#     dp = [[False for _ in range(20000)] for _ in range(len(x_moves)+1)]  # 20000 * 8000 = O(10**8) ぐらい
#     def read_dp(i, j):
#         return dp[i][j+10000]
#     def write_dp(i, j, k):
#         dp[i][j+10000] = k
#     write_dp(0, default_pos, True)
#     for i in range(len(x_moves)):
#         for j in range(20000):
#             if dp[i][j] == True:
#                 dp[i+1][j+x_moves[i]] = True
#                 dp[i+1][j-x_moves[i]] = True
#     return read_dp(len(x_moves), x_aim)
    

def can_reach(x_aim, default_pos, x_moves):  # dp with dict
    dp = set([default_pos])
    for i in x_moves:
        new_dp = []
        for j in dp:
            new_dp.append(j+i)
            new_dp.append(j-i)
        dp = set(new_dp)
    return x_aim in dp


def main(): 
    s = SI()
    x, y = LI()

    x_moves = []
    y_moves = []
    moving_x = True
    for i in s.split('T'):
        if moving_x:
            x_moves.append(len(i))
        else:
            y_moves.append(len(i))
        moving_x = not moving_x

    if can_reach(x, x_moves[0], x_moves[1:]) and can_reach(y, 0, y_moves):
        print('Yes')
    else:
        print('No')

main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**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 II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

# def can_reach(x, default_pos, x_moves):
#     for tries in range(2**len(x_moves)):  # x_moves は最大 4000, 2**100 で既に 10**30 なのでぜんぜん間に合わない。
#         result = default_pos
#         for digit in range(len(x_moves)):
#             result += (x_moves[digit] if tries & (1<<digit) else -x_moves[digit])
#         if result == x:
#             return True
#     return False

def can_reach(x_aim, default_pos, x_moves):  # ソートして貪欲？
    for i in sorted(x_moves, reverse=True):
        if x_aim > default_pos:
            default_pos += i
        else:
            default_pos -= i
    if default_pos == x_aim:
        return True
    else:
        return False

def main(): 
    s = SI()
    x, y = LI()

    x_moves = []
    y_moves = []
    moving_x = True
    for i in s.split('T'):
        if moving_x:
            x_moves.append(len(i))
        else:
            y_moves.append(len(i))
        moving_x = not moving_x

    if can_reach(x, x_moves[0], x_moves[1:]) and can_reach(y, 0, y_moves):
        print('Yes')
    else:
        print('No')


main()

Submission status: Accepted

Solution code:
s = input()
X, Y = map(int, input().split())
fs = s.split("T")
nsx = list(map(len, fs[0::2]))
nsy = list(map(len, fs[1::2]))
ssx = []
ssx.append({ 0 })
ssx.append({ nsx[0] })
for i in range(1, len(nsx)):
  s = ssx[i]
  n = nsx[i]
  s2 = set()
  for x in s:
    s2.add(x+n)
    s2.add(x-n)
  ssx.append(s2)
#print(ssx)
ssy = [{ 0 }]
for i in range(0, len(nsy)):
  s = ssy[i]
  n = nsy[i]
  s2 = set()
  for y in s:
    s2.add(y+n)
    s2.add(y-n)
  ssy.append(s2)
#print(ssy)
if X in ssx[-1] and Y in ssy[-1]:
  print("Yes")
else:
  print("No")