Codeforces Round #312 (Div.2)

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

A. Lala Land and Apple Trees

ざっくりと大意

・n本のリンゴの木が\(x_i\)の位置にあり\(a_i\)の実がついている。
・0の地点から左右どちらかの向きに出発してリンゴを手に入れたら反転する。
・移動する方向によってはその先にはもうリンゴがなく獲得が終わる場合もある。
・最大で獲得できるリンゴはいくつか。

方針のようなもの

・左出発と右出発を試す。

python

n=int(raw_input())
l,r=[],[]
ans=chk=0
while n:
    n-=1
    x,a=map(int,raw_input().split())
    if x<0:
        l.append((-x,a))
    else:
        r.append((x,a))
l.sort()
r.sort()
def apple(p,q):
    s=d=0
    while 1:
        try:
            if d%2:
                s+=p[d/2][1]
            else:
                s+=q[d/2][1]
        except IndexError:
            break
        d+=1
    return s

print max(apple(l,r),apple(r,l))

解き直してみたけどリアタイで参加時と書いていることは殆ど変わらず。参加時の方が1回でACで優秀だったけど。。 移動回数ごとにdを1加算して%2の余りで移動している方向を決め、d/2番目の木を見ていれば端数が切り捨てられて左右どちらの木も順々に１つずつ見ていける。

B. Amr and The Large Array

ざっくりと大意

・大きさnの配列が嫌なので小さくしたい。
・出現回数が最大でかつ出現位置の幅が狭いものがよい。

方針のようなもの

・出現回数と出現位置を全部見る。

python

n=int(raw_input())
l=map(int,raw_input().split())
chk={}
for i,j in enumerate(l):
    if chk.has_key(j):
        chk[j][1]=i+1
        chk[j][2]+=1
    else:
        chk[j]=[i+1,i+1,1]
s=e=k=0
for i in chk:
    tmp=chk[i]
    if tmp[2]>k or (tmp[2]==k and e-s>tmp[1]-tmp[0]):
        s=tmp[0]
        e=tmp[1]
        k=tmp[2]
print s,e

コンテスト当時はcountで出現回数をみててTLE。。。そりゃ10⁵個もあるような配列をcountで回数とかindexで出現位置見てたら時間足りなくなりますわ。。適当にindexやcount使うとTLEで連想配列とかで書き直すと解決する、というのはこの問題以外にも何度かあったはずなので同じミスをしないように注意する。