TopCoder SRM 663 Div1 o-- 1243->1264

久しぶりにTopCoderで問題を正解できました
解くのが遅かったのでレートは微増

?位, 117.32点, +0/-0 challenge
Volatility: ?->168

300: ABBADiv1

'A'と'B'の2種類の文字だけで構成された文字列、initialとtargetが与えられる(文字列の長さ\(N \le 50\))
以下の2つの操作ができる時にinitialからtargetに変換できるか答える

• 文字列の末尾に'A'を足す
• 文字列を逆転して先頭に'B'を足す

解法

targetからinitialに変換していくと考える
可能な操作は、文字列の末尾から'A'を取り除くことと文字列の先頭から'B'を取り除いて逆転すること
つまり文字を左右から取り除くあるいは逆転させることの組み合わせなので、途中で取りうる状態数は文字列中から始まりと終わりの位置を選ぶ場合の数と前後を選ぶ場合の数をかければよくて、\(O(N^2)\)ぐらいになる
取りうる状態数が少ないので、メモ化再帰や動的計画法などですぐに計算できる

# -*- coding: utf-8 -*-
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys

class ABBADiv1:
    def canObtain(self, initial, target):
        sys.setrecursionlimit(20000)
        L = len(initial)
        
        check = set()
        check_r = set()
        for i in xrange(len(target)):
            if target[i:].startswith(initial):
                check.add(i)
            if target[i::-1].startswith(initial):
                check_r.add(i)
        
        memo = {}
        def solve(start, end):
            key = start, end
            if key in memo:
                return memo[key]
            l = abs(end - start) + 1
            z = 1 if start < end else -1
            if l == L:
                if start <= end:
                    ret = start in check
                else:
                    ret = start in check_r
            elif l > L:
                c = target[start]
                d = target[end]
                if c == 'A':
                    if d == 'A':
                        ret = solve(start, end - z)
                    else:
                        ret = False
                elif c == 'B':
                    if d == 'B':
                        ret = solve(end, start + z)
                    else:
                        ret = solve(start, end - z) or solve(end, start + z)
            memo[key] = ret
            return ret
        return "Possible" if solve(0, len(target) - 1) else "Impossible"