Codeforces Round #364 (Div. 2)

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

A. Cards

ざっくりと大意

・n枚のカードが有る(nは偶数)。2枚組を選んでいずれのペアも値の和が同じになるようにする。

Python2

n=int(raw_input())
l=map(int,raw_input().split())
d={}
ans=chk=0
chk=sum(l)/(n/2)
for a,i in enumerate(l):
    if i in d:
        d[i].append(a+1)
    else:
        d[i]=[a+1]
while 1:
    if len(d)==0:
        break
    for i in d:
        print d[i].pop(),
        print d[chk-i].pop()
        if len(d[i])==0:
            del d[i]
        if len(d)>0 and len(d[chk-i])==0:
            del d[chk-i]
        break

ペアの和が同じ値になるのは数列の平均値 * 2のはず。但し、平均値を出してから2倍にしようとすると切り捨てがあるので平均値 * 2では計算できない。。 処理は連想配列にして適当にforで1つ取り出してペアになる値をまた連想配列内から特定して〜〜で処理した。

B. Cells Not Under Attack

ざっくりと大意

・n * nの盤にm個のルークがある。\(m_i\)のルークが置かれた時にルークの可動範囲外のマスがいくつ残っているか？？

Python2

n,m=map(int,raw_input().split())
chk=n*n
h,w=set([]),set([])
hc=wc=0
for i in range(m):
    x,y=map(str,raw_input().split())
    if x not in w:
        w.add(x)
        wc+=1
        chk-=(n-hc)
    if y not in h:
        h.add(y)
        hc+=1
        chk-=(n-wc)
    print chk,

クエリのx,yでxが既に同じ軸になる位置にルークがないかを確認する。まだなければ横の長さnから既に置かれているルークと交差する分は重複になるので減らない。yも同等の処理をする。xの処理した後の情報でyを計算するのでルークを置く位置が二重に計算されることはない、はず。。 最初はなぜかリストを使ってしまって無駄にTLEした。。しばらくしてsetにすれば良いことに気づきAC。連想配列も試したけど処理時間は今回は変わらなかった。