ABC480 F - Cake Cutting
- サイト
- AtCoder
- コンテスト
- ABC480
- 問題
- F - Cake Cutting
- 難易度
- 1840
大きさ の 個のケーキを 人に配ります。大きさの総和を とし、 は の倍数です。ケーキを 1 つ選んで自由に 2 つに切り分ける操作を何回か行ったあと、全員がもらう大きさの合計がちょうど になるように配りたいです。操作回数の最小値を求める問題です(、、)。
とします。
答えの言い換え
Section titled “答えの言い換え”ケーキを 個のグループに分けて、どのグループも大きさの和が の倍数になるようにできたとします。このとき、操作回数 で配れます。グループを順に一列に並べて、先頭から長さ ずつ切っていけばよいからです。 か所の切れ目のうち、グループの境目にある か所はケーキを切らずに済むので、切る回数は高々 です。
逆に、どんな配り方でも操作回数は 以上です。ケーキと人を頂点とし、人がケーキの一部をもらっているときにその 2 つを辺で結んだグラフを考えます。各辺は 1 つ以上の切れ端に対応するので、切れ端の個数は辺の本数 以上です。1 回の操作で切れ端は 1 個増えるので、操作回数は 以上です。グラフの連結成分の個数を とすると、頂点は 個なので で、操作回数は 以上になります。各連結成分のケーキの大きさの和は、そこに含まれる人数の 倍です。また、どの人もケーキをもらうので、どの連結成分にもケーキが含まれます。よって、連結成分ごとにケーキを分ければ、和が の倍数になる 個のグループができます。
したがって答えは、「ケーキを、大きさの和がどれも の倍数になるようにグループ分けするときのグループの個数の最大値」を として、 です。
bit DP
Section titled “bit DP”ケーキを一列に並べて、先頭からの和が の倍数になる位置で区切ると考えれば、グループ分けは並べ方と対応します。グループの個数は、先頭からの和が の倍数になる位置の個数(最後のケーキの後ろも含む)です。
そこで、ケーキの集合 に対して、 を「 のケーキを先頭に並べるとき、 の中で先頭からの和が の倍数になる位置の個数の最大値」とします。 の最後に置くケーキ で場合分けすると、
です。 は条件が成り立てば 、成り立たなければ を表します。答えは です。
計算量は です。
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][1] が のケーキの大きさの和を で割った余りです。余りは だけで決まるので、組を辞書順で chmax しても、dp[u][0] の最大値がとられます。remove_one(u) は、u に含まれる位置 i と、u から i を除いた集合 v の組を列挙します。
使用ライブラリ:cpp_include@9c33ee7