POH! Vol.1 Python模範解答

こちらではpaiza事務局側で作成した模範解答を掲載していす。
提出された最速コードは下記リンク先でご覧いただけます。

【POH Vol.1結果発表】新人女子を最も助けたコードとは?

Python: paiza事務局作成コード Vol.3 O(DN)

通過テストケース数:3
実行時間(テストケース1):0.10秒
実行時間(テストケース2):0.61秒
実行時間(テストケース3):12.33秒

if __name__ == "__main__":
    n, d = map(int, raw_input().split())
    p = []
    for i in xrange(n):
        p.append(input())
    p.sort()
    p_len = len(p) - 1
    for i in xrange(d):
        m_i = input()
        ans = 0
        j = 0
        k = p_len
        while j != k:
            s = p[j] + p[k]
            if s > m_i:
                k -= 1
            else:
                j += 1
                if ans < s:
                    ans = s
        print ans

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

通過テストケース数:2
実行時間(テストケース1):0.28秒
実行時間(テストケース2):5.25秒
実行時間(テストケース3):--

if __name__ == "__main__":
    n, d = map(int, raw_input().split())
    p = []
    for i in xrange(n):
        p.append(input())
    p.sort()

    for i in xrange(d):
        m_i = input()
        ans = 0
        for j in xrange(n):
            r = m_i - p[j]
            lb = 0
            ub = n
            while ub - lb != 1:
                mid = (ub + lb) / 2
                if p[mid] <= r:
                    lb = mid
                else:
                    ub = mid
            ub -= 1
            if j >= ub:
                continue
            if p[ub] > r:
                continue
            tmp = p[j] + p[ub]
            if tmp <= m_i and ans < tmp:
                ans = tmp
        print ans

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

通過テストケース数:1
実行時間(テストケース1):9.50秒
実行時間(テストケース1):--
実行時間(テストケース1):--

if __name__ == "__main__":
    n, d = map(int, raw_input().split())
    p = []
    for i in xrange(n):
        p.append(input())

    for x in xrange(d):
        m_i = input()
        ans = 0
        for i in xrange(n):
            for j in xrange(n):
                s = p[i] + p[j]
                if s <= m_i and ans <= s and not i == j:
                    ans = s
        print ans
ページの先頭へ戻る