C - Harmonic Mean 解説 by evima
When \(N=1\), the conditions are satisfied by \(A=(1)\). When \(N=2\), there is no \(A\) that satisfies the conditions. From now on, we assume that \(N \ge 3\).
By using the fact that \(\frac{1}{k(k+1)} = \frac{1}{k} - \frac{1}{k+1}\), we can let \(A\) be \((2,6,12,20,\dots,N(N-1),N)\) to satisfy the condition of the sum.
However, if we leave it as it is, \(A\) will have duplicated elements when \(N=k(k-1)\). For example, with the above construction, \(A=(2,6,12,20,30,6)\) when \(N=6\). Let’s deal with this.
This will be resolved by using \(A=(2,2A'_1,2A'_2,\dots,2A'_{N-1})\) for the solution \(A'=(A'_1,A'_2,\dots,A'_{N-1})\) for one less \(N\). Let’s confirm that this integer sequence \(A\) satisfies the conditions.
- Since \(\sum_{i=1}^{N-1} \frac{1}{2A'_i} = \frac{1}{2}\), it satisfies \(\sum_{i=1}^{N} \frac{1}{A_i} = 1\).
- \(A'\) clearly does not contain \(1\), so \(2\) and \(2A'_i\) does not coincide. Also, since all elements of \(A'\) are distinct, all elements of \(A\) are distinct.
- Since the integers that can be expressed as \(k(k-1)\) using an integer \(k\) are not consecutive, \(A'\) is \((2,6,12,20,\dots,(N-2)(N-1),N-1)\). Even if this is doubled, it clearly does not exceed \(10^9\), so all elements are between \(1\) and \(10^9\).
Therefore, we have confirmed that \(A'\) satisfies all the conditions.
By implementing the above, this problem can be solved in \(\mathrm{O}(N)\).
If there are duplicate elements, you can also eliminate them by summing and reducing them and splitting the last element using \(\frac{1}{2} = \frac{1}{3} + \frac{1}{6}\), etc., to make the length \(N\). However, note that you need to reduce them multiple times because \(\frac{N}{2}\) can also be expressed as \(k(k-1)\) when \(N=12,420\).
(Modified the first draft written by GPT-4.)
投稿日時:
最終更新: