コンテンツにスキップ

ABC480 F - Cake Cutting

サイト
AtCoder
コンテスト
ABC480
問題
F - Cake Cutting
難易度
1840

大きさ A1,…,ANA_1, \dots, A_N の NN 個のケーキを MM 人に配ります。大きさの総和を SS とし、SS は MM の倍数です。ケーキを 1 つ選んで自由に 2 つに切り分ける操作を何回か行ったあと、全員がもらう大きさの合計がちょうど S/MS / M になるように配りたいです。操作回数の最小値を求める問題です(1≤N≤201 \le N \le 20、1≤M≤1001 \le M \le 100、1≤Ai≤1091 \le A_i \le 10^9)。

t=S/Mt = S / M とします。

ケーキを cc 個のグループに分けて、どのグループも大きさの和が tt の倍数になるようにできたとします。このとき、操作回数 M−cM - c で配れます。グループを順に一列に並べて、先頭から長さ tt ずつ切っていけばよいからです。M−1M - 1 か所の切れ目のうち、グループの境目にある c−1c - 1 か所はケーキを切らずに済むので、切る回数は高々 (M−1)−(c−1)=M−c(M - 1) - (c - 1) = M - c です。

逆に、どんな配り方でも操作回数は M−cM - c 以上です。ケーキと人を頂点とし、人がケーキの一部をもらっているときにその 2 つを辺で結んだグラフを考えます。各辺は 1 つ以上の切れ端に対応するので、切れ端の個数は辺の本数 EE 以上です。1 回の操作で切れ端は 1 個増えるので、操作回数は E−NE - N 以上です。グラフの連結成分の個数を cc とすると、頂点は N+MN + M 個なので E≥N+M−cE \ge N + M - c で、操作回数は M−cM - c 以上になります。各連結成分のケーキの大きさの和は、そこに含まれる人数の tt 倍です。また、どの人もケーキをもらうので、どの連結成分にもケーキが含まれます。よって、連結成分ごとにケーキを分ければ、和が tt の倍数になる cc 個のグループができます。

したがって答えは、「ケーキを、大きさの和がどれも tt の倍数になるようにグループ分けするときのグループの個数の最大値」を cc として、M−cM - c です。

ケーキを一列に並べて、先頭からの和が tt の倍数になる位置で区切ると考えれば、グループ分けは並べ方と対応します。グループの個数は、先頭からの和が tt の倍数になる位置の個数(最後のケーキの後ろも含む)です。

そこで、ケーキの集合 UU に対して、dp[U]\mathrm{dp}[U] を「UU のケーキを先頭に並べるとき、UU の中で先頭からの和が tt の倍数になる位置の個数の最大値」とします。UU の最後に置くケーキ ii で場合分けすると、

dp[U]=max⁡i∈U(dp[U∖{i}]+[∑j∈UAj≡0(modt)])\mathrm{dp}[U] = \max_{i \in U} \left( \mathrm{dp}[U \setminus \{i\}] + [\textstyle\sum_{j \in U} A_j \equiv 0 \pmod t] \right)

です。[⋯ ][\cdots] は条件が成り立てば 11、成り立たなければ 00 を表します。答えは M−dp[{1,…,N}]M - \mathrm{dp}[\{1, \dots, N\}] です。

計算量は O(2NN)O(2^N N) です。

C++
#include "shogo-library/base/all"
#include "shogo-library/utility/bit.hpp"
#include "shogo-library/utility/container_func.hpp"
void solve() {
LL(N, M);
VL(A, N);
ll t = sum(A) / M;
val<2> dp(1 << N, al<2>{-1, 0});
dp[0] = {0, 0};
rep(u, 1, 1 << N) {
for (auto [i, v] : remove_one(u)) {
ll y = (dp[v][1] + A[i]) % t;
chmax(dp[u], al<2>{dp[v][0] + (y == 0), y});
}
}
print(M - dp.back()[0]);
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

dp[u] は 2 つの値の組で、dp[u][0] が上の dp[U]\mathrm{dp}[U]、dp[u][1] が UU のケーキの大きさの和を tt で割った余りです。余りは UU だけで決まるので、組を辞書順で chmax しても、dp[u][0] の最大値がとられます。remove_one(u) は、u に含まれる位置 i と、u から i を除いた集合 v の組を列挙します。

使用ライブラリ:cpp_include@9c33ee7