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

12/28: AtCoder Beginner Contest 147 E - Balanced Path

供養

問題

Difficulty: 1656 (2019/12/28現在)

解法

各マス $(i, j)$ について $C_{ij} = | A_{ij} - B_{ij} |$ とする
マスの時点で偏りのパスを作れるか、というBooleanをもつDPをする
- 左もしくは上のマスに $k$ との差分がちょうど $C_{ij}$ であるような偏りのパスがあればよいので、以下のように求めていくことができる
  $$ \begin{align} DP[i\rbrack[j\rbrack[k\rbrack &= DP[i - 1\rbrack[j\rbrack[k + C_{ij}\rbrack\\ &\lor DP[i - 1\rbrack[j\rbrack[|k - C_{ij}|\rbrack\\ &\lor DP[i\rbrack[j - 1\rbrack[k + C_{ij}\rbrack\\ &\lor DP[i\rbrack[j - 1\rbrack[|k - C_{ij}|\rbrack \end{align} $$
$\mathit{DP}[H\rbrack[W\rbrack[k\rbrack = \mathit{True}$ であるような最小の $k$ を出力する

計算量は $D = \mathrm{max}\lbrace C_{ij} \mid 1 \le i \le H, 1 \le j \le W \rbrace$ として $O(HW(H+W)D)$

公式解説

躓いた点

DPの計算で各 $k$ についてBooleanのOR演算でいいところを連想配列を使って計算したためTLE

12/29 AtCoder Grand Contest 041 C - Domino Quality

供養

問題

Difficulty: 2280 (2019/12/29現在)

解法

$N = 4, 5, 6, 7$ 、クオリティ3のパターンを下記のように作成し、それぞれ $P_{4}, P_{5}, P_{6}, P_{7}$ とする

aacd
bbcd
cdaa
cdbb

aabba
bc..a
bc..b
a.ccb
abbaa

a.bb.a
ab...a
.baabb
ac.cc.
aca...
bba.aa

aabbaa.
bc....a
bc....a
a..ab..
a..ab..
.aa.caa
..bbcbb

$N \ge 4$ のとき、 $k = \lfloor \frac{N}{4} \rfloor - 1$ 個の $P_{4}$ と、1個の $P_{N - 4k} (4 \le N - 4k \le 7)$ のパターンを下記のように組み合わせたものを出力するとクオリティ3のパターンになる
e.g. $N = 13$ （2個の $P_{4}$ と1個の $P_{5}$ の組み合わせ）

aacd.........
bbcd.........
cdaa.........
cdbb.........
....aacd.....
....bbcd.....
....cdaa.....
....cdbb.....
........aabba
........bc..a
........bc..b
........a.ccb
........abbaa

$N = 3$ のときはクオリティ1の下記を出力する

a..
a..
.aa

$N = 2$ のときは作れないので -1 を出力する

公式解説

躓いた点

$N = 3, 4, 5, 7$ あたりまで作ったがmod4で帳尻を合わせて組み合わせる発想がコンテスト時間内に出なかった

12/30: AtCoder Beginner Contest 041 D - 徒競走

供養

問題

Difficulty: 1882(estimated) (2019/12/30現在)

解法

部分点解法は省略

$\lbrace 1, \dots, N \rbrace$ の部分集合 $S$ について、観客の情報と合致する着順のパターン数を $f(S)$ とするとき、以下が言える

$f(\phi) = 1$
任意の $u \in S$ について先着したという情報がないような $v \notin S$ が存在するとき、 $S \cup \lbrace v \rbrace$ には $v$ が最後尾であるような、観客の情報と合致する着順が $f(S)$ 通り存在する

これを式にすると
$$ \begin{equation} f(S) = \sum_{v \in S^{'}} f(S \setminus \lbrace v \rbrace)\\ S^{'} = \lbrace v \mid v \in S \land \forall u. \forall i. (u \in S \setminus \lbrace v \rbrace) \land (1 \le i \le M) \land (x_{i} \ne v \lor y_{i} \ne u) \rbrace \end{equation} $$

上記を計算するためのbitDPをする

$1 \le i \le N$ について $B_{i} = 2^{i - 1}$ で初期化し、 $1 \le j \le M$ について $B_{x_{j}} = B_{x_{j}} + 2^{y_{j} - 1}$ とする
i.e. $1 \le i \le N$ について $B_{i} = \sum_{1 \le j \le N} (2^{j - 1}\; \mathit{if}\; (\exists m.(1 \le m \le M) \land (x_{m} = i \land y_{m} = j)) \lor (i = j)\;\mathit{else}\; 0 )$ となり、自分より遅くついた情報があるうさぎ（もしくは自分自身）に対応するbitが立っているbitmaskとなる
$\mathit{DP}[0\rbrack = 1$ とする
部分集合 $S_{k}$ を $k = \sum_{1 \le i \le N} (2^{i - 1}\,\mathit{if}\; i \in S_{k}\; \mathit{else}\; 0)$ と表現し、 $k = 0, \dots, 2^{N} - 1$ について、 $k\; \mathrm{and}\; B_{i} = 0$ ならば $\mathit{DP}[k + 2^{i - 1}\rbrack$ に $\mathit{DP}[k\rbrack$ を加算する
i.e. $S_{k} \cup \lbrace i \rbrace$ について $i$ が最後尾であるパターン数を加算する
$\mathit{DP}[2^{N} - 1\rbrack$ を出力する

計算量はbitmaskの前処理に $O(M) = O(N^{2})$ 、DPの計算に $O(N2^{N})$ なので $O(N2^{N})$

公式解説

躓いた点

着順の関係に囚われすぎて、着順の関係がある部分集合についてパターン数を出そうとしていた
ある部分集合の着順のパターン数=最後尾を固定した残りの部分集合のパターン数の合計、という発想がなかった

12/31 AtCoder Regular Contest 017 C - 無駄なものが嫌いな人

供養

問題

Difficulty: 1989(estimated) (2019/12/31現在)

解法

$W = [ w_{1}, \dots, w_{N}\rbrack$ を2分割し、 $W_{1}$ 、 $W_{2}$ とする
それぞれ取りうる組み合わせについて全列挙し、重量の合計をkey、パターン数をvalueとした連想配列を $H_{1}$ 、 $H_{2}$ とする
$H_{1}$ の全keyの集合を $K(H_{1})$ としたとき、 $\sum_{k \in K(H_{i})}(H_{1}[k\rbrack \times H_{2}[X - k\rbrack)$ を出力する