Codeforces Round #318 RussianCodeCup Thanks-Round (Div.2) - 君はまるで砂漠に咲く、一輪の花。

A. Bear and Elections

ざっくりと大意

・n人分の選挙の得票結果の数列aがある？
・a[1]のLimakを勝たせるようにa[2]からa[n]の人たちの票を最小の手数で調整する？？

方針のようなもの

・票調整をシミュレートする。

#heapq 使う場合
import heapq

n=int(raw_input())
a=map(int,raw_input().split())

x=a[0]
hq=[]
for i in a[1:]:
    heapq.heappush(hq,-i)
ans=0
while x<=abs(hq[0]):
    tmp=heapq.heappop(hq)
    tmp+=1
    x+=1
    ans+=1
    heapq.heappush(hq,tmp)
print ans

python

#heapq 使わない場合
n=int(raw_input())
a=map(int,raw_input().split())
x=a[0]
a=a[1:]
a.sort()
ans=0
while x<=a[-1]:
    x+=1
    ans+=1
    tmp=a.pop(-1)
    tmp-=1
    a.append(tmp)
    a.sort()
print ans

誤差程度だけどheapq使ったほうが遅かった。n=1000,a[1]=1で他全員が1000の場合に毎回ソートしたりとかTLEなるんじゃないかなーと勝手に思ってたら全然そんなこと無くて計算が終わるようだった。

B. Bear and Three Musketeers

ざっくりと大意

・n人の戦士がいてm件のa,bが知り合いであるという情報がある？
・この中で3人がそれぞれ互いに知り合いであり、かつ余計な3人以外の知り合いが最小であるものを探す？

方針のようなもの

・多分全部調べるしか無い気がするけどTLEが。。

C++11

#include<bits/stdc++.h>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<algorithm>
using namespace std;


int main(){
    int mof=1000000007;
    int n,m;
    int deg[5005];
    bool t[5005][5005];
    scanf("%d %d",&n,&m);
    for(int i=0;i<m;i++){
        int a,b;
        scanf("%d %d",&a,&b);
        t[a][b]=t[b][a]=true;
        deg[a]++;
        deg[b]++;
    }
    int res=mof;
    for(int i=1;i<=n;++i){
        for(int j=i;j<=n;++j){
            if(t[i][j]){
                for(int k=j+1;k<=n;++k){
                    if(t[i][k] && t[j][k]){
                        res=min(res,deg[i]+deg[j]+deg[k]);
                    }
                }
            }
        }
    }
    if(res==mof){
        printf("-1\n");
    }else{
        printf("%d\n",res-6);
    }
    return 0;
}

どうにも出来なかったのでtutorialの解答例パクった。C++11なら46msでTLEなんて全然意識する必要ないのに、似せてpython2で書くとさっぱりダメ。

python

# -*- TLE -*-
mod=1000000007


t=[[0]*5001 for i in range(5001)]
deg=[0]*5001
#n=int(raw_input())
n,m=map(int,raw_input().split())
M=range(m)
for i in M:
    a,b=map(int,raw_input().split())
    a-=1
    b-=1
    t[a][b]=1
    t[b][a]=1
    deg[a]+=1
    deg[b]+=1
res=mod
for i in range(n-2):
    for j in range(i+1,n-1):
        if t[i][j]:
            for k in range(j+1,n):
                if t[i][k] and t[j][k]:
                    res=min(res,deg[i]+deg[j]+deg[k])
print res-6 if res!=mod else -1

よくわからんので他のに進もう。。