CODE THANKS FESTIVAL 2018 (Parallel)

ABCDで4完だった。

A - Two Problems (100点)

問題: A - Two Problems
条件を見ると ${B \leq D}$ なので、2問目を優先して解くようにする。

拙解 (C++): Submission #3662310 - CODE THANKS FESTIVAL 2018(Parallel)

B - Colored Balls (200点)

問題: B - Colored Balls
操作を行う回数をそれぞれ ${a,b}$ とおいて
${ \displaystyle X=3a+b\\ Y=a+3b }$
なので、
${ \displaystyle a=\frac{3Y-X}{8}\\ \displaystyle b=\frac{3X-Y}{8} }$
したがって ${a\in\mathbb{N}, b\in\mathbb{N}}$ より、 ${3Y-X}$ と ${3X-Y}$ がいずれも8の倍数かつ負でないときに"Yes"を出力。

拙解 (C++): Submission #3662676 - CODE THANKS FESTIVAL 2018(Parallel)

C - Pair Distance (300点)

問題: C - Pair Distance
なんとなくでやって3WA出したのでちゃんと式に起こしてやったら通った。

全ての ${(i, j)}$ の組み合わせ（ただし ${1\leq i\lt j\leq N}$ ）における点の間の距離の和を取ればいいが、 ${N\le 10^5}$ なので愚直にやると ${O(N^2)}$ になってしまって間に合わない。
累積和 ${S_i=\sum_{j=1}^{i} x_j}$ を計算しておけば、
${\displaystyle \begin{eqnarray} \sum_{1\leq i\lt j\leq N}^{} (x_j-x_i) &=& \sum_{j=2}^{N} \sum_{i=1}^{j-1} (x_j-x_i) \\ &=& \sum_{j=2}^{N} ((j-1)x_j-\sum_{i=1}^{j-1} x_i) \\ &=& \sum_{j=2}^{N} ((j-1)x_j-S_{j-1}) \end{eqnarray} }$
というふうに求められる。累積和を求めるのも上の式の値を求めるのも ${O(N)}$ なので、これで解けた。

拙解 (C++): Submission #3662310 - CODE THANKS FESTIVAL 2018(Parallel)

D - Concatenation (300点)

問題: D - Concatenation
Cで唸ってる間にできてしまった。
iを0から見ていってs[i]が最小を更新したor最小と等しかった回数を数えればOK

拙解 (C++): Submission #3663260 - CODE THANKS FESTIVAL 2018(Parallel)

E - Union (400点)

問題: E - Union
できなかった。久々に誤読に誤読を重ねた。まずは操作のところの「黒板に ${X+1}$ を ${1}$ つ書く」を「黒板に ${X+1}$ を ${2}$ つ書く」と思い込み、加えて「ただ ${1}$ つの整数が黒板に書かれているように」を「 ${1}$ 種類だけの整数が黒板に書かれているように」の意味に思い込んだ。偶然、小さなテストケースが６つくらいなら通ってしまう誤読をしたので気付かなかった。