ABC016を解いてみた

A問題

　m%d が0かどうかで判断しました。

m, d = map(int, input().split())

if(m%d == 0):
    print("YES")
else:
    print("NO")

B問題

　4パターンに場合分けしてelse-if構文で実装しました。

a, b, c = map(int, input().split())

if(a+b == c and (a-b == c or b-a == c)):
    print("?")
elif(a+b == c):
    print("+")
elif(a-b == c or b-a == c):
    print("-")
else:
    print("!")

C問題

　グラフを2次元配列で書き、「友達の友達」を全探索しました。

n, m = map(int, input().split())
a = [0] * m
b = [0] * m
friend = [[0 for i in range(n)] for j in range(n)]

# iとjが友達ならfriend[i][j]=1
for i in range(m):
    a, b = map(int, input().split())
    friend[a-1][b-1] = 1
    friend[b-1][a-1] = 1

# jがiの友達の友達ならfriend[i][j] = 2
for i in range(n):
    for j in range(n):
        # iとjが友達ならjの友達を確認
        if friend[i][j] == 1:
            for k in range(n):
                # kがjの友達で、iの友達でなく、すでに友達の友達とカウントされておらず、kがi本人でなかったら
                if friend[j][k] == 1 and friend[i][k] == 0 and i != k:
                    friend[i][k] = 2

# friend[i][j] = 2 の人数を数えて出力
num = 0
for i in range(n):
    for j in range(n):
        if(friend[j][i] == 2):
            num += 1
    print(num)
    num = 0

D問題

　分断された板の数は、分断している線分の数を求める、つまり分断している線分と多角形の交点を数えることより求められる。線分の交差判定を使用して交点の数を数え、出力しました。

#線分((ax, ay)(bx, by))と((cx, cy)(dx, dy))の当たり判定
def lineIntersection(ax, ay, bz, by, cx, cy, dx, dy):
    ta = (cx - dx) * (ay - cy) + (cy - dy) * (cx - ax)
    tb = (cx - dx) * (by - cy) + (cy - dy) * (cx - bx)
    tc = (ax - bx) * (cy - ay) + (ay - by) * (ax - cx)
    td = (ax - bx) * (dy - ay) + (ay - by) * (ax - dx)

    return (tc*td < 0 and ta*tb < 0)

#入力
ax, ay, bx, by = map(int, input().split())
n = int(input())
x = [0] * n
y = [0] * n
for i in range(n):
    x[i], y[i] = map(int, input().split())

#線分交差してたら変数を+1
num = 0
for i in range(n-1):
    if(lineIntersection(ax, ay, bx, by, x[i], y[i], x[i+1], y[i+1])):
        num+=1

# 点n-1から0への線分との交差判定
if(lineIntersection(ax, ay, bx, by, x[n-1], y[n-1], x[0], y[0])): num+=1

# 交差している点/2 が分断している線分の数　それに1を加えた数が割れたあとの枚数
print(int(num/2)+1)

雑感

　時間はオーバーしてしまいましたが初めて4完できて嬉しいです。蟻本を読んで問題を見てDPなのかグラフなのか全探索なのか判断できるようになり、アルゴリズムが思い浮かぶようになりました。