AtCoder Beginner Contest 151

Tasks - AtCoder Beginner Contest 151

A

言語を間違えてしまい 1WA。char 型に一を足すと int 型になることを考えてなくて 1WA。インクリメントなら壊れません。

B

N 掛ける M 引く総和をそのまま出力して 1WA。点数に上下限があることにきづいて修正しましたが、100 点満点だと勘違いして 1WA。

C

定期的に似たような問題が出されるので、AC してない問題の WA は数えないことは印象に残っていました。

D

グラフの直径といいます。木であれば線形時間で解けますが、一般には二乗時間かかると思います。

E

max X の総和から min X の総和を引けば求まります。max X の総和と min の総和は対称的なので、max X を求めることだけ考えます。A を整列しておきます。N 個から K 個選んだときの最大値は、選ばれた数のうちもっとも右側の数です。もっとも右側の数が A[x] であるような組合せは A[1] から A[x-1] までから K - 1 個選ぶ組合せの数だけあるので、A[x] は C(x-1,K-1) 回足されます。これをすべての A[1] から A[N] に対して行えばよいです。

余談ですが A[1] から A[N] までから K 個選ぶ選び方は、「A[x] が最も右側である K 個の選び方」をすべての x=1 から N までをあわせたもの、なので

\begin{align}
\sum_{x=1}^{N} {}_{x - 1}\mathrm{C}_{K - 1} = {}_{N} \mathrm{C}_{K}
\end{align}

という恒等式が成り立ちます。

F

最小包含円の形は二通りあって、ある二点を直径とする円か、ある三点を通る円です。このことから最小包含円の中心の候補は、二点の中点と、三点の外心に限られます。二点の中点はすぐに求められますが、三点の外心はそこまで明らかではありません。

外心は三角形の各辺に対する垂直二等分線の交点です。よって交点が求められればよいです。任意の三角形は平行移動によって原点を頂点にもつ三角形に移せるので、一点が原点のうえにあるような三角形 OAB に対して外心を与えることを考えます。

直交座標

A(a,b), B(c,d) とします。線分 OA の垂直二等分線は $(a,b) \cdot ( (x, y) - (a / 2, b / 2) ) = 0$ です。原点を通りベクトル $(a,b)$ と直交する直線は $(a,b) \cdot (x,y) = 0$ なので、これを $(a/2, b/2)$ だけ平行移動したと考えればよいです。同様にして線分 OB の垂直二等分線は $(c,d) \cdot ( (x, y) - (c / 2, d / 2) ) = 0$ です。この二直線の交点は連立方程式

\begin{align}
ax + by &= \frac{a^2 + b^2}{2} \\
cx + dy &= \frac{c^2 + d^2}{2}
\end{align}

の解になります。クラメルの公式によって

\begin{align}
x = \frac{\begin{vmatrix} \frac{a^2+b^2}{2} & b \\ \frac{c^2+d^2}{2} & d\end{vmatrix}}{\begin{vmatrix} a & b \\ c & d \end{vmatrix}}
\end{align}

\begin{align}
y = \frac{\begin{vmatrix} a & \frac{a^2+b^2}{2} \\ c & \frac{c^2+d^2}{2}\end{vmatrix}}{\begin{vmatrix} a & b \\ c & d \end{vmatrix}}
\end{align}

です。

複素座標

点 A(a), B(b) とします。線分 OA の垂直二等分線は $|z|^2 = |z-a|^2$ です。$|z|^2 = z \overline{z}$ なので $z \overline{a} + \overline{z} a = a \overline{a}$ と書き換えられます。同様に線分 OB の垂直二等分線は $|z|^2 = |z-b|^2$ であり、書き換えれば $z \overline{b} + \overline{z} b = b \overline{b}$ です。$z$ と $\overline{z}$ の連立方程式を解けばよく、クラメルの公式より

\begin{align}
z = \frac{\begin{vmatrix} a \overline{a} & a \\ b \overline{b} & b\end{vmatrix}}{\begin{vmatrix} \overline{a} & a \\ \overline{b} & b \end{vmatrix} }
\end{align}

です。



直交座標だと x と y の両方を解かなければならないのに対して、複素座標だと z だけ解けばいいので実装するのが楽です。

ちなみに本番は検索して出てきた tubo さんのコードを貼りました。