スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

All-Ukrainian School Olympiad in Informatics

2011/04/12 21:00 ~ 23:30 (JST)
Codeforces で開催された All-Ukrainian School Olympiad in Informatics の参加記録

Tags : プログラミング Codeforces 未解決

結果

A. -
B. -
C. -
D. 2WA, AC
E. WA, AC
F. -
Standing : 87/651
Unrated


問題

問題セットの原文はここを参照。

A.

B.

C.

D. Plus and xor
非負整数 A, B に対して、
・ A = X + Y
・ B = X xor Y
をみたす非負整数 X, Y のうち、X が最小になるものを求めよ。
そのような X, Y がない場合はそれを報告せよ。

E. Points
平面上のN 個の点 (xi, yi) が与えられる。
∑∑i<j { (xi - xj)2 + (yi - yj)2 }
を求めよ。

1 ≦ N ≦ 100000

F.

解答

言語は C++。テンプレはここを参照。

A.



B.



C.



D.
int main(){
ull A,B; cin>>A>>B;
ull X=0;
bool carry=false;
for(int i=63;i>=0;i--){
bool flg;
if(B&(1ULL<<i)){
if(!carry && (A&(1ULL<<i))==0){
carry=true;
break;
}
flg=false;
}
else{
if(A&(1ULL<<i)){
if(carry) flg=true;
else flg=false,carry=true;
}
else{
if(carry) flg=true,carry=false;
else flg=false;
}
}
if(flg) X|=1ULL<<i;
}
if(carry) cout<<-1<<endl;
else cout<<X<<' '<<A-X<<endl;

return 0;
}

B = X xor Y ⇔ Y = B xor X
だから
A = X + (B xor X).
これを使って、X の値を最上位ビットから順に決めていった。

i ビット目を決めるのには、i+1 ビット目への繰り上げが必要かがわかればいい。
i ビット目が 0 でも 1 でもいいときは 0 を選ぶようにした。( greedy に小さいものを選んでいることになる

E.
int main(){
int n; cin>>n;
ll x[100000],y[100000];
ll xsum=0,ysum=0;
rep(i,n){
cin>>x[i]>>y[i];
xsum+=(n-1)*x[i]*x[i];
ysum+=(n-1)*y[i]*y[i];
}

ll xtmp=x[n-1],ytmp=y[n-1];
for(int i=n-2;i>=0;i--){
xsum-=2*x[i]*xtmp;
xtmp+=x[i];
ysum-=2*y[i]*ytmp;
ytmp+=y[i];
}

cout<<xsum+ysum<<endl;

return 0;
}

x と y は独立に計算できるので、x についてだけ考える。
∑の範囲が省略されているものは 1 から n までの意味。
∑∑i<j ( xi - xj )2
= ∑∑i<j ( xi2 - 2 xi xj + xj2 )
= ∑∑i<j ( xi2 + xj2 ) - 2 ∑∑i<j xi xj
= (n-1) ∑ xi2 - 2 ∑∑i<j xi xj

最右辺第 2 項は
∑∑i<j xi xj
= x1 ( x2 + x3 + x4 + ... + xn )
+ x2 ( x3 + x4 + ... + xn )
+ x3 ( x4 + ... + xn )
+ ...
+ xn-1 xn

と変形すれば、うまく計算を再利用できることがわかる。
全体で O(n).

F.



感想

全体的に難しかった。
B. くらいの難易度の問題が解けたらよかったのだが、まだ実力不足だった。

D.
驚きの O(1) 解法があった。

E.
問題を読んだ直後は FFT で O(nlogn) かなと思っていたけど、式変形してたらさくっとできた。
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

Author : fura2
数学・コンピュータを中心に、考えたこと・やったことを書いていきます。

誤植等を含め、間違いはご指摘いただければ幸いです。

FC2カウンター
検索フォーム
最新記事
最新コメント
最新トラックバック
月別アーカイブ
リンク
RSSリンクの表示
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。