ダイクストラ法 時刻の概念があるのでノードに時刻を持たせる必要がある 実は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適当にググッたところ、海外の掲示板でそれっ…

貪欲法 葉巻が作れなくなるまで順番に作っていく 一本ずつシミュレーションするとTLE public class Main { public static void main(String[] args) { final Scanner cin = new Scanner(System.in); while (cin.hasNextInt()) { long n = cin.nextLong(); fi…

作られる数の集合を見ていくとパターンがあることに気付く JavaとCで速度がだいぶ違うが、そういうものなのだと思う public class Main { public static void main(String[] args) { final Scanner scanner = new Scanner(System.in); final int S = scanner…

metaballの値を順に足していき、総和の半分と等しくなればそれが答え import java.util.Scanner; public class Main { public static void main(String[] args) { final Scanner cin = new Scanner(System.in); for (int N; (N = cin.nextInt()) != 0;) { fi…

時間制限が緩いので条件を丁寧に書けば通る static int type[256]; bool check(const string& s) { vector<int> types; for (string::const_iterator it = s.begin(), itEnd = s.end(); it != itEnd; ++it) { types.push_back(type[*it]); } if (find(types.begin</int>…

三次元の幅優先探索 広げる方向は6方向 static const int dx[] = {1, -1, 0, 0, 0, 0}; static const int dy[] = {0, 0, 1, -1, 0, 0}; static const int dz[] = {0, 0, 0, 0, 1, -1}; int main() { for (int X, Y, Z; cin >> X >> Y >> Z && (X || Y || Z);…

300x300なので幅優先探索で十分 広げる方向は8方向 static const int dx[] = {2, 2, 1, 1, -1, -1, -2, -2}; static const int dy[] = {1, -1, 2, -2, 2, -2, 1, -1}; int main() { int numberOfTests; cin >> numberOfTests; for (int testIndex = 0; testI…

幅優先探索 広げる方向は8方向 static const int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1}; static const int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1}; int main() { for (int height, width; cin >> height >> width && (height || width); ) { static char maze[1…

数列の公式を当てはめるだけ 正負で式が微妙に変わる点に注意する 正負で分けずに解く方法もあったはず・・・ ll myabs(ll i) { return i >= 0 ? i : -i; } ll calc(ll i) { const ll sign = i / myabs(i); i = myabs(i); const ll value = (i * (i + 1)) / …

動的計画法 横方向でここからここまでの和というテーブルを作り、 縦方向でそれらを足し合わせる O(N^4) int main() { int N; scanf("%d", &N); for (int row = 0; row < N; ++row) { for (int column = 0; column < N; ++column) { int value; scanf("%d", …