2021/02/06
Attack to a Tree
橙diff
木の2乗DPということは事前に知っている状態で解いた。
dp[i][j][k]:頂点iの部分木でj回切断を行った時のiと連結しているAの和の最小値(k=0の場合は全てのAが正)とした。遷移させた後に初期化が必要。
遷移元と遷移先が一致する場合が存在するので注意。
Circle Lattice Points
青diff
本番中に解けなかった。誤差が怖いので10000倍して整数で考える。
負の割り算は、正の値の時と同じ様に扱ってたらバグる時がある(例えばC++では(-12)/10=-1となる)。下のようにしたら頭に優しかった。
for(ll h=(y-r)-(y-r)%10000-man*2/*(余分にマイナス)*/;h<=y+r;h+=10000){
if(h<y-r) continue; //帳尻合わせ
ll tate=abs(y-h);
ll yoko=0,ng=1e15;
while(ng-yoko!=1){
ll mid=(yoko+ng)/2;
if(mid*mid+tate*tate<=r*r) yoko=mid;
else ng=mid;
}
ll up=(yoko+x)/man*man+man*2;/*(余分にプラス)*/
ll down=(x-yoko)/man*man-man*2;/*(余分にマイナス)*/
while(up>yoko+x) up-=man;//帳尻合わせ
while(down<x-yoko) down+=man;//帳尻合わせ
ret+=up/man-down/man+1;
}
その他
ABC191に参加してレート+6だった。Dが解けなかったの悔しい。
