Codeforces Round #312 (Div.2) 参加記

はい。 ox--x (0/0) 1332(-74) http://codeforces.com/contest/558
またB問題がシステムテストでTLE落ちという無駄なミスを。。。

A. Lala Land and Apple Trees

ざっくりと大意

・開始位置は0の位置にいて座標が-105<=\(x_i\)<=105,\(x_i\)≠0の範囲で\(a_i\)のリンゴがある。
・正の方向に向かって移動してリンゴがあったら、それを手に入れて負の方向に移動する。負の方向に移動してリンゴを手に入れたら正の方向に移動する。
・リンゴは最大いくつ手に入るか。

方針のようなもの

・実際に移動を試してみる。

python

n=int(raw_input())
ans=chk=0
l,r=[],[]
for i in range(n):
    x,a=map(int,raw_input().split())
    if x<0:
        l.append((-x,a))
    else:
        r.append((x,a))
l.sort()
r.sort()

def sol(a,b):
    chk=cnt=0
    while 1:
        try:
            if chk%2==0:
                cnt+=a[chk/2][1]
            else:
                cnt+=b[chk/2][1]
        except IndexError:
            return cnt
        chk+=1


print max(sol(l,r),sol(r,l))

正の側と負の側のリンゴをソートしておいて、先に正の側と負の側のどちらを取りに行くほうが大きくなるかを比較すればいいっぽい。最近はリストの範囲外の対策をtry/exceptで拾うのが楽な気がしている。他の方法が出てくるまではしばらく試してみよう。

B. Amr and The Large Array

ざっくりと大意

・\(a_i\)の中で出現回数が最も多く、かつ最も狭い範囲の数のものの最初と最後の位置を出力する。

方針のようなもの

・出現回数や位置を全部確認する。

python

n=int(raw_input())
a=map(int,raw_input().split())
log={}
memo=0
chk=[]
for i,j in enumerate(a):
    if log.has_key(j):
        log[j][2]=i
    else:
        log[j]=[0,i,i]
    log[j][0]+=1

memo,l,r=0,0,10000000000
for i in log:
    if log[i][0]>memo:
        memo=log[i][0]
        l=log[i][1]
        r=log[i][2]
    elif log[i][0]==memo:
        if r-l>log[i][2]-log[i][1]:
            l=log[i][1]
            r=log[i][2]
print l+1,r+1

当初は出現回数が多いものを数と回数だけメモしておいて、最後にまた出現位置を調べるとか無駄すぎて酷かった。。aを先頭から見て連想配列で数をキーにして、出現回数,最初の出現位置, 最後の出現位置をメモをする。それが終わったら連想配列内の全てのキーと値を調べて出現回数が多く範囲の狭いものを出力という風にすれば間に合った。もったいない。。

E. A Simple Task

ざっくりと大意

・長さnの文字列Sに対してq回分のクエリi,j,kの処理をする。
・クエリはiからjの範囲の文字列をkが0なら降順に、1なら昇順にソートする。

方針のようなもの

・単純にクエリをpythonでリスト処理してたら間に合うはずがなかった。。
・また後で