幅優先探索 あらかじめエラトステネスの篩で素数表を作っておく static const int pows[] = {1, 10, 100, 1000}; int change(int number, int digit, int insert) { switch (digit) { case 0: return number / 10 * 10 + insert; case 1: return number / 10…

幾何 接する点を固定してベクトルの足し算と引き算 typedef complex<double> P; void go(const P& a, const P& b, const P& c, const P& d) { if (abs(a - c) > EPS) { return; } assert(abs(a - d) > EPS); assert(abs(b - c) > EPS); assert(abs(b - d) > EPS); P </double>…

幾何 複素数ライブラリを使うと楽 角度でソートして尺取メソッド int main() { double r; for (int X, Y; cin >> X >> Y >> r && r >= 0.0; ) { int N; cin >> N; vector<double> angles; for (int n = 0; n < N; ++n) { int x, y; cin >> x >> y; x -= X; y -= Y; i</double>…

ダイクストラ法 時刻の概念があるのでノードに時刻を持たせる必要がある 実はUVA時代に生まれて初めて解けたダイクストラ法の問題だったりする struct Dic { map<string, int> m; int get(const string& s) { if (!m.count(s)) { const int index = m.size(); m[s] = inde</string,>…

ソート 残りは書いてある通りに実装 int main() { string key; while (getline(cin, key) && key != "THEEND") { vector<pair<char, int> > p; for (int i = 0; i < key.size(); ++i) { p.push_back(make_pair(key[i], i)); } stable_sort(p.begin(), p.end()); string body;</pair<char,>…

動的計画法 縦に何番目のキー、横に何番目の文字を取る 更新の条件式を工夫することで最後のキーに多く割り当てることが出来る ただし以下の解答は本当に条件を満たすかどうか未確認 static int dp[128][128]; static int previous[128][128]; int main() { …

比較関数を変えてnext_permutation()を呼び出す 比較関数を関数オブジェクト等にすればもっと綺麗だった int main() { int letterToIndex[0x100]; char indexToLetter[0x100]; for (char c = 'A'; c <= 'Z'; ++c) { letterToIndex[c] = (c - 'A') * 2; index…

最短経路問題として解いた 各ノードを数字、各エッジをx2,x3,x5に対応させる 小さな数字から順に展開していく int main() { set<ll> q; q.insert(1); vector<int> answer; while (answer.size() < 1500) { const ll value = *q.begin(); q.erase(q.begin()); answer.p</int></ll>…

深さ優先探索 タイルを二次元配列で持たせることができないのでハッシュマップを使って持たせている 時間がギリギリのためscanf()を使用した #ifdef _MSC_VER #include <hash_set> #include <hash_map> using namespace stdext; #else #include <ext/hash_set> #include <ext/hash_map> using namespace __gnu</ext/hash_map></ext/hash_set></hash_map></hash_set>…

C++ならnext_permutation()で終り int main() { string line; while (getline(cin, line) && line != "#") { if (next_permutation(line.begin(), line.end())) { cout << line << endl; } else { cout << "No Successor" << endl; } } }

全域最小木 プリム法またはクラスカル法が使える typedef double Weight; struct Edge { int src, dst; Weight weight; Edge(int src, int dst, Weight weight) : src(src), dst(dst), weight(weight) { } }; bool operator < (const Edge &e, const Edge &f…

最短経路の応用 エッジを更新するときにそれまでの最大容量と道の容量の高い方を伝搬する 上はダイクストラ法、下はワーシャルフロイド法の解答 struct Dic { map<string, int> m; int get(const string& s) { map<string, int>::iterator it = m.find(s); if (it != m.end()) { return</string,></string,>…

全点間最短距離 ダイクストラ法またはワーシャルフロイド法が使える static int g[128][128]; int main() { for (int N; cin >> N && N; ) { fill_n((int*)g, sizeof(g) / sizeof(g[0][0]), INT_MAX / 2); for (int n = 1; n <= N; ++n) { int M; cin >> M; …

シミュレーション 連想コンテナを使うのが定石 int main() { int n; cin >> n; string line; getline(cin, line); map<string, string> candidateToParty; for (int i = 0; i < n; ++i) { string candidate, party; getline(cin, candidate); getline(cin, party); candidate</string,>…

ダイクストラ法 一度訪れたintersectionは二度訪れる必要はない よって初めから行ける場所とそれ以外の場所でコストを変えてダイクストラをすれば良い int main() { for (int N, A, B; cin >> N >> A >> B; ) { int dp[128]; fill_n(dp, sizeof(dp) / sizeof…

動的計画法 Subset Sum Problemという有名問題らしい 横方向に桁数、縦方向にNの余剰を配置する REで通らなかったため、テーブルを埋め込んだ static const char* table[] = {"", "1", "10", "111", "100", "10", "1110", "1001", "1000", "111111111", "10"…

動的計画法 縦に車の数、横に2レーンのうち片方の車の総重量をとる DPが終わったらバックトラックして答えを求める static char dp[256][16 * 1024]; int main() { int length; cin >> length; length *= 100; vector<int> cars; dp[0][0] = -1; int bestCarIndex</int>…

並べかえられた文字列はソートして比較すると良い 短い文字列をソートしようとしてREをもらってしまった・・・ int main() { int n; cin >> n; for (int caseIndex = 1; caseIndex <= n; ++caseIndex) { map<string, int> dic; int m; cin >> m; for (int i = 0; i < m; +</string,>…

標準ライブラリと関数オブジェクトの使い方の練習問題として調度良いと思う データサイズの記述がないが、適当にやっても大丈夫だと思った const string toLower(const string& s) { string result; for (string::const_iterator it = s.begin(), itEnd = s.…

最悪ケースは下記のようなものだと思う ABCDEFGHIJKLMNOPQRST BCDEFGHIJKLMNOPQRSTU CDEFGHIJKLMNOPQRSTUV DEFGHIJKLMNOPQRSTUVW FGHIJKLMNOPQRSTUVWXY GHIJKLMNOPQRSTUVWXYZ HIJKLMNOPQRSTUVWXYZZ ... 2^26なので全探索しても通るはず static const int dx[…

最初に考えたときはナイーブな方法だと計算量が足りないなぁと延々と考えていた 繰り返される文字数kを全部回すとで通らない Nの約数の個数は個なので、Nの約数kだけ見ればとなり通る static char input[2 * 1024 * 1024]; int main() { while (scanf("%s", …

パスカルの三角形を書いたところ、REとなってしまった 入力が符号なし32ビット整数なのでintに入れたときに負の数になってしまったのだろう コンビネーションの式に変形して通した public class Main { public static void main(String[] args) { final Scan…

結局makeでコケた

cygwin + llvm-gccでSenna+MySQLを試そうとしている。Sennaのソースをダウンロードし./configureを使用としたところ、以下のようなエラーメッセージが出た。 configure: error: no acceptable ld found in $PATH適当にググッたところ、海外の掲示板でそれっ…