| A | B | C | D | E | F | |
| 問題文 | ■ | ■ | ■ | ■ | ■ | ■ |
| 自分の提出 | ■ | ■ | ■ | ■ | ■ | ■ |
| 結果 | AC | AC | AC | AC | AC | AC |
全体感想
31分6完で、24位でした。 簡単回なのに頭が全然働いてなくてめちゃくちゃバグはまりしてしまって悲しんだ……のですが、順位はそんなに悪くなくてびっくりしました。
最近の参加者レベルでいくと、また4桁人数が全問解くような難易度だと思っていたのですが、そうでもなかったみたいです。
問題C – Distinct or Not
len(set(A)) あるいは、 len(np.unique(A)) など。
問題D – Dice in Line
ダイスの和の期待値は、各ダイスの期待値の和です（期待値の線形性）。よって、$\frac{1+p_i}{2}$ の長さ $K$ の区間和を全部計算できればよいです。
区間和は、累積和の事前計算のもと、1件あたり $\Theta(1)$ で計算できます（$\sum_{i=L}^R a_i = \sum_{i=0}^{R} a_i – \sum_{i=0}^{L-1} a_i$）。
Pcum = np.zeros(N + 1, np.int32)
Pcum[1:] = P.cumsum()
length_K_sums = Pcum[K:] - Pcum[:-K]
print(length_K_sums.max() / 2)Pcum[K:] - Pcum[:-K]）はスライスで簡潔に。よく出てくるので、numpy を使うなら覚えておくいいですね。問題E – Almost Everywhere Zero
- $r$ が $1, 2, 3, 4$ のどれかの場合：
条件 $n\leqq 314$ は、$m\leqq 31$ と同値です。また、$1$ の位で「$0$ でない数字」を 1 回消費するので、$m$ に現れる「$0$ でない数字」は $1$ 回でなくてはいけません。各 $r$ に対して、$F(31, 1)$ 通りの $n$ があります。 - $r$ が $5,6,7,8,9$ のどれかの場合：
今度は条件 $n\leqq 314$ が、$m\leqq 30$ と同値になります。他は上記と同様です。各 $r$ に対して、$F(30, 1)$ 通りの $n$ があります。 - $r = 0$ の場合：
条件 $n\leqq 314$ は、$m\leqq 31$ と同値。今度は $1$ の位で「$0$ でない数字」を消費していないので、$m$ の部分で $2$ つとることになります。$F(31, 2)$ 通りの $n$ があります。
まとめると、$F(314, 2) = F(31, 1) \cdot 4 + F(30, 1) \cdot 5 + F(31, 2)$ となります。
あとは適切な終了条件を書いて、メモ化再帰の形でこれを一般的に実装すればACになります。
※ メモ化再帰の実装は、functools.lru_cache がお手軽。
※ 例えば $F(314159, 3)$ の計算過程で呼び出される $F(N,K)$ は、$N\in \{2,3,30,31,313,314,3140,3141,31414,31415,314159\}$ かつ $K\in \{0,1,2,3\}$ に限定されます。ここから計算量が評価できます。
※ 特に現れる $N$ の種類に注目してみると、「左からいくつかの桁をとったもの」「それよりも $1$ 小さくしたもの」の 2 種類があることが分かります。このことから、「左から見る桁数」「2種類のどっちか」をキーにして、桁数の小さい方から順番に計算していく形で DP を計算させることもできます。
※ 数え上げでは、重複・漏れのないように、とにかく「適切に場合分け」が最重要となる基礎。その結果として元の問題と同種の問題に帰着できればDPになる。まずは再帰で実装できるようにして、から非再帰な方法に慣らしていくとよい（パフォーマンスが良くなるので）。
関連：ABC 138 – F
問題 F – Many Many Paths
長方形領域 $(x_1,x_2] \times (y_1,y_2]$ に対する値の総和は、$[0,x]\times [0,y]$ の形に対する総和計算（2次元累積和）から計算できます。
- $\sum_{x_1 < x\leqq x_2}\sum_{y_1 < y\leqq y_2} = \sum_{0\leqq x\leqq x_2}\sum_{y_1 < y\leqq y_2} – \sum_{0\leqq x\leqq x_1}\sum_{y_1 < y\leqq y_2}$
- $\sum_{0\leqq x\leqq x_2}\sum_{y_1 < y\leqq y_2} = \sum_{0\leqq x\leqq x_2}\sum_{0 \leqq y\leqq y_2}-\sum_{0\leqq x\leqq x_2}\sum_{0 \leqq y\leqq y_1}$
- $\sum_{0\leqq x\leqq x_1}\sum_{y_1 < y\leqq y_2} = \sum_{0\leqq x\leqq x_1}\sum_{0 \leqq y\leqq y_2}-\sum_{0\leqq x\leqq x_1}\sum_{0 \leqq y\leqq y_1}$
2次元累積和 $\sum_{0 \leq i \leq x}\sum_{0 \leq j \leq y}\binom{i+j}{i}$ の計算に帰着されます。
あとは例えば、私の AGC 018-E 解説の序盤などの方法で、多項式計算によりこの和を簡潔な二項係数にできます。
小さい $(x,y)$ に対する累積和を計算するとすぐに予想できる数式なので、無証明も含めてもっとACされると思っていました。
