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

3/1: AtCoder Grand Contest 024 D - Isomorphism Freak

供養

問題

Difficulty: 2342 (記事作成時点)

解法

もとの木の直径を $R$ とすると、少なくとも $\lfloor \frac{R}{2} \rfloor + 1$ 色が必要
$\because$ 直径を $r$ だけ増加させるよう点を追加した木の中心から $d$ だけ離れた点を根とした根付き木の深さは $\lfloor \frac{R + r}{2} \rfloor + d$ となるので、 $d$ が異なれば同型にはならない
$T$ の中心から $0 \le d \le \lfloor \frac{R}{2} \rfloor$ だけ離れた点同士が全て同じ次数、同じ色となるようにすればよい彩色となるので、 $\lfloor \frac{R}{2} \rfloor + 1$ 色あれば十分
もとの木の中心が $u, v$ の2つあるときは、各点 $1 \le w \le N$ について $u, v$ の近い方との距離を $r$ としたときに $r$ の等しい点同士で次数を揃える(i. e. 最大値にする)よう追加すればよい
もとの木の中心が $u$ 1つのときは、 $u$ のみが木の中心である場合と、 $u$ の隣接点から任意の $v$ を選んで $u, v$ が木の中心となるようにした場合で上記と同様に計算し、葉が最小となる場合を選ぶ

実装は

全点対間最短距離を求める
- Warshall-Floydで $O(N^{3})$ 、各点Dijkstraで $O(N^{2})$
- 以降、 $u, v$ 間の最短距離を $d_{u, v}$ と表記する
$1 \le u \le N$ について、 $\mathrm{max}(d_{u, v} \mid 1 \le v \le N)$ が最小となる点集合を $C$ とし、そのときの最小値を $R$ とする
を引数とする関数を以下のように作る
- 配列 $D$ を用意する
- $1 \le w \le N$ について、 $r = \mathrm{min(d_{u, w}, d_{v, w})}$ とし、 $D \lbrack r \rbrack$ を $w$ の次数と比較して最大値を保存する
- をならば、ならばとする
  - $\mathrm{max}()$ は $N = 2$ のときに $L = 0$ とならないようにしている
- $r = 1, \dots$ について、 $D \lbrack r \rbrack \gt 1$ ならば $L = L \times D \lbrack r \rbrack$ とする
- $L$ を出力する
$C$ が $u, v$ の2点あれば $R$ と $L(u, v)$ を出力する
$C$ が $u$ の1点のみの場合、 $L(u, u)$ と $u$ の各隣接点 $v$ について $L(u, v)$ から最小値を求め、 $R + 1$ とその最小値を出力する

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

公式解説

躓いた点

もとの木の中心が1つの場合に隣接点と2つを中心とする場合と比較する実装をしていなかった

3/2: AtCoder Regular Contest 032 C - 仕事計画

供養

問題

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

解法

$T = \mathrm{max}(b_{i} \mid 1 \le i \le N)$ とする
$\lbrack a_{i}, b_{i}, i \rbrack$ を $b_{i}$ について降順にソートする
について、で初期化する
- 以降、表記の簡略化のため $\mathit{DP} \lbrack t \rbrack \lbrack j \rbrack$ を $\mathit{DP}_{k, j}$ と表記する
配列 $A, B$ について $A \lbrack 0 \rbrack \gt B \lbrack 0 \rbrack$ もしくは $A \lbrack 0 \rbrack = B \lbrack 0 \rbrack \land A \lbrack 1 \rbrack \lt B \lbrack 1 \rbrack$ であるかを返す関数を $F(A, B)$ とする
について、以下のように更新していく
- $F(\mathit{DP}_{t + 1}, \mathit{DP}_{t}) = \mathrm{true}$ ならば $\mathit{DP}_{t} = \mathit{DP}_{t + 1}$
- $b_{i} = t$ であるような $i$ について、 $A = \lbrack \mathit{DP}_{t, 0} + 1, i, t \rbrack$ としたとき、 $F(A, \mathit{DP}_{a_{i}}) = \mathrm{true}$ ならば $\mathit{DP}_{a_{i}} = A$
$W = \emptyset, t = 0$ とする
$\mathit{DP}_{t, 0} \gt 0$ ならば $W$ の末尾に $\mathit{DP}_{t, 1}$ を追加し、 $t = \mathit{DP}_{t, 2}$ とする更新を $\mathit{DP}_{t, 0} = 0$ となるまで繰り返す
$\mathit{DP}_{0, 0}$ を出力する
$W$ を出力する

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

公式解説

躓いた点

前から求めようとしてMLEとTLEの解法しか出なかった

3/3: AtCoder Grand Contest 011 C - Squared Graph

供養

問題

Difficulty: 2349 (記事作成時点)

解法

グラフの任意の極大連結成分 $G_{A} = (V_{A}, E_{A}), G_{B} = (V_{B}, E_{B})$ について、 $H_{AB} = V_{A} \times V_{B}$ の領域にある連結成分の数 $C_{AB}$ を考える
$|V_{A}| = 1$ ならば $C_{AB} = |V_{B}|$ であり、 $|V_{B}| = 1$ ならば $C_{AB} = |V_{A}|$ である
$a, a^{'} \in V_{A}$ および $b, b^{'} \in V_{B}$ について任意の正整数 $l$ を用いて、 $a a_{1} \dots a_{l - 1} a^{'}, b b_{1} \dots b_{l - 1} b^{'}$ という長さ $l$ のパスが $G_{A}, G_{B}$ にそれぞれ存在するとき、 $(a, b) (a_{1}, b_{1}) \dots (a_{l - 1}, b_{l - 1}) (a^{'}, b^{'})$ というパスが [H_{AB}] に作られるので、 $(a, b)$ と $(a^{'}, b^{'})$ は $a, a^{'}$ 間と $b, b^{'}$ 間に同じ長さのパスがある場合かつその限りにおいて連結となる
長さ $l$ のパスがある場合、任意の非負整数 $k$ を用いた長さ $l + 2k$ のパスを作ることができるので、上の条件は $(a, b)$ と $(a^{'}, b^{'})$ は $a, a^{'}$ 間と $b, b^{'}$ 間に偶奇の等しいパスがある場合かつその限りにおいて連結と言い換えられる
連結成分中に奇ループが存在する場合、任意の2点間の間に偶奇両方のパスを作ることができるので、 $G_{A}, G_{B}$ の少なくとも一方が二部グラフでない場合、 $C_{AB} = 1$ である
$G_{A}, G_{B}$ の両方とも二部グラフの場合、 $G_{A} = (V_{A}, W_{A}, E_{A}), G_{B} = (V_{B}, W_{B}, E_{B})$ としたときに $V_{A} \times V_{B} \cup W_{A} \times W_{B}, V_{A} \times W_{B} \cup W_{A} \times V_{B}$ はそれぞれ連結だが、これら2つの連結成分を接続する辺は存在しないので $C_{AB} = 2$ となる
上記を全て合計すると、孤立点の個数を $n$ 、2点以上からなる二部グラフである連結成分の個数を $p$ 、2点以上からなる二部グラフでない連結成分の個数を $q$ としたとき、求める答えは $n(2N - n) + 2p(p + q) + q^{2}$

実装は

グラフについてUnion-Findにより連結成分を求める
$n = 0, p = 0, q = 0$ とする
各連結成分について、孤立点か、2点以上からなる二部グラフか、それ以外かを求め、それぞれ $n, p, q$ をインクリメントする
$n(2N - n) + 2p(p + q) + q^{2}$ を出力する

計算量は $O(N + M)$

公式解説

躓いた点

連結成分の場合分け条件で二部グラフかどうかであることに気付かなかった
連結成分が二部グラフかの判定時に毎回 $O(N)$ の初期化を入れてTLE

3/4: AtCoder Grand Contest 036 C - GP 2

供養

問題

Difficulty: 2351 (記事作成時点)

解法

大まかな方針として以下の計算をおこなう
- $i = j$ を許容してありうるパターンの数を求める
- $\mathrm{max}(p_{i}) \gt 2M$ となってしまうパターンを引く
前者について、最終的に奇数となる要素の数を $n$ とすると、非負整数 $k$ を用いて $n = M_{\mathrm{mod}\; 2} + 2k \le \mathrm{min}(N, M)$ と表せる
$3M - n$ を $2$ ずつ $N$ 人に分配し、 $n$ を $1$ ずつ（ $N$ 人の中から） $n$ 人に分配すればいいので、あり得る組み合わせは $_{\frac{3M - n}{2} + N - 1}\mathrm{C}_{N - 1} \times _{N}\mathrm{C}_{n}$
上記をありうる $n$ についてすべて計算して合計を取る
後者について、としたとき、を人に分配し、かつへの分配が1以上のパターンを数える
- 残り $2M$ は全て $x$ に分配されているとする
$x$ への分配が0となるパターン i.e. $M$ を $N - 1$ 人で分配するパターンを、配布されない1人を選ぶために $N$ 倍した数を $M$ を $N$ 人で分配する全パターンから引けばよい
全パターンは前者と同様に奇数となる人数 $n = M_{\mathrm{mod}\; 2} + 2k \le \mathrm{min}(N, M)$ を決めて $_{\frac{M - n}{2} + N - 1}\mathrm{C}_{N - 1} \times _{N}\mathrm{C}_{n}$ を合計すればよい
$N - 1$ 人に配布するパターンは $上記の N$ が $N - 1$ のときを考えればいいので、奇数となる人数 $n = M_{\mathrm{mod}\; 2} + 2k \le \mathrm{min}(N - 1, M)$ を決めて $_{\frac{M - n}{2} + N - 2}\mathrm{C}_{N - 2} \times _{N - 1}\mathrm{C}_{n}$ を合計すればよい

実装は

$p = 998244353$ とし、 $0 \le n \le \lfloor \frac{3M}{2} \rfloor + N$ について $n!_{\mathrm{mod}\; p}, n!^{-1}_{\mathrm{mod}\; p}$ を前計算しておく
$P = 0$ とする
$0 \le k \le \lfloor \frac{\mathrm{min}(N, M)}{2} \rfloor$ について $n = M_{\mathrm{mod}\; 2} + 2k$ とし、 $_{\frac{3M - n}{2} + N - 1}\mathrm{C}_{N - 1} \times _{N}\mathrm{C}_{n} - _{\frac{M - n}{2} + N - 1}\mathrm{C}_{N - 1} \times _{N}\mathrm{C}_{n}$ を $P$ に加算する
$0 \le k \le \lfloor \frac{\mathrm{min}(N - 1, M)}{2} \rfloor$ について $n = M_{\mathrm{mod}\; 2} + 2k$ とし、 $_{\frac{M - n}{2} + N - 2}\mathrm{C}_{N - 2} \times _{N - 1}\mathrm{C}_{n}$ を $P$ に加算する
$P$ を出力する

計算量は $O(N + M)$

公式解説

躓いた点

あり得るパターンからNGとなるパターンを引く発想が出なかった

3/5: AtCoder Beginner Contest 133 F - Colorful Tree

供養

問題

Difficulty: 2351 (記事作成時点)

解法

適当な点 (e.g. 1)を根とする木としてとらえ、についてからまでの距離、そのうち色のみでの距離、登場回数を前計算する
- $r$ からの距離 $L$ 、色ごとの距離と登場回数 $D_{c}, A_{c}\;(1 \le c \le N - 1)$ とそれらを格納していくための配列をそれぞれ用意する
- $r$ からDFSをしたときに $j$ 番目に通った枝 $u_{j} \to v_{j}$ の色と長さをそれぞれ $c_{j}, d_{j}$ とする
- $u_{j} \to v_{j}$ が根から葉に向かう方向だったとき $L = L + d_{j}, D_{c_{j}} = D_{c_{j}} + d_{j}, A_{c_{j}} = A_{c_{j}} + 1$ とし、 $u_{j} \to v_{j}$ が葉から根に向かう方向だったとき $L = L - d_{j}, D_{c_{j}} = D_{c_{j}} - d_{j}, A_{c_{j}} = A_{c_{j}} - 1$ と更新し、それぞれ対応する配列に $j$ と一緒に追加する
- 番目の移動により点が初めて見つかった場合、とする
  - $F_{r} = 0$ である
  - それぞれのリストから $j \le F_{u}$ である最も後に追加された要素を二分探索で求めれば、 $l_{u}, d_{c, u}, a_{c, u}$ が求められる
各クエリについての最短共通祖先を求め、を計算する
- ここで $D_{u} = l_{u} - d_{x_{i}, u} + c_{x_{i}, u} \times y_{i}$ である

実装は

配列と二次元配列 [L]、三次元配列をそれぞれ用意する
- 表記の簡略化のためそれぞれの配列の $i$ 番目の要素を下付き文字 $i$ で表現し(e.g. $L_{i}$ )、また、末尾の要素を下付き文字 -1 で表現(e.g. $L_{-1}$ )する
とし、適当な点からDFSをし、以下のように更新していく
- 点 $u$ の隣接点から未訪点 $v$ が見つかったとき、 $j$ をインクリメントし、 $F_{v} = j$ とする
- 辺 $(u, v)$ の色と長さをそれぞれ $c, d$ としたとき、 $\lbrack j, L_{-1, 1} + d \rbrack, \lbrack j, D_{c, -1, 1} + d \rbrack, \lbrack j, A_{c, -1, 1} + 1 \rbrack$ をそれぞれ $L, D_{c}, A_{c}$ に追加する
- $v$ 以降の探索が終わって $u$ に戻ってきたとき、 $j$ をインクリメントする
- $\lbrack j, L_{-1, 1} - d \rbrack, \lbrack j, D_{c, -1, 1} - d \rbrack, \lbrack j, A_{c, -1, 1} - 1 \rbrack$ をそれぞれ $L, D_{c}, A_{c}$ に追加する
について、の番目に近い先祖を求めて配列を作る
- $u \ne r$ について $P_{u, 0}$ を $u$ の親、 $P_{r, 0} = r$ とする
- $1 \le u \le N, k = 1, \dots, \lfloor \mathrm{log}N \rfloor$ について、 $P_{u, k} = P_{P_{u, k - 1}, k - 1}$ とする
について、以下の計算をする
- LCA $w_{q}$ を求める
- を求める
  - $l_{u_{q}}$ は $L$ について $L_{k, 0} \le F_{u_{q}}$ であるような最大の $k$ を二分探索で求め、そのときの $L_{k, 1}$ である
  - $d_{x_{q}, u_{q}}, a_{x_{q}, u_{q}}$ も $D_{x_{q}}, A_{x_{q}}$ について同様に二分探索で求める
- 同様にして $D_{v_{q}}, D_{v_{q}}$ を求める
- $D_{u_{q}} + D_{v_{q}} - 2 \times D_{w_{q}}$ を出力する

計算量は前計算に $O(N\mathrm{log}N)$ 、クエリごとにLCAと $D_{u_{i}}$ をそれぞれ $O(\mathrm{log}N)$ で求めるので、合計で $O((N + Q)\mathrm{log}N)$

公式解説

躓いた点

LCAを線形探索で求めていてTLE
- 距離を求めるほうが遅いと勘違いしていた

3/6: AtCoder Beginner Contest 141 F - Xor Sum 3

供養

問題

Difficulty: 2354 (記事作成時点)

解法

$U = A_{1} \oplus \dots \oplus A_{N}$ 、青く塗った要素のXORを $X$ とすると、赤く塗った要素のXOR $Y$ は $Y = U \oplus X$ である
$U, X, Y$ の $j$ bit目をそれぞれ $u_{j}, x_{j}$ とすると、 $u_{j} = 1$ ならば $(x_{j}, y_{j}) = (1, 0)\;\mathrm{or}\;(0, 1)$ であることから $X + Y$ への $x_{j} + y_{j}$ の寄与分は一定
$u_{j} = 0$ ならば $(x_{j}, y_{j}) = (0, 0)\;\mathrm{or}\;(1, 1)$ であり、 $(x_{j}, y_{j}) = (1, 1)$ のほうが $X + Y$ への $x_{j} + y_{j}$ の寄与分が大きくなる
$j \lt j^{'}$ のとき、 $(x_{j}, y_{j}), (x_{j^{'}}, y_{j^{'}})$ がともに $(1, 1)$ ならば $x_{j} + y_{j} \lt x_{j^{'}} + y_{j^{'}}$ である
以上から、 $u_{j} = 0$ であるような $j$ について降順かつ貪欲に $(x_{j}, y_{j}) = (1, 1)$ となるような分割を作ればよい
からいくつかを選んで作られるXORの集合と、任意のについてに変えたときに作られるXORの集合は同一である
- 二者間において $A_{i}^{'}, A_{j}$ が両方選ばれた場合が元の集合において $A_{i}$ のみが選ばれた場合に対応し、 $A_{i}^{'}$ のみが選ばれた場合が元の集合において $A_{i}, A_{j}$ 両方が選ばれた場合に対応するため
についてである bit目が1になる要素が高々1つとなるように要素同士のXORをしていく
- 線形代数で言うところの行標準形を作る操作に相当する
操作後のについてである部分のみを見たときのXORを最大化するもの（のひとつ）はである
- 各当該bitが1となっている要素は高々ひとつしかないため
- $A_{i}^{'}$ はいくつかの要素のXORである可能性があるが、それを展開した場合も計算結果は一致する
上記の分割を $X$ とすると、求める答えは $U \oplus X + X$ となる

実装は

$U = A_{1} \oplus \dots \oplus A_{N}$ を求める
$k = 1$ とする
について、以下のようにを更新する
- の中から bit目が1であるようなをひとつ決める
  - そのような $A_{i}$ がひとつもなければ下記の操作はしない
- $A_{k}$ と $A_{i}$ を入れ換える
- $A_{1}, \dots, A_{N}$ について、 $i \ne k$ かつ $j$ bit目が1である $A_{i}$ について $A_{i} = A_{i} \oplus A_{k}$ とする
- $k$ を1インクリメントする
$X = A_{1} \oplus \dots \oplus A_{N}$ とする
$U \oplus X + X$ を出力する

計算量は $O(N)$

公式解説

躓いた点

$X$ の最大化の方法を思いつかなかった

3/7: AtCoder Grand Contest 010 C - Cleaning

供養

問題

Difficulty: 2360 (記事作成時点)

解法

すべての石を取り除く操作をしたと仮定する
各辺 $j$ について、石を取り除く対象のパスに含まれた回数を $c_{j}$ とする
各点 $u$ について、 $u$ を端点のひとつに持つ辺集合を $E_{u}$ とする
点 $u$ が葉のとき、 $\sum_{j \in E_{u}} c_{j} = A_{u}$ である
点 $u$ が葉ではないとき、1回の操作で $uv, uv^{'}\;(v \ne v^{'})$ のカウントが1ずつ増えるので、 $\sum_{j \in E_{u}} c_{j} = 2A_{u}$ である
木を適当な点 $r$ (e.g. 1)を根とする根つき木として考える
各点 $u \ne r$ から $u$ の親に向かう辺について、石を取り除く対象のパスに含まれた回数を $C_{u}$ とする
点 $u$ が葉ならば $C_{u} = A_{u}$ である
点 $u$ が葉でなく、 $u$ の子 $v_{1}, \dots, v_{k}$ について $C_{v_{j}}$ が分かっている場合、 $C_{u} = 2A_{u} - \sum_{j = 1}^{k}C_{v_{j}}$ である
ここで、すべてのは非負整数であることと、1回の操作でカウントを増やす辺対についてという条件があるので、以下の式が成り立たない場合は矛盾が生じる
- $C_{u} \ge 0$
- $\mathrm{max}(C_{v_{j}}, C_{u}) \le A_{u}$
$r$ については $r$ のそれぞれの子 $v_{1}, \dots, v_{k}$ について $\sum_{j = 1}^{k}C_{v_{j}} = A_{r}$ であることを確認する

実装は

点を根として探索を行い、発見順に並べたものを、各点の親をとする
- $u_{1} = 1$ である
配列 $S, C$ を用意する
について、以下のように更新していく
- $u$ の次数が1(i.e. $u$ は葉)のとき、 $S_{u} = A_{u}$ とする
- $c = 2A_{u} - S_{u}$ とし、 $C_{u} = \mathrm{max}(c, C_{u})$ とする
- $c \lt 0 \lor A_{u} \lt C_{u}$ ならば NO を出力して終了
- $S_{P_{u}}$ に $c$ を加算する
- $C_{P_{u}} = \mathrm{max}(c, C_{P_{u}})$ とする
点 $1$ の次数が1なら $S_{1} = A_{1}$ 、2以上なら $S_{1} = 2A_{1}$ ならば YES 、そうでなければ NO を出力する