Zenn
📘

[python] ABC181 個人的メモ [Atcoder]

2020/11/01に公開
Python
競技プログラミング
AtCoder
tech

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点を通る1次関数の式を求める
その1次関数の式が3点目でも成立すればおｋ
選んだ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)

最初割り算をしたせいかwaした
多分，誤差がどうとかいう話だと思う

#!/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
下2桁が8の倍数かつ3桁目が偶数，下2桁が8の倍数-4かつ3桁目が奇数
この条件のいずれかを満たせばその数字は8の倍数
って考えて解こうと思ったら，こんがらがって実装しきれなかった

素直に下3桁で実装すればよかったらしい
コードは解説とほぼ一緒

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を昇順でソートしておく
各クエリで二分探索でW_iをHに挿入し，前から順にペアを組めば良い
それから合計を計算すればおｋ

でも，合計の計算を高速化する方法が分からなかった
累積和を使えばいいらしい

下図の様に2種類の方法でペアを組んだ時の身長差を累積和として計算しておく
これで，合計の計算はO(1)で済む
よって，各クエリでの計算量は挿入点を二分探索で探すO(\log N)となる
これなら間に合う

#!/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)

参考資料

Discussion