AtCoder ARC123 個人的メモ

1 min read

A - Arithmetic Sequence

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

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

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

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

  • 右辺 = 左辺
    既に等差数列なので答えは0
  • 右辺 > 左辺
    左辺が右辺と等しくなるようにaかcに加算すればおk
  • 右辺 < 左辺
    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_iBの要素B_jCの要素C_kを考える。
A_i<B_j<C_kとなる要素がある時、B_jC_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)

Discussion

ログインするとコメントできます