2015-12-01から1ヶ月間の記事一覧
問題 http://codeforces.com/contest/611/problem/Ccodeforces.com 解法 2次元の累積和。kenkoooo.hatenablog.com コード #include <cstdio> #include <iostream> #include <sstream> #include <fstream> #include <iomanip> #include <algorithm> #include <cmath> #include <string> #include <vector> #include <list> #include </list></vector></string></cmath></algorithm></iomanip></fstream></sstream></iostream></cstdio>
問題 codeforces.com 解法 y座標について Fenwick Tree を作りたいので、y 座標を座標圧縮する。 xを小さい方から順に見ていく。 xで始まる水平方向の区間があれば、それをBITに保存する。 x上にある垂直方向の区間を全て足し合わせる。ただし、水平方向と重…
問題 Range Sum Query | Aizu Online Judge 解法 Binary Indexed Tree (Fenwick Tree) ライブラリ確認用 コード #include <cstdio> #include <iostream> #include <sstream> #include <fstream> #include <iterator> #include <iomanip> #include <algorithm> #include <cmath> #include <string> #include <vector> #include <list> #incl…</list></vector></string></cmath></algorithm></iomanip></iterator></fstream></sstream></iostream></cstdio>
問題 indeednow-finala-open.contest.atcoder.jp 解法 木DP。 コード #include <cstdio> #include <iostream> #include <sstream> #include <fstream> #include <iterator> #include <iomanip> #include <algorithm> #include <cmath> #include <string> #include <vector> #include <list> #include <queue> #include <stack> #incl…</stack></queue></list></vector></string></cmath></algorithm></iomanip></iterator></fstream></sstream></iostream></cstdio>
解法 すぎむさんのコードを参考にしました。木DP。 dp[u][x]:= 頂点uから生えるの最大の辺の長さがxとなる確率を保存しながらDFSして、作りうる辺の最大値がmax_lを超えないように計算していく。すると、確率の合計が「辺がmax_l以下になる確率」になる。こ…
解法 全探索 コード #include <cstdio> #include <cmath> #include <cstring> #include <ctime> #include <iostream> #include <algorithm> #include <set> #include <vector> #include <sstream> #include <typeinfo> #include <fstream> using namespace std; typedef long long ll; class DoubleOrOneEasy { public: int minimal…</fstream></typeinfo></sstream></vector></set></algorithm></iostream></ctime></cstring></cmath></cstdio>
問題 Twirling Robot | Aizu Online Judge 解法 位置・状態を頂点にしたグラフでダイクストラ。類題 kenkoooo.hatenablog.com コード #include <cstdio> #include <iostream> #include <sstream> #include <fstream> #include <iterator> #include <iomanip> #include <algorithm> #include <cmath> #include <string> #include <vector> #include <list> #…</list></vector></string></cmath></algorithm></iomanip></iterator></fstream></sstream></iostream></cstdio>
解法 二分探索 + UnionFind コード #include <cstdio> #include <cmath> #include <cstring> #include <ctime> #include <iostream> #include <algorithm> #include <set> #include <vector> #include <sstream> #include <typeinfo> #include <fstream> using namespace std; class UnionFind { public: UnionFind(const int &x) { …</fstream></typeinfo></sstream></vector></set></algorithm></iostream></ctime></cstring></cmath></cstdio>
問題 www.spoj.com 解説 ダイクストラライブラリ確認用 コード #include <cstdio> #include <iostream> #include <sstream> #include <fstream> #include <iterator> #include <iomanip> #include <algorithm> #include <cmath> #include <string> #include <vector> #include <list> #include <queue> #include <stack> #include <set> #include…</set></stack></queue></list></vector></string></cmath></algorithm></iomanip></iterator></fstream></sstream></iostream></cstdio>
問題 codeforces.com 解法 区間DP。@mayoko_ 申し訳ねぇ申し訳ねぇ… [l,r]で回文を挿入しまくって文字列を作りたいです. a[l]==a[i]のところがあったときそこを使うことにしたとき,[l+1,i-1]と[i+1,r]について考えればOKです 回文が始まるのは長さ1か長さ2…
問題 code-festival-2015-morning-hard.contest.atcoder.jp 解法 1回もひっくり返されない区間iが存在する。この時、区間i-jと区間i+jは、それぞれj回ひっくり返されるので、ある区間を選んだ時にひっくり返される合計の回数は累積和で予め計算しておくこと…
全完 Advent Calendar 2015 - Adventar 問題 abc015.contest.atcoder.jp A-C 略 D kenkoooo.hatenablog.com
問題 abc015.contest.atcoder.jp 解法 DP コード #include <cstdio> #include <iostream> #include <sstream> #include <fstream> #include <iomanip> #include <algorithm> #include <cmath> #include <string> #include <vector> #include <list> #include <queue> #include <stack> #include <set> #include <map> #include </map></set></stack></queue></list></vector></string></cmath></algorithm></iomanip></fstream></sstream></iostream></cstdio>
全完 Advent Calendar 2015 - Adventar 問題 code-thanks-festival-2015-open.contest.atcoder.jp A-F 略 G kenkoooo.hatenablog.com H kenkoooo.hatenablog.com
この記事は全完 Advent Calendar 2015 - Adventarの一部として書かれました。 問題 arc046.contest.atcoder.jp A 略 B 略 C kenkoooo.hatenablog.com D kenkoooo.hatenablog.com
問題 arc046.contest.atcoder.jp 解法 AtCoder Regular Contest 046 from AtCoder Inc. www.slideshare.net組み合わせを高速に求める数論ライブラリを手に入れた。 コード #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> using namespace std</map></set></queue></vector></algorithm></iostream>…
問題 arc046.contest.atcoder.jp 解法 AtCoder Regular Contest 046 from AtCoder Inc. www.slideshare.net コード #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> using namespace std; int main() { int N, M; cin >> N >> M; vector<int> men_o</int></map></set></queue></vector></algorithm></iostream>…
問題 code-thanks-festival-2015-open.contest.atcoder.jp 解法 ダイクストラやるだけ。 コード #include <cstdio> #include <cmath> #include <cstring> #include <ctime> #include <iostream> #include <algorithm> #include <set> #include <vector> #include <tuple> #include <sstream> #include <typeinfo> #include <fstream> #include…</fstream></typeinfo></sstream></tuple></vector></set></algorithm></iostream></ctime></cstring></cmath></cstdio>
問題 code-thanks-festival-2015-open.contest.atcoder.jp 解法 2次元の累積和をとる。こうすると長方形の中の累積和がO(1)で得られる。kenkoooo.hatenablog.com後はしゃくとりする。 コード ライブラリはmamekinさんのコピペです。 #include <cstdio> #include <iostream> #in</iostream></cstdio>…
この記事は退学 Advent Calendar 2015 - Adventarの一部として書かれました。 僕は大学院の修士課程を修士2年で退学したので、それについて書こうと思う。高校生の時は将来やりたいことがなかった(まともに考えていなかった)。強いて言えば、「ゼルダの伝説…