A - Arithmetic Sequence Editorial
by 
maspy
◆ 次元削減
数列 \(A\) が等差数列であることは、\(2A_2 - A_1 - A_3 = 0\) と同値です。したがって、\(A_i\) の値そのものは重要ではなく、\(2A_2 - A_1 - A_3\) の値のみが重要です。
そこで、\(X = 2A_2 - A_1 - A_3\) とおくことにします。操作結果の \(X\) の値も \(A_i\) の値は使わずに計算できるため、問題を解くにあたって \(A_i\) の値は完全に無視してしまって構いません。結局、次の問題を解けばよいことが分かります。
整数 \(X\) が与えられる。 次の \(2\) 種の操作が行える：
- \(X\) に \(-1\) を加える（\(i = 1, 3\) とした場合）
- \(X\) に \(2\) を加える （\(i = 2\) とした場合）
\(X = 0\) が成り立つようにするための最小の操作回数を求めよ。
数列の状態として考慮すべき変数の数（次元）が \(A_1, A_2, A_3\) の \(3\) つから、\(X\) の \(1\) つになって、状況が簡潔になりました。
◆ 答の計算
\(X\) に \(2\) を加える回数を \(k\) とすると、\(k\geqq 0\) および \(X + 2k\geqq 0\) が必要です。この条件は、 \(k_0 = \max(0, \lceil (-X)/2\rceil)\) として、\(k\geqq k_0\) と表すことができます。
\(2\) を加える回数 \(k\geqq k_0\) を固定すると、\(-1\) を加える回数は \(X + 2k\) となり、全体の操作回数は \(X + 3k\) です。これを最小化するためには \(k\) を最小化すればよく、答は \(X + 3k_0\) であることが分かります。時間計算量は \(\Theta(1)\) 時間です。
◆ 解答例
posted:
last update: