POH! Vol.2 Python模範解答

こちらではpaiza事務局側で作成したコードを随時掲載していきます。
更新日:2014年4月30日(水)

Python: paiza事務局作成コード Vol.3 動的計画法

得点:100点
通過テストケース数:7/7

if __name__ == "__main__":
    H, W = map(int, raw_input().split())

    display = [map(str, raw_input()) for i in xrange(H)]
    table = [[0]*310 for i in xrange(310)]
    dp = [[100100100]*310 for i in xrange(310)]

    for k in xrange(H):
        for i in xrange(H - k):
            dp[i][0] = min(dp[i][0], 1) if display[i+k][0] == '0' else 0
            for j in xrange(1, W):
                dp[i][j] = min(dp[i][j], dp[i][j-1]+1) if display[i+k][j] == '0' else 0

        hist = [0 for i in xrange(310)]

        for i in xrange(H-k):
            for j in xrange(W-1):
                if dp[i][j+1] == 0 and dp[i][j] >= 1:
                    hist[dp[i][j]] += 1
            if dp[i][W-1] > 0:
                hist[dp[i][W-1]] += 1

        total = 0

        for i in xrange(W):
            total += hist[i+1]
        for i in xrange(W):
            table[k+1][1] += (i+1) * hist[i+1]
        for i in xrange(2, W+1):
            table[k+1][i] = table[k+1][i-1]-total
            total -= hist[i-1]

    for i in xrange(input()):
        S, T = map(int, raw_input().split())
        print table[S][T]

Python: paiza事務局作成コード Vol.2 O(H^2W^2)

得点:71点
通過テストケース数:5/7

if __name__ == "__main__":
    display = [[0]*310 for i in xrange(310)]

    H, W = map(int, raw_input().split())
    for i in xrange(H):
        s = raw_input()
        for j in xrange(W):
            display[i+1][j+1] = 1 if s[j] == '1' else 0

    for i in xrange(H):
        for j in xrange(W):
            display[i+1][j+1] += display[i+1][j]

    for j in xrange(W):
        for i in xrange(H):
            display[i+1][j+1] += display[i][j+1]

    for i in xrange(input()):
        S, T = map(int, raw_input().split())
        cnt = 0
        for i in xrange(H-S+1):
            for j in xrange(W-T+1):
                d = display[i+S][j+T] - display[i+S][j] - display[i][j+T] + display[i][j]
                if d == 0:
                    cnt += 1
        print cnt

Python: paiza事務局作成コード Vol.1 O(H^3W^3)

得点:42点
通過テストケース数:3/7

if __name__ == "__main__":
    H, W = map(int, raw_input().split())
    display = []
    for i in xrange(H):
        display.append([i for i in raw_input()])

    for i in xrange(input()):
        count = 0
        S, T = map(int, raw_input().split())
        for i in xrange(H):
            for j in xrange(W):
                flag = True
                for k in xrange(S):
                    for l in xrange(T):
                        x, y = i+k, j+l
                        if x < H and y < W:
                            if '1' == display[x][y]:
                                flag = False
                        else:
                            flag = False
                        if flag == False:
                            break
                    if flag == False:
                        break
                if flag:
                    count += 1
        print count
ページの先頭へ戻る