http://poj.org/problem?id=3252 パスカルの三角形をあらかじめ計算しておく。 まず、((数字の桁数) - 1)桁以下の2進数についてRound Numberを求める。 これは、iを桁数、jを0の個数として iCj - (i-1)C(j-1) の和を計算すればよい。次に(数字の桁数)桁の2進…

いもす法をする [a,a]みたいな区間を忘れないようにする #include <cstdio> #include <algorithm> using namespace std; int s[1000002]; int single[1000002]; int main(){ int N; int mi = 1000002, ma = 0; scanf("%d", &N); for(int i = 0; i < N; i++){ int a, b; scanf("%</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>…

問題 http://poj.org/problem?id=1029解法 N枚のコインをそれぞれ偽のコインと仮定したとき矛盾が生じるかどうかで判定する 実装ですこしつまずいた #include <cstdio> #include <vector> #include <algorithm> using namespace std; const int MAX_N = 1000; int N, K; vector<vector<int> > L(100)</vector<int></algorithm></vector></cstdio>…

問題 http://poj.org/problem?id=2019解法 segment tree の二次元版みたいなやつを作ると各クエリに対してO(log N)で処理できる #include <cstdio> #include <algorithm> using namespace std; typedef pair<int, int> P; const int N_ = 256; const int TREE_SIZE = 87381; // A_1 = 0, A</int,></algorithm></cstdio>…

問題 http://poj.org/problem?id=2378 解法 適当な頂点を選んで根にしてDFSして子を数えてやるとできる。 #include <cstdio> #include <algorithm> #include <vector> using namespace std; int N; vector<int> T[10001]; vector<int> ans; int dfs(int p, int q){ int sum = 0; bool f = true; fo</int></int></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>…

問題 http://poj.org/problem?id=1989 (翻訳)K種類の整数N個からなる整数列が与えられるので、その部分列とならない整数列のうち最短のものの長さを答えろ。 解法 整数列の先頭から、K種類の整数が一通り出るところまで進み、さらにその場所からまたK種類の…

解法 二部グラフの最大マッチングとみなせるので最大流問題をとけばいい ford-fulkerson法が使える #include <cstdio> #include <algorithm> #include <vector> using namespace std; const int MAX_N = 200, MAX_M = 200; int N, M; class edge{ public: int to, cap, flow, rev; edge(</vector></algorithm></cstdio>…

問題 http://poj.org/problem?id=1226解法 全探索したら通った。最小の文字列を選んで計算回数を落としたが別に必要ないっぽい。 #include <cstdio> #include <algorithm> #include <string> #include <iostream> using namespace std; int t, n; int main(){ cin >> t; for(;t > 0; t--){ cin >> </iostream></string></algorithm></cstdio>…

解法 ソートして中央値を適当にとる よくわからない #include <cstdio> #include <algorithm> using namespace std; const int MAX_N = 10000; int X[MAX_N], Y[MAX_N]; int N; int main(){ scanf("%d", &N); for(int i = 0; i < N; i++) scanf("%d %d", &X[i], &Y[i]); sort(Y,</algorithm></cstdio>…

問題解法 最長増加部分列(LIS)をとけばよい spaghetti source みてLISをO(n log n)で解くアルゴリズムをみた #include <cstdio> #include <vector> #include <algorithm> using namespace std; const int INF = 1 << 29; const int MAX_P = 40000; int T, P; int a[MAX_P]; int solve_li</algorithm></vector></cstdio>…

問題解法 union-findを使う。 人数の2倍の大きさのUF木を作って、 「AとBが違う」を unite(a, b+N), unite(a + N, b) とする。 A,Bが同じ根を持つなら同じグループ、A,B+Nが同じ根を持つなら違うグループとなり どちらでもない場合は「まだ分からない」とな…

問題解法 Union-Find木を使って連結状態的なものを持っておく。 コンピュータpを修理したとき、他の修理されたコンピュータの中で距離d以内のものとuniteする 同じ根を持てば、通信可能である。 #include <cstdio> #include <algorithm> using namespace std; typedef pair<int, int> P; c</int,></algorithm></cstdio>…

問題 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>…

問題 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>

問題 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][…

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

問題 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://poj.org/problem?id=2707解法 ほとんどやるだけ 両方とも横長か縦長に揃えて考えるといい。 あとは場合分けを気をつける #include <cstdio> #include <algorithm> using namespace std; int x1, y1, x2, y2; void swap(int *a, int *b){ int t; t = *a; *a = *b; *b</algorithm></cstdio>…

http://poj.org/problem?id=1948自力で解けなかった。 なんか、頭いい方法でDPするらしい。 こんなループのまわし方はどうやったら思いつくのだろうか。 #include <cstdio> #include <math.h> #include <algorithm> using namespace std; const int M_N = 40; const int M_L = 40; int N</algorithm></math.h></cstdio>…

PCK参加しました。 bitDP気づいたけど実装力なさすぎでバグりまくったのが悔しい 本選参加できるかどうか微妙(地域枠) 今はコード手元にないから今度のせる(追記) コードはどっかいったPOJ 1936部分文字列かどうか判定する問題 再帰書くだけでよい solve(p, …

問題 http://poj.org/problem?id=1922 解法 途中で別の人に追い抜かれてからスピードあげるぐらいなら、 最初からその人でいいだろが、という話。 出発時間が負の人には追い抜かれることはないから無視して構わない。 #include <cstdio> using namespace std; int ma</cstdio>…

問題 http://poj.org/problem?id=1915 ナイトの動きで何手で目的地までいけるかを計算せよ解法 BFS 移動先座標を配列で持っておくのがコツ #include <cstdio> #include <algorithm> #include <queue> using namespace std; typedef pair<int,int> P; const int INF = 1 << 29; const int dx[8] =</int,int></queue></algorithm></cstdio>…

問題 解法 最小全域木をつくればいいからプリム法かクラスカル法をつかうといい 僕はプリム法を使いました。 #include <cstdio> #include <queue> #include <vector> #include <algorithm> using namespace std; const int MAX_N = 100; const int INF = 1 << 30; typedef pair<int, int> P; //(cost, v) </int,></algorithm></vector></queue></cstdio>…

問題 ISBNの隠れてしまった文字を求める問題解法 10通りか9通りくらい調べる #include <cstdio> int main(){ int sum = 0, posQ; char c; for(int i = 0; i < 10; i++){ scanf("%c", &c); if('0' <= c && c <= '9'){ sum += (c - '0') * (10 - i); }else if(c == 'X'</cstdio>…

http://poj.org/problem?id=2181 初め、DP ( O(P^2) ) しようとしたけどP( わからなくて結局写経した。 O(P)すげー。おもいつけるようになりたい↓TLE実装 #include <cstdio> #include <algorithm> using namespace std; const int MAX_N = 150000; int N; int a[MAX_N]; int sol</algorithm></cstdio>…

問題 http://poj.org/problem?id=2390解法 単純な複利計算 やるだけ #include <cstdio> using namespace std; int main(){ int R, M, Y; double r, sum; scanf("%d %d %d", &R, &M, &Y); sum = (double)M; r = 1.0 + (double)R / 100.0; for(int i = 0; i < Y; i++){</cstdio>…

問題 http://poj.org/problem?id=3264解法 SegmentTree で RMQ みたいなことをする。 自力でせぐつりーを実装できるようになった。 #include <cstdio> #include <algorithm> using namespace std; const int INF = 1 << 29; int n, a[100001 * 2], b[100001 * 2], q; // a:最大</algorithm></cstdio>…