トップページ -> AOJの解答例 -> ALDS1_10の解答例

ALDS1_10の解答例(Python)

二分探索木に関する問題です． A,B,Cしかできていない上にコードが相当酷いですが，一応載せておきます．アルゴリズムについて詳しく知りたい方は参考文献などをご覧ください． B,Cは特にアルゴリズムイントロダクション2巻で詳しく解説されています．

1. ALDS1_10_A: Fibonacci Number

フィボナッチ数列の第n項を求める問題です．再帰関数で実装したりしない限りはなんでも時間制限をクリアできると思います．


# ALDS1_10_A

n = int(input())

fib_list = [1,1]
for i in range(2,n+1):
    fib_list.append(fib_list[i-1] + fib_list[i-2])
    
print(fib_list[n])

2. ALDS1_10_B: Matrix Chain Multiplication

連鎖行列積問題です． 3つの積までは感覚的に分かりやすいので考え方を整理するためにそのままコードを書きました． 4つ以上の場合は分割する位置をずらしてコストを計算します． find_minは(ABC)|(DEFG)のように分割した場合，DEFGで再度find_minが呼び出されるような再帰関数です．同じ計算を何度もしなくてよいように計算結果を記録するanswer_dictを用意して記録しています．


# ALDS1_10_B
n = int(input())
M = []

for _ in range(n):
    M.append(list(map(int,input().split(" "))))
    
answer_dict = {}

for i in range(n-1):
    key = str(i)+","+str(i+1)
    answer_dict[key] = M[i][0]*M[i][1]*M[i+1][1]

# 左からの積
def find_min(m_list):
    # 計算にコストがかからない
    if len(m_list) == 1:
        return 0 
    # 積の計算回数は1通りのみ
    elif len(m_list) == 2:
        m1,m2 = m_list
        key = str(m1) + "," + str(m2)
        return answer_dict[key]
    # 3つの積の計算回数はAB Cか A BCのいずれか
    elif len(m_list) == 3:
        m1,m2,m3 = m_list
        key = str(m1) + "," + str(m2) + "," + str(m3)
        if key in answer_dict.keys():
            return answer_dict[key]
        else:
            c = min(answer_dict[str(m1)+","+str(m2)] + (M[m1][0] * M[m2][1]) * M[m3][1],M[m1][0]*M[m1][1]*M[m3][1] + answer_dict[str(m2)+","+str(m3)])
            answer_dict[key] = c
            return c
    # 4つ以上はA | BCD, AB | CD, ABC | Dのように区切りを入れる位置を変えて計算し最小を取ればよい 
    else:
        key = ""
        for m in m_list:
            key += str(m) + ","
            
        # 既に計算をしていれば記録している計算結果を返す
        if key in answer_dict.keys():
            return answer_dict[key]
        else:
            # 区切りを入れる位置を変えて計算
            min_c = float("inf")
            for i in range(len(m_list)-1):
                # print(i,m_list[:i+1],m_list[i+1:])
                c = find_min(m_list[:i+1]) + find_min(m_list[i+1:]) + M[m_list[0]][0]*M[m_list[i]][1]*M[m_list[-1]][1]
                min_c = min(min_c,c)

            answer_dict[key] = min_c
            return min_c

print(find_min([i for i in range(n)]))

3. ALDS1_10_C: Longest Common Subsequence

最長共通部分列です． A_nとB_mの最長部分列の長さを調べるのにA_(n-1)とB_(m-1)の情報を使うようにしています．(動的計画法)


# ALDS1_10_C
n = int(input())
    
for _ in range(n):
    A = " " + input()
    B = " " + input()
    row1 = [0 for _ in range((len(B)+1))]
    for i in range(1,len(A)):
        row2 = [0 for _ in range((len(B)))]
        for j in range(1,len(B)):
            if A[i] == B[j]:
                row2[j] = row1[j-1] + 1
            else:
                if row1[j] > row2[j-1]:
                    row2[j] = row1[j]
                else:
                    row2[j] = row2[j-1]
                    
        row1 = row2
        
    print(row2[-1])

4. ALDS1_10_D: Optimal Binary Search Tree

最適二分探索木に関する問題です．


# ALDS1_10_D Optimal Binary Search Tree
# 編集中

<- 前へ戻る【目次に戻る】次へ進む ->