AtCoder Beginner Contest 156 に参加したので、各問題の考察を書いていきます。結果はE完でした。

前回: 競プロ参戦記 #71 Many Many Paths | ABC 154
問題一覧: https://atcoder.jp/contests/abc156/tasks

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

余りを使う問題で商を使う発想がなかったのが反省点でした。