アルゴリズムコンテスト入門経典第三章まとめ(2):後半の練習問題解答

UVA 232:テーマは書かないで、主に単語の変換を模擬します.注意啓示格の順に出力する必要がある.縦の単語を出力するときは、アクセスされたか否かをマトリクスでマークする.もちろん縦書きで並べ替えることもできる.

def cross(matrix,r,c):
    mark = [[0]*c for i in range(r)]
    def test(i,j):#            
        #if(matrix[i][j]=='U'):print(mark)
        if(i==0 or j==0):return True
        elif(matrix[i-1][j] == '*' or matrix[i][j-1]=='*'):return True
        else:return False
    i = 0;across = ''
    while(i<r):
        j = 0
        while(j<c):
            #print(matrix[i][j])
            if(matrix[i][j]!='*' and test(i,j)):
                across = ''
                across+=matrix[i][j]
                while(j+1<c and matrix[i][j+1]!='*'):across+=matrix[i][j+1];j+=1
                j+=1
                print(across)
            else: j+=1
        i+=1
    print('Down:')
    i = 0;across = ''
    while(i<r):
        j = 0
        while(j<c):
            if(matrix[i][j]!='*' and test(i,j) and mark[i][j]!=1):
                across = ''
                mark[i][j] = 1#       
                across+=matrix[i][j]
                _i = i;
                while(_i+1<r and matrix[_i+1][j]!='*'):
                    #print(_i+1,j)
                    across+=matrix[_i+1][j]
                    mark[_i+1][j] = 1
                    _i+=1
                j+=1
                print(across)
            else: j+=1
        i+=1

UVA 1368:DNA配列
各位置のDNAは独立しており、他のDNAとは無関係であるため、1列1列で比較すればよい.

def Hamming(buf,m,n):
    ans = ''
    diff = 0
    for j in range(n):
        count = {'A':0,'C':0,'G':0,'T':0}
        max = 0
        for i in range(m):
            count[buf[i][j]]+=1
            if(count[buf[i][j]] > max):
                max = count[buf[i][j]]
                max_alpha = buf[i][j]
            elif(count[buf[i][j]] == max):#     
                if(buf[i][j]<max_alpha):
                    max = count[buf[i][j]]
                max_alpha = buf[i][j]
        ans += max_alpha
        diff += (m - max)
    print(ans,diff)
Hamming(['TATGATAC','TAAGCTAC','AAAGATCC','TGAGATAC','TAAGATGT'],5,8)

UVA 202、このテーマの鍵は小数を判断するのではなく、毎回の残数を判断し、残数が繰り返す限り小数は繰り返される.この点を考えると難しくない.

def Repeating(a,b):
    ans1 = a//b
    a = a%b
    tmp = ''
    ans2 = str((a*10)//b)
    mark_store = []
    while(True):
        a = (a*10)%b
        tmp = (a*10)//b
        if(a in mark_store):break
        else:
            mark_store.append(a)
            ans2 += str(tmp)
    m = ans2[:-1]
    print(str(ans1)+'.'+'(%s)'%(m),len(m))

UVA 10340:この問題は逆思考で、s文字列の文字がtの中で順番に見つけることができるかどうかを考えることです.つまり、後ろに探すしかありません.これで簡単に判断できます.O(m+n)の複雑さ.

def Allinall(s,t):#s-->t??
    index = -1
    for ch in s:
        index = t.find(ch,index+1)
        if(index == -1):print('NO');return False
    print('YES')
Allinall('dc','abcde')

UVA 1587、この問題の鍵は入力を標準化し、辺の状況を統計してから検査することである.必ず3種類の分布を満たす3本の異なる辺は、2本が同じで、3本が同じである.

def Box(L,W):
    def mysort():
        for i in range(6):
            if(L[i]<W[i]):L[i],W[i] = W[i],L[i]
    mysort()
    X = [(L[i],W[i]) for i in range(6)]
    Count = {}
    for each in X:
        if str(each) not in Count:
            Count[str(each)] = 1
        else:Count[str(each)] += 1
    if(len(Count)==3):
        print(Count)
        for each,val in Count.items():
            if(val != 2):print('Impossible 4');return
        print('Possible')
    elif(len(Count)==2):
        test = [x for k,x in Count.items()]
        test.sort()
        if (test!=[2,4]):print('Impossible 8');return
        print('Possible')
    elif(len(Count)==1):
        for each,val in Count.items():
            if(Count[each]!=6):print('Impossible 12');return
        print('Possible')
    else:print('Impossible');return
Box([3,3,4,4,4,4],[3,3,5,3,3,3])

UVA 1588は、2つのシミュレーションの方向に注意するトラップがある.直接シミュレーションを行い、長尺の長尺を入れる、長尺の長尺の各点から遍歴する.次に短い長尺を入れて巡り、最後に最小値をとります

def Kickdown(h1,h2):
    n1 = len(h1);n2 = len(h2)
    def geth(i):
        if(i>=n1):return 0
        else: return h1[i]
    def geth2(i):
        if(i>=n2):return 0
        else: return h2[i]
    for i in range(n1+1):
        if(geth(i)+h2[0]<=3):
            test = True
            for j in range(1,n2):
                if(geth(i+j)+h2[j]>3):test = False;break
            if(test):ans1 = max(n2+i,n1);break
    for i in range(n2+1):#  n2
        if(h1[0]+geth2(i)<=3):
            test = True
            for j in range(1,n1):
                if(h1[j]+geth2(i+j)>3):test = False;break
            if(test):ans2 = max(n1+i,n2);break
    print(min(ans1,ans2))