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

AtCoder Beginner Contest 197（Sponsored by Panasonic）に参加。微増しましたがHighest更新ではありませんでした。

A - Rotate (100点)
B - Visibility (200点)
C - ORXOR (300点)
D - Opposite (400点)
E - Traveler (500点)
F - Construct a Palindrome (600点、実行時間制限: 3 sec)
結果、感想

A - Rotate (100点)

std::rotateやstd::string.substrを使ってもできますが、今回は3文字固定なのでS[1], S[2], S[0]の順に出力すればいいです。

B - Visibility (200点)

マス $(X,\,Y)$ から4方向それぞれへ範囲外に出る、もしくは障害物がにぶつかるまで数えながら進んでいけばいいです。実装方法によってはスタートマスの重複カウントに注意。

C - ORXOR (300点)

区間の分け方は最後を除くどの要素の後で区切るかの $2^{N-1}$ 通りでこれをbit全探索していくことで答えを出すことができます。
答えの初期値を $10^9$ にしていたのですが、この問題では最大 $2^{30}-1 = 1\,073\,741\,823$ になりうるので、1WA出してしまいました...

またこの問題はDFSでも答えを出すことができ、こっちの場合は関数の返り値を答えにすればいいので、初期値に悩まされる心配はありません。

$N$ が偶数であり、 $p_0$ と $p_{\frac{N}{2}}$ の中点が正 $N$ 角形の対称中心*1になり、この点を $o$ とします。この正 $N$ 角形の頂点は点 $o$ を中心とする円の演習を $N$ 等分する $N$ 点であり、 $p_0,\,p_1,\,\dots,\,p_{N-1}$ は反時計回りに並んでいるので、 $\overrightarrow{o\,p_1}$ は $\overrightarrow{o\,p_0}$ を点 $o$ 中心で反時計回りに $\displaystyle \frac{360}{N}^\circ = \frac{2\pi}{N}$ 回転させたものであるので、点 $p_1$ の座標を計算することができます。

$\begin{pmatrix} x \\ y \\ \end{pmatrix}$ を始点中点で反時計周りに角度 $\theta$ だけ回転させるとき、 $x = r \cos \alpha,$ $y = r\sin\alpha$ となる実数 $r,\,\alpha$ を用いると回転後のベクトルは $\begin{pmatrix} r \cos (\alpha + \theta) \\ r \sin (\alpha + \theta) \\ \end{pmatrix} = \begin{pmatrix} x \cos \theta - y \sin \theta \\ x \sin \theta + y \sin \theta \\ \end{pmatrix}$ となります(途中式は加法定理を用いて計算)。これを直接計算さてもいいですし、回転は一次変換であることから回転行列 $\boldsymbol{R}_{\theta} = \begin{pmatrix} \cos\theta & -\sin\theta \\ \sin\theta & \cos\theta \\ \end{pmatrix}$ を用いた行列積でも求まりますし、Gauß平面上の回転は複素数の積であることから $(x + \mathrm{i}y)(\cos \theta + \mathrm{i}\sin \theta) = (x\cos \theta - y\sin \theta) + \mathrm{i}(x \sin \theta + y \sin \theta)$ でも計算することができます。

また、別解として $\triangle{p_0p_1p_{\frac{N}{2}}}$ は $\angle p_1 = 90^\circ$ ( $p_0p_{\frac{N}{2}}$ が直径より円周角) $,$ $\angle p_{\frac{N}{2}} = \displaystyle \frac{180}{N}^\circ = \frac{\pi}{N}$ (これも円周角) の三角形であることから $\overrightarrow{p_{\frac{N}{2}}p_1}$ は $\overrightarrow{p_{\frac{N}{2}}p_0}$ を点 $p_{\frac{N}{2}}$ 中心で反時計回りに $\displaystyle \frac{\pi}{N}$ 回転させたものを $\displaystyle \cos \frac{\pi}{N}$ 倍したものになる、という解法があります。

E - Traveler (500点)

回収するボールの色を表す整数が広義単調増加でなければならないので色の回収順は固定されています。

色が $c$ であるようなボール(のインデックス)の集合を $S_c$ とすると色 $c$ を回収しているときに $\displaystyle \min_{i \in S_c} X_i$ と $\displaystyle \max_{i \in S_c} X_i$ の両方を訪れる必要があり、その一方を訪れたのちもう一方へ向かう途中に色 $c$ であるようなボールを全て回収することができます。同じ色の改修中に両端点を複数回訪れることに意味はないため、どちらの端点を先に訪れるかを決めたときこのような回収方法が最適手の1つとなります。

さて各色ごとにどちら向きに進むのが最善かを判断することになりますが、これは前の色をどちら向きで回収するかによって最後の位置が決まるのでそれを基にDPで求めることができます。
色について座標圧縮しておいて $i$ 番目に小さい色を $k_i$ とし、この色の個数を $n$ とします。ただし、最初と最後には座標 $0$ にいなければならないため、便宜上 $k_0,\,k_{n+1}$ $(\forall i, k_0 \lt C_i \lt k_{n+1})$ と存在しない色を追加し、この色のボールが座標 $0$ にあるものとします。また、 $d_i = \displaystyle \max_{i \in S_{k_i}} X_i - \min_{i \in S_{k_i}} X_i$ とします。

$$ {\mathrm{dp}}_{i,j} = (\text{色 $k_i$ のボールを ($j=0$ ? 右 : 左) 向きにとる時の最後までの最小移動距離}) $$ としたとき $$ {\mathrm{dp}}_{0,0} = {\mathrm{dp}}_{0,1} = 0 $$ であり、 $0 \lt i \leq n+1$ について
$$
{\mathrm{dp}}_{i,0} = \min\left\{{\mathrm{dp}}_{i-1,0} + \left|\max_{i \in S_{k_{i-1}}} X_i - \min_{i \in S_{k_i}} X_i \right|,\,{\mathrm{dp}}_{i-1,1} + \left|\min_{i \in S_{k_{i-1}}} X_i - \min_{i \in S_{k_i}} X_i \right| \right\} + d_i
$$ $$
{\mathrm{dp}}_{i,1} = \min\left\{{\mathrm{dp}}_{i-1,0} + \left|\max_{i \in S_{k_{i-1}}} X_i - \max_{i \in S_{k_i}} X_i \right|,\,{\mathrm{dp}}_{i-1,1} + \left|\min_{i \in S_{k_{i-1}}} X_i - \max_{i \in S_{k_i}} X_i \right| \right\} + d_i
$$

という漸化式が成り立ち、答えは ${\mathrm{dp}}_{n+1,0} = {\mathrm{dp}}_{n+1,1}$ となります。

F - Construct a Palindrome (600点、実行時間制限: 3 sec)

回文ができる時、「 $1 \rightarrow v$ と $N \rightarrow v$ で同じ文字列のパスが存在するような頂点 $v$ が存在する」、または「 $1 \rightarrow u$ と $N \rightarrow v$ で同じ文字列のパスが存在するような隣接頂点組 $(u,\,v)$ が存在する」が成立します。始点である頂点 $1$ と終点である頂点 $N$ から同時に同じ文字が書かれている辺を辿って同じ頂点もしくは隣接頂点に到達するかどうかを調べればいい、という所まではコンテスト中に考察できましたが、そこから何も進めませんでした。

次のようなグラフを考えます。 $N^2$ 頂点で、各頂点は元のグラフの2頂点の組に対応する(2つが同じ頂点でもよい)、ここで $(u,\,v)$ に対応する頂点を $\mathrm{node}(u,\,v)$ と表記します。辺については元のグラフで $u_1,\,u_2$ の辺と $v_1,\,v_2$ の辺で同じ文字が書かれている辺が存在する場合 $\mathrm{node}(u_1,\,v_1)$ と $\mathrm{node}(u_2,\,v_2)$ の間に無向辺を張ります。

このグラフにおいて元の「 $1 \rightarrow v$ と $N \rightarrow v$ で同じ文字列のパスが存在するような頂点 $v$ が存在する」ことは $\mathrm{node}(1,\,N)$ から $\mathrm{node}(v,\,v)$ への経路が存在し、その距離の2倍が回文の長さになります。
また、「 $1 \rightarrow u$ と $N \rightarrow v$ で同じ文字列のパスが存在するような隣接頂点組 $(u,\,v)$ が存在する」については $\mathrm{node}(1,\,N)$ から $\mathrm{node}(u,\,v)$ への経路が存在し、その距離の2倍 + 1 が回文の長さになります。