2015-01-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年で退学したので、それについて書こうと思う。高校生の時は将来やりたいことがなかった(まともに考えていなかった)。強いて言えば、「ゼルダの伝説…
問題 code-festival-2015-qualb.contest.atcoder.jp 解法 塗り終わった区間の[始点, 終点]を保持しおく。塗るときに合併される区間がある場合は合併していけば、保持する情報も少なくて済む。これのイメージで解いた↓kenkoooo.hatenablog.com コード import …
解法 n-200からn+200までの数の約数を全列挙して殴る。 コード import java.util.Arrays; import java.util.HashSet; public class Procrastination { public long findFinalAssignee(long n) { HashSet<Long> divisers = new HashSet<>(); long min = Math.max(2,</long>…
解法 上の桁から貪欲に埋めていく。できるだけ小さい数字を入れてみて、残りの数字が条件を満たす最大のものだった時にN以上になるなら大丈夫。 コード public class FavouriteDigits { public long findNext(long lN, int dSmall, int cSmall, int dBig, in…
コード public class Spacetsk { private final int MOD = (int) 1e9 + 7; public int countsets(int L, int H, int K) { if (K == 1) { return ((L + 1) * (H + 1)) % MOD; } // パスカルの三角形 int N = Math.max(Math.max(L + 2, H + 2), K + 2); int[][…
解法 まだ顔として使われていない;の数と;_の数を保持したDPをすれば良い。 コード public class BearCries { private final int MOD = (int) 1e9 + 7; public int count(String string) { int N = string.length(); char[] m = string.toCharArray(); // i…
解法 Med、a/b=c/dという変形は考えたのにそれを使って単に舐めるだけでシンプルに解く方法に至らなかったのは酷い・・・それにしてもみんな早く解きすぎじゃないですかね— SKY/sky58 (@skyaozora) 2015, 10月 14 コード import java.util.HashMap; public c…
解法 ワーシャルフロイトで2点間の距離を出しておく。Aの各コマa_iについて、以下の操作によってゲームを終わらせるのに必要なターン数を出す。 必要なターン数movesを固定する。 a_i からmoves以内で行けて、かつ、Bの全ての駒がmoves以内で行けない頂点を…
解法 1文字取り出して別のところに挿入するとLCSが最大の文字列が生成される。数は大して大きくないので、全探索でいける。 コード import java.util.HashSet; public class Bracket107 { public int yetanother(String s) { int N = s.length(); HashSet<String> an</string>…
問題 TopCoder Statistics - Problem Statement コード public class AlternateColors2 { public long countWays(int n, int k) { long ans = 0; for (int red = 1; red <= k; red++) { int notred = k - red;// k番目の赤ボールが破壊される前に破壊される…
問題 TopCoder Statistics - Problem Statement コード public class XorBoard { private final int MOD = 555555555; public int count(int H, int W, int Rcount, int Ccount, int S) { // パスカルの三角形 int N = Math.max(W, H) * 2; int[][] nCm = ne…