Codeforces All-Ukrainian School Olympiad in Informatics

Result

5時間コンテスト。

/ (3WA) / / 1:46 / 1:19
83位(no rated)

E. Points

問題

座標平面上にN個の点がある。
それぞれの点の座標x[i],y[i]が与えられる。
この時、異なる2点の距離の二乗の総和を求めよ。

N≦100000, x[i]は整数。

試行錯誤

まず、x座標ごと、y座標ごとに考えてよい。
でも、そのままやろうとするとO(n^2)でTLE.

式変形を試行錯誤してO(n)に落とせないか検討。
2S = ΣΣ(xi-xj)^2 = ΣΣ(xi^2 + xj^2 - 2xixj)
= Σ (Σxi^2 + Σxj^2 - 2xiΣxj )
= Σ ( sum^2 + sum^2 - 2xiΣxj )
= 2nsum^2 - 2ΣxiΣxj
なので、S = Σ(xi^2 - xi * sum)とすればよい。

ソースコード

int n;
ll solve(vi &x){
   sort(all(x));     
   ll ret=0, sum=0;
   rep(i,n)sum+=x[i];
       
   rep(i,n){
     ret+=(n-1ll)*x[i]*x[i];
     ret-=x[i]*(sum-x[i]);
   }     
   return ret;
}
void run()
{
   cin>>n;
   vi x,y;
   rep(i,n){
     int a,b; cin>>a>>b;
     x.pb(a); y.pb(b);
  }     
  cout<<solve(x)+solve(y)<<endl;
}

D. Plus and xor

問題

二つの整数A,Bが与えられる。このとき次の二整数X,Yを求めよ。
A = X+Y
B = X xor Y
0≦X,Y≦2^64 -1を満たす。

試行錯誤

A xor B xor B = Aであるから、A = X + (B xor X)と変形できる。
X + (B xor X)という式において、XにBで元々立っているビットを立てると、
和は変化しない。（B xor Xにおいてそのビットが0になってしまうため)

したがって、Bに立っていないビットのみを立ててX+(B xor X) = Aを成り立たせる必要がある。
すなわち、X + (B xor X) = B + 2Xになるため、X = (A-B)/2が必要。
あとはこれに対して適切なYが存在するかを見ればよい。

ソースコード

typedef unsigned long long ll;
void run()
{
        ll a,b; cin>>a>>b;
        if(b>a)swap(a,b);
       
        ll x=(a-b)/2,y=a-x;
        if(a>=x&&((x^y)==b))cout<<x<<" "<<y<<endl;
        else cout<<-1<<endl;
}

B.

しばらく考えたけど問題読み違えていた等して気力が尽きる。
後で復習……できたらいいなあ。