roiti46's blog

主に競プロ問題の解説を載せてます

Atcoder Beginner Contest #016

オンタイムで参加してたけど、書くのを忘れていたので記事化。いちおう全問解けたけれど、最終問で2線分上にあるという条件をきちんとかけていなかったので時間がかかった。計算量的にはかなり楽な問題セットで全問pythonでOK。問題はこちら

A: 12月6日

月と日が与えられるので、月が日で割り切れるかどうか答える問題。

m,d = map(int,raw_input().split())
print "YES" if m%d == 0 else "NO"

B: A±B問題

A, B, C の3つが与えられる。A+B = C, A-B = C が成り立つかどうかを答える問題。

a,b,c = map(int,raw_input().split())
x,y = a+b,a-b
if   x == y == c: print "?"
elif x == c: print "+"
elif y == c: print "-"
else: print "!"

C: 友達の友達

n 人のそれぞれの友達リストが与えられる。それぞれの人の友達の友達の人数を答える問題。

ふつうはグラフを作ってやる問題のようだが、setを使えば簡単に答えを求めることができる。人 i の友達それぞれについてその友達をセット ff に加え、最終的にそこから人 i の友達を引いて、その長さ−1を答えれば良い (1を引くのは自分を除くため)。

n,m = map(int,raw_input().split())
friend = [[] for _ in range(n)]
pop = [0]*n
for roop in range(m):
    a,b = map(int,raw_input().split())
    a -= 1; b -= 1
    friend[a].append(b)
    friend[b].append(a)
for i in range(n):
    ff = set([])
    if len(friend[i]) == 0:
        print 0
        continue
    for j in friend[i]:
        ff |= set(friend[j])
    print len(ff-set(friend[i]))-1

D: 一刀両断

ある多角形と1つの線分が与えられる。その線分により多角形が何個に切断されるかを答える問題。線分の短点、線は多角形の頂点と重ならず、線分の短点は多角形外部にある。

サンプルを眺めていると解法が浮かんできた問題。ある領域が切り離されるとき、多角形の2点が線分と交点を持つことになる。ということで、多角形と線分の交点を数えて、それの2分の1+1を答えれば正解となる。交点がきちんと線分と多角形の線上にあることを確認しないと答えが合わないので注意。

def denomi(cx,cy,dx,dy):
    return (by-ay)*(dx-cx)-(bx-ax)*(dy-cy)
    
def getip(cx,cy,dx,dy):
    dn = denomi(cx,cy,dx,dy)*1.0
    x = ((cy*dx-cx*dy)*(bx-ax)-(ay*bx-ax*by)*(dx-cx))/dn
    y = ((cy*dx-cx*dy)*(by-ay)-(ay*bx-ax*by)*(dy-cy))/dn
    return x,y
 
def ison(x,y):
    if min(cx,dx) <= x <= max(cx,dx) and min(cy,dy) <= y <= max(cy,dy):
            if min(ax,bx) <= x <= max(ax,bx) and min(ay,by) <= y <= max(ay,by):
                return True
    return False
    
ax,ay,bx,by = map(int,raw_input().split())
n = int(raw_input())
xy = [map(int,raw_input().split()) for _ in range(n)]
num = 0
for c,d in zip(xy,xy[1:]+[xy[0]]):
    cx,cy = c
    dx,dy = d
    if denomi(cx,cy,dx,dy) != 0:
        x,y = getip(cx,cy,dx,dy)
        if ison(x,y):
            num += 1
print num/2+1