Testing Round #10

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

A. Forgotten Episode

ざっくりと大意

・n-1個の数列が与えられるので1からnまでの間で欠番になっているものを出力。

方針のようなもの

・探す。ただしinとかnot inは遅いのでダメ。

n=int(raw_input())
a=map(int,raw_input().split())
a.sort()
x=1
while 1:
    if a[x-1]!=x:
        print x
        break
    x+=1
    if x==n:
        print x
        break

コンテスト当時はnot inで探しててTLEしてた。aをソートして新しく変数を1ずつ加算して比較していけばnot inとか使う必要なかった。

B. Balancer

ざっくりと大意

・k本のマッチとn個のマッチ箱が並んでいる。
・全てのマッチ箱でマッチの本数が等しくなるように移動させる最小の移動本数はいくつか？？

方針のようなもの

・全て等しくなる本数=平均値を求めた後に左端から見ていく。

n=int(raw_input())
l=map(int,raw_input().split())
chk=0
for i in l:
    chk+=i
chk/=n
cnt=ans=0
for i in l:
    if i!=chk:
        cnt+=(i-chk)
    ans+=abs(cnt)
print ans

#include<iostream>
#include<cmath>
#include<string>
#include<cctype>
#include<vector>
#include<numeric>
#include<algorithm>
using namespace std;
/**
vector<int>ar(3);
for(auto&e:ar){
    scanf("%d",&e);
        }
sort(ar.begin(),ar.end())
int sum=accumulate(ar.begin(),ar.end(),0);
**/

int main(){
    double pai=3.141592653589;
    int n;
    long long s=0,av=0,cnt=0,ans=0;
    scanf("%d",&n);
    long long a[n];
    for(int i=0;i<n;i++){
        scanf("%I64d",&a[i]);
        s+=a[i];
    }
    av=s/n;
    for(int i=0;i<n;i++){
        if(a[i]!=av){
            cnt+=(a[i]-av);
        }
        if(cnt<0){
            ans+=(-1*cnt);
        }else{
            ans+=cnt;
        }
    }
    printf("%I64d\n",ans);
    return 0;
}

平均値との差分を積み重ねて計算しつつソレの絶対値を加算し続けて端まで見れば移動手数になる。多分。。