問題解法 最長増加部分列(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>…

2012年がもうすぐ終わるので振り返りを書きます。1月 蟻本でアルゴリズムを勉強する。 2月 JOI本選のことがツイッターでつぶやかれているのをみる。来年行きたいなーと思う。 3月 高校受験。やべぇ勉強全然していない。 →なぜか受かったのでよかった 4月 高…

問題解法 10^7回も散歩する太郎君の問題 解説みた。動的計画法を使う。 #include <cstdio> #include <algorithm> using namespace std; const int MAX_HW = 1000; int N, H, W; int a[MAX_HW + 2][MAX_HW + 2]; int dp[MAX_HW + 2][MAX_HW + 2]; int main(){ while(scanf("%d %d</algorithm></cstdio>…

解説みた。 最大値の伝搬を使った #include <cstdio> #include <algorithm> using namespace std; const int MAX_N = 5000; const int MAX_M = 500000; int N, M; short nail[MAX_N][MAX_N]; int main(){ scanf("%d %d", &N, &M); for(int i = 0; i < M; i++){ int a, b, x; sca</algorithm></cstdio>…

Bから新しい山を作るとき、下から取り除く分は考えずに、 上からn枚取り除いたときのことを考える。 この時できた新しい山とAとの最長の共通列？はO(N)で求まる。 よって全体としてはO(N^2)で計算できる。 #include <cstdio> #include <algorithm> using namespace std; const i</algorithm></cstdio>…

文字列を圧縮(文字の種類+その文字が何個あるかの情報に)する 圧縮した文字列にJOIがあったら、JOI列の条件を満たしているか確認してレベル計算 O(N) #include <cstdio> #include <cstring> #include <algorithm> using namespace std; char s[1000010]; char t[1000010]; int tn[1000010</algorithm></cstring></cstdio>…

84点Aランクで本選行きます。AOJのJOI本選過去問埋めをやっています

こどふぉ初参加でした ABCの3完 1516(青)だった。 codeforcesのルールがよく分からない。 1500以上だとdiv1?A 各行が黒白互い違いになっていればYES,そうでないならNO #include <cstdio> using namespace std; char a[8][8]; int main(){ char c; bool f = true; for</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>…

4完 + 部分点4点 = 84 だと思う。 1 #include <cstdio> #include <algorithm> using namespace std; int main(){ int l, a, b, c, d; scanf("%d %d %d %d %d", &l, &a, &b, &c, &d); printf("%d\n", l - max((a+c-1)/c, (b+d-1)/d)); return 0; } 2 #include <cstdio> #include <algorithm> using n</algorithm></cstdio></algorithm></cstdio>…

今日はJOI予選です。5完を目指します 問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0530解法 動的計画法をつかう 横の列の個数分の配列をとるとTLEしそう。 そこで、一つの行には石がたかだか10個しかないという制約を利用するとはやくな…

東京大学プログラミングコンテスト2012 に先週参加してました。 期末テストから解放されたので記事書きます。 A:100 B:100 C:50 F:0.52 合計 250.52 順位 66位 でした。 実力相応です。A #include <cstdio> #include <algorithm> using namespace std; int y, m, d; bool u[4]; </algorithm></cstdio>…