| A | B | C | D | E | F | |
| 問題文 | ■ | ■ | ■ | ■ | ■ | ■ |
| 自分の提出 | ■ | ■ | ■ | ■ | ■ | ■ |
| 結果 | AC | AC | AC | AC | AC | AC |
全体感想
今日もかなりのんびりやっていましたが、全完はできました。
問題F、なかなか面白かったです。単純に考察で10分以上かかりました。
問題C – Rally
$n$ 次元空間上に点 $\vect{p_1},\ldots, \vect{p_k}$ があって、$\sum_i \lvert \vect{p}-\vect{p_i}\rvert^2$ を最小化したいとき、$P$ を $P_i$ の重心にとるのがベスト。という豆知識。
$\lvert \vect{p}-\vect{p_i}\rvert^2 = (\vect{p}-\vect{p_i})\cdot(\vect{p}-\vect{p_i})$ を各座標軸に沿って微分するとすぐに分かります。
今回は、重心に近い整数座標をとればよいです。まぁ私は$0$ 以上 $100$ 以下を全探索しました。
問題D – Bouquet
問題 E – Roaming
まずは、「ちょうど $k$ 回の移動で作れる人数構成」がどのようなものかを考えないといけません。
具体的な人数構成を想像して、何回で作れるかを考えると、最小回数が評価できそうな気持ちになります。そこからもう少し考えていきましょう。今回は、部屋が3つ以上あるため、1回の移動を2回に分解することができます。よって、最小の移動回数が $k$ 以下であれば、ちょうど $k$ 回の移動も可能です。
合計人数が $n$ であるような人数構成に対して、最小の移動回数を達成する場合、ある部屋に対して「出る人数」「入る人数」がどちらも正であることはありえません（出て入る移動を合成できるため）。結局、
- $\sum_i a_i = n$
- $\sum_i \max(0, a_i-1) = \sum_i\max(0, 1-a_i) \leqq k$
を満たす人数構成がすべて実現できることが分かります。
あとは最小移動回数 $i$ を軸に場合分けして計算すればよいです。「出る移動」の選び方が$\binom{n}{i}$ 通りあり、これに「入る移動」の選び方が掛け算されます。「入る移動」は、$n-i$部屋に$i$個のものを割り振る方法の数ですが、これは高校数学典型の重複組み合わせです。
なお、形式的べき級数解釈もあります。(移動回数、人数の過不足)を状態に持たせて形式的べき級数をつくり、$1$ 部屋分の遷移をべき級数にエンコードします：\[f = x^{-1}t + 1 + xt + x^2t^2 + \cdots = x^{-1}t + \frac{1}{1-xt}\]
$f^n$ において、$t$ について $k$ 次以下、$x$ について定数の部分を集計すればよくて、$\bigl(x^{-1}t + \frac{1}{1-xt}\bigr)^n$ を二項展開すれば結局同じ式が出てきます。いずれにせよ、$k$ 回以下で移動できるかの判定問題については乗り越えておく必要があるでしょう。
問題F – Modularness
共通の前処理を準備しようと思うと手がかりが見つかりませんでしたが、どうせクエリごとに $\Theta(K)$ 程度はかけてもよいのだから、完全に独立な問題と思ってしまおうとすると気持ちが楽になりました。
$d_i< m$ としてよいです。$a_j = mq_j + r_j$ とすると、$d_j < m$ のもとで、$r_j$ が減少するのは、「繰り上がる場合」つまり$q_{j} = q_{j-1} + 1$ の場合に限られます。「繰り上がりの回数」の合計を計算する問題に帰着されるので、$a_0$ と $a_{n-1}$ の値のみから答が計算できることが分かります。
ちょっとうそで、$d_i = 0$ のときも除外しないといけませんね。私は $0\leqq d_i < m$ としましたが、$0 < d_i \leqq m$ とした方が処理が簡潔になるようです。
