estie プログラミングコンテスト2025 （AtCoder Regular Contest 210）A,B,C,D,E問題メモ

estie プログラミングコンテスト2025 （AtCoder Regular Contest 210）

う～む、昨日のABCに続きあっさり解けるはずの問題でハマってるなあ。

A - Always Increasing

問題文

長さ $N$ の正整数列 $A=(A_1,A_2,\ldots,A_N)$ に対して，$Q$ 回の操作を行います．
$q$ 回目の操作は $A_{i_q}$ に $x_q$ を加算するというものです．
あなたの目標は，$A$ の初期状態を適切に定めることで，どの時点においても（つまり，初期状態および各操作の直後においても）以下の条件が成り立つようにすることです．
- $0\lt A_1 \lt A_2 \lt \cdots \lt A_N$ が成り立つ．

この目標を達成するとき，$A$ の初期状態における要素の総和として考えられる最小値を求めてください．

制約

$2\leq N\leq 2\times 10^5$
$1\leq Q\leq 2\times 10^5$
$1\leq i_q\leq N$
$1\leq x_q\leq 10^5$
入力される値はすべて整数．

解法

「初期状態」を求めるというのが罠(?)で、「最終状態」を考えて、そこから途中で足された $x_q$ を全て引く方が考えやすい。

また狭義単調増加は考えづらいので、$0$ 以上の広義単調増加として答えを求め、後から全てに $A_i+=i$ するとよい。

差分配列 $D_i=A_{i}-A_{i-1}$ を考える。先頭と末尾にもとりあえず値は持っておく。

i     1   2   3   4
A     0   2   5   5
i   1   2   3   4  (5)
D   0   2   3   0   0

$A_i$ に $x$ を足すということは、$D_i$ に $x$ を足し、$D_{i+1}$ から $x$ を引くことに相当する。

この時、$D_{i+1} \lt 0$ になってしまうと単調増加に違反してしまう。
負の場合はここを強制的に $0$ にすることで単調増加を保てる。
（言い換えると、「元から、ギリギリ負にならない値だったことにしてしまう」）

$D=(0,0,...)$ からスタートして、負が発生したら $0$ にするという方針で最後まで $D$ を更新して累積和で復元すると、最終状態として最小の $A$ が求まる。
その総和から、途中で足された $x_q$ を全て引くと答えとなる。

Python3

from itertools import accumulate


def solve(n, q, queries):
    ddd = [0] * n
    x_sum = 0
    for i, x in queries:
        i -= 1
        x_sum += x
        if i == n - 1:
            ddd[i] += x
            continue
        ddd[i + 1] = max(0, ddd[i + 1] - x)
        ddd[i] += x

    ans = n * (n + 1) // 2 - x_sum
    ans += sum(accumulate(ddd))
    return ans


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

B - Remove Median Operations

問題文

長さ $N$ の整数列 $A=(A_1,A_2,\ldots,A_N)$ および，長さ $M$ の整数列 $B=(B_1,B_2,\ldots,B_M)$ が与えられます．
ここで $N$ は偶数です．
$Q$ 個のクエリが与えられます．
- $t_q=1$ の場合：$A_{i_q}$ を $x_q$ に変更する．
- $t_q=2$ の場合：$B_{i_q}$ を $x_q$ に変更する．

クエリを処理するたびに，次の小問題の答を求めてください．
- 多重集合 $X$ を $X=\lbrace A_1,A_2,\ldots,A_N\rbrace$ で初期化します．
- $j=1,2,\ldots,M$ に対して次の操作を行います：
  - $X$ に $B_j$ を挿入する．その後，$X$ の中央値を $X$ からひとつ削除する．
- すべての操作が終了したときの $X$ の要素の総和を求めてください．

制約

$1\leq N,M,Q\leq 2\times 10^5$
$N$ は偶数．
$1\leq A_i\leq 10^9$
$1\leq B_i\leq 10^9$
$t_q\in\lbrace 1,2\rbrace$
$t_q=1$ ならば $1\leq i_q\leq N$
$t_q=2$ ならば $1\leq i_q\leq M$
$1\leq x_q\leq 10^9$
入力される値はすべて整数．

解法

仮にクエリが無く、初期状態の $A,B$ で小問題を素直に解くことを考えると、以下のイメージになる。

$A$ を値の小さい方と大きい方 $\frac{N}{2}$ 個ずつに分ける。
- 小さい方は、大きい値から取り出せるヒープキュー $S$ に入れる。
- 大きい方は、小さい値から取り出せるヒープキュー $L$ に入れる。
$j=1,2,...,M$ の順に、$B_j$ をどっちかに入れるか、捨てる。
- $B_j \lt S.top$ なら、$S$ に入れて、最大値を取り出して捨てる。
- $S.top \le B_j \le L.top$ なら、$B_j$ を捨てる。
- $L.top \lt B_j$ なら、$L$ に入れて、最小値を取り出して捨てる。
最終的な $S,L$ に入っている値が、$X$ に残っている要素である。

この操作を考えると、結局、「$A$ と $B$ を合わせた多重集合から、小さい方 $\frac{N}{2}$ 個と大きい方 $\frac{N}{2}$ 個」が残ることになり、 $A$ や $B$ の順番には依らないことが分かる。

略証

座標圧縮をした上で、FenwickTreeを2本用意して値毎の個数と総和を管理しておく。

変更クエリは特に難しくない。

値を求める際は、個数のFenwickTree上で二分探索して、上下から $\frac{N}{2}$ 個となる箇所を見つければよい。

同じ値が複数含まれる場合に注意。
「$\frac{N}{2}$ 個目に当たる値は $3$ だけど、$4$ 個ある $3$ の中で $2$ 個しか要らない」みたいなことがあるので、余剰分は加えないようにする。

Python3

from operator import add, lt


class FenwickTreeInjectable:
    def __init__(self, n, identity_factory, func):
        self.size = n
        self.tree = [identity_factory() for _ in range(n + 1)]
        self.func = func
        self.idf = identity_factory
        self.depth = n.bit_length()

    def add(self, i, x):
        i += 1
        tree = self.tree
        func = self.func
        while i <= self.size:
            tree[i] = func(tree[i], x)
            i += i & -i

    def sum(self, i):
        i += 1
        s = self.idf()
        tree = self.tree
        func = self.func
        while i > 0:
            s = func(s, tree[i])
            i -= i & -i
        return s

    def lower_bound(self, x, lt):
        """
        累積和がx以上になる最小のindexと、その直前までの累積和

        :param lt: lt(a, b) で a < b ならTrueを返す関数
        """
        total = self.idf()
        pos = 0
        tree = self.tree
        func = self.func
        for i in range(self.depth, -1, -1):
            k = pos + (1 << i)
            if k > self.size:
                continue
            new_total = func(total, tree[k])
            if lt(new_total, x):
                total = new_total
                pos += 1 << i
        return pos, total

    def debug_print(self):
        prev = 0
        arr = []
        for i in range(self.size):
            curr = self.sum(i)
            arr.append(curr - prev)
            prev = curr
        print(arr)


def solve(n, m, q, aaa, bbb, queries):
    values = set(aaa)
    values.update(bbb)
    for t, i, x in queries:
        values.add(x)
    values.add(0)
    values = sorted(values)
    mapping = {a: i for i, a in enumerate(values)}

    n2 = len(values)
    fwt_count = FenwickTreeInjectable(n2, int, add)
    fwt_total = FenwickTreeInjectable(n2, int, add)
    for a in aaa:
        i = mapping[a]
        fwt_count.add(i, 1)
        fwt_total.add(i, a)
    for b in bbb:
        i = mapping[b]
        fwt_count.add(i, 1)
        fwt_total.add(i, b)

    hl = n // 2
    hr = n + m - n // 2
    buf = []
    for t, i, x in queries:
        i -= 1
        if t == 1:
            p = aaa[i]
            aaa[i] = x
        else:
            p = bbb[i]
            bbb[i] = x
        pi = mapping[p]
        xi = mapping[x]
        fwt_count.add(pi, -1)
        fwt_count.add(xi, 1)
        fwt_total.add(pi, -p)
        fwt_total.add(xi, x)

        j, acc_cnt1 = fwt_count.lower_bound(hl, lt)
        k, acc_cnt2 = fwt_count.lower_bound(hr + 1, lt)
        ans = fwt_total.sum(j - 1) + (hl - acc_cnt1) * values[j]
        ans += fwt_total.sum(n2 - 1) - fwt_total.sum(k - 1) - (hr - acc_cnt2) * values[k]
        buf.append(ans)
    return buf


n, m, q = list(map(int, input().split()))
aaa = list(map(int, input().split()))
bbb = list(map(int, input().split()))
queries = [list(map(int, input().split())) for _ in range(q)]
ans = solve(n, m, q, aaa, bbb, queries)
print('\n'.join(map(str, ans)))

C - Fair Coin Partition

問題文

$N$ 種類のコインがあります．
$i=0,1,...,N-1$ 種類目のコインは価値が $10^{i}$ で，あなたはこのコインを $A_i$ 枚所持しています．
これらのコインを，$M$ 人に配ることにしました．
- ただし，$1$ 人あたりに配るコインの価値の総和が等しくなるようにします．
- また，配らないコインがあってもよいです．
$1$ 人あたりに配るコインの価値の総和としてありうる最大値を求めてください．

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

制約

$1\leq T\leq 10^5$
$1\leq N\leq 2\times 10^5$
$1\leq M\leq 10^9$
$0\leq A_i\leq 10^9$
すべてのテストケースにわたる $N$ の総和は $2\times 10^5$ 以下．
入力される値はすべて整数．

解法

$10^{200000}$ など桁数がとんでもないことになるので、問題を解きつつ巨大な整数を上手く管理する、という複合的な問題となる。

まず、以下の情報を計算する。

$C_i:=$ コイン $i-1$ 以下のコインの総額は、コイン $i$ 何枚分に相当するか（切り捨て）

$C_0=0$ であり、$i=1,2,...$ の順に $C_i=(A_{i-1}+C_{i-1})/10$ として計算できる。

例えば以下のようになる。$N=5$ で、$M=7$ 人に配るとする。

N=5  M=7
i   0   1   2   3   4
A  10 650 500  50  20
C   0   1  65  56  10

まずは最大価値のコイン4の分配を考える。

コイン4だけなら $20/7=2$ 枚ずつしか配れないが、 $C_4$ も含めて考えると $(20+10)/7=4$ 枚（に相当する価値）ずつ配ることができる。
この時、コイン3以下からは、コイン4の $配る枚数 \times M - A_4 = 4 \times 7 - 20 = 8$ 枚分の価値を借りていることになる。

「コイン3以下から、コイン4の $8$ 枚分の価値を借りている」という情報を持ちつつ、コイン4を $4$ 枚ずつ配ったことにする。

コイン $i$ の価値はコイン $i-1$ の価値の倍数なので、総額さえ足りていれば必ず分配できる。
言い換えると、コイン3以下から構成される「総額 $k \times 10^4$ のコイン群」は、必ず「総額 $10^4$ のコイン群 $k$ 個」に分割でき、1人1人にコイン4の $1$ 枚相当のコイン群を配ることができる。（「総額では足りているが、きっちりと $10^4$ のコイン群 $k$ 個に分ける手段がない」可能性は考慮しなくていい）

※この方法とは逆に、「コイン4は $2$ 枚ずつ配り、残りをコイン3 $60$ 枚分の価値として繰り下げる」という方法をとると、「コイン4を0.5枚Aさんに、0.5枚Bさんに分配する」みたいな分配方法まで可能だと見なしてしまう場合があるため上手くいかなくなる。

次、コイン3を何枚ずつ分配するかだが、借金をまず返す。
コイン3の $1$ 枚とコイン2の $10$ 枚では、コイン2の方が分配の柔軟性の面で必ず優位なので、借金はなるべく大きいコインで返してよい。

現在の借金はコイン4 $8$ 枚分＝コイン3 $80$ 枚分に当たるが、コイン3は $50$ 枚しかないので、借金は返しきれない。この場合、コイン3 $30$ 枚分の借金が残っているとして、次に引き継ぐ。コイン3の分配は $0$ 枚となる。

コイン2では借金を返しても $200$ 枚残る。残りをコイン4の時と同様に分配する。
$(A_2の残り + C_2)/M = (200+65)/7 = 37$ 枚ずつ配れる。借金はコイン2 $37 \times 7 - 200 = 59$ 枚分となる。

これをコイン0まで繰り返すと、各コイン（に相当する価値）を何枚ずつ配れるか、求められる。

       i   0   1   2   3   4
配る枚数   1   8  37   0   4

後は、下の桁から繰り上げていき、各枚数を $10$ 未満にする。
逆転させて文字列として結合すれば、答えとなる。

       i   0   1   2   3   4
配る枚数   1   8   7   3   4    →  43781

Python3

def solve(n, m, aaa):
    cap = [0] * n  # i 未満のコインを全て集めると、コイン i 何枚分の支払いが可能か
    for i in range(1, n):
        cap[i] = (cap[i - 1] + aaa[i - 1]) // 10

    res = [0] * (n + 100)
    rent = 0
    for i in range(n - 1, -1, -1):
        rent *= 10
        if aaa[i] <= rent:
            rent -= aaa[i]
            continue
        aaa[i] -= rent
        d = (aaa[i] + cap[i]) // m
        res[i] += d
        rent = max(0, d * m - aaa[i])

    ans = []
    carry = 0
    for c in res:
        c += carry
        d, r = divmod(c, 10)
        ans.append(r)
        carry = d
    while len(ans) > 1 and ans[-1] == 0:
        ans.pop()
    ans.reverse()
    ans = ''.join(map(str, ans))
    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)

D - Independent Set Game

問題文

$N$ 頂点 $M$ 辺の単純無向グラフ $G$ が与えられます．
$G$ の頂点にははじめ色が塗られていません．
Alice と Bob が $G$ を使ってゲームをします．Alice と Bob は $t=1,\ldots,N$ の順に次の行動を行います．
- $t$ が奇数ならば，Alice がまだ色の塗られていない頂点をひとつ選び，その頂点を黒色で塗る．
- $t$ が偶数ならば，Bob がまだ色の塗られていない頂点をひとつ選び，その頂点を白色で塗る．
$N$ 回すべての行動が終わった時点で，黒色で塗られた頂点全体が $G$ の独立集合であれば Alice が勝者，そうでなければ Bob が勝者となります．両者が最適に行動した場合の勝者の名前を出力してください．
$T$ 個のテストケースが与えられるので，それぞれについて解いてください．

制約

$1\leq T\leq 2\times 10^5$
$2\leq N\leq 2\times 10^5$
$0\leq M\leq 2\times 10^5$
$1\leq u_i \lt v_i \leq N$
与えられるグラフは単純無向グラフである．
すべてのテストケースにわたる $N$ の総和は $2\times 10^5$ 以下．
すべてのテストケースにわたる $M$ の総和は $2\times 10^5$ 以下．

解法

かな～りAliceに不利なゲームであることはわかるが、細部を詰めるのが非常に難しい。

公式Editorialでは、証明の観点から「頂点数2,3,5などの連結成分やループを含むか」で場合分けしている。
本番では、考察が詰まったら愚直と全探索テストケースを書いて漏れを見つけていく、というのが着実に見える。

単純な言い換え

Bobの操作は「グラフから1頂点を選んで取り除く」と言い換えることができる。
最終的にAliceの選んだ黒い頂点が全て孤立頂点の状態になっていればAliceの勝ちとなる。

「まだ取り除かれてもおらず、色も塗られていない、黒に隣接する頂点」を「悪い頂点」とする。
Aliceは悪い頂点を塗ってしまうと負けとなる。
Bobの方も、Aliceに悪い頂点を塗らせたい（＝悪い頂点しか残っていない状態でAliceに手番を回したい）ので、基本的には悪い頂点以外を潰していくという戦法となりそう。

$N$ 奇数の時

とりあえず、$N$ 奇数の時は簡単。最後の手番がAliceになる。
Aliceは悪い頂点を「1つでも発生」させてしまった瞬間、負けが確定する。
AliceもBobも、悪い頂点を最後まで残し続けるので、最後にAliceが塗らざるを得ない。

つまりAliceは、実質的に孤立頂点しか塗れない。

最初から孤立した頂点は塗れる
サイズ2の連結成分があり、Bobに1つ取り除かせることができれば、孤立頂点が発生するのでもう一方を塗れる

一方、Bobの最適手を考えると、孤立頂点をまずAliceと交互に潰していく。
潰しきった直後がAliceの手番なら勝ちだし、 Bobの手番でもサイズ3以上の連結成分があればそちらを取り除くことで、孤立頂点がない状態でAliceに手番を回せる。

逆に潰しきった直後がBobでサイズ2しか残っていなければ、Aliceの勝ちとなる。

つまり「奇数個の孤立頂点」と「サイズ2の連結成分」のみからなる場合のみ、Aliceの勝ちとなる。

$N$ 偶数の時

最後に塗るのがBobなので、奇数の時よりは少しだけAliceが勝ちやすくなる。

悪い頂点を2個以上、同時に発生させるとAliceの負けが確定する。
（AliceもBobもその2頂点を残し続け、最後から2手目で詰む）

（最適性は証明できてないが、なんとなく）両者、孤立頂点から潰していくのがよさそう。
その後を考える。

孤立頂点が偶数個

孤立頂点が無くなった状態でAliceの手番となる。

次数2以上の頂点を塗ると悪い頂点が2個以上発生してアウトなので、次数1の頂点を選んで塗る。
それによってできる1個の悪い頂点は「AliceもBobも最後まで残し続け、最終的にBobが取り除く」と考えれば、はじめから無かったものと考えられる。

$N$ が奇数の時に帰着でき、Aliceがさっき塗ったのは孤立頂点と見なせる。
無かったことにする頂点は次数1に隣接する中でAliceが自由に選べる。

最初からサイズ3以上の連結成分が無い場合はAliceの勝ち。

サイズ3以上の連結成分がある場合、それが「ある1頂点に、サイズ1または2の成分がくっついた連結成分」が、1つだけあるならよい。

      ○--○
       ＼／      ●を塗り、◎をはじめから無かったものとすると、
○--○--◎--●   全てサイズ2以下の連結成分に分かれる
       ／＼
      ○--○     ※頂点数の偶奇から、サイズ1がくっついた成分(●)が必ず1個以上存在する

このような形状のグラフを「花グラフ」（勝手に命名）とする。

初期状態で「サイズ3以上の連結成分が高々1つであり、存在する場合はそれが花グラフ」の場合はAliceの勝ち。
それ以外はBobの勝ちとなる。

孤立頂点が奇数個

孤立頂点が無くなった状態でBobの手番となる。

前提として、頂点数の偶奇から、サイズ3以上はかならず $1$ 個以上存在する。

Bobは、サイズ2から取り除くとAliceはもう片方を塗るので状況が変わらない。
いずれサイズ3以上から頂点を取り除くことになる。

ここで、「Bobは新たな孤立頂点を生まないような頂点を取り除く」のがよい。
孤立頂点を生むようなら、その孤立頂点の方を取り除いた方が辺を多く残せ、悪い頂点を発生させる上で上位互換となる。
その結果、孤立頂点が無い状態でAliceに手番が回り、先ほどの「孤立頂点が偶数個」の時に帰着できる。

Bobがどの頂点を取っても「孤立頂点が偶数個」の場合にAliceが勝つ形にしかできないなら、Aliceの勝ちとなる。

サイズ3以上の連結成分が2個以上ある場合、偶奇から、少なくとも一方はサイズ4以上である。
Bobは「サイズ3以上の連結成分が2つ以上」にして帰着できるのでBobの勝ち。

Aliceが勝つためには、やはりサイズ3以上は初期状態で1つでなければならない。
（必然的に、その1個のサイズは奇数となる）

その1個が花グラフの場合は、どの頂点を取り除いても花グラフが保たれるのでAliceの勝ちとなる。

それ以外では？
「どの1頂点を取り除いても花グラフとなる」ような、花グラフでないグラフは存在するか？

サイズ5では、全探索すると、以下の2種類が条件を満たす。

○--○--○  ○ ○ ○
 \      /    \/  \/
  ○--○     ○--○

サイズ7以上は無さそう。
「花グラフに1頂点追加して花グラフで無くなったグラフ」は、以下のいずれかである。（※花びら:花の中心を取り除いて分割される個々の成分）

①サイズ2の花びらに1頂点を追加する
②2個以上の花びらを、新たな1頂点を介して結ぶ

①の場合、Bobは他の花びらから取り除く頂点を選ぶことでサイズ3の花びらを残すことができ、勝てる。
（サイズ5の右図の時は、他の花びらが1頂点のみであり、これを取り除くと“花の中心”を都合良く変えることができたため、Aliceが勝てたが、サイズ7以上は無理）

②の場合、「3つ以上の花びらを結ぶと、サイズ3以上の花びらが必ず残る」ので、結ぶ花びらは2個しかない。
2つを結んだ場合、必ず「長さ4以上のループ」が生成され、また他の花びらが1頂点は存在する。
正しい花グラフに、長さ4以上のループは発生し得ない。Bobは長さ4以上のループを残し、花グラフとならないようにできる。

よって、「サイズ3以上が1つのみ、その1つが花グラフまたは上記の2つの場合、Aliceの勝ち」となる。

Python3

from atcoder.dsu import DSU


def solve(n, m, edges):
    uft = DSU(n)
    links = [[] for _ in range(n)]
    for u, v in edges:
        u -= 1
        v -= 1
        uft.merge(u, v)
        links[u].append(v)
        links[v].append(u)

    groups = uft.groups()

    if n % 2 == 1:
        for grp in groups:
            if len(grp) > 2:
                return False
        return True

    def judge_gt2(grp):
        n = len(grp)
        d3 = [v for v in grp if len(links[v]) > 2]
        if len(d3) >= 2:
            if n == 5 and sum(len(links[v]) == 1 for v in grp) == 2:
                return True
            return False
        if len(d3) == 0:
            edge_count = sum(len(links[v]) for v in grp) // 2
            if n < edge_count:
                return False
            if n == edge_count:
                return n == 3 or n == 5
            return n <= 5
        u = d3[0]
        lu = set(links[u])
        for v in grp:
            if u == v:
                continue
            if len(links[v]) - (v in lu) >= 2:
                return False
        return True

    gt2 = 0
    for grp in groups:
        l = len(grp)
        if l <= 2:
            continue
        if gt2 >= 1:
            return False
        if judge_gt2(grp):
            gt2 += 1
            continue
        return False

    return True


t = int(input())
for _ in range(t):
    n, m = map(int, input().split())
    edges = [tuple(map(int, input().split())) for _ in range(m)]
    ans = solve(n, m, edges)
    if ans:
        print('Alice')
    else:
        print('Bob')

E - Subset Sum Gaps

問題文

正整数列 $A=(A_1,A_2,\ldots,A_N)$ が与えられます．
$A$ の部分列は，要素の添字の違いを区別すれば，$2^N$ 個あります．これらの各部分列の総和を昇順に列挙したものを，$S_1, S_2, \ldots, S_{2^N}$ とします．
整数 $k$ （$1\leq k\leq 2^N-1$）であって，$1.01 \times S_k\leq S_{k+1}$ を満たすものすべてについて，$S_k, S_{k+1}, (k\bmod 998244353)$ を出力してください．

制約

$2\leq N\leq 5000$
$1\leq A_i\leq 10^{13}$

解法

誤った解法

実際に $N=15$ くらいのランダムサンプルでやってみると、条件を満たす $k$ は最初と最後の方に集中しがちな様子が見られる。
最初の方は 1 つとか 2 つしか選択しない場合の部分和となりがちなので、飛び飛びになりやすい。最後の方も（最初の方より $0.01$ 相当が大きくなるので条件は若干狭まるが） 1つや2つのみを選択しない場合となるので、やはり飛び飛びになりやすい。逆に中ごろの値は、様々な部分列により達成可能となり密になりやすい。

なので、最初と最後の $10^6$ 要素くらいのみ愚直に求めてみればよい？
……と考えたが、やはりそのような雑な考察ではWAとなった。
例えば $A$ に同じ要素が多く含まれるときなどで上手くいかないことがわかる。

なお（本問題の解法とは関係ないが）「とても $2^N$ 個の部分和を全て求めてソートすることはできないが、小さい方から $K$ 個の部分和を列挙したい」という場合、$A_i$ が全て非負なら Dijkstra の要領で $O(K \log{K})$ でおこなえる。

$A$ をソートする。
全てを選ばない場合=$0$ を、最小の部分和として記録する。
$(A[0],0)$ を優先度付きキューに追加する。
- (現在の部分和, 使用した最も大きいindex) を表す
以下を $K-1$ 回行う
- キューから取り出した値を $(a,i)$ とする。$a$ が次に大きい部分和である。
- $i=N-1$ でない場合、以下の2つをキューに追加する。
  - $(a-A[i]+A[i+1], i+1)$
  - $(a+A[i+1], i+1)$
  - つまり、$i+1$ を、$i$ を使わなかったことにして使うか、そのまま使うか。

正しい解法

仮に $O(2^N)$ かけて全ての部分和を列挙する場合、以下のような方法がオーソドックスである。

$S=[0]$ で初期化する
$i=1,2,...,N$ の順に、
- $S$ に $S_k + A_i$（$k=1,2,...,|S|$）を追加する。

この時、ポイントなのが、以下の事実である。

ある $i$ で、$S_k \times 1.01 \gt S_{k+1}$ となった2数があるとする。
その2数から派生する最終的なペア（2数に対する $j=i+1$ 以降の $A_j$ が足される・足されないのパターンが同じ2数）の1つを $(a,b)$ とする。
この時、$a \times 1.01 \le b$ となることは絶対にない。
- ∵ $b-a = S_{k+1}-S_k \lt S_k \times 0.01 \le a \times 0.01$

そして $i$ を進めて行くにつれ、$a,b$ の間にまた他の部分和が入ってきたり、隣り合う2区間 $(a_1,b_1),(a_2,b_2)$ が $b_1 \times 1.01 \gt a_2$ となるなどで、どんどんと集合として統合されていく。

この統合された部分は答えとなることが無いので、区間としてまとめて最小値・最大値を管理しておけば十分である。

上記の部分和列挙のアルゴリズムを、$(暫定部分和の最小値,最大値,要素数)$ で管理するように変更し、 $i$ を進めるたびに、隣り合う区間との比が $1.01$ 未満となったものは統合していけばよい。

答えの個数の上限を考えると、$S$ の最大値が $5000 \times 10^{13} = 5 \times 10^{16}$ 程度であり、 $\log_{1.01}{(5 \times 10^{16})} \simeq 3864$ なので、$3864$ 個以下となることが分かる。

$|S|$ は $i=1,2,...$ を進める過程で常にこれ以下になるので、$O(N \log(N \max(A)))$ で解ける。

Python3

def solve(n, aaa):
    MOD = 998244353

    def add_queue(q, s, t, c):
        if len(q) == 0:
            q.append((s, t, c))
            return
        if q[-1][1] * 101 <= s * 100:
            q.append((s, t, c))
            return
        s2, t2, c2 = q.pop()
        q.append((s2, max(t, t2), (c + c2) % MOD))

    aaa.sort()
    q = [(0, 0, 1)]
    for a in aaa:
        aq = [(s + a, t + a, c) for s, t, c in q]
        nq = []
        i = 0
        j = 0
        while i < len(q) and j < len(aq):
            if q[i][0] <= aq[j][0]:
                add_queue(nq, *q[i])
                i += 1
            else:
                add_queue(nq, *aq[j])
                j += 1
        for ii in range(i, len(q)):
            add_queue(nq, *q[ii])
        for jj in range(j, len(aq)):
            add_queue(nq, *aq[jj])
        q = nq
        # print(f'{a=} {q=}')

    ans = []
    idx = 0
    for i in range(len(q) - 1):
        s1, t1, c1 = q[i]
        s2, t2, c2 = q[i + 1]
        idx = (idx + c1) % MOD
        ans.append(f'{t1} {s2} {idx}')
    return ans


n = int(input())
aaa = list(map(int, input().split()))
ans = solve(n, aaa)
print(len(ans))
print('\n'.join(ans))

目次

estie プログラミングコンテスト2025 （AtCoder Regular Contest 210）A,B,C,D,E問題メモ

A - Always Increasing

問題文

制約

解法

B - Remove Median Operations

問題文

制約

解法

C - Fair Coin Partition

問題文

制約

解法

D - Independent Set Game

問題文

制約

解法

単純な言い換え

$N$ 奇数の時

$N$ 偶数の時

孤立頂点が偶数個

孤立頂点が奇数個

E - Subset Sum Gaps

問題文

制約

解法

誤った解法

正しい解法