ユニークビジョンプログラミングコンテスト2026 夏（AtCoder Regular Contest 226）A,B,C,D問題メモ

def solve(n, meetings):
    acc = [0] * (n * 2 + 1)
    for s, t in meetings:
        acc[s] += 1
        acc[t] -= 1
    for i in range(n * 2):
        acc[i + 1] += acc[i]

    if max(acc) > 2:
        return 0

    zero = acc.count(0) - 1
    return pow(2, zero, 998244353)


n = int(input())
meetings = [list(map(int, input().split())) for _ in range(n)]
ans = solve(n, meetings)
print(ans)

• $T$: この解法で最大となった袋の重量
• $x$: 最大重量となった袋の内、「最後に入れた荷物の重さ」が最も重い袋
• $w$: $x$ に最後に入れた荷物の重さ

この時、解法に従えば、$x$ に $w$ を入れる直前、全ての袋の重量が等しく $T-w$ となっているはずである。

つまり、重さ $w$ 以上の荷物だけで、総重量は $N(T-w)+w$ 以上ある。 全ての荷物の重さは $w$ の倍数である点を考慮すると、 これだけの総重量を $N$ 個の袋に詰めるには、他の手法を採っても必ず最大重量が $T$ 以上になる。

from collections import defaultdict


def solve(n, m, aaa):
    bags = {0: n}
    for i in range(m - 1, -1, -1):
        a = aaa[i]
        p = 1 << i
        w = max(bags)
        new_bags = defaultdict(int)
        for b, c in bags.items():
            k = (w - b) // p
            if k * c <= a:
                a -= k * c
                new_bags[w] += c
            else:
                d, r = divmod(a, k)
                new_bags[w] += d
                if r == 0:
                    new_bags[b] += c - d
                else:
                    new_bags[b + p * r] += 1
                    new_bags[b] += c - d - 1
                a = 0

        bags = new_bags
        if a == 0:
            continue

        d, r = divmod(a, n)
        if r == 0:
            bags = {w + p * d: n}
        else:
            bags = {w + p * (d + 1): r, w + p * d: n - r}

    ans = max(bags)
    return ans


t = int(input())
for _ in range(t):
    n, m = list(map(int, input().split()))
    aaa = list(map(int, input().split()))
    ans = solve(n, m, aaa)
    print(ans)

def solve(h, w, h_offset=0, w_offset=0):
    if h <= 1 or w <= 1:
        return []

    def grid(h, w, h_offset, w_offset):
        ans = []
        for i in range(0, h - 1, 2):
            for j in range(0, w - 1, 2):
                ans.append(f'{i + h_offset + 1} {j + w_offset + 1} 1')
        return ans

    if h % 2 == 0 or w % 2 == 0:
        return grid(h, w, h_offset, w_offset)

    if h == 3 or w == 3:
        return grid(h, w, h_offset, w_offset)

    s = min(h, w)
    ans = []
    ans.append(f'{1 + h_offset} {1 + w_offset} {s - 1}')
    for i in range(3, s - 1, 2):
        ans.append(f'{1 + h_offset} {i + w_offset} 1')
        ans.append(f'{i + h_offset} {s - 1 + w_offset} 1')
        ans.append(f'{s - 1 + h_offset} {s - i + w_offset} 1')
        ans.append(f'{s - i + h_offset} {1 + w_offset} 1')
    ans.extend(solve(s - 4, s - 4, h_offset + 2, w_offset + 2))

    if h < w:
        ans.extend(solve(h, w - h, h_offset, w_offset + h))
    elif h > w:
        ans.extend(solve(h - w, w, h_offset + w, w_offset))
    return ans


def check(h, w, ans):
    field = [[-1] * w for _ in range(h)]
    for k, row in enumerate(ans):
        r, c, s = list(map(int, row.split()))
        r -= 1
        c -= 1
        for i, j in ((r, c), (r + s, c), (r, c + s), (r + s, c + s)):
            if field[i][j] != -1:
                print(f'Error {i} {j}')
                for row in field:
                    print(*row)
                raise AssertionError
            field[i][j] = k
    for row in field:
        print(*row)


t = int(input())
for _ in range(t):
    h, w = list(map(int, input().split()))
    ans = solve(h, w)
    print(len(ans))
    print('\n'.join(ans))

    # check(h, w, ans)

from collections import deque


class SortedQueues:
    def __init__(self):
        self.queues = [deque() for _ in range(5)]  # 物理キュー ①～⑤
        self.qa = self.queues[0]
        self.qe, self.qs, self.qm, self.ql = self.queues[1:]
        self.num = {id(q): i for i, q in enumerate(self.queues, 1)}
        self.shift = 0
        self.size = 0
        self.ops = []  # 直近の push でおこなったシフト操作列

    def _move(self, src, dst):
        dst.append(src.popleft())
        self.shift += 1
        self.ops.append((self.num[id(src)], self.num[id(dst)]))

    def _merge_to_e(self, sources):
        # sources: [キュー, 移す残数] のリスト。全要素を昇順に E へマージ
        total = sum(c for _, c in sources)
        for _ in range(total):
            best = None
            for src in sources:
                if src[1] > 0 and (best is None or src[0][0] < best[0][0]):
                    best = src
            self._move(best[0], self.qe)
            best[1] -= 1

    def push(self, x):
        """A に x を追加し、昇順維持のためにおこなったシフト操作列 [(from, to), ...] を返す"""
        self.ops = []
        qa = self.qa
        qa.append(x)
        self.size += 1
        if len(qa) > 1 and qa[-2] > x:
            qs, qm, ql = self.qs, self.qm, self.ql
            na = len(qa) - 1  # |A'|
            r = max(1.0, 0.5 * self.size ** (1 / 3))
            if r * (na + len(qs)) < len(qm):
                # a1) の行き先を事前シミュレーションしてコストを見積もる
                qsml = (qs, qm, ql)
                tails = [q[-1] if q else None for q in qsml]
                dests = []  # 各要素の行き先: 0..2=S/M/L, 'A'=ローテーション, 'E'=待避
                e_cnt = rot_cnt = 0
                for i, v in enumerate(qa):
                    if i == na:
                        break
                    best = None
                    for j, t in enumerate(tails):
                        if t is not None and t < v and (best is None or t > tails[best]):
                            best = j
                    if best is None:
                        for j, t in enumerate(tails):
                            if t is None:
                                best = j
                                break
                    if best is not None:
                        tails[best] = v
                        dests.append(best)
                    elif v < x:
                        dests.append('A')
                        rot_cnt += 1
                    else:
                        dests.append('E')
                        e_cnt += 1
                cost_a1 = na + e_cnt + (1 if rot_cnt else 0)
                cost_a2 = na + len(qs)
                if cost_a1 <= cost_a2:
                    # a1) S/M/L へ払い出せる要素は払い出し、残りはローテーション/E 待避で A を並べ直す
                    for dest in dests:
                        if dest == 'A':
                            self._move(qa, qa)
                        elif dest == 'E':
                            self._move(qa, self.qe)
                        else:
                            self._move(qa, qsml[dest])
                    if rot_cnt:
                        self._move(qa, qa)  # x を末尾へ回す
                    while self.qe:
                        self._move(self.qe, qa)
                    # 払い出しでサイズ序列が変わり得るので役割を再割り当て
                    self.qs, self.qm, self.ql = sorted(qsml, key=len)
                else:
                    # a2) Merge(A',S)→E し、E と S の役割を入れ替える
                    self._merge_to_e([[qa, na], [qs, len(qs)]])
                    self.qs, self.qe = self.qe, self.qs
            elif r * (na + len(qs) + len(qm)) < len(ql):
                # b) Merge(A',S,M)→E とし、E と M の役割を入れ替える
                self._merge_to_e([[qa, na], [qs, len(qs)], [qm, len(qm)]])
                self.qm, self.qe = self.qe, self.qm
            else:
                # c) Merge(A',S,M,L)→E とし、E と L の役割を入れ替える
                self._merge_to_e([[qa, na], [qs, len(qs)], [qm, len(qm)], [ql, len(ql)]])
                self.ql, self.qe = self.qe, self.ql
        return self.ops

    def pop(self):
        """全キュー中の最小値を pop し、そのキュー番号を返す (全て空なら None)"""
        best = None
        for q in self.queues:
            if q and (best is None or q[0] < best[0]):
                best = q
        if best is None:
            return None
        i = self.num[id(best)]
        best.popleft()
        self.size -= 1
        # pop でサイズ序列が変わり得るので役割を再割り当て
        self.qs, self.qm, self.ql = sorted((self.qs, self.qm, self.ql), key=len)
        return i

    def count(self):
        """現在までのシフト操作回数を返す"""
        return self.shift


def solve():
    q = int(input())
    sqs = SortedQueues()
    for _ in range(q * 2):
        query = input()
        if query[0] == "1":
            x = int(query[2:])
            result = sqs.push(x)
            print(len(result), flush=True)
            if len(result) > 0:
                print('\n'.join(f'{a} {b}' for a, b in result), flush=True)
        elif query[0] == "2":
            i = sqs.pop()
            print(i, flush=True)
        else:
            break


solve()