[python]白俊14929-面倒(SIB)解答

Overview

BOJ 14929面倒(SIB)Python解答
分類:Prefix Sum(累計)

質問ページ

https://www.acmicpc.net/problem/14929
すべての状況を後追跡するとタイムアウトが発生します.

プールコード1

from sys import stdin


def main():
    def input():
        return stdin.readline().rstrip()

    n = int(input())
    nums = list(map(int, input().split()))

    prefix_sum = 0
    res = 0
    for i in range(len(nums) - 1, 0, -1):
        prefix_sum += nums[i]
        res += nums[i - 1] * prefix_sum

    print(res)


if __name__ == "__main__":
    main()

問題では、与えられた式は、次のように分配法則で表すことができます.

したがって,与えられた数字に逆累積和を求めれば,答えが得られる.

プールコード2

from sys import stdin


def main():
    def input():
        return stdin.readline().rstrip()

    n = int(input())
    nums = list(map(int, input().split()))

    prefix_sum = 0
    res = 0
    for i in range(len(nums) - 1):
        prefix_sum += nums[i]
        res += nums[i + 1] * prefix_sum

    print(res)


if __name__ == "__main__":
    main()
    

以前の解では,逆累積和を求める必要はなかった.条件式は次のように変更できます.

式の各要素は同じ数を使用し、順次加算して解くことができます.