【競プロ精進日記】AtCoder ABC156

2020.03.18
競プロ

1. はじめに
2. A
3. B
4. C
5. D
6. E
7. F

はじめに

当ブログは問題の解説がメインではなく、筆者の解法やアイデアの保存がメインです。
したがって、読者の期待に沿えないことがあると思いますがご了承ください。

A

A – Beginner
題意に従う
https://atcoder.jp/contests/abc156/submissions/10971833

B

B – Digits
10進数Nの桁数を求める式$\lfloor\log_{10}{N}\rfloor + 1$と全く同じ要領で計算します。
（公式解説ではNがKで何回割れるかを調べていました。）
K進数Nの桁数を求めるには$\lfloor\log_{K}{N}\rfloor + 1$を計算するだけです。
しかし、ほとんどのプログラミング言語には任意の底の対数を計算する関数が実装されていないため、自分で変換します。
$$\log_ab=\frac{\log_cb}{\log_ca}$$
なので出力する答えは下記のようになります。
$$\left\lfloor \frac{\log_eN}{\log_eK} \right\rfloor + 1$$
https://atcoder.jp/contests/abc156/submissions/10973118

C

C – Rally
$1\leq N\leq 100, 1\leq X_i\leq 100$であり、適切なPの位置は人々の座標の範囲内であるので（Pが左端・右端になる場合は適切でない）、Pを100回試しその都度体力の総和を計算すれば最大10000回で計算できます。
しかし今回は$O(N)$で計算しましょう。
適切なPの位置について考えます。
直感では人々の座標の平均、すなわち重心の位置で体力の総和が最小になる気がします。
証明してみましょう。
N人が消費する体力の総和を計算する関数$f(X)$は次のように定義できます。
$$ f(X) = \sum(X_i-P)^2 $$
この関数が最小になるPを式変形によって求めます。
$$ f(X) = \sum(X_i^2 – 2PX_i + P^2) $$
$$ = \sum X_i^2 – 2P\sum X_i + \sum P^2 $$
$$ = \sum X_i^2 – 2P\sum X_i + NP^2 $$
この関数が最小になるPは微分すると簡単に求まります。
$$ f'(X) = -2\sum X_i + 2NP $$
関数$f'(X)=0$となる$P$が最小なので、
$$ 2\sum X_i = 2NP $$
$$ P = \frac{\sum X_i}{N} $$
したがって、人々の座標の平均値で体力の総和が最小になることが証明できました。
$P$の位置を$O(N)$で計算し、体力の総和$\sum(X_i-P)^2$を$O(N)$で求めるので、この問題を$O(N)$で計算できました。
https://atcoder.jp/contests/abc156/submissions/10972002

D

D – Bouquet
花束の本数$ k $からできる花束の種類は$ _nC_k $通りです。
したがって、花束の本数をa,b除いたすべてに対して求めればよいので、
$$ _nC_1+_nC_2+\ldots+_nC_n \ – _nC_a \ – _nC_b$$
が答えですが、これでは$ O(n) $かかり最大で$ 10^9 $回の計算が必要で間に合いません。
ここで式変形を行います。
二項定理より、
$$ (1+1)^n= _nC_0+_nC_1+_nC_2+\ldots+_nC_n = 2^n $$
となるので、
$$ _nC_1+_nC_2+\ldots+_nC_n = 2^n – 1 $$
と変形できます。
これは繰り返し二乗法によって$O(\log n)$で計算できます。
したがって元の式は下記のようになります。
$$ 2^n – 1 \ – _nC_a \ – _nC_b $$
組み合わせの分母は逆元で計算すること、差のmodを取るときはmodを加えることに注意しましょう。
https://atcoder.jp/contests/abc156/submissions/10972229

E

E – Roaming
自力で解けなくて解説を見ました。組み合わせ系の問題とても苦手です。
組み合わせ系の問題を解くポイント（定石？）はある数を固定したときの組み合わせを考えるらしいです（どこかの解説ページで見た）。
この問題では、誰もいない部屋（0人の部屋）がいくつあるかを固定して考えます。
0人の部屋の数を$m$としましょう。
すると$n$人の部屋から$m$人を選ぶ組み合わせは$_nC_m$通り。
選ばれた$m$人を0人でない$n-m$部屋に分配する組み合わせは$_{n-m}H_m$通りになります。
※$_{n-m}H_m$：$n-m$部屋から重複を許して$m$部屋を選ぶ組み合わせ（各部屋は区別されるので311と113とかもちゃんと区別される）
したがって、0人の部屋の数が$m$部屋の時の各部屋にいる人の組み合わせは下記のようになります。
$$ _nC_m \times _{n-m}H_m$$
$$ =_nC_m \times _{n-1}C_m \ldots (1)$$
$$ なぜなら _nH_r = _{n+r-1}H_r $$
よって、0人の部屋の数$m$をすべてに対して計算すれば答えが求まります。
$n <= k$の場合0人の部屋の数の最大は$n-1$です（最も移動したとしても1部屋に全員集まるのが最大、それ以上に何回移動してもこれを超えることはないため$k$が$m$よりいくら大きくても関係ない）。 $n > k$の場合0人の部屋の数の最大は$k$です（k回しか移動できないのでk人が別の部屋に移動したときが0人の部屋の数が最大）。
$n$と$k$の大小により、最大の$m$まで$(1)$を計算した総和が答えになります。
組み合わせ$C$は$_nC_r=_nC_{r-1}\times \frac{n-r+1}{r}$と分数をかけて更新していき、分数の分母は逆元を繰り返し二乗法で計算することで$O(min(n,k)\log{MOD7})$で求まります。
https://atcoder.jp/contests/abc156/submissions/10986245