競プロ典型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で三角形を分割することです。
この斜めの線のどこかまで到達する経路を全部作って、それを反転してつなぎ合わせます。これならある程度無駄が少なくなって、メモリもそんなに使いません。
辞書順ということで、少しめんどうです。
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まで行けるようになりました。
これ以上はうまくいきませんね。