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

ユニークビジョンプログラミングコンテスト2026 夏（AtCoder Regular Contest 226）

A - Meeting Division

問題文

$1,2, \dots ,N$ の番号がついた $N$ 個の会議があります。会議 $i$ の開始時刻は $S_i$、終了時刻は $T_i$ です。
高橋君と青木君は、各会議に $2$ 人のうちちょうど一方を担当者として割り当てようとしています。正の長さの時間帯で重なる $2$ 個の会議を同じ人が担当することはできません。より厳密には、会議 $i$ と会議 $j$ を同じ人が担当することができるのは、$T_i \le S_j$ または $T_j \le S_i$ を満たすときに限ります。
条件を満たす担当者の割り当て方の個数を $998244353$ で割った余りを求めてください。

制約

$1 \le N \le 3 \times 10^5$
$1 \le S_i \lt T_i \le 2N$
$S_1,T_1,S_2,T_2,\dots,S_N,T_N$ は全て異なる
入力される値は全て整数

解法

まず、imos法などによって、同時におこなわれる最大会議数を求める。「$S_1,T_1,S_2,T_2,\dots,S_N,T_N$ は全て異なる」という制約があるので、ある会議が終わった瞬間に別の会議が始まる可能性はない。実装が少し楽。

最大同時会議数が $3$ 以上なら不可能。$0$ 通り。

$2$ 以下の場合、可能なのだが、2つの系統が互いに重なり合う関係になっている場合、途中で系統を交替することはできない。

系統1   |--------| |-----| |-----------| ...  ←どちらかはずっと高橋君、
系統2     |--| |-----| |----| |--| |-|   ...    もう一方はずっと青木君でないといけない

交替することができるのは、両方の系統で会議が行われていないタイミングに限られる。

                                         v ここ
系統1   |--------| |-----| |-----------|   |---| |---| ...
系統2     |--| |-----| |----| |--| |-|       |-----|   ...

この回数は、imos法で累積和が $0$ になった回数と一致する。その回数を $k$ とし、$2^k$ が答え。

Python3

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)

B - Bin-ary Packing

問題文

$1,2,\dots,N$ の番号がついた $N$ 個の袋があります。また、各 $i=0,1,\dots,M-1$ について、重さ $2^i$ の荷物が $A_i$ 個あります。荷物は合計 $A_0+A_1+\dots+A_{M-1}$ 個です。
全ての荷物を、それぞれいずれか $1$ 個の袋に入れます。空の袋があっても構いません。
各袋について、その袋に入っている全ての荷物の重さの総和を袋の重量と呼びます。
$N$ 個の袋の重量の最大値としてあり得る最小の値を求めてください。

$T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

$1 \le T \le 10^5$
$1 \le N \le 10^6$
$1 \le M \le 40$
$0 \le A_i \le 10^6$
全てのテストケースにおける $M$ の総和は $2 \times 10^5$ 以下
入力される値は全て整数

解法

わりと、素直な発想をそのまま実装するだけ、という問題に感じた。

重い荷物からなるべく均等に詰めていく。
均等というのはつまり、「その時点で最も重量が軽い袋を1つ選び、そこに入れる」ことを繰り返すのが正当な手法となる。

重さ $2^i$ までの荷物を詰めた結果、袋 $p,q$ の間で重量に差ができても、その差分 $|w_p-w_q|$ は、$2^{i-1}$ より軽い荷物ならいずれも（個数が足りれば）必ずぴったり埋めることができる。

同じ重量の袋はまとめて管理する。
$S=\{0:N\}$ で初期化する。暫定重量 $0$ の袋が $N$ 個あることを意味する。

$i=M-1,M-2,...,0$ の順に、以下をすればいい。

その時点の $S$ の最大重量を $W$ とする。
重量 $W$ 未満の重さの袋に、$W$ まで荷物を詰めていく。
途中で $A_i$ が無くなったらそれまで。端数も忘れないように詰め、次の $i$ へ。
全て $W$ まで詰め終えても $A_i$ が残っていたら、$N$ 個に残りをなるべく均等に配る。

最終的に全ての袋の中で最大重量が答えとなる。

正当性の略証

$S$ のサイズ（袋の重量の種類数）は、1つの $i$ を処理する毎に高々 $1$ つ増えるのみである。
よって1つのケース $O(M^2)$ で求めることができる。

もし暫定重量の同じ袋をまとめない場合、1つのケースに $O(NM)$ かかってしまう。テストケース全体を通しての $N$ の総和に対する制約はないので、これだとTLEとなる。

Python3

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)

C - Square Corner Packing

問題文

$H$ 行 $W$ 列のマス目があります。上から $i$ 行目、左から $j$ 列目のマスを $(i,j)$ と表します。
はじめ、全てのマスは白です。
以下の操作を好きな回数行います。
- 以下の条件を全て満たす整数 $r,c,s$ を選び、マス $(r,c),(r+s,c),(r,c+s),(r+s,c+s)$ を黒く塗る。
  - $1\le r\lt r+s\le H$
  - $1\le c\lt c+s\le W$
  - マス $(r,c),(r+s,c),(r,c+s),(r+s,c+s)$ が全て白。
行うことができる操作回数の最大値を求め、その最大値を達成する操作列を $1$ つ出力してください。

$T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

$1\le T\le 500$
$2\le H,W\le 500$
全てのテストケースにおける $HW$ の総和は $250000$ 以下
入力される値は全て整数

解法

「正方形の角になる4マス」を、被らないようになるべく多く取りなさい、という問題。

できる操作の自由度が高すぎて、しばらく「$2 \times 2$ を敷き詰めれば自明では？」となってしまった。
実際、$H$ または $W$ が偶数なら、それが正解となる。

1つの操作毎に、行・列ともに、$2$ マスが必ず塗られる。
$H$ が奇数なら、各列ごとに、必ずどこか1マス以上の奇数マス、塗れないマスができる。
$W$ が奇数なら、各行ごとに、必ずどこか1マス以上の奇数マス、塗れないマスができる。

$2 \times 2$ を敷き詰める解法は、$H$ または $W$ が偶数の場合、この「絶対に塗れない最小個数」を除いて全て塗ることを達成できる。

曲者なのは、$H,W$ がともに奇数の時である。
そのまま $2 \times 2$ 解法だと $H+W-1$ 個のマスが残ってしまうが、「どの行・どの列にも必ず1マス以上奇数個の白マスがある」という状態の白マスの最小個数は $\max(H,W)$ である。

問題の操作で塗れるかどうかは一旦無視して、例えば以下のように白マスを残すことができれば、 $2 \times 2$ 解法より多くの操作ができることになる。

□■■■■■■■■
■□■■■■■■■
■■□■■■■■■
■■■□■■■■■
■■■■□□□□□

小さいケースからあれこれ試行錯誤する。ひとまず対称性を頼りに構築しやすい正方グリッドから。

$1 \times 1, 3 \times 3$ は、さすがに全探索が容易で、無理とわかる。

$5 \times 5$ 以上は、外側の $2$ マスずつを以下のように埋めることで、最小を達成しつつ、$N-4$ のケースに帰着できる。

1 . 2 2 3 3 4 4 1
d d 2 2 3 3 4 4 .
d d . . . . . 5 5
c c . . . . . 5 5
c c . . . . . 6 6
b b . . . . . 6 6
b b . . . . . 7 7
. a a 9 9 8 8 7 7
1 a a 9 9 8 8 . 1

この時、$N=5,9,13,...$ のように、$4$ で割って $1$ 余る奇数なら最小で埋められるが、 $N=3,7,11,...$ のように $3$ 余る奇数の場合は最後で $3 \times 3$ が残り、どうしても最小より $2$ マス、余分に白マスが生じてしまう。
ただ、1回の操作では必ず $4$ マスが塗られるので、塗るマスを $2$ マスだけ増やすことは不可能である。よって、後者の場合もこれが最適であることが確認できる。

正方グリッドでは無い場合、短辺側の端に、$N=\min(H,W)$ とした正方グリッドの場合の答えを作る。
そうすると残った部分は一方が偶数になるので、$2 \times 2$ 解法が最適となる。

Python3

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)

目次

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

A - Meeting Division

問題文

制約

解法

B - Bin-ary Packing

問題文

制約

解法

C - Square Corner Packing

問題文

制約

解法