PythonでAtCorder255 (A〜C)｜タムタムのアウトプット

もう一週間前になりますが、AtCorder 255に参加しました。

A, Bしか解けませんでした・・・ Cは時間かければできそうな気はしたけど時間切れって感じです。

今回はいつもみてるQiitaにPythonの解説がなかったので、公式解説から自分でできるところまでやっていきます。

Contents

【A】You should output ARC, though this is ABC.
【B】 Light It Up
【C】±1 Operation 1
【D】±1 Operation 2
まとめ

【A】You should output ARC, though this is ABC.

提出したコードはこちら

R, C = map(int, input().split())
a11, a12 = map(int, input().split())
a21, a22 = map(int, input().split())

a = [[a11, a12], [a21, a22]]

print(a[R-1][C-1])

特に考えることはないと思います。

【B】 Light It Up

今回のB問題は難しく感じました。何とかPASSしましたが、一回目の提出では通りませんでしたし、解けるまで時間もかかりました。

提出したコードはこちら

N, K = map(int, input().split())
an = list(map(int, input().split()))
xy = [(input()) for _ in range(N)]  # ['0 0', '0 1', '1 2', '2 0']

import math

has_list = []
nothas_list = []

for i, v in enumerate(xy):
    if (i + 1) in an:
        has_list.append(v)
    else:
        nothas_list.append(v)

# print(has_list)
# print(nothas_list)

r_list = []
for nothas in nothas_list:
    r = math.inf
    # print('""""""""""""')
    for has in has_list:
        has_x, has_y = map(int, has.split())
        nothas_x, nothas_y = map(int, nothas.split())

        r_tmp = math.sqrt((has_x - nothas_x) ** 2 + (has_y - nothas_y) ** 2)
        # print(r_tmp)
        r = min(r, r_tmp)
    r_list.append(r)
# print(r_list)

print(max(r_list))

本番では解くことしか考えていなかったのですが、今見ると計算量的によく通ったなと思います。最初のfor文で、計算量はO(10^8)。次の多重ループでもO(10^8)。全体でO(2 * 10^8)でTLEになりそうですが。。。

計算量の計算の仕方が間違っているのでしょうか？いまいち良くわかっていないです。

【C】±1 Operation 1

できませんでした。

途中まで考えていたコードはこちら

# X, A, D, N = map(int, input().split())


def solution(X, A, D, N):
    ans = 0
    if D == 0:
        ans = abs(X - A)
    else:
        last = A + D * (N - 1)

        # Case: X out S
        if D > 0:
            if X >= last:
                ans = X - last
            if X <= A:
                ans = A - X
            return ans
        if D < 0:
            if X >= A:
                ans = X - A
            if X <= last:
                ans = last - X
            return ans

        # Case: X in S
        base = abs((X - A) // D)  # Xはbase+1個目 と base+2個目の間の数字
        before = A + D * (base)
        after = A + D * (base + 1)
        if D > 0:
            ans = min(X - before, after - X)
        else:
            ans = min(X - after, before - X)

    return ans


# print(solution(X, A, D, N))
# print(solution(0, 0, 0, 1))  # 0
# print(solution(6, 2, 3, 3))  # 2
# print(solution(5, 1, 1, 2))  # 3
# print(solution(998244353, -10, -20, 30))  # 998244363
print(solution(-555555555555555555,-1000000000000000000,1000000,1000000000000))

場合分けの考え方で、どうにかやろうとしていますが、収集つかなくなっていますね。。。

公式の解説にある

S には 0≤k≤N−1 なる全ての整数 k に対して、 A+kD が含まれ、さらに A≤X≤A+(N−1)D が成立するため、答えは min((X−A)%D,D−(X−A)%D) です。

ということに問題解いている時は気がつきませんでした。実際の両端の値を出してその差分を求めようとして、分けがわからないことに。

解説を見て書き直したコードはこちら。

def get_s_min_max(A, N, D):
    if D < 0:
        s_min = A + (N - 1) * D
        s_max = A
    else:
        s_min = A
        s_max = A + (N - 1) * D
    return s_min, s_max


def solution(X, A, D, N):
    """ 場合分けで解く """
    if D == 0:
        ans = abs(X - A)
    else:
        s_min, s_max = get_s_min_max(A, N, D)
        if X > s_max:
            ans = X - s_max
        elif X < s_min:
            ans = s_min - X
        else:  # Case: X in S
            ans1 = (X - A) % D
            ans2 = D - ans1
            ans = min(abs(ans1), abs(ans2))

    return abs(ans)


X, A, D, N = map(int, input().split())
print(solution(X, A, D, N))

# assert solution(0, 0, 0, 1) == 0  # case D=0
# assert solution(100, 10, 0, 1000) == 90  # case D=0
# assert solution(6, 2, 3, 3) == 1
# assert solution(5, 1, 1, 2) == 3  # case X > s_max
# assert solution(998244353, -10, -20, 30) == 998244363  # case X > s_max
# assert solution(-555555555555555555, -1000000000000000000, 1000000, 1000000000000) == 444445