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

君はまるで砂漠に咲く、一輪の花。

僕はその花に引き寄せられる蝶。

Codeforces Round #341 (Div.2)

はい。
http://codeforces.com/contest/621

A. Wet Shark and Odd and Even

ざっくりと大意

・n個の数からいくつか選んで2で割り切れる最大のものになるようにする?

Python

n=int(raw_input())
o,e=[],[]
l=map(int,raw_input().split())
ans=chk=0
for i in l:
    if i%2:
        o.append(i)
        chk+=1
    else:
        ans+=i
o.sort()
print ans+sum(o) if chk%2==0 else ans+sum(o[1:])

いくつか選ぶ中で偶数は必ず選ぶ扱いにする。奇数は一旦は全て配列に格納して最後にソートする。奇数の件数が偶数ならば総和が偶数になる。件数が奇数ならば最小のものを取り除く。最後にすべて選んだ扱いの偶数と、件数を確認した奇数との総和が解になる。

B. Wet Shark and Bishops

ざっくりと大意

・1000 * 1000 のマスの中の座標が最大で200000件与えられる。
・それらの座標で対角線の位置関係にあるものの総数を出力。

Python

n=int(raw_input())
#n,k=map(int,raw_input().split())
l=[0]*1999
r=[0]*1999
memo=[0,0]
p=[1]
for i in range(1001):
    p=map(lambda x,y:x+y,[0]+p,p+[0])
    if i>0:
        memo.append(p[2])


for i in range(n):
    x,y=map(int,raw_input().split())
    l[x-y+999]+=1
    r[x+y-2]+=1
l=[i for i in l if i>1]
r=[i for i in r if i>1]
ans=chk=0
for i in l:
    ans+=memo[i]
for i in r:
    ans+=memo[i]
print ans

x+y と x-y で斜めで一直線上に並ぶものを分けられるのでそれらを保存していく。同一直線上に2点以上あるならばnC2で並んでいる点から2点選ぶ組み合わせの総和が解になるはず。