naoya_t@hatenablog

いわゆるチラシノウラであります

Codeforces Round #448 (Div. 2)

http://codeforces.com/contest/895
agwたんお薦め問題を解きに来た
C→A→B

A - Pizza Separation

http://codeforces.com/contest/895/problem/A
連続区間総当り。高々360C2通り。
http://codeforces.com/contest/895/submission/32699458
→AC

B - XK Segments

http://codeforces.com/contest/895/problem/B
(i, j) のペアって i<j だけみたいな妄想制約を入れてて、a はソートされてないから a[i] より大きい数だけ拾うの面倒、とか最初思っちゃってた
いや、a
をソートするところから始めていい

ソート済みのa[] の、あるiについて、a[i] も含めてxの倍数がちょうどk個a[j]までとの間に含まれるような区間になる j を探すのは、a[j] がとりうる範囲を計算しておけばupper_bound() - lower_bound() 的な作業だからO(log N)で。
(x=1, k=0のとき、そのような j は存在しない)
http://codeforces.com/contest/895/submission/32700344

→WA

直した
http://codeforces.com/contest/895/submission/32700474
→WA
xとkの乗算が入ってオーバーフローするのを考慮に入れてないじゃん

直した
http://codeforces.com/contest/895/submission/32700508
→AC

C - Square Subsets

http://codeforces.com/contest/895/problem/C
agwたんおすすめ問題。

素因数分解したときにそれぞれの素数が偶数個になるように掛け合わせていく。
70までの素数って19個しかない
素因数分解して
a[i] を使う場合使わない場合と分岐していく数え上げをDPで。
http://codeforces.com/contest/895/submission/32699209
→WA
あ。XORじゃなくてORで計算してた。
1文字だけ、| を ^ に直して再提出
http://codeforces.com/contest/895/submission/32699243
→TLE
O(N * 2^19) では間に合わない。
a[] の値って高々70種類しかないから、それぞれがいくつずつあるかを数えておいて、二項係数を使ってまとめて数え上げるべし。
Σ nCk の同じ行を1個おきに足した和 = Σ(n-1)Ck の行の総和 = 2^(n-1) という関係を使う程度。
http://codeforces.com/contest/895/submission/32699356
→AC