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

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

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

Codeforces Round #215 (Div. 2)

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

A. Sereja and Coat Rack

ざっくりと大意

・Serejaはn人入れるレストランを経営していて、衣紋掛けもn人分用意している。
・衣紋掛けは使用料\(a_i\)で提供していてお客様はお安い方からご利用される。
・お客様m人ご利用でキャパオーバーの時には1人ずつにペナルティd支払って、収支結果はいくらか。

方針のようなもの

・aはソートして利用人数分の和を出す。キャパオーバーしたらaの総和からペナルティ分を引く。

n,d=map(int,raw_input().split())
a=map(int,raw_input().split())
m=input()
a.sort()
if n>=m:
    print sum(a[:m])
else:
    print sum(a)-(m-n)*d

B. Sereja and Suffixes

ざっくりと大意

・n個の横に並んだ\(a_i\)の数列と、m個の縦に並んだ\(l_i\)の数列。
・配列aの\(l_i\)番目から末尾まで何種類の数があるか知りたい。

方針のようなもの

・末尾を起点でsetに放り込んで行って今何種類あるかを元の配列aを上書きしていく。

import sys
n,m=map(int,raw_input().split())
a=sys.stdin.readline().split()
chk=0
sute=set()
for i in range(-1,-n-1,-1):
    if a[i] not in sute:
        sute.add(a[i])
        chk+=1
        a[i]=chk
    else:
        a[i]=chk
for i in range(m):
    x=input()
    print a[x-1]

使い捨ての今まで出てる数字を放り込んでるのをlistに入れてた間はTLE取れなかったがset方にしたら1000ms制限でTLEだったのが、764msで通った。