| A | B | C | D | E | F | |
| 問題文 | ■ | ■ | ■ | ■ | ■ | ■ |
| 自分の提出 | ■ | ■ | ■ | ■ | ■ | ■ |
| 結果 | AC | AC | AC | AC | AC | AC |
全体感想
64 分 全完で、16 位でした。
まぁ悪くないでしょうか。方針に迷うところはほとんどなかったですし、得意セット寄りだったと思うので、もっと速く仕上げたかったです。
問題B – Futon
for _ in range(2):
ans += np.sum(space[:-1] & space[1:])
space = space.T縦向きの集計 → 転置して同じことをやれば、横向きの集計になる。
という実装テクです。問題 E でも似たようなことを使いました。
問題C – Neq Min
ans = 0
for x in P:
ng[x] = 1
while ng[ans]:
ans += 1
print(ans)クエリが来るたびに、解の候補をひとつずつ調べています。運が悪く、なかなか未使用の数が見つからないこともあって、クエリあたりの計算量は $O(N)$ という評価になりますが、一連の計算全体で見ると、「解が見つからず ans をインクリメントする回数」は合計で $N$ 回程度しかなく、全体で計算量 $O(N)$ と解析できます。（ans 自体をポテンシャルとする償却計算量の解析）
問題E – Lamps
和の期待値は期待値の和、という典型で、各マス目ごとに照らされる確率を計算できればよいと分かります。各マス目に対して、そこが照らされる確率を計算するには、上下左右方向に合計いくつの空きマスが並んでいるかを調べればよいです。
for _ in range(4):
wall = wall.T[::-1] # 反時計まわり 90 度回転
# 上にある空きマスの個数を計算といった要領で、4 方向のロジックをまとめて 1 回で実装してしまうことができます。
問題F – Random Max
$N$ 個のものの max って、そのままでは扱いにくいことがあります。一方
$$\max\{a_1,a_2,\ldots,a_n\} \leq x \iff \forall i, a_i \leq x$$
という性質があって、「$\max (\cdots) \leq x$」であれば項別の条件に簡潔に切り分けられます。有名な典型だと例えば：
（例）サイコロを $n$ 個投げて、$\max$ が $5$ となる確率は？
→ $\max$ が $5$ 以下である確率から、$4$ 以下である確率を引いて、$(5/6)^n – (4/6)^n$
など。
今回も、$N$ 個の確率変数 $X_1, \ldots, X_N$ に対して、
$$f(x) = P(\max\{X_1,\ldots, X_N\})\leq x$$
であれば簡単に計算できそうです。（区間ごとに、$\frac{x-L}{R-L}$ または $0, 1$ をかけあわせた多項式関数になります）。
興味のあるもの：$\max\{X_1,\ldots,X_N\}$ の確率密度関数を $g(x)$ とすると、$f(x) = \int_0^x g(t)dt$ より、$g(x) = f'(x)$ が成り立ちます。
期待値は $\int_a^b xg(x)dx$ といった積分で計算できます。あとはこれを実装していけばよいです。
- 計算式の変わる区間の境界を検出する
- $f(x)$ を表す多項式関数を更新する
- 積分 $\int_a^b f(x)dx$ を計算する
などをすればよいでしょう。
私は実装の都合、$L[i]$ の割り算が必要となった（容易に回避可能ですが）ため、全部 $1$ ずらしてから計算を行いました。小さな $x$ から順に計算しましたが、結果的には大きな $x$ から計算した方が計算が簡単だった気がします。（全部多項式をかけたあと、ひとつずつ割っていくといういかにも無駄な計算手順になってしまいました）
