AtCoder Regular Contest 094: C - Same Integers

solution

貪欲。$O(1)$で書ける。

$A \le B \le C$と仮定する。 $2$種類の操作は共に$A, B, C$を減少させることはなくまた$A + B + C$を$2$増やす。 操作の開始前の$C = C_0$を使って$A = B = C = C_0$が達成できればそれが答えであり、それができないなら$A = B = C = C_0 + 1$の場合が答え。 まず$A + 2, B + 2 \le C$の間$A, B$に$2$加える。 その後$A \le B \le C$であるように取り直すと$A = B = C = C_0$または$A = C_0 - 1 \land B = C = C_0$または$A = B = C_0 - 1 \land C = C_0$である。 $A = C_0 - 1 \land B = C = C_0$の場合に$A = B = C = C_0$が達成不能なのは$A + B$の偶奇から言える。 よってこの貪欲は妥当。

note

• 未証明のまま貪欲を投げました

implementation

#!/usr/bin/env python3
a, b, c = map(int, input().split())
answer = 0
while not (a == b == c):
    a, b, c = sorted([ a, b, c ])
    if a + 2 <= c:
        a += 2
    else:
        a += 1
        b += 1
    answer += 1
print(answer)