[pythhon] AB181 개인 노트 [Atcoder]

ABC181

감상

abc3 완료
564표
다갈색으로 격하하다
요즘 고찰의 부족함을 실감할 기회가 많아서 뭔가를 하고 싶어요.

A - Heavy Rotation

#!/usr/bin/env python3
N = int(input())

print("White" if N % 2 == 0 else "Black")

B - Trapezoid Sum

합계 방정식 사용
0에서 B까지의 합에서 0에서 A까지의 합을 빼면 i차 작업의 정수의 합은 O(1)로 구한다.
처음에는 총화의 공식을 사용하지 않고 각 i에서

ans += sum(range(a, b + 1))

TLE를 만들었어요.
고찰이 너무 순진하다

#!/usr/bin/env python3
N = int(input())
ans = 0
for _ in range(N):
    a, b = map(int, input().split())
    ans += b * (b + 1) // 2 - a * (a - 1) // 2

print(ans)

C - Collinearity

combinations에서 3점을 선택하고 그 중 2점에서 연립방정식 2점을 통해 함수의 공식을 구한다
만약 이 함수의 공식이 세 번째로 성립된다면
선택한 3점의 좌표는 (x 1, y 1), (x 2, y 2), (x 3, y 3)로 설정합니다.
y_3=\frac{y_1-y_2}{x_1-x_2}x_3+y_1-\frac{y_1-y_2}{x_1-x_2}x_1
성립되면 됩니다.
그러나 제법에 오차가 생길 수 있기 때문에 공식을 약간 변형시켜 다음과 같은 공식을 사용했다
(y_3-y_1)(x_1-x_2)=(y_1-y_2)(x_3-x_1)
방금 계산한 결과가 허사가 되었다
아마 오차가 어떤 문제일 거예요.

#!/usr/bin/env python3
from itertools import combinations

N = int(input())
points = [list(map(int, input().split())) for _ in range(N)]

for a, b, c in combinations(points, 3):
    left = (c[1] - a[1]) * (a[0] - b[0])
    right = (a[1] - b[1]) * (c[0] - a[0])
    if left == right:
        print("Yes")
        exit()

print("No")

D - Hachi

wa
다음 두 자리는 8의 배수, 세 번째는 짝수, 다음 두 자리는 8의 배수 - 4, 세 번째는 홀수.
이 조건 중 하나를 충족시키면 그 숫자는 8의 배수이다
나는 이렇게 생각하니 알고 보니 한데 엉켜 실현되지 못했다
솔직하게 다음 세 분으로 이루어졌으면 좋겠습니다.
코드와 해설은 거의 같다

from collections import Counter

S = input()

if len(S) <= 2:
    if int(S) % 8 == 0 or int(S[::-1]) % 8 == 0:
        print("Yes")
        exit()
    print("No")
else:
    cnt = Counter(S)
    for n in range(112, 1000, 8):
        if not Counter(str(n)) - cnt:
            print("Yes")
            exit()
    print("No")

E - Transformable Teacher

H를 오름차순으로 정렬하기
검색어당 2분 W 검색i를 H에 삽입하고 앞쪽부터 순서대로 조립하면 됩니다
그리고 합계를 계산하시면 됩니다.
그러나 나는 합계 계산 속도를 어떻게 높여야 할지 모르겠다
적화하면 될 것 같아요.
아래 그림에서 보듯이 두 가지 방법으로 조합할 때의 키 차이를 누적하고 계산한다
이렇게 합계 계산은 O(1)만 하면 된다
따라서 각 쿼리의 계산량은 O(\logN)로 삽입점에 대한 이분 검색을 통해 찾을 수 있다
이러면 늦지 않아요.

#!/usr/bin/env python3
from itertools import accumulate
from bisect import bisect

N, M = map(int, input().split())
H = sorted([int(x) for x in input().split()])
W = [int(x) for x in input().split()]

# 最初の項からペアを作っていく，最後の項が余る
cumsum1 = list(accumulate([0] + [H[i] - H[i - 1] for i in range(1, N, 2)]))
# 2つ目の項からペアを作っていく，最初の項が余る
cumsum2 = list(accumulate([0] + [H[i] - H[i - 1] for i in range(2, N, 2)]))

ans = 10 ** 18
for w in W:
    i = bisect(H, w)
    if i % 2:
        insert = abs(H[i - 1] - w)
    else:
        insert = abs(H[i] - w)
    res = cumsum1[i // 2] + insert + cumsum2[-1] - cumsum2[i // 2]
    ans = min(ans, res)

print(ans)

참고 자료

해설 - AtCoder Beginner Contest 181
https://atcoder.jp/contests/abc181/editorial

AtCoder ABC 181E-Transformable Teacher(녹색 500점)-가위바위보 경기의 전문 정진 기록
https://drken1215.hatenablog.com/entry/2020/11/02/021500