そのうち誰かの役に立つ

もしくは誰の役にも立たない

AtCoderチャレンジ供養会場(2020/02/22-2020/02/29)

競技プログラミング AtCoder BIT BitSet Union-Find

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

2/22: AtCoder Grand Contest 014 D - Black and White Tree

供養

問題

Difficulty: 2293 (記事作成時点)

解法

木が完全マッチング可能な場合かつその限りにおいて後手が勝つ
- $( \Rightarrow )$ ある完全マッチングをもとに、先手が選んだ点と対になる点を後手が選び続ければ後手が勝つ
- 対偶である、が完全マッチング不可能ならば先手が勝つことを示す
  - $T$ を適当な点を根とした根つき木として見たときに、先手が任意の葉 $v$ の親 $u$ を選ぶと、後手は $v$ を選ばないとその次の手で先手に $v$ を選ばれて負けが確定するので、後手は $v$ を選ぶことになる
  - 上記の選択後は $V \setminus \lbrace u, v \rbrace$ から誘導される $T$ の部分木について同様の選択をすることができ、このように選んでいった点対は $T$ の極大マッチングを作る
  - また、このようにして点を選んでいった場合、後手は直前に先手が選んだ点しか干渉できる(その後の操作で黒く塗れる)点を増やせない
  - (木を含む)二部グラフで完全マッチング不可能なとき、任意の極大マッチングについてマッチングしていない点からなる誘導部分グラフには孤立点 $u^{'}$ が含まれる
  - 極大マッチング構成後に先手が $u^{'}$ を選ぶと、 $u^{'}$ に干渉できる点を後手が選べないので先手の勝ちとなる

実装は

適当な点(e.g. 1)から幅優先探索をして発見した順に $v_{1}, \dots, v_{N}$ とする
$i = N, \dots, 1$ について、 $v_{i}$ がまだマッチングしていないならば、 $v_{i}$ の隣接点からまだマッチングしていない点 $v_{j}$ を任意に選びマッチングさせていく
途中でマッチングが作れなくなったときは First 、全ての点でマッチングを作れれば Second を出力する

計算量は $O(N)$

躓いた点

完全マッチングの判定問題であることに気付かずWA

2/23: AtCoder Regular Contest 088 E - Papple Sort

供養

問題

Difficulty: 2303 (記事作成時点)

解法

$S = s_{1} \dots s_{|S|}$ とする
アルファベットごとに登場回数をカウントして、奇数個登場する文字が2種類以上存在すれば回文は作れない
$1 \le i \le |S|$ について $s_{i} = c$ としたとき、 $s_{i}$ が $c$ の何回目の登場になるのかを $A_{i, c}$ で表す
アルファベット $c$ の登場回数を $C_{c}$ としたとき、各アルファベットについて前半( $A_{i, c} \le \lfloor \frac{C_{c}}{2} \rfloor$ )の登場となる集合、奇数個登場するアルファベットがあればその中央、後半( $A_{i, c} \gt \lceil \frac{C_{c}}{2} \rceil$ )の登場となる集合をそれぞれ $L, M, R$ とする
を登場順に固定するとの並びも決まり、内部では入れ替えが発生しないので全体としても入れ替え回数が最小化できる
- $L$ に対応した $R$ の並びを $R_{L}$ としたとき、 $L$ を任意の $n$ 回入れ換えて作れる $L^{'}$ に対応する $R_{L^{'}}$ に並べ替える回数を $R_{L}$ に並べ替える回数より $n$ 回以上真に小さくすることはできない
  $\because$ そのように並べた $R_{L^{'}}$ を $n$ 回入れ換えると $R_{L}$ になるため
並べ方が決まるので転倒数をBITなどを用いて求める

実装は

アルファベットごとに $S$ での登場回数をカウントし、各アルファベットの登場回数を $C = \lbrack c_{c} \rbrack$ とする
奇数回登場のアルファベットが2種類以上存在すれば -1 を出力して終了
各アルファベットごとの登場回数を表す配列 $A = \lbrack a_{c} \rbrack$ と 2次元配列 $B$ 、配列 $T$ を用意する
とする
- 各アルファベットの前半部の登場回数を意味する
について、以下のように値を更新していく
- $A_{s_{i}} \lt \lfloor \frac{C_{s_{i}}}{2} \rfloor$ のとき、 $T_{i} = L, B_{s_{i}, A_{s_{i}}} = L$ とし、 $L$ をインクリメント
- $C_{s_{i}}\; \mathrm{mod}\; 2 = 1 \land A_{s_{i}} = \lfloor \frac{C_{s_{i}}}{2} \rfloor$ のとき、 $T_{i} = \lfloor \frac{|S|}{2} \rfloor$
- $A_{s_{i}} \ge \lceil \frac{C_{s_{i}}}{2} \rceil$ のとき、 $T_{i} = |S| - 1 - B_{s_{i}, C_{s_{i}} - A_{s_{i}} - 1}$
$T$ の転倒数をBITなどで求めて出力

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

躓いた点

奇数個登場するアルファベットについて3個以上の登場を考慮せず、その位置を一律に中央にしてしまってWA

2/24: AtCoder Regular Contest 039 C - 幼稚園児高橋君

供養

問題

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

解法

1回移動するごとに、4方向について次の移動先候補の未訪問点を求めていく
次の訪問点候補 $(x, y)$ から $d$ 方向に1つ進んだ点 $(x^{'}, y^{'})$ が既訪問点ならば、 $(x, y)$ の $d$ 方向の次の移動先は $(x^{'}, y^{'})$ の $d$ 方向の移動先となる
また、 $(x, y)$ から $d$ 方向に進めるだけ進んだ点 $(x^{''}, y^{''})$ について、 $(x^{''}, y^{''})$ が $d$ の逆方向 $d^{-1}$ に進む移動先は $(x, y)$ の $d^{-1}$ 方向の移動先に更新される
既訪問点はHashmapの値の存在の有無で管理する

実装

既訪問点を管理するHashmap を用意する
- 記述の簡略化のため、 $A \lbrack x \rbrack \lbrack y \rbrack$ を $A_{x, y}$ と表記する
とする
- 順に、右方向、左方向、上方向、下方向に移動したときの次の座標を意味する
- 記述の簡略化のため、 $A \lbrack x \rbrack \lbrack y \rbrack \lbrack d \rbrack$ を $A_{x, y, d}$ と表記し、また、 $d$ の逆方向を $d^{-1}$ で表す
現在地を $(x, y) = (0, 0)$ とする
について、下記のように更新する
- $A_{x, y}$ から次の訪問点 $(x^{+}, y^{+})$ を求めて $(x, y)$ を $(x^{+}, y^{+})$ に更新する
- $A_{x, y} = \lbrack (x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1) \rbrack$ とする
- 各方向 $d$ について、 $A_{x, y, d} = (x^{'}, y^{'})$ が訪問済(i. e. $A_{x^{'}, y^{'}}$ が存在する)とき、 $A_{x, y, d}$ を $A_{x^{'}, y^{'}, d}$ に更新する
- 各方向 $d$ について、 $A_{x, y, d}$ の $d^{-1}$ 方向で1つ隣(i. e. $(x, y)$ から $d$ 方向に進めるだけ進んだ既訪問点)を $(x^{''}, y^{''})$ としたとき、 $A_{x^{''}, y^{''}, d^{-1}}$ を $A_{x, y, d^{-1}}$ に更新する
$(X, Y)$ を出力する

計算量は $O(K)$

躓いた点

$A_{x, y, d}$ と $A_{x^{''}, y^{''}, d^{-1}}$ の片方しか更新せずに2WA

2/25: AtCoder Regular Contest 068 E - Snuke Line

供養

問題

Difficulty: 2310 (記事作成時点)

解法

$d$ を固定して考えたとき、 $d \le r_{i} - l_{i} + 1$ であるような名産品 $i$ は必ず購入できる
について、であるようなのときは高々1回しか購入チャンスが無いので、の間だけカウントされるようにして、の倍数までの累積和を見ることで購入できた個数をカウントできる
- BITを使うことで累積和の更新を $O(\mathrm{log} M)$ でできる

実装は

二次元配列を用意する
- 表記の簡略化のため、 $\mathit{LT} \lbrack i \rbrack$ を $\mathit{LR}_{i}$ と表記する
$1 \le i \le N$ について、 $\lbrack l_{i}, r_{i} \rbrack$ を $\mathit{LR}_{r_{i} - l_{i} + 1}$ に追加していく
長さ $M + 1$ のBITを用意し、BITの $i$ 番目までの和を取得する操作の出力を $\mathrm{BIT}_{i}$ とする
$k = 0$ とする
について、以下の操作を実施する
- 各 $\lbrack l_{i}, r_{i} \rbrack \in \mathit{LR}_{d - 1}$ について、BITで $l_{i}$ 番目をインクリメントする操作と $r_{i} + 1$ 番目をデクリメントする操作を実施する
- $k$ に $| \mathit{LR}_{d - 1} |$ を加算する
- $N - k + \sum_{m = 1}^{\lfloor \frac{M}{d} \rfloor} \mathrm{BIT}_{m * d}$ を出力する

計算量はソートに $O(N)$ 、BITのインクリメントとデクリメントが $N$ 回実施されるので $O(N \mathrm{log} M)$ 、BITのGet操作が $M \mathrm{log} M$ 回実施されるので $O(M \mathrm{log} M \mathrm{log} M)$ となるので、合計で $O((N + M \mathrm{log} M) \mathrm{log} M)$

躓いた点

BITで累積和を更新していく発想が出なかった

2/26: AtCoder Grand Contest 020 C - Median Sum

供養

問題

Difficulty: 2311 (記事作成時点)

解法

$A$ の任意の部分集合とその補集合を考えたとき、それぞれの和が $S_{j}$ となり、2つを足した値は $\sum_{i = 1}^{N}A_{i}$ で一定である
上記の関係はとで観測することができる
- $S_{0} = 0$ とする
よって、 $S_{2^{N - 1}}$ は $s \ge \lceil \frac{\sum_{i = 1}^{N}A_{i}}{2} \rceil$ かつ $A$ の要素の組合せで作れる最小の値となる
愚直にやると $O(NS_{2^{N} - 1})$ となって間に合わないので、BitSetなどで高速化する

実装は

$S_{2^{N} - 1} = \sum_{i = 1}^{N}A_{i}$ を求める
BitSet $B$ を用意し、 $B_{0} = 1$ とする
$1 \le i \le N$ について、 $B$ を $B$ と $B$ を $A_{i}$ だけ左シフトさせたものの論理和をとって更新していく
$s = \lceil \frac{S_{2^{N} - 1}}{2} \rceil, \dots$ について、最初に $B_{s} = 1$ となる $s$ を出力する

計算量は $O(\frac{NS_{2^{N} - 1}}{64})$

躓いた点

BitSetがうまく実装できなかった

2/27: AtCoder Regular Contest 006 D - アルファベット探し

供養

問題

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

解法

長さ $H \times W$ の配列 $R$ を用意し、 $R \lbrack x \rbrack = x$ とする
$h = 0, \dots, H - 1, w = 0, \dots, W - 1$ について、 $c_{(h, w)}$ が黒ならば8方向に隣接している黒とUnionし、 $R \lbrack h \times w \rbrack$ が $(h, w)$ の属する連結成分の代表点となるよう更新していく
長さ $H \times W$ の2次元配列 $M$ を用意し、 $M \lbrack x \rbrack = \lbrack 0, W, 0 \rbrack$ とする
について、とし、を1加算、、と更新する
- $x = h \times w$ であるような $(h, w)$ が代表点である連結成分の要素数と、それらの左端/右端を持つ
$\mathit{ABC} = \lbrack 0, 0, 0 \rbrack$ を用意する
について、を求める
- $k \ge 1$ ならば倍率となる
$k \ge 1$ ならば $\frac{M \lbrack r \rbrack \lbrack 0 \rbrack}{k^{2}}$ を計算し、 $12$ ならば $\mathit{ABC} \lbrack 0 \rbrack$ 、 $16$ ならば $\mathit{ABC} \lbrack 1 \rbrack$ 、 $11$ ならば $\mathit{ABC} \lbrack 2 \rbrack$ をインクリメントする
$\mathit{ABC}$ を出力する

計算量は $O(HW)$

~~公式解説~~

躓いた点

斜め方向に接続しているのでUnion-Findできるという発想が出なかった

2/28: AtCoder Regular Contest 078 E - Awkward Response

供養

問題

Difficulty: 2340 (記事作成時点)

解法

$n$ について質問して Y が返ってくるかを判定する関数を $Q(n)$ とする
かつの桁数との桁数が等しいとき、はならば true、ならば false となる
- $k = 0, \dots$ について、 $Q(10^{k + 1})$ がはじめて false になったとき、 $10^{k} \le N \lt 10^{k + 1}$ である
- 上記がわかれば二部探索で求められる
$N = 10^{k}$ のときは、 $k = 0, \dots$ について、 $Q(10^{k + 1} - 1)$ がはじめて true になったとき $N = 10^{k}$ である
$N = 10^{k}$ かどうかは $Q(10^{10})$ が true となるかで判定できる

実装は

$U = 10, k = 0, X = \mathrm{false}$ とする
$Q(10^{10})$ が true ならば $k = 1, X = \mathrm{true}$ とする
{tex: Q(U - k) = X} となるまで $U$ を10倍し続ける
$X = \mathrm{true}$ のとき(i.e. $N = 10^{k}$ のとき)、 $\frac{U}{10}$ を答えとして出力する
$\frac{U}{10} \le n \lt U$ の範囲で、 $Q(10n) = \mathrm{true}$ である最小の $n$ を二分探索で求め、 $n$ を答えとして出力する

計算量は $O(\mathrm{log}N)$ 、クエリの発行回数は最大で40回程度

躓いた点

桁ごとに求めようとしてWA

2/29: AtCoder Beginner Contest 147 F - Sum Difference

供養

問題

Difficulty: 2341 (記事作成時点)

解法

$S + T$ は一定なので、 $U = S + T$ としたとき $S - T = S - (U - S) = U - 2S$ より $S$ のとりうる値の種類を数えればよい
のとき、は要素をいくつとるかだけに依存するので通り
- $D = 0 \land X = 0$ のときのみ $1$ 通り
$D \ne 0$ のとき、 $X, D$ の符号をそれぞれ反転しても同じ計算ができるので一般性を失わずに $D \gt 0$ とする
要素を個選ぶとき、と表現できる
- このとき $k$ は $\sigma_{i = 0}^{n} i = \frac{n(n + 1)}{2} \le k \le \sigma_{j = N - n}^{N - 1} j = \frac{n(2N - n - 1)}{2}$ の範囲の任意の整数をとることができる
- よって、 $S$ のとりうる範囲を $\lbrack n \times X + \frac{n(n + 1)}{2} \times D, n \times X + \frac{n(2N - n - 1)}{2} \times D \rbrack$ と求められる
$n \times X \; \mathrm{mod}\; D \equiv n^{'} \times X \; \mathrm{mod}\; D$ が等しいときのみ $S$ の値が重なる可能性があるので、 $n \times X \; \mathrm{mod}\; D$ ごとにとりうる区間をまとめてコンテストでの時間切れや解けなかった過去問を振り返って供養していく

2/22: AtCoder Grand Contest 014 D - Black and White Tree

供養

問題

Difficulty: 2293 (記事作成時点)

解法

木が完全マッチング可能な場合かつその限りにおいて後手が勝つ
- $( \Rightarrow )$ ある完全マッチングをもとに、先手が選んだ点と対になる点を後手が選び続ければ後手が勝つ
- 対偶である、が完全マッチング不可能ならば先手が勝つことを示す
  - $T$ を適当な点を根とした根つき木として見たときに、先手が任意の葉 $v$ の親 $u$ を選ぶと、後手は $v$ を選ばないとその次の手で先手に $v$ を選ばれて負けが確定するので、後手は $v$ を選ぶことになる
  - 上記の選択後は $V \setminus \lbrace u, v \rbrace$ から誘導される $T$ の部分木について同様の選択をすることができ、このように選んでいった点対は $T$ の極大マッチングを作る
  - また、このようにして点を選んでいった場合、後手は直前に先手が選んだ点しか干渉できる(その後の操作で黒く塗れる)点を増やせない
  - (木を含む)二部グラフで完全マッチング不可能なとき、任意の極大マッチングについてマッチングしていない点からなる誘導部分グラフには孤立点 $u^{'}$ が含まれる
  - 極大マッチング構成後に先手が $u^{'}$ を選ぶと、 $u^{'}$ に干渉できる点を後手が選べないので先手の勝ちとなる

実装は

適当な点(e.g. 1)から幅優先探索をして発見した順に $v_{1}, \dots, v_{N}$ とする
$i = N, \dots, 1$ について、 $v_{i}$ がまだマッチングしていないならば、 $v_{i}$ の隣接点からまだマッチングしていない点 $v_{j}$ を任意に選びマッチングさせていく
途中でマッチングが作れなくなったときは First 、全ての点でマッチングを作れれば Second を出力する

計算量は $O(N)$

躓いた点

完全マッチングの判定問題であることに気付かずWA

2/23: AtCoder Regular Contest 088 E - Papple Sort

供養

問題

Difficulty: 2303 (記事作成時点)

解法

$S = s_{1} \dots s_{|S|}$ とする
アルファベットごとに登場回数をカウントして、奇数個登場する文字が2種類以上存在すれば回文は作れない
$1 \le i \le |S|$ について $s_{i} = c$ としたとき、 $s_{i}$ が $c$ の何回目の登場になるのかを $A_{i, c}$ で表す
アルファベット $c$ の登場回数を $C_{c}$ としたとき、各アルファベットについて前半( $A_{i, c} \le \lfloor \frac{C_{c}}{2} \rfloor$ )の登場となる集合、奇数個登場するアルファベットがあればその中央、後半( $A_{i, c} \gt \lceil \frac{C_{c}}{2} \rceil$ )の登場となる集合をそれぞれ $L, M, R$ とする
を登場順に固定するとの並びも決まり、内部では入れ替えが発生しないので全体としても入れ替え回数が最小化できる
- $L$ に対応した $R$ の並びを $R_{L}$ としたとき、 $L$ を任意の $n$ 回入れ換えて作れる $L^{'}$ に対応する $R_{L^{'}}$ に並べ替える回数を $R_{L}$ に並べ替える回数より $n$ 回以上真に小さくすることはできない
  $\because$ そのように並べた $R_{L^{'}}$ を $n$ 回入れ換えると $R_{L}$ になるため
並べ方が決まるので転倒数をBITなどを用いて求める

実装は

アルファベットごとに $S$ での登場回数をカウントし、各アルファベットの登場回数を $C = \lbrack c_{c} \rbrack$ とする
奇数回登場のアルファベットが2種類以上存在すれば -1 を出力して終了
各アルファベットごとの登場回数を表す配列 $A = \lbrack a_{c} \rbrack$ と 2次元配列 $B$ 、配列 $T$ を用意する
とする
- 各アルファベットの前半部の登場回数を意味する
について、以下のように値を更新していく
- $A_{s_{i}} \lt \lfloor \frac{C_{s_{i}}}{2} \rfloor$ のとき、 $T_{i} = L, B_{s_{i}, A_{s_{i}}} = L$ とし、 $L$ をインクリメント
- $C_{s_{i}}\; \mathrm{mod}\; 2 = 1 \land A_{s_{i}} = \lfloor \frac{C_{s_{i}}}{2} \rfloor$ のとき、 $T_{i} = \lfloor \frac{|S|}{2} \rfloor$
- $A_{s_{i}} \ge \lceil \frac{C_{s_{i}}}{2} \rceil$ のとき、 $T_{i} = |S| - 1 - B_{s_{i}, C_{s_{i}} - A_{s_{i}} - 1}$
$T$ の転倒数をBITなどで求めて出力

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

躓いた点

奇数個登場するアルファベットについて3個以上の登場を考慮せず、その位置を一律に中央にしてしまってWA

2/24: AtCoder Regular Contest 039 C - 幼稚園児高橋君

供養

問題

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

解法

1回移動するごとに、4方向について次の移動先候補の未訪問点を求めていく
次の訪問点候補 $(x, y)$ から $d$ 方向に1つ進んだ点 $(x^{'}, y^{'})$ が既訪問点ならば、 $(x, y)$ の $d$ 方向の次の移動先は $(x^{'}, y^{'})$ の $d$ 方向の移動先となる
また、 $(x, y)$ から $d$ 方向に進めるだけ進んだ点 $(x^{''}, y^{''})$ について、 $(x^{''}, y^{''})$ が $d$ の逆方向 $d^{-1}$ に進む移動先は $(x, y)$ の $d^{-1}$ 方向の移動先に更新される
既訪問点はHashmapの値の存在の有無で管理する

実装

既訪問点を管理するHashmap を用意する
- 記述の簡略化のため、 $A \lbrack x \rbrack \lbrack y \rbrack$ を $A_{x, y}$ と表記する
とする
- 順に、右方向、左方向、上方向、下方向に移動したときの次の座標を意味する
- 記述の簡略化のため、 $A \lbrack x \rbrack \lbrack y \rbrack \lbrack d \rbrack$ を $A_{x, y, d}$ と表記し、また、 $d$ の逆方向を $d^{-1}$ で表す
現在地を $(x, y) = (0, 0)$ とする
について、下記のように更新する
- $A_{x, y}$ から次の訪問点 $(x^{+}, y^{+})$ を求めて $(x, y)$ を $(x^{+}, y^{+})$ に更新する
- $A_{x, y} = \lbrack (x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1) \rbrack$ とする
- 各方向 $d$ について、 $A_{x, y, d} = (x^{'}, y^{'})$ が訪問済(i. e. $A_{x^{'}, y^{'}}$ が存在する)とき、 $A_{x, y, d}$ を $A_{x^{'}, y^{'}, d}$ に更新する
- 各方向 $d$ について、 $A_{x, y, d}$ の $d^{-1}$ 方向で1つ隣(i. e. $(x, y)$ から $d$ 方向に進めるだけ進んだ既訪問点)を $(x^{''}, y^{''})$ としたとき、 $A_{x^{''}, y^{''}, d^{-1}}$ を $A_{x, y, d^{-1}}$ に更新する
$(X, Y)$ を出力する

計算量は $O(K)$

躓いた点

$A_{x, y, d}$ と $A_{x^{''}, y^{''}, d^{-1}}$ の片方しか更新せずに2WA

2/25: AtCoder Regular Contest 068 E - Snuke Line

供養

問題

Difficulty: 2310 (記事作成時点)

解法

$d$ を固定して考えたとき、 $d \le r_{i} - l_{i} + 1$ であるような名産品 $i$ は必ず購入できる
について、であるようなのときは高々1回しか購入チャンスが無いので、の間だけカウントされるようにして、の倍数までの累積和を見ることで購入できた個数をカウントできる
- BITを使うことで累積和の更新を $O(\mathrm{log} M)$ でできる

実装は

二次元配列を用意する
- 表記の簡略化のため、 $\mathit{LT} \lbrack i \rbrack$ を $\mathit{LR}_{i}$ と表記する
$1 \le i \le N$ について、 $\lbrack l_{i}, r_{i} \rbrack$ を $\mathit{LR}_{r_{i} - l_{i} + 1}$ に追加していく
長さ $M + 1$ のBITを用意し、BITの $i$ 番目までの和を取得する操作の出力を $\mathrm{BIT}_{i}$ とする
$k = 0$ とする
について、以下の操作を実施する
- 各 $\lbrack l_{i}, r_{i} \rbrack \in \mathit{LR}_{d - 1}$ について、BITで $l_{i}$ 番目をインクリメントする操作と $r_{i} + 1$ 番目をデクリメントする操作を実施する
- $k$ に $| \mathit{LR}_{d - 1} |$ を加算する
- $N - k + \sum_{m = 1}^{\lfloor \frac{M}{d} \rfloor} \mathrm{BIT}_{m * d}$ を出力する

計算量はソートに $O(N)$ 、BITのインクリメントとデクリメントが $N$ 回実施されるので $O(N \mathrm{log} M)$ 、BITのGet操作が $M \mathrm{log} M$ 回実施されるので $O(M \mathrm{log} M \mathrm{log} M)$ となるので、合計で $O((N + M \mathrm{log} M) \mathrm{log} M)$

躓いた点

BITで累積和を更新していく発想が出なかった

2/26: AtCoder Grand Contest 020 C - Median Sum

供養

問題

Difficulty: 2311 (記事作成時点)

解法

$A$ の任意の部分集合とその補集合を考えたとき、それぞれの和が $S_{j}$ となり、2つを足した値は $\sum_{i = 1}^{N}A_{i}$ で一定である
上記の関係はとで観測することができる
- $S_{0} = 0$ とする
よって、 $S_{2^{N - 1}}$ は $s \ge \lceil \frac{\sum_{i = 1}^{N}A_{i}}{2} \rceil$ かつ $A$ の要素の組合せで作れる最小の値となる
愚直にやると $O(NS_{2^{N} - 1})$ となって間に合わないので、BitSetなどで高速化する

実装は

$S_{2^{N} - 1} = \sum_{i = 1}^{N}A_{i}$ を求める
BitSet $B$ を用意し、 $B_{0} = 1$ とする
$1 \le i \le N$ について、 $B$ を $B$ と $B$ を $A_{i}$ だけ左シフトさせたものの論理和をとって更新していく
$s = \lceil \frac{S_{2^{N} - 1}}{2} \rceil, \dots$ について、最初に $B_{s} = 1$ となる $s$ を出力する

計算量は $O(\frac{NS_{2^{N} - 1}}{64})$

躓いた点

BitSetがうまく実装できなかった

2/27: AtCoder Regular Contest 006 D - アルファベット探し

供養

問題

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

解法

長さ $H \times W$ の配列 $R$ を用意し、 $R \lbrack x \rbrack = x$ とする
$h = 0, \dots, H - 1, w = 0, \dots, W - 1$ について、 $c_{(h, w)}$ が黒ならば8方向に隣接している黒とUnionし、 $R \lbrack h \times w \rbrack$ が $(h, w)$ の属する連結成分の代表点となるよう更新していく
長さ $H \times W$ の2次元配列 $M$ を用意し、 $M \lbrack x \rbrack = \lbrack 0, W, 0 \rbrack$ とする
について、とし、を1加算、、と更新する
- $x = h \times w$ であるような $(h, w)$ が代表点である連結成分の要素数と、それらの左端/右端を持つ
$\mathit{ABC} = \lbrack 0, 0, 0 \rbrack$ を用意する
について、を求める
- $k \ge 1$ ならば倍率となる
$k \ge 1$ ならば $\frac{M \lbrack r \rbrack \lbrack 0 \rbrack}{k^{2}}$ を計算し、 $12$ ならば $\mathit{ABC} \lbrack 0 \rbrack$ 、 $16$ ならば $\mathit{ABC} \lbrack 1 \rbrack$ 、 $11$ ならば $\mathit{ABC} \lbrack 2 \rbrack$ をインクリメントする
$\mathit{ABC}$ を出力する

計算量は $O(HW)$

~~公式解説~~

躓いた点

斜め方向に接続しているのでUnion-Findできるという発想が出なかった

2/28: AtCoder Regular Contest 078 E - Awkward Response

供養

問題

Difficulty: 2340 (記事作成時点)

解法

$n$ について質問して Y が返ってくるかを判定する関数を $Q(n)$ とする
かつの桁数との桁数が等しいとき、はならば true、ならば false となる
- $k = 0, \dots$ について、 $Q(10^{k + 1})$ がはじめて false になったとき、 $10^{k} \le N \lt 10^{k + 1}$ である
- 上記がわかれば二部探索で求められる
$N = 10^{k}$ のときは、 $k = 0, \dots$ について、 $Q(10^{k + 1} - 1)$ がはじめて true になったとき $N = 10^{k}$ である
$N = 10^{k}$ かどうかは $Q(10^{10})$ が true となるかで判定できる

実装は

$U = 10, k = 0, X = \mathrm{false}$ とする
$Q(10^{10})$ が true ならば $k = 1, X = \mathrm{true}$ とする
{tex: Q(U - k) = X} となるまで $U$ を10倍し続ける
$X = \mathrm{true}$ のとき(i.e. $N = 10^{k}$ のとき)、 $\frac{U}{10}$ を答えとして出力する
$\frac{U}{10} \le n \lt U$ の範囲で、 $Q(10n) = \mathrm{true}$ である最小の $n$ を二分探索で求め、 $n$ を答えとして出力する

計算量は $O(\mathrm{log}N)$ 、クエリの発行回数は最大で40回程度

躓いた点

桁ごとに求めようとしてWA

2/29: AtCoder Beginner Contest 147 F - Sum Difference

供養

問題

Difficulty: 2341 (記事作成時点)

解法

$S + T$ は一定なので、 $U = S + T$ としたとき $S - T = S - (U - S) = U - 2S$ より $S$ のとりうる値の種類を数えればよい
のとき、は要素をいくつとるかだけに依存するので通り
- $D = 0 \land X = 0$ のときのみ $1$ 通り
$D \ne 0$ のとき、 $X, D$ の符号をそれぞれ反転しても同じ計算ができるので一般性を失わずに $D \gt 0$ とする
要素を個選ぶとき、と表現できる
- このとき $k$ は $\sum_{i = 0}^{n} i = \frac{n(n + 1)}{2} \le k \le \sum_{j = N - n}^{N - 1} j = \frac{n(2N - n - 1)}{2}$ の範囲の任意の整数をとることができる
- よって、 $S$ のとりうる範囲を $\lbrack n \times X + \frac{n(n + 1)}{2} \times D, n \times X + \frac{n(2N - n - 1)}{2} \times D \rbrack$ と求められる
$n \times X \; \mathrm{mod}\; D \equiv n^{'} \times X \; \mathrm{mod}\; D$ のときのみ $S$ の値が重なる可能性があるので、 $n \times X \; \mathrm{mod}\; D$ ごとに区間をまとめて取り得る値の種類を計算する

実装は

$D = 0$ のとき、 $X = 0$ ならば $1$ を、そうでなければ $N + 1$ を出力して終了
$D \lt 0$ のとき、 $X = -X, D = -D$ とする
keyが整数、valueが二次元配列となるようなhashmap $M$ を用意する
$0 \le n \le N$ について、 $M \lbrack n \times X \; \mathrm{mod}\; D \rbrack$ に $\lbrack n \times X + \frac{n(n + 1)}{2} \times D, n \times X + \frac{n(2N - n - 1)}{2} \times D \rbrack$ を追加する
$C = 0$ とする
各 $M \lbrack k \rbrack$ について、要素である区間の始点について昇順となるようにソートする
$t^{'} = M \lbrack k \rbrack \lbrack 0 \rbrack \lbrack 0 \rbrack - 1$ とする
各区間について以下のように更新していく
- ならばとする
  - 左端をカウントするために $C$ に加算しておく
- $C = C + \mathrm{max}({t - t^{'}, 0})$ とする
- $t^{'} = \mathrm{max}(t, t^{'})$ とする
$\frac{C}{D}$ を出力する

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

躓いた点

$S - T$ の取り得る値を求めようとして条件詰め切れずWA