AtCoder Beginner Contest 154 に参加しました。考察を書いていきます。結果はぎりぎり滑りこんでの全完でした。

前回: 競プロ参戦記 #70 Flatten | ABC 152
問題一覧: https://atcoder.jp/contests/abc154/tasks

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) 通り。
...

このあたりでやめておけばよかったんですが……。完全に方針ミスなので反省しています。

結局、次の典型的な桁 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