AtCoderログ：0030 - ARC 123 A

問題：ARC 123 A - Arithmetic Sequence

問題文

$3$ 項からなる整数列 $A=(A_1,A_2,A_3)$ が与えられます。あなたはこの数列に対して、次の操作を何回でも行うことができます：
・$i \in \{1,2,3\}$ をひとつ選び、$A_i$ に $1$ を加える。
数列 $A$ を等差数列にするために必要な操作回数の最小値を求めてください。ただし、数列 $A=(A_1,A_2,A_3)$ が等差数列であるとは、$A_2−A_1=A_3−A_2$ が成り立つことを意味します。

制約

・$1 \le A_1,A_2,A_3 \le 10^{15}$

回答1 (AC)

等差数列 (Arithmetic Sequence) とは、各項の差が等しい数列のことで、例えば $(1,2,3,4,5)$, $(1,3,5,7,9,11)$, $(6,4,2,0,-2,-4)$, $(3,3,3,3)$ は全て等差数列です。差はプラスだけでなく、マイナス (数列は減少していく) やゼロ (数列は同じ値が並ぶ) の場合もあります。

この問題では、等差数列 $A=(A_1,A_2,A_3)$ は3項なので、等差数列になるための条件は $A_2-A_1=A_3-A_2$ となるので、この条件を満たすように $A_1,A_2,A_3$ に値を加えていくことになります。どの項に値を加えるかについては、以下のように場合分けするとわかりやすいです。

(1) $A_1<A_3$ の場合：$A_2$ は $A_1$, $A_3$ の真ん中になって欲しいので、$A_2$ が $(A_1+A_3)/2$ より小さいか大きいかで扱いが変わります。

(1-i) $A_2<(A_1+A_3)/2$ の場合：$A_2$ に $(A_1+A_3)/2-A_2$ を加えれば $A=(A_1.A_2,A_3)$ は等差数列になります。しかし、$A_1+A_3$ が奇数の場合には値が整数にならないので、あらかじめ $A_1$ (または $A_3$) に $1$ を加える必要があります。つまり、$A_1+A_3$ が偶数なら $(A_1+A_3)/2-A_2$、奇数なら $1+(A_1+A_3+1)/2-A_2$ 回の操作が必要です。

(1-ii) $A_2=(A_1+A_3)/2$ の場合：既に $A=(A_1.A_2,A_3)$ は等差数列になっているので、操作の必要はありません。

(i-iii) $(A_1+A_3)/2 < A_2$ の場合：$A_3$ を操作した値 $A_3'$ に対して $(A_1,A_2,A_3')$ が等差数列になったとすると、$A_3'=A_2+(A_2-A_1)$ となるので、$A_3$ に $A_2+(A_2-A_1)-A_3$ を加えれば良いことがわかります。

(2) $A_1=A_3$ の場合

(2-i) $A_2<A_1=A_3$ の場合：$A_2$ に $A_1-A_2$ を加えます。

(2-ii) $A_2=A_1=A_3$ の場合：既に $A=(A_1.A_2,A_3)$ は等差数列になっているので、操作の必要はありません。

(2-iii) $A_1=A_3<A_2$ の場合：$A_3$ に $2(A_2-A_1)$ を加えます。

(3) $A_1>A_3$ の場合：$A_1$ と $A_3$ の値を入れ替えることで、(1) の場合になります。

(1-i), (1-ii), (1-iii) に $A_1=A_3$ を代入すると (2-i), (2-ii), (2-iii) と同じ結果が得られるので、(1) と (2) の場合分けは不要です。

以上をまとめると、以下のコードとなります。

arc123a-1.cpp

#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int64_t a1, a2, a3;
  cin >> a1 >> a2 >> a3;
 
  if ( a1>a3 ) {
    swap(a1,a3);
  }
   
  if ( a2<(a1+a3)/2 ) {
    if ( (a1+a3)%2==1 ) {
      cout << 1+(a1+a3+1)/2-a2 << endl;
    } else {
      cout << (a1+a3)/2-a2 << endl;
    }
  } else if ( a2==(a1+a3)/2 ) {
    cout << 0 << endl;
  } else {
    cout << a2+(a2-a1)-a3 << endl;
  }
}

回答2 (AC)

回答1のコードに少し手を入れていきます。まず、a1 と a3 は必ずペアで登場していて、和 a1+a3 の値しか使っていないので、a1, a3 の大小関係は気にする必要はなく、swap に必要はありません。

次に (1-i) に $A_2=(A_1+A_3)/2$ を代入すると (1-ii) と同じ結果になるので、(1-i) は a2<=(a1+a3)/2 の場合としてまとめることが可能です。

さらに (1-i) の2種類の出力は、e=(a1+a3)%2 という変数を導入することで、e+(a1+a3+e)/2-a2 とまとめることもできます。

これらの考察を用いたコードは以下のようになりました。残った2種類の出力値は本質的に異なる値なので、これ以上の改良は難しそうです。

arc123b-2.cpp

#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int64_t a1, a2, a3;
  cin >> a1 >> a2 >> a3;
 
  if ( 2*a2<=a1+a3 ) {
    int e = (a1+a3)%2;
    cout << e+(a1+a3+e)/2-a2 << endl;
  } else {
    cout << 2*a2-(a1+a3) << endl;
  }
}

このように説明すると、回答1のような場合分けが必須なように思えてしまいます。しかし、等差数列の定義式を変形すると $2A_2=A_1+A_3$ になることに気づけば、左辺と右辺の大小関係が大きな意味を持つことがわかるので、回答1のような場合分けを経由せずに、回答2のようなコードにたどり着くことが出来ます。

調べたこと

AtCoder の解説 → 公式解説

$A_1, A_2, A_3$ の3変数問題から $X=2A_2-A_1-A_3$ に関する制約問題に帰着させていました。ここまでシンプルにできるのは驚きました。

リンク

• 前の記事 → AtCoderログ：0029 - ABC 072 B
• 次の記事 → AtCoderログ：0031 - ABC 053 B