AtCoder ARC123 個人的メモ

A - Arithmetic Sequence

等差数列の差が0でも良いのかでめちゃくちゃ混乱してた。

$A=(a,b,c)$とする。
問題文の等差数列の式は以下のように変形できる。

$$\begin{aligned} b-a&=c-b\\ 2b&=c-a \end{aligned}$$

両辺の大小で場合分けする。

• 右辺 = 左辺
  既に等差数列なので答えは0
• 右辺 > 左辺
  左辺が右辺と等しくなるようにaかcに加算すればおｋ
• 右辺 < 左辺
  bに加算するわけだが、bを+1すると右辺は+2される。
  よって、bが加算される回数は(左辺 - 右辺) / 2の切り上げとなる。
  (左辺-右辺)が奇数の場合はaかcに+1をして両辺を等しくする。

a, b, c = map(int, input().split())

left = 2 * b
right = a + c
if left == right:
    ans = 0
elif left > right:
    ans = left - right
else:
    ans = -(-(right - left) // 2) + (right - left) % 2

print(ans)

B - Increasing Triples

$A$の要素$A_i$、$B$の要素$B_j$、$C$の要素$C_k$を考える。
$A_i<B_j<C_k$となる要素がある時、$B_j$と$C_k$はそれぞれの数列内で最も小さい数にしたほうが良さそう。
というわけでそれを貪欲法で実装したら通った。

N = int(input())
A = sorted(map(int, input().split()), reverse=True)
B = sorted(map(int, input().split()), reverse=True)
C = sorted(map(int, input().split()), reverse=True)

ans = 0
while A:
    a = A.pop()
    b = 0
    while B and a >= b:
        b = B.pop()
    if not B and a >= b:
        break
    c = 0
    while C and b >= c:
        c = C.pop()
    if not C and b >= c:
        break
    ans += 1

print(ans)