コンテストでの時間切れや解けなかった過去問を振り返って供養していく

2/8: AtCoder Regular Contest 025 C - ウサギとカメ

供養

問題

Difficulty: 2258(estimated) (記事作成時点)

解法

について、を始点とする各点への最短路を探索し、である各点への最短距離で数列を作成する
- 目的地を $T$ としたときの各点を始点としたときの最短距離
$D$ を昇順にソートする
$S = 0, r = 0$ とする
[0 \le t \lt N - 1] について、以下の操作をおこなう
- $\mathit{TT} = D \lbrack t \rbrack \times R$ とする
- となるまでをインクリメントする
  - $\frac{D \lbrack t \rbrack}{T} \lt \frac{D \lbrack r \rbrack}{R}$ を意味する
- $N - 1 - r$ を $S$ に加算する
- のとき、から1減算する
  - 同じ始点を選べないことに対応
$S$ を出力する

計算量は目的地ごとに $O(N\mathrm{log}N)$ の計算をするので全体で $O(N^{2}\mathrm{log}N)$

公式解説

躓いた点

$r \le t$ の場合の処理を忘れてWA

2/9: AtCoder Regular Contest 092 D - Two Sequences

供養

問題

Difficulty: 2268 (記事作成時点)

解法

$1 \le k \le 29$ について、答え $k$ bit目を考える
$A_{k} = \lbrack a_{k, i} \mid a_{k, i} = a_{i}\; \mathrm{mod}\; 2^{k} \rbrack, B_{k} = \lbrace b_{k, i} \mid b_{k, i} = b_{i}\; \mathrm{mod}\; 2^{k} \rbrace$ とする
$B_{k}$ を昇順にソートしたものを $B^{'}_{k}$ とする
について、であるようなを二部探索で求める
- $a_{k, i}, b^{'}_{k, i} \lt 2^{k}$ より $a_{k, i} + b^{'}_{k, i} \lt 2^{k + 1} = 4 \times 2^{k - 1}$ なので、このとき $k$ bit目が1となる値域は $\lbrack 2^{k - 1}, 2 \times 2^{k - 1} ), \lbrack 3 \times 2^{k - 1}, 4 \times 2^{k - 1} )$
$k$ bit 目を $(k_{4, 1} - k_{3, 1} + k_{2, 1} - k_{1, 1}) \oplus \dots \oplus (k_{4, N} - k_{3, N} + k_{2, N} - k_{1, N})\; \mathrm{mod}\; 2$ とする
すべてのbitについて求めたら出力する

計算量は $O(N\mathrm{log}N)$

公式解説

躓いた点

剰余を作る発想がなく、下位bitからの繰り上がりの処理をしようとして手詰まり

2/10: 全国統一プログラミング王決定戦予選 E - Weights on Vertices and Edges

供養

問題

Difficulty: 2270 (記事作成時点)

解法

辺を重みについて昇順にソートしたものを $E^{'} = \lbrack e^{'}_{i} \mid e^{'}_{i} = (A^{'}_{i}, B^{'}_{i}, Y^{'}_{i}) \rbrack$ とする
について、でUnionし、代表点の重みが連結成分の各頂点の重みの合計となるようにする
- このとき、代表点へのリンクの変更が発生した頂点を $j_{i}$ で記録しておく
- 後の計算でFindでの経路圧縮を行っていないリンク集合が必要だが、Find用に経路圧縮を行うリンク集合を別途用いると高速化できる
について、の属する連結成分の代表点をとしたとき、であるような辺を数えて出力する
- かつが存在するとき、以下の操作をする
  - $X_{r_{i}}$ から $X_{j_{i}}$ を減算する
  - $j_{i}$ が指す連結成分の代表点へのリンクを $j_{i}$ 自身に向ける

計算量は $O(M\mathrm{log}M)$

公式解説

躓いた点

Union-Findの履歴を作ろうと無駄に複雑に作ってバグを埋め込んでWA

2/11: AtCoder Beginner Contest 143 F - Distinct Numbers

供養

問題

Difficulty: 2275 (記事作成時点)

解法

取り出す列の個数を $X$ に固定した場合を考える
$1 \le j \le N$ について $C_{j}$ を [A_{i} = j] であるような $A$ の要素数とすると、 $X$ 個取り出したいときに使える要素数は $\sum_{j = 1}^{N}\mathrm{min}(C_{j}, X)$ であることから、1個あたりの長さの最大値は $\lfloor \frac{\sum_{j = 1}^{N}\mathrm{min}(C_{j}, X)}{X} \rfloor$
$0 \le k \le N$ について $D_{k}$ を $C_{j} = k$ であるような $C$ の要素数とすると、 $\sum_{j = 1}^{N}\mathrm{min}(C_{j}, X) = \sum_{k = 0}^{X} \bigl( k \times D_{k} \bigr) + X \times \sum_{k = X + 1}^{N} D_{k}$ と式変形できる
$1 \le X \le N$ について上記の方法で求めた最大長を $L_{X}$ とする
についてであるような最大のを出力する
- $L_{1} \lt K$ ならば0

実装は

配列 $C$ を用意し、 $1 \le i \le N$ について、 $C \lbrack A_{i} \rbrack$ をインクリメントする
配列 $D$ を用意し、 $0 \le j \le N$ について、 $D \lbrack C_{j} \rbrack$ をインクリメントする
配列 $\mathit{KD}$ を用意し、 $0 \le k \le N$ について $\mathit{KD} \lbrack k \rbrack = k \times D \lbrack k \rbrack$ とする
$k = 1, \dots, N$ について $\mathit{KD} \lbrack k \rbrack = \mathit{KD} \lbrack k - 1 \rbrack + \mathit{KD} \lbrack k \rbrack$ とする
配列 $\mathit{XD}$ を用意し、 $k = N - 1, \dots, 0$ について $\mathit{XD} \lbrack k \rbrack = \mathit{XD} \lbrack k + 1 \rbrack + D \lbrack k + 1 \rbrack$ とする
配列 $L$ を用意し、 $1 \le X \le N$ について、 $L \lbrack X \rbrack = \lfloor \frac{\mathit{KD} \lbrack X \rbrack + X \times \mathit{XD} \lbrack X \rbrack}{X} \rfloor$ とする
について、となるような最大のを二分探索で求め、出力していく
- $L \lbrack 1 \rbrack \lt K$ ならば0を出力する

計算量は $L$ を作るまでが $O(N)$ と $N$ 回の二分探索なので $O(N\mathrm{log}N)$

公式解説

躓いた点

$L$ の計算を整理できなかった
$A$ の値域についての条件を見落としていた

2/12: AtCoder Beginner Contest 154 F - Many Many Paths

供養

問題

Difficulty: 1752 (記事作成時点)

解法

$(0, 0)$ から $(r, c)$ までの経路のパターン数を $f(r, c)$ としたときに、 $g(r, c) = \sum_{x = 0}^{r}\sum_{y = 0}^{c}f(x, y)$ とする
であることから、である
- $\because (0, 0) \to \dots \to (r + 1, c)$ を考えたとき、 $0 \le y \le c$ のいずれかで $(0, 0) \to \dots \to (r, y) \to (r + 1, y) \to \dots \to (r + 1, c)$ となり、 $(r + 1, y) \to \dots \to (r + 1, c)$ は一本道なので $f(r + 1, c)$ は $(0, 0) \to \dots \to (r, y)$ の合計、すなわち $\sum_{y = 0}^{c}f(r, y)$ で表すことができる
問題は二次元累積和の計算なので $g(r_{2}, c_{2}) - g(r_{1} - 1, c_{2}) - g(r_{2}, c_{1} - 1) + g(r_{1} - 1, c_{1} - 1)$ で求められる

実装は

$0 \le k \le r_{2} + c_{2} + 1$ について、 $F \lbrack k \rbrack = k!\; \mathrm{mod}\; p, F^{-1} \lbrack k \rbrack = k!^{-1}\; \mathrm{mod}\; p$ を求めておく
$g(r, c) = \sum_{x = 1}^{r + 1}\frac{(x + c)!}{x!c!} = \sum_{x = 1}^{r + 1}F \lbrack x + c \rbrack F^{-1} \lbrack x \rbrack F^{-1} \lbrack c \rbrack$ を求める関数を作成する
$g(r_{2}, c_{2}) - g(r_{1} - 1, c_{2}) - g(r_{2}, c_{1} - 1) + g(r_{1} - 1, c_{1} - 1)$ を出力する

計算量は $O(r_{2} + c_{2})$

公式解説

躓いた点

$g(r, c)$ の計算方法を思いつかなかった

2/13: AtCoder Grand Contest 037 B - RGB Balls

供養

問題

Difficulty: 2276 (記事作成時点)

解法

赤、緑、青のボールをそれぞれ番号で昇順にソートし、それぞれ $i$ 個目のボールの番号を $r_{i}, g_{i}, b_{i}$ とする
$1 \le i \le N$ について、 $M_{i} = \mathrm{max}(r_{i}, g_{i}, b_{i}), m_{i} = \mathrm{min}(r_{i}, g_{i}, b_{i})$ とする
ある人が受け取ったボールの番号をとしたとき、が成り立つ
- $a_{j}$ について昇順にソートしたとき、各色について $a_{j^{'}}$ より真に小さいボールは高々 $j^{'} - 1$ 個なので、 $a_{j^{'}} \le \mathrm{min}(r_{j^{'}}, g_{j^{'}}, b_{j^{'}}) = m_{j^{'}}$ より、 $\sum_{j = 1}^{N}a_{j} \le \sum_{i = 1}^{N}m_{i}$
- $c_{j}$ について昇順にソートしたとき、各色について $c_{j^{'}}$ より真に小さいボールは少なくとも $j^{'} - 1$ 個存在するので、 $c_{j^{'}} \ge \mathrm{max}(r_{j^{'}}, g_{j^{'}}, b_{j^{'}}) = M_{j^{'}}$ より、 $\sum_{j = 1}^{N} \ge \sum_{i = 1}^{N}M_{i}$
- 上記より、 $\sum_{j = 1}^{N}(c_{j} - a_{j}) = \sum_{j = 1}^{N}c_{j} - \sum_{j = 1}^{N}a_{j} \ge \sum_{i = 1}^{N}M_{i} - \sum_{i = 1}^{N}m_{i} = \sum_{i = 1}^{N}(M_{i} - m_{i})$
ある2つの分配について、であればとを入れ換えてもは変化しない
- 同様に、 $b_{j^{'}} \lt c_{j}$ であれば $c_{j}$ と $c_{j^{'}}$ を入れ換えても $\sum_{j = 1}^{N}(c_{j} - a_{j})$ は変化しない
上記の関係を満たすようなの組合せのパターンを数える
- についてからを作り、とする
  - $A$ が $m_{i}$ の集合、 $C$ が $M_{i}$ の集合、 $B$ がそれ以外を意味する
- について、ならば未満のの個数から未満のの個数を引いた数だけ割り当てられるパターンが存在する
  - 同様に、 $k \in C$ ならば $k$ 未満の $b_{i}$ の個数から $k$ 未満の $c_{i}$ の個数を引いた数だけ割り当てられるパターンが存在する
求めた組合せ数に $N!$ を乗算することで誰に分配するかのパターンを数えられる

実装は

R、G、Bそれぞれに対応する空の配列 $R, G, B$ を用意する
$i \le i \le 3N$ について、 $S$ の $i$ 文字目に対応する配列の末尾に $i$ を追加していく
配列 $\mathit{ABC}$ を用意する
$1 \le i \le N$ について、 $\lbrack R \lbrack i \rbrack, G \lbrack i \rbrack, B \lbrack i \rbrack \rbrack$ を昇順にソートして $j$ 番目に小さい値を $\mathit{abc}_{i, j}$ としたとき、 $\mathit{ABC} \lbrack \mathit{abc}_{i, j} \rbrack = j$ としていく
$P = 1$ とする
$1 \le i \le 3$ について、 $C_{i} = 0$ とする
$1 \le k \le 3N$ について、 $C_{\mathit{ABC} \lbrack k \rbrack}$ をインクリメントする
$\mathit{ABC} \lbrack k \rbrack \ge 2$ のとき、 $P$ に $C_{\mathit{ABC} \lbrack k \rbrack - 1} - C_{\mathit{ABC} \lbrack k \rbrack} + 1$ を乗算する
$P \times N!$ を出力する

計算量は $O(N)$

公式解説

躓いた点

解説で省略されたところを思いつかなかった

2/14: エクサウィザーズ 2019 E - Black or White

供養

問題

Difficulty: 2277 (記事作成時点)

解法

$(0, 0)$ から $(+1, 0)$ もしくは $(0, +1)$ の移動で $(B, W)$ に移動することを考える
現在の座標が $(B, y)$ ならば確率1で $(0, +1)$ の移動をし、 $(x, W)$ ならば確率1で $(+1, 0)$ の移動をする
回の移動の後ににいる確率を、にいる確率をとすると、は下記のように表せる
- $(B, i - B - 1)$ から $(B, i - B)$ に移動する確率や $(i - W - 1, W)$ から $(i - W, W)$ に移動する確率は1なので、単純に $p_{i} = \frac{_{i}\mathrm{C}_{B}}{2^{i}}, q_{i} = \frac{_{i}\mathrm{C}_{W}}{2^{i}}$ としてはいけない
$1 \le i \le B + W$ 回目に黒を食べる確率は $\frac{1 - p_{i - 1} - q_{i - 1}}{2} + q_{i - 1} = \frac{1 - p_{i - 1} + q_{i - 1}}{2}$

実装は

$0 \le k \le B + W$ について、 $k!\; \mathrm{mod}\; p, k!^{-1}\; \mathrm{mod}\; p$ を計算しておく
$0 \le k \lt B + W$ について、 $2^{-k}\; \mathrm{mod}\; p$ を計算しておく
$P_{B} = 0, P_{W} = 0$ とする
について、以下のようにを更新していきながらを出力していく
- $i \ge B$ のとき、 $P_{B} = P_{B} + _{i - 1}\mathrm{C}_{B - 1} \times 2^{-i} = P_{B} + i! \times (B - 1)!^{-1} \times (i - B)!^{-1} \times 2^{-i}$
- $i \ge W$ のとき、 $P_{W} = P_{W} + _{i - 1}\mathrm{C}_{W - 1} \times 2^{-i} = P_{W} + i! \times (W - 1)!^{-1} \times (i - W)!^{-1} \times 2^{-i}$