AtCoder Beginner Contest 156 に参加したので、各問題の考察を書いていきます。結果はE完でした。
A - Beginner
問題概要: ButCoder の会員は内部レーティングと表示レーティングを持つ。その会員のコンテスト参加回数が10以上のときは、表示レーティングは内部レーティングに等しい。そうでなければ参加回数を K として、表示レーティングは内部レーティングから 100(10-K) を引いたものに等しい。コンテスト参加回数が N で、表示レーティングが R の会員の内部レーティングを求めよ。
A: 考察
求める内部レーティングを X とします。
N≥10 のとき、表示レーティングと内部レーティングは等しいので、X = R です。
N < 10 のとき、R = X - 100(10-K) なので X = R + 100(10-K) になります。
筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc156/submissions/10273771
B - Digits
問題概要: 整数 N を K 進数で表したときの桁数を求めよ。
B: 考察
K=10 で考えます。
小数点の移動を考えると分かりやすいかもしれません。例えば 31415 は5桁ですが、小数点を5回左に移動して 0.31415 とすると小数点が左端に来ます。
- 31415.0
- 3141.5
- 314.15
- 31.415
- 3.1415
- 0.31415
つまり、5桁の整数をちょうど5回 10 で割ると、はじめて整数部が 0 になりました。これを一般化して、「h 桁の整数をちょうど h 回 K で割ったら整数部が 0 になる」ような h を計算すれば OK です。
let mut x = N;
let mut h = 0;
while x > 0 {
x /= K;
h += 1;
}
println!("{}", h)
筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc156/submissions/10272846
形式的に考える場合は、まず「n が K 進数表記で h 桁である」を言い換えなければいけません。これは、0 以上 K 未満の整数からなる長さ h の数列 $(x_i)$ で、次の2つの条件をともに満たすものがあることです:
- $x_{h-1} \ne 0$ (一番上の桁がゼロでないこと)
- $n = \sum_{i=0}^{h-1} x_i K^i$
次に n を変形します。(イメージは 31415 ≤ 99999 < 10^5)
\begin{align}
n & = \sum_{i=0}^{h-1} x_i K^i & \\
& ≤ (K-1) \sum_{i=0}^{h-1} K^i & (x_i ≤ K-1 だから) & \\
& = (K-1) \cdot \frac{K^h-1}{K-1} & (\sum_{i=0}^{n-1} x^i = \frac{1-x^n}{1-x} だから) & \\
& = K^h-1 \\
& < K^h
\end{align}
したがって $\frac{n}{K^h} < 1$ なので、n を K で h 回以上割ればで整数部が 0 になるといえます。
一方、h-1 回目まで整数部が 0 にならないことは次の評価で示せます。(イメージは 31415/10^4 = 3.1415 ≥ 3 ≥ 1)
\begin{align}
\frac{n}{K^{h-1}}
& = \frac{\sum_{i=0}^{h-2} x_i K^i}{K^{h-1}} + x_{h-1} \\
& ≥ x_{h-1} \\
& ≥ 1 \\
\end{align}
C - Rally
問題概要: N 個の座標 X(i) が与えられる。座標 P に対して、(X(i) - P)^2 の総和をコストとする。コストの最小値を求めよ。
- 制約: 1≤X(i)≤100
C: 考察
座標 P と各位置 X(i) との距離 |X(i) - P| が大きいほどコストが重くなります。言い換えると、P は X(i) に近いほどコストが小さいです。そのため、P は真ん中＝平均値にするのが最適です。
とはいえ、制約から 1≤P≤100 が分かるので、この100通りをすべて試せばうかつな WA のリスクもなくせて、安心です。
筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc156/submissions/10272019
D - Bouquet
問題概要: n 種類の花が1本ずつある。1本以上の花からなる花束を作る。ただし、ちょうど a 本またはちょうど b 本からなる花束は作れないとする。作れる花束の種類の数を求めよ。(mod 10^9 + 7)
D: 考察
まず「1本以上」「ただし」を無視して、n 種類のものから好きな個数を選ぶ場合の数を考えます。部分集合の個数なので、2^n 通りです。ここから次の3パターンの花束を除外します。
- 0本の花束
- ちょうど a 本の花束
- ちょうど b 本の花束
制約から 0 < a < b なので、これら3パターンは互いに排反であり、単純に場合の数を引けばいいです。
0本の花束は1通りです。n 種類の花からちょうど a 種類を重複なく選ぶ場合の数は C(n, a) で表せます。b の方も、同様に、C(n, b) です。
問題は n が巨大なので、C(n, a) の計算を (n!)/(a! (n-a)!) でやる階乗DPが間に合わないことです。高校数学で C を手計算するときのように、以下の式を使えば O(a) 時間で間に合います。
C(n, a) = (n/a)・((n-1)/(a-1))・((n-2)/(a-2))・...・((n-a+1)/1)
筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc156/submissions/10278435
E - Roaming
問題概要: n 個の部屋がある。はじめ、各部屋にはちょうど1人いた。ちょうど k 回、人の移動 (1人が異なる部屋に移動すること) が起こった。建物の各部屋の人数の組み合わせの場合の数を求めよ。(mod 10^9 + 7)
E: 考察
「ちょうど」k 回、というのが厄介そうですが、n≥3 なので実は無視できます。k 回未満の移動で目的の組み合わせにできるなら、「無駄な移動」を挟むことでちょうど k 回の移動にできるからです。
例えば 部屋1 → 部屋2 という1回の移動を、部屋1 → 部屋3 → 部屋2 という2回の移動にできます。
そのため、無駄な移動を考える必要はありません。特に、誰かが退室した部屋に別の人が入る、というケースは考えなくてよいです。このことから、部屋を「はじめにいた人が退室する部屋」か否かで分類することが考えられます。
「はじめにいた人が退室する部屋」の個数を z (z≤k) とします。退室した人がどこに行くかは自由なので、これら z 人を残りの n-z 部屋に分配するすべての可能性があります。これは重複組み合わせで計算できます。
筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc156/submissions/10284738
F - Modularness
問題概要: 長さ k の非負整数列 d(i) が与えられる。q 個のクエリのそれぞれにおいて、非負整数 n, x, m が与えられる。a(j) を以下のように定めるとき、a(j) % m < a(j+1) % m となる整数 j (0≤j < n-1) の個数を求めよ。
- a(0) = x
- a(j+1) = a(j) + d(j % k)
F: 考察
整数の切り捨ての除算を x // y で書くことにします。
a(j) % m < a(j+1) % m となる j を数える代わりに、この不等式が成り立たない j を数えて n-1 から引くことにします。
a(j) % m ≥ a(j+1) % m となる j の個数は、次の2種類の条件を満たす j を別個に数えて足すことで求まります。
- a(j) % m = a(j+1) % m
- a(j) % m > a(j+1) % m
a(j+1) は定義に従って展開できます。
- a(j) % m = (a(j) + d(j % k)) % m
- a(j) % m > (a(j) + d(j % k)) % m
(=) の方は d(j % k) = 0 となる j の数で数えられるので、以下 d(j % k) ≠ 0 とします。
(>) の方は、a(j) に d(j % k) を足して余りが減ったということは余りが「一巡した」ということなので、a//m = (a + (d % m))//m - 1 がいえます。
- a(j) % m ≤ (a(j) + d(j % k)) % m のとき
- a(j)//m = a(j+1)//m
- a(j) % m > (a(j) + d(j % k)) % m のとき
- a(j)//m = a(j+1)//m - 1
数列 (a(j)//m) の値が増える回数と > の不等号が成立する回数が一致するので、> の不等号を満たす j の個数は a(n-1)//m - a(0)//m で求まります。
解説AC: https://atcoder.jp/contests/abc156/submissions/10311747
余りを使う問題で商を使う発想がなかったのが反省点でした。