競プロ典型90問 002

https://atcoder.jp/contests/typical90/tasks/typical90_b

これは、wikipedia:カタラン数ですね。格子状の経路の数え方に対応していて、右に一つ移動すると'('、上に一つ移動すると')'です。
単純に1歩ずつ進むだけでOKです。

def F(N):
    def g(x, y):
        if (x, y) == (N/2, N/2):
            yield ''
        if x < N/2:
            for s in g(x+1, y):
                yield '(' + s
        if x > y:
            for s in g(x, y+1):
                yield ')' + s
    
    if N % 2 == 1:
        return
    
    for s in g(0, 0):
        print s

N = 20ならこれでも十分です。もう少し数を大きくしてみましょう。

$ echo 26 | time pypy typical002.py > /dev/null
1.32user 0.12system 0:01.46elapsed 99%CPU (0avgtext+0avgdata 56700maxresident)k
0inputs+0outputs (0major+21924minor)pagefaults 0swaps
$ echo 28 | time pypy typical002.py > /dev/null
5.07user 0.14system 0:05.24elapsed 99%CPU (0avgtext+0avgdata 57104maxresident)k
0inputs+0outputs (0major+34368minor)pagefaults 0swaps

どうやら26が限界のようです。
上の方法には非常に無駄があります。スタートを(0, 0)、ゴールを(N/2, N/2)として、例えば(3, 2)を通る経路は何通りかありますが、その度にそこから(N/2, N/2)までの経路を辿らなければいけません。かといって、メモ化だとやたらメモリを使うし。

分割統治法はできないでしょうか。すぐに思いつくのは、x + y = N/2で三角形を分割することです。

f:id:inamori:20211009142257p:plain

この斜めの線のどこかまで到達する経路を全部作って、それを反転してつなぎ合わせます。これならある程度無駄が少なくなって、メモリもそんなに使いません。
辞書順ということで、少しめんどうです。

def reverse(s):
    return ''.join(')' if c == '(' else '(' for c in s[::-1])

def F(N):
    def g(x, y, s):
        if x + y == N/2:
            yield (x, y), s
            return
        
        for v in g(x+1, y, s + '('):
            yield v
        if x > y:
            for v in g(x, y+1, s + ')'):
                yield v
    
    if N % 2 == 1:
        return
    
    dic = defaultdict(list)
    half_paths = list(g(0, 0, ''))
    for pt, s in half_paths:
        dic[pt].append(reverse(s))
    dic2 = dict((pt, sorted(ss)) for pt, ss in dic.items())
    
    counter = 0
    for pt, s1 in half_paths:
        for s2 in dic2[pt]:
            print s1 + s2
            counter += 1
echo 28 | time pypy typical002a.py > /dev/null
0.26user 0.12system 0:00.54elapsed 71%CPU (0avgtext+0avgdata 59664maxresident)k
0inputs+0outputs (0major+16019minor)pagefaults 0swaps
$ echo 30 | time pypy typical002a.py > /dev/null
1.03user 0.09system 0:01.13elapsed 98%CPU (0avgtext+0avgdata 59524maxresident)k
0inputs+0outputs (0major+20179minor)pagefaults 0swaps
$ echo 32 | time pypy typical002a.py > /dev/null
3.43user 0.42system 0:03.86elapsed 99%CPU (0avgtext+0avgdata 58940maxresident)k
0inputs+0outputs (0major+31366minor)pagefaults 0swaps

30まで行けるようになりました。
これ以上はうまくいきませんね。