問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0539解法 二分探索。 店の距離を小さい順にソートして宅配先がどこの店の間にあるかを二分探索して求める。 環状になっているので宅配先の距離が一番距離の大きい店より大きいなら、本店とど…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0556 解法 座標x,yを次のように変換する nx = min(x, N+1-x) ny = min(y, N+1-y) するとタイルの左上の4分の1の範囲だけで考えることができて、 場合分けしなくてよいので楽 あとは適当にmod…

問題 http://poj.org/problem?id=1990解法 x座標に関してBIT木を使っていろいろやる #include <cstdio> #include <algorithm> #define fst first #define snd second using namespace std; const int MAX_N = 20000; const int MAX_X = 20002; typedef pair<int,int> P; P cows[MAX_N]; i</int,int></algorithm></cstdio>…

スタンプの長さのとりうる値の範囲は 0[i-l+1, i]をスタンプで色j(それより前は何の色でもよい)で塗る, という条件で 塗る方法の数 というDPを思いついた。 あとは漸化式たてて解いて、最小となるLを見つけて計算する。 O(N^4)ぐらいだと思う #include <cstdio> #inc</cstdio>…

SRM 558 div2に参加しました easyは解けた med はDPで解けそうだなーと思いつつ実装間に合わなかった。 結果は 843 -> 879 (+36) 緑にあと2歩ぐらい届かず。 次こそ、緑になりたい。 #include <cstdio> #include <cstring> #include <string> #include <vector> #include <queue> #include <set> #include <algorithm></algorithm></set></queue></vector></string></cstring></cstdio>…

問題 http://poj.org/problem?id=2105解法 やるだけ ソースコードもっと短く綺麗にかきたい #include <cstdio> using namespace std; int main(){ int N; char c; char ip[33]; int ad[4]; scanf("%d", &N); for(int k=0;k</cstdio>

三角関数を使うだけ 出力形式を間違えていて、WA量産しまくった。 問題文をよく読もう(小学生並) #include <cstdio> #include <cmath> using namespace std; const double PI2 = 3.1415926535 * 2; int main(){ double x=0, y=0; double r = 0.0; int N; double d; while(sc</cmath></cstdio>…

解法 外接円は辺の垂直二等分線だから、適当に方程式作って解かせるだけ。 0で割り算しないように、分母が0になるときは適当な小さい値を足してしまえばいい #include <cstdio> #include <cmath> #include <algorithm> using namespace std; double jijo(double a){ return a*a; } int </algorithm></cmath></cstdio>…

SRM 557 div2に参加しました。 英語力がついていて、問題文をモリモリ読めた気がする。 あと、1つ撃墜できたのでよかった。 715 -> 843 (+128) はやく緑になりたい(小並感)easy250 #include <cstdio> #include <vector> #include <algorithm> using namespace std; class GreatFairyWar{</algorithm></vector></cstdio>…

問題 http://poj.org/problem?id=2719解法 4を抜かして数える は 4->5 5->6 6->7 7->8 8->9 と置き換えた9進数で数えることと同じと考える。 つまり、与えられた数の各位に4より大きい数があれば、その位の数から1を引き、できあがった数を9進数とみて10進数…

問題 http://poj.org/problem?id=2704解法 ゴールから逆にたどるように考えるといい。ゴールの方から道をみると下のような漸化式が成り立つ。a[i][j] := そのマスに書いてある数字 dp[i][j] := そこの場所からゴールまで行き方の総数dp[N-1][N-1] = 1 dp[i][…

POJ 2104 を http://www.graco.c.u-tokyo.ac.jp/icpc-challenge/index.php?2010%2F%C6%FC%C4%F8%C9%BD%2F01-17 のスライドを参考にして解こうとしたけどうまくできなかった コードの残骸だけ載せておく(一部分) void init(int d, int l, int r){ if(l == r-1…

解法 やるだけ #include <cstdio> #include <algorithm> using namespace std; const int MAX = 10; int a[MAX+4][MAX+4]; int lx[13]={-2,-1,-1,-1,0,0,0,0,0,1,1,1,2}; int ly[13]={0,-1,0,1,-2,-1,0,1,2,-1,0,1,0}; int mx[9]={-1,-1,-1,0,0,0,1,1,1}; int my[9]={-1,0,1,-1,</algorithm></cstdio>…

問題 http://poj.org/problem?id=2739 はじめ英語の問題文の解釈を間違っていて、 (連続していなくてもいいと思って動的計画法とか試していた) 1時間ぐらい無駄にしてしまった。解法 10000以下の素数の個数は P=1229個だから可能な連続した素数の和をすべて…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0114解法 (x,y,z) = (1,1,1) を {x' = a1*x mod m1 {y' = a2*y mod m2 {z' = a3*z mod m3 で計算していくと、再び(1,1,1)になるという条件から xだけでみたとき、xが再び1になるまでの計算回…

問題 http://poj.org/problem?id=2709 #include <cstdio> #include <algorithm> using namespace std; int main(){ int N; while(scanf("%d", &N), N!=0){ int p[N], g; for(int i=0;i<N; i++) scanf("%d", &p[i]); scanf("%d", &g); while(g > 0){ sort(p, p+N); p[0]++; p[1]++; p[2]++; g--; } sort(p,p+N); printf("%d\n"…</n;></algorithm></cstdio>

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2011解法 T日にスケジュールのあいている子孫の集合をCtとする 子孫cがT日に持っている地図の集合をMctとするMct = Mc(t-1) (c ∈ Ct でない) ∪{Md(t-1) | d ∈ Ct} (c ∈ Ct) を計算していって…