kb84tkhrのブログ

何を書こうか考え中です あ、あと組織とは関係ないってやつです 個人的なやつ

ALDS1_10_C: Longest Common Subsequence (続き2)

やっぱTLEじゃないすかー

ほかのひとのコードを見てみる
本のアルゴリズムで通ってるやつはないっぽい
そして(細かくは見てないけど)けっこういろんな解き方があるっぽい

Webで探してみるとみんな動的計画法のサンプルとして解いてて
同じ解き方

もうちょっと自分で考えてみよう
・・・と思って考えてみたけど再帰以外思いつかないなあ

あらためてほかのひとのコードを見てみると
Heesanさんという人のコードが、2次元配列を使ってないだけで
ほぼ本と同様の動的計画法であることに気づいた

見てくれを前回の普通にメモ化したコードに寄せて書き直してみるとこう
配列で必要なのは直前の行(列?)だけなので、前行だけコピーして
覚えるようになってるけれど、考え方は同じ

def lcs2(s1, s2):
    l1 = len(s1)
    l2 = len(s2)
    c = [0] * (l2 + 1)
    for i1 in range(l1):
        cprev = c[:]
        for i2 in range(l2):
            if s1[i1] == s2[i2]:
                c[i2 + 1] = cprev[i2] + 1
            elif c[i2 + 1] < c[i2]:
                c[i2 + 1] = c[i2]
    return c[-1]

これでずいぶんと速くなってジャッジを通る
2次元配列と1次元配列でけっこうアクセス速度が変わるってことかな

あと、毎回maxlと比較してたのは実は不要っぽい
c[l1][l2]が最大に決まってるので
maxlの比較をやめるだけでもけっこう速くなる
(でもジャッジが通るほどではない)

上のコードに合わせて、普通にメモ化したコードの添字ずらしたり
maxlの比較をやめたりしたコードはこう
やっぱり同じ

def lcs(s1, s2):
    l1 = len(s1)
    l2 = len(s2)
    c = [[0] * (l2 + 1) for _ in range(l1 + 1)]
    for i1 in range(l1):
        for i2 in range(l2):
            if s1[i1] == s2[i2]:
                c[i1 + 1][i2 + 1] = c[i1][i2] + 1
            else:
                c[i1 + 1][i2 + 1] = max(c[i1][i2 + 1],
                                        c[i1 + 1][i2])
    return c[l1][l2]

ただし、+1が増えたせいかただmaxlの比較をやめた版より少し遅い
ループの中ってやっぱり影響大きいんだなあ(こなみ

これくらいで!