Kickstart Round G 2018 - Problem A. Product Triplets

Dashboard - Kickstart Round G 2018 - Google Code Jam

smallはまわすだけ、largeはむずい。 atcoderでいうと、smallは200点、largeは400点問題ぐらいだろうか。

def small_solve(case):
    nums = list(map(int, case.split(" ")))
    count = 0
    for x in range(len(nums)):
        for y in range(x + 1, len(nums)):
            for z in range(y + 1, len(nums)):
                xn, yn, zn = nums[x], nums[y], nums[z]
                if xn == yn * zn or yn == xn * zn or zn == xn * yn:
                    count += 1
    return count

0を特別扱いするところまでは思いついたが、 x = 0 and y = 0を特別扱いするか、x = 0 or y = 0を特別扱いするかあたりがうまく回らなかったのと、 x, y を定めた後のzをbinary searchしたがまだ遅かった。

from math import factorial as f
def large_solve(case):
    def nCr(n, r):
        return f(n) // f(r) // f(n - r)
    nums = sorted(list(map(int, case.split(" "))))
    counter = {i: 0 for i in nums}
    ans = 0
    for yi in range(len(nums) - 1, -1, -1):
        y = nums[yi]
        for xi in range(yi - 1, -1, -1):
            x = nums[xi]
            if y > 0 and x > 0:
                ans += counter[y*x] if x * y in counter else 0
        counter[y] += 1

    z = counter[0] if 0 in counter else 0
    if z >= 3:
        ans += nCr(z, 3)
    if z >= 2:
        ans += nCr(z, 2) * (len(nums) - z)
    return ans

今回の学び。

1. ソートすること、探索する計算は減らせる時がある。
2. 配列の組み合わせでx < y < zにおいて、x, yから計算結果をzに見つけるとき、逆順にすることでsearchをせずにカウントが可能。
3. pythonのrangeは逆順がとても読みにくいんだがきちんとかけるように。
4. 特別な場合はダブりに気をつければ、countだけとって別に計算することも出来る。今回の場合は0。

過去のkickstartをとことんやらなくては。