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

3/22: AtCoder Grand Contest 043 B - 123 Triangle

供養

問題

Difficulty: 1982 (記事作成時点)

解法

$i \ge 2$ において $a_{i, x}$ は $0, 1, 2$ の3通りだけしか出てこない
偶奇だけに着目すると、 $a_{i, x} \% 2 = a_{i - 1, x} \oplus a_{i - 1, x + 1}$ に等しくなる
においてがに寄与する回数はとなる
- $N - 2$ 回の $|a_{i - 1, x^{'}} - a_{i - 1, x^{'} + 1}|$ の計算において $x^{'} ＋ 1$ 側で使われる回数が $x - 1$ 回
のうち、奇数の要素全体で何回寄与するかで偶奇が決められる
- $\sum_{x = 1}^{N - 1}(a_{2, x} \% 2) \times (_{N - 2}\mathrm{C}_{x - 1} \% 2)$ の偶奇を求めればよい
- $_{N - 2}\mathrm{C}_{x - 1 \% 2}$ は Lucasの定理より $(N - 2)\;\mathrm{AND}\;(x - 1) = x - 1$ ならば 1、そうでなければ 0 と求められる
$a_{2, x}$ にひとつでも 1 があると解が 2 になることはないので、このとき解候補が偶数ならば解は 0 と言える
要素がすべて偶数のとき、偶奇のときと同様に2の寄与回数を計算すれば解が 2 であるかを確認できる
上記条件にすべて該当しなければ解は 0

実装は

長さ $N - 1$ の配列 $B$ を用意し、 $B_{i} = |a_{i} - a_{i + 1}|$ とする
$p = \left( \sum_{i = 0}^{N - 2}(B_{i} \% 2) \times (_{N - 2}\mathrm{C}_{i} \% 2) \right) \% 2$ とし、 $p = 1$ ならば 1 を出力して終了
$0 \le i \lt N - 1$ について、 $B_{i} = 1$ ならば 0 を出力して終了、そうでなければ $B_{i} = \frac{B_{i}}{2}$ とする
$p = \left( \sum_{i = 0}^{N - 2}(B_{i} \% 2) \times (_{N - 2}\mathrm{C}_{i} \% 2) \right) \% 2$ とし、 $p = 1$ ならば 2 を出力して終了
0 を出力する

計算量は $O(N)$

公式解説

躓いた点

まず偶奇に分けるという発想がなかった

3/23: AtCoder Beginner Contest 159 F - Knapsack for All Segments

供養

問題

Difficulty: 1841 (記事作成時点)

解法

$\mathit{DP}_{i, j}$ を、 $A_{i}$ まで見たときに合計が $j$ であるような部分数列を作れる $L$ と部分数列の組の数とする
要素の合計が $S$ で、 $R = A_{i}$ を最後の要素としてもつような部分数列を作れる $L, R$ は $\mathit{DP}_{i - 1, S - A_{i}} \times (N - i + 1)$ 個作れる

実装は

$(N + 1) \times (S + 1)$ のDP表 $\mathit{DP}$ を用意し、 $\mathit{DP}_{0, 0} = 1$ とする
$C = 0$ とする
について、下記のようにDP表を更新する
- $\mathit{DP}_{i + 1, 0} = \mathit{DP}_{i, 0} + 1$ 、 $1 \le j \le S$ について $\mathit{DP}_{i + 1, j} = \mathit{DP}_{i, j}$ とする
- $A_{i} \le S$ ならば $\mathit{DP}_{i, S - A_{i}} \times (N - i)$ を $C$ に加算する
- $0 \le j \le S - A_{i}$ について $\mathit{DP}_{i, j}$ を $\mathit{DP}_{i + 1, j + A_{i}}$ に加算する
$C$ を出力する

計算量は $O(NS)$

公式解説

躓いた点

コンテスト中は愚直にやってTLE
DPの構築に苦戦

3/24: AtCoder Regular Contest 009 C - 高橋君、24歳

供養

問題

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

解法

誤配送される $K$ 人の組合せ $_{N} \mathrm{C} _{K}$ と、 $K$ 人が誰も正しく配送されない組合せ $P_{K}$ が答えとなる
について、人全員に正しく配送されていないときにそのうち誰か1人と交換するか、人には正しく配送されておらず、1人だけ正しく配送されている場合にその正しく配送されている人と交換することで人全員が正しく配送されていない状況を作ることができるので、となる
- $P_{1} = 0, P_{2} = 1$ なので、 $K \ge 3$ については帰納的に求めることができる

実装は

$k = 1, \dots, K$ について $k!^{-1}$ を求める
$_{N}\mathrm{C}_{K} = \left( \prod_{k = 0}^{K - 1}(N - k) \right) \times K!^{-1}$ を求める
長さ $K + 1$ の配列 $P$ を用意し、 $P_{1} = 0, P_{2} = 1$ とする
$k = 3, \dots, K$ について $P_{k} = (k - 1)(P_{k - 1} + P_{k - 2})$ と計算していく
$_{N}\mathrm{C}_{K} \times P_{K}$ を出力する

計算量は $O(K)$

~~公式解説~~

躓いた点

$P_{K}$ の求め方について、 $K!$ から成立していない状況を引く方法で計算しようとして式が整理できなくなった

3/25: 天下一プログラマーコンテスト2013予選A C - 天下一二三パズル

供養

問題

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

解法

のとき、マスを破綻なく続けるためには 123(1213)+21 から連続したマスを取り出す
- $M = 9$ までのパターン数は $3, 6, 8, 8, 8, 8, 9, 10, 9$
- 繰り返しが存在するのでのときはと同値となる
  - 縦横で条件が同じなので、 $N \lt 9$ のときも $N^{'} = 6 + (N - 6) \% 4$ と同値となる
  - 一般性を失わず $N^{'} \le M^{'}$ としてよい
$N = 2 \land 2 \le M \le 4$ のときは $18, 20, 16$
$N = 3 \land M = 3$ のときのパターン数は $28$ で最大化する
上記以外の場合、上辺と左辺もしくは右辺からなる $N + M - 1$ 個のマスで破綻なく連続している必要があるので、 $N = 1$ のときと同様 $(N + M - 7) \% 4$ について $20, 18, 16, 18$

実装は

$M^{'} = 6 + (M - 6 \% 4), N^{'} = 6 + (N - 6 \% 4)$ とし、 $M^{'} \lt N^{'}$ ならば $M^{'}, N^{'}$ を入れ換える
$N^{'} = 1$ のとき、 $\lbrack 3, 6, 8, 8, 8, 8, 9, 10, 9 \rbrack \lbrack M^{'} - 1 \rbrack$ を出力して終了
$N^{'} = 2 \land M^{'} \lt 5$ のとき、 $\lbrack 6, 18, 20, 16 \rbrack \lbrack M^{'} - 1 \rbrack$ を出力して終了
$N^{'} = 3, M^{'} = 3$ のとき、 $28$ を出力して終了
上記以外のとき、 $\lbrack 20, 18, 16, 18 \rbrack \lbrack (N^{'} + M^{'} - 1) \% 4 \rbrack$ を出力して終了

計算量は $O(1)$

~~公式解説~~

躓いた点

パターンを整理しきれなかった

3/26: Code Formula 2014 本選 D - 映画の連続視聴

供養

問題

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

解法

$(M_{i}, S_{i}, E_{i})$ を $E_{i}$ について昇順にソートする
$\mathit{DP}_{i}$ を「最後に $i$ 番目の映画を見たときに得られる最大の幸福度」としたとき、 $DP_{i}$ は「 $j \lt i$ 番目までの映画を見た後に可能な限り種類が $M_{i}$ である映画を連続視聴したときの幸福度の最大値」として計算できる

実装は

長さ $N + 1$ の配列 $\mathit{CH}$ を用意し、 $\mathit{CH}_{i} = \sum_{j = 0}^{i - 1}H_{j}$ とする
$(M_{i}, S_{i}, E_{i})$ を $E_{i}$ について昇順にソートする
の配列を用意し、とする
- $i$ 番目からどれだけ連続視聴できるかと、そのとき最も早く視聴が終わる時間を記録する
長さ $N$ の配列 $\mathit{DP}$ を用意し、 $DP_{i} = H_{0}$ で初期化する
について下記のように更新する
- について下記のように操作する
  - $S_{i} \lt E_{j}$ ならば何もしない
  - $M_{i} \ne M_{j}$ ならば、 $\mathit{DP}_{i} = \mathrm{max}(\mathit{DP}_{j} + H_{0}, \mathit{DP}_{i})$ とする
  - ならば下記の操作をする
    - $C_{j, 1} \le S_{i}$ ならば $C_{j} = \lbrack C_{j, 0} + 1, E_{i} \rbrack$ とする
    - とする
      - $j$ 時点で連続視聴中で、そこからまた連続視聴数を数えなおす本来あり得ない幸福度が発生しうるが、連続視聴の起点 $k \le j$ からの計算結果が必ずそれを上回るので気にしない
$\mathrm{max}(\mathit{DP})$ を出力する

計算量は $O(N^{2})$

~~公式解説~~

躓いた点

$O(N^{3})$ のDPでTLE

3/27: Indeedなう（予選A） D - パズル

供養

問題

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

解法

ある盤面について、最短手の下限値をとする
- $C_{i, j} \ne 0$ について、 $C_{i, j}$ の正しい位置までのマンハッタン距離を $d_{i, j}$ としたとき、 $E_{C} = \sum_{i}\sum_{j}d_{i, j}$
現在の手数と、最短手の下限値の和を基準に初期盤面 $C_{0}$ からA*探索をする

実装は

ある盤面の最短手の下限値を見積もる関数を下記のように定義する
- $e = 0$ とする
- について、下記のように計算する
  - $C_{i, j} = 0$ ならば何もしない
  - $h = \lfloor \frac{C_{i, j} - 1}{W} \rfloor, w = (C_{i, j} - 1) \% W$ とする
  - $|i - h| + |j - w|$ を $e$ に加算する
- $e$ を返す
$C_{h, w} = 0$ であるような $h, w$ を探す
$S = 0$ とする
Priority Queue $\mathit{PQ}$ を用意し、 $(C, S, E(C), h, w, -1, -1)$ をPushする
下記の操作を実行する
- $\mathit{PQ}$ から $S + E_{C}$ が最も小さい要素をPopし、 $(C, S, E(C), h, w, h^{-1}, w^{-1})$ とする
- $E(C) = 0$ ならば $S$ を出力して終了
- $h \lt H - 1 \land h + 1 \ne h^{-1}$ ならば $C_{h, w}$ と $C_{h + 1, w}$ を入れ換えたものを $C^{'}$ とし、 $(C^{'}, S + 1, E(C^{'}), h + 1, w, h, w)$ を $\mathit{PQ}$ にPushする
- $0 \lt h \land h - 1 \ne h^{-1}$ ならば $C_{h, w}$ と $C_{h - 1, w}$ を入れ換えたものを $C^{'}$ とし、 $(C^{'}, S + 1, E(C^{'}), h - 1, w, h, w)$ を $\mathit{PQ}$ にPushする
- $w \lt W - 1 \land w + 1 \ne w^{-1}$ ならば $C_{h, w}$ と $C_{h, w + 1}$ を入れ換えたものを $C^{'}$ とし、 $(C^{'}, S + 1, E(C^{'}), h, w + 1, h, w)$ を $\mathit{PQ}$ にPushする
- $0 \lt w \land w - 1 \ne w^{-1}$ ならば $C_{h, w}$ と $C_{h, w - 1}$ を入れ換えたものを $C^{'}$ とし、 $(C^{'}, S + 1, E(C^{'}), h, w - 1, h, w)$ を $\mathit{PQ}$ にPushする

厳密な計算量の推定は困難だが、少なくともGoではACする

公式解説

躓いた点

計算量が保証されないA*探索をする発想は無かった

3/28: AtCoder Beginner Contest 160 F - Distributing Integers

供養

問題

Difficulty: 1962 (記事作成時点)

解法

$T$ を任意の点 $r$ (e.g. 0)を根とした根付き木として考える
各点 $u$ について、 $u$ を根とした部分木 $T_{u}$ のサイズを $S_{u}$ 、 $T_{u}$ のみに着目した場合の順番のパターン数を $A_{u}$ 、 $u$ の子を $C_{u}$ とするとき、 $A_{u} = (S_{u} - 1)!\prod{v \in C_{u}}\frac{A_{v}}{S_{v}!}$ となる
全方位木DPでパターンを数え上げる
任意の点 $r$ を根として各 $A_{u}$ を求める
以外の点について、の親をとすると、からに関する寄与分を除いた値を用いてを再計算すればよい
- $B_{p_{u}} = A_{p_{u}} \times (N - 1)^{-1}\dots(N - S_{u})^{-1} \times \left(\frac{A_{u}}{S_{u}!}\right)^{-1} = A_{p_{u}} \times \left(_{N - 1}\mathrm{C}_{S_{u}}\right)^{-1} \times A_{u}^{-1}$
- $A_{u} = A_{u} \times (N - 1)\dots(N - (N - S_{u})) \times \frac{B_{p_{u}}}{(N - S_{u})!} = A_{u} \times _{N - 1}\mathrm{C}_{N - (N - S_{u})} \times B_{p_{u}} = _{N - 1}\mathrm{C}_{S_{u} - 1} \times A_{p_{u}} \times \left(_{N - 1}\mathrm{C}_{S_{u}}\right)^{-1} = A_{p_{u}} \times \frac{N \times S_{u}}{N - S_{u}}$

実装は

を0を根とした根つき木とし、からの探索の発見順に並べた配列を、各点の親を並べた配列をとする
- $P_{r} = -1$ とする
長さ $N$ の配列 $A, V$ を用意し、各要素を1で初期化する
について、下記のように更新する
- の各隣接点について、下記の操作を行う
  - $v = P_{q}$ ならば何もしない
  - $A_{v} \times V_{v}!^{-1}$ を $A_{q}$ に乗算する
  - $V_{v}$ を $V_{q}$ に加算する
- $(V_{q} - 1)!$ を $A_{q}$ に乗算する
について、下記のように更新する
- の各隣接点について、下記の操作を行う
  - $v = P_{q}$ ならば何もしない
  - $A_{v} = A_{q} \times N \times V_{v} \times (N - V_{v})^{-1}$ とする
$A_{0}, \dots, A_{N - 1}$ を順に出力していく

計算量は $O(N)$

公式解説

躓いた点

式の整理に手こずって実装中に時間切れ

3/29: DISCO presents ディスカバリーチャンネル プログラミングコンテスト2016 本選 B - DDPC特別ビュッフェⅡ

供養

問題

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

解法

$A_{i}$ の大きい順に貪欲に選んでいく
取るタイミングは $t \lt T_{i}$ かつ他の皿を選んでいない中で最大の $t$ とする
取得した $A_{i}$ の累積が $X$ 以上となったときに取った枚数が答えとなる

実装は

$(T_{i}, A_{i})$ を $A_{i}$ について降順にソートする
要素数がのSegment Tree を用意し、で初期化する
- $\lbrack 0, t)$ の範囲での $\mathit{ST}$ の最大値を返す関数を $Q(t)$ とする
$x = 0, t = 0$ とする
について下記のように操作する
- $t^{'} = Q(T_{i})$ とし、 $t^{'} \lt 0$ ならば何もしない
- $\mathit{ST}_{t^{'}} = -1$ に更新する
- $t$ をインクリメントする
- $A_{i}$ を $x$ に加算し、 $X \le x$ ならば $t$ を出力して終了する
-1 を出力する
- 最後まで $x \lt X$ だったことを意味する

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

公式解説

躓いた点

同じ料理を連続で取ってはいけないだけで2回以上取ることはできると誤読していた

3/30: CODE FESTIVAL 2014 Middle C - eject

供養

問題

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

解法

回開閉したときにスイッチがONになっている確率をとすると、を用いて以下の2式が得られる
- $P_{n} = P_{n - 1}(1 - p) + (1 - P_{n - 1})p = p + (1 - 2p)P_{n - 1}$
- $1 - P_{n} = P_{n - 1}p + (1 - P_{n - 1})(1 - p) = 1 - p - (1 - 2p)P_{n - 1}$
これを式変形すると $2P{n} - 1 = (1 - 2p)(1 - 2P_{n - 1})$ と $1 - 2P_{n} = (1 - 2p)(1 - 2P_{n - 1})$ が得られることから、 $P_{n} = \frac{1}{2} \times (1 - (1 - 2p)^{n}(1 - P_{0}))$ となり、 $P_{0} = 0$ より、 $P_{n} = \frac{1}{2} \times (1 - (1 - 2p)^{n})$ となる

実装は

を求める関数を下記のように定義する
- $N = n, X = 1, P = p$ とする
- である間、以下の操作を繰り返す
  - $N \% 2 = 1$ ならば $X = X \times P$ とする
  - $P = P \times P$ とする
  - $N = \lfloor \frac{N}{2} \rfloor$ とする
- $X$ を返す
$0.5 \times (1 - \mathrm{Pow}(1 - 2p, n))$ を出力する

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

~~公式解説~~

躓いた点

確率計算がまったく導出できなかった

3/31: AtCoder Regular Contest 016 C - ソーシャルゲーム

供養

問題

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

解法

所有しているカードの種類についてのbitDPを行う
各bitで対応するカードを持っているかを表す
- e.g. $\mathit{DP}_{0}$ で1枚も持っていない状態、 $\mathit{DP}_{2^{N} - 1}$ ですべてのカードを持っている状態
$\mathit{DP}_{2^{N} - 1}$ の期待値は0
各状態 $i$ について、くじごとに (まだ持っていないカードを引く期待値) $+ \sum$ (引いたことによって進んだ状態 $i^{'}$ の期待値) $\times$ (状態 $i^{'}$ への遷移確率) を求め、その最小値が $\mathit{DP}_{i}$ となる

実装は

長さ $2^{N}$ の配列 $\mathit{DP}$ を用意し、各要素を0で初期化する
$B = 2^{N} - 1$ とする
空の配列 $Q$ を用意し、 $2^{N} - 1$ を配列の末尾に挿入する
が空になるまで下記操作を繰り返す
- $Q$ の先頭の要素を取り出し、 $S$ とする
- について下記の操作を実施する
  - $s = S\;\mathrm{AND}\;(B - 2^{i})$ とし、 $\mathit{DP}_{s}$ が計算済み(i.e. 0より大きい)ならば何もせず次に行く
  - 各くじについて、下記の操作を実施する
    - 長さ $N$ の配列 $T$ を用意し、 $0 \le j \lt N$ について $T_{j} = s\;\mathrm{OR}\;2^{j}$ とする
    - $a = \sum_{j | T_{j} \ne s}p_{m, j}$ とし、 $a = 0$ ならば次のくじに行く
    - $e = \mathit{cost}_{m} \times \frac{100}{a} + \sum_{j | T_{j} \ne s}\mathit{DP}_{T_{j}} \times \frac{p_{m, j}}{a}$ とする
    - $\mathit{DP}_{s}$ が未定なら $\mathit{DP}_{s} = e$ とし、そうでないなら $\mathit{DP}_{s} = \mathrm{min}(e, \mathit{DP}_{s})$ とする
  - $Q$ の末尾に $s$ を追加する
$\mathit{DP}_{0}$ を出力する