課題 · データ処理上級 Python ·

Range assign, range minimum

Process operations on a list of integers, indexed from 0: - ["set", l, r, v] sets every element with index from l to r inclusive to v; - ["min", l, r] asks for the smallest element with index from l to r inclusive. Return the answers to the "min" operations, in order. Always 0 <= l <= r < len(nums). Up to 60,000 elements and 60,000 operations, most of them covering long ranges.

シグネチャ

def assign_min(nums: list[int], ops: list[list]) -> list[int]:

入力例

assign_min([5, 3, 8, 6], [['min', 0, 3], ['set', 1, 2, 9], ['min', 0, 2], ['min', 1, 3]])  # -> [3, 5, 6]
assign_min([4], [['set', 0, 0, -1], ['min', 0, 0]])  # -> [-1]

その他、入力値が非公開の6個の非公開テストおよび制限時間付きの2個の大規模入力テストがあります。モデルへの課題は英語で出題されます。

#1OpenAI GPT-6.1 Sol正解 · 10 / 10 件のテストにパス回答時間 21 秒 · 実行時間 1.8 秒 · $0.01

✓	assign_min([5, 3, 8, 6], [['min', 0, 3], ['set', 1, 2, 9], ['min', 0, 2], ['min', 1, 3]])期待値 [3, 5, 6]	2 ms
✓	assign_min([4], [['set', 0, 0, -1], ['min', 0, 0]])期待値 [-1]	4 ms

✓ 1 ms✓ 3 ms✓ 1 ms✓ 2 ms✓ 2 ms✓ 1 ms⏱ 881 ms⏱ 860 ms

コード

def assign_min(nums: list[int], ops: list[list]) -> list[int]:
    if not nums or not ops:
        return []

    size = 1 << (len(nums) - 1).bit_length()
    tree = [float("inf")] * (size * 2)
    lazy = [None] * (size * 2)
    tree[size:size + len(nums)] = nums

    for p in range(size - 1, 0, -1):
        a = tree[p * 2]
        b = tree[p * 2 + 1]
        tree[p] = a if a < b else b

    def update(p, lo, hi, left, right, value):
        if lazy[p] == value:
            return
        if left <= lo and hi <= right:
            tree[p] = value
            lazy[p] = value
            return

        child = p * 2
        tag = lazy[p]
        if tag is not None:
            tree[child] = tree[child + 1] = tag
            lazy[child] = lazy[child + 1] = tag
            lazy[p] = None

        mid = (lo + hi) >> 1
        if left < mid:
            update(child, lo, mid, left, right, value)
        if right > mid:
            update(child + 1, mid, hi, left, right, value)

        a = tree[child]
        b = tree[child + 1]
        tree[p] = a if a < b else b

    def query(p, lo, hi, left, right):
        tag = lazy[p]
        if tag is not None:
            return tag
        if left <= lo and hi <= right:
            return tree[p]

        mid = (lo + hi) >> 1
        if right <= mid:
            return query(p * 2, lo, mid, left, right)
        if left >= mid:
            return query(p * 2 + 1, mid, hi, left, right)

        a = query(p * 2, lo, mid, left, right)
        b = query(p * 2 + 1, mid, hi, left, right)
        return a if a < b else b

    answers = []
    for op in ops:
        if op[0] == "set":
            update(1, 0, size, op[1], op[2] + 1, op[3])
        else:
            answers.append(query(1, 0, size, op[1], op[2] + 1))

    return answers

#2MiniMax M3.1 Flash正解 · 10 / 10 件のテストにパス回答時間 8.0 秒 · 実行時間 2.4 秒 · $0.0009

✓	assign_min([5, 3, 8, 6], [['min', 0, 3], ['set', 1, 2, 9], ['min', 0, 2], ['min', 1, 3]])期待値 [3, 5, 6]	1 ms
✓	assign_min([4], [['set', 0, 0, -1], ['min', 0, 0]])期待値 [-1]	1 ms

✓ 2 ms✓ 2 ms✓ 1 ms✓ 1 ms✓ <1 ms✓ <1 ms⏱ 1.2 秒⏱ 1.2 秒

コード

def assign_min(nums: list[int], ops: list[list]) -> list[int]:
    n = len(nums)
    if n == 0:
        return []
    size = 4 * n + 8
    tree = [0] * size
    lazy = [None] * size

    def build(p, lo, hi):
        if lo == hi:
            tree[p] = nums[lo]
            return
        mid = (lo + hi) >> 1
        c = p << 1
        build(c, lo, mid)
        build(c + 1, mid + 1, hi)
        a = tree[c]
        b = tree[c + 1]
        tree[p] = a if a < b else b

    def update(p, lo, hi, ql, qr, v):
        if ql <= lo and hi <= qr:
            tree[p] = v
            lazy[p] = v
            return
        c = p << 1
        t = lazy[p]
        if t is not None:
            tree[c] = t
            tree[c + 1] = t
            lazy[c] = t
            lazy[c + 1] = t
            lazy[p] = None
        mid = (lo + hi) >> 1
        if ql <= mid:
            update(c, lo, mid, ql, qr, v)
        if qr > mid:
            update(c + 1, mid + 1, hi, ql, qr, v)
        a = tree[c]
        b = tree[c + 1]
        tree[p] = a if a < b else b

    def query(p, lo, hi, ql, qr):
        if ql <= lo and hi <= qr:
            return tree[p]
        c = p << 1
        t = lazy[p]
        if t is not None:
            tree[c] = t
            tree[c + 1] = t
            lazy[c] = t
            lazy[c + 1] = t
            lazy[p] = None
        mid = (lo + hi) >> 1
        if qr <= mid:
            return query(c, lo, mid, ql, qr)
        if ql > mid:
            return query(c + 1, mid + 1, hi, ql, qr)
        a = query(c, lo, mid, ql, qr)
        b = query(c + 1, mid + 1, hi, ql, qr)
        return a if a < b else b

    build(1, 0, n - 1)
    out = []
    for op in ops:
        if op[0] == "set":
            update(1, 0, n - 1, op[1], op[2], op[3])
        else:
            out.append(query(1, 0, n - 1, op[1], op[2]))
    return out

#2Google Gemini 3.8 Flash正解 · 10 / 10 件のテストにパス回答時間 6.6 秒 · 実行時間 2.9 秒 · $0.0034

✓	assign_min([5, 3, 8, 6], [['min', 0, 3], ['set', 1, 2, 9], ['min', 0, 2], ['min', 1, 3]])期待値 [3, 5, 6]	<1 ms
✓	assign_min([4], [['set', 0, 0, -1], ['min', 0, 0]])期待値 [-1]	<1 ms

✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 1.5 秒⏱ 1.4 秒

コード

import sys

def assign_min(nums: list[int], ops: list[list]) -> list[int]:
    n = len(nums)
    if n == 0:
        return []

    # Segment tree size
    size = 1
    while size < n:
        size <<= 1
    
    tree = [0] * (2 * size)
    # lazy[i] stores the pending assignment value, or None if no pending update
    lazy = [None] * size

    for i in range(n):
        tree[size + i] = nums[i]
    for i in range(n, size):
        tree[size + i] = float('inf')
    for i in range(size - 1, 0, -1):
        tree[i] = min(tree[2 * i], tree[2 * i + 1])

    # Helper functions for lazy propagation
    def apply(p, value):
        tree[p] = value
        if p < size:
            lazy[p] = value

    def push(p):
        s = size.bit_length()
        for s_shift in range(s - 1, 0, -1):
            i = p >> s_shift
            val = lazy[i]
            if val is not None:
                apply(2 * i, val)
                apply(2 * i + 1, val)
                lazy[i] = None

    def build(p):
        while p > 1:
            p >>= 1
            if lazy[p] is not None:
                tree[p] = lazy[p]
            else:
                tree[p] = min(tree[2 * p], tree[2 * p + 1])

    res = []
    for op in ops:
        if op[0] == 'set':
            _, l, r, v = op
            l += size
            r += size + 1

            l0, r0 = l, r
            push(l0)
            push(r0 - 1)

            while l < r:
                if l & 1:
                    apply(l, v)
                    l += 1
                if r & 1:
                    r -= 1
                    apply(r, v)
                l >>= 1
                r >>= 1

            build(l0)
            build(r0 - 1)
        else:
            _, l, r = op
            l += size
            r += size + 1

            push(l)
            push(r - 1)

            ans = float('inf')
            while l < r:
                if l & 1:
                    if tree[l] < ans:
                        ans = tree[l]
                    l += 1
                if r & 1:
                    r -= 1
                    if tree[r] < ans:
                        ans = tree[r]
                l >>= 1
                r >>= 1
            res.append(ans)

    return res

#4SpaceXAI Grok Build 0.1正解 · 10 / 10 件のテストにパス回答時間 8.7 秒 · 実行時間 5.3 秒 · $0.0058

✓	assign_min([5, 3, 8, 6], [['min', 0, 3], ['set', 1, 2, 9], ['min', 0, 2], ['min', 1, 3]])期待値 [3, 5, 6]	2 ms
✓	assign_min([4], [['set', 0, 0, -1], ['min', 0, 0]])期待値 [-1]	<1 ms

✓ 2 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 2.7 秒⏱ 2.6 秒

コード

def assign_min(nums: list[int], ops: list[list]) -> list[int]:
    n = len(nums)
    if n == 0:
        return []
    tree = [0] * (4 * n)
    lazy = [None] * (4 * n)
    def build(node, start, end):
        if start == end:
            tree[node] = nums[start]
            return
        mid = (start + end) // 2
        build(2 * node, start, mid)
        build(2 * node + 1, mid + 1, end)
        tree[node] = min(tree[2 * node], tree[2 * node + 1])
    def propagate(node, start, end):
        if lazy[node] is not None:
            tree[node] = lazy[node]
            if start != end:
                lazy[2 * node] = lazy[node]
                lazy[2 * node + 1] = lazy[node]
            lazy[node] = None
    def update_range(node, start, end, l, r, val):
        propagate(node, start, end)
        if start > end or start > r or end < l:
            return
        if start >= l and end <= r:
            lazy[node] = val
            propagate(node, start, end)
            return
        mid = (start + end) // 2
        update_range(2 * node, start, mid, l, r, val)
        update_range(2 * node + 1, mid + 1, end, l, r, val)
        tree[node] = min(tree[2 * node], tree[2 * node + 1])
    def query_min(node, start, end, l, r):
        propagate(node, start, end)
        if start > end or start > r or end < l:
            return float('inf')
        if start >= l and end <= r:
            return tree[node]
        mid = (start + end) // 2
        left = query_min(2 * node, start, mid, l, r)
        right = query_min(2 * node + 1, mid + 1, end, l, r)
        return min(left, right)
    build(1, 0, n - 1)
    answers = []
    for op in ops:
        if op[0] == 'set':
            _, l, r, v = op
            update_range(1, 0, n - 1, l, r, v)
        elif op[0] == 'min':
            _, l, r = op
            ans = query_min(1, 0, n - 1, l, r)
            answers.append(ans)
    return answers

トークンコスト: $0.02 · 対戦の進行と評価方法について →