AtCoder Beginner Contest 199のきろく - Flkanjin’s 競プロ録

AtCoder Beginner Contest 199（Sponsored by Panasonic）で3問しか解けませんでした...

A - Square Inequality (100点)
B - Intersection (200点)
C - IPFL (300点)
D - RGB Coloring 2 (400点)
E - Permutation (500点)
F - Graph Smoothing (600点)
結果、感想

A - Square Inequality (100点)

いつぞやの誤差を気にする問題のような問題文ですがこちらは元から整数なので素直に $A^2 + B^2$ と $C^2$ を計算して大小比較すればいいです。

B - Intersection (200点)

整数 $x$ が満たす条件は $\max A \leq x \leq \min B$ であるので答えは $\max\{\min B - \max A + 1,\,0\}$ となります。

C - IPFL (300点)

問題文の通りに実装すると $T_i = 2$ のクエリで毎回 $O(N)$ となるので $O(NQ)$ となり、間に合いません。前半後半を入れ替えたかどうかというフラグを管理し、 $T_i = 2$ のクエリが来るたびにこのフラグを反転させます。 $T_i = 1$ のクエリで入れ替える文字に注意。

D - RGB Coloring 2 (400点)

各頂点が赤、黄、青の $3$ 色なので全て試せば $3^N$ 通り、正しいかどうかを確かめるの込みで $O(3^N M)$ で間に合わない...ってやっているうちに時間が来てしまいました...

まず、連結成分ごとに独立で、それぞれの値の積が答えとなります。DFSやBFSを用いて連結成分に属す頂点をvectorに入れていったとき、最初の頂点以外は辺で結ばれた頂点がそれより前に少なくとも1つ存在し、そのためその頂点と同じ色は考えなくともいいため、連結成分の頂点数を $v$ とすると高々 $2^v$ 通りしか考えなくてもいいことが分かります(最初の頂点は任意の色がいけるが、どれをとっても対称なので1色に固定し3倍すればいい)。そのため全体の計算量が $O((N+M)2^N)$ となり、間に合うようになります。

E - Permutation (500点)

$2 \leq N \leq 18$ という制約から $O(N \cdot N!)$ は通らないな、という感じでした。

$O((N+M) 2^N)$ は通るのでbitDPなどを考えます。 $S$ を $1$ から $N$ までの整数の集合の部分集合とし、

${\mathrm{dp}}_{S} = (最初の\, |S|\, 個のみを考えたときに\, X_i \leq |S|\, である条件を全て満たす場合の数)$

としたとき、 ${\mathrm{dp}}_{\emptyset} = 1$ であり、 $x \notin S$ について $S \cup \{x\}$ が $X_i \leq |S|+1$ であるような条件を全て満たすときに $S$ から $S \cup \{x\}$ に遷移できるため、それに従って遷移させる $({\mathrm{dp}}_{S \cup \{x\}} \texttt{+=}\, {\mathrm{dp}}_{S})$ ことで答え ${\mathrm{dp}}_{\{1,\,2,\,\dots,\,N\}}$ が求まります。

F - Graph Smoothing (600点)

期待値問題なので、コンテスト中はあまり考えていませんでした。後で考えてみれば後半3問の中で一番可能性があった...

行列累乗です。 $\boldsymbol{A} = (A_1,\,A_2,\,\dots,\,A_N)^{\top}$ とし、 $N \times N$ 行列 $\boldsymbol{M} = (M_{i,\,j})$ を考えます。各頂点 $v$ の次数を $d_v$ とします。
$M_{v,\,v}$ について頂点 $v$ に隣接する頂点が選ばれたとき $A_v$ への自分自身の寄与が半分に減るため $M_{v,\,v} =\displaystyle 1 - \frac{d_v}{2M}$ となります。
$M_{v,\,u}$ については頂点 $u$ と $v$ を結ぶ辺が選ばれたとき $A_v$ への $A_u$ の寄与が $\dfrac{1}{2}$ 増えるため $M_{v,\,u} =\displaystyle \frac{1}{2M}$ となります。
その他の要素は全て $0$ です。