SRM349
Rate 1507->1548
- 250 幾何苦手と言ってもこれぐらいはできてもよかった.
- 500 どうみてもDP 429.78
- 1000 N個から赤球をk個,青玉をn-k個とってくるって,まんま超幾何分布ですよね,忘れてた.わかってても,解けたかどうかはべつだけど.
500の方が250よりも明らかに解きやすかった.250は2つの円が与えられた時に,その交点の個数を求めよという問題で場合分けとかごちゃごちゃ考えてたら普通に間違えた.なんとなく使え回せそうな気もするのでメモって置く.squareとか関数を作ってるのはlongにキャストするのがめんどかったから.
public class RadarFinder { /** * (x1,y1),(x2,y2)を中心にもつ半径r1,r2の2円があたえられたときにその交点の数を返す. * ただし,2つの円が一致するときは-1を返す. * @param x1 * @param y1 * @param r1 * @param x2 * @param y2 * @param r2 * @return 交点の数 */ public int possibleLocations(int x1, int y1, int r1, int x2, int y2, int r2) { long dist = norm(x1-x2,y1-y2); if(dist==0)return r1==r2?-1:0; long d2 = square(r1+r2); long d3 = square(r1-r2); if(dist==d2)return 1; if(dist==d3)return 1; return dist>d2 || dist<d3 ? 0:2; } long square(long x){ return x * x; } long norm(long x,long y){ return square(x) + square(y); } }