パナソニックグループプログラミングコンテスト2022（AtCoder Beginner Contest 251）G,Ex問題メモ

import sys


def ccw(ax, ay, bx, by, cx, cy):
    """
        C         :1
    A------>B  C  :0
        C         :-1
    """
    dx1 = bx - ax
    dy1 = by - ay
    dx2 = cx - ax
    dy2 = cy - ay
    if dy1 * dx2 > dy2 * dx1:
        return -1
    if dx1 * dy2 > dy1 * dx2:
        return 1
    if dx1 * dx2 < 0 or dy1 * dy2 < 0:
        return 1
    if dx1 * dx1 + dy1 * dy1 < dx2 * dx2 + dy2 * dy2:
        return -1
    return 0


input = sys.stdin.buffer.readline

n = int(input())
vertices = [tuple(map(int, input().split())) for _ in range(n)]
vertices.append(vertices[0])
m = int(input())
# slides = [tuple(map(int, input().split())) for _ in range(n)]

# n本の各辺につき、最も厳しい（内側に近い）多角形の線分を前計算
nearest = []
u, v = map(int, input().split())
for i in range(n):
    x1, y1 = vertices[i]
    x2, y2 = vertices[i + 1]
    x1 += u
    y1 += v
    x2 += u
    y2 += v
    nearest.append((x1, y1, x2, y2))

for _ in range(m - 1):
    u, v = map(int, input().split())
    for i in range(n):
        x1, y1 = vertices[i]
        x2, y2 = vertices[i + 1]
        x1 += u
        y1 += v
        x2 += u
        y2 += v
        cx1, cy1, cx2, cy2 = nearest[i]
        if ccw(cx1, cy1, cx2, cy2, x1, y1) == 1:
            nearest[i] = (x1, y1, x2, y2)

buf = []
q = int(input())
for _ in range(q):
    a, b = map(int, input().split())
    for i in range(n):
        x1, y1, x2, y2 = nearest[i]
        if ccw(x1, y1, x2, y2, a, b) < 0:
            buf.append('No')
            break
    else:
        buf.append('Yes')

print('\n'.join(buf))

細かな高速化（特にPython）として、ランレングス圧縮を行わなくてもメモリに乗るくらい1段の要素数が小さくなったら、展開した方が計算は速い。

n, m, k = map(int, input().split())
nums = [tuple(map(int, input().split())) for _ in range(m)]
is_rle = True

d = 7 ** 10

while d > 0:
    while n - d >= k:

        if is_rle:

            i1 = 0
            a1, c1 = nums[0]

            r = d
            for i, (a, c) in enumerate(nums):
                if r < c:
                    i2 = i
                    a2 = a
                    c2 = c - r
                    break
                r -= c

            l = len(nums)
            new_nums = []
            is_all_one = True

            while i2 < l:
                if c1 == c2:
                    new_nums.append(((a1 + a2) % 7, c1))
                    if c1 > 1:
                        is_all_one = False
                    i1 += 1
                    i2 += 1
                    if i2 >= l:
                        break
                    a1, c1 = nums[i1]
                    a2, c2 = nums[i2]
                elif c1 < c2:
                    new_nums.append(((a1 + a2) % 7, c1))
                    if c1 > 1:
                        is_all_one = False
                    c2 -= c1
                    i1 += 1
                    a1, c1 = nums[i1]
                else:
                    new_nums.append(((a1 + a2) % 7, c2))
                    if c2 > 1:
                        is_all_one = False
                    c1 -= c2
                    i2 += 1
                    if i2 >= l:
                        break
                    a2, c2 = nums[i2]

            if is_all_one:
                nums = [a for a, c in new_nums]
                is_rle = False
            else:
                nums = new_nums

        else:
            nums = [(a1 + a2) % 7 for a1, a2 in zip(nums, nums[d:])]

        n -= d

    d //= 7

if is_rle:
    ans = []
    for a, c in nums:
        ans.extend([a] * c)
    print(*ans)
else:
    print(*nums)