・５００点問題
１直線上に質量の与えられた物質がN個置かれていて、さらにもう１つ置く時に、万有引力的につり合う位置はdoubleでN-1個返せって問題。

高校の物理とかで、問題が言ってることは理解できるんだけど、
フツーにやったら高次方程式になりそうで、プログラムで解き方が分からなくて断念。

→２分探索で解けるよと教えてもらったのでやってみた。

public class EquilibriumPoints { public double[] getPoints(int[] x, int[] m) { double[] p = new double[x.length-1]; for(int n=0; nglt;p.length; n++) { p[n] = getP(x, m, n, x[n], (x[n]+x[n+1])/2.0, x[n+1]); } return p; } private double getP(int[] x, int[] m, int n, double left, double p, double right) { double fLeft = 0.0d; double fRight = 0.0d; if(right-left < 0.0000000001) return p; for(int i=0; iglt;=n; i++) { fLeft += m[i]/(p-x[i])/(p-x[i]); } for(int i=n+1; iglt;x.length; i++) { fRight += m[i]/(x[i]-p)/(x[i]-p); } if(fLeft == fRight) { return p; } else if(fLeft > fRight) { return getP(x, m, n, p, (right+p)/2, right); } else { return getP(x, m, n, left, (left+p)/2, p); } }

まず、x[n]とx[n+1]の間に一個あるんだから、とりあえず真ん中をとって計算してみて、
左の方が大きければ求めたい点は右半分にあり・・・ってなって、
それを再帰でぐるぐるまわして行くと、範囲が半分の半分の半分の・・・ってなって最終的に誤差が1e-9になれば良くって、
誤差が1e-9ってめっちゃ精度高いように見えるけど、2^30が10^9くらいだから３０回くらいやれば答えは出て、１回のループが意外と思い計算じゃないのでタイムアウトにもならないみたい。


・１０００点問題
コンテスト終了力後に解き終わって、あとでシステムテストしてみたら通ってた涙

問題は、

	"###...#.###.###.#.#.###.###.###.###.###",
	"#.#...#...#...#.#.#.#...#.....#.#.#.#.#",
	"#.#...#.###.###.###.###.###...#.###.###",
	"#.#...#.#.....#...#...#.#.#...#.#.#...#",
	"###...#.###.###...#.###.###...#.###.###"

みたいな感じでデジタル表示で数字を表していて、いくつか電球が切れた（？）ものが与えられて、もともと表示していた可能性のある数字の平均を返す問題。

import java.util.ArrayList; public class FloorIndicator { private final char ON = '#'; private final char OFF = '.'; private final int[] NUMBER = {31599, 4681, 29671, 29647, 23497,31183,31215,29257,31727,31695}; public double averageFloor(int N, String[] indicator) { int light[] = split(N, indicator); double sum = 0; double p = 1; ArrayList[] candidates = new ArrayList[N]; for(int i=0; i<N; i++) { candidates[i] = include(light[i]); if(candidates[i].size() == 0) return -1.0; p *= candidates[i].size(); } for(int i=0; i<N; i++) { int temp = 0; for(int j=0; j<candidates[i].size(); j++) { temp += (Integer)candidates[i].get(j); } sum += p/candidates[i].size()*temp; sum *= 10; } sum /= 10; return sum/p; } private int[] split(int N, String[] indicator) { int[] light = new int[N]; for(int n=0; n<N; n++) { for(int y=0; y<5; y++) { for(int x=0; x<3; x++) { if(indicator[y].charAt(x+(n*4)) == ON) { light[n] += 1; } light[n] *= 2; } } light[n] /= 2; } return light; } }


とりあえず方針として、
String配列はややこしいので、１桁ずつのデジタル数字に直す。
切れた電球に何かを加えるともとの表示になるので、つまり、今すでに光っている部分を光らせない数字の補集合をとれば良い。
簡単にするのに光ってるのを1、消えてるのを0にして、
事前に用意した1とか2とかのとANDをとって、変化がなければおkってこと。