ARC 118
Table of Contents
A. Tax Included Price
https://atcoder.jp/contests/arc118/tasks/arc118_a
B. Village of M People
https://atcoder.jp/contests/arc118/tasks/arc118_b
解説 AC.
二分探索を使って upper bound を探索するところまでは思いついたが、$B$ を構築できるかの判定が甘くて自力で AC できなかった。
$\max_i |\frac{B_i}{M} - \frac{A_i}{N}| = \frac{1}{MN} \max_i | NB_i - MA_i |$ より $\max_i | NB_i - MA_i |$ の最小化問題に帰着できる。
$\max_i | NB_i - MA_i | \leq D$ となる $D$ が存在するとき
\begin{align*} -D \leq NB_i - MA_i \leq D \\ -D + MA_i \leq NB_i \leq D + MA_i \\ \frac{-D + MA_i}{N} \leq B_i \leq \frac{D + MA_i}{N} \end{align*}
ここで $B_i$ は非負整数だから
\begin{align*} \max\left(0, \left\lceil \frac{-D + MA_i}{N} \right\rceil \right) \leq B_i \leq \left\lfloor \frac{D + MA_i}{N} \right\rfloor \end{align*}
$L = \sum_i \max\left(0, \left\lceil \frac{-D + MA_i}{N} \right\rceil \right)$, $R = \sum_i \left\lfloor \frac{D + MA_i}{N} \right\rfloor $ とすると $L \leq M \leq R$ のとき、$|NB_i - MA_i| \leq D$ を満たす正数列 $B$ が存在する。
$B$ の構築の仕方は、始め $B_i$ を上限で初期化しておいて、余分な分を各 $B_i$ から引いていく。このとき、下限未満にはできないことに注意
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
ll K, N, M;
cin >> K >> N >> M;
vll A(K);
rep(i, K) cin >> A[i];
auto cal = [&](ll d) -> bool {
ll rsum = 0;
for (ll a : A) {
rsum += (d + M * a) / N;
}
ll lsum = 0;
for (ll a : A) {
lsum += (max(0ll, (-d + M * a)) + N - 1) / N;
}
return lsum <= M && M <= rsum;
};
ll ac = INF, wa = -1;
while (ac - wa > 1) {
ll wj = (ac + wa) / 2;
if (cal(wj))
ac = wj;
else
wa = wj;
}
vll B;
rep(i, K) {
B.push_back((ac + M * A[i]) / N);
}
ll ndel = accumulate(all(B), 0ll) - M;
rep(i, K) {
if (ndel == 0)
break;
ll lower = (max(0ll, (-ac + M * A[i])) + N - 1) / N;
ll x = min(ndel, B[i] - lower);
B[i] -= x;
ndel -= x;
}
print(B);
}
C. Coprime Set
https://atcoder.jp/contests/arc118/tasks/arc118_c
$N = 3$ のとき、最小の3つの数字の組み合わせは $6 = 2 \times 3$, $10 = 2 \times 5$, $15 = 3 \times 5$ である。 これら3つの数字に加えて $6, 10, 15$ の倍数を追加しても正数列 $A$ を構成できる。
- $P$: $10000$ 以下の $6$ の倍数
- $Q$: $10000$ 以下の $10$ の倍数
- $R$: $10000$ 以下の $15$ の倍数
とする。$n(X)$ を事象 $X$ の場合の数とする。
\begin{align*} n(P) &= \floor{\frac{10000}{6}} = 1666 \\ n(Q) &= \floor{\frac{10000}{10}} = 1000 \\ n(R) &= \floor{\frac{10000}{15}} = 666 \\ n(P \cap Q) &= \floor{\frac{10000}{\mathrm{lcm}(6, 10)}} = \floor{\frac{10000}{30}} = 333 \\ n(P \cap R) &= \floor{\frac{10000}{\mathrm{lcm}(6, 15)}} = \floor{\frac{10000}{30}} = 333 \\ n(R \cap R) &= \floor{\frac{10000}{\mathrm{lcm}(10, 15)}} = \floor{\frac{10000}{30}} = 333 \\ n(P \cap Q \cap R) &= \floor{\frac{10000}{\mathrm{lcm}(6, 10, 15)}} = \floor{\frac{10000}{30}} = 333 \end{align*}
\begin{align*} n(P \cup Q \cup R) &= n(P) + n(Q) + n(R) \\ &~~~ - n(P \cap Q) - n(P \cap R) - n(Q \cap R) \\ &~~~ + n(P \cap Q \cap R) \\ &= 1666 + 1000 + 666 - 3 \times 333 + 333 \\ &= 2666 \end{align*}
よって、$2500$ 個の数字を工面することができる。
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int N;
cin >> N;
set<int> ans = {6, 10, 15};
set<int> tmp;
rep2(i, 2, N) {
for (int x : ans) {
if (i * x <= 10000)
tmp.insert(i * x);
}
}
for (int x : tmp) {
if ((int)ans.size() == N)
break;
ans.insert(x);
}
int i = 0;
for (int x : ans) {
if (i != 0)
cout << ' ' << x;
else
cout << x;
i++;
}
cout << endl;
}
D. Hamiltonian Cycle
https://atcoder.jp/contests/arc118/tasks/arc118_d
E. Avoid Permutations
https://atcoder.jp/contests/arc118/tasks/arc118_e