AtCoder Beginner Contest 181の感想

ABC181をコンテスト後に解いた。

AtCoder Beginner Contest 181 - AtCoder
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

A – Heavy Rotation

偶数か奇数か判定する。

n = int(input())

if n % 2 != 0:
    print('Black')
else:
    print('White')

B – Trapezoid Sum

等差数列の和の公式を使う。

n = int(input())

ans = 0
for _ in range(n):
    a, b = map(int, input().split())
    samples = b - a + 1
    ans += (a + b) * samples // 2

print(ans)

C – Collinearity

 2点間の傾きが一致していれば一直線上になる。

今思えば傾きの計算でゼロ除算が発生するかもしれないので、移項して掛け算に直したほうが楽。

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

for i in range(n):
    for j in range(i + 1, n):
        for k in range(j + 1, n):
            x1, y1 = xy[i]
            x2, y2 = xy[j]
            x3, y3 = xy[k]
            if y1 - y2 == 0 or y3 - y1 == 0:
                if y1 - y2 == y3 - y1:
                    print('Yes')
                    exit()
                else:
                    continue
            elif (x1 - x2) / (y1 - y2) == (x3 - x1) / (y3 - y1):
                print('Yes')
                exit()

print('No')

D – Hachi

S<10^5なので、総当たりしていると間に合わない。

8の倍数は下3桁が8で割れる性質があるので、Sに含まれる数字から3個選んだ時に8の倍数が出来るかどうか判定する問題に変わる。

Sに含まれる1〜9の数字が何個あるか判定し、最大で3個保持するような配列を作る。

数字9種類x最大3個=27で、27P3はO(10^4)なので順列を総当りしても間に合う。

from collections import Counter
from itertools import permutations

s = list(input())
s = Counter(s)

num = []
for key, val in s.most_common():
    for i in range(min(3, val)):
        num.append(int(key))

ans = False
for l in permutations(num, min(3, len(num))):
    keta = 1
    temp = 0
    for i in l:
        temp += keta * i
        keta *= 10
    if temp % 8 == 0:
        ans = True
        break

print('Yes') if ans else print('No')


コメント

タイトルとURLをコピーしました