2019/10/27

Codeforces 1247 D

a,xについての探索は間に合いそうにない

条件式の右辺がk乗なので素因数で議論をしたくなる

10^5個の数の約数列挙の計算量はO(N√N)!(は?)(O(N√(a^2)ですが...)

実験しているとあるaiに対するpairの素因数の個数に周期性があることが分かる

周期性がある→mod

素因数の個数をmodkで考えたとき、同じ数になるaは同一視できる

→組み合わせるべきpairが一意に定まるので各aに対してmapでカウントすればよい

 

天下一コン D - IntegerotS

最大値

bitの制約→桁DPのような見方をしたい

kの立っている各bitに対して、どのbitを0にして、そのbitより下位のbitを自由にするかを全探索 O(N*30)

 

ABC144 D - Water Bottle

幾何

多角形の面積→包除原理で面積を求めやすい図形の面積に帰着させる

 

ABC144 E - Gluttony

最小値

昇順と降順を組み合わせるのが最適であることは有名事実(だと思っている)

きれいに単調にならないので二分探索できないねとなっていた

条件をkになるかどうかでなくk以下になるかどうかにすれば二分探索できる

 

思考の筋道を整理するべき(一本道になっていない)