読者です 読者をやめる 読者になる 読者になる

AtCoder Beginner Contest #016

はい。 oooo 140位
初全完だった。まぁ私でも出来る程度に難易度低めだったので全完の人は一杯いらっしゃるんですけどね!!
http://abc016.contest.atcoder.jp/

A - 12月6日

ざっくりと大意

・日付が与えられるので月が日で割り切れるかを判定する。

方針のようなもの

・剰余を見れば良いと思う。

n,k=map(int,raw_input().split())
print 'NO' if n%k else 'YES'

別にどうしても1文字でも少なくする必要ないし print 'YES' if n%k==0 else 'NO' の方が色々といいと思う。他言語にも手を伸ばした時に全ての言語でn%kが0ではないときに真で実行されるわけでは無い気がするけどソースはない。

B - A±B Problem

ざっくりと大意

・高橋くんが書いたプログラムが A+B なのか、 A-B なのか、どちらの可能性もあるか、どちらでもないかを判定してください。

方針のようなもの

・丁寧に分類する。

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

+が成立の時に+2で-が成立の時に+1をして!,-,+,?から出力させるとかも出来たけど、自分が出来る確実な書き方で出した。

C - 友達の友達

ざっくりと大意

・友達関係が与えられるので、各ユーザの「友達の友達」の人数を求めてください。ただし、自分自身や友達は、「友達の友達」に含みません。

方針のようなもの

・自分の友達リストにいる人の友達リストを調べる。

n,m=map(int,raw_input().split())
ans=chk=0
l=[[i] for i in range(n+1)]
ans=[0]*(n+1)
for i in range(m):
    a,b=map(int,raw_input().split())
    l[a].append(b)
    l[b].append(a)
for i in range(1,n+1):
    chk=[]
    for j in range(1,n+1):
        if i!=j and j in l[i]:
            for k in l[j]:
                if k not in l[i] and k not in chk:
                    ans[i]+=1
                    chk.append(k)
for i in range(1,n+1):
    print ans[i]

無向グラフの問題だったらしい。ですけどまぁ特に工夫しなくて全部調べるだけで引っ掛けや時間制限で困ること無く入力が優しく設定されていると思う。for i in で友達をカウントする人を順々に出して、for j in と for k in で友達の友だち関係になっているかを調べる。一度カウントした人はメモしておかないと何度でもカウントして計算が合わなくなるのでそこだけ注意。

D - 一刀両断

ざっくりと大意

・空手チョップの軌道を表す線分と板の形を表す多角形が与えられるので、板がいくつに切断されたか求めてください。
・入力のルール、制限が凄い優しい。
・多角形の頂点は反時計回りの順で与えられる。(各頂点を結ぶ線が途切れないので多角形がドーナツ型にならないことが保証されていると思う)
・多角形の頂点は線分から0.1以上離れている。(おそらく誤差で誤答にならないようにしたのだと思う)
・線分の端点は多角形から0.1以上離れている。(おそらく誤差で誤答にならないようにしたのだと思う)
・線分の端点は多角形の外部にある。(交差した線分は必ず多角形を切断することが保証されていると思う)
・多角形の連続する3頂点が一直線上に並ぶことはない。(頂点座標といいつつ実は直線となっている箇所が無いことが保証されていると思う)
・あと計算方法によっては頂点座標を通過する場合は交差の判定をしない計算方法の人にも気を使って優しい制限に制限になってると思う。

方針のようなもの

・交差する辺の数を調べる。

ax,ay,bx,by=map(int,raw_input().split())
n=int(raw_input())
l=[]
ans=chk=0
for i in range(n):
    x,y=map(int,raw_input().split())
    l.append((x,y))
for i in range(n):
    a2x=l[i-1][0]
    a2y=l[i-1][1]
    b2x=l[i][0]
    b2y=l[i][1]
    if((ax-bx)*(a2y-ay)+(ay-by)*(ax-a2x))*((ax-bx)*(b2y-ay)+(ay-by)*(ax-b2x))<0:
        if((a2x-b2x)*(ay-a2y)+(a2y-b2y)*(a2x-ax))*((a2x-b2x)*(by-a2y)+(a2y-b2y)*(a2x-bx))<0:
            chk+=1
print chk/2+1

交差する辺の数を調べて2回交差するごとに形が1つ切断されるので、交差した回数を2で割って元々は多角形が1つあったので1を足すと全部でいくつになったかが求まる。