kb84tkhrのブログ

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

ALDS1_10_C: Longest Common Subsequence

最長共通部分文字列

TCCAGATGGと
TCACAなら
TCAAなんだって

途中がとびとびでもいいんだ
何か実世界の応用もあるのかな

さてどうする
当然メモ化するんだろうけど
まずは総当たりでもいいからメモ化なしで解けないとお話にならない

でも、メモ化をどう使うかって考えると
さっきのペアと同じだったら結果が使える、っていうんじゃたぶん意味ないから
あるペアを解く過程でメモ化が有効になるような解き方をするんだろうな
ちょっと小さい問題に分割して再帰、っていうのを繰り返すんだろう

どうすると分解できるかな

TCCAGATGGとTCACAを題材にして考えると

Tを使う場合とTを使わない場合に分けるといい気がする

Tを使う場合、答えは両方の文字列からTを取り去って
CCAGATGGとCACAの最長共通部分文字列の長さに1を足したもの
Tを使わない場合、前者からTを取り去って
CCAGATGGとTCACAの最長共通部分文字列の長さ

長い方を取ればOK

えーっと、Tを使うとした場合に、TCACAじゃなくてCTACAだったら
どうしたらいいんだ
CTを取り去ればいいのか

できそうな気はするな
ただメモ化がどこまで有効なのかよくわからない
そんなに重複するかな?

とりあえず書いてみよう

def lcs(s1, s2):
    if s1 == "" or s2 == "":
        return 0

    first = s1[0]
    rest = s1[1:]

    index = s2.find(first)
    if index == -1:
        return lcs(rest, s2)
    else:
        return max(lcs(rest, s2[index+1:]) + 1, lcs(rest, s2))

4つめのテストケースでTLE
そんなもんでしょう

解けてるみたいだからメモ化入れてみる
楽してlru_cacheを使う
うまくいったら自前で書くかな

from functools import lru_cache

@lru_cache()
def lcs(s1, s2):
    if s1 == "" or s2 == "":
        return 0
    :
    :

でもやっぱり4つめのテストケースでTLE
自前テストではメモ化の効果ははっきり出てるんだけど・・・
もともとのアルゴリズムがよくないのかな?

いや、もしかして引数にそのまんま文字列を使ってるのがよくないのかも?
1000文字の文字列をハッシュ化?するのに時間がかかってたりとか?
文字列自体は変わらないから、今何文字目かだけわかればいいんだよな
数字に変えたら速くならないかな?

def lcs(s1, s2):

    @lru_cache()
    def rec(i1, i2):
        nonlocal s1, l1, s2, l2

        if i1 == l1 or i2 == l2:
            return 0

        index = s2.find(s1[i1], i2)
        if index == -1:
            return rec(i1 + 1, i2)
        else:
            return max(rec(i1 + 1, index + 1) + 1,
                       rec(i1 + 1, i2))

    l1 = len(s1)
    l2 = len(s2)
    return rec(0, 0)

少し速くなった・・・けどやっぱりTLE
むー
やっぱりアルゴリズムの問題?