DOJ logoDOJ
ログイン新規登録
DOJ logoDOJ
問題募集
DOJ logoDOJ

OI形式のサブタスク採点、Eloレーティング、Discord連携を備えたオンラインジャッジです。

問題
問題一覧カテゴリ
コミュニティ
コンテストランキング掲示板お知らせ外部のコンテストを開催するガイド
アカウント
ログイン新規登録ジャッジ状態
ポリシー
利用規約DLCの利用規則プライバシーAPI 文書言語ランタイムコンテストの順位報酬レーティングとパフォーマンス
© 2026 DOJ
All rights reserved
問題
最近追加された問題保存した問題Workbooks
カテゴリDLCコンテストグループチーム掲示板
ランキング
正解数ランキングストリークランキングDOJ Powerランキング
提出状況
解説

働くダダス

問題に戻る

解説

候補の整列とチェーン 各モジュールの候補を性能の昇順に並べ、整列後の性能と消費量を bi,j,ci,jb_{i,j},c_{i,j}bi,j​,ci,j​ とする。性能と消費量の組を崩さずに整列する。

di,k=bi,k+1−bi,k≥0(1≤k<Ai).d_{i,k}=b_{i,k+1}-b_{i,k}\geq 0\qquad(1\leq k<A_i).di,k​=bi,k+1​−bi,k​

モジュール iii に Ai−1A_i-1Ai​−1 個の頂点 vi,1,…,vi,Ai−1v_{i,1},\ldots,v_{i,A_i-1}v を作り、, とする。 が始点側にあることは、選んだ候補の番号が より大きいことを表す。各 について、逆向きの辺 の容量を無限大にする。有限容量のカットでは始点側の頂点が接頭部分となり、順方向のチェーン辺がちょうど 本切れる。 の場合も の辺 本で表せる。

積の分解 鉱山のモジュールを入力順に u,vu,vu,v とし、選んだ性能を Bu,BvB_u,B_vBu​,Bv​ とする。

−BuBv=−bv,1Bu−bu,AuBv+bu,Aubv,1+(bu,Au−Bu)(Bv−bv,1).-B_uB_v=-b_{v,1}B_u-b_{u,A_u}B_v+b_{u,A_u}b_{v,1}+(b_{u,A_u}-B_u)(B_v-b_{v,1}).−Bu​B

最後の項は ∑k,ldu,kdv,l[vu,k∈T][vv,l∈S]\sum_{k,l}d_{u,k}d_{v,l}[v_{u,k}\in T][v_{v,l}\in S]∑k,l​du,k​d である。各 , について、 に容量 の辺を追加する。増分が の辺は省略してよい。同じ組のモジュールを使う鉱山も個別に処理する。

単項費用と答えの復元

αi=∑k:Uk=ibVk,1+∑k:Vk=ibUk,AUk,qi(j)=ci,j−αibi,j.\alpha_i=\sum_{k:U_k=i}b_{V_k,1}+\sum_{k:V_k=i}b_{U_k,A_{U_k}},\qquad q_i(j)=c_{i,j}-\alpha_i b_{i,j}.αi​= K=1+max⁡(0,max⁡i,j(−qi(j))).K=1+\max\left(0,\max_{i,j}(-q_i(j))\right).K=1+max(0,i,jmax​(−q

各 1≤j≤Ai1\leq j\leq A_i1≤j≤Ai​ について、順方向の辺 vi,j−1→vi,jv_{i,j-1}\to v_{i,j}vi の容量を とする。この値は正である。候補の選択と有限カットは一対一に対応する。カット容量は純利益の符号を反転した値に を加えた値なので、最小カットを求めればよい。

answer=MK−mincut⁡−∑k=1NbUk,AUkbVk,1.\text{answer}=MK-\operatorname{mincut}-\sum_{k=1}^{N}b_{U_k,A_{U_k}}b_{V_k,1}.answer=MK−mincut−k=1∑

数値範囲と計算量 答えは −49 998-49\,998−49998 以上 999 999 998999\,999\,998999999998 以下である。αi≤106\alpha_i\leq10^6αi​≤10, , , が成り立つ。鉱山 個の罰則容量の合計は である。有限容量の総和は 未満なので、無限大として を使える。すべての演算は符号付き ビット整数に収まる。

頂点数は V≤452V\leq452V≤452、追加する辺数は E≤82 000E\leq82\,000E≤82000 である。残余逆辺は別に保持する。Dinic 法の一般的な時間計算量は O(V2E)O(V^2E)O(V2E)、空間計算量は である。

サブタスク サブタスク 1 では候補の組合せを全列挙する。時間計算量は O((N+M)∏iAi)O((N+M)\prod_i A_i)O((N+M)∏i​Ai​) で、組合せは最大 10610^6 個である。サブタスク 2 では各モジュールの二択を最大 個の頂点で表す最小カットを使う。サブタスク 3 では完全なチェーンを使う。別の正解コードでは による閾値展開を実装し、構成を照合する。

Solution written by GPT6

≥
0(1≤
k<
Ai​).
i,1
​
,
…
,
vi,Ai​−1​
vi,0=Sv_{i,0}=Svi,0​=S
vi,Ai=Tv_{i,A_i}=Tvi,Ai​​=T
vi,kv_{i,k}vi,k​
kkk
1≤k≤Ai1\leq k\leq A_i1≤k≤Ai​
vi,k→vi,k−1v_{i,k}\to v_{i,k-1}vi,k​→vi,k−1​
111
Ai=1A_i=1Ai​=1
S→TS\to TS→T
111
v
​
=
−bv,1​Bu​−
bu,Au​​Bv​+
bu,Au​​bv,1​+
(bu,Au​​−
Bu​)(Bv​−
bv,1​).
v,l​
[
vu,k​
∈
T][vv,l​∈
S]
1≤k<Au1\leq k<A_u1≤k<Au​
1≤l<Av1\leq l<A_v1≤l<Av​
vv,l→vu,kv_{v,l}\to v_{u,k}vv,l​→vu,k​
du,kdv,ld_{u,k}d_{v,l}du,k​dv,l​
000
k:Uk​=i∑​
bVk​,1​
+
k:Vk​=i∑​bUk​,AUk​​​,qi​(j)=
ci,j​−
αi​bi,j​.
i​
(
j
))
)
.
,
j
−
1
​
→
vi,j​
K+qi(j)K+q_i(j)K+qi​(j)
MK−∑kbUk,AUkbVk,1MK-\sum_k b_{U_k,A_{U_k}}b_{V_k,1}MK−∑k​bUk​,AUk​​​bVk​,1​
N
​
bUk​,AUk​​​
bVk​,1​
.
6
1−109≤qi(j)≤10001-10^9\leq q_i(j)\leq10001−109≤qi​(j)≤1000
K≤109K\leq10^9K≤109
MK≤5⋅1010MK\leq5\cdot10^{10}MK≤5⋅1010
111
(bu,Au−bu,1)(bv,Av−bv,1)≤9992(b_{u,A_u}-b_{u,1})(b_{v,A_v}-b_{v,1})\leq999^2(bu,Au​​−bu,1​)(bv,Av​​−bv,1​)≤9992
5.01⋅10115.01\cdot10^{11}5.01⋅1011
101510^{15}1015
646464
O(V+E)O(V+E)
O(V+E)
106
111
−wxy=wx(1−y)−wx-wxy=wx(1-y)-wx−wxy=wx(1−y)−wx