Educational Codeforces Round 3 - 君はまるで砂漠に咲く、一輪の花。

A. USB Flash Drives

ざっくりと大意

・n個のUSBメモリの容量がそれぞれ\(a_i\)で、容量mのデータを保存するのに使用する最小のUSBメモリ個数はいくつか？

方針のようなもの

・nが最大で100のようなので何やっても大丈夫そう。

n=int(raw_input())
m=int(raw_input())
a=[]
for i in range(n):
    a.append(int(raw_input()))
a.sort()
ans=chk=0
for i,j in enumerate(a[::-1]):
    ans+=j
    if ans>=m:
        print i+1
        break

容量の大きい方から使えば大丈夫だと思う。

B. The Best Gift

ざっくりと大意

・a冊の本の中から違うジャンルの本を2冊選んでプレゼントするのに選び方は何通りあるか？
・サンプル1は1,2番目を選ぶのと1,4番目を選ぶのはジャンルは[2,1]で同じであるが違う本なのでプレゼントになる。だが2,4番目は違う本でも同じジャンルなのでプレゼントに出来ない。

方針のようなもの

・本の数が多いのであんまり適当だとダメ。

python

ans=chk=0
n,m=map(int,raw_input().split())
a=map(int,raw_input().split())
d={}
for i in a:
    if d.has_key(i):
        d[i]+=1
    else:
        d[i]=1
for i in d:
    for j in d:
        if i!=j:
            ans+=d[i]*d[j]
print ans/2

1度目は適当に全ペアを見たらTLEになった。仕方ないので連想配列に同じジャンルの本が何冊あるかをカウントしておいてから全組み合わせを計算した。ただしこれだと1,2番目を選ぶのと2,1番目を選ぶのを計上してしまうので最後に2で割って解にした。

C. Load Balancing

ざっくりと大意

・学校にはn台のサーバがある。それぞれのサーバは\(m_i\)のタスクを持っている。
・タスクの差を最小化して負荷のバランスをとる。
・1秒に1タスクを再割当てして、最短で何秒で割当が終るか。

方針のようなもの

・シミュレートは無理なので別の方法で計算する。

python

n=int(raw_input())
#n,k=map(int,raw_input().split())
l=map(int,raw_input().split())
chk=0
ans=[0,0]
chk=chk2=sum(l)/n
if sum(l)%n:
    chk2+=1
for i in l:
    if i<chk:
        ans[0]+=chk-i
    elif i>chk:
        ans[1]+=i-chk2
print max(ans)

aの平均値を整数で求める。但し割り切れない数の時は切り捨てと切り上げのを用意した。それで数列aを先頭からなめて平均値との差がタスク再割当てに必要な数なのですけど、これでなんでACなのか、本当に正しいのかは根拠なしです。