二分法
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2317 二分探索。場合分けを冷静にしてオーバーフローに気をつける import std.stdio; import std.string; import std.conv; import std.algorithm; import std.range; import std.typecons; int a…
いまごろですがJOI本選に通過していました。 本選問3バウムクーヘンで配列を2倍にするところを、なぜか2乗の長さが必要だと思い込んでいて解けませんでした。 #include <cstdio> #include <algorithm> using namespace std; #define IDX(a,n,v) distance(a,lower_bound(a,a+n,v)</algorithm></cstdio>…
正方形の2つの頂点を決めてしまってから、残りの2頂点が存在するかを二分探索する #include <cstdio> #include <algorithm> using namespace std; #define X first #define Y second typedef pair<int, int> P; int N; P stars[1000]; int main(){ while(scanf("%d", &N) && N != 0){ int </int,></algorithm></cstdio>…
easyだけ解いた 二分探索してレベルを決定して、コーナーケースに気をつけながら表面積を計算する。 コーナーケースありすぎorz #include <cstdio> #include <algorithm> #include <vector> #include <string> using namespace std; typedef long long ll; class PyramidOfCubes{ public: ll k; </string></vector></algorithm></cstdio>…
問題 http://poj.org/problem?id=2456 解法 距離で二分探索。はじめ再帰で書いたが終了条件がよくわからなくてWAになったのでループ回した。 #include <cstdio> #include <algorithm> using namespace std; const int MAX_N = 100000; int N, C; int a[MAX_N]; bool c(int d){ /</algorithm></cstdio>…
SPOJを始めました問題 http://www.spoj.com/problems/ABCDEF/解法 式を ab + c = (f + e)d と変形すると二分探索が使える。右辺の値を決めて、左辺の値をにぶたんするとやりやすいと思う。 計算量は O(N^3 log (N^3) ) = O(N^3 log N) となる。 #include <cstdio> #i</cstdio>…
問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0539解法 二分探索。 店の距離を小さい順にソートして宅配先がどこの店の間にあるかを二分探索して求める。 環状になっているので宅配先の距離が一番距離の大きい店より大きいなら、本店とど…
問題 解法 は0点の的に当たったとしてあつかえばいい。n回目に投げたダーツの得点をPnとすると、 P1 + p2 + P3 + p4 が成り立つようにしなければならない。このまま計算すると、計算量は O(N^4) となりN ここで、式を変形して、 P3 + P4 これを計算する 2つ…
蟻本を参考にした。 二分法で解の存在する幅を狭めていく。 #include <cstdio> #include <algorithm> using namespace std; const int MAX_N = 10000; int N, K; double L[MAX_N]; bool c(double t){ int s = 0; for(int i = 0; i < N; i++){ s += (int)(L[i] / t); } return s </algorithm></cstdio>…
Haskellで2分探索をつかい入力された値の平方根を求めるプログラムを作ってみた。 EPSで精度を変えられる。 inf = 1000000000 eps = 0.0000001 main = getContents >>= putStrLn . show . root 0.0 inf . read root l h n = let ave = (l + h) / 2.0 in if (…
