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

レート上がらない… easyしか分からなかった medは制約の読み間違えというクズいことをして、全探索するだけなのに気づかなかった。 気づけたとしても実装重めなので、できなかったかもしれない（小並感）250 #include <cstdio> #include <iostream> #include <cstring> #include <string> #inclu</string></cstring></iostream></cstdio>…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0536解法 やるだけ問題なんだけど実装キツい カードの数字なんて気にしなくてよいので、最初に、r以下のカードを白い碁石、rよりおおきいカードを黒い碁石にでも置き換えると、ちょっと実装…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0123解法 やらないだけ #include <cstdio> #include <algorithm> using namespace std; const double t500[7] = { 35.50,37.50,40.00,43.00,50.00,55.00,70.00 }; const double t1000[7] = { 71.00,77.00,83.00,</algorithm></cstdio>…

明日、PCK本選です。 がんばります!問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0223解法 地道に幅優先探索する。 #include <cstdio> #include <algorithm> #include <queue> #include <vector> using namespace std; typedef pair<int,int> P; typedef pair<int , pair<P, P> > T; const int INF = 1 </int></int,int></vector></queue></algorithm></cstdio>…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0124解法 ソートするだけ ”勝ち点が同点の場合は入力順に出力してください。”を読み間違えて1WA 入力順を記録するための値をpairに持つと便利 #include <string> #include <iostream> #include <algorithm> using namespac</algorithm></iostream></string>…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0557解法 動的計画法 状態は [i][j] = i番目の数字までを使ってjを作る+-の入れ方の総数 とした。 #include <cstdio> #include <algorithm> using namespace std; typedef long long ll; int a[101]; ll dp[101]</algorithm></cstdio>…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0547解法 動的計画法。 #include <cstdio> #include <algorithm> using namespace std; const int MOD = 100000; typedef pair<int, int> P; typedef pair<P, P> PP; PP dp[101][101]; int main(){ int h, w; for(int i=0; i < 1</p,></int,></algorithm></cstdio>…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0538解法 動的計画法を使う。 Oの数を数えることを意識して、 a[i] = if(s[i-1]=='I' && s[i]=='O' && s[i+1] == 'I') a[i-2] + 1 else 0 という漸化式を作り、aの中に何個N以上の数があるか…

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