AtCoder Beginner Contest 154 に参加しました。考察を書いていきます。結果はぎりぎり滑りこんでの全完でした。
A - Remaining Balls
問題概要: 文字列 S の書かれたボールが A 個あり、文字列 T の書かれたボールが B 個ある。文字列 U が与えられる。文字列 U が書かれたボールを1つ捨てた。文字列 S, T の書かれたボールがそれぞれ何個残っているか求めよ。
制約:
- S≠T
- S=U または T=U
A: 考察
制約を見ると、S=T=U のケースは考えなくていいようです。
U=S なら A を1減らし、U=T なら B を1減らせばよいです。
筆者の提出 (Rust, AC): https://atcoder.jp/contests/abc154/submissions/9976949
B - I miss you...
問題概要: 英小文字からなる文字列 S が与えられる。S のすべての文字を x に置き換えたものを求めよ。
B: 考察
イテレータの map を使うと、「すべての文字を x に置き換える」を表現できます。
S.chars().map(|_| 'x').collect::<String>()
筆者の提出 (Rust, AC): https://atcoder.jp/contests/abc154/submissions/9972413
C - Distinct or Not
問題概要: 整数列 A(1), ..., A(N) が与えられる。どの2つの要素も互いに異なるかどうか判定せよ。
制約: 2≤N≤200000
C: 考察
「どの2つの要素も互いに異なる」は「すべての i, j (1≤i < j≤N) について A(i) ≠ A(j)」と形式化できます。しかし実際に i, j を列挙するループを回すと O(N^2) 時間かかり、実行時間制限を超過します。
解決策は複数ありますが、楽なのは集合 (std::collections::HashSet または std::collections::BTreeSet) を使う方法です。
集合には同じ要素が1つまでしか入らないので、A(i) の値をすべて集合に入れてみて、すべての値が集合に入ったら (= 要素数が N だったら) 重複がないと分かります。集合への要素の挿入は十分高速で、HashSet なら償却 O(1)、BTreeSet なら O(log N) です。全体で O(N) 時間となり、時間制限に間に合います。
筆者の提出 (Rust, AC): https://atcoder.jp/contests/abc154/submissions/9971129
別解として、ソートする方法が考えられます。もし A に同じ要素が含まれているなら、ソートするとそれらの要素は必ず隣接します。そのため、ソート後に隣接している要素のペアを調べるだけで、重複の有無を判定できます。判定に O(N) 時間、ソートに O(N log N) 時間なので間に合います。
D - Dice in Line
問題概要: N 個のサイコロが一列に並んでいる。左から i 番目のサイコロは、振ると 1 以上 p(i) 以下の整数が等確率で1つ出る。隣接する K 個のサイコロを選んでそれぞれ独立に振る。出る目の合計の期待値の最大値を求めよ。
制約: N≤200000
D: 考察
サイコロは左右の区別がつくので 1, 2 と 2, 1 が区別される点に注意。
例として K=N=2, p=(2, 3) の全事象を書き下してみます。
| 1つ目 | 2つ目 | 和 |
|---|---|---|
| 1 | 1 | 2 |
| 1 | 2 | 3 |
| 1 | 3 | 4 |
| 2 | 1 | 3 |
| 2 | 2 | 4 |
| 2 | 3 | 5 |
それぞれ確率 1/6 で起こるので、期待値は (2+3+4+3+4+5)/6 = 21/6 = 3.5 です。
期待値は 線形性 を持つので、「出目の合計の期待値」は「出目の期待値の合計」に一致します。実際、
- 1つ目のサイコロの出目の期待値は (1+2)/2 = 1.5
- 2つ目のサイコロの出目の期待値は (1+2+3)/3 = 2
なので、出目の期待値の合計は 3.5 になり、上で計算した「出目の合計の期待値」と一致しています。
そこで、i 番目のサイコロの期待値を計算して合計すれば K=N での答えが出せます。
(i 番目のサイコロの出目の期待値)
= 1/p(i) + 2/p(i) + ... + p(i)/p(i) (期待値の定義を使った)
= (1 + ... + p(i)) / p(i) (分子をまとめた)
= (1/2・p(i)・(p(i) + 1)) / p(i) (等比級数の公式を使った)
= 1/2・(p(i) + 1) (約分した)
= (p(i) + 1) / 2
(N 個のサイコロの出目の合計の期待値)
= (N 個のサイコロの出目の期待値の合計)
= (Σp(i) + N) / 2
次に K < N のケースも含めて考えます。幅 K の各区間について同様に和を計算すれば、最大値が求まります。しかし2重ループでこれをすると O(KN) 時間かかって TLE です。
和の計算を省略することを考えます。a+b+c+d+e の和が分かっているとき、b+c+d+e+f は (a+b+c+d+e)+f-a に変形すればたった2回の計算 (+f, -a) で計算可能です。
a+b+c+d+e
b+c+d+e+f
はじめに K 個の各サイコロの期待値の和を計算しておけば、残りの N-K 通りの区間における期待値の和は、期待値の足し引きにより O(1) で求まります。全体として O(N) 時間であり、間に合います。
筆者の提出 (Rust, AC): https://atcoder.jp/contests/abc154/submissions/9986685
E - Almost Everywhere Zero
問題概要: 正の整数 N が与えられる。1 以上 N 以下の整数で、10進数で表したときに0でない桁がちょうど K 個あるようなものを数えよ。
制約: N≤10^100, 1≤K≤3
E: 考察
問題のタイトル「ほとんど至るところゼロ」がヒントになっていて、最大で 100 桁もある整数のうち最大 K 桁しか 0 でないということは、逆にいうと、ほとんどの桁がゼロであるような整数を数えるということです。あーそういうことね。桁DPで解けそうです。
制約をよく見ると K が 1, 2, 3 の3通りしかありません。これは「桁 DP を書いても解けるけど、実は、手で場合分けしたら短いし O(1) でエレガント」というやつなのかな、と思って場合分けしてみました。
まず K=1 のときは、
- 一番上の桁が N と一致するケース (これを
=00と書きます)- 1通り
- 一番上の桁が N より小さく、0でないケース (これを
*00と書きます)- N の一番上の桁を d とすると d-1 通り
- 一番上の桁が 0 のケース (
090/009)- N を h 桁とすると h-1 個のどこかに 1-9 のどれかを配置すればいいので 9(h-1) 通り。
次に K=2 のときは、
- 一番上の桁が N と一致するケース
- 上から2桁目が 0 でないケース
- 上から2桁目も一致するケース (
==00)- 1通り
- 上から2桁目が N より小さく、0 でないケース (
=*00)- 上から2桁目を d2 とすると d2-1 通り
- 上から2桁目が 0 のケース
- (h-2) 桁のどこかに 1-9 なので 9(h-2) 通り。
- 上から2桁目も一致するケース (
- 上から2桁目が 0 でないケース
- ...
このあたりでやめておけばよかったんですが……。完全に方針ミスなので反省しています。
結局、次の典型的な桁 DP で解けます。
- dp 表
dp[i][k][eq] - 状態
- 上から i 桁は決定済み
- 上から i 桁のうち 0 でない数字は k 個
- 上から i 桁が N と一致するとき eq=1、そうでなければ eq=0
- 遷移
- 実装を参照
筆者の提出 (Rust, AC): https://atcoder.jp/contests/abc154/submissions/10004596
F - Many Many Paths
問題概要: 2次元平面上の点 (0, 0) から x または y 方向に 1 進む操作の繰り返しで点 (r, c) に至るまでの経路の個数を f(r, c) とおく。整数 r1, r2, c1, c2 が与えられる。f(r, c) (r1≤r≤r2, c1≤c≤c2) の総和を mod 10^9+7 で求めよ。
F: 考察
x 方向の移動を →、y 方向の移動を ↑ で表すと、(0, 0) から (r, c) への経路は r 個の → と c 個の ↑ の順列で表せます。(どこか見たことがありました。)
f(r, c) は (r+c) 個の矢印のうちどの r 個が → なのかを選ぶ場合の数なので、C(r+c, r) です。その総和を書いてみます。
Σ_r Σ_c (r+c)! / (r!・c!)
= Σ_r 1/(r!)・(Σ_c ((r+c)!/c!)) (1/(r!) を外側に移動した)
= ...?
内側のシグマをなんとかして高速に計算できたら間に合いますが、E問題で時間を溶かしたせいで考察する余裕がありません。無念。
ところで、Wolfram Alpha という便利なウェブサイトがあります。問題の数式を入力してボタンを押します。
sum (i + j)! / j! (j=c..d) - Wolfram|Alpha
出力:
$\sum_{j=c}^{d} \frac{(i + j)!}{j!}= \frac{\frac{(d + 1) \cdot (d + i + 1)!}{(d + 1)!} - \frac{c \cdot (c + i)!}{c!}}{i + 1}$
解けました！
筆者の提出 (Rust, AC): https://atcoder.jp/contests/abc154/submissions/10010458